aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/go/_std_1.21/src/internal/zstd/xxhash.go
blob: 4d579ee2d5c0d61e621cdfb37f2aada82336d897 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
// 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
}