BitVec – Managing memory bit by bit

Crate Documentation License Continuous Integration Code Coverage Crate Downloads

This crate provides packed bit-level analogues to [T] and Vec<T>. The slice type BitSlice and the vector type BitVec allow bitwise access to a region of memory in any endian ordering or underlying primitive type. This permits construction of space-efficient sets or fine-grained control over the values in a region of memory.

BitVec is a strict expansion of BitSlice to include allocation management. Since BitVec is shorter to type, the rest of this document will use it by default, and mark out sections that apply only to the vector type and not to the slice type. Unless marked, assume that the text applies to both.

BitVec is generic over an ordering cursor, using the trait Cursor, and the primitive type, using the trait Bits. This means that BitVec structures can be built with a great deal of flexibility over how they manage their memory and translate between the in-memory representation and their semantic contents.

BitVec acts as closely to a standard Vec as possible, and can be assumed by default to be what a Vec<u1> would be if such a type were possible to express in Rust. It has stack semantics, in that push and pop operations take place only on one end of the BitVec’s buffer. It supports iteration, bitwise operations, and rendering for Display and Debug.

How Is This Different Than the bit_vec Crate

Why Would You Use This

Usage

Minimum Rust Version: 1.31.0

I wrote this crate because I was unhappy with the other bit-vector crates available. I specifically need to manage raw memory in bit-level precision, and this is not a behavior pattern the other bit-vector crates made easily available to me. This served as the guiding star for my development process on this crate, and remains the crate’s primary goal.

To this end, the default type parameters for the BitVec type use u8 as the storage primitive and use big-endian ordering of bits: the forwards direction is from MSb to LSb, and the backwards direction is from LSb to MSb.

To use this crate, you need to depend on it in Cargo.toml:

toml [dependencies] bitvec = "0.10"

and include it in your crate root src/main.rs or src/lib.rs:

```rust,no-run extern crate bitvec;

use bitvec::*; ```

This imports the following symbols:

BitVec has the same API as Vec, and should be easy to use.

The bitvec! macro requires type information as its first two arguments. Because macros do not have access to the type checker, this currently only accepts the literal tokens BigEndian or LittleEndian as the first argument, one of the four unsigned integer primitives as the second argument, and then as many values as you wish to insert into the BitVec. It accepts any integer value, and maps them to bits by comparing against 0. 0 becomes 0 and any other integer, whether it is odd or not, becomes 1. While the syntax is loose, you should only use 0 and 1 to fill the macro, for readability and lack of surprise.

no_std

This crate can be used in #![no_std] libraries, by disabling the default feature set. In your Cargo.toml, write:

toml [dependencies] bitvec = { version = "0.10", default-features = false }

or

toml [dependencies.bitvec] version = "0.10" default-features = false

This turns off the standard library imports and all usage of dynamic memory allocation. Without an allocator, the bitvec! macro and the BitVec type are both disable and removed from the library, leaving only the BitSlice type.

To use bitvec in a #![no_std] environment that does have an allocator, re-enable the alloc feature, like so:

toml [dependencies.bitvec] version = "0.10" default-features = false features = ["alloc"]

The alloc feature restores bitvec! and BitVec, as well as the BitSlice interoperability with BitVec. The only difference between alloc and std is the presence of the standard library façade and runtime support.

The std feature turns on alloc, so using this crate without any feature flags or by explicitly enabling the std feature will enable full functionality.

Example

```rust extern crate bitvec;

use bitvec::*;

use std::iter::repeat;

fn main() { let mut bv = bitvec![BigEndian, u8; 0, 1, 0, 1]; bv.reserve(8); bv.extend(repeat(false).take(4).chain(repeat(true).take(4)));

//  Memory access
assert_eq!(bv.as_slice(), &[0b0101_0000, 0b1111_0000]);
//                 index 0 -^               ^- index 11
assert_eq!(bv.len(), 12);
assert!(bv.capacity() >= 16);

//  Set operations
bv &= repeat(true);
bv = bv | repeat(false);
bv ^= repeat(true);
bv = !bv;

//  Arithmetic operations
let one = bitvec![1];
bv += one.clone();
assert_eq!(bv.as_slice(), &[0b0101_0001, 0b0000_0000]);
bv -= one.clone();
assert_eq!(bv.as_slice(), &[0b0101_0000, 0b1111_0000]);

//  Borrowing iteration
let mut iter = bv.iter();
//  index 0
assert_eq!(iter.next().unwrap(), false);
//  index 11
assert_eq!(iter.next_back().unwrap(), true);
assert_eq!(iter.len(), 10);

} ```

Immutable and mutable access to the underlying memory is provided by the AsRef and AsMut implementations, so the BitVec can be readily passed to transport functions.

BitVec implements Borrow down to BitSlice, and BitSlice implements ToOwned up to BitVec, so they can be used in a Cow or wherever this API is desired. Any case where a Vec/[T] pair cannot be replaced with a BitVec/BitSlice pair is a bug in this library, and a bug report is appropriate.

BitVec can relinquish its owned memory as a Box<[T]> via the .into_boxed_slice() method, and BitSlice can relinquish access to its memory simply by going out of scope.

Planned Features

Contributions of items in this list are absolutely welcome! Contributions of other features are also welcome, but I’ll have to be sold on them.