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