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