1 /* 2 * RangeEncoder 3 * 4 * Authors: Lasse Collin <lasse.collin (at) tukaani.org> 5 * Igor Pavlov <http://7-zip.org/> 6 * 7 * This file has been put into the public domain. 8 * You can do whatever you want with this file. 9 */ 10 11 package org.tukaani.xz.rangecoder; 12 13 import java.io.OutputStream; 14 import java.io.IOException; 15 16 public final class RangeEncoder extends RangeCoder { 17 private static final int MOVE_REDUCING_BITS = 4; 18 private static final int BIT_PRICE_SHIFT_BITS = 4; 19 20 private static final int[] prices 21 = new int[BIT_MODEL_TOTAL >>> MOVE_REDUCING_BITS]; 22 23 private long low; 24 private int range; 25 26 // NOTE: int is OK for LZMA2 because a compressed chunk 27 // is not more than 64 KiB, but with LZMA1 there is no chunking 28 // so in theory cacheSize can grow very big. To be very safe, 29 // use long instead of int if you adapt this code for LZMA1. 30 private int cacheSize; 31 private byte cache; 32 33 private final byte[] buf; 34 private int bufPos; 35 36 static { 37 for (int i = (1 << MOVE_REDUCING_BITS) / 2; i < BIT_MODEL_TOTAL; 38 i += (1 << MOVE_REDUCING_BITS)) { 39 int w = i; 40 int bitCount = 0; 41 42 for (int j = 0; j < BIT_PRICE_SHIFT_BITS; ++j) { 43 w *= w; 44 bitCount <<= 1; 45 46 while ((w & 0xFFFF0000) != 0) { 47 w >>>= 1; 48 ++bitCount; 49 } 50 } 51 52 prices[i >> MOVE_REDUCING_BITS] 53 = (BIT_MODEL_TOTAL_BITS << BIT_PRICE_SHIFT_BITS) 54 - 15 - bitCount; 55 } 56 } 57 58 public RangeEncoder(int bufSize) { 59 buf = new byte[bufSize]; 60 reset(); 61 } 62 63 public void reset() { 64 low = 0; 65 range = 0xFFFFFFFF; 66 cache = 0x00; 67 cacheSize = 1; 68 bufPos = 0; 69 } 70 71 public int getPendingSize() { 72 return bufPos + cacheSize + 5 - 1; 73 } 74 75 public int finish() { 76 for (int i = 0; i < 5; ++i) 77 shiftLow(); 78 79 return bufPos; 80 } 81 82 public void write(OutputStream out) throws IOException { 83 out.write(buf, 0, bufPos); 84 } 85 86 private void shiftLow() { 87 int lowHi = (int)(low >>> 32); 88 89 if (lowHi != 0 || low < 0xFF000000L) { 90 int temp = cache; 91 92 do { 93 buf[bufPos++] = (byte)(temp + lowHi); 94 temp = 0xFF; 95 } while (--cacheSize != 0); 96 97 cache = (byte)(low >>> 24); 98 } 99 100 ++cacheSize; 101 low = (low & 0x00FFFFFF) << 8; 102 } 103 104 public void encodeBit(short[] probs, int index, int bit) { 105 int prob = probs[index]; 106 int bound = (range >>> BIT_MODEL_TOTAL_BITS) * prob; 107 108 // NOTE: Any non-zero value for bit is taken as 1. 109 if (bit == 0) { 110 range = bound; 111 probs[index] = (short)( 112 prob + ((BIT_MODEL_TOTAL - prob) >>> MOVE_BITS)); 113 } else { 114 low += bound & 0xFFFFFFFFL; 115 range -= bound; 116 probs[index] = (short)(prob - (prob >>> MOVE_BITS)); 117 } 118 119 if ((range & TOP_MASK) == 0) { 120 range <<= SHIFT_BITS; 121 shiftLow(); 122 } 123 } 124 125 public static int getBitPrice(int prob, int bit) { 126 // NOTE: Unlike in encodeBit(), here bit must be 0 or 1. 127 assert bit == 0 || bit == 1; 128 return prices[(prob ^ ((-bit) & (BIT_MODEL_TOTAL - 1))) 129 >>> MOVE_REDUCING_BITS]; 130 } 131 132 public void encodeBitTree(short[] probs, int symbol) { 133 int index = 1; 134 int mask = probs.length; 135 136 do { 137 mask >>>= 1; 138 int bit = symbol & mask; 139 encodeBit(probs, index, bit); 140 141 index <<= 1; 142 if (bit != 0) 143 index |= 1; 144 145 } while (mask != 1); 146 } 147 148 public static int getBitTreePrice(short[] probs, int symbol) { 149 int price = 0; 150 symbol |= probs.length; 151 152 do { 153 int bit = symbol & 1; 154 symbol >>>= 1; 155 price += getBitPrice(probs[symbol], bit); 156 } while (symbol != 1); 157 158 return price; 159 } 160 161 public void encodeReverseBitTree(short[] probs, int symbol) { 162 int index = 1; 163 symbol |= probs.length; 164 165 do { 166 int bit = symbol & 1; 167 symbol >>>= 1; 168 encodeBit(probs, index, bit); 169 index = (index << 1) | bit; 170 } while (symbol != 1); 171 } 172 173 public static int getReverseBitTreePrice(short[] probs, int symbol) { 174 int price = 0; 175 int index = 1; 176 symbol |= probs.length; 177 178 do { 179 int bit = symbol & 1; 180 symbol >>>= 1; 181 price += getBitPrice(probs[index], bit); 182 index = (index << 1) | bit; 183 } while (symbol != 1); 184 185 return price; 186 } 187 188 public void encodeDirectBits(int value, int count) { 189 do { 190 range >>>= 1; 191 low += range & (0 - ((value >>> --count) & 1)); 192 193 if ((range & TOP_MASK) == 0) { 194 range <<= SHIFT_BITS; 195 shiftLow(); 196 } 197 } while (count != 0); 198 } 199 200 public static int getDirectBitsPrice(int count) { 201 return count << BIT_PRICE_SHIFT_BITS; 202 } 203 } 204
