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