Index: trunk/src/org/tukaani/xz/rangecoder/RangeCoder.java =================================================================== --- trunk/src/org/tukaani/xz/rangecoder/RangeCoder.java (revision 15662) +++ (revision ) @@ -1,26 +1,0 @@ -/* - * RangeCoder - * - * Authors: Lasse Collin - * Igor Pavlov - * - * This file has been put into the public domain. - * You can do whatever you want with this file. - */ - -package org.tukaani.xz.rangecoder; - -import java.util.Arrays; - -public abstract class RangeCoder { - static final int SHIFT_BITS = 8; - static final int TOP_MASK = 0xFF000000; - static final int BIT_MODEL_TOTAL_BITS = 11; - static final int BIT_MODEL_TOTAL = 1 << BIT_MODEL_TOTAL_BITS; - static final short PROB_INIT = (short)(BIT_MODEL_TOTAL / 2); - static final int MOVE_BITS = 5; - - public static final void initProbs(short[] probs) { - Arrays.fill(probs, PROB_INIT); - } -} Index: trunk/src/org/tukaani/xz/rangecoder/RangeDecoder.java =================================================================== --- trunk/src/org/tukaani/xz/rangecoder/RangeDecoder.java (revision 15662) +++ (revision ) @@ -1,83 +1,0 @@ -/* - * RangeDecoder - * - * Authors: Lasse Collin - * Igor Pavlov - * - * This file has been put into the public domain. - * You can do whatever you want with this file. - */ - -package org.tukaani.xz.rangecoder; - -import java.io.DataInputStream; -import java.io.IOException; - -public abstract class RangeDecoder extends RangeCoder { - int range = 0; - int code = 0; - - public abstract void normalize() throws IOException; - - public int decodeBit(short[] probs, int index) throws IOException { - normalize(); - - int prob = probs[index]; - int bound = (range >>> BIT_MODEL_TOTAL_BITS) * prob; - int bit; - - // Compare code and bound as if they were unsigned 32-bit integers. - if ((code ^ 0x80000000) < (bound ^ 0x80000000)) { - range = bound; - probs[index] = (short)( - prob + ((BIT_MODEL_TOTAL - prob) >>> MOVE_BITS)); - bit = 0; - } else { - range -= bound; - code -= bound; - probs[index] = (short)(prob - (prob >>> MOVE_BITS)); - bit = 1; - } - - return bit; - } - - public int decodeBitTree(short[] probs) throws IOException { - int symbol = 1; - - do { - symbol = (symbol << 1) | decodeBit(probs, symbol); - } while (symbol < probs.length); - - return symbol - probs.length; - } - - public int decodeReverseBitTree(short[] probs) throws IOException { - int symbol = 1; - int i = 0; - int result = 0; - - do { - int bit = decodeBit(probs, symbol); - symbol = (symbol << 1) | bit; - result |= bit << i++; - } while (symbol < probs.length); - - return result; - } - - public int decodeDirectBits(int count) throws IOException { - int result = 0; - - do { - normalize(); - - range >>>= 1; - int t = (code - range) >>> 31; - code -= range & (t - 1); - result = (result << 1) | (1 - t); - } while (--count != 0); - - return result; - } -} Index: trunk/src/org/tukaani/xz/rangecoder/RangeDecoderFromBuffer.java =================================================================== --- trunk/src/org/tukaani/xz/rangecoder/RangeDecoderFromBuffer.java (revision 15662) +++ (revision ) @@ -1,71 +1,0 @@ -/* - * RangeDecoderFromBuffer - * - * Authors: Lasse Collin - * Igor Pavlov - * - * This file has been put into the public domain. - * You can do whatever you want with this file. - */ - -package org.tukaani.xz.rangecoder; - -import java.io.DataInputStream; -import java.io.IOException; -import org.tukaani.xz.ArrayCache; -import org.tukaani.xz.CorruptedInputException; - -public final class RangeDecoderFromBuffer extends RangeDecoder { - private static final int INIT_SIZE = 5; - - private final byte[] buf; - private int pos; - - public RangeDecoderFromBuffer(int inputSizeMax, ArrayCache arrayCache) { - // We will use the *end* of the array so if the cache gives us - // a bigger-than-requested array, we still want to use buf.length. - buf = arrayCache.getByteArray(inputSizeMax - INIT_SIZE, false); - pos = buf.length; - } - - public void putArraysToCache(ArrayCache arrayCache) { - arrayCache.putArray(buf); - } - - public void prepareInputBuffer(DataInputStream in, int len) - throws IOException { - if (len < INIT_SIZE) - throw new CorruptedInputException(); - - if (in.readUnsignedByte() != 0x00) - throw new CorruptedInputException(); - - code = in.readInt(); - range = 0xFFFFFFFF; - - // Read the data to the end of the buffer. If the data is corrupt - // and the decoder, reading from buf, tries to read past the end of - // the data, ArrayIndexOutOfBoundsException will be thrown and - // the problem is detected immediately. - len -= INIT_SIZE; - pos = buf.length - len; - in.readFully(buf, pos, len); - } - - public boolean isFinished() { - return pos == buf.length && code == 0; - } - - public void normalize() throws IOException { - if ((range & TOP_MASK) == 0) { - try { - // If the input is corrupt, this might throw - // ArrayIndexOutOfBoundsException. - code = (code << SHIFT_BITS) | (buf[pos++] & 0xFF); - range <<= SHIFT_BITS; - } catch (ArrayIndexOutOfBoundsException e) { - throw new CorruptedInputException(); - } - } - } -} Index: trunk/src/org/tukaani/xz/rangecoder/RangeEncoder.java =================================================================== --- trunk/src/org/tukaani/xz/rangecoder/RangeEncoder.java (revision 15662) +++ (revision ) @@ -1,200 +1,0 @@ -/* - * RangeEncoder - * - * Authors: Lasse Collin - * Igor Pavlov - * - * This file has been put into the public domain. - * You can do whatever you want with this file. - */ - -package org.tukaani.xz.rangecoder; - -import java.io.IOException; - -public abstract class RangeEncoder extends RangeCoder { - private static final int MOVE_REDUCING_BITS = 4; - private static final int BIT_PRICE_SHIFT_BITS = 4; - - private static final int[] prices - = new int[BIT_MODEL_TOTAL >>> MOVE_REDUCING_BITS]; - - private long low; - private int range; - - // NOTE: int is OK for LZMA2 because a compressed chunk - // is not more than 64 KiB, but with LZMA1 there is no chunking - // so in theory cacheSize can grow very big. To be very safe, - // use long instead of int since this code is used for LZMA1 too. - long cacheSize; - private byte cache; - - static { - for (int i = (1 << MOVE_REDUCING_BITS) / 2; i < BIT_MODEL_TOTAL; - i += (1 << MOVE_REDUCING_BITS)) { - int w = i; - int bitCount = 0; - - for (int j = 0; j < BIT_PRICE_SHIFT_BITS; ++j) { - w *= w; - bitCount <<= 1; - - while ((w & 0xFFFF0000) != 0) { - w >>>= 1; - ++bitCount; - } - } - - prices[i >> MOVE_REDUCING_BITS] - = (BIT_MODEL_TOTAL_BITS << BIT_PRICE_SHIFT_BITS) - - 15 - bitCount; - } - } - - public void reset() { - low = 0; - range = 0xFFFFFFFF; - cache = 0x00; - cacheSize = 1; - } - - public int getPendingSize() { - // This function is only needed by users of RangeEncoderToBuffer, - // but providing a must-be-never-called version here makes - // LZMAEncoder simpler. - throw new Error(); - } - - public int finish() throws IOException { - for (int i = 0; i < 5; ++i) - shiftLow(); - - // RangeEncoderToBuffer.finish() needs a return value to tell - // how big the finished buffer is. RangeEncoderToStream has no - // buffer and thus no return value is needed. Here we use a dummy - // value which can be overridden in RangeEncoderToBuffer.finish(). - return -1; - } - - abstract void writeByte(int b) throws IOException; - - private void shiftLow() throws IOException { - int lowHi = (int)(low >>> 32); - - if (lowHi != 0 || low < 0xFF000000L) { - int temp = cache; - - do { - writeByte(temp + lowHi); - temp = 0xFF; - } while (--cacheSize != 0); - - cache = (byte)(low >>> 24); - } - - ++cacheSize; - low = (low & 0x00FFFFFF) << 8; - } - - public void encodeBit(short[] probs, int index, int bit) - throws IOException { - int prob = probs[index]; - int bound = (range >>> BIT_MODEL_TOTAL_BITS) * prob; - - // NOTE: Any non-zero value for bit is taken as 1. - if (bit == 0) { - range = bound; - probs[index] = (short)( - prob + ((BIT_MODEL_TOTAL - prob) >>> MOVE_BITS)); - } else { - low += bound & 0xFFFFFFFFL; - range -= bound; - probs[index] = (short)(prob - (prob >>> MOVE_BITS)); - } - - if ((range & TOP_MASK) == 0) { - range <<= SHIFT_BITS; - shiftLow(); - } - } - - public static int getBitPrice(int prob, int bit) { - // NOTE: Unlike in encodeBit(), here bit must be 0 or 1. - assert bit == 0 || bit == 1; - return prices[(prob ^ ((-bit) & (BIT_MODEL_TOTAL - 1))) - >>> MOVE_REDUCING_BITS]; - } - - public void encodeBitTree(short[] probs, int symbol) throws IOException { - int index = 1; - int mask = probs.length; - - do { - mask >>>= 1; - int bit = symbol & mask; - encodeBit(probs, index, bit); - - index <<= 1; - if (bit != 0) - index |= 1; - - } while (mask != 1); - } - - public static int getBitTreePrice(short[] probs, int symbol) { - int price = 0; - symbol |= probs.length; - - do { - int bit = symbol & 1; - symbol >>>= 1; - price += getBitPrice(probs[symbol], bit); - } while (symbol != 1); - - return price; - } - - public void encodeReverseBitTree(short[] probs, int symbol) - throws IOException { - int index = 1; - symbol |= probs.length; - - do { - int bit = symbol & 1; - symbol >>>= 1; - encodeBit(probs, index, bit); - index = (index << 1) | bit; - } while (symbol != 1); - } - - public static int getReverseBitTreePrice(short[] probs, int symbol) { - int price = 0; - int index = 1; - symbol |= probs.length; - - do { - int bit = symbol & 1; - symbol >>>= 1; - price += getBitPrice(probs[index], bit); - index = (index << 1) | bit; - } while (symbol != 1); - - return price; - } - - public void encodeDirectBits(int value, int count) throws IOException { - do { - range >>>= 1; - low += range & (0 - ((value >>> --count) & 1)); - - if ((range & TOP_MASK) == 0) { - range <<= SHIFT_BITS; - shiftLow(); - } - } while (count != 0); - } - - public static int getDirectBitsPrice(int count) { - return count << BIT_PRICE_SHIFT_BITS; - } -} Index: trunk/src/org/tukaani/xz/rangecoder/RangeEncoderToBuffer.java =================================================================== --- trunk/src/org/tukaani/xz/rangecoder/RangeEncoderToBuffer.java (revision 15662) +++ (revision ) @@ -1,59 +1,0 @@ -/* - * RangeEncoderToBuffer - * - * Authors: Lasse Collin - * Igor Pavlov - * - * This file has been put into the public domain. - * You can do whatever you want with this file. - */ - -package org.tukaani.xz.rangecoder; - -import java.io.OutputStream; -import java.io.IOException; -import org.tukaani.xz.ArrayCache; - -public final class RangeEncoderToBuffer extends RangeEncoder { - private final byte[] buf; - private int bufPos; - - public RangeEncoderToBuffer(int bufSize, ArrayCache arrayCache) { - buf = arrayCache.getByteArray(bufSize, false); - reset(); - } - - public void putArraysToCache(ArrayCache arrayCache) { - arrayCache.putArray(buf); - } - - public void reset() { - super.reset(); - bufPos = 0; - } - - public int getPendingSize() { - // With LZMA2 it is known that cacheSize fits into an int. - return bufPos + (int)cacheSize + 5 - 1; - } - - public int finish() { - // super.finish() cannot throw an IOException because writeByte() - // provided in this file cannot throw an IOException. - try { - super.finish(); - } catch (IOException e) { - throw new Error(); - } - - return bufPos; - } - - public void write(OutputStream out) throws IOException { - out.write(buf, 0, bufPos); - } - - void writeByte(int b) { - buf[bufPos++] = (byte)b; - } -}