1package brotli 2 3/* Copyright 2013 Google Inc. All Rights Reserved. 4 5 Distributed under MIT license. 6 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT 7*/ 8 9const ( 10 decoderResultError = 0 11 decoderResultSuccess = 1 12 decoderResultNeedsMoreInput = 2 13 decoderResultNeedsMoreOutput = 3 14) 15 16/** 17 * Error code for detailed logging / production debugging. 18 * 19 * See ::BrotliDecoderGetErrorCode and ::BROTLI_LAST_ERROR_CODE. 20 */ 21const ( 22 decoderNoError = 0 23 decoderSuccess = 1 24 decoderNeedsMoreInput = 2 25 decoderNeedsMoreOutput = 3 26 decoderErrorFormatExuberantNibble = -1 27 decoderErrorFormatReserved = -2 28 decoderErrorFormatExuberantMetaNibble = -3 29 decoderErrorFormatSimpleHuffmanAlphabet = -4 30 decoderErrorFormatSimpleHuffmanSame = -5 31 decoderErrorFormatClSpace = -6 32 decoderErrorFormatHuffmanSpace = -7 33 decoderErrorFormatContextMapRepeat = -8 34 decoderErrorFormatBlockLength1 = -9 35 decoderErrorFormatBlockLength2 = -10 36 decoderErrorFormatTransform = -11 37 decoderErrorFormatDictionary = -12 38 decoderErrorFormatWindowBits = -13 39 decoderErrorFormatPadding1 = -14 40 decoderErrorFormatPadding2 = -15 41 decoderErrorFormatDistance = -16 42 decoderErrorDictionaryNotSet = -19 43 decoderErrorInvalidArguments = -20 44 decoderErrorAllocContextModes = -21 45 decoderErrorAllocTreeGroups = -22 46 decoderErrorAllocContextMap = -25 47 decoderErrorAllocRingBuffer1 = -26 48 decoderErrorAllocRingBuffer2 = -27 49 decoderErrorAllocBlockTypeTrees = -30 50 decoderErrorUnreachable = -31 51) 52 53const huffmanTableBits = 8 54 55const huffmanTableMask = 0xFF 56 57/* We need the slack region for the following reasons: 58 - doing up to two 16-byte copies for fast backward copying 59 - inserting transformed dictionary word (5 prefix + 24 base + 8 suffix) */ 60const kRingBufferWriteAheadSlack uint32 = 42 61 62var kCodeLengthCodeOrder = [codeLengthCodes]byte{1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15} 63 64/* Static prefix code for the complex code length code lengths. */ 65var kCodeLengthPrefixLength = [16]byte{2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 4} 66 67var kCodeLengthPrefixValue = [16]byte{0, 4, 3, 2, 0, 4, 3, 1, 0, 4, 3, 2, 0, 4, 3, 5} 68 69/* Saves error code and converts it to BrotliDecoderResult. */ 70func saveErrorCode(s *Reader, e int) int { 71 s.error_code = int(e) 72 switch e { 73 case decoderSuccess: 74 return decoderResultSuccess 75 76 case decoderNeedsMoreInput: 77 return decoderResultNeedsMoreInput 78 79 case decoderNeedsMoreOutput: 80 return decoderResultNeedsMoreOutput 81 82 default: 83 return decoderResultError 84 } 85} 86 87/* Decodes WBITS by reading 1 - 7 bits, or 0x11 for "Large Window Brotli". 88 Precondition: bit-reader accumulator has at least 8 bits. */ 89func decodeWindowBits(s *Reader, br *bitReader) int { 90 var n uint32 91 var large_window bool = s.large_window 92 s.large_window = false 93 takeBits(br, 1, &n) 94 if n == 0 { 95 s.window_bits = 16 96 return decoderSuccess 97 } 98 99 takeBits(br, 3, &n) 100 if n != 0 { 101 s.window_bits = 17 + n 102 return decoderSuccess 103 } 104 105 takeBits(br, 3, &n) 106 if n == 1 { 107 if large_window { 108 takeBits(br, 1, &n) 109 if n == 1 { 110 return decoderErrorFormatWindowBits 111 } 112 113 s.large_window = true 114 return decoderSuccess 115 } else { 116 return decoderErrorFormatWindowBits 117 } 118 } 119 120 if n != 0 { 121 s.window_bits = 8 + n 122 return decoderSuccess 123 } 124 125 s.window_bits = 17 126 return decoderSuccess 127} 128 129/* Decodes a number in the range [0..255], by reading 1 - 11 bits. */ 130func decodeVarLenUint8(s *Reader, br *bitReader, value *uint32) int { 131 var bits uint32 132 switch s.substate_decode_uint8 { 133 case stateDecodeUint8None: 134 if !safeReadBits(br, 1, &bits) { 135 return decoderNeedsMoreInput 136 } 137 138 if bits == 0 { 139 *value = 0 140 return decoderSuccess 141 } 142 fallthrough 143 144 /* Fall through. */ 145 case stateDecodeUint8Short: 146 if !safeReadBits(br, 3, &bits) { 147 s.substate_decode_uint8 = stateDecodeUint8Short 148 return decoderNeedsMoreInput 149 } 150 151 if bits == 0 { 152 *value = 1 153 s.substate_decode_uint8 = stateDecodeUint8None 154 return decoderSuccess 155 } 156 157 /* Use output value as a temporary storage. It MUST be persisted. */ 158 *value = bits 159 fallthrough 160 161 /* Fall through. */ 162 case stateDecodeUint8Long: 163 if !safeReadBits(br, *value, &bits) { 164 s.substate_decode_uint8 = stateDecodeUint8Long 165 return decoderNeedsMoreInput 166 } 167 168 *value = (1 << *value) + bits 169 s.substate_decode_uint8 = stateDecodeUint8None 170 return decoderSuccess 171 172 default: 173 return decoderErrorUnreachable 174 } 175} 176 177/* Decodes a metablock length and flags by reading 2 - 31 bits. */ 178func decodeMetaBlockLength(s *Reader, br *bitReader) int { 179 var bits uint32 180 var i int 181 for { 182 switch s.substate_metablock_header { 183 case stateMetablockHeaderNone: 184 if !safeReadBits(br, 1, &bits) { 185 return decoderNeedsMoreInput 186 } 187 188 if bits != 0 { 189 s.is_last_metablock = 1 190 } else { 191 s.is_last_metablock = 0 192 } 193 s.meta_block_remaining_len = 0 194 s.is_uncompressed = 0 195 s.is_metadata = 0 196 if s.is_last_metablock == 0 { 197 s.substate_metablock_header = stateMetablockHeaderNibbles 198 break 199 } 200 201 s.substate_metablock_header = stateMetablockHeaderEmpty 202 fallthrough 203 204 /* Fall through. */ 205 case stateMetablockHeaderEmpty: 206 if !safeReadBits(br, 1, &bits) { 207 return decoderNeedsMoreInput 208 } 209 210 if bits != 0 { 211 s.substate_metablock_header = stateMetablockHeaderNone 212 return decoderSuccess 213 } 214 215 s.substate_metablock_header = stateMetablockHeaderNibbles 216 fallthrough 217 218 /* Fall through. */ 219 case stateMetablockHeaderNibbles: 220 if !safeReadBits(br, 2, &bits) { 221 return decoderNeedsMoreInput 222 } 223 224 s.size_nibbles = uint(byte(bits + 4)) 225 s.loop_counter = 0 226 if bits == 3 { 227 s.is_metadata = 1 228 s.substate_metablock_header = stateMetablockHeaderReserved 229 break 230 } 231 232 s.substate_metablock_header = stateMetablockHeaderSize 233 fallthrough 234 235 /* Fall through. */ 236 case stateMetablockHeaderSize: 237 i = s.loop_counter 238 239 for ; i < int(s.size_nibbles); i++ { 240 if !safeReadBits(br, 4, &bits) { 241 s.loop_counter = i 242 return decoderNeedsMoreInput 243 } 244 245 if uint(i+1) == s.size_nibbles && s.size_nibbles > 4 && bits == 0 { 246 return decoderErrorFormatExuberantNibble 247 } 248 249 s.meta_block_remaining_len |= int(bits << uint(i*4)) 250 } 251 252 s.substate_metablock_header = stateMetablockHeaderUncompressed 253 fallthrough 254 255 /* Fall through. */ 256 case stateMetablockHeaderUncompressed: 257 if s.is_last_metablock == 0 { 258 if !safeReadBits(br, 1, &bits) { 259 return decoderNeedsMoreInput 260 } 261 262 if bits != 0 { 263 s.is_uncompressed = 1 264 } else { 265 s.is_uncompressed = 0 266 } 267 } 268 269 s.meta_block_remaining_len++ 270 s.substate_metablock_header = stateMetablockHeaderNone 271 return decoderSuccess 272 273 case stateMetablockHeaderReserved: 274 if !safeReadBits(br, 1, &bits) { 275 return decoderNeedsMoreInput 276 } 277 278 if bits != 0 { 279 return decoderErrorFormatReserved 280 } 281 282 s.substate_metablock_header = stateMetablockHeaderBytes 283 fallthrough 284 285 /* Fall through. */ 286 case stateMetablockHeaderBytes: 287 if !safeReadBits(br, 2, &bits) { 288 return decoderNeedsMoreInput 289 } 290 291 if bits == 0 { 292 s.substate_metablock_header = stateMetablockHeaderNone 293 return decoderSuccess 294 } 295 296 s.size_nibbles = uint(byte(bits)) 297 s.substate_metablock_header = stateMetablockHeaderMetadata 298 fallthrough 299 300 /* Fall through. */ 301 case stateMetablockHeaderMetadata: 302 i = s.loop_counter 303 304 for ; i < int(s.size_nibbles); i++ { 305 if !safeReadBits(br, 8, &bits) { 306 s.loop_counter = i 307 return decoderNeedsMoreInput 308 } 309 310 if uint(i+1) == s.size_nibbles && s.size_nibbles > 1 && bits == 0 { 311 return decoderErrorFormatExuberantMetaNibble 312 } 313 314 s.meta_block_remaining_len |= int(bits << uint(i*8)) 315 } 316 317 s.meta_block_remaining_len++ 318 s.substate_metablock_header = stateMetablockHeaderNone 319 return decoderSuccess 320 321 default: 322 return decoderErrorUnreachable 323 } 324 } 325} 326 327/* Decodes the Huffman code. 328 This method doesn't read data from the bit reader, BUT drops the amount of 329 bits that correspond to the decoded symbol. 330 bits MUST contain at least 15 (BROTLI_HUFFMAN_MAX_CODE_LENGTH) valid bits. */ 331func decodeSymbol(bits uint32, table []huffmanCode, br *bitReader) uint32 { 332 table = table[bits&huffmanTableMask:] 333 if table[0].bits > huffmanTableBits { 334 var nbits uint32 = uint32(table[0].bits) - huffmanTableBits 335 dropBits(br, huffmanTableBits) 336 table = table[uint32(table[0].value)+((bits>>huffmanTableBits)&bitMask(nbits)):] 337 } 338 339 dropBits(br, uint32(table[0].bits)) 340 return uint32(table[0].value) 341} 342 343/* Reads and decodes the next Huffman code from bit-stream. 344 This method peeks 16 bits of input and drops 0 - 15 of them. */ 345func readSymbol(table []huffmanCode, br *bitReader) uint32 { 346 return decodeSymbol(get16BitsUnmasked(br), table, br) 347} 348 349/* Same as DecodeSymbol, but it is known that there is less than 15 bits of 350 input are currently available. */ 351func safeDecodeSymbol(table []huffmanCode, br *bitReader, result *uint32) bool { 352 var val uint32 353 var available_bits uint32 = getAvailableBits(br) 354 if available_bits == 0 { 355 if table[0].bits == 0 { 356 *result = uint32(table[0].value) 357 return true 358 } 359 360 return false /* No valid bits at all. */ 361 } 362 363 val = uint32(getBitsUnmasked(br)) 364 table = table[val&huffmanTableMask:] 365 if table[0].bits <= huffmanTableBits { 366 if uint32(table[0].bits) <= available_bits { 367 dropBits(br, uint32(table[0].bits)) 368 *result = uint32(table[0].value) 369 return true 370 } else { 371 return false /* Not enough bits for the first level. */ 372 } 373 } 374 375 if available_bits <= huffmanTableBits { 376 return false /* Not enough bits to move to the second level. */ 377 } 378 379 /* Speculatively drop HUFFMAN_TABLE_BITS. */ 380 val = (val & bitMask(uint32(table[0].bits))) >> huffmanTableBits 381 382 available_bits -= huffmanTableBits 383 table = table[uint32(table[0].value)+val:] 384 if available_bits < uint32(table[0].bits) { 385 return false /* Not enough bits for the second level. */ 386 } 387 388 dropBits(br, huffmanTableBits+uint32(table[0].bits)) 389 *result = uint32(table[0].value) 390 return true 391} 392 393func safeReadSymbol(table []huffmanCode, br *bitReader, result *uint32) bool { 394 var val uint32 395 if safeGetBits(br, 15, &val) { 396 *result = decodeSymbol(val, table, br) 397 return true 398 } 399 400 return safeDecodeSymbol(table, br, result) 401} 402 403/* Makes a look-up in first level Huffman table. Peeks 8 bits. */ 404func preloadSymbol(safe int, table []huffmanCode, br *bitReader, bits *uint32, value *uint32) { 405 if safe != 0 { 406 return 407 } 408 409 table = table[getBits(br, huffmanTableBits):] 410 *bits = uint32(table[0].bits) 411 *value = uint32(table[0].value) 412} 413 414/* Decodes the next Huffman code using data prepared by PreloadSymbol. 415 Reads 0 - 15 bits. Also peeks 8 following bits. */ 416func readPreloadedSymbol(table []huffmanCode, br *bitReader, bits *uint32, value *uint32) uint32 { 417 var result uint32 = *value 418 var ext []huffmanCode 419 if *bits > huffmanTableBits { 420 var val uint32 = get16BitsUnmasked(br) 421 ext = table[val&huffmanTableMask:][*value:] 422 var mask uint32 = bitMask((*bits - huffmanTableBits)) 423 dropBits(br, huffmanTableBits) 424 ext = ext[(val>>huffmanTableBits)&mask:] 425 dropBits(br, uint32(ext[0].bits)) 426 result = uint32(ext[0].value) 427 } else { 428 dropBits(br, *bits) 429 } 430 431 preloadSymbol(0, table, br, bits, value) 432 return result 433} 434 435func log2Floor(x uint32) uint32 { 436 var result uint32 = 0 437 for x != 0 { 438 x >>= 1 439 result++ 440 } 441 442 return result 443} 444 445/* Reads (s->symbol + 1) symbols. 446 Totally 1..4 symbols are read, 1..11 bits each. 447 The list of symbols MUST NOT contain duplicates. */ 448func readSimpleHuffmanSymbols(alphabet_size uint32, max_symbol uint32, s *Reader) int { 449 var br *bitReader = &s.br 450 var max_bits uint32 = log2Floor(alphabet_size - 1) 451 var i uint32 = s.sub_loop_counter 452 /* max_bits == 1..11; symbol == 0..3; 1..44 bits will be read. */ 453 454 var num_symbols uint32 = s.symbol 455 for i <= num_symbols { 456 var v uint32 457 if !safeReadBits(br, max_bits, &v) { 458 s.sub_loop_counter = i 459 s.substate_huffman = stateHuffmanSimpleRead 460 return decoderNeedsMoreInput 461 } 462 463 if v >= max_symbol { 464 return decoderErrorFormatSimpleHuffmanAlphabet 465 } 466 467 s.symbols_lists_array[i] = uint16(v) 468 i++ 469 } 470 471 for i = 0; i < num_symbols; i++ { 472 var k uint32 = i + 1 473 for ; k <= num_symbols; k++ { 474 if s.symbols_lists_array[i] == s.symbols_lists_array[k] { 475 return decoderErrorFormatSimpleHuffmanSame 476 } 477 } 478 } 479 480 return decoderSuccess 481} 482 483/* Process single decoded symbol code length: 484 A) reset the repeat variable 485 B) remember code length (if it is not 0) 486 C) extend corresponding index-chain 487 D) reduce the Huffman space 488 E) update the histogram */ 489func processSingleCodeLength(code_len uint32, symbol *uint32, repeat *uint32, space *uint32, prev_code_len *uint32, symbol_lists symbolList, code_length_histo []uint16, next_symbol []int) { 490 *repeat = 0 491 if code_len != 0 { /* code_len == 1..15 */ 492 symbolListPut(symbol_lists, next_symbol[code_len], uint16(*symbol)) 493 next_symbol[code_len] = int(*symbol) 494 *prev_code_len = code_len 495 *space -= 32768 >> code_len 496 code_length_histo[code_len]++ 497 } 498 499 (*symbol)++ 500} 501 502/* Process repeated symbol code length. 503 A) Check if it is the extension of previous repeat sequence; if the decoded 504 value is not BROTLI_REPEAT_PREVIOUS_CODE_LENGTH, then it is a new 505 symbol-skip 506 B) Update repeat variable 507 C) Check if operation is feasible (fits alphabet) 508 D) For each symbol do the same operations as in ProcessSingleCodeLength 509 510 PRECONDITION: code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH or 511 code_len == BROTLI_REPEAT_ZERO_CODE_LENGTH */ 512func processRepeatedCodeLength(code_len uint32, repeat_delta uint32, alphabet_size uint32, symbol *uint32, repeat *uint32, space *uint32, prev_code_len *uint32, repeat_code_len *uint32, symbol_lists symbolList, code_length_histo []uint16, next_symbol []int) { 513 var old_repeat uint32 /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */ /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */ 514 var extra_bits uint32 = 3 515 var new_len uint32 = 0 516 if code_len == repeatPreviousCodeLength { 517 new_len = *prev_code_len 518 extra_bits = 2 519 } 520 521 if *repeat_code_len != new_len { 522 *repeat = 0 523 *repeat_code_len = new_len 524 } 525 526 old_repeat = *repeat 527 if *repeat > 0 { 528 *repeat -= 2 529 *repeat <<= extra_bits 530 } 531 532 *repeat += repeat_delta + 3 533 repeat_delta = *repeat - old_repeat 534 if *symbol+repeat_delta > alphabet_size { 535 *symbol = alphabet_size 536 *space = 0xFFFFF 537 return 538 } 539 540 if *repeat_code_len != 0 { 541 var last uint = uint(*symbol + repeat_delta) 542 var next int = next_symbol[*repeat_code_len] 543 for { 544 symbolListPut(symbol_lists, next, uint16(*symbol)) 545 next = int(*symbol) 546 (*symbol)++ 547 if (*symbol) == uint32(last) { 548 break 549 } 550 } 551 552 next_symbol[*repeat_code_len] = next 553 *space -= repeat_delta << (15 - *repeat_code_len) 554 code_length_histo[*repeat_code_len] = uint16(uint32(code_length_histo[*repeat_code_len]) + repeat_delta) 555 } else { 556 *symbol += repeat_delta 557 } 558} 559 560/* Reads and decodes symbol codelengths. */ 561func readSymbolCodeLengths(alphabet_size uint32, s *Reader) int { 562 var br *bitReader = &s.br 563 var symbol uint32 = s.symbol 564 var repeat uint32 = s.repeat 565 var space uint32 = s.space 566 var prev_code_len uint32 = s.prev_code_len 567 var repeat_code_len uint32 = s.repeat_code_len 568 var symbol_lists symbolList = s.symbol_lists 569 var code_length_histo []uint16 = s.code_length_histo[:] 570 var next_symbol []int = s.next_symbol[:] 571 if !warmupBitReader(br) { 572 return decoderNeedsMoreInput 573 } 574 var p []huffmanCode 575 for symbol < alphabet_size && space > 0 { 576 p = s.table[:] 577 var code_len uint32 578 if !checkInputAmount(br, shortFillBitWindowRead) { 579 s.symbol = symbol 580 s.repeat = repeat 581 s.prev_code_len = prev_code_len 582 s.repeat_code_len = repeat_code_len 583 s.space = space 584 return decoderNeedsMoreInput 585 } 586 587 fillBitWindow16(br) 588 p = p[getBitsUnmasked(br)&uint64(bitMask(huffmanMaxCodeLengthCodeLength)):] 589 dropBits(br, uint32(p[0].bits)) /* Use 1..5 bits. */ 590 code_len = uint32(p[0].value) /* code_len == 0..17 */ 591 if code_len < repeatPreviousCodeLength { 592 processSingleCodeLength(code_len, &symbol, &repeat, &space, &prev_code_len, symbol_lists, code_length_histo, next_symbol) /* code_len == 16..17, extra_bits == 2..3 */ 593 } else { 594 var extra_bits uint32 595 if code_len == repeatPreviousCodeLength { 596 extra_bits = 2 597 } else { 598 extra_bits = 3 599 } 600 var repeat_delta uint32 = uint32(getBitsUnmasked(br)) & bitMask(extra_bits) 601 dropBits(br, extra_bits) 602 processRepeatedCodeLength(code_len, repeat_delta, alphabet_size, &symbol, &repeat, &space, &prev_code_len, &repeat_code_len, symbol_lists, code_length_histo, next_symbol) 603 } 604 } 605 606 s.space = space 607 return decoderSuccess 608} 609 610func safeReadSymbolCodeLengths(alphabet_size uint32, s *Reader) int { 611 var br *bitReader = &s.br 612 var get_byte bool = false 613 var p []huffmanCode 614 for s.symbol < alphabet_size && s.space > 0 { 615 p = s.table[:] 616 var code_len uint32 617 var available_bits uint32 618 var bits uint32 = 0 619 if get_byte && !pullByte(br) { 620 return decoderNeedsMoreInput 621 } 622 get_byte = false 623 available_bits = getAvailableBits(br) 624 if available_bits != 0 { 625 bits = uint32(getBitsUnmasked(br)) 626 } 627 628 p = p[bits&bitMask(huffmanMaxCodeLengthCodeLength):] 629 if uint32(p[0].bits) > available_bits { 630 get_byte = true 631 continue 632 } 633 634 code_len = uint32(p[0].value) /* code_len == 0..17 */ 635 if code_len < repeatPreviousCodeLength { 636 dropBits(br, uint32(p[0].bits)) 637 processSingleCodeLength(code_len, &s.symbol, &s.repeat, &s.space, &s.prev_code_len, s.symbol_lists, s.code_length_histo[:], s.next_symbol[:]) /* code_len == 16..17, extra_bits == 2..3 */ 638 } else { 639 var extra_bits uint32 = code_len - 14 640 var repeat_delta uint32 = (bits >> p[0].bits) & bitMask(extra_bits) 641 if available_bits < uint32(p[0].bits)+extra_bits { 642 get_byte = true 643 continue 644 } 645 646 dropBits(br, uint32(p[0].bits)+extra_bits) 647 processRepeatedCodeLength(code_len, repeat_delta, alphabet_size, &s.symbol, &s.repeat, &s.space, &s.prev_code_len, &s.repeat_code_len, s.symbol_lists, s.code_length_histo[:], s.next_symbol[:]) 648 } 649 } 650 651 return decoderSuccess 652} 653 654/* Reads and decodes 15..18 codes using static prefix code. 655 Each code is 2..4 bits long. In total 30..72 bits are used. */ 656func readCodeLengthCodeLengths(s *Reader) int { 657 var br *bitReader = &s.br 658 var num_codes uint32 = s.repeat 659 var space uint32 = s.space 660 var i uint32 = s.sub_loop_counter 661 for ; i < codeLengthCodes; i++ { 662 var code_len_idx byte = kCodeLengthCodeOrder[i] 663 var ix uint32 664 var v uint32 665 if !safeGetBits(br, 4, &ix) { 666 var available_bits uint32 = getAvailableBits(br) 667 if available_bits != 0 { 668 ix = uint32(getBitsUnmasked(br) & 0xF) 669 } else { 670 ix = 0 671 } 672 673 if uint32(kCodeLengthPrefixLength[ix]) > available_bits { 674 s.sub_loop_counter = i 675 s.repeat = num_codes 676 s.space = space 677 s.substate_huffman = stateHuffmanComplex 678 return decoderNeedsMoreInput 679 } 680 } 681 682 v = uint32(kCodeLengthPrefixValue[ix]) 683 dropBits(br, uint32(kCodeLengthPrefixLength[ix])) 684 s.code_length_code_lengths[code_len_idx] = byte(v) 685 if v != 0 { 686 space = space - (32 >> v) 687 num_codes++ 688 s.code_length_histo[v]++ 689 if space-1 >= 32 { 690 /* space is 0 or wrapped around. */ 691 break 692 } 693 } 694 } 695 696 if num_codes != 1 && space != 0 { 697 return decoderErrorFormatClSpace 698 } 699 700 return decoderSuccess 701} 702 703/* Decodes the Huffman tables. 704 There are 2 scenarios: 705 A) Huffman code contains only few symbols (1..4). Those symbols are read 706 directly; their code lengths are defined by the number of symbols. 707 For this scenario 4 - 49 bits will be read. 708 709 B) 2-phase decoding: 710 B.1) Small Huffman table is decoded; it is specified with code lengths 711 encoded with predefined entropy code. 32 - 74 bits are used. 712 B.2) Decoded table is used to decode code lengths of symbols in resulting 713 Huffman table. In worst case 3520 bits are read. */ 714func readHuffmanCode(alphabet_size uint32, max_symbol uint32, table []huffmanCode, opt_table_size *uint32, s *Reader) int { 715 var br *bitReader = &s.br 716 717 /* Unnecessary masking, but might be good for safety. */ 718 alphabet_size &= 0x7FF 719 720 /* State machine. */ 721 for { 722 switch s.substate_huffman { 723 case stateHuffmanNone: 724 if !safeReadBits(br, 2, &s.sub_loop_counter) { 725 return decoderNeedsMoreInput 726 } 727 728 /* The value is used as follows: 729 1 for simple code; 730 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */ 731 if s.sub_loop_counter != 1 { 732 s.space = 32 733 s.repeat = 0 /* num_codes */ 734 var i int 735 for i = 0; i <= huffmanMaxCodeLengthCodeLength; i++ { 736 s.code_length_histo[i] = 0 737 } 738 739 for i = 0; i < codeLengthCodes; i++ { 740 s.code_length_code_lengths[i] = 0 741 } 742 743 s.substate_huffman = stateHuffmanComplex 744 continue 745 } 746 fallthrough 747 748 /* Read symbols, codes & code lengths directly. */ 749 case stateHuffmanSimpleSize: 750 if !safeReadBits(br, 2, &s.symbol) { /* num_symbols */ 751 s.substate_huffman = stateHuffmanSimpleSize 752 return decoderNeedsMoreInput 753 } 754 755 s.sub_loop_counter = 0 756 fallthrough 757 758 case stateHuffmanSimpleRead: 759 { 760 var result int = readSimpleHuffmanSymbols(alphabet_size, max_symbol, s) 761 if result != decoderSuccess { 762 return result 763 } 764 } 765 fallthrough 766 767 case stateHuffmanSimpleBuild: 768 var table_size uint32 769 if s.symbol == 3 { 770 var bits uint32 771 if !safeReadBits(br, 1, &bits) { 772 s.substate_huffman = stateHuffmanSimpleBuild 773 return decoderNeedsMoreInput 774 } 775 776 s.symbol += bits 777 } 778 779 table_size = buildSimpleHuffmanTable(table, huffmanTableBits, s.symbols_lists_array[:], s.symbol) 780 if opt_table_size != nil { 781 *opt_table_size = table_size 782 } 783 784 s.substate_huffman = stateHuffmanNone 785 return decoderSuccess 786 787 /* Decode Huffman-coded code lengths. */ 788 case stateHuffmanComplex: 789 { 790 var i uint32 791 var result int = readCodeLengthCodeLengths(s) 792 if result != decoderSuccess { 793 return result 794 } 795 796 buildCodeLengthsHuffmanTable(s.table[:], s.code_length_code_lengths[:], s.code_length_histo[:]) 797 for i = 0; i < 16; i++ { 798 s.code_length_histo[i] = 0 799 } 800 801 for i = 0; i <= huffmanMaxCodeLength; i++ { 802 s.next_symbol[i] = int(i) - (huffmanMaxCodeLength + 1) 803 symbolListPut(s.symbol_lists, s.next_symbol[i], 0xFFFF) 804 } 805 806 s.symbol = 0 807 s.prev_code_len = initialRepeatedCodeLength 808 s.repeat = 0 809 s.repeat_code_len = 0 810 s.space = 32768 811 s.substate_huffman = stateHuffmanLengthSymbols 812 } 813 fallthrough 814 815 case stateHuffmanLengthSymbols: 816 var table_size uint32 817 var result int = readSymbolCodeLengths(max_symbol, s) 818 if result == decoderNeedsMoreInput { 819 result = safeReadSymbolCodeLengths(max_symbol, s) 820 } 821 822 if result != decoderSuccess { 823 return result 824 } 825 826 if s.space != 0 { 827 return decoderErrorFormatHuffmanSpace 828 } 829 830 table_size = buildHuffmanTable(table, huffmanTableBits, s.symbol_lists, s.code_length_histo[:]) 831 if opt_table_size != nil { 832 *opt_table_size = table_size 833 } 834 835 s.substate_huffman = stateHuffmanNone 836 return decoderSuccess 837 838 default: 839 return decoderErrorUnreachable 840 } 841 } 842} 843 844/* Decodes a block length by reading 3..39 bits. */ 845func readBlockLength(table []huffmanCode, br *bitReader) uint32 { 846 var code uint32 847 var nbits uint32 848 code = readSymbol(table, br) 849 nbits = kBlockLengthPrefixCode[code].nbits /* nbits == 2..24 */ 850 return kBlockLengthPrefixCode[code].offset + readBits(br, nbits) 851} 852 853/* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then 854 reading can't be continued with ReadBlockLength. */ 855func safeReadBlockLength(s *Reader, result *uint32, table []huffmanCode, br *bitReader) bool { 856 var index uint32 857 if s.substate_read_block_length == stateReadBlockLengthNone { 858 if !safeReadSymbol(table, br, &index) { 859 return false 860 } 861 } else { 862 index = s.block_length_index 863 } 864 { 865 var bits uint32 /* nbits == 2..24 */ 866 var nbits uint32 = kBlockLengthPrefixCode[index].nbits 867 if !safeReadBits(br, nbits, &bits) { 868 s.block_length_index = index 869 s.substate_read_block_length = stateReadBlockLengthSuffix 870 return false 871 } 872 873 *result = kBlockLengthPrefixCode[index].offset + bits 874 s.substate_read_block_length = stateReadBlockLengthNone 875 return true 876 } 877} 878 879/* Transform: 880 1) initialize list L with values 0, 1,... 255 881 2) For each input element X: 882 2.1) let Y = L[X] 883 2.2) remove X-th element from L 884 2.3) prepend Y to L 885 2.4) append Y to output 886 887 In most cases max(Y) <= 7, so most of L remains intact. 888 To reduce the cost of initialization, we reuse L, remember the upper bound 889 of Y values, and reinitialize only first elements in L. 890 891 Most of input values are 0 and 1. To reduce number of branches, we replace 892 inner for loop with do-while. */ 893func inverseMoveToFrontTransform(v []byte, v_len uint32, state *Reader) { 894 var mtf [256]byte 895 var i int 896 for i = 1; i < 256; i++ { 897 mtf[i] = byte(i) 898 } 899 var mtf_1 byte 900 901 /* Transform the input. */ 902 for i = 0; uint32(i) < v_len; i++ { 903 var index int = int(v[i]) 904 var value byte = mtf[index] 905 v[i] = value 906 mtf_1 = value 907 for index >= 1 { 908 index-- 909 mtf[index+1] = mtf[index] 910 } 911 912 mtf[0] = mtf_1 913 } 914} 915 916/* Decodes a series of Huffman table using ReadHuffmanCode function. */ 917func huffmanTreeGroupDecode(group *huffmanTreeGroup, s *Reader) int { 918 if s.substate_tree_group != stateTreeGroupLoop { 919 s.next = group.codes 920 s.htree_index = 0 921 s.substate_tree_group = stateTreeGroupLoop 922 } 923 924 for s.htree_index < int(group.num_htrees) { 925 var table_size uint32 926 var result int = readHuffmanCode(uint32(group.alphabet_size), uint32(group.max_symbol), s.next, &table_size, s) 927 if result != decoderSuccess { 928 return result 929 } 930 group.htrees[s.htree_index] = s.next 931 s.next = s.next[table_size:] 932 s.htree_index++ 933 } 934 935 s.substate_tree_group = stateTreeGroupNone 936 return decoderSuccess 937} 938 939/* Decodes a context map. 940 Decoding is done in 4 phases: 941 1) Read auxiliary information (6..16 bits) and allocate memory. 942 In case of trivial context map, decoding is finished at this phase. 943 2) Decode Huffman table using ReadHuffmanCode function. 944 This table will be used for reading context map items. 945 3) Read context map items; "0" values could be run-length encoded. 946 4) Optionally, apply InverseMoveToFront transform to the resulting map. */ 947func decodeContextMap(context_map_size uint32, num_htrees *uint32, context_map_arg *[]byte, s *Reader) int { 948 var br *bitReader = &s.br 949 var result int = decoderSuccess 950 951 switch int(s.substate_context_map) { 952 case stateContextMapNone: 953 result = decodeVarLenUint8(s, br, num_htrees) 954 if result != decoderSuccess { 955 return result 956 } 957 958 (*num_htrees)++ 959 s.context_index = 0 960 *context_map_arg = make([]byte, uint(context_map_size)) 961 if *context_map_arg == nil { 962 return decoderErrorAllocContextMap 963 } 964 965 if *num_htrees <= 1 { 966 for i := 0; i < int(context_map_size); i++ { 967 (*context_map_arg)[i] = 0 968 } 969 return decoderSuccess 970 } 971 972 s.substate_context_map = stateContextMapReadPrefix 973 fallthrough 974 /* Fall through. */ 975 case stateContextMapReadPrefix: 976 { 977 var bits uint32 978 979 /* In next stage ReadHuffmanCode uses at least 4 bits, so it is safe 980 to peek 4 bits ahead. */ 981 if !safeGetBits(br, 5, &bits) { 982 return decoderNeedsMoreInput 983 } 984 985 if bits&1 != 0 { /* Use RLE for zeros. */ 986 s.max_run_length_prefix = (bits >> 1) + 1 987 dropBits(br, 5) 988 } else { 989 s.max_run_length_prefix = 0 990 dropBits(br, 1) 991 } 992 993 s.substate_context_map = stateContextMapHuffman 994 } 995 fallthrough 996 997 /* Fall through. */ 998 case stateContextMapHuffman: 999 { 1000 var alphabet_size uint32 = *num_htrees + s.max_run_length_prefix 1001 result = readHuffmanCode(alphabet_size, alphabet_size, s.context_map_table[:], nil, s) 1002 if result != decoderSuccess { 1003 return result 1004 } 1005 s.code = 0xFFFF 1006 s.substate_context_map = stateContextMapDecode 1007 } 1008 fallthrough 1009 1010 /* Fall through. */ 1011 case stateContextMapDecode: 1012 { 1013 var context_index uint32 = s.context_index 1014 var max_run_length_prefix uint32 = s.max_run_length_prefix 1015 var context_map []byte = *context_map_arg 1016 var code uint32 = s.code 1017 var skip_preamble bool = (code != 0xFFFF) 1018 for context_index < context_map_size || skip_preamble { 1019 if !skip_preamble { 1020 if !safeReadSymbol(s.context_map_table[:], br, &code) { 1021 s.code = 0xFFFF 1022 s.context_index = context_index 1023 return decoderNeedsMoreInput 1024 } 1025 1026 if code == 0 { 1027 context_map[context_index] = 0 1028 context_index++ 1029 continue 1030 } 1031 1032 if code > max_run_length_prefix { 1033 context_map[context_index] = byte(code - max_run_length_prefix) 1034 context_index++ 1035 continue 1036 } 1037 } else { 1038 skip_preamble = false 1039 } 1040 1041 /* RLE sub-stage. */ 1042 { 1043 var reps uint32 1044 if !safeReadBits(br, code, &reps) { 1045 s.code = code 1046 s.context_index = context_index 1047 return decoderNeedsMoreInput 1048 } 1049 1050 reps += 1 << code 1051 if context_index+reps > context_map_size { 1052 return decoderErrorFormatContextMapRepeat 1053 } 1054 1055 for { 1056 context_map[context_index] = 0 1057 context_index++ 1058 reps-- 1059 if reps == 0 { 1060 break 1061 } 1062 } 1063 } 1064 } 1065 } 1066 fallthrough 1067 1068 case stateContextMapTransform: 1069 var bits uint32 1070 if !safeReadBits(br, 1, &bits) { 1071 s.substate_context_map = stateContextMapTransform 1072 return decoderNeedsMoreInput 1073 } 1074 1075 if bits != 0 { 1076 inverseMoveToFrontTransform(*context_map_arg, context_map_size, s) 1077 } 1078 1079 s.substate_context_map = stateContextMapNone 1080 return decoderSuccess 1081 1082 default: 1083 return decoderErrorUnreachable 1084 } 1085} 1086 1087/* Decodes a command or literal and updates block type ring-buffer. 1088 Reads 3..54 bits. */ 1089func decodeBlockTypeAndLength(safe int, s *Reader, tree_type int) bool { 1090 var max_block_type uint32 = s.num_block_types[tree_type] 1091 type_tree := s.block_type_trees[tree_type*huffmanMaxSize258:] 1092 len_tree := s.block_len_trees[tree_type*huffmanMaxSize26:] 1093 var br *bitReader = &s.br 1094 var ringbuffer []uint32 = s.block_type_rb[tree_type*2:] 1095 var block_type uint32 1096 if max_block_type <= 1 { 1097 return false 1098 } 1099 1100 /* Read 0..15 + 3..39 bits. */ 1101 if safe == 0 { 1102 block_type = readSymbol(type_tree, br) 1103 s.block_length[tree_type] = readBlockLength(len_tree, br) 1104 } else { 1105 var memento bitReaderState 1106 bitReaderSaveState(br, &memento) 1107 if !safeReadSymbol(type_tree, br, &block_type) { 1108 return false 1109 } 1110 if !safeReadBlockLength(s, &s.block_length[tree_type], len_tree, br) { 1111 s.substate_read_block_length = stateReadBlockLengthNone 1112 bitReaderRestoreState(br, &memento) 1113 return false 1114 } 1115 } 1116 1117 if block_type == 1 { 1118 block_type = ringbuffer[1] + 1 1119 } else if block_type == 0 { 1120 block_type = ringbuffer[0] 1121 } else { 1122 block_type -= 2 1123 } 1124 1125 if block_type >= max_block_type { 1126 block_type -= max_block_type 1127 } 1128 1129 ringbuffer[0] = ringbuffer[1] 1130 ringbuffer[1] = block_type 1131 return true 1132} 1133 1134func detectTrivialLiteralBlockTypes(s *Reader) { 1135 var i uint 1136 for i = 0; i < 8; i++ { 1137 s.trivial_literal_contexts[i] = 0 1138 } 1139 for i = 0; uint32(i) < s.num_block_types[0]; i++ { 1140 var offset uint = i << literalContextBits 1141 var error uint = 0 1142 var sample uint = uint(s.context_map[offset]) 1143 var j uint 1144 for j = 0; j < 1<<literalContextBits; { 1145 var k int 1146 for k = 0; k < 4; k++ { 1147 error |= uint(s.context_map[offset+j]) ^ sample 1148 j++ 1149 } 1150 } 1151 1152 if error == 0 { 1153 s.trivial_literal_contexts[i>>5] |= 1 << (i & 31) 1154 } 1155 } 1156} 1157 1158func prepareLiteralDecoding(s *Reader) { 1159 var context_mode byte 1160 var trivial uint 1161 var block_type uint32 = s.block_type_rb[1] 1162 var context_offset uint32 = block_type << literalContextBits 1163 s.context_map_slice = s.context_map[context_offset:] 1164 trivial = uint(s.trivial_literal_contexts[block_type>>5]) 1165 s.trivial_literal_context = int((trivial >> (block_type & 31)) & 1) 1166 s.literal_htree = []huffmanCode(s.literal_hgroup.htrees[s.context_map_slice[0]]) 1167 context_mode = s.context_modes[block_type] & 3 1168 s.context_lookup = getContextLUT(int(context_mode)) 1169} 1170 1171/* Decodes the block type and updates the state for literal context. 1172 Reads 3..54 bits. */ 1173func decodeLiteralBlockSwitchInternal(safe int, s *Reader) bool { 1174 if !decodeBlockTypeAndLength(safe, s, 0) { 1175 return false 1176 } 1177 1178 prepareLiteralDecoding(s) 1179 return true 1180} 1181 1182func decodeLiteralBlockSwitch(s *Reader) { 1183 decodeLiteralBlockSwitchInternal(0, s) 1184} 1185 1186func safeDecodeLiteralBlockSwitch(s *Reader) bool { 1187 return decodeLiteralBlockSwitchInternal(1, s) 1188} 1189 1190/* Block switch for insert/copy length. 1191 Reads 3..54 bits. */ 1192func decodeCommandBlockSwitchInternal(safe int, s *Reader) bool { 1193 if !decodeBlockTypeAndLength(safe, s, 1) { 1194 return false 1195 } 1196 1197 s.htree_command = []huffmanCode(s.insert_copy_hgroup.htrees[s.block_type_rb[3]]) 1198 return true 1199} 1200 1201func decodeCommandBlockSwitch(s *Reader) { 1202 decodeCommandBlockSwitchInternal(0, s) 1203} 1204 1205func safeDecodeCommandBlockSwitch(s *Reader) bool { 1206 return decodeCommandBlockSwitchInternal(1, s) 1207} 1208 1209/* Block switch for distance codes. 1210 Reads 3..54 bits. */ 1211func decodeDistanceBlockSwitchInternal(safe int, s *Reader) bool { 1212 if !decodeBlockTypeAndLength(safe, s, 2) { 1213 return false 1214 } 1215 1216 s.dist_context_map_slice = s.dist_context_map[s.block_type_rb[5]<<distanceContextBits:] 1217 s.dist_htree_index = s.dist_context_map_slice[s.distance_context] 1218 return true 1219} 1220 1221func decodeDistanceBlockSwitch(s *Reader) { 1222 decodeDistanceBlockSwitchInternal(0, s) 1223} 1224 1225func safeDecodeDistanceBlockSwitch(s *Reader) bool { 1226 return decodeDistanceBlockSwitchInternal(1, s) 1227} 1228 1229func unwrittenBytes(s *Reader, wrap bool) uint { 1230 var pos uint 1231 if wrap && s.pos > s.ringbuffer_size { 1232 pos = uint(s.ringbuffer_size) 1233 } else { 1234 pos = uint(s.pos) 1235 } 1236 var partial_pos_rb uint = (s.rb_roundtrips * uint(s.ringbuffer_size)) + pos 1237 return partial_pos_rb - s.partial_pos_out 1238} 1239 1240/* Dumps output. 1241 Returns BROTLI_DECODER_NEEDS_MORE_OUTPUT only if there is more output to push 1242 and either ring-buffer is as big as window size, or |force| is true. */ 1243func writeRingBuffer(s *Reader, available_out *uint, next_out *[]byte, total_out *uint, force bool) int { 1244 start := s.ringbuffer[s.partial_pos_out&uint(s.ringbuffer_mask):] 1245 var to_write uint = unwrittenBytes(s, true) 1246 var num_written uint = *available_out 1247 if num_written > to_write { 1248 num_written = to_write 1249 } 1250 1251 if s.meta_block_remaining_len < 0 { 1252 return decoderErrorFormatBlockLength1 1253 } 1254 1255 if next_out != nil && *next_out == nil { 1256 *next_out = start 1257 } else { 1258 if next_out != nil { 1259 copy(*next_out, start[:num_written]) 1260 *next_out = (*next_out)[num_written:] 1261 } 1262 } 1263 1264 *available_out -= num_written 1265 s.partial_pos_out += num_written 1266 if total_out != nil { 1267 *total_out = s.partial_pos_out 1268 } 1269 1270 if num_written < to_write { 1271 if s.ringbuffer_size == 1<<s.window_bits || force { 1272 return decoderNeedsMoreOutput 1273 } else { 1274 return decoderSuccess 1275 } 1276 } 1277 1278 /* Wrap ring buffer only if it has reached its maximal size. */ 1279 if s.ringbuffer_size == 1<<s.window_bits && s.pos >= s.ringbuffer_size { 1280 s.pos -= s.ringbuffer_size 1281 s.rb_roundtrips++ 1282 if uint(s.pos) != 0 { 1283 s.should_wrap_ringbuffer = 1 1284 } else { 1285 s.should_wrap_ringbuffer = 0 1286 } 1287 } 1288 1289 return decoderSuccess 1290} 1291 1292func wrapRingBuffer(s *Reader) { 1293 if s.should_wrap_ringbuffer != 0 { 1294 copy(s.ringbuffer, s.ringbuffer_end[:uint(s.pos)]) 1295 s.should_wrap_ringbuffer = 0 1296 } 1297} 1298 1299/* Allocates ring-buffer. 1300 1301 s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before 1302 this function is called. 1303 1304 Last two bytes of ring-buffer are initialized to 0, so context calculation 1305 could be done uniformly for the first two and all other positions. */ 1306func ensureRingBuffer(s *Reader) bool { 1307 var old_ringbuffer []byte = s.ringbuffer 1308 if s.ringbuffer_size == s.new_ringbuffer_size { 1309 return true 1310 } 1311 1312 s.ringbuffer = make([]byte, uint(s.new_ringbuffer_size)+uint(kRingBufferWriteAheadSlack)) 1313 if s.ringbuffer == nil { 1314 /* Restore previous value. */ 1315 s.ringbuffer = old_ringbuffer 1316 1317 return false 1318 } 1319 1320 s.ringbuffer[s.new_ringbuffer_size-2] = 0 1321 s.ringbuffer[s.new_ringbuffer_size-1] = 0 1322 1323 if !(old_ringbuffer == nil) { 1324 copy(s.ringbuffer, old_ringbuffer[:uint(s.pos)]) 1325 1326 old_ringbuffer = nil 1327 } 1328 1329 s.ringbuffer_size = s.new_ringbuffer_size 1330 s.ringbuffer_mask = s.new_ringbuffer_size - 1 1331 s.ringbuffer_end = s.ringbuffer[s.ringbuffer_size:] 1332 1333 return true 1334} 1335 1336func copyUncompressedBlockToOutput(available_out *uint, next_out *[]byte, total_out *uint, s *Reader) int { 1337 /* TODO: avoid allocation for single uncompressed block. */ 1338 if !ensureRingBuffer(s) { 1339 return decoderErrorAllocRingBuffer1 1340 } 1341 1342 /* State machine */ 1343 for { 1344 switch s.substate_uncompressed { 1345 case stateUncompressedNone: 1346 { 1347 var nbytes int = int(getRemainingBytes(&s.br)) 1348 if nbytes > s.meta_block_remaining_len { 1349 nbytes = s.meta_block_remaining_len 1350 } 1351 1352 if s.pos+nbytes > s.ringbuffer_size { 1353 nbytes = s.ringbuffer_size - s.pos 1354 } 1355 1356 /* Copy remaining bytes from s->br.buf_ to ring-buffer. */ 1357 copyBytes(s.ringbuffer[s.pos:], &s.br, uint(nbytes)) 1358 1359 s.pos += nbytes 1360 s.meta_block_remaining_len -= nbytes 1361 if s.pos < 1<<s.window_bits { 1362 if s.meta_block_remaining_len == 0 { 1363 return decoderSuccess 1364 } 1365 1366 return decoderNeedsMoreInput 1367 } 1368 1369 s.substate_uncompressed = stateUncompressedWrite 1370 } 1371 fallthrough 1372 1373 case stateUncompressedWrite: 1374 { 1375 result := writeRingBuffer(s, available_out, next_out, total_out, false) 1376 if result != decoderSuccess { 1377 return result 1378 } 1379 1380 if s.ringbuffer_size == 1<<s.window_bits { 1381 s.max_distance = s.max_backward_distance 1382 } 1383 1384 s.substate_uncompressed = stateUncompressedNone 1385 break 1386 } 1387 } 1388 } 1389} 1390 1391/* Calculates the smallest feasible ring buffer. 1392 1393 If we know the data size is small, do not allocate more ring buffer 1394 size than needed to reduce memory usage. 1395 1396 When this method is called, metablock size and flags MUST be decoded. */ 1397func calculateRingBufferSize(s *Reader) { 1398 var window_size int = 1 << s.window_bits 1399 var new_ringbuffer_size int = window_size 1400 var min_size int 1401 /* We need at least 2 bytes of ring buffer size to get the last two 1402 bytes for context from there */ 1403 if s.ringbuffer_size != 0 { 1404 min_size = s.ringbuffer_size 1405 } else { 1406 min_size = 1024 1407 } 1408 var output_size int 1409 1410 /* If maximum is already reached, no further extension is retired. */ 1411 if s.ringbuffer_size == window_size { 1412 return 1413 } 1414 1415 /* Metadata blocks does not touch ring buffer. */ 1416 if s.is_metadata != 0 { 1417 return 1418 } 1419 1420 if s.ringbuffer == nil { 1421 output_size = 0 1422 } else { 1423 output_size = s.pos 1424 } 1425 1426 output_size += s.meta_block_remaining_len 1427 if min_size < output_size { 1428 min_size = output_size 1429 } 1430 1431 if !(s.canny_ringbuffer_allocation == 0) { 1432 /* Reduce ring buffer size to save memory when server is unscrupulous. 1433 In worst case memory usage might be 1.5x bigger for a short period of 1434 ring buffer reallocation. */ 1435 for new_ringbuffer_size>>1 >= min_size { 1436 new_ringbuffer_size >>= 1 1437 } 1438 } 1439 1440 s.new_ringbuffer_size = new_ringbuffer_size 1441} 1442 1443/* Reads 1..256 2-bit context modes. */ 1444func readContextModes(s *Reader) int { 1445 var br *bitReader = &s.br 1446 var i int = s.loop_counter 1447 1448 for i < int(s.num_block_types[0]) { 1449 var bits uint32 1450 if !safeReadBits(br, 2, &bits) { 1451 s.loop_counter = i 1452 return decoderNeedsMoreInput 1453 } 1454 1455 s.context_modes[i] = byte(bits) 1456 i++ 1457 } 1458 1459 return decoderSuccess 1460} 1461 1462func takeDistanceFromRingBuffer(s *Reader) { 1463 if s.distance_code == 0 { 1464 s.dist_rb_idx-- 1465 s.distance_code = s.dist_rb[s.dist_rb_idx&3] 1466 1467 /* Compensate double distance-ring-buffer roll for dictionary items. */ 1468 s.distance_context = 1 1469 } else { 1470 var distance_code int = s.distance_code << 1 1471 const kDistanceShortCodeIndexOffset uint32 = 0xAAAFFF1B 1472 const kDistanceShortCodeValueOffset uint32 = 0xFA5FA500 1473 var v int = (s.dist_rb_idx + int(kDistanceShortCodeIndexOffset>>uint(distance_code))) & 0x3 1474 /* kDistanceShortCodeIndexOffset has 2-bit values from LSB: 1475 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */ 1476 1477 /* kDistanceShortCodeValueOffset has 2-bit values from LSB: 1478 -0, 0,-0, 0,-1, 1,-2, 2,-3, 3,-1, 1,-2, 2,-3, 3 */ 1479 s.distance_code = s.dist_rb[v] 1480 1481 v = int(kDistanceShortCodeValueOffset>>uint(distance_code)) & 0x3 1482 if distance_code&0x3 != 0 { 1483 s.distance_code += v 1484 } else { 1485 s.distance_code -= v 1486 if s.distance_code <= 0 { 1487 /* A huge distance will cause a () soon. 1488 This is a little faster than failing here. */ 1489 s.distance_code = 0x7FFFFFFF 1490 } 1491 } 1492 } 1493} 1494 1495func safeReadBitsMaybeZero(br *bitReader, n_bits uint32, val *uint32) bool { 1496 if n_bits != 0 { 1497 return safeReadBits(br, n_bits, val) 1498 } else { 1499 *val = 0 1500 return true 1501 } 1502} 1503 1504/* Precondition: s->distance_code < 0. */ 1505func readDistanceInternal(safe int, s *Reader, br *bitReader) bool { 1506 var distval int 1507 var memento bitReaderState 1508 var distance_tree []huffmanCode = []huffmanCode(s.distance_hgroup.htrees[s.dist_htree_index]) 1509 if safe == 0 { 1510 s.distance_code = int(readSymbol(distance_tree, br)) 1511 } else { 1512 var code uint32 1513 bitReaderSaveState(br, &memento) 1514 if !safeReadSymbol(distance_tree, br, &code) { 1515 return false 1516 } 1517 1518 s.distance_code = int(code) 1519 } 1520 1521 /* Convert the distance code to the actual distance by possibly 1522 looking up past distances from the s->ringbuffer. */ 1523 s.distance_context = 0 1524 1525 if s.distance_code&^0xF == 0 { 1526 takeDistanceFromRingBuffer(s) 1527 s.block_length[2]-- 1528 return true 1529 } 1530 1531 distval = s.distance_code - int(s.num_direct_distance_codes) 1532 if distval >= 0 { 1533 var nbits uint32 1534 var postfix int 1535 var offset int 1536 if safe == 0 && (s.distance_postfix_bits == 0) { 1537 nbits = (uint32(distval) >> 1) + 1 1538 offset = ((2 + (distval & 1)) << nbits) - 4 1539 s.distance_code = int(s.num_direct_distance_codes) + offset + int(readBits(br, nbits)) 1540 } else { 1541 /* This branch also works well when s->distance_postfix_bits == 0. */ 1542 var bits uint32 1543 postfix = distval & s.distance_postfix_mask 1544 distval >>= s.distance_postfix_bits 1545 nbits = (uint32(distval) >> 1) + 1 1546 if safe != 0 { 1547 if !safeReadBitsMaybeZero(br, nbits, &bits) { 1548 s.distance_code = -1 /* Restore precondition. */ 1549 bitReaderRestoreState(br, &memento) 1550 return false 1551 } 1552 } else { 1553 bits = readBits(br, nbits) 1554 } 1555 1556 offset = ((2 + (distval & 1)) << nbits) - 4 1557 s.distance_code = int(s.num_direct_distance_codes) + ((offset + int(bits)) << s.distance_postfix_bits) + postfix 1558 } 1559 } 1560 1561 s.distance_code = s.distance_code - numDistanceShortCodes + 1 1562 s.block_length[2]-- 1563 return true 1564} 1565 1566func readDistance(s *Reader, br *bitReader) { 1567 readDistanceInternal(0, s, br) 1568} 1569 1570func safeReadDistance(s *Reader, br *bitReader) bool { 1571 return readDistanceInternal(1, s, br) 1572} 1573 1574func readCommandInternal(safe int, s *Reader, br *bitReader, insert_length *int) bool { 1575 var cmd_code uint32 1576 var insert_len_extra uint32 = 0 1577 var copy_length uint32 1578 var v cmdLutElement 1579 var memento bitReaderState 1580 if safe == 0 { 1581 cmd_code = readSymbol(s.htree_command, br) 1582 } else { 1583 bitReaderSaveState(br, &memento) 1584 if !safeReadSymbol(s.htree_command, br, &cmd_code) { 1585 return false 1586 } 1587 } 1588 1589 v = kCmdLut[cmd_code] 1590 s.distance_code = int(v.distance_code) 1591 s.distance_context = int(v.context) 1592 s.dist_htree_index = s.dist_context_map_slice[s.distance_context] 1593 *insert_length = int(v.insert_len_offset) 1594 if safe == 0 { 1595 if v.insert_len_extra_bits != 0 { 1596 insert_len_extra = readBits(br, uint32(v.insert_len_extra_bits)) 1597 } 1598 1599 copy_length = readBits(br, uint32(v.copy_len_extra_bits)) 1600 } else { 1601 if !safeReadBitsMaybeZero(br, uint32(v.insert_len_extra_bits), &insert_len_extra) || !safeReadBitsMaybeZero(br, uint32(v.copy_len_extra_bits), ©_length) { 1602 bitReaderRestoreState(br, &memento) 1603 return false 1604 } 1605 } 1606 1607 s.copy_length = int(copy_length) + int(v.copy_len_offset) 1608 s.block_length[1]-- 1609 *insert_length += int(insert_len_extra) 1610 return true 1611} 1612 1613func readCommand(s *Reader, br *bitReader, insert_length *int) { 1614 readCommandInternal(0, s, br, insert_length) 1615} 1616 1617func safeReadCommand(s *Reader, br *bitReader, insert_length *int) bool { 1618 return readCommandInternal(1, s, br, insert_length) 1619} 1620 1621func checkInputAmountMaybeSafe(safe int, br *bitReader, num uint) bool { 1622 if safe != 0 { 1623 return true 1624 } 1625 1626 return checkInputAmount(br, num) 1627} 1628 1629func processCommandsInternal(safe int, s *Reader) int { 1630 var pos int = s.pos 1631 var i int = s.loop_counter 1632 var result int = decoderSuccess 1633 var br *bitReader = &s.br 1634 var hc []huffmanCode 1635 1636 if !checkInputAmountMaybeSafe(safe, br, 28) { 1637 result = decoderNeedsMoreInput 1638 goto saveStateAndReturn 1639 } 1640 1641 if safe == 0 { 1642 warmupBitReader(br) 1643 } 1644 1645 /* Jump into state machine. */ 1646 if s.state == stateCommandBegin { 1647 goto CommandBegin 1648 } else if s.state == stateCommandInner { 1649 goto CommandInner 1650 } else if s.state == stateCommandPostDecodeLiterals { 1651 goto CommandPostDecodeLiterals 1652 } else if s.state == stateCommandPostWrapCopy { 1653 goto CommandPostWrapCopy 1654 } else { 1655 return decoderErrorUnreachable 1656 } 1657 1658CommandBegin: 1659 if safe != 0 { 1660 s.state = stateCommandBegin 1661 } 1662 1663 if !checkInputAmountMaybeSafe(safe, br, 28) { /* 156 bits + 7 bytes */ 1664 s.state = stateCommandBegin 1665 result = decoderNeedsMoreInput 1666 goto saveStateAndReturn 1667 } 1668 1669 if s.block_length[1] == 0 { 1670 if safe != 0 { 1671 if !safeDecodeCommandBlockSwitch(s) { 1672 result = decoderNeedsMoreInput 1673 goto saveStateAndReturn 1674 } 1675 } else { 1676 decodeCommandBlockSwitch(s) 1677 } 1678 1679 goto CommandBegin 1680 } 1681 1682 /* Read the insert/copy length in the command. */ 1683 if safe != 0 { 1684 if !safeReadCommand(s, br, &i) { 1685 result = decoderNeedsMoreInput 1686 goto saveStateAndReturn 1687 } 1688 } else { 1689 readCommand(s, br, &i) 1690 } 1691 1692 if i == 0 { 1693 goto CommandPostDecodeLiterals 1694 } 1695 1696 s.meta_block_remaining_len -= i 1697 1698CommandInner: 1699 if safe != 0 { 1700 s.state = stateCommandInner 1701 } 1702 1703 /* Read the literals in the command. */ 1704 if s.trivial_literal_context != 0 { 1705 var bits uint32 1706 var value uint32 1707 preloadSymbol(safe, s.literal_htree, br, &bits, &value) 1708 for { 1709 if !checkInputAmountMaybeSafe(safe, br, 28) { /* 162 bits + 7 bytes */ 1710 s.state = stateCommandInner 1711 result = decoderNeedsMoreInput 1712 goto saveStateAndReturn 1713 } 1714 1715 if s.block_length[0] == 0 { 1716 if safe != 0 { 1717 if !safeDecodeLiteralBlockSwitch(s) { 1718 result = decoderNeedsMoreInput 1719 goto saveStateAndReturn 1720 } 1721 } else { 1722 decodeLiteralBlockSwitch(s) 1723 } 1724 1725 preloadSymbol(safe, s.literal_htree, br, &bits, &value) 1726 if s.trivial_literal_context == 0 { 1727 goto CommandInner 1728 } 1729 } 1730 1731 if safe == 0 { 1732 s.ringbuffer[pos] = byte(readPreloadedSymbol(s.literal_htree, br, &bits, &value)) 1733 } else { 1734 var literal uint32 1735 if !safeReadSymbol(s.literal_htree, br, &literal) { 1736 result = decoderNeedsMoreInput 1737 goto saveStateAndReturn 1738 } 1739 1740 s.ringbuffer[pos] = byte(literal) 1741 } 1742 1743 s.block_length[0]-- 1744 pos++ 1745 if pos == s.ringbuffer_size { 1746 s.state = stateCommandInnerWrite 1747 i-- 1748 goto saveStateAndReturn 1749 } 1750 i-- 1751 if i == 0 { 1752 break 1753 } 1754 } 1755 } else { 1756 var p1 byte = s.ringbuffer[(pos-1)&s.ringbuffer_mask] 1757 var p2 byte = s.ringbuffer[(pos-2)&s.ringbuffer_mask] 1758 for { 1759 var context byte 1760 if !checkInputAmountMaybeSafe(safe, br, 28) { /* 162 bits + 7 bytes */ 1761 s.state = stateCommandInner 1762 result = decoderNeedsMoreInput 1763 goto saveStateAndReturn 1764 } 1765 1766 if s.block_length[0] == 0 { 1767 if safe != 0 { 1768 if !safeDecodeLiteralBlockSwitch(s) { 1769 result = decoderNeedsMoreInput 1770 goto saveStateAndReturn 1771 } 1772 } else { 1773 decodeLiteralBlockSwitch(s) 1774 } 1775 1776 if s.trivial_literal_context != 0 { 1777 goto CommandInner 1778 } 1779 } 1780 1781 context = getContext(p1, p2, s.context_lookup) 1782 hc = []huffmanCode(s.literal_hgroup.htrees[s.context_map_slice[context]]) 1783 p2 = p1 1784 if safe == 0 { 1785 p1 = byte(readSymbol(hc, br)) 1786 } else { 1787 var literal uint32 1788 if !safeReadSymbol(hc, br, &literal) { 1789 result = decoderNeedsMoreInput 1790 goto saveStateAndReturn 1791 } 1792 1793 p1 = byte(literal) 1794 } 1795 1796 s.ringbuffer[pos] = p1 1797 s.block_length[0]-- 1798 pos++ 1799 if pos == s.ringbuffer_size { 1800 s.state = stateCommandInnerWrite 1801 i-- 1802 goto saveStateAndReturn 1803 } 1804 i-- 1805 if i == 0 { 1806 break 1807 } 1808 } 1809 } 1810 1811 if s.meta_block_remaining_len <= 0 { 1812 s.state = stateMetablockDone 1813 goto saveStateAndReturn 1814 } 1815 1816CommandPostDecodeLiterals: 1817 if safe != 0 { 1818 s.state = stateCommandPostDecodeLiterals 1819 } 1820 1821 if s.distance_code >= 0 { 1822 /* Implicit distance case. */ 1823 if s.distance_code != 0 { 1824 s.distance_context = 0 1825 } else { 1826 s.distance_context = 1 1827 } 1828 1829 s.dist_rb_idx-- 1830 s.distance_code = s.dist_rb[s.dist_rb_idx&3] 1831 } else { 1832 /* Read distance code in the command, unless it was implicitly zero. */ 1833 if s.block_length[2] == 0 { 1834 if safe != 0 { 1835 if !safeDecodeDistanceBlockSwitch(s) { 1836 result = decoderNeedsMoreInput 1837 goto saveStateAndReturn 1838 } 1839 } else { 1840 decodeDistanceBlockSwitch(s) 1841 } 1842 } 1843 1844 if safe != 0 { 1845 if !safeReadDistance(s, br) { 1846 result = decoderNeedsMoreInput 1847 goto saveStateAndReturn 1848 } 1849 } else { 1850 readDistance(s, br) 1851 } 1852 } 1853 1854 if s.max_distance != s.max_backward_distance { 1855 if pos < s.max_backward_distance { 1856 s.max_distance = pos 1857 } else { 1858 s.max_distance = s.max_backward_distance 1859 } 1860 } 1861 1862 i = s.copy_length 1863 1864 /* Apply copy of LZ77 back-reference, or static dictionary reference if 1865 the distance is larger than the max LZ77 distance */ 1866 if s.distance_code > s.max_distance { 1867 /* The maximum allowed distance is BROTLI_MAX_ALLOWED_DISTANCE = 0x7FFFFFFC. 1868 With this choice, no signed overflow can occur after decoding 1869 a special distance code (e.g., after adding 3 to the last distance). */ 1870 if s.distance_code > maxAllowedDistance { 1871 return decoderErrorFormatDistance 1872 } 1873 1874 if i >= minDictionaryWordLength && i <= maxDictionaryWordLength { 1875 var address int = s.distance_code - s.max_distance - 1 1876 var words *dictionary = s.dictionary 1877 var trans *transforms = s.transforms 1878 var offset int = int(s.dictionary.offsets_by_length[i]) 1879 var shift uint32 = uint32(s.dictionary.size_bits_by_length[i]) 1880 var mask int = int(bitMask(shift)) 1881 var word_idx int = address & mask 1882 var transform_idx int = address >> shift 1883 1884 /* Compensate double distance-ring-buffer roll. */ 1885 s.dist_rb_idx += s.distance_context 1886 1887 offset += word_idx * i 1888 if words.data == nil { 1889 return decoderErrorDictionaryNotSet 1890 } 1891 1892 if transform_idx < int(trans.num_transforms) { 1893 word := words.data[offset:] 1894 var len int = i 1895 if transform_idx == int(trans.cutOffTransforms[0]) { 1896 copy(s.ringbuffer[pos:], word[:uint(len)]) 1897 } else { 1898 len = transformDictionaryWord(s.ringbuffer[pos:], word, int(len), trans, transform_idx) 1899 } 1900 1901 pos += int(len) 1902 s.meta_block_remaining_len -= int(len) 1903 if pos >= s.ringbuffer_size { 1904 s.state = stateCommandPostWrite1 1905 goto saveStateAndReturn 1906 } 1907 } else { 1908 return decoderErrorFormatTransform 1909 } 1910 } else { 1911 return decoderErrorFormatDictionary 1912 } 1913 } else { 1914 var src_start int = (pos - s.distance_code) & s.ringbuffer_mask 1915 copy_dst := s.ringbuffer[pos:] 1916 copy_src := s.ringbuffer[src_start:] 1917 var dst_end int = pos + i 1918 var src_end int = src_start + i 1919 1920 /* Update the recent distances cache. */ 1921 s.dist_rb[s.dist_rb_idx&3] = s.distance_code 1922 1923 s.dist_rb_idx++ 1924 s.meta_block_remaining_len -= i 1925 1926 /* There are 32+ bytes of slack in the ring-buffer allocation. 1927 Also, we have 16 short codes, that make these 16 bytes irrelevant 1928 in the ring-buffer. Let's copy over them as a first guess. */ 1929 copy(copy_dst, copy_src[:16]) 1930 1931 if src_end > pos && dst_end > src_start { 1932 /* Regions intersect. */ 1933 goto CommandPostWrapCopy 1934 } 1935 1936 if dst_end >= s.ringbuffer_size || src_end >= s.ringbuffer_size { 1937 /* At least one region wraps. */ 1938 goto CommandPostWrapCopy 1939 } 1940 1941 pos += i 1942 if i > 16 { 1943 if i > 32 { 1944 copy(copy_dst[16:], copy_src[16:][:uint(i-16)]) 1945 } else { 1946 /* This branch covers about 45% cases. 1947 Fixed size short copy allows more compiler optimizations. */ 1948 copy(copy_dst[16:], copy_src[16:][:16]) 1949 } 1950 } 1951 } 1952 1953 if s.meta_block_remaining_len <= 0 { 1954 /* Next metablock, if any. */ 1955 s.state = stateMetablockDone 1956 1957 goto saveStateAndReturn 1958 } else { 1959 goto CommandBegin 1960 } 1961CommandPostWrapCopy: 1962 { 1963 var wrap_guard int = s.ringbuffer_size - pos 1964 for { 1965 i-- 1966 if i < 0 { 1967 break 1968 } 1969 s.ringbuffer[pos] = s.ringbuffer[(pos-s.distance_code)&s.ringbuffer_mask] 1970 pos++ 1971 wrap_guard-- 1972 if wrap_guard == 0 { 1973 s.state = stateCommandPostWrite2 1974 goto saveStateAndReturn 1975 } 1976 } 1977 } 1978 1979 if s.meta_block_remaining_len <= 0 { 1980 /* Next metablock, if any. */ 1981 s.state = stateMetablockDone 1982 1983 goto saveStateAndReturn 1984 } else { 1985 goto CommandBegin 1986 } 1987 1988saveStateAndReturn: 1989 s.pos = pos 1990 s.loop_counter = i 1991 return result 1992} 1993 1994func processCommands(s *Reader) int { 1995 return processCommandsInternal(0, s) 1996} 1997 1998func safeProcessCommands(s *Reader) int { 1999 return processCommandsInternal(1, s) 2000} 2001 2002/* Returns the maximum number of distance symbols which can only represent 2003 distances not exceeding BROTLI_MAX_ALLOWED_DISTANCE. */ 2004 2005var maxDistanceSymbol_bound = [maxNpostfix + 1]uint32{0, 4, 12, 28} 2006var maxDistanceSymbol_diff = [maxNpostfix + 1]uint32{73, 126, 228, 424} 2007 2008func maxDistanceSymbol(ndirect uint32, npostfix uint32) uint32 { 2009 var postfix uint32 = 1 << npostfix 2010 if ndirect < maxDistanceSymbol_bound[npostfix] { 2011 return ndirect + maxDistanceSymbol_diff[npostfix] + postfix 2012 } else if ndirect > maxDistanceSymbol_bound[npostfix]+postfix { 2013 return ndirect + maxDistanceSymbol_diff[npostfix] 2014 } else { 2015 return maxDistanceSymbol_bound[npostfix] + maxDistanceSymbol_diff[npostfix] + postfix 2016 } 2017} 2018 2019/* Invariant: input stream is never overconsumed: 2020 - invalid input implies that the whole stream is invalid -> any amount of 2021 input could be read and discarded 2022 - when result is "needs more input", then at least one more byte is REQUIRED 2023 to complete decoding; all input data MUST be consumed by decoder, so 2024 client could swap the input buffer 2025 - when result is "needs more output" decoder MUST ensure that it doesn't 2026 hold more than 7 bits in bit reader; this saves client from swapping input 2027 buffer ahead of time 2028 - when result is "success" decoder MUST return all unused data back to input 2029 buffer; this is possible because the invariant is held on enter */ 2030func decoderDecompressStream(s *Reader, available_in *uint, next_in *[]byte, available_out *uint, next_out *[]byte) int { 2031 var result int = decoderSuccess 2032 var br *bitReader = &s.br 2033 2034 /* Do not try to process further in a case of unrecoverable error. */ 2035 if int(s.error_code) < 0 { 2036 return decoderResultError 2037 } 2038 2039 if *available_out != 0 && (next_out == nil || *next_out == nil) { 2040 return saveErrorCode(s, decoderErrorInvalidArguments) 2041 } 2042 2043 if *available_out == 0 { 2044 next_out = nil 2045 } 2046 if s.buffer_length == 0 { /* Just connect bit reader to input stream. */ 2047 br.input_len = *available_in 2048 br.input = *next_in 2049 br.byte_pos = 0 2050 } else { 2051 /* At least one byte of input is required. More than one byte of input may 2052 be required to complete the transaction -> reading more data must be 2053 done in a loop -> do it in a main loop. */ 2054 result = decoderNeedsMoreInput 2055 2056 br.input = s.buffer.u8[:] 2057 br.byte_pos = 0 2058 } 2059 2060 /* State machine */ 2061 for { 2062 if result != decoderSuccess { 2063 /* Error, needs more input/output. */ 2064 if result == decoderNeedsMoreInput { 2065 if s.ringbuffer != nil { /* Pro-actively push output. */ 2066 var intermediate_result int = writeRingBuffer(s, available_out, next_out, nil, true) 2067 2068 /* WriteRingBuffer checks s->meta_block_remaining_len validity. */ 2069 if int(intermediate_result) < 0 { 2070 result = intermediate_result 2071 break 2072 } 2073 } 2074 2075 if s.buffer_length != 0 { /* Used with internal buffer. */ 2076 if br.byte_pos == br.input_len { 2077 /* Successfully finished read transaction. 2078 Accumulator contains less than 8 bits, because internal buffer 2079 is expanded byte-by-byte until it is enough to complete read. */ 2080 s.buffer_length = 0 2081 2082 /* Switch to input stream and restart. */ 2083 result = decoderSuccess 2084 2085 br.input_len = *available_in 2086 br.input = *next_in 2087 br.byte_pos = 0 2088 continue 2089 } else if *available_in != 0 { 2090 /* Not enough data in buffer, but can take one more byte from 2091 input stream. */ 2092 result = decoderSuccess 2093 2094 s.buffer.u8[s.buffer_length] = (*next_in)[0] 2095 s.buffer_length++ 2096 br.input_len = uint(s.buffer_length) 2097 *next_in = (*next_in)[1:] 2098 (*available_in)-- 2099 2100 /* Retry with more data in buffer. */ 2101 continue 2102 } 2103 2104 /* Can't finish reading and no more input. */ 2105 break 2106 /* Input stream doesn't contain enough input. */ 2107 } else { 2108 /* Copy tail to internal buffer and return. */ 2109 *next_in = br.input[br.byte_pos:] 2110 2111 *available_in = br.input_len - br.byte_pos 2112 for *available_in != 0 { 2113 s.buffer.u8[s.buffer_length] = (*next_in)[0] 2114 s.buffer_length++ 2115 *next_in = (*next_in)[1:] 2116 (*available_in)-- 2117 } 2118 2119 break 2120 } 2121 } 2122 2123 /* Unreachable. */ 2124 2125 /* Fail or needs more output. */ 2126 if s.buffer_length != 0 { 2127 /* Just consumed the buffered input and produced some output. Otherwise 2128 it would result in "needs more input". Reset internal buffer. */ 2129 s.buffer_length = 0 2130 } else { 2131 /* Using input stream in last iteration. When decoder switches to input 2132 stream it has less than 8 bits in accumulator, so it is safe to 2133 return unused accumulator bits there. */ 2134 bitReaderUnload(br) 2135 2136 *available_in = br.input_len - br.byte_pos 2137 *next_in = br.input[br.byte_pos:] 2138 } 2139 2140 break 2141 } 2142 2143 switch s.state { 2144 /* Prepare to the first read. */ 2145 case stateUninited: 2146 if !warmupBitReader(br) { 2147 result = decoderNeedsMoreInput 2148 break 2149 } 2150 2151 /* Decode window size. */ 2152 result = decodeWindowBits(s, br) /* Reads 1..8 bits. */ 2153 if result != decoderSuccess { 2154 break 2155 } 2156 2157 if s.large_window { 2158 s.state = stateLargeWindowBits 2159 break 2160 } 2161 2162 s.state = stateInitialize 2163 2164 case stateLargeWindowBits: 2165 if !safeReadBits(br, 6, &s.window_bits) { 2166 result = decoderNeedsMoreInput 2167 break 2168 } 2169 2170 if s.window_bits < largeMinWbits || s.window_bits > largeMaxWbits { 2171 result = decoderErrorFormatWindowBits 2172 break 2173 } 2174 2175 s.state = stateInitialize 2176 fallthrough 2177 2178 /* Maximum distance, see section 9.1. of the spec. */ 2179 /* Fall through. */ 2180 case stateInitialize: 2181 s.max_backward_distance = (1 << s.window_bits) - windowGap 2182 2183 /* Allocate memory for both block_type_trees and block_len_trees. */ 2184 s.block_type_trees = make([]huffmanCode, (3 * (huffmanMaxSize258 + huffmanMaxSize26))) 2185 2186 if s.block_type_trees == nil { 2187 result = decoderErrorAllocBlockTypeTrees 2188 break 2189 } 2190 2191 s.block_len_trees = s.block_type_trees[3*huffmanMaxSize258:] 2192 2193 s.state = stateMetablockBegin 2194 fallthrough 2195 2196 /* Fall through. */ 2197 case stateMetablockBegin: 2198 decoderStateMetablockBegin(s) 2199 2200 s.state = stateMetablockHeader 2201 fallthrough 2202 2203 /* Fall through. */ 2204 case stateMetablockHeader: 2205 result = decodeMetaBlockLength(s, br) 2206 /* Reads 2 - 31 bits. */ 2207 if result != decoderSuccess { 2208 break 2209 } 2210 2211 if s.is_metadata != 0 || s.is_uncompressed != 0 { 2212 if !bitReaderJumpToByteBoundary(br) { 2213 result = decoderErrorFormatPadding1 2214 break 2215 } 2216 } 2217 2218 if s.is_metadata != 0 { 2219 s.state = stateMetadata 2220 break 2221 } 2222 2223 if s.meta_block_remaining_len == 0 { 2224 s.state = stateMetablockDone 2225 break 2226 } 2227 2228 calculateRingBufferSize(s) 2229 if s.is_uncompressed != 0 { 2230 s.state = stateUncompressed 2231 break 2232 } 2233 2234 s.loop_counter = 0 2235 s.state = stateHuffmanCode0 2236 2237 case stateUncompressed: 2238 result = copyUncompressedBlockToOutput(available_out, next_out, nil, s) 2239 if result == decoderSuccess { 2240 s.state = stateMetablockDone 2241 } 2242 2243 case stateMetadata: 2244 for ; s.meta_block_remaining_len > 0; s.meta_block_remaining_len-- { 2245 var bits uint32 2246 2247 /* Read one byte and ignore it. */ 2248 if !safeReadBits(br, 8, &bits) { 2249 result = decoderNeedsMoreInput 2250 break 2251 } 2252 } 2253 2254 if result == decoderSuccess { 2255 s.state = stateMetablockDone 2256 } 2257 2258 case stateHuffmanCode0: 2259 if s.loop_counter >= 3 { 2260 s.state = stateMetablockHeader2 2261 break 2262 } 2263 2264 /* Reads 1..11 bits. */ 2265 result = decodeVarLenUint8(s, br, &s.num_block_types[s.loop_counter]) 2266 2267 if result != decoderSuccess { 2268 break 2269 } 2270 2271 s.num_block_types[s.loop_counter]++ 2272 if s.num_block_types[s.loop_counter] < 2 { 2273 s.loop_counter++ 2274 break 2275 } 2276 2277 s.state = stateHuffmanCode1 2278 fallthrough 2279 2280 case stateHuffmanCode1: 2281 { 2282 var alphabet_size uint32 = s.num_block_types[s.loop_counter] + 2 2283 var tree_offset int = s.loop_counter * huffmanMaxSize258 2284 result = readHuffmanCode(alphabet_size, alphabet_size, s.block_type_trees[tree_offset:], nil, s) 2285 if result != decoderSuccess { 2286 break 2287 } 2288 s.state = stateHuffmanCode2 2289 } 2290 fallthrough 2291 2292 case stateHuffmanCode2: 2293 { 2294 var alphabet_size uint32 = numBlockLenSymbols 2295 var tree_offset int = s.loop_counter * huffmanMaxSize26 2296 result = readHuffmanCode(alphabet_size, alphabet_size, s.block_len_trees[tree_offset:], nil, s) 2297 if result != decoderSuccess { 2298 break 2299 } 2300 s.state = stateHuffmanCode3 2301 } 2302 fallthrough 2303 2304 case stateHuffmanCode3: 2305 var tree_offset int = s.loop_counter * huffmanMaxSize26 2306 if !safeReadBlockLength(s, &s.block_length[s.loop_counter], s.block_len_trees[tree_offset:], br) { 2307 result = decoderNeedsMoreInput 2308 break 2309 } 2310 2311 s.loop_counter++ 2312 s.state = stateHuffmanCode0 2313 2314 case stateMetablockHeader2: 2315 { 2316 var bits uint32 2317 if !safeReadBits(br, 6, &bits) { 2318 result = decoderNeedsMoreInput 2319 break 2320 } 2321 2322 s.distance_postfix_bits = bits & bitMask(2) 2323 bits >>= 2 2324 s.num_direct_distance_codes = numDistanceShortCodes + (bits << s.distance_postfix_bits) 2325 s.distance_postfix_mask = int(bitMask(s.distance_postfix_bits)) 2326 s.context_modes = make([]byte, uint(s.num_block_types[0])) 2327 if s.context_modes == nil { 2328 result = decoderErrorAllocContextModes 2329 break 2330 } 2331 2332 s.loop_counter = 0 2333 s.state = stateContextModes 2334 } 2335 fallthrough 2336 2337 case stateContextModes: 2338 result = readContextModes(s) 2339 2340 if result != decoderSuccess { 2341 break 2342 } 2343 2344 s.state = stateContextMap1 2345 fallthrough 2346 2347 case stateContextMap1: 2348 result = decodeContextMap(s.num_block_types[0]<<literalContextBits, &s.num_literal_htrees, &s.context_map, s) 2349 2350 if result != decoderSuccess { 2351 break 2352 } 2353 2354 detectTrivialLiteralBlockTypes(s) 2355 s.state = stateContextMap2 2356 fallthrough 2357 2358 case stateContextMap2: 2359 { 2360 var num_direct_codes uint32 = s.num_direct_distance_codes - numDistanceShortCodes 2361 var num_distance_codes uint32 2362 var max_distance_symbol uint32 2363 if s.large_window { 2364 num_distance_codes = uint32(distanceAlphabetSize(uint(s.distance_postfix_bits), uint(num_direct_codes), largeMaxDistanceBits)) 2365 max_distance_symbol = maxDistanceSymbol(num_direct_codes, s.distance_postfix_bits) 2366 } else { 2367 num_distance_codes = uint32(distanceAlphabetSize(uint(s.distance_postfix_bits), uint(num_direct_codes), maxDistanceBits)) 2368 max_distance_symbol = num_distance_codes 2369 } 2370 var allocation_success bool = true 2371 result = decodeContextMap(s.num_block_types[2]<<distanceContextBits, &s.num_dist_htrees, &s.dist_context_map, s) 2372 if result != decoderSuccess { 2373 break 2374 } 2375 2376 if !decoderHuffmanTreeGroupInit(s, &s.literal_hgroup, numLiteralSymbols, numLiteralSymbols, s.num_literal_htrees) { 2377 allocation_success = false 2378 } 2379 2380 if !decoderHuffmanTreeGroupInit(s, &s.insert_copy_hgroup, numCommandSymbols, numCommandSymbols, s.num_block_types[1]) { 2381 allocation_success = false 2382 } 2383 2384 if !decoderHuffmanTreeGroupInit(s, &s.distance_hgroup, num_distance_codes, max_distance_symbol, s.num_dist_htrees) { 2385 allocation_success = false 2386 } 2387 2388 if !allocation_success { 2389 return saveErrorCode(s, decoderErrorAllocTreeGroups) 2390 } 2391 2392 s.loop_counter = 0 2393 s.state = stateTreeGroup 2394 } 2395 fallthrough 2396 2397 case stateTreeGroup: 2398 var hgroup *huffmanTreeGroup = nil 2399 switch s.loop_counter { 2400 case 0: 2401 hgroup = &s.literal_hgroup 2402 case 1: 2403 hgroup = &s.insert_copy_hgroup 2404 case 2: 2405 hgroup = &s.distance_hgroup 2406 default: 2407 return saveErrorCode(s, decoderErrorUnreachable) 2408 } 2409 2410 result = huffmanTreeGroupDecode(hgroup, s) 2411 if result != decoderSuccess { 2412 break 2413 } 2414 s.loop_counter++ 2415 if s.loop_counter >= 3 { 2416 prepareLiteralDecoding(s) 2417 s.dist_context_map_slice = s.dist_context_map 2418 s.htree_command = []huffmanCode(s.insert_copy_hgroup.htrees[0]) 2419 if !ensureRingBuffer(s) { 2420 result = decoderErrorAllocRingBuffer2 2421 break 2422 } 2423 2424 s.state = stateCommandBegin 2425 } 2426 2427 case stateCommandBegin, stateCommandInner, stateCommandPostDecodeLiterals, stateCommandPostWrapCopy: 2428 result = processCommands(s) 2429 2430 if result == decoderNeedsMoreInput { 2431 result = safeProcessCommands(s) 2432 } 2433 2434 case stateCommandInnerWrite, stateCommandPostWrite1, stateCommandPostWrite2: 2435 result = writeRingBuffer(s, available_out, next_out, nil, false) 2436 2437 if result != decoderSuccess { 2438 break 2439 } 2440 2441 wrapRingBuffer(s) 2442 if s.ringbuffer_size == 1<<s.window_bits { 2443 s.max_distance = s.max_backward_distance 2444 } 2445 2446 if s.state == stateCommandPostWrite1 { 2447 if s.meta_block_remaining_len == 0 { 2448 /* Next metablock, if any. */ 2449 s.state = stateMetablockDone 2450 } else { 2451 s.state = stateCommandBegin 2452 } 2453 } else if s.state == stateCommandPostWrite2 { 2454 s.state = stateCommandPostWrapCopy /* BROTLI_STATE_COMMAND_INNER_WRITE */ 2455 } else { 2456 if s.loop_counter == 0 { 2457 if s.meta_block_remaining_len == 0 { 2458 s.state = stateMetablockDone 2459 } else { 2460 s.state = stateCommandPostDecodeLiterals 2461 } 2462 2463 break 2464 } 2465 2466 s.state = stateCommandInner 2467 } 2468 2469 case stateMetablockDone: 2470 if s.meta_block_remaining_len < 0 { 2471 result = decoderErrorFormatBlockLength2 2472 break 2473 } 2474 2475 decoderStateCleanupAfterMetablock(s) 2476 if s.is_last_metablock == 0 { 2477 s.state = stateMetablockBegin 2478 break 2479 } 2480 2481 if !bitReaderJumpToByteBoundary(br) { 2482 result = decoderErrorFormatPadding2 2483 break 2484 } 2485 2486 if s.buffer_length == 0 { 2487 bitReaderUnload(br) 2488 *available_in = br.input_len - br.byte_pos 2489 *next_in = br.input[br.byte_pos:] 2490 } 2491 2492 s.state = stateDone 2493 fallthrough 2494 2495 case stateDone: 2496 if s.ringbuffer != nil { 2497 result = writeRingBuffer(s, available_out, next_out, nil, true) 2498 if result != decoderSuccess { 2499 break 2500 } 2501 } 2502 2503 return saveErrorCode(s, result) 2504 } 2505 } 2506 2507 return saveErrorCode(s, result) 2508} 2509 2510func decoderHasMoreOutput(s *Reader) bool { 2511 /* After unrecoverable error remaining output is considered nonsensical. */ 2512 if int(s.error_code) < 0 { 2513 return false 2514 } 2515 2516 return s.ringbuffer != nil && unwrittenBytes(s, false) != 0 2517} 2518 2519func decoderGetErrorCode(s *Reader) int { 2520 return int(s.error_code) 2521} 2522 2523func decoderErrorString(c int) string { 2524 switch c { 2525 case decoderNoError: 2526 return "NO_ERROR" 2527 case decoderSuccess: 2528 return "SUCCESS" 2529 case decoderNeedsMoreInput: 2530 return "NEEDS_MORE_INPUT" 2531 case decoderNeedsMoreOutput: 2532 return "NEEDS_MORE_OUTPUT" 2533 case decoderErrorFormatExuberantNibble: 2534 return "EXUBERANT_NIBBLE" 2535 case decoderErrorFormatReserved: 2536 return "RESERVED" 2537 case decoderErrorFormatExuberantMetaNibble: 2538 return "EXUBERANT_META_NIBBLE" 2539 case decoderErrorFormatSimpleHuffmanAlphabet: 2540 return "SIMPLE_HUFFMAN_ALPHABET" 2541 case decoderErrorFormatSimpleHuffmanSame: 2542 return "SIMPLE_HUFFMAN_SAME" 2543 case decoderErrorFormatClSpace: 2544 return "CL_SPACE" 2545 case decoderErrorFormatHuffmanSpace: 2546 return "HUFFMAN_SPACE" 2547 case decoderErrorFormatContextMapRepeat: 2548 return "CONTEXT_MAP_REPEAT" 2549 case decoderErrorFormatBlockLength1: 2550 return "BLOCK_LENGTH_1" 2551 case decoderErrorFormatBlockLength2: 2552 return "BLOCK_LENGTH_2" 2553 case decoderErrorFormatTransform: 2554 return "TRANSFORM" 2555 case decoderErrorFormatDictionary: 2556 return "DICTIONARY" 2557 case decoderErrorFormatWindowBits: 2558 return "WINDOW_BITS" 2559 case decoderErrorFormatPadding1: 2560 return "PADDING_1" 2561 case decoderErrorFormatPadding2: 2562 return "PADDING_2" 2563 case decoderErrorFormatDistance: 2564 return "DISTANCE" 2565 case decoderErrorDictionaryNotSet: 2566 return "DICTIONARY_NOT_SET" 2567 case decoderErrorInvalidArguments: 2568 return "INVALID_ARGUMENTS" 2569 case decoderErrorAllocContextModes: 2570 return "CONTEXT_MODES" 2571 case decoderErrorAllocTreeGroups: 2572 return "TREE_GROUPS" 2573 case decoderErrorAllocContextMap: 2574 return "CONTEXT_MAP" 2575 case decoderErrorAllocRingBuffer1: 2576 return "RING_BUFFER_1" 2577 case decoderErrorAllocRingBuffer2: 2578 return "RING_BUFFER_2" 2579 case decoderErrorAllocBlockTypeTrees: 2580 return "BLOCK_TYPE_TREES" 2581 case decoderErrorUnreachable: 2582 return "UNREACHABLE" 2583 default: 2584 return "INVALID" 2585 } 2586} 2587