phash: don't rely on the build platform Perl version of rand()

rand() in Perl can vary between platforms, so don't use it.  Instead,
remove a completely pointless level of indirection (it introduced a
permutation which cancelled itself out) and provide a canned set of
random numbers for the rest.  This guarantees we will always use the
same numbers.

3 files changed, 168 insertions, 58 deletions

diff --git a/perllib/gensv.pl b/perllib/gensv.pl
new file mode 100755
index 0000000..2790b0e
--- /dev/null
+++ b/perllib/gensv.pl
@@ -0,0 +1,42 @@
+#!/usr/bin/perl
+#
+# Generate a list of rotation vectors so we always use the same set.
+# This needs to be run on a platform with /dev/urandom.
+#
+
+($n) = @ARGV;
+
+sysopen(UR, '/dev/urandom', O_RDONLY) or die;
+
+$maxlen = 78;
+
+print "\@random_sv_vectors = (\n";
+$outl = '   ';
+
+for ($i = 0; $i < $n; $i++) {
+
+    do {
+	die if (sysread(UR, $x4, 4) != 4);
+	@n = unpack("C*", $x4);
+
+	$n[0] &= 31;
+	$n[1] &= 31;
+	$n[2] &= 31;
+	$n[3] &= 31;
+    } while ($n[0] == 0 || $n[1] == 0 || $n[2] == 0 || $n[3] == 0 ||
+	$n[0] == $n[3] || $n[1] == $n[2]);
+
+    $xl = sprintf(" [%d,%d,%d,%d]%s",
+		  $n[0], $n[1], $n[2], $n[3],
+		  ($i == $n-1) ? '' : ',');
+    if (length($outl.$xl) > $maxlen) {
+	print $outl, "\n";
+	$outl = '   ';
+    }
+    $outl .= $xl;
+}
+close(UR);
+
+print $outl, "\n";
+print ");\n";
+print "1;\n";
diff --git a/perllib/phash.ph b/perllib/phash.ph
index e17874a..679dc4f 100644
--- a/perllib/phash.ph
+++ b/perllib/phash.ph
@@ -4,12 +4,10 @@
 # C output.
 #
 # Requires the CPAN Graph module (tested against 0.81, 0.83, 0.84)
+#
 
 use Graph::Undirected;
-
-
-# Produce the same values every time, please...
-srand(0);
+require 'random_sv_vectors.ph';
 
 #
 # 32-bit rotate
@@ -38,42 +36,11 @@ sub prehash($$$) {
 	$k1 = $kn1; $k2 = $kn2;
     }
 
-    return ($k1 % $n, $k2 % $n);
-}
-
-#
-# Shuffle a list.
-#
-sub shuffle(@) {
-    my(@l) = @_;
-    my($i, $j);
-    my $tmp;
-
-    for ($i = scalar(@l)-1; $i > 0; $i--) {
-	$j = int(rand($i));
-	
-	$tmp = $l[$j];
-	$l[$j] = $l[$i];
-	$l[$i] = $tmp;
-    }
-
-    return @l;
-}
+    # Create a bipartite graph...
+    $k1 = (($k1 % $n) << 1) + 0;
+    $k2 = (($k2 % $n) << 1) + 1;
 
-#
-# Pick a set of F-functions of length N.
-#
-# ffunc(N)
-#
-sub ffunc($$$) {
-    my($n,$s,$i) = @_;
-    my(@l) = ();
-
-    while ($n--) {
-	push(@l, $i);
-	$i += $s;
-    }
-    return shuffle(@l);
+    return ($k1, $k2);
 }
 
 #
