package com.dpforge.droidgif.decoder2.lzw;

import java.io.IOException;
import java.io.InputStream;

public class LZW {
	private final static int MAX_SIZE = 4096;

	private LZW() {
	}

	public static int decompress(final InputStream inputStream, final int minCodeSize, final byte[] indexStream) throws IOException {
		int codeSize = minCodeSize;
		final CodeStream codeStream = new CodeStream(inputStream, codeSize);

		int code;
		int clearCode = 1 << (minCodeSize - 1);
		int endCode = clearCode + 1;
		int lastIndex = endCode + 1;
		int prevCode = -1;
		int threshold = (1 << codeSize);
		int resultIndex = 0;

		short[] prefix = new short[MAX_SIZE];
		byte[] suffix = new byte[MAX_SIZE];

		for (code = 0; code < clearCode; ++code) {
			suffix[code] = (byte) code;
			prefix[code] = -1;
		}

		while (true) {
			code = codeStream.nextValue();
			if (code == clearCode) {
				codeSize = minCodeSize;
				codeStream.setCodeSize(codeSize);
				threshold = (1 << codeSize);
				lastIndex = endCode + 1;
				prevCode = codeStream.nextValue();
				indexStream[resultIndex++] = suffix[prevCode];
				continue;
			}
			if (code == endCode) {
				break;
			}

			byte k;
			if (code < lastIndex) { // code is in the code table
				int tmp = code;
				k = suffix[tmp];
				while (tmp >= 0) {
					k = suffix[tmp];
					indexStream[resultIndex++] = k;
					tmp = prefix[tmp];
				}
			} else { // not in code table
				int tmp = prevCode;
				k = suffix[tmp];
				while (tmp >= 0) {
					k = suffix[tmp];
					indexStream[resultIndex++] = k;
					tmp = prefix[tmp];
				}
				indexStream[resultIndex++] = k;
			}

			if (lastIndex < MAX_SIZE) {
				prefix[lastIndex] = (short) prevCode;
				suffix[lastIndex] = k;
				lastIndex++;

				if (lastIndex >= threshold && lastIndex < MAX_SIZE) {
					threshold <<= 1;
					codeSize++;
					codeStream.setCodeSize(codeSize);
				}
			}
			prevCode = code;
		}

		return resultIndex;
	}
}

@@ -789,16 +789,78 @@
 1;%0A%09%09%7D%0A%0A
+%09%09byte%5B%5D stack = new byte%5BMAX_SIZE + 1%5D;%0A%09%09int stackTop = 0;%0A%0A
 %09%09while 
@@ -1368,39 +1368,30 @@
 %5D;%0A%09%09%09%09%09
-indexStream%5BresultIndex
+stack%5BstackTop
 ++%5D = k;
@@ -1549,39 +1549,30 @@
 %5D;%0A%09%09%09%09%09
-indexStream%5BresultIndex
+stack%5BstackTop
 ++%5D = k;
@@ -1602,16 +1602,75 @@
 ;%0A%09%09%09%09%7D%0A
+%09%09%09%09stack%5BstackTop++%5D = k;%0A%09%09%09%7D%0A%0A%09%09%09while (stackTop %3E 0) %7B%0A
 %09%09%09%09inde
@@ -1690,25 +1690,41 @@
 tIndex++%5D = 
-k
+stack%5B--stackTop%5D
 ;%0A%09%09%09%7D%0A%0A%09%09%09i

Fix LZW with stack