| // 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] | |
| for i := range xh.buf { | |
| xh.buf[i] = 0 | |
| } | |
| 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 | |
| } |