// Copyright 2011 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 lzw
import (
"bytes"
"fmt"
"io"
"io/ioutil"
"math"
"runtime"
"strconv"
"strings"
"testing"
)
type lzwTest struct {
desc string
raw string
compressed string
err error
}
var lzwTests = []lzwTest{
{
"empty;LSB;8",
"",
"\x01\x01",
nil,
},
{
"empty;MSB;8",
"",
"\x80\x80",
nil,
},
{
"tobe;LSB;7",
"TOBEORNOTTOBEORTOBEORNOT",
"\x54\x4f\x42\x45\x4f\x52\x4e\x4f\x54\x82\x84\x86\x8b\x85\x87\x89\x81",
nil,
},
{
"tobe;LSB;8",
"TOBEORNOTTOBEORTOBEORNOT",
"\x54\x9e\x08\x29\xf2\x44\x8a\x93\x27\x54\x04\x12\x34\xb8\xb0\xe0\xc1\x84\x01\x01",
nil,
},
{
"tobe;MSB;7",
"TOBEORNOTTOBEORTOBEORNOT",
"\x54\x4f\x42\x45\x4f\x52\x4e\x4f\x54\x82\x84\x86\x8b\x85\x87\x89\x81",
nil,
},
{
"tobe;MSB;8",
"TOBEORNOTTOBEORTOBEORNOT",
"\x2a\x13\xc8\x44\x52\x79\x48\x9c\x4f\x2a\x40\xa0\x90\x68\x5c\x16\x0f\x09\x80\x80",
nil,
},
{
"tobe-truncated;LSB;8",
"TOBEORNOTTOBEORTOBEORNOT",
"\x54\x9e\x08\x29\xf2\x44\x8a\x93\x27\x54\x04",
io.ErrUnexpectedEOF,
},
// This example comes from http://en.wikipedia.org/wiki/Graphics_Interchange_Format.
{
"gif;LSB;8",
"\x28\xff\xff\xff\x28\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff",
"\x00\x51\xfc\x1b\x28\x70\xa0\xc1\x83\x01\x01",
nil,
},
// This example comes from http://compgroups.net/comp.lang.ruby/Decompressing-LZW-compression-from-PDF-file
{
"pdf;MSB;8",
"-----A---B",
"\x80\x0b\x60\x50\x22\x0c\x0c\x85\x01",
nil,
},
}
func TestReader(t *testing.T) {
var b bytes.Buffer
for _, tt := range lzwTests {
d := strings.Split(tt.desc, ";")
var order Order
switch d[1] {
case "LSB":
order = LSB
case "MSB":
order = MSB
default:
t.Errorf("%s: bad order %q", tt.desc, d[1])
}
litWidth, _ := strconv.Atoi(d[2])
rc := NewReader(strings.NewReader(tt.compressed), order, litWidth)
defer rc.Close()
b.Reset()
n, err := io.Copy(&b, rc)
s := b.String()
if err != nil {
if err != tt.err {
t.Errorf("%s: io.Copy: %v want %v", tt.desc, err, tt.err)
}
if err == io.ErrUnexpectedEOF {
// Even if the input is truncated, we should still return the
// partial decoded result.
if n == 0 || !strings.HasPrefix(tt.raw, s) {
t.Errorf("got %d bytes (%q), want a non-empty prefix of %q", n, s, tt.raw)
}
}
continue
}
if s != tt.raw {
t.Errorf("%s: got %d-byte %q want %d-byte %q", tt.desc, n, s, len(tt.raw), tt.raw)
}
}
}
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 {
b.Fatal(err)
}
if len(buf) == 0 {
b.Fatalf("test file has no data")
}
for e := 4; e <= 6; e++ {
n := int(math.Pow10(e))
b.Run(fmt.Sprint("1e", e), func(b *testing.B) {
b.StopTimer()
b.SetBytes(int64(n))
buf0 := buf
compressed := new(bytes.Buffer)
w := NewWriter(compressed, LSB, 8)
for i := 0; i < n; i += len(buf0) {
if len(buf0) > n-i {
buf0 = buf0[:n-i]
}
w.Write(buf0)
}
w.Close()
buf1 := compressed.Bytes()
buf0, compressed, w = nil, nil, nil
runtime.GC()
b.StartTimer()
for i := 0; i < b.N; i++ {
io.Copy(ioutil.Discard, NewReader(bytes.NewReader(buf1), LSB, 8))
}
})
}
}