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