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

// The irreductible polynom to be used in the fingerprint function.
pub trait Polynom {
    fn degree(&self) -> i32;
    fn modulo(&self, m: &Self) -> Self;
}

pub type Polynom64 = u64;

impl Polynom for Polynom64 {
    // The degree of the polynom.
    fn degree(&self) -> i32 {
        for i in (0..63).rev() {
            if *self >= ((1 as Self) << i) {
                return i;
            }
        }

        // The "0" polynom has a degree -1.
        return -1;
    }

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

        return p;
    }
}

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

    #[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);
    }
}