Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Hash_impl

annotate jenkinsHash_lookup8.c @ 39:fd25f8700c9c

find changesets by author, revision, files, or words in the commit message
Merge
author Sean Halle <seanhalle@yahoo.com>
date Fri, 14 Feb 2014 07:20:34 -0800
parents
children
rev   line source
seanhalle@25 1 /*
seanhalle@25 2 --------------------------------------------------------------------
seanhalle@25 3 lookup8.c, by Bob Jenkins, January 4 1997, Public Domain.
seanhalle@25 4 hash(), hash2(), hash3, and mix() are externally useful functions.
seanhalle@25 5 Routines to test the hash are included if SELF_TEST is defined.
seanhalle@25 6 You can use this free for any purpose. It has no warranty.
seanhalle@25 7
seanhalle@25 8 2009: This is obsolete. I recently timed lookup3.c as being faster
seanhalle@25 9 at producing 64-bit results.
seanhalle@25 10 --------------------------------------------------------------------
seanhalle@25 11 */
seanhalle@25 12 //#define SELF_TEST
seanhalle@25 13
seanhalle@25 14 #include <stdio.h>
seanhalle@25 15 #include <stddef.h>
seanhalle@25 16 #include <stdlib.h>
seanhalle@25 17 typedef unsigned long long ub8; /* unsigned 8-byte quantities */
seanhalle@25 18 typedef unsigned long int ub4; /* unsigned 4-byte quantities */
seanhalle@25 19 typedef unsigned char ub1;
seanhalle@25 20
seanhalle@25 21 #define hashsize(n) ((ub8)1<<(n))
seanhalle@25 22 #define hashmask(n) (hashsize(n)-1)
seanhalle@25 23
seanhalle@25 24 /*
seanhalle@25 25 --------------------------------------------------------------------
seanhalle@25 26 mix -- mix 3 64-bit values reversibly.
seanhalle@25 27 mix() takes 48 machine instructions, but only 24 cycles on a superscalar
seanhalle@25 28 machine (like Intel's new MMX architecture). It requires 4 64-bit
seanhalle@25 29 registers for 4::2 parallelism.
seanhalle@25 30 All 1-bit deltas, all 2-bit deltas, all deltas composed of top bits of
seanhalle@25 31 (a,b,c), and all deltas of bottom bits were tested. All deltas were
seanhalle@25 32 tested both on random keys and on keys that were nearly all zero.
seanhalle@25 33 These deltas all cause every bit of c to change between 1/3 and 2/3
seanhalle@25 34 of the time (well, only 113/400 to 287/400 of the time for some
seanhalle@25 35 2-bit delta). These deltas all cause at least 80 bits to change
seanhalle@25 36 among (a,b,c) when the mix is run either forward or backward (yes it
seanhalle@25 37 is reversible).
seanhalle@25 38 This implies that a hash using mix64 has no funnels. There may be
seanhalle@25 39 characteristics with 3-bit deltas or bigger, I didn't test for
seanhalle@25 40 those.
seanhalle@25 41 --------------------------------------------------------------------
seanhalle@25 42 */
seanhalle@25 43 #define mix64(a,b,c) \
seanhalle@25 44 { \
seanhalle@25 45 a -= b; a -= c; a ^= (c>>43); \
seanhalle@25 46 b -= c; b -= a; b ^= (a<<9); \
seanhalle@25 47 c -= a; c -= b; c ^= (b>>8); \
seanhalle@25 48 a -= b; a -= c; a ^= (c>>38); \
seanhalle@25 49 b -= c; b -= a; b ^= (a<<23); \
seanhalle@25 50 c -= a; c -= b; c ^= (b>>5); \
seanhalle@25 51 a -= b; a -= c; a ^= (c>>35); \
seanhalle@25 52 b -= c; b -= a; b ^= (a<<49); \
seanhalle@25 53 c -= a; c -= b; c ^= (b>>11); \
seanhalle@25 54 a -= b; a -= c; a ^= (c>>12); \
seanhalle@25 55 b -= c; b -= a; b ^= (a<<18); \
seanhalle@25 56 c -= a; c -= b; c ^= (b>>22); \
seanhalle@25 57 }
seanhalle@25 58
seanhalle@25 59 /*
seanhalle@25 60 --------------------------------------------------------------------
seanhalle@25 61 hash() -- hash a variable-length key into a 64-bit value
seanhalle@25 62 k : the key (the unaligned variable-length array of bytes)
seanhalle@25 63 len : the length of the key, counting by bytes
seanhalle@25 64 level : can be any 8-byte value
seanhalle@25 65 Returns a 64-bit value. Every bit of the key affects every bit of
seanhalle@25 66 the return value. No funnels. Every 1-bit and 2-bit delta achieves
seanhalle@25 67 avalanche. About 41+5len instructions.
seanhalle@25 68
seanhalle@25 69 The best hash table sizes are powers of 2. There is no need to do
seanhalle@25 70 mod a prime (mod is sooo slow!). If you need less than 64 bits,
seanhalle@25 71 use a bitmask. For example, if you need only 10 bits, do
seanhalle@25 72 h = (h & hashmask(10));
seanhalle@25 73 In which case, the hash table should have hashsize(10) elements.
seanhalle@25 74
seanhalle@25 75 If you are hashing n strings (ub1 **)k, do it like this:
seanhalle@25 76 for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
seanhalle@25 77
seanhalle@25 78 By Bob Jenkins, Jan 4 1997. bob_jenkins@burtleburtle.net. You may
seanhalle@25 79 use this code any way you wish, private, educational, or commercial,
seanhalle@25 80 but I would appreciate if you give me credit.
seanhalle@25 81
seanhalle@25 82 See http://burtleburtle.net/bob/hash/evahash.html
seanhalle@25 83 Use for hash table lookup, or anything where one collision in 2^^64
seanhalle@25 84 is acceptable. Do NOT use for cryptographic purposes.
seanhalle@25 85 --------------------------------------------------------------------
seanhalle@25 86 */
seanhalle@25 87
seanhalle@25 88 ub8 hash( k, length, level)
seanhalle@25 89 register ub1 *k; /* the key */
seanhalle@25 90 register ub8 length; /* the length of the key */
seanhalle@25 91 register ub8 level; /* the previous hash, or an arbitrary value */
seanhalle@25 92 {
seanhalle@25 93 register ub8 a,b,c,len;
seanhalle@25 94
seanhalle@25 95 /* Set up the internal state */
seanhalle@25 96 len = length;
seanhalle@25 97 a = b = level; /* the previous hash value */
seanhalle@25 98 c = 0x9e3779b97f4a7c13LL; /* the golden ratio; an arbitrary value */
seanhalle@25 99
seanhalle@25 100 /*---------------------------------------- handle most of the key */
seanhalle@25 101 while (len >= 24)
seanhalle@25 102 {
seanhalle@25 103 a += (k[0] +((ub8)k[ 1]<< 8)+((ub8)k[ 2]<<16)+((ub8)k[ 3]<<24)
seanhalle@25 104 +((ub8)k[4 ]<<32)+((ub8)k[ 5]<<40)+((ub8)k[ 6]<<48)+((ub8)k[ 7]<<56));
seanhalle@25 105 b += (k[8] +((ub8)k[ 9]<< 8)+((ub8)k[10]<<16)+((ub8)k[11]<<24)
seanhalle@25 106 +((ub8)k[12]<<32)+((ub8)k[13]<<40)+((ub8)k[14]<<48)+((ub8)k[15]<<56));
seanhalle@25 107 c += (k[16] +((ub8)k[17]<< 8)+((ub8)k[18]<<16)+((ub8)k[19]<<24)
seanhalle@25 108 +((ub8)k[20]<<32)+((ub8)k[21]<<40)+((ub8)k[22]<<48)+((ub8)k[23]<<56));
seanhalle@25 109 mix64(a,b,c);
seanhalle@25 110 k += 24; len -= 24;
seanhalle@25 111 }
seanhalle@25 112
seanhalle@25 113 /*------------------------------------- handle the last 23 bytes */
seanhalle@25 114 c += length;
seanhalle@25 115 switch(len) /* all the case statements fall through */
seanhalle@25 116 {
seanhalle@25 117 case 23: c+=((ub8)k[22]<<56);
seanhalle@25 118 case 22: c+=((ub8)k[21]<<48);
seanhalle@25 119 case 21: c+=((ub8)k[20]<<40);
seanhalle@25 120 case 20: c+=((ub8)k[19]<<32);
seanhalle@25 121 case 19: c+=((ub8)k[18]<<24);
seanhalle@25 122 case 18: c+=((ub8)k[17]<<16);
seanhalle@25 123 case 17: c+=((ub8)k[16]<<8);
seanhalle@25 124 /* the first byte of c is reserved for the length */
seanhalle@25 125 case 16: b+=((ub8)k[15]<<56);
seanhalle@25 126 case 15: b+=((ub8)k[14]<<48);
seanhalle@25 127 case 14: b+=((ub8)k[13]<<40);
seanhalle@25 128 case 13: b+=((ub8)k[12]<<32);
seanhalle@25 129 case 12: b+=((ub8)k[11]<<24);
seanhalle@25 130 case 11: b+=((ub8)k[10]<<16);
seanhalle@25 131 case 10: b+=((ub8)k[ 9]<<8);
seanhalle@25 132 case 9: b+=((ub8)k[ 8]);
seanhalle@25 133 case 8: a+=((ub8)k[ 7]<<56);
seanhalle@25 134 case 7: a+=((ub8)k[ 6]<<48);
seanhalle@25 135 case 6: a+=((ub8)k[ 5]<<40);
seanhalle@25 136 case 5: a+=((ub8)k[ 4]<<32);
seanhalle@25 137 case 4: a+=((ub8)k[ 3]<<24);
seanhalle@25 138 case 3: a+=((ub8)k[ 2]<<16);
seanhalle@25 139 case 2: a+=((ub8)k[ 1]<<8);
seanhalle@25 140 case 1: a+=((ub8)k[ 0]);
seanhalle@25 141 /* case 0: nothing left to add */
seanhalle@25 142 }
seanhalle@25 143 mix64(a,b,c);
seanhalle@25 144 /*-------------------------------------------- report the result */
seanhalle@25 145 return c;
seanhalle@25 146 }
seanhalle@25 147
seanhalle@25 148 /*
seanhalle@25 149 --------------------------------------------------------------------
seanhalle@25 150 This works on all machines, is identical to hash() on little-endian
seanhalle@25 151 machines, and it is much faster than hash(), but it requires
seanhalle@25 152 -- that the key be an array of ub8's, and
seanhalle@25 153 -- that all your machines have the same endianness, and
seanhalle@25 154 -- that the length be the number of ub8's in the key
seanhalle@25 155 --------------------------------------------------------------------
seanhalle@25 156 */
seanhalle@25 157 ub8 hash2( k, length, level)
seanhalle@25 158 register ub8 *k; /* the key */
seanhalle@25 159 register ub8 length; /* the length of the key */
seanhalle@25 160 register ub8 level; /* the previous hash, or an arbitrary value */
seanhalle@25 161 {
seanhalle@25 162 register ub8 a,b,c,len;
seanhalle@25 163
seanhalle@25 164 /* Set up the internal state */
seanhalle@25 165 len = length;
seanhalle@25 166 a = b = level; /* the previous hash value */
seanhalle@25 167 c = 0x9e3779b97f4a7c13LL; /* the golden ratio; an arbitrary value */
seanhalle@25 168
seanhalle@25 169 /*---------------------------------------- handle most of the key */
seanhalle@25 170 while (len >= 3)
seanhalle@25 171 {
seanhalle@25 172 a += k[0];
seanhalle@25 173 b += k[1];
seanhalle@25 174 c += k[2];
seanhalle@25 175 mix64(a,b,c);
seanhalle@25 176 k += 3; len -= 3;
seanhalle@25 177 }
seanhalle@25 178
seanhalle@25 179 /*-------------------------------------- handle the last 2 ub8's */
seanhalle@25 180 c += (length<<3);
seanhalle@25 181 switch(len) /* all the case statements fall through */
seanhalle@25 182 {
seanhalle@25 183 /* c is reserved for the length */
seanhalle@25 184 case 2: b+=k[1];
seanhalle@25 185 case 1: a+=k[0];
seanhalle@25 186 /* case 0: nothing left to add */
seanhalle@25 187 }
seanhalle@25 188 mix64(a,b,c);
seanhalle@25 189 /*-------------------------------------------- report the result */
seanhalle@25 190 return c;
seanhalle@25 191 }
seanhalle@25 192
seanhalle@25 193 /*
seanhalle@25 194 --------------------------------------------------------------------
seanhalle@25 195 This is identical to hash() on little-endian machines, and it is much
seanhalle@25 196 faster than hash(), but a little slower than hash2(), and it requires
seanhalle@25 197 -- that all your machines be little-endian, for example all Intel x86
seanhalle@25 198 chips or all VAXen. It gives wrong results on big-endian machines.
seanhalle@25 199 --------------------------------------------------------------------
seanhalle@25 200 */
seanhalle@25 201
seanhalle@25 202 ub8 hash3( k, length, level)
seanhalle@25 203 register ub1 *k; /* the key */
seanhalle@25 204 register ub8 length; /* the length of the key */
seanhalle@25 205 register ub8 level; /* the previous hash, or an arbitrary value */
seanhalle@25 206 {
seanhalle@25 207 register ub8 a,b,c,len;
seanhalle@25 208
seanhalle@25 209 /* Set up the internal state */
seanhalle@25 210 len = length;
seanhalle@25 211 a = b = level; /* the previous hash value */
seanhalle@25 212 c = 0x9e3779b97f4a7c13LL; /* the golden ratio; an arbitrary value */
seanhalle@25 213
seanhalle@25 214 /*---------------------------------------- handle most of the key */
seanhalle@25 215 if (((size_t)k)&7)
seanhalle@25 216 {
seanhalle@25 217 while (len >= 24)
seanhalle@25 218 {
seanhalle@25 219 a += (k[0] +((ub8)k[ 1]<< 8)+((ub8)k[ 2]<<16)+((ub8)k[ 3]<<24)
seanhalle@25 220 +((ub8)k[4 ]<<32)+((ub8)k[ 5]<<40)+((ub8)k[ 6]<<48)+((ub8)k[ 7]<<56));
seanhalle@25 221 b += (k[8] +((ub8)k[ 9]<< 8)+((ub8)k[10]<<16)+((ub8)k[11]<<24)
seanhalle@25 222 +((ub8)k[12]<<32)+((ub8)k[13]<<40)+((ub8)k[14]<<48)+((ub8)k[15]<<56));
seanhalle@25 223 c += (k[16] +((ub8)k[17]<< 8)+((ub8)k[18]<<16)+((ub8)k[19]<<24)
seanhalle@25 224 +((ub8)k[20]<<32)+((ub8)k[21]<<40)+((ub8)k[22]<<48)+((ub8)k[23]<<56));
seanhalle@25 225 mix64(a,b,c);
seanhalle@25 226 k += 24; len -= 24;
seanhalle@25 227 }
seanhalle@25 228 }
seanhalle@25 229 else
seanhalle@25 230 {
seanhalle@25 231 while (len >= 24) /* aligned */
seanhalle@25 232 {
seanhalle@25 233 a += *(ub8 *)(k+0);
seanhalle@25 234 b += *(ub8 *)(k+8);
seanhalle@25 235 c += *(ub8 *)(k+16);
seanhalle@25 236 mix64(a,b,c);
seanhalle@25 237 k += 24; len -= 24;
seanhalle@25 238 }
seanhalle@25 239 }
seanhalle@25 240
seanhalle@25 241 /*------------------------------------- handle the last 23 bytes */
seanhalle@25 242 c += length;
seanhalle@25 243 switch(len) /* all the case statements fall through */
seanhalle@25 244 {
seanhalle@25 245 case 23: c+=((ub8)k[22]<<56);
seanhalle@25 246 case 22: c+=((ub8)k[21]<<48);
seanhalle@25 247 case 21: c+=((ub8)k[20]<<40);
seanhalle@25 248 case 20: c+=((ub8)k[19]<<32);
seanhalle@25 249 case 19: c+=((ub8)k[18]<<24);
seanhalle@25 250 case 18: c+=((ub8)k[17]<<16);
seanhalle@25 251 case 17: c+=((ub8)k[16]<<8);
seanhalle@25 252 /* the first byte of c is reserved for the length */
seanhalle@25 253 case 16: b+=((ub8)k[15]<<56);
seanhalle@25 254 case 15: b+=((ub8)k[14]<<48);
seanhalle@25 255 case 14: b+=((ub8)k[13]<<40);
seanhalle@25 256 case 13: b+=((ub8)k[12]<<32);
seanhalle@25 257 case 12: b+=((ub8)k[11]<<24);
seanhalle@25 258 case 11: b+=((ub8)k[10]<<16);
seanhalle@25 259 case 10: b+=((ub8)k[ 9]<<8);
seanhalle@25 260 case 9: b+=((ub8)k[ 8]);
seanhalle@25 261 case 8: a+=((ub8)k[ 7]<<56);
seanhalle@25 262 case 7: a+=((ub8)k[ 6]<<48);
seanhalle@25 263 case 6: a+=((ub8)k[ 5]<<40);
seanhalle@25 264 case 5: a+=((ub8)k[ 4]<<32);
seanhalle@25 265 case 4: a+=((ub8)k[ 3]<<24);
seanhalle@25 266 case 3: a+=((ub8)k[ 2]<<16);
seanhalle@25 267 case 2: a+=((ub8)k[ 1]<<8);
seanhalle@25 268 case 1: a+=((ub8)k[ 0]);
seanhalle@25 269 /* case 0: nothing left to add */
seanhalle@25 270 }
seanhalle@25 271 mix64(a,b,c);
seanhalle@25 272 /*-------------------------------------------- report the result */
seanhalle@25 273 return c;
seanhalle@25 274 }
seanhalle@25 275
seanhalle@25 276 #ifdef SELF_TEST
seanhalle@25 277
seanhalle@25 278 /* used for timings */
seanhalle@25 279 void driver1()
seanhalle@25 280 {
seanhalle@25 281 ub8 buf[256];
seanhalle@25 282 ub8 i;
seanhalle@25 283 ub8 h=0;
seanhalle@25 284
seanhalle@25 285 for (i=0; i<256; ++i)
seanhalle@25 286 {
seanhalle@25 287 h = hash(buf,i,h);
seanhalle@25 288 }
seanhalle@25 289 }
seanhalle@25 290
seanhalle@25 291 /* check that every input bit changes every output bit half the time */
seanhalle@25 292 #define HASHSTATE 1
seanhalle@25 293 #define HASHLEN 1
seanhalle@25 294 #define MAXPAIR 80
seanhalle@25 295 #define MAXLEN 5
seanhalle@25 296 void driver2()
seanhalle@25 297 {
seanhalle@25 298 ub1 qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
seanhalle@25 299 ub8 c[HASHSTATE], d[HASHSTATE], i, j=0, k, l, m, z;
seanhalle@25 300 ub8 e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
seanhalle@25 301 ub8 x[HASHSTATE],y[HASHSTATE];
seanhalle@25 302 ub8 hlen;
seanhalle@25 303
seanhalle@25 304 printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
seanhalle@25 305 for (hlen=0; hlen < MAXLEN; ++hlen)
seanhalle@25 306 {
seanhalle@25 307 z=0;
seanhalle@25 308 for (i=0; i<hlen; ++i) /*----------------------- for each byte, */
seanhalle@25 309 {
seanhalle@25 310 for (j=0; j<8; ++j) /*------------------------ for each bit, */
seanhalle@25 311 {
seanhalle@25 312 for (m=0; m<8; ++m) /*-------- for serveral possible levels, */
seanhalle@25 313 {
seanhalle@25 314 for (l=0; l<HASHSTATE; ++l) e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((ub8)0);
seanhalle@25 315
seanhalle@25 316 /*---- check that every input bit affects every output bit */
seanhalle@25 317 for (k=0; k<MAXPAIR; k+=2)
seanhalle@25 318 {
seanhalle@25 319 ub8 finished=1;
seanhalle@25 320 /* keys have one bit different */
seanhalle@25 321 for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (ub1)0;}
seanhalle@25 322 /* have a and b be two keys differing in only one bit */
seanhalle@25 323 a[i] ^= (k<<j);
seanhalle@25 324 a[i] ^= (k>>(8-j));
seanhalle@25 325 c[0] = hash(a, hlen, m);
seanhalle@25 326 b[i] ^= ((k+1)<<j);
seanhalle@25 327 b[i] ^= ((k+1)>>(8-j));
seanhalle@25 328 d[0] = hash(b, hlen, m);
seanhalle@25 329 /* check every bit is 1, 0, set, and not set at least once */
seanhalle@25 330 for (l=0; l<HASHSTATE; ++l)
seanhalle@25 331 {
seanhalle@25 332 e[l] &= (c[l]^d[l]);
seanhalle@25 333 f[l] &= ~(c[l]^d[l]);
seanhalle@25 334 g[l] &= c[l];
seanhalle@25 335 h[l] &= ~c[l];
seanhalle@25 336 x[l] &= d[l];
seanhalle@25 337 y[l] &= ~d[l];
seanhalle@25 338 if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
seanhalle@25 339 }
seanhalle@25 340 if (finished) break;
seanhalle@25 341 }
seanhalle@25 342 if (k>z) z=k;
seanhalle@25 343 if (k==MAXPAIR)
seanhalle@25 344 {
seanhalle@25 345
seanhalle@25 346 printf("Some bit didn't change: ");
seanhalle@25 347 printf("%.8lx %.8lx %.8lx %.8lx %.8lx %.8lx ",
seanhalle@25 348 e[0],f[0],g[0],h[0],x[0],y[0]);
seanhalle@25 349 printf("i %ld j %ld m %ld len %ld\n",
seanhalle@25 350 (ub4)i,(ub4)j,(ub4)m,(ub4)hlen);
seanhalle@25 351
seanhalle@25 352 }
seanhalle@25 353 if (z==MAXPAIR) goto done;
seanhalle@25 354 }
seanhalle@25 355 }
seanhalle@25 356 }
seanhalle@25 357 done:
seanhalle@25 358 if (z < MAXPAIR)
seanhalle@25 359 {
seanhalle@25 360 printf("Mix success %2ld bytes %2ld levels ",(ub4)i,(ub4)m);
seanhalle@25 361 printf("required %ld trials\n",(ub4)(z/2));
seanhalle@25 362 }
seanhalle@25 363 }
seanhalle@25 364 printf("\n");
seanhalle@25 365 }
seanhalle@25 366
seanhalle@25 367 /* Check for reading beyond the end of the buffer and alignment problems */
seanhalle@25 368 void driver3()
seanhalle@25 369 {
seanhalle@25 370 ub1 buf[MAXLEN+20], *b;
seanhalle@25 371 ub8 len;
seanhalle@25 372 ub1 q[] = "This is the time for all good men to come to the aid of their country";
seanhalle@25 373 ub1 qq[] = "xThis is the time for all good men to come to the aid of their country";
seanhalle@25 374 ub1 qqq[] = "xxThis is the time for all good men to come to the aid of their country";
seanhalle@25 375 ub1 qqqq[] = "xxxThis is the time for all good men to come to the aid of their country";
seanhalle@25 376 ub1 o[] = "xxxxThis is the time for all good men to come to the aid of their country";
seanhalle@25 377 ub1 oo[] = "xxxxxThis is the time for all good men to come to the aid of their country";
seanhalle@25 378 ub1 ooo[] = "xxxxxxThis is the time for all good men to come to the aid of their country";
seanhalle@25 379 ub1 oooo[] = "xxxxxxxThis is the time for all good men to come to the aid of their country";
seanhalle@25 380 ub8 h,i,j,ref,x,y;
seanhalle@25 381
seanhalle@25 382 printf("Endianness. These should all be the same:\n");
seanhalle@25 383 h = hash(q+0, (ub8)(sizeof(q)-1), (ub8)0);
seanhalle@25 384 printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h>>32));
seanhalle@25 385 h = hash(qq+1, (ub8)(sizeof(q)-1), (ub8)0);
seanhalle@25 386 printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h>>32));
seanhalle@25 387 h = hash(qqq+2, (ub8)(sizeof(q)-1), (ub8)0);
seanhalle@25 388 printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h>>32));
seanhalle@25 389 h = hash(qqqq+3, (ub8)(sizeof(q)-1), (ub8)0);
seanhalle@25 390 printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h>>32));
seanhalle@25 391 h = hash(o+4, (ub8)(sizeof(q)-1), (ub8)0);
seanhalle@25 392 printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h>>32));
seanhalle@25 393 h = hash(oo+5, (ub8)(sizeof(q)-1), (ub8)0);
seanhalle@25 394 printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h>>32));
seanhalle@25 395 h = hash(ooo+6, (ub8)(sizeof(q)-1), (ub8)0);
seanhalle@25 396 printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h>>32));
seanhalle@25 397 h = hash(oooo+7, (ub8)(sizeof(q)-1), (ub8)0);
seanhalle@25 398 printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h>>32));
seanhalle@25 399 printf("\n");
seanhalle@25 400 for (h=0, b=buf+1; h<8; ++h, ++b)
seanhalle@25 401 {
seanhalle@25 402 for (i=0; i<MAXLEN; ++i)
seanhalle@25 403 {
seanhalle@25 404 len = i;
seanhalle@25 405 for (j=0; j<i; ++j) *(b+j)=0;
seanhalle@25 406
seanhalle@25 407 /* these should all be equal */
seanhalle@25 408 ref = hash(b, len, (ub8)1);
seanhalle@25 409 *(b+i)=(ub1)~0;
seanhalle@25 410 *(b-1)=(ub1)~0;
seanhalle@25 411 x = hash(b, len, (ub8)1);
seanhalle@25 412 y = hash(b, len, (ub8)1);
seanhalle@25 413 if ((ref != x) || (ref != y))
seanhalle@25 414 {
seanhalle@25 415
seanhalle@25 416 printf("alignment error: %.8lx %.8lx %.8lx %ld %ld\n",ref,x,y,h,i);
seanhalle@25 417
seanhalle@25 418 }
seanhalle@25 419 }
seanhalle@25 420 }
seanhalle@25 421 }
seanhalle@25 422
seanhalle@25 423 /* check for problems with nulls */
seanhalle@25 424 void driver4()
seanhalle@25 425 {
seanhalle@25 426 ub1 buf[1];
seanhalle@25 427 ub8 h,i,state[HASHSTATE];
seanhalle@25 428
seanhalle@25 429
seanhalle@25 430 buf[0] = ~0;
seanhalle@25 431 for (i=0; i<HASHSTATE; ++i) state[i] = 1;
seanhalle@25 432 printf("These should all be different\n");
seanhalle@25 433 for (i=0, h=0; i<8; ++i)
seanhalle@25 434 {
seanhalle@25 435 h = hash(buf, (ub8)0, h);
seanhalle@25 436 printf("%2ld 0-byte strings, hash is %.8lx%.8lx\n", (ub4)i,
seanhalle@25 437 (ub4)h,(ub4)(h>>32));
seanhalle@25 438 }
seanhalle@25 439 }
seanhalle@25 440
seanhalle@25 441
seanhalle@25 442 int test_lookup8()
seanhalle@25 443 {
seanhalle@25 444 driver1(); /* test that the key is hashed: used for timings */
seanhalle@25 445 driver2(); /* test that whole key is hashed thoroughly */
seanhalle@25 446 driver3(); /* test that nothing but the key is hashed */
seanhalle@25 447 driver4(); /* test hashing multiple buffers (all buffers are null) */
seanhalle@25 448 return 1;
seanhalle@25 449 }
seanhalle@25 450
seanhalle@25 451 #endif /* SELF_TEST */