broadword-rs: broadword algorithms

This crate includes broadword algorithms that treat a u64 as a parallel vector of eight u8s or i8s, as well as population count and select algorithms.

Usage

It’s on crates.io, so you can add

[dependencies]
broadword = "0.2.2"

to your Cargo.toml and

extern crate broadword;

to your crate root.

lib.rs:

Broadword operations treat a u64 as a parallel vector of eight u8s or i8s. This module also provides a population count function count_ones and a select function select1.

The algorithms here are from Sebastiano Vigna, “Broadword Implementation of Rank/Select Queries,” but with several changes from that work:

• Vigna uses a 17-digit (68-bit) constant “0x0F0F0F0F0F0F0F0F0.” I believe the correct constant is these 64 bits: 0x0F0F_0F0F_0F0F_0F0F.

• Arithmetic operations are assumed to wrap on overflow. If this were not the case, Algorithm 1 (count_ones) would overflow its last line, when multiplying by L₈.

• Line 2 of Algorithm 2 should read

  s = (s & 0x3333_3333_3333_3333) + ((s >> 2) & 0x3333_3333_3333_3333);
  

  In the paper, the shifted s appears as x.