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            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                            int a1;
440                            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                                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                    int a1;
537                    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                        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++) {
639            // noop
640        }
641
642        return Math.min(position, line.length);
643    }
644
645    private static int readTotalRunLength(final BitInputStreamFlexible bitStream, final int color) throws ImagingException {
646        int totalLength = 0;
647        Integer runLength;
648        do {
649            if (color == WHITE) {
650                runLength = WHITE_RUN_LENGTHS.decode(bitStream);
651            } else {
652                runLength = BLACK_RUN_LENGTHS.decode(bitStream);
653            }
654            totalLength += runLength;
655        } while (runLength > 63);
656        return totalLength;
657    }
658
659    private static void writeRunLength(final BitArrayOutputStream bitStream, int runLength, final int color) {
660        final T4_T6_Tables.Entry[] makeUpCodes;
661        final T4_T6_Tables.Entry[] terminatingCodes;
662        if (color == WHITE) {
663            makeUpCodes = T4_T6_Tables.WHITE_MAKE_UP_CODES;
664            terminatingCodes = T4_T6_Tables.WHITE_TERMINATING_CODES;
665        } else {
666            makeUpCodes = T4_T6_Tables.BLACK_MAKE_UP_CODES;
667            terminatingCodes = T4_T6_Tables.BLACK_TERMINATING_CODES;
668        }
669        while (runLength >= 1792) {
670            final T4_T6_Tables.Entry entry = lowerBound(T4_T6_Tables.ADDITIONAL_MAKE_UP_CODES, runLength);
671            entry.writeBits(bitStream);
672            runLength -= entry.value;
673        }
674        while (runLength >= 64) {
675            final T4_T6_Tables.Entry entry = lowerBound(makeUpCodes, runLength);
676            entry.writeBits(bitStream);
677            runLength -= entry.value;
678        }
679        final T4_T6_Tables.Entry terminatingEntry = terminatingCodes[runLength];
680        terminatingEntry.writeBits(bitStream);
681    }
682
683    private T4AndT6Compression() {
684    }
685}