Bittricks

A c library with cross-platform optimised support for bit operations.

Currently:

• Parallel bit extract (PEXT)
• Parallel bit deposit (PDEP)

Why?

PEXT and PDEP are truly amazing operations with a ton of uses, but they're not available everywhere and actually using them while retaining portability is a bit involved.

Adding to the fun is that for years AMD shipped versions of them which were unreasonably slow (up to 290 cycles!), to the degree that we could polyfill them quicker than using the native implementation, even with the fully portable algorithm!

We deal with all the gotchas and provide an easy way to use these amazing operations without having to spend months working out all the details.

How does it work

Basically, it's a normal library. We produce two artifacts:

1. The library, libbittricks.so
2. The header, bittricks.h

Some platforms have multiple versions of the code to take advantage of various ISA extensions:

• x86-64/amd64 (BMI2, PCLMUL)
• aarch64 (SVE2 BITPERM, SVE2 AES, CRYPTO)

For these platforms, we switch implementations according to what the cpu is detected as supporting on startup. We have two mechanisms for this:

• When IFUNCs are supported, we resolve the best version at dynamic link time.
• Otherwise we use a switchy implementation and rely on branch prediction to make it fast.

For other targets, we ship a portable implementations.

Build

We use meson to build. Start by creating a build directory. This is analogous to the configure step in autotools, where you can provide things like install prefixes.

meson setup build

Change into that directory and compile:

cd build
meson compile

Run the tests:

meson test

And finally install:

meson install

Algorithm details

When direct instructions are unavailable or undesirable, we use a bitwise prefix popcounting approach which I copied from zp7.

8-64 bit integers

These are unfortunately handled differently depending on the capabilities of the platform.

When BMI2 (AMD64) is fast or BITPERM (AARCH64) is present, we have fast 32 and 64-bit versions of PEXT and PDEP. 8 and 16-bit versions are provided based on the 32-bit versions with casting. This is a bit annoying with BITPERM as we're working with an array

The other implementations (the polyfills) use a variable number of prefix popcounting rounds according to the size of the integer, scaling in duration according to the log2 size of the integer.

Arrays

When BMI2 (AMD64) is fast, we run up to 12 per iteration to try and get the throughput up (Zen 5 can chew through these at 3/0.3)

When BITPERM (AARCH64) is present, we perform it across a vector register at a time. For 64 and 32 bit integers, there are native instructions. For 16 bit integers, we run the 32 bit instructions twice per register. For 8 bit integers it's much the same, but four times per register.

Otherwise, it's a simple loop.

Performance

Here's a benchmark run on my slightly fucked zen2 whose absolute numbers you should probably not trust, but which is fine for order of magnitude. You'll notice that zen2 is one of those platforms where the native instructions are unreasonably slow. That's how I ended up writing this library...

estimated overhead 2.190 msec ( 2.190 nsec per iteration )
pext: zp7 pclmul 9.809 msec ( 9.809 nsec per iteration )
pext: zp7 portable 22.649 msec ( 22.649 nsec per iteration )
pext: bmi2 native 50.927 msec ( 50.927 nsec per iteration )
pdep: zp7 clmul bmi2 11.473 msec ( 11.473 nsec per iteration )
pdep: zp7 clmul 11.693 msec ( 11.693 nsec per iteration )
pdep: zp7 portable 25.679 msec ( 25.679 nsec per iteration )
pdep: bmi2 native 51.825 msec ( 51.825 nsec per iteration )

On AMD64 platforms without this bug, the native should be 3 cycles plus a few for the wrapping.

Copyright and License

Derived from ZP7 (Zach's Peppy Parallel-Prefix-Popcountin' PEXT/PDEP Polyfill) https://github.com/zwegner/zp7/blob/master/zp7.c

Adapted into a polyfill library by James Laver

Copyright (c) 2026 James Laver, 2020 Zach Wegner

Licensed under the terms of the MIT License:

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.