1// Written in 2012-2014 by Dmitry Chestnykh.
2//
3// To the extent possible under law, the author have dedicated all copyright
4// and related and neighboring rights to this software to the public domain
5// worldwide. This software is distributed without any warranty.
6// http://creativecommons.org/publicdomain/zero/1.0/
7
8// Package siphash implements SipHash-2-4, a fast short-input PRF
9// created by Jean-Philippe Aumasson and Daniel J. Bernstein.
10package siphash
11
12import "hash"
13
14const (
15	// BlockSize is the block size of hash algorithm in bytes.
16	BlockSize = 8
17
18	// Size is the size of hash output in bytes.
19	Size = 8
20
21	// Size128 is the size of 128-bit hash output in bytes.
22	Size128 = 16
23)
24
25type digest struct {
26	v0, v1, v2, v3 uint64  // state
27	k0, k1         uint64  // two parts of key
28	x              [8]byte // buffer for unprocessed bytes
29	nx             int     // number of bytes in buffer x
30	size           int     // output size in bytes (8 or 16)
31	t              uint8   // message bytes counter (mod 256)
32}
33
34// newDigest returns a new digest with the given output size in bytes (must be 8 or 16).
35func newDigest(size int, key []byte) *digest {
36	if size != Size && size != Size128 {
37		panic("size must be 8 or 16")
38	}
39	d := new(digest)
40	d.k0 = uint64(key[0]) | uint64(key[1])<<8 | uint64(key[2])<<16 | uint64(key[3])<<24 |
41		uint64(key[4])<<32 | uint64(key[5])<<40 | uint64(key[6])<<48 | uint64(key[7])<<56
42	d.k1 = uint64(key[8]) | uint64(key[9])<<8 | uint64(key[10])<<16 | uint64(key[11])<<24 |
43		uint64(key[12])<<32 | uint64(key[13])<<40 | uint64(key[14])<<48 | uint64(key[15])<<56
44	d.size = size
45	d.Reset()
46	return d
47}
48
49// New returns a new hash.Hash64 computing SipHash-2-4 with 16-byte key and 8-byte output.
50func New(key []byte) hash.Hash64 {
51	return newDigest(Size, key)
52}
53
54// New128 returns a new hash.Hash computing SipHash-2-4 with 16-byte key and 16-byte output.
55//
56// Note that 16-byte output is considered experimental by SipHash authors at this time.
57func New128(key []byte) hash.Hash {
58	return newDigest(Size128, key)
59}
60
61func (d *digest) Reset() {
62	d.v0 = d.k0 ^ 0x736f6d6570736575
63	d.v1 = d.k1 ^ 0x646f72616e646f6d
64	d.v2 = d.k0 ^ 0x6c7967656e657261
65	d.v3 = d.k1 ^ 0x7465646279746573
66	d.t = 0
67	d.nx = 0
68	if d.size == Size128 {
69		d.v1 ^= 0xee
70	}
71}
72
73func (d *digest) Size() int { return d.size }
74
75func (d *digest) BlockSize() int { return BlockSize }
76
77func (d *digest) Write(p []byte) (nn int, err error) {
78	nn = len(p)
79	d.t += uint8(nn)
80	if d.nx > 0 {
81		n := len(p)
82		if n > BlockSize-d.nx {
83			n = BlockSize - d.nx
84		}
85		d.nx += copy(d.x[d.nx:], p)
86		if d.nx == BlockSize {
87			once(d)
88			d.nx = 0
89		}
90		p = p[n:]
91	}
92	if len(p) >= BlockSize {
93		n := len(p) &^ (BlockSize - 1)
94		blocks(d, p[:n])
95		p = p[n:]
96	}
97	if len(p) > 0 {
98		d.nx = copy(d.x[:], p)
99	}
100	return
101}
102
103func (d *digest) Sum64() uint64 {
104	for i := d.nx; i < BlockSize-1; i++ {
105		d.x[i] = 0
106	}
107	d.x[7] = d.t
108	return finalize(d)
109}
110
111func (d0 *digest) sum128() (r0, r1 uint64) {
112	// Make a copy of d0 so that caller can keep writing and summing.
113	d := *d0
114
115	for i := d.nx; i < BlockSize-1; i++ {
116		d.x[i] = 0
117	}
118	d.x[7] = d.t
119	blocks(&d, d.x[:])
120
121	v0, v1, v2, v3 := d.v0, d.v1, d.v2, d.v3
122	v2 ^= 0xee
123
124	// Round 1.
125	v0 += v1
126	v1 = v1<<13 | v1>>(64-13)
127	v1 ^= v0
128	v0 = v0<<32 | v0>>(64-32)
129
130	v2 += v3
131	v3 = v3<<16 | v3>>(64-16)
132	v3 ^= v2
133
134	v0 += v3
135	v3 = v3<<21 | v3>>(64-21)
136	v3 ^= v0
137
138	v2 += v1
139	v1 = v1<<17 | v1>>(64-17)
140	v1 ^= v2
141	v2 = v2<<32 | v2>>(64-32)
142
143	// Round 2.
144	v0 += v1
145	v1 = v1<<13 | v1>>(64-13)
146	v1 ^= v0
147	v0 = v0<<32 | v0>>(64-32)
148
149	v2 += v3
150	v3 = v3<<16 | v3>>(64-16)
151	v3 ^= v2
152
153	v0 += v3
154	v3 = v3<<21 | v3>>(64-21)
155	v3 ^= v0
156
157	v2 += v1
158	v1 = v1<<17 | v1>>(64-17)
159	v1 ^= v2
160	v2 = v2<<32 | v2>>(64-32)
161
162	// Round 3.
163	v0 += v1
164	v1 = v1<<13 | v1>>(64-13)
165	v1 ^= v0
166	v0 = v0<<32 | v0>>(64-32)
167
168	v2 += v3
169	v3 = v3<<16 | v3>>(64-16)
170	v3 ^= v2
171
172	v0 += v3
173	v3 = v3<<21 | v3>>(64-21)
174	v3 ^= v0
175
176	v2 += v1
177	v1 = v1<<17 | v1>>(64-17)
178	v1 ^= v2
179	v2 = v2<<32 | v2>>(64-32)
180
181	// Round 4.
182	v0 += v1
183	v1 = v1<<13 | v1>>(64-13)
184	v1 ^= v0
185	v0 = v0<<32 | v0>>(64-32)
186
187	v2 += v3
188	v3 = v3<<16 | v3>>(64-16)
189	v3 ^= v2
190
191	v0 += v3
192	v3 = v3<<21 | v3>>(64-21)
193	v3 ^= v0
194
195	v2 += v1
196	v1 = v1<<17 | v1>>(64-17)
197	v1 ^= v2
198	v2 = v2<<32 | v2>>(64-32)
199
200	r0 = v0 ^ v1 ^ v2 ^ v3
201
202	v1 ^= 0xdd
203
204	// Round 1.
205	v0 += v1
206	v1 = v1<<13 | v1>>(64-13)
207	v1 ^= v0
208	v0 = v0<<32 | v0>>(64-32)
209
210	v2 += v3
211	v3 = v3<<16 | v3>>(64-16)
212	v3 ^= v2
213
214	v0 += v3
215	v3 = v3<<21 | v3>>(64-21)
216	v3 ^= v0
217
218	v2 += v1
219	v1 = v1<<17 | v1>>(64-17)
220	v1 ^= v2
221	v2 = v2<<32 | v2>>(64-32)
222
223	// Round 2.
224	v0 += v1
225	v1 = v1<<13 | v1>>(64-13)
226	v1 ^= v0
227	v0 = v0<<32 | v0>>(64-32)
228
229	v2 += v3
230	v3 = v3<<16 | v3>>(64-16)
231	v3 ^= v2
232
233	v0 += v3
234	v3 = v3<<21 | v3>>(64-21)
235	v3 ^= v0
236
237	v2 += v1
238	v1 = v1<<17 | v1>>(64-17)
239	v1 ^= v2
240	v2 = v2<<32 | v2>>(64-32)
241
242	// Round 3.
243	v0 += v1
244	v1 = v1<<13 | v1>>(64-13)
245	v1 ^= v0
246	v0 = v0<<32 | v0>>(64-32)
247
248	v2 += v3
249	v3 = v3<<16 | v3>>(64-16)
250	v3 ^= v2
251
252	v0 += v3
253	v3 = v3<<21 | v3>>(64-21)
254	v3 ^= v0
255
256	v2 += v1
257	v1 = v1<<17 | v1>>(64-17)
258	v1 ^= v2
259	v2 = v2<<32 | v2>>(64-32)
260
261	// Round 4.
262	v0 += v1
263	v1 = v1<<13 | v1>>(64-13)
264	v1 ^= v0
265	v0 = v0<<32 | v0>>(64-32)
266
267	v2 += v3
268	v3 = v3<<16 | v3>>(64-16)
269	v3 ^= v2
270
271	v0 += v3
272	v3 = v3<<21 | v3>>(64-21)
273	v3 ^= v0
274
275	v2 += v1
276	v1 = v1<<17 | v1>>(64-17)
277	v1 ^= v2
278	v2 = v2<<32 | v2>>(64-32)
279
280	r1 = v0 ^ v1 ^ v2 ^ v3
281
282	return r0, r1
283}
284
285func (d *digest) Sum(in []byte) []byte {
286	if d.size == Size {
287		r := d.Sum64()
288		in = append(in,
289			byte(r),
290			byte(r>>8),
291			byte(r>>16),
292			byte(r>>24),
293			byte(r>>32),
294			byte(r>>40),
295			byte(r>>48),
296			byte(r>>56))
297	} else {
298		r0, r1 := d.sum128()
299		in = append(in,
300			byte(r0),
301			byte(r0>>8),
302			byte(r0>>16),
303			byte(r0>>24),
304			byte(r0>>32),
305			byte(r0>>40),
306			byte(r0>>48),
307			byte(r0>>56),
308			byte(r1),
309			byte(r1>>8),
310			byte(r1>>16),
311			byte(r1>>24),
312			byte(r1>>32),
313			byte(r1>>40),
314			byte(r1>>48),
315			byte(r1>>56))
316	}
317	return in
318}
319