Struct PackedGf2 

pub struct PackedGf2<U: Underlier>(/* private fields */);

Several independent elements of GF(2), one per bit of a block of storage.

Lane i is bit i mod B of word i / B, counting from the least significant bit. Read as bytes, that puts lane i at bit i mod 8 of byte i / 8.

This is the order a bit witness already has on the wire, so packing one moves no bits.

The arithmetic is what the field does to one bit, applied to the whole block at once:

    a + b   ->  a XOR b
    a * b   ->  a AND b
    a^2     ->  a

Implementations

impl<U: Underlier> PackedGf2<U>

pub const WIDTH: usize = U::BITS

How many independent elements one value holds.

pub const fn new(bits: U) -> Self

The packing over a block of storage, read lane for bit.

pub const fn to_bits(self) -> U

The block of storage behind the packing.

pub fn words(&self) -> &[U::Word]

The backing words, lowest lanes first.

pub fn words_mut(&mut self) -> &mut [U::Word]

The backing words, lowest lanes first.

Every bit pattern is a valid packing, so writing here cannot break an invariant.

pub fn get(&self, lane: usize) -> Gf2

The element in the given lane.

Panics

Panics if the lane index is not below the width.

pub fn set(&mut self, lane: usize, value: Gf2)

Overwrite the element in the given lane.

Panics

Panics if the lane index is not below the width.

pub fn from_fn(f: impl FnMut(usize) -> Gf2) -> Self

Build a value lane by lane.

pub fn broadcast(value: Gf2) -> Self

The same element in every lane.

pub fn lanes(self) -> impl Iterator<Item = Gf2>

The lanes, lowest first.

pub fn count_ones(&self) -> u32

How many lanes hold one.

pub const fn invert_or_zero(self) -> Self

The lane-wise inverse, with zero sent to zero.

One is the only invertible element of GF(2) and it is its own inverse.

Extending the map by 0^-1 = 0 therefore makes it the identity on every lane.

pub fn narrow<V: Underlier>(&self) -> &[PackedGf2<V>]

where U: Divisible<V>,

This value read as a run of narrower packings, lowest lanes first.

A wide block is narrow ones side by side: lane i is lane i mod w of part i / w.

pub fn narrow_mut<V: Underlier>(&mut self) -> &mut [PackedGf2<V>]

where U: Divisible<V>,

This value read as a run of narrower packings, lowest lanes first.

pub fn narrow_slice<V: Underlier>(slice: &[Self]) -> &[PackedGf2<V>]

where U: Divisible<V>,

A run of these packings read as a run of narrower ones, lowest lanes first.

The same bytes carry the same lanes in order, so a narrower read copies nothing.

pub fn narrow_slice_mut<V: Underlier>(slice: &mut [Self]) -> &mut [PackedGf2<V>]

where U: Divisible<V>,

A run of these packings read as a run of narrower ones, lowest lanes first.

pub const fn as_bytes(slice: &[Self]) -> &[u8]

A run of these packings read as bytes, lowest lanes first.

Byte k holds lanes 8k .. 8k + 8, lowest lane at the lowest bit.

pub fn interleave(&self, other: Self, block_len: usize) -> (Self, Self)

Cut both operands into chunks of block_len lanes and interleave the chunks.

Cut the stack of the two into two-by-two matrices of chunks, and transpose each:

    A = [x0, y0, x1, y1]
    B = [x2, y2, x3, y3]

    block_len = 1  ->  ([x0, x2, x1, x3], [y0, y2, y1, y3])

A chunk as wide as the value leaves both operands untouched.

This is the convention the packed-field trait fixes. So a caller can swap a bit-sliced packing for any other and see one permutation.

Panics

Panics unless the chunk length is a power of two no larger than the width.

impl<U: Underlier> PackedGf2<U>

pub fn transpose(rows: &mut [Self])

Replace the square bit matrix whose row i is rows[i] by its transpose.

Lane c of row r becomes lane r of row c.

Panics

Panics unless the matrix has exactly as many rows as the packing has lanes.

Trait Implementations

impl<U: Underlier> Add for PackedGf2<U>

type Output = PackedGf2<U>

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self

Performs the + operation.

impl<U: Underlier> Add<Gf2> for PackedGf2<U>

type Output = PackedGf2<U>

The resulting type after applying the + operator.

fn add(self, rhs: Gf2) -> Self

Performs the + operation.

impl<U: Underlier, T: Into<Self>> AddAssign<T> for PackedGf2<U>

fn add_assign(&mut self, rhs: T)

Performs the += operation.

impl<U: Underlier> Algebra<Gf2> for PackedGf2<U>

fn quadratic_extension_square(a: &[Self; 2], w: F) -> [Self; 2]

Square a[0] + a[1] X modulo X^2 - w.

fn mixed_dot_product<const N: usize>(a: &[Self; N], f: &[F; N]) -> Self

where F: Dup,

Dot product between algebra elements and base field scalars.

const BATCHED_LC_CHUNK: usize = 8

Optimal chunk size for batched_linear_combination.

fn batched_linear_combination(values: &[Self], coeffs: &[F]) -> Self

where F: Dup,

Runtime-length linear combination: Σ values[i] * coeffs[i].

impl<U: Clone + Underlier> Clone for PackedGf2<U>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<U: Copy + Underlier> Copy for PackedGf2<U>

impl<U: Underlier> Debug for PackedGf2<U>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<U: Default + Underlier> Default for PackedGf2<U>

fn default() -> Self

Returns the “default value” for a type.

impl<U: Underlier> Distribution<PackedGf2<U>> for StandardUniform

fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> PackedGf2<U>

Generate a random value of T, using rng as the source of randomness.

