pdfbox-trunk/pdfbox/src/main/java/org/apache/pdfbox/filter/Predictor.java
/*
 * Copyright 2014 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.pdfbox.filter;

import java.io.FilterOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.util.Arrays;

import org.apache.pdfbox.cos.COSDictionary;
import org.apache.pdfbox.cos.COSName;

/**
 * Helper class to contain predictor decoding used by Flate and LZW filter. 
 * To see the history, look at the FlateFilter class.
 */
public final class Predictor
{

    private Predictor()
    {
    }

    /**
     * Decodes a single line of data in-place.
     * @param predictor Predictor value for the current line
     * @param colors Number of color components, from decode parameters.
     * @param bitsPerComponent Number of bits per components, from decode parameters.
     * @param columns Number samples in a row, from decode parameters.
     * @param actline Current (active) line to decode. Data will be decoded in-place,
     *                i.e. - the contents of this buffer will be modified.
     * @param lastline The previous decoded line. When decoding the first line, this
     *                 parameter should be an empty byte array of the same length as
     *                 <code>actline</code>.
     */
    static void decodePredictorRow(int predictor, int colors, int bitsPerComponent, int columns, byte[] actline, byte[] lastline)
    {
        if (predictor == 1)
        {
            // no prediction
            return;
        }
        final int bitsPerPixel = colors * bitsPerComponent;
        final int bytesPerPixel = (bitsPerPixel + 7) / 8;
        final int rowlength = actline.length;
        switch (predictor)
        {
            case 2:
                // PRED TIFF SUB
                if (bitsPerComponent == 8)
                {
                    // for 8 bits per component it is the same algorithm as PRED SUB of PNG format
                    for (int p = bytesPerPixel; p < rowlength; p++)
                    {
                        int sub = actline[p] & 0xff;
                        int left = actline[p - bytesPerPixel] & 0xff;
                        actline[p] = (byte) (sub + left);
                    }
                    break;
                }
                if (bitsPerComponent == 16)
                {
                    for (int p = bytesPerPixel; p < rowlength - 1; p += 2)
                    {
                        int sub = ((actline[p] & 0xff) << 8) + (actline[p + 1] & 0xff);
                        int left = (((actline[p - bytesPerPixel] & 0xff) << 8)
                                + (actline[p - bytesPerPixel + 1] & 0xff));
                        actline[p] = (byte) (((sub + left) >> 8) & 0xff);
                        actline[p + 1] = (byte) ((sub + left) & 0xff);
                    }
                    break;
                }
                if (bitsPerComponent == 1 && colors == 1)
                {
                    // bytesPerPixel cannot be used:
                    // "A row shall occupy a whole number of bytes, rounded up if necessary.
                    // Samples and their components shall be packed into bytes
                    // from high-order to low-order bits."
                    for (int p = 0; p < rowlength; p++)
                    {
                        for (int bit = 7; bit >= 0; --bit)
                        {
                            int sub = (actline[p] >> bit) & 1;
                            if (p == 0 && bit == 7)
                            {
                                continue;
                            }
                            int left;
                            if (bit == 7)
                            {
                                // use bit #0 from previous byte
                                left = actline[p - 1] & 1;
                            }
                            else
                            {
                                // use "previous" bit
                                left = (actline[p] >> (bit + 1)) & 1;
                            }
                            if (((sub + left) & 1) == 0)
                            {
                                // reset bit
                                actline[p] &= ~(1 << bit);
                            }
                            else
                            {
                                // set bit
                                actline[p] |= 1 << bit;
                            }
                        }
                    }
                    break;
                }
                // everything else, i.e. bpc 2 and 4, but has been tested for bpc 1 and 8 too
                int elements = columns * colors;
                for (int p = colors; p < elements; ++p)
                {
                    int bytePosSub = p * bitsPerComponent / 8;
                    int bitPosSub = 8 - p * bitsPerComponent % 8 - bitsPerComponent;
                    int bytePosLeft = (p - colors) * bitsPerComponent / 8;
                    int bitPosLeft = 8 - (p - colors) * bitsPerComponent % 8 - bitsPerComponent;

                    int sub = getBitSeq(actline[bytePosSub], bitPosSub, bitsPerComponent);
                    int left = getBitSeq(actline[bytePosLeft], bitPosLeft, bitsPerComponent);
                    actline[bytePosSub] = (byte) calcSetBitSeq(actline[bytePosSub], bitPosSub, bitsPerComponent, sub + left);
                }
                break;
            case 10:
                // PRED NONE
                // do nothing
                break;
            case 11:
                // PRED SUB
                for (int p = bytesPerPixel; p < rowlength; p++)
                {
                    int sub = actline[p];
                    int left = actline[p - bytesPerPixel];
                    actline[p] = (byte) (sub + left);
                }
                break;
            case 12:
                // PRED UP
                for (int p = 0; p < rowlength; p++)
                {
                    int up = actline[p] & 0xff;
                    int prior = lastline[p] & 0xff;
                    actline[p] = (byte) ((up + prior) & 0xff);
                }
                break;
            case 13:
                // PRED AVG
                for (int p = 0; p < rowlength; p++)
                {
                    int avg = actline[p] & 0xff;
                    int left = p - bytesPerPixel >= 0 ? actline[p - bytesPerPixel] & 0xff : 0;
                    int up = lastline[p] & 0xff;
                    actline[p] = (byte) ((avg + (left + up) / 2) & 0xff);
                }
                break;
            case 14:
                // PRED PAETH
                for (int p = 0; p < rowlength; p++)
                {
                    int paeth = actline[p] & 0xff;
                    int a = p - bytesPerPixel >= 0 ? actline[p - bytesPerPixel] & 0xff : 0;// left
                    int b = lastline[p] & 0xff;// upper
                    int c = p - bytesPerPixel >= 0 ? lastline[p - bytesPerPixel] & 0xff : 0;// upperleft
                    int value = a + b - c;
                    int absa = Math.abs(value - a);
                    int absb = Math.abs(value - b);
                    int absc = Math.abs(value - c);

                    if (absa <= absb && absa <= absc)
                    {
                        actline[p] = (byte) ((paeth + a) & 0xff);
                    }
                    else if (absb <= absc)
                    {
                        actline[p] = (byte) ((paeth + b) & 0xff);
                    }
                    else
                    {
                        actline[p] = (byte) ((paeth + c) & 0xff);
                    }
                }
                break;
            default:
                break;
        }
    }

