Adding upstream version 1.16.10.upstream/1.16.10upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 112 insertions, 0 deletions

diff --git a/src/runtime/hash32.go b/src/runtime/hash32.go
new file mode 100644
index 0000000..966f70e
--- /dev/null
+++ b/src/runtime/hash32.go
@@ -0,0 +1,112 @@
+// Copyright 2014 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Hashing algorithm inspired by
+//   xxhash: https://code.google.com/p/xxhash/
+// cityhash: https://code.google.com/p/cityhash/
+
+// +build 386 arm mips mipsle
+
+package runtime
+
+import "unsafe"
+
+const (
+	// Constants for multiplication: four random odd 32-bit numbers.
+	m1 = 3168982561
+	m2 = 3339683297
+	m3 = 832293441
+	m4 = 2336365089
+)
+
+func memhashFallback(p unsafe.Pointer, seed, s uintptr) uintptr {
+	h := uint32(seed + s*hashkey[0])
+tail:
+	switch {
+	case s == 0:
+	case s < 4:
+		h ^= uint32(*(*byte)(p))
+		h ^= uint32(*(*byte)(add(p, s>>1))) << 8
+		h ^= uint32(*(*byte)(add(p, s-1))) << 16
+		h = rotl_15(h*m1) * m2
+	case s == 4:
+		h ^= readUnaligned32(p)
+		h = rotl_15(h*m1) * m2
+	case s <= 8:
+		h ^= readUnaligned32(p)
+		h = rotl_15(h*m1) * m2
+		h ^= readUnaligned32(add(p, s-4))
+		h = rotl_15(h*m1) * m2
+	case s <= 16:
+		h ^= readUnaligned32(p)
+		h = rotl_15(h*m1) * m2
+		h ^= readUnaligned32(add(p, 4))
+		h = rotl_15(h*m1) * m2
+		h ^= readUnaligned32(add(p, s-8))
+		h = rotl_15(h*m1) * m2
+		h ^= readUnaligned32(add(p, s-4))
+		h = rotl_15(h*m1) * m2
+	default:
+		v1 := h
+		v2 := uint32(seed * hashkey[1])
+		v3 := uint32(seed * hashkey[2])
+		v4 := uint32(seed * hashkey[3])
+		for s >= 16 {
+			v1 ^= readUnaligned32(p)
+			v1 = rotl_15(v1*m1) * m2
+			p = add(p, 4)
+			v2 ^= readUnaligned32(p)
+			v2 = rotl_15(v2*m2) * m3
+			p = add(p, 4)
+			v3 ^= readUnaligned32(p)
+			v3 = rotl_15(v3*m3) * m4
+			p = add(p, 4)
+			v4 ^= readUnaligned32(p)
+			v4 = rotl_15(v4*m4) * m1
+			p = add(p, 4)
+			s -= 16
+		}
+		h = v1 ^ v2 ^ v3 ^ v4
+		goto tail
+	}
+	h ^= h >> 17
+	h *= m3
+	h ^= h >> 13
+	h *= m4
+	h ^= h >> 16
+	return uintptr(h)
+}
+
+func memhash32Fallback(p unsafe.Pointer, seed uintptr) uintptr {
+	h := uint32(seed + 4*hashkey[0])
+	h ^= readUnaligned32(p)
+	h = rotl_15(h*m1) * m2
+	h ^= h >> 17
+	h *= m3
+	h ^= h >> 13
+	h *= m4
+	h ^= h >> 16
+	return uintptr(h)
+}
+
+func memhash64Fallback(p unsafe.Pointer, seed uintptr) uintptr {
+	h := uint32(seed + 8*hashkey[0])
+	h ^= readUnaligned32(p)
+	h = rotl_15(h*m1) * m2
+	h ^= readUnaligned32(add(p, 4))
+	h = rotl_15(h*m1) * m2
+	h ^= h >> 17
+	h *= m3
+	h ^= h >> 13
+	h *= m4
+	h ^= h >> 16
+	return uintptr(h)
+}
+
+// Note: in order to get the compiler to issue rotl instructions, we
+// need to constant fold the shift amount by hand.
+// TODO: convince the compiler to issue rotl instructions after inlining.
+func rotl_15(x uint32) uint32 {
+	return (x << 15) | (x >> (32 - 15))
+}