fn sample_iter<R>(self, rng: R) -> Iter<Self, R, T>

where R: Rng, Self: Sized,

Create an iterator that generates random values of T, using rng as the source of randomness.

fn map<F, S>(self, func: F) -> Map<Self, F, T, S>

where F: Fn(T) -> S, Self: Sized,

Map sampled values to type S

impl<U: Underlier> Div<Gf2> for PackedGf2<U>

type Output = PackedGf2<U>

The resulting type after applying the / operator.

fn div(self, rhs: Gf2) -> Self

Performs the / operation.

impl<U: Underlier> DivAssign<Gf2> for PackedGf2<U>

fn div_assign(&mut self, rhs: Gf2)

Performs the /= operation.

impl<U: Eq + Underlier> Eq for PackedGf2<U>

impl<U: Underlier> From<Gf2> for PackedGf2<U>

fn from(value: Gf2) -> Self

Converts to this type from the input type.

impl<U: Hash + Underlier> Hash for PackedGf2<U>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<U: Underlier> Mul for PackedGf2<U>

type Output = PackedGf2<U>

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self

Performs the * operation.

impl<U: Underlier> Mul<Gf2> for PackedGf2<U>

type Output = PackedGf2<U>

The resulting type after applying the * operator.

fn mul(self, rhs: Gf2) -> Self

Performs the * operation.

impl<U: Underlier, T: Into<Self>> MulAssign<T> for PackedGf2<U>

fn mul_assign(&mut self, rhs: T)

Performs the *= operation.

impl<U: Underlier> Neg for PackedGf2<U>

type Output = PackedGf2<U>

The resulting type after applying the - operator.

fn neg(self) -> Self

Performs the unary - operation.

impl<U: PartialEq + Underlier> PartialEq for PackedGf2<U>

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl<U: Underlier> PrimeCharacteristicRing for PackedGf2<U>

fn halve(&self) -> Self

Panics

Always panics: 2 is not invertible in characteristic 2.

fn div_2exp_u64(&self, _exp: u64) -> Self

Panics

Always panics: 2 is not invertible in characteristic 2.

const ZERO: Self

The additive identity of the ring.

const ONE: Self

The multiplicative identity of the ring.

const TWO: Self

The element in the ring given by ONE + ONE.

const NEG_ONE: Self

The element in the ring given by -ONE.

type PrimeSubfield = Gf2

The field ℤ/p where the characteristic of this ring is p.

fn from_prime_subfield(f: Self::PrimeSubfield) -> Self

Embed an element of the prime field ℤ/p into the ring R.

fn from_bool(b: bool) -> Self

Return Self::ONE if b is true and Self::ZERO if b is false.

fn double(&self) -> Self

The elementary function double(a) = 2*a.

fn xor(&self, y: &Self) -> Self

Computes the arithmetic generalization of boolean xor.

fn mul_2exp_u64(&self, exp: u64) -> Self

The elementary function mul_2exp_u64(a, exp) = a * 2^{exp}.

fn square(&self) -> Self

The elementary function square(a) = a^2.

fn andn(&self, y: &Self) -> Self

Computes the arithmetic generalization of andnot.

fn bool_check(&self) -> Self

The vanishing polynomial for boolean values: x * (x - 1).

fn from_u8(int: u8) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_u16(int: u16) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_u32(int: u32) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_u64(int: u64) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_u128(int: u128) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_usize(int: usize) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_i8(int: i8) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_i16(int: i16) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_i32(int: i32) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_i64(int: i64) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_i128(int: i128) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_isize(int: isize) -> Self

Given an integer r, return the sum of r copies of ONE:

fn cube(&self) -> Self

The elementary function cube(a) = a^3.

fn xor3(&self, y: &Self, z: &Self) -> Self

Computes the arithmetic generalization of a triple xor.

fn exp_u64(&self, power: u64) -> Self

Exponentiation by a u64 power.

fn exp_const_u64<const POWER: u64>(&self) -> Self

Exponentiation by a small constant power.

fn exp_power_of_2(&self, power_log: usize) -> Self

The elementary function exp_power_of_2(a, power_log) = a^{2^power_log}.

fn powers(&self) -> Powers<Self>

Construct an iterator which returns powers of self: self^0, self^1, self^2, ....

fn shifted_powers(&self, start: Self) -> Powers<Self>

Construct an iterator which returns powers of self shifted by start: start, start*self^1, start*self^2, ....

fn dot_product<const N: usize>(u: &[Self; N], v: &[Self; N]) -> Self

Compute the dot product of two vectors.

fn sum_array<const N: usize>(input: &[Self]) -> Self

Compute the sum of a slice of elements whose length is a compile time constant.

fn zero_vec(len: usize) -> Vec<Self>

Allocates a vector of zero elements of length len. Many operating systems zero pages before assigning them to a userspace process. In that case, our process should not need to write zeros, which would be redundant. However, the compiler may not always recognize this.

impl<U: Underlier> Product for PackedGf2<U>

fn product<I: Iterator<Item = Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by multiplying the items.

impl<U: PartialEq + Underlier> StructuralPartialEq for PackedGf2<U>

impl<U: Underlier> Sub for PackedGf2<U>

type Output = PackedGf2<U>

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self

Performs the - operation.

impl<U: Underlier> Sub<Gf2> for PackedGf2<U>

type Output = PackedGf2<U>

The resulting type after applying the - operator.

fn sub(self, rhs: Gf2) -> Self

Performs the - operation.

impl<U: Underlier, T: Into<Self>> SubAssign<T> for PackedGf2<U>

fn sub_assign(&mut self, rhs: T)

Performs the -= operation.

impl<U: Underlier> Sum for PackedGf2<U>

fn sum<I: Iterator<Item = Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by “summing up” the items.