source/core/hash.cpp

   1 #include <stdexcept>
   2 #include "hash.h"
   3
   4 using namespace std;
   5
   6 namespace Msp {
   7
   8 /*
   9 http://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function
  10 http://www.isthe.com/chongo/tech/comp/fnv/index.html
  11 */
  12
  13 UInt32 hash32(const void *data, unsigned size, unsigned bits)
  14 {
  15         if(bits==0 || bits>32)
  16                 throw invalid_argument("hash32");
  17
  18         static const unsigned prime = 16777619;
  19         static const unsigned offset = 2166136261U;
  20
  21         unsigned result = offset;
  22         for(unsigned i=0; i<size; ++i)
  23                 result = (result^*(reinterpret_cast<const unsigned char *>(data)+i))*prime;
  24
  25         if(bits<32)
  26                 result = (result>>bits ^ result) & ((1<<bits)-1);
  27
  28         return result;
  29 }
  30
  31 UInt64 hash64(const void *data, unsigned size, unsigned bits)
  32 {
  33         if(bits==0 || bits>64)
  34                 throw invalid_argument("hash64");
  35
  36         static const UInt64 prime = 1099511628211ULL;
  37         static const UInt64 offset = 14695981039346656037ULL;
  38
  39         UInt64 result = offset;
  40         for(unsigned i=0; i<size; ++i)
  41                 result = (result^*(reinterpret_cast<const unsigned char *>(data)+i))*prime;
  42
  43         if(bits<64)
  44                 result = (result>>bits ^ result) & ((1ULL<<bits)-1);
  45
  46         return result;
  47 }
  48
  49 } // namespace Msp