ObjFW  Check-in [a8c62e1c0d]

 *
 * 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"

#import "OFDeflate64Stream.h"

static const uint_fast8_t numDistanceCodes = 32;
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, 0
};
static const 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, 16
};
static const uint16_t distanceCodes[32] = {
	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,
	32769, 49153
};
static const uint8_t distanceExtraBits[32] = {
	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, 14, 14
};

@implementation OFDeflate64Stream
- initWithStream: (OFStream*)stream
{
	self = [super initWithStream: stream];

	_slidingWindowMask = 0xFFFF;
	_codes.numDistanceCodes = numDistanceCodes;
	_codes.lengthCodes = lengthCodes;
	_codes.lengthExtraBits = lengthExtraBits;
	_codes.distanceCodes = distanceCodes;
	_codes.distanceExtraBits = distanceExtraBits;

	return self;
}
@end

	uint_fast16_t _bufferIndex, _bufferLength;
	uint8_t _byte;
	uint_fast8_t _bitIndex, _savedBitsLength;
	uint_fast16_t _savedBits;
@protected
	uint8_t *_slidingWindow;
	uint_fast16_t _slidingWindowIndex, _slidingWindowMask;
	struct {
		uint_fast8_t numDistanceCodes;
		const uint8_t *lengthCodes;
		const uint8_t *lengthExtraBits;
		const uint16_t *distanceCodes;
		const uint8_t *distanceExtraBits;
	} _codes;
	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;

#include "config.h"

#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"

#define MAX_BITS 15

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


static const uint_fast8_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
};
static const 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 const 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 const 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 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, uint_fast16_t *bits, uint_fast8_t count)

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

	fixedDistTree = constructTree(lengths, 32);
}


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

- init
{
	OF_INVALID_INIT_METHOD
}

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

	_stream = [stream retain];
	_bitIndex = 8;	/* 0-7 address the bit, 8 means fetch next byte */
	_slidingWindowMask = 0x7FFF;
	_codes.numDistanceCodes = numDistanceCodes;
	_codes.lengthCodes = lengthCodes;
	_codes.lengthExtraBits = lengthExtraBits;
	_codes.distanceCodes = distanceCodes;
	_codes.distanceExtraBits = distanceExtraBits;

	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, i, tmp;
	uint16_t value;

			/* Distance of length distance pair */
			if (CTX.state == AWAIT_DISTANCE) {
				if OF_UNLIKELY (!walkTree(self, &CTX.treeIter,
				    &value))
					return bytesWritten;

				if OF_UNLIKELY (value >=
				    _codes.numDistanceCodes)
					@throw [OFInvalidFormatException
					    exception];

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

				if (extraBits > 0) {
					if OF_UNLIKELY (!tryReadBits(self,
					    &bits, extraBits)) {
						CTX.state =
						    AWAIT_DISTANCE_EXTRA_BITS;
						CTX.extraBits = extraBits;

			}

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

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

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

		break;
#undef CTX
	}

	OF_UNREACHABLE
}


- (bool)lowlevelIsAtEndOfStream
{
	return _atEndOfStream;
}

@end