## -*-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
##
##----- 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.
##
## --- 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
./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
@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
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 \
--- /dev/null
+#! /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 <<EOF;
+# test vectors for unihash
+
+hash {
+EOF
+hash(0x00000000, "anything you like");
+hash(0x12345678, "an exaple test string");
+hash(0xb8a171f0, "The quick brown fox jumps over the lazy dog.");
+hash(0x2940521b, "A man, a plan, a canal: Panama!");
+
+my $k = 0x94b22a73;
+my $m = 0xbb7b1fef;
+for (my $i = 0; $i < 48; $i++) {
+ hash($k, "If we don't succeed, we run the risk of failure.");
+ $k = gfmul($k, $m);
+}
+
+print <<EOF;
+}
+EOF
/* -*-c-*-
*
- * $Id: unihash.c,v 1.1 2003/10/12 14:43:24 mdw Exp $
+ * $Id: unihash.c,v 1.2 2003/12/14 14:45:30 mdw Exp $
*
* Simple and efficient universal hashing for hashtables
*
/*----- Revision history --------------------------------------------------*
*
* $Log: unihash.c,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.
*
* @const void *p@ = pointer to data to hash
* @size_t sz@ = size of the data
*
- * Returns: ---
+ * Returns: Hash of data so far.
*
* Use: Hashes data. Call this as many times as needed.
*/
a ^= BYTEMULT(2, *pp++);
a ^= BYTEMULT(1, *pp++);
a ^= BYTEMULT(0, *pp++);
+ sz -= UNIHASH_NBATCH;
}
/* --- The tail end is a smaller batch --- */
return (UNIHASH(i, p, sz));
}
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+#include "testrig.h"
+
+static int verify(dstr *v)
+{
+ unihash_info ui;
+ uint32 k;
+ uint32 h, hh;
+ size_t n;
+ int i, c;
+ const char *p;
+ int ok = 1;
+
+ static const int step[] = { 0, 1, 5, 6, 7, 8, 23, -1 };
+
+ /* --- Set up for using this key --- */
+
+ k = *(uint32 *)v[0].buf;
+ h = *(uint32 *)v[2].buf;
+ unihash_setkey(&ui, k);
+
+ /* --- Hash the data a lot --- */
+
+ for (i = 0; step[i] >= 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 -------------------------------------------------*/
/* -*-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
*
/*----- 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.
*
* $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<n} m_i k^{i+1}.$%
+ * %$H_k(M) = k^{n+1} + \sum_{0\le i<n} m_i k^{i+1}.$%
*
* Note that %$H_0(M) = 0$% for all messages %$M$%.
*
* computationally unbounded adversaries. Simply XOR the hash with a random
* string indexed from a large random pad by some nonce sent with the
* message. The probability of a forgery attempt being successful is then
- * %$(\ell + 1)/2^t$%, where %$t$% is the tag length and %$n$% is the longest
- * message permitted.
+ * %$(\ell + 1)/2^t$%, where %$t$% is the tag length and %$\ell$% is the
+ * longest message permitted.
*/
/*----- Practicalities ----------------------------------------------------*
*
* We work in %$\gf{2^32}$%, represented as a field of polynomials modulo
- * %$\{104c11db7}_x$% (this is the standard CRC-32 polynomial). Our blocks
- * are bytes. We append a big-endian byte length.
+ * %$\texttt{104c11db7}_x$% (this is the standard CRC-32 polynomial). Our
+ * blocks are bytes.
*
* The choice of a 32-bit hash is made for pragmatic reasons: we're never
* likely to actually want all 32 bits for a real hashtable anyway. The
* @const void *p@ = pointer to data to hash
* @size_t sz@ = size of the data
*
- * Returns: ---
+ * Returns: Hash of data so far.
*
* Use: Hashes data. Call this as many times as needed.
*/
~mdw / mLib / commitdiff