Skip to content

Instantly share code, notes, and snippets.

@jhaberstro
Created August 17, 2010 00:35
Show Gist options
  • Save jhaberstro/528045 to your computer and use it in GitHub Desktop.
Save jhaberstro/528045 to your computer and use it in GitHub Desktop.
#define CONSTANTHASH_DEPTH 64
// randomly generated constants. The bottom half has to be FFFF or
// else the entire hash loses some strength
static const size_t CONSTANTHASH_CONSTANTS[CONSTANTHASH_DEPTH+1] =
{
0x6157FFFF, 0x5387FFFF, 0x8ECBFFFF, 0xB3DBFFFF, 0x1AFDFFFF, 0xD1FDFFFF, 0x19B3FFFF, 0xE6C7FFFF,
0x53BDFFFF, 0xCDAFFFFF, 0xE543FFFF, 0x369DFFFF, 0x8135FFFF, 0x50E1FFFF, 0x115BFFFF, 0x07D1FFFF,
0x9AA1FFFF, 0x4D87FFFF, 0x442BFFFF, 0xEAA5FFFF, 0xAEDBFFFF, 0xB6A5FFFF, 0xAFE9FFFF, 0xE895FFFF,
0x4E05FFFF, 0xF8BFFFFF, 0xCB5DFFFF, 0x2F85FFFF, 0xF1DFFFFF, 0xD5ADFFFF, 0x438DFFFF, 0x6073FFFF,
0xA99FFFFF, 0x2E0BFFFF, 0xF729FFFF, 0x5D01FFFF, 0x1ACDFFFF, 0xFAD1FFFF, 0xD86BFFFF, 0xE909FFFF,
0xD3BDFFFF, 0xF35BFFFF, 0xD53DFFFF, 0x4DC1FFFF, 0x6897FFFF, 0x6E4DFFFF, 0x305BFFFF, 0x6F0DFFFF,
0x33C9FFFF, 0xC955FFFF, 0xC1EDFFFF, 0x48D5FFFF, 0x0CF5FFFF, 0x356BFFFF, 0x5F65FFFF, 0x71C1FFFF,
0x3F13FFFF, 0x489DFFFF, 0xEBA3FFFF, 0x340DFFFF, 0xF537FFFF, 0xD5E7FFFF, 0x6D27FFFF, 0x89D7FFFF,
0xA93FFFFF,
};
// multiplication constants, this allows an abstract use
// of the string length
static const size_t CONSTANTHASH_MULTS[CONSTANTHASH_DEPTH+1] =
{
33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48,
49, 50, 51, 52, 53, 54, 55, 56,
57, 58, 59, 60, 61, 62, 63, 64,
65, 66, 67, 68, 69, 70, 71, 72,
73, 74, 75, 76, 77, 78, 79, 80,
81, 82, 83, 84, 85, 86, 87, 88,
89, 90, 91, 92, 93, 94, 95, 96,
97,
};
}
#define CONSTANTHASH_RECURSE_00(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[0] : CONSTANTHASH_MULTS[0] * CONSTANTHASH_RECURSE_01(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_01(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[1] : CONSTANTHASH_MULTS[1] * CONSTANTHASH_RECURSE_02(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_02(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[2] : CONSTANTHASH_MULTS[2] * CONSTANTHASH_RECURSE_03(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_03(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[3] : CONSTANTHASH_MULTS[3] * CONSTANTHASH_RECURSE_04(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_04(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[4] : CONSTANTHASH_MULTS[4] * CONSTANTHASH_RECURSE_05(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_05(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[5] : CONSTANTHASH_MULTS[5] * CONSTANTHASH_RECURSE_06(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_06(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[6] : CONSTANTHASH_MULTS[6] * CONSTANTHASH_RECURSE_07(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_07(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[7] : CONSTANTHASH_MULTS[7] * CONSTANTHASH_RECURSE_08(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_08(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[8] : CONSTANTHASH_MULTS[8] * CONSTANTHASH_RECURSE_09(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_09(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[9] : CONSTANTHASH_MULTS[9] * CONSTANTHASH_RECURSE_10(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_10(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[10] : CONSTANTHASH_MULTS[10] * CONSTANTHASH_RECURSE_11(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_11(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[11] : CONSTANTHASH_MULTS[11] * CONSTANTHASH_RECURSE_12(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_12(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[12] : CONSTANTHASH_MULTS[12] * CONSTANTHASH_RECURSE_13(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_13(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[13] : CONSTANTHASH_MULTS[13] * CONSTANTHASH_RECURSE_14(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_14(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[14] : CONSTANTHASH_MULTS[14] * CONSTANTHASH_RECURSE_15(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_15(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[15] : CONSTANTHASH_MULTS[15] * CONSTANTHASH_RECURSE_16(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_16(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[16] : CONSTANTHASH_MULTS[16] * CONSTANTHASH_RECURSE_17(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_17(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[17] : CONSTANTHASH_MULTS[17] * CONSTANTHASH_RECURSE_18(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_18(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[18] : CONSTANTHASH_MULTS[18] * CONSTANTHASH_RECURSE_19(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_19(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[19] : CONSTANTHASH_MULTS[19] * CONSTANTHASH_RECURSE_20(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_20(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[20] : CONSTANTHASH_MULTS[20] * CONSTANTHASH_RECURSE_21(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_21(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[21] : CONSTANTHASH_MULTS[21] * CONSTANTHASH_RECURSE_22(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_22(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[22] : CONSTANTHASH_MULTS[22] * CONSTANTHASH_RECURSE_23(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_23(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[23] : CONSTANTHASH_MULTS[23] * CONSTANTHASH_RECURSE_24(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_24(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[24] : CONSTANTHASH_MULTS[24] * CONSTANTHASH_RECURSE_25(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_25(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[25] : CONSTANTHASH_MULTS[25] * CONSTANTHASH_RECURSE_26(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_26(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[26] : CONSTANTHASH_MULTS[26] * CONSTANTHASH_RECURSE_27(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_27(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[27] : CONSTANTHASH_MULTS[27] * CONSTANTHASH_RECURSE_28(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_28(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[28] : CONSTANTHASH_MULTS[28] * CONSTANTHASH_RECURSE_29(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_29(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[29] : CONSTANTHASH_MULTS[29] * CONSTANTHASH_RECURSE_30(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_30(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[30] : CONSTANTHASH_MULTS[30] * CONSTANTHASH_RECURSE_31(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_31(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[31] : CONSTANTHASH_MULTS[31] * CONSTANTHASH_RECURSE_32(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_32(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[32] : CONSTANTHASH_MULTS[32] * CONSTANTHASH_RECURSE_33(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_33(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[33] : CONSTANTHASH_MULTS[33] * CONSTANTHASH_RECURSE_34(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_34(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[34] : CONSTANTHASH_MULTS[34] * CONSTANTHASH_RECURSE_35(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_35(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[35] : CONSTANTHASH_MULTS[35] * CONSTANTHASH_RECURSE_36(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_36(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[36] : CONSTANTHASH_MULTS[36] * CONSTANTHASH_RECURSE_37(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_37(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[37] : CONSTANTHASH_MULTS[37] * CONSTANTHASH_RECURSE_38(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_38(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[38] : CONSTANTHASH_MULTS[38] * CONSTANTHASH_RECURSE_39(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_39(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[39] : CONSTANTHASH_MULTS[39] * CONSTANTHASH_RECURSE_40(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_40(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[40] : CONSTANTHASH_MULTS[40] * CONSTANTHASH_RECURSE_41(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_41(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[41] : CONSTANTHASH_MULTS[41] * CONSTANTHASH_RECURSE_42(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_42(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[42] : CONSTANTHASH_MULTS[42] * CONSTANTHASH_RECURSE_43(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_43(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[43] : CONSTANTHASH_MULTS[43] * CONSTANTHASH_RECURSE_44(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_44(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[44] : CONSTANTHASH_MULTS[44] * CONSTANTHASH_RECURSE_45(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_45(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[45] : CONSTANTHASH_MULTS[45] * CONSTANTHASH_RECURSE_46(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_46(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[46] : CONSTANTHASH_MULTS[46] * CONSTANTHASH_RECURSE_47(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_47(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[47] : CONSTANTHASH_MULTS[47] * CONSTANTHASH_RECURSE_48(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_48(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[48] : CONSTANTHASH_MULTS[48] * CONSTANTHASH_RECURSE_49(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_49(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[49] : CONSTANTHASH_MULTS[49] * CONSTANTHASH_RECURSE_50(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_50(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[50] : CONSTANTHASH_MULTS[50] * CONSTANTHASH_RECURSE_51(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_51(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[51] : CONSTANTHASH_MULTS[51] * CONSTANTHASH_RECURSE_52(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_52(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[52] : CONSTANTHASH_MULTS[52] * CONSTANTHASH_RECURSE_53(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_53(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[53] : CONSTANTHASH_MULTS[53] * CONSTANTHASH_RECURSE_54(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_54(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[54] : CONSTANTHASH_MULTS[54] * CONSTANTHASH_RECURSE_55(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_55(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[55] : CONSTANTHASH_MULTS[55] * CONSTANTHASH_RECURSE_56(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_56(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[56] : CONSTANTHASH_MULTS[56] * CONSTANTHASH_RECURSE_57(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_57(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[57] : CONSTANTHASH_MULTS[57] * CONSTANTHASH_RECURSE_58(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_58(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[58] : CONSTANTHASH_MULTS[58] * CONSTANTHASH_RECURSE_59(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_59(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[59] : CONSTANTHASH_MULTS[59] * CONSTANTHASH_RECURSE_60(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_60(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[60] : CONSTANTHASH_MULTS[60] * CONSTANTHASH_RECURSE_61(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_61(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[61] : CONSTANTHASH_MULTS[61] * CONSTANTHASH_RECURSE_62(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_62(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[62] : CONSTANTHASH_MULTS[62] * CONSTANTHASH_RECURSE_63(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_63(string, value) CONSTANTHASH_FUNCTION((*(string+1) == 0 ? CONSTANTHASH_CONSTANTS[63] : CONSTANTHASH_MULTS[63] * CONSTANTHASH_RECURSE_64(string+1, *(string+1))), value)
#define CONSTANTHASH_RECURSE_64(string, value) CONSTANTHASH_CONSTANTS[64]
// The following is the function used for hashing
// Do NOT use NEXTHASH more than once, it will cause
// N-Squared expansion and make compilation very slow
// If not impossible
#define CONSTANTHASH_FUNCTION(next, value) ((value << 15) | value | 33) + ((11 * value * value * 257) ^ CONSTANTHASH_CONSTANTS[value & 0x3f] ^ (next))
// finally the macro used to generate the hash
#define CONST_HASH(string) CONSTANTHASH_RECURSE_00(string, *string)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment