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 import static org.brotli.dec.RunningState.BLOCK_START; 10 import static org.brotli.dec.RunningState.CLOSED; 11 import static org.brotli.dec.RunningState.COMPRESSED_BLOCK_START; 12 import static org.brotli.dec.RunningState.COPY_LOOP; 13 import static org.brotli.dec.RunningState.COPY_UNCOMPRESSED; 14 import static org.brotli.dec.RunningState.COPY_WRAP_BUFFER; 15 import static org.brotli.dec.RunningState.FINISHED; 16 import static org.brotli.dec.RunningState.INSERT_LOOP; 17 import static org.brotli.dec.RunningState.MAIN_LOOP; 18 import static org.brotli.dec.RunningState.READ_METADATA; 19 import static org.brotli.dec.RunningState.TRANSFORM; 20 import static org.brotli.dec.RunningState.UNINITIALIZED; 21 import static org.brotli.dec.RunningState.WRITE; 22 23 /** 24 * API for Brotli decompression. 25 */ 26 final class Decode { 27 28 private static final int DEFAULT_CODE_LENGTH = 8; 29 private static final int CODE_LENGTH_REPEAT_CODE = 16; 30 private static final int NUM_LITERAL_CODES = 256; 31 private static final int NUM_INSERT_AND_COPY_CODES = 704; 32 private static final int NUM_BLOCK_LENGTH_CODES = 26; 33 private static final int LITERAL_CONTEXT_BITS = 6; 34 private static final int DISTANCE_CONTEXT_BITS = 2; 35 36 private static final int HUFFMAN_TABLE_BITS = 8; 37 private static final int HUFFMAN_TABLE_MASK = 0xFF; 38 39 private static final int CODE_LENGTH_CODES = 18; 40 private static final int[] CODE_LENGTH_CODE_ORDER = { 41 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15, 42 }; 43 44 private static final int NUM_DISTANCE_SHORT_CODES = 16; 45 private static final int[] DISTANCE_SHORT_CODE_INDEX_OFFSET = { 46 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 47 }; 48 49 private static final int[] DISTANCE_SHORT_CODE_VALUE_OFFSET = { 50 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3 51 }; 52 53 /** 54 * Static Huffman code for the code length code lengths. 55 */ 56 private static final int[] FIXED_TABLE = { 57 0x020000, 0x020004, 0x020003, 0x030002, 0x020000, 0x020004, 0x020003, 0x040001, 58 0x020000, 0x020004, 0x020003, 0x030002, 0x020000, 0x020004, 0x020003, 0x040005 59 }; 60 61 /** 62 * Decodes a number in the range [0..255], by reading 1 - 11 bits. 63 */ 64 private static int decodeVarLenUnsignedByte(BitReader br) { 65 if (BitReader.readBits(br, 1) != 0) { 66 int n = BitReader.readBits(br, 3); 67 if (n == 0) { 68 return 1; 69 } else { 70 return BitReader.readBits(br, n) + (1 << n); 71 } 72 } 73 return 0; 74 } 75 76 private static void decodeMetaBlockLength(BitReader br, State state) { 77 state.inputEnd = BitReader.readBits(br, 1) == 1; 78 state.metaBlockLength = 0; 79 state.isUncompressed = false; 80 state.isMetadata = false; 81 if (state.inputEnd && BitReader.readBits(br, 1) != 0) { 82 return; 83 } 84 int sizeNibbles = BitReader.readBits(br, 2) + 4; 85 if (sizeNibbles == 7) { 86 state.isMetadata = true; 87 if (BitReader.readBits(br, 1) != 0) { 88 throw new BrotliRuntimeException("Corrupted reserved bit"); 89 } 90 int sizeBytes = BitReader.readBits(br, 2); 91 if (sizeBytes == 0) { 92 return; 93 } 94 for (int i = 0; i < sizeBytes; i++) { 95 int bits = BitReader.readBits(br, 8); 96 if (bits == 0 && i + 1 == sizeBytes && sizeBytes > 1) { 97 throw new BrotliRuntimeException("Exuberant nibble"); 98 } 99 state.metaBlockLength |= bits << (i * 8); 100 } 101 } else { 102 for (int i = 0; i < sizeNibbles; i++) { 103 int bits = BitReader.readBits(br, 4); 104 if (bits == 0 && i + 1 == sizeNibbles && sizeNibbles > 4) { 105 throw new BrotliRuntimeException("Exuberant nibble"); 106 } 107 state.metaBlockLength |= bits << (i * 4); 108 } 109 } 110 state.metaBlockLength++; 111 if (!state.inputEnd) { 112 state.isUncompressed = BitReader.readBits(br, 1) == 1; 113 } 114 } 115 116 /** 117 * Decodes the next Huffman code from bit-stream. 118 */ 119 private static int readSymbol(int[] table, int offset, BitReader br) { 120 int val = (int) (br.accumulator >>> br.bitOffset); 121 offset += val & HUFFMAN_TABLE_MASK; 122 int bits = table[offset] >> 16; 123 int sym = table[offset] & 0xFFFF; 124 if (bits <= HUFFMAN_TABLE_BITS) { 125 br.bitOffset += bits; 126 return sym; 127 } 128 offset += sym; 129 offset += (val & ((1L << bits) - 1)) >>> HUFFMAN_TABLE_BITS; 130 br.bitOffset += ((table[offset] >> 16) + HUFFMAN_TABLE_BITS); 131 return table[offset] & 0xFFFF; 132 } 133 134 private static int readBlockLength(int[] table, int offset, BitReader br) { 135 BitReader.fillBitWindow(br); 136 int code = readSymbol(table, offset, br); 137 int n = Prefix.BLOCK_LENGTH_N_BITS[code]; 138 return Prefix.BLOCK_LENGTH_OFFSET[code] + BitReader.readBits(br, n); 139 } 140 141 private static int translateShortCodes(int code, int[] ringBuffer, int index) { 142 if (code < NUM_DISTANCE_SHORT_CODES) { 143 index += DISTANCE_SHORT_CODE_INDEX_OFFSET[code]; 144 index &= 3; 145 return ringBuffer[index] + DISTANCE_SHORT_CODE_VALUE_OFFSET[code]; 146 } 147 return code - NUM_DISTANCE_SHORT_CODES + 1; 148 } 149 150 private static void moveToFront(int[] v, int index) { 151 int value = v[index]; 152 for (; index > 0; index--) { 153 v[index] = v[index - 1]; 154 } 155 v[0] = value; 156 } 157 158 private static void inverseMoveToFrontTransform(byte[] v, int vLen) { 159 int[] mtf = new int[256]; 160 for (int i = 0; i < 256; i++) { 161 mtf[i] = i; 162 } 163 for (int i = 0; i < vLen; i++) { 164 int index = v[i] & 0xFF; 165 v[i] = (byte) mtf[index]; 166 if (index != 0) { 167 moveToFront(mtf, index); 168 } 169 } 170 } 171 172 private static void readHuffmanCodeLengths( 173 int[] codeLengthCodeLengths, int numSymbols, int[] codeLengths, BitReader br) { 174 int symbol = 0; 175 int prevCodeLen = DEFAULT_CODE_LENGTH; 176 int repeat = 0; 177 int repeatCodeLen = 0; 178 int space = 32768; 179 int[] table = new int[32]; 180 181 Huffman.buildHuffmanTable(table, 0, 5, codeLengthCodeLengths, CODE_LENGTH_CODES); 182 183 while (symbol < numSymbols && space > 0) { 184 BitReader.readMoreInput(br); 185 BitReader.fillBitWindow(br); 186 int p = (int) ((br.accumulator >>> br.bitOffset)) & 31; 187 br.bitOffset += table[p] >> 16; 188 int codeLen = table[p] & 0xFFFF; 189 if (codeLen < CODE_LENGTH_REPEAT_CODE) { 190 repeat = 0; 191 codeLengths[symbol++] = codeLen; 192 if (codeLen != 0) { 193 prevCodeLen = codeLen; 194 space -= 32768 >> codeLen; 195 } 196 } else { 197 int extraBits = codeLen - 14; 198 int newLen = 0; 199 if (codeLen == CODE_LENGTH_REPEAT_CODE) { 200 newLen = prevCodeLen; 201 } 202 if (repeatCodeLen != newLen) { 203 repeat = 0; 204 repeatCodeLen = newLen; 205 } 206 int oldRepeat = repeat; 207 if (repeat > 0) { 208 repeat -= 2; 209 repeat <<= extraBits; 210 } 211 repeat += BitReader.readBits(br, extraBits) + 3; 212 int repeatDelta = repeat - oldRepeat; 213 if (symbol + repeatDelta > numSymbols) { 214 throw new BrotliRuntimeException("symbol + repeatDelta > numSymbols"); // COV_NF_LINE 215 } 216 for (int i = 0; i < repeatDelta; i++) { 217 codeLengths[symbol++] = repeatCodeLen; 218 } 219 if (repeatCodeLen != 0) { 220 space -= repeatDelta << (15 - repeatCodeLen); 221 } 222 } 223 } 224 if (space != 0) { 225 throw new BrotliRuntimeException("Unused space"); // COV_NF_LINE 226 } 227 // TODO: Pass max_symbol to Huffman table builder instead? 228 Utils.fillWithZeroes(codeLengths, symbol, numSymbols - symbol); 229 } 230 231 // TODO: Use specialized versions for smaller tables. 232 static void readHuffmanCode(int alphabetSize, int[] table, int offset, BitReader br) { 233 boolean ok = true; 234 int simpleCodeOrSkip; 235 BitReader.readMoreInput(br); 236 // TODO: Avoid allocation. 237 int[] codeLengths = new int[alphabetSize]; 238 simpleCodeOrSkip = BitReader.readBits(br, 2); 239 if (simpleCodeOrSkip == 1) { // Read symbols, codes & code lengths directly. 240 int maxBitsCounter = alphabetSize - 1; 241 int maxBits = 0; 242 int[] symbols = new int[4]; 243 int numSymbols = BitReader.readBits(br, 2) + 1; 244 while (maxBitsCounter != 0) { 245 maxBitsCounter >>= 1; 246 maxBits++; 247 } 248 // TODO: uncomment when codeLengths is reused. 249 // Utils.fillWithZeroes(codeLengths, 0, alphabetSize); 250 for (int i = 0; i < numSymbols; i++) { 251 symbols[i] = BitReader.readBits(br, maxBits) % alphabetSize; 252 codeLengths[symbols[i]] = 2; 253 } 254 codeLengths[symbols[0]] = 1; 255 switch (numSymbols) { 256 case 1: 257 break; 258 case 2: 259 ok = symbols[0] != symbols[1]; 260 codeLengths[symbols[1]] = 1; 261 break; 262 case 3: 263 ok = symbols[0] != symbols[1] && symbols[0] != symbols[2] && symbols[1] != symbols[2]; 264 break; 265 case 4: 266 default: 267 ok = symbols[0] != symbols[1] && symbols[0] != symbols[2] && symbols[0] != symbols[3] 268 && symbols[1] != symbols[2] && symbols[1] != symbols[3] && symbols[2] != symbols[3]; 269 if (BitReader.readBits(br, 1) == 1) { 270 codeLengths[symbols[2]] = 3; 271 codeLengths[symbols[3]] = 3; 272 } else { 273 codeLengths[symbols[0]] = 2; 274 } 275 break; 276 } 277 } else { // Decode Huffman-coded code lengths. 278 int[] codeLengthCodeLengths = new int[CODE_LENGTH_CODES]; 279 int space = 32; 280 int numCodes = 0; 281 for (int i = simpleCodeOrSkip; i < CODE_LENGTH_CODES && space > 0; i++) { 282 int codeLenIdx = CODE_LENGTH_CODE_ORDER[i]; 283 BitReader.fillBitWindow(br); 284 int p = (int) (br.accumulator >>> br.bitOffset) & 15; 285 // TODO: Demultiplex FIXED_TABLE. 286 br.bitOffset += FIXED_TABLE[p] >> 16; 287 int v = FIXED_TABLE[p] & 0xFFFF; 288 codeLengthCodeLengths[codeLenIdx] = v; 289 if (v != 0) { 290 space -= (32 >> v); 291 numCodes++; 292 } 293 } 294 ok = (numCodes == 1 || space == 0); 295 readHuffmanCodeLengths(codeLengthCodeLengths, alphabetSize, codeLengths, br); 296 } 297 if (!ok) { 298 throw new BrotliRuntimeException("Can't readHuffmanCode"); // COV_NF_LINE 299 } 300 Huffman.buildHuffmanTable(table, offset, HUFFMAN_TABLE_BITS, codeLengths, alphabetSize); 301 } 302 303 private static int decodeContextMap(int contextMapSize, byte[] contextMap, BitReader br) { 304 BitReader.readMoreInput(br); 305 int numTrees = decodeVarLenUnsignedByte(br) + 1; 306 307 if (numTrees == 1) { 308 Utils.fillWithZeroes(contextMap, 0, contextMapSize); 309 return numTrees; 310 } 311 312 boolean useRleForZeros = BitReader.readBits(br, 1) == 1; 313 int maxRunLengthPrefix = 0; 314 if (useRleForZeros) { 315 maxRunLengthPrefix = BitReader.readBits(br, 4) + 1; 316 } 317 int[] table = new int[Huffman.HUFFMAN_MAX_TABLE_SIZE]; 318 readHuffmanCode(numTrees + maxRunLengthPrefix, table, 0, br); 319 for (int i = 0; i < contextMapSize; ) { 320 BitReader.readMoreInput(br); 321 BitReader.fillBitWindow(br); 322 int code = readSymbol(table, 0, br); 323 if (code == 0) { 324 contextMap[i] = 0; 325 i++; 326 } else if (code <= maxRunLengthPrefix) { 327 int reps = (1 << code) + BitReader.readBits(br, code); 328 while (reps != 0) { 329 if (i >= contextMapSize) { 330 throw new BrotliRuntimeException("Corrupted context map"); // COV_NF_LINE 331 } 332 contextMap[i] = 0; 333 i++; 334 reps--; 335 } 336 } else { 337 contextMap[i] = (byte) (code - maxRunLengthPrefix); 338 i++; 339 } 340 } 341 if (BitReader.readBits(br, 1) == 1) { 342 inverseMoveToFrontTransform(contextMap, contextMapSize); 343 } 344 return numTrees; 345 } 346 347 private static void decodeBlockTypeAndLength(State state, int treeType) { 348 final BitReader br = state.br; 349 final int[] ringBuffers = state.blockTypeRb; 350 final int offset = treeType * 2; 351 BitReader.fillBitWindow(br); 352 int blockType = readSymbol( 353 state.blockTypeTrees, treeType * Huffman.HUFFMAN_MAX_TABLE_SIZE, br); 354 state.blockLength[treeType] = readBlockLength(state.blockLenTrees, 355 treeType * Huffman.HUFFMAN_MAX_TABLE_SIZE, br); 356 357 if (blockType == 1) { 358 blockType = ringBuffers[offset + 1] + 1; 359 } else if (blockType == 0) { 360 blockType = ringBuffers[offset]; 361 } else { 362 blockType -= 2; 363 } 364 if (blockType >= state.numBlockTypes[treeType]) { 365 blockType -= state.numBlockTypes[treeType]; 366 } 367 ringBuffers[offset] = ringBuffers[offset + 1]; 368 ringBuffers[offset + 1] = blockType; 369 } 370 371 private static void decodeLiteralBlockSwitch(State state) { 372 decodeBlockTypeAndLength(state, 0); 373 int literalBlockType = state.blockTypeRb[1]; 374 state.contextMapSlice = literalBlockType << LITERAL_CONTEXT_BITS; 375 state.literalTreeIndex = state.contextMap[state.contextMapSlice] & 0xFF; 376 state.literalTree = state.hGroup0.trees[state.literalTreeIndex]; 377 int contextMode = state.contextModes[literalBlockType]; 378 state.contextLookupOffset1 = Context.LOOKUP_OFFSETS[contextMode]; 379 state.contextLookupOffset2 = Context.LOOKUP_OFFSETS[contextMode + 1]; 380 } 381 382 private static void decodeCommandBlockSwitch(State state) { 383 decodeBlockTypeAndLength(state, 1); 384 state.treeCommandOffset = state.hGroup1.trees[state.blockTypeRb[3]]; 385 } 386 387 private static void decodeDistanceBlockSwitch(State state) { 388 decodeBlockTypeAndLength(state, 2); 389 state.distContextMapSlice = state.blockTypeRb[5] << DISTANCE_CONTEXT_BITS; 390 } 391 392 private static void maybeReallocateRingBuffer(State state) { 393 int newSize = state.maxRingBufferSize; 394 if ((long) newSize > state.expectedTotalSize) { 395 /* TODO: Handle 2GB+ cases more gracefully. */ 396 int minimalNewSize = (int) state.expectedTotalSize + state.customDictionary.length; 397 while ((newSize >> 1) > minimalNewSize) { 398 newSize >>= 1; 399 } 400 if (!state.inputEnd && newSize < 16384 && state.maxRingBufferSize >= 16384) { 401 newSize = 16384; 402 } 403 } 404 if (newSize <= state.ringBufferSize) { 405 return; 406 } 407 int ringBufferSizeWithSlack = newSize + Dictionary.MAX_TRANSFORMED_WORD_LENGTH; 408 byte[] newBuffer = new byte[ringBufferSizeWithSlack]; 409 if (state.ringBuffer != null) { 410 System.arraycopy(state.ringBuffer, 0, newBuffer, 0, state.ringBufferSize); 411 } else { 412 /* Prepend custom dictionary, if any. */ 413 if (state.customDictionary.length != 0) { 414 int length = state.customDictionary.length; 415 int offset = 0; 416 if (length > state.maxBackwardDistance) { 417 offset = length - state.maxBackwardDistance; 418 length = state.maxBackwardDistance; 419 } 420 System.arraycopy(state.customDictionary, offset, newBuffer, 0, length); 421 state.pos = length; 422 state.bytesToIgnore = length; 423 } 424 } 425 state.ringBuffer = newBuffer; 426 state.ringBufferSize = newSize; 427 } 428 429 /** 430 * Reads next metablock header. 431 * 432 * @param state decoding state 433 */ 434 private static void readMetablockInfo(State state) { 435 final BitReader br = state.br; 436 437 if (state.inputEnd) { 438 state.nextRunningState = FINISHED; 439 state.bytesToWrite = state.pos; 440 state.bytesWritten = 0; 441 state.runningState = WRITE; 442 return; 443 } 444 // TODO: Reset? Do we need this? 445 state.hGroup0.codes = null; 446 state.hGroup0.trees = null; 447 state.hGroup1.codes = null; 448 state.hGroup1.trees = null; 449 state.hGroup2.codes = null; 450 state.hGroup2.trees = null; 451 452 BitReader.readMoreInput(br); 453 decodeMetaBlockLength(br, state); 454 if (state.metaBlockLength == 0 && !state.isMetadata) { 455 return; 456 } 457 if (state.isUncompressed || state.isMetadata) { 458 BitReader.jumpToByteBoundary(br); 459 state.runningState = state.isMetadata ? READ_METADATA : COPY_UNCOMPRESSED; 460 } else { 461 state.runningState = COMPRESSED_BLOCK_START; 462 } 463 464 if (state.isMetadata) { 465 return; 466 } 467 state.expectedTotalSize += state.metaBlockLength; 468 if (state.ringBufferSize < state.maxRingBufferSize) { 469 maybeReallocateRingBuffer(state); 470 } 471 } 472 473 private static void readMetablockHuffmanCodesAndContextMaps(State state) { 474 final BitReader br = state.br; 475 476 for (int i = 0; i < 3; i++) { 477 state.numBlockTypes[i] = decodeVarLenUnsignedByte(br) + 1; 478 state.blockLength[i] = 1 << 28; 479 if (state.numBlockTypes[i] > 1) { 480 readHuffmanCode(state.numBlockTypes[i] + 2, state.blockTypeTrees, 481 i * Huffman.HUFFMAN_MAX_TABLE_SIZE, br); 482 readHuffmanCode(NUM_BLOCK_LENGTH_CODES, state.blockLenTrees, 483 i * Huffman.HUFFMAN_MAX_TABLE_SIZE, br); 484 state.blockLength[i] = readBlockLength(state.blockLenTrees, 485 i * Huffman.HUFFMAN_MAX_TABLE_SIZE, br); 486 } 487 } 488 489 BitReader.readMoreInput(br); 490 state.distancePostfixBits = BitReader.readBits(br, 2); 491 state.numDirectDistanceCodes = 492 NUM_DISTANCE_SHORT_CODES + (BitReader.readBits(br, 4) << state.distancePostfixBits); 493 state.distancePostfixMask = (1 << state.distancePostfixBits) - 1; 494 int numDistanceCodes = state.numDirectDistanceCodes + (48 << state.distancePostfixBits); 495 // TODO: Reuse? 496 state.contextModes = new byte[state.numBlockTypes[0]]; 497 for (int i = 0; i < state.numBlockTypes[0];) { 498 /* Ensure that less than 256 bits read between readMoreInput. */ 499 int limit = Math.min(i + 96, state.numBlockTypes[0]); 500 for (; i < limit; ++i) { 501 state.contextModes[i] = (byte) (BitReader.readBits(br, 2) << 1); 502 } 503 BitReader.readMoreInput(br); 504 } 505 506 // TODO: Reuse? 507 state.contextMap = new byte[state.numBlockTypes[0] << LITERAL_CONTEXT_BITS]; 508 int numLiteralTrees = decodeContextMap(state.numBlockTypes[0] << LITERAL_CONTEXT_BITS, 509 state.contextMap, br); 510 state.trivialLiteralContext = true; 511 for (int j = 0; j < state.numBlockTypes[0] << LITERAL_CONTEXT_BITS; j++) { 512 if (state.contextMap[j] != j >> LITERAL_CONTEXT_BITS) { 513 state.trivialLiteralContext = false; 514 break; 515 } 516 } 517 518 // TODO: Reuse? 519 state.distContextMap = new byte[state.numBlockTypes[2] << DISTANCE_CONTEXT_BITS]; 520 int numDistTrees = decodeContextMap(state.numBlockTypes[2] << DISTANCE_CONTEXT_BITS, 521 state.distContextMap, br); 522 523 HuffmanTreeGroup.init(state.hGroup0, NUM_LITERAL_CODES, numLiteralTrees); 524 HuffmanTreeGroup.init(state.hGroup1, NUM_INSERT_AND_COPY_CODES, state.numBlockTypes[1]); 525 HuffmanTreeGroup.init(state.hGroup2, numDistanceCodes, numDistTrees); 526 527 HuffmanTreeGroup.decode(state.hGroup0, br); 528 HuffmanTreeGroup.decode(state.hGroup1, br); 529 HuffmanTreeGroup.decode(state.hGroup2, br); 530 531 state.contextMapSlice = 0; 532 state.distContextMapSlice = 0; 533 state.contextLookupOffset1 = Context.LOOKUP_OFFSETS[state.contextModes[0]]; 534 state.contextLookupOffset2 = Context.LOOKUP_OFFSETS[state.contextModes[0] + 1]; 535 state.literalTreeIndex = 0; 536 state.literalTree = state.hGroup0.trees[0]; 537 state.treeCommandOffset = state.hGroup1.trees[0]; // TODO: == 0? 538 539 state.blockTypeRb[0] = state.blockTypeRb[2] = state.blockTypeRb[4] = 1; 540 state.blockTypeRb[1] = state.blockTypeRb[3] = state.blockTypeRb[5] = 0; 541 } 542 543 private static void copyUncompressedData(State state) { 544 final BitReader br = state.br; 545 final byte[] ringBuffer = state.ringBuffer; 546 547 // Could happen if block ends at ring buffer end. 548 if (state.metaBlockLength <= 0) { 549 BitReader.reload(br); 550 state.runningState = BLOCK_START; 551 return; 552 } 553 554 int chunkLength = Math.min(state.ringBufferSize - state.pos, state.metaBlockLength); 555 BitReader.copyBytes(br, ringBuffer, state.pos, chunkLength); 556 state.metaBlockLength -= chunkLength; 557 state.pos += chunkLength; 558 if (state.pos == state.ringBufferSize) { 559 state.nextRunningState = COPY_UNCOMPRESSED; 560 state.bytesToWrite = state.ringBufferSize; 561 state.bytesWritten = 0; 562 state.runningState = WRITE; 563 return; 564 } 565 566 BitReader.reload(br); 567 state.runningState = BLOCK_START; 568 } 569 570 private static boolean writeRingBuffer(State state) { 571 /* Ignore custom dictionary bytes. */ 572 if (state.bytesToIgnore != 0) { 573 state.bytesWritten += state.bytesToIgnore; 574 state.bytesToIgnore = 0; 575 } 576 int toWrite = Math.min(state.outputLength - state.outputUsed, 577 state.bytesToWrite - state.bytesWritten); 578 if (toWrite != 0) { 579 System.arraycopy(state.ringBuffer, state.bytesWritten, state.output, 580 state.outputOffset + state.outputUsed, toWrite); 581 state.outputUsed += toWrite; 582 state.bytesWritten += toWrite; 583 } 584 585 return state.outputUsed < state.outputLength; 586 } 587 588 static void setCustomDictionary(State state, byte[] data) { 589 state.customDictionary = (data == null) ? new byte[0] : data; 590 } 591 592 /** 593 * Actual decompress implementation. 594 */ 595 static void decompress(State state) { 596 if (state.runningState == UNINITIALIZED) { 597 throw new IllegalStateException("Can't decompress until initialized"); 598 } 599 if (state.runningState == CLOSED) { 600 throw new IllegalStateException("Can't decompress after close"); 601 } 602 final BitReader br = state.br; 603 int ringBufferMask = state.ringBufferSize - 1; 604 byte[] ringBuffer = state.ringBuffer; 605 606 while (state.runningState != FINISHED) { 607 // TODO: extract cases to methods for the better readability. 608 switch (state.runningState) { 609 case BLOCK_START: 610 if (state.metaBlockLength < 0) { 611 throw new BrotliRuntimeException("Invalid metablock length"); 612 } 613 readMetablockInfo(state); 614 /* Ring-buffer would be reallocated here. */ 615 ringBufferMask = state.ringBufferSize - 1; 616 ringBuffer = state.ringBuffer; 617 continue; 618 619 case COMPRESSED_BLOCK_START: 620 readMetablockHuffmanCodesAndContextMaps(state); 621 state.runningState = MAIN_LOOP; 622 // Fall through 623 624 case MAIN_LOOP: 625 if (state.metaBlockLength <= 0) { 626 state.runningState = BLOCK_START; 627 continue; 628 } 629 BitReader.readMoreInput(br); 630 if (state.blockLength[1] == 0) { 631 decodeCommandBlockSwitch(state); 632 } 633 state.blockLength[1]--; 634 BitReader.fillBitWindow(br); 635 int cmdCode = readSymbol(state.hGroup1.codes, state.treeCommandOffset, br); 636 int rangeIdx = cmdCode >>> 6; 637 state.distanceCode = 0; 638 if (rangeIdx >= 2) { 639 rangeIdx -= 2; 640 state.distanceCode = -1; 641 } 642 int insertCode = Prefix.INSERT_RANGE_LUT[rangeIdx] + ((cmdCode >>> 3) & 7); 643 int copyCode = Prefix.COPY_RANGE_LUT[rangeIdx] + (cmdCode & 7); 644 state.insertLength = Prefix.INSERT_LENGTH_OFFSET[insertCode] + BitReader 645 .readBits(br, Prefix.INSERT_LENGTH_N_BITS[insertCode]); 646 state.copyLength = Prefix.COPY_LENGTH_OFFSET[copyCode] + BitReader 647 .readBits(br, Prefix.COPY_LENGTH_N_BITS[copyCode]); 648 649 state.j = 0; 650 state.runningState = INSERT_LOOP; 651 652 // Fall through 653 case INSERT_LOOP: 654 if (state.trivialLiteralContext) { 655 while (state.j < state.insertLength) { 656 BitReader.readMoreInput(br); 657 if (state.blockLength[0] == 0) { 658 decodeLiteralBlockSwitch(state); 659 } 660 state.blockLength[0]--; 661 BitReader.fillBitWindow(br); 662 ringBuffer[state.pos] = 663 (byte) readSymbol(state.hGroup0.codes, state.literalTree, br); 664 state.j++; 665 if (state.pos++ == ringBufferMask) { 666 state.nextRunningState = INSERT_LOOP; 667 state.bytesToWrite = state.ringBufferSize; 668 state.bytesWritten = 0; 669 state.runningState = WRITE; 670 break; 671 } 672 } 673 } else { 674 int prevByte1 = ringBuffer[(state.pos - 1) & ringBufferMask] & 0xFF; 675 int prevByte2 = ringBuffer[(state.pos - 2) & ringBufferMask] & 0xFF; 676 while (state.j < state.insertLength) { 677 BitReader.readMoreInput(br); 678 if (state.blockLength[0] == 0) { 679 decodeLiteralBlockSwitch(state); 680 } 681 int literalTreeIndex = state.contextMap[state.contextMapSlice 682 + (Context.LOOKUP[state.contextLookupOffset1 + prevByte1] 683 | Context.LOOKUP[state.contextLookupOffset2 + prevByte2])] & 0xFF; 684 state.blockLength[0]--; 685 prevByte2 = prevByte1; 686 BitReader.fillBitWindow(br); 687 prevByte1 = readSymbol( 688 state.hGroup0.codes, state.hGroup0.trees[literalTreeIndex], br); 689 ringBuffer[state.pos] = (byte) prevByte1; 690 state.j++; 691 if (state.pos++ == ringBufferMask) { 692 state.nextRunningState = INSERT_LOOP; 693 state.bytesToWrite = state.ringBufferSize; 694 state.bytesWritten = 0; 695 state.runningState = WRITE; 696 break; 697 } 698 } 699 } 700 if (state.runningState != INSERT_LOOP) { 701 continue; 702 } 703 state.metaBlockLength -= state.insertLength; 704 if (state.metaBlockLength <= 0) { 705 state.runningState = MAIN_LOOP; 706 continue; 707 } 708 if (state.distanceCode < 0) { 709 BitReader.readMoreInput(br); 710 if (state.blockLength[2] == 0) { 711 decodeDistanceBlockSwitch(state); 712 } 713 state.blockLength[2]--; 714 BitReader.fillBitWindow(br); 715 state.distanceCode = readSymbol(state.hGroup2.codes, state.hGroup2.trees[ 716 state.distContextMap[state.distContextMapSlice 717 + (state.copyLength > 4 ? 3 : state.copyLength - 2)] & 0xFF], br); 718 if (state.distanceCode >= state.numDirectDistanceCodes) { 719 state.distanceCode -= state.numDirectDistanceCodes; 720 int postfix = state.distanceCode & state.distancePostfixMask; 721 state.distanceCode >>>= state.distancePostfixBits; 722 int n = (state.distanceCode >>> 1) + 1; 723 int offset = ((2 + (state.distanceCode & 1)) << n) - 4; 724 state.distanceCode = state.numDirectDistanceCodes + postfix 725 + ((offset + BitReader.readBits(br, n)) << state.distancePostfixBits); 726 } 727 } 728 729 // Convert the distance code to the actual distance by possibly looking up past distances 730 // from the ringBuffer. 731 state.distance = translateShortCodes(state.distanceCode, state.distRb, state.distRbIdx); 732 if (state.distance < 0) { 733 throw new BrotliRuntimeException("Negative distance"); // COV_NF_LINE 734 } 735 736 if (state.maxDistance != state.maxBackwardDistance 737 && state.pos < state.maxBackwardDistance) { 738 state.maxDistance = state.pos; 739 } else { 740 state.maxDistance = state.maxBackwardDistance; 741 } 742 743 state.copyDst = state.pos; 744 if (state.distance > state.maxDistance) { 745 state.runningState = TRANSFORM; 746 continue; 747 } 748 749 if (state.distanceCode > 0) { 750 state.distRb[state.distRbIdx & 3] = state.distance; 751 state.distRbIdx++; 752 } 753 754 if (state.copyLength > state.metaBlockLength) { 755 throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE 756 } 757 state.j = 0; 758 state.runningState = COPY_LOOP; 759 // fall through 760 case COPY_LOOP: 761 for (; state.j < state.copyLength;) { 762 ringBuffer[state.pos] = 763 ringBuffer[(state.pos - state.distance) & ringBufferMask]; 764 // TODO: condense 765 state.metaBlockLength--; 766 state.j++; 767 if (state.pos++ == ringBufferMask) { 768 state.nextRunningState = COPY_LOOP; 769 state.bytesToWrite = state.ringBufferSize; 770 state.bytesWritten = 0; 771 state.runningState = WRITE; 772 break; 773 } 774 } 775 if (state.runningState == COPY_LOOP) { 776 state.runningState = MAIN_LOOP; 777 } 778 continue; 779 780 case TRANSFORM: 781 if (state.copyLength >= Dictionary.MIN_WORD_LENGTH 782 && state.copyLength <= Dictionary.MAX_WORD_LENGTH) { 783 int offset = Dictionary.OFFSETS_BY_LENGTH[state.copyLength]; 784 int wordId = state.distance - state.maxDistance - 1; 785 int shift = Dictionary.SIZE_BITS_BY_LENGTH[state.copyLength]; 786 int mask = (1 << shift) - 1; 787 int wordIdx = wordId & mask; 788 int transformIdx = wordId >>> shift; 789 offset += wordIdx * state.copyLength; 790 if (transformIdx < Transform.TRANSFORMS.length) { 791 int len = Transform.transformDictionaryWord(ringBuffer, state.copyDst, 792 Dictionary.getData(), offset, state.copyLength, 793 Transform.TRANSFORMS[transformIdx]); 794 state.copyDst += len; 795 state.pos += len; 796 state.metaBlockLength -= len; 797 if (state.copyDst >= state.ringBufferSize) { 798 state.nextRunningState = COPY_WRAP_BUFFER; 799 state.bytesToWrite = state.ringBufferSize; 800 state.bytesWritten = 0; 801 state.runningState = WRITE; 802 continue; 803 } 804 } else { 805 throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE 806 } 807 } else { 808 throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE 809 } 810 state.runningState = MAIN_LOOP; 811 continue; 812 813 case COPY_WRAP_BUFFER: 814 System.arraycopy(ringBuffer, state.ringBufferSize, ringBuffer, 0, 815 state.copyDst - state.ringBufferSize); 816 state.runningState = MAIN_LOOP; 817 continue; 818 819 case READ_METADATA: 820 while (state.metaBlockLength > 0) { 821 BitReader.readMoreInput(br); 822 // Optimize 823 BitReader.readBits(br, 8); 824 state.metaBlockLength--; 825 } 826 state.runningState = BLOCK_START; 827 continue; 828 829 830 case COPY_UNCOMPRESSED: 831 copyUncompressedData(state); 832 continue; 833 834 case WRITE: 835 if (!writeRingBuffer(state)) { 836 // Output buffer is full. 837 return; 838 } 839 if (state.pos >= state.maxBackwardDistance) { 840 state.maxDistance = state.maxBackwardDistance; 841 } 842 state.pos &= ringBufferMask; 843 state.runningState = state.nextRunningState; 844 continue; 845 846 default: 847 throw new BrotliRuntimeException("Unexpected state " + state.runningState); 848 } 849 } 850 if (state.runningState == FINISHED) { 851 if (state.metaBlockLength < 0) { 852 throw new BrotliRuntimeException("Invalid metablock length"); 853 } 854 BitReader.jumpToByteBoundary(br); 855 BitReader.checkHealth(state.br, true); 856 } 857 } 858 } 859
