diff options
Diffstat (limited to 'flatcc/external/hash/cmetrohash64.c')
| -rw-r--r-- | flatcc/external/hash/cmetrohash64.c | 185 |
1 files changed, 185 insertions, 0 deletions
diff --git a/flatcc/external/hash/cmetrohash64.c b/flatcc/external/hash/cmetrohash64.c new file mode 100644 index 0000000..2923958 --- /dev/null +++ b/flatcc/external/hash/cmetrohash64.c @@ -0,0 +1,185 @@ +// metrohash64.cpp +// +// The MIT License (MIT) +// +// Copyright (c) 2015 J. Andrew Rogers +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to deal +// in the Software without restriction, including without limitation the rights +// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in all +// copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +// SOFTWARE. +// + +#include "cmetrohash.h" + + +void cmetrohash64_1(const uint8_t * key, uint64_t len, uint32_t seed, uint8_t * out) +{ + static const uint64_t k0 = 0xC83A91E1; + static const uint64_t k1 = 0x8648DBDB; + static const uint64_t k2 = 0x7BDEC03B; + static const uint64_t k3 = 0x2F5870A5; + + const uint8_t * ptr = key; + const uint8_t * const end = ptr + len; + + uint64_t hash = ((((uint64_t) seed) + k2) * k0) + len; + + if (len >= 32) + { + uint64_t v[4]; + v[0] = hash; + v[1] = hash; + v[2] = hash; + v[3] = hash; + + do + { + v[0] += cread_u64(ptr) * k0; ptr += 8; v[0] = crotate_right(v[0],29) + v[2]; + v[1] += cread_u64(ptr) * k1; ptr += 8; v[1] = crotate_right(v[1],29) + v[3]; + v[2] += cread_u64(ptr) * k2; ptr += 8; v[2] = crotate_right(v[2],29) + v[0]; + v[3] += cread_u64(ptr) * k3; ptr += 8; v[3] = crotate_right(v[3],29) + v[1]; + } + while (ptr <= (end - 32)); + + v[2] ^= crotate_right(((v[0] + v[3]) * k0) + v[1], 33) * k1; + v[3] ^= crotate_right(((v[1] + v[2]) * k1) + v[0], 33) * k0; + v[0] ^= crotate_right(((v[0] + v[2]) * k0) + v[3], 33) * k1; + v[1] ^= crotate_right(((v[1] + v[3]) * k1) + v[2], 33) * k0; + hash += v[0] ^ v[1]; + } + + if ((end - ptr) >= 16) + { + uint64_t v0, v1; + v0 = hash + (cread_u64(ptr) * k0); ptr += 8; v0 = crotate_right(v0,33) * k1; + v1 = hash + (cread_u64(ptr) * k1); ptr += 8; v1 = crotate_right(v1,33) * k2; + v0 ^= crotate_right(v0 * k0, 35) + v1; + v1 ^= crotate_right(v1 * k3, 35) + v0; + hash += v1; + } + + if ((end - ptr) >= 8) + { + hash += cread_u64(ptr) * k3; ptr += 8; + hash ^= crotate_right(hash, 33) * k1; + + } + + if ((end - ptr) >= 4) + { + hash += cread_u32(ptr) * k3; ptr += 4; + hash ^= crotate_right(hash, 15) * k1; + } + + if ((end - ptr) >= 2) + { + hash += cread_u16(ptr) * k3; ptr += 2; + hash ^= crotate_right(hash, 13) * k1; + } + + if ((end - ptr) >= 1) + { + hash += cread_u8 (ptr) * k3; + hash ^= crotate_right(hash, 25) * k1; + } + + hash ^= crotate_right(hash, 33); + hash *= k0; + hash ^= crotate_right(hash, 33); + + memcpy(out, &hash, 8); +} + + +void cmetrohash64_2(const uint8_t * key, uint64_t len, uint32_t seed, uint8_t * out) +{ + static const uint64_t k0 = 0xD6D018F5; + static const uint64_t k1 = 0xA2AA033B; + static const uint64_t k2 = 0x62992FC1; + static const uint64_t k3 = 0x30BC5B29; + + const uint8_t * ptr = key; + const uint8_t * const end = ptr + len; + + uint64_t hash = ((((uint64_t) seed) + k2) * k0) + len; + + if (len >= 32) + { + uint64_t v[4]; + v[0] = hash; + v[1] = hash; + v[2] = hash; + v[3] = hash; + + do + { + v[0] += cread_u64(ptr) * k0; ptr += 8; v[0] = crotate_right(v[0],29) + v[2]; + v[1] += cread_u64(ptr) * k1; ptr += 8; v[1] = crotate_right(v[1],29) + v[3]; + v[2] += cread_u64(ptr) * k2; ptr += 8; v[2] = crotate_right(v[2],29) + v[0]; + v[3] += cread_u64(ptr) * k3; ptr += 8; v[3] = crotate_right(v[3],29) + v[1]; + } + while (ptr <= (end - 32)); + + v[2] ^= crotate_right(((v[0] + v[3]) * k0) + v[1], 30) * k1; + v[3] ^= crotate_right(((v[1] + v[2]) * k1) + v[0], 30) * k0; + v[0] ^= crotate_right(((v[0] + v[2]) * k0) + v[3], 30) * k1; + v[1] ^= crotate_right(((v[1] + v[3]) * k1) + v[2], 30) * k0; + hash += v[0] ^ v[1]; + } + + if ((end - ptr) >= 16) + { + uint64_t v0, v1; + v0 = hash + (cread_u64(ptr) * k2); ptr += 8; v0 = crotate_right(v0,29) * k3; + v1 = hash + (cread_u64(ptr) * k2); ptr += 8; v1 = crotate_right(v1,29) * k3; + v0 ^= crotate_right(v0 * k0, 34) + v1; + v1 ^= crotate_right(v1 * k3, 34) + v0; + hash += v1; + } + + if ((end - ptr) >= 8) + { + hash += cread_u64(ptr) * k3; ptr += 8; + hash ^= crotate_right(hash, 36) * k1; + } + + if ((end - ptr) >= 4) + { + hash += cread_u32(ptr) * k3; ptr += 4; + hash ^= crotate_right(hash, 15) * k1; + } + + if ((end - ptr) >= 2) + { + hash += cread_u16(ptr) * k3; ptr += 2; + hash ^= crotate_right(hash, 15) * k1; + } + + if ((end - ptr) >= 1) + { + hash += cread_u8 (ptr) * k3; + hash ^= crotate_right(hash, 23) * k1; + } + + hash ^= crotate_right(hash, 28); + hash *= k0; + hash ^= crotate_right(hash, 29); + + memcpy(out, &hash, 8); +} + + |