1// Package xxhash implements the 64-bit variant of xxHash (XXH64) as described 2// at http://cyan4973.github.io/xxHash/. 3package xxhash 4 5import ( 6 "encoding/binary" 7 "hash" 8) 9 10const ( 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). 24var ( 25 prime1v = prime1 26 prime2v = prime2 27 prime3v = prime3 28 prime4v = prime4 29 prime5v = prime5 30) 31 32type 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. 43func New() hash.Hash64 { 44 var x xxh 45 x.Reset() 46 return &x 47} 48 49func (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 58func (x *xxh) Size() int { return 8 } 59func (x *xxh) BlockSize() int { return 32 } 60 61// Write adds more data to x. It always returns len(b), nil. 62func (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 96func (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 111func (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 153func u64(b []byte) uint64 { return binary.LittleEndian.Uint64(b) } 154func u32(b []byte) uint32 { return binary.LittleEndian.Uint32(b) } 155 156func round(acc, input uint64) uint64 { 157 acc += input * prime2 158 acc = rol31(acc) 159 acc *= prime1 160 return acc 161} 162 163func mergeRound(acc, val uint64) uint64 { 164 val = round(0, val) 165 acc ^= val 166 acc = acc*prime1 + prime4 167 return acc 168} 169