From b938e043ca175a0911598e7f439ed6e200ab6f13 Mon Sep 17 00:00:00 2001 From: "H. Peter Anvin" Date: Fri, 31 Aug 2007 18:10:23 +0000 Subject: 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. --- perllib/gensv.pl | 42 +++++++++++++++++ perllib/phash.ph | 78 ++++++++----------------------- perllib/random_sv_vectors.ph | 106 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 168 insertions(+), 58 deletions(-) create mode 100755 perllib/gensv.pl create mode 100644 perllib/random_sv_vectors.ph (limited to 'perllib') 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; -- cgit v1.2.3