// This file contains an implementation of perfect-hash generation.

// It is an bastardized version of code originally due to Bob Jenkins.

// See this website for discussion:

// <http://www.burtleburtle.net/bob/hash/perfect.html>

//

// This code creates a command-line utility that should be placed

//

///////////////////////////////////////////////////////////////////////////////

// BEGIN STANDARD.H

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stddef.h>

#include <stdint.h>

typedef uint64_t ub8;

#define UB8MAXVAL 0xffffffffffffffffLL

#define UB8BITS 64

typedef int64_t sb8;

#define SB8MAXVAL 0x7fffffffffffffffLL

typedef uint32_t ub4; /* unsigned 4-byte quantities */

#define UB4MAXVAL 0xffffffff

typedef int32_t sb4;

#define UB4BITS 32

#define SB4MAXVAL 0x7fffffff

typedef uint16_t ub2;

#define UB2MAXVAL 0xffff

#define UB2BITS 16

typedef int16_t sb2;

#define SB2MAXVAL 0x7fff

typedef unsigned char ub1;

#define UB1MAXVAL 0xff

#define UB1BITS 8

typedef signed char sb1; /* signed 1-byte quantities */

#define SB1MAXVAL 0x7f

typedef int32_t word; /* fastest type available */

#define bis(target,mask) ((target) |= (mask))

#define bic(target,mask) ((target) &= ~(mask))

#define bit(target,mask) ((target) & (mask))

#ifndef min

# define min(a,b) (((a)<(b)) ? (a) : (b))

#endif /* min */

#ifndef max

# define max(a,b) (((a)<(b)) ? (b) : (a))

#endif /* max */

#ifndef align

# define align(a) (((ub4)a+(sizeof(void *)-1))&(~(sizeof(void *)-1)))

#endif /* align */

#ifndef abs

# define abs(a) (((a)>0) ? (a) : -(a))

#endif

#define TRUE 1

#define FALSE 0

#define SUCCESS 0 /* 1 on VAX */

// END STANDARD.H

///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////

// BEGIN RECYCLE.H

#define RESTART 0

#define REMAX 32000

struct recycle

{

struct recycle *next;

};

typedef struct recycle recycle;

struct reroot

{

struct recycle *list; /* list of malloced blocks */

struct recycle *trash; /* list of deleted items */

size_t size; /* size of an item */

size_t logsize; /* log_2 of number of items in a block */

word numleft; /* number of bytes left in this block */

};

typedef struct reroot reroot;

/* make a new recycling root */

reroot *remkroot(/*_ size_t mysize _*/);

/* free a recycling root and all the items it has made */

void refree(/*_ struct reroot *r _*/);

/* get a new (cleared) item from the root */

#define renew(r) ((r)->numleft ? \

(((char *)((r)->list+1))+((r)->numleft-=(r)->size)) : renewx(r))

char *renewx(/*_ struct reroot *r _*/);

/* delete an item; let the root recycle it */

/* void redel(/o_ struct reroot *r, struct recycle *item _o/); */

#define redel(root,item) { \

((recycle *)item)->next=(root)->trash; \

(root)->trash=(recycle *)(item); \

}

/* malloc, but complain to stderr and exit program if no joy */

/* use plain free() to free memory allocated by remalloc() */

char *remalloc(/*_ size_t len, char *purpose _*/);

// END RECYCLE.H

///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////

// BEGIN PERFECT.H

#define MAXKEYLEN 30 /* maximum length of a key */

#define USE_SCRAMBLE 4096 /* use scramble if blen >= USE_SCRAMBLE */

#define SCRAMBLE_LEN ((ub4)1<<16) /* length of *scramble* */

#define RETRY_INITKEY 2048 /* number of times to try to find distinct (a,b) */

#define RETRY_PERFECT 1 /* number of times to try to make a perfect hash */

#define RETRY_HEX 200 /* RETRY_PERFECT when hex keys given */

/* the generated code for the final hash, assumes initial hash is done */

struct gencode

