pdfbox-trunk/pdfbox/src/main/java/org/apache/pdfbox/filter/CCITTFaxEncoderStream.java
/*
 * Copyright (c) 2013, Harald Kuhr
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name "TwelveMonkeys" nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.apache.pdfbox.filter;

import java.io.IOException;
import java.io.OutputStream;

/**
 * CCITT Modified Group 4 (T6) fax compression.
 *
 * @author <a href="mailto:mail@schmidor.de">Oliver Schmidtmer</a>
 *
 * Taken from commit 047884e3d9e1b30516c79b147ead763303dc9bcb of 21.4.2016 from
 * twelvemonkeys/imageio/plugins/tiff/CCITTFaxEncoderStream.java
 *
 * Initial changes for PDFBox:
 * - removed Validate
 * - G4 compression only
 * - removed options
 */
final class CCITTFaxEncoderStream extends OutputStream {
    
    private int currentBufferLength = 0;
    private final byte[] inputBuffer;
    private final int inputBufferLength;
    private final int columns;
    private final int rows;

    private int[] changesCurrentRow;
    private int[] changesReferenceRow;
    private int currentRow = 0;
    private int changesCurrentRowLength = 0;
    private int changesReferenceRowLength = 0;
    private byte outputBuffer = 0;
    private byte outputBufferBitLength = 0;
    private final int fillOrder;
    private final OutputStream stream;

    CCITTFaxEncoderStream(final OutputStream stream, final int columns, final int rows, final int fillOrder) {

        this.stream = stream;
        this.columns = columns;
        this.rows = rows;
        this.fillOrder = fillOrder;

        this.changesReferenceRow = new int[columns];
        this.changesCurrentRow = new int[columns];
        
        inputBufferLength = (columns + 7) / 8;
        inputBuffer = new byte[inputBufferLength];
    }

    @Override
    public void write(int b) throws IOException {
        inputBuffer[currentBufferLength] = (byte) b;
        currentBufferLength++;

        if (currentBufferLength == inputBufferLength) {
            encodeRow();
            currentBufferLength = 0;
        }
    }

    @Override
    public void flush() throws IOException {
        stream.flush();
    }

    @Override
    public void close() throws IOException {
        stream.close();
    }

    private void encodeRow() throws IOException {
        currentRow++;
        int[] tmp = changesReferenceRow;
        changesReferenceRow = changesCurrentRow;
        changesCurrentRow = tmp;
        changesReferenceRowLength = changesCurrentRowLength;
        changesCurrentRowLength = 0;

        int index = 0;
        boolean white = true;
        while (index < columns) {
            int byteIndex = index / 8;
            int bit = index % 8;
            if ((((inputBuffer[byteIndex] >> (7 - bit)) & 1) == 1) == (white)) {
                changesCurrentRow[changesCurrentRowLength] = index;
                changesCurrentRowLength++;
                white = !white;
            }
            index++;
        }

        encodeRowType6();

        if (currentRow == rows) {
            writeEOL();
            writeEOL();
            fill();
        }
    }


    private void encodeRowType6() throws IOException {
        encode2D();
    }

    private int[] getNextChanges(int pos, boolean white) {
        int[] result = new int[] {columns, columns};
        for (int i = 0; i < changesCurrentRowLength; i++) {
            if (pos < changesCurrentRow[i] || (pos == 0 && white)) {
                result[0] = changesCurrentRow[i];
                if ((i + 1) < changesCurrentRowLength) {
                    result[1] = changesCurrentRow[i + 1];
                }
                break;
            }
        }

        return result;
    }

    private void writeRun(int runLength, boolean white) throws IOException {
        int nonterm = runLength / 64;
        Code[] codes = white ? WHITE_NONTERMINATING_CODES : BLACK_NONTERMINATING_CODES;
        while (nonterm > 0) {
            if (nonterm >= codes.length) {
                write(codes[codes.length - 1].code, codes[codes.length - 1].length);
                nonterm -= codes.length;
            }
            else {
                write(codes[nonterm - 1].code, codes[nonterm - 1].length);
                nonterm = 0;
            }
        }

        Code c = white ? WHITE_TERMINATING_CODES[runLength % 64] : BLACK_TERMINATING_CODES[runLength % 64];
        write(c.code, c.length);
    }

