tab_hash/
lib.rs

1//! This crate offers Rust implementations of simple, twisted, and mixed tabulation hashing
2//! for 32-bit and 64-bit integer values.
3//!
4//! Instantiating `Tab32Simple`, `Tab32Twisted`, or `Tab32Mixed` will initialize tables and
5//! create a random hash function from the respective hash family.
6//! The hash value of a 32-bit integer can be computed by calling its `hash` method.
7//!
8//! # Example:
9//!
10//! ```rust
11//! use tab_hash::Tab32Simple;
12//!
13//! let keys = vec![0, 8, 15, 47, 11];
14//! let simple = Tab32Simple::new();
15//! for k in keys {
16//!     println!("{}", simple.hash(k));
17//! }
18//! ```
19//!
20//! To reprocude hashes, save the table used by the hash function and save it.
21//! The function can be recreated using the `with_table` constructor.
22//!
23//! ```rust
24//! use tab_hash::Tab32Twisted;
25//!
26//! let key = 42;
27//! let twisted_1 = Tab32Twisted::new();
28//! let twisted_2 = Tab32Twisted::with_table(twisted_1.get_table());
29//! let twisted_3 = Tab32Twisted::new();
30//! assert_eq!(twisted_1.hash(key), twisted_2.hash(key));
31//! assert_ne!(twisted_1.hash(key), twisted_3.hash(key));
32//! ```
33//!
34//! # Note:
35//! These hash functions do not implement the `std::hash::Hasher` trait,
36//! since they do not work on arbitrary length byte streams.
37//!
38//! # Literature:
39//! This implementation is based on the articles of Mihai Patrascu and Mikkel Thorup:
40//! - [Simple Tabulation Hashing](http://dx.doi.org/10.1145/1993636.1993638)
41//! - [Twisted Tabulation Hashing](https://doi.org/10.1137/1.9781611973105.16)
42//! - [Hashing for Statistics over k-Partitions](https://doi.org/10.1109/FOCS.2015.83)
43//! - [Fast and Powerful Hashing Using Tabulation](https://arxiv.org/abs/1505.01523)
44use serde::{Deserialize, Deserializer, Serialize, Serializer};
45
46/// Split up a 32bit number into 8bit chunks
47fn byte_chunks_32(x: u32) -> [u8; 4] {
48    [
49        (x & 0x0000_00FF) as u8,
50        ((x & 0x0000_FF00) >> 8) as u8,
51        ((x & 0x00FF_0000) >> 16) as u8,
52        ((x & 0xFF00_0000) >> 24) as u8,
53    ]
54}
55
56/// Split up a 64bit number into 8bit chunks
57fn byte_chunks_64(x: u64) -> [u8; 8] {
58    [
59        (x & 0x0000_0000_0000_00FF) as u8,
60        ((x & 0x0000_0000_0000_FF00) >> 8) as u8,
61        ((x & 0x0000_0000_00FF_0000) >> 16) as u8,
62        ((x & 0x0000_0000_FF00_0000) >> 24) as u8,
63        ((x & 0x0000_00FF_0000_0000) >> 32) as u8,
64        ((x & 0x0000_FF00_0000_0000) >> 40) as u8,
65        ((x & 0x00FF_0000_0000_0000) >> 48) as u8,
66        ((x & 0xFF00_0000_0000_0000) >> 56) as u8,
67    ]
68}
69
70/// A universal hash function for 32-bit integers using simple tabulation.
71///
72/// Usage:
73/// ```rust
74/// use tab_hash::Tab32Simple;
75///
76/// let keys = vec![0, 8, 15, 47, 11];
77/// let simple = Tab32Simple::new();
78/// for k in keys {
79///     println!("{}", simple.hash(k));
80/// }
81/// ```
82#[derive(Clone, Deserialize)]
83pub struct Tab32Simple {
84    #[serde(deserialize_with = "tab32simple_from_vec")]
85    table: [[u32; 256]; 4],
86}
87
88impl Tab32Simple {
89    /// Create a new simple tabulation hash function with a random table.
90    pub fn new() -> Self {
91        Tab32Simple {
92            table: Tab32Simple::initialize_table(),
93        }
94    }
95
96    /// Create a new simple tabulation hash function with a random table.
97    pub fn to_vec(&self) -> Vec<Vec<u32>> {
98        let mut vec = Vec::with_capacity(4);
99        for col in self.table.iter() {
100            vec.push(col.to_vec());
101        }
102        vec
103    }
104
105    /// Create a new simple tabulation hash function with a random table.
106    pub fn from_vec(table_data: Vec<Vec<u32>>) -> Self {
107        let mut table = [[0_u32; 256]; 4];
108        assert_eq!(table_data.len(), 4);
109        for (i, column) in table_data.iter().enumerate() {
110            assert_eq!(column.len(), 256);
111            for (j, value) in column.iter().enumerate() {
112                table[i][j] = *value;
113            }
114        }
115        Tab32Simple { table }
116    }
117
118    /// Create a new simple tabulation hash function with a given table.
119    pub fn with_table(table: [[u32; 256]; 4]) -> Self {
120        Tab32Simple { table }
121    }
122
123    /// Generate a table of 32bit uints for simple tabulation hashing
124    fn initialize_table() -> [[u32; 256]; 4] {
125        let table: [[u32; 256]; 4] =
126            array_init::array_init(|_| array_init::array_init(|_| rand::random()));
127        table
128    }
129
130    /// Get the table used by this hash function.
131    pub fn get_table(&self) -> [[u32; 256]; 4] {
132        self.table
133    }
134
135    /// Compute simple tabulation hash value for a 32bit integer number.
136    pub fn hash(&self, x: u32) -> u32 {
137        let mut h: u32 = 0; // initialize hash values as 0
138
139        for (i, c) in byte_chunks_32(x).iter().enumerate() {
140            h ^= self.table[i as usize][*c as usize];
141        }
142        h
143    }
144}
145
146/// Custom serialization converting nested array to a nested vec (cannot be derived)
147fn tab32simple_from_vec<'de, D>(deserializer: D) -> Result<[[u32; 256]; 4], D::Error>
148where
149    D: Deserializer<'de>,
150{
151    let table_data: Vec<Vec<u32>> = Deserialize::deserialize(deserializer)?;
152
153    let mut table = [[0_u32; 256]; 4];
154    assert_eq!(table_data.len(), 4);
155    for (i, column) in table_data.iter().enumerate() {
156        assert_eq!(column.len(), 256);
157        for (j, value) in column.iter().enumerate() {
158            table[i][j] = *value;
159        }
160    }
161    Ok(table)
162}
163
164#[derive(Clone, Serialize)]
165struct _VecTab32Simple {
166    table: Vec<Vec<u32>>,
167}
168
169impl Serialize for Tab32Simple {
170    fn serialize<S>(&self, s: S) -> Result<S::Ok, S::Error>
171    where
172        S: Serializer,
173    {
174        _VecTab32Simple {
175            table: self.to_vec(),
176        }
177        .serialize(s)
178    }
179}
180
181/// A universal hash function for 64-bit integers using simple tabulation.
182///
183/// Usage:
184/// ```rust
185/// use tab_hash::Tab64Simple;
186///
187/// let keys = vec![0, 8, 15, 47, 11];
188/// let simple = Tab64Simple::new();
189/// for k in keys {
190///     println!("{}", simple.hash(k));
191/// }
192/// ```
193#[derive(Clone, Deserialize)]
194pub struct Tab64Simple {
195    #[serde(deserialize_with = "tab64simple_from_vec")]
196    table: [[u64; 256]; 8],
197}
198
199impl Tab64Simple {
200    /// Create a new simple tabulation hash function with a random table.
201    pub fn new() -> Self {
202        Tab64Simple {
203            table: Tab64Simple::initialize_table(),
204        }
205    }
206
207    /// Create a new simple tabulation hash function with a random table.
208    pub fn to_vec(&self) -> Vec<Vec<u64>> {
209        let mut vec = Vec::with_capacity(8);
210        for col in self.table.iter() {
211            vec.push(col.to_vec());
212        }
213        vec
214    }
215
216    /// Create a new simple tabulation hash function with a random table.
217    pub fn from_vec(table_data: Vec<Vec<u64>>) -> Self {
218        let mut table = [[0_u64; 256]; 8];
219        assert_eq!(table_data.len(), 8);
220        for (i, column) in table_data.iter().enumerate() {
221            assert_eq!(column.len(), 256);
222            for (j, value) in column.iter().enumerate() {
223                table[i][j] = *value;
224            }
225        }
226        Tab64Simple { table }
227    }
228
229    /// Create a new simple tabulation hash function with a given table.
230    pub fn with_table(table: [[u64; 256]; 8]) -> Self {
231        Tab64Simple { table }
232    }
233
234    /// Generate a table of 64bit uints for simple tabulation hashing
235    fn initialize_table() -> [[u64; 256]; 8] {
236        let table: [[u64; 256]; 8] =
237            array_init::array_init(|_| array_init::array_init(|_| rand::random()));
238        table
239    }
240
241    /// Get the table used by this hash function.
242    pub fn get_table(&self) -> [[u64; 256]; 8] {
243        self.table
244    }
245
246    /// Compute simple tabulation hash value for a 64bit integer number.
247    pub fn hash(&self, x: u64) -> u64 {
248        let mut h: u64 = 0; // initialize hash values as 0
249
250        for (i, c) in byte_chunks_64(x).iter().enumerate() {
251            h ^= self.table[i as usize][*c as usize];
252        }
253        h
254    }
255}
256
257/// Custom serialization converting nested array to a nested vec (cannot be derived)
258fn tab64simple_from_vec<'de, D>(deserializer: D) -> Result<[[u64; 256]; 8], D::Error>
259where
260    D: Deserializer<'de>,
261{
262    let table_data: Vec<Vec<u64>> = Deserialize::deserialize(deserializer)?;
263
264    let mut table = [[0_u64; 256]; 8];
265    assert_eq!(table_data.len(), 8);
266    for (i, column) in table_data.iter().enumerate() {
267        assert_eq!(column.len(), 256);
268        for (j, value) in column.iter().enumerate() {
269            table[i][j] = *value;
270        }
271    }
272    Ok(table)
273}
274
275#[derive(Clone, Serialize)]
276struct _VecTab64Simple {
277    table: Vec<Vec<u64>>,
278}
279
280impl Serialize for Tab64Simple {
281    fn serialize<S>(&self, s: S) -> Result<S::Ok, S::Error>
282    where
283        S: Serializer,
284    {
285        _VecTab64Simple {
286            table: self.to_vec(),
287        }
288        .serialize(s)
289    }
290}
291
292/// A hash function for 32-bit integers using mixed tabulation.
293///
294/// Mixed tabulation first hashes the four input bytes into a 32-bit intermediate
295/// hash value and four derived bytes. The derived bytes are then hashed by a
296/// second simple tabulation function and XORed into the intermediate value.
297/// This implementation uses `c = d = 4`, where `c` is the number of input
298/// characters and `d` is the number of derived characters.
299///
300/// Usage:
301/// ```rust
302/// use tab_hash::Tab32Mixed;
303///
304/// let keys = vec![0, 8, 15, 47, 11];
305/// let mixed = Tab32Mixed::new();
306/// for k in keys {
307///     println!("{}", mixed.hash(k));
308/// }
309/// ```
310#[derive(Clone, Deserialize)]
311pub struct Tab32Mixed {
312    #[serde(deserialize_with = "tab32mixed_first_from_vec")]
313    first_table: [[u64; 256]; 4],
314    #[serde(deserialize_with = "tab32mixed_second_from_vec")]
315    second_table: [[u32; 256]; 4],
316}
317
318impl Tab32Mixed {
319    /// Create a new mixed tabulation hash function with random tables.
320    pub fn new() -> Self {
321        Tab32Mixed {
322            first_table: array_init::array_init(|_| array_init::array_init(|_| rand::random())),
323            second_table: array_init::array_init(|_| array_init::array_init(|_| rand::random())),
324        }
325    }
326
327    /// Convert the two tables to nested vectors.
328    pub fn to_vec(&self) -> (Vec<Vec<u64>>, Vec<Vec<u32>>) {
329        let first_table = self
330            .first_table
331            .iter()
332            .map(|column| column.to_vec())
333            .collect();
334        let second_table = self
335            .second_table
336            .iter()
337            .map(|column| column.to_vec())
338            .collect();
339        (first_table, second_table)
340    }
341
342    /// Create a mixed tabulation hash function from nested-vector table data.
343    pub fn from_vec(first_table_data: Vec<Vec<u64>>, second_table_data: Vec<Vec<u32>>) -> Self {
344        let mut first_table = [[0_u64; 256]; 4];
345        assert_eq!(first_table_data.len(), 4);
346        for (i, column) in first_table_data.iter().enumerate() {
347            assert_eq!(column.len(), 256);
348            for (j, value) in column.iter().enumerate() {
349                first_table[i][j] = *value;
350            }
351        }
352
353        let mut second_table = [[0_u32; 256]; 4];
354        assert_eq!(second_table_data.len(), 4);
355        for (i, column) in second_table_data.iter().enumerate() {
356            assert_eq!(column.len(), 256);
357            for (j, value) in column.iter().enumerate() {
358                second_table[i][j] = *value;
359            }
360        }
361
362        Tab32Mixed {
363            first_table,
364            second_table,
365        }
366    }
367
368    /// Create a mixed tabulation hash function with the given tables.
369    pub fn with_table(first_table: [[u64; 256]; 4], second_table: [[u32; 256]; 4]) -> Self {
370        Tab32Mixed {
371            first_table,
372            second_table,
373        }
374    }
375
376    /// Get the tables used by this hash function.
377    pub fn get_table(&self) -> ([[u64; 256]; 4], [[u32; 256]; 4]) {
378        (self.first_table, self.second_table)
379    }
380
381    /// Compute a mixed tabulation hash value for a 32-bit integer.
382    pub fn hash(&self, x: u32) -> u32 {
383        let mut first_hash = 0_u64;
384        for (i, c) in byte_chunks_32(x).iter().enumerate() {
385            first_hash ^= self.first_table[i][*c as usize];
386        }
387
388        let derived = byte_chunks_32((first_hash >> 32) as u32);
389        let mut hash = first_hash as u32;
390        for (i, c) in derived.iter().enumerate() {
391            hash ^= self.second_table[i][*c as usize];
392        }
393        hash
394    }
395}
396
397fn tab32mixed_first_from_vec<'de, D>(deserializer: D) -> Result<[[u64; 256]; 4], D::Error>
398where
399    D: Deserializer<'de>,
400{
401    let table_data: Vec<Vec<u64>> = Deserialize::deserialize(deserializer)?;
402    let mut table = [[0_u64; 256]; 4];
403    assert_eq!(table_data.len(), 4);
404    for (i, column) in table_data.iter().enumerate() {
405        assert_eq!(column.len(), 256);
406        for (j, value) in column.iter().enumerate() {
407            table[i][j] = *value;
408        }
409    }
410    Ok(table)
411}
412
413fn tab32mixed_second_from_vec<'de, D>(deserializer: D) -> Result<[[u32; 256]; 4], D::Error>
414where
415    D: Deserializer<'de>,
416{
417    let table_data: Vec<Vec<u32>> = Deserialize::deserialize(deserializer)?;
418    let mut table = [[0_u32; 256]; 4];
419    assert_eq!(table_data.len(), 4);
420    for (i, column) in table_data.iter().enumerate() {
421        assert_eq!(column.len(), 256);
422        for (j, value) in column.iter().enumerate() {
423            table[i][j] = *value;
424        }
425    }
426    Ok(table)
427}
428
429#[derive(Serialize)]
430struct _VecTab32Mixed {
431    first_table: Vec<Vec<u64>>,
432    second_table: Vec<Vec<u32>>,
433}
434
435impl Serialize for Tab32Mixed {
436    fn serialize<S>(&self, s: S) -> Result<S::Ok, S::Error>
437    where
438        S: Serializer,
439    {
440        let (first_table, second_table) = self.to_vec();
441        _VecTab32Mixed {
442            first_table,
443            second_table,
444        }
445        .serialize(s)
446    }
447}
448
449/// A hash function for 64-bit integers using mixed tabulation.
450/// see paper:Dahlgaard, S., Knudsen, M. and Thorup, M., 2017. Practical hash functions for similarity estimation and dimensionality reduction. Advances in neural information processing systems, 30.
451/// The first stage uses eight input-byte lookups to produce a 64-bit intermediate
452/// hash value and eight derived bytes. Eight more lookups hash the derived bytes.
453/// This implementation uses `c = d = 8`, where `c` is the number of input
454/// characters and `d` is the number of derived characters.
455///
456/// Usage:
457/// ```rust
458/// use tab_hash::Tab64Mixed;
459///
460/// let keys = vec![0, 8, 15, 47, 11];
461/// let mixed = Tab64Mixed::new();
462/// for k in keys {
463///     println!("{}", mixed.hash(k));
464/// }
465/// ```
466#[derive(Clone, Deserialize)]
467pub struct Tab64Mixed {
468    #[serde(deserialize_with = "tab64mixed_first_from_vec")]
469    first_table: [[u128; 256]; 8],
470    #[serde(deserialize_with = "tab64mixed_second_from_vec")]
471    second_table: [[u64; 256]; 8],
472}
473
474impl Tab64Mixed {
475    /// Create a new mixed tabulation hash function with random tables.
476    pub fn new() -> Self {
477        Tab64Mixed {
478            first_table: array_init::array_init(|_| array_init::array_init(|_| rand::random())),
479            second_table: array_init::array_init(|_| array_init::array_init(|_| rand::random())),
480        }
481    }
482
483    /// Convert the two tables to nested vectors.
484    pub fn to_vec(&self) -> (Vec<Vec<u128>>, Vec<Vec<u64>>) {
485        let first_table = self
486            .first_table
487            .iter()
488            .map(|column| column.to_vec())
489            .collect();
490        let second_table = self
491            .second_table
492            .iter()
493            .map(|column| column.to_vec())
494            .collect();
495        (first_table, second_table)
496    }
497
498    /// Create a mixed tabulation hash function from nested-vector table data.
499    pub fn from_vec(first_table_data: Vec<Vec<u128>>, second_table_data: Vec<Vec<u64>>) -> Self {
500        let mut first_table = [[0_u128; 256]; 8];
501        assert_eq!(first_table_data.len(), 8);
502        for (i, column) in first_table_data.iter().enumerate() {
503            assert_eq!(column.len(), 256);
504            for (j, value) in column.iter().enumerate() {
505                first_table[i][j] = *value;
506            }
507        }
508
509        let mut second_table = [[0_u64; 256]; 8];
510        assert_eq!(second_table_data.len(), 8);
511        for (i, column) in second_table_data.iter().enumerate() {
512            assert_eq!(column.len(), 256);
513            for (j, value) in column.iter().enumerate() {
514                second_table[i][j] = *value;
515            }
516        }
517
518        Tab64Mixed {
519            first_table,
520            second_table,
521        }
522    }
523
524    /// Create a mixed tabulation hash function with the given tables.
525    pub fn with_table(first_table: [[u128; 256]; 8], second_table: [[u64; 256]; 8]) -> Self {
526        Tab64Mixed {
527            first_table,
528            second_table,
529        }
530    }
531
532    /// Get the tables used by this hash function.
533    pub fn get_table(&self) -> ([[u128; 256]; 8], [[u64; 256]; 8]) {
534        (self.first_table, self.second_table)
535    }
536
537    /// Compute a mixed tabulation hash value for a 64-bit integer.
538    pub fn hash(&self, x: u64) -> u64 {
539        let mut first_hash = 0_u128;
540        for (i, c) in byte_chunks_64(x).iter().enumerate() {
541            first_hash ^= self.first_table[i][*c as usize];
542        }
543
544        let derived = byte_chunks_64((first_hash >> 64) as u64);
545        let mut hash = first_hash as u64;
546        for (i, c) in derived.iter().enumerate() {
547            hash ^= self.second_table[i][*c as usize];
548        }
549        hash
550    }
551}
552
553fn tab64mixed_first_from_vec<'de, D>(deserializer: D) -> Result<[[u128; 256]; 8], D::Error>
554where
555    D: Deserializer<'de>,
556{
557    let table_data: Vec<Vec<u128>> = Deserialize::deserialize(deserializer)?;
558    let mut table = [[0_u128; 256]; 8];
559    assert_eq!(table_data.len(), 8);
560    for (i, column) in table_data.iter().enumerate() {
561        assert_eq!(column.len(), 256);
562        for (j, value) in column.iter().enumerate() {
563            table[i][j] = *value;
564        }
565    }
566    Ok(table)
567}
568
569fn tab64mixed_second_from_vec<'de, D>(deserializer: D) -> Result<[[u64; 256]; 8], D::Error>
570where
571    D: Deserializer<'de>,
572{
573    let table_data: Vec<Vec<u64>> = Deserialize::deserialize(deserializer)?;
574    let mut table = [[0_u64; 256]; 8];
575    assert_eq!(table_data.len(), 8);
576    for (i, column) in table_data.iter().enumerate() {
577        assert_eq!(column.len(), 256);
578        for (j, value) in column.iter().enumerate() {
579            table[i][j] = *value;
580        }
581    }
582    Ok(table)
583}
584
585#[derive(Serialize)]
586struct _VecTab64Mixed {
587    first_table: Vec<Vec<u128>>,
588    second_table: Vec<Vec<u64>>,
589}
590
591impl Serialize for Tab64Mixed {
592    fn serialize<S>(&self, s: S) -> Result<S::Ok, S::Error>
593    where
594        S: Serializer,
595    {
596        let (first_table, second_table) = self.to_vec();
597        _VecTab64Mixed {
598            first_table,
599            second_table,
600        }
601        .serialize(s)
602    }
603}
604
605/// A universal hash function for 32-bit integers using twisted tabulation.
606///
607/// Usage:
608/// ```rust
609/// use tab_hash::Tab32Twisted;
610///
611/// let keys = vec![0, 8, 15, 47, 11];
612/// let twisted = Tab32Twisted::new();
613/// for k in keys {
614///     println!("{}", twisted.hash(k));
615/// }
616/// ```
617#[derive(Clone, Deserialize)]
618pub struct Tab32Twisted {
619    #[serde(deserialize_with = "tab32twisted_from_vec")]
620    table: [[u64; 256]; 4],
621}
622
623impl Tab32Twisted {
624    /// Create a new twisted tabulation hash function with a random table.
625    pub fn new() -> Self {
626        Tab32Twisted {
627            table: Tab32Twisted::initialize_table(),
628        }
629    }
630
631    /// Create a new simple tabulation hash function with a random table.
632    pub fn to_vec(&self) -> Vec<Vec<u64>> {
633        let mut vec = Vec::with_capacity(4);
634        for col in self.table.iter() {
635            vec.push(col.to_vec());
636        }
637        vec
638    }
639
640    /// Create a new simple tabulation hash function with a random table.
641    pub fn from_vec(table_data: Vec<Vec<u64>>) -> Self {
642        let mut table = [[0_u64; 256]; 4];
643        assert_eq!(table_data.len(), 4);
644        for (i, column) in table_data.iter().enumerate() {
645            assert_eq!(column.len(), 256);
646            for (j, value) in column.iter().enumerate() {
647                table[i][j] = *value;
648            }
649        }
650        Tab32Twisted { table }
651    }
652
653    /// Create a new twisted tabulation hash function with a given table.
654    pub fn with_table(table: [[u64; 256]; 4]) -> Self {
655        Tab32Twisted { table }
656    }
657
658    /// Generate a table of 64bit uints for twisted tabulation hashing
659    fn initialize_table() -> [[u64; 256]; 4] {
660        let table: [[u64; 256]; 4] =
661            array_init::array_init(|_| array_init::array_init(|_| rand::random()));
662        table
663    }
664
665    /// Get the table used by this hash function.
666    pub fn get_table(&self) -> [[u64; 256]; 4] {
667        self.table
668    }
669
670    /// Compute twisted tabulation hash value for a 32bit integer number.
671    pub fn hash(&self, x: u32) -> u32 {
672        let mut h: u64 = 0; // initialize hash values as 0
673        let chunks = byte_chunks_32(x);
674        for (i, c) in chunks[0..3].iter().enumerate() {
675            h ^= self.table[i as usize][*c as usize];
676        }
677        // compute address for last chunk by XOring the lowest byte of the
678        // current hash value with the content of the last chunk of the key
679        let c = chunks[3] ^ (h & 0xFF) as u8;
680        h ^= self.table[3][c as usize];
681        // shift out the 32 low bits of the resulting hash
682        h = h.overflowing_shr(32).0;
683
684        h as u32
685    }
686}
687
688/// Custom serialization converting nested array to a nested vec (cannot be derived)
689fn tab32twisted_from_vec<'de, D>(deserializer: D) -> Result<[[u64; 256]; 4], D::Error>
690where
691    D: Deserializer<'de>,
692{
693    let table_data: Vec<Vec<u64>> = Deserialize::deserialize(deserializer)?;
694
695    let mut table = [[0_u64; 256]; 4];
696    assert_eq!(table_data.len(), 4);
697    for (i, column) in table_data.iter().enumerate() {
698        assert_eq!(column.len(), 256);
699        for (j, value) in column.iter().enumerate() {
700            table[i][j] = *value;
701        }
702    }
703    Ok(table)
704}
705
706#[derive(Clone, Serialize)]
707struct _VecTab32Twisted {
708    table: Vec<Vec<u64>>,
709}
710
711impl Serialize for Tab32Twisted {
712    fn serialize<S>(&self, s: S) -> Result<S::Ok, S::Error>
713    where
714        S: Serializer,
715    {
716        _VecTab32Twisted {
717            table: self.to_vec(),
718        }
719        .serialize(s)
720    }
721}
722
723/// A universal hash function for 64-bit integers using twisted tabulation.
724///
725/// Usage:
726/// ```rust
727/// use tab_hash::Tab64Twisted;
728///
729/// let keys = vec![0, 8, 15, 47, 11];
730/// let twisted = Tab64Twisted::new();
731/// for k in keys {
732///     println!("{}", twisted.hash(k));
733/// }
734/// ```
735#[derive(Clone, Deserialize)]
736pub struct Tab64Twisted {
737    #[serde(deserialize_with = "tab64twisted_from_vec")]
738    table: [[u128; 256]; 8],
739}
740
741impl Tab64Twisted {
742    /// Create a new twisted tabulation hash function with a random table.
743    pub fn new() -> Self {
744        Tab64Twisted {
745            table: Tab64Twisted::initialize_table(),
746        }
747    }
748
749    /// Create a new simple tabulation hash function with a random table.
750    pub fn to_vec(&self) -> Vec<Vec<u128>> {
751        let mut vec = Vec::with_capacity(8);
752        for col in self.table.iter() {
753            vec.push(col.to_vec());
754        }
755        vec
756    }
757
758    /// Create a new simple tabulation hash function with a random table.
759    pub fn from_vec(table_data: Vec<Vec<u128>>) -> Self {
760        let mut table = [[0_u128; 256]; 8];
761        assert_eq!(table_data.len(), 8);
762        for (i, column) in table_data.iter().enumerate() {
763            assert_eq!(column.len(), 256);
764            for (j, value) in column.iter().enumerate() {
765                table[i][j] = *value;
766            }
767        }
768        Tab64Twisted { table }
769    }
770
771    /// Create a new twisted tabulation hash function with a given table.
772    pub fn with_table(table: [[u128; 256]; 8]) -> Self {
773        Tab64Twisted { table }
774    }
775
776    /// Generate a table of 128bit uints for twisted tabulation hashing
777    fn initialize_table() -> [[u128; 256]; 8] {
778        let table: [[u128; 256]; 8] =
779            array_init::array_init(|_| array_init::array_init(|_| rand::random()));
780        table
781    }
782
783    /// Get the table used by this hash function.
784    pub fn get_table(&self) -> [[u128; 256]; 8] {
785        self.table
786    }
787
788    /// Compute twisted tabulation hash value for a 64bit integer number.
789    pub fn hash(&self, x: u64) -> u64 {
790        let mut h: u128 = 0; // initialize hash values as 0
791        let chunks = byte_chunks_64(x);
792        for (i, c) in chunks[0..7].iter().enumerate() {
793            h ^= self.table[i as usize][*c as usize];
794        }
795        // compute address for last chunk by XOring the lowest byte of the
796        // current hash value with the content of the last chunk of the key
797        let c = chunks[7] ^ (h & 0xFF) as u8;
798        h ^= self.table[7][c as usize];
799        // shift out the 64 low bits of the resulting hash
800        h = h.overflowing_shr(64).0;
801
802        h as u64
803    }
804}
805
806/// Custom serialization converting nested array to a nested vec (cannot be derived)
807fn tab64twisted_from_vec<'de, D>(deserializer: D) -> Result<[[u128; 256]; 8], D::Error>
808where
809    D: Deserializer<'de>,
810{
811    let table_data: Vec<Vec<u128>> = Deserialize::deserialize(deserializer)?;
812
813    let mut table = [[0_u128; 256]; 8];
814    assert_eq!(table_data.len(), 8);
815    for (i, column) in table_data.iter().enumerate() {
816        assert_eq!(column.len(), 256);
817        for (j, value) in column.iter().enumerate() {
818            table[i][j] = *value;
819        }
820    }
821    Ok(table)
822}
823
824#[derive(Clone, Serialize)]
825struct _VecTab64Twisted {
826    table: Vec<Vec<u128>>,
827}
828
829impl Serialize for Tab64Twisted {
830    fn serialize<S>(&self, s: S) -> Result<S::Ok, S::Error>
831    where
832        S: Serializer,
833    {
834        _VecTab64Twisted {
835            table: self.to_vec(),
836        }
837        .serialize(s)
838    }
839}
840
841// Tests for private methods
842#[test]
843fn byte_chunking_32() {
844    let random_bytes: [u8; 400] = array_init::array_init(|_| rand::random());
845    for four_bytes in random_bytes.chunks(4) {
846        let mut number = 0_u32;
847        for byte in four_bytes.iter().rev() {
848            number = (number << 8) | *byte as u32;
849        }
850        assert_eq!(four_bytes, byte_chunks_32(number));
851    }
852}
853
854#[test]
855fn byte_chunking_64() {
856    let random_bytes: [u8; 480] = array_init::array_init(|_| rand::random());
857    for four_bytes in random_bytes.chunks(8) {
858        let mut number = 0_u64;
859        for byte in four_bytes.iter().rev() {
860            number = (number << 8) | *byte as u64;
861        }
862        assert_eq!(four_bytes, byte_chunks_64(number));
863    }
864}
tab_hash/lib.rs

tab_hash/
lib.rs
