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

   1 /***
   2  *  $Id$
   3  **
   4  *  File: functional_add.hpp
   5  *  Created: Apr 02, 2011
   6  *
   7  *  Author: Jaroslaw Zola <jaroslaw.zola@gmail.com>
   8  *  Copyright (c) 2011 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 FUNCTIONAL_ADD_HPP
  16 #define FUNCTIONAL_ADD_HPP
  17
  18 #include <functional>
  19 #include <inttypes.h>
  20 #include <string.h>
  21
  22
  23 namespace jaz {
  24
  25   /** DJB2 with XOR. It is hard to say if this is good or bad function!
  26    *  Some claim it is, but some tests show it is not:
  27    *  http://www.team5150.com/~andrew/noncryptohashzoo/DJB.html
  28    *  Default seed: http://en.wikipedia.org/wiki/2147483647
  29    */
  30   class djb32 : public std::unary_function<std::string, uint32_t> {
  31   public:
  32       explicit djb32(uint32_t seed = 2147483647) : seed_(seed) { }
  33
  34       uint32_t operator()(const char* s, unsigned int l) const {
  35           const unsigned char* S = (const unsigned char*)s;
  36           uint32_t len = l;
  37
  38           uint32_t hash = 5381 + seed_ + len;
  39
  40           for (; len & ~1; len -= 2, S += 2) {
  41               hash = ((((hash << 5) + hash) ^ S[0]) * 33) ^ S[1];
  42           }
  43
  44           if (len & 1) hash = ((hash << 5) + hash) ^ S[0];
  45
  46           return hash ^ (hash >> 16);
  47       } // operator()
  48
  49       uint32_t operator()(const std::string& s) const {
  50           return this->operator()(s.c_str(), s.size());
  51       } // operator()
  52
  53   private:
  54       uint32_t seed_;
  55
  56   }; // class djb32
  57
  58
  59
  60
  61   /** Implementation of Rabin fingerprint. This code is based (to some extent)
  62    *  on Java implementations available in the Internet. I just removed all
  63    *  junk and fixed a few bugs.
  64    */
  65   class rabin64 : public std::unary_function<std::string, uint64_t> {
  66   public:
  67       // p_ represents: x^64 + x^4 + x^3 + x + 1 (which I hope is irreducible in Z2)
  68       rabin64() : p_(0x000000000000001BL), p_deg_(64) { init_(); }
  69
  70       uint64_t operator()(const char* s, unsigned int l) const {
  71           const unsigned char* S = (const unsigned char*)s;
  72
  73           uint64_t h = 0;
  74           unsigned int pos = l % 8;
  75
  76           unsigned int i = 0;
  77           if (pos != 0) for (; i < pos; ++i) h = (h << 8) ^ S[i];
  78
  79           while (i < l) {
  80               h = tab32_[h & 0xFF] ^
  81                   tab40_[(h >> 8) & 0xFF] ^
  82                   tab48_[(h >> 16) & 0xFF] ^
  83                   tab56_[(h >> 24) & 0xFF] ^
  84                   tab64_[(h >> 32) & 0xFF] ^
  85                   tab72_[(h >> 40) & 0xFF] ^
  86                   tab80_[(h >> 48) & 0xFF] ^
  87                   tab88_[(h >> 56) & 0xFF] ^
  88                   ((uint64_t)S[i] << 56) ^
  89                   ((uint64_t)S[i + 1] << 48) ^
  90                   ((uint64_t)S[i + 2] << 40) ^
  91                   ((uint64_t)S[i + 3] << 32) ^
  92                   ((uint64_t)S[i + 4] << 24) ^
  93                   ((uint64_t)S[i + 5] << 16) ^
  94                   ((uint64_t)S[i + 6] << 8) ^
  95                   (uint64_t)S[i + 7];
  96               i += 8;
  97           } // while
  98
  99           return h;
 100       } // operator
 101
 102       uint64_t operator()(const std::string& s) const {
 103           return this->operator()(s.c_str(), s.size());
 104       } // operator()
 105
 106   private:
 107       uint64_t p_;
 108       unsigned int p_deg_;
 109
 110       void init_() {
 111           uint64_t xp = (uint64_t)1 << (p_deg_ - 1);
 112           uint64_t* mods = new uint64_t[p_deg_];
 113
 114           mods[0] = p_;
 115
 116           for (unsigned int i = 1; i < p_deg_; i++) {
 117               mods[i] = mods[i - 1] << 1;
 118               if (mods[i - 1] & xp) mods[i] ^= p_;
 119           }
 120
 121           memset(tab32_, 0, 256);
 122           memset(tab40_, 0, 256);
 123           memset(tab48_, 0, 256);
 124           memset(tab56_, 0, 256);
 125           memset(tab64_, 0, 256);
 126           memset(tab72_, 0, 256);
 127           memset(tab80_, 0, 256);
 128           memset(tab88_, 0, 256);
 129
 130           for (unsigned int i = 0; i < 256; ++i) {
 131               unsigned int c = i;
 132               for (unsigned int j = 0; (j < 8) && (c > 0); ++j) {
 133                   if (c & 1) {
 134                       tab32_[i] ^= mods[j];
 135                       tab40_[i] ^= mods[j + 8];
 136                       tab48_[i] ^= mods[j + 16];
 137                       tab56_[i] ^= mods[j + 24];
 138                       tab64_[i] ^= mods[j + 32];
 139                       tab72_[i] ^= mods[j + 40];
 140                       tab80_[i] ^= mods[j + 48];
 141                       tab88_[i] ^= mods[j + 56];
 142                   }
 143                   c >>= 1;
 144               } // for j
 145           } // for i
 146
 147           delete[] mods;
 148       } // init_
 149
 150       uint64_t tab32_[256];
 151       uint64_t tab40_[256];
 152       uint64_t tab48_[256];
 153       uint64_t tab56_[256];
 154       uint64_t tab64_[256];
 155       uint64_t tab72_[256];
 156       uint64_t tab80_[256];
 157       uint64_t tab88_[256];
 158
 159   }; // class rabin64
 160
 161 } // namespace jaz
 162
 163 #endif // FUNCTIONAL_ADD_HPP