ref: d687b4ee0c7ac58d9a9e5e50fb1813f47f17681d
dir: /src/inflate.c/
/* This file is part of REWise.
*
* REWise is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* REWise is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
#include <errno.h>
#include "inflate.h"
#include "errors.h"
#include "print.h"
static HuffmanNode * FixedLiteralTree = NULL;
static HuffmanNode * FixedDistanceTree = NULL;
// Constant defined in the PKZIP APPNOTE (5.5.3 Expanding Huffman Codes)
// Also here https://www.rfc-editor.org/rfc/rfc1951#page-13
static unsigned char CODE_LENGTH_ORDER[19] = {
0x10, 0x11, 0x12, 0x00, 0x08, 0x07, 0x09, 0x06, 0x0A, 0x05, 0x0B, 0x04,
0x0C, 0x03, 0x0D, 0x02, 0x0E, 0x01, 0x0F
};
// DEFLATE static dictionary (Bit reduction)
static int LENGTH_CODE_VALUE_OFFSET[286] = {
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000003, 0x00000004, 0x00000005,
0x00000006, 0x00000007, 0x00000008, 0x00000009,
0x0000000A, 0x0000000B, 0x0000000D, 0x0000000F,
0x00000011, 0x00000013, 0x00000017, 0x0000001B,
0x0000001F, 0x00000023, 0x0000002B, 0x00000033,
0x0000003B, 0x00000043, 0x00000053, 0x00000063,
0x00000073, 0x00000083, 0x000000A3, 0x000000C3,
0x000000E3, 0x00000102
};
static unsigned char LENGTH_CODE_VALUE_EXTRA_BITS[286] = {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02,
0x02, 0x03, 0x03, 0x03, 0x03, 0x04, 0x04, 0x04,
0x04, 0x05, 0x05, 0x05, 0x05, 0x00
};
static int DISTANCE_CODE_VALUE_OFFSET[30] = {
0x00000001, 0x00000002, 0x00000003, 0x00000004,
0x00000005, 0x00000007, 0x00000009, 0x0000000D,
0x00000011, 0x00000019, 0x00000021, 0x00000031,
0x00000041, 0x00000061, 0x00000081, 0x000000C1,
0x00000101, 0x00000181, 0x00000201, 0x00000301,
0x00000401, 0x00000601, 0x00000801, 0x00000C01,
0x00001001, 0x00001801, 0x00002001, 0x00003001,
0x00004001, 0x00006001
};
static unsigned char DISTANCE_CODE_VALUE_EXTRA_BITS[30] = {
0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x02, 0x02,
0x03, 0x03, 0x04, 0x04, 0x05, 0x05, 0x06, 0x06,
0x07, 0x07, 0x08, 0x08, 0x09, 0x09, 0x0A, 0x0A,
0x0B, 0x0B, 0x0C, 0x0C, 0x0D, 0x0D
};
/* newHuffmanNode() - Create new Huffman node. This allocates memory and inits
* the new node.
*
* @returns: Pointer to the new Huffman node or NULL on error. */
HuffmanNode * newHuffmanNode(void) {
HuffmanNode * newNode = NULL;
newNode = malloc(sizeof(HuffmanNode));
if (newNode == NULL) {
printError("newHuffmanNode errno: %s\n", strerror(errno));
return NULL;
}
newNode->value = 0xffff;
newNode->childeren[HUFFMAN_LEFT] = NULL;
newNode->childeren[HUFFMAN_RIGHT] = NULL;
newNode->leafes[HUFFMAN_LEFT] = false;
newNode->leafes[HUFFMAN_RIGHT] = false;
return newNode;
}
/* HuffmanAddCode() - Adds new code to a Huffman tree.
*
* @param node : Node to add the code to.
* @param codeLength: The traverse count to the node we want to set the value
* to (count from given 'node').
* @param codeValue : The value to set.
*
* @returns: 'true' on success, 'false' on error. */
bool HuffmanAddCode(HuffmanNode * node, unsigned char codeLength, int codeValue) {
bool result = false;
if (codeLength == 0) {
printError("HuffmanAddCode codeLength == 0\n");
return result;
}
// Left child of current node is not a end node
if (node->leafes[HUFFMAN_LEFT] == false) {
// Add new left node
if (node->childeren[HUFFMAN_LEFT] == NULL) {
HuffmanNode * newNode = newHuffmanNode();
if (newNode == NULL) {
return false;
}
node->childeren[HUFFMAN_LEFT] = newNode;
}
// Left (new) child is a end node
if (codeLength == 1) {
node->leafes[HUFFMAN_LEFT] = true;
node->childeren[HUFFMAN_LEFT]->value = codeValue;
result = true;
}
else {
result = HuffmanAddCode(node->childeren[HUFFMAN_LEFT], codeLength - 1, codeValue);
}
}
if (result == false) {
// Right child of current node is not a end node
if (node->leafes[HUFFMAN_RIGHT] == false) {
// Set left child as a end node ???
node->leafes[HUFFMAN_LEFT] = true;
// Add new right node
if (node->childeren[HUFFMAN_RIGHT] == NULL) {
HuffmanNode * newNode = newHuffmanNode();
if (newNode == NULL) {
return false;
}
node->childeren[HUFFMAN_RIGHT] = newNode;
}
// The new right child is a end node
if (codeLength == 1) {
node->leafes[HUFFMAN_RIGHT] = true;
node->childeren[HUFFMAN_RIGHT]->value = codeValue;
result = true;
}
else {
result = HuffmanAddCode(node->childeren[HUFFMAN_RIGHT], codeLength - 1, codeValue);
}
}
else {
node->leafes[HUFFMAN_RIGHT] = true;
}
}
return result;
}
/* huffmanFreeTree() - Free a Huffman tree.
*
* @param node: Root node of the Huffman tree. */
void huffmanFreeTree(HuffmanNode * node) {
if (node->childeren[HUFFMAN_LEFT] != NULL) {
huffmanFreeTree(node->childeren[HUFFMAN_LEFT]);
node->childeren[HUFFMAN_LEFT] = NULL;
}
if (node->childeren[HUFFMAN_RIGHT] != NULL) {
huffmanFreeTree(node->childeren[HUFFMAN_RIGHT]);
node->childeren[HUFFMAN_RIGHT] = NULL;
}
free(node);
}
/* huffmanInitFixedTrees() - Build fixed DEFLATE Huffman tree.
* NOTE: huffmanFreeFixedTrees() should be called when this has returned true!
**/
bool huffmanInitFixedTrees(void) {
HuffmanNode * literalTree = newHuffmanNode();
if (literalTree == NULL) {
return false;
}
// 256 - 279
for (uint16_t value=256; value < 280; value++) {
if (HuffmanAddCode(literalTree, 7, value) == false) {
huffmanFreeTree(literalTree);
return false;
}
}
// 0 - 143
for (uint16_t value=0; value < 144; value++) {
if (HuffmanAddCode(literalTree, 8, value) == false) {
huffmanFreeTree(literalTree);
return false;
}
}
// 280 - 287
for (uint16_t value=280; value < 288; value++) {
if (HuffmanAddCode(literalTree, 8, value) == false) {
huffmanFreeTree(literalTree);
return false;
}
}
// 144 - 255
for (uint16_t value=144; value < 256; value++) {
if (HuffmanAddCode(literalTree, 9, value) == false) {
huffmanFreeTree(literalTree);
return false;
}
}
HuffmanNode * distanceTree = newHuffmanNode();
if (distanceTree == NULL) {
huffmanFreeTree(literalTree);
return false;
}
// 0 - 31
for (unsigned char value=0; value < 32; value++) {
if (HuffmanAddCode(distanceTree, 5, value) == false) {
huffmanFreeTree(literalTree);
huffmanFreeTree(distanceTree);
return false;
}
}
FixedLiteralTree = literalTree;
FixedDistanceTree = distanceTree;
return true;
}
void huffmanFreeFixedTrees(void) {
huffmanFreeTree(FixedLiteralTree);
huffmanFreeTree(FixedDistanceTree);
FixedLiteralTree = NULL;
FixedDistanceTree = NULL;
}
// forward deceleration
int inflateReadBits(InflateObject * inflateObj, uint8_t bitCount);
// return value larger then 0x11e is error
/* huffmanReadValue() - Keep reading 1 bit until we arrive at a leaf of the
* given 'tree' and return that value.
*
* @param inflateObj: Inflate descriptor.
* @param tree : The Huffman tree for resolving the value.
*
* @returns: The real value, or 0xffffffff on error. */
int huffmanReadValue(InflateObject * inflateObj, HuffmanNode * tree) {
HuffmanNode * node = tree;
// loop until a leaf node has reached
while (node->value == 0xffff) {
int direction = inflateReadBits(inflateObj, 1);
if (direction > 1) {
printError("huffmanReadValue inflateReadBits failed\n");
return 0xffffffff; // error
}
if (node->childeren[direction] == NULL) {
printError("huffmanReadValue the tree is incomplete or invalid bit path "
"requested.\n");
return 0xffffffff; // error
}
node = node->childeren[direction];
}
return node->value;
}
/* inflateInit() - This should be called on every new InflateObject to init it.
*
* @param inflateObj: Inflate descriptor.
* @param inputFile : Valid and open FILE to the input PE file (installer exe),
* this may NOT be NULL!
**/
void inflateInit(InflateObject * inflateObj, FILE * inputFile) {
memset(inflateObj->window , 0x00, sizeof(unsigned char) * WINDOW_SIZE);
memset(inflateObj->chunkBuff, 0x00, sizeof(unsigned char) * CHUNK_SIZE);
inflateObj->bitOffset = 8; // trigger read new byte
inflateObj->windowPosition = 0;
inflateObj->chunkBuffPosition = CHUNK_SIZE; // set to max, to trigger new read
inflateObj->chunkBuffSize = CHUNK_SIZE;
inflateObj->inputFile = inputFile;
inflateObj->outputFile = NULL;
inflateObj->outputSize = 0;
inflateObj->crc32 = CRC32_NEW;
long inputFileOffset = ftell(inputFile); // backup input positions
fseek(inputFile, 0L, SEEK_END); // seek to end
inflateObj->inputFileSize = ftell(inputFile); // store file size
fseek(inputFile, inputFileOffset, SEEK_SET); // restore input position
}
/* inflateNew() - Prepare the 'InflateObject' for a new file to extract. This
* should be called before trying to extract a file.
*
* @param inflateObj: Inflate descriptor.
* @param outputFile: Should be a valid and open FILE to actually inflate to a
* output file. This may be NULL to not write the inflated
* data to a file. */
void inflateNew(InflateObject * inflateObj, FILE * outputFile) {
inflateObj->bitOffset = 8; // trigger read new byte
inflateObj->windowPosition = 0;
inflateObj->chunkBuffPosition = CHUNK_SIZE; // set to max, to trigger new read
inflateObj->chunkBuffSize = CHUNK_SIZE;
inflateObj->outputFile = outputFile;
inflateObj->outputSize = 0;
inflateObj->crc32 = CRC32_NEW;
}
/* inflateRead() - Read a byte from the inflate chunk buffer.
*
* @returns: A value greater then 0xff on error, else it will return the value.
**/
uint16_t inflateRead(InflateObject * inflateObj) {
// Read new chunk
if (inflateObj->chunkBuffPosition >= inflateObj->chunkBuffSize) {
// End Of File
if (ftell(inflateObj->inputFile) == inflateObj->inputFileSize) {
printError("inflateRead EOF.\n");
return 0xffff;
}
// Last chunk of the inputFile is smaller then 16k, adjust the
// inputBuffSize
if (inflateObj->chunkBuffPosition > (inflateObj->inputFileSize - ftell(inflateObj->inputFile))) {
inflateObj->chunkBuffSize = inflateObj->inputFileSize - ftell(inflateObj->inputFile);
}
// Read next chunk
REWError status = readBytesInto(inflateObj->inputFile, inflateObj->chunkBuff, inflateObj->chunkBuffSize);
if (status != REWERR_OK) {
// failed to read next chunk
printError("inflateRead failed to read next chunk.\n");
return 0xffff;
}
inflateObj->chunkBuffPosition = 0;
}
uint16_t result = (uint16_t)inflateObj->chunkBuff[inflateObj->chunkBuffPosition];
inflateObj->chunkBuffPosition++;
return result;
}
/* inflateReadBits() - Reads 'bitCount' of bits from the chunk buffer.
*
* @param inflateObj: Inflate descriptor.
* @param bitCount : The amount of bits to read. (TODO define maximum bitCount)
*
* @returns: The value on success, 0xffffffff on error. */
int inflateReadBits(InflateObject * inflateObj, uint8_t bitCount) {
int result = 0;
int resultOffset = 0;
while (bitCount > 0) {
// Read new byte into buffer
if (inflateObj->bitOffset == 8) {
uint16_t readResult = inflateRead(inflateObj);
if (readResult > 0xff) {
// inflateRead error
return 0xffffffff;
}
inflateObj->bitBuff = (unsigned char)readResult;
inflateObj->bitOffset = 0;
}
int mask = 1 << inflateObj->bitOffset;
if ((inflateObj->bitBuff & mask)) {
result |= 1 << resultOffset;
}
inflateObj->bitOffset++;
bitCount--;
resultOffset++;
}
return result;
}
/* huffmanReadDynamicTrees() - Read and build dynamic Huffman trees.
*
* @param inflateObj: Inflate descriptor.
* @param hlit : Literal/Length codes
* @param hdist : Distance codes
* @param hclen : Code Length codes
* @param literalTree : Literal tree destination on success, this should be
* freed with huffmanFreeTree() on success.
* @param distanceTree: Distance tree destination on success, this should be
* freed with huffmanFreeTree() on success.
*
* @returns: 'true' on success, 'false' on error. */
bool huffmanReadDynamicTrees(InflateObject * inflateObj, int hlit, int hdist,
int hclen, HuffmanNode ** literalTree,
HuffmanNode ** distanceTree) {
bool result;
int repeatAmount;
unsigned char repeatValue;
unsigned char maxCodeLength, maxCodeLength2;
unsigned char codeLengths[19];
unsigned char codeLengthAlphabet[318];
unsigned char codeLength;
int codeValue;
int readBitsResult;
memset(codeLengths, 0x00, sizeof(unsigned char) * 19);
memset(codeLengthAlphabet, 0x00, sizeof(unsigned char) * 318);
maxCodeLength = 0;
// Read codeLengths
for (uint16_t i=0; i < hclen; i++) {
readBitsResult = inflateReadBits(inflateObj, 3);
if (readBitsResult == 0xffffffff) {
// inflateReadBits error
printError("Failed to read dynamic trees.\n");
return false;
}
codeLength = (unsigned char)readBitsResult;
if (codeLength > maxCodeLength) {
maxCodeLength = codeLength;
}
codeLengths[CODE_LENGTH_ORDER[i]] = codeLength;
}
// Build codeLengthTree
HuffmanNode * codeLengthTree = newHuffmanNode();
if (codeLengthTree == NULL) {
printError("huffmanReadDynamicTrees failed to build dynamic code length "
"tree.\n");
printError("huffmanReadDynamicTrees errno: %s\n", strerror(errno));
return false;
}
result = false;
// 1 - 16
for (codeLength = 0x01; codeLength < 0x10; codeLength++) {
// 0 - 18
for (codeValue = 0x00; codeValue < 0x13; codeValue++) {
if (codeLength == codeLengths[codeValue]) {
result = HuffmanAddCode(codeLengthTree, codeLength, codeValue);
}
}
}
if (result == false) {
huffmanFreeTree(codeLengthTree);
printError("huffmanReadDynamicTrees failed to build dynamic code length "
"tree.\n");
return false;
}
if (maxCodeLength == 0) {
maxCodeLength++;
}
result = !HuffmanAddCode(codeLengthTree, maxCodeLength, 0);
if (result == false) {
huffmanFreeTree(codeLengthTree);
printError("huffmanReadDynamicTrees ailed to build dynamic code length "
"tree. It has nodes without end-node.\n");
return false;
}
// Build alphabet
repeatAmount = 0;
repeatValue = 0;
maxCodeLength = 0;
maxCodeLength2 = 0;
for (codeValue=0; codeValue < (int)(hlit + hdist); codeValue++) {
if (repeatAmount == 0) {
// read and decode codeLength
codeLength = (unsigned char)huffmanReadValue(inflateObj, codeLengthTree);
if (codeLength < 0x10) {
codeLengthAlphabet[codeValue] = codeLength;
// Update maxBits/maxBits2
if (codeValue < hlit) {
if (codeLength > maxCodeLength) {
maxCodeLength = codeLength;
}
}
else {
if (codeLength > maxCodeLength2) {
maxCodeLength2 = codeLength;
}
}
}
else if (codeLength == 0x10) {
readBitsResult = inflateReadBits(inflateObj, 2);
if (readBitsResult == 0xffffffff) {
printError("Failed to read dynamic trees.\n");
return false;
}
repeatAmount = 0x02 + readBitsResult;
repeatValue = codeLengthAlphabet[codeValue - 0x01];
codeLengthAlphabet[codeValue] = repeatValue;
}
else if (codeLength == 0x11) {
readBitsResult = inflateReadBits(inflateObj, 3);
if (readBitsResult == 0xffffffff) {
printError("Failed to read dynamic trees.\n");
return false;
}
repeatAmount = 0x02 + readBitsResult;
repeatValue = 0;
codeLengthAlphabet[codeValue] = repeatValue;
}
else if (codeLength == 0x12) {
readBitsResult = inflateReadBits(inflateObj, 7);
if (readBitsResult == 0xffffffff) {
printError("Failed to read dynamic trees.\n");
return false;
}
repeatAmount = 0x0A + readBitsResult;
repeatValue = 0;
codeLengthAlphabet[codeValue] = repeatValue;
}
}
else {
codeLengthAlphabet[codeValue] = repeatValue;
repeatAmount--;
}
}
// free the codeLengthTree, we don't need it anymore.
huffmanFreeTree(codeLengthTree);
// build literal tree
HuffmanNode * litTree = newHuffmanNode();
if (litTree == NULL) {
printError("huffmanReadDynamicTrees failed to allocate literalTree.\n");
printError("huffmanReadDynamicTrees errno: %s\n", strerror(errno));
return false;
}
for (codeLength=0x01; codeLength < 0x10; codeLength++) {
for (codeValue=0; codeValue < hlit; codeValue++) {
if (codeLength == codeLengthAlphabet[codeValue]) {
result = HuffmanAddCode(litTree, codeLength, codeValue);
}
}
}
if (result == true) {
if (maxCodeLength == 0) {
maxCodeLength++;
}
result = !HuffmanAddCode(litTree, maxCodeLength, 0);
if (result == false) {
huffmanFreeTree(litTree);
printError("huffmanReadDynamicTrees failed to build dynamic literal "
"tree (1). It has a open branch without leaf?\n");
return false;
}
}
else {
huffmanFreeTree(litTree);
printError("huffmanReadDynamicTrees failed to build dynamic literal tree "
"(2).\n");
return false;
}
// build distance tree
HuffmanNode * distTree = newHuffmanNode();
if (distTree == NULL) {
printError("huffmanReadDynamicTrees failed to allocate distanceTree.\n");
printError("huffmanReadDynamicTrees errno: %s\n", strerror(errno));
return false;
}
for (codeLength=0x01; codeLength < 0x10; codeLength++) {
for (codeValue=0; codeValue < hdist; codeValue++) {
if (codeLength == codeLengthAlphabet[codeValue + hlit]) {
result = HuffmanAddCode(distTree, codeLength, codeValue);
}
}
}
if (result == true) {
if (maxCodeLength2 == 0) {
maxCodeLength2++;
}
result = !HuffmanAddCode(distTree, maxCodeLength2, 0);
if (result == false) {
huffmanFreeTree(litTree);
huffmanFreeTree(distTree);
printError("huffmanReadDynamicTrees failed to build dynamic distance "
"tree (1).\n");
return false;
}
}
else {
huffmanFreeTree(litTree);
huffmanFreeTree(distTree);
printError("huffmanReadDynamicTrees failed to build dynamic distance tree "
"(2).\n");
return false;
}
*literalTree = litTree;
*distanceTree = distTree;
return true;
}
#ifdef REWISE_DEV_DEBUG
void inflateInitStaticTables(void) {
int lengthOffset = 3;
unsigned char lengthExtraBits = 0;
int distanceOffset = 1;
unsigned char distanceExtraBits = 0;
LENGTH_CODE_VALUE_OFFSET[285] = 258; // 258 = 0x102
LENGTH_CODE_VALUE_EXTRA_BITS[285] = 0;
for (unsigned char pos=0; pos < 30; pos++) {
// increment number of extra bits for length code table every 4th value
if (pos >= 0x08 && !(pos & 0x03)) {
lengthExtraBits++;
}
// increment number of extra bits for distance code table every 2nd value
if (pos >= 0x04 && !(pos & 0x01)) {
distanceExtraBits++;
}
// for pos<0x1c put value entry into length code table
if (pos < 0x1c) {
LENGTH_CODE_VALUE_OFFSET[pos + 0x101] = lengthOffset;
LENGTH_CODE_VALUE_EXTRA_BITS[pos + 0x101] = lengthExtraBits;
}
// put value entry into distance code table
DISTANCE_CODE_VALUE_OFFSET[pos] = distanceOffset;
DISTANCE_CODE_VALUE_EXTRA_BITS[pos] = distanceExtraBits;
// increment length and distance code values
lengthOffset += (1 << lengthExtraBits);
distanceOffset += (1 << distanceExtraBits);
}
}
void inflatePrintStaticTables(void) {
uint8_t colCount;
colCount = 4;
printf("LENGTH_CODE_VALUE_OFFSET\n");
for (uint32_t i=0; i<286; i++) {
printf("0x%08X", LENGTH_CODE_VALUE_OFFSET[i]);
uint8_t colMod = (i+1) % colCount;
if (i == 285) { printf("\n"); }
else if (colMod) { printf(", "); }
else { printf(",\n"); }
}
colCount = 8;
printf("\n");
printf("LENGTH_CODE_VALUE_EXTRA_BITS\n");
for (uint32_t i=0; i<286; i++) {
printf("0x%02X", LENGTH_CODE_VALUE_EXTRA_BITS[i]);
if (i == 285) { printf("\n"); }
else if ((i+1) % colCount) { printf(", "); }
else { printf(",\n"); }
}
colCount = 4;
printf("\n");
printf("DISTANCE_CODE_VALUE_OFFSET\n");
for (uint32_t i=0; i<30; i++) {
printf("0x%08X", DISTANCE_CODE_VALUE_OFFSET[i]);
if (i == 29) { printf("\n"); }
else if ((i+1) % colCount) { printf(", "); }
else { printf(",\n"); }
}
colCount = 8;
printf("\n");
printf("DISTANCE_CODE_VALUE_EXTRA_BITS\n");
for (uint32_t i=0; i<30; i++) {
printf("0x%02X", DISTANCE_CODE_VALUE_EXTRA_BITS[i]);
if (i == 29) { printf("\n"); }
else if ((i+1) % colCount) { printf(", "); }
else { printf(",\n"); }
}
}
#endif
/* inflateWriteOutput() - Writes the content of the sliding window to the
* 'InflateObject->outputFile' when it is not 'NULL'.
*
* It will also keep track of the total number of bytes
* written to this file and update the CRC32.
*
* This does not reset the sliding window position, the
* caller is responsible for that when this returns
* 'true'.
*
* @param inflateObj: Inflate descriptor.
* @param size : Amount of bytes in the sliding window to write.
*
* @returns: 'true' on success, 'false' on error. */
bool inflateWriteOutput(InflateObject * inflateObj, uint32_t size) {
// Write to output file
if (inflateObj->outputFile != NULL) {
size_t noWritten = fwrite(inflateObj->window, sizeof(unsigned char),
(size_t)size, inflateObj->outputFile);
if (noWritten != (size_t)size) {
// Failed to write to file, out of disk space or something got corrupted.
printError("Failed to write to file, only wrote %ld of %ld bytes. "
"Out of disk space?\n", noWritten, size);
return false;
}
}
inflateObj->outputSize += (long)size;
// Update CRC32
inflateObj->crc32 = crc32Update(inflateObj->crc32, inflateObj->window, size);
return true;
}
/* inflateOutputByte() - Appends the given 'byte' to the sliding window, when
* the sliding window is full it will output the sliding
* window to 'inflateObj->outputFile' (when it isn't
* 'NULL') and resets the sliding window.
*
* @param inflateObj: Inflate descriptor.
* @param byte : The 'byte' to output.
*
* @returns: 'true' on success, 'false' on error. */
bool inflateOutputByte(InflateObject * inflateObj, unsigned char byte) {
inflateObj->window[inflateObj->windowPosition] = byte;
inflateObj->windowPosition++;
if (inflateObj->windowPosition == WINDOW_SIZE) {
if (inflateWriteOutput(inflateObj, WINDOW_SIZE) == false) {
return false;
}
inflateObj->windowPosition = 0;
}
return true;
}
/* inflateCopyBytes() - Copy 'codeLength' amount of bytes (with 'codeDistance'
* offset) from the sliding window to the end of the
* sliding window.
* @param inflateObj : Inflate descriptor.
* @param codeDistance: Offset from the end of the current sliding window.
* @param codeLength : Amount of bytes to copy and append to the end of the
* current sliding window.
*
* @returns: 'true' on success, 'false' on error. */
bool inflateCopyBytes(InflateObject * inflateObj, int codeDistance,
int codeLength)
{
while (codeLength > 0) {
unsigned char byte = inflateObj->window[
(inflateObj->windowPosition + WINDOW_SIZE - codeDistance) & 0x7fff];
if (inflateOutputByte(inflateObj, byte) == false) {
return false;
}
codeLength--;
}
return true;
}
/* inflateNext() - Inflate next file.
*
* @returns: 'true' on success, 'false' on error. */
bool inflateNext(InflateObject * inflateObj) {
unsigned char lastBlock;
unsigned char blockType;
int hclen;
int hdist;
int hlit;
// TODO just for DEBUG
inflateObj->deflatedStart = ftell(inflateObj->inputFile);
printDebug("deflatedStart: %08lX\n", inflateObj->deflatedStart);
lastBlock = 0;
while (lastBlock == 0) {
// read lastBlock
int readBitsResult = inflateReadBits(inflateObj, 1);
if (readBitsResult == 0xffffffff) {
return false;
}
lastBlock = (unsigned char)readBitsResult;
// read blockType
readBitsResult = inflateReadBits(inflateObj, 2);
if (readBitsResult == 0xffffffff) {
return false;
}
blockType = (unsigned char)readBitsResult;
if (blockType == BTYPE_UNCOMPRESSED) {
// Make sure we start on a fresh byte (aligned)
inflateObj->bitOffset = 8;
hclen = inflateRead(inflateObj) + (inflateRead(inflateObj) << 8);
hdist = inflateRead(inflateObj) + (inflateRead(inflateObj) << 8);
if ((hclen ^ hdist) != 0xffff) {
printError("Code-length or code-distance invalid! 0x%04X hclen: 0x%02X hdist: 0x%02X\n", (hclen ^ hdist), hclen, hdist);
return false;
}
while (hclen > 0) {
// read hlit
uint16_t readResultHlit = inflateRead(inflateObj);
if (readResultHlit > 255) {
return false;
}
//hlit = (unsigned char)readResult;
if (inflateOutputByte(inflateObj, (unsigned char)readResultHlit) == false) {
return false;
}
hclen--;
}
}
else
if (blockType == BTYPE_FIXED) {
hlit = 0;
while (hlit != 0x100) {
hlit = huffmanReadValue(inflateObj, FixedLiteralTree);
if (hlit < 0x100) {
if (inflateOutputByte(inflateObj, (unsigned char)hlit) == false) {
return false;
}
}
else
if (hlit == 0x100) {
break;
}
else
if (hlit < 0x11e) {
// Read code length extra bits
readBitsResult = inflateReadBits(inflateObj,
LENGTH_CODE_VALUE_EXTRA_BITS[hlit]);
if (readBitsResult == 0xffffffff) {
// inflateReadBits error
printError("Failed to read fixed length extra bits.\n");
return false;
}
int codeLength = LENGTH_CODE_VALUE_OFFSET[hlit] + readBitsResult;
int codeDistance = huffmanReadValue(inflateObj, FixedDistanceTree);
if (codeDistance > 0x1d) {
printError("Unexpected code distance 0x%08X\n", codeDistance);
return false;
}
// Read code distance extra bits
readBitsResult = inflateReadBits(inflateObj,
DISTANCE_CODE_VALUE_EXTRA_BITS[codeDistance]);
if (readBitsResult == 0xffffffff) {
printError("Failed to read fixed distance extra bits.\n");
return false;
}
codeDistance = DISTANCE_CODE_VALUE_OFFSET[codeDistance] + readBitsResult;
if (inflateCopyBytes(inflateObj, codeDistance, codeLength) == false) {
return false;
}
}
else {
printError("Unexpected literal 0x%08X\n", hlit);
return false;
}
}
}
else
if (blockType == BTYPE_DYNAMIC) {
// Read hlit
readBitsResult = inflateReadBits(inflateObj, 5);
if (readBitsResult == 0xffffffff) {
printError("Failed to read dynamic hlit bits.\n");
return false;
}
hlit = readBitsResult + 0x101;
// Read hdist
readBitsResult = inflateReadBits(inflateObj, 5);
if (readBitsResult == 0xffffffff) {
printError("Failed to read dynamic hdist bits.\n");
return false;
}
hdist = readBitsResult + 0x01;
// Read hclen
readBitsResult = inflateReadBits(inflateObj, 4);
if (readBitsResult == 0xffffffff) {
printError("Failed to read dynamic hclen bits.\n");
return false;
}
hclen = readBitsResult + 0x04;
HuffmanNode * literalTree = NULL;
HuffmanNode * distanceTree = NULL;
if (huffmanReadDynamicTrees(inflateObj, hlit, hdist, hclen, &literalTree,
&distanceTree) == false) {
printError("Failed to build dynamic trees\n");
return false;
}
while (hlit != 0x100) {
hlit = huffmanReadValue(inflateObj, literalTree);
if (hlit < 0x100) {
if (inflateOutputByte(inflateObj, (unsigned char)hlit) == false) {
huffmanFreeTree(literalTree);
huffmanFreeTree(distanceTree);
return false;
}
}
else
if (hlit == 0x100) {
break;
}
else
if (hlit < 0x11e) {
// Read code value extra bits
readBitsResult = inflateReadBits(inflateObj, LENGTH_CODE_VALUE_EXTRA_BITS[hlit]);
if (readBitsResult == 0xffffffff) {
huffmanFreeTree(literalTree);
huffmanFreeTree(distanceTree);
printError("Failed to read dynamic code value extra bits.\n");
return false;
}
int codeLength = LENGTH_CODE_VALUE_OFFSET[hlit] + readBitsResult;
int codeDistance = huffmanReadValue(inflateObj, distanceTree);
// Read distance value extra bits
readBitsResult = inflateReadBits(inflateObj, DISTANCE_CODE_VALUE_EXTRA_BITS[codeDistance]);
if (readBitsResult == 0xffffffff) {
huffmanFreeTree(literalTree);
huffmanFreeTree(distanceTree);
printError("Failed to read dynamic distance value extra bits.\n");
return false;
}
codeDistance = DISTANCE_CODE_VALUE_OFFSET[codeDistance] + readBitsResult;
if (inflateCopyBytes(inflateObj, codeDistance, codeLength) == false) {
huffmanFreeTree(literalTree);
huffmanFreeTree(distanceTree);
return false;
}
}
else {
huffmanFreeTree(literalTree);
huffmanFreeTree(distanceTree);
printError("Unexpected literal 0x%08X\n", hlit);
return false;
}
}
// free dynamic trees
huffmanFreeTree(literalTree);
huffmanFreeTree(distanceTree);
}
else {
printError("Unknown block type! '%X'\n", blockType);
return false;
}
}
// Write leftover (smaller then WINDOW_SIZE)
if (inflateObj->windowPosition > 0) {
if (inflateWriteOutput(inflateObj, inflateObj->windowPosition) == false) {
return false;
}
}
return true;
}
/* inflateExtractNextFile() - Inflate helper that opens/creates the output file
* when 'outputFilePath' is not 'NULL'. This also
* reads and checks the CRC32. The input file offset
* should be EOF or the beginning of the next
* deflated file data after this returns 'true'.
*
* @param inflateObj : Inflate descriptor.
* @param outputFilePath: File path to extract the data to, this may be 'NULL'
* to not extract to a file (for just verify crc32 or to
* skip a file).
*
* @returns: 'true' on success, 'false' on error. */
bool inflateExtractNextFile(InflateObject * inflateObj,
const char * outputFilePath) {
FILE * outputFp;
bool result;
uint32_t newCrc;
if (outputFilePath != NULL) {
outputFp = fopen(outputFilePath, "wb");
if (outputFp == NULL) {
printError("Failed to open output file '%s'\n", outputFilePath);
return false;
}
}
else {
outputFp = NULL;
}
inflateNew(inflateObj, outputFp);
result = inflateNext(inflateObj);
// close output file when there is any
if (outputFp != NULL) {
fclose(outputFp);
}
if (result == false) {
return false;
}
inflateObj->crc32 = crc32Finalize(inflateObj->crc32);
// Seek to the end of the deflate data since we probably overshot due to the
// chunk buffer.
if (fseek(inflateObj->inputFile, ftell(inflateObj->inputFile) -
inflateObj->chunkBuffSize +
inflateObj->chunkBuffPosition, SEEK_SET) != 0)
{
printError("Failed to seek back to deflate end.\n");
return false;
}
if (readUInt32(inflateObj->inputFile, &newCrc) != REWERR_OK) {
printError("Failed to read CRC32\n");
return false;
}
if (inflateObj->crc32 != newCrc) {
// deflated data should be 8 byte aligned?
// NOTE: largest offset I have seen is 1. Probably because of the bits read.
uint8_t attempt;
for (attempt=0; attempt<8; attempt++) {
if (fseek(inflateObj->inputFile, -3l, SEEK_CUR) != 0) {
printError("Failed to seek to next crc attempt.\n");
return false;
}
if (readUInt32(inflateObj->inputFile, &newCrc) != REWERR_OK) {
printError("Failed to read CRC32 attempt\n");
return false;
}
if (inflateObj->crc32 == newCrc) {
break;
}
}
if (inflateObj->crc32 != newCrc) {
printError("CRC32 mismatch\n");
return false;
}
printDebug("crc32 attempt %d\n", attempt);
}
return true;
}