Torque3D Documentation / _generateds / hashFunction.cpp

hashFunction.cpp

Engine/source/core/util/hashFunction.cpp

More...

Namespaces:

namespace
Torque

Public Defines

define
hashmask(n) (()-1)
define
hashsize(n) (()1<<())
define
mix(a, b, c) { \
    -= ;  -= c;  ^= (c>>13); \
    -= c;  -= ;  ^= (<<8); \
   c -= ; c -= ; c ^= (>>13); \
    -= ;  -= c;  ^= (c>>12);  \
    -= c;  -= ;  ^= (<<16); \
   c -= ; c -= ; c ^= (>>5); \
    -= ;  -= c;  ^= (c>>3);  \
    -= c;  -= ;  ^= (<<10); \
   c -= ; c -= ; c ^= (>>15); \
}
define
mix64(a, b, c) { \
   -= ;  -= c;  ^= (c>>43); \
   -= c;  -= ;  ^= (<<9); \
  c -= ; c -= ; c ^= (>>8); \
   -= ;  -= c;  ^= (c>>38); \
   -= c;  -= ;  ^= (<<23); \
  c -= ; c -= ; c ^= (>>5); \
   -= ;  -= c;  ^= (c>>35); \
   -= c;  -= ;  ^= (<<49); \
  c -= ; c -= ; c ^= (>>11); \
   -= ;  -= c;  ^= (c>>12); \
   -= c;  -= ;  ^= (<<18); \
  c -= ; c -= ; c ^= (>>22); \
}

Detailed Description

Public Defines

hashmask(n) (()-1)

hashsize(n) (()1<<())

mix(a, b, c) { \
    -= ;  -= c;  ^= (c>>13); \
    -= c;  -= ;  ^= (<<8); \
   c -= ; c -= ; c ^= (>>13); \
    -= ;  -= c;  ^= (c>>12);  \
    -= c;  -= ;  ^= (<<16); \
   c -= ; c -= ; c ^= (>>5); \
    -= ;  -= c;  ^= (c>>3);  \
    -= c;  -= ;  ^= (<<10); \
   c -= ; c -= ; c ^= (>>15); \
}

