21#ifndef OF_INFLATE64_STREAM_M
22# import "OFInflateStream.h"
24# import "OFInflate64Stream.h"
25# define OFInflateStream OFInflate64Stream
27#import "OFHuffmanTree.h"
29#import "OFInitializationFailedException.h"
30#import "OFInvalidFormatException.h"
31#import "OFNotOpenException.h"
32#import "OFOutOfMemoryException.h"
34#ifndef OF_INFLATE64_STREAM_M
35# define bufferSize OFInflateStreamBufferSize
37# define bufferSize OFInflate64StreamBufferSize
42 stateUncompressedBlockHeader,
43 stateUncompressedBlock,
49 huffmanStateWriteValue,
50 huffmanStateAwaitCode,
51 huffmanStateAwaitLengthExtraBits,
52 huffmanStateAwaitDistance,
53 huffmanStateAwaitDistanceExtraBits,
54 huffmanStateProcessPair
57#ifndef OF_INFLATE64_STREAM_M
58static const uint8_t numDistanceCodes = 30;
59static const uint8_t lengthCodes[29] = {
61 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
62 64, 80, 96, 112, 128, 160, 192, 224, 255
64static const uint8_t lengthExtraBits[29] = {
65 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4,
68static const uint16_t distanceCodes[30] = {
69 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385,
70 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
72static const uint8_t distanceExtraBits[30] = {
73 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10,
74 10, 11, 11, 12, 12, 13, 13
77static const uint8_t numDistanceCodes = 32;
78static const uint8_t lengthCodes[29] = {
80 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
81 64, 80, 96, 112, 128, 160, 192, 224, 0
83static const uint8_t lengthExtraBits[29] = {
84 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4,
87static const uint16_t distanceCodes[32] = {
88 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385,
89 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577,
92static const uint8_t distanceExtraBits[32] = {
93 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10,
94 10, 11, 11, 12, 12, 13, 13, 14, 14
97static const uint8_t codeLengthsOrder[19] = {
98 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
100static OFHuffmanTree fixedLitLenTree, fixedDistTree;
108 uint16_t ret = stream->_savedBits;
110 OFAssert(stream->_savedBitsLength < count);
112 for (uint_fast8_t i = stream->_savedBitsLength; i < count; i++) {
113 if OF_UNLIKELY (stream->_bitIndex == 8) {
114 if OF_LIKELY (stream->_bufferIndex <
115 stream->_bufferLength)
117 stream->_buffer[stream->_bufferIndex++];
119 size_t length = [stream->_stream
123 if OF_UNLIKELY (length < 1) {
124 stream->_savedBits = ret;
125 stream->_savedBitsLength = i;
129 stream->_byte = stream->_buffer[0];
130 stream->_bufferIndex = 1;
131 stream->_bufferLength = (uint16_t)length;
134 stream->_bitIndex = 0;
137 ret |= ((stream->_byte >> stream->_bitIndex++) & 1) << i;
140 stream->_savedBits = 0;
141 stream->_savedBitsLength = 0;
149 uint8_t lengths[288];
154 for (uint16_t i = 0; i <= 143; i++)
156 for (uint16_t i = 144; i <= 255; i++)
158 for (uint16_t i = 256; i <= 279; i++)
160 for (uint16_t i = 280; i <= 287; i++)
163 fixedLitLenTree = OFHuffmanTreeNew(lengths, 288);
165 for (uint16_t i = 0; i <= 31; i++)
168 fixedDistTree = OFHuffmanTreeNew(lengths, 32);
171+ (instancetype)streamWithStream: (
OFStream *)stream
173 return [[[
self alloc] initWithStream: stream] autorelease];
178 OF_INVALID_INIT_METHOD
181- (instancetype)initWithStream: (
OFStream *)stream
186 _stream = [stream
retain];
191#ifdef OF_INFLATE64_STREAM_M
192 _slidingWindowMask = 0xFFFF;
194 _slidingWindowMask = 0x7FFF;
212 if (_state == stateHuffmanTree) {
215 if (_context.huffmanTree.codeLenTree != NULL)
216 OFHuffmanTreeFree(_context.huffmanTree.codeLenTree);
219 if (_state == stateHuffmanTree || _state == stateHuffmanBlock) {
220 if (_context.huffman.litLenTree != fixedLitLenTree)
221 OFHuffmanTreeFree(_context.huffman.litLenTree);
222 if (_context.huffman.distTree != fixedDistTree)
223 OFHuffmanTreeFree(_context.huffman.distTree);
229- (size_t)lowlevelReadIntoBuffer: (
void *)buffer_
230 length: (
size_t)length
232 unsigned char *buffer = buffer_;
233 uint16_t bits = 0, tmp, value = 0;
234 size_t bytesWritten = 0;
235 unsigned char *slidingWindow;
236 uint16_t slidingWindowIndex;
245 switch ((
enum State)_state) {
246 case stateBlockHeader:
247 if OF_UNLIKELY (_inLastBlock) {
248 [_stream unreadFromBuffer: _buffer + _bufferIndex
249 length: _bufferLength -
251 _bufferIndex = _bufferLength = 0;
253 _atEndOfStream =
true;
257 if OF_UNLIKELY (!tryReadBits(
self, &bits, 3))
260 _inLastBlock = (bits & 1);
264 _state = stateUncompressedBlockHeader;
266 _context.uncompressedHeader.position = 0;
267 memset(_context.uncompressedHeader.length, 0, 4);
270 _state = stateHuffmanBlock;
271 _context.huffman.state = huffmanStateAwaitCode;
272 _context.huffman.litLenTree = fixedLitLenTree;
273 _context.huffman.distTree = fixedDistTree;
274 _context.huffman.treeIter = fixedLitLenTree;
277 _state = stateHuffmanTree;
278 _context.huffmanTree.lengths = NULL;
279 _context.huffmanTree.receivedCount = 0;
280 _context.huffmanTree.value = 0xFE;
281 _context.huffmanTree.litLenCodesCount = 0xFF;
282 _context.huffmanTree.distCodesCount = 0xFF;
283 _context.huffmanTree.codeLenCodesCount = 0xFF;
290 case stateUncompressedBlockHeader:
291#define CTX _context.uncompressedHeader
293 [_stream unreadFromBuffer: _buffer + _bufferIndex
294 length: _bufferLength - _bufferIndex];
295 _bufferIndex = _bufferLength = 0;
297 CTX.position += [_stream
298 readIntoBuffer: CTX.length + CTX.position
299 length: 4 - CTX.position];
301 if OF_UNLIKELY (CTX.position < 4)
304 if OF_UNLIKELY ((CTX.length[0] | (CTX.length[1] << 8)) !=
305 (uint16_t)~(CTX.length[2] | (CTX.length[3] << 8)))
308 _state = stateUncompressedBlock;
314 _context.uncompressed.length =
315 CTX.length[0] | (CTX.length[1] << 8);
316 _context.uncompressed.position = 0;
320 case stateUncompressedBlock:
321#define CTX _context.uncompressed
322 if OF_UNLIKELY (length == 0)
325 tmp = (length < (
size_t)CTX.length - CTX.position
326 ? (uint16_t)length : CTX.length - CTX.position);
328 tmp = (uint16_t)[_stream readIntoBuffer: buffer + bytesWritten
331 slidingWindow = _slidingWindow;
332 slidingWindowIndex = _slidingWindowIndex;
333 for (uint_fast16_t i = 0; i < tmp; i++) {
334 slidingWindow[slidingWindowIndex] =
335 buffer[bytesWritten + i];
336 slidingWindowIndex = (slidingWindowIndex + 1) &
339 _slidingWindowIndex = slidingWindowIndex;
345 if OF_UNLIKELY (CTX.position == CTX.length)
346 _state = stateBlockHeader;
350 case stateHuffmanTree:
351#define CTX _context.huffmanTree
352 if OF_LIKELY (CTX.value == 0xFE) {
353 if OF_LIKELY (CTX.litLenCodesCount == 0xFF) {
354 if OF_UNLIKELY (!tryReadBits(
self, &bits, 5))
357 if OF_UNLIKELY (bits > 29)
361 CTX.litLenCodesCount = bits;
364 if OF_LIKELY (CTX.distCodesCount == 0xFF) {
365 if OF_UNLIKELY (!tryReadBits(
self, &bits, 5))
368 CTX.distCodesCount = bits;
371 if OF_LIKELY (CTX.codeLenCodesCount == 0xFF) {
372 if OF_UNLIKELY (!tryReadBits(
self, &bits, 4))
375 CTX.codeLenCodesCount = bits;
378 if OF_LIKELY (CTX.lengths == NULL)
381 for (uint16_t i = CTX.receivedCount;
382 i < CTX.codeLenCodesCount + 4; i++) {
383 if OF_UNLIKELY (!tryReadBits(
self, &bits, 3)) {
384 CTX.receivedCount = i;
388 CTX.lengths[codeLengthsOrder[i]] = bits;
391 CTX.codeLenTree = OFHuffmanTreeNew(CTX.lengths, 19);
392 CTX.treeIter = CTX.codeLenTree;
396 CTX.receivedCount = 0;
400 if OF_LIKELY (CTX.lengths == NULL)
402 CTX.litLenCodesCount + CTX.distCodesCount + 258, 1);
404 for (uint16_t i = CTX.receivedCount;
405 i < CTX.litLenCodesCount + CTX.distCodesCount + 258;) {
408 if OF_LIKELY (CTX.value == 0xFF) {
409 if OF_UNLIKELY (!OFHuffmanTreeWalk(
self,
410 tryReadBits, &CTX.treeIter, &value)) {
411 CTX.receivedCount = i;
415 CTX.treeIter = CTX.codeLenTree;
418 CTX.lengths[i++] = value;
426 if OF_UNLIKELY (i < 1)
430 if OF_UNLIKELY (!tryReadBits(
self, &bits, 2)) {
431 CTX.receivedCount = i;
436 value = CTX.lengths[i - 1];
441 if OF_UNLIKELY (!tryReadBits(
self, &bits, 3)) {
442 CTX.receivedCount = i;
452 if OF_UNLIKELY (!tryReadBits(
self, &bits, 7)) {
453 CTX.receivedCount = i;
466 if OF_UNLIKELY (i + count >
467 CTX.litLenCodesCount + CTX.distCodesCount + 258)
470 for (j = 0; j < count; j++)
471 CTX.lengths[i++] = value;
476 OFHuffmanTreeFree(CTX.codeLenTree);
477 CTX.codeLenTree = NULL;
479 CTX.litLenTree = OFHuffmanTreeNew(CTX.lengths,
480 CTX.litLenCodesCount + 257);
481 CTX.distTree = OFHuffmanTreeNew(
482 CTX.lengths + CTX.litLenCodesCount + 257,
483 CTX.distCodesCount + 1);
492 _state = stateHuffmanBlock;
493 _context.huffman.state = huffmanStateAwaitCode;
494 _context.huffman.treeIter = CTX.litLenTree;
498 case stateHuffmanBlock:
499#define CTX _context.huffman
501 uint8_t extraBits, lengthCodeIndex;
503 if OF_UNLIKELY (CTX.state == huffmanStateWriteValue) {
504 if OF_UNLIKELY (length == 0)
507 buffer[bytesWritten++] = CTX.value;
510 _slidingWindow[_slidingWindowIndex] = CTX.value;
511 _slidingWindowIndex =
512 (_slidingWindowIndex + 1) &
515 CTX.state = huffmanStateAwaitCode;
516 CTX.treeIter = CTX.litLenTree;
519 if OF_UNLIKELY (CTX.state ==
520 huffmanStateAwaitLengthExtraBits) {
521 if OF_UNLIKELY (!tryReadBits(
self, &bits,
527 CTX.state = huffmanStateAwaitDistance;
528 CTX.treeIter = CTX.distTree;
532 if (CTX.state == huffmanStateAwaitDistance) {
533 if OF_UNLIKELY (!OFHuffmanTreeWalk(
self,
534 tryReadBits, &CTX.treeIter, &value))
537 if OF_UNLIKELY (value >= numDistanceCodes)
541 CTX.distance = distanceCodes[value];
542 extraBits = distanceExtraBits[value];
545 if OF_UNLIKELY (!tryReadBits(
self,
547#define HSADEB huffmanStateAwaitDistanceExtraBits
550 CTX.extraBits = extraBits;
554 CTX.distance += bits;
557 CTX.state = huffmanStateProcessPair;
558 }
else if (CTX.state ==
559 huffmanStateAwaitDistanceExtraBits) {
560 if OF_UNLIKELY (!tryReadBits(
self, &bits,
564 CTX.distance += bits;
566 CTX.state = huffmanStateProcessPair;
570 if (CTX.state == huffmanStateProcessPair) {
571 for (uint_fast16_t j = 0; j < CTX.length; j++) {
574 if OF_UNLIKELY (length == 0) {
579 idx = (_slidingWindowIndex -
580 CTX.distance) & _slidingWindowMask;
581 value = _slidingWindow[idx];
583 buffer[bytesWritten++] = value;
586 _slidingWindow[_slidingWindowIndex] =
588 _slidingWindowIndex =
589 (_slidingWindowIndex + 1) &
593 CTX.state = huffmanStateAwaitCode;
594 CTX.treeIter = CTX.litLenTree;
597 if OF_UNLIKELY (!OFHuffmanTreeWalk(
self, tryReadBits,
598 &CTX.treeIter, &value))
602 if OF_UNLIKELY (value == 256) {
603 if (CTX.litLenTree != fixedLitLenTree)
604 OFHuffmanTreeFree(CTX.litLenTree);
605 if (CTX.distTree != fixedDistTree)
606 OFHuffmanTreeFree(CTX.distTree);
608 _state = stateBlockHeader;
613 if OF_LIKELY (value < 256) {
614 if OF_UNLIKELY (length == 0) {
615 CTX.state = huffmanStateWriteValue;
620 buffer[bytesWritten++] = value;
623 _slidingWindow[_slidingWindowIndex] = value;
624 _slidingWindowIndex =
625 (_slidingWindowIndex + 1) &
628 CTX.treeIter = CTX.litLenTree;
632 if OF_UNLIKELY (value > 285)
636 lengthCodeIndex = value - 257;
637 CTX.length = lengthCodes[lengthCodeIndex] + 3;
638 extraBits = lengthExtraBits[lengthCodeIndex];
641 if OF_UNLIKELY (!tryReadBits(
self, &bits,
643 CTX.extraBits = extraBits;
645 huffmanStateAwaitLengthExtraBits;
652 CTX.treeIter = CTX.distTree;
653 CTX.state = huffmanStateAwaitDistance;
668 return _atEndOfStream;
673 return ((id <OFReadyForReadingObserving>)_stream)
674 .fileDescriptorForReading;
680 _bufferLength - _bufferIndex > 0);
689 [_stream unreadFromBuffer: _buffer + _bufferIndex
690 length: _bufferLength - _bufferIndex];
691 _bufferIndex = _bufferLength = 0;
void * OFAllocMemory(size_t count, size_t size)
Allocates memory for the specified number of items of the specified size.
Definition OFObject.m:101
void OFFreeMemory(void *pointer)
Frees memory allocated by OFAllocMemory, OFAllocZeroedMemory or OFResizeMemory.
Definition OFObject.m:156
void * OFAllocZeroedMemory(size_t count, size_t size)
Allocates memory for the specified number of items of the specified size and initializes it with zero...
Definition OFObject.m:119
#define nil
A value representing no object.
Definition ObjFWRT.h:64
instancetype exception()
Creates a new, autoreleased exception.
Definition OFException.m:279
A class that handles Deflate decompression transparently for an underlying stream.
Definition OFInflateStream.h:35
OFStream * underlyingStream
The underlying stream of the inflate stream.
Definition OFInflateStream.h:80
An exception indicating an object is not open, connected or bound.
Definition OFNotOpenException.h:26
instancetype exceptionWithObject:(id object)
Creates a new, autoreleased not open exception.
Definition OFNotOpenException.m:29
instancetype init()
Initializes an already allocated object.
Definition OFObject.m:586
void dealloc()
Deallocates the object.
Definition OFObject.m:1229
void initialize()
A method which is called the moment before the first call to the class is being made.
Definition OFObject.m:434
A base class for different types of streams.
Definition OFStream.h:188
size_t readIntoBuffer:length:(void *buffer,[length] size_t length)
Reads at most length bytes from the stream into a buffer.
Definition OFStream.m:127
bool lowlevelIsAtEndOfStream()
Returns whether the lowlevel is at the end of the stream.
Definition OFStream.m:99
void close()
Closes the stream.
Definition OFStream.m:1298
bool hasDataInReadBuffer
Whether data is present in the internal read buffer.
Definition OFStream.h:214
instancetype retain()
Increases the retain count.
int fileDescriptorForReading
The file descriptor for reading that should be checked by the OFKernelEventObserver.
Definition OFKernelEventObserver.h:89