aboutsummaryrefslogtreecommitdiff
path: root/libgo/go/compress
diff options
context:
space:
mode:
authorIan Lance Taylor <iant@golang.org>2017-09-14 17:11:35 +0000
committerIan Lance Taylor <ian@gcc.gnu.org>2017-09-14 17:11:35 +0000
commitbc998d034f45d1828a8663b2eed928faf22a7d01 (patch)
tree8d262a22ca7318f4bcd64269fe8fe9e45bcf8d0f /libgo/go/compress
parenta41a6142df74219f596e612d3a7775f68ca6e96f (diff)
downloadgcc-bc998d034f45d1828a8663b2eed928faf22a7d01.zip
gcc-bc998d034f45d1828a8663b2eed928faf22a7d01.tar.gz
gcc-bc998d034f45d1828a8663b2eed928faf22a7d01.tar.bz2
libgo: update to go1.9
Reviewed-on: https://go-review.googlesource.com/63753 From-SVN: r252767
Diffstat (limited to 'libgo/go/compress')
-rw-r--r--libgo/go/compress/bzip2/bzip2_test.go24
-rw-r--r--libgo/go/compress/bzip2/huffman.go4
-rw-r--r--libgo/go/compress/flate/huffman_code.go5
-rw-r--r--libgo/go/compress/flate/inflate.go7
-rw-r--r--libgo/go/compress/flate/reverse_bits.go48
-rw-r--r--libgo/go/compress/gzip/gzip.go5
-rw-r--r--libgo/go/compress/lzw/reader.go14
-rw-r--r--libgo/go/compress/lzw/reader_test.go97
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 {