{

char **line; /* array of text lines, 80 bytes apiece */

/*

* The code placed here must declare "ub4 rsl"

* and assign it the value of the perfect hash using the function inputs.

* Later code will be tacked on which returns rsl or manipulates it according

* to the user directives.

*

* This code is at the top of the routine; it may and must declare any

* local variables it needs.

*

* Each way of filling in **line should be given a comment that is a unique

* tag. A testcase named with that tag should also be found which tests

* the generated code.

*/

ub4 len; /* number of lines available for final hash */

ub4 used; /* number of lines used by final hash */

ub4 lowbit; /* for HEX, lowest interesting bit */

ub4 highbit; /* for HEX, highest interesting bit */

ub4 diffbits; /* bits which differ for some key */

ub4 i,j,k,l,m,n,o; /* state machine used in hexn() */

};

typedef struct gencode gencode;

/* user directives: perfect hash? minimal perfect hash? input is an int? */

struct hashform

{

enum {

NORMAL_HM, /* key is a string */

INLINE_HM, /* user will do initial hash, we must choose salt for them */

HEX_HM, /* key to be hashed is a hexidecimal 4-byte integer */

DECIMAL_HM, /* key to be hashed is a decimal 4-byte integer */

AB_HM, /* key to be hashed is "A B", where A and B are (A,B) in hex */

ABDEC_HM /* like AB_HM, but in decimal */

} mode;

enum {

STRING_HT, /* key is a string */

INT_HT, /* key is an integer */

AB_HT /* dunno what key is, but input is distinct (A,B) pair */

} hashtype;

enum {

NORMAL_HP, /* just find a perfect hash */

MINIMAL_HP /* find a minimal perfect hash */

} perfect;

enum {

FAST_HS, /* fast mode */

SLOW_HS /* slow mode */

} speed;

};

typedef struct hashform hashform;

/* representation of a key */

struct key

{

ub1 *name_k; /* the actual key */

ub4 len_k; /* the length of the actual key */

ub4 hash_k; /* the initial hash value for this key */

struct key *next_k; /* next key */

/* beyond this point is mapping-dependent */

ub4 a_k; /* a, of the key maps to (a,b) */

ub4 b_k; /* b, of the key maps to (a,b) */

struct key *nextb_k; /* next key with this b */

ub4 final_hash_k;

};

typedef struct key key;

/* things indexed by b of original (a,b) pair */

struct bstuff

{

ub2 val_b; /* hash=a^tabb[b].val_b */

key *list_b; /* tabb[i].list_b is list of keys with b==i */

ub4 listlen_b; /* length of list_b */

ub4 water_b; /* high watermark of who has visited this map node */

};

typedef struct bstuff bstuff;

/* things indexed by final hash value */

struct hstuff

{

key *key_h; /* tabh[i].key_h is the key with a hash of i */

};

typedef struct hstuff hstuff;

/* things indexed by queue position */

struct qstuff

{

bstuff *b_q; /* b that currently occupies this hash */

ub4 parent_q; /* queue position of parent that could use this hash */

ub2 newval_q; /* what to change parent tab[b] to to use this hash */

ub2 oldval_q; /* original value of tab[b] */

};

typedef struct qstuff qstuff;

/* return ceiling(log based 2 of x) */

ub4 mylog2(/*_ ub4 x _*/);

/* Given the keys, scramble[], and hash mode, find the perfect hash */

void findhash(/*_ bstuff **tabb, ub4 *alen, ub4 *blen, ub4 *salt,

gencode *final, ub4 *scramble, ub4 smax, key *keys, ub4 nkeys,

hashform *form _*/);

/* private, but in a different file because it's excessively verbose */

int inithex(/*_ key *keys, ub4 *alen, ub4 *blen, ub4 smax, ub4 nkeys,

ub4 salt, gencode *final, gencode *form _*/);

// END PERFECT.H

///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////

// BEGIN LOOKUPA.H

#define CHECKSTATE 8

#define hashsize(n) ((ub4)1<<(n))

#define hashmask(n) (hashsize(n)-1)

ub4 lookup(/*_ ub1 *k, ub4 length, ub4 level _*/);

void checksum(/*_ ub1 *k, ub4 length, ub4 *state _*/);

// END LOOKUPA.H

///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////

reroot *remkroot(size)

size_t size;

