ObjFW  Check-in [d83d3aa719]

		4B745BA6168B25E600A6C20E /* OFSystemInfo.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B745BA4168B25E600A6C20E /* OFSystemInfo.m */; };
		4B7FF3B4133CED6200000324 /* OFConditionStillWaitingException.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B7FF3B2133CED6100000324 /* OFConditionStillWaitingException.h */; settings = {ATTRIBUTES = (Public, ); }; };
		4B7FF3B5133CED6200000324 /* OFConditionStillWaitingException.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B7FF3B3133CED6100000324 /* OFConditionStillWaitingException.m */; };
		4B837D7916829C5F007A3E83 /* block.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B837D7716829C5F007A3E83 /* block.h */; settings = {ATTRIBUTES = (Public, ); }; };
		4B837D7A16829C5F007A3E83 /* instance.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B837D7816829C5F007A3E83 /* instance.h */; settings = {ATTRIBUTES = (Public, ); }; };
		4B83F0F4142FDEFD00E4A821 /* OFStreamObserver_kqueue.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B83F0F2142FDEFD00E4A821 /* OFStreamObserver_kqueue.h */; };
		4B83F0F5142FDEFD00E4A821 /* OFStreamObserver_kqueue.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B83F0F3142FDEFD00E4A821 /* OFStreamObserver_kqueue.m */; };
		4B86E7CB17F8B98200ACA680 /* OFDeflateStream.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B86E7C917F8B98200ACA680 /* OFDeflateStream.h */; settings = {ATTRIBUTES = (Public, ); }; };
		4B86E7CC17F8B98200ACA680 /* OFDeflateStream.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B86E7CA17F8B98200ACA680 /* OFDeflateStream.m */; };
		4B879A8C177231F000EBCEA4 /* OFDataArray+MessagePackValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B879A89177231F000EBCEA4 /* OFDataArray+MessagePackValue.h */; settings = {ATTRIBUTES = (Public, ); }; };
		4B879A8D177231F000EBCEA4 /* OFDataArray+MessagePackValue.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B879A8A177231F000EBCEA4 /* OFDataArray+MessagePackValue.m */; };
		4B879A8E177231F000EBCEA4 /* OFMessagePackRepresentation.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B879A8B177231F000EBCEA4 /* OFMessagePackRepresentation.h */; settings = {ATTRIBUTES = (Public, ); }; };
		4B8B025917BBA7C7009ED983 /* OFZIPArchiveEntry.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B8B025717BBA7C7009ED983 /* OFZIPArchiveEntry.h */; settings = {ATTRIBUTES = (Public, ); }; };
		4B8B025A17BBA7C7009ED983 /* OFZIPArchiveEntry.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B8B025817BBA7C7009ED983 /* OFZIPArchiveEntry.m */; };
		4B8B16FE133A3B84007CD8B3 /* OFHashAlreadyCalculatedException.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B8B16FC133A3B84007CD8B3 /* OFHashAlreadyCalculatedException.h */; settings = {ATTRIBUTES = (Public, ); }; };
		4B8B16FF133A3B84007CD8B3 /* OFHashAlreadyCalculatedException.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B8B16FD133A3B84007CD8B3 /* OFHashAlreadyCalculatedException.m */; };

		4B745BA4168B25E600A6C20E /* OFSystemInfo.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFSystemInfo.m; path = src/OFSystemInfo.m; sourceTree = "<group>"; };
		4B7FF3B2133CED6100000324 /* OFConditionStillWaitingException.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFConditionStillWaitingException.h; path = src/exceptions/OFConditionStillWaitingException.h; sourceTree = "<group>"; };
		4B7FF3B3133CED6100000324 /* OFConditionStillWaitingException.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFConditionStillWaitingException.m; path = src/exceptions/OFConditionStillWaitingException.m; sourceTree = "<group>"; };
		4B837D7716829C5F007A3E83 /* block.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = block.h; path = src/block.h; sourceTree = "<group>"; };
		4B837D7816829C5F007A3E83 /* instance.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = instance.h; path = src/instance.h; sourceTree = "<group>"; };
		4B83F0F2142FDEFD00E4A821 /* OFStreamObserver_kqueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFStreamObserver_kqueue.h; path = src/OFStreamObserver_kqueue.h; sourceTree = "<group>"; };
		4B83F0F3142FDEFD00E4A821 /* OFStreamObserver_kqueue.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFStreamObserver_kqueue.m; path = src/OFStreamObserver_kqueue.m; sourceTree = "<group>"; };
		4B86E7C917F8B98200ACA680 /* OFDeflateStream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFDeflateStream.h; path = src/OFDeflateStream.h; sourceTree = "<group>"; };
		4B86E7CA17F8B98200ACA680 /* OFDeflateStream.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFDeflateStream.m; path = src/OFDeflateStream.m; sourceTree = "<group>"; };
		4B879A89177231F000EBCEA4 /* OFDataArray+MessagePackValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = "OFDataArray+MessagePackValue.h"; path = "src/OFDataArray+MessagePackValue.h"; sourceTree = "<group>"; };
		4B879A8A177231F000EBCEA4 /* OFDataArray+MessagePackValue.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = "OFDataArray+MessagePackValue.m"; path = "src/OFDataArray+MessagePackValue.m"; sourceTree = "<group>"; };
		4B879A8B177231F000EBCEA4 /* OFMessagePackRepresentation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFMessagePackRepresentation.h; path = src/OFMessagePackRepresentation.h; sourceTree = "<group>"; };
		4B8B025717BBA7C7009ED983 /* OFZIPArchiveEntry.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFZIPArchiveEntry.h; path = src/OFZIPArchiveEntry.h; sourceTree = "<group>"; };
		4B8B025817BBA7C7009ED983 /* OFZIPArchiveEntry.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFZIPArchiveEntry.m; path = src/OFZIPArchiveEntry.m; sourceTree = "<group>"; };
		4B8B16FC133A3B84007CD8B3 /* OFHashAlreadyCalculatedException.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFHashAlreadyCalculatedException.h; path = src/exceptions/OFHashAlreadyCalculatedException.h; sourceTree = "<group>"; };
		4B8B16FD133A3B84007CD8B3 /* OFHashAlreadyCalculatedException.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFHashAlreadyCalculatedException.m; path = src/exceptions/OFHashAlreadyCalculatedException.m; sourceTree = "<group>"; };

				4B6799611099E7C50041064A /* OFDataArray.m */,
				4BE17AD912FD746D002CEB0B /* OFDataArray+Hashing.h */,
				4BE17ADA12FD746D002CEB0B /* OFDataArray+Hashing.m */,
				4B879A89177231F000EBCEA4 /* OFDataArray+MessagePackValue.h */,
				4B879A8A177231F000EBCEA4 /* OFDataArray+MessagePackValue.m */,
				4BE5F0D912DF4225005C7A0C /* OFDate.h */,
				4BE5F0DA12DF4225005C7A0C /* OFDate.m */,
				4B86E7C917F8B98200ACA680 /* OFDeflateStream.h */,
				4B86E7CA17F8B98200ACA680 /* OFDeflateStream.m */,
				4B6799621099E7C50041064A /* OFDictionary.h */,
				4B6799631099E7C50041064A /* OFDictionary.m */,
				4B2B3E75140D430500EC2F7C /* OFDictionary_hashtable.h */,
				4B2B3E76140D430500EC2F7C /* OFDictionary_hashtable.m */,
				4B0108C910EB8C9300631877 /* OFEnumerator.h */,
				4B0108CA10EB8C9300631877 /* OFEnumerator.m */,
				4B6799661099E7C50041064A /* OFFile.h */,

				4B3D23C11337FC8300DD29B8 /* OFConstantString.h in Headers */,
				4B45355313DCFE1E0037AB4D /* OFCountedSet.h in Headers */,
				4B3D23C21337FC8300DD29B8 /* OFDataArray.h in Headers */,
				4B3D23C31337FC8300DD29B8 /* OFDataArray+Hashing.h in Headers */,
				4B879A8C177231F000EBCEA4 /* OFDataArray+MessagePackValue.h in Headers */,
				4B3D23C41337FC8300DD29B8 /* OFDate.h in Headers */,
				4B3D23C51337FCB000DD29B8 /* OFDictionary.h in Headers */,
				4B86E7CB17F8B98200ACA680 /* OFDeflateStream.h in Headers */,
				4B3D23C61337FCB000DD29B8 /* OFEnumerator.h in Headers */,
				4B17FF74133A2AAB003E6DCD /* OFException.h in Headers */,
				4B3D23C81337FCB000DD29B8 /* OFFile.h in Headers */,
				4B3D23C91337FCB000DD29B8 /* OFHash.h in Headers */,
				4BB4B54416775FF4002A2DCE /* OFHTTPClient.h in Headers */,
				4B3D23CA1337FCB000DD29B8 /* OFHTTPRequest.h in Headers */,
				4B7161AD17A6FC7600B74970 /* OFHTTPResponse.h in Headers */,

				4B3D238F1337FC0D00DD29B8 /* OFConstantString.m in Sources */,
				4B45355413DCFE1E0037AB4D /* OFCountedSet.m in Sources */,
				4BA85BCB140ECCE800E91D51 /* OFCountedSet_hashtable.m in Sources */,
				4B3D23901337FC0D00DD29B8 /* OFDataArray.m in Sources */,
				4B3D23911337FC0D00DD29B8 /* OFDataArray+Hashing.m in Sources */,
				4B879A8D177231F000EBCEA4 /* OFDataArray+MessagePackValue.m in Sources */,
				4B3D23921337FC0D00DD29B8 /* OFDate.m in Sources */,
				4B86E7CC17F8B98200ACA680 /* OFDeflateStream.m in Sources */,
				4B3D23931337FC0D00DD29B8 /* OFDictionary.m in Sources */,
				4B2B3E80140D430500EC2F7C /* OFDictionary_hashtable.m in Sources */,
				4B3D23941337FC0D00DD29B8 /* OFEnumerator.m in Sources */,
				4B3D23961337FC0D00DD29B8 /* OFFile.m in Sources */,
				4BB4B54516775FF4002A2DCE /* OFHTTPClient.m in Sources */,
				4B3D23981337FC0D00DD29B8 /* OFHTTPRequest.m in Sources */,
				4B7161AE17A6FC7600B74970 /* OFHTTPResponse.m in Sources */,

       OFBlock.m			\
       OFConstantString.m		\
       OFCountedSet.m			\
       OFDataArray.m			\
       OFDataArray+Hashing.m		\
       OFDataArray+MessagePackValue.m	\
       OFDate.m				\
       OFDeflateStream.m		\
       OFDictionary.m			\
       OFEnumerator.m			\
       OFFile.m				\
       OFIntrospection.m		\
       OFList.m				\
       OFMapTable.m			\
       OFMD5Hash.m			\

