Last active
December 3, 2016 18:47
-
-
Save vstakhov/b58b855532a424cd634b6c7ea7baa1b9 to your computer and use it in GitHub Desktop.
Seahash in C(++)
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 <string.h> | |
| #include <assert.h> | |
| static inline uint64_t | |
| diffuse(uint64_t val) | |
| { | |
| uint64_t a, b; | |
| val *= 0x6eed0e9da4d94a4fULL; | |
| a = val >> 32; | |
| b = val >> 60; | |
| val ^= a >> b; | |
| val *= 0x6eed0e9da4d94a4fULL; | |
| return val; | |
| } | |
| void sea_hash_test(const void *key, int len, uint32_t seed, void *out) { | |
| uint64_t a, b, c, d; | |
| uint64_t s = seed; | |
| uint64_t *p; | |
| unsigned char pad[8] = {0}; | |
| a = 0x16f11fe89b0d677cULL ^ s; | |
| b = 0xb480a793d8e6c86cULL; | |
| c = 0x6fe2e5aaf078ebc9ULL; | |
| d = 0x14f994a4c5259381ULL; | |
| p = (uint64_t *)key; | |
| while (len >= 32) { | |
| a ^= *p++; | |
| b ^= *p++; | |
| c ^= *p++; | |
| d ^= *p++; | |
| a = diffuse(a); | |
| b = diffuse(b); | |
| c = diffuse(c); | |
| d = diffuse(d); | |
| len -= 32; | |
| } | |
| switch (len) { | |
| case 25 ... 31: | |
| a ^= *p++; | |
| b ^= *p++; | |
| c ^= *p++; | |
| memcpy(pad, p, len - 24); | |
| d ^= *(uint64_t *)pad; | |
| a = diffuse(a); | |
| b = diffuse(b); | |
| c = diffuse(c); | |
| d = diffuse(d); | |
| break; | |
| case 24: | |
| a ^= *p++; | |
| b ^= *p++; | |
| c ^= *p++; | |
| a = diffuse(a); | |
| b = diffuse(b); | |
| c = diffuse(c); | |
| break; | |
| case 17 ... 23: | |
| a ^= *p++; | |
| b ^= *p++; | |
| memcpy(pad, p, len - 16); | |
| c ^= *(uint64_t *)pad; | |
| a = diffuse(a); | |
| b = diffuse(b); | |
| c = diffuse(c); | |
| break; | |
| case 16: | |
| a ^= *p++; | |
| b ^= *p++; | |
| a = diffuse(a); | |
| b = diffuse(b); | |
| break; | |
| case 9 ... 15: | |
| a ^= *p++; | |
| memcpy(pad, p, len - 8); | |
| b ^= *(uint64_t *)pad; | |
| a = diffuse(a); | |
| b = diffuse(b); | |
| break; | |
| case 8: | |
| a ^= *p++; | |
| a = diffuse(a); | |
| break; | |
| case 1 ... 7: | |
| memcpy(pad, p, len); | |
| a ^= *(uint64_t *)pad; | |
| a = diffuse(a); | |
| break; | |
| case 0: | |
| break; | |
| default: | |
| assert(0); | |
| } | |
| a ^= b; | |
| c ^= d; | |
| a ^= c; | |
| a ^= (uint64_t)len; | |
| uint64_t r = diffuse(a); | |
| memcpy(out, &r, 8); | |
| } |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
--- Testing metrohash64crc_1 "MetroHash64crc_1 for x64"
[[[ Sanity Tests ]]]
Verification value 0x29C68A50 : PASS
Running sanity check 1 ..........PASS
Running AppendedZeroesTest..........PASS
[[[ Speed Tests ]]]
Bulk speed test - 262144-byte keys
Alignment 7 - 10.785 bytes/cycle - 30857.32 MiB/sec @ 3 ghz
Alignment 6 - 7.986 bytes/cycle - 22848.70 MiB/sec @ 3 ghz
Alignment 5 - 9.084 bytes/cycle - 25990.22 MiB/sec @ 3 ghz
Alignment 4 - 8.705 bytes/cycle - 24904.86 MiB/sec @ 3 ghz
Alignment 3 - 9.312 bytes/cycle - 26641.40 MiB/sec @ 3 ghz
Alignment 2 - 9.567 bytes/cycle - 27372.12 MiB/sec @ 3 ghz
Alignment 1 - 10.151 bytes/cycle - 29042.75 MiB/sec @ 3 ghz
Alignment 0 - 9.258 bytes/cycle - 26486.22 MiB/sec @ 3 ghz
Average - 9.356 bytes/cycle - 26767.95 MiB/sec @ 3 ghz
Small key speed test - 1-byte keys - 18.80 cycles/hash
Small key speed test - 2-byte keys - 19.63 cycles/hash
Small key speed test - 3-byte keys - 25.01 cycles/hash
Small key speed test - 4-byte keys - 19.15 cycles/hash
Small key speed test - 5-byte keys - 24.92 cycles/hash
Small key speed test - 6-byte keys - 24.00 cycles/hash
Small key speed test - 7-byte keys - 30.76 cycles/hash
Small key speed test - 8-byte keys - 25.38 cycles/hash
Small key speed test - 9-byte keys - 34.20 cycles/hash
Small key speed test - 10-byte keys - 30.89 cycles/hash
Small key speed test - 11-byte keys - 36.45 cycles/hash
Small key speed test - 12-byte keys - 30.68 cycles/hash
Small key speed test - 13-byte keys - 36.88 cycles/hash
Small key speed test - 14-byte keys - 44.51 cycles/hash
Small key speed test - 15-byte keys - 42.52 cycles/hash
Small key speed test - 16-byte keys - 29.52 cycles/hash
Small key speed test - 17-byte keys - 35.43 cycles/hash
Small key speed test - 18-byte keys - 35.57 cycles/hash
Small key speed test - 19-byte keys - 42.90 cycles/hash
Small key speed test - 20-byte keys - 35.00 cycles/hash
Small key speed test - 21-byte keys - 41.88 cycles/hash
Small key speed test - 22-byte keys - 47.02 cycles/hash
Small key speed test - 23-byte keys - 47.26 cycles/hash
Small key speed test - 24-byte keys - 33.50 cycles/hash
Small key speed test - 25-byte keys - 39.33 cycles/hash
Small key speed test - 26-byte keys - 39.16 cycles/hash
Small key speed test - 27-byte keys - 46.94 cycles/hash
Small key speed test - 28-byte keys - 40.27 cycles/hash
Small key speed test - 29-byte keys - 45.88 cycles/hash
Small key speed test - 30-byte keys - 45.00 cycles/hash
Small key speed test - 31-byte keys - 51.64 cycles/hash
Average 35.487 cycles/hash