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