libgo/go/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 //   xxhash: https://code.google.com/p/xxhash/
   7 // cityhash: https://code.google.com/p/cityhash/
   8
   9 // +build amd64 amd64p32 arm64 mips64 mips64le ppc64 ppc64le s390x alpha arm64be ia64 mips64p32 mips64p32le sparc64
  10
  11 package runtime
  12
  13 import "unsafe"
  14
  15 // For gccgo, use go:linkname to rename compiler-called functions to
  16 // themselves, so that the compiler will export them.
  17 //
  18 //go:linkname memhash runtime.memhash
  19
  20 const (
  21         // Constants for multiplication: four random odd 64-bit numbers.
  22         m1 = 16877499708836156737
  23         m2 = 2820277070424839065
  24         m3 = 9497967016996688599
  25         m4 = 15839092249703872147
  26 )
  27
  28 func memhash(p unsafe.Pointer, seed, s uintptr) uintptr {
  29         if GOARCH == "amd64" && GOOS != "nacl" && useAeshash {
  30                 return aeshash(p, seed, s)
  31         }
  32         h := uint64(seed + s*hashkey[0])
  33 tail:
  34         switch {
  35         case s == 0:
  36         case s < 4:
  37                 h ^= uint64(*(*byte)(p))
  38                 h ^= uint64(*(*byte)(add(p, s>>1))) << 8
  39                 h ^= uint64(*(*byte)(add(p, s-1))) << 16
  40                 h = rotl_31(h*m1) * m2
  41         case s <= 8:
  42                 h ^= uint64(readUnaligned32(p))
  43                 h ^= uint64(readUnaligned32(add(p, s-4))) << 32
  44                 h = rotl_31(h*m1) * m2
  45         case s <= 16:
  46                 h ^= readUnaligned64(p)
  47                 h = rotl_31(h*m1) * m2
  48                 h ^= readUnaligned64(add(p, s-8))
  49                 h = rotl_31(h*m1) * m2
  50         case s <= 32:
  51                 h ^= readUnaligned64(p)
  52                 h = rotl_31(h*m1) * m2
  53                 h ^= readUnaligned64(add(p, 8))
  54                 h = rotl_31(h*m1) * m2
  55                 h ^= readUnaligned64(add(p, s-16))
  56                 h = rotl_31(h*m1) * m2
  57                 h ^= readUnaligned64(add(p, s-8))
  58                 h = rotl_31(h*m1) * m2
  59         default:
  60                 v1 := h
  61                 v2 := uint64(seed * hashkey[1])
  62                 v3 := uint64(seed * hashkey[2])
  63                 v4 := uint64(seed * hashkey[3])
  64                 for s >= 32 {
  65                         v1 ^= readUnaligned64(p)
  66                         v1 = rotl_31(v1*m1) * m2
  67                         p = add(p, 8)
  68                         v2 ^= readUnaligned64(p)
  69                         v2 = rotl_31(v2*m2) * m3
  70                         p = add(p, 8)
  71                         v3 ^= readUnaligned64(p)
  72                         v3 = rotl_31(v3*m3) * m4
  73                         p = add(p, 8)
  74                         v4 ^= readUnaligned64(p)
  75                         v4 = rotl_31(v4*m4) * m1
  76                         p = add(p, 8)
  77                         s -= 32
  78                 }
  79                 h = v1 ^ v2 ^ v3 ^ v4
  80                 goto tail
  81         }
  82
  83         h ^= h >> 29
  84         h *= m3
  85         h ^= h >> 32
  86         return uintptr(h)
  87 }
  88
  89 func memhash32(p unsafe.Pointer, seed uintptr) uintptr {
  90         h := uint64(seed + 4*hashkey[0])
  91         v := uint64(readUnaligned32(p))
  92         h ^= v
  93         h ^= v << 32
  94         h = rotl_31(h*m1) * m2
  95         h ^= h >> 29
  96         h *= m3
  97         h ^= h >> 32
  98         return uintptr(h)
  99 }
 100
 101 func memhash64(p unsafe.Pointer, seed uintptr) uintptr {
 102         h := uint64(seed + 8*hashkey[0])
 103         h ^= uint64(readUnaligned32(p)) | uint64(readUnaligned32(add(p, 4)))<<32
 104         h = rotl_31(h*m1) * m2
 105         h ^= h >> 29
 106         h *= m3
 107         h ^= h >> 32
 108         return uintptr(h)
 109 }
 110
 111 // Note: in order to get the compiler to issue rotl instructions, we
 112 // need to constant fold the shift amount by hand.
 113 // TODO: convince the compiler to issue rotl instructions after inlining.
 114 func rotl_31(x uint64) uint64 {
 115         return (x << 31) | (x >> (64 - 31))
 116 }