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 || 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         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 }