35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
-
+
-
-
-
-
-
-
-
+
+
+
+
+
+
+
|
#ifndef OF_INFLATE64_STREAM_M
# define bufferSize OFInflateStreamBufferSize
#else
# define bufferSize OFInflate64StreamBufferSize
#endif
enum state {
enum State {
StateBlockHeader,
StateUncompressedBlockHeader,
StateUncompressedBlock,
StateHuffmanTree,
StateHuffmanBlock
};
enum huffman_state {
WRITE_VALUE,
AWAIT_CODE,
AWAIT_LENGTH_EXTRA_BITS,
AWAIT_DISTANCE,
AWAIT_DISTANCE_EXTRA_BITS,
PROCESS_PAIR
enum HuffmanState {
HuffmanStateWriteValue,
HuffmanStateAwaitCode,
HuffmanStateAwaitLengthExtraBits,
HuffmanStateAwaitDistance,
HuffmanStateAwaitDistanceExtraBits,
HuffmanStateProcessPair
};
#ifndef OF_INFLATE64_STREAM_M
static const uint8_t numDistanceCodes = 30;
static const uint8_t lengthCodes[29] = {
/* indices are -257, values -3 */
0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
|
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
|
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
|
-
+
|
if (_stream == nil)
@throw [OFNotOpenException exceptionWithObject: self];
if (_atEndOfStream)
return 0;
start:
switch ((enum state)_state) {
switch ((enum State)_state) {
case StateBlockHeader:
if OF_UNLIKELY (_inLastBlock) {
[_stream unreadFromBuffer: _buffer + _bufferIndex
length: _bufferLength -
_bufferIndex];
_bufferIndex = _bufferLength = 0;
|
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
|
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
|
-
+
|
_state = StateUncompressedBlockHeader;
_bitIndex = 8;
_context.uncompressedHeader.position = 0;
memset(_context.uncompressedHeader.length, 0, 4);
break;
case 1: /* Fixed Huffman */
_state = StateHuffmanBlock;
_context.huffman.state = AWAIT_CODE;
_context.huffman.state = HuffmanStateAwaitCode;
_context.huffman.litLenTree = fixedLitLenTree;
_context.huffman.distTree = fixedDistTree;
_context.huffman.treeIter = fixedLitLenTree;
break;
case 2: /* Dynamic Huffman */
_state = StateHuffmanTree;
_context.huffmanTree.lengths = NULL;
|
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
|
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
|
-
+
-
+
-
+
-
+
+
-
+
-
+
+
-
+
-
+
-
-
+
+
+
-
+
-
+
|
/*
* litLenTree and distTree are at the same location in
* _context.huffman and _context.huffmanTree, thus no need to
* set them.
*/
_state = StateHuffmanBlock;
_context.huffman.state = AWAIT_CODE;
_context.huffman.state = HuffmanStateAwaitCode;
_context.huffman.treeIter = CTX.litLenTree;
goto start;
#undef CTX
case StateHuffmanBlock:
#define CTX _context.huffman
for (;;) {
uint8_t extraBits, lengthCodeIndex;
if OF_UNLIKELY (CTX.state == WRITE_VALUE) {
if OF_UNLIKELY (CTX.state == HuffmanStateWriteValue) {
if OF_UNLIKELY (length == 0)
return bytesWritten;
buffer[bytesWritten++] = CTX.value;
length--;
_slidingWindow[_slidingWindowIndex] = CTX.value;
_slidingWindowIndex =
(_slidingWindowIndex + 1) &
_slidingWindowMask;
CTX.state = AWAIT_CODE;
CTX.state = HuffmanStateAwaitCode;
CTX.treeIter = CTX.litLenTree;
}
if OF_UNLIKELY (CTX.state == AWAIT_LENGTH_EXTRA_BITS) {
if OF_UNLIKELY (CTX.state ==
HuffmanStateAwaitLengthExtraBits) {
if OF_UNLIKELY (!tryReadBits(self, &bits,
CTX.extraBits))
return bytesWritten;
CTX.length += bits;
CTX.state = AWAIT_DISTANCE;
CTX.state = HuffmanStateAwaitDistance;
CTX.treeIter = CTX.distTree;
}
/* Distance of length distance pair */
if (CTX.state == AWAIT_DISTANCE) {
if (CTX.state == HuffmanStateAwaitDistance) {
if OF_UNLIKELY (!OFHuffmanTreeWalk(self,
tryReadBits, &CTX.treeIter, &value))
return bytesWritten;
if OF_UNLIKELY (value >= numDistanceCodes)
@throw [OFInvalidFormatException
exception];
CTX.distance = distanceCodes[value];
extraBits = distanceExtraBits[value];
if (extraBits > 0) {
if OF_UNLIKELY (!tryReadBits(self,
&bits, extraBits)) {
#define HSADEB HuffmanStateAwaitDistanceExtraBits
CTX.state =
CTX.state = HSADEB;
AWAIT_DISTANCE_EXTRA_BITS;
CTX.state = PROCESS_PAIR;
} else if (CTX.state == AWAIT_DISTANCE_EXTRA_BITS) {
CTX.state = HuffmanStateProcessPair;
} else if (CTX.state ==
HuffmanStateAwaitDistanceExtraBits) {
if OF_UNLIKELY (!tryReadBits(self, &bits,
CTX.extraBits))
return bytesWritten;
CTX.distance += bits;
CTX.state = PROCESS_PAIR;
CTX.state = HuffmanStateProcessPair;
}
/* Length distance pair */
if (CTX.state == PROCESS_PAIR) {
if (CTX.state == HuffmanStateProcessPair) {
for (uint_fast16_t j = 0; j < CTX.length; j++) {
uint16_t idx;
if OF_UNLIKELY (length == 0) {
CTX.length -= j;
return bytesWritten;
}
|
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
|
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
|
-
+
|
_slidingWindow[_slidingWindowIndex] =
value;
_slidingWindowIndex =
(_slidingWindowIndex + 1) &
_slidingWindowMask;
}
CTX.state = AWAIT_CODE;
CTX.state = HuffmanStateAwaitCode;
CTX.treeIter = CTX.litLenTree;
}
if OF_UNLIKELY (!OFHuffmanTreeWalk(self, tryReadBits,
&CTX.treeIter, &value))
return bytesWritten;
|
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
|
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
|
-
+
|
_state = StateBlockHeader;
goto start;
}
/* Literal byte */
if OF_LIKELY (value < 256) {
if OF_UNLIKELY (length == 0) {
CTX.state = WRITE_VALUE;
CTX.state = HuffmanStateWriteValue;
CTX.value = value;
return bytesWritten;
}
buffer[bytesWritten++] = value;
length--;
|
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
|
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
|
-
+
+
-
+
|
CTX.length = lengthCodes[lengthCodeIndex] + 3;
extraBits = lengthExtraBits[lengthCodeIndex];
if (extraBits > 0) {
if OF_UNLIKELY (!tryReadBits(self, &bits,
extraBits)) {
CTX.extraBits = extraBits;
CTX.state = AWAIT_LENGTH_EXTRA_BITS;
CTX.state =
HuffmanStateAwaitLengthExtraBits;
return bytesWritten;
}
CTX.length += bits;
}
CTX.treeIter = CTX.distTree;
CTX.state = AWAIT_DISTANCE;
CTX.state = HuffmanStateAwaitDistance;
}
break;
#undef CTX
}
OF_UNREACHABLE
|