Update to current version of Go library (revision 94d654be2064).

From-SVN: r171076

4 files changed, 712 insertions, 0 deletions

diff --git a/libgo/go/compress/lzw/reader.go b/libgo/go/compress/lzw/reader.go
new file mode 100644
index 00000000000..8a540cbe6a1
--- /dev/null
+++ b/libgo/go/compress/lzw/reader.go
@@ -0,0 +1,210 @@
+// 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.
+
+// The lzw package implements the Lempel-Ziv-Welch compressed data format,
+// described in T. A. Welch, ``A Technique for High-Performance Data
+// Compression'', Computer, 17(6) (June 1984), pp 8-19.
+//
+// In particular, it implements LZW as used by the GIF, TIFF and PDF file
+// formats, which means variable-width codes up to 12 bits and the first
+// two non-literal codes are a clear code and an EOF code.
+package lzw
+
+// TODO(nigeltao): check that TIFF and PDF use LZW in the same way as GIF,
+// modulo LSB/MSB packing order.
+
+import (
+	"bufio"
+	"fmt"
+	"io"
+	"os"
+)
+
+// Order specifies the bit ordering in an LZW data stream.
+type Order int
+
+const (
+	// LSB means Least Significant Bits first, as used in the GIF file format.
+	LSB Order = iota
+	// MSB means Most Significant Bits first, as used in the TIFF and PDF
+	// file formats.
+	MSB
+)
+
+// decoder is the state from which the readXxx method converts a byte
+// stream into a code stream.
+type decoder struct {
+	r     io.ByteReader
+	bits  uint32
+	nBits uint
+	width uint
+}
+
+// readLSB returns the next code for "Least Significant Bits first" data.
+func (d *decoder) readLSB() (uint16, os.Error) {
+	for d.nBits < d.width {
+		x, err := d.r.ReadByte()
+		if err != nil {
+			return 0, err
+		}
+		d.bits |= uint32(x) << d.nBits
+		d.nBits += 8
+	}
+	code := uint16(d.bits & (1<<d.width - 1))
+	d.bits >>= d.width
+	d.nBits -= d.width
+	return code, nil
+}
+
+// readMSB returns the next code for "Most Significant Bits first" data.
+func (d *decoder) readMSB() (uint16, os.Error) {
+	for d.nBits < d.width {
+		x, err := d.r.ReadByte()
+		if err != nil {
+			return 0, err
+		}
+		d.bits |= uint32(x) << (24 - d.nBits)
+		d.nBits += 8
+	}
+	code := uint16(d.bits >> (32 - d.width))
+	d.bits <<= d.width
+	d.nBits -= d.width
+	return code, nil
+}
+
+// decode decompresses bytes from r and writes them to pw.
+// read specifies how to decode bytes into codes.
+// litWidth is the width in bits of literal codes.
+func decode(r io.Reader, read func(*decoder) (uint16, os.Error), litWidth int, pw *io.PipeWriter) {
+	br, ok := r.(io.ByteReader)
+	if !ok {
+		br = bufio.NewReader(r)
+	}
+	pw.CloseWithError(decode1(pw, br, read, uint(litWidth)))
+}
+
+func decode1(pw *io.PipeWriter, r io.ByteReader, read func(*decoder) (uint16, os.Error), litWidth uint) os.Error {
+	const (
+		maxWidth    = 12
+		invalidCode = 0xffff
+	)
+	d := decoder{r, 0, 0, 1 + litWidth}
+	w := bufio.NewWriter(pw)
+	// The first 1<<litWidth codes are literal codes.
+	// 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.
+	clear := uint16(1) << litWidth
+	eof, hi := clear+1, clear+1
+	// overflow is the code at which hi overflows the code width.
+	overflow := uint16(1) << d.width
+	var (
+		// Each code c in [lo, hi] expands to two or more bytes. For c != hi:
+		//   suffix[c] is the last of these bytes.
+		//   prefix[c] is the code for all but the last byte.
+		//   This code can either be a literal code or another code in [lo, c).
+		// The c == hi case is a special case.
+		suffix [1 << maxWidth]uint8
+		prefix [1 << maxWidth]uint16
+		// buf is a scratch buffer for reconstituting the bytes that a code expands to.
+		// Code suffixes are written right-to-left from the end of the buffer.
+		buf [1 << maxWidth]byte
+	)
+
+	// Loop over the code stream, converting codes into decompressed bytes.
+	last := uint16(invalidCode)
+	for {
+		code, err := read(&d)
+		if err != nil {
+			if err == os.EOF {
+				err = io.ErrUnexpectedEOF
+			}
+			return err
+		}
+		switch {
+		case code < clear:
+			// We have a literal code.
+			if err := w.WriteByte(uint8(code)); err != nil {
+				return err
+			}
+			if last != invalidCode {
+				// Save what the hi code expands to.
+				suffix[hi] = uint8(code)
+				prefix[hi] = last
+			}
+		case code == clear:
+			d.width = 1 + litWidth
+			hi = eof
+			overflow = 1 << d.width
+			last = invalidCode
+			continue
+		case code == eof:
+			return w.Flush()
+		case code <= hi:
+			c, i := code, len(buf)-1
+			if code == hi {
+				// 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.
+				c = last
+				for c >= clear {
+					c = prefix[c]
+				}
+				buf[i] = uint8(c)
+				i--
+				c = last
+			}
+			// Copy the suffix chain into buf and then write that to w.
+			for c >= clear {
+				buf[i] = suffix[c]
+				i--
+				c = prefix[c]
+			}
+			buf[i] = uint8(c)
+			if _, err := w.Write(buf[i:]); err != nil {
+				return err
+			}
+			// Save what the hi code expands to.
+			suffix[hi] = uint8(c)
+			prefix[hi] = last
+		default:
+			return os.NewError("lzw: invalid code")
+		}
+		last, hi = code, hi+1
+		if hi == overflow {
+			if d.width == maxWidth {
+				return os.NewError("lzw: missing clear code")
+			}
+			d.width++
+			overflow <<= 1
+		}
+	}
+	panic("unreachable")
+}
+
+// NewReader creates a new io.ReadCloser that satisfies reads by decompressing
+// the data read from r.
+// It is the caller's responsibility to call Close on the ReadCloser when
+// finished reading.
+// The number of bits to use for literal codes, litWidth, must be in the
+// range [2,8] and is typically 8.
+func NewReader(r io.Reader, order Order, litWidth int) io.ReadCloser {
+	pr, pw := io.Pipe()
+	var read func(*decoder) (uint16, os.Error)
+	switch order {
+	case LSB:
+		read = (*decoder).readLSB
+	case MSB:
+		read = (*decoder).readMSB
+	default:
+		pw.CloseWithError(os.NewError("lzw: unknown order"))
+		return pr
+	}
+	if litWidth < 2 || 8 < litWidth {
+		pw.CloseWithError(fmt.Errorf("lzw: litWidth %d out of range", litWidth))
+		return pr
+	}
+	go decode(r, read, litWidth, pw)
+	return pr
+}
diff --git a/libgo/go/compress/lzw/reader_test.go b/libgo/go/compress/lzw/reader_test.go
new file mode 100644
index 00000000000..7795a4c1489
--- /dev/null
+++ b/libgo/go/compress/lzw/reader_test.go
@@ -0,0 +1,132 @@
+// 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"
+	"io"
+	"io/ioutil"
+	"os"
+	"strconv"
+	"strings"
+	"testing"
+)
+
+type lzwTest struct {
+	desc       string
+	raw        string
+	compressed string
+	err        os.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) {
+	b := bytes.NewBuffer(nil)
+	for _, tt := range lzwTests {
+		d := strings.Split(tt.desc, ";", -1)
+		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)
+		if err != nil {
+			if err != tt.err {
+				t.Errorf("%s: io.Copy: %v want %v", tt.desc, err, tt.err)
+			}
+			continue
+		}
+		s := b.String()
+		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 devNull struct{}
+
+func (devNull) Write(p []byte) (int, os.Error) {
+	return len(p), nil
+}
+
+func BenchmarkDecoder(b *testing.B) {
+	b.StopTimer()
+	buf0, _ := ioutil.ReadFile("../testdata/e.txt")
+	compressed := bytes.NewBuffer(nil)
+	w := NewWriter(compressed, LSB, 8)
+	io.Copy(w, bytes.NewBuffer(buf0))
+	w.Close()
+	buf1 := compressed.Bytes()
+	b.StartTimer()
+	for i := 0; i < b.N; i++ {
+		io.Copy(devNull{}, NewReader(bytes.NewBuffer(buf1), LSB, 8))
+	}
+}
diff --git a/libgo/go/compress/lzw/writer.go b/libgo/go/compress/lzw/writer.go
new file mode 100644
index 00000000000..87143b7aa94
--- /dev/null
+++ b/libgo/go/compress/lzw/writer.go
@@ -0,0 +1,259 @@
+// 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 (
+	"bufio"
+	"fmt"
+	"io"
+	"os"
+)
+
+// A writer is a buffered, flushable writer.
+type writer interface {
+	WriteByte(byte) os.Error
+	Flush() os.Error
+}
+
+// An errWriteCloser is an io.WriteCloser that always returns a given error.
+type errWriteCloser struct {
+	err os.Error
+}
+
+func (e *errWriteCloser) Write([]byte) (int, os.Error) {
+	return 0, e.err
+}
+
+func (e *errWriteCloser) Close() os.Error {
+	return e.err
+}
+
+const (
+	// A code is a 12 bit value, stored as a uint32 when encoding to avoid
+	// type conversions when shifting bits.
+	maxCode     = 1<<12 - 1
+	invalidCode = 1<<32 - 1
+	// There are 1<<12 possible codes, which is an upper bound on the number of
+	// valid hash table entries at any given point in time. tableSize is 4x that.
+	tableSize = 4 * 1 << 12
+	tableMask = tableSize - 1
+	// A hash table entry is a uint32. Zero is an invalid entry since the
+	// lower 12 bits of a valid entry must be a non-literal code.
+	invalidEntry = 0
+)
+
+// encoder is LZW compressor.
+type encoder struct {
+	// w is the writer that compressed bytes are written to.
+	w writer
+	// write, bits, nBits and width are the state for converting a code stream
+	// into a byte stream.
+	write func(*encoder, uint32) os.Error
+	bits  uint32
+	nBits uint
+	width uint
+	// litWidth is the width in bits of literal codes.
+	litWidth uint
+	// hi is the code implied by the next code emission.
+	// overflow is the code at which hi overflows the code width.
+	hi, overflow uint32
+	// savedCode is the accumulated code at the end of the most recent Write
+	// call. It is equal to invalidCode if there was no such call.
+	savedCode uint32
+	// err is the first error encountered during writing. Closing the encoder
+	// will make any future Write calls return os.EINVAL.
+	err os.Error
+	// table is the hash table from 20-bit keys to 12-bit values. Each table
+	// entry contains key<<12|val and collisions resolve by linear probing.
+	// The keys consist of a 12-bit code prefix and an 8-bit byte suffix.
+	// The values are a 12-bit code.
+	table [tableSize]uint32
+}
+
+// writeLSB writes the code c for "Least Significant Bits first" data.
+func (e *encoder) writeLSB(c uint32) os.Error {
+	e.bits |= c << e.nBits
+	e.nBits += e.width
+	for e.nBits >= 8 {
+		if err := e.w.WriteByte(uint8(e.bits)); err != nil {
+			return err
+		}
+		e.bits >>= 8
+		e.nBits -= 8
+	}
+	return nil
+}
+
+// writeMSB writes the code c for "Most Significant Bits first" data.
+func (e *encoder) writeMSB(c uint32) os.Error {
+	e.bits |= c << (32 - e.width - e.nBits)
+	e.nBits += e.width
+	for e.nBits >= 8 {
+		if err := e.w.WriteByte(uint8(e.bits >> 24)); err != nil {
+			return err
+		}
+		e.bits <<= 8
+		e.nBits -= 8
+	}
+	return nil
+}
+
+// errOutOfCodes is an internal error that means that the encoder has run out
+// of unused codes and a clear code needs to be sent next.
+var errOutOfCodes = os.NewError("lzw: out of codes")
+
+// incHi increments e.hi and checks for both overflow and running out of
+// unused codes. In the latter case, incHi sends a clear code, resets the
+// encoder state and returns errOutOfCodes.
+func (e *encoder) incHi() os.Error {
+	e.hi++
+	if e.hi == e.overflow {
+		e.width++
+		e.overflow <<= 1
+	}
+	if e.hi == maxCode {
+		clear := uint32(1) << e.litWidth
+		if err := e.write(e, clear); err != nil {
+			return err
+		}
+		e.width = uint(e.litWidth) + 1
+		e.hi = clear + 1
+		e.overflow = clear << 1
+		for i := range e.table {
+			e.table[i] = invalidEntry
+		}
+		return errOutOfCodes
+	}
+	return nil
+}
+
+// Write writes a compressed representation of p to e's underlying writer.
+func (e *encoder) Write(p []byte) (int, os.Error) {
+	if e.err != nil {
+		return 0, e.err
+	}
+	if len(p) == 0 {
+		return 0, nil
+	}
+	litMask := uint32(1<<e.litWidth - 1)
+	code := e.savedCode
+	if code == invalidCode {
+		// The first code sent is always a literal code.
+		code, p = uint32(p[0])&litMask, p[1:]
+	}
+loop:
+	for _, x := range p {
+		literal := uint32(x) & litMask
+		key := code<<8 | literal
+		// If there is a hash table hit for this key then we continue the loop
+		// and do not emit a code yet.
+		hash := (key>>12 ^ key) & tableMask
+		for h, t := hash, e.table[hash]; t != invalidEntry; {
+			if key == t>>12 {
+				code = t & maxCode
+				continue loop
+			}
+			h = (h + 1) & tableMask
+			t = e.table[h]
+		}
+		// Otherwise, write the current code, and literal becomes the start of
+		// the next emitted code.
+		if e.err = e.write(e, code); e.err != nil {
+			return 0, e.err
+		}
+		code = literal
+		// Increment e.hi, the next implied code. If we run out of codes, reset
+		// the encoder state (including clearing the hash table) and continue.
+		if err := e.incHi(); err != nil {
+			if err == errOutOfCodes {
+				continue
+			}
+			e.err = err
+			return 0, e.err
+		}
+		// Otherwise, insert key -> e.hi into the map that e.table represents.
+		for {
+			if e.table[hash] == invalidEntry {
+				e.table[hash] = (key << 12) | e.hi
+				break
+			}
+			hash = (hash + 1) & tableMask
+		}
+	}
+	e.savedCode = code
+	return len(p), nil
+}
+
+// Close closes the encoder, flushing any pending output. It does not close or
+// flush e's underlying writer.
+func (e *encoder) Close() os.Error {
+	if e.err != nil {
+		if e.err == os.EINVAL {
+			return nil
+		}
+		return e.err
+	}
+	// Make any future calls to Write return os.EINVAL.
+	e.err = os.EINVAL
+	// Write the savedCode if valid.
+	if e.savedCode != invalidCode {
+		if err := e.write(e, e.savedCode); err != nil {
+			return err
+		}
+		if err := e.incHi(); err != nil && err != errOutOfCodes {
+			return err
+		}
+	}
+	// Write the eof code.
+	eof := uint32(1)<<e.litWidth + 1
+	if err := e.write(e, eof); err != nil {
+		return err
+	}
+	// Write the final bits.
+	if e.nBits > 0 {
+		if e.write == (*encoder).writeMSB {
+			e.bits >>= 24
+		}
+		if err := e.w.WriteByte(uint8(e.bits)); err != nil {
+			return err
+		}
+	}
+	return e.w.Flush()
+}
+
+// NewWriter creates a new io.WriteCloser that satisfies writes by compressing
+// the data and writing it to w.
+// It is the caller's responsibility to call Close on the WriteCloser when
+// finished writing.
+// The number of bits to use for literal codes, litWidth, must be in the
+// range [2,8] and is typically 8.
+func NewWriter(w io.Writer, order Order, litWidth int) io.WriteCloser {
+	var write func(*encoder, uint32) os.Error
+	switch order {
+	case LSB:
+		write = (*encoder).writeLSB
+	case MSB:
+		write = (*encoder).writeMSB
+	default:
+		return &errWriteCloser{os.NewError("lzw: unknown order")}
+	}
+	if litWidth < 2 || 8 < litWidth {
+		return &errWriteCloser{fmt.Errorf("lzw: litWidth %d out of range", litWidth)}
+	}
+	bw, ok := w.(writer)
+	if !ok {
+		bw = bufio.NewWriter(w)
+	}
+	lw := uint(litWidth)
+	return &encoder{
+		w:         bw,
+		write:     write,
+		width:     1 + lw,
+		litWidth:  lw,
+		hi:        1<<lw + 1,
+		overflow:  1 << (lw + 1),
+		savedCode: invalidCode,
+	}
+}
diff --git a/libgo/go/compress/lzw/writer_test.go b/libgo/go/compress/lzw/writer_test.go
new file mode 100644
index 00000000000..715b974aa1e
--- /dev/null
+++ b/libgo/go/compress/lzw/writer_test.go
@@ -0,0 +1,111 @@
+// 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 (
+	"io"
+	"io/ioutil"
+	"os"
+	"testing"
+)
+
+var filenames = []string{
+	"../testdata/e.txt",
+	"../testdata/pi.txt",
+}
+
+// testFile tests that compressing and then decompressing the given file with
+// the given options yields equivalent bytes to the original file.
+func testFile(t *testing.T, fn string, order Order, litWidth int) {
+	// Read the file, as golden output.
+	golden, err := os.Open(fn, os.O_RDONLY, 0400)
+	if err != nil {
+		t.Errorf("%s (order=%d litWidth=%d): %v", fn, order, litWidth, err)
+		return
+	}
+	defer golden.Close()
+
+	// Read the file again, and push it through a pipe that compresses at the write end, and decompresses at the read end.
+	raw, err := os.Open(fn, os.O_RDONLY, 0400)
+	if err != nil {
+		t.Errorf("%s (order=%d litWidth=%d): %v", fn, order, litWidth, err)
+		return
+	}
+
+	piper, pipew := io.Pipe()
+	defer piper.Close()
+	go func() {
+		defer raw.Close()
+		defer pipew.Close()
+		lzww := NewWriter(pipew, order, litWidth)
+		defer lzww.Close()
+		var b [4096]byte
+		for {
+			n, err0 := raw.Read(b[:])
+			if err0 != nil && err0 != os.EOF {
+				t.Errorf("%s (order=%d litWidth=%d): %v", fn, order, litWidth, err0)
+				return
+			}
+			_, err1 := lzww.Write(b[:n])
+			if err1 == os.EPIPE {
+				// Fail, but do not report the error, as some other (presumably reportable) error broke the pipe.
+				return
+			}
+			if err1 != nil {
+				t.Errorf("%s (order=%d litWidth=%d): %v", fn, order, litWidth, err1)
+				return
+			}
+			if err0 == os.EOF {
+				break
+			}
+		}
+	}()
+	lzwr := NewReader(piper, order, litWidth)
+	defer lzwr.Close()
+
+	// Compare the two.
+	b0, err0 := ioutil.ReadAll(golden)
+	b1, err1 := ioutil.ReadAll(lzwr)
+	if err0 != nil {
+		t.Errorf("%s (order=%d litWidth=%d): %v", fn, order, litWidth, err0)
+		return
+	}
+	if err1 != nil {
+		t.Errorf("%s (order=%d litWidth=%d): %v", fn, order, litWidth, err1)
+		return
+	}
+	if len(b0) != len(b1) {
+		t.Errorf("%s (order=%d litWidth=%d): length mismatch %d versus %d", fn, order, litWidth, len(b0), len(b1))
+		return
+	}
+	for i := 0; i < len(b0); i++ {
+		if b0[i] != b1[i] {
+			t.Errorf("%s (order=%d litWidth=%d): mismatch at %d, 0x%02x versus 0x%02x\n", fn, order, litWidth, i, b0[i], b1[i])
+			return
+		}
+	}
+}
+
+func TestWriter(t *testing.T) {
+	for _, filename := range filenames {
+		for _, order := range [...]Order{LSB, MSB} {
+			// The test data "2.71828 etcetera" is ASCII text requiring at least 6 bits.
+			for _, litWidth := range [...]int{6, 7, 8} {
+				testFile(t, filename, order, litWidth)
+			}
+		}
+	}
+}
+
+func BenchmarkEncoder(b *testing.B) {
+	b.StopTimer()
+	buf, _ := ioutil.ReadFile("../testdata/e.txt")
+	b.StartTimer()
+	for i := 0; i < b.N; i++ {
+		w := NewWriter(devNull{}, LSB, 8)
+		w.Write(buf)
+		w.Close()
+	}
+}