{

reroot *r = (reroot *)remalloc(sizeof(reroot), "recycle.c, root");

r->list = (recycle *)0;

r->trash = (recycle *)0;

r->size = align(size);

r->logsize = RESTART;

r->numleft = 0;

return r;

}

void refree(r)

struct reroot *r;

{

recycle *temp;

if (temp = r->list) while (r->list)

{

temp = r->list->next;

free((char *)r->list);

r->list = temp;

}

free((char *)r);

return;

}

/* to be called from the macro renew only */

char *renewx(r)

struct reroot *r;

{

recycle *temp;

if (r->trash)

{ /* pull a node off the trash heap */

temp = r->trash;

r->trash = temp->next;

(void)memset((void *)temp, 0, r->size);

}

else

{ /* allocate a new block of nodes */

r->numleft = r->size*((ub4)1<<r->logsize);

if (r->numleft < REMAX) ++r->logsize;

temp = (recycle *)remalloc(sizeof(recycle) + r->numleft,

"recycle.c, data");

temp->next = r->list;

r->list = temp;

r->numleft-=r->size;

temp = (recycle *)((char *)(r->list+1)+r->numleft);

}

return (char *)temp;

}

char *remalloc(len, purpose)

size_t len;

char *purpose;

{

char *x = (char *)malloc(len);

if (!x)

{

fprintf(stderr, "malloc of %d failed for %s\n",

len, purpose);

exit(1);

}

return x;

}

///////////////////////////////////////////////////////////////////////////////

/*

--------------------------------------------------------------------

mix -- mix 3 32-bit values reversibly.

For every delta with one or two bit set, and the deltas of all three

high bits or all three low bits, whether the original value of a,b,c

is almost all zero or is uniformly distributed,

* If mix() is run forward or backward, at least 32 bits in a,b,c

have at least 1/4 probability of changing.

* If mix() is run forward, every bit of c will change between 1/3 and

2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)

mix() was built out of 36 single-cycle latency instructions in a

structure that could supported 2x parallelism, like so:

a -= b;

a -= c; x = (c>>13);

b -= c; a ^= x;

b -= a; x = (a<<8);

c -= a; b ^= x;

c -= b; x = (b>>13);

...

Unfortunately, superscalar Pentiums and Sparcs can't take advantage

of that parallelism. They've also turned some of those single-cycle

latency instructions into multi-cycle latency instructions. Still,

this is the fastest good hash I could find. There were about 2^^68

to choose from. I only looked at a billion or so.

--------------------------------------------------------------------

*/

#define mix(a,b,c) \

{ \

a -= b; a -= c; a ^= (c>>13); \

b -= c; b -= a; b ^= (a<<8); \

c -= a; c -= b; c ^= (b>>13); \

a -= b; a -= c; a ^= (c>>12); \

b -= c; b -= a; b ^= (a<<16); \

c -= a; c -= b; c ^= (b>>5); \

a -= b; a -= c; a ^= (c>>3); \

b -= c; b -= a; b ^= (a<<10); \

c -= a; c -= b; c ^= (b>>15); \

}

/*

--------------------------------------------------------------------

lookup() -- hash a variable-length key into a 32-bit value

k : the key (the unaligned variable-length array of bytes)

len : the length of the key, counting by bytes

level : can be any 4-byte value

Returns a 32-bit value. Every bit of the key affects every bit of

the return value. Every 1-bit and 2-bit delta achieves avalanche.

About 6len+35 instructions.

The best hash table sizes are powers of 2. There is no need to do

mod a prime (mod is sooo slow!). If you need less than 32 bits,

use a bitmask. For example, if you need only 10 bits, do

h = (h & hashmask(10));

In which case, the hash table should have hashsize(10) elements.

If you are hashing n strings (ub1 **)k, do it like this:

for (i=0, h=0; i<n; ++i) h = lookup( k[i], len[i], h);

By Bob Jenkins, 1996. [email protected]. You may use this

code any way you wish, private, educational, or commercial.

See http://burtleburtle.net/bob/hash/evahash.html

Use for hash table lookup, or anything where one collision in 2^32 is

acceptable. Do NOT use for cryptographic purposes.

--------------------------------------------------------------------

*/

ub4 lookup( k, length, level)

register ub1 *k; /* the key */

