tech-userlevel archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: Perfect hash function generator
On Mon, Jul 13, 2009 at 09:29:38PM +0200, Joerg Sonnenberger wrote:
> I'd like to fix this issue in two steps. First, I'd like the integrate
> the Jenkins hash function into libc.
Updated patch for this part is attached. Much faster when using -O2 (and
not -O3) by not expecting the compiler to be smart. Also includes a
regression test and a some man page additions. Goes into stdlib.h now.
Joerg
Index: distrib/sets/lists/base/md.amd64
===================================================================
RCS file: /home/joerg/repo/netbsd/src/distrib/sets/lists/base/md.amd64,v
retrieving revision 1.57
diff -u -p -r1.57 md.amd64
--- distrib/sets/lists/base/md.amd64 8 Jul 2009 21:23:52 -0000 1.57
+++ distrib/sets/lists/base/md.amd64 14 Jul 2009 11:36:14 -0000
@@ -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: distrib/sets/lists/base/md.sparc64
===================================================================
RCS file: /home/joerg/repo/netbsd/src/distrib/sets/lists/base/md.sparc64,v
retrieving revision 1.51
diff -u -p -r1.51 md.sparc64
--- distrib/sets/lists/base/md.sparc64 8 Jul 2009 21:23:52 -0000 1.51
+++ distrib/sets/lists/base/md.sparc64 14 Jul 2009 11:36:18 -0000
@@ -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: distrib/sets/lists/base/shl.mi
===================================================================
RCS file: /home/joerg/repo/netbsd/src/distrib/sets/lists/base/shl.mi,v
retrieving revision 1.478
diff -u -p -r1.478 shl.mi
--- distrib/sets/lists/base/shl.mi 8 Jul 2009 21:23:52 -0000 1.478
+++ distrib/sets/lists/base/shl.mi 14 Jul 2009 11:36:28 -0000
@@ -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.1 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: distrib/sets/lists/comp/mi
===================================================================
RCS file: /home/joerg/repo/netbsd/src/distrib/sets/lists/comp/mi,v
retrieving revision 1.1279
diff -u -p -r1.1279 mi
--- distrib/sets/lists/comp/mi 14 Jul 2009 08:01:02 -0000 1.1279
+++ distrib/sets/lists/comp/mi 14 Jul 2009 16:50:56 -0000
@@ -5872,6 +5872,8 @@
./usr/share/man/cat3/j0f.0 comp-c-catman .cat
./usr/share/man/cat3/j1.0 comp-c-catman .cat
./usr/share/man/cat3/j1f.0 comp-c-catman .cat
+./usr/share/man/cat3/jenkins_hash.0 comp-c-catman .cat
+./usr/share/man/cat3/jenkins_vector_hash.0 comp-c-catman .cat
./usr/share/man/cat3/jn.0 comp-c-catman .cat
./usr/share/man/cat3/jnf.0 comp-c-catman .cat
./usr/share/man/cat3/jrand48.0 comp-c-catman .cat
@@ -11366,6 +11368,8 @@
./usr/share/man/html3/j0f.html comp-c-htmlman html
./usr/share/man/html3/j1.html comp-c-htmlman html
./usr/share/man/html3/j1f.html comp-c-htmlman html
+./usr/share/man/html3/jenkins_hash.html comp-c-htmlman
html
+./usr/share/man/html3/jenkins_vector_hash.html comp-c-htmlman html
./usr/share/man/html3/jn.html comp-c-htmlman html
./usr/share/man/html3/jnf.html comp-c-htmlman html
./usr/share/man/html3/jrand48.html comp-c-htmlman html
@@ -16778,6 +16782,8 @@
./usr/share/man/man3/j0f.3 comp-c-man .man
./usr/share/man/man3/j1.3 comp-c-man .man
./usr/share/man/man3/j1f.3 comp-c-man .man
+./usr/share/man/man3/jenkins_hash.3 comp-c-man .man
+./usr/share/man/man3/jenkins_vector_hash.3 comp-c-man .man
./usr/share/man/man3/jn.3 comp-c-man .man
./usr/share/man/man3/jnf.3 comp-c-man .man
./usr/share/man/man3/jrand48.3 comp-c-man .man
Index: distrib/sets/lists/tests/mi
===================================================================
RCS file: /home/joerg/repo/netbsd/src/distrib/sets/lists/tests/mi,v
retrieving revision 1.43
diff -u -p -r1.43 mi
--- distrib/sets/lists/tests/mi 2 May 2009 20:08:52 -0000 1.43
+++ distrib/sets/lists/tests/mi 16 Jul 2009 19:21:47 -0000
@@ -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_jenkins.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_jenkins tests-lib-tests
./usr/tests/modules tests-sys-tests
./usr/tests/modules/Atffile tests-sys-tests
./usr/tests/net tests-net-tests
Index: etc/mtree/NetBSD.dist
===================================================================
RCS file: /home/joerg/repo/netbsd/src/etc/mtree/NetBSD.dist,v
retrieving revision 1.405
diff -u -p -r1.405 NetBSD.dist
--- etc/mtree/NetBSD.dist 11 Jun 2009 05:40:56 -0000 1.405
+++ etc/mtree/NetBSD.dist 16 Jul 2009 18:33:16 -0000
@@ -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: include/stdlib.h
===================================================================
RCS file: /home/joerg/repo/netbsd/src/include/stdlib.h,v
retrieving revision 1.88
diff -u -p -r1.88 stdlib.h
--- include/stdlib.h 20 Jan 2009 20:08:12 -0000 1.88
+++ include/stdlib.h 14 Jul 2009 11:32:07 -0000
@@ -295,6 +295,10 @@ int radixsort(const unsigned char **, i
int sradixsort(const unsigned char **, int, const unsigned char *,
unsigned);
+void jenkins_vector_hash(const void * __restrict, size_t, uint32_t,
+ uint32_t[3]);
+uint32_t jenkins_hash(const void * __restrict, size_t, uint32_t);
+
void setproctitle(const char *, ...)
__attribute__((__format__(__printf__, 1, 2)));
const char *getprogname(void) __attribute__((const));
Index: lib/libc/shlib_version
===================================================================
RCS file: /home/joerg/repo/netbsd/src/lib/libc/shlib_version,v
retrieving revision 1.212
diff -u -p -r1.212 shlib_version
--- lib/libc/shlib_version 26 May 2009 08:04:11 -0000 1.212
+++ lib/libc/shlib_version 14 Jul 2009 11:36:03 -0000
@@ -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: lib/libc/stdlib/Makefile.inc
===================================================================
RCS file: /home/joerg/repo/netbsd/src/lib/libc/stdlib/Makefile.inc,v
retrieving revision 1.71
diff -u -p -r1.71 Makefile.inc
--- lib/libc/stdlib/Makefile.inc 26 Oct 2008 07:43:07 -0000 1.71
+++ lib/libc/stdlib/Makefile.inc 14 Jul 2009 11:33:45 -0000
@@ -8,7 +8,8 @@ SRCS+= _rand48.c \
a64l.c abort.c atexit.c atof.c atoi.c atol.c atoll.c \
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 \
+ hcreate.c heapsort.c imaxdiv.c insque.c jenkins_hash.c jrand48.c \
+ l64a.c lldiv.c \
lcong48.c lrand48.c lsearch.c merge.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 \
@@ -40,7 +41,7 @@ MAN+= a64l.3 abort.3 abs.3 alloca.3 atex
exit.3 \
getenv.3 getopt.3 getopt_long.3 getsubopt.3 grantpt.3 \
hcreate.3 \
- imaxabs.3 imaxdiv.3 insque.3 \
+ imaxabs.3 imaxdiv.3 insque.3 jenkins_hash.3 \
labs.3 ldiv.3 llabs.3 lldiv.3 lsearch.3 \
malloc.3 memory.3 \
posix_memalign.3 posix_openpt.3 ptsname.3 \
@@ -56,6 +57,7 @@ MLINKS+=getenv.3 setenv.3 getenv.3 unset
MLINKS+=getenv.3 getenv_r.3
MLINKS+=hcreate.3 hdestroy.3 hcreate.3 hsearch.3
MLINKS+=insque.3 remque.3
+MLINKS+=jenkins_hash.3 jenkins_vector_hash.3
MLINKS+=lsearch.3 lfind.3
MLINKS+=malloc.3 calloc.3 malloc.3 realloc.3 malloc.3 free.3
MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3
Index: lib/libc/stdlib/jenkins_hash.3
===================================================================
RCS file: lib/libc/stdlib/jenkins_hash.3
diff -N lib/libc/stdlib/jenkins_hash.3
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ lib/libc/stdlib/jenkins_hash.3 16 Jul 2009 15:23:22 -0000
@@ -0,0 +1,72 @@
+.\" $NetBSD$
+.\"
+.\" 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 JENKINS_HASH 3
+.Os
+.Sh NAME
+.Nm jenkins_hash ,
+.Nm jenkins_vector_hash
+.Nd fast 32bit hash functions
+.Sh LIBRARY
+.Lb libc
+.Sh SYNOPSIS
+.In stdlib.h
+.Ft void
+.Fn jenkins_vector_hash "const void * restrict key" "size_t len" \
+ "uint32_t seed" "uint32_t hashes[3]"
+.Ft uint32_t
+.Fn jenkins_hash "const void * restrict key" "size_t len" "uint32_t seed"
+.Sh DESCRIPTION
+The
+.Fn jenkins_hash
+function computes a 32-bit hash value of the memory area starting at
+.Fa key
+with length
+.Fa len .
+.Pp
+The
+.Fn jenkins_vector_hash
+function computes three 32-bit hash values in parallel similar to
+.Fn jenkins_hash .
+.Pp
+The output of
+.Fn jenkins_hash
+and
+.Fn jenkins_vector_hash
+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 is named after its author Bob Jenkins.
Index: lib/libc/stdlib/jenkins_hash.c
===================================================================
RCS file: lib/libc/stdlib/jenkins_hash.c
diff -N lib/libc/stdlib/jenkins_hash.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ lib/libc/stdlib/jenkins_hash.c 16 Jul 2009 14:20:26 -0000
@@ -0,0 +1,169 @@
+/* $NetBSD$ */
+/*-
+ * 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$");
+
+#include <sys/endian.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
+jenkins_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;
+}
+
+uint32_t
+jenkins_hash(const void * __restrict key, size_t len, uint32_t seed)
+{
+ uint32_t hashes[3];
+
+ jenkins_vector_hash(key, len, seed, hashes);
+ return hashes[0];
+}
Index: tests/Makefile
===================================================================
RCS file: /home/joerg/repo/netbsd/src/tests/Makefile,v
retrieving revision 1.15
diff -u -p -r1.15 Makefile
--- tests/Makefile 2 May 2009 16:02:18 -0000 1.15
+++ tests/Makefile 16 Jul 2009 18:11:35 -0000
@@ -2,7 +2,7 @@
.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
Index: tests/lib/Atffile
===================================================================
RCS file: tests/lib/Atffile
diff -N tests/lib/Atffile
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/lib/Atffile 16 Jul 2009 20:43:55 -0000
@@ -0,0 +1,6 @@
+Content-Type: application/X-atf-atffile; version="1"
+X-NetBSD-Id: "$NetBSD: Atffile,v 1.1 2009/02/13 20:58:13 jmmv Exp $"
+
+prop: test-suite = "NetBSD"
+
+tp-glob: *
Index: tests/lib/Makefile
===================================================================
RCS file: tests/lib/Makefile
diff -N tests/lib/Makefile
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/lib/Makefile 16 Jul 2009 20:43:55 -0000
@@ -0,0 +1,10 @@
+# $NetBSD$
+
+.include <bsd.own.mk>
+
+SUBDIR= libc
+
+TESTSDIR= ${TESTSBASE}/lib
+
+.include <bsd.test.mk>
+.include <bsd.subdir.mk>
Index: tests/lib/libc/Atffile
===================================================================
RCS file: tests/lib/libc/Atffile
diff -N tests/lib/libc/Atffile
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/lib/libc/Atffile 16 Jul 2009 20:43:55 -0000
@@ -0,0 +1,5 @@
+Content-Type: application/X-atf-atffile; version="1"
+
+prop: test-suite = "NetBSD"
+
+tp: stdlib
Index: tests/lib/libc/Makefile
===================================================================
RCS file: tests/lib/libc/Makefile
diff -N tests/lib/libc/Makefile
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/lib/libc/Makefile 16 Jul 2009 20:43:55 -0000
@@ -0,0 +1,10 @@
+# $NetBSD: Makefile,v 1.3 2009/02/13 22:01:49 jmmv Exp $
+
+.include <bsd.own.mk>
+
+SUBDIR+= stdlib
+
+TESTSDIR= ${TESTSBASE}/lib/libc
+
+.include <bsd.subdir.mk>
+.include <bsd.test.mk>
Index: tests/lib/libc/stdlib/Atffile
===================================================================
RCS file: tests/lib/libc/stdlib/Atffile
diff -N tests/lib/libc/stdlib/Atffile
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/lib/libc/stdlib/Atffile 16 Jul 2009 20:43:55 -0000
@@ -0,0 +1,7 @@
+Content-Type: application/X-atf-atffile; version="1"
+X-NetBSD-Id: "$NetBSD$"
+
+prop: test-suite = "NetBSD"
+
+tp: t_jenkins
+
Index: tests/lib/libc/stdlib/Makefile
===================================================================
RCS file: tests/lib/libc/stdlib/Makefile
diff -N tests/lib/libc/stdlib/Makefile
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/lib/libc/stdlib/Makefile 16 Jul 2009 20:43:55 -0000
@@ -0,0 +1,9 @@
+# $NetBSD: Makefile,v 1.2 2008/05/01 15:38:17 jmmv Exp $
+
+.include <bsd.own.mk>
+
+TESTSDIR= ${TESTSBASE}/lib/libc/stdlib
+
+TESTS_C+= t_jenkins
+
+.include <bsd.test.mk>
Index: tests/lib/libc/stdlib/t_jenkins.c
===================================================================
RCS file: tests/lib/libc/stdlib/t_jenkins.c
diff -N tests/lib/libc/stdlib/t_jenkins.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/lib/libc/stdlib/t_jenkins.c 16 Jul 2009 20:43:55 -0000
@@ -0,0 +1,93 @@
+/* $NetBSD$ */
+/*-
+ * 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(jenkins);
+
+ATF_TC_HEAD(jenkins, tc)
+{
+ atf_tc_set_md_var(tc, "descr",
+ "Test jenkins_vector_hash for consistent results");
+}
+
+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(jenkins, 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);
+ jenkins_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, jenkins);
+
+ return atf_no_error();
+}
Home |
Main Index |
Thread Index |
Old Index