maphash_purego.go

     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  	"errors"
    12  	"internal/byteorder"
    13  	"math"
    14  	"math/bits"
    15  	"reflect"
    16  )
    17  
    18  const purego = true
    19  
    20  var hashkey [4]uint64
    21  
    22  func init() {
    23  	for i := range hashkey {
    24  		hashkey[i] = randUint64()
    25  	}
    26  }
    27  
    28  func rthash(buf []byte, seed uint64) uint64 {
    29  	if len(buf) == 0 {
    30  		return seed
    31  	}
    32  	return wyhash(buf, seed, uint64(len(buf)))
    33  }
    34  
    35  func rthashString(s string, state uint64) uint64 {
    36  	return rthash([]byte(s), state)
    37  }
    38  
    39  func randUint64() uint64 {
    40  	buf := make([]byte, 8)
    41  	_, _ = rand.Read(buf)
    42  	return byteorder.LEUint64(buf)
    43  }
    44  
    45  // This is a port of wyhash implementation in runtime/hash64.go,
    46  // without using unsafe for purego.
    47  
    48  const m5 = 0x1d8e4e27c47d124f
    49  
    50  func wyhash(key []byte, seed, len uint64) uint64 {
    51  	p := key
    52  	i := len
    53  	var a, b uint64
    54  	seed ^= hashkey[0]
    55  
    56  	if i > 16 {
    57  		if i > 48 {
    58  			seed1 := seed
    59  			seed2 := seed
    60  			for ; i > 48; i -= 48 {
    61  				seed = mix(r8(p)^hashkey[1], r8(p[8:])^seed)
    62  				seed1 = mix(r8(p[16:])^hashkey[2], r8(p[24:])^seed1)
    63  				seed2 = mix(r8(p[32:])^hashkey[3], r8(p[40:])^seed2)
    64  				p = p[48:]
    65  			}
    66  			seed ^= seed1 ^ seed2
    67  		}
    68  		for ; i > 16; i -= 16 {
    69  			seed = mix(r8(p)^hashkey[1], r8(p[8:])^seed)
    70  			p = p[16:]
    71  		}
    72  	}
    73  	switch {
    74  	case i == 0:
    75  		return seed
    76  	case i < 4:
    77  		a = r3(p, i)
    78  	default:
    79  		n := (i >> 3) << 2
    80  		a = r4(p)<<32 | r4(p[n:])
    81  		b = r4(p[i-4:])<<32 | r4(p[i-4-n:])
    82  	}
    83  	return mix(m5^len, mix(a^hashkey[1], b^seed))
    84  }
    85  
    86  func r3(p []byte, k uint64) uint64 {
    87  	return (uint64(p[0]) << 16) | (uint64(p[k>>1]) << 8) | uint64(p[k-1])
    88  }
    89  
    90  func r4(p []byte) uint64 {
    91  	return uint64(byteorder.LEUint32(p))
    92  }
    93  
    94  func r8(p []byte) uint64 {
    95  	return byteorder.LEUint64(p)
    96  }
    97  
    98  func mix(a, b uint64) uint64 {
    99  	hi, lo := bits.Mul64(a, b)
   100  	return hi ^ lo
   101  }
   102  
   103  func comparableHash[T comparable](v T, seed Seed) uint64 {
   104  	var h Hash
   105  	h.SetSeed(seed)
   106  	writeComparable(&h, v)
   107  	return h.Sum64()
   108  }
   109  
   110  func writeComparable[T comparable](h *Hash, v T) {
   111  	vv := reflect.ValueOf(v)
   112  	appendT(h, vv)
   113  }
   114  
   115  // appendT hash a value.
   116  func appendT(h *Hash, v reflect.Value) {
   117  	h.WriteString(v.Type().String())
   118  	switch v.Kind() {
   119  	case reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64, reflect.Int:
   120  		var buf [8]byte
   121  		byteorder.LEPutUint64(buf[:], uint64(v.Int()))
   122  		h.Write(buf[:])
   123  		return
   124  	case reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uint, reflect.Uintptr:
   125  		var buf [8]byte
   126  		byteorder.LEPutUint64(buf[:], v.Uint())
   127  		h.Write(buf[:])
   128  		return
   129  	case reflect.Array:
   130  		var buf [8]byte
   131  		for i := range uint64(v.Len()) {
   132  			byteorder.LEPutUint64(buf[:], i)
   133  			// do not want to hash to the same value,
   134  			// [2]string{"foo", ""} and [2]string{"", "foo"}.
   135  			h.Write(buf[:])
   136  			appendT(h, v.Index(int(i)))
   137  		}
   138  		return
   139  	case reflect.String:
   140  		h.WriteString(v.String())
   141  		return
   142  	case reflect.Struct:
   143  		var buf [8]byte
   144  		for i := range v.NumField() {
   145  			f := v.Field(i)
   146  			byteorder.LEPutUint64(buf[:], uint64(i))
   147  			// do not want to hash to the same value,
   148  			// struct{a,b string}{"foo",""} and
   149  			// struct{a,b string}{"","foo"}.
   150  			h.Write(buf[:])
   151  			appendT(h, f)
   152  		}
   153  		return
   154  	case reflect.Complex64, reflect.Complex128:
   155  		c := v.Complex()
   156  		h.float64(real(c))
   157  		h.float64(imag(c))
   158  		return
   159  	case reflect.Float32, reflect.Float64:
   160  		h.float64(v.Float())
   161  		return
   162  	case reflect.Bool:
   163  		h.WriteByte(btoi(v.Bool()))
   164  		return
   165  	case reflect.UnsafePointer, reflect.Pointer, reflect.Chan:
   166  		var buf [8]byte
   167  		// because pointing to the abi.Escape call in comparableReady,
   168  		// So this is ok to hash pointer,
   169  		// this way because we know their target won't be moved.
   170  		byteorder.LEPutUint64(buf[:], uint64(v.Pointer()))
   171  		h.Write(buf[:])
   172  		return
   173  	case reflect.Interface:
   174  		appendT(h, v.Elem())
   175  		return
   176  	}
   177  	panic(errors.New("maphash: hash of unhashable type " + v.Type().String()))
   178  }
   179  
   180  func (h *Hash) float64(f float64) {
   181  	if f == 0 {
   182  		h.WriteByte(0)
   183  		return
   184  	}
   185  	var buf [8]byte
   186  	if f != f {
   187  		byteorder.LEPutUint64(buf[:], randUint64())
   188  		h.Write(buf[:])
   189  		return
   190  	}
   191  	byteorder.LEPutUint64(buf[:], math.Float64bits(f))
   192  	h.Write(buf[:])
   193  }
   194  
   195  func btoi(b bool) byte {
   196  	if b {
   197  		return 1
   198  	}
   199  	return 0
   200  }
   201
View as plain text