1 /*
2  * RangeDecoder
3  *
4  * Authors: Lasse Collin <lasse.collin@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.DataInputStream;
14 import java.io.IOException;
15 
16 public abstract class RangeDecoder extends RangeCoder {
17     int range = 0;
18     int code = 0;
19 
normalize()20     public abstract void normalize() throws IOException;
21 
decodeBit(short[] probs, int index)22     public int decodeBit(short[] probs, int index) throws IOException {
23         normalize();
24 
25         int prob = probs[index];
26         int bound = (range >>> BIT_MODEL_TOTAL_BITS) * prob;
27         int bit;
28 
29         // Compare code and bound as if they were unsigned 32-bit integers.
30         if ((code ^ 0x80000000) < (bound ^ 0x80000000)) {
31             range = bound;
32             probs[index] = (short)(
33                     prob + ((BIT_MODEL_TOTAL - prob) >>> MOVE_BITS));
34             bit = 0;
35         } else {
36             range -= bound;
37             code -= bound;
38             probs[index] = (short)(prob - (prob >>> MOVE_BITS));
39             bit = 1;
40         }
41 
42         return bit;
43     }
44 
decodeBitTree(short[] probs)45     public int decodeBitTree(short[] probs) throws IOException {
46         int symbol = 1;
47 
48         do {
49             symbol = (symbol << 1) | decodeBit(probs, symbol);
50         } while (symbol < probs.length);
51 
52         return symbol - probs.length;
53     }
54 
decodeReverseBitTree(short[] probs)55     public int decodeReverseBitTree(short[] probs) throws IOException {
56         int symbol = 1;
57         int i = 0;
58         int result = 0;
59 
60         do {
61             int bit = decodeBit(probs, symbol);
62             symbol = (symbol << 1) | bit;
63             result |= bit << i++;
64         } while (symbol < probs.length);
65 
66         return result;
67     }
68 
decodeDirectBits(int count)69     public int decodeDirectBits(int count) throws IOException {
70         int result = 0;
71 
72         do {
73             normalize();
74 
75             range >>>= 1;
76             int t = (code - range) >>> 31;
77             code -= range & (t - 1);
78             result = (result << 1) | (1 - t);
79         } while (--count != 0);
80 
81         return result;
82     }
83 }
84