Home | History | Annotate | Download | only in runtime 
      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 // Hashing algorithm inspired by
      6 //   xxhash: https://code.google.com/p/xxhash/
      7 // cityhash: https://code.google.com/p/cityhash/
      8 
      9 // +build amd64 amd64p32 arm64 mips64 mips64le ppc64 ppc64le s390x
     10 
     11 package runtime
     12 
     13 import "unsafe"
     14 
     15 const (
     16 	// Constants for multiplication: four random odd 64-bit numbers.
     17 	m1 = 16877499708836156737
     18 	m2 = 2820277070424839065
     19 	m3 = 9497967016996688599
     20 	m4 = 15839092249703872147
     21 )
     22 
     23 func memhash(p unsafe.Pointer, seed, s uintptr) uintptr {
     24 	if GOARCH == "amd64" && GOOS != "nacl" && useAeshash {
     25 		return aeshash(p, seed, s)
     26 	}
     27 	h := uint64(seed + s*hashkey[0])
     28 tail:
     29 	switch {
     30 	case s == 0:
     31 	case s < 4:
     32 		h ^= uint64(*(*byte)(p))
     33 		h ^= uint64(*(*byte)(add(p, s>>1))) << 8
     34 		h ^= uint64(*(*byte)(add(p, s-1))) << 16
     35 		h = rotl_31(h*m1) * m2
     36 	case s <= 8:
     37 		h ^= uint64(readUnaligned32(p))
     38 		h ^= uint64(readUnaligned32(add(p, s-4))) << 32
     39 		h = rotl_31(h*m1) * m2
     40 	case s <= 16:
     41 		h ^= readUnaligned64(p)
     42 		h = rotl_31(h*m1) * m2
     43 		h ^= readUnaligned64(add(p, s-8))
     44 		h = rotl_31(h*m1) * m2
     45 	case s <= 32:
     46 		h ^= readUnaligned64(p)
     47 		h = rotl_31(h*m1) * m2
     48 		h ^= readUnaligned64(add(p, 8))
     49 		h = rotl_31(h*m1) * m2
     50 		h ^= readUnaligned64(add(p, s-16))
     51 		h = rotl_31(h*m1) * m2
     52 		h ^= readUnaligned64(add(p, s-8))
     53 		h = rotl_31(h*m1) * m2
     54 	default:
     55 		v1 := h
     56 		v2 := uint64(seed * hashkey[1])
     57 		v3 := uint64(seed * hashkey[2])
     58 		v4 := uint64(seed * hashkey[3])
     59 		for s >= 32 {
     60 			v1 ^= readUnaligned64(p)
     61 			v1 = rotl_31(v1*m1) * m2
     62 			p = add(p, 8)
     63 			v2 ^= readUnaligned64(p)
     64 			v2 = rotl_31(v2*m2) * m3
     65 			p = add(p, 8)
     66 			v3 ^= readUnaligned64(p)
     67 			v3 = rotl_31(v3*m3) * m4
     68 			p = add(p, 8)
     69 			v4 ^= readUnaligned64(p)
     70 			v4 = rotl_31(v4*m4) * m1
     71 			p = add(p, 8)
     72 			s -= 32
     73 		}
     74 		h = v1 ^ v2 ^ v3 ^ v4
     75 		goto tail
     76 	}
     77 
     78 	h ^= h >> 29
     79 	h *= m3
     80 	h ^= h >> 32
     81 	return uintptr(h)
     82 }
     83 
     84 func memhash32(p unsafe.Pointer, seed uintptr) uintptr {
     85 	h := uint64(seed + 4*hashkey[0])
     86 	v := uint64(readUnaligned32(p))
     87 	h ^= v
     88 	h ^= v << 32
     89 	h = rotl_31(h*m1) * m2
     90 	h ^= h >> 29
     91 	h *= m3
     92 	h ^= h >> 32
     93 	return uintptr(h)
     94 }
     95 
     96 func memhash64(p unsafe.Pointer, seed uintptr) uintptr {
     97 	h := uint64(seed + 8*hashkey[0])
     98 	h ^= uint64(readUnaligned32(p)) | uint64(readUnaligned32(add(p, 4)))<<32
     99 	h = rotl_31(h*m1) * m2
    100 	h ^= h >> 29
    101 	h *= m3
    102 	h ^= h >> 32
    103 	return uintptr(h)
    104 }
    105 
    106 // Note: in order to get the compiler to issue rotl instructions, we
    107 // need to constant fold the shift amount by hand.
    108 // TODO: convince the compiler to issue rotl instructions after inlining.
    109 func rotl_31(x uint64) uint64 {
    110 	return (x << 31) | (x >> (64 - 31))
    111 }
    112