rustic_cdc 0.3.1

A library for performing Content-Defined Chunking (CDC) on data streams.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

/// The irreducible polynom to be used in the fingerprint function.
pub trait Polynom {
    /// The degree of the polynom.
    fn degree(&self) -> i32;

    /// Returns the modulo of the polynom.
    #[must_use]
    fn modulo(&self, m: &Self) -> Self;
}

/// A 64 bit polynom.
pub type Polynom64 = u64;

impl Polynom for Polynom64 {
    /// The degree of the polynom.
    // `self` is u64, so `self.leading_zeroes() <= 64` which
    // fits perfectly into a `i32`. (@aawsome)
    #[allow(clippy::cast_possible_wrap)]
    fn degree(&self) -> i32 {
        63 - self.leading_zeros() as i32
    }

    /// Returns the modulo of the polynom.
    fn modulo(&self, m: &Self) -> Self {
        let mut p = *self;
        while p.degree() >= m.degree() {
            p ^= m << (p.degree() - m.degree());
        }

        p
    }
}

#[cfg(test)]
mod tests {
    use crate::*;

    #[test]
    fn polynom_degree() {
        assert_eq!(0u64.degree(), -1);
        assert_eq!(1u64.degree(), 0);

        assert_eq!(((1u64 << 7) - 1).degree(), 6);
        assert_eq!((1u64 << 7).degree(), 7);
        assert_eq!(((1u64 << 7) + 1).degree(), 7);
    }

    #[test]
    fn polynom_modulo() {
        assert_eq!(7u64.modulo(&3), 1);
        assert_eq!(7u64.modulo(&4), 3);
        assert_eq!(7u64.modulo(&2), 1);

        assert_eq!(16u64.modulo(&8), 0);
        assert_eq!(19u64.modulo(&8), 3);

        assert_eq!(16u64.modulo(&4), 0);
        assert_eq!(19u64.modulo(&4), 3);
    }
}