rpm 5.3.12
rpmio/lookup3.c
Go to the documentation of this file.
00001 /* -------------------------------------------------------------------- */
00002 /*
00003  * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
00004  * 
00005  * These are functions for producing 32-bit hashes for hash table lookup.
00006  * jlu32w(), jlu32l(), jlu32lpair(), jlu32b(), _JLU3_MIX(), and _JLU3_FINAL() 
00007  * are externally useful functions.  Routines to test the hash are included 
00008  * if SELF_TEST is defined.  You can use this free for any purpose.  It's in
00009  * the public domain.  It has no warranty.
00010  * 
00011  * You probably want to use jlu32l().  jlu32l() and jlu32b()
00012  * hash byte arrays.  jlu32l() is is faster than jlu32b() on
00013  * little-endian machines.  Intel and AMD are little-endian machines.
00014  * On second thought, you probably want jlu32lpair(), which is identical to
00015  * jlu32l() except it returns two 32-bit hashes for the price of one.  
00016  * You could implement jlu32bpair() if you wanted but I haven't bothered here.
00017  * 
00018  * If you want to find a hash of, say, exactly 7 integers, do
00019  *   a = i1;  b = i2;  c = i3;
00020  *   _JLU3_MIX(a,b,c);
00021  *   a += i4; b += i5; c += i6;
00022  *   _JLU3_MIX(a,b,c);
00023  *   a += i7;
00024  *   _JLU3_FINAL(a,b,c);
00025  * then use c as the hash value.  If you have a variable size array of
00026  * 4-byte integers to hash, use jlu32w().  If you have a byte array (like
00027  * a character string), use jlu32l().  If you have several byte arrays, or
00028  * a mix of things, see the comments above jlu32l().  
00029  * 
00030  * Why is this so big?  I read 12 bytes at a time into 3 4-byte integers, 
00031  * then mix those integers.  This is fast (you can do a lot more thorough
00032  * mixing with 12*3 instructions on 3 integers than you can with 3 instructions
00033  * on 1 byte), but shoehorning those bytes into integers efficiently is messy.
00034 */
00035 /* -------------------------------------------------------------------- */
00036 
00037 #include "system.h"
00038 #include "rpmiotypes.h"
00039 #include "debug.h"
00040 
00041 #ifdef WITH_VALGRIND
00042 #if !defined(RUNNING_ON_VALGRIND)
00043 #define RUNNING_ON_VALGRIND     0
00044 #endif
00045 #if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__)
00046 #  define UNLIKELY(value) __builtin_expect((value), 0) && (value > 0 || (value = RUNNING_ON_VALGRIND))
00047 #else
00048 #  define UNLIKELY(value) (value) && (value > 0 || (value = RUNNING_ON_VALGRIND))
00049 #endif
00050 static int _running_on_valgrind = -1;
00051 #endif
00052 
00053 #if defined(_JLU3_SELFTEST)
00054 # define _JLU3_jlu32w           1
00055 # define _JLU3_jlu32l           1
00056 # define _JLU3_jlu32lpair       1
00057 # define _JLU3_jlu32b           1
00058 #endif
00059 
00060 /*@-redef@*/
00061 /*@unchecked@*/
00062 static const union _dbswap {
00063     const rpmuint32_t ui;
00064     const unsigned char uc[4];
00065 } endian = { .ui = 0x11223344 };
00066 # define HASH_LITTLE_ENDIAN     (endian.uc[0] == (unsigned char) 0x44)
00067 # define HASH_BIG_ENDIAN        (endian.uc[0] == (unsigned char) 0x11)
00068 /*@=redef@*/
00069 
00070 #ifndef ROTL32
00071 # define ROTL32(x, s) (((x) << (s)) | ((x) >> (32 - (s))))
00072 #endif
00073 
00074 /* NOTE: The _size parameter should be in bytes. */
00075 #define _JLU3_INIT(_h, _size)   (0xdeadbeef + ((rpmuint32_t)(_size)) + (_h))
00076 
00077 /* -------------------------------------------------------------------- */
00078 /*
00079  * _JLU3_MIX -- mix 3 32-bit values reversibly.
00080  * 
00081  * This is reversible, so any information in (a,b,c) before _JLU3_MIX() is
00082  * still in (a,b,c) after _JLU3_MIX().
00083  * 
00084  * If four pairs of (a,b,c) inputs are run through _JLU3_MIX(), or through
00085  * _JLU3_MIX() in reverse, there are at least 32 bits of the output that
00086  * are sometimes the same for one pair and different for another pair.
00087  * This was tested for:
00088  * * pairs that differed by one bit, by two bits, in any combination
00089  *   of top bits of (a,b,c), or in any combination of bottom bits of
00090  *   (a,b,c).
00091  * * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
00092  *   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
00093  *   is commonly produced by subtraction) look like a single 1-bit
00094  *   difference.
00095  * * the base values were pseudorandom, all zero but one bit set, or 
00096  *   all zero plus a counter that starts at zero.
00097  * 
00098  * Some k values for my "a-=c; a^=ROTL32(c,k); c+=b;" arrangement that
00099  * satisfy this are
00100  *     4  6  8 16 19  4
00101  *     9 15  3 18 27 15
00102  *    14  9  3  7 17  3
00103  * Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
00104  * for "differ" defined as + with a one-bit base and a two-bit delta.  I
00105  * used http://burtleburtle.net/bob/hash/avalanche.html to choose 
00106  * the operations, constants, and arrangements of the variables.
00107  * 
00108  * This does not achieve avalanche.  There are input bits of (a,b,c)
00109  * that fail to affect some output bits of (a,b,c), especially of a.  The
00110  * most thoroughly mixed value is c, but it doesn't really even achieve
00111  * avalanche in c.
00112  * 
00113  * This allows some parallelism.  Read-after-writes are good at doubling
00114  * the number of bits affected, so the goal of mixing pulls in the opposite
00115  * direction as the goal of parallelism.  I did what I could.  Rotates
00116  * seem to cost as much as shifts on every machine I could lay my hands
00117  * on, and rotates are much kinder to the top and bottom bits, so I used
00118  * rotates.
00119  */
00120 /* -------------------------------------------------------------------- */
00121 #define _JLU3_MIX(a,b,c) \
00122 { \
00123   a -= c;  a ^= ROTL32(c, 4);  c += b; \
00124   b -= a;  b ^= ROTL32(a, 6);  a += c; \
00125   c -= b;  c ^= ROTL32(b, 8);  b += a; \
00126   a -= c;  a ^= ROTL32(c,16);  c += b; \
00127   b -= a;  b ^= ROTL32(a,19);  a += c; \
00128   c -= b;  c ^= ROTL32(b, 4);  b += a; \
00129 }
00130 
00131 /* -------------------------------------------------------------------- */
00155 /* -------------------------------------------------------------------- */
00156 #define _JLU3_FINAL(a,b,c) \
00157 { \
00158   c ^= b; c -= ROTL32(b,14); \
00159   a ^= c; a -= ROTL32(c,11); \
00160   b ^= a; b -= ROTL32(a,25); \
00161   c ^= b; c -= ROTL32(b,16); \
00162   a ^= c; a -= ROTL32(c,4);  \
00163   b ^= a; b -= ROTL32(a,14); \
00164   c ^= b; c -= ROTL32(b,24); \
00165 }
00166 
00167 #if defined(_JLU3_jlu32w)
00168 rpmuint32_t jlu32w(rpmuint32_t h, /*@null@*/ const rpmuint32_t *k, size_t size)
00169         /*@*/;
00170 /* -------------------------------------------------------------------- */
00187 /* -------------------------------------------------------------------- */
00188 rpmuint32_t jlu32w(rpmuint32_t h, const rpmuint32_t *k, size_t size)
00189 {
00190     rpmuint32_t a = _JLU3_INIT(h, (size * sizeof(*k)));
00191     rpmuint32_t b = a;
00192     rpmuint32_t c = a;
00193 
00194     if (k == NULL)
00195         goto exit;
00196 
00197     /*----------------------------------------------- handle most of the key */
00198     while (size > 3) {
00199         a += k[0];
00200         b += k[1];
00201         c += k[2];
00202         _JLU3_MIX(a,b,c);
00203         size -= 3;
00204         k += 3;
00205     }
00206 
00207     /*----------------------------------------- handle the last 3 rpmuint32_t's */
00208     switch (size) {
00209     case 3 : c+=k[2];
00210     case 2 : b+=k[1];
00211     case 1 : a+=k[0];
00212         _JLU3_FINAL(a,b,c);
00213         /*@fallthrough@*/
00214     case 0:
00215         break;
00216     }
00217     /*---------------------------------------------------- report the result */
00218 exit:
00219     return c;
00220 }
00221 #endif  /* defined(_JLU3_jlu32w) */
00222 
00223 #if defined(_JLU3_jlu32l)
00224 rpmuint32_t jlu32l(rpmuint32_t h, const void *key, size_t size)
00225         /*@*/;
00226 /* -------------------------------------------------------------------- */
00227 /*
00228  * jlu32l() -- hash a variable-length key into a 32-bit value
00229  *   h       : can be any 4-byte value
00230  *   k       : the key (the unaligned variable-length array of bytes)
00231  *   size    : the size of the key, counting by bytes
00232  * Returns a 32-bit value.  Every bit of the key affects every bit of
00233  * the return value.  Two keys differing by one or two bits will have
00234  * totally different hash values.
00235  * 
00236  * The best hash table sizes are powers of 2.  There is no need to do
00237  * mod a prime (mod is sooo slow!).  If you need less than 32 bits,
00238  * use a bitmask.  For example, if you need only 10 bits, do
00239  *   h = (h & hashmask(10));
00240  * In which case, the hash table should have hashsize(10) elements.
00241  * 
00242  * If you are hashing n strings (rpmuint8_t **)k, do it like this:
00243  *   for (i=0, h=0; i<n; ++i) h = jlu32l(h, k[i], len[i]);
00244  * 
00245  * By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
00246  * code any way you wish, private, educational, or commercial.  It's free.
00247  * 
00248  * Use for hash table lookup, or anything where one collision in 2^^32 is
00249  * acceptable.  Do NOT use for cryptographic purposes.
00250  *
00251  * @param h             the previous hash, or an arbitrary value
00252  * @param *k            the key, an array of rpmuint8_t values
00253  * @param size          the size of the key
00254  * @return              the lookup3 hash
00255  */
00256 /* -------------------------------------------------------------------- */
00257 rpmuint32_t jlu32l(rpmuint32_t h, const void *key, size_t size)
00258 {
00259     union { const void *ptr; size_t i; } u;
00260     rpmuint32_t a = _JLU3_INIT(h, size);
00261     rpmuint32_t b = a;
00262     rpmuint32_t c = a;
00263 
00264     if (key == NULL)
00265         goto exit;
00266 
00267     u.ptr = key;
00268     if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
00269         const rpmuint32_t *k = (const rpmuint32_t *)key;        /* read 32-bit chunks */
00270 
00271     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
00272         while (size > 12) {
00273             a += k[0];
00274             b += k[1];
00275             c += k[2];
00276             _JLU3_MIX(a,b,c);
00277             size -= 12;
00278             k += 3;
00279         }
00280 
00281         /*------------------------- handle the last (probably partial) block */
00282         /* 
00283          * "k[2]&0xffffff" actually reads beyond the end of the string, but
00284          * then masks off the part it's not allowed to read.  Because the
00285          * string is aligned, the masked-off tail is in the same word as the
00286          * rest of the string.  Every machine with memory protection I've seen
00287          * does it on word boundaries, so is OK with this.  But VALGRIND will
00288          * still catch it and complain.  The masking trick does make the hash
00289          * noticably faster for short strings (like English words).
00290          */
00291 #ifdef WITH_VALGRIND
00292       if (UNLIKELY(_running_on_valgrind)) {
00293         const rpmuint8_t  * k8 = (const rpmuint8_t *)k;
00294 
00295         switch (size) {
00296         case 12:        c += k[2]; b+=k[1]; a+=k[0];    break;
00297         case 11:        c += ((rpmuint32_t)k8[10])<<16; /*@fallthrough@*/
00298         case 10:        c += ((rpmuint32_t)k8[9])<<8;   /*@fallthrough@*/
00299         case  9:        c += k8[8];                     /*@fallthrough@*/
00300         case  8:        b += k[1]; a+=k[0];             break;
00301         case  7:        b += ((rpmuint32_t)k8[6])<<16;  /*@fallthrough@*/
00302         case  6:        b += ((rpmuint32_t)k8[5])<<8;   /*@fallthrough@*/
00303         case  5:        b += k8[4];                     /*@fallthrough@*/
00304         case  4:        a += k[0];                      break;
00305         case  3:        a += ((rpmuint32_t)k8[2])<<16;  /*@fallthrough@*/
00306         case  2:        a += ((rpmuint32_t)k8[1])<<8;   /*@fallthrough@*/
00307         case  1:        a += k8[0];                     break;
00308         case  0:        goto exit;
00309         }
00310 
00311       } else
00312 #endif
00313       {
00314         switch (size) {
00315         case 12:        c += k[2]; b+=k[1]; a+=k[0]; break;
00316         case 11:        c += k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
00317         case 10:        c += k[2]&0xffff; b+=k[1]; a+=k[0]; break;
00318         case  9:        c += k[2]&0xff; b+=k[1]; a+=k[0]; break;
00319         case  8:        b += k[1]; a+=k[0]; break;
00320         case  7:        b += k[1]&0xffffff; a+=k[0]; break;
00321         case  6:        b += k[1]&0xffff; a+=k[0]; break;
00322         case  5:        b += k[1]&0xff; a+=k[0]; break;
00323         case  4:        a += k[0]; break;
00324         case  3:        a += k[0]&0xffffff; break;
00325         case  2:        a += k[0]&0xffff; break;
00326         case  1:        a += k[0]&0xff; break;
00327         case  0:        goto exit;
00328         }
00329       }
00330     } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
00331         const rpmuint16_t *k = (const rpmuint16_t *)key;        /* read 16-bit chunks */
00332         const rpmuint8_t  *k8;
00333 
00334         /*----------- all but last block: aligned reads and different mixing */
00335         while (size > 12) {
00336             a += k[0] + (((rpmuint32_t)k[1])<<16);
00337             b += k[2] + (((rpmuint32_t)k[3])<<16);
00338             c += k[4] + (((rpmuint32_t)k[5])<<16);
00339             _JLU3_MIX(a,b,c);
00340             size -= 12;
00341             k += 6;
00342         }
00343 
00344         /*------------------------- handle the last (probably partial) block */
00345         k8 = (const rpmuint8_t *)k;
00346         switch (size) {
00347         case 12:
00348             c += k[4]+(((rpmuint32_t)k[5])<<16);
00349             b += k[2]+(((rpmuint32_t)k[3])<<16);
00350             a += k[0]+(((rpmuint32_t)k[1])<<16);
00351             break;
00352         case 11:
00353             c += ((rpmuint32_t)k8[10])<<16;
00354             /*@fallthrough@*/
00355         case 10:
00356             c += (rpmuint32_t)k[4];
00357             b += k[2]+(((rpmuint32_t)k[3])<<16);
00358             a += k[0]+(((rpmuint32_t)k[1])<<16);
00359             break;
00360         case  9:
00361             c += (rpmuint32_t)k8[8];
00362             /*@fallthrough@*/
00363         case  8:
00364             b += k[2]+(((rpmuint32_t)k[3])<<16);
00365             a += k[0]+(((rpmuint32_t)k[1])<<16);
00366             break;
00367         case  7:
00368             b += ((rpmuint32_t)k8[6])<<16;
00369             /*@fallthrough@*/
00370         case  6:
00371             b += (rpmuint32_t)k[2];
00372             a += k[0]+(((rpmuint32_t)k[1])<<16);
00373             break;
00374         case  5:
00375             b += (rpmuint32_t)k8[4];
00376             /*@fallthrough@*/
00377         case  4:
00378             a += k[0]+(((rpmuint32_t)k[1])<<16);
00379             break;
00380         case  3:
00381             a += ((rpmuint32_t)k8[2])<<16;
00382             /*@fallthrough@*/
00383         case  2:
00384             a += (rpmuint32_t)k[0];
00385             break;
00386         case  1:
00387             a += (rpmuint32_t)k8[0];
00388             break;
00389         case  0:
00390             goto exit;
00391         }
00392 
00393     } else {            /* need to read the key one byte at a time */
00394         const rpmuint8_t *k = (const rpmuint8_t *)key;
00395 
00396         /*----------- all but the last block: affect some 32 bits of (a,b,c) */
00397         while (size > 12) {
00398             a += (rpmuint32_t)k[0];
00399             a += ((rpmuint32_t)k[1])<<8;
00400             a += ((rpmuint32_t)k[2])<<16;
00401             a += ((rpmuint32_t)k[3])<<24;
00402             b += (rpmuint32_t)k[4];
00403             b += ((rpmuint32_t)k[5])<<8;
00404             b += ((rpmuint32_t)k[6])<<16;
00405             b += ((rpmuint32_t)k[7])<<24;
00406             c += (rpmuint32_t)k[8];
00407             c += ((rpmuint32_t)k[9])<<8;
00408             c += ((rpmuint32_t)k[10])<<16;
00409             c += ((rpmuint32_t)k[11])<<24;
00410             _JLU3_MIX(a,b,c);
00411             size -= 12;
00412             k += 12;
00413         }
00414 
00415         /*---------------------------- last block: affect all 32 bits of (c) */
00416         switch (size) {
00417         case 12:        c += ((rpmuint32_t)k[11])<<24;  /*@fallthrough@*/
00418         case 11:        c += ((rpmuint32_t)k[10])<<16;  /*@fallthrough@*/
00419         case 10:        c += ((rpmuint32_t)k[9])<<8;    /*@fallthrough@*/
00420         case  9:        c += (rpmuint32_t)k[8];         /*@fallthrough@*/
00421         case  8:        b += ((rpmuint32_t)k[7])<<24;   /*@fallthrough@*/
00422         case  7:        b += ((rpmuint32_t)k[6])<<16;   /*@fallthrough@*/
00423         case  6:        b += ((rpmuint32_t)k[5])<<8;    /*@fallthrough@*/
00424         case  5:        b += (rpmuint32_t)k[4];         /*@fallthrough@*/
00425         case  4:        a += ((rpmuint32_t)k[3])<<24;   /*@fallthrough@*/
00426         case  3:        a += ((rpmuint32_t)k[2])<<16;   /*@fallthrough@*/
00427         case  2:        a += ((rpmuint32_t)k[1])<<8;    /*@fallthrough@*/
00428         case  1:        a += (rpmuint32_t)k[0];
00429             break;
00430         case  0:
00431             goto exit;
00432         }
00433     }
00434 
00435     _JLU3_FINAL(a,b,c);
00436 
00437 exit:
00438     return c;
00439 }
00440 #endif  /* defined(_JLU3_jlu32l) */
00441 
00442 #if defined(_JLU3_jlu32lpair)
00443 void jlu32lpair(/*@null@*/ const void *key, size_t size,
00444                 rpmuint32_t *pc, rpmuint32_t *pb)
00445         /*@modifies *pc, *pb@*/;
00462 void jlu32lpair(const void *key, size_t size, rpmuint32_t *pc, rpmuint32_t *pb)
00463 {
00464     union { const void *ptr; size_t i; } u;
00465     rpmuint32_t a = _JLU3_INIT(*pc, size);
00466     rpmuint32_t b = a;
00467     rpmuint32_t c = a;
00468 
00469     if (key == NULL)
00470         goto exit;
00471 
00472     c += *pb;   /* Add the secondary hash. */
00473 
00474     u.ptr = key;
00475     if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
00476         const rpmuint32_t *k = (const rpmuint32_t *)key;        /* read 32-bit chunks */
00477 
00478         /*-- all but last block: aligned reads and affect 32 bits of (a,b,c) */
00479         while (size > 12) {
00480             a += k[0];
00481             b += k[1];
00482             c += k[2];
00483             _JLU3_MIX(a,b,c);
00484             size -= 12;
00485             k += 3;
00486         }
00487         /*------------------------- handle the last (probably partial) block */
00488         /* 
00489          * "k[2]&0xffffff" actually reads beyond the end of the string, but
00490          * then masks off the part it's not allowed to read.  Because the
00491          * string is aligned, the masked-off tail is in the same word as the
00492          * rest of the string.  Every machine with memory protection I've seen
00493          * does it on word boundaries, so is OK with this.  But VALGRIND will
00494          * still catch it and complain.  The masking trick does make the hash
00495          * noticably faster for short strings (like English words).
00496          */
00497 #ifdef WITH_VALGRIND
00498       if (UNLIKELY(_running_on_valgrind)) {
00499         const rpmuint8_t  * k8 = (const rpmuint8_t *)k;
00500 
00501         switch (size) {
00502         case 12:        c += k[2]; b+=k[1]; a+=k[0];    break;
00503         case 11:        c += ((rpmuint32_t)k8[10])<<16; /*@fallthrough@*/
00504         case 10:        c += ((rpmuint32_t)k8[9])<<8;   /*@fallthrough@*/
00505         case  9:        c += k8[8];                     /*@fallthrough@*/
00506         case  8:        b += k[1]; a+=k[0];             break;
00507         case  7:        b += ((rpmuint32_t)k8[6])<<16;  /*@fallthrough@*/
00508         case  6:        b += ((rpmuint32_t)k8[5])<<8;   /*@fallthrough@*/
00509         case  5:        b += k8[4];                     /*@fallthrough@*/
00510         case  4:        a += k[0];                      break;
00511         case  3:        a += ((rpmuint32_t)k8[2])<<16;  /*@fallthrough@*/
00512         case  2:        a += ((rpmuint32_t)k8[1])<<8;   /*@fallthrough@*/
00513         case  1:        a += k8[0];                     break;
00514         case  0:        goto exit;
00515         }
00516 
00517       } else
00518 #endif
00519       {
00520         switch (size) {
00521         case 12:        c += k[2]; b+=k[1]; a+=k[0]; break;
00522         case 11:        c += k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
00523         case 10:        c += k[2]&0xffff; b+=k[1]; a+=k[0]; break;
00524         case  9:        c += k[2]&0xff; b+=k[1]; a+=k[0]; break;
00525         case  8:        b += k[1]; a+=k[0]; break;
00526         case  7:        b += k[1]&0xffffff; a+=k[0]; break;
00527         case  6:        b += k[1]&0xffff; a+=k[0]; break;
00528         case  5:        b += k[1]&0xff; a+=k[0]; break;
00529         case  4:        a += k[0]; break;
00530         case  3:        a += k[0]&0xffffff; break;
00531         case  2:        a += k[0]&0xffff; break;
00532         case  1:        a += k[0]&0xff; break;
00533         case  0:        goto exit;
00534         }
00535       } 
00536     } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
00537         const rpmuint16_t *k = (const rpmuint16_t *)key;        /* read 16-bit chunks */
00538         const rpmuint8_t  *k8;
00539 
00540         /*----------- all but last block: aligned reads and different mixing */
00541         while (size > 12) {
00542             a += k[0] + (((rpmuint32_t)k[1])<<16);
00543             b += k[2] + (((rpmuint32_t)k[3])<<16);
00544             c += k[4] + (((rpmuint32_t)k[5])<<16);
00545             _JLU3_MIX(a,b,c);
00546             size -= 12;
00547             k += 6;
00548         }
00549 
00550         /*------------------------- handle the last (probably partial) block */
00551         k8 = (const rpmuint8_t *)k;
00552         switch (size) {
00553         case 12:
00554             c += k[4]+(((rpmuint32_t)k[5])<<16);
00555             b += k[2]+(((rpmuint32_t)k[3])<<16);
00556             a += k[0]+(((rpmuint32_t)k[1])<<16);
00557             break;
00558         case 11:
00559             c += ((rpmuint32_t)k8[10])<<16;
00560             /*@fallthrough@*/
00561         case 10:
00562             c += k[4];
00563             b += k[2]+(((rpmuint32_t)k[3])<<16);
00564             a += k[0]+(((rpmuint32_t)k[1])<<16);
00565             break;
00566         case  9:
00567             c += k8[8];
00568             /*@fallthrough@*/
00569         case  8:
00570             b += k[2]+(((rpmuint32_t)k[3])<<16);
00571             a += k[0]+(((rpmuint32_t)k[1])<<16);
00572             break;
00573         case  7:
00574             b += ((rpmuint32_t)k8[6])<<16;
00575             /*@fallthrough@*/
00576         case  6:
00577             b += k[2];
00578             a += k[0]+(((rpmuint32_t)k[1])<<16);
00579             break;
00580         case  5:
00581             b += k8[4];
00582             /*@fallthrough@*/
00583         case  4:
00584             a += k[0]+(((rpmuint32_t)k[1])<<16);
00585             break;
00586         case  3:
00587             a += ((rpmuint32_t)k8[2])<<16;
00588             /*@fallthrough@*/
00589         case  2:
00590             a += k[0];
00591             break;
00592         case  1:
00593             a += k8[0];
00594             break;
00595         case  0:
00596             goto exit;
00597         }
00598 
00599     } else {            /* need to read the key one byte at a time */
00600         const rpmuint8_t *k = (const rpmuint8_t *)key;
00601 
00602         /*----------- all but the last block: affect some 32 bits of (a,b,c) */
00603         while (size > 12) {
00604             a += k[0];
00605             a += ((rpmuint32_t)k[1])<<8;
00606             a += ((rpmuint32_t)k[2])<<16;
00607             a += ((rpmuint32_t)k[3])<<24;
00608             b += k[4];
00609             b += ((rpmuint32_t)k[5])<<8;
00610             b += ((rpmuint32_t)k[6])<<16;
00611             b += ((rpmuint32_t)k[7])<<24;
00612             c += k[8];
00613             c += ((rpmuint32_t)k[9])<<8;
00614             c += ((rpmuint32_t)k[10])<<16;
00615             c += ((rpmuint32_t)k[11])<<24;
00616             _JLU3_MIX(a,b,c);
00617             size -= 12;
00618             k += 12;
00619         }
00620 
00621         /*---------------------------- last block: affect all 32 bits of (c) */
00622         switch (size) {
00623         case 12:        c += ((rpmuint32_t)k[11])<<24;  /*@fallthrough@*/
00624         case 11:        c += ((rpmuint32_t)k[10])<<16;  /*@fallthrough@*/
00625         case 10:        c += ((rpmuint32_t)k[9])<<8;    /*@fallthrough@*/
00626         case  9:        c += k[8];                      /*@fallthrough@*/
00627         case  8:        b += ((rpmuint32_t)k[7])<<24;   /*@fallthrough@*/
00628         case  7:        b += ((rpmuint32_t)k[6])<<16;   /*@fallthrough@*/
00629         case  6:        b += ((rpmuint32_t)k[5])<<8;    /*@fallthrough@*/
00630         case  5:        b += k[4];                      /*@fallthrough@*/
00631         case  4:        a += ((rpmuint32_t)k[3])<<24;   /*@fallthrough@*/
00632         case  3:        a += ((rpmuint32_t)k[2])<<16;   /*@fallthrough@*/
00633         case  2:        a += ((rpmuint32_t)k[1])<<8;    /*@fallthrough@*/
00634         case  1:        a += k[0];                      /*@fallthrough@*/
00635             break;
00636         case  0:
00637             goto exit;
00638         }
00639     }
00640 
00641     _JLU3_FINAL(a,b,c);
00642 
00643 exit:
00644     *pc = c;
00645     *pb = b;
00646     return;
00647 }
00648 #endif  /* defined(_JLU3_jlu32lpair) */
00649 
00650 #if defined(_JLU3_jlu32b)
00651 rpmuint32_t jlu32b(rpmuint32_t h, /*@null@*/ const void *key, size_t size)
00652         /*@*/;
00653 /*
00654  * jlu32b():
00655  * This is the same as jlu32w() on big-endian machines.  It is different
00656  * from jlu32l() on all machines.  jlu32b() takes advantage of
00657  * big-endian byte ordering. 
00658  *
00659  * @param h             the previous hash, or an arbitrary value
00660  * @param *k            the key, an array of rpmuint8_t values
00661  * @param size          the size of the key
00662  * @return              the lookup3 hash
00663  */
00664 rpmuint32_t jlu32b(rpmuint32_t h, const void *key, size_t size)
00665 {
00666     union { const void *ptr; size_t i; } u;
00667     rpmuint32_t a = _JLU3_INIT(h, size);
00668     rpmuint32_t b = a;
00669     rpmuint32_t c = a;
00670 
00671     if (key == NULL)
00672         return h;
00673 
00674     u.ptr = key;
00675     if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
00676         const rpmuint32_t *k = (const rpmuint32_t *)key;        /* read 32-bit chunks */
00677 
00678         /*-- all but last block: aligned reads and affect 32 bits of (a,b,c) */
00679         while (size > 12) {
00680             a += k[0];
00681             b += k[1];
00682             c += k[2];
00683             _JLU3_MIX(a,b,c);
00684             size -= 12;
00685             k += 3;
00686         }
00687 
00688         /*------------------------- handle the last (probably partial) block */
00689         /* 
00690          * "k[2]<<8" actually reads beyond the end of the string, but
00691          * then shifts out the part it's not allowed to read.  Because the
00692          * string is aligned, the illegal read is in the same word as the
00693          * rest of the string.  Every machine with memory protection I've seen
00694          * does it on word boundaries, so is OK with this.  But VALGRIND will
00695          * still catch it and complain.  The masking trick does make the hash
00696          * noticably faster for short strings (like English words).
00697          */
00698 #ifdef WITH_VALGRIND
00699       if (UNLIKELY(_running_on_valgrind)) {
00700         const rpmuint8_t  * k8 = (const rpmuint8_t *)k;
00701 
00702         switch (size) { /* all the case statements fall through */
00703         case 12:        c += k[2]; b+=k[1]; a+=k[0];    break;
00704         case 11:        c += ((rpmuint32_t)k8[10])<<8;  /*@fallthrough@*/
00705         case 10:        c += ((rpmuint32_t)k8[9])<<16;  /*@fallthrough@*/
00706         case  9:        c += ((rpmuint32_t)k8[8])<<24;  /*@fallthrough@*/
00707         case  8:        b += k[1]; a+=k[0];             break;
00708         case  7:        b += ((rpmuint32_t)k8[6])<<8;   /*@fallthrough@*/
00709         case  6:        b += ((rpmuint32_t)k8[5])<<16;  /*@fallthrough@*/
00710         case  5:        b += ((rpmuint32_t)k8[4])<<24;  /*@fallthrough@*/
00711         case  4:        a += k[0];                      break;
00712         case  3:        a += ((rpmuint32_t)k8[2])<<8;   /*@fallthrough@*/
00713         case  2:        a += ((rpmuint32_t)k8[1])<<16;  /*@fallthrough@*/
00714         case  1:        a += ((rpmuint32_t)k8[0])<<24;  break;
00715         case  0:        goto exit;
00716         }
00717 
00718       } else
00719 #endif
00720       {
00721         switch (size) {
00722         case 12:        c += k[2]; b+=k[1]; a+=k[0]; break;
00723         case 11:        c += k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
00724         case 10:        c += k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
00725         case  9:        c += k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
00726         case  8:        b += k[1]; a+=k[0]; break;
00727         case  7:        b += k[1]&0xffffff00; a+=k[0]; break;
00728         case  6:        b += k[1]&0xffff0000; a+=k[0]; break;
00729         case  5:        b += k[1]&0xff000000; a+=k[0]; break;
00730         case  4:        a += k[0]; break;
00731         case  3:        a += k[0]&0xffffff00; break;
00732         case  2:        a += k[0]&0xffff0000; break;
00733         case  1:        a += k[0]&0xff000000; break;
00734         case  0:        goto exit;
00735         }
00736       }
00737     } else {                        /* need to read the key one byte at a time */
00738         const rpmuint8_t *k = (const rpmuint8_t *)key;
00739 
00740         /*----------- all but the last block: affect some 32 bits of (a,b,c) */
00741         while (size > 12) {
00742             a += ((rpmuint32_t)k[0])<<24;
00743             a += ((rpmuint32_t)k[1])<<16;
00744             a += ((rpmuint32_t)k[2])<<8;
00745             a += ((rpmuint32_t)k[3]);
00746             b += ((rpmuint32_t)k[4])<<24;
00747             b += ((rpmuint32_t)k[5])<<16;
00748             b += ((rpmuint32_t)k[6])<<8;
00749             b += ((rpmuint32_t)k[7]);
00750             c += ((rpmuint32_t)k[8])<<24;
00751             c += ((rpmuint32_t)k[9])<<16;
00752             c += ((rpmuint32_t)k[10])<<8;
00753             c += ((rpmuint32_t)k[11]);
00754             _JLU3_MIX(a,b,c);
00755             size -= 12;
00756             k += 12;
00757         }
00758 
00759         /*---------------------------- last block: affect all 32 bits of (c) */
00760         switch (size) { /* all the case statements fall through */
00761         case 12:        c += k[11];                     /*@fallthrough@*/
00762         case 11:        c += ((rpmuint32_t)k[10])<<8;   /*@fallthrough@*/
00763         case 10:        c += ((rpmuint32_t)k[9])<<16;   /*@fallthrough@*/
00764         case  9:        c += ((rpmuint32_t)k[8])<<24;   /*@fallthrough@*/
00765         case  8:        b += k[7];                      /*@fallthrough@*/
00766         case  7:        b += ((rpmuint32_t)k[6])<<8;    /*@fallthrough@*/
00767         case  6:        b += ((rpmuint32_t)k[5])<<16;   /*@fallthrough@*/
00768         case  5:        b += ((rpmuint32_t)k[4])<<24;   /*@fallthrough@*/
00769         case  4:        a += k[3];                      /*@fallthrough@*/
00770         case  3:        a += ((rpmuint32_t)k[2])<<8;    /*@fallthrough@*/
00771         case  2:        a += ((rpmuint32_t)k[1])<<16;   /*@fallthrough@*/
00772         case  1:        a += ((rpmuint32_t)k[0])<<24;   /*@fallthrough@*/
00773             break;
00774         case  0:
00775             goto exit;
00776         }
00777     }
00778 
00779     _JLU3_FINAL(a,b,c);
00780 
00781 exit:
00782     return c;
00783 }
00784 #endif  /* defined(_JLU3_jlu32b) */
00785 
00786 #if defined(_JLU3_SELFTEST)
00787 
00788 /* used for timings */
00789 static void driver1(void)
00790         /*@*/
00791 {
00792     rpmuint8_t buf[256];
00793     rpmuint32_t i;
00794     rpmuint32_t h=0;
00795     time_t a,z;
00796 
00797     time(&a);
00798     for (i=0; i<256; ++i) buf[i] = 'x';
00799     for (i=0; i<1; ++i) {
00800         h = jlu32l(h, &buf[0], sizeof(buf[0]));
00801     }
00802     time(&z);
00803     if (z-a > 0) printf("time %d %.8x\n", (int)(z-a), h);
00804 }
00805 
00806 /* check that every input bit changes every output bit half the time */
00807 #define HASHSTATE 1
00808 #define HASHLEN   1
00809 #define MAXPAIR 60
00810 #define MAXLEN  70
00811 static void driver2(void)
00812         /*@*/
00813 {
00814     rpmuint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
00815     rpmuint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
00816     rpmuint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
00817     rpmuint32_t x[HASHSTATE],y[HASHSTATE];
00818     rpmuint32_t hlen;
00819 
00820     printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
00821     for (hlen=0; hlen < MAXLEN; ++hlen) {
00822         z=0;
00823         for (i=0; i<hlen; ++i) {        /*-------------- for each input byte, */
00824             for (j=0; j<8; ++j) {       /*--------------- for each input bit, */
00825                 for (m=1; m<8; ++m) {   /*--- for serveral possible initvals, */
00826                     for (l=0; l<HASHSTATE; ++l)
00827                         e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((rpmuint32_t)0);
00828 
00829                     /* check that every output bit is affected by that input bit */
00830                     for (k=0; k<MAXPAIR; k+=2) { 
00831                         rpmuint32_t finished=1;
00832                         /* keys have one bit different */
00833                         for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (rpmuint8_t)0;}
00834                         /* have a and b be two keys differing in only one bit */
00835                         a[i] ^= (k<<j);
00836                         a[i] ^= (k>>(8-j));
00837                         c[0] = jlu32l(m, a, hlen);
00838                         b[i] ^= ((k+1)<<j);
00839                         b[i] ^= ((k+1)>>(8-j));
00840                         d[0] = jlu32l(m, b, hlen);
00841                         /* check every bit is 1, 0, set, and not set at least once */
00842                         for (l=0; l<HASHSTATE; ++l) {
00843                             e[l] &= (c[l]^d[l]);
00844                             f[l] &= ~(c[l]^d[l]);
00845                             g[l] &= c[l];
00846                             h[l] &= ~c[l];
00847                             x[l] &= d[l];
00848                             y[l] &= ~d[l];
00849                             if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
00850                         }
00851                         if (finished) break;
00852                     }
00853                     if (k>z) z=k;
00854                     if (k == MAXPAIR) {
00855                         printf("Some bit didn't change: ");
00856                         printf("%.8x %.8x %.8x %.8x %.8x %.8x  ",
00857                                 e[0],f[0],g[0],h[0],x[0],y[0]);
00858                         printf("i %d j %d m %d len %d\n", i, j, m, hlen);
00859                     }
00860                     if (z == MAXPAIR) goto done;
00861                 }
00862             }
00863         }
00864    done:
00865         if (z < MAXPAIR) {
00866             printf("Mix success  %2d bytes  %2d initvals  ",i,m);
00867             printf("required  %d  trials\n", z/2);
00868         }
00869     }
00870     printf("\n");
00871 }
00872 
00873 /* Check for reading beyond the end of the buffer and alignment problems */
00874 static void driver3(void)
00875         /*@*/
00876 {
00877     rpmuint8_t buf[MAXLEN+20], *b;
00878     rpmuint32_t len;
00879     rpmuint8_t q[] = "This is the time for all good men to come to the aid of their country...";
00880     rpmuint32_t h;
00881     rpmuint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
00882     rpmuint32_t i;
00883     rpmuint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
00884     rpmuint32_t j;
00885     rpmuint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
00886     rpmuint32_t ref,x,y;
00887     rpmuint8_t *p;
00888     rpmuint32_t m = 13;
00889 
00890     printf("Endianness.  These lines should all be the same (for values filled in):\n");
00891     printf("%.8x                            %.8x                            %.8x\n",
00892         jlu32w(m, (const rpmuint32_t *)q, (sizeof(q)-1)/4),
00893         jlu32w(m, (const rpmuint32_t *)q, (sizeof(q)-5)/4),
00894         jlu32w(m, (const rpmuint32_t *)q, (sizeof(q)-9)/4));
00895     p = q;
00896     printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
00897         jlu32l(m, p, sizeof(q)-1), jlu32l(m, p, sizeof(q)-2),
00898         jlu32l(m, p, sizeof(q)-3), jlu32l(m, p, sizeof(q)-4),
00899         jlu32l(m, p, sizeof(q)-5), jlu32l(m, p, sizeof(q)-6),
00900         jlu32l(m, p, sizeof(q)-7), jlu32l(m, p, sizeof(q)-8),
00901         jlu32l(m, p, sizeof(q)-9), jlu32l(m, p, sizeof(q)-10),
00902         jlu32l(m, p, sizeof(q)-11), jlu32l(m, p, sizeof(q)-12));
00903     p = &qq[1];
00904     printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
00905         jlu32l(m, p, sizeof(q)-1), jlu32l(m, p, sizeof(q)-2),
00906         jlu32l(m, p, sizeof(q)-3), jlu32l(m, p, sizeof(q)-4),
00907         jlu32l(m, p, sizeof(q)-5), jlu32l(m, p, sizeof(q)-6),
00908         jlu32l(m, p, sizeof(q)-7), jlu32l(m, p, sizeof(q)-8),
00909         jlu32l(m, p, sizeof(q)-9), jlu32l(m, p, sizeof(q)-10),
00910         jlu32l(m, p, sizeof(q)-11), jlu32l(m, p, sizeof(q)-12));
00911     p = &qqq[2];
00912     printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
00913         jlu32l(m, p, sizeof(q)-1), jlu32l(m, p, sizeof(q)-2),
00914         jlu32l(m, p, sizeof(q)-3), jlu32l(m, p, sizeof(q)-4),
00915         jlu32l(m, p, sizeof(q)-5), jlu32l(m, p, sizeof(q)-6),
00916         jlu32l(m, p, sizeof(q)-7), jlu32l(m, p, sizeof(q)-8),
00917         jlu32l(m, p, sizeof(q)-9), jlu32l(m, p, sizeof(q)-10),
00918         jlu32l(m, p, sizeof(q)-11), jlu32l(m, p, sizeof(q)-12));
00919     p = &qqqq[3];
00920     printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
00921         jlu32l(m, p, sizeof(q)-1), jlu32l(m, p, sizeof(q)-2),
00922         jlu32l(m, p, sizeof(q)-3), jlu32l(m, p, sizeof(q)-4),
00923         jlu32l(m, p, sizeof(q)-5), jlu32l(m, p, sizeof(q)-6),
00924         jlu32l(m, p, sizeof(q)-7), jlu32l(m, p, sizeof(q)-8),
00925         jlu32l(m, p, sizeof(q)-9), jlu32l(m, p, sizeof(q)-10),
00926         jlu32l(m, p, sizeof(q)-11), jlu32l(m, p, sizeof(q)-12));
00927     printf("\n");
00928     for (h=0, b=buf+1; h<8; ++h, ++b) {
00929         for (i=0; i<MAXLEN; ++i) {
00930             len = i;
00931             for (j=0; j<i; ++j)
00932                 *(b+j)=0;
00933 
00934             /* these should all be equal */
00935             m = 1;
00936             ref = jlu32l(m, b, len);
00937             *(b+i)=(rpmuint8_t)~0;
00938             *(b-1)=(rpmuint8_t)~0;
00939             x = jlu32l(m, b, len);
00940             y = jlu32l(m, b, len);
00941             if ((ref != x) || (ref != y)) 
00942                 printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y, h, i);
00943         }
00944     }
00945 }
00946 
00947 /* check for problems with nulls */
00948 static void driver4(void)
00949         /*@*/
00950 {
00951     rpmuint8_t buf[1];
00952     rpmuint32_t h;
00953     rpmuint32_t i;
00954     rpmuint32_t state[HASHSTATE];
00955 
00956     buf[0] = ~0;
00957     for (i=0; i<HASHSTATE; ++i)
00958         state[i] = 1;
00959     printf("These should all be different\n");
00960     h = 0;
00961     for (i=0; i<8; ++i) {
00962         h = jlu32l(h, buf, 0);
00963         printf("%2ld  0-byte strings, hash is  %.8x\n", (long)i, h);
00964     }
00965 }
00966 
00967 
00968 int main(int argc, char ** argv)
00969 {
00970     driver1();  /* test that the key is hashed: used for timings */
00971     driver2();  /* test that whole key is hashed thoroughly */
00972     driver3();  /* test that nothing but the key is hashed */
00973     driver4();  /* test hashing multiple buffers (all buffers are null) */
00974     return 1;
00975 }
00976 
00977 #endif  /* _JLU3_SELFTEST */