Source file src/runtime/hash32.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 386 arm mips mipsle
    10	
    11	package runtime
    12	
    13	import "unsafe"
    14	
    15	const (
    16		// Constants for multiplication: four random odd 32-bit numbers.
    17		m1 = 3168982561
    18		m2 = 3339683297
    19		m3 = 832293441
    20		m4 = 2336365089
    21	)
    22	
    23	func memhash(p unsafe.Pointer, seed, s uintptr) uintptr {
    24		if GOARCH == "386" && GOOS != "nacl" && useAeshash {
    25			return aeshash(p, seed, s)
    26		}
    27		h := uint32(seed + s*hashkey[0])
    28	tail:
    29		switch {
    30		case s == 0:
    31		case s < 4:
    32			h ^= uint32(*(*byte)(p))
    33			h ^= uint32(*(*byte)(add(p, s>>1))) << 8
    34			h ^= uint32(*(*byte)(add(p, s-1))) << 16
    35			h = rotl_15(h*m1) * m2
    36		case s == 4:
    37			h ^= readUnaligned32(p)
    38			h = rotl_15(h*m1) * m2
    39		case s <= 8:
    40			h ^= readUnaligned32(p)
    41			h = rotl_15(h*m1) * m2
    42			h ^= readUnaligned32(add(p, s-4))
    43			h = rotl_15(h*m1) * m2
    44		case s <= 16:
    45			h ^= readUnaligned32(p)
    46			h = rotl_15(h*m1) * m2
    47			h ^= readUnaligned32(add(p, 4))
    48			h = rotl_15(h*m1) * m2
    49			h ^= readUnaligned32(add(p, s-8))
    50			h = rotl_15(h*m1) * m2
    51			h ^= readUnaligned32(add(p, s-4))
    52			h = rotl_15(h*m1) * m2
    53		default:
    54			v1 := h
    55			v2 := uint32(seed * hashkey[1])
    56			v3 := uint32(seed * hashkey[2])
    57			v4 := uint32(seed * hashkey[3])
    58			for s >= 16 {
    59				v1 ^= readUnaligned32(p)
    60				v1 = rotl_15(v1*m1) * m2
    61				p = add(p, 4)
    62				v2 ^= readUnaligned32(p)
    63				v2 = rotl_15(v2*m2) * m3
    64				p = add(p, 4)
    65				v3 ^= readUnaligned32(p)
    66				v3 = rotl_15(v3*m3) * m4
    67				p = add(p, 4)
    68				v4 ^= readUnaligned32(p)
    69				v4 = rotl_15(v4*m4) * m1
    70				p = add(p, 4)
    71				s -= 16
    72			}
    73			h = v1 ^ v2 ^ v3 ^ v4
    74			goto tail
    75		}
    76		h ^= h >> 17
    77		h *= m3
    78		h ^= h >> 13
    79		h *= m4
    80		h ^= h >> 16
    81		return uintptr(h)
    82	}
    83	
    84	func memhash32(p unsafe.Pointer, seed uintptr) uintptr {
    85		h := uint32(seed + 4*hashkey[0])
    86		h ^= readUnaligned32(p)
    87		h = rotl_15(h*m1) * m2
    88		h ^= h >> 17
    89		h *= m3
    90		h ^= h >> 13
    91		h *= m4
    92		h ^= h >> 16
    93		return uintptr(h)
    94	}
    95	
    96	func memhash64(p unsafe.Pointer, seed uintptr) uintptr {
    97		h := uint32(seed + 8*hashkey[0])
    98		h ^= readUnaligned32(p)
    99		h = rotl_15(h*m1) * m2
   100		h ^= readUnaligned32(add(p, 4))
   101		h = rotl_15(h*m1) * m2
   102		h ^= h >> 17
   103		h *= m3
   104		h ^= h >> 13
   105		h *= m4
   106		h ^= h >> 16
   107		return uintptr(h)
   108	}
   109	
   110	// Note: in order to get the compiler to issue rotl instructions, we
   111	// need to constant fold the shift amount by hand.
   112	// TODO: convince the compiler to issue rotl instructions after inlining.
   113	func rotl_15(x uint32) uint32 {
   114		return (x << 15) | (x >> (32 - 15))
   115	}
   116	

View as plain text