Ruby 1.9.3p327(2012-11-10revision37606)
siphash.c
Go to the documentation of this file.
00001 #include <string.h>
00002 #include <stdio.h>
00003 #include "siphash.h"
00004 #ifndef SIP_HASH_STREAMING
00005   #define SIP_HASH_STREAMING 1
00006 #endif
00007 
00008 #ifdef _WIN32
00009   #define BYTE_ORDER __LITTLE_ENDIAN
00010 #elif !defined BYTE_ORDER
00011   #include <endian.h>
00012 #endif
00013 #ifndef LITTLE_ENDIAN
00014 #define LITTLE_ENDIAN __LITTLE_ENDIAN
00015 #endif
00016 #ifndef BIG_ENDIAN
00017 #define BIG_ENDIAN __BIG_ENDIAN
00018 #endif
00019 
00020 #if BYTE_ORDER == LITTLE_ENDIAN
00021   #define lo u32[0]
00022   #define hi u32[1]
00023 #elif BYTE_ORDER == BIG_ENDIAN
00024   #define hi u32[0]
00025   #define lo u32[1]
00026 #else
00027   #error "Only strictly little or big endian supported"
00028 #endif
00029 
00030 #ifndef UNALIGNED_WORD_ACCESS
00031 # if defined(__i386) || defined(__i386__) || defined(_M_IX86) || \
00032      defined(__x86_64) || defined(__x86_64__) || defined(_M_AMD86) || \
00033      defined(__mc68020__)
00034 #   define UNALIGNED_WORD_ACCESS 1
00035 # endif
00036 #endif
00037 #ifndef UNALIGNED_WORD_ACCESS
00038 # define UNALIGNED_WORD_ACCESS 0
00039 #endif
00040 
00041 #define U8TO32_LE(p)                                                    \
00042     (((uint32_t)((p)[0])       ) | ((uint32_t)((p)[1]) <<  8) |         \
00043      ((uint32_t)((p)[2]) <<  16) | ((uint32_t)((p)[3]) << 24))          \
00044 
00045 #define U32TO8_LE(p, v)                 \
00046 do {                                    \
00047     (p)[0] = (uint8_t)((v)      );      \
00048     (p)[1] = (uint8_t)((v) >>  8);      \
00049     (p)[2] = (uint8_t)((v) >> 16);      \
00050     (p)[3] = (uint8_t)((v) >> 24);      \
00051 } while (0)
00052 
00053 #ifdef HAVE_UINT64_T
00054 #define U8TO64_LE(p)                                                    \
00055     ((uint64_t)U8TO32_LE(p) | ((uint64_t)U8TO32_LE((p) + 4)) << 32 )
00056 
00057 #define U64TO8_LE(p, v) \
00058 do {                                            \
00059     U32TO8_LE((p),     (uint32_t)((v)      ));  \
00060     U32TO8_LE((p) + 4, (uint32_t)((v) >> 32));  \
00061 } while (0)
00062 
00063 #define ROTL64(v, s)                    \
00064     ((v) << (s)) | ((v) >> (64 - (s)))
00065 
00066 #define ROTL64_TO(v, s) ((v) = ROTL64((v), (s)))
00067 
00068 #define ADD64_TO(v, s) ((v) += (s))
00069 #define XOR64_TO(v, s) ((v) ^= (s))
00070 #define XOR64_INT(v, x) ((v) ^= (x))
00071 #else
00072 #define U8TO64_LE(p) u8to64_le(p)
00073 static inline uint64_t
00074 u8to64_le(const uint8_t *p)
00075 {
00076     uint64_t ret;
00077     ret.lo = U8TO32_LE(p);
00078     ret.hi = U8TO32_LE(p + 4);
00079     return ret;
00080 }
00081 
00082 #define U64TO8_LE(p, v) u64to8_le(p, v)
00083 static inline void
00084 u64to8_le(uint8_t *p, uint64_t v)
00085 {
00086     U32TO8_LE(p,     v.lo);
00087     U32TO8_LE(p + 4, v.hi);
00088 }
00089 
00090 #define ROTL64_TO(v, s) ((s) > 32 ? rotl64_swap(rotl64_to(&(v), (s) - 32)) : \
00091                          (s) == 32 ? rotl64_swap(&(v)) : rotl64_to(&(v), (s)))
00092 static inline uint64_t *
00093 rotl64_to(uint64_t *v, unsigned int s)
00094 {
00095     uint32_t uhi = (v->hi << s) | (v->lo >> (32 - s));
00096     uint32_t ulo = (v->lo << s) | (v->hi >> (32 - s));
00097     v->hi = uhi;
00098     v->lo = ulo;
00099     return v;
00100 }
00101 
00102 static inline uint64_t *
00103 rotl64_swap(uint64_t *v)
00104 {
00105     uint32_t t = v->lo;
00106     v->lo = v->hi;
00107     v->hi = t;
00108     return v;
00109 }
00110 
00111 #define ADD64_TO(v, s) add64_to(&(v), (s))
00112 static inline uint64_t *
00113 add64_to(uint64_t *v, const uint64_t s)
00114 {
00115     v->lo += s.lo;
00116     v->hi += s.hi;
00117     if (v->lo < s.lo) v->hi++;
00118     return v;
00119 }
00120 
00121 #define XOR64_TO(v, s) xor64_to(&(v), (s))
00122 static inline uint64_t *
00123 xor64_to(uint64_t *v, const uint64_t s)
00124 {
00125     v->lo ^= s.lo;
00126     v->hi ^= s.hi;
00127     return v;
00128 }
00129 
00130 #define XOR64_INT(v, x) ((v).lo ^= (x))
00131 #endif
00132 
00133 static const union {
00134     char bin[32];
00135     uint64_t u64[4];
00136 } sip_init_state_bin = {"uespemos""modnarod""arenegyl""setybdet"};
00137 #define sip_init_state sip_init_state_bin.u64
00138 
00139 #if SIP_HASH_STREAMING
00140 struct sip_interface_st {
00141     void (*init)(sip_state *s, const uint8_t *key);
00142     void (*update)(sip_state *s, const uint8_t *data, size_t len);
00143     void (*final)(sip_state *s, uint64_t *digest);
00144 };
00145 
00146 static void int_sip_init(sip_state *state, const uint8_t *key);
00147 static void int_sip_update(sip_state *state, const uint8_t *data, size_t len);
00148 static void int_sip_final(sip_state *state, uint64_t *digest);
00149 
00150 static const sip_interface sip_methods = {
00151     int_sip_init,
00152     int_sip_update,
00153     int_sip_final
00154 };
00155 #endif /* SIP_HASH_STREAMING */
00156 
00157 #define SIP_COMPRESS(v0, v1, v2, v3)    \
00158 do {                                    \
00159     ADD64_TO((v0), (v1));               \
00160     ADD64_TO((v2), (v3));               \
00161     ROTL64_TO((v1), 13);                \
00162     ROTL64_TO((v3), 16);                \
00163     XOR64_TO((v1), (v0));               \
00164     XOR64_TO((v3), (v2));               \
00165     ROTL64_TO((v0), 32);                \
00166     ADD64_TO((v2), (v1));               \
00167     ADD64_TO((v0), (v3));               \
00168     ROTL64_TO((v1), 17);                \
00169     ROTL64_TO((v3), 21);                \
00170     XOR64_TO((v1), (v2));               \
00171     XOR64_TO((v3), (v0));               \
00172     ROTL64_TO((v2), 32);                \
00173 } while(0)
00174 
00175 #if SIP_HASH_STREAMING
00176 static void
00177 int_sip_dump(sip_state *state)
00178 {
00179     int v;
00180 
00181     for (v = 0; v < 4; v++) {
00182 #if HAVE_UINT64_T
00183         printf("v%d: %" PRIx64 "\n", v, state->v[v]);
00184 #else
00185         printf("v%d: %" PRIx32 "%.8" PRIx32 "\n", v, state->v[v].hi, state->v[v].lo);
00186 #endif
00187     }
00188 }
00189 
00190 static void
00191 int_sip_init(sip_state *state, const uint8_t key[16])
00192 {
00193     uint64_t k0, k1;
00194 
00195     k0 = U8TO64_LE(key);
00196     k1 = U8TO64_LE(key + sizeof(uint64_t));
00197 
00198     state->v[0] = k0; XOR64_TO(state->v[0], sip_init_state[0]);
00199     state->v[1] = k1; XOR64_TO(state->v[1], sip_init_state[1]);
00200     state->v[2] = k0; XOR64_TO(state->v[2], sip_init_state[2]);
00201     state->v[3] = k1; XOR64_TO(state->v[3], sip_init_state[3]);
00202 }
00203 
00204 static inline void
00205 int_sip_round(sip_state *state, int n)
00206 {
00207     int i;
00208 
00209     for (i = 0; i < n; i++) {
00210         SIP_COMPRESS(state->v[0], state->v[1], state->v[2], state->v[3]);
00211     }
00212 }
00213 
00214 static inline void
00215 int_sip_update_block(sip_state *state, uint64_t m)
00216 {
00217     XOR64_TO(state->v[3], m);
00218     int_sip_round(state, state->c);
00219     XOR64_TO(state->v[0], m);
00220 }
00221 
00222 static inline void
00223 int_sip_pre_update(sip_state *state, const uint8_t **pdata, size_t *plen)
00224 {
00225     int to_read;
00226     uint64_t m;
00227 
00228     if (!state->buflen) return;
00229 
00230     to_read = sizeof(uint64_t) - state->buflen;
00231     memcpy(state->buf + state->buflen, *pdata, to_read);
00232     m = U8TO64_LE(state->buf);
00233     int_sip_update_block(state, m);
00234     *pdata += to_read;
00235     *plen -= to_read;
00236     state->buflen = 0;
00237 }
00238 
00239 static inline void
00240 int_sip_post_update(sip_state *state, const uint8_t *data, size_t len)
00241 {
00242     uint8_t r = len % sizeof(uint64_t);
00243     if (r) {
00244         memcpy(state->buf, data + len - r, r);
00245         state->buflen = r;
00246     }
00247 }
00248 
00249 static void
00250 int_sip_update(sip_state *state, const uint8_t *data, size_t len)
00251 {
00252     uint64_t *end;
00253     uint64_t *data64;
00254 
00255     state->msglen_byte = state->msglen_byte + (len % 256);
00256     data64 = (uint64_t *) data;
00257 
00258     int_sip_pre_update(state, &data, &len);
00259 
00260     end = data64 + (len / sizeof(uint64_t));
00261 
00262 #if BYTE_ORDER == LITTLE_ENDIAN
00263     while (data64 != end) {
00264         int_sip_update_block(state, *data64++);
00265     }
00266 #elif BYTE_ORDER == BIG_ENDIAN
00267     {
00268         uint64_t m;
00269         uint8_t *data8 = data;
00270         for (; data8 != (uint8_t *) end; data8 += sizeof(uint64_t)) {
00271             m = U8TO64_LE(data8);
00272             int_sip_update_block(state, m);
00273         }
00274     }
00275 #endif
00276 
00277     int_sip_post_update(state, data, len);
00278 }
00279 
00280 static inline void
00281 int_sip_pad_final_block(sip_state *state)
00282 {
00283     int i;
00284     /* pad with 0's and finalize with msg_len mod 256 */
00285     for (i = state->buflen; i < sizeof(uint64_t); i++) {
00286         state->buf[i] = 0x00;
00287     }
00288     state->buf[sizeof(uint64_t) - 1] = state->msglen_byte;
00289 }
00290 
00291 static void
00292 int_sip_final(sip_state *state, uint64_t *digest)
00293 {
00294     uint64_t m;
00295 
00296     int_sip_pad_final_block(state);
00297 
00298     m = U8TO64_LE(state->buf);
00299     int_sip_update_block(state, m);
00300 
00301     XOR64_INT(state->v[2], 0xff);
00302 
00303     int_sip_round(state, state->d);
00304 
00305     *digest = state->v[0];
00306     XOR64_TO(*digest, state->v[1]);
00307     XOR64_TO(*digest, state->v[2]);
00308     XOR64_TO(*digest, state->v[3]);
00309 }
00310 
00311 sip_hash *
00312 sip_hash_new(const uint8_t key[16], int c, int d)
00313 {
00314     sip_hash *h = NULL;
00315 
00316     if (!(h = (sip_hash *) malloc(sizeof(sip_hash)))) return NULL;
00317     return sip_hash_init(h, key, c, d);
00318 }
00319 
00320 sip_hash *
00321 sip_hash_init(sip_hash *h, const uint8_t key[16], int c, int d)
00322 {
00323     h->state->c = c;
00324     h->state->d = d;
00325     h->state->buflen = 0;
00326     h->state->msglen_byte = 0;
00327     h->methods = &sip_methods;
00328     h->methods->init(h->state, key);
00329     return h;
00330 }
00331 
00332 int
00333 sip_hash_update(sip_hash *h, const uint8_t *msg, size_t len)
00334 {
00335     h->methods->update(h->state, msg, len);
00336     return 1;
00337 }
00338 
00339 int
00340 sip_hash_final(sip_hash *h, uint8_t **digest, size_t* len)
00341 {
00342     uint64_t digest64;
00343     uint8_t *ret;
00344 
00345     h->methods->final(h->state, &digest64);
00346     if (!(ret = (uint8_t *)malloc(sizeof(uint64_t)))) return 0;
00347     U64TO8_LE(ret, digest64);
00348     *len = sizeof(uint64_t);
00349     *digest = ret;
00350 
00351     return 1;
00352 }
00353 
00354 int
00355 sip_hash_final_integer(sip_hash *h, uint64_t *digest)
00356 {
00357     h->methods->final(h->state, digest);
00358     return 1;
00359 }
00360 
00361 int
00362 sip_hash_digest(sip_hash *h, const uint8_t *data, size_t data_len, uint8_t **digest, size_t *digest_len)
00363 {
00364     if (!sip_hash_update(h, data, data_len)) return 0;
00365     return sip_hash_final(h, digest, digest_len);
00366 }
00367 
00368 int
00369 sip_hash_digest_integer(sip_hash *h, const uint8_t *data, size_t data_len, uint64_t *digest)
00370 {
00371     if (!sip_hash_update(h, data, data_len)) return 0;
00372     return sip_hash_final_integer(h, digest);
00373 }
00374 
00375 void
00376 sip_hash_free(sip_hash *h)
00377 {
00378     free(h);
00379 }
00380 
00381 void
00382 sip_hash_dump(sip_hash *h)
00383 {
00384     int_sip_dump(h->state);
00385 }
00386 #endif /* SIP_HASH_STREAMING */
00387 
00388 #define SIP_2_ROUND(m, v0, v1, v2, v3)  \
00389 do {                                    \
00390     XOR64_TO((v3), (m));                \
00391     SIP_COMPRESS(v0, v1, v2, v3);       \
00392     SIP_COMPRESS(v0, v1, v2, v3);       \
00393     XOR64_TO((v0), (m));                \
00394 } while (0)
00395 
00396 uint64_t
00397 sip_hash24(const uint8_t key[16], const uint8_t *data, size_t len)
00398 {
00399     uint64_t k0, k1;
00400     uint64_t v0, v1, v2, v3;
00401     uint64_t m, last;
00402     const uint8_t *end = data + len - (len % sizeof(uint64_t));
00403 
00404     k0 = U8TO64_LE(key);
00405     k1 = U8TO64_LE(key + sizeof(uint64_t));
00406 
00407     v0 = k0; XOR64_TO(v0, sip_init_state[0]);
00408     v1 = k1; XOR64_TO(v1, sip_init_state[1]);
00409     v2 = k0; XOR64_TO(v2, sip_init_state[2]);
00410     v3 = k1; XOR64_TO(v3, sip_init_state[3]);
00411 
00412 #if BYTE_ORDER == LITTLE_ENDIAN && UNALIGNED_WORD_ACCESS
00413     {
00414         uint64_t *data64 = (uint64_t *)data;
00415         while (data64 != (uint64_t *) end) {
00416             m = *data64++;
00417             SIP_2_ROUND(m, v0, v1, v2, v3);
00418         }
00419     }
00420 #elif BYTE_ORDER == BIG_ENDIAN
00421     for (; data != end; data += sizeof(uint64_t)) {
00422         m = U8TO64_LE(data);
00423         SIP_2_ROUND(m, v0, v1, v2, v3);
00424     }
00425 #endif
00426 
00427 #ifdef HAVE_UINT64_T
00428     last = (uint64_t)len << 56;
00429 #define OR_BYTE(n) (last |= ((uint64_t) end[n]) << ((n) * 8))
00430 #else
00431     last.hi = len << 24;
00432     last.lo = 0;
00433 #define OR_BYTE(n) do { \
00434         if (n >= 4) \
00435             last.hi |= ((uint32_t) end[n]) << ((n) >= 4 ? (n) * 8 - 32 : 0); \
00436         else \
00437             last.lo |= ((uint32_t) end[n]) << ((n) >= 4 ? 0 : (n) * 8); \
00438     } while (0)
00439 #endif
00440 
00441     switch (len % sizeof(uint64_t)) {
00442         case 7:
00443             OR_BYTE(6);
00444         case 6:
00445             OR_BYTE(5);
00446         case 5:
00447             OR_BYTE(4);
00448         case 4:
00449 #if BYTE_ORDER == LITTLE_ENDIAN && UNALIGNED_WORD_ACCESS
00450   #if HAVE_UINT64_T
00451             last |= (uint64_t) ((uint32_t *) end)[0];
00452   #else
00453             last.lo |= ((uint32_t *) end)[0];
00454   #endif
00455             break;
00456 #elif BYTE_ORDER == BIG_ENDIAN
00457             OR_BYTE(3);
00458 #endif
00459         case 3:
00460             OR_BYTE(2);
00461         case 2:
00462             OR_BYTE(1);
00463         case 1:
00464             OR_BYTE(0);
00465             break;
00466         case 0:
00467             break;
00468     }
00469 
00470     SIP_2_ROUND(last, v0, v1, v2, v3);
00471 
00472     XOR64_INT(v2, 0xff);
00473 
00474     SIP_COMPRESS(v0, v1, v2, v3);
00475     SIP_COMPRESS(v0, v1, v2, v3);
00476     SIP_COMPRESS(v0, v1, v2, v3);
00477     SIP_COMPRESS(v0, v1, v2, v3);
00478 
00479     XOR64_TO(v0, v1);
00480     XOR64_TO(v0, v2);
00481     XOR64_TO(v0, v3);
00482     return v0;
00483 }
00484