1 // Copyright 2014 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package runtime 6 7 import "unsafe" 8 9 const ( 10 c0 = uintptr((8-ptrSize)/4*2860486313 + (ptrSize-4)/4*33054211828000289) 11 c1 = uintptr((8-ptrSize)/4*3267000013 + (ptrSize-4)/4*23344194077549503) 12 ) 13 14 // type algorithms - known to compiler 15 const ( 16 alg_MEM = iota 17 alg_MEM0 18 alg_MEM8 19 alg_MEM16 20 alg_MEM32 21 alg_MEM64 22 alg_MEM128 23 alg_NOEQ 24 alg_NOEQ0 25 alg_NOEQ8 26 alg_NOEQ16 27 alg_NOEQ32 28 alg_NOEQ64 29 alg_NOEQ128 30 alg_STRING 31 alg_INTER 32 alg_NILINTER 33 alg_SLICE 34 alg_FLOAT32 35 alg_FLOAT64 36 alg_CPLX64 37 alg_CPLX128 38 alg_max 39 ) 40 41 // typeAlg is also copied/used in reflect/type.go. 42 // keep them in sync. 43 type typeAlg struct { 44 // function for hashing objects of this type 45 // (ptr to object, seed) -> hash 46 hash func(unsafe.Pointer, uintptr) uintptr 47 // function for comparing objects of this type 48 // (ptr to object A, ptr to object B) -> ==? 49 equal func(unsafe.Pointer, unsafe.Pointer) bool 50 } 51 52 func memhash0(p unsafe.Pointer, h uintptr) uintptr { 53 return h 54 } 55 func memhash8(p unsafe.Pointer, h uintptr) uintptr { 56 return memhash(p, h, 1) 57 } 58 func memhash16(p unsafe.Pointer, h uintptr) uintptr { 59 return memhash(p, h, 2) 60 } 61 func memhash32(p unsafe.Pointer, h uintptr) uintptr { 62 return memhash(p, h, 4) 63 } 64 func memhash64(p unsafe.Pointer, h uintptr) uintptr { 65 return memhash(p, h, 8) 66 } 67 func memhash128(p unsafe.Pointer, h uintptr) uintptr { 68 return memhash(p, h, 16) 69 } 70 71 // memhash_varlen is defined in assembly because it needs access 72 // to the closure. It appears here to provide an argument 73 // signature for the assembly routine. 74 func memhash_varlen(p unsafe.Pointer, h uintptr) uintptr 75 76 var algarray = [alg_max]typeAlg{ 77 alg_MEM: {nil, nil}, // not used 78 alg_MEM0: {memhash0, memequal0}, 79 alg_MEM8: {memhash8, memequal8}, 80 alg_MEM16: {memhash16, memequal16}, 81 alg_MEM32: {memhash32, memequal32}, 82 alg_MEM64: {memhash64, memequal64}, 83 alg_MEM128: {memhash128, memequal128}, 84 alg_NOEQ: {nil, nil}, 85 alg_NOEQ0: {nil, nil}, 86 alg_NOEQ8: {nil, nil}, 87 alg_NOEQ16: {nil, nil}, 88 alg_NOEQ32: {nil, nil}, 89 alg_NOEQ64: {nil, nil}, 90 alg_NOEQ128: {nil, nil}, 91 alg_STRING: {strhash, strequal}, 92 alg_INTER: {interhash, interequal}, 93 alg_NILINTER: {nilinterhash, nilinterequal}, 94 alg_SLICE: {nil, nil}, 95 alg_FLOAT32: {f32hash, f32equal}, 96 alg_FLOAT64: {f64hash, f64equal}, 97 alg_CPLX64: {c64hash, c64equal}, 98 alg_CPLX128: {c128hash, c128equal}, 99 } 100 101 var useAeshash bool 102 103 // in asm_*.s 104 func aeshash(p unsafe.Pointer, h, s uintptr) uintptr 105 func aeshash32(p unsafe.Pointer, h uintptr) uintptr 106 func aeshash64(p unsafe.Pointer, h uintptr) uintptr 107 func aeshashstr(p unsafe.Pointer, h uintptr) uintptr 108 109 func strhash(a unsafe.Pointer, h uintptr) uintptr { 110 x := (*stringStruct)(a) 111 return memhash(x.str, h, uintptr(x.len)) 112 } 113 114 // NOTE: Because NaN != NaN, a map can contain any 115 // number of (mostly useless) entries keyed with NaNs. 116 // To avoid long hash chains, we assign a random number 117 // as the hash value for a NaN. 118 119 func f32hash(p unsafe.Pointer, h uintptr) uintptr { 120 f := *(*float32)(p) 121 switch { 122 case f == 0: 123 return c1 * (c0 ^ h) // +0, -0 124 case f != f: 125 return c1 * (c0 ^ h ^ uintptr(fastrand1())) // any kind of NaN 126 default: 127 return memhash(p, h, 4) 128 } 129 } 130 131 func f64hash(p unsafe.Pointer, h uintptr) uintptr { 132 f := *(*float64)(p) 133 switch { 134 case f == 0: 135 return c1 * (c0 ^ h) // +0, -0 136 case f != f: 137 return c1 * (c0 ^ h ^ uintptr(fastrand1())) // any kind of NaN 138 default: 139 return memhash(p, h, 8) 140 } 141 } 142 143 func c64hash(p unsafe.Pointer, h uintptr) uintptr { 144 x := (*[2]float32)(p) 145 return f32hash(unsafe.Pointer(&x[1]), f32hash(unsafe.Pointer(&x[0]), h)) 146 } 147 148 func c128hash(p unsafe.Pointer, h uintptr) uintptr { 149 x := (*[2]float64)(p) 150 return f64hash(unsafe.Pointer(&x[1]), f64hash(unsafe.Pointer(&x[0]), h)) 151 } 152 153 func interhash(p unsafe.Pointer, h uintptr) uintptr { 154 a := (*iface)(p) 155 tab := a.tab 156 if tab == nil { 157 return h 158 } 159 t := tab._type 160 fn := t.alg.hash 161 if fn == nil { 162 panic(errorString("hash of unhashable type " + *t._string)) 163 } 164 if isDirectIface(t) { 165 return c1 * fn(unsafe.Pointer(&a.data), h^c0) 166 } else { 167 return c1 * fn(a.data, h^c0) 168 } 169 } 170 171 func nilinterhash(p unsafe.Pointer, h uintptr) uintptr { 172 a := (*eface)(p) 173 t := a._type 174 if t == nil { 175 return h 176 } 177 fn := t.alg.hash 178 if fn == nil { 179 panic(errorString("hash of unhashable type " + *t._string)) 180 } 181 if isDirectIface(t) { 182 return c1 * fn(unsafe.Pointer(&a.data), h^c0) 183 } else { 184 return c1 * fn(a.data, h^c0) 185 } 186 } 187 188 func memequal(p, q unsafe.Pointer, size uintptr) bool { 189 if p == q { 190 return true 191 } 192 return memeq(p, q, size) 193 } 194 195 func memequal0(p, q unsafe.Pointer) bool { 196 return true 197 } 198 func memequal8(p, q unsafe.Pointer) bool { 199 return *(*int8)(p) == *(*int8)(q) 200 } 201 func memequal16(p, q unsafe.Pointer) bool { 202 return *(*int16)(p) == *(*int16)(q) 203 } 204 func memequal32(p, q unsafe.Pointer) bool { 205 return *(*int32)(p) == *(*int32)(q) 206 } 207 func memequal64(p, q unsafe.Pointer) bool { 208 return *(*int64)(p) == *(*int64)(q) 209 } 210 func memequal128(p, q unsafe.Pointer) bool { 211 return *(*[2]int64)(p) == *(*[2]int64)(q) 212 } 213 func f32equal(p, q unsafe.Pointer) bool { 214 return *(*float32)(p) == *(*float32)(q) 215 } 216 func f64equal(p, q unsafe.Pointer) bool { 217 return *(*float64)(p) == *(*float64)(q) 218 } 219 func c64equal(p, q unsafe.Pointer) bool { 220 return *(*complex64)(p) == *(*complex64)(q) 221 } 222 func c128equal(p, q unsafe.Pointer) bool { 223 return *(*complex128)(p) == *(*complex128)(q) 224 } 225 func strequal(p, q unsafe.Pointer) bool { 226 return *(*string)(p) == *(*string)(q) 227 } 228 func interequal(p, q unsafe.Pointer) bool { 229 return ifaceeq(*(*interface { 230 f() 231 })(p), *(*interface { 232 f() 233 })(q)) 234 } 235 func nilinterequal(p, q unsafe.Pointer) bool { 236 return efaceeq(*(*interface{})(p), *(*interface{})(q)) 237 } 238 func efaceeq(p, q interface{}) bool { 239 x := (*eface)(unsafe.Pointer(&p)) 240 y := (*eface)(unsafe.Pointer(&q)) 241 t := x._type 242 if t != y._type { 243 return false 244 } 245 if t == nil { 246 return true 247 } 248 eq := t.alg.equal 249 if eq == nil { 250 panic(errorString("comparing uncomparable type " + *t._string)) 251 } 252 if isDirectIface(t) { 253 return eq(noescape(unsafe.Pointer(&x.data)), noescape(unsafe.Pointer(&y.data))) 254 } 255 return eq(x.data, y.data) 256 } 257 func ifaceeq(p, q interface { 258 f() 259 }) bool { 260 x := (*iface)(unsafe.Pointer(&p)) 261 y := (*iface)(unsafe.Pointer(&q)) 262 xtab := x.tab 263 if xtab != y.tab { 264 return false 265 } 266 if xtab == nil { 267 return true 268 } 269 t := xtab._type 270 eq := t.alg.equal 271 if eq == nil { 272 panic(errorString("comparing uncomparable type " + *t._string)) 273 } 274 if isDirectIface(t) { 275 return eq(noescape(unsafe.Pointer(&x.data)), noescape(unsafe.Pointer(&y.data))) 276 } 277 return eq(x.data, y.data) 278 } 279 280 // Testing adapters for hash quality tests (see hash_test.go) 281 func stringHash(s string, seed uintptr) uintptr { 282 return algarray[alg_STRING].hash(noescape(unsafe.Pointer(&s)), seed) 283 } 284 285 func bytesHash(b []byte, seed uintptr) uintptr { 286 s := (*slice)(unsafe.Pointer(&b)) 287 return memhash(s.array, seed, uintptr(s.len)) 288 } 289 290 func int32Hash(i uint32, seed uintptr) uintptr { 291 return algarray[alg_MEM32].hash(noescape(unsafe.Pointer(&i)), seed) 292 } 293 294 func int64Hash(i uint64, seed uintptr) uintptr { 295 return algarray[alg_MEM64].hash(noescape(unsafe.Pointer(&i)), seed) 296 } 297 298 func efaceHash(i interface{}, seed uintptr) uintptr { 299 return algarray[alg_NILINTER].hash(noescape(unsafe.Pointer(&i)), seed) 300 } 301 302 func ifaceHash(i interface { 303 F() 304 }, seed uintptr) uintptr { 305 return algarray[alg_INTER].hash(noescape(unsafe.Pointer(&i)), seed) 306 } 307 308 // Testing adapter for memclr 309 func memclrBytes(b []byte) { 310 s := (*slice)(unsafe.Pointer(&b)) 311 memclr(s.array, uintptr(s.len)) 312 } 313 314 const hashRandomBytes = ptrSize / 4 * 64 315 316 // used in asm_{386,amd64}.s to seed the hash function 317 var aeskeysched [hashRandomBytes]byte 318 319 // used in hash{32,64}.go to seed the hash function 320 var hashkey [4]uintptr 321 322 func init() { 323 // Install aes hash algorithm if we have the instructions we need 324 if (GOARCH == "386" || GOARCH == "amd64") && 325 GOOS != "nacl" && 326 cpuid_ecx&(1<<25) != 0 && // aes (aesenc) 327 cpuid_ecx&(1<<9) != 0 && // sse3 (pshufb) 328 cpuid_ecx&(1<<19) != 0 { // sse4.1 (pinsr{d,q}) 329 useAeshash = true 330 algarray[alg_MEM32].hash = aeshash32 331 algarray[alg_MEM64].hash = aeshash64 332 algarray[alg_STRING].hash = aeshashstr 333 // Initialize with random data so hash collisions will be hard to engineer. 334 getRandomData(aeskeysched[:]) 335 return 336 } 337 getRandomData((*[len(hashkey) * ptrSize]byte)(unsafe.Pointer(&hashkey))[:]) 338 hashkey[0] |= 1 // make sure this number is odd 339 } 340
