c_cpp/etc/mVicuna/src/jaz/hash.hpp

   1 /***
   2  *  $Id$
   3  **
   4  *  File: hash.hpp
   5  *  Created: Apr 02, 2011
   6  *
   7  *  Author: Jaroslaw Zola <jaroslaw.zola@gmail.com>
   8  *  Copyright (c) 2011-2012 Jaroslaw Zola
   9  *  Distributed under the Boost Software License.
  10  *  See accompanying LICENSE.
  11  *
  12  *  This file is part of jaz.
  13  */
  14
  15 #ifndef HASH_HPP
  16 #define HASH_HPP
  17
  18 #include <inttypes.h>
  19 #include <string.h>
  20
  21
  22 /** File: hash.hpp
  23  */
  24 namespace jaz {
  25
  26   /** Class: djb32
  27    *  Functor implementing 32bit hash DJB2 with XOR. It is hard to say if this is
  28    *  a good or a bad function! Some claim it is good, but some tests show
  29    *  it is not: http://www.team5150.com/~andrew/noncryptohashzoo/DJB.html.
  30    */
  31   class djb32 {
  32   public:
  33       /** Constructor: djb32
  34        *
  35        *  Parameter:
  36        *  seed - Default seed from http://en.wikipedia.org/wiki/2147483647.
  37        */
  38       explicit djb32(uint32_t seed = 2147483647) : seed_(seed) { }
  39
  40       /** Function: operator()
  41        *  Performs hashing.
  42        */
  43       uint32_t operator()(const char* s, unsigned int l) const {
  44           const unsigned char* S = (const unsigned char*)s;
  45           uint32_t len = l;
  46           uint32_t hash = 5381 + seed_ + len;
  47
  48           for (; len & ~1; len -= 2, S += 2) {
  49               hash = ((((hash << 5) + hash) ^ S[0]) * 33) ^ S[1];
  50           }
  51
  52           if (len & 1) hash = ((hash << 5) + hash) ^ S[0];
  53
  54           return hash ^ (hash >> 16);
  55       } // operator()
  56
  57       /** Function: operator()
  58        *  Performs hashing.
  59        */
  60       uint32_t operator()(const std::string& s) const {
  61           return this->operator()(s.c_str(), s.size());
  62       } // operator()
  63
  64   private:
  65       uint32_t seed_;
  66
  67   }; // class djb32
  68
  69
  70   /** Class: murmur264
  71    *  Functor implementing 64bit hash Murmur2.
  72    */
  73   class murmur264 {
  74   public:
  75       /** Constructor: murmur264
  76        */
  77       explicit murmur264(uint64_t seed = 2147483647) : seed_(seed) { }
  78
  79       /** Function: operator()
  80        *  Performs hashing.
  81        */
  82       uint64_t operator()(const char* s, unsigned int l) const {
  83           const unsigned char* S = (const unsigned char*)s;
  84           uint64_t len = l;
  85
  86           const uint64_t m = 0xc6a4a7935bd1e995LL;
  87           const uint8_t r = 47;
  88
  89           uint64_t h = len + seed_;
  90
  91           for (; len >= 8; len -= 8, S += 8) {
  92               uint64_t k = (*(uint64_t*)S) * m;
  93               k ^= k >> r;
  94               k *= m;
  95               h = (h * m) ^ k;
  96           } // for
  97
  98           switch (len & 7) {
  99             case 7: h ^= (uint64_t)S[6] << 48;
 100             case 6: h ^= (uint64_t)S[5] << 40;
 101             case 5: h ^= (uint64_t)S[4] << 32;
 102             case 4: h ^= (uint64_t)S[3] << 24;
 103             case 3: h ^= (uint64_t)S[2] << 16;
 104             case 2: h ^= (uint64_t)S[1] << 8;
 105             case 1: h ^= (uint64_t)S[0];
 106                 h *= m;
 107           } // switch
 108
 109           h ^= h >> r;
 110           h *= m;
 111           h ^= h >> r;
 112
 113           return h;
 114       } // operator()
 115
 116       /** Function: operator()
 117        *  Performs hashing.
 118        */
 119       uint64_t operator()(const std::string& s) const {
 120           return this->operator()(s.c_str(), s.size());
 121       } // operator()
 122
 123   private:
 124       uint64_t seed_;
 125
 126   }; // class murmur264
 127
 128
 129   /** Class: rabin64
 130    *  Functor implementing Rabin fingerprint. This code is based (to some extent)
 131    *  on Java implementations available in the Internet (with junk removed
 132    *  and several bug-fixes).
 133    */
 134   class rabin64 {
 135   public:
 136       // p_ represents: x^64 + x^4 + x^3 + x + 1 (which I hope is irreducible in Z2)
 137
 138       /** Constructor: rabin64
 139        */
 140       rabin64() : p_(0x000000000000001BLL), p_deg_(64) { prv_init__(); }
 141
 142       /** Function: operator()
 143        *  Performs hashing.
 144        */
 145       uint64_t operator()(const char* s, unsigned int l) const {
 146           const unsigned char* S = (const unsigned char*)s;
 147
 148           uint64_t h = 0;
 149           unsigned int pos = l % 8;
 150
 151           unsigned int i = 0;
 152           if (pos != 0) for (; i < pos; ++i) h = (h << 8) ^ S[i];
 153
 154           while (i < l) {
 155               h = tab32_[h & 0xFF] ^
 156                   tab40_[(h >> 8) & 0xFF] ^
 157                   tab48_[(h >> 16) & 0xFF] ^
 158                   tab56_[(h >> 24) & 0xFF] ^
 159                   tab64_[(h >> 32) & 0xFF] ^
 160                   tab72_[(h >> 40) & 0xFF] ^
 161                   tab80_[(h >> 48) & 0xFF] ^
 162                   tab88_[(h >> 56) & 0xFF] ^
 163                   ((uint64_t)S[i] << 56) ^
 164                   ((uint64_t)S[i + 1] << 48) ^
 165                   ((uint64_t)S[i + 2] << 40) ^
 166                   ((uint64_t)S[i + 3] << 32) ^
 167                   ((uint64_t)S[i + 4] << 24) ^
 168                   ((uint64_t)S[i + 5] << 16) ^
 169                   ((uint64_t)S[i + 6] << 8) ^
 170                   (uint64_t)S[i + 7];
 171               i += 8;
 172           } // while
 173
 174           return h;
 175       } // operator
 176
 177       /** Function: operator()
 178        *  Performs hashing.
 179        */
 180       uint64_t operator()(const std::string& s) const {
 181           return this->operator()(s.c_str(), s.size());
 182       } // operator()
 183
 184   private:
 185       uint64_t p_;
 186       unsigned int p_deg_;
 187
 188       void prv_init__() {
 189           uint64_t xp = (uint64_t)1 << (p_deg_ - 1);
 190           uint64_t* mods = new uint64_t[p_deg_];
 191
 192           mods[0] = p_;
 193
 194           for (unsigned int i = 1; i < p_deg_; i++) {
 195               mods[i] = mods[i - 1] << 1;
 196               if (mods[i - 1] & xp) mods[i] ^= p_;
 197           }
 198
 199           memset(tab32_, 0, 256);
 200           memset(tab40_, 0, 256);
 201           memset(tab48_, 0, 256);
 202           memset(tab56_, 0, 256);
 203           memset(tab64_, 0, 256);
 204           memset(tab72_, 0, 256);
 205           memset(tab80_, 0, 256);
 206           memset(tab88_, 0, 256);
 207
 208           for (unsigned int i = 0; i < 256; ++i) {
 209               unsigned int c = i;
 210               for (unsigned int j = 0; (j < 8) && (c > 0); ++j) {
 211                   if (c & 1) {
 212                       tab32_[i] ^= mods[j];
 213                       tab40_[i] ^= mods[j + 8];
 214                       tab48_[i] ^= mods[j + 16];
 215                       tab56_[i] ^= mods[j + 24];
 216                       tab64_[i] ^= mods[j + 32];
 217                       tab72_[i] ^= mods[j + 40];
 218                       tab80_[i] ^= mods[j + 48];
 219                       tab88_[i] ^= mods[j + 56];
 220                   } // if
 221                   c >>= 1;
 222               } // for j
 223           } // for i
 224
 225           delete[] mods;
 226       } // prv_init__
 227
 228       uint64_t tab32_[256];
 229       uint64_t tab40_[256];
 230       uint64_t tab48_[256];
 231       uint64_t tab56_[256];
 232       uint64_t tab64_[256];
 233       uint64_t tab72_[256];
 234       uint64_t tab80_[256];
 235       uint64_t tab88_[256];
 236
 237   }; // class rabin64
 238
 239 } // namespace jaz
 240
 241 #endif // HASH_HPP