shithub: rewise

ref: d687b4ee0c7ac58d9a9e5e50fb1813f47f17681d
dir: /src/inflate.c/

View raw version
/* 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;
}