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}