/*
 * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of ObjFW. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE.QPL included in
 * the packaging of this file.
 *
 * Alternatively, it may be distributed under the terms of the GNU General
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#import "OFStream.h"

#define OF_DEFLATE_STREAM_BUFFER_SIZE 4096

/*!
 * @brief A class for a stream that handles deflate compression or decompression
 *	  transparently for an underlying stream.
 */
@interface OFDeflateStream: OFStream
{
#ifdef OF_DEFLATE_STREAM_M
@public
#endif
	OFStream *_stream;
	uint8_t _buffer[OF_DEFLATE_STREAM_BUFFER_SIZE];
	uint_fast16_t _bufferIndex, _bufferLength;
	uint8_t _byte;
	uint_fast8_t _bitIndex, _savedBitsLength;
	uint_fast16_t _savedBits;
@protected
	char *_slidingWindow;
	uint_fast16_t _slidingWindowIndex;
	enum {
		OF_DEFLATE_STREAM_BLOCK_HEADER,
		OF_DEFLATE_STREAM_UNCOMPRESSED_BLOCK_HEADER,
		OF_DEFLATE_STREAM_UNCOMPRESSED_BLOCK,
		OF_DEFLATE_STREAM_HUFFMAN_TREE,
		OF_DEFLATE_STREAM_HUFFMAN_BLOCK
	} _state;
	union {
		struct {
			uint_fast8_t position;
			uint8_t length[4];
		} uncompressedHeader;
		struct {
			uint_fast16_t position, length;
		} uncompressed;
		struct {
			struct huffman_tree *litLenTree, *distTree;
			struct huffman_tree *codeLenTree, *treeIter;
			uint8_t *lengths;
			uint_fast16_t receivedCount;
			uint_fast8_t value, litLenCodesCount, distCodesCount;
			uint_fast8_t codeLenCodesCount;
		} huffmanTree;
		struct {
			struct huffman_tree *litLenTree, *distTree, *treeIter;
			enum {
				OF_DEFLATE_STREAM_WRITE_VALUE,
				OF_DEFLATE_STREAM_AWAIT_CODE,
				OF_DEFLATE_STREAM_AWAIT_LENGTH_EXTRA_BITS,
				OF_DEFLATE_STREAM_AWAIT_DISTANCE,
				OF_DEFLATE_STREAM_AWAIT_DISTANCE_EXTRA_BITS,
				OF_DEFLATE_STREAM_PROCESS_PAIR
			} state;
			uint_fast16_t value, length, distance;
			uint_fast16_t extraBits;
		} huffman;
	} _context;
	bool _inLastBlock, _atEndOfStream;
}

