maphash_purego.go

Documentation: hash/maphash

     1  // Copyright 2023 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  //go:build purego
     6  
     7  package maphash
     8  
     9  import (
    10  	"crypto/rand"
    11  	"math/bits"
    12  )
    13  
    14  func rthash(buf []byte, seed uint64) uint64 {
    15  	if len(buf) == 0 {
    16  		return seed
    17  	}
    18  	return wyhash(buf, seed, uint64(len(buf)))
    19  }
    20  
    21  func rthashString(s string, state uint64) uint64 {
    22  	return rthash([]byte(s), state)
    23  }
    24  
    25  func randUint64() uint64 {
    26  	buf := make([]byte, 8)
    27  	_, _ = rand.Read(buf)
    28  	return leUint64(buf)
    29  }
    30  
    31  // This is a port of wyhash implementation in runtime/hash64.go,
    32  // without using unsafe for purego.
    33  
    34  const (
    35  	m1 = 0xa0761d6478bd642f
    36  	m2 = 0xe7037ed1a0b428db
    37  	m3 = 0x8ebc6af09c88c6e3
    38  	m4 = 0x589965cc75374cc3
    39  	m5 = 0x1d8e4e27c47d124f
    40  )
    41  
    42  func wyhash(key []byte, seed, len uint64) uint64 {
    43  	p := key
    44  	i := len
    45  	var a, b uint64
    46  	seed ^= m1
    47  
    48  	if i > 16 {
    49  		if i > 48 {
    50  			seed1 := seed
    51  			seed2 := seed
    52  			for ; i > 48; i -= 48 {
    53  				seed = mix(r8(p)^m2, r8(p[8:])^seed)
    54  				seed1 = mix(r8(p[16:])^m3, r8(p[24:])^seed1)
    55  				seed2 = mix(r8(p[32:])^m4, r8(p[40:])^seed2)
    56  				p = p[48:]
    57  			}
    58  			seed ^= seed1 ^ seed2
    59  		}
    60  		for ; i > 16; i -= 16 {
    61  			seed = mix(r8(p)^m2, r8(p[8:])^seed)
    62  			p = p[16:]
    63  		}
    64  	}
    65  	switch {
    66  	case i == 0:
    67  		return seed
    68  	case i < 4:
    69  		a = r3(p, i)
    70  	default:
    71  		n := (i >> 3) << 2
    72  		a = r4(p)<<32 | r4(p[n:])
    73  		b = r4(p[i-4:])<<32 | r4(p[i-4-n:])
    74  	}
    75  	return mix(m5^len, mix(a^m2, b^seed))
    76  }
    77  
    78  func r3(p []byte, k uint64) uint64 {
    79  	return (uint64(p[0]) << 16) | (uint64(p[k>>1]) << 8) | uint64(p[k-1])
    80  }
    81  
    82  func r4(p []byte) uint64 {
    83  	return uint64(leUint32(p))
    84  }
    85  
    86  func r8(p []byte) uint64 {
    87  	return leUint64(p)
    88  }
    89  
    90  func mix(a, b uint64) uint64 {
    91  	hi, lo := bits.Mul64(a, b)
    92  	return hi ^ lo
    93  }
    94  
    95  func leUint32(b []byte) uint32 {
    96  	_ = b[3] // bounds check hint to compiler; see golang.org/issue/14808
    97  	return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
    98  }
    99  
   100  func leUint64(b []byte) uint64 {
   101  	_ = b[7] // bounds check hint to compiler; see golang.org/issue/14808
   102  	return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |
   103  		uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56
   104  }
   105
View as plain text