reader.go

Documentation: compress/lzw

		 1  // Copyright 2011 The Go Authors. All rights reserved.
		 2  // Use of this source code is governed by a BSD-style
		 3  // license that can be found in the LICENSE file.
		 4  
		 5  // Package lzw implements the Lempel-Ziv-Welch compressed data format,
		 6  // described in T. A. Welch, ``A Technique for High-Performance Data
		 7  // Compression'', Computer, 17(6) (June 1984), pp 8-19.
		 8  //
		 9  // In particular, it implements LZW as used by the GIF and PDF file
		10  // formats, which means variable-width codes up to 12 bits and the first
		11  // two non-literal codes are a clear code and an EOF code.
		12  //
		13  // The TIFF file format uses a similar but incompatible version of the LZW
		14  // algorithm. See the golang.org/x/image/tiff/lzw package for an
		15  // implementation.
		16  package lzw
		17  
		18  // TODO(nigeltao): check that PDF uses LZW in the same way as GIF,
		19  // modulo LSB/MSB packing order.
		20  
		21  import (
		22  	"bufio"
		23  	"errors"
		24  	"fmt"
		25  	"io"
		26  )
		27  
		28  // Order specifies the bit ordering in an LZW data stream.
		29  type Order int
		30  
		31  const (
		32  	// LSB means Least Significant Bits first, as used in the GIF file format.
		33  	LSB Order = iota
		34  	// MSB means Most Significant Bits first, as used in the TIFF and PDF
		35  	// file formats.
		36  	MSB
		37  )
		38  
		39  const (
		40  	maxWidth					 = 12
		41  	decoderInvalidCode = 0xffff
		42  	flushBuffer				= 1 << maxWidth
		43  )
		44  
		45  // Reader is an io.Reader which can be used to read compressed data in the
		46  // LZW format.
		47  type Reader struct {
		48  	r				io.ByteReader
		49  	bits		 uint32
		50  	nBits		uint
		51  	width		uint
		52  	read		 func(*Reader) (uint16, error) // readLSB or readMSB
		53  	litWidth int													 // width in bits of literal codes
		54  	err			error
		55  
		56  	// The first 1<<litWidth codes are literal codes.
		57  	// The next two codes mean clear and EOF.
		58  	// Other valid codes are in the range [lo, hi] where lo := clear + 2,
		59  	// with the upper bound incrementing on each code seen.
		60  	//
		61  	// overflow is the code at which hi overflows the code width. It always
		62  	// equals 1 << width.
		63  	//
		64  	// last is the most recently seen code, or decoderInvalidCode.
		65  	//
		66  	// An invariant is that hi < overflow.
		67  	clear, eof, hi, overflow, last uint16
		68  
		69  	// Each code c in [lo, hi] expands to two or more bytes. For c != hi:
		70  	//	 suffix[c] is the last of these bytes.
		71  	//	 prefix[c] is the code for all but the last byte.
		72  	//	 This code can either be a literal code or another code in [lo, c).
		73  	// The c == hi case is a special case.
		74  	suffix [1 << maxWidth]uint8
		75  	prefix [1 << maxWidth]uint16
		76  
		77  	// output is the temporary output buffer.
		78  	// Literal codes are accumulated from the start of the buffer.
		79  	// Non-literal codes decode to a sequence of suffixes that are first
		80  	// written right-to-left from the end of the buffer before being copied
		81  	// to the start of the buffer.
		82  	// It is flushed when it contains >= 1<<maxWidth bytes,
		83  	// so that there is always room to decode an entire code.
		84  	output [2 * 1 << maxWidth]byte
		85  	o			int		// write index into output
		86  	toRead []byte // bytes to return from Read
		87  }
		88  
		89  // readLSB returns the next code for "Least Significant Bits first" data.
		90  func (r *Reader) readLSB() (uint16, error) {
		91  	for r.nBits < r.width {
		92  		x, err := r.r.ReadByte()
		93  		if err != nil {
		94  			return 0, err
		95  		}
		96  		r.bits |= uint32(x) << r.nBits
		97  		r.nBits += 8
		98  	}
		99  	code := uint16(r.bits & (1<<r.width - 1))
	 100  	r.bits >>= r.width
	 101  	r.nBits -= r.width
	 102  	return code, nil
	 103  }
	 104  
	 105  // readMSB returns the next code for "Most Significant Bits first" data.
	 106  func (r *Reader) readMSB() (uint16, error) {
	 107  	for r.nBits < r.width {
	 108  		x, err := r.r.ReadByte()
	 109  		if err != nil {
	 110  			return 0, err
	 111  		}
	 112  		r.bits |= uint32(x) << (24 - r.nBits)
	 113  		r.nBits += 8
	 114  	}
	 115  	code := uint16(r.bits >> (32 - r.width))
	 116  	r.bits <<= r.width
	 117  	r.nBits -= r.width
	 118  	return code, nil
	 119  }
	 120  
	 121  // Read implements io.Reader, reading uncompressed bytes from its underlying Reader.
	 122  func (r *Reader) Read(b []byte) (int, error) {
	 123  	for {
	 124  		if len(r.toRead) > 0 {
	 125  			n := copy(b, r.toRead)
	 126  			r.toRead = r.toRead[n:]
	 127  			return n, nil
	 128  		}
	 129  		if r.err != nil {
	 130  			return 0, r.err
	 131  		}
	 132  		r.decode()
	 133  	}
	 134  }
	 135  
	 136  // decode decompresses bytes from r and leaves them in d.toRead.
	 137  // read specifies how to decode bytes into codes.
	 138  // litWidth is the width in bits of literal codes.
	 139  func (r *Reader) decode() {
	 140  	// Loop over the code stream, converting codes into decompressed bytes.
	 141  loop:
	 142  	for {
	 143  		code, err := r.read(r)
	 144  		if err != nil {
	 145  			if err == io.EOF {
	 146  				err = io.ErrUnexpectedEOF
	 147  			}
	 148  			r.err = err
	 149  			break
	 150  		}
	 151  		switch {
	 152  		case code < r.clear:
	 153  			// We have a literal code.
	 154  			r.output[r.o] = uint8(code)
	 155  			r.o++
	 156  			if r.last != decoderInvalidCode {
	 157  				// Save what the hi code expands to.
	 158  				r.suffix[r.hi] = uint8(code)
	 159  				r.prefix[r.hi] = r.last
	 160  			}
	 161  		case code == r.clear:
	 162  			r.width = 1 + uint(r.litWidth)
	 163  			r.hi = r.eof
	 164  			r.overflow = 1 << r.width
	 165  			r.last = decoderInvalidCode
	 166  			continue
	 167  		case code == r.eof:
	 168  			r.err = io.EOF
	 169  			break loop
	 170  		case code <= r.hi:
	 171  			c, i := code, len(r.output)-1
	 172  			if code == r.hi && r.last != decoderInvalidCode {
	 173  				// code == hi is a special case which expands to the last expansion
	 174  				// followed by the head of the last expansion. To find the head, we walk
	 175  				// the prefix chain until we find a literal code.
	 176  				c = r.last
	 177  				for c >= r.clear {
	 178  					c = r.prefix[c]
	 179  				}
	 180  				r.output[i] = uint8(c)
	 181  				i--
	 182  				c = r.last
	 183  			}
	 184  			// Copy the suffix chain into output and then write that to w.
	 185  			for c >= r.clear {
	 186  				r.output[i] = r.suffix[c]
	 187  				i--
	 188  				c = r.prefix[c]
	 189  			}
	 190  			r.output[i] = uint8(c)
	 191  			r.o += copy(r.output[r.o:], r.output[i:])
	 192  			if r.last != decoderInvalidCode {
	 193  				// Save what the hi code expands to.
	 194  				r.suffix[r.hi] = uint8(c)
	 195  				r.prefix[r.hi] = r.last
	 196  			}
	 197  		default:
	 198  			r.err = errors.New("lzw: invalid code")
	 199  			break loop
	 200  		}
	 201  		r.last, r.hi = code, r.hi+1
	 202  		if r.hi >= r.overflow {
	 203  			if r.hi > r.overflow {
	 204  				panic("unreachable")
	 205  			}
	 206  			if r.width == maxWidth {
	 207  				r.last = decoderInvalidCode
	 208  				// Undo the d.hi++ a few lines above, so that (1) we maintain
	 209  				// the invariant that d.hi < d.overflow, and (2) d.hi does not
	 210  				// eventually overflow a uint16.
	 211  				r.hi--
	 212  			} else {
	 213  				r.width++
	 214  				r.overflow = 1 << r.width
	 215  			}
	 216  		}
	 217  		if r.o >= flushBuffer {
	 218  			break
	 219  		}
	 220  	}
	 221  	// Flush pending output.
	 222  	r.toRead = r.output[:r.o]
	 223  	r.o = 0
	 224  }
	 225  
	 226  var errClosed = errors.New("lzw: reader/writer is closed")
	 227  
	 228  // Close closes the Reader and returns an error for any future read operation.
	 229  // It does not close the underlying io.Reader.
	 230  func (r *Reader) Close() error {
	 231  	r.err = errClosed // in case any Reads come along
	 232  	return nil
	 233  }
	 234  
	 235  // Reset clears the Reader's state and allows it to be reused again
	 236  // as a new Reader.
	 237  func (r *Reader) Reset(src io.Reader, order Order, litWidth int) {
	 238  	*r = Reader{}
	 239  	r.init(src, order, litWidth)
	 240  }
	 241  
	 242  // NewReader creates a new io.ReadCloser.
	 243  // Reads from the returned io.ReadCloser read and decompress data from r.
	 244  // If r does not also implement io.ByteReader,
	 245  // the decompressor may read more data than necessary from r.
	 246  // It is the caller's responsibility to call Close on the ReadCloser when
	 247  // finished reading.
	 248  // The number of bits to use for literal codes, litWidth, must be in the
	 249  // range [2,8] and is typically 8. It must equal the litWidth
	 250  // used during compression.
	 251  //
	 252  // It is guaranteed that the underlying type of the returned io.ReadCloser
	 253  // is a *Reader.
	 254  func NewReader(r io.Reader, order Order, litWidth int) io.ReadCloser {
	 255  	return newReader(r, order, litWidth)
	 256  }
	 257  
	 258  func newReader(src io.Reader, order Order, litWidth int) *Reader {
	 259  	r := new(Reader)
	 260  	r.init(src, order, litWidth)
	 261  	return r
	 262  }
	 263  
	 264  func (r *Reader) init(src io.Reader, order Order, litWidth int) {
	 265  	switch order {
	 266  	case LSB:
	 267  		r.read = (*Reader).readLSB
	 268  	case MSB:
	 269  		r.read = (*Reader).readMSB
	 270  	default:
	 271  		r.err = errors.New("lzw: unknown order")
	 272  		return
	 273  	}
	 274  	if litWidth < 2 || 8 < litWidth {
	 275  		r.err = fmt.Errorf("lzw: litWidth %d out of range", litWidth)
	 276  		return
	 277  	}
	 278  
	 279  	br, ok := src.(io.ByteReader)
	 280  	if !ok && src != nil {
	 281  		br = bufio.NewReader(src)
	 282  	}
	 283  	r.r = br
	 284  	r.litWidth = litWidth
	 285  	r.width = 1 + uint(litWidth)
	 286  	r.clear = uint16(1) << uint(litWidth)
	 287  	r.eof, r.hi = r.clear+1, r.clear+1
	 288  	r.overflow = uint16(1) << r.width
	 289  	r.last = decoderInvalidCode
	 290  }
	 291
View as plain text