Trait bitvec::order::BitOrder[−][src]

pub unsafe trait BitOrder {
    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 counts, not bit positions. The BitOrder::at function takes a semantic ordering, BitIdx, and produces an 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 scenario 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. In the future, a verification function may be provided for your test suite; however, it is not yet possible to verify your implementation at compile-time.

This is an unsafe trait to implement, because you are responsible for upholding the state requirements. The types you manipulate have unsafe fn constructors, because they require you to maintain correct and consistent processes in order for the rest of the library to use them.

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

Rust currently lacks Zig’s compile-time computation capability. This means that bitvec cannot fail a compile if it detects that a BitOrder implementation is invalid and breaks the stated requirements. bitvec does offer a function, verify, which ensures the correctness of an implementation. When Rust gains the capability to run this function in generic const contexts, bitvec will use it to prevent at compile-time the construction of data structures that use incorrect ordering implementations.

The verifier function panics when it detects invalid behavior, with an error message intended to clearly indicate the broken requirement.

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

pub struct Custom;
unsafe impl BitOrder for Custom {
  fn at<R: BitRegister>(idx: BitIdx<R>) -> BitPos<R> {
  // impl
  }
}

#[test]
#[cfg(test)]
fn prove_custom() {
  order::verify::<Custom>();
}

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 considered correct.

Parameters
  • index: The semantic index of a bit within a register R.
Returns

The electrical position of the indexed bit within a register R. See the BitPos documentation for what electrical positions are considered to mean.

Type Parameters
  • R: The register type which the index and position describe.
Requirements

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

Totality

This function must be able to accept every input in the BitIdx<R> value range, and produce a corresponding BitPos<R>. It must not abort the program or return an invalid BitPos<R> for any input value in the BitIdx<R> range.

Bijection

There must be an exactly one-to-one correspondence between input value and output value. No input index may select from a set of more than one output 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 the program. This function may refer to global state, but that state must be immutable for the program lifetime, and must not be used to violate the totality or bijection requirements.

Output Validity

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

Usage

This function will only ever be called with input values in the valid BitIdx<R> 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.

The default implementation of this function calls Self::at to produce an electrical position, then turns that into a selector mask by setting the nth bit more significant than the least significant bit of the element. BitOrder implementations may choose to provide a faster mask production here, but they must satisfy the requirements listed below.

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.

Type Parameters
  • R: The storage type for which the mask will be calculated. The mask must also be this type, as it will be applied to a register of R in order to set, clear, or test a single bit.
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>(place).

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

Constructs a multi-bit selector mask for batch operations on a single 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.

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.

Type Parameters
  • R: The storage type for which the mask will be calculated. The mask must also be this type, as it will be applied to a register of R in order to set, clear, or test all the selected bits.
Requirements

This function must always be equivalent to

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

Implementors