1// Copyright 2019 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//go:generate go run gen.go
6
7// Package ccitt implements a CCITT (fax) image decoder.
8package ccitt
9
10import (
11 "encoding/binary"
12 "errors"
13 "image"
14 "io"
15 "math/bits"
16)
17
18var (
19 errInvalidBounds = errors.New("ccitt: invalid bounds")
20 errInvalidCode = errors.New("ccitt: invalid code")
21 errInvalidMode = errors.New("ccitt: invalid mode")
22 errInvalidOffset = errors.New("ccitt: invalid offset")
23 errMissingEOL = errors.New("ccitt: missing End-of-Line")
24 errRunLengthOverflowsWidth = errors.New("ccitt: run length overflows width")
25 errRunLengthTooLong = errors.New("ccitt: run length too long")
26 errUnsupportedMode = errors.New("ccitt: unsupported mode")
27 errUnsupportedSubFormat = errors.New("ccitt: unsupported sub-format")
28 errUnsupportedWidth = errors.New("ccitt: unsupported width")
29)
30
31// Order specifies the bit ordering in a CCITT data stream.
32type Order uint32
33
34const (
35 // LSB means Least Significant Bits first.
36 LSB Order = iota
37 // MSB means Most Significant Bits first.
38 MSB
39)
40
41// SubFormat represents that the CCITT format consists of a number of
42// sub-formats. Decoding or encoding a CCITT data stream requires knowing the
43// sub-format context. It is not represented in the data stream per se.
44type SubFormat uint32
45
46const (
47 Group3 SubFormat = iota
48 Group4
49)
50
51// Options are optional parameters.
52type Options struct {
53 // Align means that some variable-bit-width codes are byte-aligned.
54 Align bool
55 // Invert means that black is the 1 bit or 0xFF byte, and white is 0.
56 Invert bool
57}
58
59// maxWidth is the maximum (inclusive) supported width. This is a limitation of
60// this implementation, to guard against integer overflow, and not anything
61// inherent to the CCITT format.
62const maxWidth = 1 << 20
63
64func invertBytes(b []byte) {
65 for i, c := range b {
66 b[i] = ^c
67 }
68}
69
70func reverseBitsWithinBytes(b []byte) {
71 for i, c := range b {
72 b[i] = bits.Reverse8(c)
73 }
74}
75
76// highBits writes to dst (1 bit per pixel, most significant bit first) the
77// high (0x80) bits from src (1 byte per pixel). It returns the number of bytes
78// written and read such that dst[:d] is the packed form of src[:s].
79//
80// For example, if src starts with the 8 bytes [0x7D, 0x7E, 0x7F, 0x80, 0x81,
81// 0x82, 0x00, 0xFF] then 0x1D will be written to dst[0].
82//
83// If src has (8 * len(dst)) or more bytes then only len(dst) bytes are
84// written, (8 * len(dst)) bytes are read, and invert is ignored.
85//
86// Otherwise, if len(src) is not a multiple of 8 then the final byte written to
87// dst is padded with 1 bits (if invert is true) or 0 bits. If inverted, the 1s
88// are typically temporary, e.g. they will be flipped back to 0s by an
89// invertBytes call in the highBits caller, reader.Read.
90func highBits(dst []byte, src []byte, invert bool) (d int, s int) {
91 // Pack as many complete groups of 8 src bytes as we can.
92 n := len(src) / 8
93 if n > len(dst) {
94 n = len(dst)
95 }
96 dstN := dst[:n]
97 for i := range dstN {
98 src8 := src[i*8 : i*8+8]
99 dstN[i] = ((src8[0] & 0x80) >> 0) |
100 ((src8[1] & 0x80) >> 1) |
101 ((src8[2] & 0x80) >> 2) |
102 ((src8[3] & 0x80) >> 3) |
103 ((src8[4] & 0x80) >> 4) |
104 ((src8[5] & 0x80) >> 5) |
105 ((src8[6] & 0x80) >> 6) |
106 ((src8[7] & 0x80) >> 7)
107 }
108 d, s = n, 8*n
109 dst, src = dst[d:], src[s:]
110
111 // Pack up to 7 remaining src bytes, if there's room in dst.
112 if (len(dst) > 0) && (len(src) > 0) {
113 dstByte := byte(0)
114 if invert {
115 dstByte = 0xFF >> uint(len(src))
116 }
117 for n, srcByte := range src {
118 dstByte |= (srcByte & 0x80) >> uint(n)
119 }
120 dst[0] = dstByte
121 d, s = d+1, s+len(src)
122 }
123 return d, s
124}
125
126type bitReader struct {
127 r io.Reader
128
129 // readErr is the error returned from the most recent r.Read call. As the
130 // io.Reader documentation says, when r.Read returns (n, err), "always
131 // process the n > 0 bytes returned before considering the error err".
132 readErr error
133
134 // order is whether to process r's bytes LSB first or MSB first.
135 order Order
136
137 // The high nBits bits of the bits field hold upcoming bits in MSB order.
138 bits uint64
139 nBits uint32
140
141 // bytes[br:bw] holds bytes read from r but not yet loaded into bits.
142 br uint32
143 bw uint32
144 bytes [1024]uint8
145}
146
147func (b *bitReader) alignToByteBoundary() {
148 n := b.nBits & 7
149 b.bits <<= n
150 b.nBits -= n
151}
152
153// nextBitMaxNBits is the maximum possible value of bitReader.nBits after a
154// bitReader.nextBit call, provided that bitReader.nBits was not more than this
155// value before that call.
156//
157// Note that the decode function can unread bits, which can temporarily set the
158// bitReader.nBits value above nextBitMaxNBits.
159const nextBitMaxNBits = 31
160
161func (b *bitReader) nextBit() (uint64, error) {
162 for {
163 if b.nBits > 0 {
164 bit := b.bits >> 63
165 b.bits <<= 1
166 b.nBits--
167 return bit, nil
168 }
169
170 if available := b.bw - b.br; available >= 4 {
171 // Read 32 bits, even though b.bits is a uint64, since the decode
172 // function may need to unread up to maxCodeLength bits, putting
173 // them back in the remaining (64 - 32) bits. TestMaxCodeLength
174 // checks that the generated maxCodeLength constant fits.
175 //
176 // If changing the Uint32 call, also change nextBitMaxNBits.
177 b.bits = uint64(binary.BigEndian.Uint32(b.bytes[b.br:])) << 32
178 b.br += 4
179 b.nBits = 32
180 continue
181 } else if available > 0 {
182 b.bits = uint64(b.bytes[b.br]) << (7 * 8)
183 b.br++
184 b.nBits = 8
185 continue
186 }
187
188 if b.readErr != nil {
189 return 0, b.readErr
190 }
191
192 n, err := b.r.Read(b.bytes[:])
193 b.br = 0
194 b.bw = uint32(n)
195 b.readErr = err
196
197 if b.order != MSB {
198 reverseBitsWithinBytes(b.bytes[:b.bw])
199 }
200 }
201}
202
203func decode(b *bitReader, decodeTable [][2]int16) (uint32, error) {
204 nBitsRead, bitsRead, state := uint32(0), uint64(0), int32(1)
205 for {
206 bit, err := b.nextBit()
207 if err != nil {
208 return 0, err
209 }
210 bitsRead |= bit << (63 - nBitsRead)
211 nBitsRead++
212 // The "&1" is redundant, but can eliminate a bounds check.
213 state = int32(decodeTable[state][bit&1])
214 if state < 0 {
215 return uint32(^state), nil
216 } else if state == 0 {
217 // Unread the bits we've read, then return errInvalidCode.
218 b.bits = (b.bits >> nBitsRead) | bitsRead
219 b.nBits += nBitsRead
220 return 0, errInvalidCode
221 }
222 }
223}
224
225type reader struct {
226 br bitReader
227 subFormat SubFormat
228
229 // width is the image width in pixels.
230 width int
231
232 // rowsRemaining starts at the image height in pixels, when the reader is
233 // driven through the io.Reader interface, and decrements to zero as rows
234 // are decoded. When driven through DecodeIntoGray, this field is unused.
235 rowsRemaining int
236
237 // curr and prev hold the current and previous rows. Each element is either
238 // 0x00 (black) or 0xFF (white).
239 //
240 // prev may be nil, when processing the first row.
241 curr []byte
242 prev []byte
243
244 // ri is the read index. curr[:ri] are those bytes of curr that have been
245 // passed along via the Read method.
246 //
247 // When the reader is driven through DecodeIntoGray, instead of through the
248 // io.Reader interface, this field is unused.
249 ri int
250
251 // wi is the write index. curr[:wi] are those bytes of curr that have
252 // already been decoded via the decodeRow method.
253 //
254 // What this implementation calls wi is roughly equivalent to what the spec
255 // calls the a0 index.
256 wi int
257
258 // These fields are copied from the *Options (which may be nil).
259 align bool
260 invert bool
261
262 // atStartOfRow is whether we have just started the row. Some parts of the
263 // spec say to treat this situation as if "wi = -1".
264 atStartOfRow bool
265
266 // penColorIsWhite is whether the next run is black or white.
267 penColorIsWhite bool
268
269 // seenStartOfImage is whether we've called the startDecode method.
270 seenStartOfImage bool
271
272 // readErr is a sticky error for the Read method.
273 readErr error
274}
275
276func (z *reader) Read(p []byte) (int, error) {
277 if z.readErr != nil {
278 return 0, z.readErr
279 }
280 originalP := p
281
282 for len(p) > 0 {
283 // Allocate buffers (and decode any start-of-image codes), if
284 // processing the first or second row.
285 if z.curr == nil {
286 if !z.seenStartOfImage {
287 if z.readErr = z.startDecode(); z.readErr != nil {
288 break
289 }
290 z.atStartOfRow = true
291 }
292 z.curr = make([]byte, z.width)
293 }
294
295 // Decode the next row, if necessary.
296 if z.atStartOfRow {
297 if z.rowsRemaining <= 0 {
298 if z.readErr = z.finishDecode(); z.readErr != nil {
299 break
300 }
301 z.readErr = io.EOF
302 break
303 }
304 if z.readErr = z.decodeRow(); z.readErr != nil {
305 break
306 }
307 z.rowsRemaining--
308 }
309
310 // Pack from z.curr (1 byte per pixel) to p (1 bit per pixel).
311 packD, packS := highBits(p, z.curr[z.ri:], z.invert)
312 p = p[packD:]
313 z.ri += packS
314
315 // Prepare to decode the next row, if necessary.
316 if z.ri == len(z.curr) {
317 z.ri, z.curr, z.prev = 0, z.prev, z.curr
318 z.atStartOfRow = true
319 }
320 }
321
322 n := len(originalP) - len(p)
323 if z.invert {
324 invertBytes(originalP[:n])
325 }
326 return n, z.readErr
327}
328
329func (z *reader) penColor() byte {
330 if z.penColorIsWhite {
331 return 0xFF
332 }
333 return 0x00
334}
335
336func (z *reader) startDecode() error {
337 switch z.subFormat {
338 case Group3:
339 if err := z.decodeEOL(); err != nil {
340 return err
341 }
342
343 case Group4:
344 // No-op.
345
346 default:
347 return errUnsupportedSubFormat
348 }
349
350 z.seenStartOfImage = true
351 return nil
352}
353
354func (z *reader) finishDecode() error {
355 numberOfEOLs := 0
356 switch z.subFormat {
357 case Group3:
358 // The stream ends with a RTC (Return To Control) of 6 consecutive
359 // EOL's, but we should have already just seen an EOL, either in
360 // z.startDecode (for a zero-height image) or in z.decodeRow.
361 numberOfEOLs = 5
362
363 case Group4:
364 // The stream ends with two EOL's, the first of which is possibly
365 // byte-aligned.
366 numberOfEOLs = 2
367 if err := z.decodeEOL(); err == nil {
368 numberOfEOLs--
369 } else if err == errInvalidCode {
370 // Try again, this time starting from a byte boundary.
371 z.br.alignToByteBoundary()
372 } else {
373 return err
374 }
375
376 default:
377 return errUnsupportedSubFormat
378 }
379
380 for ; numberOfEOLs > 0; numberOfEOLs-- {
381 if err := z.decodeEOL(); err != nil {
382 return err
383 }
384 }
385 return nil
386}
387
388func (z *reader) decodeEOL() error {
389 // TODO: EOL doesn't have to be in the modeDecodeTable. It could be in its
390 // own table, or we could just hard-code it, especially if we might need to
391 // cater for optional byte-alignment, or an arbitrary number (potentially
392 // more than 8) of 0-valued padding bits.
393 if mode, err := decode(&z.br, modeDecodeTable[:]); err != nil {
394 return err
395 } else if mode != modeEOL {
396 return errMissingEOL
397 }
398 return nil
399}
400
401func (z *reader) decodeRow() error {
402 z.wi = 0
403 z.atStartOfRow = true
404 z.penColorIsWhite = true
405
406 if z.align {
407 z.br.alignToByteBoundary()
408 }
409
410 switch z.subFormat {
411 case Group3:
412 for ; z.wi < len(z.curr); z.atStartOfRow = false {
413 if err := z.decodeRun(); err != nil {
414 return err
415 }
416 }
417 return z.decodeEOL()
418
419 case Group4:
420 for ; z.wi < len(z.curr); z.atStartOfRow = false {
421 mode, err := decode(&z.br, modeDecodeTable[:])
422 if err != nil {
423 return err
424 }
425 rm := readerMode{}
426 if mode < uint32(len(readerModes)) {
427 rm = readerModes[mode]
428 }
429 if rm.function == nil {
430 return errInvalidMode
431 }
432 if err := rm.function(z, rm.arg); err != nil {
433 return err
434 }
435 }
436 return nil
437 }
438
439 return errUnsupportedSubFormat
440}
441
442func (z *reader) decodeRun() error {
443 table := blackDecodeTable[:]
444 if z.penColorIsWhite {
445 table = whiteDecodeTable[:]
446 }
447
448 total := 0
449 for {
450 n, err := decode(&z.br, table)
451 if err != nil {
452 return err
453 }
454 if n > maxWidth {
455 panic("unreachable")
456 }
457 total += int(n)
458 if total > maxWidth {
459 return errRunLengthTooLong
460 }
461 // Anything 0x3F or below is a terminal code.
462 if n <= 0x3F {
463 break
464 }
465 }
466
467 if total > (len(z.curr) - z.wi) {
468 return errRunLengthOverflowsWidth
469 }
470 dst := z.curr[z.wi : z.wi+total]
471 penColor := z.penColor()
472 for i := range dst {
473 dst[i] = penColor
474 }
475 z.wi += total
476 z.penColorIsWhite = !z.penColorIsWhite
477
478 return nil
479}
480
481// The various modes' semantics are based on determining a row of pixels'
482// "changing elements": those pixels whose color differs from the one on its
483// immediate left.
484//
485// The row above the first row is implicitly all white. Similarly, the column
486// to the left of the first column is implicitly all white.
487//
488// For example, here's Figure 1 in "ITU-T Recommendation T.6", where the
489// current and previous rows contain black (B) and white (w) pixels. The a?
490// indexes point into curr, the b? indexes point into prev.
491//
492// b1 b2
493// v v
494// prev: BBBBBwwwwwBBBwwwww
495// curr: BBBwwwwwBBBBBBwwww
496// ^ ^ ^
497// a0 a1 a2
498//
499// a0 is the "reference element" or current decoder position, roughly
500// equivalent to what this implementation calls reader.wi.
501//
502// a1 is the next changing element to the right of a0, on the "coding line"
503// (the current row).
504//
505// a2 is the next changing element to the right of a1, again on curr.
506//
507// b1 is the first changing element on the "reference line" (the previous row)
508// to the right of a0 and of opposite color to a0.
509//
510// b2 is the next changing element to the right of b1, again on prev.
511//
512// The various modes calculate a1 (and a2, for modeH):
513// - modePass calculates that a1 is at or to the right of b2.
514// - modeH calculates a1 and a2 without considering b1 or b2.
515// - modeV* calculates a1 to be b1 plus an adjustment (between -3 and +3).
516
517const (
518 findB1 = false
519 findB2 = true
520)
521
522// findB finds either the b1 or b2 value.
523func (z *reader) findB(whichB bool) int {
524 // The initial row is a special case. The previous row is implicitly all
525 // white, so that there are no changing pixel elements. We return b1 or b2
526 // to be at the end of the row.
527 if len(z.prev) != len(z.curr) {
528 return len(z.curr)
529 }
530
531 i := z.wi
532
533 if z.atStartOfRow {
534 // a0 is implicitly at -1, on a white pixel. b1 is the first black
535 // pixel in the previous row. b2 is the first white pixel after that.
536 for ; (i < len(z.prev)) && (z.prev[i] == 0xFF); i++ {
537 }
538 if whichB == findB2 {
539 for ; (i < len(z.prev)) && (z.prev[i] == 0x00); i++ {
540 }
541 }
542 return i
543 }
544
545 // As per figure 1 above, assume that the current pen color is white.
546 // First, walk past every contiguous black pixel in prev, starting at a0.
547 oppositeColor := ^z.penColor()
548 for ; (i < len(z.prev)) && (z.prev[i] == oppositeColor); i++ {
549 }
550
551 // Then walk past every contiguous white pixel.
552 penColor := ^oppositeColor
553 for ; (i < len(z.prev)) && (z.prev[i] == penColor); i++ {
554 }
555
556 // We're now at a black pixel (or at the end of the row). That's b1.
557 if whichB == findB2 {
558 // If we're looking for b2, walk past every contiguous black pixel
559 // again.
560 oppositeColor := ^penColor
561 for ; (i < len(z.prev)) && (z.prev[i] == oppositeColor); i++ {
562 }
563 }
564
565 return i
566}
567
568type readerMode struct {
569 function func(z *reader, arg int) error
570 arg int
571}
572
573var readerModes = [...]readerMode{
574 modePass: {function: readerModePass},
575 modeH: {function: readerModeH},
576 modeV0: {function: readerModeV, arg: +0},
577 modeVR1: {function: readerModeV, arg: +1},
578 modeVR2: {function: readerModeV, arg: +2},
579 modeVR3: {function: readerModeV, arg: +3},
580 modeVL1: {function: readerModeV, arg: -1},
581 modeVL2: {function: readerModeV, arg: -2},
582 modeVL3: {function: readerModeV, arg: -3},
583 modeExt: {function: readerModeExt},
584}
585
586func readerModePass(z *reader, arg int) error {
587 b2 := z.findB(findB2)
588 if (b2 < z.wi) || (len(z.curr) < b2) {
589 return errInvalidOffset
590 }
591 dst := z.curr[z.wi:b2]
592 penColor := z.penColor()
593 for i := range dst {
594 dst[i] = penColor
595 }
596 z.wi = b2
597 return nil
598}
599
600func readerModeH(z *reader, arg int) error {
601 // The first iteration finds a1. The second finds a2.
602 for i := 0; i < 2; i++ {
603 if err := z.decodeRun(); err != nil {
604 return err
605 }
606 }
607 return nil
608}
609
610func readerModeV(z *reader, arg int) error {
611 a1 := z.findB(findB1) + arg
612 if (a1 < z.wi) || (len(z.curr) < a1) {
613 return errInvalidOffset
614 }
615 dst := z.curr[z.wi:a1]
616 penColor := z.penColor()
617 for i := range dst {
618 dst[i] = penColor
619 }
620 z.wi = a1
621 z.penColorIsWhite = !z.penColorIsWhite
622 return nil
623}
624
625func readerModeExt(z *reader, arg int) error {
626 return errUnsupportedMode
627}
628
629// DecodeIntoGray decodes the CCITT-formatted data in r into dst.
630//
631// It returns an error if dst's width and height don't match the implied width
632// and height of CCITT-formatted data.
633func DecodeIntoGray(dst *image.Gray, r io.Reader, order Order, sf SubFormat, opts *Options) error {
634 bounds := dst.Bounds()
635 if (bounds.Dx() < 0) || (bounds.Dy() < 0) {
636 return errInvalidBounds
637 }
638 if bounds.Dx() > maxWidth {
639 return errUnsupportedWidth
640 }
641
642 z := reader{
643 br: bitReader{r: r, order: order},
644 subFormat: sf,
645 align: (opts != nil) && opts.Align,
646 invert: (opts != nil) && opts.Invert,
647 width: bounds.Dx(),
648 }
649 if err := z.startDecode(); err != nil {
650 return err
651 }
652
653 width := bounds.Dx()
654 for y := bounds.Min.Y; y < bounds.Max.Y; y++ {
655 p := (y - bounds.Min.Y) * dst.Stride
656 z.curr = dst.Pix[p : p+width]
657 if err := z.decodeRow(); err != nil {
658 return err
659 }
660 z.curr, z.prev = nil, z.curr
661 }
662
663 if err := z.finishDecode(); err != nil {
664 return err
665 }
666
667 if z.invert {
668 for y := bounds.Min.Y; y < bounds.Max.Y; y++ {
669 p := (y - bounds.Min.Y) * dst.Stride
670 invertBytes(dst.Pix[p : p+width])
671 }
672 }
673
674 return nil
675}
676
677// NewReader returns an io.Reader that decodes the CCITT-formatted data in r.
678// The resultant byte stream is one bit per pixel (MSB first), with 1 meaning
679// white and 0 meaning black. Each row in the result is byte-aligned.
680func NewReader(r io.Reader, order Order, sf SubFormat, width int, height int, opts *Options) io.Reader {
681 readErr := error(nil)
682 if (width < 0) || (height < 0) {
683 readErr = errInvalidBounds
684 } else if width > maxWidth {
685 readErr = errUnsupportedWidth
686 }
687
688 return &reader{
689 br: bitReader{r: r, order: order},
690 subFormat: sf,
691 align: (opts != nil) && opts.Align,
692 invert: (opts != nil) && opts.Invert,
693 width: width,
694 rowsRemaining: height,
695 readErr: readErr,
696 }
697}