1 module mecca.lib.hashing; 2 3 // Licensed under the Boost license. Full copyright information in the AUTHORS file 4 5 // 6 // adapted from https://github.com/gchatelet/murmurhash3_d/blob/8cb8ebe284a085abbd1d97eff8f3a3e78a95f995/murmurhash3.d 7 // can be used in CTFE 8 // 9 ulong[2] murmurHash3_128(const(ubyte)[] data, ulong seed1=0, ulong seed2=0) pure nothrow @safe @nogc { 10 alias Block = ulong[2]; 11 enum ulong c1 = 0x87c37b91114253d5; 12 enum ulong c2 = 0x4cf5ad432745937f; 13 ulong h1 = seed1; 14 ulong h2 = seed2; 15 ulong k1 = 0; 16 ulong k2 = 0; 17 ulong size = data.length; 18 19 static T rotl(T)(T x, uint y) pure nothrow @nogc @safe { 20 return ((x << y) | (x >> (T.sizeof * 8 - y))); 21 } 22 static T shuffle(T)(T k, T c1, T c2, ubyte r1) pure nothrow @nogc @safe { 23 k *= c1; 24 k = rotl(k, r1); 25 k *= c2; 26 return k; 27 } 28 static T update(T)(ref T h, T k, T mixWith, T c1, T c2, ubyte r1, ubyte r2, T n) pure nothrow @nogc @safe { 29 h ^= shuffle(k, c1, c2, r1); 30 h = rotl(h, r2); 31 h += mixWith; 32 return h * 5 + n; 33 } 34 static ulong fmix(ulong k) pure nothrow @nogc @safe { 35 k ^= k >> 33; 36 k *= 0xff51afd7ed558ccd; 37 k ^= k >> 33; 38 k *= 0xc4ceb9fe1a85ec53; 39 k ^= k >> 33; 40 return k; 41 } 42 43 // 16-byte blocks 44 auto blockAligned = data[0 .. ($ / Block.sizeof) * Block.sizeof]; 45 if (__ctfe) { 46 import std.range: chunks; 47 foreach(chunk; chunks(blockAligned, Block.sizeof)) { 48 ulong b0 = ulong(chunk[0]) | (ulong(chunk[1]) << 8) | (ulong(chunk[2]) << 16) | (ulong(chunk[3]) << 24) | (ulong(chunk[4]) << 32) | (ulong(chunk[5]) << 40) | (ulong(chunk[6]) << 48) | (ulong(chunk[7]) << 56); 49 ulong b1 = ulong(chunk[8]) | (ulong(chunk[9]) << 8) | (ulong(chunk[10]) << 16) | (ulong(chunk[11]) << 24) | (ulong(chunk[12]) << 32) | (ulong(chunk[13]) << 40) | (ulong(chunk[14]) << 48) | (ulong(chunk[15]) << 56); 50 h1 = update(h1, b0, h2, c1, c2, 31, 27, 0x52dce729U); 51 h2 = update(h2, b1, h1, c2, c1, 33, 31, 0x38495ab5U); 52 } 53 } 54 else { 55 foreach(b; cast(const(Block)[])blockAligned) { 56 h1 = update(h1, b[0], h2, c1, c2, 31, 27, 0x52dce729U); 57 h2 = update(h2, b[1], h1, c2, c1, 33, 31, 0x38495ab5U); 58 } 59 } 60 61 // remainder 62 auto remainder = data[blockAligned.length .. $]; 63 assert(remainder.length < Block.sizeof); 64 assert(remainder.length >= 0); 65 66 final switch (remainder.length) { 67 case 15: 68 k2 ^= ulong(remainder[14]) << 48; 69 goto case; 70 case 14: 71 k2 ^= ulong(remainder[13]) << 40; 72 goto case; 73 case 13: 74 k2 ^= ulong(remainder[12]) << 32; 75 goto case; 76 case 12: 77 k2 ^= ulong(remainder[11]) << 24; 78 goto case; 79 case 11: 80 k2 ^= ulong(remainder[10]) << 16; 81 goto case; 82 case 10: 83 k2 ^= ulong(remainder[9]) << 8; 84 goto case; 85 case 9: 86 k2 ^= ulong(remainder[8]) << 0; 87 h2 ^= shuffle(k2, c2, c1, 33); 88 goto case; 89 case 8: 90 k1 ^= ulong(remainder[7]) << 56; 91 goto case; 92 case 7: 93 k1 ^= ulong(remainder[6]) << 48; 94 goto case; 95 case 6: 96 k1 ^= ulong(remainder[5]) << 40; 97 goto case; 98 case 5: 99 k1 ^= ulong(remainder[4]) << 32; 100 goto case; 101 case 4: 102 k1 ^= ulong(remainder[3]) << 24; 103 goto case; 104 case 3: 105 k1 ^= ulong(remainder[2]) << 16; 106 goto case; 107 case 2: 108 k1 ^= ulong(remainder[1]) << 8; 109 goto case; 110 case 1: 111 k1 ^= ulong(remainder[0]) << 0; 112 h1 ^= shuffle(k1, c1, c2, 31); 113 goto case; 114 case 0: 115 } 116 117 // finalize 118 h1 ^= size; 119 h2 ^= size; 120 121 h1 += h2; 122 h2 += h1; 123 h1 = fmix(h1); 124 h2 = fmix(h2); 125 h1 += h2; 126 h2 += h1; 127 128 ulong[2] res = [h1, h2]; 129 return res; 130 } 131 132 ulong murmurHash3_64(const(ubyte)[] data) pure nothrow @safe @nogc { 133 return murmurHash3_128(data)[0]; 134 } 135 ulong murmurHash3_64(string data) pure nothrow @safe @nogc { 136 return murmurHash3_64(cast(const(ubyte)[])data); 137 } 138 139 ubyte[16] murmurHash3_128_ubytes(const(ubyte)[] data) pure nothrow @safe @nogc { 140 if (__ctfe) { 141 ulong[2] tmp = murmurHash3_128(data); 142 ubyte[16] res = [ 143 tmp[0] & 0xff, 144 (tmp[0] >> 8) & 0xff, 145 (tmp[0] >> 16) & 0xff, 146 (tmp[0] >> 24) & 0xff, 147 (tmp[0] >> 32) & 0xff, 148 (tmp[0] >> 40) & 0xff, 149 (tmp[0] >> 48) & 0xff, 150 (tmp[0] >> 56) & 0xff, 151 tmp[1] & 0xff, 152 (tmp[1] >> 8) & 0xff, 153 (tmp[1] >> 16) & 0xff, 154 (tmp[1] >> 24) & 0xff, 155 (tmp[1] >> 32) & 0xff, 156 (tmp[1] >> 40) & 0xff, 157 (tmp[1] >> 48) & 0xff, 158 (tmp[1] >> 56) & 0xff, 159 ]; 160 return res; 161 } 162 else { 163 return cast(ubyte[16])murmurHash3_128(data); 164 } 165 } 166 ubyte[16] murmurHash3_128_ubytes(string data) pure nothrow @safe @nogc { 167 return murmurHash3_128_ubytes(cast(const(ubyte)[])data); 168 } 169 170 unittest { 171 import std.conv: hexString; 172 static assert (murmurHash3_128_ubytes("abcdefghijklmnopqrstuvwxyz") == 173 cast(ubyte[])hexString!"A94A6F517E9D9C7429D5A7B6899CADE9"); 174 175 foreach(inp, outp; ["" : hexString!"00000000000000000000000000000000", 176 "a" : hexString!"897859F6655555855A890E51483AB5E6", 177 "ab" : hexString!"2E1BED16EA118B93ADD4529B01A75EE6", 178 "abc" : hexString!"6778AD3F3F3F96B4522DCA264174A23B", 179 "abcd" : hexString!"4FCD5646D6B77BB875E87360883E00F2", 180 "abcde" : hexString!"B8BB96F491D036208CECCF4BA0EEC7C5", 181 "abcdef" : hexString!"55BFA3ACBF867DE45C842133990971B0", 182 "abcdefg" : hexString!"99E49EC09F2FCDA6B6BB55B13AA23A1C", 183 "abcdefgh" : hexString!"028CEF37B00A8ACCA14069EB600D8948", 184 "abcdefghi" : hexString!"64793CF1CFC0470533E041B7F53DB579", 185 "abcdefghij" : hexString!"998C2F770D5BC1B6C91A658CDC854DA2", 186 "abcdefghijk" : hexString!"029D78DFB8D095A871E75A45E2317CBB", 187 "abcdefghijkl" : hexString!"94E17AE6B19BF38E1C62FF7232309E1F", 188 "abcdefghijklm" : hexString!"73FAC0A78D2848167FCCE70DFF7B652E", 189 "abcdefghijklmn" : hexString!"E075C3F5A794D09124336AD2276009EE", 190 "abcdefghijklmno" : hexString!"FB2F0C895124BE8A612A969C2D8C546A", 191 "abcdefghijklmnop" : hexString!"23B74C22A33CCAC41AEB31B395D63343", 192 "abcdefghijklmnopq" : hexString!"57A6BD887F746475E40D11A19D49DAEC", 193 "abcdefghijklmnopqr" : hexString!"508A7F90EC8CF0776BC7005A29A8D471", 194 "abcdefghijklmnopqrs" : hexString!"886D9EDE23BC901574946FB62A4D8AA6", 195 "abcdefghijklmnopqrst" : hexString!"F1E237F926370B314BD016572AF40996", 196 "abcdefghijklmnopqrstu" : hexString!"3CC9FF79E268D5C9FB3C9BE9C148CCD7", 197 "abcdefghijklmnopqrstuv" : hexString!"56F8ABF430E388956DA9F4A8741FDB46", 198 "abcdefghijklmnopqrstuvw" : hexString!"8E234F9DBA0A4840FFE9541CEBB7BE83", 199 "abcdefghijklmnopqrstuvwx" : hexString!"F72CDED40F96946408F22153A3CF0F79", 200 "abcdefghijklmnopqrstuvwxy" : hexString!"0F96072FA4CBE771DBBD9E398115EEED", 201 "abcdefghijklmnopqrstuvwxyz" : hexString!"A94A6F517E9D9C7429D5A7B6899CADE9"]) { 202 assert(murmurHash3_128_ubytes(inp) == cast(ubyte[])outp, inp); 203 } 204 } 205 206