ObjFW  Check-in [e9e89aa4c0]

 */
@interface OFDeflateStream: OFStream
{
#ifdef OF_INFLATE_STREAM_M
@public
#endif
	OFStream *_stream;
	struct of_deflate_stream_decompression_ivars {
		uint8_t buffer[OF_INFLATE_STREAM_BUFFER_SIZE];
		uint16_t bufferIndex, bufferLength;
		uint8_t byte;
		uint8_t bitIndex, savedBitsLength;
		uint16_t savedBits;

		uint8_t *slidingWindow;
		uint16_t slidingWindowIndex, slidingWindowMask;






		int state;
		union {
			struct {
				uint8_t position;
				uint8_t length[4];
			} uncompressedHeader;
			struct {
				uint16_t position, length;
			} uncompressed;
			struct {
				struct huffman_tree *litLenTree, *distTree;
				struct huffman_tree *codeLenTree, *treeIter;
				uint8_t *lengths;
				uint16_t receivedCount;
				uint8_t value, litLenCodesCount, distCodesCount;
				uint8_t codeLenCodesCount;
			} huffmanTree;
			struct {
				struct huffman_tree *litLenTree, *distTree;
				struct huffman_tree *treeIter;






				int state;
				uint16_t value, length, distance;
				uint16_t extraBits;
			} huffman;
		} context;
		bool inLastBlock, atEndOfStream;
	} *_decompression;
}

/*!
 * @brief Creates a new OFDeflateStream with the specified underlying stream.
 *
 * @param stream The underlying stream to which compressed data is written or
 *		 from which compressed data is read

#import "OFDataArray.h"

#import "OFInitializationFailedException.h"
#import "OFInvalidFormatException.h"
#import "OFOutOfMemoryException.h"
#import "OFReadFailedException.h"

#define BUFFER_SIZE		  OF_INFLATE_STREAM_BUFFER_SIZE

#define MAX_BITS 15

enum state {
	BLOCK_HEADER,
	UNCOMPRESSED_BLOCK_HEADER,
	UNCOMPRESSED_BLOCK,
	HUFFMAN_TREE,
	HUFFMAN_BLOCK
};




enum huffman_state {
	WRITE_VALUE,
	AWAIT_CODE,
	AWAIT_LENGTH_EXTRA_BITS,
	AWAIT_DISTANCE,
	AWAIT_DISTANCE_EXTRA_BITS,
	PROCESS_PAIR

};


struct huffman_tree {
	struct huffman_tree *leafs[2];
	uint16_t value;
};

@interface OFDeflateStream ()
- (void)OF_initDecompression;
@end

#ifndef DEFLATE64
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,
	64, 80, 96, 112, 128, 160, 192, 224, 255

#endif
static const uint8_t codeLengthsOrder[19] = {
	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
};
static struct huffman_tree *fixedLitLenTree, *fixedDistTree;

static bool
tryReadBits(OFDeflateStream *stream,
    struct of_deflate_stream_decompression_ivars *ivars,
    uint16_t *bits, uint8_t count)
{
	uint16_t ret = ivars->savedBits;

	assert(ivars->savedBitsLength < count);

	for (uint8_t i = ivars->savedBitsLength; i < count; i++) {
		if OF_UNLIKELY (ivars->bitIndex == 8) {
			if (ivars->bufferIndex < ivars->bufferLength)
				ivars->byte =
				    ivars->buffer[ivars->bufferIndex++];
			else {
				size_t length = [stream->_stream
				    readIntoBuffer: ivars->buffer
					    length: BUFFER_SIZE];

				if OF_UNLIKELY (length < 1) {
					ivars->savedBits = ret;
					ivars->savedBitsLength = i;
					return false;
				}

				ivars->byte = ivars->buffer[0];
				ivars->bufferIndex = 1;
				ivars->bufferLength = (uint16_t)length;
			}

			ivars->bitIndex = 0;
		}

		ret |= ((ivars->byte >> ivars->bitIndex++) & 1) << i;
	}

	ivars->savedBits = 0;
	ivars->savedBitsLength = 0;
	*bits = ret;

	return true;
}

static struct huffman_tree*
newTree(void)

			treeInsert(tree, nextCode[length]++, length, i);
	}

	return tree;
}

static bool
walkTree(OFDeflateStream *stream,
    struct of_deflate_stream_decompression_ivars *ivars,
    struct huffman_tree **tree, uint16_t *value)
{
	struct huffman_tree *iter = *tree;
	uint16_t bits;

	while (iter->value == 0xFFFF) {
		if OF_UNLIKELY (!tryReadBits(stream, ivars, &bits, 1)) {
			*tree = iter;
			return false;
		}

		if OF_UNLIKELY (iter->leafs[bits] == NULL)
			@throw [OFInvalidFormatException exception];

}

- initWithStream: (OFStream*)stream
{
	self = [super init];

	_stream = [stream retain];



	return self;
}

- (void)dealloc
{
	[_stream release];

	if (_decompression != NULL && _decompression->state == HUFFMAN_TREE)
		if (_decompression->context.huffmanTree.codeLenTree != NULL)
			releaseTree(
			    _decompression->context.huffmanTree.codeLenTree);

	if (_decompression != NULL && (_decompression->state == HUFFMAN_TREE ||
	    _decompression->state == HUFFMAN_BLOCK)) {
		if (_decompression->context.huffman.litLenTree !=
		    fixedLitLenTree)
			releaseTree(_decompression->context.huffman.litLenTree);
		if (_decompression->context.huffman.distTree != fixedDistTree)
			releaseTree(_decompression->context.huffman.distTree);
	}

	[super dealloc];
}
#endif

- (void)OF_initDecompression
{
	_decompression = [self allocMemoryWithSize: sizeof(*_decompression)];
	memset(_decompression, 0, sizeof(*_decompression));

	/* 0-7 address the bit, 8 means fetch next byte */
	_decompression->bitIndex = 8;
	_decompression->slidingWindowMask = 0x7FFF;
}

