Documentation
¶
Overview ¶
Package rollinghash implements Rabin hashing (fingerprinting).
The Rabin fingerprinting scheme is a method for implementing fingerprints using polynomials over a finite field. It was proposed by Michael O. Rabin.
The schema of the Rabin hash is defined by a polynomial over GF(2):
p(x) = ... + p₂x² + p₁x + p₀ where pₙ ∈ GF(2)
where p₁,p₂,.. are coefficients that represents the bits of the message in left-to-right most-significant-bit-first order (the values of p₁,p₂,.. can be '0' or '1']). 'x' is multiplier that is powered with the number of the bit in the message. All coefficients are multiplied with this multiplier, because this avoids collisions. For example the messages "abcd" and "cdab" will have different fingerprint hash.
After the above polynomial is calculated we pick a random irreducible polynomial f(x) of degree k over GF(2), and we define the fingerprint of the message m to be the remainder r(x) after division of p(x) mod f(x) over GF(2).
The message to be hashed is likewise interpreted as a polynomial over GF(2), where the coefficients are the bits of the message in left-to-right most-significant-bit-first order. Given a message polynomial m(x) and a hashing polynomial p(x), the Rabin hash is simply the coefficients of m(x) mod p(x).
Rabin hashing efficiently compute a "rolling hash" of data, where the hash value is calculated base on the bytes in the window of the data. This makes the algorithm ideal for splitting the data in chunks with boundaries that are robust when bytes ar shifter to the left of right.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Hash ¶
type Hash interface {
// Value return the value of the hash/sign
Value() uint64
// Next calculate the hash of the next rolling window. The window is shifted with one byte
Next(byte) uint64
}
Hash is the common interface implemented by all rolling hash functions.
func NewRabinFingerprint ¶
NewRabinFingerprint created a new Rabin fingerprint hash.
Source Files