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 #include <sys/endian.h>
50 #endif
51
52 #if defined(_KERNEL) || defined(_STANDALONE)
53 #include <sys/types.h>
54 #include <sys/systm.h>
55 #include <lib/libkern/libkern.h>
56 #else
57 #include "namespace.h"
58
59 #include <stdint.h>
60 #include <stdlib.h>
61 #endif
62
63 #define mix(a, b, c) do { \
64 a -= b; a -= c; a ^= (c >> 13); \
65 b -= c; b -= a; b ^= (a << 8); \
66 c -= a; c -= b; c ^= (b >> 13); \
67 a -= b; a -= c; a ^= (c >> 12); \
68 b -= c; b -= a; b ^= (a << 16); \
69 c -= a; c -= b; c ^= (b >> 5); \
70 a -= b; a -= c; a ^= (c >> 3); \
71 b -= c; b -= a; b ^= (a << 10); \
72 c -= a; c -= b; c ^= (b >> 15); \
73 } while (/* CONSTCOND */0)
74
75 #define FIXED_SEED 0x9e3779b9 /* Golden ratio, arbitrary constant */
76
77 #if !defined(_KERNEL) && !defined(_STANDALONE)
78 #ifdef __weak_alias
__weak_alias(mi_vector_hash,_mi_vector_hash)79 __weak_alias(mi_vector_hash, _mi_vector_hash)
80 #endif
81 #endif
82
83 void
84 mi_vector_hash(const void * __restrict key, size_t len, uint32_t seed,
85 uint32_t hashes[3])
86 {
87 static const uint32_t mask[4] = {
88 0x000000ff, 0x0000ffff, 0x00ffffff, 0xffffffff
89 };
90 uint32_t orig_len, a, b, c;
91 const uint8_t *k;
92
93 orig_len = (uint32_t)len;
94
95 a = b = FIXED_SEED;
96 c = seed;
97
98 if ((uintptr_t)key & 3) {
99 k = key;
100 while (len >= 12) {
101 a += le32dec(k);
102 b += le32dec(k + 4);
103 c += le32dec(k + 8);
104 mix(a, b, c);
105 k += 12;
106 len -= 12;
107 }
108 c += orig_len;
109
110 if (len > 8) {
111 switch (len) {
112 case 11:
113 c += (uint32_t)k[10] << 24;
114 /* FALLTHROUGH */
115 case 10:
116 c += (uint32_t)k[9] << 16;
117 /* FALLTHROUGH */
118 case 9:
119 c += (uint32_t)k[8] << 8;
120 /* FALLTHROUGH */
121 }
122 b += le32dec(k + 4);
123 a += le32dec(k);
124 } else if (len > 4) {
125 switch (len) {
126 case 8:
127 b += (uint32_t)k[7] << 24;
128 /* FALLTHROUGH */
129 case 7:
130 b += (uint32_t)k[6] << 16;
131 /* FALLTHROUGH */
132 case 6:
133 b += (uint32_t)k[5] << 8;
134 /* FALLTHROUGH */
135 case 5:
136 b += k[4];
137 /* FALLTHROUGH */
138 }
139 a += le32dec(k);
140 } else if (len) {
141 switch (len) {
142 case 4:
143 a += (uint32_t)k[3] << 24;
144 /* FALLTHROUGH */
145 case 3:
146 a += (uint32_t)k[2] << 16;
147 /* FALLTHROUGH */
148 case 2:
149 a += (uint32_t)k[1] << 8;
150 /* FALLTHROUGH */
151 case 1:
152 a += k[0];
153 /* FALLTHROUGH */
154 }
155 }
156 } else {
157 const uint32_t *key32 = key;
158 while (len >= 12) {
159 a += le32toh(key32[0]);
160 b += le32toh(key32[1]);
161 c += le32toh(key32[2]);
162 mix(a, b, c);
163 key32 += 3;
164 len -= 12;
165 }
166 c += orig_len;
167
168 if (len > 8) {
169 c += (le32toh(key32[2]) & mask[len - 9]) << 8;
170 b += le32toh(key32[1]);
171 a += le32toh(key32[0]);
172 } else if (len > 4) {
173 b += le32toh(key32[1]) & mask[len - 5];
174 a += le32toh(key32[0]);
175 } else if (len)
176 a += le32toh(key32[0]) & mask[len - 1];
177 }
178 mix(a, b, c);
179 hashes[0] = a;
180 hashes[1] = b;
181 hashes[2] = c;
182 }
183