-
Notifications
You must be signed in to change notification settings - Fork 0
/
wyfast.go
127 lines (104 loc) · 4.54 KB
/
wyfast.go
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
package wyfast
import (
"encoding/binary"
"math/bits"
"sync/atomic"
)
const (
wyp0 = 0xa0761d6478bd642f
wyp1 = 0xe7037ed1a0b428db
wyp2 = 0x8ebc6af09c88c6e3
wyp3 = 0x589965cc75374cc3
wyp4 = 0x1d8e4e27c47d124f
wyp5 = 0x16069317E428CA9
)
// Sum64 returns the 64-bit wyfast hash value for the given key and seed.
func Sum64(key []byte, seed uint64) uint64 {
seed ^= wyp4
p := key
if len(p) == 0 {
return wymix(mulm64(wyp0, seed), wyp4)
}
if len(p) > 64 {
for ; len(p) > 256; p = p[256:] {
seed = mulm64(binary.LittleEndian.Uint64(p[0:8])^wyp0, binary.LittleEndian.Uint64(p[8:16])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[16:24])^wyp1, binary.LittleEndian.Uint64(p[24:32])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[32:40])^wyp2, binary.LittleEndian.Uint64(p[40:48])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[48:56])^wyp3, binary.LittleEndian.Uint64(p[56:64])^seed)
seed = mulm64(binary.LittleEndian.Uint64(p[64:72])^wyp0, binary.LittleEndian.Uint64(p[72:80])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[80:88])^wyp1, binary.LittleEndian.Uint64(p[88:96])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[96:104])^wyp2, binary.LittleEndian.Uint64(p[104:112])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[112:120])^wyp3, binary.LittleEndian.Uint64(p[120:128])^seed)
seed = mulm64(binary.LittleEndian.Uint64(p[128:136])^wyp0, binary.LittleEndian.Uint64(p[136:144])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[144:152])^wyp1, binary.LittleEndian.Uint64(p[152:160])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[160:168])^wyp2, binary.LittleEndian.Uint64(p[168:176])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[176:184])^wyp3, binary.LittleEndian.Uint64(p[184:192])^seed)
seed = mulm64(binary.LittleEndian.Uint64(p[192:200])^wyp0, binary.LittleEndian.Uint64(p[200:208])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[208:216])^wyp1, binary.LittleEndian.Uint64(p[216:224])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[224:232])^wyp2, binary.LittleEndian.Uint64(p[232:240])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[240:248])^wyp3, binary.LittleEndian.Uint64(p[248:256])^seed)
}
for ; len(p) > 64; p = p[64:] {
seed = mulm64(binary.LittleEndian.Uint64(p[0:8])^wyp0, binary.LittleEndian.Uint64(p[8:16])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[16:24])^wyp1, binary.LittleEndian.Uint64(p[24:32])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[32:40])^wyp2, binary.LittleEndian.Uint64(p[40:48])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[48:56])^wyp3, binary.LittleEndian.Uint64(p[56:64])^seed)
}
}
if len(p) > 0 {
switch {
case len(p) < 4:
seed = mulm64(read3(p)^wyp0, seed^wyp1)
case len(p) <= 8:
seed = mulm64(uint64(binary.LittleEndian.Uint32(p[0:4]))^wyp0, uint64(binary.LittleEndian.Uint32(p[len(p)-4:len(p)]))^seed)
case len(p) <= 16:
seed = mulm64(binary.LittleEndian.Uint64(p[0:8])^wyp0, binary.LittleEndian.Uint64(p[len(p)-8:len(p)])^seed)
case len(p) <= 32:
seed = mulm64(binary.LittleEndian.Uint64(p[0:8])^wyp0, binary.LittleEndian.Uint64(p[8:16])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[len(p)-16:len(p)])^wyp1, binary.LittleEndian.Uint64(p[len(p)-8:len(p)])^seed)
case len(p) <= 64:
seed = mulm64(binary.LittleEndian.Uint64(p[0:8])^wyp0, binary.LittleEndian.Uint64(p[8:16])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[16:24])^wyp1, binary.LittleEndian.Uint64(p[24:32])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[len(p)-32:len(p)])^wyp2, binary.LittleEndian.Uint64(p[len(p)-24:len(p)])^seed) ^
mulm64(binary.LittleEndian.Uint64(p[len(p)-16:len(p)])^wyp3, binary.LittleEndian.Uint64(p[len(p)-8:len(p)])^seed)
}
}
return wymix(seed^uint64(len(key)), wyp4)
}
func read3(p []byte) uint64 {
return (uint64(p[0]) << 16) | (uint64(p[len(p)>>1]) << 8) | uint64(p[len(p)-1])
}
func mulm64(a, b uint64) uint64 {
hi, lo := bits.Mul64(a, b)
return hi ^ lo
}
func wymix(a, b uint64) uint64 {
return a ^ b ^ mulm64(a, b)
}
// Rng implements a pseudo-random 64-bit number generator for wyfast
type Rng uint64
// NewRng returns a Rng initialized with the given seed
func NewRng(seed uint64) *Rng {
return (*Rng)(&seed)
}
// Uint64 returns a pseudo-random 64-bit value as a uint64 from the Rng.
// It is safe to call Uint64 concurrently.
func (r *Rng) Uint64() uint64 {
x := atomic.AddUint64((*uint64)(r), wyp0)
return mulm64(x^wyp1, x)
}
// Read len(p) bytes from the Rng
func (r *Rng) Read(p []byte) (n int, err error) {
var pos int
var val uint64
for n = 0; n < len(p); n++ {
if pos == 0 {
val = r.Uint64()
pos = 7
}
p[n] = byte(val)
val >>= 8
pos--
}
return n, nil
}