rollsum/
gear.rs

1use super::Engine;
2use std::default::Default;
3use std::num::Wrapping;
4use std::mem;
5
6/// Default chunk size used by `gear`
7pub const CHUNK_SIZE: u32 = 1 << CHUNK_BITS;
8
9/// Default chunk size used by `gear` (log2)
10pub const CHUNK_BITS: u32 = 13;
11
12
13pub struct Gear {
14    digest: Wrapping<u64>,
15    chunk_bits: u32,
16}
17
18impl Default for Gear {
19    fn default() -> Self {
20        Gear {
21            digest: Wrapping(0),
22            chunk_bits: CHUNK_BITS,
23        }
24    }
25}
26
27
28include!("_gear_rand.rs");
29
30impl Engine for Gear {
31    type Digest = u64;
32
33    #[inline(always)]
34    fn roll_byte(&mut self, b: u8) {
35        self.digest = self.digest << 1;
36        self.digest += Wrapping(unsafe { *G.get_unchecked(b as usize) });
37    }
38
39    #[inline(always)]
40    fn digest(&self) -> u64 {
41        self.digest.0
42    }
43
44    #[inline]
45    fn reset(&mut self) {
46        *self = Gear {
47            chunk_bits: self.chunk_bits,
48            .. Default::default()
49        }
50    }
51}
52
53impl Gear {
54    /// Create new Gear engine with default chunking settings
55    pub fn new() -> Self {
56        Default::default()
57    }
58
59    /// Create new Gear engine with custom chunking settings
60    ///
61    /// `chunk_bits` is number of bits that need to match in
62    /// the edge condition. `CHUNK_BITS` constant is the default.
63    pub fn new_with_chunk_bits(chunk_bits: u32) -> Self {
64        assert!(chunk_bits < 32);
65        Gear {
66            chunk_bits: chunk_bits,
67            ..Default::default()
68        }
69    }
70
71    /// Find chunk edge using Gear defaults.
72    ///
73    /// See `Engine::find_chunk_edge_cond`.
74    pub fn find_chunk_edge(&mut self, buf: &[u8]) -> Option<(usize, u64)> {
75        const DIGEST_SIZE: usize = 64;
76        debug_assert_eq!(
77            mem::size_of::<<Self as Engine>::Digest>() * 8,
78            DIGEST_SIZE
79            );
80        let shift = DIGEST_SIZE as u32 - self.chunk_bits;
81        self.find_chunk_edge_cond(buf, |e: &Gear| (e.digest() >> shift) == 0)
82    }
83}
84
85#[cfg(test)]
86mod tests {
87    use super::{Gear, Engine};
88
89    #[test]
90    fn effective_window_size() {
91        let ones = vec![0x1; 1024];
92        let zeroes = vec![0x0; 1024];
93
94        let mut gear = Gear::new();
95        gear.roll(&ones);
96        let digest = gear.digest();
97
98        let mut gear = Gear::new();
99        gear.roll(&zeroes);
100
101        for (i, &b) in ones.iter().enumerate() {
102            gear.roll_byte(b);
103            if gear.digest() == digest {
104                assert_eq!(i, 63);
105                return;
106            }
107        }
108
109        panic!("matching digest not found");
110    }
111
112    #[cfg(feature = "bench")]
113    mod bench {
114    use test::Bencher;
115    use rand::{Rng, SeedableRng, StdRng};
116    use super::*;
117
118        #[bench]
119        fn gear_perf_1mb(b: &mut Bencher) {
120            let mut v = vec![0x0; 1024 * 1024];
121
122            let seed: &[_] = &[1, 2, 3, 4];
123            let mut rng: StdRng = SeedableRng::from_seed(seed);
124            for i in 0..v.len() {
125                v[i] = rng.gen();
126            }
127
128            b.iter(|| {
129                let mut gear = Gear::new();
130                let mut i = 0;
131                while let Some((new_i, _)) = gear.find_chunk_edge(&v[i..v.len()]) {
132                    i += new_i;
133                    if i == v.len() {
134                        break;
135                    }
136                }
137            });
138        }
139    }
140}
rollsum/gear.rs

rollsum/
gear.rs
