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