1 /* Copyright 2015 Google Inc. All Rights Reserved.
2 
3    Distributed under MIT license.
4    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5 */
6 
7 package org.brotli.dec;
8 
9 /**
10  * Bit reading helpers.
11  */
12 final class BitReader {
13 
14   // Possible values: {5, 6}.  5 corresponds to 32-bit build, 6 to 64-bit. This value is used for
15   // JIT conditional compilation.
16   private static final int LOG_BITNESS = Utils.getLogBintness();
17 
18   // Not only Java compiler prunes "if (const false)" code, but JVM as well.
19   // Code under "if (DEBUG != 0)" have zero performance impact (outside unit tests).
20   private static final int DEBUG = Utils.isDebugMode();
21 
22   static final int BITNESS = 1 << LOG_BITNESS;
23 
24   private static final int BYTENESS = BITNESS / 8;
25   private static final int CAPACITY = 4096;
26   // After encountering the end of the input stream, this amount of zero bytes will be appended.
27   private static final int SLACK = 64;
28   private static final int BUFFER_SIZE = CAPACITY + SLACK;
29   // Don't bother to replenish the buffer while this number of bytes is available.
30   private static final int SAFEGUARD = 36;
31   private static final int WATERLINE = CAPACITY - SAFEGUARD;
32 
33   // "Half" refers to "half of native integer type", i.e. on 64-bit machines it is 32-bit type,
34   // on 32-bit machines it is 16-bit.
35   private static final int HALF_BITNESS = BITNESS / 2;
36   private static final int HALF_SIZE = BYTENESS / 2;
37   private static final int HALVES_CAPACITY = CAPACITY / HALF_SIZE;
38   private static final int HALF_BUFFER_SIZE = BUFFER_SIZE / HALF_SIZE;
39   private static final int HALF_WATERLINE = WATERLINE / HALF_SIZE;
40 
41   private static final int LOG_HALF_SIZE = LOG_BITNESS - 4;
42 
43   /**
44    * Fills up the input buffer.
45    *
46    * <p> No-op if there are at least 36 bytes present after current position.
47    *
48    * <p> After encountering the end of the input stream, 64 additional zero bytes are copied to the
49    * buffer.
50    */
readMoreInput(State s)51   static void readMoreInput(State s) {
52     if (s.halfOffset > HALF_WATERLINE) {
53       doReadMoreInput(s);
54     }
55   }
56 
doReadMoreInput(State s)57   static void doReadMoreInput(State s) {
58     if (s.endOfStreamReached != 0) {
59       if (halfAvailable(s) >= -2) {
60         return;
61       }
62       throw new BrotliRuntimeException("No more input");
63     }
64     int readOffset = s.halfOffset << LOG_HALF_SIZE;
65     int bytesInBuffer = CAPACITY - readOffset;
66     // Move unused bytes to the head of the buffer.
67     Utils.copyBytesWithin(s.byteBuffer, 0, readOffset, CAPACITY);
68     s.halfOffset = 0;
69     while (bytesInBuffer < CAPACITY) {
70       int spaceLeft = CAPACITY - bytesInBuffer;
71       int len = Utils.readInput(s.input, s.byteBuffer, bytesInBuffer, spaceLeft);
72       // EOF is -1 in Java, but 0 in C#.
73       if (len <= 0) {
74         s.endOfStreamReached = 1;
75         s.tailBytes = bytesInBuffer;
76         bytesInBuffer += HALF_SIZE - 1;
77         break;
78       }
79       bytesInBuffer += len;
80     }
81     bytesToNibbles(s, bytesInBuffer);
82   }
83 
checkHealth(State s, int endOfStream)84   static void checkHealth(State s, int endOfStream) {
85     if (s.endOfStreamReached == 0) {
86       return;
87     }
88     int byteOffset = (s.halfOffset << LOG_HALF_SIZE) + ((s.bitOffset + 7) >> 3) - BYTENESS;
89     if (byteOffset > s.tailBytes) {
90       throw new BrotliRuntimeException("Read after end");
91     }
92     if ((endOfStream != 0) && (byteOffset != s.tailBytes)) {
93       throw new BrotliRuntimeException("Unused bytes after end");
94     }
95   }
96 
assertAccumulatorHealthy(State s)97   static void assertAccumulatorHealthy(State s) {
98     if (s.bitOffset > BITNESS) {
99       throw new IllegalStateException("Accumulator underloaded: " + s.bitOffset);
100     }
101   }
102 
fillBitWindow(State s)103   static void fillBitWindow(State s) {
104     if (DEBUG != 0) {
105       assertAccumulatorHealthy(s);
106     }
107     if (s.bitOffset >= HALF_BITNESS) {
108       // Same as doFillBitWindow. JVM fails to inline it.
109       if (BITNESS == 64) {
110         s.accumulator64 = ((long) s.intBuffer[s.halfOffset++] << HALF_BITNESS)
111             | (s.accumulator64 >>> HALF_BITNESS);
112       } else {
113         s.accumulator32 = ((int) s.shortBuffer[s.halfOffset++] << HALF_BITNESS)
114             | (s.accumulator32 >>> HALF_BITNESS);
115       }
116       s.bitOffset -= HALF_BITNESS;
117     }
118   }
119 
doFillBitWindow(State s)120   static void doFillBitWindow(State s) {
121     if (DEBUG != 0) {
122       assertAccumulatorHealthy(s);
123     }
124     if (BITNESS == 64) {
125       s.accumulator64 = ((long) s.intBuffer[s.halfOffset++] << HALF_BITNESS)
126           | (s.accumulator64 >>> HALF_BITNESS);
127     } else {
128       s.accumulator32 = ((int) s.shortBuffer[s.halfOffset++] << HALF_BITNESS)
129           | (s.accumulator32 >>> HALF_BITNESS);
130     }
131     s.bitOffset -= HALF_BITNESS;
132   }
133 
peekBits(State s)134   static int peekBits(State s) {
135     if (BITNESS == 64) {
136       return (int) (s.accumulator64 >>> s.bitOffset);
137     } else {
138       return s.accumulator32 >>> s.bitOffset;
139     }
140   }
141 
142   /**
143    * Fetches bits from accumulator.
144    *
145    * WARNING: accumulator MUST contain at least the specified amount of bits,
146    * otherwise BitReader will become broken.
147    */
readFewBits(State s, int n)148   static int readFewBits(State s, int n) {
149     int val = peekBits(s) & ((1 << n) - 1);
150     s.bitOffset += n;
151     return val;
152   }
153 
readBits(State s, int n)154   static int readBits(State s, int n) {
155     if (HALF_BITNESS >= 24) {
156       return readFewBits(s, n);
157     } else {
158       return (n <= 16) ? readFewBits(s, n) : readManyBits(s, n);
159     }
160   }
161 
readManyBits(State s, int n)162   private static int readManyBits(State s, int n) {
163     int low = readFewBits(s, 16);
164     doFillBitWindow(s);
165     return low | (readFewBits(s, n - 16) << 16);
166   }
167 
initBitReader(State s)168   static void initBitReader(State s) {
169     s.byteBuffer = new byte[BUFFER_SIZE];
170     if (BITNESS == 64) {
171       s.accumulator64 = 0;
172       s.intBuffer = new int[HALF_BUFFER_SIZE];
173     } else {
174       s.accumulator32 = 0;
175       s.shortBuffer = new short[HALF_BUFFER_SIZE];
176     }
177     s.bitOffset = BITNESS;
178     s.halfOffset = HALVES_CAPACITY;
179     s.endOfStreamReached = 0;
180     prepare(s);
181   }
182 
prepare(State s)183   private static void prepare(State s) {
184     readMoreInput(s);
185     checkHealth(s, 0);
186     doFillBitWindow(s);
187     doFillBitWindow(s);
188   }
189 
reload(State s)190   static void reload(State s) {
191     if (s.bitOffset == BITNESS) {
192       prepare(s);
193     }
194   }
195 
jumpToByteBoundary(State s)196   static void jumpToByteBoundary(State s) {
197     int padding = (BITNESS - s.bitOffset) & 7;
198     if (padding != 0) {
199       int paddingBits = readFewBits(s, padding);
200       if (paddingBits != 0) {
201         throw new BrotliRuntimeException("Corrupted padding bits");
202       }
203     }
204   }
205 
halfAvailable(State s)206   static int halfAvailable(State s) {
207     int limit = HALVES_CAPACITY;
208     if (s.endOfStreamReached != 0) {
209       limit = (s.tailBytes + (HALF_SIZE - 1)) >> LOG_HALF_SIZE;
210     }
211     return limit - s.halfOffset;
212   }
213 
copyBytes(State s, byte[] data, int offset, int length)214   static void copyBytes(State s, byte[] data, int offset, int length) {
215     if ((s.bitOffset & 7) != 0) {
216       throw new BrotliRuntimeException("Unaligned copyBytes");
217     }
218 
219     // Drain accumulator.
220     while ((s.bitOffset != BITNESS) && (length != 0)) {
221       data[offset++] = (byte) peekBits(s);
222       s.bitOffset += 8;
223       length--;
224     }
225     if (length == 0) {
226       return;
227     }
228 
229     // Get data from shadow buffer with "sizeof(int)" granularity.
230     int copyNibbles = Math.min(halfAvailable(s), length >> LOG_HALF_SIZE);
231     if (copyNibbles > 0) {
232       int readOffset = s.halfOffset << LOG_HALF_SIZE;
233       int delta = copyNibbles << LOG_HALF_SIZE;
234       System.arraycopy(s.byteBuffer, readOffset, data, offset, delta);
235       offset += delta;
236       length -= delta;
237       s.halfOffset += copyNibbles;
238     }
239     if (length == 0) {
240       return;
241     }
242 
243     // Read tail bytes.
244     if (halfAvailable(s) > 0) {
245       // length = 1..3
246       fillBitWindow(s);
247       while (length != 0) {
248         data[offset++] = (byte) peekBits(s);
249         s.bitOffset += 8;
250         length--;
251       }
252       checkHealth(s, 0);
253       return;
254     }
255 
256     // Now it is possible to copy bytes directly.
257     while (length > 0) {
258       int len = Utils.readInput(s.input, data, offset, length);
259       if (len == -1) {
260         throw new BrotliRuntimeException("Unexpected end of input");
261       }
262       offset += len;
263       length -= len;
264     }
265   }
266 
267   /**
268    * Translates bytes to halves (int/short).
269    */
bytesToNibbles(State s, int byteLen)270   static void bytesToNibbles(State s, int byteLen) {
271     byte[] byteBuffer = s.byteBuffer;
272     int halfLen = byteLen >> LOG_HALF_SIZE;
273     if (BITNESS == 64) {
274       int[] intBuffer = s.intBuffer;
275       for (int i = 0; i < halfLen; ++i) {
276         intBuffer[i] = ((byteBuffer[i * 4] & 0xFF))
277             | ((byteBuffer[(i * 4) + 1] & 0xFF) << 8)
278             | ((byteBuffer[(i * 4) + 2] & 0xFF) << 16)
279             | ((byteBuffer[(i * 4) + 3] & 0xFF) << 24);
280       }
281     } else {
282       short[] shortBuffer = s.shortBuffer;
283       for (int i = 0; i < halfLen; ++i) {
284         shortBuffer[i] = (short) ((byteBuffer[i * 2] & 0xFF)
285             | ((byteBuffer[(i * 2) + 1] & 0xFF) << 8));
286       }
287     }
288   }
289 }
290