diff options
Diffstat (limited to 'tools/codegen/core/perfect/perfhex.c')
| -rw-r--r-- | tools/codegen/core/perfect/perfhex.c | 1308 |
1 files changed, 0 insertions, 1308 deletions
diff --git a/tools/codegen/core/perfect/perfhex.c b/tools/codegen/core/perfect/perfhex.c deleted file mode 100644 index 9c28dc734b..0000000000 --- a/tools/codegen/core/perfect/perfhex.c +++ /dev/null @@ -1,1308 +0,0 @@ -/* ------------------------------------------------------------------------------- -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 ub4. 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(keys, final) -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], " ub4 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(keys, final) -key *keys; -gencode *final; -{ - ub4 a = keys->hash_k; - ub4 b = keys->next_k->hash_k; - ub4 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], " ub4 rsl = (val & 1);\n"); /* h2a: 3,4 */ - return; - } - - /* two instructions */ - for (i=0; i<UB4BITS; ++i) - { - if ((a&((ub4)1<<i)) != (b&((ub4)1<<i))) break; - } - /* h2b: 4,6 */ - sprintf(final->line[0], " ub4 rsl = ((val << %ld) & 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 ub4 find_adder(a,b,c) -ub4 a; -ub4 b; -ub4 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(keys, final, form) -key *keys; -gencode *final; -hashform *form; -{ - ub4 a = keys->hash_k; - ub4 b = keys->next_k->hash_k; - ub4 c = keys->next_k->next_k->hash_k; - ub4 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], " ub4 rsl = (val & 3);\n"); - } - else - { - /* h3b: 0,3,2 */ - sprintf(final->line[0], " ub4 rsl = ((val & 3) ^ %d);\n", - find_adder(x,y,z)); - } - return; - } - - x = a>>(UB4BITS-2); - y = b>>(UB4BITS-2); - z = c>>(UB4BITS-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], " ub4 rsl = (val >> %ld);\n", (ub4)(UB4BITS-2)); - } - else - { - /* h3d: 7fffffff, bfffffff, ffffffff */ - sprintf(final->line[0], " ub4 rsl = ((val >> %ld) ^ %ld);\n", - (ub4)(UB4BITS-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], " ub4 rsl = ((val >> %ld) & 3);\n", i); - } - else - { - /* h3f: ffff7fff, ffffbfff, ffffffff */ - sprintf(final->line[0], " ub4 rsl = (((val >> %ld) & 3) ^ %ld);\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], " ub4 rsl = ((val+(val>>%ld))&3);\n", i); - } - else - { - /* h3h: 0x001, 0x100, 0x101 */ - sprintf(final->line[0], " ub4 rsl = (((val+(val>>%ld))&3)^%ld);\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], - " ub4 rsl = (((val>>%ld) ^ (val>>%ld)) & 3);\n", i, j); - } - else - { - /* h3j: 0x04, 0x10, 0x14 */ - sprintf(final->line[0], - " ub4 rsl = ((((val>>%ld) ^ (val>>%ld)) & 3) ^ %ld);\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(a,b,c,d) -ub4 a; -ub4 b; -ub4 c; -ub4 d; -{ - ub4 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(keys, final) -key *keys; -gencode *final; -{ - ub4 a = keys->hash_k; - ub4 b = keys->next_k->hash_k; - ub4 c = keys->next_k->next_k->hash_k; - ub4 d = keys->next_k->next_k->next_k->hash_k; - ub4 w,x,y,z; - ub4 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], " ub4 rsl = (val & 3);\n"); /* h4a: 0,1,2,3 */ - return; - } - } - - if (((final->diffbits >> (UB4BITS-2)) & 3) == 3) - { - w = a>>(UB4BITS-2); - x = b>>(UB4BITS-2); - y = c>>(UB4BITS-2); - z = d>>(UB4BITS-2); - if (testfour(w,x,y,z)) - { /* h4b: 0fffffff, 4fffffff, 8fffffff, cfffffff */ - sprintf(final->line[0], " ub4 rsl = (val >> %ld);\n", (ub4)(UB4BITS-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], " ub4 rsl = ((val >> %ld) & 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], - " ub4 rsl = ((val + (val >> %ld)) & 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], - " ub4 rsl = ((val - (val >> %ld)) & 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], - " ub4 rsl = ((val ^ (val >> %ld)) & 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], - " ub4 rsl = ((val & 3) ^ ((val >> %ld) & 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], - " ub4 rsl = ((val & 2) ^ ((val >> %ld) & 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], - " ub4 rsl = ((val & 3) ^ ((val >> %ld) & 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], - " ub4 rsl = ((val & 1) ^ ((val >> %ld) & 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], - " ub4 rsl = (((val >> %ld) + (val >> %ld)) & 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], - " ub4 rsl = (((val >> %ld) - (val >> %ld)) & 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], - " ub4 rsl = (((val >> %ld) ^ (val >> %ld)) & 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], - " ub4 rsl = (((val >> %ld) & 3) ^ ((val >> %ld) & 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], - " ub4 rsl = (((val >> %ld) & 2) ^ ((val >> %ld) & 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], - " ub4 rsl = (((val >> %ld) ^ (val << 1)) & 3);\n", - j); - } - else if (i==1) /* h4r: 0x01,0x09,0x0b,0x10 */ - { - sprintf(final->line[0], - " ub4 rsl = (((val >> %ld) & 3) ^ (val & 2));\n", - j); - } - else /* h4s: 0,2,6,8 */ - { - sprintf(final->line[0], - " ub4 rsl = (((val >> %ld) & 3) ^ ((val >> %ld) & 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], - " ub4 rsl = (((val >> %ld) & 1) ^ ((val >> %ld) & 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<UB4BITS; ++i) - { - y = (c>>i)&1; - z = (d>>i)&1; - if (y != z) - break; - } - - for (j=final->lowbit; j<UB4BITS; ++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<UB4BITS; ++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==UB4BITS || j==UB4BITS || k==UB4BITS) - { - printf("Fatal error: hexfour(), i %ld j %ld k %ld\n", i,j,k); - exit(SUCCESS); - } - - /* now try the four cases */ - { - ub4 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 %ld n %ld o %ld %ld %ld %ld %ld\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], - " ub4 rsl = (((val^(val>>%ld))&1)^((val>>%ld)&2));\n", o, n-1); - } - else /* 0x00,0x04,0x10,0x12 */ - { - sprintf(final->line[0], - " ub4 rsl = ((((val>>%ld) ^ (val>>%ld)) & 1) ^ ((val>>%ld) & 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], - " ub4 rsl = ((val & 1) ^ (((val>>%ld) ^ (val>>%ld)) & 2));\n", - n-1, o-1); - } - else if (o==0) /* 0x00,0x04,0x05,0x10 */ - { - sprintf(final->line[0], - " ub4 rsl = (((val>>%ld) & 2) ^ (((val>>%ld) ^ val) & 1));\n", - m-1, n); - } - else /* 0x00,0x02,0x0a,0x10 */ - { - sprintf(final->line[0], - " ub4 rsl = (((val>>%ld) & 1) ^ (((val>>%ld) ^ (val>>%ld)) & 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], " ub4 b = (val >> %ld) & 1;\n", o); - if (m==o-1 && m==0) /* 0x02,0x10,0x11,0x18 */ - { - sprintf(final->line[1], - " ub4 rsl = ((val & 3) ^ ((val >> %ld) & 2) ^ b);\n", n-1); - } - else if (m==o-1) /* 0,4,6,c */ - { - sprintf(final->line[1], - " ub4 rsl = (((val >> %ld) & 3) ^ ((val >> %ld) & 2) ^ b);\n", - m, n-1); - } - else if (m==n-1 && m==0) /* 02,0a,0b,18 */ - { - sprintf(final->line[1], - " ub4 rsl = ((val & 3) ^ b ^ (b << 1));\n"); - } - else if (m==n-1) /* 0,2,4,8 */ - { - sprintf(final->line[1], - " ub4 rsl = (((val >> %ld) & 3) ^ b ^ (b << 1));\n", m); - } - else if (o==n-1 && m==0) /* h4am: not reached */ - { - sprintf(final->line[1], - " ub4 rsl = ((val & 1) ^ ((val >> %ld) & 3) ^ (b <<1 ));\n", - o); - } - else if (o==n-1) /* 0x00,0x02,0x08,0x10 */ - { - sprintf(final->line[1], - " ub4 rsl = (((val >> %ld) & 1) ^ ((val >> %ld) & 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], " ub4 newval = val & 0x%lx;\n", - (((ub4)1<<m)^((ub4)1<<n)^((ub4)1<<o))); - if (o==0) /* 0x00,0x01,0x04,0x10 */ - { - sprintf(final->line[1], " ub4 b = -newval;\n"); - } - else /* 0x00,0x04,0x09,0x10 */ - { - sprintf(final->line[1], " ub4 b = -(newval >> %ld);\n", o); - } - if (m==0) /* 0x00,0x04,0x09,0x10 */ - { - sprintf(final->line[2], - " ub4 rsl = ((newval ^ (newval>>%ld) ^ b) & 3);\n", n-1); - } - else /* 0x00,0x03,0x04,0x10 */ - { - sprintf(final->line[2], - " ub4 rsl = (((newval>>%ld) ^ (newval>>%ld) ^ b) & 3);\n", - m, n-1); - } - } - else if (o == m-1) - { - if (o==0) /* 0x02,0x03,0x0a,0x10 */ - { - sprintf(final->line[0], " ub4 b = (val<<1) & 2;\n"); - } - else if (o==1) /* 0x00,0x02,0x04,0x10 */ - { - sprintf(final->line[0], " ub4 b = val & 2;\n"); - } - else /* 0x00,0x04,0x08,0x20 */ - { - sprintf(final->line[0], " ub4 b = (val>>%ld) & 2;\n", o-1); - } - - if (o==0) /* 0x02,0x03,0x0a,0x10 */ - { - sprintf(final->line[1], - " ub4 rsl = ((val & 3) ^ ((val>>%ld) & 1) ^ b);\n", - n); - } - else /* 0x00,0x02,0x04,0x10 */ - { - sprintf(final->line[1], - " ub4 rsl = (((val>>%ld) & 3) ^ ((val>>%ld) & 1) ^ b);\n", - o, n); - } - } - else /* h4ax: 10 instructions, but not reached */ - { - sprintf(final->line[1], - " ub4 rsl = (((val>>%ld) & 1) ^ ((val>>%ld) & 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], - " ub4 rsl = (((val>>%ld) & 1) ^ ((val>>%ld) & 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(keys, badmask) -key *keys; /* keys being hashed */ -ub1 badmask; /* used for minimal perfect hashing */ -{ - ub1 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(keys, nkeys, final, form) -key *keys; -ub4 nkeys; -gencode *final; -hashform *form; -{ - key *mykey; /* walk through the keys */ - ub4 i,j,k; - ub1 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], " ub4 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], " ub4 rsl = ((val >> %ld) & 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], - " ub4 rsl = ((val + (val >> %ld)) & 7);\n", j); - else /* h8d */ - sprintf(final->line[0], - " ub4 rsl = (((val >> %ld) + (val >> %ld)) & 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], - " ub4 rsl = ((val ^ (val >> %ld)) & 7);\n", j); - else /* h8f */ - sprintf(final->line[0], - " ub4 rsl = (((val >> %ld) ^ (val >> %ld)) & 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], - " ub4 rsl = ((val - (val >> %ld)) & 7);\n", j); - else /* h8h */ - sprintf(final->line[0], - " ub4 rsl = (((val >> %ld) - (val >> %ld)) & 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], - " ub4 rsl = (((val >> %ld) + (val >> %ld) + (val >> %ld)) & 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(keys, salt, alen, blen, final) -key *keys; -ub4 salt; -ub4 alen; -ub4 blen; -gencode *final; -{ - key *mykey; - ub4 highbit = final->highbit; - ub4 lowbit = final->lowbit; - ub4 alog = mylog2(alen); - ub4 blog = mylog2(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 << (UB4BITS-(highbit+1)))>>(UB4BITS-alog); - mykey->b_k = (mykey->hash_k >> lowbit) & (blen-1); - } - if (lowbit == 0) /* hna */ - sprintf(final->line[5], " b = (val & 0x%lx);\n", - blen-1); - else /* hnb */ - sprintf(final->line[5], " b = ((val >> %ld) & 0x%lx);\n", - lowbit, blen-1); - if (highbit+1 == UB4BITS) /* hnc */ - sprintf(final->line[6], " a = (val >> %ld);\n", - UB4BITS-alog); - else /* hnd */ - sprintf(final->line[6], " a = ((val << %ld ) >> %ld);\n", - UB4BITS-(highbit+1), UB4BITS-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 << (UB4BITS-(highbit+1)))>>(UB4BITS-blog); - } - if (highbit+1 == UB4BITS) /* hne */ - sprintf(final->line[5], " b = (val >> %ld);\n", - UB4BITS-blog); - else /* hnf */ - sprintf(final->line[5], " b = ((val << %ld ) >> %ld);\n", - UB4BITS-(highbit+1), UB4BITS-blog); - if (lowbit == 0) /* hng */ - sprintf(final->line[6], " a = (val & 0x%lx);\n", - alen-1); - else /* hnh */ - sprintf(final->line[6], " a = ((val >> %ld) & 0x%lx);\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 << (UB4BITS-final->k-1)) >> (UB4BITS-alog); - } - if (final->j == 0) /* hni */ - sprintf(final->line[5], " b = val & 0x%lx;\n", - blen-1); - else if (blog+final->j == UB4BITS) /* hnja */ - sprintf(final->line[5], " b = val >> %ld;\n", - final->j); - else - sprintf(final->line[5], " b = (val >> %ld) & 0x%lx;\n", /* hnj */ - final->j, blen-1); - if (UB4BITS-final->k-1 == 0) /* hnk */ - sprintf(final->line[6], " a = (val >> %ld);\n", - UB4BITS-alog); - else /* hnl */ - sprintf(final->line[6], " a = ((val << %ld) >> %ld);\n", - UB4BITS-final->k-1, UB4BITS-alog); - while (++final->j < highbit) - { - if (((final->diffbits>>(final->j)) & (blen-1)) > 2) - break; - } - return; - - case 5: - while (++final->k < highbit) - { - if ((((final->diffbits<<(UB4BITS-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<UB4BITS-alog; ++k) - * for (j=0; j<UB4BITS-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 */ - { - ub4 addk = 0x9e3779b9*salt; - - if (!(final->j <= UB4BITS-blog)) - { - ++final->i; - break; - } - for (mykey=keys; mykey; mykey=mykey->next_k) - { - ub4 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 >> (UB4BITS-alog); - else - mykey->a_k = (val + (val << final->k)) >> (UB4BITS-alog); - } - sprintf(final->line[1], " val += 0x%lx;\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%lx;\n", blen-1); - else /* hnp */ - sprintf(final->line[5], " b = (val >> %ld) & 0x%lx;\n", - final->j, blen-1); - if (final->k == 0) /* hnq */ - sprintf(final->line[6], " a = val >> %ld;\n", UB4BITS-alog); - else /* hnr */ - sprintf(final->line[6], " a = (val + (val << %ld)) >> %ld;\n", - final->k, UB4BITS-alog); - - ++final->j; - return; - } - - case 8: - ++final->k; - if (!(final->k <= UB4BITS-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(keys, final) -key *keys; -gencode *final; -{ - ub4 lowbit; - ub4 highbit; - ub4 i; - key *mykey; - ub4 firstkey; - - /* mark the interesting bits in final->mask */ - final->diffbits = (ub4)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<UB4BITS; ++i) - if (final->diffbits & (((ub4)1)<<i)) - break; - final->lowbit = i; - - /* find the highest interesting bit */ - for (i=UB4BITS; --i; ) - if (final->diffbits & (((ub4)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(keys, nkeys, alen, blen, smax, salt, final, form) -key *keys; /* list of all keys */ -ub4 nkeys; /* number of keys to hash */ -ub4 alen; /* (a,b) has a in 0..alen-1, a power of 2 */ -ub4 blen; /* (a,b) has b in 0..blen-1, a power of 2 */ -ub4 smax; /* maximum range of computable hash values */ -ub4 salt; /* used to initialize the hash function */ -gencode *final; /* output, code for the final hash */ -hashform *form; /* user directives */ -{ - 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], " ub4 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; - } -} |