/*!
 * @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
 * @return A new, autoreleased OFDeflateStream
 */
+ (instancetype)streamWithStream: (OFStream*)stream;

/*!
 * @brief Initializes an already allocated OFDeflateStream with the specified
 *	  underlying stream.
 *
 * @param stream The underlying stream to which compressed data is written or
 *		 from which compressed data is read
 * @return A initialized OFDeflateStream
 */
- initWithStream: (OFStream*)stream;
@end

/*
 * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of ObjFW. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE.QPL included in
 * the packaging of this file.
 *
 * Alternatively, it may be distributed under the terms of the GNU General
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#include "config.h"

#define OF_DEFLATE_STREAM_M

#include <stdlib.h>
#include <string.h>

#include <assert.h>

#import "OFDeflateStream.h"
#import "OFDataArray.h"

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

#import "autorelease.h"
#import "macros.h"

#define BLOCK_HEADER		  OF_DEFLATE_STREAM_BLOCK_HEADER
#define UNCOMPRESSED_BLOCK_HEADER OF_DEFLATE_STREAM_UNCOMPRESSED_BLOCK_HEADER
#define UNCOMPRESSED_BLOCK	  OF_DEFLATE_STREAM_UNCOMPRESSED_BLOCK
#define HUFFMAN_BLOCK		  OF_DEFLATE_STREAM_HUFFMAN_BLOCK
#define HUFFMAN_TREE		  OF_DEFLATE_STREAM_HUFFMAN_TREE
#define CONSTRUCT_CODELEN_TREE	  OF_DEFLATE_STREAM_CONSTRUCT_CODELEN_TREE
#define CONSTRUCT_LITLEN_TREE	  OF_DEFLATE_STREAM_CONSTRUCT_LITLEN_TREE
#define CONSTRUCT_DIST_TREE	  OF_DEFLATE_STREAM_CONSTRUCT_DIST_TREE
#define AWAIT_CODE		  OF_DEFLATE_STREAM_AWAIT_CODE
#define WRITE_VALUE		  OF_DEFLATE_STREAM_WRITE_VALUE
#define AWAIT_LENGTH_EXTRA_BITS   OF_DEFLATE_STREAM_AWAIT_LENGTH_EXTRA_BITS
#define AWAIT_DISTANCE		  OF_DEFLATE_STREAM_AWAIT_DISTANCE
#define AWAIT_DISTANCE_EXTRA_BITS OF_DEFLATE_STREAM_AWAIT_DISTANCE_EXTRA_BITS
#define PROCESS_PAIR		  OF_DEFLATE_STREAM_PROCESS_PAIR
#define BUFFER_SIZE		  OF_DEFLATE_STREAM_BUFFER_SIZE

#define MAX_BITS    15

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

static 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
};
static uint8_t lengthExtraBits[29] = {
	0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4,
	5, 5, 5, 5, 0
};
static uint16_t distanceCodes[30] = {
	1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385,
	513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
};
static uint8_t distanceExtraBits[30] = {
	0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10,
	10, 11, 11, 12, 12, 13, 13
};
static 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, uint_fast16_t *bits, uint_fast8_t count)
{
	uint_fast16_t ret = stream->_savedBits;
	uint_fast8_t i;

	assert(stream->_savedBitsLength < count);

	for (i = stream->_savedBitsLength; i < count; i++) {
		if OF_UNLIKELY (stream->_bitIndex == 8) {
			if (stream->_bufferIndex < stream->_bufferLength)
				stream->_byte =
				    stream->_buffer[stream->_bufferIndex++];
			else {
				size_t length = [stream->_stream
				    readIntoBuffer: stream->_buffer
					    length: BUFFER_SIZE];

				if OF_UNLIKELY (length < 1) {
					stream->_savedBits = ret;
					stream->_savedBitsLength = i;
					return false;
				}

				stream->_byte = stream->_buffer[0];
				stream->_bufferIndex = 1;
				stream->_bufferLength = length;
			}

			stream->_bitIndex = 0;
		}

		ret |= ((stream->_byte >> stream->_bitIndex++) & 1) << i;
	}

	stream->_savedBits = 0;
	stream->_savedBitsLength = 0;
	*bits = ret;

	return true;
}

static struct huffman_tree*
newTree(void)
{
	struct huffman_tree *tree;

	if ((tree = malloc(sizeof(*tree))) == NULL)
		@throw [OFOutOfMemoryException
		    exceptionWithRequestedSize: sizeof(*tree)];

	tree->leafs[0] = tree->leafs[1] = NULL;
	tree->value = 0xFFFF;

	return tree;
}

static void
treeInsert(struct huffman_tree *tree, uint_fast16_t code, uint_fast8_t length,
    uint16_t value)
{
	while (length > 0) {
		uint_fast8_t bit;

		length--;
		bit = (code & (1 << length)) >> length;

		if (tree->leafs[bit] == NULL)
			tree->leafs[bit] = newTree();

		tree = tree->leafs[bit];
	}

	tree->value = value;
}

static struct huffman_tree*
constructTree(uint8_t lengths[], uint_fast16_t count)
{
	struct huffman_tree *tree;
	uint8_t lengthCount[MAX_BITS + 1] = { 0 };
	uint16_t code, maxCode, nextCode[MAX_BITS + 1];
	uint_fast16_t i;

	for (i = 0; i < count; i++) {
		uint8_t length = lengths[i];

		if OF_UNLIKELY (length > MAX_BITS)
			@throw [OFInvalidFormatException exception];

		if (length > 0) {
			lengthCount[length]++;
			maxCode = i;
		}
	}

	code = 0;
	for (i = 1; i <= MAX_BITS; i++) {
		code = (code + lengthCount[i - 1]) << 1;
		nextCode[i] = code;
	}

	tree = newTree();

	for (i = 0; i <= maxCode; i++) {
		uint8_t length = lengths[i];

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

	return tree;
}

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

	for (;;) {
		if OF_UNLIKELY (iter->leafs[0] == NULL &&
		    iter->leafs[1] == NULL)
			break;

		if OF_UNLIKELY (!tryReadBits(stream, &bits, 1)) {
			*tree = iter;
			return false;
		}

		if OF_UNLIKELY (iter->leafs[bits] == NULL)
			break;

		iter = iter->leafs[bits];
	}

	if OF_UNLIKELY (iter->value == 0xFFFF)
		@throw [OFInvalidFormatException exception];

	*value = iter->value;
	return true;
}

static void
releaseTree(struct huffman_tree *tree)
{
	uint_fast8_t i;

	for (i = 0; i < 2; i++)
		if OF_LIKELY (tree->leafs[i] != NULL)
			releaseTree(tree->leafs[i]);

	free(tree);
}

@implementation OFDeflateStream
+ (void)initialize
{
	uint_fast16_t i;
	uint8_t lengths[288];

	if (self != [OFDeflateStream class])
		return;

	for (i = 0; i <= 143; i++)
		lengths[i] = 8;
	for (i = 144; i <= 255; i++)
		lengths[i] = 9;
	for (i = 256; i <= 279; i++)
		lengths[i] = 7;
	for (i = 280; i <= 287; i++)
		lengths[i] = 8;

	fixedLitLenTree = constructTree(lengths, 288);

	for (i = 0; i <= 31; i++)
		lengths[i] = 5;

	fixedDistTree = constructTree(lengths, 32);
}

+ (instancetype)streamWithStream: (OFStream*)stream
{
	return [[[self alloc] initWithStream: stream] autorelease];
}

- init
{
	@try {
		[self doesNotRecognizeSelector: _cmd];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	abort();
}

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

	_stream = [stream retain];
	_bitIndex = 8;	/* 0-7 address the bit, 8 means fetch next byte */

	return self;
}

