Trait bitvec::order::BitOrder

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

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

    fn mask<R>(
        from: impl Into<Option<BitIdx<R>>>, 
        upto: impl Into<Option<BitTail<R>>>
    ) -> BitMask<R>
    where
        R: BitRegister,
    { ... }
}
Expand description

An ordering over a register.

Usage

bitvec structures store and operate on semantic index counters, not electrical bit positions. The BitOrder::at function takes a semantic ordering, BitIdx, and produces a corresponding electrical position, BitPos.

Safety

If your implementation violates any of the requirements on these functions, then the program will become incorrect, and have unspecified behavior. The best-case outcome is that operations relying on your implementation will crash the program; the worst-case is that memory access will silently become corrupt.

You are responsible for adhering to the requirements of these functions. There are verification functions that you can use in your test suite; however, it is not yet possible to prove correctness at compile-time.

This is an unsafe trait to implement because you are responsible for upholding the stated requirements.

The implementations of BitOrder are trusted to drive safe code, and once data leaves a BitOrder implementation, it is considered safe to use as the basis for interaction with memory.

Verification

The verify and verify_for_type functions are available for your test suites. They ensure that a BitOrder implementation satisfies the requirements when invoked for a given register type.

Examples

Implementations are not required to remain contiguous over a register. This example swizzles the high and low halves of each byte, but any translation is valid as long as it satisfies the strict one-to-one requirement of index-to-position.

use bitvec::{
  prelude::BitOrder,
  // Additional symbols:
  index::{BitIdx, BitPos},
  mem::BitRegister,
};

pub struct HiLo;
unsafe impl BitOrder for HiLo {
  fn at<R: BitRegister>(idx: BitIdx<R>) -> BitPos<R> {
    BitPos::new(idx.value() ^ 4).unwrap()
  }
}

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

Required methods

Converts a semantic bit index into an electrical 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 register type that the index and position govern.
Parameters
  • index: The semantic index of a bit within a register R.
Returns

The electrical position of the indexed bit within the register R. See the BitPos documentation for what electrical 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

This function must be able to accept every input in the range BitIdx::ZERO to BitIdx::LAST, and produce a value in the same range as a BitPos.

Bijection

There must be an exactly one-to-one correspondence between input value and output value. 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.

Output Validity

The produced BitPos must be within the valid range of that type. Call sites of this function will not take any steps to constrain or check the return value. If you use unsafe code to produce an invalid BitPos, the program is incorrect, and will likely crash.

Usage

This function is only ever called with input values in the valid BitIdx range. Implementors are not required to consider any values outside this range in their function body.

Provided methods

Converts a semantic bit index into a one-hot selector mask.

This is an optional function; a default implementation is provided for you. If you choose to override it, your implementation must retain the behavior of the default implementation.

The default implementation calls Self::at to convert the index into a position, then turns that position into a selector mask with the expression 1 << pos. BitOrder implementations may choose to provide a faster mask production here, as long as they match this behavior.

Type Parameters
  • R: The register type that the index and selector govern.
Parameters
  • index: The semantic index of a bit within a register R.
Returns

A one-hot selector mask for the bit indicated by the index value.

Requirements

A one-hot encoding means that there is exactly one bit set in the produced value. It must be equivalent to 1 << Self::at::<R>(index).

As with at, this function must produce a unique mapping from each legal index in the BitIdx domain to a one-hot value of R.

Constructs a multiple-bit selector mask for batched operations on a register R.

The default implementation of this function traverses the index range, converting each index into a single-bit selector with Self::select and accumulating into a combined register value.

Type Parameters
  • R: The register type for which the mask is built.
Parameters
  • from: The inclusive starting index for the mask.
  • upto: The exclusive ending index for the mask.
Returns

A bit-mask with all bits corresponding to the input index range set high and all others set low.

Requirements

This function must always be equivalent to this expression:

ⓘ
(from .. upto)
  .map(Self::select::<R>)
  .fold(0, |mask, sel| mask | sel)

Implementors