Source file src/runtime/hash64.go

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

View as plain text