Black Lives Matter. Support the Equal Justice Initiative.

Source file src/runtime/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