- (size_t)lowlevelReadIntoBuffer: (void*)buffer_
			  length: (size_t)length
{
	struct of_deflate_stream_decompression_ivars *ivars = _decompression;
	uint8_t *buffer = buffer_;
	uint16_t bits, tmp;
	uint16_t value;
	size_t bytesWritten = 0;
	uint8_t *slidingWindow;
	uint16_t slidingWindowIndex;

	if (ivars == NULL) {
		[self OF_initDecompression];
		ivars = _decompression;
	}

	if (ivars->atEndOfStream)
		@throw [OFReadFailedException exceptionWithObject: self
						  requestedLength: length];

start:
	switch ((enum state)ivars->state) {
	case BLOCK_HEADER:
		if OF_UNLIKELY (ivars->inLastBlock) {
			[_stream unreadFromBuffer: ivars->buffer +
						   ivars->bufferIndex
					   length: ivars->bufferLength -
						   ivars->bufferIndex];

			ivars->atEndOfStream = true;
			return bytesWritten;
		}

		if OF_UNLIKELY (!tryReadBits(self, ivars, &bits, 3))
			return bytesWritten;

		ivars->inLastBlock = (bits & 1);

		switch (bits >> 1) {
		case 0: /* No compression */
			ivars->state = UNCOMPRESSED_BLOCK_HEADER;
			ivars->bitIndex = 8;
			ivars->context.uncompressedHeader.position = 0;
			memset(ivars->context.uncompressedHeader.length, 0, 4);
			break;
		case 1: /* Fixed Huffman */
			ivars->state = HUFFMAN_BLOCK;
			ivars->context.huffman.state = AWAIT_CODE;
			ivars->context.huffman.litLenTree = fixedLitLenTree;
			ivars->context.huffman.distTree = fixedDistTree;
			ivars->context.huffman.treeIter = fixedLitLenTree;
			break;
		case 2: /* Dynamic Huffman */
			ivars->state = HUFFMAN_TREE;
			ivars->context.huffmanTree.lengths = NULL;
			ivars->context.huffmanTree.receivedCount = 0;
			ivars->context.huffmanTree.value = 0xFE;
			ivars->context.huffmanTree.litLenCodesCount = 0xFF;
			ivars->context.huffmanTree.distCodesCount = 0xFF;
			ivars->context.huffmanTree.codeLenCodesCount = 0xFF;
			break;
		default:
			@throw [OFInvalidFormatException exception];
		}

		goto start;
	case UNCOMPRESSED_BLOCK_HEADER:
#define CTX ivars->context.uncompressedHeader
		/* FIXME: This can be done more efficiently than unreading */
		[_stream unreadFromBuffer: ivars->buffer + ivars->bufferIndex
				   length: ivars->bufferLength -
					   ivars->bufferIndex];
		ivars->bufferIndex = ivars->bufferLength = 0;

		CTX.position += [_stream
		    readIntoBuffer: CTX.length + CTX.position
			    length: 4 - CTX.position];

		if OF_UNLIKELY (CTX.position < 4)
			return bytesWritten;

		if OF_UNLIKELY ((CTX.length[0] | (CTX.length[1] << 8)) !=
		    (uint16_t)~(CTX.length[2] | (CTX.length[3] << 8)))
			@throw [OFInvalidFormatException exception];

		ivars->state = UNCOMPRESSED_BLOCK;

		/*
		 * Do not reorder! ivars->context.uncompressed.position and
		 * ivars->context.uncompressedHeader.length overlap!
		 */
		ivars->context.uncompressed.length =
		    CTX.length[0] | (CTX.length[1] << 8);
		ivars->context.uncompressed.position = 0;

		goto start;
#undef CTX
	case UNCOMPRESSED_BLOCK:
#define CTX ivars->context.uncompressed
		if OF_UNLIKELY (length == 0)
			return bytesWritten;

		tmp = (length < (size_t)CTX.length - CTX.position
		    ? (uint16_t)length : CTX.length - CTX.position);

		tmp = (uint16_t)[_stream readIntoBuffer: buffer + bytesWritten
						 length: tmp];

		if OF_UNLIKELY (ivars->slidingWindow == NULL) {
			ivars->slidingWindow = [self allocMemoryWithSize:
			    ivars->slidingWindowMask + 1];
			/* Avoid leaking data */
			memset(ivars->slidingWindow, 0,
			    ivars->slidingWindowMask + 1);
		}

		slidingWindow = ivars->slidingWindow;
		slidingWindowIndex = ivars->slidingWindowIndex;
		for (uint16_t i = 0; i < tmp; i++) {
			slidingWindow[slidingWindowIndex] =
			    buffer[bytesWritten + i];
			slidingWindowIndex = (slidingWindowIndex + 1) &
			    ivars->slidingWindowMask;
		}
		ivars->slidingWindowIndex = slidingWindowIndex;

		length -= tmp;
		bytesWritten += tmp;

		CTX.position += tmp;
		if OF_UNLIKELY (CTX.position == CTX.length)
			ivars->state = BLOCK_HEADER;

		goto start;
#undef CTX
	case HUFFMAN_TREE:
#define CTX ivars->context.huffmanTree
		if OF_LIKELY (CTX.value == 0xFE) {
			if OF_LIKELY (CTX.litLenCodesCount == 0xFF) {
				if OF_UNLIKELY (!tryReadBits(self, ivars,
				    &bits, 5))
					return bytesWritten;

				if OF_UNLIKELY (bits > 29)
					@throw [OFInvalidFormatException
					    exception];

				CTX.litLenCodesCount = bits;
			}

			if OF_LIKELY (CTX.distCodesCount == 0xFF) {
				if OF_UNLIKELY (!tryReadBits(self, ivars,
				    &bits, 5))
					return bytesWritten;

				CTX.distCodesCount = bits;
			}

			if OF_LIKELY (CTX.codeLenCodesCount == 0xFF) {
				if OF_UNLIKELY (!tryReadBits(self, ivars,
				    &bits, 4))
					return bytesWritten;

				CTX.codeLenCodesCount = bits;
			}

			if OF_LIKELY (CTX.lengths == NULL) {
				CTX.lengths = [self allocMemoryWithSize: 19];
				memset(CTX.lengths, 0, 19);
			}

			for (uint16_t i = CTX.receivedCount;
			    i < CTX.codeLenCodesCount + 4; i++) {
				if OF_UNLIKELY (!tryReadBits(self, ivars,
				    &bits, 3)) {
					CTX.receivedCount = i;
					return bytesWritten;
				}

				CTX.lengths[codeLengthsOrder[i]] = bits;
			}

			    CTX.litLenCodesCount + CTX.distCodesCount + 258];

		for (uint16_t i = CTX.receivedCount;
		    i < CTX.litLenCodesCount + CTX.distCodesCount + 258;) {
			uint8_t j, count;

			if OF_LIKELY (CTX.value == 0xFF) {
				if OF_UNLIKELY (!walkTree(self, ivars,
				    &CTX.treeIter, &value)) {
					CTX.receivedCount = i;
					return bytesWritten;
				}

				CTX.treeIter = CTX.codeLenTree;

				if (value < 16) {
					CTX.lengths[i++] = value;
					continue;
				}
			} else
				value = CTX.value;

			switch (value) {
			case 16:
				if OF_UNLIKELY (i < 1)
					@throw [OFInvalidFormatException
					    exception];

				if OF_UNLIKELY (!tryReadBits(self, ivars,
				    &bits, 2)) {
					CTX.receivedCount = i;
					CTX.value = value;
					return bytesWritten;
				}

				value = CTX.lengths[i - 1];
				count = bits + 3;

				break;
			case 17:
				if OF_UNLIKELY (!tryReadBits(self, ivars,
				    &bits, 3)) {
					CTX.receivedCount = i;
					CTX.value = value;
					return bytesWritten;
				}

				value = 0;
				count = bits + 3;

				break;
			case 18:
				if OF_UNLIKELY (!tryReadBits(self, ivars,
				    &bits, 7)) {
					CTX.receivedCount = i;
					CTX.value = value;
					return bytesWritten;
				}

				value = 0;
				count = bits + 11;

		    CTX.lengths + CTX.litLenCodesCount + 257,
		    CTX.distCodesCount + 1);

		[self freeMemory: CTX.lengths];

		/*
		 * litLenTree and distTree are at the same location in
		 * ivars->context.huffman and ivars->context.huffmanTree, thus
		 * no need to set them.
		 */
		ivars->state = HUFFMAN_BLOCK;
		ivars->context.huffman.state = AWAIT_CODE;
		ivars->context.huffman.treeIter = CTX.litLenTree;

		goto start;
#undef CTX
	case HUFFMAN_BLOCK:
#define CTX ivars->context.huffman
		for (;;) {
			uint8_t extraBits, lengthCodeIndex;

			if OF_UNLIKELY (CTX.state == WRITE_VALUE) {
				if OF_UNLIKELY (length == 0)
					return bytesWritten;

				buffer[bytesWritten++] = CTX.value;
				length--;

				if (ivars->slidingWindow == NULL) {
					ivars->slidingWindow = [self
					    allocMemoryWithSize:
					    ivars->slidingWindowMask + 1];
					/* Avoid leaking data */
					memset(ivars->slidingWindow, 0,
					    ivars->slidingWindowMask + 1);
				}

				ivars->slidingWindow[
				    ivars->slidingWindowIndex] = CTX.value;
				ivars->slidingWindowIndex =
				    (ivars->slidingWindowIndex + 1) &
				    ivars->slidingWindowMask;

				CTX.state = AWAIT_CODE;
				CTX.treeIter = CTX.litLenTree;
			}

			if OF_UNLIKELY (CTX.state == AWAIT_LENGTH_EXTRA_BITS) {
				if OF_UNLIKELY (!tryReadBits(self, ivars,
				    &bits, CTX.extraBits))
					return bytesWritten;

				CTX.length += bits;

				CTX.state = AWAIT_DISTANCE;
				CTX.treeIter = CTX.distTree;
			}

			/* Distance of length distance pair */
			if (CTX.state == AWAIT_DISTANCE) {
				if OF_UNLIKELY (!walkTree(self, ivars,
				    &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,
					    ivars, &bits, extraBits)) {
						CTX.state =
						    AWAIT_DISTANCE_EXTRA_BITS;
						CTX.extraBits = extraBits;
						return bytesWritten;
					}

					CTX.distance += bits;
				}

				CTX.state = PROCESS_PAIR;
			} else if (CTX.state == AWAIT_DISTANCE_EXTRA_BITS) {
				if OF_UNLIKELY (!tryReadBits(self, ivars,
				    &bits, CTX.extraBits))
					return bytesWritten;

				CTX.distance += bits;

				CTX.state = PROCESS_PAIR;
			}

			/* Length distance pair */
			if (CTX.state == PROCESS_PAIR) {
				uint16_t j;

				if OF_UNLIKELY (ivars->slidingWindow == NULL)
					@throw [OFInvalidFormatException
					    exception];

				for (j = 0; j < CTX.length; j++) {
					uint16_t index;

					if OF_UNLIKELY (length == 0) {
						CTX.length -= j;
						return bytesWritten;
					}

					index = (ivars->slidingWindowIndex -
					    CTX.distance) &
					    ivars->slidingWindowMask;
					value = ivars->slidingWindow[index];

					buffer[bytesWritten++] = value;
					length--;

					ivars->slidingWindow[
					    ivars->slidingWindowIndex] = value;
					ivars->slidingWindowIndex =
					    (ivars->slidingWindowIndex + 1) &
					    ivars->slidingWindowMask;
				}

				CTX.state = AWAIT_CODE;
				CTX.treeIter = CTX.litLenTree;
			}

			if OF_UNLIKELY (!walkTree(self, ivars,
			    &CTX.treeIter, &value))
				return bytesWritten;

			/* End of block */
			if OF_UNLIKELY (value == 256) {
				if (CTX.litLenTree != fixedLitLenTree)
					releaseTree(CTX.litLenTree);
				if (CTX.distTree != fixedDistTree)
					releaseTree(CTX.distTree);

				ivars->state = BLOCK_HEADER;
				goto start;
			}

			/* Literal byte */
			if (value < 256) {
				if OF_UNLIKELY (length == 0) {
					CTX.state = WRITE_VALUE;
					CTX.value = value;
					return bytesWritten;
				}

				buffer[bytesWritten++] = value;
				length--;

				if (ivars->slidingWindow == NULL) {
					ivars->slidingWindow = [self
					    allocMemoryWithSize:
					    ivars->slidingWindowMask + 1];
					/* Avoid leaking data */
					memset(ivars->slidingWindow, 0,
					    ivars->slidingWindowMask + 1);
				}

				ivars->slidingWindow[
				    ivars->slidingWindowIndex] = value;
				ivars->slidingWindowIndex =
				    (ivars->slidingWindowIndex + 1) &
				    ivars->slidingWindowMask;

				CTX.treeIter = CTX.litLenTree;
				continue;
			}

			if OF_UNLIKELY (value > 285)
				@throw [OFInvalidFormatException exception];

			/* Length of length distance pair */
			lengthCodeIndex = value - 257;
			CTX.length = lengthCodes[lengthCodeIndex] + 3;
			extraBits = lengthExtraBits[lengthCodeIndex];

			if (extraBits > 0) {
				if OF_UNLIKELY (!tryReadBits(self, ivars,
				    &bits, extraBits)) {
					CTX.extraBits = extraBits;
					CTX.state = AWAIT_LENGTH_EXTRA_BITS;
					return bytesWritten;
				}

				CTX.length += bits;
			}

	OF_UNREACHABLE
}

#ifndef DEFLATE64
- (bool)lowlevelIsAtEndOfStream
{
	if (_decompression == NULL)
		return true;

	return _decompression->atEndOfStream;
}

- (int)fileDescriptorForReading
{
	return [_stream fileDescriptorForReading];
}

- (bool)hasDataInReadBuffer
{
	return ([super hasDataInReadBuffer] || [_stream hasDataInReadBuffer]);
}
#endif
@end