libgo: update to go1.9

    
    Reviewed-on: https://go-review.googlesource.com/63753

From-SVN: r252767

8 files changed, 130 insertions, 74 deletions

diff --git a/libgo/go/compress/bzip2/bzip2_test.go b/libgo/go/compress/bzip2/bzip2_test.go
index 95fb1895..a6c3080 100644
--- a/libgo/go/compress/bzip2/bzip2_test.go
+++ b/libgo/go/compress/bzip2/bzip2_test.go
@@ -204,6 +204,12 @@ func TestMTF(t *testing.T) {
 	}
 }
 
+var (
+	digits = mustLoadFile("testdata/e.txt.bz2")
+	twain  = mustLoadFile("testdata/Mark.Twain-Tom.Sawyer.txt.bz2")
+	random = mustLoadFile("testdata/random.data.bz2")
+)
+
 func benchmarkDecode(b *testing.B, compressed []byte) {
 	// Determine the uncompressed size of testfile.
 	uncompressedSize, err := io.Copy(ioutil.Discard, NewReader(bytes.NewReader(compressed)))
@@ -221,18 +227,6 @@ func benchmarkDecode(b *testing.B, compressed []byte) {
 	}
 }
 
-func BenchmarkDecodeDigits(b *testing.B) {
-	digits := mustLoadFile("testdata/e.txt.bz2")
-	b.ResetTimer()
-	benchmarkDecode(b, digits)
-}
-func BenchmarkDecodeTwain(b *testing.B) {
-	twain := mustLoadFile("testdata/Mark.Twain-Tom.Sawyer.txt.bz2")
-	b.ResetTimer()
-	benchmarkDecode(b, twain)
-}
-func BenchmarkDecodeRand(b *testing.B) {
-	random := mustLoadFile("testdata/random.data.bz2")
-	b.ResetTimer()
-	benchmarkDecode(b, random)
-}
+func BenchmarkDecodeDigits(b *testing.B) { benchmarkDecode(b, digits) }
+func BenchmarkDecodeTwain(b *testing.B)  { benchmarkDecode(b, twain) }
+func BenchmarkDecodeRand(b *testing.B)   { benchmarkDecode(b, random) }
diff --git a/libgo/go/compress/bzip2/huffman.go b/libgo/go/compress/bzip2/huffman.go
index 9d574b9..dbba9a5 100644
--- a/libgo/go/compress/bzip2/huffman.go
+++ b/libgo/go/compress/bzip2/huffman.go
@@ -108,10 +108,6 @@ func newHuffmanTree(lengths []uint8) (huffmanTree, error) {
 	codes := huffmanCodes(make([]huffmanCode, len(lengths)))
 	for i := len(pairs) - 1; i >= 0; i-- {
 		if length > pairs[i].length {
-			// If the code length decreases we shift in order to
-			// zero any bits beyond the end of the code.
-			length >>= 32 - pairs[i].length
-			length <<= 32 - pairs[i].length
 			length = pairs[i].length
 		}
 		codes[i].code = code
diff --git a/libgo/go/compress/flate/huffman_code.go b/libgo/go/compress/flate/huffman_code.go
index bdcbd82..891537e 100644
--- a/libgo/go/compress/flate/huffman_code.go
+++ b/libgo/go/compress/flate/huffman_code.go
@@ -6,6 +6,7 @@ package flate
 
 import (
 	"math"
+	"math/bits"
 	"sort"
 )
 
@@ -342,3 +343,7 @@ func (s byFreq) Less(i, j int) bool {
 }
 
 func (s byFreq) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
+
+func reverseBits(number uint16, bitLength byte) uint16 {
+	return bits.Reverse16(number << (16 - bitLength))
+}
diff --git a/libgo/go/compress/flate/inflate.go b/libgo/go/compress/flate/inflate.go
index 9a8c4fc..faa33cc 100644
--- a/libgo/go/compress/flate/inflate.go
+++ b/libgo/go/compress/flate/inflate.go
@@ -10,6 +10,7 @@ package flate
 import (
 	"bufio"
 	"io"
+	mathbits "math/bits"
 	"strconv"
 	"sync"
 )
@@ -176,7 +177,7 @@ func (h *huffmanDecoder) init(bits []int) bool {
 		link := nextcode[huffmanChunkBits+1] >> 1
 		h.links = make([][]uint32, huffmanNumChunks-link)
 		for j := uint(link); j < huffmanNumChunks; j++ {
-			reverse := int(reverseByte[j>>8]) | int(reverseByte[j&0xff])<<8
+			reverse := int(mathbits.Reverse16(uint16(j)))
 			reverse >>= uint(16 - huffmanChunkBits)
 			off := j - uint(link)
 			if sanity && h.chunks[reverse] != 0 {
@@ -194,7 +195,7 @@ func (h *huffmanDecoder) init(bits []int) bool {
 		code := nextcode[n]
 		nextcode[n]++
 		chunk := uint32(i<<huffmanValueShift | n)
-		reverse := int(reverseByte[code>>8]) | int(reverseByte[code&0xff])<<8
+		reverse := int(mathbits.Reverse16(uint16(code)))
 		reverse >>= uint(16 - n)
 		if n <= huffmanChunkBits {
 			for off := reverse; off < len(h.chunks); off += 1 << uint(n) {
@@ -556,7 +557,7 @@ readLiteral:
 					return
 				}
 			}
-			dist = int(reverseByte[(f.b&0x1F)<<3])
+			dist = int(mathbits.Reverse8(uint8(f.b & 0x1F << 3)))
 			f.b >>= 5
 			f.nb -= 5
 		} else {
diff --git a/libgo/go/compress/flate/reverse_bits.go b/libgo/go/compress/flate/reverse_bits.go
deleted file mode 100644
index 6b22290..0000000
--- a/libgo/go/compress/flate/reverse_bits.go
+++ /dev/null
@@ -1,48 +0,0 @@
-// Copyright 2009 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.
-
-package flate
-
-var reverseByte = [256]byte{
-	0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
-	0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
-	0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
-	0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
-	0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
-	0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
-	0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
-	0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
-	0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
-	0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
-	0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
-	0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
-	0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
-	0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
-	0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
-	0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
-	0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
-	0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
-	0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
-	0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
-	0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
-	0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
-	0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
-	0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
-	0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
-	0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
-	0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
-	0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
-	0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
-	0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
-	0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
-	0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
-}
-
-func reverseUint16(v uint16) uint16 {
-	return uint16(reverseByte[v>>8]) | uint16(reverseByte[v&0xFF])<<8
-}
-
-func reverseBits(number uint16, bitLength byte) uint16 {
-	return reverseUint16(number << (16 - bitLength))
-}
diff --git a/libgo/go/compress/gzip/gzip.go b/libgo/go/compress/gzip/gzip.go
index aafb442..0cc44c5 100644
--- a/libgo/go/compress/gzip/gzip.go
+++ b/libgo/go/compress/gzip/gzip.go
@@ -222,8 +222,9 @@ func (z *Writer) Flush() error {
 	return z.err
 }
 
-// Close closes the Writer, flushing any unwritten data to the underlying
-// io.Writer, but does not close the underlying io.Writer.
+// Close closes the Writer by flushing any unwritten data to the underlying
+// io.Writer and writing the GZIP footer.
+// It does not close the underlying io.Writer.
 func (z *Writer) Close() error {
 	if z.err != nil {
 		return z.err
diff --git a/libgo/go/compress/lzw/reader.go b/libgo/go/compress/lzw/reader.go
index 9eef2b2..1be52d5 100644
--- a/libgo/go/compress/lzw/reader.go
+++ b/libgo/go/compress/lzw/reader.go
@@ -57,8 +57,14 @@ type decoder struct {
 	// The next two codes mean clear and EOF.
 	// Other valid codes are in the range [lo, hi] where lo := clear + 2,
 	// with the upper bound incrementing on each code seen.
-	// overflow is the code at which hi overflows the code width.
+	//
+	// overflow is the code at which hi overflows the code width. It always
+	// equals 1 << width.
+	//
 	// last is the most recently seen code, or decoderInvalidCode.
+	//
+	// An invariant is that
+	// (hi < overflow) || (hi == overflow && last == decoderInvalidCode)
 	clear, eof, hi, overflow, last uint16
 
 	// Each code c in [lo, hi] expands to two or more bytes. For c != hi:
@@ -163,7 +169,7 @@ loop:
 			break loop
 		case code <= d.hi:
 			c, i := code, len(d.output)-1
-			if code == d.hi {
+			if code == d.hi && d.last != decoderInvalidCode {
 				// code == hi is a special case which expands to the last expansion
 				// followed by the head of the last expansion. To find the head, we walk
 				// the prefix chain until we find a literal code.
@@ -196,6 +202,10 @@ loop:
 		if d.hi >= d.overflow {
 			if d.width == maxWidth {
 				d.last = decoderInvalidCode
+				// Undo the d.hi++ a few lines above, so that (1) we maintain
+				// the invariant that d.hi <= d.overflow, and (2) d.hi does not
+				// eventually overflow a uint16.
+				d.hi--
 			} else {
 				d.width++
 				d.overflow <<= 1
diff --git a/libgo/go/compress/lzw/reader_test.go b/libgo/go/compress/lzw/reader_test.go
index 6b9f9a3..f8974de 100644
--- a/libgo/go/compress/lzw/reader_test.go
+++ b/libgo/go/compress/lzw/reader_test.go
@@ -120,6 +120,103 @@ func TestReader(t *testing.T) {
 	}
 }
 
+type devZero struct{}
+
+func (devZero) Read(p []byte) (int, error) {
+	for i := range p {
+		p[i] = 0
+	}
+	return len(p), nil
+}
+
+func TestHiCodeDoesNotOverflow(t *testing.T) {
+	r := NewReader(devZero{}, LSB, 8)
+	d := r.(*decoder)
+	buf := make([]byte, 1024)
+	oldHi := uint16(0)
+	for i := 0; i < 100; i++ {
+		if _, err := io.ReadFull(r, buf); err != nil {
+			t.Fatalf("i=%d: %v", i, err)
+		}
+		// The hi code should never decrease.
+		if d.hi < oldHi {
+			t.Fatalf("i=%d: hi=%d decreased from previous value %d", i, d.hi, oldHi)
+		}
+		oldHi = d.hi
+	}
+}
+
+// TestNoLongerSavingPriorExpansions tests the decoder state when codes other
+// than clear codes continue to be seen after decoder.hi and decoder.width
+// reach their maximum values (4095 and 12), i.e. after we no longer save prior
+// expansions. In particular, it tests seeing the highest possible code, 4095.
+func TestNoLongerSavingPriorExpansions(t *testing.T) {
+	// Iterations is used to calculate how many input bits are needed to get
+	// the decoder.hi and decoder.width values up to their maximum.
+	iterations := []struct {
+		width, n int
+	}{
+		// The final term is 257, not 256, as NewReader initializes d.hi to
+		// d.clear+1 and the clear code is 256.
+		{9, 512 - 257},
+		{10, 1024 - 512},
+		{11, 2048 - 1024},
+		{12, 4096 - 2048},
+	}
+	nCodes, nBits := 0, 0
+	for _, e := range iterations {
+		nCodes += e.n
+		nBits += e.n * e.width
+	}
+	if nCodes != 3839 {
+		t.Fatalf("nCodes: got %v, want %v", nCodes, 3839)
+	}
+	if nBits != 43255 {
+		t.Fatalf("nBits: got %v, want %v", nBits, 43255)
+	}
+
+	// Construct our input of 43255 zero bits (which gets d.hi and d.width up
+	// to 4095 and 12), followed by 0xfff (4095) as 12 bits, followed by 0x101
+	// (EOF) as 12 bits.
+	//
+	// 43255 = 5406*8 + 7, and codes are read in LSB order. The final bytes are
+	// therefore:
+	//
+	// xwwwwwww xxxxxxxx yyyyyxxx zyyyyyyy
+	// 10000000 11111111 00001111 00001000
+	//
+	// or split out:
+	//
+	// .0000000 ........ ........ ........   w = 0x000
+	// 1....... 11111111 .....111 ........   x = 0xfff
+	// ........ ........ 00001... .0001000   y = 0x101
+	//
+	// The 12 'w' bits (not all are shown) form the 3839'th code, with value
+	// 0x000. Just after decoder.read returns that code, d.hi == 4095 and
+	// d.last == 0.
+	//
+	// The 12 'x' bits form the 3840'th code, with value 0xfff or 4095. Just
+	// after decoder.read returns that code, d.hi == 4095 and d.last ==
+	// decoderInvalidCode.
+	//
+	// The 12 'y' bits form the 3841'st code, with value 0x101, the EOF code.
+	//
+	// The 'z' bit is unused.
+	in := make([]byte, 5406)
+	in = append(in, 0x80, 0xff, 0x0f, 0x08)
+
+	r := NewReader(bytes.NewReader(in), LSB, 8)
+	nDecoded, err := io.Copy(ioutil.Discard, r)
+	if err != nil {
+		t.Fatalf("Copy: %v", err)
+	}
+	// nDecoded should be 3841: 3839 literal codes and then 2 decoded bytes
+	// from 1 non-literal code. The EOF code contributes 0 decoded bytes.
+	if nDecoded != int64(nCodes+2) {
+		t.Fatalf("nDecoded: got %v, want %v", nDecoded, nCodes+2)
+	}
+}
+
 func BenchmarkDecoder(b *testing.B) {
 	buf, err := ioutil.ReadFile("../testdata/e.txt")
 	if err != nil {