intern/string/STR_HashedString.h

   1 /*
   2  * ***** BEGIN GPL LICENSE BLOCK *****
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  17  *
  18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  19  * All rights reserved.
  20  *
  21  * The Original Code is: all of this file.
  22  *
  23  * Contributor(s): none yet.
  24  *
  25  * ***** END GPL LICENSE BLOCK *****
  26  */
  27
  28 /** \file string/STR_HashedString.h
  29  *  \ingroup string
  30  *
  31  * Copyright (C) 2001 NaN Technologies B.V.
  32  * This file was formerly known as: GEN_StdString.cpp.
  33  * \date        November, 14, 2001
  34  */
  35
  36 #ifndef __STR_HASHEDSTRING_H__
  37 #define __STR_HASHEDSTRING_H__
  38
  39 #include "STR_String.h"
  40
  41
  42 // Hash Mix utility function, by Bob Jenkins - Mix 3 32-bit values reversibly
  43 //
  44 // - If gHashMix() is run forward or backward, at least 32 bits in a,b,c have at
  45 //   least 1/4 probability of changing.
  46 //
  47 // - If gHashMix() is run forward, every bit of c will change between 1/3 and
  48 //   2/3 of the time.
  49 //
  50 static inline void STR_gHashMix(dword& a, dword& b, dword& c)
  51 {
  52         a -= b; a -= c; a ^= (c >> 13);
  53         b -= c; b -= a; b ^= (a << 8);
  54         c -= a; c -= b; c ^= (b >> 13);
  55         a -= b; a -= c; a ^= (c >> 12);
  56         b -= c; b -= a; b ^= (a << 16);
  57         c -= a; c -= b; c ^= (b >> 5);
  58         a -= b; a -= c; a ^= (c >> 3);
  59         b -= c; b -= a; b ^= (a << 10);
  60         c -= a; c -= b; c ^= (b >> 15);
  61 }
  62
  63 //
  64 // Fast Hashable<int32> functionality
  65 // http://www.concentric.net/~Ttwang/tech/inthash.htm
  66 //
  67 static inline dword         STR_gHash(dword inDWord)
  68 {
  69         dword key = inDWord;
  70         key += ~(key << 16);
  71         key ^=  (key >>  5);
  72         key +=  (key <<  3);
  73         key ^=  (key >> 13);
  74         key += ~(key <<  9);
  75         key ^=  (key >> 17);
  76         return key;
  77 }
  78
  79 enum { GOLDEN_RATIO = 0x9e3779b9 }; /* arbitrary value to initialize hash funtion, well not so arbitrary
  80                                      * as this value is taken from the pigs library (Orange Games/Lost Boys) */
  81
  82
  83
  84 static dword STR_gHash(const void *in, int len, dword init_val)
  85 {
  86         unsigned int length = len;
  87         dword a = (dword)GOLDEN_RATIO;
  88         dword b = (dword)GOLDEN_RATIO;
  89         dword c = init_val;  /* the previous hash value */
  90         byte  *p_in = (byte *)in;
  91
  92         // Do the largest part of the key
  93         while (length >= 12)
  94         {
  95                 a += (p_in[0] + ((dword)p_in[1] << 8) + ((dword)p_in[2]  << 16) + ((dword)p_in[3]  << 24));
  96                 b += (p_in[4] + ((dword)p_in[5] << 8) + ((dword)p_in[6]  << 16) + ((dword)p_in[7]  << 24));
  97                 c += (p_in[8] + ((dword)p_in[9] << 8) + ((dword)p_in[10] << 16) + ((dword)p_in[11] << 24));
  98                 STR_gHashMix(a, b, c);
  99                 p_in += 12; length -= 12;
 100         }
 101
 102         // Handle the last 11 bytes
 103         c += len;
 104         switch (length) {
 105                 case 11: c += ((dword)p_in[10] << 24);
 106                 case 10: c += ((dword)p_in[9]  << 16);
 107                 case  9: c += ((dword)p_in[8]  << 8);  /* the first byte of c is reserved for the length */
 108                 case  8: b += ((dword)p_in[7]  << 24);
 109                 case  7: b += ((dword)p_in[6]  << 16);
 110                 case  6: b += ((dword)p_in[5]  << 8);
 111                 case  5: b += p_in[4];
 112                 case  4: a += ((dword)p_in[3]  << 24);
 113                 case  3: a += ((dword)p_in[2]  << 16);
 114                 case  2: a += ((dword)p_in[1]  << 8);
 115                 case  1: a += p_in[0];
 116         }
 117         STR_gHashMix(a, b, c);
 118
 119         return c;
 120 }
 121
 122
 123
 124
 125 class STR_HashedString : public STR_String
 126 {
 127 public:
 128         STR_HashedString() : STR_String(), m_Hashed(false) {}
 129         STR_HashedString(const char *str) : STR_String(str), m_Hashed(false) {}
 130         STR_HashedString(const STR_String &str) : STR_String(str), m_Hashed(false) {}
 131
 132         inline dword hash(dword init = 0) const
 133         {
 134                 if (!m_Hashed)
 135                 {
 136                         const char *str = *this;
 137                         int length = this->Length();
 138                         m_CachedHash = STR_gHash(str, length, init);
 139                         m_Hashed = true;
 140                 }
 141                 return m_CachedHash;
 142         }
 143
 144 private:
 145         mutable bool m_Hashed;
 146         mutable dword m_CachedHash;
 147 };
 148
 149 #endif //__STR_HASHEDSTRING_H__
 150