"Fossies" - the Fresh Open Source Software Archive

Member "ponyc-0.33.2/src/libponyrt/ds/fun.c" (3 Feb 2020, 5342 Bytes) of package /linux/misc/ponyc-0.33.2.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "fun.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 0.33.1_vs_0.33.2.

    1 #include "fun.h"
    2 #include <string.h>
    3 
    4 #include <platform.h>
    5 
    6 static const unsigned char the_key[16] = {
    7   0xFE, 0x09, 0xD3, 0x22, 0x6B, 0x9C, 0x10, 0x8A,
    8   0xE1, 0x35, 0x72, 0xB5, 0xCC, 0x3F, 0x92, 0x9F
    9 };
   10 
   11 
   12 #ifdef PLATFORM_IS_ILP32
   13 
   14 #define ROTL32(x, b) (uint32_t)(((x) << (b)) | ((x) >> (32 - (b))))
   15 
   16 #define SIPROUND32 \
   17   do { \
   18     v0 += v1; v1=ROTL32(v1,5); v1 ^= v0; v0 = ROTL32(v0,16); \
   19     v2 += v3; v3=ROTL32(v3,8); v3 ^= v2; \
   20     v0 += v3; v3=ROTL32(v3,7); v3 ^= v0; \
   21     v2 += v1; v1=ROTL32(v1,13); v1 ^= v2; v2 = ROTL32(v2,16); \
   22   } while (0)
   23 
   24 
   25 static uint32_t halfsiphash24(const unsigned char* key, const unsigned char* in,
   26   size_t len)
   27 {
   28   uint32_t k0 = *(uint32_t*)(key);
   29   uint32_t k1 = *(uint32_t*)(key + 4);
   30   uint32_t b = (uint32_t)len << 24;
   31 
   32   // Reference implementations that don't agree:
   33   // https://github.com/yoursunny/hsip-bf/blob/master/examples/halfsiphash/halfsiphash-reference.c#L77-L78
   34   // https://github.com/kpdemetriou/siphash-cffi/blob/master/sources/halfsiphash.c#L77-L78
   35   //
   36   // * Those two disagree with Pony's on the inital values for v0 & v1:
   37   // both use k0/k1 as-is.
   38   //
   39   // * Those two disagree with each other on the details of finalization.
   40   //
   41   // So let's leave this as-is.  If we really must match a half siphash-2-4
   42   // reference implementation, we'll choose that impl later.
   43 
   44   uint32_t v0 = k0 ^ 0x736f6d65;
   45   uint32_t v1 = k1 ^ 0x646f7261;
   46   uint32_t v2 = k0 ^ 0x6c796765;
   47   uint32_t v3 = k1 ^ 0x74656462;
   48 
   49   const unsigned char* end = (in + len) - (len % 4);
   50 
   51   for (; in != end; in += 4)
   52   {
   53     uint32_t m = *(uint32_t*)in;
   54     v3 ^= m;
   55     SIPROUND32;
   56     SIPROUND32;
   57     v0 ^= m;
   58   }
   59 
   60   switch (len & 3)
   61   {
   62     case 3: b |= ((uint32_t)in[2]) << 16; // fallthrough
   63     case 2: b |= ((uint32_t)in[1]) << 8;  // fallthrough
   64     case 1: b |= ((uint32_t)in[0]);
   65   }
   66 
   67   v3 ^= b;
   68   SIPROUND32;
   69   SIPROUND32;
   70   v0 ^= b;
   71   v2 ^= 0xff;
   72   SIPROUND32;
   73   SIPROUND32;
   74   SIPROUND32;
   75   SIPROUND32;
   76 
   77   return v0 ^ v1 ^ v2 ^ v3;
   78 }
   79 #endif
   80 
   81 #define ROTL64(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
   82 
   83 #define SIPROUND64 \
   84   do { \
   85     v0 += v1; v1=ROTL64(v1,13); v1 ^= v0; v0=ROTL64(v0,32); \
   86     v2 += v3; v3=ROTL64(v3,16); v3 ^= v2; \
   87     v0 += v3; v3=ROTL64(v3,21); v3 ^= v0; \
   88     v2 += v1; v1=ROTL64(v1,17); v1 ^= v2; v2=ROTL64(v2,32); \
   89   } while(0)
   90 
   91 
   92 static uint64_t siphash24(const unsigned char* key, const unsigned char* in, size_t len)
   93 {
   94   uint64_t k0 = *(uint64_t*)(key);
   95   uint64_t k1 = *(uint64_t*)(key + 8);
   96   uint64_t b = (uint64_t)len << 56;
   97 
   98   uint64_t v0 = k0 ^ 0x736f6d6570736575ULL;
   99   uint64_t v1 = k1 ^ 0x646f72616e646f6dULL;
  100   uint64_t v2 = k0 ^ 0x6c7967656e657261ULL;
  101   uint64_t v3 = k1 ^ 0x7465646279746573ULL;
  102 
  103   const unsigned char* end = (in + len) - (len % 8);
  104 
  105   for(; in != end; in += 8)
  106   {
  107     uint64_t m = *(uint64_t*)in;
  108     v3 ^= m;
  109     SIPROUND64;
  110     SIPROUND64;
  111     v0 ^= m;
  112   }
  113 
  114   switch(len & 7)
  115   {
  116     case 7: b |= ((uint64_t)in[6]) << 48; // fallthrough
  117     case 6: b |= ((uint64_t)in[5]) << 40; // fallthrough
  118     case 5: b |= ((uint64_t)in[4]) << 32; // fallthrough
  119     case 4: b |= ((uint64_t)in[3]) << 24; // fallthrough
  120     case 3: b |= ((uint64_t)in[2]) << 16; // fallthrough
  121     case 2: b |= ((uint64_t)in[1]) << 8;  // fallthrough
  122     case 1: b |= ((uint64_t)in[0]);
  123   }
  124 
  125   v3 ^= b;
  126   SIPROUND64;
  127   SIPROUND64;
  128   v0 ^= b;
  129   v2 ^= 0xff;
  130   SIPROUND64;
  131   SIPROUND64;
  132   SIPROUND64;
  133   SIPROUND64;
  134 
  135   return v0 ^ v1 ^ v2 ^ v3;
  136 }
  137 
  138 PONY_API size_t ponyint_hash_block(const void* p, size_t len)
  139 {
  140 #ifdef PLATFORM_IS_ILP32
  141   return halfsiphash24(the_key, (const unsigned char*)p, len);
  142 #else
  143   return siphash24(the_key, (const unsigned char*)p, len);
  144 #endif
  145 }
  146 
  147 PONY_API uint64_t ponyint_hash_block64(const void* p, size_t len)
  148 {
  149   return siphash24(the_key, (const unsigned char*)p, len);
  150 }
  151 
  152 size_t ponyint_hash_str(const char* str)
  153 {
  154 #ifdef PLATFORM_IS_ILP32
  155   return halfsiphash24(the_key, (const unsigned char *)str, strlen(str));
  156 #else
  157   return siphash24(the_key, (const unsigned char *)str, strlen(str));
  158 #endif
  159 }
  160 
  161 size_t ponyint_hash_ptr(const void* p)
  162 {
  163 #ifdef PLATFORM_IS_ILP32
  164   return ponyint_hash_int32((uintptr_t)p);
  165 #else
  166   return ponyint_hash_int64((uintptr_t)p);
  167 #endif
  168 }
  169 
  170 uint64_t ponyint_hash_int64(uint64_t key)
  171 {
  172   key = ~key + (key << 21);
  173   key = key ^ (key >> 24);
  174   key = (key + (key << 3)) + (key << 8);
  175   key = key ^ (key >> 14);
  176   key = (key + (key << 2)) + (key << 4);
  177   key = key ^ (key >> 28);
  178   key = key + (key << 31);
  179 
  180   return key;
  181 }
  182 
  183 uint32_t ponyint_hash_int32(uint32_t key)
  184 {
  185   key = ~key + (key << 15);
  186   key = key ^ (key >> 12);
  187   key = key + (key << 2);
  188   key = key ^ (key >> 4);
  189   key = (key + (key << 3)) + (key << 11);
  190   key = key ^ (key >> 16);
  191   return key;
  192 }
  193 
  194 size_t ponyint_hash_size(size_t key)
  195 {
  196 #ifdef PLATFORM_IS_ILP32
  197   return ponyint_hash_int32(key);
  198 #else
  199   return ponyint_hash_int64(key);
  200 #endif
  201 }
  202 
  203 size_t ponyint_next_pow2(size_t i)
  204 {
  205 #ifdef PLATFORM_IS_ILP32
  206   i--;
  207 // On ARM 5 and higher, the clz instruction gives the correct result for 0.
  208 #  ifndef ARMV5
  209   if(i == 0)
  210     i = 32;
  211   else
  212 #  endif
  213     i = __pony_clzzu(i);
  214   return 1 << (i == 0 ? 0 : 32 - i);
  215 #else
  216   i--;
  217 #  ifndef ARMV5
  218   if(i == 0)
  219     i = 64;
  220   else
  221 #  endif
  222     i = __pony_clzzu(i);
  223   // Cast is needed for optimal code generation (avoids an extension).
  224   return (size_t)1 << (i == 0 ? 0 : 64 - i);
  225 #endif
  226 }