Common/test/hash64_t.cpp

0001 #include "CondFormats/Common/interface/hash64.h"
0002
0003 typedef unsigned long long ub8; /* unsigned 8-byte quantities */
0004 typedef unsigned long int ub4;  /* unsigned 4-byte quantities */
0005 typedef unsigned char ub1;
0006
0007 inline ub8 hashsize(ub8 n) { return (ub8)1 << (n); }
0008 inline ub8 hashmask(ub8 n) { return hashsize(n) - 1; }
0009
0010 #include <cstdio>
0011 #include <cstddef>
0012 #include <cstdlib>
0013
0014 inline ub8 hash(ub1* k, ub8 length, ub8 level) { return cond::hash64(k, length, level); }
0015
0016 /* used for timings */
0017 void driver1() {
0018   ub1 buf[256];
0019   ub8 i;
0020   ub8 h = 0;
0021
0022   for (i = 0; i < 256; ++i) {
0023     h = hash(buf, i, h);
0024   }
0025 }
0026
0027 /* check that every input bit changes every output bit half the time */
0028 #define HASHSTATE 1
0029 #define HASHLEN 1
0030 #define MAXPAIR 80
0031 #define MAXLEN 5
0032 void driver2() {
0033   ub1 qa[MAXLEN + 1], qb[MAXLEN + 2], *a = &qa[0], *b = &qb[1];
0034   ub8 c[HASHSTATE], d[HASHSTATE], i = 0, j = 0, k = 0, l = 0, m = 0, z = 0;
0035   ub8 e[HASHSTATE], f[HASHSTATE], g[HASHSTATE], h[HASHSTATE];
0036   ub8 x[HASHSTATE], y[HASHSTATE];
0037   ub8 hlen = 0;
0038
0039   printf("No more than %d trials should ever be needed \n", MAXPAIR / 2);
0040   for (hlen = 0; hlen < MAXLEN; ++hlen) {
0041     z = 0;
0042     for (i = 0; i < hlen; ++i) /*----------------------- for each byte, */
0043     {
0044       for (j = 0; j < 8; ++j) /*------------------------ for each bit, */
0045       {
0046         for (m = 0; m < 8; ++m) /*-------- for serveral possible levels, */
0047         {
0048           for (l = 0; l < HASHSTATE; ++l)
0049             e[l] = f[l] = g[l] = h[l] = x[l] = y[l] = ~((ub8)0);
0050
0051           /*---- check that every input bit affects every output bit */
0052           for (k = 0; k < MAXPAIR; k += 2) {
0053             ub8 finished = 1;
0054             /* keys have one bit different */
0055             for (l = 0; l < hlen + 1; ++l) {
0056               a[l] = b[l] = (ub1)0;
0057             }
0058             /* have a and b be two keys differing in only one bit */
0059             a[i] ^= (k << j);
0060             a[i] ^= (k >> (8 - j));
0061             c[0] = hash(a, hlen, m);
0062             b[i] ^= ((k + 1) << j);
0063             b[i] ^= ((k + 1) >> (8 - j));
0064             d[0] = hash(b, hlen, m);
0065             /* check every bit is 1, 0, set, and not set at least once */
0066             for (l = 0; l < HASHSTATE; ++l) {
0067               e[l] &= (c[l] ^ d[l]);
0068               f[l] &= ~(c[l] ^ d[l]);
0069               g[l] &= c[l];
0070               h[l] &= ~c[l];
0071               x[l] &= d[l];
0072               y[l] &= ~d[l];
0073               if (e[l] | f[l] | g[l] | h[l] | x[l] | y[l])
0074                 finished = 0;
0075             }
0076             if (finished)
0077               break;
0078           }
0079           if (k > z)
0080             z = k;
0081           if (k == MAXPAIR) {
0082             printf("Some bit didn't change: ");
0083             printf("%.8lx %.8lx %.8lx %.8lx %.8lx %.8lx  ",
0084                    (unsigned long)e[0],
0085                    (unsigned long)f[0],
0086                    (unsigned long)g[0],
0087                    (unsigned long)h[0],
0088                    (unsigned long)x[0],
0089                    (unsigned long)y[0]);
0090             printf("i %ld j %ld m %ld len %ld\n", (ub4)i, (ub4)j, (ub4)m, (ub4)hlen);
0091           }
0092           if (z == MAXPAIR)
0093             goto done;
0094         }
0095       }
0096     }
0097   done:
0098     if (z < MAXPAIR) {
0099       printf("Mix success  %2ld bytes  %2ld levels  ", (ub4)i, (ub4)m);
0100       printf("required  %ld  trials\n", (ub4)(z / 2));
0101     }
0102   }
0103   printf("\n");
0104 }
0105
0106 /* Check for reading beyond the end of the buffer and alignment problems */
0107 void driver3() {
0108   ub1 buf[MAXLEN + 20], *b;
0109   ub8 len;
0110   ub1 q[] = "This is the time for all good men to come to the aid of their country";
0111   ub1 qq[] = "xThis is the time for all good men to come to the aid of their country";
0112   ub1 qqq[] = "xxThis is the time for all good men to come to the aid of their country";
0113   ub1 qqqq[] = "xxxThis is the time for all good men to come to the aid of their country";
0114   ub1 o[] = "xxxxThis is the time for all good men to come to the aid of their country";
0115   ub1 oo[] = "xxxxxThis is the time for all good men to come to the aid of their country";
0116   ub1 ooo[] = "xxxxxxThis is the time for all good men to come to the aid of their country";
0117   ub1 oooo[] = "xxxxxxxThis is the time for all good men to come to the aid of their country";
0118   ub8 h, i, j, ref, x, y;
0119
0120   printf("Endianness.  These should all be the same:\n");
0121   h = hash(q + 0, (ub8)(sizeof(q) - 1), (ub8)0);
0122   printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h >> 32));
0123   h = hash(qq + 1, (ub8)(sizeof(q) - 1), (ub8)0);
0124   printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h >> 32));
0125   h = hash(qqq + 2, (ub8)(sizeof(q) - 1), (ub8)0);
0126   printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h >> 32));
0127   h = hash(qqqq + 3, (ub8)(sizeof(q) - 1), (ub8)0);
0128   printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h >> 32));
0129   h = hash(o + 4, (ub8)(sizeof(q) - 1), (ub8)0);
0130   printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h >> 32));
0131   h = hash(oo + 5, (ub8)(sizeof(q) - 1), (ub8)0);
0132   printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h >> 32));
0133   h = hash(ooo + 6, (ub8)(sizeof(q) - 1), (ub8)0);
0134   printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h >> 32));
0135   h = hash(oooo + 7, (ub8)(sizeof(q) - 1), (ub8)0);
0136   printf("%.8lx%.8lx\n", (ub4)h, (ub4)(h >> 32));
0137   printf("\n");
0138   for (h = 0, b = buf + 1; h < 8; ++h, ++b) {
0139     for (i = 0; i < MAXLEN; ++i) {
0140       len = i;
0141       for (j = 0; j < i; ++j)
0142         *(b + j) = 0;
0143
0144       /* these should all be equal */
0145       ref = hash(b, len, (ub8)1);
0146       *(b + i) = (ub1)~0;
0147       *(b - 1) = (ub1)~0;
0148       x = hash(b, len, (ub8)1);
0149       y = hash(b, len, (ub8)1);
0150       if ((ref != x) || (ref != y)) {
0151         printf("alignment error: %.8lx %.8lx %.8lx %ld %ld\n",
0152                (unsigned long)ref,
0153                (unsigned long)x,
0154                (unsigned long)y,
0155                (long)h,
0156                (long)i);
0157       }
0158     }
0159   }
0160 }
0161
0162 /* check for problems with nulls */
0163 void driver4() {
0164   ub1 buf[1];
0165   ub8 h, i;
0166
0167   buf[0] = ~0;
0168   printf("These should all be different\n");
0169   for (i = 0, h = 0; i < 8; ++i) {
0170     h = hash(buf, (ub8)0, h);
0171     printf("%2ld  0-byte strings, hash is  %.8lx%.8lx\n", (ub4)i, (ub4)h, (ub4)(h >> 32));
0172   }
0173 }
0174
0175 int main() {
0176   driver1(); /* test that the key is hashed: used for timings */
0177   driver2(); /* test that whole key is hashed thoroughly */
0178   driver3(); /* test that nothing but the key is hashed */
0179   driver4(); /* test hashing multiple buffers (all buffers are null) */
0180   return 0;
0181 }