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