encoding/hex: implement Decode with a lookup table

Implement hex decode using a 256 byte lookup table instead of branching logic.

In happy flow, uses 3x 64 byte (or 5x 32 byte) cache lines.

	name             old time/op    new time/op    delta
	Decode/256-64       223ns ± 3%     135ns ± 2%  -39.64%  (p=0.000 n=8+8)
	Decode/1024-64      872ns ± 2%     512ns ± 2%  -41.25%  (p=0.000 n=8+8)
	Decode/4096-64     3.43µs ± 1%    2.01µs ± 2%  -41.31%  (p=0.001 n=7+7)
	Decode/16384-64    13.9µs ± 1%     8.0µs ± 1%  -42.69%  (p=0.000 n=8+7)

	name             old speed      new speed      delta
	Decode/256-64    1.15GB/s ± 3%  1.90GB/s ± 2%  +65.66%  (p=0.000 n=8+8)
	Decode/1024-64   1.17GB/s ± 2%  2.00GB/s ± 2%  +70.22%  (p=0.000 n=8+8)
	Decode/4096-64   1.20GB/s ± 1%  2.04GB/s ± 2%  +70.39%  (p=0.001 n=7+7)
	Decode/16384-64  1.18GB/s ± 1%  2.06GB/s ± 1%  +74.49%  (p=0.000 n=8+7)

Also reduces amd64 object size by 766 bytes, despite the extra RODATA due to removal of `fromHexChar()` and duplicated inlined versions of it and simplification of `Decode()`.

Change-Id: I0988c7a30562ec154eff11db6e27954e0ce2b611
GitHub-Last-Rev: 64818018afc83ab07ec128a46aaea6a16f11400e
GitHub-Pull-Request: golang/go#51432
Reviewed-on: https://go-review.googlesource.com/c/go/+/390037
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Daniel Martí <mvdan@mvdan.cc>
Trust: Daniel Martí <mvdan@mvdan.cc>
Run-TryBot: Daniel Martí <mvdan@mvdan.cc>
TryBot-Result: Gopher Robot <gobot@golang.org>

1 files changed, 32 insertions, 23 deletions

diff --git a/src/encoding/hex/hex.go b/src/encoding/hex/hex.go
index fbba78ffd2..375f583170 100644
--- a/src/encoding/hex/hex.go
+++ b/src/encoding/hex/hex.go
@@ -12,7 +12,26 @@ import (
 	"strings"
 )
 
-const hextable = "0123456789abcdef"
+const (
+	hextable        = "0123456789abcdef"
+	reverseHexTable = "" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\xff\xff\xff\xff\xff\xff" +
+		"\xff\x0a\x0b\x0c\x0d\x0e\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\x0a\x0b\x0c\x0d\x0e\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
+		"\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
+)
 
 // EncodedLen returns the length of an encoding of n source bytes.
 // Specifically, it returns n * 2.
@@ -58,13 +77,16 @@ func DecodedLen(x int) int { return x / 2 }
 func Decode(dst, src []byte) (int, error) {
 	i, j := 0, 1
 	for ; j < len(src); j += 2 {
-		a, ok := fromHexChar(src[j-1])
-		if !ok {
-			return i, InvalidByteError(src[j-1])
+		p := src[j-1]
+		q := src[j]
+
+		a := reverseHexTable[p]
+		b := reverseHexTable[q]
+		if a > 0x0f {
+			return i, InvalidByteError(p)
 		}
-		b, ok := fromHexChar(src[j])
-		if !ok {
-			return i, InvalidByteError(src[j])
+		if b > 0x0f {
+			return i, InvalidByteError(q)
 		}
 		dst[i] = (a << 4) | b
 		i++
@@ -72,7 +94,7 @@ func Decode(dst, src []byte) (int, error) {
 	if len(src)%2 == 1 {
 		// Check for invalid char before reporting bad length,
 		// since the invalid char (if present) is an earlier problem.
-		if _, ok := fromHexChar(src[j-1]); !ok {
+		if reverseHexTable[src[j-1]] > 0x0f {
 			return i, InvalidByteError(src[j-1])
 		}
 		return i, ErrLength
@@ -80,20 +102,6 @@ func Decode(dst, src []byte) (int, error) {
 	return i, nil
 }
 
-// fromHexChar converts a hex character into its value and a success flag.
-func fromHexChar(c byte) (byte, bool) {
-	switch {
-	case '0' <= c && c <= '9':
-		return c - '0', true
-	case 'a' <= c && c <= 'f':
-		return c - 'a' + 10, true
-	case 'A' <= c && c <= 'F':
-		return c - 'A' + 10, true
-	}
-
-	return 0, false
-}
-
 // EncodeToString returns the hexadecimal encoding of src.
 func EncodeToString(src []byte) string {
 	dst := make([]byte, EncodedLen(len(src)))
@@ -185,7 +193,8 @@ func (d *decoder) Read(p []byte) (n int, err error) {
 		numRead, d.err = d.r.Read(d.arr[numCopy:])
 		d.in = d.arr[:numCopy+numRead]
 		if d.err == io.EOF && len(d.in)%2 != 0 {
-			if _, ok := fromHexChar(d.in[len(d.in)-1]); !ok {
+
+			if a := reverseHexTable[d.in[len(d.in)-1]]; a > 0x0f {
 				d.err = InvalidByteError(d.in[len(d.in)-1])
 			} else {
 				d.err = io.ErrUnexpectedEOF