Documentation
¶
Overview ¶
Example ¶
package main
import (
"fmt"
"hash"
"log"
"github.com/chmduquesne/rollinghash/rabinkarp64"
)
func main() {
s := []byte("The quick brown fox jumps over the lazy dog")
classic := hash.Hash64(rabinkarp64.New())
rolling := rabinkarp64.New()
// Window len
n := 16
// You MUST load an initial window into the rolling hash before being
// able to roll bytes
rolling.Write(s[:n])
// Roll it and compare the result with full re-calculus every time
for i := n; i < len(s); i++ {
// Reset and write the window in classic
classic.Reset()
classic.Write(s[i-n+1 : i+1])
// Roll the incoming byte in rolling
rolling.Roll(s[i])
fmt.Printf("%v: checksum %x\n", string(s[i-n+1:i+1]), rolling.Sum64())
// Compare the hashes
if classic.Sum64() != rolling.Sum64() {
log.Fatalf("%v: expected %x, got %x",
string(s[i-n+1:i+1]), classic.Sum64(), rolling.Sum64())
}
}
Output:
Index ¶
- Constants
- type Pol
- func (x Pol) Add(y Pol) Pol
- func (x Pol) Deg() int
- func (x Pol) Div(d Pol) Pol
- func (x Pol) DivMod(d Pol) (Pol, Pol)
- func (x Pol) Expand() string
- func (x Pol) GCD(f Pol) Pol
- func (x Pol) Irreducible() bool
- func (x Pol) Mod(d Pol) Pol
- func (x Pol) Mul(y Pol) Pol
- func (x Pol) MulMod(f, g Pol) Pol
- func (x Pol) String() string
- type RabinKarp64
Examples ¶
Constants ¶
const Size = 8
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Pol ¶
type Pol uint64
Pol is a polynomial from F_2[X].
func DerivePolynomial ¶
DerivePolynomial returns an irreducible polynomial of degree 53 (largest prime number below 64-8) by reading bytes from source. There are (2^53-2/53) irreducible polynomials of degree 53 in F_2[X], c.f. Michael O. Rabin (1981): "Fingerprinting by Random Polynomials", page 4. If no polynomial could be found in one million tries, an error is returned.
func RandomPolynomial ¶
RandomPolynomial returns a new random irreducible polynomial of degree 53 using the input seed as a source. It is equivalent to calling DerivePolynomial(rand.Reader).
func (Pol) DivMod ¶
DivMod returns x / d = q, and remainder r, see https://en.wikipedia.org/wiki/Division_algorithm
func (Pol) Irreducible ¶
Irreducible returns true iff x is irreducible over F_2. This function uses Ben Or's reducibility test.
For details see "Tests and Constructions of Irreducible Polynomials over Finite Fields".
type RabinKarp64 ¶
type RabinKarp64 struct {
// contains filtered or unexported fields
}
func New ¶
func New() *RabinKarp64
New returns a RabinKarp64 digest from the default polynomial obtained when using RandomPolynomial with the seed 1.
func NewFromPol ¶
func NewFromPol(p Pol) *RabinKarp64
NewFromPol returns a RabinKarp64 digest from a polynomial over GF(2). It is assumed that the input polynomial is irreducible. You can obtain such a polynomial using the RandomPolynomial function.
func (*RabinKarp64) Reset ¶
func (d *RabinKarp64) Reset()
Reset resets the running hash to its initial state
func (*RabinKarp64) Roll ¶
func (d *RabinKarp64) Roll(c byte)
Roll updates the checksum of the window from the entering byte. You MUST initialize a window with Write() before calling this method.
func (*RabinKarp64) Sum ¶
func (d *RabinKarp64) Sum(b []byte) []byte
Sum returns the hash as byte slice
Source Files