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