[Dedication](dedication.md)

1. [Introduction](introduction.md)

1. [Data Structures](data-structures.md)

1. [`BitSlice`](data-structures/bitslice.md)

1. [`BitArray`](data-structures/bitarray.md)

1. [`BitVec` and `BitBox`](data-structures/bitvec.md)

1. [Type Parameters](type-parameters.md)

1. [`BitOrder`](type-parameters/bitorder.md)

1. [`BitStore`](type-parameters/bitstore.md)

1. [Practical Use](practical-use.md)

1. [`bool` Collections](practical-use/collections.md)

1. [C-Style Bitfields](practical-use/bitfields.md)

1. [Memory Model](memory-model.md)

1. [Pointer Encoding](pointer-encoding.md)

`bitvec` is unique among its class of libraries in that it distinguishes

indexing within a sequence versus selecting a bit within a memory element. Users

are allowed to choose, or even create, a function that transforms an abstract

index into an actual selection mask. To make matters even more complex, users

are also allowed to choose which of the fundamental register types will be used

as the base unit of memory, with no intermediate subdivision between that type

and the individual bits.

This is expressed through the pair of type parameters

`<O: BitOrder, T: BitStore>` on all `bitvec` data structures. The correct choice

of parameters depends on your use case. This chapter explains how each

combination translates to real memory.

`bitvec` provides three ordering names in its prelude: `LocalBits`, `Lsb0`, and

`Msb0`.

The `Lsb0` type uses the function `selector = 1 << index`, and is the typical

behavior of other bit-sequence libraries and of C-style structural bitfields on

most architectures. Notably, it is *not* the behavior of many I/O protocols,

which is why `bitvec` allows substitution.

The `Msb0` type uses the function `selector = !(!0 >> 1) >> index`, and is the

behavior used by I/O protocols such as TCP and IP, as well as C-style structural

bitfields on targets with big-endian byte ordering, such as SPARCv8.

If you do not have an explicit need for memory layout, you should probably not

use this ordering: its base constant is one of `0x80`, `0x80_00`,

`0x8000_0000`, or `0x8000_0000__0000_0000`, while the `Lsb0` base constant is

uniformly `1`. When used with register types wider than a byte, the base

constant probably will not be inlined into the instruction as an immediate

value, but will rather be computed at runtime as `(1 << reg_width) >> index`.

The `LocalBits` name aliases to either `Lsb0` or `Msb0`, depending on what C

compilers targeting your architecture would probably select when performing

structural bitfield layout. This is the default parameter used in `bitvec` types

that do not explicitly specify an ordering.

Unsigned integers that roughly correspond to ordinary (non-vector) CPU registers

on your target architecture implement `BitStore`.

This is not *quite* true: the actual **requirement** is that integers

implementing `BitStore` must always be aligned to their size. This is not the

case for `u64` on 32-bit `x86`, architectures (see the Rust [layout docs]).

In addition, `BitStore` is implemented on `Cell` wrappers of the integers, and

their atomic variants. This is used to provide alias-aware memory access, as

most architectures do not support modifying a single bit within a memory address

without locking the entire referent element.

`bitvec` is primarily developed and tested on `x86_64`, and may be incorrect on

embedded architectures. Please file an issue if you encounter errors involving

this trait.

The `BitOrder` and `BitStore` traits combine with your target architecture’s

byte-ordering of register elements to create a matrix of memory traversals. This

matrix informs what is the appropriate choice of parameters to use for your

program whenever you are using `bitvec` for precise memory control rather than

solely for a compact `usize`-to-`bool` data collection.

The tables below list bytes of a memory address space with addresses increasing

to the right, and the bits *within* those bytes with numeric significance

decreasing to the right. This is the ordering used in most debug-printing of

memory, so hopefully the table contents should match up with your prior

experience viewing memory bytes.

The `L` and `M` indicate the `Lsb0` and `Msb0` ordering parameters,

respectively, and `XX` indicates that the row matches all register types.

Within each row, traversal begins at zero and follows the arrows to each

successive step. Boundaries between registers are marked with a column;

boundaries between bytes within the same register are marked with a space.

On little-endian machines, the least-significant *byte* of a register type is

stored at the lowest memory address, and each byte higher is one step more

numerically significant than the last.

On big-endian machines, the most-significant *byte* of a register type is stored

at the lowest memory address, and each byte higher is one step less numerically

signifcant than the last.

[layout docs]: https://doc.rust-lang.org/reference/type-layout.html#primitive-data-layout

`bitvec`’s primary exports are four data structures: [`BitSlice`], [`BitArray`],

[`BitBox`], and [`BitVec`]. These correspond to the [`[bool]`][slice],

[`[bool; N]`][array], [`Box<[bool]>`][boxed], and [`Vec<bool>`] types in the

Rust standard libraries. Unlike the Rust types, the `bitvec` types are not

composable, and cannot be mixed with any other types, including pointers in the

standard library.

The `bitvec` types implement the APIs of their standard-library counterparts to

