glowworm/
lib.rs

1use std::hash::Hasher;
2
3#[derive(Debug, PartialEq)]
4pub struct Glowworm {
5    s: [u64; 32],
6    n: usize,
7    /// Temporaries
8    t: u64,
9    h: u64,
10}
11
12impl Default for Glowworm {
13    fn default() -> Self {
14        Glowworm {
15            s: [
16                14745948531085624800,
17                16120642418826990911,
18                9275000239821960485,
19                4476743750426018428,
20                741912412851399944,
21                17767459926458528083,
22                2469478127305654386,
23                6225995753166195692,
24                4750461123551357503,
25                10555348896626929070,
26                14572814704552083992,
27                2824678681307928227,
28                8198425675642015085,
29                3315257422098907176,
30                13762405054855287671,
31                15186990245784674763,
32                5015234624788364844,
33                8462123041350221017,
34                9974233762935842858,
35                11502466225357323772,
36                17531649588530077495,
37                8670185664686319238,
38                4707560773883213848,
39                10843017560065197706,
40                17676146699030180721,
41                17194224147714809490,
42                4745306135015590921,
43                11298931964348737593,
44                14067901419238702746,
45                15452291037738416485,
46                591116246257296967,
47                15728077675183395515,
48            ],
49            n: 0,
50            t: 5699370651900549022,
51            h: 14745948531085624800,
52        }
53    }
54}
55
56impl Glowworm {
57    /// Call add_bit to add a new bit to the end and return the hash.
58    #[inline]
59    pub fn add_bit(&mut self, bit: u64) -> u64 {
60        let xor = if bit == 0 { 0 } else { 0xffffffff };
61        self.t = self.s[self.n % 32] ^ xor;
62        self.t = (self.t | (self.t >> 1)) ^ (self.t << 1);
63        self.t ^= (self.t >> 4) ^ (self.t >> 8) ^ (self.t >> 16) ^ (self.t >> 32);
64        self.n += 1;
65        self.s[self.n % 32] ^= self.t;
66        self.s[self.n % 32]
67    }
68
69    /// del_bit deletes the last bit; must be passed the last bit of the most recent hash.
70    #[inline]
71    pub fn del_bit(&mut self, bit: u64) -> u64 {
72        self.n -= 1;
73        self.add_bit(bit);
74        self.n -= 1;
75        self.s[self.n % 32]
76    }
77}
78
79impl Hasher for Glowworm {
80    fn finish(&self) -> u64 {
81        self.h
82    }
83
84    fn write(&mut self, bytes: &[u8]) {
85        for byte in bytes {
86            let byte = *byte as u64;
87            self.add_bit(byte & 1);
88            self.add_bit(byte & 2);
89            self.add_bit(byte & 4);
90            self.add_bit(byte & 8);
91            self.add_bit(byte & 16);
92            self.add_bit(byte & 32);
93            self.add_bit(byte & 64);
94            self.add_bit(byte & 128);
95        }
96    }
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    /// Empty state hash.
104    const CHECKVALUE: u64 = 0xCCA4220FC78D45E0;
105
106    #[test]
107    fn same_as_default() {
108        // Uses the algorithm outline in the paper to initialize the hash.
109        let mut a = Glowworm {
110            s: [0; 32],
111            n: 0,
112            t: 1,
113            h: 1,
114        };
115
116        for _ in 0..4096 {
117            a.h = a.add_bit(a.h & 1);
118        }
119        a.n = 0;
120        assert_eq!(a.h, CHECKVALUE);
121
122        let b = Glowworm::default();
123
124        assert_eq!(a, b);
125    }
126
127    #[test]
128    fn add_delete_is_empty() {
129        let mut gw = Glowworm::default();
130        assert_eq!(gw.h, CHECKVALUE);
131
132        let hash = gw.add_bit(1);
133        assert_eq!(hash, 12612998674271867816);
134
135        let hash = gw.add_bit(0);
136        assert_eq!(hash, 3140184078842265393);
137
138        let hash = gw.del_bit(0);
139        assert_eq!(hash, 12612998674271867816);
140
141        let hash = gw.del_bit(1);
142        assert_eq!(hash, CHECKVALUE);
143    }
144
145    #[test]
146    fn hasher() {
147        let mut gw = Glowworm::default();
148        gw.write_u8(u8::MAX);
149        let hash = gw.finish();
150
151        // Check that removing all the bits from u8::MAX resets to the empty state.
152        for _ in 0..8 {
153            gw.del_bit(1);
154        }
155        assert_eq!(gw.h, CHECKVALUE);
156
157        // check that setting all bits to 1 is the same as adding u8::MAX.
158        let mut gw = Glowworm::default();
159        for _ in 0..8 {
160            gw.add_bit(1);
161        }
162        assert_eq!(gw.h, hash);
163
164        // check that order of bit insertion is low to high bits.
165        let mut gw = Glowworm::default();
166        gw.write_u64(u32::MAX as u64);
167        let hash = gw.finish();
168
169        let mut gw = Glowworm::default();
170        for _ in 0..32 {
171            gw.add_bit(1);
172        }
173        for _ in 0..32 {
174            gw.add_bit(0);
175        }
176
177        assert_eq!(gw.h, hash);
178    }
179}
glowworm/lib.rs

glowworm/
lib.rs
