    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.imaging.formats.tiff.itu_t4;
    018
    019import java.io.ByteArrayInputStream;
    020import java.io.IOException;
    021
    022import org.apache.commons.imaging.ImagingException;
    023import org.apache.commons.imaging.common.Allocator;
    024import org.apache.commons.imaging.formats.tiff.itu_t4.T4_T6_Tables.Entry;
    025
    026public final class T4AndT6Compression {
    027    private static final HuffmanTree<Integer> WHITE_RUN_LENGTHS = new HuffmanTree<>();
    028    private static final HuffmanTree<Integer> BLACK_RUN_LENGTHS = new HuffmanTree<>();
    029    private static final HuffmanTree<Entry> CONTROL_CODES = new HuffmanTree<>();
    030
    031    public static final int WHITE = 0;
    032    public static final int BLACK = 1;
    033
    034    static {
    035        try {
    036            for (final Entry entry : T4_T6_Tables.WHITE_TERMINATING_CODES) {
    037                WHITE_RUN_LENGTHS.insert(entry.bitString, entry.value);
    038            }
    039            for (final Entry entry : T4_T6_Tables.WHITE_MAKE_UP_CODES) {
    040                WHITE_RUN_LENGTHS.insert(entry.bitString, entry.value);
    041            }
    042            for (final Entry entry : T4_T6_Tables.BLACK_TERMINATING_CODES) {
    043                BLACK_RUN_LENGTHS.insert(entry.bitString, entry.value);
    044            }
    045            for (final Entry entry : T4_T6_Tables.BLACK_MAKE_UP_CODES) {
    046                BLACK_RUN_LENGTHS.insert(entry.bitString, entry.value);
    047            }
    048            for (final Entry entry : T4_T6_Tables.ADDITIONAL_MAKE_UP_CODES) {
    049                WHITE_RUN_LENGTHS.insert(entry.bitString, entry.value);
    050                BLACK_RUN_LENGTHS.insert(entry.bitString, entry.value);
    051            }
    052            CONTROL_CODES.insert(T4_T6_Tables.EOL.bitString, T4_T6_Tables.EOL);
    053            CONTROL_CODES.insert(T4_T6_Tables.EOL13.bitString, T4_T6_Tables.EOL13);
    054            CONTROL_CODES.insert(T4_T6_Tables.EOL14.bitString, T4_T6_Tables.EOL14);
    055            CONTROL_CODES.insert(T4_T6_Tables.EOL15.bitString, T4_T6_Tables.EOL15);
    056            CONTROL_CODES.insert(T4_T6_Tables.EOL16.bitString, T4_T6_Tables.EOL16);
    057            CONTROL_CODES.insert(T4_T6_Tables.EOL17.bitString, T4_T6_Tables.EOL17);
    058            CONTROL_CODES.insert(T4_T6_Tables.EOL18.bitString, T4_T6_Tables.EOL18);
    059            CONTROL_CODES.insert(T4_T6_Tables.EOL19.bitString, T4_T6_Tables.EOL19);
    060            CONTROL_CODES.insert(T4_T6_Tables.P.bitString, T4_T6_Tables.P);
    061            CONTROL_CODES.insert(T4_T6_Tables.H.bitString, T4_T6_Tables.H);
    062            CONTROL_CODES.insert(T4_T6_Tables.V0.bitString, T4_T6_Tables.V0);
    063            CONTROL_CODES.insert(T4_T6_Tables.VL1.bitString, T4_T6_Tables.VL1);
    064            CONTROL_CODES.insert(T4_T6_Tables.VL2.bitString, T4_T6_Tables.VL2);
    065            CONTROL_CODES.insert(T4_T6_Tables.VL3.bitString, T4_T6_Tables.VL3);
    066            CONTROL_CODES.insert(T4_T6_Tables.VR1.bitString, T4_T6_Tables.VR1);
    067            CONTROL_CODES.insert(T4_T6_Tables.VR2.bitString, T4_T6_Tables.VR2);
    068            CONTROL_CODES.insert(T4_T6_Tables.VR3.bitString, T4_T6_Tables.VR3);
    069        } catch (final ImagingException cannotHappen) {
    070            throw new IllegalStateException(cannotHappen);
    071        }
    072    }
    073
    074    private static int changingElementAt(final int[] line, final int position) {
    075        if (position < 0 || position >= line.length) {
    076            return WHITE;
    077        }
    078        return line[position];
    079    }
    080
    081    private static void compress1DLine(final BitInputStreamFlexible inputStream, final BitArrayOutputStream outputStream, final int[] referenceLine,
    082            final int width) throws ImagingException {
    083        int color = WHITE;
    084        int runLength = 0;
    085
    086        for (int x = 0; x < width; x++) {
    087            try {
    088                final int nextColor = inputStream.readBits(1);
    089                if (referenceLine != null) {
    090                    referenceLine[x] = nextColor;
    091                }
    092                if (color == nextColor) {
    093                    ++runLength;
    094                } else {
    095                    writeRunLength(outputStream, runLength, color);
    096                    color = nextColor;
    097                    runLength = 1;
    098                }
    099            } catch (final IOException ioException) {
    100                throw new ImagingException("Error reading image to compress", ioException);
    101            }
    102        }
    103
    104        writeRunLength(outputStream, runLength, color);
    105    }
    106
    107    /**
    108     * Compressed with the "Modified Huffman" encoding of section 10 in the TIFF6 specification. No EOLs, no RTC, rows are padded to end on a byte boundary.
    109     *
    110     * @param uncompressed uncompressed byte data
    111     * @param width        image width
    112     * @param height       image height
    113     * @return the compressed data
    114     * @throws ImagingException if it fails to write the compressed data
    115     */
    116    public static byte[] compressModifiedHuffman(final byte[] uncompressed, final int width, final int height) throws ImagingException {
    117        final BitInputStreamFlexible inputStream = new BitInputStreamFlexible(new ByteArrayInputStream(uncompressed));
    118        try (BitArrayOutputStream outputStream = new BitArrayOutputStream()) {
    119            for (int y = 0; y < height; y++) {
    120                compress1DLine(inputStream, outputStream, null, width);
    121                inputStream.flushCache();
    122                outputStream.flush();
    123            }
    124            return outputStream.toByteArray();
    125        }
    126    }
    127
    128    private static int compressT(final int a0, final int a1, final int b1, final BitArrayOutputStream outputStream, final int codingA0Color,
    129            final int[] codingLine) {
    130        final int a1b1 = a1 - b1;
    131        if (-3 <= a1b1 && a1b1 <= 3) {
    132            final T4_T6_Tables.Entry entry;
    133            switch (a1b1) {
    134            case -3:
    135                entry = T4_T6_Tables.VL3;
    136                break;
    137            case -2:
    138                entry = T4_T6_Tables.VL2;
    139                break;
    140            case -1:
    141                entry = T4_T6_Tables.VL1;
    142                break;
    143            case 0:
    144                entry = T4_T6_Tables.V0;
    145                break;
    146            case 1:
    147                entry = T4_T6_Tables.VR1;
    148                break;
    149            case 2:
    150                entry = T4_T6_Tables.VR2;
    151                break;
    152            default:
    153                entry = T4_T6_Tables.VR3;
    154                break;
    155            }
    156            entry.writeBits(outputStream);
    157            return a1;
    158        }
    159        final int a2 = nextChangingElement(codingLine, 1 - codingA0Color, a1 + 1);
    160        final int a0a1 = a1 - a0;
    161        final int a1a2 = a2 - a1;
    162        T4_T6_Tables.H.writeBits(outputStream);
    163        writeRunLength(outputStream, a0a1, codingA0Color);
    164        writeRunLength(outputStream, a1a2, 1 - codingA0Color);
    165        return a2;
    166    }
    167
    168    public static byte[] compressT4_1D(final byte[] uncompressed, final int width, final int height, final boolean hasFill) throws ImagingException {
    169        final BitInputStreamFlexible inputStream = new BitInputStreamFlexible(new ByteArrayInputStream(uncompressed));
    170        try (BitArrayOutputStream outputStream = new BitArrayOutputStream()) {
    171            if (hasFill) {
    172                T4_T6_Tables.EOL16.writeBits(outputStream);
    173            } else {
    174                T4_T6_Tables.EOL.writeBits(outputStream);
    175            }
    176
    177            for (int y = 0; y < height; y++) {
    178                compress1DLine(inputStream, outputStream, null, width);
    179                if (hasFill) {
    180                    int bitsAvailable = outputStream.getBitsAvailableInCurrentByte();
    181                    if (bitsAvailable < 4) {
    182                        outputStream.flush();
    183                        bitsAvailable = 8;
    184                    }
    185                    for (; bitsAvailable > 4; bitsAvailable--) {
    186                        outputStream.writeBit(0);
    187                    }
    188                }
    189                T4_T6_Tables.EOL.writeBits(outputStream);
    190                inputStream.flushCache();
    191            }
    192
    193            return outputStream.toByteArray();
    194        }
    195    }
    196
    197    public static byte[] compressT4_2D(final byte[] uncompressed, final int width, final int height, final boolean hasFill, final int parameterK)
    198            throws ImagingException {
    199        final BitInputStreamFlexible inputStream = new BitInputStreamFlexible(new ByteArrayInputStream(uncompressed));
    200        final BitArrayOutputStream outputStream = new BitArrayOutputStream();
    201        int[] referenceLine = Allocator.intArray(width);
    202        int[] codingLine = Allocator.intArray(width);
    203        int kCounter = 0;
    204        if (hasFill) {
    205            T4_T6_Tables.EOL16.writeBits(outputStream);
    206        } else {
    207            T4_T6_Tables.EOL.writeBits(outputStream);
    208        }
    209
    210        for (int y = 0; y < height; y++) {
    211            if (kCounter > 0) {
    212                // 2D
    213                outputStream.writeBit(0);
    214                for (int i = 0; i < width; i++) {
    215                    try {
    216                        codingLine[i] = inputStream.readBits(1);
    217                    } catch (final IOException ioException) {
    218                        throw new ImagingException("Error reading image to compress", ioException);
    219                    }
    220                }
    221                int codingA0Color = WHITE;
    222                int referenceA0Color = WHITE;
    223                int a1 = nextChangingElement(codingLine, codingA0Color, 0);
    224                int b1 = nextChangingElement(referenceLine, referenceA0Color, 0);
    225                int b2 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
    226                for (int a0 = 0; a0 < width;) {
    227                    if (b2 < a1) {
    228                        T4_T6_Tables.P.writeBits(outputStream);
    229                        a0 = b2;
    230                    } else {
    231                        a0 = compressT(a0, a1, b1, outputStream, codingA0Color, codingLine);
    232                        if (a0 == a1) {
    233                            codingA0Color = 1 - codingA0Color;
    234                        }
    235                    }
    236                    referenceA0Color = changingElementAt(referenceLine, a0);
    237                    a1 = nextChangingElement(codingLine, codingA0Color, a0 + 1);
    238                    if (codingA0Color == referenceA0Color) {
    239                        b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
    240                    } else {
    241                        b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
    242                        b1 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
    243                    }
    244                    b2 = nextChangingElement(referenceLine, 1 - codingA0Color, b1 + 1);
    245                }
    246                final int[] swap = referenceLine;
    247                referenceLine = codingLine;
    248                codingLine = swap;
    249            } else {
    250                // 1D
    251                outputStream.writeBit(1);
    252                compress1DLine(inputStream, outputStream, referenceLine, width);
    253            }
    254            if (hasFill) {
    255                int bitsAvailable = outputStream.getBitsAvailableInCurrentByte();
    256                if (bitsAvailable < 4) {
    257                    outputStream.flush();
    258                    bitsAvailable = 8;
    259                }
    260                for (; bitsAvailable > 4; bitsAvailable--) {
    261                    outputStream.writeBit(0);
    262                }
    263            }
    264            T4_T6_Tables.EOL.writeBits(outputStream);
    265            kCounter++;
    266            if (kCounter == parameterK) {
    267                kCounter = 0;
    268            }
    269            inputStream.flushCache();
    270        }
    271
    272        return outputStream.toByteArray();
    273    }
    274
    275    public static byte[] compressT6(final byte[] uncompressed, final int width, final int height) throws ImagingException {
    276        try (ByteArrayInputStream bais = new ByteArrayInputStream(uncompressed);
    277                BitInputStreamFlexible inputStream = new BitInputStreamFlexible(bais)) {
    278            final BitArrayOutputStream outputStream = new BitArrayOutputStream();
    279            int[] referenceLine = Allocator.intArray(width);
    280            int[] codingLine = Allocator.intArray(width);
    281            for (int y = 0; y < height; y++) {
    282                for (int i = 0; i < width; i++) {
    283                    try {
    284                        codingLine[i] = inputStream.readBits(1);
    285                    } catch (final IOException e) {
    286                        throw new ImagingException("Error reading image to compress", e);
    287                    }
    288                }
    289                int codingA0Color = WHITE;
    290                int referenceA0Color = WHITE;
    291                int a1 = nextChangingElement(codingLine, codingA0Color, 0);
    292                int b1 = nextChangingElement(referenceLine, referenceA0Color, 0);
    293                int b2 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
    294                for (int a0 = 0; a0 < width;) {
    295                    if (b2 < a1) {
    296                        T4_T6_Tables.P.writeBits(outputStream);
    297                        a0 = b2;
    298                    } else {
    299                        a0 = compressT(a0, a1, b1, outputStream, codingA0Color, codingLine);
    300                        if (a0 == a1) {
    301                            codingA0Color = 1 - codingA0Color;
    302                        }
    303                    }
    304                    referenceA0Color = changingElementAt(referenceLine, a0);
    305                    a1 = nextChangingElement(codingLine, codingA0Color, a0 + 1);
    306                    if (codingA0Color == referenceA0Color) {
    307                        b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
    308                    } else {
    309                        b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
    310                        b1 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
    311                    }
    312                    b2 = nextChangingElement(referenceLine, 1 - codingA0Color, b1 + 1);
    313                }
    314                final int[] swap = referenceLine;
    315                referenceLine = codingLine;
    316                codingLine = swap;
    317                inputStream.flushCache();
    318            }
    319            // EOFB
    320            T4_T6_Tables.EOL.writeBits(outputStream);
    321            T4_T6_Tables.EOL.writeBits(outputStream);
    322            return outputStream.toByteArray();
    323        } catch (final IOException ioException) {
    324            throw new ImagingException("I/O error", ioException);
    325        }
    326    }
    327
    328    /**
    329     * Decompresses the "Modified Huffman" encoding of section 10 in the TIFF6 specification. No EOLs, no RTC, rows are padded to end on a byte boundary.
    330     *
    331     * @param compressed compressed byte data
    332     * @param width      image width
    333     * @param height     image height
    334     * @return the compressed data
    335     * @throws ImagingException if it fails to read the compressed data
    336     */
    337    public static byte[] decompressModifiedHuffman(final byte[] compressed, final int width, final int height) throws ImagingException {
    338        try (ByteArrayInputStream baos = new ByteArrayInputStream(compressed);
    339                BitInputStreamFlexible inputStream = new BitInputStreamFlexible(baos);
    340                BitArrayOutputStream outputStream = new BitArrayOutputStream()) {
    341            for (int y = 0; y < height; y++) {
    342                int color = WHITE;
    343                int rowLength;
    344                for (rowLength = 0; rowLength < width;) {
    345                    final int runLength = readTotalRunLength(inputStream, color);
    346                    for (int i = 0; i < runLength; i++) {
    347                        outputStream.writeBit(color);
    348                    }
    349                    color = 1 - color;
    350                    rowLength += runLength;
    351                }
    352
    353                if (rowLength == width) {
    354                    inputStream.flushCache();
    355                    outputStream.flush();
    356                } else if (rowLength > width) {
    357                    throw new ImagingException("Unrecoverable row length error in image row " + y);
    358                }
    359            }
    360            return outputStream.toByteArray();
    361        } catch (final IOException ioException) {
    362            throw new ImagingException("Error reading image to decompress", ioException);
    363        }
    364    }
    365
    366    /**
    367     * Decompresses T.4 1D encoded data. EOL at the beginning and after each row, can be preceded by fill bits to fit on a byte boundary, no RTC.
    368     *
    369     * @param compressed compressed byte data
    370     * @param width      image width
    371     * @param height     image height
    372     * @param hasFill    used to check the end of line
    373     * @return the decompressed data
    374     * @throws ImagingException if it fails to read the compressed data
    375     */
    376    public static byte[] decompressT4_1D(final byte[] compressed, final int width, final int height, final boolean hasFill) throws ImagingException {
    377        final BitInputStreamFlexible inputStream = new BitInputStreamFlexible(new ByteArrayInputStream(compressed));
    378        try (BitArrayOutputStream outputStream = new BitArrayOutputStream()) {
    379            for (int y = 0; y < height; y++) {
    380                int rowLength;
    381                try {
    382                    final T4_T6_Tables.Entry entry = CONTROL_CODES.decode(inputStream);
    383                    if (!isEol(entry, hasFill)) {
    384                        throw new ImagingException("Expected EOL not found");
    385                    }
    386                    int color = WHITE;
    387                    for (rowLength = 0; rowLength < width;) {
    388                        final int runLength = readTotalRunLength(inputStream, color);
    389                        for (int i = 0; i < runLength; i++) {
    390                            outputStream.writeBit(color);
    391                        }
    392                        color = 1 - color;
    393                        rowLength += runLength;
    394                    }
    395                } catch (final ImagingException huffmanException) {
    396                    throw new ImagingException("Decompression error", huffmanException);
    397                }
    398
    399                if (rowLength == width) {
    400                    outputStream.flush();
    401                } else if (rowLength > width) {
    402                    throw new ImagingException("Unrecoverable row length error in image row " + y);
    403                }
    404            }
    405            return outputStream.toByteArray();
    406        }
    407    }
    408
    409    /**
    410     * Decompressed T.4 2D encoded data. EOL at the beginning and after each row, can be preceded by fill bits to fit on a byte boundary, and is succeeded by a
    411     * tag bit determining whether the next line is encoded using 1D or 2D. No RTC.
    412     *
    413     * @param compressed compressed byte data
    414     * @param width      image width
    415     * @param height     image height
    416     * @param hasFill    used to check the end of line
    417     * @return the decompressed data
    418     * @throws ImagingException if it fails to read the compressed data
    419     */
    420    public static byte[] decompressT4_2D(final byte[] compressed, final int width, final int height, final boolean hasFill) throws ImagingException {
    421        final BitInputStreamFlexible inputStream = new BitInputStreamFlexible(new ByteArrayInputStream(compressed));
    422        try (BitArrayOutputStream outputStream = new BitArrayOutputStream()) {
    423            final int[] referenceLine = Allocator.intArray(width);
    424            for (int y = 0; y < height; y++) {
    425                int rowLength = 0;
    426                try {
    427                    T4_T6_Tables.Entry entry = CONTROL_CODES.decode(inputStream);
    428                    if (!isEol(entry, hasFill)) {
    429                        throw new ImagingException("Expected EOL not found");
    430                    }
    431                    final int tagBit = inputStream.readBits(1);
    432                    if (tagBit == 0) {
    433                        // 2D
    434                        int codingA0Color = WHITE;
    435                        int referenceA0Color = WHITE;
    436                        int b1 = nextChangingElement(referenceLine, referenceA0Color, 0);
    437                        int b2 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
    438                        for (int a0 = 0; a0 < width;) {
    439                            final int a1;
    440                            final int a2;
    441                            entry = CONTROL_CODES.decode(inputStream);
    442                            if (entry == T4_T6_Tables.P) {
    443                                fillRange(outputStream, referenceLine, a0, b2, codingA0Color);
    444                                a0 = b2;
    445                            } else if (entry == T4_T6_Tables.H) {
    446                                final int a0a1 = readTotalRunLength(inputStream, codingA0Color);
    447                                a1 = a0 + a0a1;
    448                                fillRange(outputStream, referenceLine, a0, a1, codingA0Color);
    449                                final int a1a2 = readTotalRunLength(inputStream, 1 - codingA0Color);
    450                                a2 = a1 + a1a2;
    451                                fillRange(outputStream, referenceLine, a1, a2, 1 - codingA0Color);
    452                                a0 = a2;
    453                            } else {
    454                                final int a1b1;
    455                                if (entry == T4_T6_Tables.V0) {
    456                                    a1b1 = 0;
    457                                } else if (entry == T4_T6_Tables.VL1) {
    458                                    a1b1 = -1;
    459                                } else if (entry == T4_T6_Tables.VL2) {
    460                                    a1b1 = -2;
    461                                } else if (entry == T4_T6_Tables.VL3) {
    462                                    a1b1 = -3;
    463                                } else if (entry == T4_T6_Tables.VR1) {
    464                                    a1b1 = 1;
    465                                } else if (entry == T4_T6_Tables.VR2) {
    466                                    a1b1 = 2;
    467                                } else if (entry == T4_T6_Tables.VR3) {
    468                                    a1b1 = 3;
    469                                } else {
    470                                    throw new ImagingException("Invalid/unknown T.4 control code " + entry.bitString);
    471                                }
    472                                a1 = b1 + a1b1;
    473                                fillRange(outputStream, referenceLine, a0, a1, codingA0Color);
    474                                a0 = a1;
    475                                codingA0Color = 1 - codingA0Color;
    476                            }
    477                            referenceA0Color = changingElementAt(referenceLine, a0);
    478                            if (codingA0Color == referenceA0Color) {
    479                                b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
    480                            } else {
    481                                b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
    482                                b1 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
    483                            }
    484                            b2 = nextChangingElement(referenceLine, 1 - codingA0Color, b1 + 1);
    485                            rowLength = a0;
    486                        }
    487                    } else {
    488                        // 1D
    489                        int color = WHITE;
    490                        for (rowLength = 0; rowLength < width;) {
    491                            final int runLength = readTotalRunLength(inputStream, color);
    492                            for (int i = 0; i < runLength; i++) {
    493                                outputStream.writeBit(color);
    494                                referenceLine[rowLength + i] = color;
    495                            }
    496                            color = 1 - color;
    497                            rowLength += runLength;
    498                        }
    499                    }
    500                } catch (final IOException e) {
    501                    throw new ImagingException("Decompression error", e);
    502                }
    503
    504                if (rowLength == width) {
    505                    outputStream.flush();
    506                } else if (rowLength > width) {
    507                    throw new ImagingException("Unrecoverable row length error in image row " + y);
    508                }
    509            }
    510
    511            return outputStream.toByteArray();
    512        }
    513    }
    514
    515    /**
    516     * Decompress T.6 encoded data. No EOLs, except for 2 consecutive ones at the end (the EOFB, end of fax block). No RTC. No fill bits anywhere. All data is
    517     * 2D encoded.
    518     *
    519     * @param compressed compressed byte data
    520     * @param width      image width
    521     * @param height     image height
    522     * @return the decompressed data
    523     * @throws ImagingException if it fails to read the compressed data
    524     */
    525    public static byte[] decompressT6(final byte[] compressed, final int width, final int height) throws ImagingException {
    526        try (BitInputStreamFlexible inputStream = new BitInputStreamFlexible(new ByteArrayInputStream(compressed));
    527                BitArrayOutputStream outputStream = new BitArrayOutputStream()) {
    528            final int[] referenceLine = Allocator.intArray(width);
    529            for (int y = 0; y < height; y++) {
    530                int rowLength = 0;
    531                int codingA0Color = WHITE;
    532                int referenceA0Color = WHITE;
    533                int b1 = nextChangingElement(referenceLine, referenceA0Color, 0);
    534                int b2 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
    535                for (int a0 = 0; a0 < width;) {
    536                    final int a1;
    537                    final int a2;
    538                    final T4_T6_Tables.Entry entry = CONTROL_CODES.decode(inputStream);
    539                    if (entry == T4_T6_Tables.P) {
    540                        fillRange(outputStream, referenceLine, a0, b2, codingA0Color);
    541                        a0 = b2;
    542                    } else if (entry == T4_T6_Tables.H) {
    543                        final int a0a1 = readTotalRunLength(inputStream, codingA0Color);
    544                        a1 = a0 + a0a1;
    545                        fillRange(outputStream, referenceLine, a0, a1, codingA0Color);
    546                        final int a1a2 = readTotalRunLength(inputStream, 1 - codingA0Color);
    547                        a2 = a1 + a1a2;
    548                        fillRange(outputStream, referenceLine, a1, a2, 1 - codingA0Color);
    549                        a0 = a2;
    550                    } else {
    551                        final int a1b1;
    552                        if (entry == T4_T6_Tables.V0) {
    553                            a1b1 = 0;
    554                        } else if (entry == T4_T6_Tables.VL1) {
    555                            a1b1 = -1;
    556                        } else if (entry == T4_T6_Tables.VL2) {
    557                            a1b1 = -2;
    558                        } else if (entry == T4_T6_Tables.VL3) {
    559                            a1b1 = -3;
    560                        } else if (entry == T4_T6_Tables.VR1) {
    561                            a1b1 = 1;
    562                        } else if (entry == T4_T6_Tables.VR2) {
    563                            a1b1 = 2;
    564                        } else if (entry == T4_T6_Tables.VR3) {
    565                            a1b1 = 3;
    566                        } else {
    567                            throw new ImagingException("Invalid/unknown T.6 control code " + entry.bitString);
    568                        }
    569                        a1 = b1 + a1b1;
    570                        fillRange(outputStream, referenceLine, a0, a1, codingA0Color);
    571                        a0 = a1;
    572                        codingA0Color = 1 - codingA0Color;
    573                    }
    574                    referenceA0Color = changingElementAt(referenceLine, a0);
    575                    if (codingA0Color == referenceA0Color) {
    576                        b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
    577                    } else {
    578                        b1 = nextChangingElement(referenceLine, referenceA0Color, a0 + 1);
    579                        b1 = nextChangingElement(referenceLine, 1 - referenceA0Color, b1 + 1);
    580                    }
    581                    b2 = nextChangingElement(referenceLine, 1 - codingA0Color, b1 + 1);
    582                    rowLength = a0;
    583                }
    584                if (rowLength == width) {
    585                    outputStream.flush();
    586                } else if (rowLength > width) {
    587                    throw new ImagingException("Unrecoverable row length error in image row " + y);
    588                }
    589            }
    590            return outputStream.toByteArray();
    591        } catch (final IOException e) {
    592            if (e instanceof ImagingException) {
    593                throw (ImagingException) e;
    594            }
    595            // IOException cannot happen because the close() methods in use here do not throw
    596            throw new ImagingException("Closing stream", e);
    597        }
    598    }
    599
    600    private static void fillRange(final BitArrayOutputStream outputStream, final int[] referenceRow, final int a0, final int end, final int color) {
    601        for (int i = a0; i < end; i++) {
    602            referenceRow[i] = color;
    603            outputStream.writeBit(color);
    604        }
    605    }
    606
    607    private static boolean isEol(final T4_T6_Tables.Entry entry, final boolean hasFill) {
    608        if (entry == T4_T6_Tables.EOL) {
    609            return true;
    610        }
    611        if (hasFill) {
    612            return entry == T4_T6_Tables.EOL13 || entry == T4_T6_Tables.EOL14 || entry == T4_T6_Tables.EOL15 || entry == T4_T6_Tables.EOL16
    613                    || entry == T4_T6_Tables.EOL17 || entry == T4_T6_Tables.EOL18 || entry == T4_T6_Tables.EOL19;
    614        }
    615        return false;
    616    }
    617
    618    private static T4_T6_Tables.Entry lowerBound(final T4_T6_Tables.Entry[] entries, final int value) {
    619        int first = 0;
    620        int last = entries.length - 1;
    621        do {
    622            final int middle = first + last >>> 1;
    623            if (entries[middle].value <= value && (middle + 1 >= entries.length || value < entries[middle + 1].value)) {
    624                return entries[middle];
    625            }
    626            if (entries[middle].value > value) {
    627                last = middle - 1;
    628            } else {
    629                first = middle + 1;
    630            }
    631        } while (first < last);
    632
    633        return entries[first];
    634    }
    635
    636    private static int nextChangingElement(final int[] line, final int currentColour, final int start) {
    637        int position;
    638        for (position = start; position < line.length && line[position] == currentColour; position++) { // NOPMD
    639            // noop
    640        }
    641        return Math.min(position, line.length);
    642    }
    643
    644    private static int readTotalRunLength(final BitInputStreamFlexible bitStream, final int color) throws ImagingException {
    645        int totalLength = 0;
    646        Integer runLength;
    647        do {
    648            if (color == WHITE) {
    649                runLength = WHITE_RUN_LENGTHS.decode(bitStream);
    650            } else {
    651                runLength = BLACK_RUN_LENGTHS.decode(bitStream);
    652            }
    653            totalLength += runLength;
    654        } while (runLength > 63);
    655        return totalLength;
    656    }
    657
    658    private static void writeRunLength(final BitArrayOutputStream bitStream, int runLength, final int color) {
    659        final T4_T6_Tables.Entry[] makeUpCodes;
    660        final T4_T6_Tables.Entry[] terminatingCodes;
    661        if (color == WHITE) {
    662            makeUpCodes = T4_T6_Tables.WHITE_MAKE_UP_CODES;
    663            terminatingCodes = T4_T6_Tables.WHITE_TERMINATING_CODES;
    664        } else {
    665            makeUpCodes = T4_T6_Tables.BLACK_MAKE_UP_CODES;
    666            terminatingCodes = T4_T6_Tables.BLACK_TERMINATING_CODES;
    667        }
    668        while (runLength >= 1792) {
    669            final T4_T6_Tables.Entry entry = lowerBound(T4_T6_Tables.ADDITIONAL_MAKE_UP_CODES, runLength);
    670            entry.writeBits(bitStream);
    671            runLength -= entry.value;
    672        }
    673        while (runLength >= 64) {
    674            final T4_T6_Tables.Entry entry = lowerBound(makeUpCodes, runLength);
    675            entry.writeBits(bitStream);
    676            runLength -= entry.value;
    677        }
    678        final T4_T6_Tables.Entry terminatingEntry = terminatingCodes[runLength];
    679        terminatingEntry.writeBits(bitStream);
    680    }
    681
    682    private T4AndT6Compression() {
    683    }
    684}