1 /** Hash digestion of standard types. 2 * 3 * TODO: use: 4 * 5 * static if (__traits(hasMember,hasher, "putStaticArray")) 6 * digest.putStaticArray((cast(ubyte*)&value)[0 .. value.sizeof]); 7 * else 8 * digest.put((cast(ubyte*)&value)[0 .. value.sizeof]); 9 */ 10 module nxt.digestion; 11 12 import std.traits : isScalarType, hasIndirections, isArray, isPointer; 13 import std.digest : isDigest; 14 import nxt.container.traits : isAddress; 15 16 @safe: 17 18 /// ditto 19 hash_t hashOf2(alias hasher, T)(const scope auto ref T value) 20 { 21 version(LDC) pragma(inline, true); 22 static if (__traits(compiles, { enum _ = isDigest!hasher; }) && 23 isDigest!hasher) 24 { 25 import std.digest : makeDigest; 26 27 auto digest = makeDigest!(hasher); 28 static if (__traits(hasMember, T, "toDigest")) 29 value.toDigest(digest); 30 else 31 digestAny(digest, value); 32 33 static if (__traits(hasMember, hasher, "get")) 34 { 35 digest.finish(); 36 auto result = digest.get(); 37 } 38 else 39 auto result = digest.finish(); 40 41 static if (is(typeof(result) == typeof(return))) 42 return result; 43 else static if (is(typeof(result) == ubyte[4])) 44 { 45 static hash_t fix(in ubyte[4] x) @trusted => *cast(uint*)(&x); 46 return fix(result); 47 } 48 else static if (is(typeof(result) == ubyte[8])) 49 { 50 static hash_t fix(in ubyte[8] x) @trusted => *cast(typeof(return)*)(&x); 51 return fix(result); 52 } 53 else static if (is(typeof(result) == typeof(return)[2])) 54 return (result[0] ^ result[1]); 55 else 56 static assert(0, "Handle get() with return type " ~ typeof(result).stringof ~ 57 " on " ~ size_t.sizeof.stringof ~ "-bit platform"); 58 } 59 else static if (__traits(compiles, { auto _ = hasher((ubyte[]).init); })) 60 { 61 // cast input `value` to `ubyte[]` and use std.digest API 62 immutable digest = hasher((cast(ubyte*)&value)[0 .. value.sizeof]); // TODO: ask forums when this isn't correct 63 64 static assert(digest.sizeof >= 65 typeof(return).sizeof, 66 `Size of digest is ` ~ digest.sizeof 67 ~ ` but needs to be at least ` ~ typeof(return).sizeof.stringof); 68 69 import std.traits : isUnsigned, isStaticArray; 70 71 static if (isUnsigned!(typeof(digest))) 72 return cast(typeof(return))digest; // fast modulo calculation 73 else static if (isStaticArray!(typeof(digest))) 74 { 75 typeof(return) hashIndex; 76 static if (2*hash_t.sizeof == digest.sizeof) 77 // for instance, use all 128-bits when hash_t is 64-bit 78 (cast(ubyte*)&hashIndex)[0 .. hashIndex.sizeof] = (digest[0 .. hashIndex.sizeof] ^ 79 digest[hashIndex.sizeof .. 2*hashIndex.sizeof]); 80 else 81 (cast(ubyte*)&hashIndex)[0 .. hashIndex.sizeof] = digest[0 .. hashIndex.sizeof]; 82 return hashIndex; 83 } 84 else 85 static assert(0, "Unsupported digest type " ~ typeof(digest).stringof); 86 } 87 else 88 static assert(0, "Cannot combine hasher " ~ hasher.stringof ~ 89 " with element type " ~ T.stringof); 90 } 91 92 /** Digest `value` into `digest`. 93 */ 94 void digestAny(Digest, T)(ref Digest digest, 95 const scope auto ref T value) 96 if (isDigest!Digest) 97 { 98 version(LDC) pragma(inline, true); 99 static if (isScalarType!T) // first because faster to evaluate than 100 // `!hasIndirections!T` below 101 digestRaw(digest, value); 102 else static if (__traits(hasMember, T, "toDigest")) 103 value.toDigest(digest); 104 else static if (isAddress!T) 105 digestAddress(digest, value); 106 else static if (!hasIndirections!T) // no pointers left in `T`. TODO: make this the default in-place of `isScalarType` 107 { 108 version(LDC) // LDC doesn't zero pad `real`s 109 { 110 // TODO: needed to improve this with a trait 111 import std.traits : isStaticArray, isInstanceOf; 112 static if (isStaticArray!T) 113 { 114 import std.meta : staticIndexOf; 115 enum isReal = is(typeof(T.init[0]) == real); 116 static if (isReal) // static array of `real`s 117 foreach (e; value) 118 digestRaw(digest, e); // hash each element for now because padding might now be zero 119 else 120 digestRaw(digest, value); // hash everything in one call for better speed 121 } 122 else 123 { 124 import std.typecons : Nullable; 125 static if (isInstanceOf!(Nullable, T)) 126 digestRaw(digest, value); // hash everything in one call for better speed 127 else 128 { 129 import std.meta : staticIndexOf; 130 enum realIndex = staticIndexOf!(real, typeof(T.init.tupleof)); 131 static if (realIndex != -1) 132 digestStruct(digest, value); // hash each element for now because padding might now be zero 133 else 134 digestRaw(digest, value); // hash everything in one call for better speed 135 } 136 } 137 } 138 else 139 digestRaw(digest, value); // hash everything in one call for better speed 140 } 141 else static if (isArray!T) // including `T` being `string`, `wstring`, `dstring` 142 digestArray(digest, value); 143 else static if (is(T == struct)) 144 { 145 static if (is(typeof(T.init[])) && isArray!(typeof(T.init[]))) // TODO: trait: `isArrayLike` 146 digestAnyWithTrustedSystemSlicing(digest, value); 147 else 148 digestStruct(digest, value); 149 } 150 else 151 static assert(0, "handle type " ~ T.stringof); 152 } 153 154 // TODO: remove when `SSOString` gets scope-checked opSlice 155 private 156 void digestAnyWithTrustedSystemSlicing(Digest, T)(ref Digest digest, 157 const scope ref T value) @trusted 158 { 159 digestArray(digest, value[]); 160 } 161 162 /** Digest the `value` as an address (pointer). */ 163 private void digestAddress(Digest, T)(scope ref Digest digest, 164 const scope T value) @trusted // pointer passed by value 165 if (isDigest!Digest && 166 isAddress!T) 167 { 168 static if (is(T == class)) 169 { 170 static if (size_t.sizeof == 8) 171 enum bitshift = 3; // 64-bit platform 172 else 173 enum bitshift = 2; // 32-bit platform 174 } 175 else static if (isPointer!T) 176 { 177 enum Tvalue = typeof(*T.init); 178 enum Talignment = T.value.alignof; 179 static if (Talignment == 16) 180 enum bitshift = 4; 181 else static if (Talignment == 8) 182 enum bitshift = 3; 183 else static if (Talignment == 4) 184 enum bitshift = 2; 185 else static if (Talignment == 2) 186 enum bitshift = 1; 187 else static if (Talignment == 1) 188 enum bitshift = 0; 189 else 190 static assert(0, "Cannot calculate alignment of T being " ~ T.stringof); 191 } 192 const valueAsSize = *cast(size_t*)(&value); // `value` as pointer 193 assert((valueAsSize & (bitshift - 1)) == 0); // shifted out bits should all be zero 194 digestRaw(digest, valueAsSize >> bitshift); 195 } 196 197 /** Digest the struct `value` by digesting each member sequentially. */ 198 private void digestStruct(Digest, T)(scope ref Digest digest, 199 const scope auto ref T value) @trusted 200 if (isDigest!Digest && 201 is(T == struct)) 202 { 203 static if (!hasIndirections!T) 204 { 205 version(D_Coverage) {} else pragma(inline, true); 206 digestRaw(digest, value); // hash everything in one call for better speed 207 } 208 else 209 { 210 version(LDC) pragma(inline, true); 211 foreach (const ref subValue; value.tupleof) // for each member 212 digestAny(digest, subValue); 213 } 214 } 215 216 /** Digest the array `value`. */ 217 void digestArray(Digest, T)(scope ref Digest digest, 218 const scope auto ref T value) @trusted 219 if (isDigest!Digest && 220 isArray!T) 221 { 222 import std.traits : isDynamicArray; 223 static if (isDynamicArray!T) 224 // only dynamic arrays vary in length for a specific type `T` being hashed 225 digestRaw(digest, value.length); // length 226 227 alias E = typeof(T.init[0]); 228 static if (isScalarType!E || 229 isPointer!E || 230 (is(T == class) && 231 !__traits(hasMember, T, "toDigest"))) 232 { 233 version(D_Coverage) {} else pragma(inline, true); 234 digest.put((cast(ubyte*)value.ptr)[0 .. value.length * value[0].sizeof]); // faster 235 } 236 else 237 foreach (const ref element; value) 238 digestAny(digest, element); // slower 239 } 240 241 /** Digest raw bytes of `values`. 242 */ 243 private void digestRaw(Digest, T)(scope ref Digest digest, 244 const scope T value) @trusted // pass scalar types by value 245 if (isDigest!Digest && 246 isScalarType!T) // scalar type `T` 247 { 248 version(LDC) pragma(inline, true); 249 // TODO: optimize when value is size_t, ulong and digest supports it 250 digest.put((cast(ubyte*)&value)[0 .. value.sizeof]); 251 } 252 253 private void digestRaw(Digest, T)(scope ref Digest digest, 254 const scope auto ref T value) @trusted // pass non-scalar types by ref when possible 255 if (isDigest!Digest && 256 !isScalarType!T) // non-scalar type `T` 257 { 258 version(LDC) pragma(inline, true); 259 // TODO: optimize when value is size_t, ulong and digest supports it 260 digest.put((cast(ubyte*)&value)[0 .. value.sizeof]); 261 } 262 263 /// arrays and containers and its slices 264 @safe pure unittest 265 { 266 import nxt.container.dynamic_array : DynamicArray; 267 268 alias E = double; 269 270 immutable e = [cast(E)1, cast(E)2, cast(E)3].s; 271 auto a = DynamicArray!E.withElements(e.s); 272 273 // static array and its slice (dynamic array) hash differently 274 const sh = hashOf2!(FNV64)(e); /* does not need to include length in hash 275 * because all instances of typeof(e) have 276 * the same length */ 277 const dh = hashOf2!(FNV64)(e[]); // includes hash in length 278 assert(sh != dh); 279 280 // array container and its slice should hash equal 281 assert(hashOf2!(FNV64)(a) == 282 hashOf2!(FNV64)(e[])); 283 } 284 285 @trusted pure unittest 286 { 287 const ubyte[8] bytes8 = [1, 2, 3, 4, 5, 6, 7, 8]; 288 assert(hashOf2!(FNV64)(bytes8) == 9130222009665091821UL); 289 290 enum E { first, second, third } 291 292 assert(hashOf2!(FNV64)(E.first) == 293 hashOf2!(FNV64)(E.first)); 294 assert(hashOf2!(FNV64)(E.second) == 295 hashOf2!(FNV64)(E.second)); 296 assert(hashOf2!(FNV64)(E.third) == 297 hashOf2!(FNV64)(E.third)); 298 assert(hashOf2!(FNV64)(E.first) != 299 hashOf2!(FNV64)(E.second)); 300 assert(hashOf2!(FNV64)(E.second) != 301 hashOf2!(FNV64)(E.third)); 302 303 struct V 304 { 305 float f = 3; 306 double d = 5; 307 real r = 7; 308 E e; 309 } 310 311 struct S 312 { 313 string str = `abc`; 314 wstring wstr = `XYZ`; 315 dstring dstr = `123`; 316 size_t sz = 17; 317 ushort us = 18; 318 ubyte ub = 255; 319 V v; 320 } 321 322 // check determinism 323 assert(hashOf2!(FNV64)("alpha") == 324 hashOf2!(FNV64)("alpha".dup)); 325 326 assert(hashOf2!(FNV64)(S()) == 327 hashOf2!(FNV64)(S())); 328 329 struct HasDigest 330 { 331 E e; 332 void toDigest(Digest)(scope ref Digest digest) const 333 pure nothrow @nogc 334 if (isDigest!Digest) 335 { 336 digestRaw(digest, e); 337 } 338 } 339 340 assert(hashOf2!(FNV64)(HasDigest(E.first)) == 341 hashOf2!(FNV64)(HasDigest(E.first))); 342 343 assert(hashOf2!(FNV64)(HasDigest(E.first)) != 344 hashOf2!(FNV64)(HasDigest(E.second))); 345 } 346 347 version(unittest) 348 { 349 import nxt.digestx.fnv : FNV; 350 alias FNV64 = FNV!(64, true); 351 import nxt.dbgio; 352 import nxt.array_help : s; 353 }