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