5c9a73639ad098c296c0be562c34573189f3e083
[pgbouncer.git] / src / hash.c
1 /*
2 * PgBouncer - Lightweight connection pooler for PostgreSQL.
3 *
4 * Copyright (c) 2007 Marko Kreen, Skype Technologies OÜ
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19 #include "system.h"
20 #include "hash.h"
21
22 /*
23 * A simple version of Bob Jenkins' lookup3.c hash.
24 *
25 * It is supposed to give same results as hashlittle() on little-endian
26 * and hashbig() on big-endian machines.
27 *
28 * Speed seems comparable to Jenkins' optimized version (~ -10%).
29 * Actual difference varies as it depends on cpu/compiler/libc details.
30 */
31
32 /* rotate uint32 */
33 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
34
35 /* mix 3 32-bit values reversibly */
36 #define mix(a, b, c) do { \
37 a -= c; a ^= rot(c, 4); c += b; \
38 b -= a; b ^= rot(a, 6); a += c; \
39 c -= b; c ^= rot(b, 8); b += a; \
40 a -= c; a ^= rot(c,16); c += b; \
41 b -= a; b ^= rot(a,19); a += c; \
42 c -= b; c ^= rot(b, 4); b += a; \
43 } while (0)
44
45 /* final mixing of 3 32-bit values (a,b,c) into c */
46 #define final(a, b, c) do { \
47 c ^= b; c -= rot(b,14); \
48 a ^= c; a -= rot(c,11); \
49 b ^= a; b -= rot(a,25); \
50 c ^= b; c -= rot(b,16); \
51 a ^= c; a -= rot(c, 4); \
52 b ^= a; b -= rot(a,14); \
53 c ^= b; c -= rot(b,24); \
54 } while (0)
55
56 /* short version - let compiler worry about memory access */
57 uint32_t lookup3_hash(const void *data, size_t len)
58 {
59 uint32_t a, b, c;
60 uint32_t buf[3];
61 const uint8_t *p = data;
62
63 a = b = c = 0xdeadbeef + len;
64 if (len == 0)
65 goto done;
66
67 while (len > 12) {
68 memcpy(buf, p, 12);
69 a += buf[0];
70 b += buf[1];
71 c += buf[2];
72 mix(a, b, c);
73 p += 12;
74 len -= 12;
75 }
76
77 buf[0] = buf[1] = buf[2] = 0;
78 memcpy(buf, p, len);
79 a += buf[0];
80 b += buf[1];
81 c += buf[2];
82 final(a, b, c);
83 done:
84 return c;
85 }
86
87
88 /*
89 * Reversible integer hash function by Thomas Wang.
90 */
91
92 uint32_t hash32(uint32_t v)
93 {
94 v = ~v + (v << 15);
95 v = v ^ (v >> 12);
96 v = v + (v << 2);
97 v = v ^ (v >> 4);
98 v = v * 2057;
99 v = v ^ (v >> 16);
100 return v;
101 }
102