siprng.go (view raw)
1package captcha
2
3import (
4 "crypto/rand"
5 "encoding/binary"
6 "io"
7 "sync"
8)
9
10// siprng is PRNG based on SipHash-2-4.
11type siprng struct {
12 mu sync.Mutex
13 k0, k1, ctr uint64
14}
15
16// siphash implements SipHash-2-4, accepting a uint64 as a message.
17func siphash(k0, k1, m uint64) uint64 {
18 // Initialization.
19 v0 := k0 ^ 0x736f6d6570736575
20 v1 := k1 ^ 0x646f72616e646f6d
21 v2 := k0 ^ 0x6c7967656e657261
22 v3 := k1 ^ 0x7465646279746573
23 t := uint64(8) << 56
24
25 // Compression.
26 v3 ^= m
27
28 // Round 1.
29 v0 += v1
30 v1 = v1<<13 | v1>>(64-13)
31 v1 ^= v0
32 v0 = v0<<32 | v0>>(64-32)
33
34 v2 += v3
35 v3 = v3<<16 | v3>>(64-16)
36 v3 ^= v2
37
38 v0 += v3
39 v3 = v3<<21 | v3>>(64-21)
40 v3 ^= v0
41
42 v2 += v1
43 v1 = v1<<17 | v1>>(64-17)
44 v1 ^= v2
45 v2 = v2<<32 | v2>>(64-32)
46
47 // Round 2.
48 v0 += v1
49 v1 = v1<<13 | v1>>(64-13)
50 v1 ^= v0
51 v0 = v0<<32 | v0>>(64-32)
52
53 v2 += v3
54 v3 = v3<<16 | v3>>(64-16)
55 v3 ^= v2
56
57 v0 += v3
58 v3 = v3<<21 | v3>>(64-21)
59 v3 ^= v0
60
61 v2 += v1
62 v1 = v1<<17 | v1>>(64-17)
63 v1 ^= v2
64 v2 = v2<<32 | v2>>(64-32)
65
66 v0 ^= m
67
68 // Compress last block.
69 v3 ^= t
70
71 // Round 1.
72 v0 += v1
73 v1 = v1<<13 | v1>>(64-13)
74 v1 ^= v0
75 v0 = v0<<32 | v0>>(64-32)
76
77 v2 += v3
78 v3 = v3<<16 | v3>>(64-16)
79 v3 ^= v2
80
81 v0 += v3
82 v3 = v3<<21 | v3>>(64-21)
83 v3 ^= v0
84
85 v2 += v1
86 v1 = v1<<17 | v1>>(64-17)
87 v1 ^= v2
88 v2 = v2<<32 | v2>>(64-32)
89
90 // Round 2.
91 v0 += v1
92 v1 = v1<<13 | v1>>(64-13)
93 v1 ^= v0
94 v0 = v0<<32 | v0>>(64-32)
95
96 v2 += v3
97 v3 = v3<<16 | v3>>(64-16)
98 v3 ^= v2
99
100 v0 += v3
101 v3 = v3<<21 | v3>>(64-21)
102 v3 ^= v0
103
104 v2 += v1
105 v1 = v1<<17 | v1>>(64-17)
106 v1 ^= v2
107 v2 = v2<<32 | v2>>(64-32)
108
109 v0 ^= t
110
111 // Finalization.
112 v2 ^= 0xff
113
114 // Round 1.
115 v0 += v1
116 v1 = v1<<13 | v1>>(64-13)
117 v1 ^= v0
118 v0 = v0<<32 | v0>>(64-32)
119
120 v2 += v3
121 v3 = v3<<16 | v3>>(64-16)
122 v3 ^= v2
123
124 v0 += v3
125 v3 = v3<<21 | v3>>(64-21)
126 v3 ^= v0
127
128 v2 += v1
129 v1 = v1<<17 | v1>>(64-17)
130 v1 ^= v2
131 v2 = v2<<32 | v2>>(64-32)
132
133 // Round 2.
134 v0 += v1
135 v1 = v1<<13 | v1>>(64-13)
136 v1 ^= v0
137 v0 = v0<<32 | v0>>(64-32)
138
139 v2 += v3
140 v3 = v3<<16 | v3>>(64-16)
141 v3 ^= v2
142
143 v0 += v3
144 v3 = v3<<21 | v3>>(64-21)
145 v3 ^= v0
146
147 v2 += v1
148 v1 = v1<<17 | v1>>(64-17)
149 v1 ^= v2
150 v2 = v2<<32 | v2>>(64-32)
151
152 // Round 3.
153 v0 += v1
154 v1 = v1<<13 | v1>>(64-13)
155 v1 ^= v0
156 v0 = v0<<32 | v0>>(64-32)
157
158 v2 += v3
159 v3 = v3<<16 | v3>>(64-16)
160 v3 ^= v2
161
162 v0 += v3
163 v3 = v3<<21 | v3>>(64-21)
164 v3 ^= v0
165
166 v2 += v1
167 v1 = v1<<17 | v1>>(64-17)
168 v1 ^= v2
169 v2 = v2<<32 | v2>>(64-32)
170
171 // Round 4.
172 v0 += v1
173 v1 = v1<<13 | v1>>(64-13)
174 v1 ^= v0
175 v0 = v0<<32 | v0>>(64-32)
176
177 v2 += v3
178 v3 = v3<<16 | v3>>(64-16)
179 v3 ^= v2
180
181 v0 += v3
182 v3 = v3<<21 | v3>>(64-21)
183 v3 ^= v0
184
185 v2 += v1
186 v1 = v1<<17 | v1>>(64-17)
187 v1 ^= v2
188 v2 = v2<<32 | v2>>(64-32)
189
190 return v0 ^ v1 ^ v2 ^ v3
191}
192
193// rekey sets a new PRNG key, which is read from crypto/rand.
194func (p *siprng) rekey() {
195 var k [16]byte
196 if _, err := io.ReadFull(rand.Reader, k[:]); err != nil {
197 panic(err.Error())
198 }
199 p.k0 = binary.LittleEndian.Uint64(k[0:8])
200 p.k1 = binary.LittleEndian.Uint64(k[8:16])
201 p.ctr = 1
202}
203
204// Uint64 returns a new pseudorandom uint64.
205// It rekeys PRNG on the first call and every 64 MB of generated data.
206func (p *siprng) Uint64() uint64 {
207 p.mu.Lock()
208 if p.ctr == 0 || p.ctr > 8*1024*1024 {
209 p.rekey()
210 }
211 v := siphash(p.k0, p.k1, p.ctr)
212 p.ctr++
213 p.mu.Unlock()
214 return v
215}
216
217func (p *siprng) Int63() int64 {
218 return int64(p.Uint64() & 0x7fffffffffffffff)
219}
220
221func (p *siprng) Uint32() uint32 {
222 return uint32(p.Uint64())
223}
224
225func (p *siprng) Int31() int32 {
226 return int32(p.Uint32() & 0x7fffffff)
227}
228
229func (p *siprng) Intn(n int) int {
230 if n <= 0 {
231 panic("invalid argument to Intn")
232 }
233 if n <= 1<<31-1 {
234 return int(p.Int31n(int32(n)))
235 }
236 return int(p.Int63n(int64(n)))
237}
238
239func (p *siprng) Int63n(n int64) int64 {
240 if n <= 0 {
241 panic("invalid argument to Int63n")
242 }
243 max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
244 v := p.Int63()
245 for v > max {
246 v = p.Int63()
247 }
248 return v % n
249}
250
251func (p *siprng) Int31n(n int32) int32 {
252 if n <= 0 {
253 panic("invalid argument to Int31n")
254 }
255 max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
256 v := p.Int31()
257 for v > max {
258 v = p.Int31()
259 }
260 return v % n
261}
262
263func (p *siprng) Float64() float64 { return float64(p.Int63()) / (1 << 63) }