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 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 integer X, starting from BASIS. */
 106 unsigned int
 107 hash_int (int x, unsigned int basis)
 108 {
 109   x -= x << 6;
 110   x ^= x >> 17;
 111   x -= x << 9;
 112   x ^= x << 4;
 113   x -= x << 3;
 114   x ^= x << 10;
 115   x ^= x >> 15;
 116   return x + basis;
 117 }
 118
 119 /* Returns a hash value for double D, starting from BASIS. */
 120 unsigned int
 121 hash_double (double d, unsigned int basis)
 122 {
 123   if (sizeof (double) == 8)
 124     {
 125       uint32_t tmp[2];
 126       uint32_t a, b, c;
 127
 128       a = b = c = 0xdeadbeef + 8 + basis;
 129
 130       memcpy (tmp, &d, 8);
 131       a += tmp[0];
 132       b += tmp[1];
 133       HASH_FINAL (a, b, c);
 134       return c;
 135     }
 136   else
 137     return hash_bytes (&d, sizeof d, basis);
 138 }
 139
 140 /* Returns a hash value for pointer P, starting from BASIS. */
 141 unsigned int
 142 hash_pointer (const void *p, unsigned int basis)
 143 {
 144   /* Casting to uintptr_t before casting to int suppresses a GCC warning about
 145      on 64-bit platforms. */
 146   return hash_int ((int) (uintptr_t) p, basis);
 147 }