Documentation
¶
Overview ¶
Example ¶
package main
import (
"fmt"
"hash"
"log"
"github.com/chmduquesne/rollinghash/v4/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
if _, err := rolling.Write(s[:n]); err != nil {
log.Fatal(err)
}
// 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()
if _, err := classic.Write(s[i-n+1 : i+1]); err != nil {
log.Fatal(err)
}
// 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: he quick brown f: checksum 1ab89e68de7c15 e quick brown fo: checksum 1d26864e21619f quick brown fox: checksum 13fdc4aaefcf91 quick brown fox : checksum 1fab0ef7daee4a uick brown fox j: checksum 6aee0bda40445 ick brown fox ju: checksum a8cf05560301d ck brown fox jum: checksum 1945eaabdb6b67 k brown fox jump: checksum 18964a2ca37033 brown fox jumps: checksum 7f1778d0e6456 brown fox jumps : checksum 8d3dd9e2cf5a3 rown fox jumps o: checksum 5e7672798a4e5 own fox jumps ov: checksum 41e75561bd7ce wn fox jumps ove: checksum 1db9e271edcead n fox jumps over: checksum 7aeec087fe22a fox jumps over : checksum 1a3acd0bfd0c1f fox jumps over t: checksum c3620e2c8d91a ox jumps over th: checksum 8b7049026154d x jumps over the: checksum 1f639b25356c1d jumps over the : checksum a7961a2d0f9c4 jumps over the l: checksum 6e3c3ec495a7d umps over the la: checksum a3dbdf68d695e mps over the laz: checksum 1c443a5f275ca7 ps over the lazy: checksum 57e965da5efe2 s over the lazy : checksum 1d457b44849f9d over the lazy d: checksum 1d54040df5f20f over the lazy do: checksum 1aa7779b59c5fb ver the lazy dog: checksum 1d72c7f255ba24
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
- func (d *RabinKarp64) BatchBoundaries(a, b []int32, data []byte, window int, mask uint64) (na, nb int)
- func (d *RabinKarp64) BatchRoll(dst []uint64, data []byte, window int)
- func (d *RabinKarp64) BlockSize() int
- func (d *RabinKarp64) Reset()
- func (d *RabinKarp64) Roll(c byte)
- func (d *RabinKarp64) Size() int
- func (d *RabinKarp64) Sum(b []byte) []byte
- func (d *RabinKarp64) Sum64() uint64
- func (d *RabinKarp64) Write(data []byte) (int, error)
- func (d *RabinKarp64) WriteWindow(w io.Writer) (n int, err error)
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) BatchBoundaries ¶ added in v4.2.0
func (d *RabinKarp64) BatchBoundaries(a, b []int32, data []byte, window int, mask uint64) (na, nb int)
BatchBoundaries reports the window positions where the rolling checksum satisfies sum & mask == 0, fusing the test into the hashing loop (see the boundary fast path). It mirrors BatchRoll exactly, replacing each "dst[i] = uint64(v)" with the masked test. It does not modify the receiver.
func (*RabinKarp64) BatchRoll ¶ added in v4.2.0
func (d *RabinKarp64) BatchRoll(dst []uint64, data []byte, window int)
BatchRoll computes the rolling checksum of every window-sized slice of data in one pass and writes them to dst, which must have len(data)-window+1 elements: dst[i] is the checksum of data[i:i+window]. It is equivalent to Write(data[:window]) followed by a Roll for each subsequent byte, recording Sum64 after each step, but it indexes the leaving byte directly (data[i]) instead of keeping a circular window and rolls two independent lanes so their table-lookup chains overlap in the pipeline. BatchRoll does not modify the receiver; it reads d.pol and fetches the (cached) tables for window.
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
func (*RabinKarp64) Write ¶
func (d *RabinKarp64) Write(data []byte) (int, error)
Write appends data to the rolling window and updates the digest.
func (*RabinKarp64) WriteWindow ¶
func (d *RabinKarp64) WriteWindow(w io.Writer) (n int, err error)
WriteWindow writes the contents of the current window to w.
Source Files