README
¶
Go implementation of Rabin fingerprinting with SSE2 optimizations
Number are based on an Intel Core 2 Duo 2.26ghz:
$ go test -bench=".*"
PASS
Benchmark_Rabin 20000000 105 ns/op
Benchmark_RabinGeneric 10000000 126 ns/op
Benchmark_MD5 2000000 720 ns/op
Benchmark_RabinLong 5 203355985 ns/op
Benchmark_RabinGenericLong 5 214017019 ns/op
Benchmark_Rabin64Long 10 180310324 ns/op
Benchmark_Rabin64GenericLong 10 191728738 ns/op
Benchmark_MD5Long 2 665961119 ns/op
...
Benchmark_Crc64Block 2000 1059137 ns/op
Benchmark_MD5Block 3000 592506 ns/op
Benchmark_Rabin32Block 3000 574193 ns/op
Benchmark_Rabin32GenericBlock 2000 812863 ns/op
Benchmark_Rabin64Block 5000 353489 ns/op
Benchmark_Rabin64GenericBlock 3000 586740 ns/op
In the above, "Generic" versions use native Go implementations. Rabin32 and Rabin64 use SSE and SSE2, respectively,
if available. The SSE/SSE2 optimizations are more of an exercise here, as the performance increase is marginal: 15-40%,
depending on input data size. This is likely because the SSE/SSE2 implementation only optimizes XORs and
consumes data at the same rate as the native versions (due to hash state).
Of interest are the "Block" benchmarks, which run various schemes over 256KB inputs. Benchmark_Crc64Block uses
hash/crc64 from Go's standard library and is a useful comparison with Rabin fingerprinting, since both are
fundamentally similar (i.e., operating with polynomials over GF(2)).
Documentation
¶
Overview ¶
This implements Rabin fingerprinting using a fixed irreducible 64-bit polynomial.
This implements Rabin fingerprinting using a fixed irreducible 64-bit polynomial.
Index ¶
- func CalcPrimes(n int) []int
- func IsPowerOfTwo(v int) bool
- func Log2(v uint64) uint64
- func MakeRabinTables32FromPoly(p *Polynomial) (tables *[4][256]uint64)
- func MakeRabinTables64FromPoly(p *Polynomial) (tables *[8][256]uint64)
- func New() hash.Hash64
- func New64() hash.Hash64
- func RabinFingerprintFixed(data []byte) (fp uint64)
- type Polynomial
- func FindIrreducible(degree int) *Polynomial
- func MakeRandom(gen *rand.Rand, degree int) *Polynomial
- func NewPolynomial(degree uint, coeffs *big.Int) *Polynomial
- func NewPolynomialFromBigInt(coeffs *big.Int) *Polynomial
- func NewPolynomialFromCoeffs(degrees []uint) *Polynomial
- func NewPolynomialFromInt(coeffs int64) *Polynomial
- func NewPolynomialFromUint64(degree uint, coeffs uint64) *Polynomial
- func RabinFingerprint(p *Polynomial, data []byte) *Polynomial
- func (p *Polynomial) Add(x, y *Polynomial) *Polynomial
- func (x *Polynomial) Cmp(y *Polynomial) int
- func (p *Polynomial) Degree() uint
- func (q *Polynomial) Div(x, y *Polynomial) (*Polynomial, *Polynomial)
- func (p *Polynomial) Gcd(a, b *Polynomial) *Polynomial
- func (r *Polynomial) Irreducible() bool
- func (r *Polynomial) Mod(x, p *Polynomial) *Polynomial
- func (z *Polynomial) Mul(x, y *Polynomial) *Polynomial
- func (p *Polynomial) Set(other *Polynomial) *Polynomial
- func (p *Polynomial) SetCoefficient(coeffDeg, v uint) *Polynomial
- func (p *Polynomial) Square(f *Polynomial) *Polynomial
- func (p *Polynomial) String() string
- func (p *Polynomial) Uint64() (uint, uint64)
- type RollingHash
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func CalcPrimes ¶
Use the Sieve of Eratosthenes to determine prime numbers less than n.
func MakeRabinTables32FromPoly ¶
func MakeRabinTables32FromPoly(p *Polynomial) (tables *[4][256]uint64)
p is the irreducible polynomial. This generates the 4 tables TA, TB, TC, TD for fast 32-bit Rabin fingerprinting. (See rabin.tex.)
Note that tables[0] = TA, tables[1] = TB, etc.
func MakeRabinTables64FromPoly ¶
func MakeRabinTables64FromPoly(p *Polynomial) (tables *[8][256]uint64)
p is the irreducible polynomial. This generates the 8 tables TA, TB, TC, TD, TE, TF, TG, TH for fast 64-bit Rabin fingerprinting. (See rabin.tex.)
Note that tables[0] = TA, tables[1] = TB, etc.
func RabinFingerprintFixed ¶
Uses a fixed degree 64 polynomial.
Types ¶
type Polynomial ¶
type Polynomial struct {
// contains filtered or unexported fields
}
Represents a polynomial of degree n in GF(2). The zero value is a polynomial of degree 0 with value 0.
func FindIrreducible ¶
func FindIrreducible(degree int) *Polynomial
Returns an irreducible polynomial of given degree.
func MakeRandom ¶
func MakeRandom(gen *rand.Rand, degree int) *Polynomial
func NewPolynomial ¶
func NewPolynomial(degree uint, coeffs *big.Int) *Polynomial
func NewPolynomialFromBigInt ¶
func NewPolynomialFromBigInt(coeffs *big.Int) *Polynomial
func NewPolynomialFromCoeffs ¶
func NewPolynomialFromCoeffs(degrees []uint) *Polynomial
coeffs must contain the degree of each non-zero element.
func NewPolynomialFromInt ¶
func NewPolynomialFromInt(coeffs int64) *Polynomial
func NewPolynomialFromUint64 ¶
func NewPolynomialFromUint64(degree uint, coeffs uint64) *Polynomial
coeffs corresponds to that returned by the Uint64() method.
func RabinFingerprint ¶
func RabinFingerprint(p *Polynomial, data []byte) *Polynomial
Naively fingerprints the given data using polynomials.
func (*Polynomial) Add ¶
func (p *Polynomial) Add(x, y *Polynomial) *Polynomial
Set p to the sum of (x + y) in GF(2) and returns p.
func (*Polynomial) Cmp ¶
func (x *Polynomial) Cmp(y *Polynomial) int
Compare x and y and returns:
-1 if x < y 0 if x == y +1 if x > y
func (*Polynomial) Degree ¶
func (p *Polynomial) Degree() uint
func (*Polynomial) Div ¶
func (q *Polynomial) Div(x, y *Polynomial) (*Polynomial, *Polynomial)
Sets q = x / y. Returns q and the remainder r.
func (*Polynomial) Gcd ¶
func (p *Polynomial) Gcd(a, b *Polynomial) *Polynomial
Sets p to the GCD of a and b in GF(2) and returns p.
func (*Polynomial) Irreducible ¶
func (r *Polynomial) Irreducible() bool
Returns true if r is irreducible.
r (of degree d) is irreducible iff:
1)
x^{2^d} = x mod r(x)
and
2)
GCD(x^{2^{d/m}} - x, r(x)) = 1 \forall prime divisors m of d.
func (*Polynomial) Mod ¶
func (r *Polynomial) Mod(x, p *Polynomial) *Polynomial
Sets r to x mod p in GF(2) and returns r.
func (*Polynomial) Mul ¶
func (z *Polynomial) Mul(x, y *Polynomial) *Polynomial
func (*Polynomial) Set ¶
func (p *Polynomial) Set(other *Polynomial) *Polynomial
Copies other into p and returns p.
func (*Polynomial) SetCoefficient ¶
func (p *Polynomial) SetCoefficient(coeffDeg, v uint) *Polynomial
Sets the coefficient of given degree to v in p and returns p. v must be 0 or 1 or SetCoefficient will panic.
func (*Polynomial) Square ¶
func (p *Polynomial) Square(f *Polynomial) *Polynomial
Sets p to f^2 and returns p.
func (*Polynomial) String ¶
func (p *Polynomial) String() string
func (*Polynomial) Uint64 ¶
func (p *Polynomial) Uint64() (uint, uint64)
Returns (degree, coefficients). Coefficients holds the state of the variable bits (0, 1, ..., degree - 1). Note that the k-th degree of a k degree polynomial is fixed (ie., 1) in GF(2).
The result is undefined if degree > 64.
type RollingHash ¶
type RollingHash interface {
hash.Hash64
// Drains the oldest bytes oldData from the hash and appends newData.
// This is used for rolling windows.
//
// len(oldData) MUST equal len(newData). This may not be checked,
// and errant behavior may result if this does not hold.
Roll(oldData, newData []byte) (int, error)
}
func NewRolling ¶
func NewRolling(windowSize int) RollingHash
windowSize in bytes. A table will be pre-computed, so a non-negligible setup cost occurs for each rolling hash construction.
Source Files