register ub4 length; /* the length of the key */

register ub4 level; /* the previous hash, or an arbitrary value */

{

register ub4 a,b,c,len;

/* Set up the internal state */

len = length;

a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */

c = level; /* the previous hash value */

/*---------------------------------------- handle most of the key */

while (len >= 12)

{

a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));

b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));

c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));

mix(a,b,c);

k += 12; len -= 12;

}

/*------------------------------------- handle the last 11 bytes */

c += length;

switch(len) /* all the case statements fall through */

{

case 11: c+=((ub4)k[10]<<24);

case 10: c+=((ub4)k[9]<<16);

case 9 : c+=((ub4)k[8]<<8);

/* the first byte of c is reserved for the length */

case 8 : b+=((ub4)k[7]<<24);

case 7 : b+=((ub4)k[6]<<16);

case 6 : b+=((ub4)k[5]<<8);

case 5 : b+=k[4];

case 4 : a+=((ub4)k[3]<<24);

case 3 : a+=((ub4)k[2]<<16);

case 2 : a+=((ub4)k[1]<<8);

case 1 : a+=k[0];

/* case 0: nothing left to add */

}

mix(a,b,c);

/*-------------------------------------------- report the result */

return c;

}

/*

--------------------------------------------------------------------

mixc -- mixc 8 4-bit values as quickly and thoroughly as possible.

Repeating mix() three times achieves avalanche.

Repeating mix() four times eliminates all funnels and all

characteristics stronger than 2^{-11}.

--------------------------------------------------------------------

*/

#define mixc(a,b,c,d,e,f,g,h) \

{ \

a^=b<<11; d+=a; b+=c; \

b^=c>>2; e+=b; c+=d; \

c^=d<<8; f+=c; d+=e; \

d^=e>>16; g+=d; e+=f; \

e^=f<<10; h+=e; f+=g; \

f^=g>>4; a+=f; g+=h; \

g^=h<<8; b+=g; h+=a; \

h^=a>>9; c+=h; a+=b; \

}

/*

--------------------------------------------------------------------

checksum() -- hash a variable-length key into a 256-bit value

k : the key (the unaligned variable-length array of bytes)

len : the length of the key, counting by bytes

state : an array of CHECKSTATE 4-byte values (256 bits)

The state is the checksum. Every bit of the key affects every bit of

the state. There are no funnels. About 112+6.875len instructions.

If you are hashing n strings (ub1 **)k, do it like this:

for (i=0; i<8; ++i) state[i] = 0x9e3779b9;

for (i=0, h=0; i<n; ++i) checksum( k[i], len[i], state);

See http://burtleburtle.net/bob/hash/evahash.html

Use to detect changes between revisions of documents, assuming nobody

is trying to cause collisions. Do NOT use for cryptography.

--------------------------------------------------------------------

*/

void checksum( k, len, state)

register ub1 *k;

register ub4 len;

register ub4 *state;

