1 /******************************************************************************* 2 3 Hash calculator used in Map and Set, uses FNV1a to hash primitive values and 4 dynamic or static arrays of such. 5 6 Copyright: 7 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 8 All rights reserved. 9 10 License: 11 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 12 Alternatively, this file may be distributed under the terms of the Tango 13 3-Clause BSD License (see LICENSE_BSD.txt for details). 14 15 *******************************************************************************/ 16 17 module ocean.util.container.map.model.StandardHash; 18 19 import ocean.meta.types.Qualifiers; 20 21 struct StandardHash 22 { 23 static: 24 25 /************************************************************************** 26 27 Evaluates to true if T is a primitive value type; that is, a numeric 28 (integer, floating point, complex) or character type. 29 30 **************************************************************************/ 31 32 template IsPrimitiveValueType ( T ) 33 { 34 enum IsPrimitiveValueType = is (T : real) || is (T : creal) || is (T : dchar); 35 } 36 37 /************************************************************************** 38 39 Calculates the hash value from key. 40 41 - If K is a primitive type (integer, floating point, character), the 42 hash value is calculated from the raw key data using the FNV1a hash 43 function. 44 - If K is a dynamic or static array of a primitive type, the hash value 45 is calculated from the raw data of the key array content using the 46 FNV1a hash function. 47 - If K is a class, interface, struct or union, it is expected to 48 implement toHash(), which will be used. 49 - Other key types (arrays of non-primitive types, classes/interfaces/ 50 structs/unions which do not implement toHash(), pointers, function 51 references, delegates, associative arrays) are not supported. 52 53 Params: 54 key = key to hash 55 56 Returns: 57 the hash value that corresponds to key. 58 59 **************************************************************************/ 60 61 hash_t toHash ( K ) ( in K key ) 62 { 63 static if (StandardHash.IsPrimitiveValueType!(K)) 64 { 65 return StandardHash.fnv1aT(key); 66 } 67 else static if (is (K E : E[])) 68 { 69 static assert (StandardHash.IsPrimitiveValueType!(E), 70 "only arrays of primitive value types supported, " 71 ~ "not '" ~ K.stringof ~ '\''); 72 73 return StandardHash.fnv1a(key); 74 } 75 else 76 { 77 static assert (is (K == class) || is (K == interface) 78 || is (K == struct) || is (K == union), 79 "only primitive value types, arrays of such and " 80 ~ "classes/interfaces/structs/unions implementing " 81 ~ "toHash() supported, not '" ~ K.stringof ~ '\''); 82 83 // HACK: we don't want to start implementing all our class `toHash` 84 // methods as `const` yet, have to cast to silence druntime 85 static if (is(K == class) || is(K == interface)) 86 return (cast(Unqual!(K)) key).toHash(); 87 else 88 return key.toHash(); 89 } 90 } 91 92 93 /************************************************************************** 94 95 FNV1 magic constants. 96 97 **************************************************************************/ 98 99 static if (is (hash_t == uint)) 100 { 101 enum hash_t fnv1a_prime = 0x0100_0193, // 32 bit fnv1a prime 102 fnv1a_init = 0x811C_9DC5; // 32 bit initial digest 103 } 104 else 105 { 106 static assert (is (hash_t == ulong)); 107 108 enum hash_t fnv1a_prime = 0x0000_0100_0000_01B3, // 64 bit fnv1a prime 109 fnv1a_init = 0xCBF2_9CE4_8422_2325; // 64 bit initial digest 110 } 111 112 /************************************************************************** 113 114 Calculates the FNV1a hash value from data. 115 116 Params: 117 data = input data 118 hash = optional input hash 119 120 Returns: 121 the FNV1a hash value calculated from data. 122 123 **************************************************************************/ 124 125 hash_t fnv1a ( in void[] data, hash_t hash = fnv1a_init ) 126 { 127 foreach (d; cast (ubyte[]) data) 128 { 129 hash = (hash ^ d) * StandardHash.fnv1a_prime; 130 } 131 132 return hash; 133 } 134 135 /************************************************************************** 136 137 Calculates the FNV1a hash value from the raw data of x using an unrolled 138 loop to improve efficiency. 139 140 Note that, if T is a reference type, the hash value will be calculated 141 from the reference, not the referenced value. 142 143 Params: 144 x = input value 145 hash = optional input hash 146 147 Returns: 148 the FNV1a hash value calculated from the raw data of x. 149 150 **************************************************************************/ 151 152 hash_t fnv1aT ( T ) ( T x, hash_t hash = fnv1a_init ) 153 { 154 mixin (fnv1aCode!(hash.stringof, x.stringof, x.sizeof)); 155 156 return hash; 157 } 158 159 /************************************************************************** 160 161 Evaluates to D code that implements the calculation of FNV1a of a 162 variable named var with n bytes of size, storing the result in a 163 variable named hashvar. The initial value of hashvar should be 164 fnv1a_init or a previously calculated FNV1a hash. 165 166 Example: Let x be an int variable to calculate the hash value from and 167 result be the result variable: 168 --- 169 int x; 170 171 hash_t result = fnv1a_init; 172 --- 173 174 Then 175 176 --- 177 fnv1aCode!("result", x.stringof, x.sizeof) 178 --- 179 180 , where x.sizeof is 4, evaluates to 181 182 --- 183 auto __x = cast(ubyte*)&x; 184 185 result = (result ^ __x[0LU]) * 1099511628211LU; 186 result = (result ^ __x[1LU]) * 1099511628211LU; 187 result = (result ^ __x[2LU]) * 1099511628211LU; 188 result = (result ^ __x[3LU]) * 1099511628211LU; 189 --- 190 191 **************************************************************************/ 192 193 template fnv1aCode ( istring hashvar, istring var, size_t n ) 194 { 195 static if (n) 196 { 197 enum istring fnv1aCode = fnv1aCode!(hashvar, var, n - 1) ~ hashvar ~ "=(" ~ 198 hashvar ~ "^__" ~ var ~ "[" ~ 199 minus1!(n).stringof ~ "])*" ~ 200 fnv1a_prime.stringof ~ ";\n"; 201 } 202 else 203 { 204 enum istring fnv1aCode = "auto __" ~ var ~ 205 "=cast(" ~ ubyte.stringof ~ "*)&" ~ var ~ 206 ";\n"; 207 } 208 } 209 210 211 /************************************************************************** 212 213 Evaluates to n - 1. 214 215 **************************************************************************/ 216 217 template minus1 ( size_t n ) 218 { 219 enum size_t minus1 = n - 1; 220 } 221 }