    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.mylzw;
    018
    019import java.io.ByteArrayOutputStream;
    020import java.io.IOException;
    021import java.io.InputStream;
    022import java.io.OutputStream;
    023import java.nio.ByteOrder;
    024
    025import org.apache.commons.imaging.ImageReadException;
    026
    027public final class MyLzwDecompressor {
    028    private static final int MAX_TABLE_SIZE = 1 << 12;
    029    private final byte[][] table;
    030    private int codeSize;
    031    private final int initialCodeSize;
    032    private int codes = -1;
    033    private final ByteOrder byteOrder;
    034    private final Listener listener;
    035    private final int clearCode;
    036    private final int eoiCode;
    037    private int written;
    038    private boolean tiffLZWMode;
    039
    040    public interface Listener {
    041        void code(int code);
    042
    043        void init(int clearCode, int eoiCode);
    044    }
    045
    046    public MyLzwDecompressor(final int initialCodeSize, final ByteOrder byteOrder) throws ImageReadException {
    047        this(initialCodeSize, byteOrder, null);
    048    }
    049
    050    public MyLzwDecompressor(final int initialCodeSize, final ByteOrder byteOrder,
    051            final Listener listener) throws ImageReadException {
    052        this.listener = listener;
    053        this.byteOrder = byteOrder;
    054
    055        this.initialCodeSize = initialCodeSize;
    056
    057        table = new byte[MAX_TABLE_SIZE][];
    058        clearCode = 1 << initialCodeSize;
    059        eoiCode = clearCode + 1;
    060
    061        if (null != listener) {
    062            listener.init(clearCode, eoiCode);
    063        }
    064
    065        initializeTable();
    066    }
    067
    068    private void initializeTable() throws ImageReadException {
    069        codeSize = initialCodeSize;
    070
    071        final int initialEntriesCount = 1 << codeSize + 2;
    072
    073        if (initialEntriesCount > table.length) {
    074            throw new ImageReadException(String.format("Invalid Lzw table length [%d]; entries count is [%d]", table.length, initialEntriesCount));
    075        }
    076
    077        for (int i = 0; i < initialEntriesCount; i++) {
    078            table[i] = new byte[] { (byte) i, };
    079        }
    080    }
    081
    082    private void clearTable() {
    083        codes = (1 << initialCodeSize) + 2;
    084        codeSize = initialCodeSize;
    085        incrementCodeSize();
    086    }
    087
    088    private int getNextCode(final MyBitInputStream is) throws IOException {
    089        final int code = is.readBits(codeSize);
    090
    091        if (null != listener) {
    092            listener.code(code);
    093        }
    094        return code;
    095    }
    096
    097    private byte[] stringFromCode(final int code) throws IOException {
    098        if ((code >= codes) || (code < 0)) {
    099            throw new IOException("Bad Code: " + code + " codes: " + codes
    100                    + " code_size: " + codeSize + ", table: " + table.length);
    101        }
    102        return table[code];
    103    }
    104
    105    private boolean isInTable(final int code) {
    106        return code < codes;
    107    }
    108
    109    private byte firstChar(final byte[] bytes) {
    110        return bytes[0];
    111    }
    112
    113    private void addStringToTable(final byte[] bytes) {
    114        if (codes < (1 << codeSize)) {
    115            table[codes] = bytes;
    116            codes++;
    117        }
    118        // If the table already full, then we simply ignore these bytes
    119        // per the https://www.w3.org/Graphics/GIF/spec-gif89a.txt 'spec'.
    120
    121        checkCodeSize();
    122    }
    123
    124    private byte[] appendBytes(final byte[] bytes, final byte b) {
    125        final byte[] result = new byte[bytes.length + 1];
    126
    127        System.arraycopy(bytes, 0, result, 0, bytes.length);
    128        result[result.length - 1] = b;
    129        return result;
    130    }
    131
    132    private void writeToResult(final OutputStream os, final byte[] bytes)
    133            throws IOException {
    134        os.write(bytes);
    135        written += bytes.length;
    136    }
    137
    138    public void setTiffLZWMode() {
    139        tiffLZWMode = true;
    140    }
    141
    142    public byte[] decompress(final InputStream is, final int expectedLength) throws IOException {
    143        int code;
    144        int oldCode = -1;
    145        final MyBitInputStream mbis = new MyBitInputStream(is, byteOrder);
    146        if (tiffLZWMode) {
    147            mbis.setTiffLZWMode();
    148        }
    149
    150        final ByteArrayOutputStream baos = new ByteArrayOutputStream(expectedLength);
    151
    152        clearTable();
    153
    154        while ((code = getNextCode(mbis)) != eoiCode) {
    155            if (code == clearCode) {
    156                clearTable();
    157
    158                if (written >= expectedLength) {
    159                    break;
    160                }
    161                code = getNextCode(mbis);
    162
    163                if (code == eoiCode) {
    164                    break;
    165                }
    166                writeToResult(baos, stringFromCode(code));
    167
    168                oldCode = code;
    169            } else {
    170                if (isInTable(code)) {
    171                    writeToResult(baos, stringFromCode(code));
    172
    173                    addStringToTable(appendBytes(stringFromCode(oldCode),
    174                            firstChar(stringFromCode(code))));
    175                    oldCode = code;
    176                } else {
    177                    final byte[] outString = appendBytes(stringFromCode(oldCode),
    178                            firstChar(stringFromCode(oldCode)));
    179                    writeToResult(baos, outString);
    180                    addStringToTable(outString);
    181                    oldCode = code;
    182                }
    183            }
    184
    185            if (written >= expectedLength) {
    186                break;
    187            }
    188        }
    189
    190        return baos.toByteArray();
    191    }
    192
    193    private void checkCodeSize() {
    194        int limit = (1 << codeSize);
    195        if (tiffLZWMode) {
    196            limit--;
    197        }
    198
    199        if (codes == limit) {
    200            incrementCodeSize();
    201        }
    202    }
    203
    204    private void incrementCodeSize() {
    205        if (codeSize != 12) {
    206            codeSize++;
    207        }
    208    }
    209}