Lines Matching refs:blen
27 0..*blen*-1. A fast hash function determines both a and b
156 ub4 blen, /* length of tabb */
164 memset((void *)tabb, 0, (size_t)(sizeof(bstuff)*blen));
197 ub4 blen, /* (a,b) has b in 0..blen-1, a power of 2 */
203 if (phash_log2(alen)+phash_log2(blen) > UB4BITS)
213 mykey->b_k = state[1]&(blen-1);
224 alen-1, blen-1);
228 ub4 loga = phash_log2(alen); /* log based 2 of blen */
235 mykey->b_k = (blen > 1) ? hash&(blen-1) : 0;
244 else if (blen < USE_SCRAMBLE)
247 UB4BITS-phash_log2(alen), blen-1);
252 UB4BITS-phash_log2(alen), blen-1);
263 ub4 blen, /* (a,b) has b in 0..blen-1, a power of 2 */
270 ub4 blog = phash_log2(blen);
284 mykey->b_k = (blen > 1) ? (hash >> (UB4BITS-blog)) : 0;
291 else if (blen < USE_SCRAMBLE)
316 ub4 blen, /* (a,b) has b in 0..blen-1, a power of 2 */
326 initnorm(keys, alen, blen, smax, salt, final);
329 initinl(keys, alen, blen, smax, salt, final);
334 finished = inithex(keys, nkeys, alen, blen, smax, salt, final, form);
350 return inittab(tabb, blen, keys, form, FALSE);
356 ub4 blen, /* length of tabb, a power of 2 */
364 (void)inittab(tabb, blen, keys, form, TRUE);
367 for (i=0; i<blen; ++i)
379 ub4 blen,
423 apply(tabb, tabh, tabq, blen, scramble, tail, TRUE);
456 ub4 blen, /* length of tabb */
466 ub4 limit=((blen < USE_SCRAMBLE) ? smax : UB1MAXVAL+1);
524 if (apply(tabb, tabh, tabq, blen, scramble, tail, FALSE))
540 ub4 blen,
553 memset((void *)tabq, 0, (size_t)(sizeof(qstuff)*(blen+1)));
555 for (maxkeys=0,i=0; i<blen; ++i)
561 for (i=0; i<blen; ++i)
563 if (!augment(tabb, tabh, tabq, blen, scramble, smax, &tabb[i], nkeys,
566 fprintf(stderr, "fail to map group of size %ld for tab size %ld\n", j, blen);
576 * Simple case: user gave (a,b). No more mixing, no guessing alen or blen.
580 bstuff **tabb, /* output, tab[] of the perfect hash, length *blen */
582 ub4 *blen, /* output, 0..blen-1 is range for b of (a,b) */
601 /* set *alen and *blen based on max A and B from user */
603 *blen = 1;
607 while (*blen <= mykey->b_k) *blen *= 2;
619 *tabb = (bstuff *)yasm_xmalloc((size_t)(sizeof(bstuff)*(*blen)));
620 tabq = (qstuff *)yasm_xmalloc(sizeof(qstuff)*(*blen+1));
625 (void)inittab(*tabb, *blen, keys, form, FALSE);
628 if (!perfect(*tabb, tabh, tabq, *blen, *smax, scramble, nkeys, form))
643 if (!perfect(*tabb, tabh, tabq, *blen, *smax, scramble, nkeys, form))
652 for (i=0; i<*blen; ++i)
656 used_tab = (i < *blen);
665 else if (*blen < USE_SCRAMBLE)
679 /* guess initial values for alen and blen */
682 ub4 *blen, /* output, initial blen */
688 * Find initial *alen, *blen
689 * Initial alen and blen values were found empirically. Some factors:
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.
703 * and alen*blen = smax*smax/32.
705 * Values of blen less than smax/4 never work, and smax/2 always works.
707 * We want blen as small as possible because it is the number of bytes in
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
717 * When alen*blen <= 1<<UB4BITS, the initial hash must produce one integer.
729 ((ub4)1<<(UB4BITS-phash_log2(*blen))) : /* distinct keys => distinct (A,B) */
732 *blen = *smax; /* go for function speed not space */
734 *blen = ((nkeys <= *smax*0.56) ? *smax/32 :
737 *blen = ((nkeys <= *smax*0.6) ? *smax/16 :
740 if ((form->speed == FAST_HS) && (*blen < *smax/8))
741 *blen = *smax/8;
744 if (*blen < 1) *blen = 1;
752 *blen = 1;
755 *blen = *smax/2;
769 *blen = *smax/4;
774 *blen = ((nkeys <= *smax*0.52) ? *smax/8 : *smax/4);
780 *blen = *smax/4; /* always give the small size a shot */
787 *blen = *smax/2;
792 *blen = (nkeys <= *smax*(5.0/8.0)) ? *smax/4 : *smax/2;
798 *blen = (nkeys <= *smax*(5.0/8.0)) ? *smax/4 : *smax/2;
802 *blen = *smax/2; /* we'll be thrashing virtual memory at this size */
814 bstuff **tabb, /* output, tab[] of the perfect hash, length *blen */
817 ub4 *blen, /* output, 0..blen-1 is range for b of (a,b) */
835 hash_ab(tabb, alen, blen, salt, final,
840 /* guess initial values for smax, alen and blen */
842 initalen(alen, blen, smax, nkeys, form);
849 *tabb = (bstuff *)yasm_xmalloc((size_t)(sizeof(bstuff)*(*blen)));
850 tabq = (qstuff *)yasm_xmalloc(sizeof(qstuff)*(*blen+1));
863 rslinit = initkey(keys, nkeys, *tabb, *alen, *blen, *smax, trysalt,
869 *blen = 0;
882 else if (*blen < *smax)
884 *blen *= 2;
887 *tabb = (bstuff *)yasm_xmalloc((size_t)(sizeof(bstuff)*(*blen)));
888 tabq = (qstuff *)yasm_xmalloc((size_t)(sizeof(qstuff)*(*blen+1)));
892 duplicates(*tabb, *blen, keys, form); /* check for duplicates */
903 if (!perfect(*tabb, *tabh, tabq, *blen, *smax, scramble, nkeys, form))
908 if (*blen < *smax)
910 *blen *= 2;
913 *tabb = (bstuff *)yasm_xmalloc((size_t)(sizeof(bstuff)*(*blen)));
914 tabq = (qstuff *)yasm_xmalloc((size_t)(sizeof(qstuff)*(*blen+1)));
988 static void make_c(tab, smax, blen, scramble, final, form)
991 ub4 blen; /* b in 0..blen-1, power of 2 */
1002 if (blen >= USE_SCRAMBLE)
1024 if (blen > 0)
1028 if (smax <= UB1MAXVAL+1 || blen >= USE_SCRAMBLE)
1033 if (blen < 16)
1035 for (i=0; i<blen; ++i) fprintf(f, "%3d,", scramble[tab[i].val_b]);
1037 else if (blen <= 1024)
1039 for (i=0; i<blen; i+=16)
1050 else if (blen < USE_SCRAMBLE)
1052 for (i=0; i<blen; i+=8)
1061 for (i=0; i<blen; i+=16)
1118 ub4 blen; /* b in 0..blen-1, a power of 2 */
1142 findhash(&tab, &alen, &blen, &salt, &final,
1146 make_c(tab, smax, blen, scramble, &final, form);
