Test universal hashing and fix bugs.

[mLib] / unihash-check.pl

diff --git a/unihash-check.pl b/unihash-check.pl
new file mode 100644 (file)
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 <<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