Trait bitvec::order::BitOrder

source ·
pub unsafe trait BitOrder: 'static {
    // Required method
    fn at<R>(index: BitIdx<R>) -> BitPos<R>
       where R: BitRegister;

    // Provided methods
    fn select<R>(index: BitIdx<R>) -> BitSel<R>
       where R: BitRegister { ... }
    fn mask<R>(
        from: impl Into<Option<BitIdx<R>>>,
        upto: impl Into<Option<BitEnd<R>>>
    ) -> BitMask<R>
       where R: BitRegister { ... }
}
Expand description

In-Element Bit Ordering

This trait manages the translation of semantic bit indices into electrical positions within storage elements of a memory region.

Usage

bitvec APIs operate on semantic index counters that exist in an abstract memory space independently of the real memory that underlies them. In order to affect real memory, bitvec must translate these indices into real values. The at function maps abstract index values into their corresponding real positions that can then be used to access memory.

You will likely never call any of the trait functions yourself. They are used by bitvec internals to operate on memory regions; all you need to do is provide an implementation of this trait as a type parameter to bitvec data structures.

Safety

BitOrder is unsafe to implement because its translation of index to position cannot be forcibly checked by bitvec itself, and an improper implementation will lead to memory unsafety errors and unexpected collisions. The trait has strict requirements for each function. If these are not upheld, then the implementation is considered undefined at the library level and its use may produce incorrect or undefined behavior during compilation.

You are responsible for running verify_for_type or verify in your test suite if you implement BitOrder.

Implementation Rules

Values of this type are never constructed or passed to bitvec functions. Your implementation does not need to be zero-sized, but it will never have access to an instance to view its state. It may refer to other global state, but per the rules of at, that state may not change while any bitvec data structures are alive.

The only function you need to provide is at. Its requirements are listed in its trait documentation.

You may also choose to provide implementations of select and mask. These have a default implementation that is correct, but may be unoptimized for your implementation. As such, you may replace them with a better version, but your implementation of these functions must be exactly equal to the default implementation for all possible inputs.

This requirement is checked by the verify_for_type function.

Verification

The verify_for_type function verifies that a BitOrder implementation is correct for a single BitStore implementor, and the verify function runs verify_for_type on all unsigned integers that implement BitStore on a target. If you run these functions in your test suite, they will provide detailed information if your implementation is incorrect.

Examples

Implementations are not required to remain contiguous over a register, and may have any mapping they wish as long as it is total and bijective. This example swizzles the high and low halves of each byte.

use bitvec::{
  order::BitOrder,
  index::{BitIdx, BitPos},
  mem::BitRegister,
};

pub struct HiLo;

unsafe impl BitOrder for HiLo {
  fn at<R>(index: BitIdx<R>) -> BitPos<R>
  where R: BitRegister {
    unsafe { BitPos::new_unchecked(index.into_inner() ^ 4) }
  }
}

#[test]
#[cfg(test)]
fn prove_hilo() {
  bitvec::order::verify::<HiLo>();
}

Once a BitOrder implementation passes the test suite, it can be freely used as a type parameter in bitvec data structures. The translation takes place automatically, and you never need to look at this trait again.

Required Methods§

source

fn at<R>(index: BitIdx<R>) -> BitPos<R>where R: BitRegister,

Translates a semantic bit index into a real bit position.

This function is the basis of the trait, and must adhere to a number of requirements in order for an implementation to be correct.

Type Parameters
  • R: The memory element type that the index and position govern.
Parameters
  • index: A semantic bit-index within some R element.
Returns

The real position of the indexed bit within an R element. See the BitPos documentation for what these positions are considered to mean.

Requirements

This function must satisfy the following requirements for all possible input and output values, for all possible R type parameters:

  • Totality: The implementation must be able to accept every input in BitIdx::<R>::range_all(), and produce some BitPos value for each.
  • Bijection: There must be an exactly one-to-one correspondence between input and output values. No input index may choose its output from a set of more than one position, and no output position may be produced by more than one input index.
  • Purity: The translation from index to position must be consistent for the lifetime of at least all data structures in the program. This function may refer to global state, but that state must be immutable while any bitvec data structures exist, and must not be used to violate the totality or bijection requirements.
  • Validity: The produced BitPos value must be within the valid range of its type. This is enforced by BitPos::new, but not by the unsafe constructor BitPos::new_unchecked.

Provided Methods§

source

fn select<R>(index: BitIdx<R>) -> BitSel<R>where R: BitRegister,

Produces a single-bit selection mask from a bit-index.

This is an optional function: it is implemented as, and must always be exactly identical to, BitOrder::at(index).select(). If your ordering has a faster implementation, you may provide it, but it must be exactly numerically equivalent.

source

fn mask<R>( from: impl Into<Option<BitIdx<R>>>, upto: impl Into<Option<BitEnd<R>>> ) -> BitMask<R>where R: BitRegister,

Produces a multi-bit selection mask from a range of bit-indices.

This is an optional function: it is implemented as, and must always be exactly identical to, BitIdx::range(from, upto).map(BitOrder::select).sum(). If your ordering has a faster implementation, you may provide it, but it must be exactly numerically equivalent.

Parameters
  • from: The inclusive starting value of the indices being selected. Defaults to BitIdx::MIN.
  • upto: The exclusive ending value of the indices being selected. Defaults to BitEnd::MAX.
Returns

A selection mask with all bit-positions corresponding to from .. upto selected.

Implementors§