1// Copyright 2023 The Go Authors. 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 zstd 6 7import ( 8 "encoding/binary" 9 "math/bits" 10) 11 12const ( 13 xxhPrime64c1 = 0x9e3779b185ebca87 14 xxhPrime64c2 = 0xc2b2ae3d27d4eb4f 15 xxhPrime64c3 = 0x165667b19e3779f9 16 xxhPrime64c4 = 0x85ebca77c2b2ae63 17 xxhPrime64c5 = 0x27d4eb2f165667c5 18) 19 20// xxhash64 is the state of a xxHash-64 checksum. 21type xxhash64 struct { 22 len uint64 // total length hashed 23 v [4]uint64 // accumulators 24 buf [32]byte // buffer 25 cnt int // number of bytes in buffer 26} 27 28// reset discards the current state and prepares to compute a new hash. 29// We assume a seed of 0 since that is what zstd uses. 30func (xh *xxhash64) reset() { 31 xh.len = 0 32 33 // Separate addition for awkward constant overflow. 34 xh.v[0] = xxhPrime64c1 35 xh.v[0] += xxhPrime64c2 36 37 xh.v[1] = xxhPrime64c2 38 xh.v[2] = 0 39 40 // Separate negation for awkward constant overflow. 41 xh.v[3] = xxhPrime64c1 42 xh.v[3] = -xh.v[3] 43 44 for i := range xh.buf { 45 xh.buf[i] = 0 46 } 47 xh.cnt = 0 48} 49 50// update adds a buffer to the has. 51func (xh *xxhash64) update(b []byte) { 52 xh.len += uint64(len(b)) 53 54 if xh.cnt+len(b) < len(xh.buf) { 55 copy(xh.buf[xh.cnt:], b) 56 xh.cnt += len(b) 57 return 58 } 59 60 if xh.cnt > 0 { 61 n := copy(xh.buf[xh.cnt:], b) 62 b = b[n:] 63 xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(xh.buf[:])) 64 xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(xh.buf[8:])) 65 xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(xh.buf[16:])) 66 xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(xh.buf[24:])) 67 xh.cnt = 0 68 } 69 70 for len(b) >= 32 { 71 xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(b)) 72 xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(b[8:])) 73 xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(b[16:])) 74 xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(b[24:])) 75 b = b[32:] 76 } 77 78 if len(b) > 0 { 79 copy(xh.buf[:], b) 80 xh.cnt = len(b) 81 } 82} 83 84// digest returns the final hash value. 85func (xh *xxhash64) digest() uint64 { 86 var h64 uint64 87 if xh.len < 32 { 88 h64 = xh.v[2] + xxhPrime64c5 89 } else { 90 h64 = bits.RotateLeft64(xh.v[0], 1) + 91 bits.RotateLeft64(xh.v[1], 7) + 92 bits.RotateLeft64(xh.v[2], 12) + 93 bits.RotateLeft64(xh.v[3], 18) 94 h64 = xh.mergeRound(h64, xh.v[0]) 95 h64 = xh.mergeRound(h64, xh.v[1]) 96 h64 = xh.mergeRound(h64, xh.v[2]) 97 h64 = xh.mergeRound(h64, xh.v[3]) 98 } 99 100 h64 += xh.len 101 102 len := xh.len 103 len &= 31 104 buf := xh.buf[:] 105 for len >= 8 { 106 k1 := xh.round(0, binary.LittleEndian.Uint64(buf)) 107 buf = buf[8:] 108 h64 ^= k1 109 h64 = bits.RotateLeft64(h64, 27)*xxhPrime64c1 + xxhPrime64c4 110 len -= 8 111 } 112 if len >= 4 { 113 h64 ^= uint64(binary.LittleEndian.Uint32(buf)) * xxhPrime64c1 114 buf = buf[4:] 115 h64 = bits.RotateLeft64(h64, 23)*xxhPrime64c2 + xxhPrime64c3 116 len -= 4 117 } 118 for len > 0 { 119 h64 ^= uint64(buf[0]) * xxhPrime64c5 120 buf = buf[1:] 121 h64 = bits.RotateLeft64(h64, 11) * xxhPrime64c1 122 len-- 123 } 124 125 h64 ^= h64 >> 33 126 h64 *= xxhPrime64c2 127 h64 ^= h64 >> 29 128 h64 *= xxhPrime64c3 129 h64 ^= h64 >> 32 130 131 return h64 132} 133 134// round updates a value. 135func (xh *xxhash64) round(v, n uint64) uint64 { 136 v += n * xxhPrime64c2 137 v = bits.RotateLeft64(v, 31) 138 v *= xxhPrime64c1 139 return v 140} 141 142// mergeRound updates a value in the final round. 143func (xh *xxhash64) mergeRound(v, n uint64) uint64 { 144 n = xh.round(0, n) 145 v ^= n 146 v = v*xxhPrime64c1 + xxhPrime64c4 147 return v 148} 149