1 /* $NetBSD: mi_vector_hash.c,v 1.1 2013/12/11 01:24:08 joerg Exp $ */
2 /*-
3 * Copyright (c) 2009 The NetBSD Foundation, Inc.
4 * All rights reserved.
5 *
6 * This code is derived from software contributed to The NetBSD Foundation
7 * by Joerg Sonnenberger.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
28 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
29 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
30 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34 /*
35 * See http://burtleburtle.net/bob/hash/doobs.html for the full description
36 * and the original version of the code. This version differs by exposing
37 * the full internal state and avoiding byte operations in the inner loop
38 * if the key is aligned correctly.
39 */
40
41 #if HAVE_NBTOOL_CONFIG_H
42 #include "nbtool_config.h"
43 #endif
44
45 #include <sys/cdefs.h>
46 __RCSID("$NetBSD: mi_vector_hash.c,v 1.1 2013/12/11 01:24:08 joerg Exp $");
47
48 #if !HAVE_NBTOOL_CONFIG_H || HAVE_SYS_ENDIAN_H
49 #if defined(__NetBSD__) || defined(__FreeBSD__)
50 #include <sys/endian.h>
51 #else
52 #include <endian.h>
53 #endif
54 #endif
55
56 #if defined(_KERNEL) || defined(_STANDALONE)
57 #include <sys/types.h>
58 #include <sys/systm.h>
59 #include <lib/libkern/libkern.h>
60 #else
61 #if 0
62 #include "namespace.h"
63 #endif
64
65 #include <stdint.h>
66 #include <stdlib.h>
67 #endif
68
69 #include "cdb_impl.h"
70
71 #define mix(a, b, c) do { \
72 a -= b; a -= c; a ^= (c >> 13); \
73 b -= c; b -= a; b ^= (a << 8); \
74 c -= a; c -= b; c ^= (b >> 13); \
75 a -= b; a -= c; a ^= (c >> 12); \
76 b -= c; b -= a; b ^= (a << 16); \
77 c -= a; c -= b; c ^= (b >> 5); \
78 a -= b; a -= c; a ^= (c >> 3); \
79 b -= c; b -= a; b ^= (a << 10); \
80 c -= a; c -= b; c ^= (b >> 15); \
81 } while (/* CONSTCOND */0)
82
83 #define FIXED_SEED 0x9e3779b9 /* Golden ratio, arbitrary constant */
84
85 #if !defined(_KERNEL) && !defined(_STANDALONE)
86 #ifdef __weak_alias
__weak_alias(mi_vector_hash,_mi_vector_hash)87 __weak_alias(mi_vector_hash, _mi_vector_hash)
88 #endif
89 #endif
90
91 void
92 mi_vector_hash(const void * __restrict key, size_t len, uint32_t seed,
93 uint32_t hashes[3])
94 {
95 static const uint32_t mask[4] = {
96 0x000000ff, 0x0000ffff, 0x00ffffff, 0xffffffff
97 };
98 uint32_t orig_len, a, b, c;
99 const uint8_t *k;
100
101 orig_len = (uint32_t)len;
102
103 a = b = FIXED_SEED;
104 c = seed;
105
106 if ((uintptr_t)key & 3) {
107 k = key;
108 while (len >= 12) {
109 a += le32dec(k);
110 b += le32dec(k + 4);
111 c += le32dec(k + 8);
112 mix(a, b, c);
113 k += 12;
114 len -= 12;
115 }
116 c += orig_len;
117
118 if (len > 8) {
119 switch (len) {
120 case 11:
121 c += (uint32_t)k[10] << 24;
122 /* FALLTHROUGH */
123 case 10:
124 c += (uint32_t)k[9] << 16;
125 /* FALLTHROUGH */
126 case 9:
127 c += (uint32_t)k[8] << 8;
128 /* FALLTHROUGH */
129 }
130 b += le32dec(k + 4);
131 a += le32dec(k);
132 } else if (len > 4) {
133 switch (len) {
134 case 8:
135 b += (uint32_t)k[7] << 24;
136 /* FALLTHROUGH */
137 case 7:
138 b += (uint32_t)k[6] << 16;
139 /* FALLTHROUGH */
140 case 6:
141 b += (uint32_t)k[5] << 8;
142 /* FALLTHROUGH */
143 case 5:
144 b += k[4];
145 /* FALLTHROUGH */
146 }
147 a += le32dec(k);
148 } else if (len) {
149 switch (len) {
150 case 4:
151 a += (uint32_t)k[3] << 24;
152 /* FALLTHROUGH */
153 case 3:
154 a += (uint32_t)k[2] << 16;
155 /* FALLTHROUGH */
156 case 2:
157 a += (uint32_t)k[1] << 8;
158 /* FALLTHROUGH */
159 case 1:
160 a += k[0];
161 /* FALLTHROUGH */
162 }
163 }
164 } else {
165 const uint32_t *key32 = key;
166 while (len >= 12) {
167 a += le32toh(key32[0]);
168 b += le32toh(key32[1]);
169 c += le32toh(key32[2]);
170 mix(a, b, c);
171 key32 += 3;
172 len -= 12;
173 }
174 c += orig_len;
175
176 if (len > 8) {
177 c += (le32toh(key32[2]) & mask[len - 9]) << 8;
178 b += le32toh(key32[1]);
179 a += le32toh(key32[0]);
180 } else if (len > 4) {
181 b += le32toh(key32[1]) & mask[len - 5];
182 a += le32toh(key32[0]);
183 } else if (len)
184 a += le32toh(key32[0]) & mask[len - 1];
185 }
186 mix(a, b, c);
187 hashes[0] = a;
188 hashes[1] = b;
189 hashes[2] = c;
190 }
191