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