source: code/trunk/vendor/github.com/andybalholm/brotli/decode.go@ 145

Last change on this file since 145 was 145, checked in by Izuru Yakumo, 22 months ago

Updated the Makefile and vendored depedencies

Signed-off-by: Izuru Yakumo <yakumo.izuru@…>
File size: 67.4 KB
Line 
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), &copy_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}
Note: See TracBrowser for help on using the repository browser.