- (void)dealloc
{
	[_stream release];

	[super dealloc];
}

- (size_t)lowlevelReadIntoBuffer: (void*)buffer_
			  length: (size_t)length
{
	uint8_t *buffer = buffer_;
	uint_fast16_t bits, value;
	size_t i, tmp, bytesWritten = 0;
	char *slidingWindow;
	uint_fast16_t slidingWindowIndex;

	if (_atEndOfStream)
		@throw [OFReadFailedException exceptionWithStream: self
						  requestedLength: length];

start:
	switch (_state) {
	case BLOCK_HEADER:
		if OF_UNLIKELY (_inLastBlock) {
			[_stream unreadFromBuffer: _buffer + _bufferIndex
					   length: _bufferLength -
						   _bufferIndex];

			_atEndOfStream = true;
			return bytesWritten;
		}

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

		_inLastBlock = (bits & 1);

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

		goto start;
	case UNCOMPRESSED_BLOCK_HEADER:
#define CTX _context.uncompressedHeader
		/* FIXME: This can be done more efficiently than unreading */
		[_stream unreadFromBuffer: _buffer + _bufferIndex
				   length: _bufferLength - _bufferIndex];
		_bufferIndex = _bufferLength = 0;

		CTX.position += [_stream readIntoBuffer: CTX.length
						 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];

		_state = UNCOMPRESSED_BLOCK;

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

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

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

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

		if OF_UNLIKELY (_slidingWindow == NULL) {
			_slidingWindow = [self allocMemoryWithSize: 0x8000];
			/* Avoid leaking data */
			memset(_slidingWindow, 0, 0x8000);
		}

		slidingWindow = _slidingWindow;
		slidingWindowIndex = _slidingWindowIndex;
		for (i = 0; i < tmp; i++) {
			slidingWindow[slidingWindowIndex] =
			    buffer[bytesWritten + i];
			slidingWindowIndex = (slidingWindowIndex + 1) & 0x7FFF;
		}
		_slidingWindowIndex = slidingWindowIndex;

		length -= tmp;
		bytesWritten += tmp;

		CTX.position += tmp;
		if OF_UNLIKELY (CTX.position == CTX.length)
			_state = BLOCK_HEADER;

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

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

				CTX.litLenCodesCount = bits;
			}

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

				CTX.distCodesCount = bits;
			}

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

				if OF_UNLIKELY (bits + 4 > 19)
					@throw [OFInvalidFormatException
					    exception];

				CTX.codeLenCodesCount = bits;
			}

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

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

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

			CTX.codeLenTree = constructTree(CTX.lengths, 19);
			CTX.treeIter = CTX.codeLenTree;

			[self freeMemory: CTX.lengths];
			CTX.lengths = NULL;
			CTX.receivedCount = 0;
			CTX.value = 0xFF;
		}

		if OF_LIKELY (CTX.lengths == NULL)
			CTX.lengths = [self allocMemoryWithSize:
			    CTX.litLenCodesCount + CTX.distCodesCount + 258];

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

			if OF_LIKELY (CTX.value == 0xFF) {
				if OF_UNLIKELY (!walkTree(self, &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, &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, &bits, 3)) {
					CTX.receivedCount = i;
					CTX.value = value;
					return bytesWritten;
				}

				value = 0;
				count = bits + 3;

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

				value = 0;
				count = bits + 11;

				break;
			default:
				@throw [OFInvalidFormatException exception];
			}

			if OF_UNLIKELY (i + count >
			    CTX.litLenCodesCount + CTX.distCodesCount + 258)
				@throw [OFInvalidFormatException exception];

			for (j = 0; j < count; j++)
				CTX.lengths[i++] = value;
			i--;

			CTX.value = 0xFF;
		}

		releaseTree(CTX.codeLenTree);

		CTX.litLenTree = constructTree(CTX.lengths,
		    CTX.litLenCodesCount + 257);
		CTX.distTree = constructTree(
		    CTX.lengths + CTX.litLenCodesCount + 257,
		    CTX.distCodesCount + 1);

		[self freeMemory: CTX.lengths];

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

		goto start;
