Home | History | Annotate | Line # | Download | only in stdlib 
      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