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