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