the fullest extent possible. The only missing feature is currently

`IndexMut<usize>`, preventing `collection[index] = bit;` assignment. This means

that, for users looking for compact `usize => bool` collections, substituting

types in your project codebase ought to be enough to make your project Just

Work™️.

It is the fact that `BitSlice` acts exactly like `[bool]`, and can only be used

through `&BitSlice` and `&mut BitSlice` references, that makes `bitvec` work. No

other Rust library has this capability.

Before we explore the data structures in more detail, there are three caveats I

must provide:

1. `bitvec` uses an opaque, custom, pointer representation for everything except

`BitArray`. You may not inspect or modify this pointer. You may not use it as

a type or value parameter in any other types or functions. You will break

your program if you try.

`bitvec` ensures that this pointer encoding does not fail the compiler and

language requirements for reference correctness. The rules used to do so are

internal to the crate, and will not be present outside it. `bitvec` pointers

are perfectly safe to use, as long as you treat them as completely opaque and

use *only* the interfaces provided.

1. These structures all have two type parameters, `<O: BitOrder, T: BitStore>`.

These parameters are described in the next chapter. They govern the in-memory

representation of data storage, but are not relevant to the general use of the

handle types.

1. `bitvec` trades an increased memory space efficiency for decreased

instruction size and speed efficiency. The compiler *may* optimize some of

the costs away, but `bitvec` structures are not free to use. The “zero-cost”

of the `bitvec` abstraction is that you cannot write a better bitset, and

*not* that it is equal to an ordinary `bool` sequence.

Now that the disclaimers are over, we can talk about how the types actually

work.

[`BitArray`]: https://docs.rs/bitvec/latest/bitvec/array/struct.BitArray.html "BitArray API documentation"

[`BitBox`]: https://docs.rs/bitvec/latest/bitvec/boxed/struct.BitBox.html "BitBox API documentation"

[`BitSlice`]: https://docs.rs/bitvec/latest/bitvec/slice/struct.BitSlice.html "BitSlice API documentation"

[`BitVec`]: https://docs.rs/bitvec/latest/bitvec/vec/struct.BitVec.html "BitVec API documentation"

[`Vec<bool>`]: https://doc.rust-lang.org/stable/alloc/vec/struct.Vec.html "Vec API documentation"

[`std::bitset<N>`]: https://en.cppreference.com/w/cpp/utility/bitset "C++ std::bitset documentation"

[`std::vector<bool>`]: https://en.cppreference.com/w/cpp/container/vector_bool "C++ std::vector<bool> documentation"

[array]: https://doc.rust-lang.org/stable/std/primitive.array.html "array API documentation"

[boxed]: https://doc.rust-lang.org/stable/alloc/boxed/struct.Boxed.html "Box API documentation"

[slice]: https://doc.rust-lang.org/stable/std/primitive.slice.html "slice API documentation"

While `BitSlice` describes a region of borrowed data, `BitArray` provides a

container that can hold and manage such a region.

It is most comparable to the C++ type [`std::bitset<N>`]. Unfortunately, the

Rust support for type-level integers is still experimental, so it is unable to

take the length of the `BitSlice` it contains as a type parameter. Instead, it

must take the entire region it contains as a type parameter. The full type

declaration is

As described in the [previous chapter], the `BitView` trait is implemented on

the unsigned integers, and on arrays of them. Currently, array support is

limited to arrays up to and including 32 elements long; as Rust type-level

integers mature, this will grow to include all arrays.

This array dereferences to a `BitSlice` region over its entire length. It does

not currently permit shortening its `BitSlice` from either end. If this is a

behavior you want, please file an issue.

The `::zeroed` function constructs a new `BitArray` with its memory completely

zeroed. The `::new` function wraps an existing element or array into a

`BitArray`. In addition, the macro constructor `bitarr!` takes the exact same

arguments as the `bits!` constructor, except that it returns an array directly

rather than a reference to a `static` buffer.

In addition, `BitArray` structures and references can be constructed from

`&BitSlice` references using the `TryFrom` trait, just as arrays can be

constructed in the standard library.

Once constructed, `BitArray` offers the `.as_bitslice` and `.as_mut_bitslice`

explicit methods, as well as all the standard traits, to borrow its data as a

`BitSlice`. The array has no functionality of its own, and serves only to own a

region used as a`BitSlice`.

Once you are done using `BitSlice` to manipulate the array, you can remove the

array with `.unwrap` and regain the `V` memory within. This name is subject to

change if users are sufficiently unhappy with it.

That’s everything that the array does! Like regular arrays, it is useful

primarily for its ability to move memory through a program, and has essentially

no behavior in its own right. It is useful for programs that do not have access

to a dynamic allocator, and do not wish to use `static` buffers. However, if you

do have access to an allocator, you will probably prefer to use `BitVec`

instead.

[previous chapter]: ./bitslice.html "BitSlice region"

[`std::bitset<N>`]: https://en.cppreference.com/w/cpp/utility/bitset "C++ std::bitset documentation"