1 files changed, 66 insertions, 0 deletions

diff --git a/vendor/github.com/ulikunitz/xz/internal/hash/rabin_karp.go b/vendor/github.com/ulikunitz/xz/internal/hash/rabin_karp.go
new file mode 100644
index 0000000..58635b1
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/internal/hash/rabin_karp.go
@@ -0,0 +1,66 @@
+// Copyright 2014-2017 Ulrich Kunitz. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package hash
+
+// A is the default constant for Robin-Karp rolling hash. This is a random
+// prime.
+const A = 0x97b548add41d5da1
+
+// RabinKarp supports the computation of a rolling hash.
+type RabinKarp struct {
+        A uint64
+        // a^n
+        aOldest uint64
+        h       uint64
+        p       []byte
+        i       int
+}
+
+// NewRabinKarp creates a new RabinKarp value. The argument n defines the
+// length of the byte sequence to be hashed. The default constant will will be
+// used.
+func NewRabinKarp(n int) *RabinKarp {
+        return NewRabinKarpConst(n, A)
+}
+
+// NewRabinKarpConst creates a new RabinKarp value. The argument n defines the
+// length of the byte sequence to be hashed. The argument a provides the
+// constant used to compute the hash.
+func NewRabinKarpConst(n int, a uint64) *RabinKarp {
+        if n <= 0 {
+                panic("number of bytes n must be positive")
+        }
+        aOldest := uint64(1)
+        // There are faster methods. For the small n required by the LZMA
+        // compressor O(n) is sufficient.
+        for i := 0; i < n; i++ {
+                aOldest *= a
+        }
+        return &RabinKarp{
+                A: a, aOldest: aOldest,
+                p: make([]byte, 0, n),
+        }
+}
+
+// Len returns the length of the byte sequence.
+func (r *RabinKarp) Len() int {
+        return cap(r.p)
+}
+
+// RollByte computes the hash after x has been added.
+func (r *RabinKarp) RollByte(x byte) uint64 {
+        if len(r.p) < cap(r.p) {
+                r.h += uint64(x)
+                r.h *= r.A
+                r.p = append(r.p, x)
+        } else {
+                r.h -= uint64(r.p[r.i]) * r.aOldest
+                r.h += uint64(x)
+                r.h *= r.A
+                r.p[r.i] = x
+                r.i = (r.i + 1) % cap(r.p)
+        }
+        return r.h
+}