gnzlbg / bitwise Goto Github PK

Implement:

• find_first_bit_set, find first one, bit scan forward. Instructions: FFS, BSF.
• find_first_bit_unset, find first zero. Instructions: FFZ.

Right now the feature flag bmi2 must be explicitly passed to the library to enable the BMI2.0 instruction set. It would be better to enable this depending on the architecture.

Blocked on rust-lang/rust#30462 .

Current Morton index encoding/decoding algorithms use parallel_bit_deposit/parallel_bit_extract which are very fast (4cycles) if the architecture supports the BMI2.0 instruction set.

However, if the architecture doesn't support BMI2.0 we are falling back to a software emulation for the parallel_bit_deposit/extract algorithms. For computing morton codes there are faster methods available:

• libmorton and blog post,
• Morton encoding/decoding through bit interleaving: Implementations,
• Decoding morton codes,
• Bit Twiddling Hacks.

All the algorithms have been given readable names that clearly state what they do. Some of the algorithms map to hardware intrinsics and other names that are also commonly in use. It should be easy to find any algorithm using any of its common names.

i128 and u128 should implement Word as well. I need this in an application of morton encoding where I need more than 21 bits of precision on each axis. In the meantime I will use two u64, but it would be nice if we could have support for general bitwise operations on the 128-bit types as well. Is there any interest in this?

Hey, any chance you could publish the latest state to crates.io? Thank you

The command llc -mattr=help can be used to list all target features! The following features are relevant for bitwise manipulation:

• bmi
• bm2
• sse4.2
• sse4a
• tbm
• abm

These tooling issues should be fixed before 1.0:

• fix travis-cargo doc upload #14
• use quick-check to test 64-bit integers
  • enable quick-check
  • use it to test the algorithms
• run the sanitizers on travis (address, memory, and leak, thread sanitizer doesn't make much sense yet)
• run valgrind on travis
• fuzz the library using cargo-fuzz
• evaluate using bitintr asm.py to test the generated assembly of some algorithms on some platforms (as long as we rely on bitintr we should be fine though).

The following benchmarks are important:

• Algorithms that are part of the Bit Manipulation instruction sets (to be sure that the intrinsics are faster than the emulation layers and to be able to improve the emulation layers over time).
• Morton indices.

State and assert pre-conditions on library functions using debug_assert!.

Problem:
error: unrecognized platform-specific intrinsic function: x86_bmi_bextr_32
src/x86/intrinsics/bmi/bextr.rs:11:9
|
11 | fn x86_bmi_bextr_32(x: u32, y: u32) -> u32;

Solution: update Cargo.toml to

[dependencies]
bitintr = "0.3"

Implement morton index algorithms to interleave/de-interleave morton coordinates in integers.

This is a mind dump of what I'd like to see in for 1.0, API wise, functionality wise, and algorithmic wise.

• The big goals for 1.0 are:
  • API for Word algorithms.
  • API for SWAR algorithms.
  • API for algorithms on Word slices.
  • i128/u128 support.
  • Support stable Rust.

• The word algorithms I would like to see in the library for 1.0 are:
  • Basic algorithms from N3864 / stdcxx-bitops.
  • Morton indices algorithms:
    • BMI2.0
    • Magicbits
    • LUT
    • sLUT
  • Greatest common divisor: #11.
  • Hamming distance: #2 .
  • Swap by primitives.
  • parallel_bits_deposit/extract-right and extract_bits_right (see compress and expand.
  • Butterfly network.
  • sheep-and-goats
  • deposit/extract flip variants (left and right).
  • omega-flip network.
  • sign extend
  • gray code (and inverse)
  • is x a contiguous sequence of 1 bits ?

• The subword algorithms (SWAR) I would like to see in the library for 1.0 are:
  • broadcast/deposit all: fill every subword with value
  • gather/extract: extract the value of a subword
  • broadcast/deposit: fill subword i with value
  • count_ones/count_zeros/ leading ones/ leading zeros / trailing ones / trailing zeros in subword i
  • does one subword contain the value zero ?
  • parity of the subword i
  • binary operations for the i-th subword values (and for all values) of the words x and y, with/without wrapping/saturation, signed/unsigned, etc: : : add/sub/mul/div/mod ...
  • unary operations for the i-th subword values (and for all values) of the word x: neg, increment, decrement, abs, ..
  • logical operations for the i-th subword values (and for all values) of the words x and y: eq, neq, leq,geq, le, ge,
  • bitwise operations for the i-th subword values (and for all values) of the word x: shifts, and/or/xor/rotation...
  • "horizontal" binary operations (for adjacent subwords in a word): add/sub/mul/...

• The word slices algorithms I would like to see in the library for 1.0 are:
  • count non-zero/zero bytes (use the byteorder crate for this?)
  • bit matrices: inversion, transposition

Use intrinsics from the llvmint package.

• parallel_bits_deposit/extract => bmi_pdep_32/64 and bmi_pext_32/64 (BMI 2.0),
• leading_zeros => LLVM's __lzcnt16/32/u32/64/u64 (blocked on huonw/llvmint#3) (BMI 1.0, ABM),
• count_ones => LLVM's _popcnt_32/u32/64/u64 (blocked on huonw/llvmint#4) (SSE4.2, ABM),
• trailing_zeros => tzcnt (BMI 1.0), (blocked on huonw/llvmint#5 and rust-lang/rust#34382)
• reset_bits_geq(starting bit) => bmi_bzhi_32/64 (BMI 1.0)
• reset_least_significant_one => BLSR (BMI 1.0)
• Logical and not ~x & y (BMI 1.0) (TODO: implement algorithm)
• Bit field extract (with register): (src >> start) & ((1 << len)-1) => bmi_bextr_32/64 (BMI 1.0)
• isolate_least_significant_one: Extract lowest set isolated bit: x & -x (blocked on "not available in llvmint) (BMI 1.0)
• mask_trailing_zeros_and_least_significant_one: Get mask up to lowest set bit: x ^ (x - 1) (blocked on "not available in llvmint") (BMI 1.0)