{

register ub4 a,b,c,d,e,f,g,h,length;

/* Use the length and level; add in the golden ratio. */

length = len;

a=state[0]; b=state[1]; c=state[2]; d=state[3];

e=state[4]; f=state[5]; g=state[6]; h=state[7];

/*---------------------------------------- handle most of the key */

while (len >= 32)

{

a += (k[0] +(k[1]<<8) +(k[2]<<16) +(k[3]<<24));

b += (k[4] +(k[5]<<8) +(k[6]<<16) +(k[7]<<24));

c += (k[8] +(k[9]<<8) +(k[10]<<16)+(k[11]<<24));

d += (k[12]+(k[13]<<8)+(k[14]<<16)+(k[15]<<24));

e += (k[16]+(k[17]<<8)+(k[18]<<16)+(k[19]<<24));

f += (k[20]+(k[21]<<8)+(k[22]<<16)+(k[23]<<24));

g += (k[24]+(k[25]<<8)+(k[26]<<16)+(k[27]<<24));

h += (k[28]+(k[29]<<8)+(k[30]<<16)+(k[31]<<24));

mixc(a,b,c,d,e,f,g,h);

mixc(a,b,c,d,e,f,g,h);

mixc(a,b,c,d,e,f,g,h);

mixc(a,b,c,d,e,f,g,h);

k += 32; len -= 32;

}

/*------------------------------------- handle the last 31 bytes */

h += length;

switch(len)

{

case 31: h+=(k[30]<<24);

case 30: h+=(k[29]<<16);

case 29: h+=(k[28]<<8);

case 28: g+=(k[27]<<24);

case 27: g+=(k[26]<<16);

case 26: g+=(k[25]<<8);

case 25: g+=k[24];

case 24: f+=(k[23]<<24);

case 23: f+=(k[22]<<16);

case 22: f+=(k[21]<<8);

case 21: f+=k[20];

case 20: e+=(k[19]<<24);

case 19: e+=(k[18]<<16);

case 18: e+=(k[17]<<8);

case 17: e+=k[16];

case 16: d+=(k[15]<<24);

case 15: d+=(k[14]<<16);

case 14: d+=(k[13]<<8);

case 13: d+=k[12];

case 12: c+=(k[11]<<24);

case 11: c+=(k[10]<<16);

case 10: c+=(k[9]<<8);

case 9 : c+=k[8];

case 8 : b+=(k[7]<<24);

case 7 : b+=(k[6]<<16);

case 6 : b+=(k[5]<<8);

case 5 : b+=k[4];

case 4 : a+=(k[3]<<24);

case 3 : a+=(k[2]<<16);

case 2 : a+=(k[1]<<8);

case 1 : a+=k[0];

}

mixc(a,b,c,d,e,f,g,h);

mixc(a,b,c,d,e,f,g,h);

mixc(a,b,c,d,e,f,g,h);

mixc(a,b,c,d,e,f,g,h);

/*-------------------------------------------- report the result */

state[0]=a; state[1]=b; state[2]=c; state[3]=d;

state[4]=e; state[5]=f; state[6]=g; state[7]=h;

}

///////////////////////////////////////////////////////////////////////////////

/*

------------------------------------------------------------------------------

Find the mapping that will produce a perfect hash

------------------------------------------------------------------------------

*/

/* return the ceiling of the log (base 2) of val */

ub4 mylog2(val)

ub4 val;

{

ub4 i;

for (i=0; ((ub4)1<<i) < val; ++i)

;

return i;

}

/* compute p(x), where p is a permutation of 0..(1<<nbits)-1 */

/* permute(0)=0. This is intended and useful. */

static ub4 permute(x, nbits)

ub4 x; /* input, a value in some range */

ub4 nbits; /* input, number of bits in range */

{

int i;

int mask = ((ub4)1<<nbits)-1; /* all ones */

int const2 = 1+nbits/2;

int const3 = 1+nbits/3;

int const4 = 1+nbits/4;

int const5 = 1+nbits/5;

for (i=0; i<20; ++i)

{

x = (x+(x<<const2)) & mask;

x = (x^(x>>const3));

x = (x+(x<<const4)) & mask;

x = (x^(x>>const5));

}

return x;

}

/* initialize scramble[] with distinct random values in 0..smax-1 */

static void scrambleinit(scramble, smax)

ub4 *scramble; /* hash is a^scramble[tab[b]] */

ub4 smax; /* scramble values should be in 0..smax-1 */

{

ub4 i;

/* fill scramble[] with distinct random integers in 0..smax-1 */

for (i=0; i<SCRAMBLE_LEN; ++i)

{

scramble[i] = permute(i, mylog2(smax));

}

}

/*

* Check if key1 and key2 are the same.

* We already checked (a,b) are the same.

*/

static void checkdup(key1, key2, form)

key *key1;

key *key2;

hashform *form;

{

switch(form->hashtype)

{

case STRING_HT:

if ((key1->len_k == key2->len_k) &&

!memcmp(key1->name_k, key2->name_k, (size_t)key1->len_k))

{

fprintf(stderr, "perfect.c: Duplicate keys! %.*s\n",

key1->len_k, key1->name_k);

exit(1);

}

break;

case INT_HT:

if (key1->hash_k == key2->hash_k)

{

fprintf(stderr, "perfect.c: Duplicate keys! %.8x\n", key1->hash_k);

exit(2);

}

break;

case AB_HT:

fprintf(stderr, "perfect.c: Duplicate keys! %.8x %.8x\n",

key1->a_k, key1->b_k);

exit(3);

break;

default:

fprintf(stderr, "perfect.c: Illegal hash type %u\n", (ub4)form->hashtype);

exit(4);

break;

}

}

