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