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 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