Index: src/Makefile ================================================================== --- src/Makefile +++ src/Makefile @@ -107,10 +107,11 @@ OFXMLProcessingInstructions.m \ OFZIPArchive.m \ OFZIPArchiveEntry.m \ base64.m \ crc32.m \ + huffman_tree.m \ of_asprintf.m \ of_strptime.m \ pbkdf2.m \ scrypt.m \ ${UNICODE_M} \ Index: src/OFInflateStream.h ================================================================== --- src/OFInflateStream.h +++ src/OFInflateStream.h @@ -35,16 +35,16 @@ { #ifdef OF_INFLATE_STREAM_M @public #endif OF_KINDOF(OFStream *) _stream; - uint8_t _buffer[OF_INFLATE_STREAM_BUFFER_SIZE]; + unsigned char _buffer[OF_INFLATE_STREAM_BUFFER_SIZE]; uint16_t _bufferIndex, _bufferLength; uint8_t _byte; uint8_t _bitIndex, _savedBitsLength; uint16_t _savedBits; - uint8_t *_Nullable _slidingWindow; + unsigned char *_Nullable _slidingWindow; uint16_t _slidingWindowIndex, _slidingWindowMask; int _state; union { struct { uint8_t position; @@ -52,23 +52,23 @@ } uncompressedHeader; struct { uint16_t position, length; } uncompressed; struct { - struct huffman_tree *_Nullable litLenTree; - struct huffman_tree *_Nullable distTree; - struct huffman_tree *_Nullable codeLenTree; - struct huffman_tree *_Nullable treeIter; + struct of_huffman_tree *_Nullable litLenTree; + struct of_huffman_tree *_Nullable distTree; + struct of_huffman_tree *_Nullable codeLenTree; + struct of_huffman_tree *_Nullable treeIter; uint8_t *_Nullable lengths; uint16_t receivedCount; uint8_t value, litLenCodesCount, distCodesCount; uint8_t codeLenCodesCount; } huffmanTree; struct { - struct huffman_tree *_Nullable litLenTree; - struct huffman_tree *_Nullable distTree; - struct huffman_tree *_Nullable treeIter; + struct of_huffman_tree *_Nullable litLenTree; + struct of_huffman_tree *_Nullable distTree; + struct of_huffman_tree *_Nullable treeIter; int state; uint16_t value, length, distance, extraBits; } huffman; } _context; bool _inLastBlock, _atEndOfStream; Index: src/OFInflateStream.m ================================================================== --- src/OFInflateStream.m +++ src/OFInflateStream.m @@ -28,20 +28,20 @@ # import "OFInflateStream.h" #else # import "OFInflate64Stream.h" # define OFInflateStream OFInflate64Stream #endif + +#import "huffman_tree.h" #import "OFInitializationFailedException.h" #import "OFInvalidFormatException.h" #import "OFNotOpenException.h" #import "OFOutOfMemoryException.h" #define BUFFER_SIZE OF_INFLATE_STREAM_BUFFER_SIZE -#define MAX_BITS 15 - enum state { BLOCK_HEADER, UNCOMPRESSED_BLOCK_HEADER, UNCOMPRESSED_BLOCK, HUFFMAN_TREE, @@ -55,15 +55,10 @@ AWAIT_DISTANCE, AWAIT_DISTANCE_EXTRA_BITS, PROCESS_PAIR }; -struct huffman_tree { - struct huffman_tree *leafs[2]; - uint16_t value; -}; - #ifndef INFLATE64 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, @@ -103,20 +98,20 @@ }; #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 struct of_huffman_tree *fixedLitLenTree, *fixedDistTree; static bool tryReadBits(OFInflateStream *stream, uint16_t *bits, uint8_t count) { uint16_t ret = stream->_savedBits; assert(stream->_savedBitsLength < count); - for (uint8_t i = stream->_savedBitsLength; i < count; i++) { + for (uint_fast8_t i = stream->_savedBitsLength; i < count; i++) { if OF_UNLIKELY (stream->_bitIndex == 8) { if (stream->_bufferIndex < stream->_bufferLength) stream->_byte = stream->_buffer[stream->_bufferIndex++]; else { @@ -146,113 +141,10 @@ *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, uint16_t code, uint8_t length, - uint16_t value) -{ - while (length > 0) { - uint8_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[], uint16_t count) -{ - struct huffman_tree *tree; - uint16_t lengthCount[MAX_BITS + 1] = { 0 }; - uint16_t code, maxCode = 0, nextCode[MAX_BITS + 1]; - - for (uint16_t 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 (size_t i = 1; i <= MAX_BITS; i++) { - code = (code + lengthCount[i - 1]) << 1; - nextCode[i] = code; - } - - tree = newTree(); - - for (uint16_t i = 0; i <= maxCode; i++) { - uint8_t length = lengths[i]; - - if (length > 0) - treeInsert(tree, nextCode[length]++, length, i); - } - - return tree; -} - -static bool -walkTree(OFInflateStream *stream, struct huffman_tree **tree, uint16_t *value) -{ - struct huffman_tree *iter = *tree; - uint16_t bits; - - while (iter->value == 0xFFFF) { - if OF_UNLIKELY (!tryReadBits(stream, &bits, 1)) { - *tree = iter; - return false; - } - - if OF_UNLIKELY (iter->leafs[bits] == NULL) - @throw [OFInvalidFormatException exception]; - - iter = iter->leafs[bits]; - } - - *value = iter->value; - return true; -} - -static void -releaseTree(struct huffman_tree *tree) -{ - for (uint8_t i = 0; i < 2; i++) - if OF_LIKELY (tree->leafs[i] != NULL) - releaseTree(tree->leafs[i]); - - free(tree); -} - @implementation OFInflateStream + (void)initialize { uint8_t lengths[288]; @@ -266,16 +158,16 @@ for (uint16_t i = 256; i <= 279; i++) lengths[i] = 7; for (uint16_t i = 280; i <= 287; i++) lengths[i] = 8; - fixedLitLenTree = constructTree(lengths, 288); + fixedLitLenTree = of_huffman_tree_construct(lengths, 288); for (uint16_t i = 0; i <= 31; i++) lengths[i] = 5; - fixedDistTree = constructTree(lengths, 32); + fixedDistTree = of_huffman_tree_construct(lengths, 32); } #ifndef INFLATE64 + (instancetype)streamWithStream: (OFStream *)stream { @@ -289,19 +181,29 @@ - (instancetype)initWithStream: (OFStream *)stream { self = [super init]; - _stream = [stream retain]; + @try { + _stream = [stream retain]; - /* 0-7 address the bit, 8 means fetch next byte */ - _bitIndex = 8; + /* 0-7 address the bit, 8 means fetch next byte */ + _bitIndex = 8; + #ifdef INFLATE64 - _slidingWindowMask = 0xFFFF; + _slidingWindowMask = 0xFFFF; #else - _slidingWindowMask = 0x7FFF; + _slidingWindowMask = 0x7FFF; #endif + _slidingWindow = [self allocMemoryWithSize: + _slidingWindowMask + 1]; + /* Avoid leaking data */ + memset(_slidingWindow, 0, _slidingWindowMask + 1); + } @catch (id e) { + [self release]; + @throw e; + } return self; } - (void)dealloc @@ -308,31 +210,31 @@ { [self close]; if (_state == HUFFMAN_TREE) if (_context.huffmanTree.codeLenTree != NULL) - releaseTree(_context.huffmanTree.codeLenTree); + of_huffman_tree_release( + _context.huffmanTree.codeLenTree); if (_state == HUFFMAN_TREE || _state == HUFFMAN_BLOCK) { if (_context.huffman.litLenTree != fixedLitLenTree) - releaseTree(_context.huffman.litLenTree); + of_huffman_tree_release(_context.huffman.litLenTree); if (_context.huffman.distTree != fixedDistTree) - releaseTree(_context.huffman.distTree); + of_huffman_tree_release(_context.huffman.distTree); } [super dealloc]; } #endif - (size_t)lowlevelReadIntoBuffer: (void *)buffer_ length: (size_t)length { - uint8_t *buffer = buffer_; - uint16_t bits, tmp; - uint16_t value; + unsigned char *buffer = buffer_; + uint16_t bits, tmp, value; size_t bytesWritten = 0; - uint8_t *slidingWindow; + unsigned char *slidingWindow; uint16_t slidingWindowIndex; if (_stream == nil) @throw [OFNotOpenException exceptionWithObject: self]; @@ -423,20 +325,13 @@ ? (uint16_t)length : CTX.length - CTX.position); tmp = (uint16_t)[_stream readIntoBuffer: buffer + bytesWritten length: tmp]; - if OF_UNLIKELY (_slidingWindow == NULL) { - _slidingWindow = - [self allocMemoryWithSize: _slidingWindowMask + 1]; - /* Avoid leaking data */ - memset(_slidingWindow, 0, _slidingWindowMask + 1); - } - slidingWindow = _slidingWindow; slidingWindowIndex = _slidingWindowIndex; - for (uint16_t i = 0; i < tmp; i++) { + for (uint_fast16_t i = 0; i < tmp; i++) { slidingWindow[slidingWindowIndex] = buffer[bytesWritten + i]; slidingWindowIndex = (slidingWindowIndex + 1) & _slidingWindowMask; } @@ -482,21 +377,22 @@ if OF_LIKELY (CTX.lengths == NULL) { CTX.lengths = [self allocMemoryWithSize: 19]; memset(CTX.lengths, 0, 19); } - for (uint16_t i = CTX.receivedCount; + for (uint_fast16_t 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.codeLenTree = of_huffman_tree_construct( + CTX.lengths, 19); CTX.treeIter = CTX.codeLenTree; [self freeMemory: CTX.lengths]; CTX.lengths = NULL; CTX.receivedCount = 0; @@ -505,17 +401,17 @@ if OF_LIKELY (CTX.lengths == NULL) CTX.lengths = [self allocMemoryWithSize: CTX.litLenCodesCount + CTX.distCodesCount + 258]; - for (uint16_t i = CTX.receivedCount; + for (uint_fast16_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, &CTX.treeIter, - &value)) { + if OF_UNLIKELY (!of_huffman_tree_walk(self, + tryReadBits, &CTX.treeIter, &value)) { CTX.receivedCount = i; return bytesWritten; } CTX.treeIter = CTX.codeLenTree; @@ -577,16 +473,16 @@ CTX.lengths[i++] = value; CTX.value = 0xFF; } - releaseTree(CTX.codeLenTree); + of_huffman_tree_release(CTX.codeLenTree); CTX.codeLenTree = NULL; - CTX.litLenTree = constructTree(CTX.lengths, + CTX.litLenTree = of_huffman_tree_construct(CTX.lengths, CTX.litLenCodesCount + 257); - CTX.distTree = constructTree( + CTX.distTree = of_huffman_tree_construct( CTX.lengths + CTX.litLenCodesCount + 257, CTX.distCodesCount + 1); [self freeMemory: CTX.lengths]; @@ -611,19 +507,10 @@ return bytesWritten; buffer[bytesWritten++] = CTX.value; length--; - if (_slidingWindow == NULL) { - _slidingWindow = [self - allocMemoryWithSize: - _slidingWindowMask + 1]; - /* Avoid leaking data */ - memset(_slidingWindow, 0, - _slidingWindowMask + 1); - } - _slidingWindow[_slidingWindowIndex] = CTX.value; _slidingWindowIndex = (_slidingWindowIndex + 1) & _slidingWindowMask; @@ -642,12 +529,12 @@ CTX.treeIter = CTX.distTree; } /* Distance of length distance pair */ if (CTX.state == AWAIT_DISTANCE) { - if OF_UNLIKELY (!walkTree(self, &CTX.treeIter, - &value)) + if OF_UNLIKELY (!of_huffman_tree_walk(self, + tryReadBits, &CTX.treeIter, &value)) return bytesWritten; if OF_UNLIKELY (value >= numDistanceCodes) @throw [OFInvalidFormatException exception]; @@ -678,17 +565,11 @@ CTX.state = PROCESS_PAIR; } /* Length distance pair */ if (CTX.state == PROCESS_PAIR) { - uint16_t j; - - if OF_UNLIKELY (_slidingWindow == NULL) - @throw [OFInvalidFormatException - exception]; - - for (j = 0; j < CTX.length; j++) { + for (uint_fast16_t j = 0; j < CTX.length; j++) { uint16_t idx; if OF_UNLIKELY (length == 0) { CTX.length -= j; return bytesWritten; @@ -710,44 +591,36 @@ CTX.state = AWAIT_CODE; CTX.treeIter = CTX.litLenTree; } - if OF_UNLIKELY (!walkTree(self, &CTX.treeIter, &value)) + if OF_UNLIKELY (!of_huffman_tree_walk(self, tryReadBits, + &CTX.treeIter, &value)) return bytesWritten; /* End of block */ if OF_UNLIKELY (value == 256) { if (CTX.litLenTree != fixedLitLenTree) - releaseTree(CTX.litLenTree); + of_huffman_tree_release(CTX.litLenTree); if (CTX.distTree != fixedDistTree) - releaseTree(CTX.distTree); + of_huffman_tree_release(CTX.distTree); _state = BLOCK_HEADER; goto start; } /* Literal byte */ - if (value < 256) { + if OF_LIKELY (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: - _slidingWindowMask + 1]; - /* Avoid leaking data */ - memset(_slidingWindow, 0, - _slidingWindowMask + 1); - } - _slidingWindow[_slidingWindowIndex] = value; _slidingWindowIndex = (_slidingWindowIndex + 1) & _slidingWindowMask; Index: src/OFLHAArchive.m ================================================================== --- src/OFLHAArchive.m +++ src/OFLHAArchive.m @@ -14,10 +14,12 @@ * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this * file. */ #include "config.h" + +#include #import "OFLHAArchive.h" #import "OFLHAArchiveEntry.h" #import "OFLHAArchiveEntry+Private.h" #ifdef OF_HAVE_FILES @@ -24,15 +26,48 @@ # import "OFFile.h" #endif #import "OFStream.h" #import "OFSeekableStream.h" #import "OFString.h" + +#import "huffman_tree.h" #import "OFInvalidArgumentException.h" +#import "OFInvalidFormatException.h" #import "OFNotImplementedException.h" #import "OFNotOpenException.h" #import "OFTruncatedDataException.h" + +#define LHSTREAM_BUFFER_SIZE 4096 + +@interface OFLHAArchive_LHStream: OFStream +{ +@public + OFStream *_stream; + uint8_t _distanceBits, _dictionaryBits; + unsigned char _buffer[LHSTREAM_BUFFER_SIZE]; + uint16_t _bufferIndex, _bufferLength; + uint8_t _byte; + uint8_t _bitIndex, _savedBitsLength; + uint16_t _savedBits; + unsigned char *_slidingWindow; + uint32_t _slidingWindowIndex, _slidingWindowMask; + int _state; + uint16_t _symbolsLeft; + struct of_huffman_tree *_codeLenTree, *_litLenTree, *_distTree; + struct of_huffman_tree *_treeIter; + uint16_t _codesCount, _codesReceived; + bool _currentIsExtendedLength, _skip; + uint8_t *_codesLengths; + uint16_t _length; + uint32_t _distance; +} + +- (instancetype)of_initWithStream: (OFStream *)stream + distanceBits: (uint8_t)distanceBits + dictionaryBits: (uint8_t)dictionaryBits; +@end @interface OFLHAArchive_FileReadStream: OFStream { OF_KINDOF(OFStream *) _stream; uint32_t _toRead; @@ -41,10 +76,69 @@ - (instancetype)of_initWithStream: (OFStream *)stream entry: (OFLHAArchiveEntry *)entry; - (void)of_skip; @end + +enum state { + STATE_BLOCK_HEADER, + STATE_CODE_LEN_CODES_COUNT, + STATE_CODE_LEN_TREE, + STATE_CODE_LEN_TREE_SINGLE, + STATE_LITLEN_CODES_COUNT, + STATE_LITLEN_TREE, + STATE_LITLEN_TREE_SINGLE, + STATE_DIST_CODES_COUNT, + STATE_DIST_TREE, + STATE_DIST_TREE_SINGLE, + STATE_BLOCK_LITLEN, + STATE_BLOCK_DIST_LENGTH, + STATE_BLOCK_DIST_LENGTH_EXTRA, + STATE_BLOCK_LEN_DIST_PAIR +}; + +static bool +tryReadBits(OFLHAArchive_LHStream *stream, uint16_t *bits, uint8_t count) +{ + uint16_t ret = stream->_savedBits; + + assert(stream->_savedBitsLength < count); + + for (uint_fast8_t 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: LHSTREAM_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 = (uint16_t)length; + } + + stream->_bitIndex = 0; + } + + ret = (ret << 1) | + ((stream->_byte >> (7 - stream->_bitIndex++)) & 1); + } + + stream->_savedBits = 0; + stream->_savedBitsLength = 0; + *bits = ret; + + return true; +} @implementation OFLHAArchive @synthesize encoding = _encoding; + (instancetype)archiveWithStream: (OF_KINDOF(OFStream *))stream @@ -167,16 +261,10 @@ if (_lastReturnedStream == nil) @throw [OFInvalidArgumentException exception]; method = [_lastEntry method]; - if (![method isEqual: @"-lh0-"] && ![method isEqual: @"-lhd-"] && - ![method isEqual: @"-lz4-"]) - @throw [OFNotImplementedException - exceptionWithSelector: _cmd - object: self]; - return [[_lastReturnedStream retain] autorelease]; } - (void)close { @@ -192,25 +280,463 @@ [_stream release]; _stream = nil; } @end + +@implementation OFLHAArchive_LHStream +- (instancetype)of_initWithStream: (OFStream *)stream + distanceBits: (uint8_t)distanceBits + dictionaryBits: (uint8_t)dictionaryBits +{ + self = [super init]; + + @try { + _stream = [stream retain]; + + /* 0-7 address the bit, 8 means fetch next byte */ + _bitIndex = 8; + + _distanceBits = distanceBits; + _dictionaryBits = dictionaryBits; + + _slidingWindowMask = (1 << dictionaryBits) - 1; + _slidingWindow = [self allocMemoryWithSize: + _slidingWindowMask + 1]; + /* Avoid leaking data */ + memset(_slidingWindow, 0, _slidingWindowMask + 1); + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- (void)dealloc +{ + [self close]; + + if (_codeLenTree != NULL) + of_huffman_tree_release(_codeLenTree); + if (_litLenTree != NULL) + of_huffman_tree_release(_litLenTree); + if (_distTree != NULL) + of_huffman_tree_release(_distTree); + + [super dealloc]; +} + +- (size_t)lowlevelReadIntoBuffer: (void *)buffer_ + length: (size_t)length +{ + unsigned char *buffer = buffer_; + uint16_t bits, value; + size_t bytesWritten = 0; + + if (_stream == nil) + @throw [OFNotOpenException exceptionWithObject: self]; + + if ([_stream isAtEndOfStream] && _bufferLength - _bufferIndex == 0 && + _state == STATE_BLOCK_HEADER) + return 0; + +start: + switch ((enum state)_state) { + case STATE_BLOCK_HEADER: + if OF_UNLIKELY (!tryReadBits(self, &bits, 16)) + return bytesWritten; + + _symbolsLeft = bits; + + _state = STATE_CODE_LEN_CODES_COUNT; + goto start; + case STATE_CODE_LEN_CODES_COUNT: + if OF_UNLIKELY (!tryReadBits(self, &bits, 5)) + return bytesWritten; + + if OF_UNLIKELY (bits > 20) + @throw [OFInvalidFormatException exception]; + + if OF_UNLIKELY (bits == 0) { + _state = STATE_CODE_LEN_TREE_SINGLE; + goto start; + } + + _codesCount = bits; + _codesReceived = 0; + _codesLengths = [self allocMemoryWithSize: bits]; + memset(_codesLengths, 0, bits); + _skip = true; + + _state = STATE_CODE_LEN_TREE; + goto start; + case STATE_CODE_LEN_TREE: + while (_codesReceived < _codesCount) { + if OF_UNLIKELY (_currentIsExtendedLength) { + if OF_UNLIKELY (!tryReadBits(self, &bits, 1)) + return bytesWritten; + + if OF_UNLIKELY (bits == 0) { + _codesReceived++; + _currentIsExtendedLength = false; + continue; + } + + _codesLengths[_codesReceived]++; + continue; + } + + if OF_UNLIKELY (_codesReceived == 3 && _skip) { + if OF_UNLIKELY (!tryReadBits(self, &bits, 2)) + return bytesWritten; + + if OF_UNLIKELY (_codesReceived + bits > + _codesCount) + @throw [OFInvalidFormatException + exception]; + + for (uint_fast8_t j = 0; j < bits; j++) + _codesLengths[_codesReceived++] = 0; + + _skip = false; + continue; + } + + if OF_UNLIKELY (!tryReadBits(self, &bits, 3)) + return bytesWritten; + + _codesLengths[_codesReceived] = bits; + + if OF_UNLIKELY (bits == 7) { + _currentIsExtendedLength = true; + continue; + } else + _codesReceived++; + } + + _codeLenTree = of_huffman_tree_construct(_codesLengths, + _codesCount); + [self freeMemory: _codesLengths]; + + _state = STATE_LITLEN_CODES_COUNT; + goto start; + case STATE_CODE_LEN_TREE_SINGLE: + if OF_UNLIKELY (!tryReadBits(self, &bits, 5)) + return bytesWritten; + + _codeLenTree = of_huffman_tree_construct_single(bits); + + _state = STATE_LITLEN_CODES_COUNT; + goto start; + case STATE_LITLEN_CODES_COUNT: + if OF_UNLIKELY (!tryReadBits(self, &bits, 9)) + return bytesWritten; + + if OF_UNLIKELY (bits > 510) + @throw [OFInvalidFormatException exception]; + + if OF_UNLIKELY (bits == 0) { + of_huffman_tree_release(_codeLenTree); + _codeLenTree = NULL; + + _state = STATE_LITLEN_TREE_SINGLE; + goto start; + } + + _codesCount = bits; + _codesReceived = 0; + _codesLengths = [self allocMemoryWithSize: bits]; + memset(_codesLengths, 0, bits); + _skip = false; + + _treeIter = _codeLenTree; + _state = STATE_LITLEN_TREE; + goto start; + case STATE_LITLEN_TREE: + while (_codesReceived < _codesCount) { + if OF_UNLIKELY (_skip) { + uint_fast16_t skipCount; + + switch (_codesLengths[_codesReceived]) { + case 0: + skipCount = 1; + break; + case 1: + if OF_UNLIKELY (!tryReadBits(self, + &bits, 4)) + return bytesWritten; + + skipCount = bits + 3; + break; + case 2: + if OF_UNLIKELY (!tryReadBits(self, + &bits, 9)) + return bytesWritten; + + skipCount = bits + 20; + break; + default: + assert(0); + } + + if OF_UNLIKELY (_codesReceived + skipCount > + _codesCount) + @throw [OFInvalidFormatException + exception]; + + for (uint16_t j = 0; j < skipCount; j++) + _codesLengths[_codesReceived++] = 0; + + _skip = false; + continue; + } + + if (!of_huffman_tree_walk(self, tryReadBits, + &_treeIter, &value)) + return bytesWritten; + + _treeIter = _codeLenTree; + + if (value < 3) { + _codesLengths[_codesReceived] = value; + _skip = true; + } else + _codesLengths[_codesReceived++] = value - 2; + } + + _litLenTree = of_huffman_tree_construct(_codesLengths, + _codesCount); + [self freeMemory: _codesLengths]; + + of_huffman_tree_release(_codeLenTree); + _codeLenTree = NULL; + + _state = STATE_DIST_CODES_COUNT; + goto start; + case STATE_LITLEN_TREE_SINGLE: + if OF_UNLIKELY (!tryReadBits(self, &bits, 9)) + return bytesWritten; + + _litLenTree = of_huffman_tree_construct_single(bits); + + _state = STATE_DIST_CODES_COUNT; + goto start; + case STATE_DIST_CODES_COUNT: + if OF_UNLIKELY (!tryReadBits(self, &bits, _distanceBits)) + return bytesWritten; + + if OF_UNLIKELY (bits > _dictionaryBits) + @throw [OFInvalidFormatException exception]; + + if OF_UNLIKELY (bits == 0) { + _state = STATE_DIST_TREE_SINGLE; + goto start; + } + + _codesCount = bits; + _codesReceived = 0; + _codesLengths = [self allocMemoryWithSize: bits]; + memset(_codesLengths, 0, bits); + + _treeIter = _codeLenTree; + _state = STATE_DIST_TREE; + goto start; + case STATE_DIST_TREE: + while (_codesReceived < _codesCount) { + if OF_UNLIKELY (_currentIsExtendedLength) { + if OF_UNLIKELY (!tryReadBits(self, &bits, 1)) + return bytesWritten; + + if OF_UNLIKELY (bits == 0) { + _codesReceived++; + _currentIsExtendedLength = false; + continue; + } + + _codesLengths[_codesReceived]++; + continue; + } + + if OF_UNLIKELY (!tryReadBits(self, &bits, 3)) + return bytesWritten; + + _codesLengths[_codesReceived] = bits; + + if OF_UNLIKELY (bits == 7) { + _currentIsExtendedLength = true; + continue; + } else + _codesReceived++; + } + + _distTree = of_huffman_tree_construct(_codesLengths, + _codesCount); + [self freeMemory: _codesLengths]; + + _treeIter = _litLenTree; + _state = STATE_BLOCK_LITLEN; + goto start; + case STATE_DIST_TREE_SINGLE: + if OF_UNLIKELY (!tryReadBits(self, &bits, _distanceBits)) + return bytesWritten; + + _distTree = of_huffman_tree_construct_single(bits); + + _treeIter = _litLenTree; + _state = STATE_BLOCK_LITLEN; + goto start; + case STATE_BLOCK_LITLEN: + if OF_UNLIKELY (_symbolsLeft == 0) { + of_huffman_tree_release(_litLenTree); + of_huffman_tree_release(_distTree); + _litLenTree = _distTree = NULL; + + _state = STATE_BLOCK_HEADER; + + /* + * We must return here, as there is no indication + * whether this was the last block. Whoever called this + * method needs to check if everything has been read + * already and only call read again if that is not the + * case. + * + * We must also unread the buffer, in case this was the + * last block and something else follows, e.g. another + * LHA header. + */ + [_stream unreadFromBuffer: _buffer + _bufferIndex + length: _bufferLength - + _bufferIndex]; + _bufferIndex = _bufferLength = 0; + + return bytesWritten; + } + + if OF_UNLIKELY (length == 0) + return bytesWritten; + + if OF_UNLIKELY (!of_huffman_tree_walk(self, tryReadBits, + &_treeIter, &value)) + return bytesWritten; + + if OF_LIKELY (value < 256) { + buffer[bytesWritten++] = value; + length--; + + _slidingWindow[_slidingWindowIndex] = value; + _slidingWindowIndex = (_slidingWindowIndex + 1) & + _slidingWindowMask; + + _symbolsLeft--; + _treeIter = _litLenTree; + } else { + _length = value - 253; + _treeIter = _distTree; + _state = STATE_BLOCK_DIST_LENGTH; + } + + goto start; + case STATE_BLOCK_DIST_LENGTH: + if OF_UNLIKELY (!of_huffman_tree_walk(self, tryReadBits, + &_treeIter, &value)) + return bytesWritten; + + _distance = value; + + _state = (value < 2 + ? STATE_BLOCK_LEN_DIST_PAIR + : STATE_BLOCK_DIST_LENGTH_EXTRA); + goto start; + case STATE_BLOCK_DIST_LENGTH_EXTRA: + if OF_UNLIKELY (!tryReadBits(self, &bits, _distance - 1)) + return bytesWritten; + + _distance = bits + (1 << (_distance - 1)); + + _state = STATE_BLOCK_LEN_DIST_PAIR; + goto start; + case STATE_BLOCK_LEN_DIST_PAIR: + for (uint_fast16_t i = 0; i < _length; i++) { + uint32_t idx; + + if OF_UNLIKELY (length == 0) { + _length -= i; + return bytesWritten; + } + + idx = (_slidingWindowIndex - _distance - 1) & + _slidingWindowMask; + value = _slidingWindow[idx]; + + buffer[bytesWritten++] = value; + length--; + + _slidingWindow[_slidingWindowIndex] = value; + _slidingWindowIndex = (_slidingWindowIndex + 1) & + _slidingWindowMask; + } + + _symbolsLeft--; + + _treeIter = _litLenTree; + _state = STATE_BLOCK_LITLEN; + goto start; + } +} + +- (bool)lowlevelIsAtEndOfStream +{ + if (_stream == nil) + @throw [OFNotOpenException exceptionWithObject: self]; + + return ([_stream isAtEndOfStream] && + _bufferLength - _bufferIndex == 0 && _state == STATE_BLOCK_HEADER); +} + +- (void)close +{ + [_stream release]; + _stream = nil; + + [super close]; +} +@end @implementation OFLHAArchive_FileReadStream - (instancetype)of_initWithStream: (OFStream *)stream entry: (OFLHAArchiveEntry *)entry { self = [super init]; @try { - _stream = [stream retain]; - /* - * Use the compressed size, as that is the number of bytes we - * need to skip for the next entry and is equal for - * uncompressed files, the only thing supported so far. - */ - _toRead = [entry compressedSize]; + OFString *method = [entry method]; + + if ([method isEqual: @"-lh4-"] || [method isEqual: @"-lh5-"]) + _stream = [[OFLHAArchive_LHStream alloc] + of_initWithStream: stream + distanceBits: 4 + dictionaryBits: 14]; + else if ([method isEqual: @"-lh6-"]) + _stream = [[OFLHAArchive_LHStream alloc] + of_initWithStream: stream + distanceBits: 5 + dictionaryBits: 16]; + else if ([method isEqual: @"-lh7-"]) + _stream = [[OFLHAArchive_LHStream alloc] + of_initWithStream: stream + distanceBits: 5 + dictionaryBits: 17]; + else + _stream = [stream retain]; + + if ([method isEqual: @"-lh0-"] || [method isEqual: @"-lhd-"] || + [method isEqual: @"-lz4-"] || [method isEqual: @"-lh5-"] || + [method isEqual: @"-lh6-"] || [method isEqual: @"-lh6-"]) + _toRead = [entry uncompressedSize]; + else + _toRead = [entry compressedSize]; } @catch (id e) { [self release]; @throw e; } @@ -239,15 +765,15 @@ length = _toRead; ret = [_stream readIntoBuffer: buffer length: length]; - if (ret == 0) - _atEndOfStream = true; - _toRead -= ret; + if (_toRead == 0) + _atEndOfStream = true; + return ret; } - (bool)lowlevelIsAtEndOfStream { Index: src/OFZIPArchive.m ================================================================== --- src/OFZIPArchive.m +++ src/OFZIPArchive.m @@ -80,12 +80,12 @@ uint64_t _toRead; uint32_t _CRC32; bool _atEndOfStream; } -- (instancetype)initWithStream: (OFStream *)stream - entry: (OFZIPArchiveEntry *)entry; +- (instancetype)of_initWithStream: (OFStream *)stream + entry: (OFZIPArchiveEntry *)entry; @end @interface OFZIPArchive_FileWriteStream: OFStream { OFStream *_stream; @@ -461,12 +461,12 @@ @throw [OFUnsupportedVersionException exceptionWithVersion: version]; } _lastReturnedStream = [[OFZIPArchive_FileReadStream alloc] - initWithStream: _stream - entry: entry]; + of_initWithStream: _stream + entry: entry]; objc_autoreleasePoolPop(pool); return [[_lastReturnedStream retain] autorelease]; } @@ -726,12 +726,12 @@ return true; } @end @implementation OFZIPArchive_FileReadStream -- (instancetype)initWithStream: (OFStream *)stream - entry: (OFZIPArchiveEntry *)entry +- (instancetype)of_initWithStream: (OFStream *)stream + entry: (OFZIPArchiveEntry *)entry { self = [super init]; @try { _stream = [stream retain]; ADDED src/huffman_tree.h Index: src/huffman_tree.h ================================================================== --- src/huffman_tree.h +++ src/huffman_tree.h @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, + * 2018 + * 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 +#include + +#import "macros.h" + +OF_ASSUME_NONNULL_BEGIN + +@class OFStream; + +struct of_huffman_tree { + struct of_huffman_tree *_Nullable leaves[2]; + uint16_t value; +}; + +#ifdef __cplusplus +extern "C" { +#endif +extern struct of_huffman_tree *_Nonnull of_huffman_tree_construct( + uint8_t lengths[_Nonnull], uint16_t count); +extern struct of_huffman_tree *_Nonnull of_huffman_tree_construct_single( + uint16_t value); +extern bool of_huffman_tree_walk(OFStream *_Nullable stream, + bool (*bitReader)(OFStream *_Nullable, uint16_t *_Nonnull, uint8_t), + struct of_huffman_tree *_Nonnull *_Nonnull tree, uint16_t *_Nonnull value); +extern void of_huffman_tree_release(struct of_huffman_tree *_Nonnull tree); +#ifdef __cplusplus +} +#endif + +OF_ASSUME_NONNULL_END ADDED src/huffman_tree.m Index: src/huffman_tree.m ================================================================== --- src/huffman_tree.m +++ src/huffman_tree.m @@ -0,0 +1,145 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, + * 2018 + * 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" + +#include +#include + +#import "huffman_tree.h" + +#import "OFInvalidFormatException.h" +#import "OFOutOfMemoryException.h" + +#define MAX_BIT 15 + +static struct of_huffman_tree * +newTree(void) +{ + struct of_huffman_tree *tree; + + if ((tree = malloc(sizeof(*tree))) == NULL) + @throw [OFOutOfMemoryException + exceptionWithRequestedSize: sizeof(*tree)]; + + tree->leaves[0] = tree->leaves[1] = NULL; + tree->value = 0xFFFF; + + return tree; +} + +static void +insertTree(struct of_huffman_tree *tree, uint16_t code, uint8_t length, + uint16_t value) +{ + while (length > 0) { + uint8_t bit; + + length--; + bit = (code & (1 << length)) >> length; + + if (tree->leaves[bit] == NULL) + tree->leaves[bit] = newTree(); + + tree = tree->leaves[bit]; + } + + tree->value = value; +} + +struct of_huffman_tree * +of_huffman_tree_construct(uint8_t lengths[], uint16_t count) +{ + struct of_huffman_tree *tree; + uint16_t lengthCount[MAX_BIT + 1]; + uint16_t code, maxCode = 0, nextCode[MAX_BIT + 1]; + + memset(&lengthCount, 0, (MAX_BIT + 1) * 2); + + for (uint16_t i = 0; i < count; i++) { + uint8_t length = lengths[i]; + + if OF_UNLIKELY (length > MAX_BIT) + @throw [OFInvalidFormatException exception]; + + if (length > 0) { + lengthCount[length]++; + maxCode = i; + } + } + + code = 0; + for (size_t i = 1; i <= MAX_BIT; i++) { + code = (code + lengthCount[i - 1]) << 1; + nextCode[i] = code; + } + + tree = newTree(); + + for (uint16_t i = 0; i <= maxCode; i++) { + uint8_t length = lengths[i]; + + if (length > 0) + insertTree(tree, nextCode[length]++, length, i); + } + + return tree; +} + +struct of_huffman_tree * +of_huffman_tree_construct_single(uint16_t value) +{ + struct of_huffman_tree *tree = newTree(); + + tree->value = value; + + return tree; +} + +bool +of_huffman_tree_walk(OFStream *stream, + bool (*bitReader)(OFStream *, uint16_t *, uint8_t), + struct of_huffman_tree **tree, uint16_t *value) +{ + struct of_huffman_tree *iter = *tree; + uint16_t bits; + + while (iter->value == 0xFFFF) { + if OF_UNLIKELY (!bitReader(stream, &bits, 1)) { + *tree = iter; + return false; + } + + if OF_UNLIKELY (iter->leaves[bits] == NULL) + @throw [OFInvalidFormatException exception]; + + iter = iter->leaves[bits]; + } + + *value = iter->value; + return true; +} + +void +of_huffman_tree_release(struct of_huffman_tree *tree) +{ + for (uint_fast8_t i = 0; i < 2; i++) + if OF_LIKELY (tree->leaves[i] != NULL) + of_huffman_tree_release(tree->leaves[i]); + + free(tree); +}