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