Struct binjs_io::entropy::rw::TableRefStreamState

pub struct TableRefStreamState<T> { /* fields omitted */ }

State of a input/output stream of TableRef.

Used to (de)serialize TableRef, as the encoding of an TableRef may depend on that of previous values.

Format

u32 representation: TableRef interpretation

• Next in Prelude

  • 0: TableRef::Prelude(prelude_latest + 1) where prelude_latest is the latest prelude value encountered so far or -1 if no prelude value has been encountered yet

• Recall Window Range [1, window_len] where window_len is the length of the window, specified when creating the TableRefStreamState

  • 1: Latest value
  • 2: Second latest value
  • ...
  • window_len: ...

• Reference into Prelude Range: [window_len + 1, window_len + prelude_len] where prelude_len is the number of elements in the Prelude.

  • window_len + 1: TableRef::Prelude(0)
  • window_len + 2: TableRef::Prelude(1)
  • ...

• Imported Reference into Shared Range: [window_len + prelude_len + 1, window_len + import_len], where import_len is the number of distinct TableRef::Shared references encountere so far in the stream.

  • window_len + prelude_len + 1: TableRef::Shared(s1) where TableRef::Shared(s1) was the first TableRef::Shared reference encountered in the stream
  • window_len + prelude_len + 2: TableRef::Shared(s2) where TableRef::Shared(s2) was the first TableRef::Shared reference encountered in the stream and distinct from s1
  • window_len + prelude_len + 3: TableRef::Shared(s3) where TableRef::Shared(s1) was the first TableRef::Shared reference encountered in the stream and distinct from s1, s2, ...
  • ...

• First-time Reference into Shared Range: [window_len + prelude_len + import_len + 1, ...[

  • window_len + prelude_len + import_len + 1: TableRef::Shared(0)
  • window_len + prelude_len + import_len + 2: TableRef::Shared(2)
  • ...

Design notes

The main goals of this format are to:

• support both stream reading;
• expose wherever possible patterns that a stream compressor (e.g. brotli) can use to efficiently compress the stream.

Experiments show that the use of 0 and, for some streams, the Recall Window Range, expose such useful patterns.

Experiments show that the dual Imported Shared References/First-time Shared References mechanism considerably decrease the sparsity of references into the shared dictionary. Where raw references into the shared dictionary are typically represented by a 3 bytes long varnum, consisting in unpredictable bytes, this mechanism tends to reduce them to varnums that may be represented with either 1 byte or 2 bytes with a small (hence easy to predict) first byte. In turn, this exposes patterns that the stream compressor may use efficiently.

Methods

impl<T> TableRefStreamState<T> where
    T: Eq + Hash + Clone, 

pub fn new(window_max_len: usize, table: &LinearTable<T>) -> Self

Create a new TableRefStreamState.

window_max_len represents the number of integers to reserve to represent backreferences to values encountered recently.

pub fn from_u32(&mut self, value: u32) -> Option<TableRef>

Decode a TableRef from a u32.

pub fn into_u32(&mut self, value: TableRef) -> u32

Encode an TableRef into a u32.

This method does not perform any kind of sanity check on the TableRef.

Trait Implementations

impl<T: Debug> Debug for TableRefStreamState<T>

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

Formats the value using the given formatter.