1 /* Modified for use with yasm by Peter Johnson. */ 2 /* 3 ------------------------------------------------------------------------------ 4 perfect.c: code to generate code for a hash for perfect hashing. 5 (c) Bob Jenkins, September 1996, December 1999 6 You may use this code in any way you wish, and it is free. No warranty. 7 I hereby place this in the public domain. 8 Source is http://burtleburtle.net/bob/c/perfect.c 9 10 This generates a minimal perfect hash function. That means, given a 11 set of n keys, this determines a hash function that maps each of 12 those keys into a value in 0..n-1 with no collisions. 13 14 The perfect hash function first uses a normal hash function on the key 15 to determine (a,b) such that the pair (a,b) is distinct for all 16 keys, then it computes a^scramble[tab[b]] to get the final perfect hash. 17 tab[] is an array of 1-byte values and scramble[] is a 256-term array of 18 2-byte or 4-byte values. If there are n keys, the length of tab[] is a 19 power of two between n/3 and n. 20 21 I found the idea of computing distinct (a,b) values in "Practical minimal 22 perfect hash functions for large databases", Fox, Heath, Chen, and Daoud, 23 Communications of the ACM, January 1992. They found the idea in Chichelli 24 (CACM Jan 1980). Beyond that, our methods differ. 25 26 The key is hashed to a pair (a,b) where a in 0..*alen*-1 and b in 27 0..*blen*-1. A fast hash function determines both a and b 28 simultaneously. Any decent hash function is likely to produce 29 hashes so that (a,b) is distinct for all pairs. I try the hash 30 using different values of *salt* until all pairs are distinct. 31 32 The final hash is (a XOR scramble[tab[b]]). *scramble* is a 33 predetermined mapping of 0..255 into 0..smax-1. *tab* is an 34 array that we fill in in such a way as to make the hash perfect. 35 36 First we fill in all values of *tab* that are used by more than one 37 key. We try all possible values for each position until one works. 38 39 This leaves m unmapped keys and m values that something could hash to. 40 If you treat unmapped keys as lefthand nodes and unused hash values 41 as righthand nodes, and draw a line connecting each key to each hash 42 value it could map to, you get a bipartite graph. We attempt to 43 find a perfect matching in this graph. If we succeed, we have 44 determined a perfect hash for the whole set of keys. 45 46 *scramble* is used because (a^tab[i]) clusters keys around *a*. 47 ------------------------------------------------------------------------------ 48 */ 49 50 #include <string.h> 51 #include "tools/genperf/standard.h" 52 #include "libyasm/coretype.h" 53 #include "libyasm/phash.h" 54 #include "tools/genperf/perfect.h" 55 56 #define CHECKSTATE 8 57 58 /* 59 ------------------------------------------------------------------------------ 60 Find the mapping that will produce a perfect hash 61 ------------------------------------------------------------------------------ 62 */ 63 64 /* return the ceiling of the log (base 2) of val */ 65 ub4 phash_log2(val) 66 ub4 val; 67 { 68 ub4 i; 69 for (i=0; ((ub4)1<<i) < val; ++i) 70 ; 71 return i; 72 } 73 74 /* compute p(x), where p is a permutation of 0..(1<<nbits)-1 */ 75 /* permute(0)=0. This is intended and useful. */ 76 static ub4 permute( 77 ub4 x, /* input, a value in some range */ 78 ub4 nbits) /* input, number of bits in range */ 79 { 80 int i; 81 int mask = ((ub4)1<<nbits)-1; /* all ones */ 82 int const2 = 1+nbits/2; 83 int const3 = 1+nbits/3; 84 int const4 = 1+nbits/4; 85 int const5 = 1+nbits/5; 86 for (i=0; i<20; ++i) 87 { 88 x = (x+(x<<const2)) & mask; 89 x = (x^(x>>const3)); 90 x = (x+(x<<const4)) & mask; 91 x = (x^(x>>const5)); 92 } 93 return x; 94 } 95 96 /* initialize scramble[] with distinct random values in 0..smax-1 */ 97 static void scrambleinit( 98 ub4 *scramble, /* hash is a^scramble[tab[b]] */ 99 ub4 smax) /* scramble values should be in 0..smax-1 */ 100 { 101 ub4 i; 102 103 /* fill scramble[] with distinct random integers in 0..smax-1 */ 104 for (i=0; i<SCRAMBLE_LEN; ++i) 105 { 106 scramble[i] = permute(i, phash_log2(smax)); 107 } 108 } 109 110 /* 111 * Check if key1 and key2 are the same. 112 * We already checked (a,b) are the same. 113 */ 114 static void checkdup( 115 key *key1, 116 key *key2, 117 hashform *form) 118 { 119 switch(form->hashtype) 120 { 121 case STRING_HT: 122 if ((key1->len_k == key2->len_k) && 123 !memcmp(key1->name_k, key2->name_k, (size_t)key1->len_k)) 124 { 125 fprintf(stderr, "perfect.c: Duplicates keys! %.*s\n", 126 (int)key1->len_k, key1->name_k); 127 exit(EXIT_FAILURE); 128 } 129 break; 130 case INT_HT: 131 if (key1->hash_k == key2->hash_k) 132 { 133 fprintf(stderr, "perfect.c: Duplicate keys! %.8lx\n", key1->hash_k); 134 exit(EXIT_FAILURE); 135 } 136 break; 137 case AB_HT: 138 fprintf(stderr, "perfect.c: Duplicate keys! %.8lx %.8lx\n", 139 key1->a_k, key1->b_k); 140 exit(EXIT_FAILURE); 141 break; 142 default: 143 fprintf(stderr, "perfect.c: Illegal hash type %ld\n", (ub4)form->hashtype); 144 exit(EXIT_FAILURE); 145 break; 146 } 147 } 148 149 150 /* 151 * put keys in tabb according to key->b_k 152 * check if the initial hash might work 153 */ 154 static int inittab( 155 bstuff *tabb, /* output, list of keys with b for (a,b) */ 156 ub4 blen, /* length of tabb */ 157 key *keys, /* list of keys already hashed */ 158 hashform *form, /* user directives */ 159 int complete) /* TRUE means to complete init despite collisions */ 160 { 161 int nocollision = TRUE; 162 key *mykey; 163 164 memset((void *)tabb, 0, (size_t)(sizeof(bstuff)*blen)); 165 166 /* Two keys with the same (a,b) guarantees a collision */ 167 for (mykey=keys; mykey; mykey=mykey->next_k) 168 { 169 key *otherkey; 170 171 for (otherkey=tabb[mykey->b_k].list_b; 172 otherkey; 173 otherkey=otherkey->nextb_k) 174 { 175 if (mykey->a_k == otherkey->a_k) 176 { 177 nocollision = FALSE; 178 checkdup(mykey, otherkey, form); 179 if (!complete) 180 return FALSE; 181 } 182 } 183 ++tabb[mykey->b_k].listlen_b; 184 mykey->nextb_k = tabb[mykey->b_k].list_b; 185 tabb[mykey->b_k].list_b = mykey; 186 } 187 188 /* no two keys have the same (a,b) pair */ 189 return nocollision; 190 } 191 192 193 /* Do the initial hash for normal mode (use lookup and checksum) */ 194 static void initnorm( 195 key *keys, /* list of all keys */ 196 ub4 alen, /* (a,b) has a in 0..alen-1, a power of 2 */ 197 ub4 blen, /* (a,b) has b in 0..blen-1, a power of 2 */ 198 ub4 smax, /* maximum range of computable hash values */ 199 ub4 salt, /* used to initialize the hash function */ 200 gencode *final) /* output, code for the final hash */ 201 { 202 key *mykey; 203 if (phash_log2(alen)+phash_log2(blen) > UB4BITS) 204 { 205 ub4 initlev = (salt*0x9e3779b9)&0xffffffff; /* the golden ratio; an arbitrary value */ 206 207 for (mykey=keys; mykey; mykey=mykey->next_k) 208 { 209 ub4 i, state[CHECKSTATE]; 210 for (i=0; i<CHECKSTATE; ++i) state[i] = initlev; 211 phash_checksum( mykey->name_k, mykey->len_k, state); 212 mykey->a_k = state[0]&(alen-1); 213 mykey->b_k = state[1]&(blen-1); 214 } 215 final->used = 4; 216 sprintf(final->line[0], 217 " unsigned long i,state[CHECKSTATE],rsl;\n"); 218 sprintf(final->line[1], 219 " for (i=0; i<CHECKSTATE; ++i) state[i]=0x%lx;\n",initlev); 220 sprintf(final->line[2], 221 " phash_checksum(key, len, state);\n"); 222 sprintf(final->line[3], 223 " rsl = ((state[0]&0x%lx)^scramble[tab[state[1]&0x%lx]]);\n", 224 alen-1, blen-1); 225 } 226 else 227 { 228 ub4 loga = phash_log2(alen); /* log based 2 of blen */ 229 ub4 initlev = (salt*0x9e3779b9)&0xffffffff; /* the golden ratio; an arbitrary value */ 230 231 for (mykey=keys; mykey; mykey=mykey->next_k) 232 { 233 ub4 hash = phash_lookup(mykey->name_k, mykey->len_k, initlev); 234 mykey->a_k = (loga > 0) ? hash>>(UB4BITS-loga) : 0; 235 mykey->b_k = (blen > 1) ? hash&(blen-1) : 0; 236 } 237 final->used = 2; 238 sprintf(final->line[0], 239 " unsigned long rsl, val = phash_lookup(key, len, 0x%lxUL);\n", initlev); 240 if (smax <= 1) 241 { 242 sprintf(final->line[1], " rsl = 0;\n"); 243 } 244 else if (blen < USE_SCRAMBLE) 245 { 246 sprintf(final->line[1], " rsl = ((val>>%ld)^tab[val&0x%lx]);\n", 247 UB4BITS-phash_log2(alen), blen-1); 248 } 249 else 250 { 251 sprintf(final->line[1], " rsl = ((val>>%ld)^scramble[tab[val&0x%lx]]);\n", 252 UB4BITS-phash_log2(alen), blen-1); 253 } 254 } 255 } 256 257 258 259 /* Do initial hash for inline mode */ 260 static void initinl( 261 key *keys, /* list of all keys */ 262 ub4 alen, /* (a,b) has a in 0..alen-1, a power of 2 */ 263 ub4 blen, /* (a,b) has b in 0..blen-1, a power of 2 */ 264 ub4 smax, /* range of computable hash values */ 265 ub4 salt, /* used to initialize the hash function */ 266 gencode *final) /* generated code for final hash */ 267 { 268 key *mykey; 269 ub4 amask = alen-1; 270 ub4 blog = phash_log2(blen); 271 ub4 initval = salt*0x9e3779b9; /* the golden ratio; an arbitrary value */ 272 273 /* It's more important to have b uniform than a, so b is the low bits */ 274 for (mykey = keys; mykey != (key *)0; mykey = mykey->next_k) 275 { 276 ub4 hash = initval; 277 ub4 i; 278 for (i=0; i<mykey->len_k; ++i) 279 { 280 hash = ((ub1)mykey->name_k[i] ^ hash) + ((hash<<(UB4BITS-6))+(hash>>6)); 281 } 282 mykey->hash_k = hash; 283 mykey->a_k = (alen > 1) ? (hash & amask) : 0; 284 mykey->b_k = (blen > 1) ? (hash >> (UB4BITS-blog)) : 0; 285 } 286 final->used = 1; 287 if (smax <= 1) 288 { 289 sprintf(final->line[0], " unsigned long rsl = 0;\n"); 290 } 291 else if (blen < USE_SCRAMBLE) 292 { 293 sprintf(final->line[0], " unsigned long rsl = ((val & 0x%lx) ^ tab[val >> %ld]);\n", 294 amask, UB4BITS-blog); 295 } 296 else 297 { 298 sprintf(final->line[0], " unsigned long rsl = ((val & 0x%lx) ^ scramble[tab[val >> %ld]]);\n", 299 amask, UB4BITS-blog); 300 } 301 } 302 303 304 /* 305 * Run a hash function on the key to get a and b 306 * Returns: 307 * 0: didn't find distinct (a,b) for all keys 308 * 1: found distinct (a,b) for all keys, put keys in tabb[] 309 * 2: found a perfect hash, no need to do any more work 310 */ 311 static ub4 initkey( 312 key *keys, /* list of all keys */ 313 ub4 nkeys, /* total number of keys */ 314 bstuff *tabb, /* stuff indexed by b */ 315 ub4 alen, /* (a,b) has a in 0..alen-1, a power of 2 */ 316 ub4 blen, /* (a,b) has b in 0..blen-1, a power of 2 */ 317 ub4 smax, /* range of computable hash values */ 318 ub4 salt, /* used to initialize the hash function */ 319 hashform *form, /* user directives */ 320 gencode *final) /* code for final hash */ 321 { 322 /* Do the initial hash of the keys */ 323 switch(form->mode) 324 { 325 case NORMAL_HM: 326 initnorm(keys, alen, blen, smax, salt, final); 327 break; 328 case INLINE_HM: 329 initinl(keys, alen, blen, smax, salt, final); 330 break; 331 #if 0 332 case HEX_HM: 333 case DECIMAL_HM: 334 finished = inithex(keys, nkeys, alen, blen, smax, salt, final, form); 335 if (finished) return 2; 336 break; 337 #endif 338 default: 339 fprintf(stderr, "fatal error: illegal mode\n"); 340 exit(1); 341 } 342 343 if (nkeys <= 1) 344 { 345 final->used = 1; 346 sprintf(final->line[0], " unsigned long rsl = 0;\n"); 347 return 2; 348 } 349 350 return inittab(tabb, blen, keys, form, FALSE); 351 } 352 353 /* Print an error message and exit if there are duplicates */ 354 static void duplicates( 355 bstuff *tabb, /* array of lists of keys with the same b */ 356 ub4 blen, /* length of tabb, a power of 2 */ 357 key *keys, 358 hashform *form) /* user directives */ 359 { 360 ub4 i; 361 key *key1; 362 key *key2; 363 364 (void)inittab(tabb, blen, keys, form, TRUE); 365 366 /* for each b, do nested loops through key list looking for duplicates */ 367 for (i=0; i<blen; ++i) 368 for (key1=tabb[i].list_b; key1; key1=key1->nextb_k) 369 for (key2=key1->nextb_k; key2; key2=key2->nextb_k) 370 checkdup(key1, key2, form); 371 } 372 373 374 /* Try to apply an augmenting list */ 375 static int apply( 376 bstuff *tabb, 377 hstuff *tabh, 378 qstuff *tabq, 379 ub4 blen, 380 ub4 *scramble, 381 ub4 tail, 382 int rollback) /* FALSE applies augmenting path, TRUE rolls back */ 383 { 384 ub4 hash; 385 key *mykey; 386 bstuff *pb; 387 ub4 child; 388 ub4 parent; 389 ub4 stabb; /* scramble[tab[b]] */ 390 391 /* walk from child to parent */ 392 for (child=tail-1; child; child=parent) 393 { 394 parent = tabq[child].parent_q; /* find child's parent */ 395 pb = tabq[parent].b_q; /* find parent's list of siblings */ 396 397 /* erase old hash values */ 398 stabb = scramble[pb->val_b]; 399 for (mykey=pb->list_b; mykey; mykey=mykey->nextb_k) 400 { 401 hash = mykey->a_k^stabb; 402 if (mykey == tabh[hash].key_h) 403 { /* erase hash for all of child's siblings */ 404 tabh[hash].key_h = (key *)0; 405 } 406 } 407 408 /* change pb->val_b, which will change the hashes of all parent siblings */ 409 pb->val_b = (rollback ? tabq[child].oldval_q : tabq[child].newval_q); 410 411 /* set new hash values */ 412 stabb = scramble[pb->val_b]; 413 for (mykey=pb->list_b; mykey; mykey=mykey->nextb_k) 414 { 415 hash = mykey->a_k^stabb; 416 if (rollback) 417 { 418 if (parent == 0) continue; /* root never had a hash */ 419 } 420 else if (tabh[hash].key_h) 421 { 422 /* very rare: roll back any changes */ 423 apply(tabb, tabh, tabq, blen, scramble, tail, TRUE); 424 return FALSE; /* failure, collision */ 425 } 426 tabh[hash].key_h = mykey; 427 } 428 } 429 return TRUE; 430 } 431 432 433 /* 434 ------------------------------------------------------------------------------- 435 augment(): Add item to the mapping. 436 437 Construct a spanning tree of *b*s with *item* as root, where each 438 parent can have all its hashes changed (by some new val_b) with 439 at most one collision, and each child is the b of that collision. 440 441 I got this from Tarjan's "Data Structures and Network Algorithms". The 442 path from *item* to a *b* that can be remapped with no collision is 443 an "augmenting path". Change values of tab[b] along the path so that 444 the unmapped key gets mapped and the unused hash value gets used. 445 446 Assuming 1 key per b, if m out of n hash values are still unused, 447 you should expect the transitive closure to cover n/m nodes before 448 an unused node is found. Sum(i=1..n)(n/i) is about nlogn, so expect 449 this approach to take about nlogn time to map all single-key b's. 450 ------------------------------------------------------------------------------- 451 */ 452 static int augment( 453 bstuff *tabb, /* stuff indexed by b */ 454 hstuff *tabh, /* which key is associated with which hash, indexed by hash */ 455 qstuff *tabq, /* queue of *b* values, this is the spanning tree */ 456 ub4 blen, /* length of tabb */ 457 ub4 *scramble, /* final hash is a^scramble[tab[b]] */ 458 ub4 smax, /* highest value in scramble */ 459 bstuff *item, /* &tabb[b] for the b to be mapped */ 460 ub4 nkeys, /* final hash must be in 0..nkeys-1 */ 461 ub4 highwater, /* a value higher than any now in tabb[].water_b */ 462 hashform *form) /* TRUE if we should do a minimal perfect hash */ 463 { 464 ub4 q; /* current position walking through the queue */ 465 ub4 tail; /* tail of the queue. 0 is the head of the queue. */ 466 ub4 limit=((blen < USE_SCRAMBLE) ? smax : UB1MAXVAL+1); 467 ub4 highhash = ((form->perfect == MINIMAL_HP) ? nkeys : smax); 468 int trans = (form->speed == SLOW_HS || form->perfect == MINIMAL_HP); 469 470 /* initialize the root of the spanning tree */ 471 tabq[0].b_q = item; 472 tail = 1; 473 474 /* construct the spanning tree by walking the queue, add children to tail */ 475 for (q=0; q<tail; ++q) 476 { 477 bstuff *myb = tabq[q].b_q; /* the b for this node */ 478 ub4 i; /* possible value for myb->val_b */ 479 480 if (!trans && (q == 1)) 481 break; /* don't do transitive closure */ 482 483 for (i=0; i<limit; ++i) 484 { 485 bstuff *childb = (bstuff *)0; /* the b that this i maps to */ 486 key *mykey; /* for walking through myb's keys */ 487 488 for (mykey = myb->list_b; mykey; mykey=mykey->nextb_k) 489 { 490 key *childkey; 491 ub4 hash = mykey->a_k^scramble[i]; 492 493 if (hash >= highhash) break; /* out of bounds */ 494 childkey = tabh[hash].key_h; 495 496 if (childkey) 497 { 498 bstuff *hitb = &tabb[childkey->b_k]; 499 500 if (childb) 501 { 502 if (childb != hitb) break; /* hit at most one child b */ 503 } 504 else 505 { 506 childb = hitb; /* remember this as childb */ 507 if (childb->water_b == highwater) break; /* already explored */ 508 } 509 } 510 } 511 if (mykey) continue; /* myb with i has multiple collisions */ 512 513 /* add childb to the queue of reachable things */ 514 if (childb) childb->water_b = highwater; 515 tabq[tail].b_q = childb; 516 tabq[tail].newval_q = (ub2)i; /* how to make parent (myb) use this hash */ 517 tabq[tail].oldval_q = myb->val_b; /* need this for rollback */ 518 tabq[tail].parent_q = q; 519 ++tail; 520 521 if (!childb) 522 { /* found an *i* with no collisions? */ 523 /* try to apply the augmenting path */ 524 if (apply(tabb, tabh, tabq, blen, scramble, tail, FALSE)) 525 return TRUE; /* success, item was added to the perfect hash */ 526 527 --tail; /* don't know how to handle such a child! */ 528 } 529 } 530 } 531 return FALSE; 532 } 533 534 535 /* find a mapping that makes this a perfect hash */ 536 static int perfect( 537 bstuff *tabb, 538 hstuff *tabh, 539 qstuff *tabq, 540 ub4 blen, 541 ub4 smax, 542 ub4 *scramble, 543 ub4 nkeys, 544 hashform *form) 545 { 546 ub4 maxkeys; /* maximum number of keys for any b */ 547 ub4 i, j; 548 549 /* clear any state from previous attempts */ 550 memset((void *)tabh, 0, 551 (size_t)(sizeof(hstuff)* 552 ((form->perfect == MINIMAL_HP) ? nkeys : smax))); 553 memset((void *)tabq, 0, (size_t)(sizeof(qstuff)*(blen+1))); 554 555 for (maxkeys=0,i=0; i<blen; ++i) 556 if (tabb[i].listlen_b > maxkeys) 557 maxkeys = tabb[i].listlen_b; 558 559 /* In descending order by number of keys, map all *b*s */ 560 for (j=maxkeys; j>0; --j) 561 for (i=0; i<blen; ++i) 562 if (tabb[i].listlen_b == j) 563 if (!augment(tabb, tabh, tabq, blen, scramble, smax, &tabb[i], nkeys, 564 i+1, form)) 565 { 566 fprintf(stderr, "fail to map group of size %ld for tab size %ld\n", j, blen); 567 return FALSE; 568 } 569 570 /* Success! We found a perfect hash of all keys into 0..nkeys-1. */ 571 return TRUE; 572 } 573 574 575 /* 576 * Simple case: user gave (a,b). No more mixing, no guessing alen or blen. 577 * This assumes a,b reside in (key->a_k, key->b_k), and final->form == AB_HK. 578 */ 579 static void hash_ab( 580 bstuff **tabb, /* output, tab[] of the perfect hash, length *blen */ 581 ub4 *alen, /* output, 0..alen-1 is range for a of (a,b) */ 582 ub4 *blen, /* output, 0..blen-1 is range for b of (a,b) */ 583 ub4 *salt, /* output, initializes initial hash */ 584 gencode *final, /* code for final hash */ 585 ub4 *scramble, /* input, hash = a^scramble[tab[b]] */ 586 ub4 *smax, /* input, scramble[i] in 0..smax-1 */ 587 key *keys, /* input, keys to hash */ 588 ub4 nkeys, /* input, number of keys being hashed */ 589 hashform *form) /* user directives */ 590 { 591 hstuff *tabh; 592 qstuff *tabq; 593 key *mykey; 594 ub4 i; 595 int used_tab; 596 597 /* initially make smax the first power of two bigger than nkeys */ 598 *smax = ((ub4)1<<phash_log2(nkeys)); 599 scrambleinit(scramble, *smax); 600 601 /* set *alen and *blen based on max A and B from user */ 602 *alen = 1; 603 *blen = 1; 604 for (mykey = keys; mykey != (key *)0; mykey = mykey->next_k) 605 { 606 while (*alen <= mykey->a_k) *alen *= 2; 607 while (*blen <= mykey->b_k) *blen *= 2; 608 } 609 if (*alen > 2**smax) 610 { 611 fprintf(stderr, 612 "perfect.c: Can't deal with (A,B) having A bigger than twice \n"); 613 fprintf(stderr, 614 " the smallest power of two greater or equal to any legal hash.\n"); 615 exit(EXIT_FAILURE); 616 } 617 618 /* allocate working memory */ 619 *tabb = (bstuff *)yasm_xmalloc((size_t)(sizeof(bstuff)*(*blen))); 620 tabq = (qstuff *)yasm_xmalloc(sizeof(qstuff)*(*blen+1)); 621 tabh = (hstuff *)yasm_xmalloc(sizeof(hstuff)*(form->perfect == MINIMAL_HP ? 622 nkeys : *smax)); 623 624 /* check that (a,b) are distinct and put them in tabb indexed by b */ 625 (void)inittab(*tabb, *blen, keys, form, FALSE); 626 627 /* try with smax */ 628 if (!perfect(*tabb, tabh, tabq, *blen, *smax, scramble, nkeys, form)) 629 { 630 if (form->perfect == MINIMAL_HP) 631 { 632 fprintf(stderr, "fatal error: Cannot find perfect hash for user (A,B) pairs\n"); 633 exit(EXIT_FAILURE); 634 } 635 else 636 { 637 /* try with 2*smax */ 638 free((void *)tabh); 639 *smax = *smax * 2; 640 scrambleinit(scramble, *smax); 641 tabh = (hstuff *)yasm_xmalloc(sizeof(hstuff)*(form->perfect == MINIMAL_HP ? 642 nkeys : *smax)); 643 if (!perfect(*tabb, tabh, tabq, *blen, *smax, scramble, nkeys, form)) 644 { 645 fprintf(stderr, "fatal error: Cannot find perfect hash for user (A,B) pairs\n"); 646 exit(EXIT_FAILURE); 647 } 648 } 649 } 650 651 /* check if tab[] was really needed */ 652 for (i=0; i<*blen; ++i) 653 { 654 if ((*tabb)[i].val_b != 0) break; /* assumes permute(0) == 0 */ 655 } 656 used_tab = (i < *blen); 657 658 /* write the code for the perfect hash */ 659 *salt = 1; 660 final->used = 1; 661 if (!used_tab) 662 { 663 sprintf(final->line[0], " unsigned long rsl = a;\n"); 664 } 665 else if (*blen < USE_SCRAMBLE) 666 { 667 sprintf(final->line[0], " unsigned long rsl = (a ^ tab[b]);\n"); 668 } 669 else 670 { 671 sprintf(final->line[0], " unsigned long rsl = (a ^ scramble[tab[b]]);\n"); 672 } 673 674 free((void *)tabq); 675 free((void *)tabh); 676 } 677 678 679 /* guess initial values for alen and blen */ 680 static void initalen( 681 ub4 *alen, /* output, initial alen */ 682 ub4 *blen, /* output, initial blen */ 683 ub4 *smax,/* input, power of two greater or equal to max hash value */ 684 ub4 nkeys, /* number of keys being hashed */ 685 hashform *form) /* user directives */ 686 { 687 /* 688 * Find initial *alen, *blen 689 * Initial alen and blen values were found empirically. Some factors: 690 * 691 * If smax<256 there is no scramble, so tab[b] needs to cover 0..smax-1. 692 * 693 * alen and blen must be powers of 2 because the values in 0..alen-1 and 694 * 0..blen-1 are produced by applying a bitmask to the initial hash function. 695 * 696 * alen must be less than smax, in fact less than nkeys, because otherwise 697 * there would often be no i such that a^scramble[i] is in 0..nkeys-1 for 698 * all the *a*s associated with a given *b*, so there would be no legal 699 * value to assign to tab[b]. This only matters when we're doing a minimal 700 * perfect hash. 701 * 702 * It takes around 800 trials to find distinct (a,b) with nkey=smax*(5/8) 703 * and alen*blen = smax*smax/32. 704 * 705 * Values of blen less than smax/4 never work, and smax/2 always works. 706 * 707 * We want blen as small as possible because it is the number of bytes in 708 * the huge array we must create for the perfect hash. 709 * 710 * When nkey <= smax*(5/8), blen=smax/4 works much more often with 711 * alen=smax/8 than with alen=smax/4. Above smax*(5/8), blen=smax/4 712 * doesn't seem to care whether alen=smax/8 or alen=smax/4. I think it 713 * has something to do with 5/8 = 1/8 * 5. For example examine 80000, 714 * 85000, and 90000 keys with different values of alen. This only matters 715 * if we're doing a minimal perfect hash. 716 * 717 * When alen*blen <= 1<<UB4BITS, the initial hash must produce one integer. 718 * Bigger than that it must produce two integers, which increases the 719 * cost of the hash per character hashed. 720 */ 721 if (form->perfect == NORMAL_HP) 722 { 723 if ((form->speed == FAST_HS) && (nkeys > *smax*0.8)) 724 { 725 *smax = *smax * 2; 726 } 727 728 *alen = ((form->hashtype==INT_HT) && *smax>131072) ? 729 ((ub4)1<<(UB4BITS-phash_log2(*blen))) : /* distinct keys => distinct (A,B) */ 730 *smax; /* no reason to restrict alen to smax/2 */ 731 if ((form->hashtype == INT_HT) && *smax < 32) 732 *blen = *smax; /* go for function speed not space */ 733 else if (*smax/4 <= (1<<14)) 734 *blen = ((nkeys <= *smax*0.56) ? *smax/32 : 735 (nkeys <= *smax*0.74) ? *smax/16 : *smax/8); 736 else 737 *blen = ((nkeys <= *smax*0.6) ? *smax/16 : 738 (nkeys <= *smax*0.8) ? *smax/8 : *smax/4); 739 740 if ((form->speed == FAST_HS) && (*blen < *smax/8)) 741 *blen = *smax/8; 742 743 if (*alen < 1) *alen = 1; 744 if (*blen < 1) *blen = 1; 745 } 746 else 747 { 748 switch(phash_log2(*smax)) 749 { 750 case 0: 751 *alen = 1; 752 *blen = 1; 753 case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: 754 *alen = (form->perfect == NORMAL_HP) ? *smax : *smax/2; 755 *blen = *smax/2; 756 break; 757 case 9: 758 case 10: 759 case 11: 760 case 12: 761 case 13: 762 case 14: 763 case 15: 764 case 16: 765 case 17: 766 if (form->speed == FAST_HS) 767 { 768 *alen = *smax/2; 769 *blen = *smax/4; 770 } 771 else if (*smax/4 < USE_SCRAMBLE) 772 { 773 *alen = ((nkeys <= *smax*0.52) ? *smax/8 : *smax/4); 774 *blen = ((nkeys <= *smax*0.52) ? *smax/8 : *smax/4); 775 } 776 else 777 { 778 *alen = ((nkeys <= *smax*(5.0/8.0)) ? *smax/8 : 779 (nkeys <= *smax*(3.0/4.0)) ? *smax/4 : *smax/2); 780 *blen = *smax/4; /* always give the small size a shot */ 781 } 782 break; 783 case 18: 784 if (form->speed == FAST_HS) 785 { 786 *alen = *smax/2; 787 *blen = *smax/2; 788 } 789 else 790 { 791 *alen = *smax/8; /* never require the multiword hash */ 792 *blen = (nkeys <= *smax*(5.0/8.0)) ? *smax/4 : *smax/2; 793 } 794 break; 795 case 19: 796 case 20: 797 *alen = (nkeys <= *smax*(5.0/8.0)) ? *smax/8 : *smax/2; 798 *blen = (nkeys <= *smax*(5.0/8.0)) ? *smax/4 : *smax/2; 799 break; 800 default: 801 *alen = *smax/2; /* just find a hash as quick as possible */ 802 *blen = *smax/2; /* we'll be thrashing virtual memory at this size */ 803 break; 804 } 805 } 806 } 807 808 /* 809 ** Try to find a perfect hash function. 810 ** Return the successful initializer for the initial hash. 811 ** Return 0 if no perfect hash could be found. 812 */ 813 void findhash( 814 bstuff **tabb, /* output, tab[] of the perfect hash, length *blen */ 815 hstuff **tabh, /* output, table of keys indexed by hash value */ 816 ub4 *alen, /* output, 0..alen-1 is range for a of (a,b) */ 817 ub4 *blen, /* output, 0..blen-1 is range for b of (a,b) */ 818 ub4 *salt, /* output, initializes initial hash */ 819 gencode *final, /* code for final hash */ 820 ub4 *scramble, /* input, hash = a^scramble[tab[b]] */ 821 ub4 *smax, /* input, scramble[i] in 0..smax-1 */ 822 key *keys, /* input, keys to hash */ 823 ub4 nkeys, /* input, number of keys being hashed */ 824 hashform *form) /* user directives */ 825 { 826 ub4 bad_initkey; /* how many times did initkey fail? */ 827 ub4 bad_perfect; /* how many times did perfect fail? */ 828 ub4 trysalt; /* trial initializer for initial hash */ 829 ub4 maxalen; 830 qstuff *tabq; /* table of stuff indexed by queue value, used by augment */ 831 832 /* The case of (A,B) supplied by the user is a special case */ 833 if (form->hashtype == AB_HT) 834 { 835 hash_ab(tabb, alen, blen, salt, final, 836 scramble, smax, keys, nkeys, form); 837 return; 838 } 839 840 /* guess initial values for smax, alen and blen */ 841 *smax = ((ub4)1<<phash_log2(nkeys)); 842 initalen(alen, blen, smax, nkeys, form); 843 844 scrambleinit(scramble, *smax); 845 846 maxalen = (form->perfect == MINIMAL_HP) ? *smax/2 : *smax; 847 848 /* allocate working memory */ 849 *tabb = (bstuff *)yasm_xmalloc((size_t)(sizeof(bstuff)*(*blen))); 850 tabq = (qstuff *)yasm_xmalloc(sizeof(qstuff)*(*blen+1)); 851 *tabh = (hstuff *)yasm_xmalloc(sizeof(hstuff)*(form->perfect == MINIMAL_HP ? 852 nkeys : *smax)); 853 854 /* Actually find the perfect hash */ 855 *salt = 0; 856 bad_initkey = 0; 857 bad_perfect = 0; 858 for (trysalt=1; ; ++trysalt) 859 { 860 ub4 rslinit; 861 /* Try to find distinct (A,B) for all keys */ 862 863 rslinit = initkey(keys, nkeys, *tabb, *alen, *blen, *smax, trysalt, 864 form, final); 865 866 if (rslinit == 2) 867 { /* initkey actually found a perfect hash, not just distinct (a,b) */ 868 *salt = 1; 869 *blen = 0; 870 break; 871 } 872 else if (rslinit == 0) 873 { 874 /* didn't find distinct (a,b) */ 875 if (++bad_initkey >= RETRY_INITKEY) 876 { 877 /* Try to put more bits in (A,B) to make distinct (A,B) more likely */ 878 if (*alen < maxalen) 879 { 880 *alen *= 2; 881 } 882 else if (*blen < *smax) 883 { 884 *blen *= 2; 885 free(tabq); 886 free(*tabb); 887 *tabb = (bstuff *)yasm_xmalloc((size_t)(sizeof(bstuff)*(*blen))); 888 tabq = (qstuff *)yasm_xmalloc((size_t)(sizeof(qstuff)*(*blen+1))); 889 } 890 else 891 { 892 duplicates(*tabb, *blen, keys, form); /* check for duplicates */ 893 fprintf(stderr, "fatal error: Cannot perfect hash: cannot find distinct (A,B)\n"); 894 exit(EXIT_FAILURE); 895 } 896 bad_initkey = 0; 897 bad_perfect = 0; 898 } 899 continue; /* two keys have same (a,b) pair */ 900 } 901 902 /* Given distinct (A,B) for all keys, build a perfect hash */ 903 if (!perfect(*tabb, *tabh, tabq, *blen, *smax, scramble, nkeys, form)) 904 { 905 if ((form->hashtype != INT_HT && ++bad_perfect >= RETRY_PERFECT) || 906 (form->hashtype == INT_HT && ++bad_perfect >= RETRY_HEX)) 907 { 908 if (*blen < *smax) 909 { 910 *blen *= 2; 911 free(*tabb); 912 free(tabq); 913 *tabb = (bstuff *)yasm_xmalloc((size_t)(sizeof(bstuff)*(*blen))); 914 tabq = (qstuff *)yasm_xmalloc((size_t)(sizeof(qstuff)*(*blen+1))); 915 --trysalt; /* we know this salt got distinct (A,B) */ 916 } 917 else 918 { 919 fprintf(stderr, "fatal error: Cannot perfect hash: cannot build tab[]\n"); 920 exit(EXIT_FAILURE); 921 } 922 bad_perfect = 0; 923 } 924 continue; 925 } 926 927 *salt = trysalt; 928 break; 929 } 930 931 /* free working memory */ 932 free((void *)tabq); 933 } 934 935 #if 0 936 /* 937 ------------------------------------------------------------------------------ 938 Input/output type routines 939 ------------------------------------------------------------------------------ 940 */ 941 942 /* get the list of keys */ 943 static void getkeys(keys, nkeys, textroot, keyroot, form) 944 key **keys; /* list of all keys */ 945 ub4 *nkeys; /* number of keys */ 946 reroot *textroot; /* get space to store key text */ 947 reroot *keyroot; /* get space for keys */ 948 hashform *form; /* user directives */ 949 { 950 key *mykey; 951 char *mytext; 952 mytext = (char *)renew(textroot); 953 *keys = 0; 954 *nkeys = 0; 955 while (fgets(mytext, MAXKEYLEN, stdin)) 956 { 957 mykey = (key *)renew(keyroot); 958 if (form->mode == AB_HM) 959 { 960 sscanf(mytext, "%lx %lx ", &mykey->a_k, &mykey->b_k); 961 } 962 else if (form->mode == ABDEC_HM) 963 { 964 sscanf(mytext, "%ld %ld ", &mykey->a_k, &mykey->b_k); 965 } 966 else if (form->mode == HEX_HM) 967 { 968 sscanf(mytext, "%lx ", &mykey->hash_k); 969 } 970 else if (form->mode == DECIMAL_HM) 971 { 972 sscanf(mytext, "%ld ", &mykey->hash_k); 973 } 974 else 975 { 976 mykey->name_k = (ub1 *)mytext; 977 mytext = (char *)renew(textroot); 978 mykey->len_k = (ub4)(strlen((char *)mykey->name_k)-1); 979 } 980 mykey->next_k = *keys; 981 *keys = mykey; 982 ++*nkeys; 983 } 984 redel(textroot, mytext); 985 } 986 987 /* make the .c file */ 988 static void make_c(tab, smax, blen, scramble, final, form) 989 bstuff *tab; /* table indexed by b */ 990 ub4 smax; /* range of scramble[] */ 991 ub4 blen; /* b in 0..blen-1, power of 2 */ 992 ub4 *scramble; /* used in final hash */ 993 gencode *final; /* code for the final hash */ 994 hashform *form; /* user directives */ 995 { 996 ub4 i; 997 FILE *f; 998 f = fopen("phash.c", "w"); 999 fprintf(f, "/* table for the mapping for the perfect hash */\n"); 1000 fprintf(f, "#include \"lookupa.h\"\n"); 1001 fprintf(f, "\n"); 1002 if (blen >= USE_SCRAMBLE) 1003 { 1004 fprintf(f, "/* A way to make the 1-byte values in tab bigger */\n"); 1005 if (smax > UB2MAXVAL+1) 1006 { 1007 fprintf(f, "unsigned long scramble[] = {\n"); 1008 for (i=0; i<=UB1MAXVAL; i+=4) 1009 fprintf(f, "0x%.8lx, 0x%.8lx, 0x%.8lx, 0x%.8lx,\n", 1010 scramble[i+0], scramble[i+1], scramble[i+2], scramble[i+3]); 1011 } 1012 else 1013 { 1014 fprintf(f, "unsigned short scramble[] = {\n"); 1015 for (i=0; i<=UB1MAXVAL; i+=8) 1016 fprintf(f, 1017 "0x%.4lx, 0x%.4lx, 0x%.4lx, 0x%.4lx, 0x%.4lx, 0x%.4lx, 0x%.4lx, 0x%.4lx,\n", 1018 scramble[i+0], scramble[i+1], scramble[i+2], scramble[i+3], 1019 scramble[i+4], scramble[i+5], scramble[i+6], scramble[i+7]); 1020 } 1021 fprintf(f, "};\n"); 1022 fprintf(f, "\n"); 1023 } 1024 if (blen > 0) 1025 { 1026 fprintf(f, "/* small adjustments to _a_ to make values distinct */\n"); 1027 1028 if (smax <= UB1MAXVAL+1 || blen >= USE_SCRAMBLE) 1029 fprintf(f, "unsigned char tab[] = {\n"); 1030 else 1031 fprintf(f, "unsigned short tab[] = {\n"); 1032 1033 if (blen < 16) 1034 { 1035 for (i=0; i<blen; ++i) fprintf(f, "%3d,", scramble[tab[i].val_b]); 1036 } 1037 else if (blen <= 1024) 1038 { 1039 for (i=0; i<blen; i+=16) 1040 fprintf(f, "%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,\n", 1041 scramble[tab[i+0].val_b], scramble[tab[i+1].val_b], 1042 scramble[tab[i+2].val_b], scramble[tab[i+3].val_b], 1043 scramble[tab[i+4].val_b], scramble[tab[i+5].val_b], 1044 scramble[tab[i+6].val_b], scramble[tab[i+7].val_b], 1045 scramble[tab[i+8].val_b], scramble[tab[i+9].val_b], 1046 scramble[tab[i+10].val_b], scramble[tab[i+11].val_b], 1047 scramble[tab[i+12].val_b], scramble[tab[i+13].val_b], 1048 scramble[tab[i+14].val_b], scramble[tab[i+15].val_b]); 1049 } 1050 else if (blen < USE_SCRAMBLE) 1051 { 1052 for (i=0; i<blen; i+=8) 1053 fprintf(f, "%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,\n", 1054 scramble[tab[i+0].val_b], scramble[tab[i+1].val_b], 1055 scramble[tab[i+2].val_b], scramble[tab[i+3].val_b], 1056 scramble[tab[i+4].val_b], scramble[tab[i+5].val_b], 1057 scramble[tab[i+6].val_b], scramble[tab[i+7].val_b]); 1058 } 1059 else 1060 { 1061 for (i=0; i<blen; i+=16) 1062 fprintf(f, "%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,\n", 1063 tab[i+0].val_b, tab[i+1].val_b, 1064 tab[i+2].val_b, tab[i+3].val_b, 1065 tab[i+4].val_b, tab[i+5].val_b, 1066 tab[i+6].val_b, tab[i+7].val_b, 1067 tab[i+8].val_b, tab[i+9].val_b, 1068 tab[i+10].val_b, tab[i+11].val_b, 1069 tab[i+12].val_b, tab[i+13].val_b, 1070 tab[i+14].val_b, tab[i+15].val_b); 1071 } 1072 fprintf(f, "};\n"); 1073 fprintf(f, "\n"); 1074 } 1075 fprintf(f, "/* The hash function */\n"); 1076 switch(form->mode) 1077 { 1078 case NORMAL_HM: 1079 fprintf(f, "ub4 phash(key, len)\n"); 1080 fprintf(f, "char *key;\n"); 1081 fprintf(f, "int len;\n"); 1082 break; 1083 case INLINE_HM: 1084 case HEX_HM: 1085 case DECIMAL_HM: 1086 fprintf(f, "ub4 phash(val)\n"); 1087 fprintf(f, "ub4 val;\n"); 1088 break; 1089 case AB_HM: 1090 case ABDEC_HM: 1091 fprintf(f, "ub4 phash(a,b)\n"); 1092 fprintf(f, "ub4 a;\n"); 1093 fprintf(f, "ub4 b;\n"); 1094 break; 1095 } 1096 fprintf(f, "{\n"); 1097 for (i=0; i<final->used; ++i) 1098 fprintf(f, final->line[i]); 1099 fprintf(f, " return rsl;\n"); 1100 fprintf(f, "}\n"); 1101 fprintf(f, "\n"); 1102 fclose(f); 1103 } 1104 1105 /* 1106 ------------------------------------------------------------------------------ 1107 Read in the keys, find the hash, and write the .c and .h files 1108 ------------------------------------------------------------------------------ 1109 */ 1110 static void driver(form) 1111 hashform *form; /* user directives */ 1112 { 1113 ub4 nkeys; /* number of keys */ 1114 key *keys; /* head of list of keys */ 1115 bstuff *tab; /* table indexed by b */ 1116 ub4 smax; /* scramble[] values in 0..smax-1, a power of 2 */ 1117 ub4 alen; /* a in 0..alen-1, a power of 2 */ 1118 ub4 blen; /* b in 0..blen-1, a power of 2 */ 1119 ub4 salt; /* a parameter to the hash function */ 1120 reroot *textroot; /* MAXKEYLEN-character text lines */ 1121 reroot *keyroot; /* source of keys */ 1122 gencode final; /* code for final hash */ 1123 ub4 i; 1124 ub4 scramble[SCRAMBLE_LEN]; /* used in final hash function */ 1125 char buf[10][80]; /* buffer for generated code */ 1126 char *buf2[10]; /* also for generated code */ 1127 1128 /* set up memory sources */ 1129 textroot = remkroot((size_t)MAXKEYLEN); 1130 keyroot = remkroot(sizeof(key)); 1131 1132 /* set up code for final hash */ 1133 final.line = buf2; 1134 final.used = 0; 1135 final.len = 10; 1136 for (i=0; i<10; ++i) final.line[i] = buf[i]; 1137 1138 /* read in the list of keywords */ 1139 getkeys(&keys, &nkeys, textroot, keyroot, form); 1140 1141 /* find the hash */ 1142 findhash(&tab, &alen, &blen, &salt, &final, 1143 scramble, &smax, keys, nkeys, form); 1144 1145 /* generate the phash.c file */ 1146 make_c(tab, smax, blen, scramble, &final, form); 1147 1148 /* clean up memory sources */ 1149 refree(textroot); 1150 refree(keyroot); 1151 free((void *)tab); 1152 } 1153 1154 1155 /* Interpret arguments and call the driver */ 1156 /* See usage_error for the expected arguments */ 1157 int main(argc, argv) 1158 int argc; 1159 char **argv; 1160 { 1161 int mode_given = FALSE; 1162 int minimal_given = FALSE; 1163 int speed_given = FALSE; 1164 hashform form; 1165 char *c; 1166 1167 /* default behavior */ 1168 form.mode = NORMAL_HM; 1169 form.hashtype = STRING_HT; 1170 form.perfect = MINIMAL_HP; 1171 form.speed = SLOW_HS; 1172 1173 /* Generate the [minimal] perfect hash */ 1174 driver(&form); 1175 1176 return EXIT_SUCCESS; 1177 } 1178 #endif 1179