pintos-os.org Git - pspp/blob - src/libpspp/hash-functions.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 1997-9, 2000, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (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, see <http://www.gnu.org/licenses/>. */
  16
  17 #include <config.h>
  18
  19 #include "libpspp/hash-functions.h"
  20
  21 #include <assert.h>
  22 #include <ctype.h>
  23 #include <math.h>
  24 #include <stdint.h>
  25 #include <string.h>
  26
  27 /* Based on http://burtleburtle.net/bob/c/lookup3.c, by Bob
  28    Jenkins <bob_jenkins@burtleburtle.net>, as retrieved on April
  29    8, 2009.  The license information there says the following:
  30    "You can use this free for any purpose.  It's in the public
  31    domain.  It has no warranty." and "You may use this code any
  32    way you wish, private, educational, or commercial.  It's
  33    free." */
  34
  35 #define HASH_ROT(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
  36
  37 #define HASH_MIX(a, b, c)                               \
  38         do                                              \
  39           {                                             \
  40             a -= c;  a ^= HASH_ROT (c,  4);  c += b;    \
  41             b -= a;  b ^= HASH_ROT (a,  6);  a += c;    \
  42             c -= b;  c ^= HASH_ROT (b,  8);  b += a;    \
  43             a -= c;  a ^= HASH_ROT (c, 16);  c += b;    \
  44             b -= a;  b ^= HASH_ROT (a, 19);  a += c;    \
  45             c -= b;  c ^= HASH_ROT (b,  4);  b += a;    \
  46           }                                             \
  47         while (0)
  48
  49 #define HASH_FINAL(a, b, c)                     \
  50         do                                      \
  51           {                                     \
  52             c ^= b; c -= HASH_ROT (b, 14);      \
  53             a ^= c; a -= HASH_ROT (c, 11);      \
  54             b ^= a; b -= HASH_ROT (a, 25);      \
  55             c ^= b; c -= HASH_ROT (b, 16);      \
  56             a ^= c; a -= HASH_ROT (c, 4);       \
  57             b ^= a; b -= HASH_ROT (a, 14);      \
  58             c ^= b; c -= HASH_ROT (b, 24);      \
  59           }                                     \
  60         while (0)
  61
  62 /* Returns a hash value for the N bytes starting at P, starting
  63    from BASIS. */
  64 unsigned int
  65 hash_bytes (const void *p_, size_t n, unsigned int basis)
  66 {
  67   const uint8_t *p = p_;
  68   uint32_t a, b, c;
  69   uint32_t tmp[3];
  70
  71   a = b = c = 0xdeadbeef + n + basis;
  72
  73   while (n >= 12)
  74     {
  75       memcpy (tmp, p, 12);
  76       a += tmp[0];
  77       b += tmp[1];
  78       c += tmp[2];
  79       HASH_MIX (a, b, c);
  80       n -= 12;
  81       p += 12;
  82     }
  83
  84   if (n > 0)
  85     {
  86       memset (tmp, 0, 12);
  87       memcpy (tmp, p, n);
  88       a += tmp[0];
  89       b += tmp[1];
  90       c += tmp[2];
  91     }
  92
  93   HASH_FINAL (a, b, c);
  94   return c;
  95 }
  96
  97 /* Returns a hash value for null-terminated string S, starting
  98    from BASIS. */
  99 unsigned int
 100 hash_string (const char *s, unsigned int basis)
 101 {
 102   return hash_bytes (s, strlen (s), basis);
 103 }
 104
 105 /* Returns a hash value for the N bytes at S, with lowercase and uppercase
 106    letters treated as equal, starting from BASIS. */
 107 unsigned int
 108 hash_case_bytes (const void *s_, size_t n, unsigned int basis)
 109 {
 110   const char *s = s_;
 111   uint32_t a, b, c;
 112   uint32_t tmp[3];
 113   int i;
 114
 115   a = b = c = 0xdeadbeef + n + basis;
 116
 117   while (n >= 12)
 118     {
 119       for (i = 0; i < 12; i++)
 120         ((unsigned char *)tmp)[i] = toupper ((unsigned char) s[i]);
 121       a += tmp[0];
 122       b += tmp[1];
 123       c += tmp[2];
 124       HASH_MIX (a, b, c);
 125       n -= 12;
 126       s += 12;
 127     }
 128
 129   if (n > 0)
 130     {
 131       memset (tmp, 0, 12);
 132       for (i = 0; i < n; i++)
 133         ((unsigned char *)tmp)[i] = toupper ((unsigned char) s[i]);
 134       a += tmp[0];
 135       b += tmp[1];
 136       c += tmp[2];
 137     }
 138
 139   HASH_FINAL (a, b, c);
 140   return c;
 141 }
 142
 143 /* Returns a hash value for null-terminated string S, with
 144    lowercase and uppercase letters treated as equal, starting
 145    from BASIS. */
 146 unsigned int
 147 hash_case_string (const char *s, unsigned int basis)
 148 {
 149   return hash_case_bytes (s, strlen (s), basis);
 150 }
 151
 152 /* Returns a hash value for integer X, starting from BASIS. */
 153 unsigned int
 154 hash_int (int x, unsigned int basis)
 155 {
 156   x -= x << 6;
 157   x ^= x >> 17;
 158   x -= x << 9;
 159   x ^= x << 4;
 160   x -= x << 3;
 161   x ^= x << 10;
 162   x ^= x >> 15;
 163   return x + basis;
 164 }
 165
 166 /* Returns a hash value for double D, starting from BASIS. */
 167 unsigned int
 168 hash_double (double d, unsigned int basis)
 169 {
 170   if (sizeof (double) == 8)
 171     {
 172       uint32_t tmp[2];
 173       uint32_t a, b, c;
 174
 175       a = b = c = 0xdeadbeef + 8 + basis;
 176
 177       memcpy (tmp, &d, 8);
 178       a += tmp[0];
 179       b += tmp[1];
 180       HASH_FINAL (a, b, c);
 181       return c;
 182     }
 183   else
 184     return hash_bytes (&d, sizeof d, basis);
 185 }
 186
 187 /* Returns a hash value for pointer P, starting from BASIS. */
 188 unsigned int
 189 hash_pointer (const void *p, unsigned int basis)
 190 {
 191   /* Casting to uintptr_t before casting to int suppresses a GCC warning about
 192      on 64-bit platforms. */
 193   return hash_int ((int) (uintptr_t) p, basis);
 194 }