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 if OF_UNLIKELY (tmp == 0)
334 slidingWindow = _slidingWindow;
335 slidingWindowIndex = _slidingWindowIndex;
336 for (uint_fast16_t i = 0; i < tmp; i++) {
337 slidingWindow[slidingWindowIndex] =
338 buffer[bytesWritten + i];
339 slidingWindowIndex = (slidingWindowIndex + 1) &
342 _slidingWindowIndex = slidingWindowIndex;
348 if OF_UNLIKELY (CTX.position == CTX.length)
349 _state = stateBlockHeader;
353 case stateHuffmanTree:
354#define CTX _context.huffmanTree
355 if OF_LIKELY (CTX.value == 0xFE) {
356 if OF_LIKELY (CTX.litLenCodesCount == 0xFF) {
357 if OF_UNLIKELY (!tryReadBits(
self, &bits, 5))
360 if OF_UNLIKELY (bits > 29)
364 CTX.litLenCodesCount = bits;
367 if OF_LIKELY (CTX.distCodesCount == 0xFF) {
368 if OF_UNLIKELY (!tryReadBits(
self, &bits, 5))
371 CTX.distCodesCount = bits;
374 if OF_LIKELY (CTX.codeLenCodesCount == 0xFF) {
375 if OF_UNLIKELY (!tryReadBits(
self, &bits, 4))
378 CTX.codeLenCodesCount = bits;
381 if OF_LIKELY (CTX.lengths == NULL)
384 for (uint16_t i = CTX.receivedCount;
385 i < CTX.codeLenCodesCount + 4; i++) {
386 if OF_UNLIKELY (!tryReadBits(
self, &bits, 3)) {
387 CTX.receivedCount = i;
391 CTX.lengths[codeLengthsOrder[i]] = bits;
394 CTX.codeLenTree = OFHuffmanTreeNew(CTX.lengths, 19);
395 CTX.treeIter = CTX.codeLenTree;
399 CTX.receivedCount = 0;
403 if OF_LIKELY (CTX.lengths == NULL)
405 CTX.litLenCodesCount + CTX.distCodesCount + 258, 1);
407 for (uint16_t i = CTX.receivedCount;
408 i < CTX.litLenCodesCount + CTX.distCodesCount + 258;) {
411 if OF_LIKELY (CTX.value == 0xFF) {
412 if OF_UNLIKELY (!OFHuffmanTreeWalk(
self,
413 tryReadBits, &CTX.treeIter, &value)) {
414 CTX.receivedCount = i;
418 CTX.treeIter = CTX.codeLenTree;
421 CTX.lengths[i++] = value;
429 if OF_UNLIKELY (i < 1)
433 if OF_UNLIKELY (!tryReadBits(
self, &bits, 2)) {
434 CTX.receivedCount = i;
439 value = CTX.lengths[i - 1];
444 if OF_UNLIKELY (!tryReadBits(
self, &bits, 3)) {
445 CTX.receivedCount = i;
455 if OF_UNLIKELY (!tryReadBits(
self, &bits, 7)) {
456 CTX.receivedCount = i;
469 if OF_UNLIKELY (i + count >
470 CTX.litLenCodesCount + CTX.distCodesCount + 258)
473 for (j = 0; j < count; j++)
474 CTX.lengths[i++] = value;
479 OFHuffmanTreeFree(CTX.codeLenTree);
480 CTX.codeLenTree = NULL;
482 CTX.litLenTree = OFHuffmanTreeNew(CTX.lengths,
483 CTX.litLenCodesCount + 257);
484 CTX.distTree = OFHuffmanTreeNew(
485 CTX.lengths + CTX.litLenCodesCount + 257,
486 CTX.distCodesCount + 1);
495 _state = stateHuffmanBlock;
496 _context.huffman.state = huffmanStateAwaitCode;
497 _context.huffman.treeIter = CTX.litLenTree;
501 case stateHuffmanBlock:
502#define CTX _context.huffman
504 uint8_t extraBits, lengthCodeIndex;
506 if OF_UNLIKELY (CTX.state == huffmanStateWriteValue) {
507 if OF_UNLIKELY (length == 0)
510 buffer[bytesWritten++] = CTX.value;
513 _slidingWindow[_slidingWindowIndex] = CTX.value;
514 _slidingWindowIndex =
515 (_slidingWindowIndex + 1) &
518 CTX.state = huffmanStateAwaitCode;
519 CTX.treeIter = CTX.litLenTree;
522 if OF_UNLIKELY (CTX.state ==
523 huffmanStateAwaitLengthExtraBits) {
524 if OF_UNLIKELY (!tryReadBits(
self, &bits,
530 CTX.state = huffmanStateAwaitDistance;
531 CTX.treeIter = CTX.distTree;
535 if (CTX.state == huffmanStateAwaitDistance) {
536 if OF_UNLIKELY (!OFHuffmanTreeWalk(
self,
537 tryReadBits, &CTX.treeIter, &value))
540 if OF_UNLIKELY (value >= numDistanceCodes)
544 CTX.distance = distanceCodes[value];
545 extraBits = distanceExtraBits[value];
548 if OF_UNLIKELY (!tryReadBits(
self,
550#define HSADEB huffmanStateAwaitDistanceExtraBits
553 CTX.extraBits = extraBits;
557 CTX.distance += bits;
560 CTX.state = huffmanStateProcessPair;
561 }
else if (CTX.state ==
562 huffmanStateAwaitDistanceExtraBits) {
563 if OF_UNLIKELY (!tryReadBits(
self, &bits,
567 CTX.distance += bits;
569 CTX.state = huffmanStateProcessPair;
573 if (CTX.state == huffmanStateProcessPair) {
574 for (uint_fast16_t j = 0; j < CTX.length; j++) {
577 if OF_UNLIKELY (length == 0) {
582 idx = (_slidingWindowIndex -
583 CTX.distance) & _slidingWindowMask;
584 value = _slidingWindow[idx];
586 buffer[bytesWritten++] = value;
589 _slidingWindow[_slidingWindowIndex] =
591 _slidingWindowIndex =
592 (_slidingWindowIndex + 1) &
596 CTX.state = huffmanStateAwaitCode;
597 CTX.treeIter = CTX.litLenTree;
600 if OF_UNLIKELY (!OFHuffmanTreeWalk(
self, tryReadBits,
601 &CTX.treeIter, &value))
605 if OF_UNLIKELY (value == 256) {
606 if (CTX.litLenTree != fixedLitLenTree)
607 OFHuffmanTreeFree(CTX.litLenTree);
608 if (CTX.distTree != fixedDistTree)
609 OFHuffmanTreeFree(CTX.distTree);
611 _state = stateBlockHeader;
616 if OF_LIKELY (value < 256) {
617 if OF_UNLIKELY (length == 0) {
618 CTX.state = huffmanStateWriteValue;
623 buffer[bytesWritten++] = value;
626 _slidingWindow[_slidingWindowIndex] = value;
627 _slidingWindowIndex =
628 (_slidingWindowIndex + 1) &
631 CTX.treeIter = CTX.litLenTree;
635 if OF_UNLIKELY (value > 285)
639 lengthCodeIndex = value - 257;
640 CTX.length = lengthCodes[lengthCodeIndex] + 3;
641 extraBits = lengthExtraBits[lengthCodeIndex];
644 if OF_UNLIKELY (!tryReadBits(
self, &bits,
646 CTX.extraBits = extraBits;
648 huffmanStateAwaitLengthExtraBits;
655 CTX.treeIter = CTX.distTree;
656 CTX.state = huffmanStateAwaitDistance;
671 return _atEndOfStream;
676 return ((id <OFReadyForReadingObserving>)_stream)
677 .fileDescriptorForReading;
683 _bufferLength - _bufferIndex > 0);
692 [_stream unreadFromBuffer: _buffer + _bufferIndex
693 length: _bufferLength - _bufferIndex];
694 _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