Skip to content

Instantly share code, notes, and snippets.

@oplanre
Last active August 12, 2024 18:20
Show Gist options
  • Save oplanre/e384ed2a4c0fea698ed0e15d24157611 to your computer and use it in GitHub Desktop.
Save oplanre/e384ed2a4c0fea698ed0e15d24157611 to your computer and use it in GitHub Desktop.
Constexpr port of php's string hashing function
static constexpr zend_ulong DJBX33A(const char *str, size_t len){
zend_ulong hash = 5381;
#if defined(_WIN32) || defined(__i386__) || defined(__x86_64__) || defined(__aarch64__)
// Version with multiplication works better on modern CPUs
for (; len >= 8; len -= 8, str += 8) {
uint64_t chunk;
std::memcpy(&chunk, str, sizeof(chunk));
hash = hash * 33 * 33 * 33 * 33 + ((chunk >> (8 * 0)) & 0xff) * 33 * 33 * 33 + ((chunk >> (8 * 1)) & 0xff) * 33 * 33 +
((chunk >> (8 * 2)) & 0xff) * 33 + ((chunk >> (8 * 3)) & 0xff);
hash = hash * 33 * 33 * 33 * 33 + ((chunk >> (8 * 4)) & 0xff) * 33 * 33 * 33 + ((chunk >> (8 * 5)) & 0xff) * 33 * 33 +
((chunk >> (8 * 6)) & 0xff) * 33 + ((chunk >> (8 * 7)) & 0xff);
}
// Remaining bytes
for (; len >= 4; len -= 4, str += 4) {
hash = hash * 33 * 33 * 33 * 33 + str[0] * 33 * 33 * 33 + str[1] * 33 * 33 + str[2] * 33 + str[3];
}
for (; len >= 2; len -= 2, str += 2) { hash = hash * 33 * 33 * 33 + str[0] * 33 * 33 + str[1] * 33; }
if (len == 1) { hash = hash * 33 + *str; }
#else
// Variant with the hash unrolled eight times
for (; len >= 8; len -= 8) {
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
}
// Remaining bytes
switch (len) {
case 7: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
case 6: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
case 5: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
case 4: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
case 3: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
case 2: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
case 1: hash = ((hash << 5) + hash) + *str++; break;
case 0:
break;
// EMPTY_SWITCH_DEFAULT_CASE()
}
#endif
if constexpr (sizeof(zend_ulong) == 8) return hash | 0x8000000000000000ULL;
if constexpr (sizeof(zend_ulong) == 4) return hash | 0x80000000UL;
static_assert(sizeof(zend_ulong) == 8 || sizeof(zend_ulong) == 4, "Unsupported hash size");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment