reader.go 7.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272
  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. // Package lzw implements the Lempel-Ziv-Welch compressed data format,
  5. // described in T. A. Welch, ``A Technique for High-Performance Data
  6. // Compression'', Computer, 17(6) (June 1984), pp 8-19.
  7. //
  8. // In particular, it implements LZW as used by the TIFF file format, including
  9. // an "off by one" algorithmic difference when compared to standard LZW.
  10. package lzw // import "golang.org/x/image/tiff/lzw"
  11. /*
  12. This file was branched from src/pkg/compress/lzw/reader.go in the
  13. standard library. Differences from the original are marked with "NOTE".
  14. The tif_lzw.c file in the libtiff C library has this comment:
  15. ----
  16. The 5.0 spec describes a different algorithm than Aldus
  17. implements. Specifically, Aldus does code length transitions
  18. one code earlier than should be done (for real LZW).
  19. Earlier versions of this library implemented the correct
  20. LZW algorithm, but emitted codes in a bit order opposite
  21. to the TIFF spec. Thus, to maintain compatibility w/ Aldus
  22. we interpret MSB-LSB ordered codes to be images written w/
  23. old versions of this library, but otherwise adhere to the
  24. Aldus "off by one" algorithm.
  25. ----
  26. The Go code doesn't read (invalid) TIFF files written by old versions of
  27. libtiff, but the LZW algorithm in this package still differs from the one in
  28. Go's standard package library to accomodate this "off by one" in valid TIFFs.
  29. */
  30. import (
  31. "bufio"
  32. "errors"
  33. "fmt"
  34. "io"
  35. )
  36. // Order specifies the bit ordering in an LZW data stream.
  37. type Order int
  38. const (
  39. // LSB means Least Significant Bits first, as used in the GIF file format.
  40. LSB Order = iota
  41. // MSB means Most Significant Bits first, as used in the TIFF and PDF
  42. // file formats.
  43. MSB
  44. )
  45. const (
  46. maxWidth = 12
  47. decoderInvalidCode = 0xffff
  48. flushBuffer = 1 << maxWidth
  49. )
  50. // decoder is the state from which the readXxx method converts a byte
  51. // stream into a code stream.
  52. type decoder struct {
  53. r io.ByteReader
  54. bits uint32
  55. nBits uint
  56. width uint
  57. read func(*decoder) (uint16, error) // readLSB or readMSB
  58. litWidth int // width in bits of literal codes
  59. err error
  60. // The first 1<<litWidth codes are literal codes.
  61. // The next two codes mean clear and EOF.
  62. // Other valid codes are in the range [lo, hi] where lo := clear + 2,
  63. // with the upper bound incrementing on each code seen.
  64. // overflow is the code at which hi overflows the code width. NOTE: TIFF's LZW is "off by one".
  65. // last is the most recently seen code, or decoderInvalidCode.
  66. clear, eof, hi, overflow, last uint16
  67. // Each code c in [lo, hi] expands to two or more bytes. For c != hi:
  68. // suffix[c] is the last of these bytes.
  69. // prefix[c] is the code for all but the last byte.
  70. // This code can either be a literal code or another code in [lo, c).
  71. // The c == hi case is a special case.
  72. suffix [1 << maxWidth]uint8
  73. prefix [1 << maxWidth]uint16
  74. // output is the temporary output buffer.
  75. // Literal codes are accumulated from the start of the buffer.
  76. // Non-literal codes decode to a sequence of suffixes that are first
  77. // written right-to-left from the end of the buffer before being copied
  78. // to the start of the buffer.
  79. // It is flushed when it contains >= 1<<maxWidth bytes,
  80. // so that there is always room to decode an entire code.
  81. output [2 * 1 << maxWidth]byte
  82. o int // write index into output
  83. toRead []byte // bytes to return from Read
  84. }
  85. // readLSB returns the next code for "Least Significant Bits first" data.
  86. func (d *decoder) readLSB() (uint16, error) {
  87. for d.nBits < d.width {
  88. x, err := d.r.ReadByte()
  89. if err != nil {
  90. return 0, err
  91. }
  92. d.bits |= uint32(x) << d.nBits
  93. d.nBits += 8
  94. }
  95. code := uint16(d.bits & (1<<d.width - 1))
  96. d.bits >>= d.width
  97. d.nBits -= d.width
  98. return code, nil
  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. func (d *decoder) Read(b []byte) (int, error) {
  116. for {
  117. if len(d.toRead) > 0 {
  118. n := copy(b, d.toRead)
  119. d.toRead = d.toRead[n:]
  120. return n, nil
  121. }
  122. if d.err != nil {
  123. return 0, d.err
  124. }
  125. d.decode()
  126. }
  127. }
  128. // decode decompresses bytes from r and leaves them in d.toRead.
  129. // read specifies how to decode bytes into codes.
  130. // litWidth is the width in bits of literal codes.
  131. func (d *decoder) decode() {
  132. // Loop over the code stream, converting codes into decompressed bytes.
  133. loop:
  134. for {
  135. code, err := d.read(d)
  136. if err != nil {
  137. if err == io.EOF {
  138. err = io.ErrUnexpectedEOF
  139. }
  140. d.err = err
  141. break
  142. }
  143. switch {
  144. case code < d.clear:
  145. // We have a literal code.
  146. d.output[d.o] = uint8(code)
  147. d.o++
  148. if d.last != decoderInvalidCode {
  149. // Save what the hi code expands to.
  150. d.suffix[d.hi] = uint8(code)
  151. d.prefix[d.hi] = d.last
  152. }
  153. case code == d.clear:
  154. d.width = 1 + uint(d.litWidth)
  155. d.hi = d.eof
  156. d.overflow = 1 << d.width
  157. d.last = decoderInvalidCode
  158. continue
  159. case code == d.eof:
  160. d.err = io.EOF
  161. break loop
  162. case code <= d.hi:
  163. c, i := code, len(d.output)-1
  164. if code == d.hi {
  165. // code == hi is a special case which expands to the last expansion
  166. // followed by the head of the last expansion. To find the head, we walk
  167. // the prefix chain until we find a literal code.
  168. c = d.last
  169. for c >= d.clear {
  170. c = d.prefix[c]
  171. }
  172. d.output[i] = uint8(c)
  173. i--
  174. c = d.last
  175. }
  176. // Copy the suffix chain into output and then write that to w.
  177. for c >= d.clear {
  178. d.output[i] = d.suffix[c]
  179. i--
  180. c = d.prefix[c]
  181. }
  182. d.output[i] = uint8(c)
  183. d.o += copy(d.output[d.o:], d.output[i:])
  184. if d.last != decoderInvalidCode {
  185. // Save what the hi code expands to.
  186. d.suffix[d.hi] = uint8(c)
  187. d.prefix[d.hi] = d.last
  188. }
  189. default:
  190. d.err = errors.New("lzw: invalid code")
  191. break loop
  192. }
  193. d.last, d.hi = code, d.hi+1
  194. if d.hi+1 >= d.overflow { // NOTE: the "+1" is where TIFF's LZW differs from the standard algorithm.
  195. if d.width == maxWidth {
  196. d.last = decoderInvalidCode
  197. } else {
  198. d.width++
  199. d.overflow <<= 1
  200. }
  201. }
  202. if d.o >= flushBuffer {
  203. break
  204. }
  205. }
  206. // Flush pending output.
  207. d.toRead = d.output[:d.o]
  208. d.o = 0
  209. }
  210. var errClosed = errors.New("lzw: reader/writer is closed")
  211. func (d *decoder) Close() error {
  212. d.err = errClosed // in case any Reads come along
  213. return nil
  214. }
  215. // NewReader creates a new io.ReadCloser.
  216. // Reads from the returned io.ReadCloser read and decompress data from r.
  217. // If r does not also implement io.ByteReader,
  218. // the decompressor may read more data than necessary from r.
  219. // It is the caller's responsibility to call Close on the ReadCloser when
  220. // finished reading.
  221. // The number of bits to use for literal codes, litWidth, must be in the
  222. // range [2,8] and is typically 8. It must equal the litWidth
  223. // used during compression.
  224. func NewReader(r io.Reader, order Order, litWidth int) io.ReadCloser {
  225. d := new(decoder)
  226. switch order {
  227. case LSB:
  228. d.read = (*decoder).readLSB
  229. case MSB:
  230. d.read = (*decoder).readMSB
  231. default:
  232. d.err = errors.New("lzw: unknown order")
  233. return d
  234. }
  235. if litWidth < 2 || 8 < litWidth {
  236. d.err = fmt.Errorf("lzw: litWidth %d out of range", litWidth)
  237. return d
  238. }
  239. if br, ok := r.(io.ByteReader); ok {
  240. d.r = br
  241. } else {
  242. d.r = bufio.NewReader(r)
  243. }
  244. d.litWidth = litWidth
  245. d.width = 1 + uint(litWidth)
  246. d.clear = uint16(1) << uint(litWidth)
  247. d.eof, d.hi = d.clear+1, d.clear+1
  248. d.overflow = uint16(1) << d.width
  249. d.last = decoderInvalidCode
  250. return d
  251. }