/*

* put keys in tabb according to key->b_k

* check if the initial hash might work

*/

static int inittab(tabb, blen, keys, form, complete)

bstuff *tabb; /* output, list of keys with b for (a,b) */

ub4 blen; /* length of tabb */

key *keys; /* list of keys already hashed */

hashform *form; /* user directives */

int complete; /* TRUE means to complete init despite collisions */

{

int nocollision = TRUE;

key *mykey;

memset((void *)tabb, 0, (size_t)(sizeof(bstuff)*blen));

/* Two keys with the same (a,b) guarantees a collision */

for (mykey=keys; mykey; mykey=mykey->next_k)

{

key *otherkey;

for (otherkey=tabb[mykey->b_k].list_b;

otherkey;

otherkey=otherkey->nextb_k)

{

if (mykey->a_k == otherkey->a_k)

{

nocollision = FALSE;

checkdup(mykey, otherkey, form);

if (!complete)

return FALSE;

}

}

++tabb[mykey->b_k].listlen_b;

mykey->nextb_k = tabb[mykey->b_k].list_b;

tabb[mykey->b_k].list_b = mykey;

}

/* no two keys have the same (a,b) pair */

return nocollision;

}

/* Do the initial hash for normal mode (use lookup and checksum) */

static void initnorm(keys, alen, blen, smax, salt, final)

key *keys; /* list of all keys */

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 */

{

key *mykey;

if (mylog2(alen)+mylog2(blen) > UB4BITS)

{

ub4 initlev = salt*0x9e3779b9; /* the golden ratio; an arbitrary value */

for (mykey=keys; mykey; mykey=mykey->next_k)

{

ub4 i, state[CHECKSTATE];

for (i=0; i<CHECKSTATE; ++i) state[i] = initlev;

checksum( mykey->name_k, mykey->len_k, state);

mykey->a_k = state[0]&(alen-1);

mykey->b_k = state[1]&(blen-1);

}

final->used = 4;

sprintf(final->line[0],

" uint4 i,state[CHECKSTATE],rsl;\n");

sprintf(final->line[1],

" for (i=0; i<CHECKSTATE; ++i) state[i]=0x%x;\n",initlev);

sprintf(final->line[2],

" checksum(key, len, state);\n");

sprintf(final->line[3],

" rsl = ((state[0]&0x%x)^s_script_keyword_scramble_table[s_script_keyword_hash_table[state[1]&0x%x]]);\n",

alen-1, blen-1);

}

else

{

ub4 loga = mylog2(alen); /* log based 2 of blen */

ub4 initlev = salt*0x9e3779b9; /* the golden ratio; an arbitrary value */

for (mykey=keys; mykey; mykey=mykey->next_k)

{

ub4 hash = lookup(mykey->name_k, mykey->len_k, initlev);

mykey->a_k = (loga > 0) ? hash>>(UB4BITS-loga) : 0;

mykey->b_k = (blen > 1) ? hash&(blen-1) : 0;

}

final->used = 2;

sprintf(final->line[0],

" uint4 rsl, val = lookup(key, len, 0x%x);\n", initlev);

if (smax <= 1)

{

sprintf(final->line[1], " rsl = 0;\n");

}

else if (blen < USE_SCRAMBLE)

{

sprintf(final->line[1], " rsl = ((val>>%u)^s_script_keyword_hash_table[val&0x%x]);\n",

UB4BITS-mylog2(alen), blen-1);

}

else

{

sprintf(final->line[1], " rsl = ((val>>%u)^s_script_keyword_scramble_table[s_script_keyword_hash_table[val&0x%x]]);\n",

UB4BITS-mylog2(alen), blen-1);

}

}

}

/* Do initial hash for inline mode */

static void initinl(keys, alen, blen, smax, salt, final)

key *keys; /* list of all keys */

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; /* range of computable hash values */

ub4 salt; /* used to initialize the hash function */

