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