hash64.go

Documentation: 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  // wyhash: https://github.com/wangyi-fudan/wyhash
		 7  
		 8  //go:build amd64 || arm64 || mips64 || mips64le || ppc64 || ppc64le || riscv64 || s390x || wasm
		 9  // +build amd64 arm64 mips64 mips64le ppc64 ppc64le riscv64 s390x wasm
		10  
		11  package runtime
		12  
		13  import (
		14  	"runtime/internal/math"
		15  	"unsafe"
		16  )
		17  
		18  const (
		19  	m1 = 0xa0761d6478bd642f
		20  	m2 = 0xe7037ed1a0b428db
		21  	m3 = 0x8ebc6af09c88c6e3
		22  	m4 = 0x589965cc75374cc3
		23  	m5 = 0x1d8e4e27c47d124f
		24  )
		25  
		26  func memhashFallback(p unsafe.Pointer, seed, s uintptr) uintptr {
		27  	var a, b uintptr
		28  	seed ^= hashkey[0] ^ m1
		29  	switch {
		30  	case s == 0:
		31  		return seed
		32  	case s < 4:
		33  		a = uintptr(*(*byte)(p))
		34  		a |= uintptr(*(*byte)(add(p, s>>1))) << 8
		35  		a |= uintptr(*(*byte)(add(p, s-1))) << 16
		36  	case s == 4:
		37  		a = r4(p)
		38  		b = a
		39  	case s < 8:
		40  		a = r4(p)
		41  		b = r4(add(p, s-4))
		42  	case s == 8:
		43  		a = r8(p)
		44  		b = a
		45  	case s <= 16:
		46  		a = r8(p)
		47  		b = r8(add(p, s-8))
		48  	default:
		49  		l := s
		50  		if l > 48 {
		51  			seed1 := seed
		52  			seed2 := seed
		53  			for ; l > 48; l -= 48 {
		54  				seed = mix(r8(p)^m2, r8(add(p, 8))^seed)
		55  				seed1 = mix(r8(add(p, 16))^m3, r8(add(p, 24))^seed1)
		56  				seed2 = mix(r8(add(p, 32))^m4, r8(add(p, 40))^seed2)
		57  				p = add(p, 48)
		58  			}
		59  			seed ^= seed1 ^ seed2
		60  		}
		61  		for ; l > 16; l -= 16 {
		62  			seed = mix(r8(p)^m2, r8(add(p, 8))^seed)
		63  			p = add(p, 16)
		64  		}
		65  		a = r8(add(p, l-16))
		66  		b = r8(add(p, l-8))
		67  	}
		68  
		69  	return mix(m5^s, mix(a^m2, b^seed))
		70  }
		71  
		72  func memhash32Fallback(p unsafe.Pointer, seed uintptr) uintptr {
		73  	a := r4(p)
		74  	return mix(m5^4, mix(a^m2, a^seed^hashkey[0]^m1))
		75  }
		76  
		77  func memhash64Fallback(p unsafe.Pointer, seed uintptr) uintptr {
		78  	a := r8(p)
		79  	return mix(m5^8, mix(a^m2, a^seed^hashkey[0]^m1))
		80  }
		81  
		82  func mix(a, b uintptr) uintptr {
		83  	hi, lo := math.Mul64(uint64(a), uint64(b))
		84  	return uintptr(hi ^ lo)
		85  }
		86  
		87  func r4(p unsafe.Pointer) uintptr {
		88  	return uintptr(readUnaligned32(p))
		89  }
		90  
		91  func r8(p unsafe.Pointer) uintptr {
		92  	return uintptr(readUnaligned64(p))
		93  }
		94
View as plain text