prj/tech/libsrc/lg/hashfns.cpp

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // $Source: x:/prj/tech/libsrc/lg/RCS/hashfns.cpp $
   3 // $Author: TOML $
   4 // $Date: 1998/02/24 12:54:36 $
   5 // $Revision: 1.7 $
   6 //
   7 // Different flavors of the same hash
   8 //
   9 // Hashing based on algorithm published in C++ Report Sep. 94 (Cargill)
  10 //
  11
  12 #include <lg.h>
  13 #include <hashfns.h>
  14
  15 #include <ctype.h>
  16
  17 ///////////////////////////////////////////////////////////////////////////////
  18 //
  19 // Table of randomly shuffled values from 0-255 generated by:
  20 //
  21 //    int i, r;
  22 //    unsigned  t;
  23 //    srand(122969);
  24 //
  25 //    for (i = 0; i < 256; i++)
  26 //        g_RandomValues[i] = (unsigned )i;
  27 //
  28 //    for (i = 0; i < 256; i++)
  29 //    {
  30 //        r = rand() & 0xff;
  31 //        t = g_RandomValues[i];
  32 //        g_RandomValues[i] = g_RandomValues[r];
  33 //        g_RandomValues[r] = t;
  34 //    }
  35 //
  36
  37 static unsigned g_RandomValues[256] =
  38 {
  39     253, 197,  86, 221, 143, 177, 251,  29,
  40     130,  66, 219, 170, 250, 241, 159,  94,
  41     120, 107,  69,  45, 117,  82,  51, 137,
  42       5, 234, 238,  22, 104, 158,   2, 199,
  43      43, 187,  42,  31, 118, 254,  61,  70,
  44     185, 195, 242,  62, 106,  79,  10, 196,
  45      54,  58, 228,  30,  77, 244, 157,  71,
  46      67,  78, 211, 155, 200, 218, 252,  49,
  47     151, 202, 128, 246, 169, 131, 166,  40,
  48     164, 171,  81,  15, 186,  63, 208,  18,
  49     223,  85, 168,   6,   1, 132,  46,  34,
  50     249, 126,  83, 105, 180, 216, 102, 224,
  51     214, 237, 123, 114, 188, 148, 206, 183,
  52     222,  35,  48, 247,  25,  53, 191,  65,
  53     204,  24, 144,  14, 181, 100, 129,  11,
  54      21, 133,  37, 165,  74,  68, 111, 147,
  55      32, 255,  97, 207, 201,  27, 189,  84,
  56       9,  39, 152, 127, 176,  76, 182,  47,
  57     167, 233,  91,   8,  41, 154, 175,  75,
  58      89, 230, 229, 193,  96,  16, 150, 212,
  59     215, 121, 162, 220, 116,  93, 192, 227,
  60      44, 141, 115, 163,  98, 232, 139,  20,
  61     145, 172,  59,  57,  13,  56,  28,  90,
  62      60, 225, 149, 110, 210, 153, 194,  26,
  63     108,   0, 109, 178,  55, 198,  12, 146,
  64      52, 209,  88,  73,  36,  17, 203, 217,
  65       4, 136,  72, 190, 236,  87, 174, 112,
  66     245, 103,  99, 142, 140, 226,  33, 125,
  67     205, 184,  50, 179, 160, 240,  19,  80,
  68     239,   3,  23, 134,  92, 235,   7, 156,
  69      64, 135, 213, 161, 124,  38, 243, 122,
  70     119, 113, 173,  95, 248, 138, 101, 231
  71 };
  72
  73
  74 ///////////////////////////////////////////////////////////////////////////////
  75 //
  76 // Hash a string
  77 //
  78
  79 unsigned LGAPI HashString(const char * pszKey)
  80 {
  81     const uchar *   k = (const uchar *) pszKey;
  82     unsigned        even = 0,
  83                     odd  = 0,
  84                     n;
  85
  86     while ((n = *k++) != 0)
  87     {
  88         even = g_RandomValues[even ^ n];
  89         if ((n = *k++) != 0)
  90             odd = g_RandomValues[odd ^ n];
  91         else
  92             break;
  93     }
  94
  95     return (even << 8) | odd;
  96 }
  97
  98 ///////////////////////////////////////
  99
 100 unsigned LGAPI HashStringCaseless(const char * pszKey)
 101 {
 102     const uchar *   k = (const uchar *) pszKey;
 103     unsigned        even = 0,
 104                     odd  = 0,
 105                     n;
 106
 107     while ((n = toupper(*k++)) != 0)
 108     {
 109         even = g_RandomValues[even ^ n];
 110         if ((n = toupper(*k++)) != 0)
 111             odd = g_RandomValues[odd ^ n];
 112         else
 113             break;
 114     }
 115
 116     return (even << 8) | odd;
 117 }
 118
 119 ///////////////////////////////////////
 120 //
 121 // Hash a GUID
 122 //
 123
 124 unsigned LGAPI HashGUID(const GUID * pID)
 125 {
 126     register const DWORD *  p = (const DWORD *) pID;
 127     register unsigned       even,
 128                             odd,
 129                             n;
 130     n = *p;
 131     even    = g_RandomValues[n & 0xff];
 132     odd     = g_RandomValues[((n >> 8) & 0xff)];
 133
 134     even    = g_RandomValues[even ^ (n >> 24)];
 135     odd     = g_RandomValues[odd ^ (n >> 16) & 0xff];
 136     even    = g_RandomValues[even ^ ((n >> 8) & 0xff)];
 137     odd     = g_RandomValues[odd  ^ (n & 0xff)];
 138
 139     n = *(p+1);
 140     even    = g_RandomValues[even ^ (n >> 24)];
 141     odd     = g_RandomValues[odd  ^ ((n >> 16) & 0xff)];
 142     even    = g_RandomValues[even ^ ((n >> 8) & 0xff)];
 143     odd     = g_RandomValues[odd  ^ (n & 0xff)];
 144
 145     n = *(p+2);
 146     even    = g_RandomValues[even ^ (n >> 24)];
 147     odd     = g_RandomValues[odd  ^ ((n >> 16) & 0xff)];
 148     even    = g_RandomValues[even ^ ((n >> 8) & 0xff)];
 149     odd     = g_RandomValues[odd  ^ (n & 0xff)];
 150
 151     n = *(p+3);
 152     even    = g_RandomValues[even ^ (n >> 24)];
 153     odd     = g_RandomValues[odd  ^ ((n >> 16) & 0xff)];
 154     even    = g_RandomValues[even ^ ((n >> 8) & 0xff)];
 155     odd     = g_RandomValues[odd  ^ (n & 0xff)];
 156
 157     return (even << 8) | odd;
 158 }
 159
 160
 161 ///////////////////////////////////////
 162 //
 163 // Hash a pointer
 164 //
 165
 166 unsigned LGAPI HashPtr(const void * p)
 167 {
 168    unsigned    odd,
 169                even;
 170
 171    odd     = g_RandomValues[(((unsigned)p >> 8) & 0xff)];
 172    even    = g_RandomValues[(unsigned)p & 0xff];
 173
 174    odd     = g_RandomValues[odd  ^ ((unsigned)p & 0xff)];
 175    p = (const void *)((unsigned)p >> 8);
 176    even    = g_RandomValues[even ^ (((unsigned)p) & 0xff)];
 177    p = (const void *)((unsigned)p >> 8);
 178    odd     = g_RandomValues[odd  ^ (((unsigned)p) & 0xff)];
 179    p = (const void *)((unsigned)p >> 8);
 180    even    = g_RandomValues[even ^ ((unsigned)p)];
 181
 182    return (even << 8) | odd;
 183 }
 184
 185 ///////////////////////////////////////
 186 //
 187 // Hash a long
 188 //
 189
 190 // @Note (toml 02-24-98): this function is now obsoldete and should be removed
 191 // at some time in the future. Right now, it has been left in so we don't have
 192 // to rebuild the world.
 193 #undef HashLong
 194 #pragma message("read the comment dated 02-24-98!")
 195
 196 EXTERN unsigned LGAPI HashLong(long key)
 197 {
 198    return HashPtr((void *)key);
 199 }
 200
 201 ///////////////////////////////////////
 202 //
 203 // Hash an thing of the given size
 204 //
 205
 206 unsigned LGAPI HashThing(const void * pKey, unsigned size)
 207 {
 208     const uchar *       k = (const uchar *) pKey;
 209     unsigned            even = 0,
 210                         odd = 0,
 211                         n;
 212
 213     while (size--)
 214     {
 215         n = *k++;
 216         even = g_RandomValues[even ^ n];
 217         if (size--)
 218         {
 219             n = *k++;
 220             odd = g_RandomValues[odd ^ n];
 221         }
 222         else
 223             break;
 224     }
 225
 226     return (even << 8) | odd;
 227 }
 228
 229 ///////////////////////////////////////////////////////////////////////////////