math/bits: much faster Reverse, added respective benchmarks

Measured on 2.3 GHz Intel Core i7, running maxOS 10.12.3.

name         old time/op  new time/op  delta
Reverse-8    76.6ns ± 0%   8.1ns ± 0%   ~     (p=1.000 n=1+1)
Reverse8-8   12.6ns ± 0%   0.6ns ± 0%   ~     (p=1.000 n=1+1)
Reverse16-8  20.8ns ± 0%   0.6ns ± 0%   ~     (p=1.000 n=1+1)
Reverse32-8  36.5ns ± 0%   0.6ns ± 0%   ~     (p=1.000 n=1+1)
Reverse64-8  74.0ns ± 0%   6.4ns ± 0%   ~     (p=1.000 n=1+1)

benchmark                old ns/op     new ns/op     delta
BenchmarkReverse-8       76.6          8.07          -89.46%
BenchmarkReverse8-8      12.6          0.64          -94.92%
BenchmarkReverse16-8     20.8          0.64          -96.92%
BenchmarkReverse32-8     36.5          0.64          -98.25%
BenchmarkReverse64-8     74.0          6.38          -91.38%

Change-Id: I6b99b10cee2f2babfe79342b50ee36a45a34da30
Reviewed-on: https://go-review.googlesource.com/37149
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

3 files changed, 77 insertions, 13 deletions

diff --git a/src/math/bits/bits.go b/src/math/bits/bits.go
index 3164ae9bfe..ab3f3eaa1e 100644
--- a/src/math/bits/bits.go
+++ b/src/math/bits/bits.go
@@ -96,20 +96,62 @@ func RotateRight64(x uint64, k int) uint64 { return uint64(rot(uint64(x), 64, 64
 
 // --- Reverse ---
 
+const m0 = 0xaaaaaaaaaaaaaaaa // 10101010 ...
+const m1 = 0xcccccccccccccccc // 11001100 ...
+const m2 = 0xf0f0f0f0f0f0f0f0 // 11110000 ...
+const m3 = 0xff00ff00ff00ff00 // etc.
+const m4 = 0xffff0000ffff0000
+const m5 = 0xffffffff00000000
+
 // Reverse returns the value of x with its bits in reversed order.
-func Reverse(x uint) uint { return uint(rev(uint64(x), UintSize)) }
+func Reverse(x uint) uint {
+	if UintSize == 32 {
+		return uint(Reverse32(uint32(x)))
+	}
+	return uint(Reverse64(uint64(x)))
+}
 
 // Reverse8 returns the value of x with its bits in reversed order.
-func Reverse8(x uint8) uint8 { return uint8(rev(uint64(x), 8)) }
+func Reverse8(x uint8) uint8 {
+	const m = 0xff
+	x = x&(m0&m)>>1 | x&^(m0&m)<<1
+	x = x&(m1&m)>>2 | x&^(m1&m)<<2
+	x = x&(m2&m)>>4 | x&^(m2&m)<<4
+	return x
+}
 
 // Reverse16 returns the value of x with its bits in reversed order.
-func Reverse16(x uint16) uint16 { return uint16(rev(uint64(x), 16)) }
+func Reverse16(x uint16) uint16 {
+	const m = 0xffff
+	x = x&(m0&m)>>1 | x&^(m0&m)<<1
+	x = x&(m1&m)>>2 | x&^(m1&m)<<2
+	x = x&(m2&m)>>4 | x&^(m2&m)<<4
+	x = x&(m3&m)>>8 | x&^(m3&m)<<8
+	return x
+}
 
 // Reverse32 returns the value of x with its bits in reversed order.
-func Reverse32(x uint32) uint32 { return uint32(rev(uint64(x), 32)) }
+func Reverse32(x uint32) uint32 {
+	const m = 0xffffffff
+	x = x&(m0&m)>>1 | x&^(m0&m)<<1
+	x = x&(m1&m)>>2 | x&^(m1&m)<<2
+	x = x&(m2&m)>>4 | x&^(m2&m)<<4
+	x = x&(m3&m)>>8 | x&^(m3&m)<<8
+	x = x&(m4&m)>>16 | x&^(m4&m)<<16
+	return x
+}
 
 // Reverse64 returns the value of x with its bits in reversed order.
-func Reverse64(x uint64) uint64 { return uint64(rev(uint64(x), 64)) }
+func Reverse64(x uint64) uint64 {
+	const m = 0xffffffffffffffff
+	x = x&(m0&m)>>1 | x&^(m0&m)<<1
+	x = x&(m1&m)>>2 | x&^(m1&m)<<2
+	x = x&(m2&m)>>4 | x&^(m2&m)<<4
+	x = x&(m3&m)>>8 | x&^(m3&m)<<8
+	x = x&(m4&m)>>16 | x&^(m4&m)<<16
+	x = x&(m5&m)>>32 | x&^(m5&m)<<32
+	return x
+}
 
 // --- ReverseBytes ---
 
diff --git a/src/math/bits/bits_impl.go b/src/math/bits/bits_impl.go
index 6f7a49b943..da38429fee 100644
--- a/src/math/bits/bits_impl.go
+++ b/src/math/bits/bits_impl.go
@@ -93,14 +93,6 @@ func rot(x uint64, size, k uint) uint64 {
 	return x<<k | x>>(size-k)&(1<<k-1)
 }
 
-func rev(x uint64, size uint) (r uint64) {
-	for i := size; i > 0; i-- {
-		r = r<<1 | x&1
-		x >>= 1
-	}
-	return
-}
-
 func swap(x uint64, size uint) (r uint64) {
 	for i := size / 8; i > 0; i-- {
 		r = r<<8 | x&0xff
diff --git a/src/math/bits/bits_test.go b/src/math/bits/bits_test.go
index b930300036..bba35612fe 100644
--- a/src/math/bits/bits_test.go
+++ b/src/math/bits/bits_test.go
@@ -367,6 +367,36 @@ func testReverse(t *testing.T, x64, want64 uint64) {
 	}
 }
 
+func BenchmarkReverse(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		Reverse(uint(i))
+	}
+}
+
+func BenchmarkReverse8(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		Reverse8(uint8(i))
+	}
+}
+
+func BenchmarkReverse16(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		Reverse16(uint16(i))
+	}
+}
+
+func BenchmarkReverse32(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		Reverse32(uint32(i))
+	}
+}
+
+func BenchmarkReverse64(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		Reverse64(uint64(i))
+	}
+}
+
 func TestReverseBytes(t *testing.T) {
 	for _, test := range []struct {
 		x, r uint64