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 || loong64 || 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  	m5 = 0x1d8e4e27c47d124f
    19  )
    20  
    21  func memhashFallback(p unsafe.Pointer, seed, s uintptr) uintptr {
    22  	var a, b uintptr
    23  	seed ^= hashkey[0]
    24  	switch {
    25  	case s == 0:
    26  		return seed
    27  	case s < 4:
    28  		a = uintptr(*(*byte)(p))
    29  		a |= uintptr(*(*byte)(add(p, s>>1))) << 8
    30  		a |= uintptr(*(*byte)(add(p, s-1))) << 16
    31  	case s == 4:
    32  		a = r4(p)
    33  		b = a
    34  	case s < 8:
    35  		a = r4(p)
    36  		b = r4(add(p, s-4))
    37  	case s == 8:
    38  		a = r8(p)
    39  		b = a
    40  	case s <= 16:
    41  		a = r8(p)
    42  		b = r8(add(p, s-8))
    43  	default:
    44  		l := s
    45  		if l > 48 {
    46  			seed1 := seed
    47  			seed2 := seed
    48  			for ; l > 48; l -= 48 {
    49  				seed = mix(r8(p)^hashkey[1], r8(add(p, 8))^seed)
    50  				seed1 = mix(r8(add(p, 16))^hashkey[2], r8(add(p, 24))^seed1)
    51  				seed2 = mix(r8(add(p, 32))^hashkey[3], r8(add(p, 40))^seed2)
    52  				p = add(p, 48)
    53  			}
    54  			seed ^= seed1 ^ seed2
    55  		}
    56  		for ; l > 16; l -= 16 {
    57  			seed = mix(r8(p)^hashkey[1], r8(add(p, 8))^seed)
    58  			p = add(p, 16)
    59  		}
    60  		a = r8(add(p, l-16))
    61  		b = r8(add(p, l-8))
    62  	}
    63  
    64  	return mix(m5^s, mix(a^hashkey[1], b^seed))
    65  }
    66  
    67  func memhash32Fallback(p unsafe.Pointer, seed uintptr) uintptr {
    68  	a := r4(p)
    69  	return mix(m5^4, mix(a^hashkey[1], a^seed^hashkey[0]))
    70  }
    71  
    72  func memhash64Fallback(p unsafe.Pointer, seed uintptr) uintptr {
    73  	a := r8(p)
    74  	return mix(m5^8, mix(a^hashkey[1], a^seed^hashkey[0]))
    75  }
    76  
    77  func mix(a, b uintptr) uintptr {
    78  	hi, lo := math.Mul64(uint64(a), uint64(b))
    79  	return uintptr(hi ^ lo)
    80  }
    81  
    82  func r4(p unsafe.Pointer) uintptr {
    83  	return uintptr(readUnaligned32(p))
    84  }
    85  
    86  func r8(p unsafe.Pointer) uintptr {
    87  	return uintptr(readUnaligned64(p))
    88  }
    89
View as plain text