Trait LinearCheck 

pub trait LinearCheck:
    Digest
    + Send
    + Sync {
    type Shift: Clone;

    // Required methods
    fn init_shift(&self) -> Self::Shift;
    fn inc_shift(&self, shift: Self::Shift) -> Self::Shift;
    fn shift(&self, sum: Self::Sum, shift: &Self::Shift) -> Self::Sum;
    fn add(&self, sum_a: Self::Sum, sum_b: &Self::Sum) -> Self::Sum;
    fn negate(&self, sum: Self::Sum) -> Self::Sum;

    // Provided methods
    fn shift_n(&self, n: usize) -> Self::Shift { ... }
    fn find_segments<'a>(
        &self,
        bytes: &'a [Vec<u8>],
        sum: &'a [impl Fn(&'a [u8], usize) -> Option<Self::Sum> + Send + Sync],
        rel: Relativity,
    ) -> Vec<RangePair>  { ... }
    fn find_segments_range<'a>(
        &self,
        bytes: &'a [Vec<u8>],
        sum: &'a [impl Fn(&'a [u8], usize) -> Option<Self::Sum> + Send + Sync],
        start_range: SignedInclRange,
        end_range: SignedInclRange,
    ) -> Vec<RangePair>  { ... }
}

A checksum that also has some notion of linearity.

What does linearity mean here? In a mathematically pure world, it would mean that you could add the texts in some way (XOR for crc) and that would be the same as adding (XORing) both checksums. However, we live in a world that needs practical considerations, so it’s not as clean. Mostly, this is skewed by init and finalize.

This trait adds another type, the Shift type. This acts, when applied to an unfinalized sum in the shift function, as if appending n 0s to the summed text. For example, in a Fletcher sum, this would simply be an integer containing n and applying the shift corresponds to adding the first sum n times to the second one, possible in constant time. However, in the crc case, this is not possible in constant time just using the integer containing n. In this case, the value of of x^{8n} reduced by the generator is stored and the shift is applied using polynomial multiplication modulo the generator.

The assumptions are here (the selfs are omitted for clarity):

• add(a,b) forms an abeliean group with negate(a) as inverse (hereafter, the sum value 0 will be equal to add(init(), negate(init())))
• shift(s, shift_n(1)) == dig(s, 0u8)
• shift(s, shift_n(1)) is bijective in the set of all valid Sum values
• shift(shift(s, shift_n(a)), shift_n(b)) == shift(s, shift_n(a+b))
• add(dig_word(s, 0), dig_word(r, 0)) == dig_word(add(s, r), 0)
• dig_word(s, k) == dig_word(0, k) + dig_word(s, 0) (consequently, dig_word(0, 0) == 0)
• for all sums s, add(finalize(s), negate(s)) is constant (finalize adds a constant value to the sum)
• all methods without default implementations (including those from Digest) should run in constant time (assuming constant Shift, Sum types)

We can also see Digest::Sum as an abelian group with a group action by shift_n: ℤ -> Aut(Digest::Sum) (where LinearCheck::Shift represents some subgroup of Aut(Digest::Sum)). If we call σ = shift_n(1), then for various implementations it is:

• modsum: identity
• fletcher: (s, c) |-> (s, c + s) (note that automorphisms of finite abelian groups generally behave like matrices)
• crc: s |-> s * x^8
• polyhash: s |-> s * factor

dig_word(s, k) is then σ(s) + Sum::from_word(k), shift(s, t) is the application of the automorphism t(s), add and negate are the usual group operations, init_shift is the identity automorphism and inc_shift corresponds to t |-> t * σ.

Required Associated Types

type Shift: Clone

The Shift type (see trait documentation for more).

Required Methods

fn init_shift(&self) -> Self::Shift

The initial shift corresponding to the identity shift of 0 (see trait documentation for more).

fn inc_shift(&self, shift: Self::Shift) -> Self::Shift

Increments the shift by one (see trait documentation for more).

fn shift(&self, sum: Self::Sum, shift: &Self::Shift) -> Self::Sum

Applies a shift to a sum (see trait documentation for more).

fn add(&self, sum_a: Self::Sum, sum_b: &Self::Sum) -> Self::Sum

Adds two sums together (see trait documentation for more).

fn negate(&self, sum: Self::Sum) -> Self::Sum

Gets inverse in the abelian group of add (see trait documentation for more).

Provided Methods

fn shift_n(&self, n: usize) -> Self::Shift

Acts as if applying dig_word(s, 0) n times to to s (see trait documentation for more).

Please implement more efficient (equivalent) implementation for each type if possible.

fn find_segments<'a>( &self, bytes: &'a [Vec<u8>], sum: &'a [impl Fn(&'a [u8], usize) -> Option<Self::Sum> + Send + Sync], rel: Relativity, ) -> Vec<RangePair>

Given some bytes and a target sum, determines all segments in the bytes that have that particular checksum.

Each element of the return value contains a tuple consisting of an array of possible segment starts and an array of possible segment ends. If there are multiple starts or ends, each possible combination has the target checksum.

This function has a high space usage per byte: for n bytes, it uses a total space of n*(8 + 2*sizeof(Sum)) bytes. The time is bounded by the runtime of the sort algorithm, which is around n*log(n). If Hashtables were used, it could be done in linear time, but they take too much space.

fn find_segments_range<'a>( &self, bytes: &'a [Vec<u8>], sum: &'a [impl Fn(&'a [u8], usize) -> Option<Self::Sum> + Send + Sync], start_range: SignedInclRange, end_range: SignedInclRange, ) -> Vec<RangePair>

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<S: BitNum> LinearCheck for CRC<S>

type Shift = S

impl<S: Modnum> LinearCheck for Fletcher<S>

type Shift = S

impl<S: Modnum> LinearCheck for ModSum<S>

type Shift = ()

impl<S: Modnum> LinearCheck for PolyHash<S>

type Shift = S