diff options
-rw-r--r-- | crc64.c | 6 | ||||
-rw-r--r-- | hashtbl.c | 4 | ||||
-rw-r--r-- | hashtbl.h | 6 | ||||
-rw-r--r-- | perllib/crc64.ph | 158 | ||||
-rwxr-xr-x | perllib/gensv.pl | 18 | ||||
-rw-r--r-- | perllib/phash.ph | 63 | ||||
-rw-r--r-- | perllib/random_sv_vectors.ph | 359 | ||||
-rwxr-xr-x | pptok.pl | 22 | ||||
-rwxr-xr-x | tokhash.pl | 19 |
9 files changed, 465 insertions, 190 deletions
@@ -132,9 +132,8 @@ static const uint64_t crc64_tab[256] = { UINT64_C(0x536fa08fdfd90e51), UINT64_C(0x29b7d047efec8728), }; -uint64_t crc64(const char *str) +uint64_t crc64(uint64_t crc, const char *str) { - uint64_t crc = UINT64_C(0xffffffffffffffff); uint8_t c; while ((c = *str++) != 0) { @@ -144,9 +143,8 @@ uint64_t crc64(const char *str) return crc; } -uint64_t crc64i(const char *str) +uint64_t crc64i(uint64_t crc, const char *str) { - uint64_t crc = UINT64_C(0xffffffffffffffff); uint8_t c; while ((c = *str++) != 0) { @@ -48,7 +48,7 @@ void **hash_find(struct hash_table *head, const char *key, struct hash_insert *insert) { struct hash_tbl_node *np; - uint64_t hash = crc64(key); + uint64_t hash = crc64(CRC64_INIT, key); struct hash_tbl_node *tbl = head->table; size_t mask = head->size-1; size_t pos = hash & mask; @@ -76,7 +76,7 @@ void **hash_findi(struct hash_table *head, const char *key, struct hash_insert *insert) { struct hash_tbl_node *np; - uint64_t hash = crc64i(key); + uint64_t hash = crc64i(CRC64_INIT, key); struct hash_tbl_node *tbl = head->table; size_t mask = head->size-1; size_t pos = hash & mask; @@ -30,8 +30,10 @@ struct hash_insert { struct hash_tbl_node *where; }; -uint64_t crc64(const char *string); -uint64_t crc64i(const char *string); +uint64_t crc64(uint64_t crc, const char *string); +uint64_t crc64i(uint64_t crc, const char *string); +#define CRC64_INIT UINT64_C(0xffffffffffffffff) + struct hash_table *hash_init(void); void **hash_find(struct hash_table *head, const char *string, struct hash_insert *insert); diff --git a/perllib/crc64.ph b/perllib/crc64.ph new file mode 100644 index 00000000..30a47753 --- /dev/null +++ b/perllib/crc64.ph @@ -0,0 +1,158 @@ +# -*- perl -*- +# +# Pure Perl implementation of the same CRC64 implementation used +# elsewhere in NASM. +# +# Note: Perl may have 32- or 64-bit integers; we need to handle both +# without overflowing into floating point (yuck), so handle them as +# pairs of 32-bit numbers. Ordering is BIGENDIAN. +# + +@crc64_tab = ( + [0x00000000, 0x00000000], [0x7ad870c8, 0x30358979], + [0xf5b0e190, 0x606b12f2], [0x8f689158, 0x505e9b8b], + [0xc038e573, 0x9841b68f], [0xbae095bb, 0xa8743ff6], + [0x358804e3, 0xf82aa47d], [0x4f50742b, 0xc81f2d04], + [0xab28ecb4, 0x6814fe75], [0xd1f09c7c, 0x5821770c], + [0x5e980d24, 0x087fec87], [0x24407dec, 0x384a65fe], + [0x6b1009c7, 0xf05548fa], [0x11c8790f, 0xc060c183], + [0x9ea0e857, 0x903e5a08], [0xe478989f, 0xa00bd371], + [0x7d08ff3b, 0x88be6f81], [0x07d08ff3, 0xb88be6f8], + [0x88b81eab, 0xe8d57d73], [0xf2606e63, 0xd8e0f40a], + [0xbd301a48, 0x10ffd90e], [0xc7e86a80, 0x20ca5077], + [0x4880fbd8, 0x7094cbfc], [0x32588b10, 0x40a14285], + [0xd620138f, 0xe0aa91f4], [0xacf86347, 0xd09f188d], + [0x2390f21f, 0x80c18306], [0x594882d7, 0xb0f40a7f], + [0x1618f6fc, 0x78eb277b], [0x6cc08634, 0x48deae02], + [0xe3a8176c, 0x18803589], [0x997067a4, 0x28b5bcf0], + [0xfa11fe77, 0x117cdf02], [0x80c98ebf, 0x2149567b], + [0x0fa11fe7, 0x7117cdf0], [0x75796f2f, 0x41224489], + [0x3a291b04, 0x893d698d], [0x40f16bcc, 0xb908e0f4], + [0xcf99fa94, 0xe9567b7f], [0xb5418a5c, 0xd963f206], + [0x513912c3, 0x79682177], [0x2be1620b, 0x495da80e], + [0xa489f353, 0x19033385], [0xde51839b, 0x2936bafc], + [0x9101f7b0, 0xe12997f8], [0xebd98778, 0xd11c1e81], + [0x64b11620, 0x8142850a], [0x1e6966e8, 0xb1770c73], + [0x8719014c, 0x99c2b083], [0xfdc17184, 0xa9f739fa], + [0x72a9e0dc, 0xf9a9a271], [0x08719014, 0xc99c2b08], + [0x4721e43f, 0x0183060c], [0x3df994f7, 0x31b68f75], + [0xb29105af, 0x61e814fe], [0xc8497567, 0x51dd9d87], + [0x2c31edf8, 0xf1d64ef6], [0x56e99d30, 0xc1e3c78f], + [0xd9810c68, 0x91bd5c04], [0xa3597ca0, 0xa188d57d], + [0xec09088b, 0x6997f879], [0x96d17843, 0x59a27100], + [0x19b9e91b, 0x09fcea8b], [0x636199d3, 0x39c963f2], + [0xdf7adabd, 0x7a6e2d6f], [0xa5a2aa75, 0x4a5ba416], + [0x2aca3b2d, 0x1a053f9d], [0x50124be5, 0x2a30b6e4], + [0x1f423fce, 0xe22f9be0], [0x659a4f06, 0xd21a1299], + [0xeaf2de5e, 0x82448912], [0x902aae96, 0xb271006b], + [0x74523609, 0x127ad31a], [0x0e8a46c1, 0x224f5a63], + [0x81e2d799, 0x7211c1e8], [0xfb3aa751, 0x42244891], + [0xb46ad37a, 0x8a3b6595], [0xceb2a3b2, 0xba0eecec], + [0x41da32ea, 0xea507767], [0x3b024222, 0xda65fe1e], + [0xa2722586, 0xf2d042ee], [0xd8aa554e, 0xc2e5cb97], + [0x57c2c416, 0x92bb501c], [0x2d1ab4de, 0xa28ed965], + [0x624ac0f5, 0x6a91f461], [0x1892b03d, 0x5aa47d18], + [0x97fa2165, 0x0afae693], [0xed2251ad, 0x3acf6fea], + [0x095ac932, 0x9ac4bc9b], [0x7382b9fa, 0xaaf135e2], + [0xfcea28a2, 0xfaafae69], [0x8632586a, 0xca9a2710], + [0xc9622c41, 0x02850a14], [0xb3ba5c89, 0x32b0836d], + [0x3cd2cdd1, 0x62ee18e6], [0x460abd19, 0x52db919f], + [0x256b24ca, 0x6b12f26d], [0x5fb35402, 0x5b277b14], + [0xd0dbc55a, 0x0b79e09f], [0xaa03b592, 0x3b4c69e6], + [0xe553c1b9, 0xf35344e2], [0x9f8bb171, 0xc366cd9b], + [0x10e32029, 0x93385610], [0x6a3b50e1, 0xa30ddf69], + [0x8e43c87e, 0x03060c18], [0xf49bb8b6, 0x33338561], + [0x7bf329ee, 0x636d1eea], [0x012b5926, 0x53589793], + [0x4e7b2d0d, 0x9b47ba97], [0x34a35dc5, 0xab7233ee], + [0xbbcbcc9d, 0xfb2ca865], [0xc113bc55, 0xcb19211c], + [0x5863dbf1, 0xe3ac9dec], [0x22bbab39, 0xd3991495], + [0xadd33a61, 0x83c78f1e], [0xd70b4aa9, 0xb3f20667], + [0x985b3e82, 0x7bed2b63], [0xe2834e4a, 0x4bd8a21a], + [0x6debdf12, 0x1b863991], [0x1733afda, 0x2bb3b0e8], + [0xf34b3745, 0x8bb86399], [0x8993478d, 0xbb8deae0], + [0x06fbd6d5, 0xebd3716b], [0x7c23a61d, 0xdbe6f812], + [0x3373d236, 0x13f9d516], [0x49aba2fe, 0x23cc5c6f], + [0xc6c333a6, 0x7392c7e4], [0xbc1b436e, 0x43a74e9d], + [0x95ac9329, 0xac4bc9b5], [0xef74e3e1, 0x9c7e40cc], + [0x601c72b9, 0xcc20db47], [0x1ac40271, 0xfc15523e], + [0x5594765a, 0x340a7f3a], [0x2f4c0692, 0x043ff643], + [0xa02497ca, 0x54616dc8], [0xdafce702, 0x6454e4b1], + [0x3e847f9d, 0xc45f37c0], [0x445c0f55, 0xf46abeb9], + [0xcb349e0d, 0xa4342532], [0xb1eceec5, 0x9401ac4b], + [0xfebc9aee, 0x5c1e814f], [0x8464ea26, 0x6c2b0836], + [0x0b0c7b7e, 0x3c7593bd], [0x71d40bb6, 0x0c401ac4], + [0xe8a46c12, 0x24f5a634], [0x927c1cda, 0x14c02f4d], + [0x1d148d82, 0x449eb4c6], [0x67ccfd4a, 0x74ab3dbf], + [0x289c8961, 0xbcb410bb], [0x5244f9a9, 0x8c8199c2], + [0xdd2c68f1, 0xdcdf0249], [0xa7f41839, 0xecea8b30], + [0x438c80a6, 0x4ce15841], [0x3954f06e, 0x7cd4d138], + [0xb63c6136, 0x2c8a4ab3], [0xcce411fe, 0x1cbfc3ca], + [0x83b465d5, 0xd4a0eece], [0xf96c151d, 0xe49567b7], + [0x76048445, 0xb4cbfc3c], [0x0cdcf48d, 0x84fe7545], + [0x6fbd6d5e, 0xbd3716b7], [0x15651d96, 0x8d029fce], + [0x9a0d8cce, 0xdd5c0445], [0xe0d5fc06, 0xed698d3c], + [0xaf85882d, 0x2576a038], [0xd55df8e5, 0x15432941], + [0x5a3569bd, 0x451db2ca], [0x20ed1975, 0x75283bb3], + [0xc49581ea, 0xd523e8c2], [0xbe4df122, 0xe51661bb], + [0x3125607a, 0xb548fa30], [0x4bfd10b2, 0x857d7349], + [0x04ad6499, 0x4d625e4d], [0x7e751451, 0x7d57d734], + [0xf11d8509, 0x2d094cbf], [0x8bc5f5c1, 0x1d3cc5c6], + [0x12b59265, 0x35897936], [0x686de2ad, 0x05bcf04f], + [0xe70573f5, 0x55e26bc4], [0x9ddd033d, 0x65d7e2bd], + [0xd28d7716, 0xadc8cfb9], [0xa85507de, 0x9dfd46c0], + [0x273d9686, 0xcda3dd4b], [0x5de5e64e, 0xfd965432], + [0xb99d7ed1, 0x5d9d8743], [0xc3450e19, 0x6da80e3a], + [0x4c2d9f41, 0x3df695b1], [0x36f5ef89, 0x0dc31cc8], + [0x79a59ba2, 0xc5dc31cc], [0x037deb6a, 0xf5e9b8b5], + [0x8c157a32, 0xa5b7233e], [0xf6cd0afa, 0x9582aa47], + [0x4ad64994, 0xd625e4da], [0x300e395c, 0xe6106da3], + [0xbf66a804, 0xb64ef628], [0xc5bed8cc, 0x867b7f51], + [0x8aeeace7, 0x4e645255], [0xf036dc2f, 0x7e51db2c], + [0x7f5e4d77, 0x2e0f40a7], [0x05863dbf, 0x1e3ac9de], + [0xe1fea520, 0xbe311aaf], [0x9b26d5e8, 0x8e0493d6], + [0x144e44b0, 0xde5a085d], [0x6e963478, 0xee6f8124], + [0x21c64053, 0x2670ac20], [0x5b1e309b, 0x16452559], + [0xd476a1c3, 0x461bbed2], [0xaeaed10b, 0x762e37ab], + [0x37deb6af, 0x5e9b8b5b], [0x4d06c667, 0x6eae0222], + [0xc26e573f, 0x3ef099a9], [0xb8b627f7, 0x0ec510d0], + [0xf7e653dc, 0xc6da3dd4], [0x8d3e2314, 0xf6efb4ad], + [0x0256b24c, 0xa6b12f26], [0x788ec284, 0x9684a65f], + [0x9cf65a1b, 0x368f752e], [0xe62e2ad3, 0x06bafc57], + [0x6946bb8b, 0x56e467dc], [0x139ecb43, 0x66d1eea5], + [0x5ccebf68, 0xaecec3a1], [0x2616cfa0, 0x9efb4ad8], + [0xa97e5ef8, 0xcea5d153], [0xd3a62e30, 0xfe90582a], + [0xb0c7b7e3, 0xc7593bd8], [0xca1fc72b, 0xf76cb2a1], + [0x45775673, 0xa732292a], [0x3faf26bb, 0x9707a053], + [0x70ff5290, 0x5f188d57], [0x0a272258, 0x6f2d042e], + [0x854fb300, 0x3f739fa5], [0xff97c3c8, 0x0f4616dc], + [0x1bef5b57, 0xaf4dc5ad], [0x61372b9f, 0x9f784cd4], + [0xee5fbac7, 0xcf26d75f], [0x9487ca0f, 0xff135e26], + [0xdbd7be24, 0x370c7322], [0xa10fceec, 0x0739fa5b], + [0x2e675fb4, 0x576761d0], [0x54bf2f7c, 0x6752e8a9], + [0xcdcf48d8, 0x4fe75459], [0xb7173810, 0x7fd2dd20], + [0x387fa948, 0x2f8c46ab], [0x42a7d980, 0x1fb9cfd2], + [0x0df7adab, 0xd7a6e2d6], [0x772fdd63, 0xe7936baf], + [0xf8474c3b, 0xb7cdf024], [0x829f3cf3, 0x87f8795d], + [0x66e7a46c, 0x27f3aa2c], [0x1c3fd4a4, 0x17c62355], + [0x935745fc, 0x4798b8de], [0xe98f3534, 0x77ad31a7], + [0xa6df411f, 0xbfb21ca3], [0xdc0731d7, 0x8f8795da], + [0x536fa08f, 0xdfd90e51], [0x29b7d047, 0xefec8728] + ); + +sub crc64($$) { + my ($cv, $str) = @_; + my $c; + my @cc = @$cv; + $cc[0] %= 4294967296; + $cc[1] %= 4294967296; + + foreach $c (unpack("C*", $str)) { + my @ct = @{$crc64_tab[($cc[1] & 0xff) ^ $c]}; + + $cc[1] = $ct[1] ^ + ((($cc[1] & 0xffffff00) >> 8) | (($cc[0] & 0xff) << 24)); + $cc[0] = $ct[0] ^ (($cc[0] & 0xffffff00) >> 8); + } + + return @cc; +} diff --git a/perllib/gensv.pl b/perllib/gensv.pl index 2790b0ea..b80ccbe6 100755 --- a/perllib/gensv.pl +++ b/perllib/gensv.pl @@ -15,19 +15,11 @@ $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], + die if (sysread(UR, $x8, 8) != 8); + @n = unpack("V*", $x8); + + $xl = sprintf(" [0x%08x, 0x%08x]%s", + $n[0], $n[1], ($i == $n-1) ? '' : ','); if (length($outl.$xl) > $maxlen) { print $outl, "\n"; diff --git a/perllib/phash.ph b/perllib/phash.ph index 3bb3a05b..487b12ee 100644 --- a/perllib/phash.ph +++ b/perllib/phash.ph @@ -8,25 +8,7 @@ use Graph::Undirected; require 'random_sv_vectors.ph'; - -# -# Truncate to 32-bit integer -# -sub int32($) { - my($x) = @_; - - return int($x) % 4294967296; -} - -# -# 32-bit rotate -# -sub rot($$) { - my($v,$s) = @_; - - $v = int32($v); - return int32(($v << $s)|($v >> (32-$s))); -} +require 'crc64.ph'; # # Compute the prehash for a key @@ -35,20 +17,11 @@ sub rot($$) { # sub prehash($$$) { my($key, $n, $sv) = @_; - my $c; - my $k1 = 0, $k2 = 0; - my $ko1, $ko2; - my($s0, $s1, $s2, $s3) = @{$sv}; - - foreach $c (unpack("C*", $key)) { - $ko1 = $k1; $ko2 = $k2; - $k1 = int32(rot($ko1,$s0)^int32(rot($ko2, $s1)+$c)); - $k2 = int32(rot($ko2,$s2)^int32(rot($ko1, $s3)+$c)); - } + my @c = crc64($sv, $key); # Create a bipartite graph... - $k1 = (($k1 & ($n-1)) << 1) + 0; - $k2 = (($k2 & ($n-1)) << 1) + 1; + $k1 = (($c[1] & ($n-1)) << 1) + 0; # low word + $k2 = (($c[0] & ($n-1)) << 1) + 1; # high word return ($k1, $k2); } @@ -81,10 +54,10 @@ sub walk_graph($$$) { # # Generate the function assuming a given N. # -# gen_hash_n(N, sv, \%data) +# gen_hash_n(N, sv, \%data, run) # -sub gen_hash_n($$$) { - my($n, $sv, $href) = @_; +sub gen_hash_n($$$$) { + my($n, $sv, $href, $run) = @_; my @keys = keys(%{$href}); my $i, $sv, @g; my $gr; @@ -103,8 +76,10 @@ sub gen_hash_n($$$) { 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 with "; - print STDERR "$xkey ($xp1,$xp2)\n"; + if (defined($run)) { + print STDERR "$run: Collision: $pf1=$pf2 $k with "; + print STDERR "$xkey ($xp1,$xp2)\n"; + } return; } @@ -117,11 +92,15 @@ sub gen_hash_n($$$) { # At this point, we're good if the graph is acyclic. if ($gr->is_cyclic) { - print STDERR "Graph is cyclic\n"; + if (defined($run)) { + print STDERR "$run: Graph is cyclic\n"; + } return; } - print STDERR "Graph OK, computing vertices...\n"; + if (defined($run)) { + print STDERR "$run: Graph OK, computing vertices...\n"; + } # Now we need to assign values to each vertex, so that for each # edge, the sum of the values for the two vertices give the value @@ -144,7 +123,10 @@ sub gen_hash_n($$$) { # print STDERR "Vertex ", $i, ": ", $g[$i], "\n"; # } - print STDERR "Done: n = $n, sv = [", join(',', @$sv), "]\n"; + if (defined($run)) { + printf STDERR "$run: Done: n = $n, sv = [0x%08x, 0x%08x]\n", + $$sv[0], $$sv[1]; + } return ($n, $sv, \@g); } @@ -159,6 +141,7 @@ sub gen_perfect_hash($) { my @keys = keys(%{$href}); my @hashinfo; my $n, $i, $j, $sv, $maxj; + my $run = 1; # Minimal power of 2 value for N with enough wiggle room. # The scaling constant must be larger than 0.5 in order for the @@ -176,7 +159,7 @@ sub gen_perfect_hash($) { print STDERR "Trying n = $n...\n"; for ($j = 0; $j < $maxj; $j++) { $sv = $random_sv_vectors[$j]; - @hashinfo = gen_hash_n($n, $sv, $href); + @hashinfo = gen_hash_n($n, $sv, $href, $run++); return @hashinfo if (defined(@hashinfo)); } $n <<= 1; diff --git a/perllib/random_sv_vectors.ph b/perllib/random_sv_vectors.ph index 30df929a..ae67d1f9 100644 --- a/perllib/random_sv_vectors.ph +++ b/perllib/random_sv_vectors.ph @@ -1,106 +1,259 @@ @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] + [0x4f75e86a, 0xa619a221], [0x4211d883, 0x375af6e6], + [0x7657d667, 0x6333e69f], [0x51306ad6, 0xe87a75b2], + [0x818469e6, 0x19a9e82d], [0x623da09e, 0x169c4031], + [0xc3012f83, 0xbdf48dd0], [0xfcbb1f89, 0x0c51d7c9], + [0xe1e3397b, 0x8ff4d865], [0x0ac918f1, 0x4f9ec6bb], + [0xbe18da0f, 0xd87be655], [0x0f0e0e53, 0xf1288c8b], + [0xf9d28c2b, 0xf8ab94c8], [0xcfabcfae, 0x6d08b1dc], + [0xe496f39b, 0x548e8257], [0xd21e139e, 0x721b5256], + [0xbdc4bf74, 0x03160c9e], [0xd19ef1b3, 0x0ca3b520], + [0x8f52dfbd, 0x4c7a6224], [0xc67399be, 0xbb88e496], + [0x334cdf5b, 0x4a7884e6], [0x46b89a7a, 0xaafbd448], + [0x0f5f12a1, 0x3694d0f1], [0x376fd093, 0xd0dac844], + [0xcc21a4bd, 0x11fb3780], [0x0fdf4036, 0x5b51fc12], + [0x4f8ffd03, 0xea2579a6], [0x8f8cc719, 0x7c11acb4], + [0x2fe1ee56, 0x9c781da6], [0x4db1da0d, 0xb65cb4e3], + [0x70b53ff6, 0x98f35a3e], [0x9bf52704, 0x66c9f702], + [0x9ea4aa9c, 0xa45cb773], [0x1b745933, 0x0e4df7c1], + [0xd9f3cc40, 0x78b8e00f], [0x131620ea, 0x6c693290], + [0xbc0e10dd, 0x2d8de15e], [0x3e7684e5, 0x15358338], + [0x427f025b, 0x1bea99b8], [0x9e36e80a, 0x5cc209f7], + [0xe96ecd24, 0x164c80ad], [0x2a0fd487, 0x34ae53a8], + [0x374d10ad, 0xf8ba703e], [0xc7b7025c, 0x726fd38c], + [0xc9c71681, 0x749fe58c], [0x54c146f9, 0xcf5d5eed], + [0xdd63a845, 0x5b409a2b], [0x6c1eb5df, 0x236f3d7a], + [0x3f26e454, 0x6c6ddbda], [0xde49583e, 0x854d25f8], + [0x77cc1c8b, 0xb9f44f2f], [0x504d08d7, 0x8a15f37b], + [0x0fa90449, 0x767c45e6], [0x353dd4f6, 0x3945abc3], + [0x279cc804, 0x9aca2078], [0xc0889e29, 0x0887bc4b], + [0x6befcf7a, 0x34579438], [0xa1e96c99, 0x4e8d958e], + [0x7e92c701, 0x8cafd3e4], [0x88194b29, 0x549baa5b], + [0x37d5a863, 0x6d158281], [0xe39bfd81, 0xeeba2b1f], + [0xf0b45736, 0x909cd899], [0x36528974, 0x3864d47c], + [0xe8c776af, 0x9a09b791], [0x2178fa44, 0x283993fb], + [0x7705f641, 0x6b77e579], [0x3be99f1a, 0xddb55ee7], + [0x933e4adf, 0x8bf2a4d5], [0x60bd229f, 0x553a1880], + [0xf71eecc0, 0x44540d74], [0x0b2e0f02, 0x51f94819], + [0x9acb45f1, 0x56ff9489], [0x55deac30, 0xf40bd69f], + [0xc7c65da9, 0x6e98523f], [0xd20df531, 0x73229a8b], + [0x56736755, 0x58f1155e], [0x6bd03660, 0x75c2d26c], + [0x62228cdc, 0x49ea4855], [0x0856f45a, 0xd59f5a1e], + [0x2b2e8407, 0x508bb429], [0xa24b81e7, 0xd2c1752b], + [0xc1eedb28, 0xf5dc5ff0], [0xb177d794, 0xdab6f4c7], + [0xbfb6ab33, 0x77d416c3], [0x4c700e4c, 0x80f7f3ef], + [0xe347cd1d, 0xc99d97fd], [0xb956c326, 0x1db9795c], + [0xd9a297a2, 0x4fb27f28], [0xeab7b30a, 0xe6eb4149], + [0x9322674d, 0xd64f5309], [0x3a2af9ac, 0x8b5cbd69], + [0x00d7dca2, 0xa310e46e], [0x56e42d70, 0xd5c2992f], + [0x43f07ed8, 0x3bfab03e], [0x143a4553, 0xe639bbee], + [0xf60cabf6, 0xc6a3424a], [0xc750ba59, 0x9740ce3d], + [0x1675449d, 0xc8eaadb3], [0x58624a9f, 0xb57239fc], + [0x929c104e, 0x56f27b11], [0x37d4ebfd, 0xa16cc57b], + [0x94053a40, 0x76241e44], [0x45476224, 0xc691a365], + [0x79850c7b, 0x453d196a], [0xd7aab2ad, 0xaff8d277], + [0x50832666, 0xcd0d459b], [0x56b44783, 0xdc79d8ed], + [0x8ff6b84b, 0x66d87d23], [0xa7c60d26, 0xe987e43a], + [0x930ca6a5, 0xc24f2033], [0xf2563f72, 0x309e4a30], + [0xf453bad1, 0x0a72b87a], [0xdf0847c5, 0x8edd6a2d], + [0x40027952, 0x0fa1766e], [0xe5debb75, 0x4129a8e1], + [0xdba91181, 0xc1412803], [0x281f61d6, 0xb08052f1], + [0x7971effd, 0x445d6c35], [0x1a146185, 0xd4954510], + [0xb6bb87e9, 0xc2f5fc7d], [0xc49159ad, 0xf82c3a57], + [0x2af4ec6e, 0x4d292183], [0xff3153dd, 0x64fad735], + [0x2c2538fc, 0x58a8b44a], [0x3968b689, 0xb48830eb], + [0x08c13fc4, 0xa923fb77], [0x369bc946, 0x260baa8a], + [0x9ddc8916, 0x40e92e7d], [0xa136cd43, 0xe4c6d889], + [0x5de28e5a, 0x7cd5f555], [0xcfbe100e, 0xf4e907c5], + [0x1ad38836, 0xd1b65d61], [0x0f84eae1, 0xb7af25a1], + [0x555bde94, 0x30eff969], [0x841d6e2a, 0xd64de0e9], + [0x9bbe13c2, 0xe7540d27], [0x2c8ec90c, 0x7ce816b3], + [0x0314b049, 0xfc5c9b2d], [0x335b3350, 0x7c1c4afc], + [0xa33d8419, 0xae85e9fc], [0x22646aac, 0xba58e66c], + [0x716418c7, 0x51e1cd9c], [0x1240dde1, 0xba0cc0ec], + [0xb5a6057c, 0x148d2c74], [0x68450010, 0xeea292bf], + [0x229b3221, 0xea792408], [0x528b20c4, 0xea2c5951], + [0xa8f0779c, 0x42010fb9], [0x2cc31f92, 0x67b244b0], + [0xb01b74f9, 0x5c1c2dbe], [0xf6810206, 0x258f9b43], + [0x23f41154, 0x51e23da9], [0x4c1dd303, 0x34ec2d34], + [0xb0cfaa95, 0x79ca912e], [0x1c14beeb, 0xdc931183], + [0xbb752e92, 0xbf5468c7], [0x4471962b, 0xc19f6dc0], + [0x673f96ec, 0x4902ef9f], [0x724ae7a2, 0x2a6a2eca], + [0xd3a3d443, 0xe5e79fee], [0x8ab86260, 0x4a398e5d], + [0x6f6200bc, 0xaf5a76bd], [0x32620350, 0x2cfd5327], + [0x16fe8e0b, 0x6a9b06ff], [0x71b2da77, 0xd11fddce], + [0x5c522528, 0xf4a87761], [0x5bd78f68, 0xd2c6df8f], + [0x0cdba679, 0x8abcbaf7], [0x80a6f94b, 0x327bead4], + [0x27db6849, 0xe47358f6], [0x2ab4f45e, 0x0a053dc7], + [0xc87a9f0d, 0x0281bd95], [0x0f577c99, 0x8b3dae49], + [0xfe5b8224, 0x219c31c7], [0x5376dbe2, 0x4d9a7b99], + [0xca8ba206, 0xe402e775], [0x503287bc, 0x45a0bb90], + [0x1ae2e66b, 0x9f4a1142], [0xbdd6a2e6, 0xe739841b], + [0xeb2bb9dd, 0x196d2bbf], [0x0009ada3, 0x1f4a8903], + [0x136e3097, 0xb2835ac6], [0xbcb6442a, 0x34d024bd], + [0xe9dacc26, 0xb8ab0020], [0xdc8d67b8, 0xd15cc22c], + [0x4cac7bcb, 0x65526228], [0xf5460d00, 0xc9a38d07], + [0xc4f58a1a, 0x2034a9d6], [0xe19e425c, 0xae2c34ad], + [0x5904e642, 0x5ddb47b3], [0x9f635b83, 0x2ce2c1e1], + [0xa91ab3e2, 0x9e42c598], [0x0633c4c4, 0xae235414], + [0x3701d10b, 0x35e9288f], [0x8019c970, 0x3b7e7894], + [0xd829ab85, 0x4f779cbb], [0x42001b88, 0x3ed354e0], + [0x41924a24, 0x48a62944], [0x1eefe1da, 0x1b37c591], + [0x867e9dd5, 0xad80bf59], [0xe8e35fd5, 0x1aaf0305], + [0x331583b4, 0x3286194b], [0x576e57aa, 0x8b518367], + [0x0dddf5f8, 0xd8fe4dd0], [0x5da13726, 0xe96b0257], + [0x7f17c240, 0x831ad957], [0x95df4b2f, 0x01947e5d], + [0x79b6e0ef, 0xa99c3a83], [0x0dc2f9d7, 0x76b8fc6c], + [0x453a7daf, 0xdf747b17], [0x5b86e795, 0x4107c74a], + [0xcad959a5, 0x5c59fcd6], [0x6c6f1e84, 0x191032a5], + [0xe272368d, 0xfe5068e1], [0x3b999268, 0xfc720e4d], + [0x2aa05ccc, 0x8bf5a0b5], [0xbbff5284, 0xa445a0cf], + [0xa7bd1807, 0x0c98ca2b], [0x618ca6b2, 0x832c7588], + [0x44a6028e, 0x178eefd6], [0x122c356c, 0x462e75e5], + [0x274bd57d, 0xc40f85c4], [0x601704b2, 0x10a86f33], + [0xf28ee83a, 0x12fab256], [0x321b4d79, 0x3e11bcc3], + [0x5fdc994e, 0x7bcf3fcb], [0x38016483, 0x2c5dfe44], + [0xbe29a429, 0xbf4fa453], [0x50130bb4, 0x6027303b], + [0xe4dcceb1, 0x5844fcb7], [0x48dd9bc1, 0x320c434e], + [0xb478ecc6, 0x69efaa2f], [0xad49a4ff, 0xe5dd1afa], + [0x9c3ce862, 0x14707cd7], [0x4a6588ae, 0x0ecf4354], + [0x542e19db, 0x69188ba4], [0x51a6e537, 0xb5c4bdaf], + [0x55480f0a, 0x1968ba27], [0x67c58376, 0xc1c086a3], + [0x076259c3, 0xe291c26c], [0xaee7ac5c, 0xcabdec91], + [0x5d3862fb, 0x2e8a3060], [0x6fb3635c, 0x4783593a], + [0x13f0eafb, 0x407e486a], [0x7436afdd, 0xd04c4829], + [0xace2d0e4, 0x80575791], [0x2dd9a392, 0xdc1e869e], + [0x199c3e38, 0x026a9d67], [0x9f911c85, 0x3a489c87], + [0x9ac31028, 0x0b6e14b2], [0x2ccfbcf9, 0x3f9f2308], + [0x2e0210fb, 0x392f380f], [0x14ab403a, 0x81a11065], + [0xd496f63c, 0x53196b13], [0x48a34d7f, 0x2ffc6036], + [0x34ea8e9d, 0xcd1ed098], [0x2da1a3f2, 0x3d6c23f2], + [0xca7374da, 0x06054f89], [0xc909a0bb, 0x31d6c0d2], + [0x87454496, 0x15b360d7], [0x9eebbd12, 0x89532131], + [0x1119c65b, 0xd9e49705], [0x60c3be0b, 0xd6cc7c8a], + [0x117723cd, 0x40af090f], [0xfc284f51, 0x3dcf4c06], + [0xb41fcda4, 0xec03644c], [0xd99e1ea7, 0x84eaf76d], + [0x534b956a, 0x06d3fb8d], [0x2da4bb09, 0x078092eb], + [0x6a5be463, 0xbfa51a88], [0xc4e8be95, 0xe7eec27c], + [0x15a1fbb9, 0xfadc08cd], [0x0bcfab08, 0xbccade0f], + [0x629f1f6c, 0x90ccede7], [0x5c2b26aa, 0x1f0b1fce], + [0xdfe0e3fd, 0xbd7c3cfb], [0xa1628ca9, 0x90a05686], + [0xbf0267f2, 0xd2964139], [0x8009a9b9, 0xd2195918], + [0xfcc7b5f8, 0xc108c643], [0xf447d4b0, 0x71953863], + [0x95d091ed, 0xdbe01948], [0x81dec325, 0x2bfecda2], + [0x2ed2acaa, 0x7eeaa0d0], [0xb7b0a20e, 0x8bf5c01b], + [0x75eb3917, 0xfd2f758f], [0xb33a5b49, 0x8a8cedf6], + [0x3aaf2757, 0x69b319a9], [0x32cfa41b, 0xeba36f19], + [0xf54209dd, 0x941f3a08], [0x232703bb, 0x786a6f84], + [0x4937b242, 0xc9f07398], [0x74dc5d39, 0x550a58e8], + [0x6c9aebdc, 0x8fda5069], [0x5ae6d62a, 0x05cd24a3], + [0x8111e50a, 0xc1c6d19b], [0xb980a92b, 0x448b4d1f], + [0x568cf58a, 0x8bcb93ca], [0xfe96002f, 0x410cd2f1], + [0xaf511e45, 0x99e4872f], [0x822c20bc, 0x3db49ddd], + [0x184fec4e, 0xbb82ec52], [0x30ca5326, 0xf3180297], + [0x97962aa4, 0x7d4bc6d4], [0x9199a315, 0x8e9f18c6], + [0xead69a7e, 0x3262a683], [0xe261ec00, 0x81edc47a], + [0x06080c0e, 0x6d18fa9f], [0x1771ec43, 0x6747ed66], + [0xe71fe587, 0xe81ad0f3], [0xf083e80c, 0x0898bcd8], + [0x30328c5a, 0x2efb4ee7], [0xd04fa5d7, 0xec9c9f18], + [0x87820480, 0x48932224], [0xb1f18815, 0x1b27e3e3], + [0x79aa440c, 0xdf17a8fc], [0x8a83d404, 0x10fdec8c], + [0x7d4dfe60, 0x573561ee], [0x60315c7d, 0xa0692af6], + [0xb3ca4d52, 0x89ca832f], [0x9ebc5c79, 0xa84a28fc], + [0xdfa76008, 0x7772cf7c], [0xb0e3a15f, 0xbdc35aee], + [0x6e252b03, 0x32b2107d], [0x20dcc2a3, 0x21987229], + [0x848e3ad8, 0xe692a0c6], [0xdd07fa50, 0x0b64e1ae], + [0xc4072bc2, 0x2f120bba], [0xdb3af26e, 0xacab0c48], + [0xd7d4b59a, 0xcf72a7a7], [0x4628de45, 0x4dfb2750], + [0x7519211f, 0x4798b536], [0x19984af3, 0xffd2aa19], + [0x1372d9c0, 0x7512153a], [0x295d19da, 0x497416e5], + [0x70932c73, 0x8a9bf591], [0xa0960860, 0xfaa7dc61], + [0xd425f548, 0x43aeda4d], [0xaa2573c7, 0x01a2553d], + [0x988e71d7, 0xd3c004a4], [0x3da87545, 0x2197af10], + [0x2f89e592, 0xa686e2fc], [0x7b88018a, 0xae66d575], + [0x93215591, 0xed69e6ea], [0x4fcacc4a, 0x4d2aba97], + [0xbedb923b, 0x500b2f1a], [0x0b6d8aa0, 0x232511b0], + [0x282fb3ee, 0x23695de0], [0x0c455dfe, 0x820cca3f], + [0xe893868c, 0x87f698f6], [0xb6428730, 0x56e576ce], + [0xf3843ee7, 0xba79bc28], [0xa1c9ca45, 0x30c479c1], + [0xbfc244c2, 0xa9af65f0], [0x6eeb88eb, 0x62b4479c], + [0xcc328fe5, 0x60f5c9bf], [0x31aa2c21, 0xc55575fb], + [0x9429492d, 0x8e80612a], [0xb12fe59e, 0xf0e1e97b], + [0xc2501dad, 0x4a9f4bbf], [0x65ae8366, 0x3e8b0983], + [0xd5fc062a, 0xba74f808], [0x7398cc0a, 0x39a6a269], + [0x5581dd60, 0xff79d28c], [0xea5e52b3, 0x9be66c71], + [0x8f6e02a4, 0xe27318b5], [0xe8bceb99, 0xa48a7f2c], + [0x1983864a, 0x80a5aaac], [0xc3536829, 0x7394fd57], + [0xb88bee05, 0x98693f0f], [0x7d8a458b, 0xe24e1366], + [0xa9fa5e63, 0x5add82d1], [0xc855bc4b, 0x8921a914], + [0x1308a796, 0x25efdd85], [0x843b5f09, 0x6967d842], + [0x466c5324, 0x414a6b62], [0x02d396d9, 0x716e7aa2], + [0x25da50ce, 0x6d37167a], [0x77caccf4, 0x89676238], + [0xc0ce0f0a, 0xca014c04], [0x526271c8, 0x6473a5d8], + [0xb9b30903, 0x33ca1a9b], [0x73991ad9, 0xdad6ee2b], + [0xe9fded7e, 0xa62e9304], [0x2bdcc821, 0xaefcf4aa], + [0x4767e8c0, 0xfc07e9a8], [0xef2d5991, 0x25e26838], + [0x0280f732, 0xc275aa47], [0xf2d8812d, 0x7b146198], + [0xb3484033, 0xce000bb1], [0x6fde88ea, 0x32a5eaed], + [0xcb5aa54d, 0xe7a7dc62], [0xf6e61717, 0xc80bb539], + [0x9d3fa7fe, 0x8049bb13], [0x5515f524, 0x8d99a313], + [0xe0d58da7, 0x7825c6e9], [0x418e29c0, 0xe3561342], + [0x7416cac5, 0xaca48424], [0xdcce8926, 0xa88eee40], + [0x806afb9f, 0x16acedbf], [0x533d7715, 0x63a675c7], + [0x9698c34e, 0x4246145d], [0x1b244e4f, 0xe6da10bb], + [0x9cb72828, 0x6e5768db], [0xbb12f51c, 0xf7add79d], + [0xaceafb2b, 0x796afb67], [0x779c4e41, 0x22f96d7d], + [0xa48dbeff, 0x91c44711], [0x43504cdd, 0x7cb08d4f], + [0xfa7ed628, 0x2559f274], [0x1a884c3b, 0x74ed2033], + [0x0e726609, 0xfea893aa], [0x716cd1a6, 0x7f9e5fe5], + [0xc67873c7, 0x4bcad23c], [0xcbb64779, 0x2e4aa2e9], + [0x0462bcc0, 0x143db54f], [0x600a7566, 0xac4441c0], + [0x0a6b335a, 0x5c7ecab2], [0xfd76b8da, 0xc4ce6db7], + [0xbc91a726, 0x851c528f], [0x818d13eb, 0x1ca36b12], + [0x9885a5ac, 0x3a098516], [0x61e7242f, 0x1064826f], + [0xd4f7d4b9, 0x3f6f1a22], [0x72c18cf0, 0x82db9137], + [0xcf2cba90, 0xd96ad75d], [0xaf12f199, 0xcd01e204], + [0x00e2abb8, 0x78b39f3c], [0xaf0f9b9b, 0xab02f718], + [0xa7e5d223, 0x20b44deb], [0x77f727b5, 0xd86aa4b8], + [0x20d6a9c6, 0xaf7ac000], [0x90130c05, 0x5d3eda6c], + [0x8b7ac2e7, 0xb14e65da], [0x774c7459, 0x5b5d2e94], + [0xc60a6f87, 0xeb5c9dc6], [0x06b40033, 0x4d4aeb64], + [0xc49eb9ac, 0x01056963], [0x451f30a4, 0xf72585aa], + [0x90bc8094, 0x0b7fc921], [0xe8a1e238, 0x940d40bc], + [0xdf8d4143, 0x078c77d7], [0x79f5acbf, 0x02cc2063], + [0xf0972287, 0x62b66ca1], [0x8294d25d, 0xf0334623], + [0x32bd8c07, 0xe9ad0dca], [0x52d73cc5, 0x2af83f6a], + [0xd5789257, 0xd00fdd3f], [0x0ed4805f, 0x86d2e042], + [0xa8938871, 0x2a451727], [0x4fe809dd, 0xfc0fcea4], + [0x54bdfa74, 0xf74ad2e4], [0xcc50139c, 0x27d182f7], + [0x094bcb80, 0x11882d86], [0x3e2e15be, 0x2eb487ce], + [0xb1cf95c0, 0x482ed5aa], [0x3a73f950, 0x65b816e9], + [0x47678dd2, 0xe0cf3744], [0x259d2212, 0xe49211a7], + [0xf496636f, 0x0eb8d146], [0x0f841214, 0x60037c21], + [0xc9216300, 0x9b36d1fc], [0x01dc3c91, 0x59cc681e], + [0xacda8e5f, 0x06b3a4fd], [0x5d04a561, 0x59b8a3e1], + [0x2f1023a8, 0xaacaf5e2], [0xa7a2a592, 0x60383267], + [0x5685f710, 0xefd7fe80], [0x3063f740, 0x49f2378c], + [0xb5c2bba3, 0xa782e19a], [0xcccdcd9a, 0x79597cb9], + [0x234fba54, 0xd9339f83], [0x65b7823a, 0x457a49ff], + [0x4a5add23, 0xcf7cc6a9], [0xc1e77ed1, 0xba27098d], + [0x1f8c189e, 0x2f5b8023], [0xaf2fffcd, 0x8293128e], + [0x5848ec7b, 0x61158ff8], [0xe0ec6586, 0x0f237678], + [0x0b5589ee, 0xd278bf8c], [0xd0fb87e3, 0x3de30b7d], + [0xc1a930c4, 0x123d49c4], [0x9ab971f8, 0xa838c0af], + [0xfa27b840, 0x9f7e503b], [0x816429d4, 0xc27f0e83], + [0x41212e19, 0xd43f3cbc], [0x0fdf2e66, 0xca39edbd], + [0x0d66bf17, 0xac6591b4], [0x326dbfd5, 0x75333b1b], + [0xdd01e462, 0x83b73d69], [0xcdbdd110, 0x1da44770], + [0xd90b13ed, 0xb7baf1f0], [0xcc0dd031, 0x1f41c7de], + [0xc89a5ccb, 0x5cb1abc7], [0x1f2accd5, 0xc5297bac], + [0x1475293b, 0x024435b5], [0xf13cdd2c, 0xb3ee4315], + [0x8eb6760a, 0xc108d18a], [0x39e5cfd9, 0x5c0f03a8], + [0xb603bb83, 0xf7a6528f], [0x4d68a935, 0x38ad5d4d], + [0x9aace8ef, 0xb187547d], [0xced0a49c, 0x9c88f96e], + [0x6fe5277e, 0x9a37a69b], [0x5d0c42d8, 0x98e64709], + [0x6f3b089c, 0x2dd85892], [0xa1353dae, 0x16b4f0b1], + [0xadbea3a8, 0xf2aeb5d2], [0xcdd96818, 0x7ee6de2c], + [0x94e2c842, 0xd63d566d], [0x1df860c9, 0x3271c625] ); 1; @@ -141,12 +141,10 @@ if ($what eq 'c') { print OUT "#include <inttypes.h>\n"; print OUT "#include <ctype.h>\n"; print OUT "#include \"nasmlib.h\"\n"; + print OUT "#include \"hashtbl.h\"\n"; print OUT "#include \"preproc.h\"\n"; print OUT "\n"; - print OUT "#define rot(x,y) (((uint32_t)(x) << (y))+((uint32_t)(x) >> (32-(y))))\n"; - print OUT "\n"; - # Note that this is global. printf OUT "const char * const pp_directives[%d] = {\n", scalar(@pptok); foreach $d (@pptok) { @@ -180,22 +178,18 @@ if ($what eq 'c') { } print OUT " };\n"; - print OUT " uint32_t k1 = 0, k2 = 0;\n"; - print OUT " uint8_t c;\n"; + print OUT " uint32_t k1, k2;\n"; + print OUT " uint64_t crc;\n"; # For correct overflow behavior, "ix" should be unsigned of the same # width as the hash arrays. print OUT " uint16_t ix;\n"; - print OUT " const char *p = token;\n"; print OUT "\n"; - print OUT " while ((c = *p++) != 0) {\n"; - print OUT " uint32_t kn1, kn2;\n"; - print OUT " c |= 0x20; /* convert to lower case */\n"; - printf OUT " kn1 = rot(k1,%2d)^(rot(k2,%2d) + c);\n", ${$sv}[0], ${$sv}[1]; - printf OUT " kn2 = rot(k2,%2d)^(rot(k1,%2d) + c);\n", ${$sv}[2], ${$sv}[3]; - print OUT " k1 = kn1; k2 = kn2;\n"; - print OUT " }\n"; - print OUT "\n"; + printf OUT " crc = crc64i(UINT64_C(0x%08x%08x), token);\n", + $$sv[0], $$sv[1]; + print OUT " k1 = (uint32_t)crc;\n"; + print OUT " k2 = (uint32_t)(crc >> 32);\n"; + print OUT "\n"; printf OUT " ix = hash1[k1 & 0x%x] + hash2[k2 & 0x%x];\n", $n-1, $n-1; printf OUT " if (ix >= %d)\n", scalar(@pptok); print OUT " return PP_INVALID;\n"; @@ -170,12 +170,10 @@ if ($output eq 'h') { print "#include <string.h>\n"; print "#include \"nasm.h\"\n"; + print "#include \"hashtbl.h\"\n"; print "#include \"insns.h\"\n"; print "\n"; - print "#define rot(x,y) (((uint32_t)(x) << (y))+((uint32_t)(x) >> (32-(y))))\n"; - print "\n"; - # These somewhat odd sizes and ordering thereof are due to the # relative ranges of the types; this makes it fit in 16 bytes on # 64-bit machines and 12 bytes on 32-bit machines. @@ -215,20 +213,17 @@ if ($output eq 'h') { } print " };\n"; - print " uint32_t k1 = 0, k2 = 0;\n"; - print " uint8_t c;\n"; + print " uint32_t k1, k2;\n"; + print " uint64_t crc;\n"; # For correct overflow behavior, "ix" should be unsigned of the same # width as the hash arrays. print " uint16_t ix;\n"; print " const struct tokendata *data;\n"; - print " const char *p = token;\n"; print "\n"; - - print " while ((c = *p++) != 0) {\n"; - printf " uint32_t kn1 = rot(k1,%2d)^(rot(k2,%2d) + c);\n", ${$sv}[0], ${$sv}[1]; - printf " uint32_t kn2 = rot(k2,%2d)^(rot(k1,%2d) + c);\n", ${$sv}[2], ${$sv}[3]; - print " k1 = kn1; k2 = kn2;\n"; - print " }\n"; + printf " crc = crc64(UINT64_C(0x%08x%08x), token);\n", + $$sv[0], $$sv[1]; + print " k1 = (uint32_t)crc;\n"; + print " k2 = (uint32_t)(crc >> 32);\n"; print "\n"; printf " ix = hash1[k1 & 0x%x] + hash2[k2 & 0x%x];\n", $n-1, $n-1; printf " if (ix >= %d)\n", scalar(@tokendata); |