Struct bitvec::slice::BitSlice

source ·

pub struct BitSlice<T = usize, O = Lsb0>where
    T: BitStore,
    O: BitOrder,{ /* private fields */ }

Expand description

Bit-Addressable Memory

A slice of individual bits, anywhere in memory.

BitSlice<T, O> is an unsized region type; you interact with it through &BitSlice<T, O> and &mut BitSlice<T, O> 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

use bitvec::prelude::*;

fn trim<T: BitStore, O: BitOrder>(
  bits: &BitSlice<T, O>,
  to_trim: bool,
) -> &BitSlice<T, O> {
  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]
}

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]

API Differences

The slice type [bool] has no type parameters. BitSlice<T, O> has two: one for the integer type used as backing storage, and one for the order of bits within that integer type.

&BitSlice<T, O> 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<Mut, T, O> 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]>, and BitVec, which behaves like Vec<T>. 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<bool> 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<T, _> 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 bools, 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 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 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, 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.

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.

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::<O>() and .view_bits_mut::<O>() 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.

use bitvec::prelude::*;

let data = [0u32; 5];
let trait_view = data.view_bits::<Lsb0>();

let mut data = 0usize;
let trait_mut = data.view_bits_mut::<Msb0>();

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.

use bitvec::prelude::*;

let slice = bits![0; 27];
let array = bitarr![u8, LocalBits; 0; 10];
let boxed = bitbox![0; 10];
let vec = bitvec![0; 20];

// arrays always round up
assert_eq!(array.as_bitslice(), slice[.. 16]);
assert_eq!(boxed.as_bitslice(), slice[.. 10]);
assert_eq!(vec.as_bitslice(), slice[.. 20]);

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.

Type Bits	Max Elements (32-bit)	Max Elements (64-bit)
8	`0x0400_0001`	`0x0400_0000_0000_0001`
16	`0x0200_0001`	`0x0200_0000_0000_0001`
32	`0x0100_0001`	`0x0100_0000_0000_0001`
64	`0x0080_0001`	`0x0080_0000_0000_0001`

CPU word width	Value
32 bits	`0x1fff_ffff`
64 bits	`0x1fff_ffff_ffff_ffff`

Struct bitvec::slice::BitSlice

Implementations§

impl<T, O> BitSlice<T, O>where T: BitStore, O: BitOrder,

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn first(&self) -> Option<BitRef<'_, Const, T, O>>

pub fn first_mut(&mut self) -> Option<BitRef<'_, Mut, T, O>>

pub fn split_first(&self) -> Option<(BitRef<'_, Const, T, O>, &Self)>

pub fn split_first_mut( &mut self ) -> Option<(BitRef<'_, Mut, T::Alias, O>, &mut BitSlice<T::Alias, O>)>

pub fn split_last(&self) -> Option<(BitRef<'_, Const, T, O>, &Self)>

pub fn split_last_mut( &mut self ) -> Option<(BitRef<'_, Mut, T::Alias, O>, &mut BitSlice<T::Alias, O>)>

pub fn last(&self) -> Option<BitRef<'_, Const, T, O>>

pub fn last_mut(&mut self) -> Option<BitRef<'_, Mut, T, O>>

pub fn get<'a, I>(&'a self, index: I) -> Option<I::Immut>where I: BitSliceIndex<'a, T, O>,

pub fn get_mut<'a, I>(&'a mut self, index: I) -> Option<I::Mut>where I: BitSliceIndex<'a, T, O>,

pub unsafe fn get_unchecked<'a, I>(&'a self, index: I) -> I::Immutwhere I: BitSliceIndex<'a, T, O>,

pub unsafe fn get_unchecked_mut<'a, I>(&'a mut self, index: I) -> I::Mutwhere I: BitSliceIndex<'a, T, O>,

pub fn as_ptr(&self) -> BitPtr<Const, T, O>

pub fn as_mut_ptr(&mut self) -> BitPtr<Mut, T, O>

pub fn as_ptr_range(&self) -> Range<BitPtr<Const, T, O>>

pub fn as_mut_ptr_range(&mut self) -> Range<BitPtr<Mut, T, O>>

pub fn swap(&mut self, a: usize, b: usize)

pub fn reverse(&mut self)

pub fn iter(&self) -> Iter<'_, T, O> ⓘ

pub fn iter_mut(&mut self) -> IterMut<'_, T, O> ⓘ

pub fn windows(&self, size: usize) -> Windows<'_, T, O> ⓘ

pub fn chunks(&self, chunk_size: usize) -> Chunks<'_, T, O> ⓘ

pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<'_, T, O> ⓘ

pub fn chunks_exact(&self, chunk_size: usize) -> ChunksExact<'_, T, O> ⓘ

pub fn chunks_exact_mut( &mut self, chunk_size: usize ) -> ChunksExactMut<'_, T, O> ⓘ

pub fn rchunks(&self, chunk_size: usize) -> RChunks<'_, T, O> ⓘ

pub fn rchunks_mut(&mut self, chunk_size: usize) -> RChunksMut<'_, T, O> ⓘ

pub fn rchunks_exact(&self, chunk_size: usize) -> RChunksExact<'_, T, O> ⓘ

pub fn rchunks_exact_mut( &mut self, chunk_size: usize ) -> RChunksExactMut<'_, T, O> ⓘ

pub fn split_at(&self, mid: usize) -> (&Self, &Self)