Last active
January 27, 2022 21:25
-
-
Save notwa/6ec86a89d6680b6b250cf6524988640f to your computer and use it in GitHub Desktop.
a string hashing function found in Warcraft III
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdint.h> | |
#include <stdbool.h> | |
#include <stdio.h> | |
#include <string.h> | |
#include <inttypes.h> | |
typedef uint8_t u8; | |
typedef uint32_t u32; | |
typedef uint64_t u64; | |
const u64 table[16] = { | |
// magic numbers for each possible value of a nybble. | |
0x486E26EEDCAA16B3, 0xE1918EEF202DAFDB, | |
0x341C7DC71C365303, 0x40EF2D3765FD5E49, | |
0xD6057177904ECE93, 0x1C38024F98FD323B, | |
0xE3061AE7A39B0FA1, 0x9797F25FE4444563, | |
0xCD2EC20C8DC1B898, 0x31759633799A306D, | |
0x8C2063852E6E9627, 0x79237D9973922C66, | |
0x8728628D28628824, 0x8F1F7E9625887795, | |
0x296E3281389C0D60, 0x6F4893CA61636542 | |
}; | |
u64 wc3hash(const char *key, size_t len, u64 hash, bool isPath) { | |
// technically there doesn't seem to be a | |
// length argument in the original function, | |
// I'm just adding it so you can hash strings with '\0' in them. | |
if (key == NULL) | |
return 0; | |
if (hash == 0) | |
hash = 0x7FED7FED7FED7FED; | |
u64 state = 0xEEEEEEEEEEEEEEEE; | |
for (size_t i = 0; i < len; i++) { | |
u8 v; | |
if (isPath) { | |
char c = key[i]; | |
if (c >= 'a' && c <= 'z') | |
c -= 'a' - 'A'; // uppercase | |
if (c == '/') | |
c = '\\'; // DOS-style paths | |
v = (u8)c; | |
} else { | |
v = (u8)key[i]; | |
} | |
hash += state; | |
hash ^= table[v >> 4] + table[v & 0xF]; | |
state += state << 5; | |
state += hash + v + 3; | |
} | |
if (hash == 0) | |
return 1; | |
return hash; | |
} | |
u64 wc3hashC(const char *key) { | |
// simple interface that only takes a null-terminated string. | |
return wc3hash(key, strlen(key), 0, true); | |
} | |
int main(int argc, char **argv) { | |
if (argc == 1) { | |
const char str[] = "IseeDeadPeople"; | |
u64 hash = wc3hashC(str); | |
fprintf(stderr, "%" PRIX64 " should equal 701EA16D47F385FC\n", hash); | |
return hash != 0x701EA16D47F385FC; | |
} | |
for (int i = 1; i < argc; i++) { | |
u64 hash = wc3hashC(argv[i]); | |
u32 hash32 = (hash >> 32) ^ hash; | |
printf("%" PRIX64 "\t%08X\n", hash, hash32); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment