Google Git
Sign in
kernel / pub / scm / libs / libucd / libucd / 935231582df16d2e73c9de98078d82d71cd392e2 / . / perfect / perfhex.c
blob: 13fd76bff4c89141f17a8a4f7ee7e231fe694928 [file] [log] [blame]
/*
------------------------------------------------------------------------------
perfhex.c: code to generate code for a hash for perfect hashing.
(c) Bob Jenkins, December 31 1999
You may use this code in any way you wish, and it is free. No warranty.
I hereby place this in the public domain.
Source is http://burtleburtle.net/bob/c/perfhex.c
The task of this file is to do the minimal amount of mixing needed to
find distinct (a,b) for each key when each key is a distinct uint32_t. That
means trying all possible ways to mix starting with the fastest. The
output is those (a,b) pairs and code in the *final* structure for producing
those pairs.
------------------------------------------------------------------------------
*/
#ifndef STANDARD
#include "standard.h"
#endif
#ifndef LOOKUPA
#include "lookupa.h"
#endif
#ifndef RECYCLE
#include "recycle.h"
#endif
#ifndef PERFECT
#include "perfect.h"
#endif
/*
* Find a perfect hash when there is only one key. Zero instructions.
* Hint: the one key always hashes to 0
*/
static void hexone(key *keys, gencode *final)
{
/* 1 key: the hash is always 0 */
keys->a_k = 0;
keys->b_k = 0;
final->used = 1;
sprintf(final->line[0], " uint32_t rsl = 0;\n"); /* h1a: 37 */
}
/*
* Find a perfect hash when there are only two keys. Max 2 instructions.
* There exists a bit that is different for the two keys. Test it.
* Note that a perfect hash of 2 keys is automatically minimal.
*/
static void hextwo(key *keys, gencode *final)
{
uint32_t a = keys->hash_k;
uint32_t b = keys->next_k->hash_k;
uint32_t i;
if (a == b)
{
printf("fatal error: duplicate keys\n");
exit(SUCCESS);
}
final->used = 1;
/* one instruction */
if ((a&1) != (b&1))
{
sprintf(final->line[0], " uint32_t rsl = (val & 1);\n"); /* h2a: 3,4 */
return;
}
/* two instructions */
for (i=0; i<32; ++i)
{
if ((a&((uint32_t)1<<i)) != (b&((uint32_t)1<<i))) break;
}
/* h2b: 4,6 */
sprintf(final->line[0], " uint32_t rsl = ((val << %"PRId32") & 1);\n", i);
}
/*
* find the value to xor to a and b and c to make none of them 3
* assert, (a,b,c) are three distinct values in (0,1,2,3).
*/
static uint32_t find_adder(uint32_t a, uint32_t b, uint32_t c)
{
return (a^b^c^3);
}
/*
* Find a perfect hash when there are only three keys. Max 6 instructions.
*
* keys a,b,c.
* There exists bit i such that a[i] != b[i].
* Either c[i] != a[i] or c[i] != b[i], assume c[i] != a[i].
* There exists bit j such that b[j] != c[j]. Note i != j.
* Final hash should be no longer than val[i]^val[j].
*
* A minimal perfect hash needs to xor one of 0,1,2,3 afterwards to cause
* the hole to land on 3. find_adder() finds that constant
*/
static void hexthree(key *keys, gencode *final, hashform *form)
{
uint32_t a = keys->hash_k;
uint32_t b = keys->next_k->hash_k;
uint32_t c = keys->next_k->next_k->hash_k;
uint32_t i,j,x,y,z;
final->used = 1;
if (a == b || a == c || b == c)
{
printf("fatal error: duplicate keys\n");
exit(SUCCESS);
}
/* one instruction */
x = a&3;
y = b&3;
z = c&3;
if (x != y && x != z && y != z)
{
if (form->perfect == NORMAL_HP || (x != 3 && y != 3 && z != 3))
{
/* h3a: 0,1,2 */
sprintf(final->line[0], " uint32_t rsl = (val & 3);\n");
}
else
{
/* h3b: 0,3,2 */
sprintf(final->line[0], " uint32_t rsl = ((val & 3) ^ %d);\n",
find_adder(x,y,z));
}
return;
}
x = a>>(32-2);
y = b>>(32-2);
z = c>>(32-2);
if (x != y && x != z && y != z)
{
if (form->perfect == NORMAL_HP || (x != 3 && y != 3 && z != 3))
{
/* h3c: 3fffffff, 7fffffff, bfffffff */
sprintf(final->line[0], " uint32_t rsl = (val >> %"PRId32");\n", (uint32_t)(32-2));
}
else
{
/* h3d: 7fffffff, bfffffff, ffffffff */
sprintf(final->line[0], " uint32_t rsl = ((val >> %"PRId32") ^ %"PRId32");\n",
(uint32_t)(32-2), find_adder(x,y,z));
}
return;
}
/* two instructions */
for (i=0; i<final->highbit; ++i)
{
x = (a>>i)&3;
y = (b>>i)&3;
z = (c>>i)&3;
if (x != y && x != z && y != z)
{
if (form->perfect == NORMAL_HP || (x != 3 && y != 3 && z != 3))
{
/* h3e: ffff3fff, ffff7fff, ffffbfff */
sprintf(final->line[0], " uint32_t rsl = ((val >> %"PRId32") & 3);\n", i);
}
else
{
/* h3f: ffff7fff, ffffbfff, ffffffff */
sprintf(final->line[0], " uint32_t rsl = (((val >> %"PRId32") & 3) ^ %"PRId32");\n", i,
find_adder(x,y,z));
}
return;
}
}
/* three instructions */
for (i=0; i<=final->highbit; ++i)
{
x = (a+(a>>i))&3;
y = (b+(b>>i))&3;
z = (c+(c>>i))&3;
if (x != y && x != z && y != z)
{
if (form->perfect == NORMAL_HP || (x != 3 && y != 3 && z != 3))
{
/* h3g: 0x000, 0x001, 0x100 */
sprintf(final->line[0], " uint32_t rsl = ((val+(val>>%"PRId32"))&3);\n", i);
}
else
{
/* h3h: 0x001, 0x100, 0x101 */
sprintf(final->line[0], " uint32_t rsl = (((val+(val>>%"PRId32"))&3)^%"PRId32");\n", i,
find_adder(x,y,z));
}
return;
}
}
/*
* Four instructions: I can prove this will always work.
*
* If the three values are distinct, there are two bits which
* distinguish them. Choose the two such bits that are closest together.
* If those bits are values 001 and 100 for those three values,
* then there either aren't any bits in between
* or the in-between bits aren't valued 001, 110, 100, 011, 010, or 101,
* because that would violate the closest-together assumption.
* So any in-between bits must be 000 or 111, and of 000 and 111 with
* the distinguishing bits won't cause them to stop being distinguishing.
*/
for (i=final->lowbit; i<=final->highbit; ++i)
{
for (j=i; j<=final->highbit; ++j)
{
x = ((a>>i)^(a>>j))&3;
y = ((b>>i)^(b>>j))&3;
z = ((c>>i)^(c>>j))&3;
if (x != y && x != z && y != z)
{
if (form->perfect == NORMAL_HP || (x != 3 && y != 3 && z != 3))
{
/* h3i: 0x00, 0x04, 0x10 */
sprintf(final->line[0],
" uint32_t rsl = (((val>>%"PRId32") ^ (val>>%"PRId32")) & 3);\n", i, j);
}
else
{
/* h3j: 0x04, 0x10, 0x14 */
sprintf(final->line[0],
" uint32_t rsl = ((((val>>%"PRId32") ^ (val>>%"PRId32")) & 3) ^ %"PRId32");\n",
i, j, find_adder(x,y,z));
}
return;
}
}
}
printf("fatal error: hexthree\n");
exit(SUCCESS);
}
/*
* Check that a,b,c,d are some permutation of 0,1,2,3
* Assume that a,b,c,d are all have values less than 32.
*/
static int testfour(uint32_t a, uint32_t b, uint32_t c, uint32_t d)
{
uint32_t mask = (1<<a)^(1<<b)^(1<<c)^(1<<d);
return (mask == 0xf);
}
/*
* Find a perfect hash when there are only four keys. Max 10 instructions.
* Note that a perfect hash for 4 keys will automatically be minimal.
*/
static void hexfour(key *keys, gencode *final)
{
uint32_t a = keys->hash_k;
uint32_t b = keys->next_k->hash_k;
uint32_t c = keys->next_k->next_k->hash_k;
uint32_t d = keys->next_k->next_k->next_k->hash_k;
uint32_t w,x,y,z;
uint32_t i,j,k;
if (a==b || a==c || a==d || b==c || b==d || c==d)
{
printf("fatal error: Duplicate keys\n");
exit(SUCCESS);
}
final->used = 1;
/* one instruction */
if ((final->diffbits & 3) == 3)
{
w = a&3;
x = b&3;
y = c&3;
z = d&3;
if (testfour(w,x,y,z))
{
sprintf(final->line[0], " uint32_t rsl = (val & 3);\n"); /* h4a: 0,1,2,3 */
return;
}
}
if (((final->diffbits >> (32-2)) & 3) == 3)
{
w = a>>(32-2);
x = b>>(32-2);
y = c>>(32-2);
z = d>>(32-2);
if (testfour(w,x,y,z))
{ /* h4b: 0fffffff, 4fffffff, 8fffffff, cfffffff */
sprintf(final->line[0], " uint32_t rsl = (val >> %"PRId32");\n", (uint32_t)(32-2));
return;
}
}
/* two instructions */
for (i=final->lowbit; i<final->highbit; ++i)
{
if (((final->diffbits >> i) & 3) == 3)
{
w = (a>>i)&3;
x = (b>>i)&3;
y = (c>>i)&3;
z = (d>>i)&3;
if (testfour(w,x,y,z))
{ /* h4c: 0,2,4,6 */
sprintf(final->line[0], " uint32_t rsl = ((val >> %"PRId32") & 3);\n", i);
return;
}
}
}
/* three instructions (linear with the number of diffbits) */
if ((final->diffbits & 3) != 0)
{
for (i=final->lowbit; i<=final->highbit; ++i)
{
if (((final->diffbits >> i) & 3) != 0)
{
w = (a+(a>>i))&3;
x = (b+(b>>i))&3;
y = (c+(c>>i))&3;
z = (d+(d>>i))&3;
if (testfour(w,x,y,z))
{ /* h4d: 0,1,2,4 */
sprintf(final->line[0],
" uint32_t rsl = ((val + (val >> %"PRId32")) & 3);\n", i);
return;
}
w = (a-(a>>i))&3;
x = (b-(b>>i))&3;
y = (c-(c>>i))&3;
z = (d-(d>>i))&3;
if (testfour(w,x,y,z))
{ /* h4e: 0,1,3,5 */
sprintf(final->line[0],
" uint32_t rsl = ((val - (val >> %"PRId32")) & 3);\n", i);
return;
}
/* h4f: ((val>>k)-val)&3: redundant with h4e */
w = (a^(a>>i))&3;
x = (b^(b>>i))&3;
y = (c^(c>>i))&3;
z = (d^(d>>i))&3;
if (testfour(w,x,y,z))
{ /* h4g: 3,4,5,8 */
sprintf(final->line[0],
" uint32_t rsl = ((val ^ (val >> %"PRId32")) & 3);\n", i);
return;
}
}
}
}
/* four instructions (linear with the number of diffbits) */
if ((final->diffbits & 3) != 0)
{
for (i=final->lowbit; i<=final->highbit; ++i)
{
if ((((final->diffbits >> i) & 1) != 0) &&
((final->diffbits & 2) != 0))
{
w = (a&3)^((a>>i)&1);
x = (b&3)^((b>>i)&1);
y = (c&3)^((c>>i)&1);
z = (d&3)^((d>>i)&1);
if (testfour(w,x,y,z))
{ /* h4h: 1,2,6,8 */
sprintf(final->line[0],
" uint32_t rsl = ((val & 3) ^ ((val >> %"PRId32") & 1));\n", i);
return;
}
w = (a&2)^((a>>i)&1);
x = (b&2)^((b>>i)&1);
y = (c&2)^((c>>i)&1);
z = (d&2)^((d>>i)&1);
if (testfour(w,x,y,z))
{ /* h4i: 1,2,8,a */
sprintf(final->line[0],
" uint32_t rsl = ((val & 2) ^ ((val >> %"PRId32") & 1));\n", i);
return;
}
}
if ((((final->diffbits >> i) & 2) != 0) &&
((final->diffbits & 1) != 0))
{
w = (a&3)^((a>>i)&2);
x = (b&3)^((b>>i)&2);
y = (c&3)^((c>>i)&2);
z = (d&3)^((d>>i)&2);
if (testfour(w,x,y,z))
{ /* h4j: 0,1,3,4 */
sprintf(final->line[0],
" uint32_t rsl = ((val & 3) ^ ((val >> %"PRId32") & 2));\n", i);
return;
}
w = (a&1)^((a>>i)&2);
x = (b&1)^((b>>i)&2);
y = (c&1)^((c>>i)&2);
z = (d&1)^((d>>i)&2);
if (testfour(w,x,y,z))
{ /* h4k: 1,4,7,8 */
sprintf(final->line[0],
" uint32_t rsl = ((val & 1) ^ ((val >> %"PRId32") & 2));\n", i);
return;
}
}
}
}
/* four instructions (quadratic in the number of diffbits) */
for (i=final->lowbit; i<=final->highbit; ++i)
{
if (((final->diffbits >> i) & 1) == 1)
{
for (j=final->lowbit; j<=final->highbit; ++j)
{
if (((final->diffbits >> j) & 3) != 0)
{
/* test + */
w = ((a>>i)+(a>>j))&3;
x = ((b>>i)+(a>>j))&3;
y = ((c>>i)+(a>>j))&3;
z = ((d>>i)+(a>>j))&3;
if (testfour(w,x,y,z))
{ /* h4l: testcase? */
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") + (val >> %"PRId32")) & 3);\n",
i, j);
return;
}
/* test - */
w = ((a>>i)-(a>>j))&3;
x = ((b>>i)-(a>>j))&3;
y = ((c>>i)-(a>>j))&3;
z = ((d>>i)-(a>>j))&3;
if (testfour(w,x,y,z))
{ /* h4m: testcase? */
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") - (val >> %"PRId32")) & 3);\n",
i, j);
return;
}
/* test ^ */
w = ((a>>i)^(a>>j))&3;
x = ((b>>i)^(a>>j))&3;
y = ((c>>i)^(a>>j))&3;
z = ((d>>i)^(a>>j))&3;
if (testfour(w,x,y,z))
{ /* h4n: testcase? */
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") ^ (val >> %"PRId32")) & 3);\n",
i, j);
return;
}
}
}
}
}
/* five instructions (quadratic in the number of diffbits) */
for (i=final->lowbit; i<=final->highbit; ++i)
{
if (((final->diffbits >> i) & 1) != 0)
{
for (j=final->lowbit; j<=final->highbit; ++j)
{
if (((final->diffbits >> j) & 3) != 0)
{
w = ((a>>j)&3)^((a>>i)&1);
x = ((b>>j)&3)^((b>>i)&1);
y = ((c>>j)&3)^((c>>i)&1);
z = ((d>>j)&3)^((d>>i)&1);
if (testfour(w,x,y,z))
{ /* h4o: 0,4,8,a */
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") & 3) ^ ((val >> %"PRId32") & 1));\n",
j, i);
return;
}
w = ((a>>j)&2)^((a>>i)&1);
x = ((b>>j)&2)^((b>>i)&1);
y = ((c>>j)&2)^((c>>i)&1);
z = ((d>>j)&2)^((d>>i)&1);
if (testfour(w,x,y,z))
{ /* h4p: 0x04, 0x08, 0x10, 0x14 */
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") & 2) ^ ((val >> %"PRId32") & 1));\n",
j, i);
return;
}
}
if (i==0)
{
w = ((a>>j)^(a<<1))&3;
x = ((b>>j)^(b<<1))&3;
y = ((c>>j)^(c<<1))&3;
z = ((d>>j)^(d<<1))&3;
}
else
{
w = ((a>>j)&3)^((a>>(i-1))&2);
x = ((b>>j)&3)^((b>>(i-1))&2);
y = ((c>>j)&3)^((c>>(i-1))&2);
z = ((d>>j)&3)^((d>>(i-1))&2);
}
if (testfour(w,x,y,z))
{
if (i==0) /* h4q: 0,4,5,8 */
{
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") ^ (val << 1)) & 3);\n",
j);
}
else if (i==1) /* h4r: 0x01,0x09,0x0b,0x10 */
{
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") & 3) ^ (val & 2));\n",
j);
}
else /* h4s: 0,2,6,8 */
{
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") & 3) ^ ((val >> %"PRId32") & 2));\n",
j, (i-1));
}
return;
}
w = ((a>>j)&1)^((a>>i)&2);
x = ((b>>j)&1)^((b>>i)&2);
y = ((c>>j)&1)^((c>>i)&2);
z = ((d>>j)&1)^((d>>i)&2);
if (testfour(w,x,y,z)) /* h4t: 0x20,0x14,0x10,0x06 */
{
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") & 1) ^ ((val >> %"PRId32") & 2));\n",
j, i);
return;
}
}
}
}
/*
* OK, bring out the big guns.
* There exist three bits i,j,k which distinguish a,b,c,d.
* i^(j<<1)^(k*q) is guaranteed to work for some q in {0,1,2,3},
* proven by exhaustive search of all (8 choose 4) cases.
* Find three such bits and try the 4 cases.
* Linear with the number of diffbits.
* Some cases below may duplicate some cases above. I did it that way
* so that what is below is guaranteed to work, no matter what was
* attempted above.
* The generated hash is at most 10 instructions.
*/
for (i=final->lowbit; i<32; ++i)
{
y = (c>>i)&1;
z = (d>>i)&1;
if (y != z)
break;
}
for (j=final->lowbit; j<32; ++j)
{
x = ((b>>i)&1)^(((b>>j)&1)<<1);
y = ((c>>i)&1)^(((c>>j)&1)<<1);
z = ((d>>i)&1)^(((d>>j)&1)<<1);
if (x != y && x != z && y != z)
break;
}
for (k=final->lowbit; k<32; ++k)
{
w = ((a>>i)&1)^(((a>>j)&1)<<1)^(((a>>k)&1)<<2);
x = ((b>>i)&1)^(((b>>j)&1)<<1)^(((b>>k)&1)<<2);
y = ((c>>i)&1)^(((c>>j)&1)<<1)^(((c>>k)&1)<<2);
z = ((d>>i)&1)^(((d>>j)&1)<<1)^(((d>>k)&1)<<2);
if (w != x && w != y && w != z && x != y && x != z && y != z)
break;
}
/* Assert: bits i,j,k were found which distinguish a,b,c,d */
if (i==32 || j==32 || k==32)
{
printf("Fatal error: hexfour(), i %"PRId32" j %"PRId32" k %"PRId32"\n", i,j,k);
exit(SUCCESS);
}
/* now try the four cases */
{
uint32_t m,n,o,p;
/* if any bit has two 1s and two 0s, make that bit o */
if (((a>>i)&1)+((b>>i)&1)+((c>>i)&1)+((d>>i)&1) != 2)
{ m=j; n=k; o=i; }
else if (((a>>j)&1)+((b>>j)&1)+((c>>j)&1)+((d>>j)&1) != 2)
{ m=i; n=k; o=j; }
else
{ m=i; n=j; o=k; }
if (m > n) {p=m; m=n; n=p; } /* guarantee m < n */
/* printf("m %"PRId32" n %"PRId32" o %"PRId32" %"PRId32" %"PRId32" %"PRId32" %"PRId32"\n", m, n, o, w,x,y,z); */
/* seven instructions, multiply bit o by 1 */
w = (((a>>m)^(a>>o))&1)^((a>>(n-1))&2);
x = (((b>>m)^(b>>o))&1)^((b>>(n-1))&2);
y = (((c>>m)^(c>>o))&1)^((c>>(n-1))&2);
z = (((d>>m)^(d>>o))&1)^((d>>(n-1))&2);
if (testfour(w,x,y,z))
{
if (m>o) {p=m; m=o; o=p;} /* make sure m < o and m < n */
if (m==0) /* 0,2,8,9 */
{
sprintf(final->line[0],
" uint32_t rsl = (((val^(val>>%"PRId32"))&1)^((val>>%"PRId32")&2));\n", o, n-1);
}
else /* 0x00,0x04,0x10,0x12 */
{
sprintf(final->line[0],
" uint32_t rsl = ((((val>>%"PRId32") ^ (val>>%"PRId32")) & 1) ^ ((val>>%"PRId32") & 2));\n",
m, o, n-1);
}
return;
}
/* six to seven instructions, multiply bit o by 2 */
w = ((a>>m)&1)^((((a>>n)^(a>>o))&1)<<1);
x = ((b>>m)&1)^((((b>>n)^(b>>o))&1)<<1);
y = ((c>>m)&1)^((((c>>n)^(c>>o))&1)<<1);
z = ((d>>m)&1)^((((d>>n)^(d>>o))&1)<<1);
if (testfour(w,x,y,z))
{
if (m==o-1) {p=n; n=o; o=p;} /* make m==n-1 if possible */
if (m==0) /* 0,1,5,8 */
{
sprintf(final->line[0],
" uint32_t rsl = ((val & 1) ^ (((val>>%"PRId32") ^ (val>>%"PRId32")) & 2));\n",
n-1, o-1);
}
else if (o==0) /* 0x00,0x04,0x05,0x10 */
{
sprintf(final->line[0],
" uint32_t rsl = (((val>>%"PRId32") & 2) ^ (((val>>%"PRId32") ^ val) & 1));\n",
m-1, n);
}
else /* 0x00,0x02,0x0a,0x10 */
{
sprintf(final->line[0],
" uint32_t rsl = (((val>>%"PRId32") & 1) ^ (((val>>%"PRId32") ^ (val>>%"PRId32")) & 2));\n",
m, n-1, o-1);
}
return;
}
/* multiplying by 3 is a pain: seven or eight instructions */
w = (((a>>m)&1)^((a>>(n-1))&2))^((a>>o)&1)^(((a>>o)&1)<<1);
x = (((b>>m)&1)^((b>>(n-1))&2))^((b>>o)&1)^(((b>>o)&1)<<1);
y = (((c>>m)&1)^((c>>(n-1))&2))^((c>>o)&1)^(((c>>o)&1)<<1);
z = (((d>>m)&1)^((d>>(n-1))&2))^((d>>o)&1)^(((d>>o)&1)<<1);
if (testfour(w,x,y,z))
{
final->used = 2;
sprintf(final->line[0], " uint32_t b = (val >> %"PRId32") & 1;\n", o);
if (m==o-1 && m==0) /* 0x02,0x10,0x11,0x18 */
{
sprintf(final->line[1],
" uint32_t rsl = ((val & 3) ^ ((val >> %"PRId32") & 2) ^ b);\n", n-1);
}
else if (m==o-1) /* 0,4,6,c */
{
sprintf(final->line[1],
" uint32_t rsl = (((val >> %"PRId32") & 3) ^ ((val >> %"PRId32") & 2) ^ b);\n",
m, n-1);
}
else if (m==n-1 && m==0) /* 02,0a,0b,18 */
{
sprintf(final->line[1],
" uint32_t rsl = ((val & 3) ^ b ^ (b << 1));\n");
}
else if (m==n-1) /* 0,2,4,8 */
{
sprintf(final->line[1],
" uint32_t rsl = (((val >> %"PRId32") & 3) ^ b ^ (b << 1));\n", m);
}
else if (o==n-1 && m==0) /* h4am: not reached */
{
sprintf(final->line[1],
" uint32_t rsl = ((val & 1) ^ ((val >> %"PRId32") & 3) ^ (b <<1 ));\n",
o);
}
else if (o==n-1) /* 0x00,0x02,0x08,0x10 */
{
sprintf(final->line[1],
" uint32_t rsl = (((val >> %"PRId32") & 1) ^ ((val >> %"PRId32") & 3) ^ (b << 1));\n",
m, o);
}
else if ((m != o-1) && (m != n-1) && (o != m-1) && (o != n-1))
{
final->used = 3;
sprintf(final->line[0], " uint32_t newval = val & 0x%"PRIx32";\n",
(((uint32_t)1<<m)^((uint32_t)1<<n)^((uint32_t)1<<o)));
if (o==0) /* 0x00,0x01,0x04,0x10 */
{
sprintf(final->line[1], " uint32_t b = -newval;\n");
}
else /* 0x00,0x04,0x09,0x10 */
{
sprintf(final->line[1], " uint32_t b = -(newval >> %"PRId32");\n", o);
}
if (m==0) /* 0x00,0x04,0x09,0x10 */
{
sprintf(final->line[2],
" uint32_t rsl = ((newval ^ (newval>>%"PRId32") ^ b) & 3);\n", n-1);
}
else /* 0x00,0x03,0x04,0x10 */
{
sprintf(final->line[2],
" uint32_t rsl = (((newval>>%"PRId32") ^ (newval>>%"PRId32") ^ b) & 3);\n",
m, n-1);
}
}
else if (o == m-1)
{
if (o==0) /* 0x02,0x03,0x0a,0x10 */
{
sprintf(final->line[0], " uint32_t b = (val<<1) & 2;\n");
}
else if (o==1) /* 0x00,0x02,0x04,0x10 */
{
sprintf(final->line[0], " uint32_t b = val & 2;\n");
}
else /* 0x00,0x04,0x08,0x20 */
{
sprintf(final->line[0], " uint32_t b = (val>>%"PRId32") & 2;\n", o-1);
}
if (o==0) /* 0x02,0x03,0x0a,0x10 */
{
sprintf(final->line[1],
" uint32_t rsl = ((val & 3) ^ ((val>>%"PRId32") & 1) ^ b);\n",
n);
}
else /* 0x00,0x02,0x04,0x10 */
{
sprintf(final->line[1],
" uint32_t rsl = (((val>>%"PRId32") & 3) ^ ((val>>%"PRId32") & 1) ^ b);\n",
o, n);
}
}
else /* h4ax: 10 instructions, but not reached */
{
sprintf(final->line[1],
" uint32_t rsl = (((val>>%"PRId32") & 1) ^ ((val>>%"PRId32") & 2) ^ b ^ (b<<1));\n",
m, n-1);
}
return;
}
/* five instructions, multiply bit o by 0, covered before the big guns */
w = ((a>>m)&1)^(a>>(n-1)&2);
x = ((b>>m)&1)^(b>>(n-1)&2);
y = ((c>>m)&1)^(c>>(n-1)&2);
z = ((d>>m)&1)^(d>>(n-1)&2);
if (testfour(w,x,y,z))
{ /* h4v, not reached */
sprintf(final->line[0],
" uint32_t rsl = (((val>>%"PRId32") & 1) ^ ((val>>%"PRId32") & 2));\n", m, n-1);
return;
}
}
printf("fatal error: bug in hexfour!\n");
exit(SUCCESS);
return;
}
/* test if a_k is distinct and in range for all keys */
static int testeight(key *keys, uint8_t badmask)
/* keys being hashed */
/* used for minimal perfect hashing */
{
uint8_t mask = badmask;
key *mykey;
for (mykey=keys; mykey; mykey=mykey->next_k)
{
if (bit(mask, 1<<mykey->a_k)) return FALSE;
bis(mask, 1<<mykey->a_k);
}
return TRUE;
}
/*
* Try to find a perfect hash when there are five to eight keys.
*
* We can't deterministically find a perfect hash, but there's a reasonable
* chance we'll get lucky. Give it a shot. Return TRUE if we succeed.
*/
static int hexeight(key *keys, uint32_t nkeys, gencode *final, hashform *form)
{
key *mykey; /* walk through the keys */
uint32_t i,j,k;
uint8_t badmask;
printf("hexeight\n");
/* what hash values should never be used? */
badmask = 0;
if (form->perfect == MINIMAL_HP)
{
for (i=nkeys; i<8; ++i)
bis(badmask,(1<<i));
}
/* one instruction */
for (mykey=keys; mykey; mykey=mykey->next_k)
mykey->a_k = mykey->hash_k & 7;
if (testeight(keys, badmask))
{ /* h8a */
final->used = 1;
sprintf(final->line[0], " uint32_t rsl = (val & 7);\n");
return TRUE;
}
/* two instructions */
for (i=final->lowbit; i<=final->highbit-2; ++i)
{
for (mykey=keys; mykey; mykey=mykey->next_k)
mykey->a_k = (mykey->hash_k >> i) & 7;
if (testeight(keys, badmask))
{ /* h8b */
final->used = 1;
sprintf(final->line[0], " uint32_t rsl = ((val >> %"PRId32") & 7);\n", i);
return TRUE;
}
}
/* four instructions */
for (i=final->lowbit; i<=final->highbit; ++i)
{
for (j=i+1; j<=final->highbit; ++j)
{
for (mykey=keys; mykey; mykey=mykey->next_k)
mykey->a_k = ((mykey->hash_k >> i)+(mykey->hash_k >> j)) & 7;
if (testeight(keys, badmask))
{
final->used = 1;
if (i == 0) /* h8c */
sprintf(final->line[0],
" uint32_t rsl = ((val + (val >> %"PRId32")) & 7);\n", j);
else /* h8d */
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") + (val >> %"PRId32")) & 7);\n", i, j);
return TRUE;
}
for (mykey=keys; mykey; mykey=mykey->next_k)
mykey->a_k = ((mykey->hash_k >> i)^(mykey->hash_k >> j)) & 7;
if (testeight(keys, badmask))
{
final->used = 1;
if (i == 0) /* h8e */
sprintf(final->line[0],
" uint32_t rsl = ((val ^ (val >> %"PRId32")) & 7);\n", j);
else /* h8f */
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") ^ (val >> %"PRId32")) & 7);\n", i, j);
return TRUE;
}
for (mykey=keys; mykey; mykey=mykey->next_k)
mykey->a_k = ((mykey->hash_k >> i)-(mykey->hash_k >> j)) & 7;
if (testeight(keys, badmask))
{
final->used = 1;
if (i == 0) /* h8g */
sprintf(final->line[0],
" uint32_t rsl = ((val - (val >> %"PRId32")) & 7);\n", j);
else /* h8h */
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") - (val >> %"PRId32")) & 7);\n", i, j);
return TRUE;
}
}
}
/* six instructions */
for (i=final->lowbit; i<=final->highbit; ++i)
{
for (j=i+1; j<=final->highbit; ++j)
{
for (k=j+1; k<=final->highbit; ++k)
{
for (mykey=keys; mykey; mykey=mykey->next_k)
mykey->a_k = ((mykey->hash_k >> i) +
(mykey->hash_k >> j) +
(mykey->hash_k >> k)) & 7;
if (testeight(keys, badmask))
{ /* h8i */
final->used = 1;
sprintf(final->line[0],
" uint32_t rsl = (((val >> %"PRId32") + (val >> %"PRId32") + (val >> %"PRId32")) & 7);\n",
i, j, k);
return TRUE;
}
}
}
}
return FALSE;
}
/*
* Guns aren't enough. Bring out the Bomb. Use tab[].
* This finds the initial (a,b) when we need to use tab[].
*
* We need to produce a different (a,b) every time this is called. Try all
* reasonable cases, fastest first.
*
* The initial mix (which this determines) can be filled into final starting
* at line[1]. val is set and a,b are declared. The final hash (at line[7])
* is a^tab[b] or a^scramble[tab[b]].
*
* The code will probably look like this, minus some stuff:
* val += CONSTANT;
* val ^= (val<<16);
* val += (val>>8);
* val ^= (val<<4);
* b = (val >> l) & 7;
* a = (val + (val<<m)) >> 29;
* return a^scramble[tab[b]];
* Note that *a* and tab[b] will be computed in parallel by most modern chips.
*
* final->i is the current state of the state machine.
* final->j and final->k are counters in the loops the states simulate.
*/
static void hexn(key *keys, uint32_t salt, uint32_t alen, uint32_t blen, gencode *final)
{
key *mykey;
uint32_t highbit = final->highbit;
uint32_t lowbit = final->lowbit;
uint32_t alog = ilog2(alen);
uint32_t blog = ilog2(blen);
for (;;)
{
switch(final->i)
{
case 1:
/* a = val>>30; b=val&3 */
for (mykey=keys; mykey; mykey=mykey->next_k)
{
mykey->a_k = (mykey->hash_k << (32-(highbit+1)))>>(32-alog);
mykey->b_k = (mykey->hash_k >> lowbit) & (blen-1);
}
if (lowbit == 0) /* hna */
sprintf(final->line[5], " b = (val & 0x%"PRIx32");\n",
blen-1);
else /* hnb */
sprintf(final->line[5], " b = ((val >> %"PRId32") & 0x%"PRIx32");\n",
lowbit, blen-1);
if (highbit+1 == 32) /* hnc */
sprintf(final->line[6], " a = (val >> %"PRId32");\n",
32-alog);
else /* hnd */
sprintf(final->line[6], " a = ((val << %"PRId32" ) >> %"PRId32");\n",
32-(highbit+1), 32-alog);
++final->i;
return;
case 2:
/* a = val&3; b=val>>30 */
for (mykey=keys; mykey; mykey=mykey->next_k)
{
mykey->a_k = (mykey->hash_k >> lowbit) & (alen-1);
mykey->b_k = (mykey->hash_k << (32-(highbit+1)))>>(32-blog);
}
if (highbit+1 == 32) /* hne */
sprintf(final->line[5], " b = (val >> %"PRId32");\n",
32-blog);
else /* hnf */
sprintf(final->line[5], " b = ((val << %"PRId32" ) >> %"PRId32");\n",
32-(highbit+1), 32-blog);
if (lowbit == 0) /* hng */
sprintf(final->line[6], " a = (val & 0x%"PRIx32");\n",
alen-1);
else /* hnh */
sprintf(final->line[6], " a = ((val >> %"PRId32") & 0x%"PRIx32");\n",
lowbit, alen-1);
++final->i;
return;
case 3:
/*
* cases 3,4,5:
* for (k=lowbit; k<=highbit; ++k)
* for (j=lowbit; j<=highbit; ++j)
* b = (val>>j)&3;
* a = (val<<k)>>30;
*/
final->k = lowbit;
final->j = lowbit;
++final->i;
break;
case 4:
if (!(final->j < highbit))
{
++final->i;
break;
}
for (mykey=keys; mykey; mykey=mykey->next_k)
{
mykey->b_k = (mykey->hash_k >> (final->j)) & (blen-1);
mykey->a_k = (mykey->hash_k << (32-final->k-1)) >> (32-alog);
}
if (final->j == 0) /* hni */
sprintf(final->line[5], " b = val & 0x%"PRIx32";\n",
blen-1);
else if (blog+final->j == 32) /* hnja */
sprintf(final->line[5], " b = val >> %"PRId32";\n",
final->j);
else
sprintf(final->line[5], " b = (val >> %"PRId32") & 0x%"PRIx32";\n", /* hnj */
final->j, blen-1);
if (32-final->k-1 == 0) /* hnk */
sprintf(final->line[6], " a = (val >> %"PRId32");\n",
32-alog);
else /* hnl */
sprintf(final->line[6], " a = ((val << %"PRId32") >> %"PRId32");\n",
32-final->k-1, 32-alog);
while (++final->j < highbit)
{
if (((final->diffbits>>(final->j)) & (blen-1)) > 2)
break;
}
return;
case 5:
while (++final->k < highbit)
{
if ((((final->diffbits<<(32-final->k-1))>>alog) & (alen-1)) > 0)
break;
}
if (!(final->k < highbit))
{
++final->i;
break;
}
final->j = lowbit;
final->i = 4;
break;
case 6:
/*
* cases 6,7,8:
* for (k=0; k<32-alog; ++k)
* for (j=0; j<32-blog; ++j)
* val = val+f(salt);
* val ^= (val >> 16);
* val += (val << 8);
* val ^= (val >> 4);
* b = (val >> j) & 3;
* a = (val + (val << k)) >> 30;
*/
final->k = 0;
final->j = 0;
++final->i;
break;
case 7:
/* Just do something that will surely work */
{
uint32_t addk = 0x9e3779b9*salt;
if (!(final->j <= 32-blog))
{
++final->i;
break;
}
for (mykey=keys; mykey; mykey=mykey->next_k)
{
uint32_t val = mykey->hash_k + addk;
if (final->highbit+1 - final->lowbit > 16)
val ^= (val >> 16);
if (final->highbit+1 - final->lowbit > 8)
val += (val << 8);
val ^= (val >> 4);
mykey->b_k = (val >> final->j) & (blen-1);
if (final->k == 0)
mykey->a_k = val >> (32-alog);
else
mykey->a_k = (val + (val << final->k)) >> (32-alog);
}
sprintf(final->line[1], " val += 0x%"PRIx32";\n", addk);
if (final->highbit+1 - final->lowbit > 16) /* hnm */
sprintf(final->line[2], " val ^= (val >> 16);\n");
if (final->highbit+1 - final->lowbit > 8) /* hnn */
sprintf(final->line[3], " val += (val << 8);\n");
sprintf(final->line[4], " val ^= (val >> 4);\n");
if (final->j == 0) /* hno: don't know how to reach this */
sprintf(final->line[5], " b = val & 0x%"PRIx32";\n", blen-1);
else /* hnp */
sprintf(final->line[5], " b = (val >> %"PRId32") & 0x%"PRIx32";\n",
final->j, blen-1);
if (final->k == 0) /* hnq */
sprintf(final->line[6], " a = val >> %"PRId32";\n", 32-alog);
else /* hnr */
sprintf(final->line[6], " a = (val + (val << %"PRId32")) >> %"PRId32";\n",
final->k, 32-alog);
++final->j;
return;
}
case 8:
++final->k;
if (!(final->k <= 32-alog))
{
++final->i;
break;
}
final->j = 0;
final->i = 7;
break;
case 9:
final->i = 6;
break;
}
}
}
/* find the highest and lowest bit where any key differs */
static void setlow(key *keys, gencode *final)
{
uint32_t i;
key *mykey;
uint32_t firstkey;
/* mark the interesting bits in final->mask */
final->diffbits = (uint32_t)0;
if (keys) firstkey = keys->hash_k;
for (mykey=keys; mykey!=(key *)0; mykey=mykey->next_k)
final->diffbits |= (firstkey ^ mykey->hash_k);
/* find the lowest interesting bit */
for (i=0; i<32; ++i)
if (final->diffbits & (((uint32_t)1)<<i))
break;
final->lowbit = i;
/* find the highest interesting bit */
for (i=32; --i; )
if (final->diffbits & (((uint32_t)1)<<i))
break;
final->highbit = i;
}
/*
* Initialize (a,b) when keys are integers.
*
* Normally there's an initial hash which produces a number. That hash takes
* an initializer. Changing the initializer causes the initial hash to
* produce a different (uniformly distributed) number without any extra work.
*
* Well, here we start with a number. There's no initial hash. Any mixing
* costs extra work. So we go through a lot of special cases to minimize the
* mixing needed to get distinct (a,b). For small sets of keys, it's often
* fastest to skip the final hash and produce the perfect hash from the number
* directly.
*
* The target user for this is switch statement optimization. The common case
* is 3 to 16 keys, and instruction counts matter. The competition is a
* binary tree of branches.
*
* Return TRUE if we found a perfect hash and no more work is needed.
* Return FALSE if we just did an initial hash and more work is needed.
*/
int inithex(key *keys, uint32_t nkeys, uint32_t alen, uint32_t blen, uint32_t smax, uint32_t salt, gencode *final, hashform *form)
/* list of all keys */
/* number of keys to hash */
/* (a,b) has a in 0..alen-1, a power of 2 */
/* (a,b) has b in 0..blen-1, a power of 2 */
/* maximum range of computable hash values */
/* used to initialize the hash function */
/* output, code for the final hash */
/* user directives */
{
(void)smax; /* Not used */
setlow(keys, final);
switch (nkeys)
{
case 1:
hexone(keys, final);
return TRUE;
case 2:
hextwo(keys, final);
return TRUE;
case 3:
hexthree(keys, final, form);
return TRUE;
case 4:
hexfour(keys, final);
return TRUE;
case 5: case 6: case 7: case 8:
if (salt == 1 && /* first time through */
hexeight(keys, nkeys, final, form)) /* get lucky, don't need tab[] ? */
return TRUE;
/* fall through */
default:
if (salt == 1)
{
final->used = 8;
final->i = 1;
final->j = final->k = final->l = final->m = final->n = final->o = 0;
sprintf(final->line[0], " uint32_t a, b, rsl;\n");
sprintf(final->line[1], "\n");
sprintf(final->line[2], "\n");
sprintf(final->line[3], "\n");
sprintf(final->line[4], "\n");
sprintf(final->line[5], "\n");
sprintf(final->line[6], "\n");
if (blen < USE_SCRAMBLE)
{ /* hns */
sprintf(final->line[7], " rsl = (a^tab[b]);\n");
}
else
{ /* hnt */
sprintf(final->line[7], " rsl = (a^scramble[tab[b]]);\n");
}
}
hexn(keys, salt, alen, blen, final);
return FALSE;
}
}