src/ext/csiphash.c

   1 /* <MIT License>
   2  Copyright (c) 2013-2014  Marek Majkowski <marek@popcount.org>
   3
   4  Permission is hereby granted, free of charge, to any person obtaining a copy
   5  of this software and associated documentation files (the "Software"), to deal
   6  in the Software without restriction, including without limitation the rights
   7  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  copies of the Software, and to permit persons to whom the Software is
   9  furnished to do so, subject to the following conditions:
  10
  11  The above copyright notice and this permission notice shall be included in
  12  all copies or substantial portions of the Software.
  13
  14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20  THE SOFTWARE.
  21  </MIT License>
  22
  23  Original location:
  24     https://github.com/majek/csiphash/
  25
  26  Solution inspired by code from:
  27     Samuel Neves (supercop/crypto_auth/siphash24/little)
  28     djb (supercop/crypto_auth/siphash24/little2)
  29     Jean-Philippe Aumasson (https://131002.net/siphash/siphash24.c)
  30 */
  31
  32 #include "torint.h"
  33 #include "siphash.h"
  34 /* for tor_assert */
  35 #include "util.h"
  36 /* for memcpy */
  37 #include <string.h>
  38
  39 #if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && \
  40         __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
  41 #  define _le64toh(x) ((uint64_t)(x))
  42 #elif defined(_WIN32)
  43 /* Windows is always little endian, unless you're on xbox360
  44    http://msdn.microsoft.com/en-us/library/b0084kay(v=vs.80).aspx */
  45 #  define _le64toh(x) ((uint64_t)(x))
  46 #elif defined(__APPLE__)
  47 #  include <libkern/OSByteOrder.h>
  48 #  define _le64toh(x) OSSwapLittleToHostInt64(x)
  49 #elif defined(sun) || defined(__sun)
  50 #  include <sys/byteorder.h>
  51 #  define _le64toh(x) LE_64(x)
  52
  53 #else
  54
  55 /* See: http://sourceforge.net/p/predef/wiki/Endianness/ */
  56 #  if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__)
  57 #    include <sys/endian.h>
  58 #  else
  59 #    include <endian.h>
  60 #  endif
  61 #  if defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
  62         __BYTE_ORDER == __LITTLE_ENDIAN
  63 #    define _le64toh(x) ((uint64_t)(x))
  64 #  else
  65 #    if defined(__OpenBSD__)
  66 #      define _le64toh(x) letoh64(x)
  67 #    else
  68 #      define _le64toh(x) le64toh(x)
  69 #    endif
  70 #  endif
  71
  72 #endif
  73
  74 #define ROTATE(x, b) (uint64_t)( ((x) << (b)) | ( (x) >> (64 - (b))) )
  75
  76 #define HALF_ROUND(a,b,c,d,s,t)                 \
  77         a += b; c += d;                         \
  78         b = ROTATE(b, s) ^ a;                   \
  79         d = ROTATE(d, t) ^ c;                   \
  80         a = ROTATE(a, 32);
  81
  82 #define DOUBLE_ROUND(v0,v1,v2,v3)               \
  83         HALF_ROUND(v0,v1,v2,v3,13,16);          \
  84         HALF_ROUND(v2,v1,v0,v3,17,21);          \
  85         HALF_ROUND(v0,v1,v2,v3,13,16);          \
  86         HALF_ROUND(v2,v1,v0,v3,17,21);
  87
  88 #if 0
  89 /* This does not seem to save very much runtime in the fast case, and it's
  90  * potentially a big loss in the slow case where we're misaligned and we cross
  91  * a cache line. */
  92 #if (defined(__i386) || defined(__i386__) || defined(_M_IX86) ||        \
  93      defined(__x86_64) || defined(__x86_64__) ||                        \
  94      defined(_M_AMD64) || defined(_M_X64) || defined(__INTEL__))
  95 #   define UNALIGNED_OK 1
  96 #endif
  97 #endif
  98
  99 uint64_t siphash24(const void *src, unsigned long src_sz, const struct sipkey *key) {
 100         const uint8_t *m = src;
 101         uint64_t k0 = key->k0;
 102         uint64_t k1 = key->k1;
 103         uint64_t last7 = (uint64_t)(src_sz & 0xff) << 56;
 104         size_t i, blocks;
 105
 106         uint64_t v0 = k0 ^ 0x736f6d6570736575ULL;
 107         uint64_t v1 = k1 ^ 0x646f72616e646f6dULL;
 108         uint64_t v2 = k0 ^ 0x6c7967656e657261ULL;
 109         uint64_t v3 = k1 ^ 0x7465646279746573ULL;
 110
 111         for (i = 0, blocks = (src_sz & ~7); i < blocks; i+= 8) {
 112 #ifdef UNALIGNED_OK
 113                 uint64_t mi = _le64toh(*(m + i));
 114 #else
 115                 uint64_t mi;
 116                 memcpy(&mi, m + i, 8);
 117                 mi = _le64toh(mi);
 118 #endif
 119                 v3 ^= mi;
 120                 DOUBLE_ROUND(v0,v1,v2,v3);
 121                 v0 ^= mi;
 122         }
 123
 124         switch (src_sz - blocks) {
 125                 case 7: last7 |= (uint64_t)m[i + 6] << 48;
 126                 case 6: last7 |= (uint64_t)m[i + 5] << 40;
 127                 case 5: last7 |= (uint64_t)m[i + 4] << 32;
 128                 case 4: last7 |= (uint64_t)m[i + 3] << 24;
 129                 case 3: last7 |= (uint64_t)m[i + 2] << 16;
 130                 case 2: last7 |= (uint64_t)m[i + 1] <<  8;
 131                 case 1: last7 |= (uint64_t)m[i + 0]      ;
 132                 case 0:
 133                 default:;
 134         }
 135         v3 ^= last7;
 136         DOUBLE_ROUND(v0,v1,v2,v3);
 137         v0 ^= last7;
 138         v2 ^= 0xff;
 139         DOUBLE_ROUND(v0,v1,v2,v3);
 140         DOUBLE_ROUND(v0,v1,v2,v3);
 141         return v0 ^ v1 ^ v2 ^ v3;
 142 }
 143
 144
 145 static int the_siphash_key_is_set = 0;
 146 static struct sipkey the_siphash_key;
 147
 148 uint64_t siphash24g(const void *src, unsigned long src_sz) {
 149         tor_assert(the_siphash_key_is_set);
 150         return siphash24(src, src_sz, &the_siphash_key);
 151 }
 152
 153 void siphash_set_global_key(const struct sipkey *key)
 154 {
 155         tor_assert(! the_siphash_key_is_set);
 156         the_siphash_key.k0 = key->k0;
 157         the_siphash_key.k1 = key->k1;
 158         the_siphash_key_is_set = 1;
 159 }