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 // decoder is the state from which the readXxx method converts a byte 46 // stream into a code stream. 47 type decoder struct { 48 r io.ByteReader 49 bits uint32 50 nBits uint 51 width uint 52 read func(*decoder) (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 // overflow is the code at which hi overflows the code width. 61 // last is the most recently seen code, or decoderInvalidCode. 62 clear, eof, hi, overflow, last uint16 63 64 // Each code c in [lo, hi] expands to two or more bytes. For c != hi: 65 // suffix[c] is the last of these bytes. 66 // prefix[c] is the code for all but the last byte. 67 // This code can either be a literal code or another code in [lo, c). 68 // The c == hi case is a special case. 69 suffix [1 << maxWidth]uint8 70 prefix [1 << maxWidth]uint16 71 72 // output is the temporary output buffer. 73 // Literal codes are accumulated from the start of the buffer. 74 // Non-literal codes decode to a sequence of suffixes that are first 75 // written right-to-left from the end of the buffer before being copied 76 // to the start of the buffer. 77 // It is flushed when it contains >= 1<<maxWidth bytes, 78 // so that there is always room to decode an entire code. 79 output [2 * 1 << maxWidth]byte 80 o int // write index into output 81 toRead []byte // bytes to return from Read 82 } 83 84 // readLSB returns the next code for "Least Significant Bits first" data. 85 func (d *decoder) readLSB() (uint16, error) { 86 for d.nBits < d.width { 87 x, err := d.r.ReadByte() 88 if err != nil { 89 return 0, err 90 } 91 d.bits |= uint32(x) << d.nBits 92 d.nBits += 8 93 } 94 code := uint16(d.bits & (1<<d.width - 1)) 95 d.bits >>= d.width 96 d.nBits -= d.width 97 return code, nil 98 } 99 100 // readMSB returns the next code for "Most Significant Bits first" data. 101 func (d *decoder) readMSB() (uint16, error) { 102 for d.nBits < d.width { 103 x, err := d.r.ReadByte() 104 if err != nil { 105 return 0, err 106 } 107 d.bits |= uint32(x) << (24 - d.nBits) 108 d.nBits += 8 109 } 110 code := uint16(d.bits >> (32 - d.width)) 111 d.bits <<= d.width 112 d.nBits -= d.width 113 return code, nil 114 } 115 116 func (d *decoder) Read(b []byte) (int, error) { 117 for { 118 if len(d.toRead) > 0 { 119 n := copy(b, d.toRead) 120 d.toRead = d.toRead[n:] 121 return n, nil 122 } 123 if d.err != nil { 124 return 0, d.err 125 } 126 d.decode() 127 } 128 } 129 130 // decode decompresses bytes from r and leaves them in d.toRead. 131 // read specifies how to decode bytes into codes. 132 // litWidth is the width in bits of literal codes. 133 func (d *decoder) decode() { 134 // Loop over the code stream, converting codes into decompressed bytes. 135 loop: 136 for { 137 code, err := d.read(d) 138 if err != nil { 139 if err == io.EOF { 140 err = io.ErrUnexpectedEOF 141 } 142 d.err = err 143 break 144 } 145 switch { 146 case code < d.clear: 147 // We have a literal code. 148 d.output[d.o] = uint8(code) 149 d.o++ 150 if d.last != decoderInvalidCode { 151 // Save what the hi code expands to. 152 d.suffix[d.hi] = uint8(code) 153 d.prefix[d.hi] = d.last 154 } 155 case code == d.clear: 156 d.width = 1 + uint(d.litWidth) 157 d.hi = d.eof 158 d.overflow = 1 << d.width 159 d.last = decoderInvalidCode 160 continue 161 case code == d.eof: 162 d.err = io.EOF 163 break loop 164 case code <= d.hi: 165 c, i := code, len(d.output)-1 166 if code == d.hi { 167 // code == hi is a special case which expands to the last expansion 168 // followed by the head of the last expansion. To find the head, we walk 169 // the prefix chain until we find a literal code. 170 c = d.last 171 for c >= d.clear { 172 c = d.prefix[c] 173 } 174 d.output[i] = uint8(c) 175 i-- 176 c = d.last 177 } 178 // Copy the suffix chain into output and then write that to w. 179 for c >= d.clear { 180 d.output[i] = d.suffix[c] 181 i-- 182 c = d.prefix[c] 183 } 184 d.output[i] = uint8(c) 185 d.o += copy(d.output[d.o:], d.output[i:]) 186 if d.last != decoderInvalidCode { 187 // Save what the hi code expands to. 188 d.suffix[d.hi] = uint8(c) 189 d.prefix[d.hi] = d.last 190 } 191 default: 192 d.err = errors.New("lzw: invalid code") 193 break loop 194 } 195 d.last, d.hi = code, d.hi+1 196 if d.hi >= d.overflow { 197 if d.width == maxWidth { 198 d.last = decoderInvalidCode 199 } else { 200 d.width++ 201 d.overflow <<= 1 202 } 203 } 204 if d.o >= flushBuffer { 205 break 206 } 207 } 208 // Flush pending output. 209 d.toRead = d.output[:d.o] 210 d.o = 0 211 } 212 213 var errClosed = errors.New("lzw: reader/writer is closed") 214 215 func (d *decoder) Close() error { 216 d.err = errClosed // in case any Reads come along 217 return nil 218 } 219 220 // NewReader creates a new io.ReadCloser. 221 // Reads from the returned io.ReadCloser read and decompress data from r. 222 // If r does not also implement io.ByteReader, 223 // the decompressor may read more data than necessary from r. 224 // It is the caller's responsibility to call Close on the ReadCloser when 225 // finished reading. 226 // The number of bits to use for literal codes, litWidth, must be in the 227 // range [2,8] and is typically 8. It must equal the litWidth 228 // used during compression. 229 func NewReader(r io.Reader, order Order, litWidth int) io.ReadCloser { 230 d := new(decoder) 231 switch order { 232 case LSB: 233 d.read = (*decoder).readLSB 234 case MSB: 235 d.read = (*decoder).readMSB 236 default: 237 d.err = errors.New("lzw: unknown order") 238 return d 239 } 240 if litWidth < 2 || 8 < litWidth { 241 d.err = fmt.Errorf("lzw: litWidth %d out of range", litWidth) 242 return d 243 } 244 if br, ok := r.(io.ByteReader); ok { 245 d.r = br 246 } else { 247 d.r = bufio.NewReader(r) 248 } 249 d.litWidth = litWidth 250 d.width = 1 + uint(litWidth) 251 d.clear = uint16(1) << uint(litWidth) 252 d.eof, d.hi = d.clear+1, d.clear+1 253 d.overflow = uint16(1) << d.width 254 d.last = decoderInvalidCode 255 256 return d 257 } 258
