I’ve just published the first version of the bitwise crate !
In a nutshell, it relies on the bitintr crate to implement higher-level bitwise manipulation algorithms. Currently it only implement algorithms for single words (words slices will come).
There are many algorithms already. If I had to mention just one, it would be the Morton Index Encoding/Decoding algorithm, since it is the fastest implementation of it that I’ve found in native Rust. It uses BMI2.0 instructions (pdep/pext) when available on the target (Intel Haswell / AVX2 and up) and a cache friendly “magicbits” method otherwise. Other algorithms are also available with different trade-offs, e.g.,. the LUT algorithm uses more cache to load a look-up table but can be faster in some platforms, and I’ll probably add sLUT (skewed LUT) at some point with uses even more cache and can be even faster. They are all still slower than using BMI 2.0 though.
Do you like manipulating bits? Do you think code that does is magical? Or maybe you like solving puzzles, playing games (sudoku, chess, go…), or squeezing out the maximum performance out of your CPU?
Well I have good news for you!
The issue tracker has a Roadmap to 1.0 which mentions a lot of fun to implement algorithms, most of which have a link to a description or other implementations! The acknowledgements section in the readme also mentions lots of sources (Hackers Delight ) with many more algorithms that are really fun to implement!
And there are also the main things missing (API wise) that I want to get done before 1.0:
- support stable Rust (haven’t figured out a way to avoid specialization here),
- implement SWAR (Simd Within A Register) algorithms for the common operations [*],
- implement algorithms on word slices by combining the simd and the bitintr crates,
- support 128 bit integers.
Pull-requests are really appreciated!
[*] Think of SWAR as storing e.g. 4xu16 inside a single u64, and wanting to do “element-wise” arithmetic/bitwise operations (addition/substraction/…bitwise xor/… with wrapping/saturating/… arithmetic…) and reductions.