ccitt: implement NewReader and DecodeIntoGray The testdata/bw-gopher.png image was derived from testdata/bw-uncompressed.tiff The testdata/*ccitt* data was generated from a custom CCITT encoder: https://go-review.googlesource.com/c/image/+/174139/10/ccitt/writer.go Updates golang/go#19443 Change-Id: I53b7acd807aa9a627517ede5bc3316d6f1fe4724 Reviewed-on: https://go-review.googlesource.com/c/image/+/182219 Reviewed-by: Benny Siegert <bsiegert@gmail.com>
diff --git a/ccitt/reader.go b/ccitt/reader.go index ef353dc..04d0302 100644 --- a/ccitt/reader.go +++ b/ccitt/reader.go
@@ -10,12 +10,22 @@ import ( "encoding/binary" "errors" + "image" "io" "math/bits" ) var ( - errInvalidCode = errors.New("ccitt: invalid code") + errInvalidBounds = errors.New("ccitt: invalid bounds") + errInvalidCode = errors.New("ccitt: invalid code") + errInvalidMode = errors.New("ccitt: invalid mode") + errInvalidOffset = errors.New("ccitt: invalid offset") + errMissingEOL = errors.New("ccitt: missing End-of-Line") + errRunLengthOverflowsWidth = errors.New("ccitt: run length overflows width") + errRunLengthTooLong = errors.New("ccitt: run length too long") + errUnsupportedMode = errors.New("ccitt: unsupported mode") + errUnsupportedSubFormat = errors.New("ccitt: unsupported sub-format") + errUnsupportedWidth = errors.New("ccitt: unsupported width") ) // Order specifies the bit ordering in a CCITT data stream. @@ -28,6 +38,35 @@ MSB ) +// SubFormat represents that the CCITT format consists of a number of +// sub-formats. Decoding or encoding a CCITT data stream requires knowing the +// sub-format context. It is not represented in the data stream per se. +type SubFormat uint32 + +const ( + Group3 SubFormat = iota + Group4 +) + +// Options are optional parameters. +type Options struct { + // Align means that some variable-bit-width codes are byte-aligned. + Align bool + // Invert means that black is the 1 bit or 0xFF byte, and white is 0. + Invert bool +} + +// maxWidth is the maximum (inclusive) supported width. This is a limitation of +// this implementation, to guard against integer overflow, and not anything +// inherent to the CCITT format. +const maxWidth = 1 << 20 + +func invertBytes(b []byte) { + for i, c := range b { + b[i] = ^c + } +} + type bitReader struct { r io.Reader @@ -36,6 +75,7 @@ // process the n > 0 bytes returned before considering the error err". readErr error + // order is whether to process r's bytes LSB first or MSB first. order Order // The low nBits bits of the bits field hold upcoming bits in LSB order. @@ -128,3 +168,493 @@ } } } + +type reader struct { + br bitReader + subFormat SubFormat + + // width is the image width in pixels. + width int + + // rowsRemaining starts at the image height in pixels, when the reader is + // driven through the io.Reader interface, and decrements to zero as rows + // are decoded. When driven through DecodeIntoGray, this field is unused. + rowsRemaining int + + // curr and prev hold the current and previous rows. Each element is either + // 0x00 (black) or 0xFF (white). + // + // prev may be nil, when processing the first row. + curr []byte + prev []byte + + // ri is the read index. curr[:ri] are those bytes of curr that have been + // passed along via the Read method. + // + // When the reader is driven through DecodeIntoGray, instead of through the + // io.Reader interface, this field is unused. + ri int + + // wi is the write index. curr[:wi] are those bytes of curr that have + // already been decoded via the decodeRow method. + // + // What this implementation calls wi is roughly equivalent to what the spec + // calls the a0 index. + wi int + + // These fields are copied from the *Options (which may be nil). + align bool + invert bool + + // atStartOfRow is whether we have just started the row. Some parts of the + // spec say to treat this situation as if "wi = -1". + atStartOfRow bool + + // penColorIsWhite is whether the next run is black or white. + penColorIsWhite bool + + // seenStartOfImage is whether we've called the startDecode method. + seenStartOfImage bool + + // readErr is a sticky error for the Read method. + readErr error +} + +func (z *reader) Read(p []byte) (int, error) { + if z.readErr != nil { + return 0, z.readErr + } + originalP := p + + for len(p) > 0 { + // Allocate buffers (and decode any start-of-image codes), if + // processing the first or second row. + if z.curr == nil { + if !z.seenStartOfImage { + if z.readErr = z.startDecode(); z.readErr != nil { + break + } + z.atStartOfRow = true + } + z.curr = make([]byte, z.width) + } + + // Decode the next row, if necessary. + if z.atStartOfRow { + if z.rowsRemaining <= 0 { + if z.readErr = z.finishDecode(); z.readErr != nil { + break + } + z.readErr = io.EOF + break + } + if z.readErr = z.decodeRow(); z.readErr != nil { + break + } + z.rowsRemaining-- + } + + // Pack from z.curr (1 byte per pixel) to p (1 bit per pixel), up to 8 + // elements per iteration. + i := 0 + for ; i < len(p); i++ { + numToPack := len(z.curr) - z.ri + if numToPack <= 0 { + break + } else if numToPack > 8 { + numToPack = 8 + } + + byteValue := byte(0) + for j := 0; j < numToPack; j++ { + byteValue |= (z.curr[z.ri] & 0x80) >> uint(j) + z.ri++ + } + p[i] = byteValue + } + p = p[i:] + + // Prepare to decode the next row, if necessary. + if z.ri == len(z.curr) { + z.ri, z.curr, z.prev = 0, z.prev, z.curr + z.atStartOfRow = true + } + } + + n := len(originalP) - len(p) + // TODO: when invert is true, should the end-of-row padding bits be 0 or 1? + if z.invert { + invertBytes(originalP[:n]) + } + return n, z.readErr +} + +func (z *reader) penColor() byte { + if z.penColorIsWhite { + return 0xFF + } + return 0x00 +} + +func (z *reader) startDecode() error { + switch z.subFormat { + case Group3: + if err := z.decodeEOL(); err != nil { + return err + } + + case Group4: + // No-op. + + default: + return errUnsupportedSubFormat + } + + z.seenStartOfImage = true + return nil +} + +func (z *reader) finishDecode() error { + numberOfEOLs := 0 + switch z.subFormat { + case Group3: + // The stream ends with a RTC (Return To Control) of 6 consecutive + // EOL's, but we should have already just seen an EOL, either in + // z.startDecode (for a zero-height image) or in z.decodeRow. + numberOfEOLs = 5 + + case Group4: + // The stream ends with two EOL's, the first of which is possibly + // byte-aligned. + numberOfEOLs = 2 + if err := z.decodeEOL(); err == nil { + numberOfEOLs-- + } else if err == errInvalidCode { + // Try again, this time starting from a byte boundary. + z.br.alignToByteBoundary() + } else { + return err + } + + default: + return errUnsupportedSubFormat + } + + for ; numberOfEOLs > 0; numberOfEOLs-- { + if err := z.decodeEOL(); err != nil { + return err + } + } + return nil +} + +func (z *reader) decodeEOL() error { + // TODO: EOL doesn't have to be in the modeDecodeTable. It could be in its + // own table, or we could just hard-code it, especially if we might need to + // cater for optional byte-alignment, or an arbitrary number (potentially + // more than 8) of 0-valued padding bits. + if mode, err := decode(&z.br, modeDecodeTable[:]); err != nil { + return err + } else if mode != modeEOL { + return errMissingEOL + } + return nil +} + +func (z *reader) decodeRow() error { + z.wi = 0 + z.atStartOfRow = true + z.penColorIsWhite = true + + switch z.subFormat { + case Group3: + for ; z.wi < len(z.curr); z.atStartOfRow = false { + if err := z.decodeRun(); err != nil { + return err + } + } + return z.decodeEOL() + + case Group4: + if z.align { + z.br.alignToByteBoundary() + } + + for ; z.wi < len(z.curr); z.atStartOfRow = false { + mode, err := decode(&z.br, modeDecodeTable[:]) + if err != nil { + return err + } + rm := readerMode{} + if mode < uint32(len(readerModes)) { + rm = readerModes[mode] + } + if rm.function == nil { + return errInvalidMode + } + if err := rm.function(z, rm.arg); err != nil { + return err + } + } + return nil + } + + return errUnsupportedSubFormat +} + +func (z *reader) decodeRun() error { + table := blackDecodeTable[:] + if z.penColorIsWhite { + table = whiteDecodeTable[:] + } + + total := 0 + for { + n, err := decode(&z.br, table) + if err != nil { + return err + } + if n > maxWidth { + panic("unreachable") + } + total += int(n) + if total > maxWidth { + return errRunLengthTooLong + } + // Anything 0x3F or below is a terminal code. + if n <= 0x3F { + break + } + } + + if total > (len(z.curr) - z.wi) { + return errRunLengthOverflowsWidth + } + dst := z.curr[z.wi : z.wi+total] + penColor := z.penColor() + for i := range dst { + dst[i] = penColor + } + z.wi += total + z.penColorIsWhite = !z.penColorIsWhite + + return nil +} + +// The various modes' semantics are based on determining a row of pixels' +// "changing elements": those pixels whose color differs from the one on its +// immediate left. +// +// The row above the first row is implicitly all white. Similarly, the column +// to the left of the first column is implicitly all white. +// +// For example, here's Figure 1 in "ITU-T Recommendation T.6", where the +// current and previous rows contain black (B) and white (w) pixels. The a? +// indexes point into curr, the b? indexes point into prev. +// +// b1 b2 +// v v +// prev: BBBBBwwwwwBBBwwwww +// curr: BBBwwwwwBBBBBBwwww +// ^ ^ ^ +// a0 a1 a2 +// +// a0 is the "reference element" or current decoder position, roughly +// equivalent to what this implementation calls reader.wi. +// +// a1 is the next changing element to the right of a0, on the "coding line" +// (the current row). +// +// a2 is the next changing element to the right of a1, again on curr. +// +// b1 is the first changing element on the "reference line" (the previous row) +// to the right of a0 and of opposite color to a0. +// +// b2 is the next changing element to the right of b1, again on prev. +// +// The various modes calculate a1 (and a2, for modeH): +// - modePass calculates that a1 is at or to the right of b2. +// - modeH calculates a1 and a2 without considering b1 or b2. +// - modeV* calculates a1 to be b1 plus an adjustment (between -3 and +3). + +const ( + findB1 = false + findB2 = true +) + +// findB finds either the b1 or b2 value. +func (z *reader) findB(whichB bool) int { + // The initial row is a special case. The previous row is implicitly all + // white, so that there are no changing pixel elements. We return b1 or b2 + // to be at the end of the row. + if len(z.prev) != len(z.curr) { + return len(z.curr) + } + + i := z.wi + + if z.atStartOfRow { + // a0 is implicitly at -1, on a white pixel. b1 is the first black + // pixel in the previous row. b2 is the first white pixel after that. + for ; (i < len(z.prev)) && (z.prev[i] == 0xFF); i++ { + } + if whichB == findB2 { + for ; (i < len(z.prev)) && (z.prev[i] == 0x00); i++ { + } + } + return i + } + + // As per figure 1 above, assume that the current pen color is white. + // First, walk past every contiguous black pixel in prev, starting at a0. + oppositeColor := ^z.penColor() + for ; (i < len(z.prev)) && (z.prev[i] == oppositeColor); i++ { + } + + // Then walk past every contiguous white pixel. + penColor := ^oppositeColor + for ; (i < len(z.prev)) && (z.prev[i] == penColor); i++ { + } + + // We're now at a black pixel (or at the end of the row). That's b1. + if whichB == findB2 { + // If we're looking for b2, walk past every contiguous black pixel + // again. + oppositeColor := ^penColor + for ; (i < len(z.prev)) && (z.prev[i] == oppositeColor); i++ { + } + } + + return i +} + +type readerMode struct { + function func(z *reader, arg int) error + arg int +} + +var readerModes = [...]readerMode{ + modePass: {function: readerModePass}, + modeH: {function: readerModeH}, + modeV0: {function: readerModeV, arg: +0}, + modeVR1: {function: readerModeV, arg: +1}, + modeVR2: {function: readerModeV, arg: +2}, + modeVR3: {function: readerModeV, arg: +3}, + modeVL1: {function: readerModeV, arg: -1}, + modeVL2: {function: readerModeV, arg: -2}, + modeVL3: {function: readerModeV, arg: -3}, + modeExt: {function: readerModeExt}, +} + +func readerModePass(z *reader, arg int) error { + b2 := z.findB(findB2) + if (b2 < z.wi) || (len(z.curr) < b2) { + return errInvalidOffset + } + dst := z.curr[z.wi:b2] + penColor := z.penColor() + for i := range dst { + dst[i] = penColor + } + z.wi = b2 + return nil +} + +func readerModeH(z *reader, arg int) error { + // The first iteration finds a1. The second finds a2. + for i := 0; i < 2; i++ { + if err := z.decodeRun(); err != nil { + return err + } + } + return nil +} + +func readerModeV(z *reader, arg int) error { + a1 := z.findB(findB1) + arg + if (a1 < z.wi) || (len(z.curr) < a1) { + return errInvalidOffset + } + dst := z.curr[z.wi:a1] + penColor := z.penColor() + for i := range dst { + dst[i] = penColor + } + z.wi = a1 + z.penColorIsWhite = !z.penColorIsWhite + return nil +} + +func readerModeExt(z *reader, arg int) error { + return errUnsupportedMode +} + +// DecodeIntoGray decodes the CCITT-formatted data in r into dst. +// +// It returns an error if dst's width and height don't match the implied width +// and height of CCITT-formatted data. +func DecodeIntoGray(dst *image.Gray, r io.Reader, order Order, sf SubFormat, opts *Options) error { + bounds := dst.Bounds() + if (bounds.Dx() < 0) || (bounds.Dy() < 0) { + return errInvalidBounds + } + if bounds.Dx() > maxWidth { + return errUnsupportedWidth + } + + z := reader{ + br: bitReader{r: r, order: order}, + subFormat: sf, + align: (opts != nil) && opts.Align, + invert: (opts != nil) && opts.Invert, + width: bounds.Dx(), + } + if err := z.startDecode(); err != nil { + return err + } + + width := bounds.Dx() + for y := bounds.Min.Y; y < bounds.Max.Y; y++ { + p := (y - bounds.Min.Y) * dst.Stride + z.curr = dst.Pix[p : p+width] + if err := z.decodeRow(); err != nil { + return err + } + z.curr, z.prev = nil, z.curr + } + + if err := z.finishDecode(); err != nil { + return err + } + + if z.invert { + for y := bounds.Min.Y; y < bounds.Max.Y; y++ { + p := (y - bounds.Min.Y) * dst.Stride + invertBytes(dst.Pix[p : p+width]) + } + } + + return nil +} + +// NewReader returns an io.Reader that decodes the CCITT-formatted data in r. +// The resultant byte stream is one bit per pixel (MSB first), with 1 meaning +// white and 0 meaning black. Each row in the result is byte-aligned. +func NewReader(r io.Reader, order Order, sf SubFormat, width int, height int, opts *Options) io.Reader { + readErr := error(nil) + if (width < 0) || (height < 0) { + readErr = errInvalidBounds + } else if width > maxWidth { + readErr = errUnsupportedWidth + } + + return &reader{ + br: bitReader{r: r, order: order}, + subFormat: sf, + align: (opts != nil) && opts.Align, + invert: (opts != nil) && opts.Invert, + width: width, + rowsRemaining: height, + readErr: readErr, + } +}
diff --git a/ccitt/reader_test.go b/ccitt/reader_test.go index a1b9451..c582f16 100644 --- a/ccitt/reader_test.go +++ b/ccitt/reader_test.go
@@ -6,12 +6,47 @@ import ( "bytes" + "fmt" + "image" + "image/png" "io" + "io/ioutil" + "os" + "path/filepath" "reflect" "testing" "unsafe" ) +func compareImages(t *testing.T, img0 image.Image, img1 image.Image) { + t.Helper() + + b0 := img0.Bounds() + b1 := img1.Bounds() + if b0 != b1 { + t.Fatalf("bounds differ: %v vs %v", b0, b1) + } + + for y := b0.Min.Y; y < b0.Max.Y; y++ { + for x := b0.Min.X; x < b0.Max.X; x++ { + c0 := img0.At(x, y) + c1 := img1.At(x, y) + if c0 != c1 { + t.Fatalf("pixel at (%d, %d) differs: %v vs %v", x, y, c0, c1) + } + } + } +} + +func decodePNG(fileName string) (image.Image, error) { + f, err := os.Open(fileName) + if err != nil { + return nil, err + } + defer f.Close() + return png.Decode(f) +} + func TestMaxCodeLength(t *testing.T) { br := bitReader{} size := unsafe.Sizeof(br.bits) @@ -44,7 +79,7 @@ m[code.val] = code.str } - // Build the encoded form of those values. + // Build the encoded form of those values in LSB order. enc := []byte(nil) bits := uint8(0) nBits := uint32(0) @@ -163,4 +198,134 @@ } } -// TODO: more tests. +func TestReadRegular(t *testing.T) { testRead(t, false) } +func TestReadInvert(t *testing.T) { testRead(t, true) } + +func testRead(t *testing.T, invert bool) { + t.Helper() + + const width, height = 153, 55 + opts := &Options{ + Invert: invert, + } + + got := "" + { + f, err := os.Open("testdata/bw-gopher.ccitt_group3") + if err != nil { + t.Fatalf("Open: %v", err) + } + defer f.Close() + gotBytes, err := ioutil.ReadAll(NewReader(f, MSB, Group3, width, height, opts)) + if err != nil { + t.Fatalf("ReadAll: %v", err) + } + got = string(gotBytes) + } + + want := "" + { + img, err := decodePNG("testdata/bw-gopher.png") + if err != nil { + t.Fatalf("decodePNG: %v", err) + } + gray, ok := img.(*image.Gray) + if !ok { + t.Fatalf("decodePNG: got %T, want *image.Gray", img) + } + bounds := gray.Bounds() + if w := bounds.Dx(); w != width { + t.Fatalf("width: got %d, want %d", w, width) + } + if h := bounds.Dy(); h != height { + t.Fatalf("height: got %d, want %d", h, height) + } + + // Prepare to extend each row's width to a multiple of 8, to simplify + // packing from 1 byte per pixel to 1 bit per pixel. + extended := make([]byte, (width+7)&^7) + + wantBytes := []byte(nil) + for y := bounds.Min.Y; y < bounds.Max.Y; y++ { + rowPix := gray.Pix[(y-bounds.Min.Y)*gray.Stride:] + rowPix = rowPix[:width] + copy(extended, rowPix) + + // Pack from 1 byte per pixel to 1 bit per pixel, MSB first. + byteValue := uint8(0) + for x, pixel := range extended { + byteValue |= (pixel & 0x80) >> uint(x&7) + if (x & 7) == 7 { + wantBytes = append(wantBytes, byteValue) + byteValue = 0 + } + } + } + if invert { + invertBytes(wantBytes) + } + want = string(wantBytes) + } + + // We expect a width of 153 pixels, which is 20 bytes per row (at 1 bit per + // pixel, plus 7 final bits of padding). Check that want is 20 * height + // bytes long, and if got != want, format them to split at every 20 bytes. + + if n := len(want); n != 20*height { + t.Fatalf("len(want): got %d, want %d", n, 20*height) + } + + format := func(s string) string { + b := []byte(nil) + for row := 0; len(s) >= 20; row++ { + b = append(b, fmt.Sprintf("row%02d: %02X\n", row, s[:20])...) + s = s[20:] + } + if len(s) > 0 { + b = append(b, fmt.Sprintf("%02X\n", s)...) + } + return string(b) + } + + if got != want { + t.Fatalf("got:\n%s\nwant:\n%s", format(got), format(want)) + } +} + +func TestDecodeIntoGray(t *testing.T) { + for _, tt := range []struct { + fileName string + sf SubFormat + w, h int + }{ + {"testdata/bw-gopher.ccitt_group3", Group3, 153, 55}, + {"testdata/bw-gopher.ccitt_group4", Group4, 153, 55}, + } { + t.Run(tt.fileName, func(t *testing.T) { + testDecodeIntoGray(t, tt.fileName, MSB, tt.sf, tt.w, tt.h, nil) + }) + } +} + +func testDecodeIntoGray(t *testing.T, fileName string, order Order, sf SubFormat, width int, height int, opts *Options) { + t.Helper() + + f, err := os.Open(filepath.FromSlash(fileName)) + if err != nil { + t.Fatalf("Open: %v", err) + } + defer f.Close() + + got := image.NewGray(image.Rect(0, 0, width, height)) + if err := DecodeIntoGray(got, f, order, sf, opts); err != nil { + t.Fatalf("DecodeIntoGray: %v", err) + } + + baseName := fileName[:len(fileName)-len(filepath.Ext(fileName))] + want, err := decodePNG(baseName + ".png") + if err != nil { + t.Fatal(err) + } + + compareImages(t, got, want) +}
diff --git a/ccitt/testdata/bw-gopher.ccitt_group3 b/ccitt/testdata/bw-gopher.ccitt_group3 new file mode 100644 index 0000000..a461904 --- /dev/null +++ b/ccitt/testdata/bw-gopher.ccitt_group3 Binary files differ
diff --git a/ccitt/testdata/bw-gopher.ccitt_group4 b/ccitt/testdata/bw-gopher.ccitt_group4 new file mode 100644 index 0000000..05757a7 --- /dev/null +++ b/ccitt/testdata/bw-gopher.ccitt_group4 Binary files differ
diff --git a/ccitt/testdata/bw-gopher.png b/ccitt/testdata/bw-gopher.png new file mode 100644 index 0000000..6e8e957 --- /dev/null +++ b/ccitt/testdata/bw-gopher.png Binary files differ
