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 for { 136 code, err := d.read(d) 137 if err != nil { 138 if err == io.EOF { 139 err = io.ErrUnexpectedEOF 140 } 141 d.err = err 142 d.flush() 143 return 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.flush() 163 d.err = io.EOF 164 return 165 case code <= d.hi: 166 c, i := code, len(d.output)-1 167 if code == d.hi { 168 // code == hi is a special case which expands to the last expansion 169 // followed by the head of the last expansion. To find the head, we walk 170 // the prefix chain until we find a literal code. 171 c = d.last 172 for c >= d.clear { 173 c = d.prefix[c] 174 } 175 d.output[i] = uint8(c) 176 i-- 177 c = d.last 178 } 179 // Copy the suffix chain into output and then write that to w. 180 for c >= d.clear { 181 d.output[i] = d.suffix[c] 182 i-- 183 c = d.prefix[c] 184 } 185 d.output[i] = uint8(c) 186 d.o += copy(d.output[d.o:], d.output[i:]) 187 if d.last != decoderInvalidCode { 188 // Save what the hi code expands to. 189 d.suffix[d.hi] = uint8(c) 190 d.prefix[d.hi] = d.last 191 } 192 default: 193 d.err = errors.New("lzw: invalid code") 194 d.flush() 195 return 196 } 197 d.last, d.hi = code, d.hi+1 198 if d.hi >= d.overflow { 199 if d.width == maxWidth { 200 d.last = decoderInvalidCode 201 } else { 202 d.width++ 203 d.overflow <<= 1 204 } 205 } 206 if d.o >= flushBuffer { 207 d.flush() 208 return 209 } 210 } 211 } 212 213 func (d *decoder) flush() { 214 d.toRead = d.output[:d.o] 215 d.o = 0 216 } 217 218 var errClosed = errors.New("lzw: reader/writer is closed") 219 220 func (d *decoder) Close() error { 221 d.err = errClosed // in case any Reads come along 222 return nil 223 } 224 225 // NewReader creates a new io.ReadCloser. 226 // Reads from the returned io.ReadCloser read and decompress data from r. 227 // If r does not also implement io.ByteReader, 228 // the decompressor may read more data than necessary from r. 229 // It is the caller's responsibility to call Close on the ReadCloser when 230 // finished reading. 231 // The number of bits to use for literal codes, litWidth, must be in the 232 // range [2,8] and is typically 8. It must equal the litWidth 233 // used during compression. 234 func NewReader(r io.Reader, order Order, litWidth int) io.ReadCloser { 235 d := new(decoder) 236 switch order { 237 case LSB: 238 d.read = (*decoder).readLSB 239 case MSB: 240 d.read = (*decoder).readMSB 241 default: 242 d.err = errors.New("lzw: unknown order") 243 return d 244 } 245 if litWidth < 2 || 8 < litWidth { 246 d.err = fmt.Errorf("lzw: litWidth %d out of range", litWidth) 247 return d 248 } 249 if br, ok := r.(io.ByteReader); ok { 250 d.r = br 251 } else { 252 d.r = bufio.NewReader(r) 253 } 254 d.litWidth = litWidth 255 d.width = 1 + uint(litWidth) 256 d.clear = uint16(1) << uint(litWidth) 257 d.eof, d.hi = d.clear+1, d.clear+1 258 d.overflow = uint16(1) << d.width 259 d.last = decoderInvalidCode 260 261 return d 262 } 263
