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 null-terminated string S, with
 106    lowercase and uppercase letters treated as equal, starting
 107    from BASIS. */
 108 unsigned int
 109 hash_case_string (const char *s, unsigned int basis)
 110 {
 111   size_t n = strlen (s);
 112   uint32_t a, b, c;
 113   uint32_t tmp[3];
 114   int i;
 115
 116   a = b = c = 0xdeadbeef + n + basis;
 117
 118   while (n >= 12)
 119     {
 120       for (i = 0; i < 12; i++)
 121         ((unsigned char *)tmp)[i] = toupper ((unsigned char) s[i]);
 122       a += tmp[0];
 123       b += tmp[1];
 124       c += tmp[2];
 125       HASH_MIX (a, b, c);
 126       n -= 12;
 127       s += 12;
 128     }
 129
 130   if (n > 0)
 131     {
 132       memset (tmp, 0, 12);
 133       for (i = 0; i < n; i++)
 134         ((unsigned char *)tmp)[i] = toupper ((unsigned char) s[i]);
 135       a += tmp[0];
 136       b += tmp[1];
 137       c += tmp[2];
 138     }
 139
 140   HASH_FINAL (a, b, c);
 141   return c;
 142 }
 143
 144 /* Returns a hash value for integer X, starting from BASIS. */
 145 unsigned int
 146 hash_int (int x, unsigned int basis)
 147 {
 148   x -= x << 6;
 149   x ^= x >> 17;
 150   x -= x << 9;
 151   x ^= x << 4;
 152   x -= x << 3;
 153   x ^= x << 10;
 154   x ^= x >> 15;
 155   return x + basis;
 156 }
 157
 158 /* Returns a hash value for double D, starting from BASIS. */
 159 unsigned int
 160 hash_double (double d, unsigned int basis)
 161 {
 162   if (sizeof (double) == 8)
 163     {
 164       uint32_t tmp[2];
 165       uint32_t a, b, c;
 166
 167       a = b = c = 0xdeadbeef + 8 + basis;
 168
 169       memcpy (tmp, &d, 8);
 170       a += tmp[0];
 171       b += tmp[1];
 172       HASH_FINAL (a, b, c);
 173       return c;
 174     }
 175   else
 176     return hash_bytes (&d, sizeof d, basis);
 177 }
 178
 179 /* Returns a hash value for pointer P, starting from BASIS. */
 180 unsigned int
 181 hash_pointer (const void *p, unsigned int basis)
 182 {
 183   /* Casting to uintptr_t before casting to int suppresses a GCC warning about
 184      on 64-bit platforms. */
 185   return hash_int ((int) (uintptr_t) p, basis);
 186 }