# Bit-Addressable Memory A slice of individual bits, anywhere in memory. `BitSlice` is an unsized region type; you interact with it through `&BitSlice` and `&mut BitSlice` references, which work exactly like all other Rust references. As with the standard slice’s relationship to arrays and vectors, this is `bitvec`’s primary working type, but you will probably hold it through one of the provided [`BitArray`], [`BitBox`], or [`BitVec`] containers. `BitSlice` is conceptually a `[bool]` slice, and provides a nearly complete mirror of `[bool]`’s API. Every bit-vector crate can give you an opaque type that hides shift/mask calculations from you. `BitSlice` does far more than this: it offers you the full Rust guarantees about reference behavior, including lifetime tracking, mutability and aliasing awareness, and explicit memory control, *as well as* the full set of tools and APIs available to the standard `[bool]` slice type. `BitSlice` can arbitrarily split and subslice, just like `[bool]`. You can write a linear consuming function and keep the patterns you already know. For example, to trim all the bits off either edge that match a condition, you could write ```rust use bitvec::prelude::*; fn trim( bits: &BitSlice, to_trim: bool, ) -> &BitSlice { let stop = |b: bool| b != to_trim; let front = bits.iter() .by_vals() .position(stop) .unwrap_or(0); let back = bits.iter() .by_vals() .rposition(stop) .map_or(0, |p| p + 1); &bits[front .. back] } # assert_eq!(trim(bits![0, 0, 1, 1, 0, 1, 0], false), bits![1, 1, 0, 1]); ``` to get behavior something like `trim(&BitSlice[0, 0, 1, 1, 0, 1, 0], false) == &BitSlice[1, 1, 0, 1]`. ## Documentation All APIs that mirror something in the standard library will have an `Original` section linking to the corresponding item. All APIs that have a different signature or behavior than the original will have an `API Differences` section explaining what has changed, and how to adapt your existing code to the change. These sections look like this: ## Original [`[bool]`](https://doc.rust-lang.org/stable/std/primitive.slice.html) ## API Differences The slice type `[bool]` has no type parameters. `BitSlice` has two: one for the integer type used as backing storage, and one for the order of bits within that integer type. `&BitSlice` is capable of producing `&bool` references to read bits out of its memory, but is not capable of producing `&mut bool` references to write bits *into* its memory. Any `[bool]` API that would produce a `&mut bool` will instead produce a [`BitRef`] proxy reference. ## Behavior `BitSlice` is a wrapper over `[T]`. It describes a region of memory, and must be handled indirectly. This is most commonly done through the reference types `&BitSlice` and `&mut BitSlice`, which borrow memory owned by some other value in the program. These buffers can be directly owned by the sibling types [`BitBox`], which behaves like [`Box<[T]>`](alloc::boxed::Box), and [`BitVec`], which behaves like [`Vec`]. It cannot be used as the type parameter to a pointer type such as `Box`, `Rc`, `Arc`, or any other indirection. The `BitSlice` region provides access to each individual bit in the region, as if each bit had a memory address that you could use to dereference it. It packs each logical bit into exactly one bit of storage memory, just like [`std::bitset`] and [`std::vector`] in C++. ## Type Parameters `BitSlice` has two type parameters which propagate through nearly every public API in the crate. These are very important to its operation, and your choice of type arguments informs nearly every part of this library’s behavior. ### `T: BitStore` [`BitStore`] is the simpler of the two parameters. It refers to the integer type used to hold bits. It must be one of the Rust unsigned integer fundamentals: `u8`, `u16`, `u32`, `usize`, and on 64-bit systems only, `u64`. In addition, it can also be an alias-safe wrapper over them (see the [`access`] module) in order to permit bit-slices to share underlying memory without interfering with each other. `BitSlice` references can only be constructed over the integers, not over their aliasing wrappers. `BitSlice` will only use aliasing types in its `T` slots when you invoke APIs that produce them, such as [`.split_at_mut()`]. The default type argument is `usize`. The argument you choose is used as the basis of a `[T]` slice, over which the `BitSlice` view is produced. `BitSlice` is subject to all of the rules about alignment that `[T]` is. If you are working with in-memory representation formats, chances are that you already have a `T` type with which you’ve been working, and should use it here. If you are only using this crate to discard the seven wasted bits per `bool` in a collection of `bool`s, and are not too concerned about the in-memory representation, then you should use the default type argument of `usize`. This is because most processors work best when moving an entire `usize` between memory and the processor itself, and using a smaller type may cause it to slow down. Additionally, processor instructions are typically optimized for the whole register, and the processor might need to do additional clearing work for narrower types. ### `O: BitOrder` [`BitOrder`] is the more complex parameter. It has a default argument which, like `usize`, is a good baseline choice when you do not explicitly need to control the representation of bits in memory. This parameter determines how `bitvec` indexes the bits within a single `T` memory element. Computers all agree that in a slice of `T` elements, the element with the lower index has a lower memory address than the element with the higher index. But the individual bits within an element do not have addresses, and so there is no uniform standard of which bit is the zeroth, which is the first, which is the penultimate, and which is the last. To make matters even more confusing, there are two predominant ideas of in-element ordering that often *correlate* with the in-element *byte* ordering of integer types, but are in fact wholly unrelated! `bitvec` provides these two main orderings as types for you, and if you need a different one, it also provides the tools you need to write your own. #### Least Significant Bit Comes First This ordering, named the [`Lsb0`] type, indexes bits within an element by placing the `0` index at the least significant bit (numeric value `1`) and the final index at the most significant bit (numeric value [`T::MIN`][minval] for signed integers on most machines). For example, this is the ordering used by most C compilers to lay out bit-field struct members on little-endian **byte**-ordered machines. #### Most Significant Bit Comes First This ordering, named the [`Msb0`] type, indexes bits within an element by placing the `0` index at the most significant bit (numeric value [`T::MIN`][minval] for most signed integers) and the final index at the least significant bit (numeric value `1`). For example, this is the ordering used by the [TCP wire format][tcp], and by most C compilers to lay out bit-field struct members on big-endian **byte**-ordered machines. #### Default Ordering The default ordering is [`Lsb0`], as it typically produces shorter object code than [`Msb0`] does. If you are implementing a collection, then `Lsb0` will likely give you better performance; if you are implementing a buffer protocol, then your choice of ordering is dictated by the protocol definition. ## Safety `BitSlice` is designed to never introduce new memory unsafety that you did not provide yourself, either before or during the use of this crate. However, safety bugs have been identified before, and you are welcome to submit any discovered flaws as a defect report. The `&BitSlice` reference type uses a private encoding scheme to hold all of the information needed in its stack value. This encoding is **not** part of the public API of the library, and is not binary-compatible with `&[T]`. Furthermore, in order to satisfy Rust’s requirements about alias conditions, `BitSlice` performs type transformations on the `T` parameter to ensure that it never creates the potential for undefined behavior or data races. You must never attempt to type-cast a reference to `BitSlice` in any way. You must not use [`mem::transmute`] with `BitSlice` anywhere in its type arguments. You must not use `as`-casting to convert between `*BitSlice` and any other type. You must not attempt to modify the binary representation of a `&BitSlice` reference value. These actions will all lead to runtime memory unsafety, are (hopefully) likely to induce a program crash, and may possibly cause undefined behavior at compile-time. Everything in the `BitSlice` public API, even the `unsafe` parts, are guaranteed to have no more unsafety than their equivalent items in the standard library. All `unsafe` APIs will have documentation explicitly detailing what the API requires you to uphold in order for it to function safely and correctly. All safe APIs will do so themselves. ## Performance Like the standard library’s `[T]` slice, `BitSlice` is designed to be very easy to use safely, while supporting `unsafe` usage when necessary. Rust has a powerful optimizing engine, and `BitSlice` will frequently be compiled to have zero runtime cost. Where it is slower, it will not be significantly slower than a manual replacement. As the machine instructions operate on registers rather than bits, your choice of [`T: BitStore`] type parameter can influence your bits-slice’s performance. Using larger register types means that bit-slices can gallop over completely-used interior elements faster, while narrower register types permit more graceful handling of subslicing and aliased splits. ## Construction `BitSlice` views of memory can be constructed over borrowed data in a number of ways. As this is a reference-only type, it can only ever be built by borrowing an existing memory buffer and taking temporary control of your program’s view of the region. ### Macro Constructor `BitSlice` buffers can be constructed at compile-time through the [`bits!`] macro. This macro accepts a superset of the [`vec!`] arguments, and creates an appropriate buffer in the local scope. The macro expands to a borrowed [`BitArray`] temporary, which will live for the duration of the bound name. ```rust use bitvec::prelude::*; let immut = bits![u8, Lsb0; 0, 1, 0, 0, 1, 0, 0, 1]; let mutable: &mut BitSlice<_, _> = bits![mut u8, Msb0; 0; 8]; assert_ne!(immut, mutable); mutable.clone_from_bitslice(immut); assert_eq!(immut, mutable); ``` ### Borrowing Constructors You may borrow existing elements or slices with the following functions: - [`from_element`] and [`from_element_mut`], - [`from_slice`] and [`from_slice_mut`], - [`try_from_slice`] and [`try_from_slice_mut`] These take references to existing memory and construct `BitSlice` references from them. These are the most basic ways to borrow memory and view it as bits; however, you should prefer the [`BitView`] trait methods instead. ```rust use bitvec::prelude::*; let data = [0u16; 3]; let local_borrow = BitSlice::<_, Lsb0>::from_slice(&data); let mut data = [0u8; 5]; let local_mut = BitSlice::<_, Lsb0>::from_slice_mut(&mut data); ``` ### Trait Method Constructors The [`BitView`] trait implements [`.view_bits::()`] and [`.view_bits_mut::()`] methods on elements, arrays, and slices. This trait, imported in the crate prelude, is *probably* the easiest way for you to borrow memory as bits. ```rust use bitvec::prelude::*; let data = [0u32; 5]; let trait_view = data.view_bits::(); let mut data = 0usize; let trait_mut = data.view_bits_mut::(); ``` ### Owned Bit Slices If you wish to take ownership of a memory region and enforce that it is always viewed as a `BitSlice` by default, you can use one of the [`BitArray`], [`BitBox`], or [`BitVec`] types, rather than pairing ordinary buffer types with the borrowing constructors. ```rust use bitvec::prelude::*; let slice = bits![0; 27]; let array = bitarr![u8, LocalBits; 0; 10]; # #[cfg(feature = "alloc")] fn allocates() { let boxed = bitbox![0; 10]; let vec = bitvec![0; 20]; # } #[cfg(feature = "alloc")] allocates(); // arrays always round up assert_eq!(array.as_bitslice(), slice[.. 16]); # #[cfg(feature = "alloc")] fn allocates2() { # let slice = bits![0; 27]; # let boxed = bitbox![0; 10]; # let vec = bitvec![0; 20]; assert_eq!(boxed.as_bitslice(), slice[.. 10]); assert_eq!(vec.as_bitslice(), slice[.. 20]); # } #[cfg(feature = "alloc")] allocates2(); ``` ## Usage `BitSlice` implements the full standard-library `[bool]` API. The documentation for these API surfaces is intentionally sparse, and forwards to the standard library rather than try to replicate it. `BitSlice` also has a great deal of novel API surfaces. These are broken into separate `impl` blocks below. A short summary: - Since there is no `BitSlice` literal, the constructor functions `::empty()`, `::from_element()`, `::from_slice()`, and `::try_from_slice()`, and their `_mut` counterparts, create bit-slices as needed. - Since `bits[idx] = value` does not exist, you can use `.set()` or `.replace()` (as well as their `_unchecked` and `_aliased` counterparts) to write into a bit-slice. - Raw memory can be inspected with `.domain()` and `.domain_mut()`, and a bit-slice can be split on aliasing lines with `.bit_domain()` and `.bit_domain_mut()`. - The population can be queried for which indices have `0` or `1` bits by iterating across all such indices, counting them, or counting leading or trailing blocks. Additionally, `.any()`, `.all()`, `.not_any()`, `.not_all()`, and `.some()` test whether bit-slices satisfy aggregate Boolean qualities. - Buffer contents can be relocated internally by shifting or rotating to the left or right. ## Trait Implementations `BitSlice` adds trait implementations that `[bool]` and `[T]` do not necessarily have, including numeric formatting and Boolean arithmetic operators. Additionally, the [`BitField`] trait allows bit-slices to act as a buffer for wide-value storage. [minval]: https://doc.rust-lang.org/stable/std/primitive.usize.html#associatedconstant.MIN [tcp]: https://en.wikipedia.org/wiki/Transmission_Control_Protocol#TCP_segment_structure [`BitArray`]: crate::array::BitArray [`BitBox`]: crate::boxed::BitBox [`BitField`]: crate::field::BitField [`BitRef`]: crate::ptr::BitRef [`BitOrder`]: crate::order::BitOrder [`BitStore`]: crate::store::BitStore [`BitVec`]: crate::vec::BitVec [`BitView`]: crate::view::BitView [`Cell`]: core::cell::Cell [`Lsb0`]: crate::order::Lsb0 [`Msb0`]: crate::order::Msb0 [`T: BitStore`]: crate::store::BitStore [`Vec`]: alloc::vec::Vec [`access`]: crate::access [`bits!`]: macro@crate::bits [`bitvec::prelude::LocalBits`]: crate::order::LocalBits [`from_element`]: Self::from_element [`from_element_mut`]: Self::from_element_mut [`from_slice`]: Self::from_slice [`from_slice_mut`]: Self::from_slice_mut [`mem::transmute`]: core::mem::transmute [`std::bitset`]: https://en.cppreference.com/w/cpp/utility/bitset [`std::vector`]: https://en.cppreference.com/w/cpp/container/vector_bool [`try_from_slice`]: Self::try_from_slice [`try_from_slice_mut`]: Self::try_from_slice_mut [`vec!`]: macro@alloc::vec [`.split_at_mut()`]: Self::split_at_mut [`.view_bits::()`]: crate::view::BitView::view_bits [`.view_bits_mut::()`]: crate::view::BitView::view_bits_mut