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