Home | History | Annotate | Download | only in src 
      1 #include "Hashes.h"
      2 
      3 #include "Random.h"
      4 
      5 
      6 #include <stdlib.h>
      7 //#include <stdint.h>
      8 #include <assert.h>
      9 //#include <emmintrin.h>
     10 //#include <xmmintrin.h>
     11 
     12 //----------------------------------------------------------------------------
     13 // fake / bad hashes
     14 
     15 void BadHash ( const void * key, int len, uint32_t seed, void * out )
     16 {
     17   uint32_t h = seed;
     18 
     19   const uint8_t * data = (const uint8_t*)key;
     20 
     21   for(int i = 0; i < len; i++)
     22   {
     23     h ^= h >> 3;
     24     h ^= h << 5;
     25     h ^= data[i];
     26   }
     27 
     28   *(uint32_t*)out = h;
     29 }
     30 
     31 void sumhash ( const void * key, int len, uint32_t seed, void * out )
     32 {
     33   uint32_t h = seed;
     34 
     35   const uint8_t * data = (const uint8_t*)key;
     36 
     37   for(int i = 0; i < len; i++)
     38   {
     39     h += data[i];
     40   }
     41 
     42   *(uint32_t*)out = h;
     43 }
     44 
     45 void sumhash32 ( const void * key, int len, uint32_t seed, void * out )
     46 {
     47   uint32_t h = seed;
     48 
     49   const uint32_t * data = (const uint32_t*)key;
     50 
     51   for(int i = 0; i < len/4; i++)
     52   {
     53     h += data[i];
     54   }
     55 
     56   *(uint32_t*)out = h;
     57 }
     58 
     59 void DoNothingHash ( const void *, int, uint32_t, void * )
     60 {
     61 }
     62 
     63 //-----------------------------------------------------------------------------
     64 // One-byte-at-a-time hash based on Murmur's mix
     65 
     66 uint32_t MurmurOAAT ( const void * key, int len, uint32_t seed )
     67 {
     68   const uint8_t * data = (const uint8_t*)key;
     69 
     70   uint32_t h = seed;
     71 
     72   for(int i = 0; i < len; i++)
     73   {
     74     h ^= data[i];
     75     h *= 0x5bd1e995;
     76     h ^= h >> 15;
     77   }
     78 
     79   return h;
     80 }
     81 
     82 void MurmurOAAT_test ( const void * key, int len, uint32_t seed, void * out )
     83 {
     84 	*(uint32_t*)out = MurmurOAAT(key,len,seed);
     85 }
     86 
     87 //----------------------------------------------------------------------------
     88 
     89 void FNV ( const void * key, int len, uint32_t seed, void * out )
     90 {
     91   unsigned int h = seed;
     92 
     93   const uint8_t * data = (const uint8_t*)key;
     94 
     95   h ^= BIG_CONSTANT(2166136261);
     96 
     97   for(int i = 0; i < len; i++)
     98   {
     99     h ^= data[i];
    100     h *= 16777619;
    101   }
    102 
    103   *(uint32_t*)out = h;
    104 }
    105 
    106 //-----------------------------------------------------------------------------
    107 
    108 uint32_t x17 ( const void * key, int len, uint32_t h )
    109 {
    110   const uint8_t * data = (const uint8_t*)key;
    111 
    112   for(int i = 0; i < len; ++i)
    113   {
    114         h = 17 * h + (data[i] - ' ');
    115     }
    116 
    117     return h ^ (h >> 16);
    118 }
    119 
    120 //-----------------------------------------------------------------------------
    121 
    122 void Bernstein ( const void * key, int len, uint32_t seed, void * out )
    123 {
    124   const uint8_t * data = (const uint8_t*)key;
    125 
    126   for(int i = 0; i < len; ++i)
    127   {
    128         seed = 33 * seed + data[i];
    129     }
    130 
    131   *(uint32_t*)out = seed;
    132 }
    133 
    134 //-----------------------------------------------------------------------------
    135 // Crap8 hash from http://www.team5150.com/~andrew/noncryptohashzoo/Crap8.html
    136 
    137 uint32_t Crap8( const uint8_t *key, uint32_t len, uint32_t seed ) {
    138   #define c8fold( a, b, y, z ) { p = (uint32_t)(a) * (uint64_t)(b); y ^= (uint32_t)p; z ^= (uint32_t)(p >> 32); }
    139   #define c8mix( in ) { h *= m; c8fold( in, m, k, h ); }
    140 
    141   const uint32_t m = 0x83d2e73b, n = 0x97e1cc59, *key4 = (const uint32_t *)key;
    142   uint32_t h = len + seed, k = n + len;
    143   uint64_t p;
    144 
    145   while ( len >= 8 ) { c8mix(key4[0]) c8mix(key4[1]) key4 += 2; len -= 8; }
    146   if ( len >= 4 ) { c8mix(key4[0]) key4 += 1; len -= 4; }
    147   if ( len ) { c8mix( key4[0] & ( ( 1 << ( len * 8 ) ) - 1 ) ) }
    148   c8fold( h ^ k, n, k, k )
    149   return k;
    150 }
    151 
    152 void Crap8_test ( const void * key, int len, uint32_t seed, void * out )
    153 {
    154   *(uint32_t*)out = Crap8((const uint8_t*)key,len,seed);
    155 }
    156