Struct BitPackedVector 

pub(super) struct BitPackedVector<F: Field> {
    buf: Vec<u64>,
    naive_buf: Vec<F>,
    num_elements: usize,
    offset: F,
    bits_per_element: usize,
}

A space-efficient representation of an immutable vector of prime field elements. Particularly useful when all elements have values close to each other. It provides an interface similar to that of a Vec.

Encoding method

This struct interpretes elements of the prime field F_p as integers in the range [0, p-1] and tries to encode each with fewer bits than the default of sizeof::<F>() * 8 bits.

In particular, when a new bitpacked vector is created, the BitPackedVector::new method computes the smallest interval [a, b], with a < b, such that all elements v[i] in the input vector (interpreted as integers) belong to [a, b], and then instead of storing v[i], it stores the value (v[i] - a) \in [0, b - a]. If b - a is a small integer, representing v[i] - a can be done using ceil(log_2(b - a + 1)) bits.

It then stores the encoded values compactly by packing together the representation of many consecutive elements into a single machine word (when possible). This encoding can store n elements using a total size of (n * ceil(log_2(b - a + 1)) * word_width) bits.

Notes

1. Currently the implementation uses more storage than the theoretically optimal mentioned above. This is because:
   1. If ceil(log_2(b - a + 1)) > 64, we resort to the standard representation of using sizeof::<F>() bytes. This is because for our use-case, there are not many instances of vectors needing c \in [65, 256] bits to encode each value.
   2. We round ceil(log_2(b - a + 1)) up to the nearest divisor of 64. This is to simplify the implementation by avoiding the situation where the encoding of an element spans multiple words.
2. For optimal performance, the buffer used to store the encoded values should be using machine words (e.g. buf: Vec<usize>) instead of always defaulting to 64-bit entries (buf: Vec<u64>) Here we always assume a 64-bit architecture for the simplicity of the implementation.

Fields

buf: Vec<u64>

The buffer for storing the bit-packed representation. As noted above, for optimal performance, the type of each element should be the machine’s word size. For now, we’re keeping it always to u64 to make it easier to work with F chunks.

Invariant: For every instance of a BitPackedVector, either BitPackedVector::buf or BitPackedVector::naive_buf is populated but NEVER both.

naive_buf: Vec<F>

If during initialization it is deduced that the number of bits needed per element is more than 64, we revert back to a standard representation. In that case, Self::buf is never used but instead Self::naive_buf is populated.

Invariant: For every instance of a BitPackedVector, either BitPackedVector::buf or BitPackedVector::naive_buf is populated but NEVER both.

num_elements: usize

The number of field elements stored in this vector. This is generally different from self.buf.len().

offset: F

The value of the smallest element in the original vector. This is the value of a such that all elements of the original vector belong to the interval [a, b] as described above.

bits_per_element: usize

The number of bits required to represent each element optimally. This is equal to ceil(log_2(b - a + 1)) as described above.

Implementations

impl<F: Field> BitPackedVector<F>

pub fn new(data: &[F]) -> Self

Generates a bit-packed vector initialized with data.

pub fn get(&self, index: usize) -> Option<F>

Return the index-th element stored in the array, or None if index is out of bounds.

pub fn len(&self) -> usize

pub fn get_bits_per_element(&self) -> usize

Returns the number of bits used to encode each element.

pub fn iter(&self) -> BitPackedIterator<'_, F>

Trait Implementations

impl<F: Clone + Field> Clone for BitPackedVector<F>

fn clone(&self) -> BitPackedVector<F>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F: Debug + Field> Debug for BitPackedVector<F>

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

Formats the value using the given formatter.

impl<'de, F> Deserialize<'de> for BitPackedVector<F>

where F: Field,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<F: PartialEq + Field> PartialEq for BitPackedVector<F>

fn eq(&self, other: &BitPackedVector<F>) -> bool

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<F> Serialize for BitPackedVector<F>

where F: Field,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<F: Field> Zeroize for BitPackedVector<F>

fn zeroize(&mut self)

Zero out this object from memory using Rust intrinsics which ensure the zeroization operation is not “optimized away” by the compiler.

impl<F: Field> StructuralPartialEq for BitPackedVector<F>