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