@@ -109,34 +76,29 @@ sub walk_graph($$$) {
 sub gen_hash_n($$$) {
     my($n, $sv, $href) = @_;
     my @keys = keys(%{$href});
-    my $i, $sv, @f1, @f2, @g;
+    my $i, $sv, @g;
     my $gr;
     my $k, $v;
     my $gsize = 2*$n;
 
-    @f1 = ffunc($n, 2, 0);
-    @f2 = ffunc($n, 2, 1);
-
     $gr = Graph::Undirected->new;
     for ($i = 0; $i < $gsize; $i++) {
 	$gr->add_vertex($i);
     }
 
     foreach $k (@keys) {
-	my ($p1, $p2) = prehash($k, $n, $sv);
-	my $pf1 = $f1[$p1];
-	my $pf2 = $f2[$p2];
+	my ($pf1, $pf2) = prehash($k, $n, $sv);
 	my $e = ${$href}{$k};
 
 	if ($gr->has_edge($pf1, $pf2)) {
 	    my $xkey = $gr->get_edge_attribute($pf1, $pf2, "key");
 	    my ($xp1, $xp2) = prehash($xkey, $n, $sv);
-	    print STDERR "Collision: $pf1=$pf2 $k ($p1,$p2) with ";
+	    print STDERR "Collision: $pf1=$pf2 $k with ";
 	    print STDERR "$xkey ($xp1,$xp2)\n";
 	    return;
 	}
 
-	# print STDERR "Edge $pf1=$pf2 value $e from $k ($p1,$p2)\n";
+	# print STDERR "Edge $pf1=$pf2 value $e from $k\n";
 
 	$gr->add_edge($pf1, $pf2);
 	$gr->set_edge_attribute($pf1, $pf2, "hash", $e);
@@ -174,7 +136,7 @@ sub gen_hash_n($$$) {
 
     print STDERR "Done: n = $n, sv = [", join(',', @$sv), "]\n";
 
-    return ($n, $sv, \@f1, \@f2, \@g);
+    return ($n, $sv, \@g);
 }
 
 #
@@ -182,7 +144,7 @@ sub gen_hash_n($$$) {
 #
 sub prehash_vector()
 {
-    return [int(rand(32)), int(rand(32)), int(rand(32)), int(rand(32))];
+    return [myrand(32), myrand(32), myrand(32), myrand(32)];
 }
 
 #
@@ -205,12 +167,14 @@ sub gen_perfect_hash($) {
 	$n <<= 1;
     }
 
-    $maxj = 512; # Number of times to try
+    # Number of times to try...
+    $maxj = scalar @random_sv_vectors;
 
     for ($i = 0; $i < 4; $i++) {
 	print STDERR "Trying n = $n...\n";
 	for ($j = 0; $j < $maxj; $j++) {
-	    $sv = prehash_vector();
+	    $sv = $random_sv_vectors[$j];
+	    # $sv = prehash_vector();
 	    @hashinfo = gen_hash_n($n, $sv, $href);
 	    return @hashinfo if (defined(@hashinfo));
 	}
@@ -253,20 +217,18 @@ sub read_input() {
 sub verify_hash_table($$)
 {
     my ($href, $hashinfo) = @_;
-    my ($n, $sv, $f1, $f2, $g) = @{$hashinfo};
+    my ($n, $sv, $g) = @{$hashinfo};
     my $k;
     my $err = 0;
 
     foreach $k (keys(%$href)) {
-	my ($p1, $p2) = prehash($k, $n, $sv);
-	my $pf1 = ${$f1}[$p1];
-	my $pf2 = ${$f2}[$p2];
+	my ($pf1, $pf2) = prehash($k, $n, $sv);
 	my $g1 = ${$g}[$pf1];
 	my $g2 = ${$g}[$pf2];
 
 	if ($g1+$g2 != ${$href}{$k}) {
-	    printf STDERR "%s(%d,%d): %d=%d, %d+%d = %d != %d\n",
-	    $k, $p1, $p2, $pf1, $pf2, $g1, $g2, $g1+$g2, ${$href}{$k};
+	    printf STDERR "%s(%d,%d): %d+%d = %d != %d\n",
+	    $k, $pf1, $pf2, $g1, $g2, $g1+$g2, ${$href}{$k};
 	    $err = 1;
 	} else {
 	    # printf STDERR "%s: %d+%d = %d ok\n",
diff --git a/perllib/random_sv_vectors.ph b/perllib/random_sv_vectors.ph
new file mode 100644
index 0000000..30df929
--- /dev/null
+++ b/perllib/random_sv_vectors.ph
@@ -0,0 +1,106 @@
+@random_sv_vectors = (
+    [19,10,28,8], [19,13,14,5], [29,12,9,13], [19,18,27,7], [26,29,15,30],
+    [19,3,2,14], [12,12,11,27], [21,7,22,16], [5,31,11,11], [18,8,27,6],
+    [14,10,24,15], [9,4,15,3], [18,19,17,5], [17,22,9,3], [6,22,27,4],
+    [12,20,18,23], [29,15,5,7], [2,2,8,1], [29,9,14,8], [8,13,6,20],
+    [25,24,28,11], [4,7,21,24], [29,15,24,28], [3,2,29,17], [23,5,19,24],
+    [6,1,17,16], [17,13,12,3], [15,15,8,3], [21,9,10,1], [17,10,26,28],
+    [6,13,18,20], [5,7,21,23], [3,11,4,4], [25,23,1,16], [26,7,26,19],
+    [18,16,24,30], [4,5,31,13], [12,28,3,14], [27,23,29,30], [17,26,6,8],
+    [29,10,4,26], [26,5,13,6], [24,6,16,18], [20,23,28,25], [28,22,8,27],
+    [16,15,18,12], [6,17,11,17], [11,20,31,5], [7,24,7,23], [13,29,6,3],
+    [4,23,11,29], [31,6,9,28], [3,1,7,13], [11,26,18,3], [27,19,10,1],
+    [29,8,3,17], [7,25,20,21], [16,10,22,29], [15,5,6,28], [17,31,7,21],
+    [25,23,19,7], [1,15,9,23], [21,2,22,19], [11,14,23,21], [31,12,30,11],
+    [24,13,27,9], [29,17,25,1], [4,3,16,22], [1,19,16,20], [20,21,27,9],
+    [2,21,22,12], [29,18,11,17], [14,25,5,29], [12,3,21,22], [2,12,8,1],
+    [29,25,4,28], [15,7,27,14], [4,22,10,11], [15,23,16,10], [2,19,15,17],
+    [16,21,20,5], [7,21,7,24], [28,16,7,8], [14,19,31,20], [17,16,10,19],
+    [21,20,10,16], [31,4,30,5], [2,23,29,31], [22,22,18,12], [22,22,16,4],
+    [19,27,22,5], [23,16,26,22], [9,13,22,31], [14,5,8,18], [22,9,14,17],
+    [22,20,8,10], [27,20,19,15], [8,29,27,18], [11,3,12,14], [29,29,19,25],
+    [12,11,8,26], [24,8,27,19], [2,5,9,25], [24,28,7,28], [9,6,8,12],
+    [8,1,15,3], [9,31,13,6], [7,29,8,22], [27,2,17,10], [25,22,23,13],
+    [15,30,2,17], [28,20,11,3], [13,31,17,15], [18,19,1,26], [14,4,17,29],
+    [20,6,5,24], [23,17,25,16], [30,11,31,20], [24,29,17,1], [28,5,27,18],
+    [23,13,24,8], [19,19,16,24], [4,25,20,13], [17,19,1,12], [13,5,25,3],
+    [16,6,17,7], [18,21,8,31], [16,25,4,9], [18,14,12,22], [21,8,17,22],
+    [30,14,30,28], [23,9,15,5], [1,8,21,11], [4,25,7,24], [12,31,18,21],
+    [17,24,15,18], [5,7,31,30], [3,5,3,31], [18,29,28,28], [3,29,15,4],
+    [5,18,26,31], [31,27,24,4], [4,16,18,18], [17,25,15,12], [13,19,28,7],
+    [26,20,25,10], [18,12,1,2], [9,17,3,21], [25,25,6,27], [14,8,31,21],
+    [15,21,14,3], [27,15,4,30], [1,8,11,25], [7,8,3,26], [18,8,19,25],
+    [11,19,25,24], [15,22,4,8], [8,28,4,18], [29,1,8,26], [16,27,4,10],
+    [14,11,10,25], [13,3,14,14], [29,25,5,8], [5,19,11,3], [27,31,20,29],
+    [11,6,4,22], [31,7,27,11], [30,27,13,11], [21,15,21,31], [15,26,5,23],
+    [9,25,23,19], [23,28,22,31], [14,11,8,19], [18,8,28,2], [15,19,17,24],
+    [2,18,8,18], [21,30,15,18], [10,21,31,26], [11,6,18,6], [19,31,10,12],
+    [25,31,1,10], [26,12,8,8], [14,23,29,4], [4,26,11,18], [17,16,7,11],
+    [15,12,24,18], [8,30,20,4], [3,16,23,12], [21,28,12,19], [22,3,28,5],
+    [6,7,23,28], [30,22,8,27], [17,27,17,2], [24,29,20,25], [7,21,2,11],
+    [25,8,31,4], [24,11,21,14], [25,13,2,24], [11,14,2,24], [26,16,6,12],
+    [13,27,24,19], [11,27,10,5], [30,19,23,18], [14,16,4,21], [9,26,5,24],
+    [28,19,1,6], [21,29,28,4], [31,6,20,9], [11,3,8,28], [17,10,20,10],
+    [13,11,28,6], [18,8,13,11], [13,29,4,5], [23,24,3,10], [12,30,20,21],
+    [15,9,30,9], [3,2,22,25], [31,19,30,9], [9,15,14,23], [24,19,16,2],
+    [10,28,16,18], [12,4,16,23], [16,28,2,12], [7,17,8,15], [5,20,1,2],
+    [12,18,21,15], [28,25,20,18], [25,18,13,7], [1,9,11,21], [5,3,1,26],
+    [21,5,25,12], [30,28,24,7], [16,21,10,15], [29,21,9,17], [27,24,30,25],
+    [31,4,25,4], [14,21,13,6], [3,15,13,21], [6,6,14,9], [10,6,30,20],
+    [23,28,31,22], [30,11,25,2], [22,25,21,10], [10,11,31,11], [6,9,22,10],
+    [14,19,9,16], [17,17,7,20], [10,1,8,1], [29,18,10,14], [2,3,19,17],
+    [28,14,21,14], [1,14,3,5], [31,14,22,22], [13,26,13,31], [5,23,12,25],
+    [25,21,13,19], [11,2,12,21], [16,1,13,24], [6,2,4,8], [19,12,9,29],
+    [2,19,20,7], [6,18,25,16], [12,14,15,19], [5,20,22,31], [12,15,13,8],
+    [10,10,12,26], [3,28,1,23], [20,6,24,4], [29,26,27,3], [3,22,20,21],
+    [4,21,6,8], [19,18,8,11], [27,26,2,3], [9,30,26,31], [29,2,20,31],
+    [14,18,7,4], [29,18,19,16], [28,20,13,4], [18,23,12,26], [25,24,6,27],
+    [7,30,21,26], [18,9,24,13], [21,3,13,14], [26,5,7,12], [10,6,16,16],
+    [15,7,4,11], [11,2,25,3], [26,22,28,5], [8,4,30,10], [27,27,13,11],
+    [14,24,21,24], [14,26,16,20], [22,29,20,3], [7,24,3,4], [30,23,17,27],
+    [4,19,27,16], [18,31,10,8], [10,11,27,29], [24,16,13,1], [23,16,24,2],
+    [14,14,10,6], [25,16,11,17], [30,6,14,15], [8,24,30,13], [31,13,20,24],
+    [20,16,21,24], [7,1,17,16], [22,1,30,26], [25,18,23,11], [2,14,18,4],
+    [28,27,29,25], [30,16,4,11], [15,13,14,21], [8,16,18,17], [4,14,11,14],
+    [4,3,18,18], [9,21,2,23], [2,13,9,26], [12,19,21,7], [9,18,7,11],
+    [1,29,11,26], [23,5,31,27], [30,5,25,2], [11,4,21,20], [30,18,29,6],
+    [19,3,12,28], [25,9,12,23], [1,5,6,22], [13,8,28,26], [3,6,31,10],
+    [15,17,19,17], [7,8,31,29], [29,1,7,11], [15,15,1,16], [20,18,27,27],
+    [22,14,11,25], [15,8,22,11], [15,10,7,22], [19,5,21,25], [11,23,26,4],
+    [23,21,8,7], [10,3,18,17], [13,11,4,26], [5,11,2,1], [27,18,7,26],
+    [14,7,12,21], [6,3,7,23], [15,16,6,8], [6,31,16,29], [9,10,25,10],
+    [10,28,23,4], [21,3,8,31], [29,28,20,12], [20,10,7,31], [23,11,25,6],
+    [2,10,2,1], [25,3,18,24], [29,11,5,3], [26,3,7,28], [13,4,3,19],
+    [1,16,19,17], [15,12,1,16], [8,18,7,19], [21,3,5,11], [26,18,3,19],
+    [10,21,25,29], [12,22,24,22], [31,12,7,6], [20,7,6,13], [1,11,7,17],
+    [28,25,22,25], [21,4,20,11], [14,26,11,31], [4,30,7,1], [28,26,1,9],
+    [21,29,31,17], [25,17,14,4], [26,31,30,28], [4,23,2,12], [5,26,31,18],
+    [11,7,1,14], [19,6,2,20], [17,12,3,28], [25,17,12,8], [30,2,30,3],
+    [6,10,16,1], [21,24,13,26], [17,13,2,16], [12,16,12,17], [25,14,19,5],
+    [11,7,3,1], [7,9,7,31], [2,6,7,14], [24,12,8,28], [25,25,22,31],
+    [9,7,11,31], [20,8,4,23], [25,16,11,24], [2,19,20,17], [13,4,19,6],
+    [21,6,19,1], [29,21,12,23], [15,13,28,17], [31,11,20,25], [4,20,9,24],
+    [5,25,11,20], [21,25,31,12], [5,20,23,7], [27,26,3,17], [1,4,7,13],
+    [8,7,25,20], [20,4,24,14], [13,7,6,5], [14,17,23,22], [20,16,15,26],
+    [21,28,30,17], [13,1,7,15], [29,24,17,20], [22,20,16,5], [17,25,10,6],
+    [14,1,18,13], [8,26,31,7], [28,29,3,10], [27,12,15,16], [13,14,20,5],
+    [26,9,16,5], [10,12,15,23], [30,31,9,15], [15,6,7,31], [15,30,10,31],
+    [21,31,3,1], [20,8,22,8], [17,15,26,5], [31,6,11,10], [6,30,27,5],
+    [7,29,10,15], [16,10,27,22], [2,2,31,15], [20,22,26,27], [12,16,20,21],
+    [8,15,31,7], [4,30,23,28], [18,8,19,14], [30,26,11,7], [5,26,18,25],
+    [5,21,14,8], [20,30,3,31], [25,19,5,5], [29,7,2,18], [16,18,2,17],
+    [13,15,25,19], [24,1,24,30], [23,5,11,13], [30,25,5,25], [18,16,20,28],
+    [3,26,5,10], [4,12,20,20], [14,7,27,12], [7,26,15,18], [30,29,16,13],
+    [20,23,30,2], [30,27,23,21], [27,30,12,22], [31,22,25,2], [9,28,1,2],
+    [8,2,23,15], [1,16,31,2], [3,24,5,6], [27,14,30,20], [29,18,16,12],
+    [22,17,3,16], [14,20,1,19], [18,16,11,30], [27,16,23,24], [20,27,10,19],
+    [7,4,11,13], [24,23,24,16], [3,24,19,16], [22,11,29,12], [17,16,28,11],
+    [11,23,9,16], [20,12,22,24], [31,27,2,7], [28,12,9,19], [12,28,11,21],
+    [16,4,31,6], [16,1,26,25], [14,15,22,26], [12,18,11,10], [28,14,26,1],
+    [24,29,24,7], [2,21,8,22], [27,6,25,9], [5,31,16,3], [7,10,22,23],
+    [1,18,11,13], [24,20,21,6], [22,26,21,28], [11,23,24,26], [28,4,3,22],
+    [6,16,5,19], [26,1,13,1], [7,16,27,12], [10,18,20,13], [3,28,23,15],
+    [16,14,11,13], [30,12,27,26], [18,23,20,3], [24,17,25,20], [18,10,3,20],
+    [15,2,1,5], [15,29,27,7]
+);
+1;