Home | History | Annotate | Download | only in rangecoder 
      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.IOException;
     14 
     15 public abstract class RangeEncoder extends RangeCoder {
     16     private static final int MOVE_REDUCING_BITS = 4;
     17     private static final int BIT_PRICE_SHIFT_BITS = 4;
     18 
     19     private static final int[] prices
     20             = new int[BIT_MODEL_TOTAL >>> MOVE_REDUCING_BITS];
     21 
     22     private long low;
     23     private int range;
     24 
     25     // NOTE: int is OK for LZMA2 because a compressed chunk
     26     // is not more than 64 KiB, but with LZMA1 there is no chunking
     27     // so in theory cacheSize can grow very big. To be very safe,
     28     // use long instead of int since this code is used for LZMA1 too.
     29     long cacheSize;
     30     private byte cache;
     31 
     32     static {
     33         for (int i = (1 << MOVE_REDUCING_BITS) / 2; i < BIT_MODEL_TOTAL;
     34                 i += (1 << MOVE_REDUCING_BITS)) {
     35             int w = i;
     36             int bitCount = 0;
     37 
     38             for (int j = 0; j < BIT_PRICE_SHIFT_BITS; ++j) {
     39                 w *= w;
     40                 bitCount <<= 1;
     41 
     42                 while ((w & 0xFFFF0000) != 0) {
     43                     w >>>= 1;
     44                     ++bitCount;
     45                 }
     46             }
     47 
     48             prices[i >> MOVE_REDUCING_BITS]
     49                     = (BIT_MODEL_TOTAL_BITS << BIT_PRICE_SHIFT_BITS)
     50                       - 15 - bitCount;
     51         }
     52     }
     53 
     54     public void reset() {
     55         low = 0;
     56         range = 0xFFFFFFFF;
     57         cache = 0x00;
     58         cacheSize = 1;
     59     }
     60 
     61     public int getPendingSize() {
     62         // This function is only needed by users of RangeEncoderToBuffer,
     63         // but providing a must-be-never-called version here makes
     64         // LZMAEncoder simpler.
     65         throw new Error();
     66     }
     67 
     68     public int finish() throws IOException {
     69         for (int i = 0; i < 5; ++i)
     70             shiftLow();
     71 
     72         // RangeEncoderToBuffer.finish() needs a return value to tell
     73         // how big the finished buffer is. RangeEncoderToStream has no
     74         // buffer and thus no return value is needed. Here we use a dummy
     75         // value which can be overriden in RangeEncoderToBuffer.finish().
     76         return -1;
     77     }
     78 
     79     abstract void writeByte(int b) throws IOException;
     80 
     81     private void shiftLow() throws IOException {
     82         int lowHi = (int)(low >>> 32);
     83 
     84         if (lowHi != 0 || low < 0xFF000000L) {
     85             int temp = cache;
     86 
     87             do {
     88                 writeByte(temp + lowHi);
     89                 temp = 0xFF;
     90             } while (--cacheSize != 0);
     91 
     92             cache = (byte)(low >>> 24);
     93         }
     94 
     95         ++cacheSize;
     96         low = (low & 0x00FFFFFF) << 8;
     97     }
     98 
     99     public void encodeBit(short[] probs, int index, int bit)
    100             throws IOException {
    101         int prob = probs[index];
    102         int bound = (range >>> BIT_MODEL_TOTAL_BITS) * prob;
    103 
    104         // NOTE: Any non-zero value for bit is taken as 1.
    105         if (bit == 0) {
    106             range = bound;
    107             probs[index] = (short)(
    108                     prob + ((BIT_MODEL_TOTAL - prob) >>> MOVE_BITS));
    109         } else {
    110             low += bound & 0xFFFFFFFFL;
    111             range -= bound;
    112             probs[index] = (short)(prob - (prob >>> MOVE_BITS));
    113         }
    114 
    115         if ((range & TOP_MASK) == 0) {
    116             range <<= SHIFT_BITS;
    117             shiftLow();
    118         }
    119     }
    120 
    121     public static int getBitPrice(int prob, int bit) {
    122         // NOTE: Unlike in encodeBit(), here bit must be 0 or 1.
    123         assert bit == 0 || bit == 1;
    124         return prices[(prob ^ ((-bit) & (BIT_MODEL_TOTAL - 1)))
    125                       >>> MOVE_REDUCING_BITS];
    126     }
    127 
    128     public void encodeBitTree(short[] probs, int symbol) throws IOException {
    129         int index = 1;
    130         int mask = probs.length;
    131 
    132         do {
    133             mask >>>= 1;
    134             int bit = symbol & mask;
    135             encodeBit(probs, index, bit);
    136 
    137             index <<= 1;
    138             if (bit != 0)
    139                 index |= 1;
    140 
    141         } while (mask != 1);
    142     }
    143 
    144     public static int getBitTreePrice(short[] probs, int symbol) {
    145         int price = 0;
    146         symbol |= probs.length;
    147 
    148         do {
    149             int bit = symbol & 1;
    150             symbol >>>= 1;
    151             price += getBitPrice(probs[symbol], bit);
    152         } while (symbol != 1);
    153 
    154         return price;
    155     }
    156 
    157     public void encodeReverseBitTree(short[] probs, int symbol)
    158             throws IOException {
    159         int index = 1;
    160         symbol |= probs.length;
    161 
    162         do {
    163             int bit = symbol & 1;
    164             symbol >>>= 1;
    165             encodeBit(probs, index, bit);
    166             index = (index << 1) | bit;
    167         } while (symbol != 1);
    168     }
    169 
    170     public static int getReverseBitTreePrice(short[] probs, int symbol) {
    171         int price = 0;
    172         int index = 1;
    173         symbol |= probs.length;
    174 
    175         do {
    176             int bit = symbol & 1;
    177             symbol >>>= 1;
    178             price += getBitPrice(probs[index], bit);
    179             index = (index << 1) | bit;
    180         } while (symbol != 1);
    181 
    182         return price;
    183     }
    184 
    185     public void encodeDirectBits(int value, int count) throws IOException {
    186         do {
    187             range >>>= 1;
    188             low += range & (0 - ((value >>> --count) & 1));
    189 
    190             if ((range & TOP_MASK) == 0) {
    191                 range <<= SHIFT_BITS;
    192                 shiftLow();
    193             }
    194         } while (count != 0);
    195     }
    196 
    197     public static int getDirectBitsPrice(int count) {
    198         return count << BIT_PRICE_SHIFT_BITS;
    199     }
    200 }
    201