1// Copyright 2014 Dmitry Chestnykh. All rights reserved.
  2// Use of this source code is governed by a MIT-style
  3// license that can be found in the LICENSE file.
  4
  5package captcha
  6
  7import "encoding/binary"
  8
  9// siprng is PRNG based on SipHash-2-4.
 10// (Note: it's not safe to use a single siprng from multiple goroutines.)
 11type siprng struct {
 12	k0, k1, ctr uint64
 13}
 14
 15// siphash implements SipHash-2-4, accepting a uint64 as a message.
 16func siphash(k0, k1, m uint64) uint64 {
 17	// Initialization.
 18	v0 := k0 ^ 0x736f6d6570736575
 19	v1 := k1 ^ 0x646f72616e646f6d
 20	v2 := k0 ^ 0x6c7967656e657261
 21	v3 := k1 ^ 0x7465646279746573
 22	t := uint64(8) << 56
 23
 24	// Compression.
 25	v3 ^= m
 26
 27	// Round 1.
 28	v0 += v1
 29	v1 = v1<<13 | v1>>(64-13)
 30	v1 ^= v0
 31	v0 = v0<<32 | v0>>(64-32)
 32
 33	v2 += v3
 34	v3 = v3<<16 | v3>>(64-16)
 35	v3 ^= v2
 36
 37	v0 += v3
 38	v3 = v3<<21 | v3>>(64-21)
 39	v3 ^= v0
 40
 41	v2 += v1
 42	v1 = v1<<17 | v1>>(64-17)
 43	v1 ^= v2
 44	v2 = v2<<32 | v2>>(64-32)
 45
 46	// Round 2.
 47	v0 += v1
 48	v1 = v1<<13 | v1>>(64-13)
 49	v1 ^= v0
 50	v0 = v0<<32 | v0>>(64-32)
 51
 52	v2 += v3
 53	v3 = v3<<16 | v3>>(64-16)
 54	v3 ^= v2
 55
 56	v0 += v3
 57	v3 = v3<<21 | v3>>(64-21)
 58	v3 ^= v0
 59
 60	v2 += v1
 61	v1 = v1<<17 | v1>>(64-17)
 62	v1 ^= v2
 63	v2 = v2<<32 | v2>>(64-32)
 64
 65	v0 ^= m
 66
 67	// Compress last block.
 68	v3 ^= t
 69
 70	// Round 1.
 71	v0 += v1
 72	v1 = v1<<13 | v1>>(64-13)
 73	v1 ^= v0
 74	v0 = v0<<32 | v0>>(64-32)
 75
 76	v2 += v3
 77	v3 = v3<<16 | v3>>(64-16)
 78	v3 ^= v2
 79
 80	v0 += v3
 81	v3 = v3<<21 | v3>>(64-21)
 82	v3 ^= v0
 83
 84	v2 += v1
 85	v1 = v1<<17 | v1>>(64-17)
 86	v1 ^= v2
 87	v2 = v2<<32 | v2>>(64-32)
 88
 89	// Round 2.
 90	v0 += v1
 91	v1 = v1<<13 | v1>>(64-13)
 92	v1 ^= v0
 93	v0 = v0<<32 | v0>>(64-32)
 94
 95	v2 += v3
 96	v3 = v3<<16 | v3>>(64-16)
 97	v3 ^= v2
 98
 99	v0 += v3
100	v3 = v3<<21 | v3>>(64-21)
101	v3 ^= v0
102
103	v2 += v1
104	v1 = v1<<17 | v1>>(64-17)
105	v1 ^= v2
106	v2 = v2<<32 | v2>>(64-32)
107
108	v0 ^= t
109
110	// Finalization.
111	v2 ^= 0xff
112
113	// Round 1.
114	v0 += v1
115	v1 = v1<<13 | v1>>(64-13)
116	v1 ^= v0
117	v0 = v0<<32 | v0>>(64-32)
118
119	v2 += v3
120	v3 = v3<<16 | v3>>(64-16)
121	v3 ^= v2
122
123	v0 += v3
124	v3 = v3<<21 | v3>>(64-21)
125	v3 ^= v0
126
127	v2 += v1
128	v1 = v1<<17 | v1>>(64-17)
129	v1 ^= v2
130	v2 = v2<<32 | v2>>(64-32)
131
132	// Round 2.
133	v0 += v1
134	v1 = v1<<13 | v1>>(64-13)
135	v1 ^= v0
136	v0 = v0<<32 | v0>>(64-32)
137
138	v2 += v3
139	v3 = v3<<16 | v3>>(64-16)
140	v3 ^= v2
141
142	v0 += v3
143	v3 = v3<<21 | v3>>(64-21)
144	v3 ^= v0
145
146	v2 += v1
147	v1 = v1<<17 | v1>>(64-17)
148	v1 ^= v2
149	v2 = v2<<32 | v2>>(64-32)
150
151	// Round 3.
152	v0 += v1
153	v1 = v1<<13 | v1>>(64-13)
154	v1 ^= v0
155	v0 = v0<<32 | v0>>(64-32)
156
157	v2 += v3
158	v3 = v3<<16 | v3>>(64-16)
159	v3 ^= v2
160
161	v0 += v3
162	v3 = v3<<21 | v3>>(64-21)
163	v3 ^= v0
164
165	v2 += v1
166	v1 = v1<<17 | v1>>(64-17)
167	v1 ^= v2
168	v2 = v2<<32 | v2>>(64-32)
169
170	// Round 4.
171	v0 += v1
172	v1 = v1<<13 | v1>>(64-13)
173	v1 ^= v0
174	v0 = v0<<32 | v0>>(64-32)
175
176	v2 += v3
177	v3 = v3<<16 | v3>>(64-16)
178	v3 ^= v2
179
180	v0 += v3
181	v3 = v3<<21 | v3>>(64-21)
182	v3 ^= v0
183
184	v2 += v1
185	v1 = v1<<17 | v1>>(64-17)
186	v1 ^= v2
187	v2 = v2<<32 | v2>>(64-32)
188
189	return v0 ^ v1 ^ v2 ^ v3
190}
191
192// Seed sets a new secret seed for PRNG.
193func (p *siprng) Seed(k [16]byte) {
194	p.k0 = binary.LittleEndian.Uint64(k[0:8])
195	p.k1 = binary.LittleEndian.Uint64(k[8:16])
196	p.ctr = 1
197}
198
199// Uint64 returns a new pseudorandom uint64.
200func (p *siprng) Uint64() uint64 {
201	v := siphash(p.k0, p.k1, p.ctr)
202	p.ctr++
203	return v
204}
205
206func (p *siprng) Bytes(n int) []byte {
207	// Since we don't have a buffer for generated bytes in siprng state,
208	// we just generate enough 8-byte blocks and then cut the result to the
209	// required length. Doing it this way, we lose generated bytes, and we
210	// don't get the strictly sequential deterministic output from PRNG:
211	// calling Uint64() and then Bytes(3) produces different output than
212	// when calling them in the reverse order, but for our applications
213	// this is OK.
214	numBlocks := (n + 8 - 1) / 8
215	b := make([]byte, numBlocks*8)
216	for i := 0; i < len(b); i += 8 {
217		binary.LittleEndian.PutUint64(b[i:], p.Uint64())
218	}
219	return b[:n]
220}
221
222func (p *siprng) Int63() int64 {
223	return int64(p.Uint64() & 0x7fffffffffffffff)
224}
225
226func (p *siprng) Uint32() uint32 {
227	return uint32(p.Uint64())
228}
229
230func (p *siprng) Int31() int32 {
231	return int32(p.Uint32() & 0x7fffffff)
232}
233
234func (p *siprng) Intn(n int) int {
235	if n <= 0 {
236		panic("invalid argument to Intn")
237	}
238	if n <= 1<<31-1 {
239		return int(p.Int31n(int32(n)))
240	}
241	return int(p.Int63n(int64(n)))
242}
243
244func (p *siprng) Int63n(n int64) int64 {
245	if n <= 0 {
246		panic("invalid argument to Int63n")
247	}
248	max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
249	v := p.Int63()
250	for v > max {
251		v = p.Int63()
252	}
253	return v % n
254}
255
256func (p *siprng) Int31n(n int32) int32 {
257	if n <= 0 {
258		panic("invalid argument to Int31n")
259	}
260	max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
261	v := p.Int31()
262	for v > max {
263		v = p.Int31()
264	}
265	return v % n
266}
267
268func (p *siprng) Float64() float64 { return float64(p.Int63()) / (1 << 63) }
269
270// Int returns a pseudorandom int in range [from, to].
271func (p *siprng) Int(from, to int) int {
272	return p.Intn(to+1-from) + from
273}
274
275// Float returns a pseudorandom float64 in range [from, to].
276func (p *siprng) Float(from, to float64) float64 {
277	return (to-from)*p.Float64() + from
278}