Common/src/hash64.cc

0001 #include "CondFormats/Common/interface/hash64.h"
0002
0003 /*
0004 --------------------------------------------------------------------
0005 mix -- mix 3 64-bit values reversibly.
0006 mix() takes 48 machine instructions, but only 24 cycles on a superscalar
0007   machine (like Intel's new MMX architecture).  It requires 4 64-bit
0008   registers for 4::2 parallelism.
0009 All 1-bit deltas, all 2-bit deltas, all deltas composed of top bits of
0010   (a,b,c), and all deltas of bottom bits were tested.  All deltas were
0011   tested both on random keys and on keys that were nearly all zero.
0012   These deltas all cause every bit of c to change between 1/3 and 2/3
0013   of the time (well, only 113/400 to 287/400 of the time for some
0014   2-bit delta).  These deltas all cause at least 80 bits to change
0015   among (a,b,c) when the mix is run either forward or backward (yes it
0016   is reversible).
0017 This implies that a hash using mix64 has no funnels.  There may be
0018   characteristics with 3-bit deltas or bigger, I didn't test for
0019   those.
0020 --------------------------------------------------------------------
0021 */
0022 #define mix64(a, b, c) \
0023   {                    \
0024     a -= b;            \
0025     a -= c;            \
0026     a ^= (c >> 43);    \
0027     b -= c;            \
0028     b -= a;            \
0029     b ^= (a << 9);     \
0030     c -= a;            \
0031     c -= b;            \
0032     c ^= (b >> 8);     \
0033     a -= b;            \
0034     a -= c;            \
0035     a ^= (c >> 38);    \
0036     b -= c;            \
0037     b -= a;            \
0038     b ^= (a << 23);    \
0039     c -= a;            \
0040     c -= b;            \
0041     c ^= (b >> 5);     \
0042     a -= b;            \
0043     a -= c;            \
0044     a ^= (c >> 35);    \
0045     b -= c;            \
0046     b -= a;            \
0047     b ^= (a << 49);    \
0048     c -= a;            \
0049     c -= b;            \
0050     c ^= (b >> 11);    \
0051     a -= b;            \
0052     a -= c;            \
0053     a ^= (c >> 12);    \
0054     b -= c;            \
0055     b -= a;            \
0056     b ^= (a << 18);    \
0057     c -= a;            \
0058     c -= b;            \
0059     c ^= (b >> 22);    \
0060   }
0061
0062 typedef unsigned long long ub8; /* unsigned 8-byte quantities */
0063 typedef unsigned long int ub4;  /* unsigned 4-byte quantities */
0064 typedef unsigned char ub1;
0065
0066 namespace cond {
0067
0068   ub8 hash64(ub1 *k, ub8 length, ub8 level)
0069   // register ub1 *k;        /* the key */
0070   // register ub8  length;   /* the length of the key */
0071   // register ub8  level;    /* the previous hash, or an arbitrary value */
0072   {
0073     ub8 a, b, c, len;
0074
0075     /* Set up the internal state */
0076     len = length;
0077     a = b = level;            /* the previous hash value */
0078     c = 0x9e3779b97f4a7c13LL; /* the golden ratio; an arbitrary value */
0079
0080     /*---------------------------------------- handle most of the key */
0081     if (((unsigned long)k) & 7) {
0082       while (len >= 24) {
0083         a += (k[0] + ((ub8)k[1] << 8) + ((ub8)k[2] << 16) + ((ub8)k[3] << 24) + ((ub8)k[4] << 32) + ((ub8)k[5] << 40) +
0084               ((ub8)k[6] << 48) + ((ub8)k[7] << 56));
0085         b += (k[8] + ((ub8)k[9] << 8) + ((ub8)k[10] << 16) + ((ub8)k[11] << 24) + ((ub8)k[12] << 32) +
0086               ((ub8)k[13] << 40) + ((ub8)k[14] << 48) + ((ub8)k[15] << 56));
0087         c += (k[16] + ((ub8)k[17] << 8) + ((ub8)k[18] << 16) + ((ub8)k[19] << 24) + ((ub8)k[20] << 32) +
0088               ((ub8)k[21] << 40) + ((ub8)k[22] << 48) + ((ub8)k[23] << 56));
0089         mix64(a, b, c);
0090         k += 24;
0091         len -= 24;
0092       }
0093     } else {
0094       while (len >= 24) /* aligned */
0095       {
0096         a += *(ub8 *)(k + 0);
0097         b += *(ub8 *)(k + 8);
0098         c += *(ub8 *)(k + 16);
0099         mix64(a, b, c);
0100         k += 24;
0101         len -= 24;
0102       }
0103     }
0104
0105     /*------------------------------------- handle the last 23 bytes */
0106     c += length;
0107     switch (len) /* all the case statements fall through */
0108     {
0109       case 23:
0110         c += ((ub8)k[22] << 56);
0111         [[fallthrough]];
0112       case 22:
0113         c += ((ub8)k[21] << 48);
0114         [[fallthrough]];
0115       case 21:
0116         c += ((ub8)k[20] << 40);
0117         [[fallthrough]];
0118       case 20:
0119         c += ((ub8)k[19] << 32);
0120         [[fallthrough]];
0121       case 19:
0122         c += ((ub8)k[18] << 24);
0123         [[fallthrough]];
0124       case 18:
0125         c += ((ub8)k[17] << 16);
0126         [[fallthrough]];
0127       case 17:
0128         c += ((ub8)k[16] << 8);
0129         [[fallthrough]];
0130         /* the first byte of c is reserved for the length */
0131       case 16:
0132         b += ((ub8)k[15] << 56);
0133         [[fallthrough]];
0134       case 15:
0135         b += ((ub8)k[14] << 48);
0136         [[fallthrough]];
0137       case 14:
0138         b += ((ub8)k[13] << 40);
0139         [[fallthrough]];
0140       case 13:
0141         b += ((ub8)k[12] << 32);
0142         [[fallthrough]];
0143       case 12:
0144         b += ((ub8)k[11] << 24);
0145         [[fallthrough]];
0146       case 11:
0147         b += ((ub8)k[10] << 16);
0148         [[fallthrough]];
0149       case 10:
0150         b += ((ub8)k[9] << 8);
0151         [[fallthrough]];
0152       case 9:
0153         b += ((ub8)k[8]);
0154         [[fallthrough]];
0155       case 8:
0156         a += ((ub8)k[7] << 56);
0157         [[fallthrough]];
0158       case 7:
0159         a += ((ub8)k[6] << 48);
0160         [[fallthrough]];
0161       case 6:
0162         a += ((ub8)k[5] << 40);
0163         [[fallthrough]];
0164       case 5:
0165         a += ((ub8)k[4] << 32);
0166         [[fallthrough]];
0167       case 4:
0168         a += ((ub8)k[3] << 24);
0169         [[fallthrough]];
0170       case 3:
0171         a += ((ub8)k[2] << 16);
0172         [[fallthrough]];
0173       case 2:
0174         a += ((ub8)k[1] << 8);
0175         [[fallthrough]];
0176       case 1:
0177         a += ((ub8)k[0]);
0178         /* case 0: nothing left to add */
0179     }
0180     mix64(a, b, c);
0181     /*-------------------------------------------- report the result */
0182     return c;
0183   }
0184
0185 }  // namespace cond