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