summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2007-10-02 17:40:00 -0700
committerH. Peter Anvin <hpa@zytor.com>2007-10-02 17:40:00 -0700
commita59795c9860a9a31e6ccf3555ef0e0ca04a0dd87 (patch)
tree608679c4a8021e3e2e28644d1e3059a5e0091e4c
parent17394a7d8e3240c6dafddab7725d953904208e5a (diff)
downloadnasm-a59795c9860a9a31e6ccf3555ef0e0ca04a0dd87.tar.gz
Use the crc64 we already use as the perfect hash function prehash
Use the same crc64 that we already use for the symbol table hash as the perfect hash function prehash. We appear to get radically faster convergence this way, and the crc64 is probably *faster*, since the table likely to be resident in memory.
-rw-r--r--crc64.c6
-rw-r--r--hashtbl.c4
-rw-r--r--hashtbl.h6
-rw-r--r--perllib/crc64.ph158
-rwxr-xr-xperllib/gensv.pl18
-rw-r--r--perllib/phash.ph63
-rw-r--r--perllib/random_sv_vectors.ph359
-rwxr-xr-xpptok.pl22
-rwxr-xr-xtokhash.pl19
9 files changed, 465 insertions, 190 deletions
diff --git a/crc64.c b/crc64.c
index be9a15bc..da41e7db 100644
--- a/crc64.c
+++ b/crc64.c
@@ -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) {
diff --git a/hashtbl.c b/hashtbl.c
index cefd37fe..cbe2a1b9 100644
--- a/hashtbl.c
+++ b/hashtbl.c
@@ -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;
diff --git a/hashtbl.h b/hashtbl.h
index a5211414..c8f23bd4 100644
--- a/hashtbl.h
+++ b/hashtbl.h
@@ -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;
diff --git a/pptok.pl b/pptok.pl
index a835bf3e..f918e356 100755
--- a/pptok.pl
+++ b/pptok.pl
@@ -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";
diff --git a/tokhash.pl b/tokhash.pl
index 739172ce..2265bd0e 100755
--- a/tokhash.pl
+++ b/tokhash.pl
@@ -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);