cyclic_poly_23/
lib.rs

1#![forbid(unsafe_code)]
2#![forbid(missing_docs)]
3#![cfg_attr(not(any(feature = "std", test)), no_std)]
4
5//! A recursive/rolling/decomposable hash using cyclic polynomials.
6//! This crate is an implementation of the algorithm given in Section 2.3
7//! of the paper:
8//! > Jonathan D. Cohen, Recursive Hashing Functions for n-Grams,
9//! > ACM Trans. Inf. Syst. 15 (3), 1997.
10//!
11//! Most opensource implementations taken from the paper concentrate on the
12//! algorithms given in the later sections.
13//!
14//! This algorithm is simple and, unlike some of the other algorithms
15//! given in the paper, supports block sizes > the size of the hash word,
16//! i.e. it is possible to hash arbitary data and not just n-Grams.
17//!
18//! Another advantage of the algorithm is that the hash is decomposable as well
19//! as recursive/rolling.
20//!
21//! # Recursive/Rolling
22//!
23//! Is is possible to efficiently search for a block of data with a given hash value
24//! using rolling hash algorithms, such as Adler32 or Cyclic Polynomial hashing.
25//!
26//! Given a hash, `h1`, of the bytes `b[0..n]`, it is possible to efficiently
27//! calculate a second hash, `h2`, of the bytes `b[1..(n+1)]` from `h1`.
28//!
29//! # Decomposable
30//!
31//! Decomposable hash functions are useful for breaking up a large parent block
32//! with a known hash value and calculating the hash values of the smaller child
33//! blocks.
34//!
35//! Given a hash, `h1`, of the bytes `b[0..m]`, and a hash, `h2`, of the
36//! bytes `b[0..n]` where `n < m`, it is possible to efficiently
37//! calculate a hash, `h3`, of the bytes `b[n..m]` given `h1` and `h2`.
38//!
39
40mod cyclic_poly;
41mod hash_value;
42
43pub use cyclic_poly::CyclicPoly;
44
45/// A 32 bit hash.
46pub type CyclicPoly32 = CyclicPoly<u32>;
47/// A 64 bit hash.
48pub type CyclicPoly64 = CyclicPoly<u64>;
cyclic_poly_23/lib.rs

cyclic_poly_23/
lib.rs
