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

#![forbid(unsafe_code)]
#![forbid(missing_docs)]
#![cfg_attr(not(any(feature = "std", test)), no_std)]

//! A recursive/rolling/decomposable hash using cyclic polynomials.
//! This crate is an implementation of the algorithm given in Section 2.3
//! of the paper:
//! > Jonathan D. Cohen, Recursive Hashing Functions for n-Grams,
//! > ACM Trans. Inf. Syst. 15 (3), 1997.
//!
//! Most opensource implementations taken from the paper concentrate on the
//! algorithms given in the later sections.
//!
//! This algorithm is simple and, unlike some of the other algorithms
//! given in the paper, supports block sizes > the size of the hash word,
//! i.e. it is possible to hash arbitary data and not just n-Grams.
//!
//! Another advantage of the algorithm is that the hash is decomposable as well
//! as recursive/rolling.
//!
//! # Recursive/Rolling
//!
//! Is is possible to efficiently search for a block of data with a given hash value
//! using rolling hash algorithms, such as Adler32 or Cyclic Polynomial hashing.
//!
//! Given a hash, `h1`, of the bytes `b[0..n]`, it is possible to efficiently
//! calculate a second hash, `h2`, of the bytes `b[1..(n+1)]` from `h1`.
//!
//! # Decomposable
//!
//! Decomposable hash functions are useful for breaking up a large parent block
//! with a known hash value and calculating the hash values of the smaller child
//! blocks.
//!
//! Given a hash, `h1`, of the bytes `b[0..m]`, and a hash, `h2`, of the
//! bytes `b[0..n]` where `n < m`, it is possible to efficiently
//! calculate a hash, `h3`, of the bytes `b[n..m]` given `h1` and `h2`.
//!

mod cyclic_poly;
mod hash_value;

pub use cyclic_poly::CyclicPoly;

/// A 32 bit hash.
pub type CyclicPoly32 = CyclicPoly<u32>;
/// A 64 bit hash.
pub type CyclicPoly64 = CyclicPoly<u64>;