Index: ObjFW.xcodeproj/project.pbxproj ================================================================== --- ObjFW.xcodeproj/project.pbxproj +++ ObjFW.xcodeproj/project.pbxproj @@ -298,10 +298,12 @@ 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 */; }; @@ -727,10 +729,12 @@ 4B7FF3B3133CED6100000324 /* OFConditionStillWaitingException.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFConditionStillWaitingException.m; path = src/exceptions/OFConditionStillWaitingException.m; sourceTree = ""; }; 4B837D7716829C5F007A3E83 /* block.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = block.h; path = src/block.h; sourceTree = ""; }; 4B837D7816829C5F007A3E83 /* instance.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = instance.h; path = src/instance.h; sourceTree = ""; }; 4B83F0F2142FDEFD00E4A821 /* OFStreamObserver_kqueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFStreamObserver_kqueue.h; path = src/OFStreamObserver_kqueue.h; sourceTree = ""; }; 4B83F0F3142FDEFD00E4A821 /* OFStreamObserver_kqueue.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFStreamObserver_kqueue.m; path = src/OFStreamObserver_kqueue.m; sourceTree = ""; }; + 4B86E7C917F8B98200ACA680 /* OFDeflateStream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFDeflateStream.h; path = src/OFDeflateStream.h; sourceTree = ""; }; + 4B86E7CA17F8B98200ACA680 /* OFDeflateStream.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFDeflateStream.m; path = src/OFDeflateStream.m; sourceTree = ""; }; 4B879A89177231F000EBCEA4 /* OFDataArray+MessagePackValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = "OFDataArray+MessagePackValue.h"; path = "src/OFDataArray+MessagePackValue.h"; sourceTree = ""; }; 4B879A8A177231F000EBCEA4 /* OFDataArray+MessagePackValue.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = "OFDataArray+MessagePackValue.m"; path = "src/OFDataArray+MessagePackValue.m"; sourceTree = ""; }; 4B879A8B177231F000EBCEA4 /* OFMessagePackRepresentation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFMessagePackRepresentation.h; path = src/OFMessagePackRepresentation.h; sourceTree = ""; }; 4B8B025717BBA7C7009ED983 /* OFZIPArchiveEntry.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFZIPArchiveEntry.h; path = src/OFZIPArchiveEntry.h; sourceTree = ""; }; 4B8B025817BBA7C7009ED983 /* OFZIPArchiveEntry.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFZIPArchiveEntry.m; path = src/OFZIPArchiveEntry.m; sourceTree = ""; }; @@ -1154,10 +1158,12 @@ 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 */, @@ -1452,10 +1458,11 @@ 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 */, @@ -1814,10 +1821,11 @@ 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 */, Index: src/Makefile ================================================================== --- src/Makefile +++ src/Makefile @@ -16,10 +16,11 @@ OFCountedSet.m \ OFDataArray.m \ OFDataArray+Hashing.m \ OFDataArray+MessagePackValue.m \ OFDate.m \ + OFDeflateStream.m \ OFDictionary.m \ OFEnumerator.m \ OFFile.m \ OFIntrospection.m \ OFList.m \ ADDED src/OFDeflateStream.h Index: src/OFDeflateStream.h ================================================================== --- src/OFDeflateStream.h +++ src/OFDeflateStream.h @@ -0,0 +1,97 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013 + * Jonathan Schleifer + * + * 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 ADDED src/OFDeflateStream.m Index: src/OFDeflateStream.m ================================================================== --- src/OFDeflateStream.m +++ src/OFDeflateStream.m @@ -0,0 +1,753 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013 + * Jonathan Schleifer + * + * 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 +#include + +#include + +#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 Index: src/OFStream.h ================================================================== --- src/OFStream.h +++ src/OFStream.h @@ -1065,11 +1065,11 @@ * 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 that was + * 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 */ Index: src/ObjFW.h ================================================================== --- src/ObjFW.h +++ src/ObjFW.h @@ -44,10 +44,11 @@ #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"