1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 1997-9, 2000, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
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.
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.
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/>. */
19 #include "libpspp/hash-functions.h"
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
35 #define HASH_ROT(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
37 #define HASH_MIX(a, b, c) \
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; \
49 #define HASH_FINAL(a, b, c) \
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); \
62 /* Returns a hash value for the N bytes starting at P, starting
65 hash_bytes (const void *p_, size_t n, unsigned int basis)
67 const uint8_t *p = p_;
71 a = b = c = 0xdeadbeef + n + basis;
97 /* Returns a hash value for null-terminated string S, starting
100 hash_string (const char *s, unsigned int basis)
102 return hash_bytes (s, strlen (s), basis);
105 /* Returns a hash value for null-terminated string S, with
106 lowercase and uppercase letters treated as equal, starting
109 hash_case_string (const char *s, unsigned int basis)
111 size_t n = strlen (s);
116 a = b = c = 0xdeadbeef + n + basis;
120 for (i = 0; i < 12; i++)
121 ((unsigned char *)tmp)[i] = toupper ((unsigned char) s[i]);
133 for (i = 0; i < n; i++)
134 ((unsigned char *)tmp)[i] = toupper ((unsigned char) s[i]);
140 HASH_FINAL (a, b, c);
144 /* Returns a hash value for integer X, starting from BASIS. */
146 hash_int (int x, unsigned int basis)
158 /* Returns a hash value for double D, starting from BASIS. */
160 hash_double (double d, unsigned int basis)
162 if (sizeof (double) == 8)
167 a = b = c = 0xdeadbeef + 8 + basis;
172 HASH_FINAL (a, b, c);
176 return hash_bytes (&d, sizeof d, basis);
179 /* Returns a hash value for pointer P, starting from BASIS. */
181 hash_pointer (const void *p, unsigned int basis)
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);