gencode *final; /* generated code for final hash */

{

key *mykey;

ub4 amask = alen-1;

ub4 blog = mylog2(blen);

ub4 initval = salt*0x9e3779b9; /* the golden ratio; an arbitrary value */

/* It's more important to have b uniform than a, so b is the low bits */

for (mykey = keys; mykey != (key *)0; mykey = mykey->next_k)

{

ub4 hash = initval;

ub4 i;

for (i=0; i<mykey->len_k; ++i)

{

hash = (mykey->name_k[i] ^ hash) + ((hash<<(UB4BITS-6))+(hash>>6));

}

mykey->hash_k = hash;

mykey->a_k = (alen > 1) ? (hash & amask) : 0;

mykey->b_k = (blen > 1) ? (hash >> (UB4BITS-blog)) : 0;

}

final->used = 1;

if (smax <= 1)

{

sprintf(final->line[0], " uint4 rsl = 0;\n");

}

else if (blen < USE_SCRAMBLE)

{

sprintf(final->line[0], " uint4 rsl = ((val & 0x%x) ^ s_script_keyword_hash_table[val >> %u]);\n",

amask, UB4BITS-blog);

}

else

{

sprintf(final->line[0], " uint4 rsl = ((val & 0x%x) ^ s_script_keyword_scramble_table[s_script_keyword_hash_table[val >> %u]]);\n",

amask, UB4BITS-blog);

}

}

/*

* Run a hash function on the key to get a and b

* Returns:

* 0: didn't find distinct (a,b) for all keys

* 1: found distinct (a,b) for all keys, put keys in tabb[]

* 2: found a perfect hash, no need to do any more work

*/

static ub4 initkey(keys, nkeys, tabb, alen, blen, smax, salt, form, final)

key *keys; /* list of all keys */

ub4 nkeys; /* total number of keys */

bstuff *tabb; /* stuff indexed by b */

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; /* range of computable hash values */

ub4 salt; /* used to initialize the hash function */

hashform *form; /* user directives */

gencode *final; /* code for final hash */

{

ub4 finished;

/* Do the initial hash of the keys */

switch(form->mode)

{

case NORMAL_HM:

initnorm(keys, alen, blen, smax, salt, final);

break;

case INLINE_HM:

initinl(keys, alen, blen, smax, salt, final);

break;

case HEX_HM:

case DECIMAL_HM:

finished = inithex(keys, nkeys, alen, blen, smax, salt, final, form);

if (finished) return 2;

break;

default:

fprintf(stderr, "fatal error: illegal mode\n");

exit(1);

}

if (nkeys <= 1)

{

final->used = 1;

sprintf(final->line[0], " uint4 rsl = 0;\n");

return 2;

}

return inittab(tabb, blen, keys, form, FALSE);

}

/* Print an error message and exit if there are duplicates */

static void duplicates(tabb, blen, keys, form)

bstuff *tabb; /* array of lists of keys with the same b */

ub4 blen; /* length of tabb, a power of 2 */

key *keys;

hashform *form; /* user directives */

{

ub4 i;

key *key1;

key *key2;

(void)inittab(tabb, blen, keys, form, TRUE);

/* for each b, do nested loops through key list looking for duplicates */

for (i=0; i<blen; ++i)

for (key1=tabb[i].list_b; key1; key1=key1->nextb_k)

for (key2=key1->nextb_k; key2; key2=key2->nextb_k)

checkdup(key1, key2, form);

}

/* Try to apply an augmenting list */

static int apply(tabb, tabh, tabq, blen, scramble, tail, rollback)

bstuff *tabb;

hstuff *tabh;

qstuff *tabq;

ub4 blen;

ub4 *scramble;

ub4 tail;

int rollback; /* FALSE applies augmenting path, TRUE rolls back */

