Crate broadword

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.

Constants

H8

Has the highest bit of every byte set: 0x8080_8080_8080_8080.

L8

Has the lowest bit of every byte set: 0x0101_0101_0101_0101.

Functions

count_ones

Counts the number of ones in a u64.

i_le8

Parallel ≤, treating a u64 as a vector of 8 i8s.

select1

Finds the index of the rth one bit in x.

select1_raw

Finds the index of the rth one bit in x, returning 72 when not found.

u_le8

Parallel ≤, treating a u64 as a vector of 8 u8s.

u_nz8

Parallel >0, treating a u64 as a vector of 8 u8s.