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 import java.nio.ByteBuffer; 12 13 /** 14 * API for Brotli decompression. 15 */ 16 final class Decode { 17 18 static final int MIN_LARGE_WINDOW_BITS = 10; 19 /* Maximum was chosen to be 30 to allow efficient decoder implementation. 20 * Format allows bigger window, but Java does not support 2G+ arrays. */ 21 static final int MAX_LARGE_WINDOW_BITS = 30; 22 23 //---------------------------------------------------------------------------- 24 // RunningState 25 //---------------------------------------------------------------------------- 26 private static final int UNINITIALIZED = 0; 27 private static final int INITIALIZED = 1; 28 private static final int BLOCK_START = 2; 29 private static final int COMPRESSED_BLOCK_START = 3; 30 private static final int MAIN_LOOP = 4; 31 private static final int READ_METADATA = 5; 32 private static final int COPY_UNCOMPRESSED = 6; 33 private static final int INSERT_LOOP = 7; 34 private static final int COPY_LOOP = 8; 35 private static final int USE_DICTIONARY = 9; 36 private static final int FINISHED = 10; 37 private static final int CLOSED = 11; 38 private static final int INIT_WRITE = 12; 39 private static final int WRITE = 13; 40 private static final int COPY_FROM_COMPOUND_DICTIONARY = 14; 41 42 private static final int DEFAULT_CODE_LENGTH = 8; 43 private static final int CODE_LENGTH_REPEAT_CODE = 16; 44 private static final int NUM_LITERAL_CODES = 256; 45 private static final int NUM_COMMAND_CODES = 704; 46 private static final int NUM_BLOCK_LENGTH_CODES = 26; 47 private static final int LITERAL_CONTEXT_BITS = 6; 48 private static final int DISTANCE_CONTEXT_BITS = 2; 49 50 private static final int CD_BLOCK_MAP_BITS = 8; 51 private static final int HUFFMAN_TABLE_BITS = 8; 52 private static final int HUFFMAN_TABLE_MASK = 0xFF; 53 54 /** 55 * Maximum possible Huffman table size for an alphabet size of (index * 32), 56 * max code length 15 and root table bits 8. 57 * The biggest alphabet is "command" - 704 symbols. Though "distance" alphabet could theoretically 58 * outreach that limit (for 62 extra bit distances), practically it is limited by 59 * MAX_ALLOWED_DISTANCE and never gets bigger than 544 symbols. 60 */ 61 static final int[] MAX_HUFFMAN_TABLE_SIZE = { 62 256, 402, 436, 468, 500, 534, 566, 598, 630, 662, 694, 726, 758, 790, 822, 63 854, 886, 920, 952, 984, 1016, 1048, 1080 64 }; 65 66 private static final int HUFFMAN_TABLE_SIZE_26 = 396; 67 private static final int HUFFMAN_TABLE_SIZE_258 = 632; 68 69 private static final int CODE_LENGTH_CODES = 18; 70 private static final int[] CODE_LENGTH_CODE_ORDER = { 71 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15, 72 }; 73 74 private static final int NUM_DISTANCE_SHORT_CODES = 16; 75 private static final int[] DISTANCE_SHORT_CODE_INDEX_OFFSET = { 76 0, 3, 2, 1, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3 77 }; 78 79 private static final int[] DISTANCE_SHORT_CODE_VALUE_OFFSET = { 80 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3 81 }; 82 83 /** 84 * Static Huffman code for the code length code lengths. 85 */ 86 private static final int[] FIXED_TABLE = { 87 0x020000, 0x020004, 0x020003, 0x030002, 0x020000, 0x020004, 0x020003, 0x040001, 88 0x020000, 0x020004, 0x020003, 0x030002, 0x020000, 0x020004, 0x020003, 0x040005 89 }; 90 91 // TODO: generalize. 92 static final int MAX_TRANSFORMED_WORD_LENGTH = 5 + 24 + 8; 93 94 private static final int MAX_DISTANCE_BITS = 24; 95 private static final int MAX_LARGE_WINDOW_DISTANCE_BITS = 62; 96 97 /** 98 * Safe distance limit. 99 * 100 * Limit ((1 << 31) - 4) allows safe distance calculation without overflows, 101 * given the distance alphabet size is limited to corresponding size. 102 */ 103 private static final int MAX_ALLOWED_DISTANCE = 0x7FFFFFFC; 104 105 //---------------------------------------------------------------------------- 106 // Prefix code LUT. 107 //---------------------------------------------------------------------------- 108 static final int[] BLOCK_LENGTH_OFFSET = { 109 1, 5, 9, 13, 17, 25, 33, 41, 49, 65, 81, 97, 113, 145, 177, 209, 241, 305, 369, 497, 110 753, 1265, 2289, 4337, 8433, 16625 111 }; 112 113 static final int[] BLOCK_LENGTH_N_BITS = { 114 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 115 }; 116 117 static final short[] INSERT_LENGTH_N_BITS = { 118 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x02, 0x02, 0x03, 0x03, 119 0x04, 0x04, 0x05, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0C, 0x0E, 0x18 120 }; 121 122 static final short[] COPY_LENGTH_N_BITS = { 123 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x02, 0x02, 124 0x03, 0x03, 0x04, 0x04, 0x05, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x18 125 }; 126 127 // Each command is represented with 4x16-bit values: 128 // * [insertLenExtraBits, copyLenExtraBits] 129 // * insertLenOffset 130 // * copyLenOffset 131 // * distanceContext 132 static final short[] CMD_LOOKUP = new short[NUM_COMMAND_CODES * 4]; 133 134 static { 135 unpackCommandLookupTable(CMD_LOOKUP); 136 } 137 log2floor(int i)138 private static int log2floor(int i) { 139 int result = -1; 140 int step = 16; 141 while (step > 0) { 142 if ((i >>> step) != 0) { 143 result += step; 144 i = i >>> step; 145 } 146 step = step >> 1; 147 } 148 return result + i; 149 } 150 calculateDistanceAlphabetSize(int npostfix, int ndirect, int maxndistbits)151 private static int calculateDistanceAlphabetSize(int npostfix, int ndirect, int maxndistbits) { 152 return NUM_DISTANCE_SHORT_CODES + ndirect + 2 * (maxndistbits << npostfix); 153 } 154 155 // TODO: add a correctness test for this function when 156 // large-window and dictionary are implemented. calculateDistanceAlphabetLimit(int maxDistance, int npostfix, int ndirect)157 private static int calculateDistanceAlphabetLimit(int maxDistance, int npostfix, int ndirect) { 158 if (maxDistance < ndirect + (2 << npostfix)) { 159 throw new IllegalArgumentException("maxDistance is too small"); 160 } 161 int offset = ((maxDistance - ndirect) >> npostfix) + 4; 162 int ndistbits = log2floor(offset) - 1; 163 int group = ((ndistbits - 1) << 1) | ((offset >> ndistbits) & 1); 164 return ((group - 1) << npostfix) + (1 << npostfix) + ndirect + NUM_DISTANCE_SHORT_CODES; 165 } 166 unpackCommandLookupTable(short[] cmdLookup)167 private static void unpackCommandLookupTable(short[] cmdLookup) { 168 short[] insertLengthOffsets = new short[24]; 169 short[] copyLengthOffsets = new short[24]; 170 copyLengthOffsets[0] = 2; 171 for (int i = 0; i < 23; ++i) { 172 insertLengthOffsets[i + 1] = 173 (short) (insertLengthOffsets[i] + (1 << INSERT_LENGTH_N_BITS[i])); 174 copyLengthOffsets[i + 1] = 175 (short) (copyLengthOffsets[i] + (1 << COPY_LENGTH_N_BITS[i])); 176 } 177 178 for (int cmdCode = 0; cmdCode < NUM_COMMAND_CODES; ++cmdCode) { 179 int rangeIdx = cmdCode >>> 6; 180 /* -4 turns any regular distance code to negative. */ 181 int distanceContextOffset = -4; 182 if (rangeIdx >= 2) { 183 rangeIdx -= 2; 184 distanceContextOffset = 0; 185 } 186 int insertCode = (((0x29850 >>> (rangeIdx * 2)) & 0x3) << 3) | ((cmdCode >>> 3) & 7); 187 int copyCode = (((0x26244 >>> (rangeIdx * 2)) & 0x3) << 3) | (cmdCode & 7); 188 short copyLengthOffset = copyLengthOffsets[copyCode]; 189 int distanceContext = 190 distanceContextOffset + (copyLengthOffset > 4 ? 3 : copyLengthOffset - 2); 191 int index = cmdCode * 4; 192 cmdLookup[index + 0] = 193 (short) (INSERT_LENGTH_N_BITS[insertCode] | (COPY_LENGTH_N_BITS[copyCode] << 8)); 194 cmdLookup[index + 1] = insertLengthOffsets[insertCode]; 195 cmdLookup[index + 2] = copyLengthOffsets[copyCode]; 196 cmdLookup[index + 3] = (short) distanceContext; 197 } 198 } 199 200 /** 201 * Reads brotli stream header and parses "window bits". 202 * 203 * @param s initialized state, before any read is performed. 204 * @return -1 if header is invalid 205 */ decodeWindowBits(State s)206 private static int decodeWindowBits(State s) { 207 /* Change the meaning of flag. Before that step it means "decoder must be capable of reading 208 * "large-window" brotli stream. After this step it means that "large-window" feature 209 * is actually detected. Despite the window size could be same as before (lgwin = 10..24), 210 * encoded distances are allowed to be much greater, thus bigger dictinary could be used. */ 211 int largeWindowEnabled = s.isLargeWindow; 212 s.isLargeWindow = 0; 213 214 BitReader.fillBitWindow(s); 215 if (BitReader.readFewBits(s, 1) == 0) { 216 return 16; 217 } 218 int n = BitReader.readFewBits(s, 3); 219 if (n != 0) { 220 return 17 + n; 221 } 222 n = BitReader.readFewBits(s, 3); 223 if (n != 0) { 224 if (n == 1) { 225 if (largeWindowEnabled == 0) { 226 /* Reserved value in regular brotli stream. */ 227 return -1; 228 } 229 s.isLargeWindow = 1; 230 /* Check "reserved" bit for future (post-large-window) extensions. */ 231 if (BitReader.readFewBits(s, 1) == 1) { 232 return -1; 233 } 234 n = BitReader.readFewBits(s, 6); 235 if (n < MIN_LARGE_WINDOW_BITS || n > MAX_LARGE_WINDOW_BITS) { 236 /* Encoded window bits value is too small or too big. */ 237 return -1; 238 } 239 return n; 240 } else { 241 return 8 + n; 242 } 243 } 244 return 17; 245 } 246 247 /** 248 * Switch decoder to "eager" mode. 249 * 250 * In "eager" mode decoder returns as soon as there is enough data to fill output buffer. 251 * 252 * @param s initialized state, before any read is performed. 253 */ enableEagerOutput(State s)254 static void enableEagerOutput(State s) { 255 if (s.runningState != INITIALIZED) { 256 throw new IllegalStateException("State MUST be freshly initialized"); 257 } 258 s.isEager = 1; 259 } 260 enableLargeWindow(State s)261 static void enableLargeWindow(State s) { 262 if (s.runningState != INITIALIZED) { 263 throw new IllegalStateException("State MUST be freshly initialized"); 264 } 265 s.isLargeWindow = 1; 266 } 267 268 // TODO: do we need byte views? attachDictionaryChunk(State s, byte[] data)269 static void attachDictionaryChunk(State s, byte[] data) { 270 if (s.runningState != INITIALIZED) { 271 throw new IllegalStateException("State MUST be freshly initialized"); 272 } 273 if (s.cdNumChunks == 0) { 274 s.cdChunks = new byte[16][]; 275 s.cdChunkOffsets = new int[16]; 276 s.cdBlockBits = -1; 277 } 278 if (s.cdNumChunks == 15) { 279 throw new IllegalStateException("Too many dictionary chunks"); 280 } 281 s.cdChunks[s.cdNumChunks] = data; 282 s.cdNumChunks++; 283 s.cdTotalSize += data.length; 284 s.cdChunkOffsets[s.cdNumChunks] = s.cdTotalSize; 285 } 286 287 /** 288 * Associate input with decoder state. 289 * 290 * @param s uninitialized state without associated input 291 * @param input compressed data source 292 */ initState(State s, InputStream input)293 static void initState(State s, InputStream input) { 294 if (s.runningState != UNINITIALIZED) { 295 throw new IllegalStateException("State MUST be uninitialized"); 296 } 297 /* 6 trees + 1 extra "offset" slot to simplify table decoding logic. */ 298 s.blockTrees = new int[7 + 3 * (HUFFMAN_TABLE_SIZE_258 + HUFFMAN_TABLE_SIZE_26)]; 299 s.blockTrees[0] = 7; 300 s.distRbIdx = 3; 301 int maxDistanceAlphabetLimit = calculateDistanceAlphabetLimit(MAX_ALLOWED_DISTANCE, 3, 15 << 3); 302 s.distExtraBits = new byte[maxDistanceAlphabetLimit]; 303 s.distOffset = new int[maxDistanceAlphabetLimit]; 304 s.input = input; 305 BitReader.initBitReader(s); 306 s.runningState = INITIALIZED; 307 } 308 close(State s)309 static void close(State s) throws IOException { 310 if (s.runningState == UNINITIALIZED) { 311 throw new IllegalStateException("State MUST be initialized"); 312 } 313 if (s.runningState == CLOSED) { 314 return; 315 } 316 s.runningState = CLOSED; 317 if (s.input != null) { 318 Utils.closeInput(s.input); 319 s.input = null; 320 } 321 } 322 323 /** 324 * Decodes a number in the range [0..255], by reading 1 - 11 bits. 325 */ decodeVarLenUnsignedByte(State s)326 private static int decodeVarLenUnsignedByte(State s) { 327 BitReader.fillBitWindow(s); 328 if (BitReader.readFewBits(s, 1) != 0) { 329 int n = BitReader.readFewBits(s, 3); 330 if (n == 0) { 331 return 1; 332 } else { 333 return BitReader.readFewBits(s, n) + (1 << n); 334 } 335 } 336 return 0; 337 } 338 decodeMetaBlockLength(State s)339 private static void decodeMetaBlockLength(State s) { 340 BitReader.fillBitWindow(s); 341 s.inputEnd = BitReader.readFewBits(s, 1); 342 s.metaBlockLength = 0; 343 s.isUncompressed = 0; 344 s.isMetadata = 0; 345 if ((s.inputEnd != 0) && BitReader.readFewBits(s, 1) != 0) { 346 return; 347 } 348 int sizeNibbles = BitReader.readFewBits(s, 2) + 4; 349 if (sizeNibbles == 7) { 350 s.isMetadata = 1; 351 if (BitReader.readFewBits(s, 1) != 0) { 352 throw new BrotliRuntimeException("Corrupted reserved bit"); 353 } 354 int sizeBytes = BitReader.readFewBits(s, 2); 355 if (sizeBytes == 0) { 356 return; 357 } 358 for (int i = 0; i < sizeBytes; i++) { 359 BitReader.fillBitWindow(s); 360 int bits = BitReader.readFewBits(s, 8); 361 if (bits == 0 && i + 1 == sizeBytes && sizeBytes > 1) { 362 throw new BrotliRuntimeException("Exuberant nibble"); 363 } 364 s.metaBlockLength |= bits << (i * 8); 365 } 366 } else { 367 for (int i = 0; i < sizeNibbles; i++) { 368 BitReader.fillBitWindow(s); 369 int bits = BitReader.readFewBits(s, 4); 370 if (bits == 0 && i + 1 == sizeNibbles && sizeNibbles > 4) { 371 throw new BrotliRuntimeException("Exuberant nibble"); 372 } 373 s.metaBlockLength |= bits << (i * 4); 374 } 375 } 376 s.metaBlockLength++; 377 if (s.inputEnd == 0) { 378 s.isUncompressed = BitReader.readFewBits(s, 1); 379 } 380 } 381 382 /** 383 * Decodes the next Huffman code from bit-stream. 384 */ readSymbol(int[] tableGroup, int tableIdx, State s)385 private static int readSymbol(int[] tableGroup, int tableIdx, State s) { 386 int offset = tableGroup[tableIdx]; 387 int val = BitReader.peekBits(s); 388 offset += val & HUFFMAN_TABLE_MASK; 389 int bits = tableGroup[offset] >> 16; 390 int sym = tableGroup[offset] & 0xFFFF; 391 if (bits <= HUFFMAN_TABLE_BITS) { 392 s.bitOffset += bits; 393 return sym; 394 } 395 offset += sym; 396 int mask = (1 << bits) - 1; 397 offset += (val & mask) >>> HUFFMAN_TABLE_BITS; 398 s.bitOffset += ((tableGroup[offset] >> 16) + HUFFMAN_TABLE_BITS); 399 return tableGroup[offset] & 0xFFFF; 400 } 401 readBlockLength(int[] tableGroup, int tableIdx, State s)402 private static int readBlockLength(int[] tableGroup, int tableIdx, State s) { 403 BitReader.fillBitWindow(s); 404 int code = readSymbol(tableGroup, tableIdx, s); 405 int n = BLOCK_LENGTH_N_BITS[code]; 406 BitReader.fillBitWindow(s); 407 return BLOCK_LENGTH_OFFSET[code] + BitReader.readBits(s, n); 408 } 409 moveToFront(int[] v, int index)410 private static void moveToFront(int[] v, int index) { 411 int value = v[index]; 412 for (; index > 0; index--) { 413 v[index] = v[index - 1]; 414 } 415 v[0] = value; 416 } 417 inverseMoveToFrontTransform(byte[] v, int vLen)418 private static void inverseMoveToFrontTransform(byte[] v, int vLen) { 419 int[] mtf = new int[256]; 420 for (int i = 0; i < 256; i++) { 421 mtf[i] = i; 422 } 423 for (int i = 0; i < vLen; i++) { 424 int index = v[i] & 0xFF; 425 v[i] = (byte) mtf[index]; 426 if (index != 0) { 427 moveToFront(mtf, index); 428 } 429 } 430 } 431 readHuffmanCodeLengths( int[] codeLengthCodeLengths, int numSymbols, int[] codeLengths, State s)432 private static void readHuffmanCodeLengths( 433 int[] codeLengthCodeLengths, int numSymbols, int[] codeLengths, State s) { 434 int symbol = 0; 435 int prevCodeLen = DEFAULT_CODE_LENGTH; 436 int repeat = 0; 437 int repeatCodeLen = 0; 438 int space = 32768; 439 int[] table = new int[32 + 1]; /* Speculative single entry table group. */ 440 int tableIdx = table.length - 1; 441 Huffman.buildHuffmanTable(table, tableIdx, 5, codeLengthCodeLengths, CODE_LENGTH_CODES); 442 443 while (symbol < numSymbols && space > 0) { 444 BitReader.readMoreInput(s); 445 BitReader.fillBitWindow(s); 446 int p = BitReader.peekBits(s) & 31; 447 s.bitOffset += table[p] >> 16; 448 int codeLen = table[p] & 0xFFFF; 449 if (codeLen < CODE_LENGTH_REPEAT_CODE) { 450 repeat = 0; 451 codeLengths[symbol++] = codeLen; 452 if (codeLen != 0) { 453 prevCodeLen = codeLen; 454 space -= 32768 >> codeLen; 455 } 456 } else { 457 int extraBits = codeLen - 14; 458 int newLen = 0; 459 if (codeLen == CODE_LENGTH_REPEAT_CODE) { 460 newLen = prevCodeLen; 461 } 462 if (repeatCodeLen != newLen) { 463 repeat = 0; 464 repeatCodeLen = newLen; 465 } 466 int oldRepeat = repeat; 467 if (repeat > 0) { 468 repeat -= 2; 469 repeat <<= extraBits; 470 } 471 BitReader.fillBitWindow(s); 472 repeat += BitReader.readFewBits(s, extraBits) + 3; 473 int repeatDelta = repeat - oldRepeat; 474 if (symbol + repeatDelta > numSymbols) { 475 throw new BrotliRuntimeException("symbol + repeatDelta > numSymbols"); // COV_NF_LINE 476 } 477 for (int i = 0; i < repeatDelta; i++) { 478 codeLengths[symbol++] = repeatCodeLen; 479 } 480 if (repeatCodeLen != 0) { 481 space -= repeatDelta << (15 - repeatCodeLen); 482 } 483 } 484 } 485 if (space != 0) { 486 throw new BrotliRuntimeException("Unused space"); // COV_NF_LINE 487 } 488 // TODO: Pass max_symbol to Huffman table builder instead? 489 Utils.fillIntsWithZeroes(codeLengths, symbol, numSymbols); 490 } 491 checkDupes(int[] symbols, int length)492 private static void checkDupes(int[] symbols, int length) { 493 for (int i = 0; i < length - 1; ++i) { 494 for (int j = i + 1; j < length; ++j) { 495 if (symbols[i] == symbols[j]) { 496 throw new BrotliRuntimeException("Duplicate simple Huffman code symbol"); // COV_NF_LINE 497 } 498 } 499 } 500 } 501 502 /** 503 * Reads up to 4 symbols directly and applies predefined histograms. 504 */ readSimpleHuffmanCode(int alphabetSizeMax, int alphabetSizeLimit, int[] tableGroup, int tableIdx, State s)505 private static int readSimpleHuffmanCode(int alphabetSizeMax, int alphabetSizeLimit, 506 int[] tableGroup, int tableIdx, State s) { 507 // TODO: Avoid allocation? 508 int[] codeLengths = new int[alphabetSizeLimit]; 509 int[] symbols = new int[4]; 510 511 int maxBits = 1 + log2floor(alphabetSizeMax - 1); 512 513 int numSymbols = BitReader.readFewBits(s, 2) + 1; 514 for (int i = 0; i < numSymbols; i++) { 515 BitReader.fillBitWindow(s); 516 int symbol = BitReader.readFewBits(s, maxBits); 517 if (symbol >= alphabetSizeLimit) { 518 throw new BrotliRuntimeException("Can't readHuffmanCode"); // COV_NF_LINE 519 } 520 symbols[i] = symbol; 521 } 522 checkDupes(symbols, numSymbols); 523 524 int histogramId = numSymbols; 525 if (numSymbols == 4) { 526 histogramId += BitReader.readFewBits(s, 1); 527 } 528 529 switch (histogramId) { 530 case 1: 531 codeLengths[symbols[0]] = 1; 532 break; 533 534 case 2: 535 codeLengths[symbols[0]] = 1; 536 codeLengths[symbols[1]] = 1; 537 break; 538 539 case 3: 540 codeLengths[symbols[0]] = 1; 541 codeLengths[symbols[1]] = 2; 542 codeLengths[symbols[2]] = 2; 543 break; 544 545 case 4: // uniform 4-symbol histogram 546 codeLengths[symbols[0]] = 2; 547 codeLengths[symbols[1]] = 2; 548 codeLengths[symbols[2]] = 2; 549 codeLengths[symbols[3]] = 2; 550 break; 551 552 case 5: // prioritized 4-symbol histogram 553 codeLengths[symbols[0]] = 1; 554 codeLengths[symbols[1]] = 2; 555 codeLengths[symbols[2]] = 3; 556 codeLengths[symbols[3]] = 3; 557 break; 558 559 default: 560 break; 561 } 562 563 // TODO: Use specialized version? 564 return Huffman.buildHuffmanTable( 565 tableGroup, tableIdx, HUFFMAN_TABLE_BITS, codeLengths, alphabetSizeLimit); 566 } 567 568 // Decode Huffman-coded code lengths. readComplexHuffmanCode(int alphabetSizeLimit, int skip, int[] tableGroup, int tableIdx, State s)569 private static int readComplexHuffmanCode(int alphabetSizeLimit, int skip, 570 int[] tableGroup, int tableIdx, State s) { 571 // TODO: Avoid allocation? 572 int[] codeLengths = new int[alphabetSizeLimit]; 573 int[] codeLengthCodeLengths = new int[CODE_LENGTH_CODES]; 574 int space = 32; 575 int numCodes = 0; 576 for (int i = skip; i < CODE_LENGTH_CODES && space > 0; i++) { 577 int codeLenIdx = CODE_LENGTH_CODE_ORDER[i]; 578 BitReader.fillBitWindow(s); 579 int p = BitReader.peekBits(s) & 15; 580 // TODO: Demultiplex FIXED_TABLE. 581 s.bitOffset += FIXED_TABLE[p] >> 16; 582 int v = FIXED_TABLE[p] & 0xFFFF; 583 codeLengthCodeLengths[codeLenIdx] = v; 584 if (v != 0) { 585 space -= (32 >> v); 586 numCodes++; 587 } 588 } 589 if (space != 0 && numCodes != 1) { 590 throw new BrotliRuntimeException("Corrupted Huffman code histogram"); // COV_NF_LINE 591 } 592 593 readHuffmanCodeLengths(codeLengthCodeLengths, alphabetSizeLimit, codeLengths, s); 594 595 return Huffman.buildHuffmanTable( 596 tableGroup, tableIdx, HUFFMAN_TABLE_BITS, codeLengths, alphabetSizeLimit); 597 } 598 599 /** 600 * Decodes Huffman table from bit-stream. 601 * 602 * @return number of slots used by resulting Huffman table 603 */ readHuffmanCode(int alphabetSizeMax, int alphabetSizeLimit, int[] tableGroup, int tableIdx, State s)604 private static int readHuffmanCode(int alphabetSizeMax, int alphabetSizeLimit, 605 int[] tableGroup, int tableIdx, State s) { 606 BitReader.readMoreInput(s); 607 BitReader.fillBitWindow(s); 608 int simpleCodeOrSkip = BitReader.readFewBits(s, 2); 609 if (simpleCodeOrSkip == 1) { 610 return readSimpleHuffmanCode(alphabetSizeMax, alphabetSizeLimit, tableGroup, tableIdx, s); 611 } else { 612 return readComplexHuffmanCode(alphabetSizeLimit, simpleCodeOrSkip, tableGroup, tableIdx, s); 613 } 614 } 615 decodeContextMap(int contextMapSize, byte[] contextMap, State s)616 private static int decodeContextMap(int contextMapSize, byte[] contextMap, State s) { 617 BitReader.readMoreInput(s); 618 int numTrees = decodeVarLenUnsignedByte(s) + 1; 619 620 if (numTrees == 1) { 621 Utils.fillBytesWithZeroes(contextMap, 0, contextMapSize); 622 return numTrees; 623 } 624 625 BitReader.fillBitWindow(s); 626 int useRleForZeros = BitReader.readFewBits(s, 1); 627 int maxRunLengthPrefix = 0; 628 if (useRleForZeros != 0) { 629 maxRunLengthPrefix = BitReader.readFewBits(s, 4) + 1; 630 } 631 int alphabetSize = numTrees + maxRunLengthPrefix; 632 int tableSize = MAX_HUFFMAN_TABLE_SIZE[(alphabetSize + 31) >> 5]; 633 /* Speculative single entry table group. */ 634 int[] table = new int[tableSize + 1]; 635 int tableIdx = table.length - 1; 636 readHuffmanCode(alphabetSize, alphabetSize, table, tableIdx, s); 637 for (int i = 0; i < contextMapSize; ) { 638 BitReader.readMoreInput(s); 639 BitReader.fillBitWindow(s); 640 int code = readSymbol(table, tableIdx, s); 641 if (code == 0) { 642 contextMap[i] = 0; 643 i++; 644 } else if (code <= maxRunLengthPrefix) { 645 BitReader.fillBitWindow(s); 646 int reps = (1 << code) + BitReader.readFewBits(s, code); 647 while (reps != 0) { 648 if (i >= contextMapSize) { 649 throw new BrotliRuntimeException("Corrupted context map"); // COV_NF_LINE 650 } 651 contextMap[i] = 0; 652 i++; 653 reps--; 654 } 655 } else { 656 contextMap[i] = (byte) (code - maxRunLengthPrefix); 657 i++; 658 } 659 } 660 BitReader.fillBitWindow(s); 661 if (BitReader.readFewBits(s, 1) == 1) { 662 inverseMoveToFrontTransform(contextMap, contextMapSize); 663 } 664 return numTrees; 665 } 666 decodeBlockTypeAndLength(State s, int treeType, int numBlockTypes)667 private static int decodeBlockTypeAndLength(State s, int treeType, int numBlockTypes) { 668 final int[] ringBuffers = s.rings; 669 final int offset = 4 + treeType * 2; 670 BitReader.fillBitWindow(s); 671 int blockType = readSymbol(s.blockTrees, 2 * treeType, s); 672 int result = readBlockLength(s.blockTrees, 2 * treeType + 1, s); 673 674 if (blockType == 1) { 675 blockType = ringBuffers[offset + 1] + 1; 676 } else if (blockType == 0) { 677 blockType = ringBuffers[offset]; 678 } else { 679 blockType -= 2; 680 } 681 if (blockType >= numBlockTypes) { 682 blockType -= numBlockTypes; 683 } 684 ringBuffers[offset] = ringBuffers[offset + 1]; 685 ringBuffers[offset + 1] = blockType; 686 return result; 687 } 688 decodeLiteralBlockSwitch(State s)689 private static void decodeLiteralBlockSwitch(State s) { 690 s.literalBlockLength = decodeBlockTypeAndLength(s, 0, s.numLiteralBlockTypes); 691 int literalBlockType = s.rings[5]; 692 s.contextMapSlice = literalBlockType << LITERAL_CONTEXT_BITS; 693 s.literalTreeIdx = s.contextMap[s.contextMapSlice] & 0xFF; 694 int contextMode = s.contextModes[literalBlockType]; 695 s.contextLookupOffset1 = contextMode << 9; 696 s.contextLookupOffset2 = s.contextLookupOffset1 + 256; 697 } 698 decodeCommandBlockSwitch(State s)699 private static void decodeCommandBlockSwitch(State s) { 700 s.commandBlockLength = decodeBlockTypeAndLength(s, 1, s.numCommandBlockTypes); 701 s.commandTreeIdx = s.rings[7]; 702 } 703 decodeDistanceBlockSwitch(State s)704 private static void decodeDistanceBlockSwitch(State s) { 705 s.distanceBlockLength = decodeBlockTypeAndLength(s, 2, s.numDistanceBlockTypes); 706 s.distContextMapSlice = s.rings[9] << DISTANCE_CONTEXT_BITS; 707 } 708 maybeReallocateRingBuffer(State s)709 private static void maybeReallocateRingBuffer(State s) { 710 int newSize = s.maxRingBufferSize; 711 if (newSize > s.expectedTotalSize) { 712 /* TODO: Handle 2GB+ cases more gracefully. */ 713 int minimalNewSize = s.expectedTotalSize; 714 while ((newSize >> 1) > minimalNewSize) { 715 newSize >>= 1; 716 } 717 if ((s.inputEnd == 0) && newSize < 16384 && s.maxRingBufferSize >= 16384) { 718 newSize = 16384; 719 } 720 } 721 if (newSize <= s.ringBufferSize) { 722 return; 723 } 724 int ringBufferSizeWithSlack = newSize + MAX_TRANSFORMED_WORD_LENGTH; 725 byte[] newBuffer = new byte[ringBufferSizeWithSlack]; 726 if (s.ringBuffer.length != 0) { 727 System.arraycopy(s.ringBuffer, 0, newBuffer, 0, s.ringBufferSize); 728 } 729 s.ringBuffer = newBuffer; 730 s.ringBufferSize = newSize; 731 } 732 readNextMetablockHeader(State s)733 private static void readNextMetablockHeader(State s) { 734 if (s.inputEnd != 0) { 735 s.nextRunningState = FINISHED; 736 s.runningState = INIT_WRITE; 737 return; 738 } 739 // TODO: Reset? Do we need this? 740 s.literalTreeGroup = new int[0]; 741 s.commandTreeGroup = new int[0]; 742 s.distanceTreeGroup = new int[0]; 743 744 BitReader.readMoreInput(s); 745 decodeMetaBlockLength(s); 746 if ((s.metaBlockLength == 0) && (s.isMetadata == 0)) { 747 return; 748 } 749 if ((s.isUncompressed != 0) || (s.isMetadata != 0)) { 750 BitReader.jumpToByteBoundary(s); 751 s.runningState = (s.isMetadata != 0) ? READ_METADATA : COPY_UNCOMPRESSED; 752 } else { 753 s.runningState = COMPRESSED_BLOCK_START; 754 } 755 756 if (s.isMetadata != 0) { 757 return; 758 } 759 s.expectedTotalSize += s.metaBlockLength; 760 if (s.expectedTotalSize > 1 << 30) { 761 s.expectedTotalSize = 1 << 30; 762 } 763 if (s.ringBufferSize < s.maxRingBufferSize) { 764 maybeReallocateRingBuffer(s); 765 } 766 } 767 readMetablockPartition(State s, int treeType, int numBlockTypes)768 private static int readMetablockPartition(State s, int treeType, int numBlockTypes) { 769 int offset = s.blockTrees[2 * treeType]; 770 if (numBlockTypes <= 1) { 771 s.blockTrees[2 * treeType + 1] = offset; 772 s.blockTrees[2 * treeType + 2] = offset; 773 return 1 << 28; 774 } 775 776 int blockTypeAlphabetSize = numBlockTypes + 2; 777 offset += readHuffmanCode( 778 blockTypeAlphabetSize, blockTypeAlphabetSize, s.blockTrees, 2 * treeType, s); 779 s.blockTrees[2 * treeType + 1] = offset; 780 781 int blockLengthAlphabetSize = NUM_BLOCK_LENGTH_CODES; 782 offset += readHuffmanCode( 783 blockLengthAlphabetSize, blockLengthAlphabetSize, s.blockTrees, 2 * treeType + 1, s); 784 s.blockTrees[2 * treeType + 2] = offset; 785 786 return readBlockLength(s.blockTrees, 2 * treeType + 1, s); 787 } 788 calculateDistanceLut(State s, int alphabetSizeLimit)789 private static void calculateDistanceLut(State s, int alphabetSizeLimit) { 790 byte[] distExtraBits = s.distExtraBits; 791 int[] distOffset = s.distOffset; 792 int npostfix = s.distancePostfixBits; 793 int ndirect = s.numDirectDistanceCodes; 794 int postfix = 1 << npostfix; 795 int bits = 1; 796 int half = 0; 797 798 /* Skip short codes. */ 799 int i = NUM_DISTANCE_SHORT_CODES; 800 801 /* Fill direct codes. */ 802 for (int j = 0; j < ndirect; ++j) { 803 distExtraBits[i] = 0; 804 distOffset[i] = j + 1; 805 ++i; 806 } 807 808 /* Fill regular distance codes. */ 809 while (i < alphabetSizeLimit) { 810 int base = ndirect + ((((2 + half) << bits) - 4) << npostfix) + 1; 811 /* Always fill the complete group. */ 812 for (int j = 0; j < postfix; ++j) { 813 distExtraBits[i] = (byte) bits; 814 distOffset[i] = base + j; 815 ++i; 816 } 817 bits = bits + half; 818 half = half ^ 1; 819 } 820 } 821 readMetablockHuffmanCodesAndContextMaps(State s)822 private static void readMetablockHuffmanCodesAndContextMaps(State s) { 823 s.numLiteralBlockTypes = decodeVarLenUnsignedByte(s) + 1; 824 s.literalBlockLength = readMetablockPartition(s, 0, s.numLiteralBlockTypes); 825 s.numCommandBlockTypes = decodeVarLenUnsignedByte(s) + 1; 826 s.commandBlockLength = readMetablockPartition(s, 1, s.numCommandBlockTypes); 827 s.numDistanceBlockTypes = decodeVarLenUnsignedByte(s) + 1; 828 s.distanceBlockLength = readMetablockPartition(s, 2, s.numDistanceBlockTypes); 829 830 BitReader.readMoreInput(s); 831 BitReader.fillBitWindow(s); 832 s.distancePostfixBits = BitReader.readFewBits(s, 2); 833 s.numDirectDistanceCodes = BitReader.readFewBits(s, 4) << s.distancePostfixBits; 834 // TODO: Reuse? 835 s.contextModes = new byte[s.numLiteralBlockTypes]; 836 for (int i = 0; i < s.numLiteralBlockTypes;) { 837 /* Ensure that less than 256 bits read between readMoreInput. */ 838 int limit = Math.min(i + 96, s.numLiteralBlockTypes); 839 for (; i < limit; ++i) { 840 BitReader.fillBitWindow(s); 841 s.contextModes[i] = (byte) BitReader.readFewBits(s, 2); 842 } 843 BitReader.readMoreInput(s); 844 } 845 846 // TODO: Reuse? 847 s.contextMap = new byte[s.numLiteralBlockTypes << LITERAL_CONTEXT_BITS]; 848 int numLiteralTrees = decodeContextMap(s.numLiteralBlockTypes << LITERAL_CONTEXT_BITS, 849 s.contextMap, s); 850 s.trivialLiteralContext = 1; 851 for (int j = 0; j < s.numLiteralBlockTypes << LITERAL_CONTEXT_BITS; j++) { 852 if (s.contextMap[j] != j >> LITERAL_CONTEXT_BITS) { 853 s.trivialLiteralContext = 0; 854 break; 855 } 856 } 857 858 // TODO: Reuse? 859 s.distContextMap = new byte[s.numDistanceBlockTypes << DISTANCE_CONTEXT_BITS]; 860 int numDistTrees = decodeContextMap(s.numDistanceBlockTypes << DISTANCE_CONTEXT_BITS, 861 s.distContextMap, s); 862 863 s.literalTreeGroup = decodeHuffmanTreeGroup(NUM_LITERAL_CODES, NUM_LITERAL_CODES, 864 numLiteralTrees, s); 865 s.commandTreeGroup = decodeHuffmanTreeGroup(NUM_COMMAND_CODES, NUM_COMMAND_CODES, 866 s.numCommandBlockTypes, s); 867 int distanceAlphabetSizeMax = calculateDistanceAlphabetSize( 868 s.distancePostfixBits, s.numDirectDistanceCodes, MAX_DISTANCE_BITS); 869 int distanceAlphabetSizeLimit = distanceAlphabetSizeMax; 870 if (s.isLargeWindow == 1) { 871 distanceAlphabetSizeMax = calculateDistanceAlphabetSize( 872 s.distancePostfixBits, s.numDirectDistanceCodes, MAX_LARGE_WINDOW_DISTANCE_BITS); 873 distanceAlphabetSizeLimit = calculateDistanceAlphabetLimit( 874 MAX_ALLOWED_DISTANCE, s.distancePostfixBits, s.numDirectDistanceCodes); 875 } 876 s.distanceTreeGroup = decodeHuffmanTreeGroup(distanceAlphabetSizeMax, distanceAlphabetSizeLimit, 877 numDistTrees, s); 878 calculateDistanceLut(s, distanceAlphabetSizeLimit); 879 880 s.contextMapSlice = 0; 881 s.distContextMapSlice = 0; 882 s.contextLookupOffset1 = s.contextModes[0] * 512; 883 s.contextLookupOffset2 = s.contextLookupOffset1 + 256; 884 s.literalTreeIdx = 0; 885 s.commandTreeIdx = 0; 886 887 s.rings[4] = 1; 888 s.rings[5] = 0; 889 s.rings[6] = 1; 890 s.rings[7] = 0; 891 s.rings[8] = 1; 892 s.rings[9] = 0; 893 } 894 copyUncompressedData(State s)895 private static void copyUncompressedData(State s) { 896 final byte[] ringBuffer = s.ringBuffer; 897 898 // Could happen if block ends at ring buffer end. 899 if (s.metaBlockLength <= 0) { 900 BitReader.reload(s); 901 s.runningState = BLOCK_START; 902 return; 903 } 904 905 int chunkLength = Math.min(s.ringBufferSize - s.pos, s.metaBlockLength); 906 BitReader.copyBytes(s, ringBuffer, s.pos, chunkLength); 907 s.metaBlockLength -= chunkLength; 908 s.pos += chunkLength; 909 if (s.pos == s.ringBufferSize) { 910 s.nextRunningState = COPY_UNCOMPRESSED; 911 s.runningState = INIT_WRITE; 912 return; 913 } 914 915 BitReader.reload(s); 916 s.runningState = BLOCK_START; 917 } 918 writeRingBuffer(State s)919 private static int writeRingBuffer(State s) { 920 int toWrite = Math.min(s.outputLength - s.outputUsed, 921 s.ringBufferBytesReady - s.ringBufferBytesWritten); 922 if (toWrite != 0) { 923 System.arraycopy(s.ringBuffer, s.ringBufferBytesWritten, s.output, 924 s.outputOffset + s.outputUsed, toWrite); 925 s.outputUsed += toWrite; 926 s.ringBufferBytesWritten += toWrite; 927 } 928 929 if (s.outputUsed < s.outputLength) { 930 return 1; 931 } else { 932 return 0; 933 } 934 } 935 decodeHuffmanTreeGroup(int alphabetSizeMax, int alphabetSizeLimit, int n, State s)936 private static int[] decodeHuffmanTreeGroup(int alphabetSizeMax, int alphabetSizeLimit, 937 int n, State s) { 938 int maxTableSize = MAX_HUFFMAN_TABLE_SIZE[(alphabetSizeLimit + 31) >> 5]; 939 int[] group = new int[n + n * maxTableSize]; 940 int next = n; 941 for (int i = 0; i < n; ++i) { 942 group[i] = next; 943 next += readHuffmanCode(alphabetSizeMax, alphabetSizeLimit, group, i, s); 944 } 945 return group; 946 } 947 948 // Returns offset in ringBuffer that should trigger WRITE when filled. calculateFence(State s)949 private static int calculateFence(State s) { 950 int result = s.ringBufferSize; 951 if (s.isEager != 0) { 952 result = Math.min(result, s.ringBufferBytesWritten + s.outputLength - s.outputUsed); 953 } 954 return result; 955 } 956 doUseDictionary(State s, int fence)957 private static void doUseDictionary(State s, int fence) { 958 if (s.distance > MAX_ALLOWED_DISTANCE) { 959 throw new BrotliRuntimeException("Invalid backward reference"); 960 } 961 int address = s.distance - s.maxDistance - 1 - s.cdTotalSize; 962 if (address < 0) { 963 initializeCompoundDictionaryCopy(s, -address - 1, s.copyLength); 964 s.runningState = COPY_FROM_COMPOUND_DICTIONARY; 965 } else { 966 // Force lazy dictionary initialization. 967 ByteBuffer dictionaryData = Dictionary.getData(); 968 int wordLength = s.copyLength; 969 if (wordLength > Dictionary.MAX_DICTIONARY_WORD_LENGTH) { 970 throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE 971 } 972 int shift = Dictionary.sizeBits[wordLength]; 973 if (shift == 0) { 974 throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE 975 } 976 int offset = Dictionary.offsets[wordLength]; 977 int mask = (1 << shift) - 1; 978 int wordIdx = address & mask; 979 int transformIdx = address >>> shift; 980 offset += wordIdx * wordLength; 981 Transform.Transforms transforms = Transform.RFC_TRANSFORMS; 982 if (transformIdx >= transforms.numTransforms) { 983 throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE 984 } 985 int len = Transform.transformDictionaryWord(s.ringBuffer, s.pos, dictionaryData, 986 offset, wordLength, transforms, transformIdx); 987 s.pos += len; 988 s.metaBlockLength -= len; 989 if (s.pos >= fence) { 990 s.nextRunningState = MAIN_LOOP; 991 s.runningState = INIT_WRITE; 992 return; 993 } 994 s.runningState = MAIN_LOOP; 995 } 996 } 997 initializeCompoundDictionary(State s)998 private static void initializeCompoundDictionary(State s) { 999 s.cdBlockMap = new byte[1 << CD_BLOCK_MAP_BITS]; 1000 int blockBits = CD_BLOCK_MAP_BITS; 1001 // If this function is executed, then s.cdTotalSize > 0. 1002 while (((s.cdTotalSize - 1) >>> blockBits) != 0) { 1003 blockBits++; 1004 } 1005 blockBits -= CD_BLOCK_MAP_BITS; 1006 s.cdBlockBits = blockBits; 1007 int cursor = 0; 1008 int index = 0; 1009 while (cursor < s.cdTotalSize) { 1010 while (s.cdChunkOffsets[index + 1] < cursor) { 1011 index++; 1012 } 1013 s.cdBlockMap[cursor >>> blockBits] = (byte) index; 1014 cursor += 1 << blockBits; 1015 } 1016 } 1017 initializeCompoundDictionaryCopy(State s, int address, int length)1018 private static void initializeCompoundDictionaryCopy(State s, int address, int length) { 1019 if (s.cdBlockBits == -1) { 1020 initializeCompoundDictionary(s); 1021 } 1022 int index = s.cdBlockMap[address >>> s.cdBlockBits]; 1023 while (address >= s.cdChunkOffsets[index + 1]) { 1024 index++; 1025 } 1026 if (s.cdTotalSize > address + length) { 1027 throw new BrotliRuntimeException("Invalid backward reference"); 1028 } 1029 /* Update the recent distances cache */ 1030 s.distRbIdx = (s.distRbIdx + 1) & 0x3; 1031 s.rings[s.distRbIdx] = s.distance; 1032 s.metaBlockLength -= length; 1033 s.cdBrIndex = index; 1034 s.cdBrOffset = address - s.cdChunkOffsets[index]; 1035 s.cdBrLength = length; 1036 s.cdBrCopied = 0; 1037 } 1038 copyFromCompoundDictionary(State s, int fence)1039 private static int copyFromCompoundDictionary(State s, int fence) { 1040 int pos = s.pos; 1041 int origPos = pos; 1042 while (s.cdBrLength != s.cdBrCopied) { 1043 int space = fence - pos; 1044 int chunkLength = s.cdChunkOffsets[s.cdBrIndex + 1] - s.cdChunkOffsets[s.cdBrIndex]; 1045 int remChunkLength = chunkLength - s.cdBrOffset; 1046 int length = s.cdBrLength - s.cdBrCopied; 1047 if (length > remChunkLength) { 1048 length = remChunkLength; 1049 } 1050 if (length > space) { 1051 length = space; 1052 } 1053 Utils.copyBytes( 1054 s.ringBuffer, pos, s.cdChunks[s.cdBrIndex], s.cdBrOffset, s.cdBrOffset + length); 1055 pos += length; 1056 s.cdBrOffset += length; 1057 s.cdBrCopied += length; 1058 if (length == remChunkLength) { 1059 s.cdBrIndex++; 1060 s.cdBrOffset = 0; 1061 } 1062 if (pos >= fence) { 1063 break; 1064 } 1065 } 1066 return pos - origPos; 1067 } 1068 1069 /** 1070 * Actual decompress implementation. 1071 */ decompress(State s)1072 static void decompress(State s) { 1073 if (s.runningState == UNINITIALIZED) { 1074 throw new IllegalStateException("Can't decompress until initialized"); 1075 } 1076 if (s.runningState == CLOSED) { 1077 throw new IllegalStateException("Can't decompress after close"); 1078 } 1079 if (s.runningState == INITIALIZED) { 1080 int windowBits = decodeWindowBits(s); 1081 if (windowBits == -1) { /* Reserved case for future expansion. */ 1082 throw new BrotliRuntimeException("Invalid 'windowBits' code"); 1083 } 1084 s.maxRingBufferSize = 1 << windowBits; 1085 s.maxBackwardDistance = s.maxRingBufferSize - 16; 1086 s.runningState = BLOCK_START; 1087 } 1088 1089 int fence = calculateFence(s); 1090 int ringBufferMask = s.ringBufferSize - 1; 1091 byte[] ringBuffer = s.ringBuffer; 1092 1093 while (s.runningState != FINISHED) { 1094 // TODO: extract cases to methods for the better readability. 1095 switch (s.runningState) { 1096 case BLOCK_START: 1097 if (s.metaBlockLength < 0) { 1098 throw new BrotliRuntimeException("Invalid metablock length"); 1099 } 1100 readNextMetablockHeader(s); 1101 /* Ring-buffer would be reallocated here. */ 1102 fence = calculateFence(s); 1103 ringBufferMask = s.ringBufferSize - 1; 1104 ringBuffer = s.ringBuffer; 1105 continue; 1106 1107 case COMPRESSED_BLOCK_START: 1108 readMetablockHuffmanCodesAndContextMaps(s); 1109 s.runningState = MAIN_LOOP; 1110 // Fall through 1111 1112 case MAIN_LOOP: 1113 if (s.metaBlockLength <= 0) { 1114 s.runningState = BLOCK_START; 1115 continue; 1116 } 1117 BitReader.readMoreInput(s); 1118 if (s.commandBlockLength == 0) { 1119 decodeCommandBlockSwitch(s); 1120 } 1121 s.commandBlockLength--; 1122 BitReader.fillBitWindow(s); 1123 int cmdCode = readSymbol(s.commandTreeGroup, s.commandTreeIdx, s) << 2; 1124 short insertAndCopyExtraBits = CMD_LOOKUP[cmdCode]; 1125 int insertLengthOffset = CMD_LOOKUP[cmdCode + 1]; 1126 int copyLengthOffset = CMD_LOOKUP[cmdCode + 2]; 1127 s.distanceCode = CMD_LOOKUP[cmdCode + 3]; 1128 BitReader.fillBitWindow(s); 1129 { 1130 int extraBits = insertAndCopyExtraBits & 0xFF; 1131 s.insertLength = insertLengthOffset + BitReader.readBits(s, extraBits); 1132 } 1133 BitReader.fillBitWindow(s); 1134 { 1135 int extraBits = insertAndCopyExtraBits >> 8; 1136 s.copyLength = copyLengthOffset + BitReader.readBits(s, extraBits); 1137 } 1138 1139 s.j = 0; 1140 s.runningState = INSERT_LOOP; 1141 1142 // Fall through 1143 case INSERT_LOOP: 1144 if (s.trivialLiteralContext != 0) { 1145 while (s.j < s.insertLength) { 1146 BitReader.readMoreInput(s); 1147 if (s.literalBlockLength == 0) { 1148 decodeLiteralBlockSwitch(s); 1149 } 1150 s.literalBlockLength--; 1151 BitReader.fillBitWindow(s); 1152 ringBuffer[s.pos] = (byte) readSymbol(s.literalTreeGroup, s.literalTreeIdx, s); 1153 s.pos++; 1154 s.j++; 1155 if (s.pos >= fence) { 1156 s.nextRunningState = INSERT_LOOP; 1157 s.runningState = INIT_WRITE; 1158 break; 1159 } 1160 } 1161 } else { 1162 int prevByte1 = ringBuffer[(s.pos - 1) & ringBufferMask] & 0xFF; 1163 int prevByte2 = ringBuffer[(s.pos - 2) & ringBufferMask] & 0xFF; 1164 while (s.j < s.insertLength) { 1165 BitReader.readMoreInput(s); 1166 if (s.literalBlockLength == 0) { 1167 decodeLiteralBlockSwitch(s); 1168 } 1169 int literalContext = Context.LOOKUP[s.contextLookupOffset1 + prevByte1] 1170 | Context.LOOKUP[s.contextLookupOffset2 + prevByte2]; 1171 int literalTreeIdx = s.contextMap[s.contextMapSlice + literalContext] & 0xFF; 1172 s.literalBlockLength--; 1173 prevByte2 = prevByte1; 1174 BitReader.fillBitWindow(s); 1175 prevByte1 = readSymbol(s.literalTreeGroup, literalTreeIdx, s); 1176 ringBuffer[s.pos] = (byte) prevByte1; 1177 s.pos++; 1178 s.j++; 1179 if (s.pos >= fence) { 1180 s.nextRunningState = INSERT_LOOP; 1181 s.runningState = INIT_WRITE; 1182 break; 1183 } 1184 } 1185 } 1186 if (s.runningState != INSERT_LOOP) { 1187 continue; 1188 } 1189 s.metaBlockLength -= s.insertLength; 1190 if (s.metaBlockLength <= 0) { 1191 s.runningState = MAIN_LOOP; 1192 continue; 1193 } 1194 int distanceCode = s.distanceCode; 1195 if (distanceCode < 0) { 1196 // distanceCode in untouched; assigning it 0 won't affect distance ring buffer rolling. 1197 s.distance = s.rings[s.distRbIdx]; 1198 } else { 1199 BitReader.readMoreInput(s); 1200 if (s.distanceBlockLength == 0) { 1201 decodeDistanceBlockSwitch(s); 1202 } 1203 s.distanceBlockLength--; 1204 BitReader.fillBitWindow(s); 1205 int distTreeIdx = s.distContextMap[s.distContextMapSlice + distanceCode] & 0xFF; 1206 distanceCode = readSymbol(s.distanceTreeGroup, distTreeIdx, s); 1207 if (distanceCode < NUM_DISTANCE_SHORT_CODES) { 1208 int index = (s.distRbIdx + DISTANCE_SHORT_CODE_INDEX_OFFSET[distanceCode]) & 0x3; 1209 s.distance = s.rings[index] + DISTANCE_SHORT_CODE_VALUE_OFFSET[distanceCode]; 1210 if (s.distance < 0) { 1211 throw new BrotliRuntimeException("Negative distance"); // COV_NF_LINE 1212 } 1213 } else { 1214 int extraBits = s.distExtraBits[distanceCode]; 1215 int bits; 1216 if (s.bitOffset + extraBits <= BitReader.BITNESS) { 1217 bits = BitReader.readFewBits(s, extraBits); 1218 } else { 1219 BitReader.fillBitWindow(s); 1220 bits = BitReader.readBits(s, extraBits); 1221 } 1222 s.distance = s.distOffset[distanceCode] + (bits << s.distancePostfixBits); 1223 } 1224 } 1225 1226 if (s.maxDistance != s.maxBackwardDistance 1227 && s.pos < s.maxBackwardDistance) { 1228 s.maxDistance = s.pos; 1229 } else { 1230 s.maxDistance = s.maxBackwardDistance; 1231 } 1232 1233 if (s.distance > s.maxDistance) { 1234 s.runningState = USE_DICTIONARY; 1235 continue; 1236 } 1237 1238 if (distanceCode > 0) { 1239 s.distRbIdx = (s.distRbIdx + 1) & 0x3; 1240 s.rings[s.distRbIdx] = s.distance; 1241 } 1242 1243 if (s.copyLength > s.metaBlockLength) { 1244 throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE 1245 } 1246 s.j = 0; 1247 s.runningState = COPY_LOOP; 1248 // fall through 1249 case COPY_LOOP: 1250 int src = (s.pos - s.distance) & ringBufferMask; 1251 int dst = s.pos; 1252 int copyLength = s.copyLength - s.j; 1253 int srcEnd = src + copyLength; 1254 int dstEnd = dst + copyLength; 1255 if ((srcEnd < ringBufferMask) && (dstEnd < ringBufferMask)) { 1256 if (copyLength < 12 || (srcEnd > dst && dstEnd > src)) { 1257 for (int k = 0; k < copyLength; k += 4) { 1258 ringBuffer[dst++] = ringBuffer[src++]; 1259 ringBuffer[dst++] = ringBuffer[src++]; 1260 ringBuffer[dst++] = ringBuffer[src++]; 1261 ringBuffer[dst++] = ringBuffer[src++]; 1262 } 1263 } else { 1264 Utils.copyBytesWithin(ringBuffer, dst, src, srcEnd); 1265 } 1266 s.j += copyLength; 1267 s.metaBlockLength -= copyLength; 1268 s.pos += copyLength; 1269 } else { 1270 for (; s.j < s.copyLength;) { 1271 ringBuffer[s.pos] = 1272 ringBuffer[(s.pos - s.distance) & ringBufferMask]; 1273 s.metaBlockLength--; 1274 s.pos++; 1275 s.j++; 1276 if (s.pos >= fence) { 1277 s.nextRunningState = COPY_LOOP; 1278 s.runningState = INIT_WRITE; 1279 break; 1280 } 1281 } 1282 } 1283 if (s.runningState == COPY_LOOP) { 1284 s.runningState = MAIN_LOOP; 1285 } 1286 continue; 1287 1288 case USE_DICTIONARY: 1289 doUseDictionary(s, fence); 1290 continue; 1291 1292 case COPY_FROM_COMPOUND_DICTIONARY: 1293 s.pos += copyFromCompoundDictionary(s, fence); 1294 if (s.pos >= fence) { 1295 s.nextRunningState = COPY_FROM_COMPOUND_DICTIONARY; 1296 s.runningState = INIT_WRITE; 1297 return; 1298 } 1299 s.runningState = MAIN_LOOP; 1300 continue; 1301 1302 case READ_METADATA: 1303 while (s.metaBlockLength > 0) { 1304 BitReader.readMoreInput(s); 1305 // Optimize 1306 BitReader.fillBitWindow(s); 1307 BitReader.readFewBits(s, 8); 1308 s.metaBlockLength--; 1309 } 1310 s.runningState = BLOCK_START; 1311 continue; 1312 1313 case COPY_UNCOMPRESSED: 1314 copyUncompressedData(s); 1315 continue; 1316 1317 case INIT_WRITE: 1318 s.ringBufferBytesReady = Math.min(s.pos, s.ringBufferSize); 1319 s.runningState = WRITE; 1320 // fall through 1321 case WRITE: 1322 if (writeRingBuffer(s) == 0) { 1323 // Output buffer is full. 1324 return; 1325 } 1326 if (s.pos >= s.maxBackwardDistance) { 1327 s.maxDistance = s.maxBackwardDistance; 1328 } 1329 // Wrap the ringBuffer. 1330 if (s.pos >= s.ringBufferSize) { 1331 if (s.pos > s.ringBufferSize) { 1332 Utils.copyBytesWithin(ringBuffer, 0, s.ringBufferSize, s.pos); 1333 } 1334 s.pos &= ringBufferMask; 1335 s.ringBufferBytesWritten = 0; 1336 } 1337 s.runningState = s.nextRunningState; 1338 continue; 1339 1340 default: 1341 throw new BrotliRuntimeException("Unexpected state " + s.runningState); 1342 } 1343 } 1344 if (s.runningState == FINISHED) { 1345 if (s.metaBlockLength < 0) { 1346 throw new BrotliRuntimeException("Invalid metablock length"); 1347 } 1348 BitReader.jumpToByteBoundary(s); 1349 BitReader.checkHealth(s, 1); 1350 } 1351 } 1352 } 1353