cmetrohash64.c (5788B)
1 // metrohash64.cpp 2 // 3 // The MIT License (MIT) 4 // 5 // Copyright (c) 2015 J. Andrew Rogers 6 // 7 // Permission is hereby granted, free of charge, to any person obtaining a copy 8 // of this software and associated documentation files (the "Software"), to deal 9 // in the Software without restriction, including without limitation the rights 10 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 11 // copies of the Software, and to permit persons to whom the Software is 12 // furnished to do so, subject to the following conditions: 13 // 14 // The above copyright notice and this permission notice shall be included in all 15 // copies or substantial portions of the Software. 16 // 17 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 18 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 19 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 20 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 21 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 22 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 23 // SOFTWARE. 24 // 25 26 #include "cmetrohash.h" 27 28 29 void cmetrohash64_1(const uint8_t * key, uint64_t len, uint32_t seed, uint8_t * out) 30 { 31 static const uint64_t k0 = 0xC83A91E1; 32 static const uint64_t k1 = 0x8648DBDB; 33 static const uint64_t k2 = 0x7BDEC03B; 34 static const uint64_t k3 = 0x2F5870A5; 35 36 const uint8_t * ptr = key; 37 const uint8_t * const end = ptr + len; 38 39 uint64_t hash = ((((uint64_t) seed) + k2) * k0) + len; 40 41 if (len >= 32) 42 { 43 uint64_t v[4]; 44 v[0] = hash; 45 v[1] = hash; 46 v[2] = hash; 47 v[3] = hash; 48 49 do 50 { 51 v[0] += cread_u64(ptr) * k0; ptr += 8; v[0] = crotate_right(v[0],29) + v[2]; 52 v[1] += cread_u64(ptr) * k1; ptr += 8; v[1] = crotate_right(v[1],29) + v[3]; 53 v[2] += cread_u64(ptr) * k2; ptr += 8; v[2] = crotate_right(v[2],29) + v[0]; 54 v[3] += cread_u64(ptr) * k3; ptr += 8; v[3] = crotate_right(v[3],29) + v[1]; 55 } 56 while (ptr <= (end - 32)); 57 58 v[2] ^= crotate_right(((v[0] + v[3]) * k0) + v[1], 33) * k1; 59 v[3] ^= crotate_right(((v[1] + v[2]) * k1) + v[0], 33) * k0; 60 v[0] ^= crotate_right(((v[0] + v[2]) * k0) + v[3], 33) * k1; 61 v[1] ^= crotate_right(((v[1] + v[3]) * k1) + v[2], 33) * k0; 62 hash += v[0] ^ v[1]; 63 } 64 65 if ((end - ptr) >= 16) 66 { 67 uint64_t v0, v1; 68 v0 = hash + (cread_u64(ptr) * k0); ptr += 8; v0 = crotate_right(v0,33) * k1; 69 v1 = hash + (cread_u64(ptr) * k1); ptr += 8; v1 = crotate_right(v1,33) * k2; 70 v0 ^= crotate_right(v0 * k0, 35) + v1; 71 v1 ^= crotate_right(v1 * k3, 35) + v0; 72 hash += v1; 73 } 74 75 if ((end - ptr) >= 8) 76 { 77 hash += cread_u64(ptr) * k3; ptr += 8; 78 hash ^= crotate_right(hash, 33) * k1; 79 80 } 81 82 if ((end - ptr) >= 4) 83 { 84 hash += cread_u32(ptr) * k3; ptr += 4; 85 hash ^= crotate_right(hash, 15) * k1; 86 } 87 88 if ((end - ptr) >= 2) 89 { 90 hash += cread_u16(ptr) * k3; ptr += 2; 91 hash ^= crotate_right(hash, 13) * k1; 92 } 93 94 if ((end - ptr) >= 1) 95 { 96 hash += cread_u8 (ptr) * k3; 97 hash ^= crotate_right(hash, 25) * k1; 98 } 99 100 hash ^= crotate_right(hash, 33); 101 hash *= k0; 102 hash ^= crotate_right(hash, 33); 103 104 memcpy(out, &hash, 8); 105 } 106 107 108 void cmetrohash64_2(const uint8_t * key, uint64_t len, uint32_t seed, uint8_t * out) 109 { 110 static const uint64_t k0 = 0xD6D018F5; 111 static const uint64_t k1 = 0xA2AA033B; 112 static const uint64_t k2 = 0x62992FC1; 113 static const uint64_t k3 = 0x30BC5B29; 114 115 const uint8_t * ptr = key; 116 const uint8_t * const end = ptr + len; 117 118 uint64_t hash = ((((uint64_t) seed) + k2) * k0) + len; 119 120 if (len >= 32) 121 { 122 uint64_t v[4]; 123 v[0] = hash; 124 v[1] = hash; 125 v[2] = hash; 126 v[3] = hash; 127 128 do 129 { 130 v[0] += cread_u64(ptr) * k0; ptr += 8; v[0] = crotate_right(v[0],29) + v[2]; 131 v[1] += cread_u64(ptr) * k1; ptr += 8; v[1] = crotate_right(v[1],29) + v[3]; 132 v[2] += cread_u64(ptr) * k2; ptr += 8; v[2] = crotate_right(v[2],29) + v[0]; 133 v[3] += cread_u64(ptr) * k3; ptr += 8; v[3] = crotate_right(v[3],29) + v[1]; 134 } 135 while (ptr <= (end - 32)); 136 137 v[2] ^= crotate_right(((v[0] + v[3]) * k0) + v[1], 30) * k1; 138 v[3] ^= crotate_right(((v[1] + v[2]) * k1) + v[0], 30) * k0; 139 v[0] ^= crotate_right(((v[0] + v[2]) * k0) + v[3], 30) * k1; 140 v[1] ^= crotate_right(((v[1] + v[3]) * k1) + v[2], 30) * k0; 141 hash += v[0] ^ v[1]; 142 } 143 144 if ((end - ptr) >= 16) 145 { 146 uint64_t v0, v1; 147 v0 = hash + (cread_u64(ptr) * k2); ptr += 8; v0 = crotate_right(v0,29) * k3; 148 v1 = hash + (cread_u64(ptr) * k2); ptr += 8; v1 = crotate_right(v1,29) * k3; 149 v0 ^= crotate_right(v0 * k0, 34) + v1; 150 v1 ^= crotate_right(v1 * k3, 34) + v0; 151 hash += v1; 152 } 153 154 if ((end - ptr) >= 8) 155 { 156 hash += cread_u64(ptr) * k3; ptr += 8; 157 hash ^= crotate_right(hash, 36) * k1; 158 } 159 160 if ((end - ptr) >= 4) 161 { 162 hash += cread_u32(ptr) * k3; ptr += 4; 163 hash ^= crotate_right(hash, 15) * k1; 164 } 165 166 if ((end - ptr) >= 2) 167 { 168 hash += cread_u16(ptr) * k3; ptr += 2; 169 hash ^= crotate_right(hash, 15) * k1; 170 } 171 172 if ((end - ptr) >= 1) 173 { 174 hash += cread_u8 (ptr) * k3; 175 hash ^= crotate_right(hash, 23) * k1; 176 } 177 178 hash ^= crotate_right(hash, 28); 179 hash *= k0; 180 hash ^= crotate_right(hash, 29); 181 182 memcpy(out, &hash, 8); 183 } 184 185