    private void encode2D() throws IOException {
        boolean white = true;
        int index = 0; // a0
        while (index < columns) {
            int[] nextChanges = getNextChanges(index, white); // a1, a2

            int[] nextRefs = getNextRefChanges(index, white); // b1, b2

            int difference = nextChanges[0] - nextRefs[0];
            if (nextChanges[0] > nextRefs[1]) {
                // PMODE
                write(1, 4);
                index = nextRefs[1];
            }
            else if (difference > 3 || difference < -3) {
                // HMODE
                write(1, 3);
                writeRun(nextChanges[0] - index, white);
                writeRun(nextChanges[1] - nextChanges[0], !white);
                index = nextChanges[1];

            }
            else {
                // VMODE
                switch (difference) {
                    case 0:
                        write(1, 1);
                        break;
                    case 1:
                        write(3, 3);
                        break;
                    case 2:
                        write(3, 6);
                        break;
                    case 3:
                        write(3, 7);
                        break;
                    case -1:
                        write(2, 3);
                        break;
                    case -2:
                        write(2, 6);
                        break;
                    case -3:
                        write(2, 7);
                        break;
                    default:
                        break;
                }
                white = !white;
                index = nextRefs[0] + difference;
            }
        }
    }

    private int[] getNextRefChanges(int a0, boolean white) {
        int[] result = new int[] {columns, columns};
        for (int i = (white ? 0 : 1); i < changesReferenceRowLength; i += 2) {
            if (changesReferenceRow[i] > a0 || (a0 == 0 && i == 0)) {
                result[0] = changesReferenceRow[i];
                if ((i + 1) < changesReferenceRowLength) {
                    result[1] = changesReferenceRow[i + 1];
                }
                break;
            }
        }
        return result;
    }

    private void write(int code, int codeLength) throws IOException {

        for (int i = 0; i < codeLength; i++) {
            boolean codeBit = ((code >> (codeLength - i - 1)) & 1) == 1;
            if (fillOrder == TIFFExtension.FILL_LEFT_TO_RIGHT) {
                outputBuffer |= (codeBit ? 1 << (7 - ((outputBufferBitLength) % 8)) : 0);
            }
            else {
                outputBuffer |= (codeBit ? 1 << (((outputBufferBitLength) % 8)) : 0);
            }
            outputBufferBitLength++;

            if (outputBufferBitLength == 8) {
                stream.write(outputBuffer);
                clearOutputBuffer();
            }
        }
    }

    private void writeEOL() throws IOException {
        write(1, 12);
    }

    private void fill() throws IOException {
        if (outputBufferBitLength != 0) {
            stream.write(outputBuffer);
        }
        clearOutputBuffer();
    }

    private void clearOutputBuffer() {
        outputBuffer = 0;
        outputBufferBitLength = 0;
    }

    private static class Code {
        private Code(int code, int length) {
            this.code = code;
            this.length = length;
        }

        final int code;
        final int length;
    }

    private static final Code[] WHITE_TERMINATING_CODES;

    private static final Code[] WHITE_NONTERMINATING_CODES;

    private static final Code[] BLACK_TERMINATING_CODES;

    private static final Code[] BLACK_NONTERMINATING_CODES;

    static {
        // Setup HUFFMAN Codes
        WHITE_TERMINATING_CODES = new Code[64];
        WHITE_NONTERMINATING_CODES = new Code[40];
        for (int i = 0; i < CCITTFaxDecoderStream.WHITE_CODES.length; i++) {
            int bitLength = i + 4;
            for (int j = 0; j < CCITTFaxDecoderStream.WHITE_CODES[i].length; j++) {
                int value = CCITTFaxDecoderStream.WHITE_RUN_LENGTHS[i][j];
                int code = CCITTFaxDecoderStream.WHITE_CODES[i][j];

                if (value < 64) {
                    WHITE_TERMINATING_CODES[value] = new Code(code, bitLength);
                }
                else {
                    WHITE_NONTERMINATING_CODES[(value / 64) - 1] = new Code(code, bitLength);
                }
            }
        }

        BLACK_TERMINATING_CODES = new Code[64];
        BLACK_NONTERMINATING_CODES = new Code[40];
        for (int i = 0; i < CCITTFaxDecoderStream.BLACK_CODES.length; i++) {
            int bitLength = i + 2;
            for (int j = 0; j < CCITTFaxDecoderStream.BLACK_CODES[i].length; j++) {
                int value = CCITTFaxDecoderStream.BLACK_RUN_LENGTHS[i][j];
                int code = CCITTFaxDecoderStream.BLACK_CODES[i][j];

                if (value < 64) {
                    BLACK_TERMINATING_CODES[value] = new Code(code, bitLength);
                }
                else {
                    BLACK_NONTERMINATING_CODES[(value / 64) - 1] = new Code(code, bitLength);
                }
            }
        }
    }
}
