From 573eadb534c42c4feace5e493cc135dd5e7b00d9 Mon Sep 17 00:00:00 2001 Message-Id: <573eadb534c42c4feace5e493cc135dd5e7b00d9.1714147521.git.mdw@distorted.org.uk> From: Mark Wooding Date: Sun, 14 Dec 2003 14:45:30 +0000 Subject: [PATCH] Test universal hashing and fix bugs. Organization: Straylight/Edgeware From: mdw --- Makefile.am | 38 ++++++++++++++++++------ unihash-check.pl | 47 ++++++++++++++++++++++++++++++ unihash.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++-- unihash.h | 17 ++++++----- 4 files changed, 159 insertions(+), 18 deletions(-) create mode 100644 unihash-check.pl diff --git a/Makefile.am b/Makefile.am index 8e0c51d..372acd8 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1,6 +1,6 @@ ## -*-Makefile-*- ## -## $Id: Makefile.am,v 1.42 2003/12/13 20:37:59 mdw Exp $ +## $Id: Makefile.am,v 1.43 2003/12/14 14:45:30 mdw Exp $ ## ## Building the distribution ## @@ -29,6 +29,9 @@ ##----- Revision history ---------------------------------------------------- ## ## $Log: Makefile.am,v $ +## Revision 1.43 2003/12/14 14:45:30 mdw +## Test universal hashing and fix bugs. +## ## Revision 1.42 2003/12/13 20:37:59 mdw ## Add adns support in background resolver. ## @@ -193,10 +196,11 @@ crc_mktab_SOURCES = crc-mktab.c mdwopt.c quis.c pquis.c report.c str.c ## --- Test code --- -noinst_PROGRAMS = da.t sym.t assoc.t bits.t +noinst_PROGRAMS = da.t sym.t assoc.t bits.t unihash.t check: \ - da.test sym.test assoc.test bits.test base64.test hex.test + da.test sym.test assoc.test bits.test base64.test hex.test \ + unihash.test da_t_SOURCES = da-test.c da_t_LDADD = libmLib.la @@ -243,9 +247,11 @@ bits.test: bits.t ./bits.t -f $(srcdir)/bits.in base64.to: base64.c - $(COMPILE) -c -DTEST_RIG -DSRCDIR=\"$(srcdir)\" $(srcdir)/base64.c -o base64.to + $(COMPILE) -c -DTEST_RIG -DSRCDIR=\"$(srcdir)\" \ + $(srcdir)/base64.c -o base64.to base64.t: base64.to base64.o libmLib.la - $(CC) $(CFLAGS) $(LDFLAGS) base64.to .libs/libmLib.a $(LIBS) -o base64.t + $(CC) $(CFLAGS) $(LDFLAGS) \ + base64.to .libs/libmLib.a $(LIBS) -o base64.t base64.test: base64.t base64.in base64.ref ./base64.t <$(srcdir)/base64.in >base64.out cmp base64.out $(srcdir)/base64.ref @@ -254,9 +260,11 @@ base64.test: base64.t base64.in base64.ref @echo "base64 tested OK." hex.to: hex.c - $(COMPILE) -c -DTEST_RIG -DSRCDIR=\"$(srcdir)\" $(srcdir)/hex.c -o hex.to + $(COMPILE) -c -DTEST_RIG -DSRCDIR=\"$(srcdir)\" \ + $(srcdir)/hex.c -o hex.to hex.t: hex.to hex.o libmLib.la - $(CC) $(CFLAGS) $(LDFLAGS) hex.to .libs/libmLib.a $(LIBS) -o hex.t + $(CC) $(CFLAGS) $(LDFLAGS) \ + hex.to .libs/libmLib.a $(LIBS) -o hex.t hex.test: hex.t hex.in hex.ref ./hex.t <$(srcdir)/hex.in >hex.out cmp hex.out $(srcdir)/hex.ref @@ -264,11 +272,23 @@ hex.test: hex.t hex.in hex.ref cmp hex.out $(srcdir)/hex.in @echo "hex tested OK." +unihash.to: unihash.c + $(COMPILE) -c -DTEST_RIG -DSRCDIR=\"$(srcdir)\" \ + $(srcdir)/unihash.c -o unihash.to +unihash.t: unihash.to libmLib.la + $(CC) $(CFLAGS) $(LDFLAGS) \ + unihash.to .libs/libmLib.a $(LIBS) -o unihash.t +unihash.in: unihash-check.pl + perl $(srcdir)/unihash-check.pl >unihash.in.new + mv unihash.in.new unihash.in +unihash.test: unihash.t unihash.in + ./unihash.t -f unihash.in + TEST_CLEAN = \ - *.t \ + *.t *.to \ da.in da.ref da.out \ sym.in sym.ref sym.out \ - base64.out hex.out + base64.out hex.out unihash.in TEST_DIST = \ da-gtest da-ref \ diff --git a/unihash-check.pl b/unihash-check.pl new file mode 100644 index 0000000..72c3b9b --- /dev/null +++ b/unihash-check.pl @@ -0,0 +1,47 @@ +#! /usr/bin/perl + +my $MOD = 0x04c11db7; + +sub gfmul { + my ($x, $y) = @_; + my $a = 0; + + while ($y) { + if ($y & 1) { $a ^= $x }; + if ($x & 0x80000000) { $x <<= 1; $x ^= $MOD; } + else { $x <<= 1; } + $y >>= 1; + } + return $a; +} + +sub hash { + my ($k, $msg) = @_; + my $h = $k; + for (my $i = 0; $i < length $msg; $i++) { + my $m = ord(substr($msg, $i, 1)); + $h = gfmul($h ^ $m, $k); + } + printf " 0x%08x \"%s\" 0x%08x;\n", $k, $msg, $h; +} + +print <= 0; i++) { + c = step[i]; + if (!c) + hh = unihash(&ui, v[1].buf, v[1].len); + else { + hh = UNIHASH_INIT(&ui); + p = v[1].buf; + n = v[1].len; + while (n) { + if (c > n) c = n; + hh = unihash_hash(&ui, hh, p, c); + p += c; + n -= c; + } + } + if (h != hh) { + ok = 0; + fprintf(stderr, "\nunihash failed\n"); + fprintf(stderr, " key = %08lx\n", (unsigned long)k); + fprintf(stderr, " data = %s\n", v[1].buf); + fprintf(stderr, " step = %d\n", step[i]); + fprintf(stderr, " expected = %08lx\n", (unsigned long)h); + fprintf(stderr, " computed = %08lx\n", (unsigned long)hh); + } + } + return (ok); +} + +static const test_chunk tests[] = { + { "hash", verify, { &type_uint32, &type_string, &type_uint32 } }, + { 0, 0, { 0 } } +}; + +int main(int argc, char *argv[]) +{ + test_run(argc, argv, tests, "unihash.in"); + return (0); +} + +#endif + /*----- That's all, folks -------------------------------------------------*/ diff --git a/unihash.h b/unihash.h index 5fb5741..dfc5b79 100644 --- a/unihash.h +++ b/unihash.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: unihash.h,v 1.1 2003/10/12 14:43:24 mdw Exp $ + * $Id: unihash.h,v 1.2 2003/12/14 14:45:30 mdw Exp $ * * Simple and efficient universal hashing for hashtables * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: unihash.h,v $ + * Revision 1.2 2003/12/14 14:45:30 mdw + * Test universal hashing and fix bugs. + * * Revision 1.1 2003/10/12 14:43:24 mdw * Universal hashing. * @@ -50,7 +53,7 @@ * $m_{n-1}, m_{n-2}, \ldots, m_2, m_1, m_0$% in %$\gf{q}%. * Then we compute * - * %$H_k(M) = k^{n+1} \sum_{0\le i