#undef CTX
	case HUFFMAN_BLOCK:
#define CTX _context.huffman
		for (;;) {
			uint_fast8_t extraBits, lengthCodeIndex;

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

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

				if (_slidingWindow == NULL) {
					_slidingWindow = [self
					    allocMemoryWithSize: 0x8000];
					/* Avoid leaking data */
					memset(_slidingWindow, 0, 0x8000);
				}

				_slidingWindow[_slidingWindowIndex] = CTX.value;
				_slidingWindowIndex = (_slidingWindowIndex +
				    1) & 0x7FFF;

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

			if OF_UNLIKELY (CTX.state == AWAIT_LENGTH_EXTRA_BITS) {
				if OF_UNLIKELY (!tryReadBits(self, &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, &CTX.treeIter,
				    &value))
					return bytesWritten;

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

				CTX.distance = distanceCodes[value];
				extraBits = distanceExtraBits[value];

				if (extraBits > 0) {
					if OF_UNLIKELY (!tryReadBits(self,
					    &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, &bits,
				    CTX.extraBits))
					return bytesWritten;

				CTX.distance += bits;

				CTX.state = PROCESS_PAIR;
			}

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

				if OF_UNLIKELY (_slidingWindow == NULL)
					@throw [OFInvalidFormatException
					    exception];

				for (j = 0; j < CTX.length; j++) {
					uint_fast16_t index;
					uint8_t value;

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

					index = (_slidingWindowIndex -
					    CTX.distance) & 0x7FFF;
					value = _slidingWindow[index];

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

					_slidingWindow[_slidingWindowIndex] =
					    value;
					_slidingWindowIndex =
					    (_slidingWindowIndex + 1) & 0x7FFF;
				}

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

			if OF_UNLIKELY (!walkTree(self, &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);

				_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 (_slidingWindow == NULL) {
					_slidingWindow = [self
					    allocMemoryWithSize: 0x8000];
					/* Avoid leaking data */
					memset(_slidingWindow, 0, 0x8000);
				}

				_slidingWindow[_slidingWindowIndex] = value;
				_slidingWindowIndex = (_slidingWindowIndex +
				    1) & 0x7FFF;

				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, &bits,
				    extraBits)) {
					CTX.extraBits = extraBits;
					CTX.state = AWAIT_LENGTH_EXTRA_BITS;
					return bytesWritten;
				}

				CTX.length += bits;
			}

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

		break;
#undef CTX
	}
}

- (bool)lowlevelIsAtEndOfStream
{
	return _atEndOfStream;
}
@end

 * decompression - in which it would otherwise be necessary to read byte by
 * byte to avoid consuming bytes that need to be parsed by something else -
 * for example the data descriptor in a ZIP archive which immediately follows
 * the compressed data.
 *
 * If the stream is a file, this method does not change any data in the file.
 *
 * If the stream is seekable, a seek operation will discard any data which was
 * unread.
 *
 * @param buffer The buffer to unread
 * @param length The length of the buffer to unread
 */
- (void)unreadFromBuffer: (const void*)buffer
		  length: (size_t)length;

#import "OFNumber.h"
#import "OFDate.h"
#import "OFURL.h"

#import "OFStream.h"
#import "OFStdIOStream.h"
#import "OFDeflateStream.h"
#import "OFFile.h"
#import "OFZIPArchive.h"
#import "OFZIPArchiveEntry.h"
#ifdef OF_HAVE_SOCKETS
# import "OFStreamSocket.h"
# import "OFTCPSocket.h"
# import "OFTLSSocket.h"