Takahiro Suzuki | d7bf820 | 2020-12-17 20:21:59 +0900 | [diff] [blame] | 1 | // Package xxhash implements the 64-bit variant of xxHash (XXH64) as described |
| 2 | // at http://cyan4973.github.io/xxHash/. |
| 3 | package xxhash |
| 4 | |
| 5 | import ( |
| 6 | "encoding/binary" |
| 7 | "hash" |
| 8 | ) |
| 9 | |
| 10 | const ( |
| 11 | prime1 uint64 = 11400714785074694791 |
| 12 | prime2 uint64 = 14029467366897019727 |
| 13 | prime3 uint64 = 1609587929392839161 |
| 14 | prime4 uint64 = 9650029242287828579 |
| 15 | prime5 uint64 = 2870177450012600261 |
| 16 | ) |
| 17 | |
| 18 | // NOTE(caleb): I'm using both consts and vars of the primes. Using consts where |
| 19 | // possible in the Go code is worth a small (but measurable) performance boost |
| 20 | // by avoiding some MOVQs. Vars are needed for the asm and also are useful for |
| 21 | // convenience in the Go code in a few places where we need to intentionally |
| 22 | // avoid constant arithmetic (e.g., v1 := prime1 + prime2 fails because the |
| 23 | // result overflows a uint64). |
| 24 | var ( |
| 25 | prime1v = prime1 |
| 26 | prime2v = prime2 |
| 27 | prime3v = prime3 |
| 28 | prime4v = prime4 |
| 29 | prime5v = prime5 |
| 30 | ) |
| 31 | |
| 32 | type xxh struct { |
| 33 | v1 uint64 |
| 34 | v2 uint64 |
| 35 | v3 uint64 |
| 36 | v4 uint64 |
| 37 | total int |
| 38 | mem [32]byte |
| 39 | n int // how much of mem is used |
| 40 | } |
| 41 | |
| 42 | // New creates a new hash.Hash64 that implements the 64-bit xxHash algorithm. |
| 43 | func New() hash.Hash64 { |
| 44 | var x xxh |
| 45 | x.Reset() |
| 46 | return &x |
| 47 | } |
| 48 | |
| 49 | func (x *xxh) Reset() { |
| 50 | x.n = 0 |
| 51 | x.total = 0 |
| 52 | x.v1 = prime1v + prime2 |
| 53 | x.v2 = prime2 |
| 54 | x.v3 = 0 |
| 55 | x.v4 = -prime1v |
| 56 | } |
| 57 | |
| 58 | func (x *xxh) Size() int { return 8 } |
| 59 | func (x *xxh) BlockSize() int { return 32 } |
| 60 | |
| 61 | // Write adds more data to x. It always returns len(b), nil. |
| 62 | func (x *xxh) Write(b []byte) (n int, err error) { |
| 63 | n = len(b) |
| 64 | x.total += len(b) |
| 65 | |
| 66 | if x.n+len(b) < 32 { |
| 67 | // This new data doesn't even fill the current block. |
| 68 | copy(x.mem[x.n:], b) |
| 69 | x.n += len(b) |
| 70 | return |
| 71 | } |
| 72 | |
| 73 | if x.n > 0 { |
| 74 | // Finish off the partial block. |
| 75 | copy(x.mem[x.n:], b) |
| 76 | x.v1 = round(x.v1, u64(x.mem[0:8])) |
| 77 | x.v2 = round(x.v2, u64(x.mem[8:16])) |
| 78 | x.v3 = round(x.v3, u64(x.mem[16:24])) |
| 79 | x.v4 = round(x.v4, u64(x.mem[24:32])) |
| 80 | b = b[32-x.n:] |
| 81 | x.n = 0 |
| 82 | } |
| 83 | |
| 84 | if len(b) >= 32 { |
| 85 | // One or more full blocks left. |
| 86 | b = writeBlocks(x, b) |
| 87 | } |
| 88 | |
| 89 | // Store any remaining partial block. |
| 90 | copy(x.mem[:], b) |
| 91 | x.n = len(b) |
| 92 | |
| 93 | return |
| 94 | } |
| 95 | |
| 96 | func (x *xxh) Sum(b []byte) []byte { |
| 97 | s := x.Sum64() |
| 98 | return append( |
| 99 | b, |
| 100 | byte(s>>56), |
| 101 | byte(s>>48), |
| 102 | byte(s>>40), |
| 103 | byte(s>>32), |
| 104 | byte(s>>24), |
| 105 | byte(s>>16), |
| 106 | byte(s>>8), |
| 107 | byte(s), |
| 108 | ) |
| 109 | } |
| 110 | |
| 111 | func (x *xxh) Sum64() uint64 { |
| 112 | var h uint64 |
| 113 | |
| 114 | if x.total >= 32 { |
| 115 | v1, v2, v3, v4 := x.v1, x.v2, x.v3, x.v4 |
| 116 | h = rol1(v1) + rol7(v2) + rol12(v3) + rol18(v4) |
| 117 | h = mergeRound(h, v1) |
| 118 | h = mergeRound(h, v2) |
| 119 | h = mergeRound(h, v3) |
| 120 | h = mergeRound(h, v4) |
| 121 | } else { |
| 122 | h = x.v3 + prime5 |
| 123 | } |
| 124 | |
| 125 | h += uint64(x.total) |
| 126 | |
| 127 | i, end := 0, x.n |
| 128 | for ; i+8 <= end; i += 8 { |
| 129 | k1 := round(0, u64(x.mem[i:i+8])) |
| 130 | h ^= k1 |
| 131 | h = rol27(h)*prime1 + prime4 |
| 132 | } |
| 133 | if i+4 <= end { |
| 134 | h ^= uint64(u32(x.mem[i:i+4])) * prime1 |
| 135 | h = rol23(h)*prime2 + prime3 |
| 136 | i += 4 |
| 137 | } |
| 138 | for i < end { |
| 139 | h ^= uint64(x.mem[i]) * prime5 |
| 140 | h = rol11(h) * prime1 |
| 141 | i++ |
| 142 | } |
| 143 | |
| 144 | h ^= h >> 33 |
| 145 | h *= prime2 |
| 146 | h ^= h >> 29 |
| 147 | h *= prime3 |
| 148 | h ^= h >> 32 |
| 149 | |
| 150 | return h |
| 151 | } |
| 152 | |
| 153 | func u64(b []byte) uint64 { return binary.LittleEndian.Uint64(b) } |
| 154 | func u32(b []byte) uint32 { return binary.LittleEndian.Uint32(b) } |
| 155 | |
| 156 | func round(acc, input uint64) uint64 { |
| 157 | acc += input * prime2 |
| 158 | acc = rol31(acc) |
| 159 | acc *= prime1 |
| 160 | return acc |
| 161 | } |
| 162 | |
| 163 | func mergeRound(acc, val uint64) uint64 { |
| 164 | val = round(0, val) |
| 165 | acc ^= val |
| 166 | acc = acc*prime1 + prime4 |
| 167 | return acc |
| 168 | } |