    static int calculateRowLength(int colors, int bitsPerComponent, int columns)
    {
        final int bitsPerPixel = colors * bitsPerComponent;
        return  (columns * bitsPerPixel + 7) / 8;
    }
    
    // get value from bit interval from a byte
    static int getBitSeq(int by, int startBit, int bitSize)
    {
        int mask = ((1 << bitSize) - 1);
        return (by >>> startBit) & mask;
    }

    // set value in a bit interval and return that value
    static int calcSetBitSeq(int by, int startBit, int bitSize, int val)
    {
        int mask = ((1 << bitSize) - 1);
        int truncatedVal = val & mask;
        mask = ~(mask << startBit);
        return (by & mask) | (truncatedVal << startBit);
    }

    /**
     * Wraps and <code>OutputStream</code> in a predictor decoding stream as necessary.
     * If no predictor is specified by the parameters, the original stream is returned as is.
     *
     * @param out The stream to which decoded data should be written
     * @param decodeParams Decode parameters for the stream
     * @return An <code>OutputStream</code> is returned, which will write decoded data
     * into the given stream. If no predictor is specified, the original stream is returned.
     */
    static OutputStream wrapPredictor(OutputStream out, COSDictionary decodeParams)
    {
        int predictor = decodeParams.getInt(COSName.PREDICTOR);
        if (predictor > 1)
        {
            int colors = Math.min(decodeParams.getInt(COSName.COLORS, 1), 32);
            int bitsPerPixel = decodeParams.getInt(COSName.BITS_PER_COMPONENT, 8);
            int columns = decodeParams.getInt(COSName.COLUMNS, 1);

            return new PredictorOutputStream(out, predictor, colors, bitsPerPixel, columns);
        }
        else
        {
            return out;
        }
    }

    /**
     * Output stream that implements predictor decoding. Data is buffered until a complete
     * row is available, which is then decoded and written to the underlying stream.
     * The previous row is retained for decoding the next row.
     */
    private static final class PredictorOutputStream extends FilterOutputStream
    {
        // current predictor type
        private int predictor;
        // image decode parameters
        private final int colors;
        private final int bitsPerComponent;
        private final int columns;
        private final int rowLength;
        // PNG predictor (predictor>=10) means every row has a (potentially different)
        // predictor value
        private final boolean predictorPerRow;

        // data buffers
        private byte[] currentRow;
        private byte[] lastRow;
        // amount of data in the current row
        private int currentRowData = 0;
        // was the per-row predictor value read for the current row being processed
        private boolean predictorRead = false;

        PredictorOutputStream(OutputStream out, int predictor, int colors, int bitsPerComponent, int columns)
        {
            super(out);
            this.predictor = predictor;
            this.colors = colors;
            this.bitsPerComponent = bitsPerComponent;
            this.columns = columns;
            this.rowLength = calculateRowLength(colors, bitsPerComponent, columns);
            this.predictorPerRow = predictor >= 10;
            currentRow = new byte[rowLength];
            lastRow = new byte[rowLength];
        }

        @Override
        public void write(byte[] bytes) throws IOException
        {
            write(bytes, 0, bytes.length);
        }

        @Override
        public void write(byte[] bytes, int off, int len) throws IOException
        {
            int currentOffset = off;
            int maxOffset = currentOffset + len;
            while (currentOffset < maxOffset)
            {
                if (predictorPerRow && currentRowData == 0 && !predictorRead)
                {
                    // PNG predictor; each row starts with predictor type (0, 1, 2, 3, 4)
                    // read per line predictor, add 10 to tread value 0 as 10, 1 as 11, ...
                    predictor = bytes[currentOffset] + 10;
                    currentOffset++;
                    predictorRead = true;
                }
                else
                {
                    int toRead = Math.min(rowLength - currentRowData, maxOffset - currentOffset);
                    System.arraycopy(bytes, currentOffset, currentRow, currentRowData, toRead);
                    currentRowData += toRead;
                    currentOffset += toRead;

                    // current row is filled, decode it, write it to underlying stream,
                    // and reset the state.
                    if (currentRowData == currentRow.length)
                    {
                        decodeAndWriteRow();
                    }
                }
            }
        }

        private void decodeAndWriteRow() throws IOException
        {
            decodePredictorRow(predictor, colors, bitsPerComponent, columns, currentRow, lastRow);
            out.write(currentRow);
            flipRows();
        }

        /**
         * Flips the row buffers (to avoid copying), and resets the current-row index
         * and predictorRead flag
         */
        private void flipRows()
        {
            byte[] temp = lastRow;
            lastRow = currentRow;
            currentRow = temp;
            currentRowData = 0;
            predictorRead = false;
        }

        @Override
        public void flush() throws IOException
        {
            // The last row is allowed to be incomplete, and should be completed with zeros.
            if (currentRowData > 0)
            {
                Arrays.fill(currentRow, currentRowData, rowLength, (byte)0);
                decodeAndWriteRow();
            }
            super.flush();
        }

        @Override
        public void write(int i) throws IOException
        {
            throw new UnsupportedOperationException("Not supported");
        }
    }
}
