Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 485 lines (415 sloc) 10.972 kB
525cb66 @nobu siphash
nobu authored
1 #include <string.h>
2 #include <stdio.h>
3 #include "siphash.h"
4 #ifndef SIP_HASH_STREAMING
5 #define SIP_HASH_STREAMING 1
6 #endif
7
8 #ifdef _WIN32
9 #define BYTE_ORDER __LITTLE_ENDIAN
10 #elif !defined BYTE_ORDER
11 #include <endian.h>
12 #endif
13 #ifndef LITTLE_ENDIAN
14 #define LITTLE_ENDIAN __LITTLE_ENDIAN
15 #endif
16 #ifndef BIG_ENDIAN
17 #define BIG_ENDIAN __BIG_ENDIAN
18 #endif
19
20 #if BYTE_ORDER == LITTLE_ENDIAN
21 #define lo u32[0]
22 #define hi u32[1]
23 #elif BYTE_ORDER == BIG_ENDIAN
24 #define hi u32[0]
25 #define lo u32[1]
26 #else
27 #error "Only strictly little or big endian supported"
28 #endif
29
30 #ifndef UNALIGNED_WORD_ACCESS
31 # if defined(__i386) || defined(__i386__) || defined(_M_IX86) || \
29f347a @nurse * regint.h: fix typo: _M_AMD86 -> _M_AMD64.
nurse authored
32 defined(__x86_64) || defined(__x86_64__) || defined(_M_AMD64) || \
63360be @nobu UNALIGNED_WORD_ACCESS on ppc64
nobu authored
33 defined(__powerpc64__) || \
525cb66 @nobu siphash
nobu authored
34 defined(__mc68020__)
35 # define UNALIGNED_WORD_ACCESS 1
36 # endif
37 #endif
38 #ifndef UNALIGNED_WORD_ACCESS
39 # define UNALIGNED_WORD_ACCESS 0
40 #endif
41
42 #define U8TO32_LE(p) \
43 (((uint32_t)((p)[0]) ) | ((uint32_t)((p)[1]) << 8) | \
44 ((uint32_t)((p)[2]) << 16) | ((uint32_t)((p)[3]) << 24)) \
45
46 #define U32TO8_LE(p, v) \
47 do { \
48 (p)[0] = (uint8_t)((v) ); \
49 (p)[1] = (uint8_t)((v) >> 8); \
50 (p)[2] = (uint8_t)((v) >> 16); \
51 (p)[3] = (uint8_t)((v) >> 24); \
52 } while (0)
53
54 #ifdef HAVE_UINT64_T
55 #define U8TO64_LE(p) \
56 ((uint64_t)U8TO32_LE(p) | ((uint64_t)U8TO32_LE((p) + 4)) << 32 )
57
58 #define U64TO8_LE(p, v) \
59 do { \
60 U32TO8_LE((p), (uint32_t)((v) )); \
61 U32TO8_LE((p) + 4, (uint32_t)((v) >> 32)); \
62 } while (0)
63
64 #define ROTL64(v, s) \
65 ((v) << (s)) | ((v) >> (64 - (s)))
66
67 #define ROTL64_TO(v, s) ((v) = ROTL64((v), (s)))
68
69 #define ADD64_TO(v, s) ((v) += (s))
70 #define XOR64_TO(v, s) ((v) ^= (s))
71 #define XOR64_INT(v, x) ((v) ^= (x))
72 #else
73 #define U8TO64_LE(p) u8to64_le(p)
74 static inline uint64_t
75 u8to64_le(const uint8_t *p)
76 {
77 uint64_t ret;
78 ret.lo = U8TO32_LE(p);
79 ret.hi = U8TO32_LE(p + 4);
80 return ret;
81 }
82
83 #define U64TO8_LE(p, v) u64to8_le(p, v)
84 static inline void
85 u64to8_le(uint8_t *p, uint64_t v)
86 {
87 U32TO8_LE(p, v.lo);
88 U32TO8_LE(p + 4, v.hi);
89 }
90
91 #define ROTL64_TO(v, s) ((s) > 32 ? rotl64_swap(rotl64_to(&(v), (s) - 32)) : \
92 (s) == 32 ? rotl64_swap(&(v)) : rotl64_to(&(v), (s)))
93 static inline uint64_t *
94 rotl64_to(uint64_t *v, unsigned int s)
95 {
96 uint32_t uhi = (v->hi << s) | (v->lo >> (32 - s));
97 uint32_t ulo = (v->lo << s) | (v->hi >> (32 - s));
98 v->hi = uhi;
99 v->lo = ulo;
100 return v;
101 }
102
103 static inline uint64_t *
104 rotl64_swap(uint64_t *v)
105 {
106 uint32_t t = v->lo;
107 v->lo = v->hi;
108 v->hi = t;
109 return v;
110 }
111
112 #define ADD64_TO(v, s) add64_to(&(v), (s))
113 static inline uint64_t *
114 add64_to(uint64_t *v, const uint64_t s)
115 {
116 v->lo += s.lo;
117 v->hi += s.hi;
118 if (v->lo < s.lo) v->hi++;
119 return v;
120 }
121
122 #define XOR64_TO(v, s) xor64_to(&(v), (s))
123 static inline uint64_t *
124 xor64_to(uint64_t *v, const uint64_t s)
125 {
126 v->lo ^= s.lo;
127 v->hi ^= s.hi;
128 return v;
129 }
130
131 #define XOR64_INT(v, x) ((v).lo ^= (x))
132 #endif
133
496d7cc @nobu siphash.c: union sip_init_state
nobu authored
134 static const union {
135 char bin[32];
136 uint64_t u64[4];
137 } sip_init_state_bin = {"uespemos""modnarod""arenegyl""setybdet"};
138 #define sip_init_state sip_init_state_bin.u64
525cb66 @nobu siphash
nobu authored
139
140 #if SIP_HASH_STREAMING
141 struct sip_interface_st {
142 void (*init)(sip_state *s, const uint8_t *key);
143 void (*update)(sip_state *s, const uint8_t *data, size_t len);
144 void (*final)(sip_state *s, uint64_t *digest);
145 };
146
147 static void int_sip_init(sip_state *state, const uint8_t *key);
148 static void int_sip_update(sip_state *state, const uint8_t *data, size_t len);
149 static void int_sip_final(sip_state *state, uint64_t *digest);
150
151 static const sip_interface sip_methods = {
152 int_sip_init,
153 int_sip_update,
154 int_sip_final
155 };
156 #endif /* SIP_HASH_STREAMING */
157
158 #define SIP_COMPRESS(v0, v1, v2, v3) \
159 do { \
160 ADD64_TO((v0), (v1)); \
161 ADD64_TO((v2), (v3)); \
162 ROTL64_TO((v1), 13); \
163 ROTL64_TO((v3), 16); \
164 XOR64_TO((v1), (v0)); \
165 XOR64_TO((v3), (v2)); \
166 ROTL64_TO((v0), 32); \
167 ADD64_TO((v2), (v1)); \
168 ADD64_TO((v0), (v3)); \
169 ROTL64_TO((v1), 17); \
170 ROTL64_TO((v3), 21); \
171 XOR64_TO((v1), (v2)); \
172 XOR64_TO((v3), (v0)); \
173 ROTL64_TO((v2), 32); \
174 } while(0)
175
176 #if SIP_HASH_STREAMING
177 static void
178 int_sip_dump(sip_state *state)
179 {
180 int v;
181
182 for (v = 0; v < 4; v++) {
183 #if HAVE_UINT64_T
184 printf("v%d: %" PRIx64 "\n", v, state->v[v]);
185 #else
186 printf("v%d: %" PRIx32 "%.8" PRIx32 "\n", v, state->v[v].hi, state->v[v].lo);
187 #endif
188 }
189 }
190
191 static void
192 int_sip_init(sip_state *state, const uint8_t key[16])
193 {
194 uint64_t k0, k1;
195
196 k0 = U8TO64_LE(key);
197 k1 = U8TO64_LE(key + sizeof(uint64_t));
198
199 state->v[0] = k0; XOR64_TO(state->v[0], sip_init_state[0]);
200 state->v[1] = k1; XOR64_TO(state->v[1], sip_init_state[1]);
201 state->v[2] = k0; XOR64_TO(state->v[2], sip_init_state[2]);
202 state->v[3] = k1; XOR64_TO(state->v[3], sip_init_state[3]);
203 }
204
205 static inline void
206 int_sip_round(sip_state *state, int n)
207 {
208 int i;
209
210 for (i = 0; i < n; i++) {
211 SIP_COMPRESS(state->v[0], state->v[1], state->v[2], state->v[3]);
212 }
213 }
214
215 static inline void
216 int_sip_update_block(sip_state *state, uint64_t m)
217 {
218 XOR64_TO(state->v[3], m);
219 int_sip_round(state, state->c);
220 XOR64_TO(state->v[0], m);
221 }
222
223 static inline void
224 int_sip_pre_update(sip_state *state, const uint8_t **pdata, size_t *plen)
225 {
226 int to_read;
227 uint64_t m;
228
229 if (!state->buflen) return;
230
231 to_read = sizeof(uint64_t) - state->buflen;
232 memcpy(state->buf + state->buflen, *pdata, to_read);
233 m = U8TO64_LE(state->buf);
234 int_sip_update_block(state, m);
235 *pdata += to_read;
236 *plen -= to_read;
237 state->buflen = 0;
238 }
239
240 static inline void
241 int_sip_post_update(sip_state *state, const uint8_t *data, size_t len)
242 {
243 uint8_t r = len % sizeof(uint64_t);
244 if (r) {
245 memcpy(state->buf, data + len - r, r);
246 state->buflen = r;
247 }
248 }
249
250 static void
251 int_sip_update(sip_state *state, const uint8_t *data, size_t len)
252 {
253 uint64_t *end;
254 uint64_t *data64;
255
256 state->msglen_byte = state->msglen_byte + (len % 256);
257 data64 = (uint64_t *) data;
258
259 int_sip_pre_update(state, &data, &len);
260
261 end = data64 + (len / sizeof(uint64_t));
262
263 #if BYTE_ORDER == LITTLE_ENDIAN
264 while (data64 != end) {
265 int_sip_update_block(state, *data64++);
266 }
267 #elif BYTE_ORDER == BIG_ENDIAN
268 {
269 uint64_t m;
270 uint8_t *data8 = data;
271 for (; data8 != (uint8_t *) end; data8 += sizeof(uint64_t)) {
272 m = U8TO64_LE(data8);
273 int_sip_update_block(state, m);
274 }
275 }
276 #endif
277
278 int_sip_post_update(state, data, len);
279 }
280
281 static inline void
282 int_sip_pad_final_block(sip_state *state)
283 {
284 int i;
5bde05f @nurse Use C90 comment style
nurse authored
285 /* pad with 0's and finalize with msg_len mod 256 */
525cb66 @nobu siphash
nobu authored
286 for (i = state->buflen; i < sizeof(uint64_t); i++) {
287 state->buf[i] = 0x00;
288 }
289 state->buf[sizeof(uint64_t) - 1] = state->msglen_byte;
290 }
291
292 static void
293 int_sip_final(sip_state *state, uint64_t *digest)
294 {
295 uint64_t m;
296
297 int_sip_pad_final_block(state);
298
299 m = U8TO64_LE(state->buf);
300 int_sip_update_block(state, m);
301
302 XOR64_INT(state->v[2], 0xff);
303
304 int_sip_round(state, state->d);
305
306 *digest = state->v[0];
307 XOR64_TO(*digest, state->v[1]);
308 XOR64_TO(*digest, state->v[2]);
309 XOR64_TO(*digest, state->v[3]);
310 }
311
312 sip_hash *
313 sip_hash_new(const uint8_t key[16], int c, int d)
314 {
315 sip_hash *h = NULL;
316
317 if (!(h = (sip_hash *) malloc(sizeof(sip_hash)))) return NULL;
318 return sip_hash_init(h, key, c, d);
319 }
320
321 sip_hash *
322 sip_hash_init(sip_hash *h, const uint8_t key[16], int c, int d)
323 {
324 h->state->c = c;
325 h->state->d = d;
326 h->state->buflen = 0;
327 h->state->msglen_byte = 0;
328 h->methods = &sip_methods;
329 h->methods->init(h->state, key);
330 return h;
331 }
332
333 int
334 sip_hash_update(sip_hash *h, const uint8_t *msg, size_t len)
335 {
336 h->methods->update(h->state, msg, len);
337 return 1;
338 }
339
340 int
341 sip_hash_final(sip_hash *h, uint8_t **digest, size_t* len)
342 {
343 uint64_t digest64;
344 uint8_t *ret;
345
346 h->methods->final(h->state, &digest64);
347 if (!(ret = (uint8_t *)malloc(sizeof(uint64_t)))) return 0;
348 U64TO8_LE(ret, digest64);
349 *len = sizeof(uint64_t);
350 *digest = ret;
351
352 return 1;
353 }
354
355 int
356 sip_hash_final_integer(sip_hash *h, uint64_t *digest)
357 {
358 h->methods->final(h->state, digest);
359 return 1;
360 }
361
362 int
363 sip_hash_digest(sip_hash *h, const uint8_t *data, size_t data_len, uint8_t **digest, size_t *digest_len)
364 {
365 if (!sip_hash_update(h, data, data_len)) return 0;
366 return sip_hash_final(h, digest, digest_len);
367 }
368
369 int
370 sip_hash_digest_integer(sip_hash *h, const uint8_t *data, size_t data_len, uint64_t *digest)
371 {
372 if (!sip_hash_update(h, data, data_len)) return 0;
373 return sip_hash_final_integer(h, digest);
374 }
375
376 void
377 sip_hash_free(sip_hash *h)
378 {
379 free(h);
380 }
381
382 void
383 sip_hash_dump(sip_hash *h)
384 {
385 int_sip_dump(h->state);
386 }
387 #endif /* SIP_HASH_STREAMING */
388
389 #define SIP_2_ROUND(m, v0, v1, v2, v3) \
390 do { \
391 XOR64_TO((v3), (m)); \
392 SIP_COMPRESS(v0, v1, v2, v3); \
393 SIP_COMPRESS(v0, v1, v2, v3); \
394 XOR64_TO((v0), (m)); \
395 } while (0)
396
397 uint64_t
398 sip_hash24(const uint8_t key[16], const uint8_t *data, size_t len)
399 {
400 uint64_t k0, k1;
401 uint64_t v0, v1, v2, v3;
402 uint64_t m, last;
403 const uint8_t *end = data + len - (len % sizeof(uint64_t));
404
405 k0 = U8TO64_LE(key);
406 k1 = U8TO64_LE(key + sizeof(uint64_t));
407
408 v0 = k0; XOR64_TO(v0, sip_init_state[0]);
409 v1 = k1; XOR64_TO(v1, sip_init_state[1]);
410 v2 = k0; XOR64_TO(v2, sip_init_state[2]);
411 v3 = k1; XOR64_TO(v3, sip_init_state[3]);
412
413 #if BYTE_ORDER == LITTLE_ENDIAN && UNALIGNED_WORD_ACCESS
414 {
415 uint64_t *data64 = (uint64_t *)data;
416 while (data64 != (uint64_t *) end) {
417 m = *data64++;
418 SIP_2_ROUND(m, v0, v1, v2, v3);
419 }
420 }
59ed302 @nobu siphash.c: fix missing condition
nobu authored
421 #else
525cb66 @nobu siphash
nobu authored
422 for (; data != end; data += sizeof(uint64_t)) {
423 m = U8TO64_LE(data);
424 SIP_2_ROUND(m, v0, v1, v2, v3);
425 }
426 #endif
427
428 #ifdef HAVE_UINT64_T
429 last = (uint64_t)len << 56;
430 #define OR_BYTE(n) (last |= ((uint64_t) end[n]) << ((n) * 8))
431 #else
432 last.hi = len << 24;
433 last.lo = 0;
434 #define OR_BYTE(n) do { \
435 if (n >= 4) \
436 last.hi |= ((uint32_t) end[n]) << ((n) >= 4 ? (n) * 8 - 32 : 0); \
437 else \
438 last.lo |= ((uint32_t) end[n]) << ((n) >= 4 ? 0 : (n) * 8); \
439 } while (0)
440 #endif
441
442 switch (len % sizeof(uint64_t)) {
443 case 7:
444 OR_BYTE(6);
445 case 6:
446 OR_BYTE(5);
447 case 5:
448 OR_BYTE(4);
449 case 4:
450 #if BYTE_ORDER == LITTLE_ENDIAN && UNALIGNED_WORD_ACCESS
451 #if HAVE_UINT64_T
452 last |= (uint64_t) ((uint32_t *) end)[0];
453 #else
454 last.lo |= ((uint32_t *) end)[0];
455 #endif
456 break;
59ed302 @nobu siphash.c: fix missing condition
nobu authored
457 #else
525cb66 @nobu siphash
nobu authored
458 OR_BYTE(3);
459 #endif
460 case 3:
461 OR_BYTE(2);
462 case 2:
463 OR_BYTE(1);
464 case 1:
465 OR_BYTE(0);
466 break;
467 case 0:
468 break;
469 }
470
471 SIP_2_ROUND(last, v0, v1, v2, v3);
472
473 XOR64_INT(v2, 0xff);
474
475 SIP_COMPRESS(v0, v1, v2, v3);
476 SIP_COMPRESS(v0, v1, v2, v3);
477 SIP_COMPRESS(v0, v1, v2, v3);
478 SIP_COMPRESS(v0, v1, v2, v3);
479
480 XOR64_TO(v0, v1);
481 XOR64_TO(v0, v2);
482 XOR64_TO(v0, v3);
483 return v0;
484 }
Something went wrong with that request. Please try again.