Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/netbsd-6]: src Pull up following revision(s) (requested by joerg in tick...
details: https://anonhg.NetBSD.org/src/rev/afa92578c064
branches: netbsd-6
changeset: 775353:afa92578c064
user: riz <riz%NetBSD.org@localhost>
date: Wed Oct 17 21:37:11 2012 +0000
description:
Pull up following revision(s) (requested by joerg in ticket #574):
tests/usr.bin/nbperf/hash_driver.c: revision 1.2
tests/usr.bin/nbperf/h_nbperf.sh: revision 1.2
tests/usr.bin/nbperf/t_nbperf.sh: revision 1.2
usr.bin/nbperf/nbperf.1: revision 1.5
usr.bin/nbperf/nbperf-bdz.c: revision 1.5
Simplify the BDZ compression function, making it smaller at the same
time. Fixes a bug where non-minimal hash functions could be created.
Add regression tests for BDZ, including the map output functionality.
diffstat:
tests/usr.bin/nbperf/h_nbperf.sh | 32 ++++
tests/usr.bin/nbperf/hash_driver.c | 53 ++++++++
tests/usr.bin/nbperf/t_nbperf.sh | 104 ++++++++++++++++
usr.bin/nbperf/nbperf-bdz.c | 239 +++++++++++++-----------------------
usr.bin/nbperf/nbperf.1 | 6 +-
5 files changed, 277 insertions(+), 157 deletions(-)
diffs (truncated from 552 to 300 lines):
diff -r 678c4845775d -r afa92578c064 tests/usr.bin/nbperf/h_nbperf.sh
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/usr.bin/nbperf/h_nbperf.sh Wed Oct 17 21:37:11 2012 +0000
@@ -0,0 +1,32 @@
+#!/bin/sh
+# $NetBSD: h_nbperf.sh,v 1.2.2.2 2012/10/17 21:37:11 riz Exp $
+#
+# Copyright (c) 2012 The NetBSD Foundation, Inc.
+# All rights reserved.
+#
+# 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.
+#
+
+set -e
+head -n $4 $1 | nbperf -m hash.map -o hash.c -a $2 2> /dev/null
+cc -o testprog -I. $5
+head -n $4 $1 | ./testprog | $3
diff -r 678c4845775d -r afa92578c064 tests/usr.bin/nbperf/hash_driver.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/usr.bin/nbperf/hash_driver.c Wed Oct 17 21:37:11 2012 +0000
@@ -0,0 +1,53 @@
+/* $NetBSD: hash_driver.c,v 1.2.2.2 2012/10/17 21:37:11 riz Exp $ */
+/*-
+ * Copyright (c) 2012 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 <stdio.h>
+#include <inttypes.h>
+
+#include "hash.c"
+
+int
+main(void)
+{
+ char *line = NULL;
+ size_t buflen;
+ ssize_t len;
+
+ while ((len = getline(&line, &len, stdin)) > 0) {
+ if (len && line[len - 1] == '\n')
+ --len;
+ printf("%" PRId32 "\n", hash(line, len));
+ }
+ free(line);
+ return 0;
+}
diff -r 678c4845775d -r afa92578c064 tests/usr.bin/nbperf/t_nbperf.sh
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/usr.bin/nbperf/t_nbperf.sh Wed Oct 17 21:37:11 2012 +0000
@@ -0,0 +1,104 @@
+# $NetBSD: t_nbperf.sh,v 1.2.2.2 2012/10/17 21:37:11 riz Exp $
+#
+# Copyright (c) 2012 The NetBSD Foundation, Inc.
+# All rights reserved.
+#
+# 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.
+#
+
+cleanup()
+{
+ rm -f reference.txt hash.c hash.map testprog
+}
+
+atf_test_case chm
+chm_head()
+{
+ atf_set "descr" "Checks chm algorithm"
+}
+chm_body()
+{
+ for n in 4 32 128 1024 65536; do
+ seq 0 $(($n - 1)) > reference.txt
+ atf_check -o file:reference.txt \
+ $(atf_get_srcdir)/h_nbperf /usr/share/dict/web2 chm cat \
+ $n $(atf_get_srcdir)/hash_driver.c
+ atf_check -o file:hash.map \
+ $(atf_get_srcdir)/h_nbperf /usr/share/dict/web2 chm cat \
+ $n $(atf_get_srcdir)/hash_driver.c
+ done
+}
+chm_clean()
+{
+ cleanup
+}
+
+atf_test_case chm3
+chm3_head()
+{
+ atf_set "descr" "Checks chm3 algorithm"
+}
+chm3_body()
+{
+ for n in 4 32 128 1024 65536; do
+ seq 0 $(($n - 1)) > reference.txt
+ atf_check -o file:reference.txt \
+ $(atf_get_srcdir)/h_nbperf /usr/share/dict/web2 chm3 cat \
+ $n $(atf_get_srcdir)/hash_driver.c
+ atf_check -o file:hash.map \
+ $(atf_get_srcdir)/h_nbperf /usr/share/dict/web2 chm3 cat \
+ $n $(atf_get_srcdir)/hash_driver.c
+ done
+}
+chm3_clean()
+{
+ cleanup
+}
+
+atf_test_case bdz
+bdz_head()
+{
+ atf_set "descr" "Checks bdz algorithm"
+}
+bdz_body()
+{
+ for n in 4 32 128 1024 65536 131072; do
+ seq 0 $(($n - 1)) > reference.txt
+ atf_check -o file:reference.txt \
+ $(atf_get_srcdir)/h_nbperf /usr/share/dict/web2 bdz "sort -n" \
+ $n $(atf_get_srcdir)/hash_driver.c
+ atf_check -o file:hash.map \
+ $(atf_get_srcdir)/h_nbperf /usr/share/dict/web2 bdz cat \
+ $n $(atf_get_srcdir)/hash_driver.c
+ done
+}
+bdz_clean()
+{
+ cleanup
+}
+
+atf_init_test_cases()
+{
+ atf_add_test_case chm
+ atf_add_test_case chm3
+ atf_add_test_case bdz
+}
diff -r 678c4845775d -r afa92578c064 usr.bin/nbperf/nbperf-bdz.c
--- a/usr.bin/nbperf/nbperf-bdz.c Wed Oct 17 21:33:16 2012 +0000
+++ b/usr.bin/nbperf/nbperf-bdz.c Wed Oct 17 21:37:11 2012 +0000
@@ -1,6 +1,6 @@
-/* $NetBSD: nbperf-bdz.c,v 1.4 2011/10/21 23:47:11 joerg Exp $ */
+/* $NetBSD: nbperf-bdz.c,v 1.4.4.1 2012/10/17 21:37:11 riz Exp $ */
/*-
- * Copyright (c) 2009 The NetBSD Foundation, Inc.
+ * Copyright (c) 2009, 2012 The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
@@ -36,7 +36,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: nbperf-bdz.c,v 1.4 2011/10/21 23:47:11 joerg Exp $");
+__RCSID("$NetBSD: nbperf-bdz.c,v 1.4.4.1 2012/10/17 21:37:11 riz Exp $");
#include <err.h>
#include <inttypes.h>
@@ -72,10 +72,7 @@
struct graph3 graph;
uint32_t *visited;
uint32_t *holes64k;
- uint16_t *holes256;
- uint8_t *holes256_64;
- uint8_t *holes256_128;
- uint8_t *holes256_192;
+ uint16_t *holes64;
uint8_t *g;
uint32_t *result_map;
};
@@ -123,17 +120,8 @@
if (i % 65536 == 0)
state->holes64k[i >> 16] = holes;
- if (i % 256 == 0)
- state->holes256[i >> 8] = holes - state->holes64k[i >> 16];
-
- if (i % 256 == 64)
- state->holes256_64[i >> 8] = holes - state->holes256[i >> 8] - state->holes64k[i >> 16];
-
- if (i % 256 == 128)
- state->holes256_128[i >> 8] = holes - state->holes256[i >> 8] - state->holes64k[i >> 16];
-
- if (i % 256 == 192)
- state->holes256_192[i >> 8] = holes - state->holes256[i >> 8] - state->holes64k[i >> 16];
+ if (i % 64 == 0)
+ state->holes64[i >> 6] = holes - state->holes64k[i >> 16];
if (state->visited[i] > 1) {
j = state->visited[i] - 2;
@@ -143,28 +131,13 @@
if (state->g[i] == 3)
++holes;
}
-
- if (i % 65536 != 0)
- state->holes64k[(i >> 16) + 1] = holes;
-
- if (i % 256 != 0)
- state->holes256[(i >> 8) + 1] = holes - state->holes64k[((i >> 8) + 1) >> 8];
-
- if (i % 256 != 64)
- state->holes256_64[(i >> 8) + 1] = holes - state->holes256[(i >> 8) + 1] - state->holes64k[((i >> 8) + 1) >> 8];
-
- if (i % 256 != 128)
- state->holes256_128[(i >> 8) + 1] = holes - state->holes256[(i >> 8) + 1] - state->holes64k[((i >> 8) + 1) >> 8];
-
- if (i % 256 != 192)
- state->holes256_192[(i >> 8) + 1] = holes - state->holes256[(i >> 8) + 1] - state->holes64k[((i >> 8) + 1) >> 8];
}
static void
print_hash(struct nbperf *nbperf, struct state *state)
{
- size_t i, j;
- uint32_t sum;
+ uint64_t sum;
+ size_t i;
fprintf(nbperf->output, "#include <stdlib.h>\n");
fprintf(nbperf->output, "#include <strings.h>\n\n");
@@ -175,19 +148,50 @@
"%s(const void * __restrict key, size_t keylen)\n",
nbperf->hash_name);
fprintf(nbperf->output, "{\n");
- fprintf(nbperf->output,
- "\tstatic const uint32_t g[%" PRId32 "] = {\n",
- (state->graph.v + 15) / 16);
- for (i = 0; i < state->graph.v; i += 16) {
- for (j = 0, sum = 0; j < 16; ++j)
- sum |= (uint32_t)state->g[i + j] << (2 * j);
- fprintf(nbperf->output, "%s0x%08" PRIx32 "ULL,%s",
- (i / 16 % 4 == 0 ? "\t " : " "),
+ fprintf(nbperf->output,
+ "\tstatic const uint64_t g1[%" PRId32 "] = {\n",
Home |
Main Index |
Thread Index |
Old Index