// 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 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 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. // // The TIFF file format uses a similar but incompatible version of the LZW // algorithm. See the golang.org/x/image/tiff/lzw package for an // implementation.
package lzw // TODO(nigeltao): check that PDF uses LZW in the same way as GIF, // modulo LSB/MSB packing order. import ( ) // 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 ) const ( maxWidth = 12 decoderInvalidCode = 0xffff flushBuffer = 1 << maxWidth ) // 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 read func(*decoder) (uint16, error) // readLSB or readMSB litWidth int // width in bits of literal codes err error // 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. // // 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. clear, eof, hi, overflow, last uint16 // 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 // output is the temporary output buffer. // Literal codes are accumulated from the start of the buffer. // Non-literal codes decode to a sequence of suffixes that are first // written right-to-left from the end of the buffer before being copied // to the start of the buffer. // It is flushed when it contains >= 1<<maxWidth bytes, // so that there is always room to decode an entire code. output [2 * 1 << maxWidth]byte o int // write index into output toRead []byte // bytes to return from Read } // readLSB returns the next code for "Least Significant Bits first" data. func ( *decoder) () (uint16, error) { for .nBits < .width { , := .r.ReadByte() if != nil { return 0, } .bits |= uint32() << .nBits .nBits += 8 } := uint16(.bits & (1<<.width - 1)) .bits >>= .width .nBits -= .width return , nil } // readMSB returns the next code for "Most Significant Bits first" data. func ( *decoder) () (uint16, error) { for .nBits < .width { , := .r.ReadByte() if != nil { return 0, } .bits |= uint32() << (24 - .nBits) .nBits += 8 } := uint16(.bits >> (32 - .width)) .bits <<= .width .nBits -= .width return , nil } func ( *decoder) ( []byte) (int, error) { for { if len(.toRead) > 0 { := copy(, .toRead) .toRead = .toRead[:] return , nil } if .err != nil { return 0, .err } .decode() } } // decode decompresses bytes from r and leaves them in d.toRead. // read specifies how to decode bytes into codes. // litWidth is the width in bits of literal codes. func ( *decoder) () { // Loop over the code stream, converting codes into decompressed bytes. : for { , := .read() if != nil { if == io.EOF { = io.ErrUnexpectedEOF } .err = break } switch { case < .clear: // We have a literal code. .output[.o] = uint8() .o++ if .last != decoderInvalidCode { // Save what the hi code expands to. .suffix[.hi] = uint8() .prefix[.hi] = .last } case == .clear: .width = 1 + uint(.litWidth) .hi = .eof .overflow = 1 << .width .last = decoderInvalidCode continue case == .eof: .err = io.EOF break case <= .hi: , := , len(.output)-1 if == .hi && .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. = .last for >= .clear { = .prefix[] } .output[] = uint8() -- = .last } // Copy the suffix chain into output and then write that to w. for >= .clear { .output[] = .suffix[] -- = .prefix[] } .output[] = uint8() .o += copy(.output[.o:], .output[:]) if .last != decoderInvalidCode { // Save what the hi code expands to. .suffix[.hi] = uint8() .prefix[.hi] = .last } default: .err = errors.New("lzw: invalid code") break } .last, .hi = , .hi+1 if .hi >= .overflow { if .hi > .overflow { panic("unreachable") } if .width == maxWidth { .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. .hi-- } else { .width++ .overflow = 1 << .width } } if .o >= flushBuffer { break } } // Flush pending output. .toRead = .output[:.o] .o = 0 } var errClosed = errors.New("lzw: reader/writer is closed") func ( *decoder) () error { .err = errClosed // in case any Reads come along return nil } // NewReader creates a new io.ReadCloser. // Reads from the returned io.ReadCloser read and decompress data from r. // If r does not also implement io.ByteReader, // the decompressor may read more data than necessary 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. It must equal the litWidth // used during compression. func ( io.Reader, Order, int) io.ReadCloser { := new(decoder) switch { case LSB: .read = (*decoder).readLSB case MSB: .read = (*decoder).readMSB default: .err = errors.New("lzw: unknown order") return } if < 2 || 8 < { .err = fmt.Errorf("lzw: litWidth %d out of range", ) return } if , := .(io.ByteReader); { .r = } else { .r = bufio.NewReader() } .litWidth = .width = 1 + uint() .clear = uint16(1) << uint() .eof, .hi = .clear+1, .clear+1 .overflow = uint16(1) << .width .last = decoderInvalidCode return }