4 releases

Uses old Rust 2015

0.2.2 May 30, 2018
0.2.1 Apr 1, 2018
0.2.0 Apr 1, 2018
0.1.0 Apr 1, 2018

#1562 in Algorithms

MIT/Apache

14KB
244 lines

broadword-rs: broadword algorithms

Build Status Crates.io License: MIT License: Apache 2.0

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.

No runtime deps