{

ub4 hash;

key *mykey;

bstuff *pb;

ub4 child;

ub4 parent;

ub4 stabb; /* scramble[tab[b]] */

/* walk from child to parent */

for (child=tail-1; child; child=parent)

{

parent = tabq[child].parent_q; /* find child's parent */

pb = tabq[parent].b_q; /* find parent's list of siblings */

/* erase old hash values */

stabb = scramble[pb->val_b];

for (mykey=pb->list_b; mykey; mykey=mykey->nextb_k)

{

hash = mykey->a_k^stabb;

if (mykey == tabh[hash].key_h)

{ /* erase hash for all of child's siblings */

tabh[hash].key_h = (key *)0;

}

}

/* change pb->val_b, which will change the hashes of all parent siblings */

pb->val_b = (rollback ? tabq[child].oldval_q : tabq[child].newval_q);

/* set new hash values */

stabb = scramble[pb->val_b];

for (mykey=pb->list_b; mykey; mykey=mykey->nextb_k)

{

hash = mykey->a_k^stabb;

if (rollback)

{

if (parent == 0) continue; /* root never had a hash */

}

else if (tabh[hash].key_h)

{

/* very rare: roll back any changes */

(void *)apply(tabb, tabh, tabq, blen, scramble, tail, TRUE);

return FALSE; /* failure, collision */

}

tabh[hash].key_h = mykey;

}

}

return TRUE;

}

/*

-------------------------------------------------------------------------------

augment(): Add item to the mapping.

Construct a spanning tree of *b*s with *item* as root, where each

parent can have all its hashes changed (by some new val_b) with

at most one collision, and each child is the b of that collision.

I got this from Tarjan's "Data Structures and Network Algorithms". The

path from *item* to a *b* that can be remapped with no collision is

an "augmenting path". Change values of tab[b] along the path so that

the unmapped key gets mapped and the unused hash value gets used.

Assuming 1 key per b, if m out of n hash values are still unused,

you should expect the transitive closure to cover n/m nodes before

an unused node is found. Sum(i=1..n)(n/i) is about nlogn, so expect

this approach to take about nlogn time to map all single-key b's.

-------------------------------------------------------------------------------

*/

static int augment(tabb, tabh, tabq, blen, scramble, smax, item, nkeys,

highwater, form)

bstuff *tabb; /* stuff indexed by b */

hstuff *tabh; /* which key is associated with which hash, indexed by hash */

qstuff *tabq; /* queue of *b* values, this is the spanning tree */

ub4 blen; /* length of tabb */

ub4 *scramble; /* final hash is a^scramble[tab[b]] */

ub4 smax; /* highest value in scramble */

bstuff *item; /* &tabb[b] for the b to be mapped */

ub4 nkeys; /* final hash must be in 0..nkeys-1 */

ub4 highwater; /* a value higher than any now in tabb[].water_b */

hashform *form; /* TRUE if we should do a minimal perfect hash */

{

ub4 q; /* current position walking through the queue */

ub4 tail; /* tail of the queue. 0 is the head of the queue. */

ub4 limit=((blen < USE_SCRAMBLE) ? smax : UB1MAXVAL+1);

ub4 highhash = ((form->perfect == MINIMAL_HP) ? nkeys : smax);

int trans = (form->speed == SLOW_HS || form->perfect == MINIMAL_HP);

/* initialize the root of the spanning tree */

tabq[0].b_q = item;

tail = 1;

/* construct the spanning tree by walking the queue, add children to tail */

for (q=0; q<tail; ++q)

{

bstuff *myb = tabq[q].b_q; /* the b for this node */

ub4 i; /* possible value for myb->val_b */

if (!trans && (q == 1))

break; /* don't do transitive closure */

for (i=0; i<limit; ++i)

{

bstuff *childb = (bstuff *)0; /* the b that this i maps to */

key *mykey; /* for walking through myb's keys */

for (mykey = myb->list_b; mykey; mykey=mykey->nextb_k)

{

key *childkey;

ub4 hash = mykey->a_k^scramble[i];

if (hash >= highhash) break; /* out of bounds */

childkey = tabh[hash].key_h;

if (childkey)

{

bstuff *hitb = &tabb[childkey->b_k];

if (childb)

{

if (childb != hitb) break; /* hit at most one child b */

}

else

{

childb = hitb; /* remember this as childb */

if (childb->water_b == highwater) break; /* already explored */

}

}

}

if (mykey) continue; /* myb with i has multiple collisions */

/* add childb to the queue of reachable things */

if (childb) childb->water_b = highwater;

tabq[tail].b_q = childb;