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