Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src Simplify the BDZ compression function, making it smaller at ...
details: https://anonhg.NetBSD.org/src/rev/0c8d9f1d59d8
branches: trunk
changeset: 781722:0c8d9f1d59d8
user: joerg <joerg%NetBSD.org@localhost>
date: Tue Sep 25 20:53:46 2012 +0000
description:
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 | 4 +-
tests/usr.bin/nbperf/hash_driver.c | 4 +-
tests/usr.bin/nbperf/t_nbperf.sh | 37 +++++-
usr.bin/nbperf/nbperf-bdz.c | 239 +++++++++++++-----------------------
usr.bin/nbperf/nbperf.1 | 6 +-
5 files changed, 125 insertions(+), 165 deletions(-)
diffs (truncated from 467 to 300 lines):
diff -r 2fca19ba7d87 -r 0c8d9f1d59d8 tests/usr.bin/nbperf/h_nbperf.sh
--- a/tests/usr.bin/nbperf/h_nbperf.sh Tue Sep 25 16:11:42 2012 +0000
+++ b/tests/usr.bin/nbperf/h_nbperf.sh Tue Sep 25 20:53:46 2012 +0000
@@ -1,5 +1,5 @@
#!/bin/sh
-# $NetBSD: h_nbperf.sh,v 1.1 2012/07/22 20:38:20 joerg Exp $
+# $NetBSD: h_nbperf.sh,v 1.2 2012/09/25 20:53:46 joerg Exp $
#
# Copyright (c) 2012 The NetBSD Foundation, Inc.
# All rights reserved.
@@ -27,6 +27,6 @@
#
set -e
-head -n $4 $1 | nbperf -a $2 > hash.c 2> /dev/null
+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 2fca19ba7d87 -r 0c8d9f1d59d8 tests/usr.bin/nbperf/hash_driver.c
--- a/tests/usr.bin/nbperf/hash_driver.c Tue Sep 25 16:11:42 2012 +0000
+++ b/tests/usr.bin/nbperf/hash_driver.c Tue Sep 25 20:53:46 2012 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: hash_driver.c,v 1.1 2012/07/22 20:38:20 joerg Exp $ */
+/* $NetBSD: hash_driver.c,v 1.2 2012/09/25 20:53:46 joerg Exp $ */
/*-
* Copyright (c) 2012 The NetBSD Foundation, Inc.
* All rights reserved.
@@ -46,7 +46,7 @@
while ((len = getline(&line, &len, stdin)) > 0) {
if (len && line[len - 1] == '\n')
--len;
- printf("%" PRId32 "\n", 1 + hash(line, len));
+ printf("%" PRId32 "\n", hash(line, len));
}
free(line);
return 0;
diff -r 2fca19ba7d87 -r 0c8d9f1d59d8 tests/usr.bin/nbperf/t_nbperf.sh
--- a/tests/usr.bin/nbperf/t_nbperf.sh Tue Sep 25 16:11:42 2012 +0000
+++ b/tests/usr.bin/nbperf/t_nbperf.sh Tue Sep 25 20:53:46 2012 +0000
@@ -1,4 +1,4 @@
-# $NetBSD: t_nbperf.sh,v 1.1 2012/07/22 20:38:20 joerg Exp $
+# $NetBSD: t_nbperf.sh,v 1.2 2012/09/25 20:53:46 joerg Exp $
#
# Copyright (c) 2012 The NetBSD Foundation, Inc.
# All rights reserved.
@@ -27,7 +27,7 @@
cleanup()
{
- rm -f reference.txt hash.c testprog
+ rm -f reference.txt hash.c hash.map testprog
}
atf_test_case chm
@@ -38,10 +38,13 @@
chm_body()
{
for n in 4 32 128 1024 65536; do
- seq $n > reference.txt
+ 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()
@@ -57,10 +60,13 @@
chm3_body()
{
for n in 4 32 128 1024 65536; do
- seq $n > reference.txt
+ 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()
@@ -68,8 +74,31 @@
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 2fca19ba7d87 -r 0c8d9f1d59d8 usr.bin/nbperf/nbperf-bdz.c
--- a/usr.bin/nbperf/nbperf-bdz.c Tue Sep 25 16:11:42 2012 +0000
+++ b/usr.bin/nbperf/nbperf-bdz.c Tue Sep 25 20:53:46 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.5 2012/09/25 20:53:46 joerg 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.5 2012/09/25 20:53:46 joerg 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",
+ (state->graph.v + 63) / 64);
+ sum = 0;
+ for (i = 0; i < state->graph.v; ++i) {
+ sum |= ((uint64_t)state->g[i] & 1) << (i & 63);
+ if (i % 64 == 63) {
+ fprintf(nbperf->output, "%s0x%016" PRIx64 "ULL,%s",
+ (i / 64 % 2 == 0 ? "\t " : " "),
+ sum,
+ (i / 64 % 2 == 1 ? "\n" : ""));
+ sum = 0;
+ }
+ }
+ if (i % 64 != 0) {
+ fprintf(nbperf->output, "%s0x%016" PRIx64 "ULL,%s",
+ (i / 64 % 2 == 0 ? "\t " : " "),
sum,
- (i / 16 % 4 == 3 ? "\n" : ""));
+ (i / 64 % 2 == 1 ? "\n" : ""));
}
- fprintf(nbperf->output, "%s\t};\n", (i / 16 % 4 ? "\n" : ""));
+ fprintf(nbperf->output, "%s\t};\n", (i % 2 ? "\n" : ""));
+
+ fprintf(nbperf->output,
+ "\tstatic const uint64_t g2[%" PRId32 "] = {\n",
+ (state->graph.v + 63) / 64);
+ sum = 0;
+ for (i = 0; i < state->graph.v; ++i) {
+ sum |= (((uint64_t)state->g[i] & 2) >> 1) << (i & 63);
+ if (i % 64 == 63) {
+ fprintf(nbperf->output, "%s0x%016" PRIx64 "ULL,%s",
+ (i / 64 % 2 == 0 ? "\t " : " "),
+ sum,
+ (i / 64 % 2 == 1 ? "\n" : ""));
+ sum = 0;
+ }
+ }
+ if (i % 64 != 0) {
+ fprintf(nbperf->output, "%s0x%016" PRIx64 "ULL,%s",
+ (i / 64 % 2 == 0 ? "\t " : " "),
+ sum,
+ (i / 64 % 2 == 1 ? "\n" : ""));
+ }
+ fprintf(nbperf->output, "%s\t};\n", (i % 2 ? "\n" : ""));
fprintf(nbperf->output,
"\tstatic const uint32_t holes64k[%" PRId32 "] = {\n",
@@ -200,111 +204,45 @@
fprintf(nbperf->output, "%s\t};\n", (i / 65536 % 4 ? "\n" : ""));
fprintf(nbperf->output,
- "\tstatic const uint16_t holes256[%" PRId32 "] = {\n",
- (state->graph.v + 255) / 256);
- for (i = 0; i < state->graph.v; i += 256)
+ "\tstatic const uint16_t holes64[%" PRId32 "] = {\n",
+ (state->graph.v + 63) / 64);
+ for (i = 0; i < state->graph.v; i += 64)
fprintf(nbperf->output, "%s0x%04" PRIx32 ",%s",
- (i / 256 % 4 == 0 ? "\t " : " "),
- state->holes256[i >> 8],
- (i / 256 % 4 == 3 ? "\n" : ""));
- fprintf(nbperf->output, "%s\t};\n", (i / 256 % 4 ? "\n" : ""));
-
- fprintf(nbperf->output,
- "\tstatic const uint8_t holes256_64[%" PRId32 "] = {\n",
- (state->graph.v + 255) / 256);
- for (i = 64; i < state->graph.v; i += 256)
- fprintf(nbperf->output, "%s0x%02" PRIx32 ",%s",
- (i / 256 % 4 == 0 ? "\t " : " "),
- state->holes256_64[i >> 8],
- (i / 256 % 4 == 3 ? "\n" : ""));
- fprintf(nbperf->output, "%s\t};\n", (i / 256 % 4 ? "\n" : ""));
+ (i / 64 % 4 == 0 ? "\t " : " "),
+ state->holes64[i >> 6],
+ (i / 64 % 4 == 3 ? "\n" : ""));
+ fprintf(nbperf->output, "%s\t};\n", (i / 64 % 4 ? "\n" : ""));
- fprintf(nbperf->output,
- "\tstatic const uint8_t holes256_128[%" PRId32 "] = {\n",
- (state->graph.v + 255) / 256);
- for (i = 128; i < state->graph.v; i += 256)
- fprintf(nbperf->output, "%s0x%02" PRIx32 ",%s",
- (i / 256 % 4 == 0 ? "\t " : " "),
- state->holes256_128[i >> 8],
- (i / 256 % 4 == 3 ? "\n" : ""));
- fprintf(nbperf->output, "%s\t};\n", (i / 256 % 4 ? "\n" : ""));
Home |
Main Index |
Thread Index |
Old Index