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 TRANSFORM = 8; 29 private static final int FINISHED = 9; 30 private static final int CLOSED = 10; 31 private static final int INIT_WRITE = 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 decodeWindowBits(State s)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 */ initState(State s, InputStream input)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 close(State s)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 */ decodeVarLenUnsignedByte(State s)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 decodeMetaBlockLength(State s)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 */ readSymbol(int[] table, int offset, State s)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 readBlockLength(int[] table, int offset, State s)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 translateShortCodes(int code, int[] ringBuffer, int index)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 moveToFront(int[] v, int index)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 inverseMoveToFrontTransform(byte[] v, int vLen)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 readHuffmanCodeLengths( int[] codeLengthCodeLengths, int numSymbols, int[] codeLengths, State s)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 checkDupes(int[] symbols, int length)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. readHuffmanCode(int alphabetSize, int[] table, int offset, State s)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 decodeContextMap(int contextMapSize, byte[] contextMap, State s)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 decodeBlockTypeAndLength(State s, int treeType, int numBlockTypes)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 decodeLiteralBlockSwitch(State s)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 decodeCommandBlockSwitch(State s)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 decodeDistanceBlockSwitch(State s)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 maybeReallocateRingBuffer(State s)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 readNextMetablockHeader(State s)550 private static void readNextMetablockHeader(State s) { 551 if (s.inputEnd != 0) { 552 s.nextRunningState = FINISHED; 553 s.runningState = INIT_WRITE; 554 return; 555 } 556 // TODO: Reset? Do we need this? 557 s.hGroup0 = new int[0]; 558 s.hGroup1 = new int[0]; 559 s.hGroup2 = new int[0]; 560 561 BitReader.readMoreInput(s); 562 decodeMetaBlockLength(s); 563 if ((s.metaBlockLength == 0) && (s.isMetadata == 0)) { 564 return; 565 } 566 if ((s.isUncompressed != 0) || (s.isMetadata != 0)) { 567 BitReader.jumpToByteBoundary(s); 568 s.runningState = (s.isMetadata != 0) ? READ_METADATA : COPY_UNCOMPRESSED; 569 } else { 570 s.runningState = COMPRESSED_BLOCK_START; 571 } 572 573 if (s.isMetadata != 0) { 574 return; 575 } 576 s.expectedTotalSize += s.metaBlockLength; 577 if (s.expectedTotalSize > 1 << 30) { 578 s.expectedTotalSize = 1 << 30; 579 } 580 if (s.ringBufferSize < s.maxRingBufferSize) { 581 maybeReallocateRingBuffer(s); 582 } 583 } 584 readMetablockPartition(State s, int treeType, int numBlockTypes)585 private static int readMetablockPartition(State s, int treeType, int numBlockTypes) { 586 if (numBlockTypes <= 1) { 587 return 1 << 28; 588 } 589 readHuffmanCode(numBlockTypes + 2, s.blockTrees, treeType * HUFFMAN_TABLE_SIZE, s); 590 readHuffmanCode(NUM_BLOCK_LENGTH_CODES, s.blockTrees, (treeType + 3) * HUFFMAN_TABLE_SIZE, s); 591 return readBlockLength(s.blockTrees, (treeType + 3) * HUFFMAN_TABLE_SIZE, s); 592 } 593 readMetablockHuffmanCodesAndContextMaps(State s)594 private static void readMetablockHuffmanCodesAndContextMaps(State s) { 595 s.numLiteralBlockTypes = decodeVarLenUnsignedByte(s) + 1; 596 s.literalBlockLength = readMetablockPartition(s, 0, s.numLiteralBlockTypes); 597 s.numCommandBlockTypes = decodeVarLenUnsignedByte(s) + 1; 598 s.commandBlockLength = readMetablockPartition(s, 1, s.numCommandBlockTypes); 599 s.numDistanceBlockTypes = decodeVarLenUnsignedByte(s) + 1; 600 s.distanceBlockLength = readMetablockPartition(s, 2, s.numDistanceBlockTypes); 601 602 BitReader.readMoreInput(s); 603 BitReader.fillBitWindow(s); 604 s.distancePostfixBits = BitReader.readFewBits(s, 2); 605 s.numDirectDistanceCodes = 606 NUM_DISTANCE_SHORT_CODES + (BitReader.readFewBits(s, 4) << s.distancePostfixBits); 607 s.distancePostfixMask = (1 << s.distancePostfixBits) - 1; 608 int numDistanceCodes = s.numDirectDistanceCodes + (48 << s.distancePostfixBits); 609 // TODO: Reuse? 610 s.contextModes = new byte[s.numLiteralBlockTypes]; 611 for (int i = 0; i < s.numLiteralBlockTypes;) { 612 /* Ensure that less than 256 bits read between readMoreInput. */ 613 int limit = Math.min(i + 96, s.numLiteralBlockTypes); 614 for (; i < limit; ++i) { 615 BitReader.fillBitWindow(s); 616 s.contextModes[i] = (byte) (BitReader.readFewBits(s, 2)); 617 } 618 BitReader.readMoreInput(s); 619 } 620 621 // TODO: Reuse? 622 s.contextMap = new byte[s.numLiteralBlockTypes << LITERAL_CONTEXT_BITS]; 623 int numLiteralTrees = decodeContextMap(s.numLiteralBlockTypes << LITERAL_CONTEXT_BITS, 624 s.contextMap, s); 625 s.trivialLiteralContext = 1; 626 for (int j = 0; j < s.numLiteralBlockTypes << LITERAL_CONTEXT_BITS; j++) { 627 if (s.contextMap[j] != j >> LITERAL_CONTEXT_BITS) { 628 s.trivialLiteralContext = 0; 629 break; 630 } 631 } 632 633 // TODO: Reuse? 634 s.distContextMap = new byte[s.numDistanceBlockTypes << DISTANCE_CONTEXT_BITS]; 635 int numDistTrees = decodeContextMap(s.numDistanceBlockTypes << DISTANCE_CONTEXT_BITS, 636 s.distContextMap, s); 637 638 s.hGroup0 = decodeHuffmanTreeGroup(NUM_LITERAL_CODES, numLiteralTrees, s); 639 s.hGroup1 = 640 decodeHuffmanTreeGroup(NUM_INSERT_AND_COPY_CODES, s.numCommandBlockTypes, s); 641 s.hGroup2 = decodeHuffmanTreeGroup(numDistanceCodes, numDistTrees, s); 642 643 s.contextMapSlice = 0; 644 s.distContextMapSlice = 0; 645 s.contextLookupOffset1 = (int) (s.contextModes[0]) << 9; 646 s.contextLookupOffset2 = s.contextLookupOffset1 + 256; 647 s.literalTreeIndex = 0; 648 s.literalTree = s.hGroup0[0]; 649 s.treeCommandOffset = s.hGroup1[0]; 650 651 s.rings[4] = 1; 652 s.rings[5] = 0; 653 s.rings[6] = 1; 654 s.rings[7] = 0; 655 s.rings[8] = 1; 656 s.rings[9] = 0; 657 } 658 copyUncompressedData(State s)659 private static void copyUncompressedData(State s) { 660 final byte[] ringBuffer = s.ringBuffer; 661 662 // Could happen if block ends at ring buffer end. 663 if (s.metaBlockLength <= 0) { 664 BitReader.reload(s); 665 s.runningState = BLOCK_START; 666 return; 667 } 668 669 int chunkLength = Math.min(s.ringBufferSize - s.pos, s.metaBlockLength); 670 BitReader.copyBytes(s, ringBuffer, s.pos, chunkLength); 671 s.metaBlockLength -= chunkLength; 672 s.pos += chunkLength; 673 if (s.pos == s.ringBufferSize) { 674 s.nextRunningState = COPY_UNCOMPRESSED; 675 s.runningState = INIT_WRITE; 676 return; 677 } 678 679 BitReader.reload(s); 680 s.runningState = BLOCK_START; 681 } 682 writeRingBuffer(State s)683 private static int writeRingBuffer(State s) { 684 int toWrite = Math.min(s.outputLength - s.outputUsed, 685 s.ringBufferBytesReady - s.ringBufferBytesWritten); 686 if (toWrite != 0) { 687 System.arraycopy(s.ringBuffer, s.ringBufferBytesWritten, s.output, 688 s.outputOffset + s.outputUsed, toWrite); 689 s.outputUsed += toWrite; 690 s.ringBufferBytesWritten += toWrite; 691 } 692 693 if (s.outputUsed < s.outputLength) { 694 return 1; 695 } else { 696 return 0; 697 } 698 } 699 decodeHuffmanTreeGroup(int alphabetSize, int n, State s)700 private static int[] decodeHuffmanTreeGroup(int alphabetSize, int n, State s) { 701 int[] group = new int[n + (n * HUFFMAN_TABLE_SIZE)]; 702 int next = n; 703 for (int i = 0; i < n; i++) { 704 group[i] = next; 705 Decode.readHuffmanCode(alphabetSize, group, next, s); 706 next += HUFFMAN_TABLE_SIZE; 707 } 708 return group; 709 } 710 711 // Returns offset in ringBuffer that should trigger WRITE when filled. calculateFence(State s)712 private static int calculateFence(State s) { 713 int result = s.ringBufferSize; 714 if (s.isEager != 0) { 715 result = Math.min(result, s.ringBufferBytesWritten + s.outputLength - s.outputUsed); 716 } 717 return result; 718 } 719 720 /** 721 * Actual decompress implementation. 722 */ decompress(State s)723 static void decompress(State s) { 724 if (s.runningState == UNINITIALIZED) { 725 throw new IllegalStateException("Can't decompress until initialized"); 726 } 727 if (s.runningState == CLOSED) { 728 throw new IllegalStateException("Can't decompress after close"); 729 } 730 int fence = calculateFence(s); 731 int ringBufferMask = s.ringBufferSize - 1; 732 byte[] ringBuffer = s.ringBuffer; 733 734 while (s.runningState != FINISHED) { 735 // TODO: extract cases to methods for the better readability. 736 switch (s.runningState) { 737 case BLOCK_START: 738 if (s.metaBlockLength < 0) { 739 throw new BrotliRuntimeException("Invalid metablock length"); 740 } 741 readNextMetablockHeader(s); 742 /* Ring-buffer would be reallocated here. */ 743 fence = calculateFence(s); 744 ringBufferMask = s.ringBufferSize - 1; 745 ringBuffer = s.ringBuffer; 746 continue; 747 748 case COMPRESSED_BLOCK_START: 749 readMetablockHuffmanCodesAndContextMaps(s); 750 s.runningState = MAIN_LOOP; 751 // Fall through 752 753 case MAIN_LOOP: 754 if (s.metaBlockLength <= 0) { 755 s.runningState = BLOCK_START; 756 continue; 757 } 758 BitReader.readMoreInput(s); 759 if (s.commandBlockLength == 0) { 760 decodeCommandBlockSwitch(s); 761 } 762 s.commandBlockLength--; 763 BitReader.fillBitWindow(s); 764 int cmdCode = readSymbol(s.hGroup1, s.treeCommandOffset, s); 765 int rangeIdx = cmdCode >>> 6; 766 s.distanceCode = 0; 767 if (rangeIdx >= 2) { 768 rangeIdx -= 2; 769 s.distanceCode = -1; 770 } 771 int insertCode = INSERT_RANGE_LUT[rangeIdx] + ((cmdCode >>> 3) & 7); 772 BitReader.fillBitWindow(s); 773 int insertBits = INSERT_LENGTH_N_BITS[insertCode]; 774 int insertExtra = BitReader.readBits(s, insertBits); 775 s.insertLength = INSERT_LENGTH_OFFSET[insertCode] + insertExtra; 776 int copyCode = COPY_RANGE_LUT[rangeIdx] + (cmdCode & 7); 777 BitReader.fillBitWindow(s); 778 int copyBits = COPY_LENGTH_N_BITS[copyCode]; 779 int copyExtra = BitReader.readBits(s, copyBits); 780 s.copyLength = COPY_LENGTH_OFFSET[copyCode] + copyExtra; 781 782 s.j = 0; 783 s.runningState = INSERT_LOOP; 784 785 // Fall through 786 case INSERT_LOOP: 787 if (s.trivialLiteralContext != 0) { 788 while (s.j < s.insertLength) { 789 BitReader.readMoreInput(s); 790 if (s.literalBlockLength == 0) { 791 decodeLiteralBlockSwitch(s); 792 } 793 s.literalBlockLength--; 794 BitReader.fillBitWindow(s); 795 ringBuffer[s.pos] = 796 (byte) readSymbol(s.hGroup0, s.literalTree, s); 797 s.pos++; 798 s.j++; 799 if (s.pos >= fence) { 800 s.nextRunningState = INSERT_LOOP; 801 s.runningState = INIT_WRITE; 802 break; 803 } 804 } 805 } else { 806 int prevByte1 = ringBuffer[(s.pos - 1) & ringBufferMask] & 0xFF; 807 int prevByte2 = ringBuffer[(s.pos - 2) & ringBufferMask] & 0xFF; 808 while (s.j < s.insertLength) { 809 BitReader.readMoreInput(s); 810 if (s.literalBlockLength == 0) { 811 decodeLiteralBlockSwitch(s); 812 } 813 int literalTreeIndex = s.contextMap[s.contextMapSlice 814 + (Context.LOOKUP[s.contextLookupOffset1 + prevByte1] 815 | Context.LOOKUP[s.contextLookupOffset2 + prevByte2])] & 0xFF; 816 s.literalBlockLength--; 817 prevByte2 = prevByte1; 818 BitReader.fillBitWindow(s); 819 prevByte1 = readSymbol( 820 s.hGroup0, s.hGroup0[literalTreeIndex], s); 821 ringBuffer[s.pos] = (byte) prevByte1; 822 s.pos++; 823 s.j++; 824 if (s.pos >= fence) { 825 s.nextRunningState = INSERT_LOOP; 826 s.runningState = INIT_WRITE; 827 break; 828 } 829 } 830 } 831 if (s.runningState != INSERT_LOOP) { 832 continue; 833 } 834 s.metaBlockLength -= s.insertLength; 835 if (s.metaBlockLength <= 0) { 836 s.runningState = MAIN_LOOP; 837 continue; 838 } 839 if (s.distanceCode < 0) { 840 BitReader.readMoreInput(s); 841 if (s.distanceBlockLength == 0) { 842 decodeDistanceBlockSwitch(s); 843 } 844 s.distanceBlockLength--; 845 BitReader.fillBitWindow(s); 846 s.distanceCode = readSymbol(s.hGroup2, s.hGroup2[ 847 s.distContextMap[s.distContextMapSlice 848 + (s.copyLength > 4 ? 3 : s.copyLength - 2)] & 0xFF], s); 849 if (s.distanceCode >= s.numDirectDistanceCodes) { 850 s.distanceCode -= s.numDirectDistanceCodes; 851 int postfix = s.distanceCode & s.distancePostfixMask; 852 s.distanceCode >>>= s.distancePostfixBits; 853 int n = (s.distanceCode >>> 1) + 1; 854 int offset = ((2 + (s.distanceCode & 1)) << n) - 4; 855 BitReader.fillBitWindow(s); 856 int distanceExtra = BitReader.readBits(s, n); 857 s.distanceCode = s.numDirectDistanceCodes + postfix 858 + ((offset + distanceExtra) << s.distancePostfixBits); 859 } 860 } 861 862 // Convert the distance code to the actual distance by possibly looking up past distances 863 // from the ringBuffer. 864 s.distance = translateShortCodes(s.distanceCode, s.rings, s.distRbIdx); 865 if (s.distance < 0) { 866 throw new BrotliRuntimeException("Negative distance"); // COV_NF_LINE 867 } 868 869 if (s.maxDistance != s.maxBackwardDistance 870 && s.pos < s.maxBackwardDistance) { 871 s.maxDistance = s.pos; 872 } else { 873 s.maxDistance = s.maxBackwardDistance; 874 } 875 876 if (s.distance > s.maxDistance) { 877 s.runningState = TRANSFORM; 878 continue; 879 } 880 881 if (s.distanceCode > 0) { 882 s.rings[s.distRbIdx & 3] = s.distance; 883 s.distRbIdx++; 884 } 885 886 if (s.copyLength > s.metaBlockLength) { 887 throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE 888 } 889 s.j = 0; 890 s.runningState = COPY_LOOP; 891 // fall through 892 case COPY_LOOP: 893 int src = (s.pos - s.distance) & ringBufferMask; 894 int dst = s.pos; 895 int copyLength = s.copyLength - s.j; 896 int srcEnd = src + copyLength; 897 int dstEnd = dst + copyLength; 898 if ((srcEnd < ringBufferMask) && (dstEnd < ringBufferMask)) { 899 if (copyLength < 12 || (srcEnd > dst && dstEnd > src)) { 900 for (int k = 0; k < copyLength; ++k) { 901 ringBuffer[dst++] = ringBuffer[src++]; 902 } 903 } else { 904 Utils.copyBytesWithin(ringBuffer, dst, src, srcEnd); 905 } 906 s.j += copyLength; 907 s.metaBlockLength -= copyLength; 908 s.pos += copyLength; 909 } else { 910 for (; s.j < s.copyLength;) { 911 ringBuffer[s.pos] = 912 ringBuffer[(s.pos - s.distance) & ringBufferMask]; 913 s.metaBlockLength--; 914 s.pos++; 915 s.j++; 916 if (s.pos >= fence) { 917 s.nextRunningState = COPY_LOOP; 918 s.runningState = INIT_WRITE; 919 break; 920 } 921 } 922 } 923 if (s.runningState == COPY_LOOP) { 924 s.runningState = MAIN_LOOP; 925 } 926 continue; 927 928 case TRANSFORM: 929 if (s.copyLength >= MIN_WORD_LENGTH 930 && s.copyLength <= MAX_WORD_LENGTH) { 931 int offset = DICTIONARY_OFFSETS_BY_LENGTH[s.copyLength]; 932 int wordId = s.distance - s.maxDistance - 1; 933 int shift = DICTIONARY_SIZE_BITS_BY_LENGTH[s.copyLength]; 934 int mask = (1 << shift) - 1; 935 int wordIdx = wordId & mask; 936 int transformIdx = wordId >>> shift; 937 offset += wordIdx * s.copyLength; 938 if (transformIdx < Transform.NUM_TRANSFORMS) { 939 int len = Transform.transformDictionaryWord(ringBuffer, s.pos, 940 Dictionary.getData(), offset, s.copyLength, transformIdx); 941 s.pos += len; 942 s.metaBlockLength -= len; 943 if (s.pos >= fence) { 944 s.nextRunningState = MAIN_LOOP; 945 s.runningState = INIT_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 READ_METADATA: 958 while (s.metaBlockLength > 0) { 959 BitReader.readMoreInput(s); 960 // Optimize 961 BitReader.fillBitWindow(s); 962 BitReader.readFewBits(s, 8); 963 s.metaBlockLength--; 964 } 965 s.runningState = BLOCK_START; 966 continue; 967 968 969 case COPY_UNCOMPRESSED: 970 copyUncompressedData(s); 971 continue; 972 973 case INIT_WRITE: 974 s.ringBufferBytesReady = Math.min(s.pos, s.ringBufferSize); 975 s.runningState = WRITE; 976 // fall through 977 case WRITE: 978 if (writeRingBuffer(s) == 0) { 979 // Output buffer is full. 980 return; 981 } 982 if (s.pos >= s.maxBackwardDistance) { 983 s.maxDistance = s.maxBackwardDistance; 984 } 985 // Wrap the ringBuffer. 986 if (s.pos >= s.ringBufferSize) { 987 if (s.pos > s.ringBufferSize) { 988 Utils.copyBytesWithin(ringBuffer, 0, s.ringBufferSize, s.pos); 989 } 990 s.pos &= ringBufferMask; 991 s.ringBufferBytesWritten = 0; 992 } 993 s.runningState = s.nextRunningState; 994 continue; 995 996 default: 997 throw new BrotliRuntimeException("Unexpected state " + s.runningState); 998 } 999 } 1000 if (s.runningState == FINISHED) { 1001 if (s.metaBlockLength < 0) { 1002 throw new BrotliRuntimeException("Invalid metablock length"); 1003 } 1004 BitReader.jumpToByteBoundary(s); 1005 BitReader.checkHealth(s, 1); 1006 } 1007 } 1008 } 1009