1 files changed, 146 insertions, 0 deletions
diff --git a/internal/zstd/xxhash.go b/internal/zstd/xxhash.go
new file mode 100644
index 00000000..51d5ff89
--- /dev/null
+++ b/internal/zstd/xxhash.go
@@ -0,0 +1,146 @@
+// Copyright 2023 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package zstd
+
+import (
+	"encoding/binary"
+	"math/bits"
+)
+
+const (
+	xxhPrime64c1 = 0x9e3779b185ebca87
+	xxhPrime64c2 = 0xc2b2ae3d27d4eb4f
+	xxhPrime64c3 = 0x165667b19e3779f9
+	xxhPrime64c4 = 0x85ebca77c2b2ae63
+	xxhPrime64c5 = 0x27d4eb2f165667c5
+)
+
+// xxhash64 is the state of a xxHash-64 checksum.
+type xxhash64 struct {
+	len uint64    // total length hashed
+	v   [4]uint64 // accumulators
+	buf [32]byte  // buffer
+	cnt int       // number of bytes in buffer
+}
+
+// reset discards the current state and prepares to compute a new hash.
+// We assume a seed of 0 since that is what zstd uses.
+func (xh *xxhash64) reset() {
+	xh.len = 0
+
+	// Separate addition for awkward constant overflow.
+	xh.v[0] = xxhPrime64c1
+	xh.v[0] += xxhPrime64c2
+
+	xh.v[1] = xxhPrime64c2
+	xh.v[2] = 0
+
+	// Separate negation for awkward constant overflow.
+	xh.v[3] = xxhPrime64c1
+	xh.v[3] = -xh.v[3]
+
+	clear(xh.buf[:])
+	xh.cnt = 0
+}
+
+// update adds a buffer to the has.
+func (xh *xxhash64) update(b []byte) {
+	xh.len += uint64(len(b))
+
+	if xh.cnt+len(b) < len(xh.buf) {
+		copy(xh.buf[xh.cnt:], b)
+		xh.cnt += len(b)
+		return
+	}
+
+	if xh.cnt > 0 {
+		n := copy(xh.buf[xh.cnt:], b)
+		b = b[n:]
+		xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(xh.buf[:]))
+		xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(xh.buf[8:]))
+		xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(xh.buf[16:]))
+		xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(xh.buf[24:]))
+		xh.cnt = 0
+	}
+
+	for len(b) >= 32 {
+		xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(b))
+		xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(b[8:]))
+		xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(b[16:]))
+		xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(b[24:]))
+		b = b[32:]
+	}
+
+	if len(b) > 0 {
+		copy(xh.buf[:], b)
+		xh.cnt = len(b)
+	}
+}
+
+// digest returns the final hash value.
+func (xh *xxhash64) digest() uint64 {
+	var h64 uint64
+	if xh.len < 32 {
+		h64 = xh.v[2] + xxhPrime64c5
+	} else {
+		h64 = bits.RotateLeft64(xh.v[0], 1) +
+			bits.RotateLeft64(xh.v[1], 7) +
+			bits.RotateLeft64(xh.v[2], 12) +
+			bits.RotateLeft64(xh.v[3], 18)
+		h64 = xh.mergeRound(h64, xh.v[0])
+		h64 = xh.mergeRound(h64, xh.v[1])
+		h64 = xh.mergeRound(h64, xh.v[2])
+		h64 = xh.mergeRound(h64, xh.v[3])
+	}
+
+	h64 += xh.len
+
+	len := xh.len
+	len &= 31
+	buf := xh.buf[:]
+	for len >= 8 {
+		k1 := xh.round(0, binary.LittleEndian.Uint64(buf))
+		buf = buf[8:]
+		h64 ^= k1
+		h64 = bits.RotateLeft64(h64, 27)*xxhPrime64c1 + xxhPrime64c4
+		len -= 8
+	}
+	if len >= 4 {
+		h64 ^= uint64(binary.LittleEndian.Uint32(buf)) * xxhPrime64c1
+		buf = buf[4:]
+		h64 = bits.RotateLeft64(h64, 23)*xxhPrime64c2 + xxhPrime64c3
+		len -= 4
+	}
+	for len > 0 {
+		h64 ^= uint64(buf[0]) * xxhPrime64c5
+		buf = buf[1:]
+		h64 = bits.RotateLeft64(h64, 11) * xxhPrime64c1
+		len--
+	}
+
+	h64 ^= h64 >> 33
+	h64 *= xxhPrime64c2
+	h64 ^= h64 >> 29
+	h64 *= xxhPrime64c3
+	h64 ^= h64 >> 32
+
+	return h64
+}
+
+// round updates a value.
+func (xh *xxhash64) round(v, n uint64) uint64 {
+	v += n * xxhPrime64c2
+	v = bits.RotateLeft64(v, 31)
+	v *= xxhPrime64c1
+	return v
+}
+
+// mergeRound updates a value in the final round.
+func (xh *xxhash64) mergeRound(v, n uint64) uint64 {
+	n = xh.round(0, n)
+	v ^= n
+	v = v*xxhPrime64c1 + xxhPrime64c4
+	return v
+}