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