#!/usr/bin/perl

require 'phash.ph';

# Use SHA1 as a PRNG
use Digest::SHA1;

my $seed  = Digest::SHA1->new->add('02ada18ee1878d0cf34c88d7a79e0134');
my $randx = 1;
sub get_rand() {
    $seed->add($randx++);
    my ($v) = unpack("V", substr($seed->digest, 0, 4));
    return $v;
}

$entries = 200;

@table    = ();
%hashdata = ();

# Generate test data
for ($i = 0; $i < $entries; $i++) {
    my $key = get_rand();
    my $val = get_rand();

    $hashdata{$key} = scalar @table;
    push(@table, [$key, $val]);
}

@hashinfo = gen_perfect_hash(\%hashdata);

if (!@hashinfo) {
    die "$0: no hash found\n";
}

verify_hash_table(\%hashdata, \@hashinfo);

($n, $sv, $g) = @hashinfo;

print "#include <inttypes.h>\n\n";
print "#define UNUSED 0x5555\n\n";

print "static const int16_t hash0[$n] =\n";
print "{\n";
for ($i = 0; $i < $n; $i++) {
    my $h = ${$g}[$i*2+0];
    print "\t", defined($h) ? $h : "UNUSED", ",\n";
}
print "};\n\n";

print "static const int16_t hash1[$n] =\n";
print "{\n";
for ($i = 0; $i < $n; $i++) {
    my $h = ${$g}[$i*2+1];
   print "\t", defined($h) ? $h : "UNUSED", ",\n";
}
print "};\n\n";

print "static const uint32_t data[$entries][2] =\n";
print "{\n";
for ($i = 0; $i < $entries; $i++) {
    printf "\t{ 0x%08x, 0x%08x },\n", ${$table[$i]}[0], ${$table[$i]}[1];
}
print "};\n\n";


print  "static inline uint32_t circmul(uint32_t key, uint32_t k)\n";
print  "{\n";
print  "#if defined(__i386__) || defined(__x86_64__)\n";
print  "\tasm(\"mull %1 ; addl %%edx, %0\"\n";
print  "\t\t: \"+a\" (key)\n";
printf "\t\t: \"rm\" (k)\n", $sv;
print  "\t\t: \"edx\");\n";
print  "\treturn key;\n";
print  "#else\n";
printf "\tuint64_t m  = key * (uint64_t)k;\n", $sv;
print  "\treturn m + (m >> 32);\n";
print  "#endif\n";
print  "}\n\n";

$type = ${$sv}[0];

print  "uint32_t HASHNAME(uint32_t key)\n";
print  "{\n";
if ($type == 0) {
    printf "\tuint16_t ix = hash0[(key >> %u) & 0x%x] +\n".
	   "\t\thash1[(key >> %u) & 0x%x];\n",
	   ${$sv}[1], $n-1, ${$sv}[2], $n-1;
} else {
    if ($type == 1) {
	print  "\tuint32_t ph = key * 0x%08x;\n", ${$sv}[1];
    } elsif ($type == 2) {
	print  "\tuint32_t ph = circmul(key, 0x%08x);\n", ${$sv}[0];
    } else {
	die "$0: unknown prehash type\n";
    }
    printf "\tuint16_t ix = hash0[ph & 0x%x] + hash1[(ph >> 16) & 0x%x];\n", $n-1, $n-1;
}
printf "\tif (ix >= %d)\n", $entries;
print  "\t\treturn 0;\n";	# Error indicator
print  "\treturn (data[ix][0] == key) ? data[ix][1] : 0;\n";
print  "};\n";

print  "\n#ifdef TEST\n\n";

print  "#include <stdio.h>\n\n";

print  "int main(int argc, char *argv[])\n";
print  "{\n";
print  "\tint i;\n";
print  "\tint rv = 0;\n";
print  "\n";
print  "\t(void)argc;\n";
print  "\n";
printf "\tfor (i = 0; i < %d; i++) {\n", $entries;
print  "\t\tuint32_t v = HASHNAME(data[i][0]);\n";
print  "\t\tif (v != data[i][1]) {\n";
print  "\t\t\tfprintf(stderr, \"%s: 0x%08x -> 0x%08x should be 0x%08x\\n\",\n";
print  "\t\t\t\targv[0], data[i][0], v, data[i][1]);\n";
print  "\t\t\trv = 1;\n";
print  "\t\t};\n";
print  "\t};\n";
print  "\treturn rv;\n";
print  "}\n";

print  "\n#endif /* TEST */\n";
