X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/blobdiff_plain/8fe3c82b561e58c894d9b8392ef4003158f44dd8..4f6d400bf0d6324faa343ea121f465017032d72b:/unihash.c

diff --git a/unihash.c b/unihash.c
index 39e2f06..e2093b9 100644
--- a/unihash.c
+++ b/unihash.c
@@ -1,6 +1,6 @@
 /* -*-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
  *
@@ -30,6 +30,9 @@
 /*----- 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.
  *
@@ -92,7 +95,7 @@ void unihash_setkey(unihash_info *i, uint32 k)
  *		@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.  
  */
@@ -123,6 +126,7 @@ uint32 unihash_hash(const unihash_info *i, uint32 a,
     a ^= BYTEMULT(2, *pp++);
     a ^= BYTEMULT(1, *pp++);
     a ^= BYTEMULT(0, *pp++);
+    sz -= UNIHASH_NBATCH;
   }
 
   /* --- The tail end is a smaller batch --- */
@@ -156,4 +160,71 @@ uint32 unihash(const unihash_info *i, const void *p, size_t sz)
   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 -------------------------------------------------*/