bit_arch 0.1.2

High-level zero-cost bit manipulation
Documentation

bit_arch

Fast and efficient architecture-tuned bit operations.

Features

This crate implements safe wrappers around x86 instructions.

let int1_mask = 0b0011_1110; // saves 5 bits of int1
let int1_val = 37_u32; // 0b0010_0101 or 0b0010_0100 | 1

let int2_mask = 0b0000_0111;
let int2_val = 5_u32; // 0b0000_0101

let int1_packed = bit_arch::extract(int1_val, int1_mask);
let int2_packed = bit_arch::extract(int2_val, int2_mask);

// pack two u32s into one u8
let packed8 = (int1_packed | (int2_packed << 5)) as u8;

// do something with that like copy it into a struct field

// deposit only works on u32/u64
let packed32 = packed8 as u32;

// `| 1` recovers the one bit we ignored at the start of int1_mask
let extracted_int1 = bit_arch::deposit(packed32, int1_mask) | 1;
let extracted_int2 = bit_arch::deposit(packed32 >> 5, int2_mask);

assert_eq!(extracted_int1, int1_val);
assert_eq!(extracted_int2, int2_val);

It may look like just some bit shifts, but it's much more than that. Mask can be anything at all. Maybe you want to ignore bits 2, 7, and 31 of a u64 but keep the rest. That's not even the best part though; it's FAST.

Still not fast enough? You need to go a level lower. Below the abstract API of bit_arch is bit_arch::arch. Everyone knows double the "arch"es means double the performance:

let mask = 0xAC5;
let initial_val = 0xABC;

let packed = bit_arch::arch::extract_u32(initial_val, mask);
let low_contiguous = bit_arch::arch::extract_bitfield_u32(packed, 2, 7);

let lowest_clear = bit_arch::arch::isolate_lowest_clear_u32(initial_val);
let new_mask = bit_arch::arch::trailing_one_mask_u32(lowest_clear);

let new_val = bit_arch::arch::deposit_u32(low_contiguous, new_mask);
assert_eq!(new_val, 14);

There are also four optional features:

  • dynamic: Enables dynamic operation dispatch. This should only be used for testing or debugging! Using it in production will severely hurt performance. It also requires std.
  • popcnt64: Slightly lower level but much simpler. If this is enabled, the API will introduce an as u64 inside count_ones_u64 and count_ones::<u64>. It could hurt performance, but copying a few bytes isn't too expensive. This is enabled by default to promote consistency and stability in the API.
  • popcnt_uint: Also low level. Basically, it means the popcnt instruction is guaranteed to be used on supported devices in count_ones, but at the cost of casting between types. It's often better to leave this disabled because the compiler will often optimize it anyway. This has almost no effect on performance, but requires briny.
  • signed: Support for signed integers outside intrinsics. This adds reinterpretation overhead, but this is usually zero-cost and requires briny.

By default, this crate has no dependencies.

Performance

Assembly output has been carefully analyzed and is guaranteed to include the desired instructions. These instructions are listed below. Regardless, compiling with target-cpu=native has proven to greatly improved performance. Dropping from ~22.839 ns to ~521.33 ps for extract/deposit (or pext/pdep) roundtrips. That's a 44x improvement!

Architecture-Specific Details

Particularly operations in BMI 1/2, TBM, and ABM extensions. It implements most operations through a safe API. All supported operations are listed below:

x86_64 Target Feature bit_arch::arch
_andn_* bmi1 inverted_and_*
_bextr_* bmi1, tbm extract_bitfield_*
_blci_* tbm isolate_lowest_clear_*
_blcic_* tbm set_lowest_clear_*
_blcs_* tbm set_lowest_zero_*
_blsfill_* tbm from_lowest_set_*
_blsi_* bmi1 isolate_lowest_set_*
_blsic_* tbm complement_lowest_set_*
_blsmsk_* bmi1 through_lowest_set_*
_blsr_* bmi1 clear_lowest_set_*
_bzhi_* bmi2 zero_upper_*
_lzcnt_* abm leading_zeros_*
_pdep_* bmi2 deposit_*
_pext_* bmi2 extract_*
_popcnt* abm count_ones_**
_t1mskc_* tbm trailing_one_mask_*
_tzcnt_* bmi1 trailing_zeros_*
_tzmskc_* tbm trailing_zero_mask_*

[*] count_ones only uses the corresponding _popcnt* intrinsics if the popcnt_uint feature is enabled.

All functions defined in bit_arch::arch are completely safe and have optimized fallback paths. Despite this, there is a preferred higher level API that offers the same level of performance, but is generic over the type u32 or u64.

There are also more intrinsics listed below, but these don't have a high-level API in the crate. They may never get a abstraction either. They will recieve updates and will be maintained.

x86_64 Target Feature bit_arch::arch
_bextr2_* bmi1, tbm extract_bitfield_control_*
_bswap* None swap_bytes_*
bittest* None bit_test_*
bittestandset* None bit_test_set_*
bittestandreset* None bit_test_reset_*
bittestandcomplement* None bit_test_complement_*

trailing_zeros also has an intrinsic only accessible from arch, trailing_zeros_u16.