Trait Underlier 

pub trait Underlier:
    Debug
    + Default
    + Eq
    + Ord
    + Copy
    + Random
    + NoUninit
    + Zeroable
    + Sized
    + Send
    + Sync
    + 'static
    + BitAnd<Self, Output = Self>
    + BitAndAssign<Self>
    + BitOr<Self, Output = Self>
    + BitOrAssign<Self>
    + BitXor<Self, Output = Self>
    + BitXorAssign<Self>
    + Not<Output = Self>
    + Divisible<SmallU<1>> {
    const LOG_BITS: usize;
    const ZERO: Self;
    const ONE: Self;
    const ONES: Self;
    const BITS: usize = _;

    // Required method
    fn interleave(self, other: Self, log_block_len: usize) -> (Self, Self);

    // Provided methods
    fn transpose(self, other: Self, log_block_len: usize) -> (Self, Self) { ... }
    fn from_fn<T>(f: impl FnMut(usize) -> T) -> Self
       where T: Underlier,
             Self: Divisible<T> { ... }
}

A fixed-length vector of bits, whose length is a power of two.

This is the storage a binary field element lives in. An element is a bit pattern. This trait is the interface for holding that pattern and moving it around.

The same bits can be read two ways, and the interface serves both:

BITS = 32

one field element    [ -------------- x -------------- ]
eight packed ones    [ x7 x6 x5 x4 x3 x2 x1 x0 ]

Nothing here knows which reading is meant. The bitwise operators act on every bit at once, so they are correct under either. Addition in a binary field is exclusive or, which is why that operator is required.

Why the length is a power of two

A value splits evenly in half, and each half splits again, down to single bits. The two shuffling operations below walk that ladder one rung at a time. A length like 24 bits would have no such ladder.

Bit order

Bit 0 is the least significant. Every diagram here lists the low end first. That is the reverse of how a binary literal reads.

Required Associated Constants

const LOG_BITS: usize

Base-2 logarithm of the number of bits in a value.

const ZERO: Self

Every bit clear.

const ONE: Self

Bit 0 set, every other bit clear.

const ONES: Self

Every bit set.

Provided Associated Constants

const BITS: usize = _

Number of bits in a value.

This can be fewer than the bits of the type that stores it. The one-, two-, and four-bit underliers each sit in a byte. Their spare high bits carry nothing.

Required Methods

fn interleave(self, other: Self, log_block_len: usize) -> (Self, Self)

Exchanges alternating blocks of two values.

Cut both values into blocks of 2^log_block_len bits, numbered from the low end. The first result takes the even-numbered blocks of each value, one after the other. The second result takes the odd-numbered ones the same way.

BITS = 8, log_block_len = 1, so four blocks of two bits, low block first

    self    [ a0 | a1 | a2 | a3 ]
    other   [ b0 | b1 | b2 | b3 ]

    first   [ a0 | b0 | a2 | b2 ]
    second  [ a1 | b1 | a3 | b3 ]

This is one rung of the ladder that halves a value down to single bits. Repeating it at every rung is what the transpose below does.

Provided Methods

fn transpose(self, other: Self, log_block_len: usize) -> (Self, Self)

Separates two values into their even and odd blocks.

Cut both values into blocks of 2^log_block_len bits, numbered from the low end. The first result collects every even-numbered block, this value’s before the other’s. The second result collects every odd-numbered block the same way.

BITS = 8, log_block_len = 0, so eight blocks of one bit, low bit first

    self    [ a0 a1 a2 a3 a4 a5 a6 a7 ]
    other   [ b0 b1 b2 b3 b4 b5 b6 b7 ]

    first   [ a0 a2 a4 a6 b0 b2 b4 b6 ]
    second  [ a1 a3 a5 a7 b1 b3 b5 b7 ]

Lay the two values out as the two rows of a matrix whose entries are blocks. This reads that matrix out one column at a time, which is what makes it a transpose.

Panics

Panics unless the block length is shorter than the whole value.

fn from_fn<T>(f: impl FnMut(usize) -> T) -> Self

where T: Underlier, Self: Divisible<T>,

Builds a value by filling it with narrower ones, low slot first.

The two widths fix how many slots there are. The closure is called exactly that many times.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementations on Foreign Types

impl Underlier for u8

const LOG_BITS: usize

const ZERO: Self = 0

const ONE: Self = 1

const ONES: Self = Self::MAX

fn interleave(self, other: Self, log_block_len: usize) -> (Self, Self)

impl Underlier for u16

const LOG_BITS: usize

const ZERO: Self = 0

const ONE: Self = 1

const ONES: Self = Self::MAX

fn interleave(self, other: Self, log_block_len: usize) -> (Self, Self)

impl Underlier for u32

const LOG_BITS: usize

const ZERO: Self = 0

const ONE: Self = 1

const ONES: Self = Self::MAX

fn interleave(self, other: Self, log_block_len: usize) -> (Self, Self)

impl Underlier for u64

const LOG_BITS: usize

const ZERO: Self = 0

const ONE: Self = 1

const ONES: Self = Self::MAX

fn interleave(self, other: Self, log_block_len: usize) -> (Self, Self)

impl Underlier for u128

const LOG_BITS: usize

const ZERO: Self = 0

const ONE: Self = 1

const ONES: Self = Self::MAX

fn interleave(self, other: Self, log_block_len: usize) -> (Self, Self)

Implementors

impl Underlier for binius_field::arch::portable::m128::M128

const LOG_BITS: usize = 7

const ZERO: Self

const ONE: Self

const ONES: Self

impl Underlier for binius_field::arch::M128

const LOG_BITS: usize = 7

const ZERO: Self

const ONE: Self

const ONES: Self