Module Name: src
Committed By: joerg
Date: Mon Jul 20 17:03:38 UTC 2009
Modified Files:
src/distrib/sets/lists/base: md.amd64 md.sparc64 shl.mi
src/distrib/sets/lists/comp: mi
src/distrib/sets/lists/tests: mi
src/etc/mtree: NetBSD.dist
src/include: stdlib.h
src/lib/libc: shlib_version
src/lib/libc/stdlib: Makefile.inc
src/tests: Makefile
Added Files:
src/lib/libc/stdlib: mi_vector_hash.3 mi_vector_hash.c
src/tests/lib: Atffile Makefile
src/tests/lib/libc: Atffile Makefile
src/tests/lib/libc/stdlib: Atffile Makefile t_mi_vector_hash.c
Log Message:
Add a fast, platform independent hash function to libc.
The algorithm used is the Jenkins hash. The name (mi_vector_hash)
reflects the nature of the hash function.
Add glue for libc ATF tests and include a test case to make sure that
(mis)alignment and endianess are handled correctly.
Bump libc minor to 169.
To generate a diff of this commit:
cvs rdiff -u -r1.58 -r1.59 src/distrib/sets/lists/base/md.amd64
cvs rdiff -u -r1.52 -r1.53 src/distrib/sets/lists/base/md.sparc64
cvs rdiff -u -r1.480 -r1.481 src/distrib/sets/lists/base/shl.mi
cvs rdiff -u -r1.1283 -r1.1284 src/distrib/sets/lists/comp/mi
cvs rdiff -u -r1.43 -r1.44 src/distrib/sets/lists/tests/mi
cvs rdiff -u -r1.405 -r1.406 src/etc/mtree/NetBSD.dist
cvs rdiff -u -r1.88 -r1.89 src/include/stdlib.h
cvs rdiff -u -r1.212 -r1.213 src/lib/libc/shlib_version
cvs rdiff -u -r1.71 -r1.72 src/lib/libc/stdlib/Makefile.inc
cvs rdiff -u -r0 -r1.1 src/lib/libc/stdlib/mi_vector_hash.3 \
src/lib/libc/stdlib/mi_vector_hash.c
cvs rdiff -u -r1.15 -r1.16 src/tests/Makefile
cvs rdiff -u -r0 -r1.1 src/tests/lib/Atffile src/tests/lib/Makefile
cvs rdiff -u -r0 -r1.1 src/tests/lib/libc/Atffile src/tests/lib/libc/Makefile
cvs rdiff -u -r0 -r1.1 src/tests/lib/libc/stdlib/Atffile \
src/tests/lib/libc/stdlib/Makefile \
src/tests/lib/libc/stdlib/t_mi_vector_hash.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/distrib/sets/lists/base/md.amd64
diff -u src/distrib/sets/lists/base/md.amd64:1.58 src/distrib/sets/lists/base/md.amd64:1.59
--- src/distrib/sets/lists/base/md.amd64:1.58 Sun Jul 19 23:38:11 2009
+++ src/distrib/sets/lists/base/md.amd64 Mon Jul 20 17:03:36 2009
@@ -1,4 +1,4 @@
-# $NetBSD: md.amd64,v 1.58 2009/07/19 23:38:11 christos Exp $
+# $NetBSD: md.amd64,v 1.59 2009/07/20 17:03:36 joerg Exp $
./dev/lms0 base-obsolete obsolete
./dev/mms0 base-obsolete obsolete
./libexec/ld.elf_so-i386 base-sys-shlib compat,pic
@@ -64,7 +64,7 @@
./usr/lib/i386/libbz2.so.1 base-compat-shlib compat,pic
./usr/lib/i386/libbz2.so.1.1 base-compat-shlib compat,pic
./usr/lib/i386/libc.so.12 base-compat-shlib compat,pic
-./usr/lib/i386/libc.so.12.168 base-compat-shlib compat,pic
+./usr/lib/i386/libc.so.12.169 base-compat-shlib compat,pic
./usr/lib/i386/libcom_err.so.6 base-compat-shlib compat,pic,kerberos
./usr/lib/i386/libcom_err.so.6.0 base-compat-shlib compat,pic,kerberos
./usr/lib/i386/libcrypt.so.1 base-compat-shlib compat,pic
Index: src/distrib/sets/lists/base/md.sparc64
diff -u src/distrib/sets/lists/base/md.sparc64:1.52 src/distrib/sets/lists/base/md.sparc64:1.53
--- src/distrib/sets/lists/base/md.sparc64:1.52 Sun Jul 19 23:38:11 2009
+++ src/distrib/sets/lists/base/md.sparc64 Mon Jul 20 17:03:36 2009
@@ -1,4 +1,4 @@
-# $NetBSD: md.sparc64,v 1.52 2009/07/19 23:38:11 christos Exp $
+# $NetBSD: md.sparc64,v 1.53 2009/07/20 17:03:36 joerg Exp $
./libexec/ld.elf_so-sparc base-sysutil-bin compat,pic
./sbin/edlabel base-sysutil-root
./usr/bin/fdformat base-util-bin
@@ -63,7 +63,7 @@
./usr/lib/sparc/libbz2.so.1 base-compat-shlib compat,pic
./usr/lib/sparc/libbz2.so.1.1 base-compat-shlib compat,pic
./usr/lib/sparc/libc.so.12 base-compat-shlib compat,pic
-./usr/lib/sparc/libc.so.12.168 base-compat-shlib compat,pic
+./usr/lib/sparc/libc.so.12.169 base-compat-shlib compat,pic
./usr/lib/sparc/libcom_err.so.6 base-compat-shlib compat,pic
./usr/lib/sparc/libcom_err.so.6.0 base-compat-shlib compat,pic
./usr/lib/sparc/libcrypt.so.1 base-compat-shlib compat,pic
Index: src/distrib/sets/lists/base/shl.mi
diff -u src/distrib/sets/lists/base/shl.mi:1.480 src/distrib/sets/lists/base/shl.mi:1.481
--- src/distrib/sets/lists/base/shl.mi:1.480 Sun Jul 19 23:38:11 2009
+++ src/distrib/sets/lists/base/shl.mi Mon Jul 20 17:03:36 2009
@@ -1,4 +1,4 @@
-# $NetBSD: shl.mi,v 1.480 2009/07/19 23:38:11 christos Exp $
+# $NetBSD: shl.mi,v 1.481 2009/07/20 17:03:36 joerg Exp $
#
# Note: Don't delete entries from here - mark them as "obsolete" instead,
# unless otherwise stated below.
@@ -13,7 +13,7 @@
#
# Note: libtermcap and libtermlib are hardlinked and share the same version.
#
-./lib/libc.so.12.168 base-sys-shlib dynamicroot
+./lib/libc.so.12.169 base-sys-shlib dynamicroot
./lib/libcrypt.so.1.0 base-sys-shlib dynamicroot
./lib/libcrypto.so.5.2 base-crypto-shlib crypto,dynamicroot
./lib/libdevmapper.so.1.0 base-lvm-shlib lvm,dynamicroot
@@ -60,7 +60,7 @@
./usr/lib/libbluetooth.so.4.1 base-sys-shlib
./usr/lib/libbsdmalloc.so.0.0 base-sys-shlib
./usr/lib/libbz2.so.1.1 base-sys-shlib
-./usr/lib/libc.so.12.168 base-sys-shlib
+./usr/lib/libc.so.12.169 base-sys-shlib
./usr/lib/libcom_err.so.6.0 base-krb5-shlib kerberos
./usr/lib/libcrypt.so.1.0 base-sys-shlib
./usr/lib/libcrypto.so.5.1 base-crypto-shlib crypto
Index: src/distrib/sets/lists/comp/mi
diff -u src/distrib/sets/lists/comp/mi:1.1283 src/distrib/sets/lists/comp/mi:1.1284
--- src/distrib/sets/lists/comp/mi:1.1283 Sun Jul 19 23:38:11 2009
+++ src/distrib/sets/lists/comp/mi Mon Jul 20 17:03:36 2009
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.1283 2009/07/19 23:38:11 christos Exp $
+# $NetBSD: mi,v 1.1284 2009/07/20 17:03:36 joerg Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
#
@@ -6734,6 +6734,7 @@
./usr/share/man/cat3/menus.0 comp-c-catman .cat
./usr/share/man/cat3/mergesort.0 comp-c-catman .cat
./usr/share/man/cat3/meta.0 comp-c-catman .cat
+./usr/share/man/cat3/mi_vector_hash.0 comp-c-catman .cat
./usr/share/man/cat3/mkdtemp.0 comp-c-catman .cat
./usr/share/man/cat3/mkstemp.0 comp-c-catman .cat
./usr/share/man/cat3/mktemp.0 comp-c-catman .cat
@@ -12193,6 +12194,7 @@
./usr/share/man/html3/menus.html comp-c-htmlman html
./usr/share/man/html3/mergesort.html comp-c-htmlman html
./usr/share/man/html3/meta.html comp-c-htmlman html
+./usr/share/man/html3/mi_vector_hash.html comp-c-htmlman html
./usr/share/man/html3/mkdtemp.html comp-c-htmlman html
./usr/share/man/html3/mkstemp.html comp-c-htmlman html
./usr/share/man/html3/mktemp.html comp-c-htmlman html
@@ -17640,6 +17642,7 @@
./usr/share/man/man3/menus.3 comp-c-man .man
./usr/share/man/man3/mergesort.3 comp-c-man .man
./usr/share/man/man3/meta.3 comp-c-man .man
+./usr/share/man/man3/mi_vector_hash.3 comp-c-man .man
./usr/share/man/man3/mkdtemp.3 comp-c-man .man
./usr/share/man/man3/mkstemp.3 comp-c-man .man
./usr/share/man/man3/mktemp.3 comp-c-man .man
Index: src/distrib/sets/lists/tests/mi
diff -u src/distrib/sets/lists/tests/mi:1.43 src/distrib/sets/lists/tests/mi:1.44
--- src/distrib/sets/lists/tests/mi:1.43 Sat May 2 20:08:52 2009
+++ src/distrib/sets/lists/tests/mi Mon Jul 20 17:03:36 2009
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.43 2009/05/02 20:08:52 pooka Exp $
+# $NetBSD: mi,v 1.44 2009/07/20 17:03:36 joerg Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
#
@@ -132,6 +132,10 @@
./usr/libdata/debug/usr/tests/kernel/t_time.debug tests-kernel-tests debug
./usr/libdata/debug/usr/tests/kernel/t_ucontext.debug tests-kernel-tests debug
./usr/libdata/debug/usr/tests/kernel/t_writev.debug tests-kernel-tests debug
+./usr/libdata/debug/usr/tests/lib tests-lib-debug
+./usr/libdata/debug/usr/tests/lib/libc tests-lib-debug
+./usr/libdata/debug/usr/tests/lib/libc/stdlib tests-lib-debug
+./usr/libdata/debug/usr/tests/lib/libc/stdlib/t_mi_vector_hash.debug tests-lib-debug debug
./usr/libdata/debug/usr/tests/modules tests-sys-debug
./usr/libdata/debug/usr/tests/modules/t_modctl.debug tests-sys-debug debug
./usr/libdata/debug/usr/tests/net tests-net-debug
@@ -836,6 +840,13 @@
./usr/tests/kernel/t_ucontext tests-kernel-tests
./usr/tests/kernel/t_umount tests-kernel-tests
./usr/tests/kernel/t_writev tests-kernel-tests
+./usr/tests/lib tests-lib-tests
+./usr/tests/lib/Atffile tests-lib-tests
+./usr/tests/lib/libc tests-lib-tests
+./usr/tests/lib/libc/Atffile tests-lib-tests
+./usr/tests/lib/libc/stdlib tests-lib-tests
+./usr/tests/lib/libc/stdlib/Atffile tests-lib-tests
+./usr/tests/lib/libc/stdlib/t_mi_vector_hash tests-lib-tests
./usr/tests/modules tests-sys-tests
./usr/tests/modules/Atffile tests-sys-tests
./usr/tests/net tests-net-tests
Index: src/etc/mtree/NetBSD.dist
diff -u src/etc/mtree/NetBSD.dist:1.405 src/etc/mtree/NetBSD.dist:1.406
--- src/etc/mtree/NetBSD.dist:1.405 Thu Jun 11 05:40:56 2009
+++ src/etc/mtree/NetBSD.dist Mon Jul 20 17:03:37 2009
@@ -1,4 +1,4 @@
-# $NetBSD: NetBSD.dist,v 1.405 2009/06/11 05:40:56 mrg Exp $
+# $NetBSD: NetBSD.dist,v 1.406 2009/07/20 17:03:37 joerg Exp $
# @(#)4.4BSD.dist 8.1 (Berkeley) 6/13/93
# Do not customize this file as it may be overwritten on upgrades.
@@ -550,6 +550,9 @@
./usr/libdata/debug/usr/tests/kernel/kqueue
./usr/libdata/debug/usr/tests/kernel/kqueue/read
./usr/libdata/debug/usr/tests/kernel/kqueue/write
+./usr/libdata/debug/usr/tests/lib
+./usr/libdata/debug/usr/tests/lib/libc
+./usr/libdata/debug/usr/tests/lib/libc/stdlib
./usr/libdata/debug/usr/tests/modules
./usr/libdata/debug/usr/tests/net
./usr/libdata/debug/usr/tests/net/sys
@@ -1431,6 +1434,9 @@
./usr/tests/kernel/kqueue
./usr/tests/kernel/kqueue/read
./usr/tests/kernel/kqueue/write
+./usr/tests/lib
+./usr/tests/lib/libc
+./usr/tests/lib/libc/stdlib
./usr/tests/modules
./usr/tests/net
./usr/tests/net/sys
Index: src/include/stdlib.h
diff -u src/include/stdlib.h:1.88 src/include/stdlib.h:1.89
--- src/include/stdlib.h:1.88 Tue Jan 20 20:08:12 2009
+++ src/include/stdlib.h Mon Jul 20 17:03:37 2009
@@ -1,4 +1,4 @@
-/* $NetBSD: stdlib.h,v 1.88 2009/01/20 20:08:12 drochner Exp $ */
+/* $NetBSD: stdlib.h,v 1.89 2009/07/20 17:03:37 joerg Exp $ */
/*-
* Copyright (c) 1990, 1993
@@ -295,6 +295,9 @@
int sradixsort(const unsigned char **, int, const unsigned char *,
unsigned);
+void mi_vector_hash(const void * __restrict, size_t, uint32_t,
+ uint32_t[3]);
+
void setproctitle(const char *, ...)
__attribute__((__format__(__printf__, 1, 2)));
const char *getprogname(void) __attribute__((const));
Index: src/lib/libc/shlib_version
diff -u src/lib/libc/shlib_version:1.212 src/lib/libc/shlib_version:1.213
--- src/lib/libc/shlib_version:1.212 Tue May 26 08:04:11 2009
+++ src/lib/libc/shlib_version Mon Jul 20 17:03:37 2009
@@ -1,4 +1,4 @@
-# $NetBSD: shlib_version,v 1.212 2009/05/26 08:04:11 joerg Exp $
+# $NetBSD: shlib_version,v 1.213 2009/07/20 17:03:37 joerg Exp $
# Remember to update distrib/sets/lists/base/shl.* when changing
#
# things we wish to do on next major version bump:
@@ -35,4 +35,4 @@
# it's insufficient bitwidth to implement all ctype class.
# see isblank's comment in ctype.h.
major=12
-minor=168
+minor=169
Index: src/lib/libc/stdlib/Makefile.inc
diff -u src/lib/libc/stdlib/Makefile.inc:1.71 src/lib/libc/stdlib/Makefile.inc:1.72
--- src/lib/libc/stdlib/Makefile.inc:1.71 Sun Oct 26 07:43:07 2008
+++ src/lib/libc/stdlib/Makefile.inc Mon Jul 20 17:03:37 2009
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile.inc,v 1.71 2008/10/26 07:43:07 mrg Exp $
+# $NetBSD: Makefile.inc,v 1.72 2009/07/20 17:03:37 joerg Exp $
# from: @(#)Makefile.inc 8.3 (Berkeley) 2/4/95
# stdlib sources
@@ -9,7 +9,7 @@
bsearch.c drand48.c exit.c \
getenv.c getopt.c getopt_long.c getsubopt.c \
hcreate.c heapsort.c imaxdiv.c insque.c jrand48.c l64a.c lldiv.c \
- lcong48.c lrand48.c lsearch.c merge.c mrand48.c \
+ lcong48.c lrand48.c lsearch.c merge.c mi_vector_hash.c mrand48.c \
nrand48.c putenv.c qabs.c qdiv.c qsort.c posix_openpt.c pty.c \
radixsort.c rand.c rand_r.c random.c remque.c \
seed48.c setenv.c srand48.c strsuftoll.c \
@@ -42,7 +42,7 @@
hcreate.3 \
imaxabs.3 imaxdiv.3 insque.3 \
labs.3 ldiv.3 llabs.3 lldiv.3 lsearch.3 \
- malloc.3 memory.3 \
+ malloc.3 memory.3 mi_vector_hash.3 \
posix_memalign.3 posix_openpt.3 ptsname.3 \
qabs.3 qdiv.3 qsort.3 \
radixsort.3 rand48.3 rand.3 random.3 \
Index: src/tests/Makefile
diff -u src/tests/Makefile:1.15 src/tests/Makefile:1.16
--- src/tests/Makefile:1.15 Sat May 2 16:02:18 2009
+++ src/tests/Makefile Mon Jul 20 17:03:37 2009
@@ -1,8 +1,8 @@
-# $NetBSD: Makefile,v 1.15 2009/05/02 16:02:18 pooka Exp $
+# $NetBSD: Makefile,v 1.16 2009/07/20 17:03:37 joerg Exp $
.include <bsd.own.mk>
-SUBDIR= crypto fs games ipf kernel net rump syscall util
+SUBDIR= crypto fs games ipf kernel lib net rump syscall util
.if ${MACHINE} != "evbppc"
SUBDIR+= modules
Added files:
Index: src/lib/libc/stdlib/mi_vector_hash.3
diff -u /dev/null src/lib/libc/stdlib/mi_vector_hash.3:1.1
--- /dev/null Mon Jul 20 17:03:38 2009
+++ src/lib/libc/stdlib/mi_vector_hash.3 Mon Jul 20 17:03:37 2009
@@ -0,0 +1,60 @@
+.\" $NetBSD: mi_vector_hash.3,v 1.1 2009/07/20 17:03:37 joerg Exp $
+.\"
+.\" Copyright (c) 2009 The NetBSD Foundation, Inc.
+.\" All rights reserved.
+.\"
+.\" This code is derived from software contributed to The NetBSD Foundation
+.\" by Joerg Sonnenberger.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\" notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\" notice, this list of conditions and the following disclaimer in the
+.\" documentation and/or other materials provided with the distribution.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+.\" POSSIBILITY OF SUCH DAMAGE.
+.\"
+.Dd July 13, 2009
+.Dt MI_VECTOR_HASH 3
+.Os
+.Sh NAME
+.Nm mi_vector_hash
+.Nd fast 32bit hash functions
+.Sh LIBRARY
+.Lb libc
+.Sh SYNOPSIS
+.In stdlib.h
+.Ft void
+.Fn mi_vector_hash "const void * restrict key" "size_t len" \
+ "uint32_t seed" "uint32_t hashes[3]"
+.Sh DESCRIPTION
+The
+.Nm
+function computes three 32-bit hash values of the memory area starting at
+.Fa key
+with length
+.Fa len .
+.Pp
+The output is identical on all architectures and only depends on
+.Fa key
+and
+.Fa seed .
+.Sh IMPLEMENTATION NOTES
+An optimised code path is used if
+.Fa key
+is aligned on a 32-bit boundary.
+.Sh AUTHORS
+The hash function has been created by Bob Jenkins.
Index: src/lib/libc/stdlib/mi_vector_hash.c
diff -u /dev/null src/lib/libc/stdlib/mi_vector_hash.c:1.1
--- /dev/null Mon Jul 20 17:03:38 2009
+++ src/lib/libc/stdlib/mi_vector_hash.c Mon Jul 20 17:03:37 2009
@@ -0,0 +1,161 @@
+/* $NetBSD: mi_vector_hash.c,v 1.1 2009/07/20 17:03:37 joerg Exp $ */
+/*-
+ * Copyright (c) 2009 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Joerg Sonnenberger.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * See http://burtleburtle.net/bob/hash/doobs.html for the full description
+ * and the original version of the code. This version differs by exposing
+ * the full internal state and avoiding byte operations in the inner loop
+ * if the key is aligned correctly.
+ */
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: mi_vector_hash.c,v 1.1 2009/07/20 17:03:37 joerg Exp $");
+
+#include <sys/endian.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+#define mix(a, b, c) do { \
+ a -= b; a -= c; a ^= (c >> 13); \
+ b -= c; b -= a; b ^= (a << 8); \
+ c -= a; c -= b; c ^= (b >> 13); \
+ a -= b; a -= c; a ^= (c >> 12); \
+ b -= c; b -= a; b ^= (a << 16); \
+ c -= a; c -= b; c ^= (b >> 5); \
+ a -= b; a -= c; a ^= (c >> 3); \
+ b -= c; b -= a; b ^= (a << 10); \
+ c -= a; c -= b; c ^= (b >> 15); \
+} while (/* CONSTCOND */0)
+
+#define FIXED_SEED 0x9e3779b9 /* Golden ratio, arbitrary constant */
+
+void
+mi_vector_hash(const void * __restrict key, size_t len, uint32_t seed,
+ uint32_t hashes[3])
+{
+ static const uint32_t mask[4] = {
+ 0x000000ff, 0x0000ffff, 0x00ffffff, 0xffffffff
+ };
+ uint32_t orig_len, a, b, c;
+ const uint8_t *k;
+
+ orig_len = (uint32_t)len;
+
+ a = b = FIXED_SEED;
+ c = seed;
+
+ if ((uintptr_t)key & 3) {
+ k = key;
+ while (len >= 12) {
+ a += le32dec(k);
+ b += le32dec(k + 4);
+ c += le32dec(k + 8);
+ mix(a, b, c);
+ k += 12;
+ len -= 12;
+ }
+ c += orig_len;
+
+ if (len > 8) {
+ switch (len) {
+ case 11:
+ c += (uint32_t)k[10] << 24;
+ /* FALLTHROUGH */
+ case 10:
+ c += (uint32_t)k[9] << 16;
+ /* FALLTHROUGH */
+ case 9:
+ c += (uint32_t)k[8] << 8;
+ /* FALLTHROUGH */
+ }
+ b += le32dec(k + 4);
+ a += le32dec(k);
+ } else if (len > 4) {
+ switch (len) {
+ case 8:
+ b += (uint32_t)k[7] << 24;
+ /* FALLTHROUGH */
+ case 7:
+ b += (uint32_t)k[6] << 16;
+ /* FALLTHROUGH */
+ case 6:
+ b += (uint32_t)k[5] << 8;
+ /* FALLTHROUGH */
+ case 5:
+ b += k[4];
+ /* FALLTHROUGH */
+ }
+ a += le32dec(k);
+ } else if (len) {
+ switch (len) {
+ case 4:
+ a += (uint32_t)k[3] << 24;
+ /* FALLTHROUGH */
+ case 3:
+ a += (uint32_t)k[2] << 16;
+ /* FALLTHROUGH */
+ case 2:
+ a += (uint32_t)k[1] << 8;
+ /* FALLTHROUGH */
+ case 1:
+ a += k[0];
+ /* FALLTHROUGH */
+ }
+ }
+ } else {
+ const uint32_t *key32 = key;
+ while (len >= 12) {
+ a += le32toh(key32[0]);
+ b += le32toh(key32[1]);
+ c += le32toh(key32[2]);
+ mix(a, b, c);
+ key32 += 3;
+ len -= 12;
+ }
+ c += orig_len;
+
+ if (len > 8) {
+ c += (le32toh(key32[2]) & mask[len - 9]) << 8;
+ b += le32toh(key32[1]);
+ a += le32toh(key32[0]);
+ } else if (len > 4) {
+ b += le32toh(key32[1]) & mask[len - 5];
+ a += le32toh(key32[0]);
+ } else if (len)
+ a += le32toh(key32[0]) & mask[len - 1];
+ }
+ mix(a, b, c);
+ hashes[0] = a;
+ hashes[1] = b;
+ hashes[2] = c;
+}
Index: src/tests/lib/Atffile
diff -u /dev/null src/tests/lib/Atffile:1.1
--- /dev/null Mon Jul 20 17:03:38 2009
+++ src/tests/lib/Atffile Mon Jul 20 17:03:38 2009
@@ -0,0 +1,6 @@
+Content-Type: application/X-atf-atffile; version="1"
+X-NetBSD-Id: "$NetBSD: Atffile,v 1.1 2009/07/20 17:03:38 joerg Exp $"
+
+prop: test-suite = "NetBSD"
+
+tp-glob: *
Index: src/tests/lib/Makefile
diff -u /dev/null src/tests/lib/Makefile:1.1
--- /dev/null Mon Jul 20 17:03:38 2009
+++ src/tests/lib/Makefile Mon Jul 20 17:03:38 2009
@@ -0,0 +1,10 @@
+# $NetBSD: Makefile,v 1.1 2009/07/20 17:03:38 joerg Exp $
+
+.include <bsd.own.mk>
+
+SUBDIR= libc
+
+TESTSDIR= ${TESTSBASE}/lib
+
+.include <bsd.test.mk>
+.include <bsd.subdir.mk>
Index: src/tests/lib/libc/Atffile
diff -u /dev/null src/tests/lib/libc/Atffile:1.1
--- /dev/null Mon Jul 20 17:03:38 2009
+++ src/tests/lib/libc/Atffile Mon Jul 20 17:03:38 2009
@@ -0,0 +1,5 @@
+Content-Type: application/X-atf-atffile; version="1"
+
+prop: test-suite = "NetBSD"
+
+tp: stdlib
Index: src/tests/lib/libc/Makefile
diff -u /dev/null src/tests/lib/libc/Makefile:1.1
--- /dev/null Mon Jul 20 17:03:38 2009
+++ src/tests/lib/libc/Makefile Mon Jul 20 17:03:38 2009
@@ -0,0 +1,10 @@
+# $NetBSD: Makefile,v 1.1 2009/07/20 17:03:38 joerg Exp $
+
+.include <bsd.own.mk>
+
+SUBDIR+= stdlib
+
+TESTSDIR= ${TESTSBASE}/lib/libc
+
+.include <bsd.subdir.mk>
+.include <bsd.test.mk>
Index: src/tests/lib/libc/stdlib/Atffile
diff -u /dev/null src/tests/lib/libc/stdlib/Atffile:1.1
--- /dev/null Mon Jul 20 17:03:38 2009
+++ src/tests/lib/libc/stdlib/Atffile Mon Jul 20 17:03:38 2009
@@ -0,0 +1,6 @@
+Content-Type: application/X-atf-atffile; version="1"
+X-NetBSD-Id: "$NetBSD: Atffile,v 1.1 2009/07/20 17:03:38 joerg Exp $"
+
+prop: test-suite = "NetBSD"
+
+tp: t_mi_vector_hash
Index: src/tests/lib/libc/stdlib/Makefile
diff -u /dev/null src/tests/lib/libc/stdlib/Makefile:1.1
--- /dev/null Mon Jul 20 17:03:38 2009
+++ src/tests/lib/libc/stdlib/Makefile Mon Jul 20 17:03:38 2009
@@ -0,0 +1,9 @@
+# $NetBSD: Makefile,v 1.1 2009/07/20 17:03:38 joerg Exp $
+
+.include <bsd.own.mk>
+
+TESTSDIR= ${TESTSBASE}/lib/libc/stdlib
+
+TESTS_C+= t_mi_vector_hash
+
+.include <bsd.test.mk>
Index: src/tests/lib/libc/stdlib/t_mi_vector_hash.c
diff -u /dev/null src/tests/lib/libc/stdlib/t_mi_vector_hash.c:1.1
--- /dev/null Mon Jul 20 17:03:38 2009
+++ src/tests/lib/libc/stdlib/t_mi_vector_hash.c Mon Jul 20 17:03:38 2009
@@ -0,0 +1,93 @@
+/* $NetBSD: t_mi_vector_hash.c,v 1.1 2009/07/20 17:03:38 joerg Exp $ */
+/*-
+ * Copyright (c) 2009 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Joerg Sonnenberger.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <atf-c.h>
+#include <stdlib.h>
+#include <string.h>
+
+ATF_TC(t_mi_vector_hash);
+
+ATF_TC_HEAD(t_mi_vector_hash, tc)
+{
+ atf_tc_set_md_var(tc, "descr",
+ "Test mi_vector_hash_vector_hash for consistent results");
+}
+
+static const struct testvector {
+ const char *vector;
+ uint32_t hashes[3];
+} testv[] = {
+ { "hello, world", { 0xd38f7f21, 0xbf6be9ab, 0x37a0e989 } },
+ { "", { 0x9b2ec03d, 0xdb2b69ae, 0xbd49d10d } },
+ { "a", { 0x9454baa3, 0xb711c708, 0x29eec818 } },
+ { "ab", { 0x9a5dca90, 0xdd212644, 0x9879ac41 } },
+ { "abc", { 0x0b91c470, 0x4770cdf5, 0x251e4793 } },
+ { "abcd", { 0x5f128df3, 0xf5a667a6, 0x5ae61fa5 } },
+ { "abcde", { 0x4cbae281, 0x799c0ed5, 0x03a96866 } },
+ { "abcdef", { 0x507a54c8, 0xb6bd06f4, 0xde922732 } },
+ { "abcdefg", { 0xae2bca5d, 0x61e960ef, 0xb9e6762c } },
+ { "abcdefgh", { 0xd1021264, 0x87f6988f, 0x053f775e } },
+ { "abcdefghi", { 0xe380defc, 0xfc35a811, 0x3a7b0a5f } },
+ { "abcdefghij", { 0x9a504408, 0x70d2e89d, 0xc9cac242 } },
+ { "abcdefghijk", { 0x376117d0, 0x89f434d4, 0xe52b8e4c } },
+ { "abcdefghijkl", { 0x92253599, 0x7b6ff99e, 0x0b1b3ea5 } },
+ { "abcdefghijklm", { 0x92ee6a52, 0x55587d47, 0x3122b031 } },
+ { "abcdefghijklmn", { 0x827baf08, 0x1d0ada73, 0xfec330e0 } },
+ { "abcdefghijklmno", { 0x06ab787d, 0xc1ad17c2, 0x11dccf31 } },
+ { "abcdefghijklmnop", { 0x2cf18103, 0x638c9268, 0xfa1ecf51 } },
+};
+
+ATF_TC_BODY(t_mi_vector_hash, tc)
+{
+ size_t i, j, len;
+ uint32_t hashes[3];
+ char buf[256];
+
+ for (j = 0; j < 8; ++j) {
+ for (i = 0; i < sizeof(testv) / sizeof(testv[0]); ++i) {
+ len = strlen(testv[i].vector);
+ strcpy(buf + j, testv[i].vector);
+ mi_vector_hash(buf + j, len, 0, hashes);
+ ATF_CHECK_EQ(hashes[0], testv[i].hashes[0]);
+ ATF_CHECK_EQ(hashes[1], testv[i].hashes[1]);
+ ATF_CHECK_EQ(hashes[2], testv[i].hashes[2]);
+ }
+ }
+}
+
+ATF_TP_ADD_TCS(tp)
+{
+ ATF_TP_ADD_TC(tp, t_mi_vector_hash);
+
+ return atf_no_error();
+}
