gui: Allow File|Open to select an encoding for system files.
[pspp] / 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 }