mix64(a, b, c) { \
   -= ;  -= c;  ^= (c>>43); \
   -= c;  -= ;  ^= (<<9); \
  c -= ; c -= ; c ^= (>>8); \
   -= ;  -= c;  ^= (c>>38); \
   -= c;  -= ;  ^= (<<23); \
  c -= ; c -= ; c ^= (>>5); \
   -= ;  -= c;  ^= (c>>35); \
   -= c;  -= ;  ^= (<<49); \
  c -= ; c -= ; c ^= (>>11); \
   -= ;  -= c;  ^= (c>>12); \
   -= c;  -= ;  ^= (<<18); \
  c -= ; c -= ; c ^= (>>22); \
}

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24// Borrowed from: http://burtleburtle.net/bob/hash/doobs.html
 25//
 26// Original code by:
 27//
 28// By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
 29// code any way you wish, private, educational, or commercial.  It's free.
 30
 31#include "platform/platform.h"
 32
 33#include "core/util/hashFunction.h"
 34
 35namespace Torque
 36{
 37
 38#define hashsize(n) ((U32)1<<(n))
 39#define hashmask(n) (hashsize(n)-1)
 40
 41/*
 42--------------------------------------------------------------------
 43mix -- mix 3 32-bit values reversibly.
 44For every delta with one or two bits set, and the deltas of all three
 45high bits or all three low bits, whether the original value of a,b,c
 46is almost all zero or is uniformly distributed,
 47* If mix() is run forward or backward, at least 32 bits in a,b,c
 48have at least 1/4 probability of changing.
 49* If mix() is run forward, every bit of c will change between 1/3 and
 502/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
 51mix() was built out of 36 single-cycle latency instructions in a
 52structure that could supported 2x parallelism, like so:
 53a -= b;
 54a -= c; x = (c>>13);
 55b -= c; a ^= x;
 56b -= a; x = (a<<8);
 57c -= a; b ^= x;
 58c -= b; x = (b>>13);
 59...
 60Unfortunately, superscalar Pentiums and Sparcs can't take advantage
 61of that parallelism.  They've also turned some of those single-cycle
 62latency instructions into multi-cycle latency instructions.  Still,
 63this is the fastest good hash I could find.  There were about 2^^68
 64to choose from.  I only looked at a billion or so.
 65--------------------------------------------------------------------
 66*/
 67#define mix(a,b,c) \
 68{ \
 69   a -= b; a -= c; a ^= (c>>13); \
 70   b -= c; b -= a; b ^= (a<<8); \
 71   c -= a; c -= b; c ^= (b>>13); \
 72   a -= b; a -= c; a ^= (c>>12);  \
 73   b -= c; b -= a; b ^= (a<<16); \
 74   c -= a; c -= b; c ^= (b>>5); \
 75   a -= b; a -= c; a ^= (c>>3);  \
 76   b -= c; b -= a; b ^= (a<<10); \
 77   c -= a; c -= b; c ^= (b>>15); \
 78}
 79
 80/*
 81--------------------------------------------------------------------
 82hash() -- hash a variable-length key into a 32-bit value
 83k       : the key (the unaligned variable-length array of bytes)
 84len     : the length of the key, counting by bytes
 85initval : can be any 4-byte value
 86Returns a 32-bit value.  Every bit of the key affects every bit of
 87the return value.  Every 1-bit and 2-bit delta achieves avalanche.
 88About 6*len+35 instructions.
 89
 90The best hash table sizes are powers of 2.  There is no need to do
 91mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 92use a bitmask.  For example, if you need only 10 bits, do
 93h = (h & hashmask(10));
 94In which case, the hash table should have hashsize(10) elements.
 95
 96If you are hashing n strings (U8 **)k, do it like this:
 97for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
 98
 99By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
100code any way you wish, private, educational, or commercial.  It's free.
101
102See http://burtleburtle.net/bob/hash/evahash.html
103Use for hash table lookup, or anything where one collision in 2^^32 is
104acceptable.  Do NOT use for cryptographic purposes.
105--------------------------------------------------------------------
106*/
107
108U32 hash(const U8 *k, U32 length, U32 initval)
109{
110   U32 a,b,c,len;
111
112   /* Set up the internal state */
113   len = length;
114   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
115   c = initval;         /* the previous hash value */
116
117   /*---------------------------------------- handle most of the key */
118   while (len >= 12)
119   {
120      a += (k[0] +((U32)k[1]<<8) +((U32)k[2]<<16) +((U32)k[3]<<24));
121      b += (k[4] +((U32)k[5]<<8) +((U32)k[6]<<16) +((U32)k[7]<<24));
122      c += (k[8] +((U32)k[9]<<8) +((U32)k[10]<<16)+((U32)k[11]<<24));
123      mix(a,b,c);
124      k += 12; len -= 12;
125   }
126
127   /*------------------------------------- handle the last 11 bytes */
128   c += length;
129   switch(len)              /* all the case statements fall through */
130   {
131   case 11: c+=((U32)k[10]<<24);
132   case 10: c+=((U32)k[9]<<16);
133   case 9 : c+=((U32)k[8]<<8);
134      /* the first byte of c is reserved for the length */
135   case 8 : b+=((U32)k[7]<<24);
136   case 7 : b+=((U32)k[6]<<16);
137   case 6 : b+=((U32)k[5]<<8);
138   case 5 : b+=k[4];
139   case 4 : a+=((U32)k[3]<<24);
140   case 3 : a+=((U32)k[2]<<16);
141   case 2 : a+=((U32)k[1]<<8);
142   case 1 : a+=k[0];
143      /* case 0: nothing left to add */
144   }
145   mix(a,b,c);
146   /*-------------------------------------------- report the result */
147   return c;
148}
149
150
151/*
152--------------------------------------------------------------------
153mix -- mix 3 64-bit values reversibly.
154mix() takes 48 machine instructions, but only 24 cycles on a superscalar
155  machine (like Intel's new MMX architecture).  It requires 4 64-bit
156  registers for 4::2 parallelism.
157All 1-bit deltas, all 2-bit deltas, all deltas composed of top bits of
158  (a,b,c), and all deltas of bottom bits were tested.  All deltas were
159  tested both on random keys and on keys that were nearly all zero.
160  These deltas all cause every bit of c to change between 1/3 and 2/3
161  of the time (well, only 113/400 to 287/400 of the time for some
162  2-bit delta).  These deltas all cause at least 80 bits to change
163  among (a,b,c) when the mix is run either forward or backward (yes it
164  is reversible).
165This implies that a hash using mix64 has no funnels.  There may be
166  characteristics with 3-bit deltas or bigger, I didn't test for
167  those.
168--------------------------------------------------------------------
169*/
170#define mix64(a,b,c) \
171{ \
172  a -= b; a -= c; a ^= (c>>43); \
173  b -= c; b -= a; b ^= (a<<9); \
174  c -= a; c -= b; c ^= (b>>8); \
175  a -= b; a -= c; a ^= (c>>38); \
176  b -= c; b -= a; b ^= (a<<23); \
177  c -= a; c -= b; c ^= (b>>5); \
178  a -= b; a -= c; a ^= (c>>35); \
179  b -= c; b -= a; b ^= (a<<49); \
180  c -= a; c -= b; c ^= (b>>11); \
181  a -= b; a -= c; a ^= (c>>12); \
182  b -= c; b -= a; b ^= (a<<18); \
183  c -= a; c -= b; c ^= (b>>22); \
184}
185
186/*
187--------------------------------------------------------------------
188hash64() -- hash a variable-length key into a 64-bit value
189  k     : the key (the unaligned variable-length array of bytes)
190  len   : the length of the key, counting by bytes
191  level : can be any 8-byte value
192Returns a 64-bit value.  Every bit of the key affects every bit of
193the return value.  No funnels.  Every 1-bit and 2-bit delta achieves
194avalanche.  About 41+5len instructions.
195
196The best hash table sizes are powers of 2.  There is no need to do
197mod a prime (mod is sooo slow!).  If you need less than 64 bits,
198use a bitmask.  For example, if you need only 10 bits, do
199  h = (h & hashmask(10));
200In which case, the hash table should have hashsize(10) elements.
201
202If you are hashing n strings (ub1 **)k, do it like this:
203  for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
204
205By Bob Jenkins, Jan 4 1997.  bob_jenkins@burtleburtle.net.  You may
206use this code any way you wish, private, educational, or commercial,
207but I would appreciate if you give me credit.
208
209See http://burtleburtle.net/bob/hash/evahash.html
210Use for hash table lookup, or anything where one collision in 2^^64
211is acceptable.  Do NOT use for cryptographic purposes.
212--------------------------------------------------------------------
213*/
214
215U64 hash64( const U8 *k, U32 length, U64 initval )
216{
217  U64 a,b,c,len;
218
219  /* Set up the internal state */
220  len = length;
221  a = b = initval;                         /* the previous hash value */
222  c = 0x9e3779b97f4a7c13LL; /* the golden ratio; an arbitrary value */
223
224  /*---------------------------------------- handle most of the key */
225  while (len >= 24)
226  {
227    a += (k[0]        +((U64)k[ 1]<< 8)+((U64)k[ 2]<<16)+((U64)k[ 3]<<24)
228     +((U64)k[4 ]<<32)+((U64)k[ 5]<<40)+((U64)k[ 6]<<48)+((U64)k[ 7]<<56));
229    b += (k[8]        +((U64)k[ 9]<< 8)+((U64)k[10]<<16)+((U64)k[11]<<24)
230     +((U64)k[12]<<32)+((U64)k[13]<<40)+((U64)k[14]<<48)+((U64)k[15]<<56));
231    c += (k[16]       +((U64)k[17]<< 8)+((U64)k[18]<<16)+((U64)k[19]<<24)
232     +((U64)k[20]<<32)+((U64)k[21]<<40)+((U64)k[22]<<48)+((U64)k[23]<<56));
233    mix64(a,b,c);
234    k += 24; len -= 24;
235  }
236
237  /*------------------------------------- handle the last 23 bytes */
238  c += length;
239  switch(len)              /* all the case statements fall through */
240  {
241  case 23: c+=((U64)k[22]<<56);
242  case 22: c+=((U64)k[21]<<48);
243  case 21: c+=((U64)k[20]<<40);
244  case 20: c+=((U64)k[19]<<32);
245  case 19: c+=((U64)k[18]<<24);
246  case 18: c+=((U64)k[17]<<16);
247  case 17: c+=((U64)k[16]<<8);
248    /* the first byte of c is reserved for the length */
249  case 16: b+=((U64)k[15]<<56);
250  case 15: b+=((U64)k[14]<<48);
251  case 14: b+=((U64)k[13]<<40);
252  case 13: b+=((U64)k[12]<<32);
253  case 12: b+=((U64)k[11]<<24);
254  case 11: b+=((U64)k[10]<<16);
255  case 10: b+=((U64)k[ 9]<<8);
256  case  9: b+=((U64)k[ 8]);
257  case  8: a+=((U64)k[ 7]<<56);
258  case  7: a+=((U64)k[ 6]<<48);
259  case  6: a+=((U64)k[ 5]<<40);
260  case  5: a+=((U64)k[ 4]<<32);
261  case  4: a+=((U64)k[ 3]<<24);
262  case  3: a+=((U64)k[ 2]<<16);
263  case  2: a+=((U64)k[ 1]<<8);
264  case  1: a+=((U64)k[ 0]);
265    /* case 0: nothing left to add */
266  }
267  mix64(a,b,c);
268  /*-------------------------------------------- report the result */
269  return c;
270}
271
272} // namespace
273