1// Copyright 2014-2017 Ulrich Kunitz. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package hash
6
7// A is the default constant for Robin-Karp rolling hash. This is a random
8// prime.
9const A = 0x97b548add41d5da1
10
11// RabinKarp supports the computation of a rolling hash.
12type RabinKarp struct {
13	A uint64
14	// a^n
15	aOldest uint64
16	h       uint64
17	p       []byte
18	i       int
19}
20
21// NewRabinKarp creates a new RabinKarp value. The argument n defines the
22// length of the byte sequence to be hashed. The default constant will will be
23// used.
24func NewRabinKarp(n int) *RabinKarp {
25	return NewRabinKarpConst(n, A)
26}
27
28// NewRabinKarpConst creates a new RabinKarp value. The argument n defines the
29// length of the byte sequence to be hashed. The argument a provides the
30// constant used to compute the hash.
31func NewRabinKarpConst(n int, a uint64) *RabinKarp {
32	if n <= 0 {
33		panic("number of bytes n must be positive")
34	}
35	aOldest := uint64(1)
36	// There are faster methods. For the small n required by the LZMA
37	// compressor O(n) is sufficient.
38	for i := 0; i < n; i++ {
39		aOldest *= a
40	}
41	return &RabinKarp{
42		A: a, aOldest: aOldest,
43		p: make([]byte, 0, n),
44	}
45}
46
47// Len returns the length of the byte sequence.
48func (r *RabinKarp) Len() int {
49	return cap(r.p)
50}
51
52// RollByte computes the hash after x has been added.
53func (r *RabinKarp) RollByte(x byte) uint64 {
54	if len(r.p) < cap(r.p) {
55		r.h += uint64(x)
56		r.h *= r.A
57		r.p = append(r.p, x)
58	} else {
59		r.h -= uint64(r.p[r.i]) * r.aOldest
60		r.h += uint64(x)
61		r.h *= r.A
62		r.p[r.i] = x
63		r.i = (r.i + 1) % cap(r.p)
64	}
65	return r.h
66}
67