Skip to content

Instantly share code, notes, and snippets.

@nilium
Last active June 26, 2020 03:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nilium/11019417 to your computer and use it in GitHub Desktop.
Save nilium/11019417 to your computer and use it in GitHub Desktop.
A constexpr user-defined literal for C++1y (C++14) using snowhash. Do not use this hash function -- it's very bad.
.section __TEXT,__text,regular,pure_instructions
.globl _main
.align 4, 0x90
_main: ## @main
.cfi_startproc
## BB#0:
pushq %rbp
Ltmp2:
.cfi_def_cfa_offset 16
Ltmp3:
.cfi_offset %rbp, -16
movq %rsp, %rbp
Ltmp4:
.cfi_def_cfa_register %rbp
subq $64, %rsp
leaq L_.str(%rip), %rax
movl $3456861364, %ecx ## imm = 0xCE0B84B4
leaq L_.str1(%rip), %rdx
movabsq $-4531687619883848966, %r8 ## imm = 0xC11C361E9FC9AAFA
movl $0, -4(%rbp)
movl %edi, -8(%rbp)
movq %rsi, -16(%rbp)
movl $-838105932, -20(%rbp) ## imm = 0xFFFFFFFFCE0B84B4
movq %r8, -32(%rbp)
movl $-838105932, -36(%rbp) ## imm = 0xFFFFFFFFCE0B84B4
movq %r8, -48(%rbp)
movq %rax, %rdi
movl %ecx, %esi
movq %rdx, -56(%rbp) ## 8-byte Spill
movl %ecx, %edx
movq -56(%rbp), %rcx ## 8-byte Reload
movb $0, %al
callq _printf
leaq L_.str2(%rip), %rdi
movabsq $-4531687619883848966, %rcx ## imm = 0xC11C361E9FC9AAFA
leaq L_.str1(%rip), %r8
movq %rcx, %rsi
movq %rcx, %rdx
movq %r8, %rcx
movl %eax, -60(%rbp) ## 4-byte Spill
movb $0, %al
callq _printf
movl $0, %r9d
movl %eax, -64(%rbp) ## 4-byte Spill
movl %r9d, %eax
addq $64, %rsp
popq %rbp
ret
.cfi_endproc
.section __TEXT,__cstring,cstring_literals
L_.str: ## @.str
.asciz "Hash32: 0x%08X 0x%08X (same: %s)\n"
L_.str1: ## @.str1
.asciz "yes"
L_.str2: ## @.str2
.asciz "Hash64: 0x%016llX 0x%016llX (same: %s)\n"
.subsections_via_symbols
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <type_traits>
template <typename T> struct hash_bits_t { /* undefined */ };
template <>
struct hash_bits_t<uint32_t>
{
enum : uint32_t {
SEED = 0x9E2030F1U,
HASH_SCALE = 439,
CODE_SCALE = 23,
INDEX_INCR = 257,
MASK_OFFSET = 16,
};
using hash_type = uint32_t;
};
template <>
struct hash_bits_t<uint64_t>
{
enum : uint64_t {
SEED = 0x9E2030F19E2030F1ULL,
HASH_SCALE = 5741,
CODE_SCALE = 23,
INDEX_INCR = 257,
MASK_OFFSET = 48,
};
using hash_type = uint64_t;
};
template <typename IH, int OFF = hash_bits_t<IH>::MASK_OFFSET, typename IDXT>
constexpr IH hash_mask(IDXT index)
{
constexpr IH mask_left[16] {
IH(0x0000) << OFF, IH(0x8000) << OFF, IH(0xC000) << OFF, IH(0xE000) << OFF,
IH(0xF000) << OFF, IH(0xF800) << OFF, IH(0xFC00) << OFF, IH(0xFE00) << OFF,
IH(0xFF00) << OFF, IH(0xFF80) << OFF, IH(0xFFC0) << OFF, IH(0xFFE0) << OFF,
IH(0xFFF0) << OFF, IH(0xFFF8) << OFF, IH(0xFFFC) << OFF, IH(0xFFFE) << OFF
};
return mask_left[index];
}
template <typename T, typename BITS = hash_bits_t<T>>
constexpr T hash(const char *str, size_t length, T seed = BITS::SEED)
{
static_assert(std::is_same<T, typename BITS::hash_type>::value, "BITS::value_type != T");
constexpr size_t bitsize = sizeof(seed) * 8;
T hash = seed;
for (size_t index = 0; index < length; ++index) {
T const code = str[index];
hash = hash * BITS::HASH_SCALE + code * BITS::CODE_SCALE + (index + BITS::INDEX_INCR);
T const shift =
((code & 0x9) | ((code & 0x10) >> 2) | ((code & 0x40) >> 5)) ^
((code & 0xA) >> 5) | ((code & 0x2) << 2) | ((code & 0x4) >> 1);
hash = (hash << shift) | ((hash & hash_mask<T>(shift)) >> (bitsize - shift));
}
return hash;
}
constexpr uint32_t operator"" _hash32 (const char *str, size_t length)
{
using bits = hash_bits_t<uint32_t>;
return hash<uint32_t>(str, length, bits::SEED);
}
constexpr uint64_t operator"" _hash64 (const char *str, size_t length)
{
using bits = hash_bits_t<uint64_t>;
return hash<uint64_t>(str, length, bits::SEED);
}
int main(int argc, char const *argv[])
{
constexpr uint32_t cvar_r_clearScreen = "r_clearScreen"_hash32;
constexpr uint64_t cvar_r_clearScreen64 = "r_clearScreen"_hash64;
constexpr uint32_t cvar_r_clearScreen_expected = 0xce0b84b4U; // results from snowhash tool
constexpr uint64_t cvar_r_clearScreen_expected64 = 0xc11c361e9fc9aafaULL;
printf("Hash32: 0x%08X 0x%08X (same: %s)\n",
cvar_r_clearScreen,
cvar_r_clearScreen_expected,
((cvar_r_clearScreen_expected == cvar_r_clearScreen) ? "yes" : "no")
);
printf("Hash64: 0x%016llX 0x%016llX (same: %s)\n",
cvar_r_clearScreen64,
cvar_r_clearScreen_expected64,
((cvar_r_clearScreen_expected64 == cvar_r_clearScreen64) ? "yes" : "no")
);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment