/*

LodePNG version 20080927

Copyright (c) 2005-2008 Lode Vandevenne

This software is provided 'as-is', without any express or implied

warranty. In no event will the authors be held liable for any damages

arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,

including commercial applications, and to alter it and redistribute it

freely, subject to the following restrictions:

    1. The origin of this software must not be misrepresented; you must not

    claim that you wrote the original software. If you use this software

    in a product, an acknowledgment in the product documentation would be

    appreciated but is not required.

    2. Altered source versions must be plainly marked as such, and must not be

    misrepresented as being the original software.

    3. This notice may not be removed or altered from any source

    distribution.

*/

/*

The manual and changelog can be found in the header file "lodepng.h"

You are free to name this file lodepng.cpp or lodepng.c depending on your usage.

*/

#include "lodepng.h"

#include "portable.h"

#define USE_BRUTE_FORCE_ENCODING 1

#define VERSION_STRING "20080927"

/* ////////////////////////////////////////////////////////////////////////// */

/* / Tools For C                                                            / */

/* ////////////////////////////////////////////////////////////////////////// */

/*

About these tools (vector, uivector, ucvector and string):

-LodePNG was originally written in C++. The vectors replace the std::vectors that were used in the C++ version.

-The string tools are made to avoid problems with compilers that declare things like strncat as deprecated.

-They're not used in the interface, only internally in this file, so all their functions are made static.

*/

//--------------------------------------------------------------------------------------------

/*LodePNG_chunk functions: These functions need as input a large enough amount of allocated memory.*/

static unsigned LodePNG_chunk_length(const unsigned char* chunk); /*get the length of the data of the chunk. Total chunk length has 12 bytes more.*/

static void LodePNG_chunk_generate_crc(unsigned char* chunk); /*generates the correct CRC from the data and puts it in the last 4 bytes of the chunk*/

/*add chunks to out buffer. It reallocs the buffer to append the data. returns error code*/

static unsigned LodePNG_create_chunk(unsigned char** out, size_t* outlength, unsigned length, const char* type, const unsigned char* data); /*appends new chunk to out. Returns pointer to start of appended chunk, or NULL if error happened; may change memory address of out buffer*/

static void LodePNG_InfoColor_init(LodePNG_InfoColor* info);

static void LodePNG_InfoColor_cleanup(LodePNG_InfoColor* info);

static unsigned LodePNG_InfoColor_copy(LodePNG_InfoColor* dest, const LodePNG_InfoColor* source);

/*Use these functions instead of allocating palette manually*/

static void LodePNG_InfoColor_clearPalette(LodePNG_InfoColor* info);

/*additional color info*/

static unsigned LodePNG_InfoColor_getBpp(const LodePNG_InfoColor* info);      /*bits per pixel*/

static unsigned LodePNG_InfoColor_isGreyscaleType(const LodePNG_InfoColor* info); /*is it a greyscale type? (colorType 0 or 4)*/

static unsigned LodePNG_InfoColor_isAlphaType(const LodePNG_InfoColor* info);     /*has it an alpha channel? (colorType 2 or 6)*/

static void LodePNG_InfoPng_init(LodePNG_InfoPng* info);

static void LodePNG_InfoPng_cleanup(LodePNG_InfoPng* info);

static unsigned LodePNG_InfoPng_copy(LodePNG_InfoPng* dest, const LodePNG_InfoPng* source);

static void LodePNG_InfoRaw_init(LodePNG_InfoRaw* info);

static void LodePNG_InfoRaw_cleanup(LodePNG_InfoRaw* info);

static unsigned LodePNG_InfoRaw_copy(LodePNG_InfoRaw* dest, const LodePNG_InfoRaw* source);

/*

LodePNG_convert: Converts from any color type to 24-bit or 32-bit (later maybe more supported). return value = LodePNG error code

The out buffer must have (w * h * bpp + 7) / 8, where bpp is the bits per pixel of the output color type (LodePNG_InfoColor_getBpp)

*/

static unsigned LodePNG_convert(unsigned char* out, const unsigned char* in, LodePNG_InfoColor* infoOut, LodePNG_InfoColor* infoIn, unsigned w, unsigned h);

static void LodeZlib_DeflateSettings_init(LodeZlib_DeflateSettings* settings);

/* ////////////////////////////////////////////////////////////////////////// */

/* LodeFlate & LodeZlib                                                       */

/* ////////////////////////////////////////////////////////////////////////// */

/*This function reallocates the out buffer and appends the data.

Either, *out must be NULL and *outsize must be 0, or, *out must be a valid buffer and *outsize its size in bytes.*/

//unsigned LodeZlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in, size_t insize, const LodeZlib_DeflateSettings* settings);

//--------------------------------------------------------------------------------------------

typedef struct vector /*this one is used only by the deflate compressor*/

{

  void* data;

  size_t size; /*in groups of bytes depending on type*/

  size_t allocsize; /*in bytes*/

  unsigned typesize; /*sizeof the type you store in data*/

} vector;

static unsigned vector_resize(vector* p, size_t size) /*returns 1 if success, 0 if failure ==> nothing done*/

{

  if(size * p->typesize > p->allocsize)

  {

    size_t newsize = size * p->typesize * 2;

    void* data = realloc(p->data, newsize);

    if(data)

    {

      p->allocsize = newsize;

      p->data = data;

      p->size = size;

    }

    else return 0;

  }

  else p->size = size;

  return 1;

}

static unsigned vector_resized(vector* p, size_t size, void dtor(void*)) /*resize and use destructor on elements if it gets smaller*/

{

  size_t i;

  if(size < p->size) for(i = size; i < p->size; i++) dtor(&((char*)(p->data))[i * p->typesize]);

  return vector_resize(p, size);

}

static void vector_cleanup(void* p)

{

  ((vector*)p)->size = ((vector*)p)->allocsize = 0;

  free(((vector*)p)->data);

  ((vector*)p)->data = NULL;

}

static void vector_cleanupd(vector* p, void dtor(void*)) /*clear and use destructor on elements*/

{

  vector_resized(p, 0, dtor);

  vector_cleanup(p);

}

static void vector_init(vector* p, unsigned typesize)

{

  p->data = NULL;

  p->size = p->allocsize = 0;

  p->typesize = typesize;

}

static void vector_swap(vector* p, vector* q) /*they're supposed to have the same typesize*/

{

  size_t tmp;

  void* tmpp;

  tmp = p->size; p->size = q->size; q->size = tmp;

  tmp = p->allocsize; p->allocsize = q->allocsize; q->allocsize = tmp;

  tmpp = p->data; p->data = q->data; q->data = tmpp;

}

static void* vector_get(vector* p, size_t index)

{

  return &((char*)p->data)[index * p->typesize];

}

/* /////////////////////////////////////////////////////////////////////////// */

typedef struct uivector

{

  unsigned* data;

  size_t size; /*size in number of unsigned longs*/

  size_t allocsize; /*allocated size in bytes*/

} uivector;

static void uivector_cleanup(void* p)

{

  ((uivector*)p)->size = ((uivector*)p)->allocsize = 0;

  free(((uivector*)p)->data);

  ((uivector*)p)->data = NULL;

}

static unsigned uivector_resize(uivector* p, size_t size) /*returns 1 if success, 0 if failure ==> nothing done*/

{

  if(size * sizeof(unsigned) > p->allocsize)

  {

    size_t newsize = size * sizeof(unsigned) * 2;

    void* data = realloc(p->data, newsize);

    if(data)

    {

      p->allocsize = newsize;

      p->data = (unsigned*)data;

      p->size = size;

    }

    else return 0;

  }

  else p->size = size;

  return 1;

}

static unsigned uivector_resizev(uivector* p, size_t size, unsigned value) /*resize and give all new elements the value*/

{

  size_t oldsize = p->size, i;

  if(!uivector_resize(p, size)) return 0;

  for(i = oldsize; i < size; i++) p->data[i] = value;

  return 1;

}

static void uivector_init(uivector* p)

{

  p->data = NULL;

  p->size = p->allocsize = 0;

}

static unsigned uivector_push_back(uivector* p, unsigned c) /*returns 1 if success, 0 if failure ==> nothing done*/

{

  if(!uivector_resize(p, p->size + 1)) return 0;

  p->data[p->size - 1] = c;

  return 1;

}

static unsigned uivector_copy(uivector* p, const uivector* q) /*copy q to p, returns 1 if success, 0 if failure ==> nothing done*/

{

  size_t i;

  if(!uivector_resize(p, q->size)) return 0;

  for(i = 0; i < q->size; i++) p->data[i] = q->data[i];

  return 1;

}

static void uivector_swap(uivector* p, uivector* q)

{

  size_t tmp;

  unsigned* tmpp;

  tmp = p->size; p->size = q->size; q->size = tmp;

  tmp = p->allocsize; p->allocsize = q->allocsize; q->allocsize = tmp;

  tmpp = p->data; p->data = q->data; q->data = tmpp;

}

/* /////////////////////////////////////////////////////////////////////////// */

typedef struct ucvector

{

  unsigned char* data;

  size_t size; /*used size*/

  size_t allocsize; /*allocated size*/

} ucvector;

static void ucvector_cleanup(void* p)

{

  ((ucvector*)p)->size = ((ucvector*)p)->allocsize = 0;

  free(((ucvector*)p)->data);

  ((ucvector*)p)->data = NULL;

}

static unsigned ucvector_resize(ucvector* p, size_t size) /*returns 1 if success, 0 if failure ==> nothing done*/

{

  if(size * sizeof(unsigned) > p->allocsize)

  {

    size_t newsize = size * sizeof(unsigned) * 2;

    void* data = realloc(p->data, newsize);

    if(data)

    {

      p->allocsize = newsize;

      p->data = (unsigned char*)data;

      p->size = size;

    }

    else return 0; /*error: not enough memory*/

  }

  else p->size = size;

  return 1;

}

static void ucvector_init(ucvector* p)

{

  p->data = NULL;

  p->size = p->allocsize = 0;

}

/*you can both convert from vector to buffer&size and vica versa*/

static void ucvector_init_buffer(ucvector* p, unsigned char* buffer, size_t size)

{

  p->data = buffer;

  p->allocsize = p->size = size;

}

static unsigned ucvector_push_back(ucvector* p, unsigned char c) /*returns 1 if success, 0 if failure ==> nothing done*/

{

  if(!ucvector_resize(p, p->size + 1)) return 0;

  p->data[p->size - 1] = c;

  return 1;

}

/* ////////////////////////////////////////////////////////////////////////// */

/* / Reading and writing single bits and bytes from/to stream for Deflate   / */

/* ////////////////////////////////////////////////////////////////////////// */

static void addBitToStream(size_t* bitpointer, ucvector* bitstream, unsigned char bit)

{

  if((*bitpointer) % 8 == 0) ucvector_push_back(bitstream, 0); /*add a new byte at the end*/

  (bitstream->data[bitstream->size - 1]) |= (bit << ((*bitpointer) & 0x7)); /*earlier bit of huffman code is in a lesser significant bit of an earlier byte*/

  (*bitpointer)++;

}

static void addBitsToStream(size_t* bitpointer, ucvector* bitstream, unsigned value, size_t nbits)

{

  size_t i;

  for(i = 0; i < nbits; i++) addBitToStream(bitpointer, bitstream, (unsigned char)((value >> i) & 1));

}

static void addBitsToStreamReversed(size_t* bitpointer, ucvector* bitstream, unsigned value, size_t nbits)

{

  size_t i;

  for(i = 0; i < nbits; i++) addBitToStream(bitpointer, bitstream, (unsigned char)((value >> (nbits - 1 - i)) & 1));

}

/* ////////////////////////////////////////////////////////////////////////// */

/* / Deflate - Huffman                                                      / */

/* ////////////////////////////////////////////////////////////////////////// */

#define FIRST_LENGTH_CODE_INDEX 257

#define LAST_LENGTH_CODE_INDEX 285

#define NUM_DEFLATE_CODE_SYMBOLS 288 /*256 literals, the end code, some length codes, and 2 unused codes*/

#define NUM_DISTANCE_SYMBOLS 32 /*the distance codes have their own symbols, 30 used, 2 unused*/

#define NUM_CODE_LENGTH_CODES 19 /*the code length codes. 0-15: code lengths, 16: copy previous 3-6 times, 17: 3-10 zeros, 18: 11-138 zeros*/

static const unsigned LENGTHBASE[29] /*the base lengths represented by codes 257-285*/

  = {3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};

static const unsigned LENGTHEXTRA[29] /*the extra bits used by codes 257-285 (added to base length)*/

  = {0, 0, 0, 0, 0, 0, 0,  0,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,  4,  4,  4,   4,   5,   5,   5,   5,   0};

static const unsigned DISTANCEBASE[30] /*the base backwards distances (the bits of distance codes appear after length codes and use their own huffman tree)*/

  = {1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577};

static const unsigned DISTANCEEXTRA[30] /*the extra bits of backwards distances (added to base)*/

  = {0, 0, 0, 0, 1, 1, 2,  2,  3,  3,  4,  4,  5,  5,   6,   6,   7,   7,   8,   8,    9,    9,   10,   10,   11,   11,   12,    12,    13,    13};

static const unsigned CLCL[NUM_CODE_LENGTH_CODES] /*the order in which "code length alphabet code lengths" are stored, out of this the huffman tree of the dynamic huffman tree lengths is generated*/

  = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};

/* /////////////////////////////////////////////////////////////////////////// */

/*terminology used for the package-merge algorithm and the coin collector's problem*/

typedef struct Coin /*a coin can be multiple coins (when they're merged)*/

{

  uivector symbols;

  float weight; /*the sum of all weights in this coin*/

} Coin;

static void Coin_init(Coin* c)

{

  uivector_init(&c->symbols);

}

static void Coin_cleanup(void* c) /*void* so that this dtor can be given as function pointer to the vector resize function*/

{

  uivector_cleanup(&((Coin*)c)->symbols);

}

static void Coin_copy(Coin* c1, const Coin* c2)

{

  c1->weight = c2->weight;

  uivector_copy(&c1->symbols, &c2->symbols);

}

static void addCoins(Coin* c1, const Coin* c2)

{

  unsigned i;

  for(i = 0; i < c2->symbols.size; i++) uivector_push_back(&c1->symbols, c2->symbols.data[i]);

  c1->weight += c2->weight;

}

static void Coin_sort(Coin* data, size_t amount) /*combsort*/

{

  size_t gap = amount;

  unsigned char swapped = 0;

  while(gap > 1 || swapped)

  {

    size_t i;

    gap = (gap * 10) / 13; /*shrink factor 1.3*/

    if(gap == 9 || gap == 10) gap = 11; /*combsort11*/

    if(gap < 1) gap = 1;

    swapped = 0;

    for(i = 0; i < amount - gap; i++)

    {

      size_t j = i + gap;

      if(data[j].weight < data[i].weight)

      {

        float temp = data[j].weight; data[j].weight = data[i].weight; data[i].weight = temp;

        uivector_swap(&data[i].symbols, &data[j].symbols);

        swapped = 1;

      }

    }

  }

}

typedef struct HuffmanTree

{

  uivector tree2d;

  uivector tree1d;

  uivector lengths; /*the lengths of the codes of the 1d-tree*/

  unsigned maxbitlen; /*maximum number of bits a single code can get*/

  unsigned numcodes; /*number of symbols in the alphabet = number of codes*/

} HuffmanTree;

/*function used for debug purposes*/

/*#include <iostream>

static void HuffmanTree_draw(HuffmanTree* tree)

{

  std::cout << "tree. length: " << tree->numcodes << " maxbitlen: " << tree->maxbitlen << std::endl;

  for(size_t i = 0; i < tree->tree1d.size; i++)

  {

    if(tree->lengths.data[i])

      std::cout << i << " " << tree->tree1d.data[i] << " " << tree->lengths.data[i] << std::endl;

  }

  std::cout << std::endl;

}*/

static void HuffmanTree_init(HuffmanTree* tree)

{

  uivector_init(&tree->tree2d);

  uivector_init(&tree->tree1d);

  uivector_init(&tree->lengths);

}

static void HuffmanTree_cleanup(HuffmanTree* tree)

{

  uivector_cleanup(&tree->tree2d);

  uivector_cleanup(&tree->tree1d);

  uivector_cleanup(&tree->lengths);

}

/*the tree representation used by the decoder. return value is error*/

static unsigned HuffmanTree_make2DTree(HuffmanTree* tree)

{

  unsigned nodefilled = 0; /*up to which node it is filled*/

  unsigned treepos = 0; /*position in the tree (1 of the numcodes columns)*/

  unsigned n, i;

  if(!uivector_resize(&tree->tree2d, tree->numcodes * 2)) return 9901; /*if failed return not enough memory error*/

  /*convert tree1d[] to tree2d[][]. In the 2D array, a value of 32767 means uninited, a value >= numcodes is an address to another bit, a value < numcodes is a code. The 2 rows are the 2 possible bit values (0 or 1), there are as many columns as codes - 1

  a good huffmann tree has N * 2 - 1 nodes, of which N - 1 are internal nodes. Here, the internal nodes are stored (what their 0 and 1 option point to). There is only memory for such good tree currently, if there are more nodes (due to too long length codes), error 55 will happen*/

  for(n = 0;  n < tree->numcodes * 2; n++) tree->tree2d.data[n] = 32767; /*32767 here means the tree2d isn't filled there yet*/

  for(n = 0; n < tree->numcodes; n++) /*the codes*/

  for(i = 0; i < tree->lengths.data[n]; i++) /*the bits for this code*/

  {

    unsigned char bit = (unsigned char)((tree->tree1d.data[n] >> (tree->lengths.data[n] - i - 1)) & 1);

    if(treepos > tree->numcodes - 2) return 55; /*error 55: oversubscribed; see description in header*/

    if(tree->tree2d.data[2 * treepos + bit] == 32767) /*not yet filled in*/

    {

      if(i + 1 == tree->lengths.data[n]) /*last bit*/

      {

        tree->tree2d.data[2 * treepos + bit] = n; /*put the current code in it*/

        treepos = 0;

      }

      else /*put address of the next step in here, first that address has to be found of course (it's just nodefilled + 1)...*/

      {

        nodefilled++;

        tree->tree2d.data[2 * treepos + bit] = nodefilled + tree->numcodes; /*addresses encoded with numcodes added to it*/

        treepos = nodefilled;

      }

    }

    else treepos = tree->tree2d.data[2 * treepos + bit] - tree->numcodes;

  }

  for(n = 0;  n < tree->numcodes * 2; n++) if(tree->tree2d.data[n] == 32767) tree->tree2d.data[n] = 0; /*remove possible remaining 32767's*/

  return 0;

}

static unsigned HuffmanTree_makeFromLengths2(HuffmanTree* tree) /*given that numcodes, lengths and maxbitlen are already filled in correctly. return value is error.*/

{

  uivector blcount;

  uivector nextcode;

  unsigned bits, n, error = 0;

  uivector_init(&blcount);

  uivector_init(&nextcode);

  if(!uivector_resize(&tree->tree1d, tree->numcodes)

  || !uivector_resizev(&blcount, tree->maxbitlen + 1, 0)

  || !uivector_resizev(&nextcode, tree->maxbitlen + 1, 0))

    error = 9902;

  if(!error)

  {

    /*step 1: count number of instances of each code length*/

    for(bits = 0; bits < tree->numcodes; bits++) blcount.data[tree->lengths.data[bits]]++;

    /*step 2: generate the nextcode values*/

    for(bits = 1; bits <= tree->maxbitlen; bits++) nextcode.data[bits] = (nextcode.data[bits - 1] + blcount.data[bits - 1]) << 1;

    /*step 3: generate all the codes*/

    for(n = 0; n < tree->numcodes; n++) if(tree->lengths.data[n] != 0) tree->tree1d.data[n] = nextcode.data[tree->lengths.data[n]]++;

  }

  uivector_cleanup(&blcount);

  uivector_cleanup(&nextcode);

  if(!error) return HuffmanTree_make2DTree(tree);

  else return error;

}

/*given the code lengths (as stored in the PNG file), generate the tree as defined by Deflate. maxbitlen is the maximum bits that a code in the tree can have. return value is error.*/

static unsigned HuffmanTree_makeFromLengths(HuffmanTree* tree, const unsigned* bitlen, size_t numcodes, unsigned maxbitlen)

{

  unsigned i;

  if(!uivector_resize(&tree->lengths, numcodes)) return 9903;

  for(i = 0; i < numcodes; i++) tree->lengths.data[i] = bitlen[i];

  tree->numcodes = (unsigned)numcodes; /*number of symbols*/

  tree->maxbitlen = maxbitlen;

  return HuffmanTree_makeFromLengths2(tree);

}

static unsigned HuffmanTree_fillInCoins(vector* coins, const unsigned* frequencies, unsigned numcodes, size_t sum)

{

  unsigned i;

  for(i = 0; i < numcodes; i++)

  {

    Coin* coin;

    if(frequencies[i] == 0) continue; /*it's important to exclude symbols that aren't present*/

    if(!vector_resize(coins, coins->size + 1)) { vector_cleanup(coins); return 9904; }

    coin = (Coin*)(vector_get(coins, coins->size - 1));

    Coin_init(coin);

    coin->weight = frequencies[i] / (float)sum;

    uivector_push_back(&coin->symbols, i);

  }

  if(coins->size) Coin_sort((Coin*)coins->data, coins->size);

  return 0;

}

static unsigned HuffmanTree_makeFromFrequencies(HuffmanTree* tree, const unsigned* frequencies, size_t numcodes, unsigned maxbitlen)

{

  unsigned i, j;

  size_t sum = 0, numpresent = 0;

  unsigned error = 0;

  vector prev_row; /*type Coin, the previous row of coins*/

  vector coins; /*type Coin, the coins of the currently calculated row*/

  tree->maxbitlen = maxbitlen;

  for(i = 0; i < numcodes; i++)

  {

    if(frequencies[i] > 0)

    {

      numpresent++;

      sum += frequencies[i];

    }

  }

  if(numcodes == 0) return 80; /*error: a tree of 0 symbols is not supposed to be made*/

  tree->numcodes = (unsigned)numcodes; /*number of symbols*/

  uivector_resize(&tree->lengths, 0);

  if(!uivector_resizev(&tree->lengths, tree->numcodes, 0)) return 9905;

  if(numpresent == 0) /*there are no symbols at all, in that case add one symbol of value 0 to the tree (see RFC 1951 section 3.2.7) */

  {

    tree->lengths.data[0] = 1;

    return HuffmanTree_makeFromLengths2(tree);

  }

  else if(numpresent == 1) /*the package merge algorithm gives wrong results if there's only one symbol (theoretically 0 bits would then suffice, but we need a proper symbol for zlib)*/

  {

    for(i = 0; i < numcodes; i++) if(frequencies[i]) tree->lengths.data[i] = 1;

    return HuffmanTree_makeFromLengths2(tree);

  }

  vector_init(&coins, sizeof(Coin));

  vector_init(&prev_row, sizeof(Coin));

  /*Package-Merge algorithm represented by coin collector's problem

  For every symbol, maxbitlen coins will be created*/

  /*first row, lowest denominator*/

  error = HuffmanTree_fillInCoins(&coins, frequencies, tree->numcodes, sum);

  if(!error)

  {

    for(j = 1; j <= maxbitlen && !error; j++) /*each of the remaining rows*/

    {

      vector_swap(&coins, &prev_row); /*swap instead of copying*/

      if(!vector_resized(&coins, 0, Coin_cleanup)) { error = 9906; break; }

      for(i = 0; i + 1 < prev_row.size; i += 2)

      {

        if(!vector_resize(&coins, coins.size + 1)) { error = 9907; break; }

        Coin_init((Coin*)vector_get(&coins, coins.size - 1));

        Coin_copy((Coin*)vector_get(&coins, coins.size - 1), (Coin*)vector_get(&prev_row, i));

        addCoins((Coin*)vector_get(&coins, coins.size - 1), (Coin*)vector_get(&prev_row, i + 1)); /*merge the coins into packages*/

      }

      if(j < maxbitlen)

      {

        error = HuffmanTree_fillInCoins(&coins, frequencies, tree->numcodes, sum);

      }

    }

  }

  if(!error)

  {

    /*keep the coins with lowest weight, so that they add up to the amount of symbols - 1*/

    vector_resized(&coins, numpresent - 1, Coin_cleanup);

    /*calculate the lengths of each symbol, as the amount of times a coin of each symbol is used*/

    for(i = 0; i < coins.size; i++)

    {

      Coin* coin = (Coin*)vector_get(&coins, i);

      for(j = 0; j < coin->symbols.size; j++) tree->lengths.data[coin->symbols.data[j]]++;

    }

    error = HuffmanTree_makeFromLengths2(tree);

  }

  vector_cleanupd(&coins, Coin_cleanup);

  vector_cleanupd(&prev_row, Coin_cleanup);

  return error;

}

static unsigned HuffmanTree_getCode(const HuffmanTree* tree, unsigned index) { return tree->tree1d.data[index]; }

static unsigned HuffmanTree_getLength(const HuffmanTree* tree, unsigned index) { return tree->lengths.data[index]; }

/*get the tree of a deflated block with fixed tree, as specified in the deflate specification*/

static unsigned generateFixedTree(HuffmanTree* tree)

{

  unsigned i, error = 0;

  uivector bitlen;

  uivector_init(&bitlen);

  if(!uivector_resize(&bitlen, NUM_DEFLATE_CODE_SYMBOLS)) error = 9909;

  if(!error)

  {

    /*288 possible codes: 0-255=literals, 256=endcode, 257-285=lengthcodes, 286-287=unused*/

    for(i =   0; i <= 143; i++) bitlen.data[i] = 8;

    for(i = 144; i <= 255; i++) bitlen.data[i] = 9;

    for(i = 256; i <= 279; i++) bitlen.data[i] = 7;

    for(i = 280; i <= 287; i++) bitlen.data[i] = 8;

    error = HuffmanTree_makeFromLengths(tree, bitlen.data, NUM_DEFLATE_CODE_SYMBOLS, 15);

  }

  uivector_cleanup(&bitlen);

  return error;

}

static unsigned generateDistanceTree(HuffmanTree* tree)

{

  unsigned i, error = 0;

  uivector bitlen;

  uivector_init(&bitlen);

  if(!uivector_resize(&bitlen, NUM_DISTANCE_SYMBOLS)) error = 9910;

  /*there are 32 distance codes, but 30-31 are unused*/

  if(!error)

  {

    for(i = 0; i < NUM_DISTANCE_SYMBOLS; i++) bitlen.data[i] = 5;

    error = HuffmanTree_makeFromLengths(tree, bitlen.data, NUM_DISTANCE_SYMBOLS, 15);

  }

  uivector_cleanup(&bitlen);

  return error;

}

/* ////////////////////////////////////////////////////////////////////////// */

/* / Deflator                                                               / */

/* ////////////////////////////////////////////////////////////////////////// */

static const size_t MAX_SUPPORTED_DEFLATE_LENGTH = 258;

/*bitlen is the size in bits of the code*/

static void addHuffmanSymbol(size_t* bp, ucvector* compressed, unsigned code, unsigned bitlen)

{

  addBitsToStreamReversed(bp, compressed, code, bitlen);

}

/*search the index in the array, that has the largest value smaller than or equal to the given value, given array must be sorted (if no value is smaller, it returns the size of the given array)*/

static size_t searchCodeIndex(const unsigned* array, size_t array_size, size_t value)

{

  /*linear search implementation*/

  /*for(size_t i = 1; i < array_size; i++) if(array[i] > value) return i - 1;

  return array_size - 1;*/

  /*binary search implementation (not that much faster) (precondition: array_size > 0)*/

  size_t left  = 1;

  size_t right = array_size - 1;

  while(left <= right)

  {

    size_t mid = (left + right) / 2;

    if(array[mid] <= value) left = mid + 1; /*the value to find is more to the right*/

    else if(array[mid - 1] > value) right = mid - 1; /*the value to find is more to the left*/

    else return mid - 1;

  }

  return array_size - 1;

}

static void addLengthDistance(uivector* values, size_t length, size_t distance)

{

  /*values in encoded vector are those used by deflate:

  0-255: literal bytes

  256: end

  257-285: length/distance pair (length code, followed by extra length bits, distance code, extra distance bits)

  286-287: invalid*/

  unsigned length_code = (unsigned)searchCodeIndex(LENGTHBASE, 29, length);

  unsigned extra_length = (unsigned)(length - LENGTHBASE[length_code]);

  unsigned dist_code = (unsigned)searchCodeIndex(DISTANCEBASE, 30, distance);

  unsigned extra_distance = (unsigned)(distance - DISTANCEBASE[dist_code]);

  uivector_push_back(values, length_code + FIRST_LENGTH_CODE_INDEX);

  uivector_push_back(values, extra_length);

  uivector_push_back(values, dist_code);

  uivector_push_back(values, extra_distance);

}

#if USE_BRUTE_FORCE_ENCODING

#define encodeLZ77 encodeLZ77_brute

/*the "brute force" version of the encodeLZ7 algorithm, not used anymore, kept here for reference*/

static unsigned encodeLZ77_brute(uivector* out, const unsigned char* in, size_t size, unsigned windowSize)

{

  size_t pos;

  /*using pointer instead of vector for input makes it faster when NOT using optimization when compiling; no influence if optimization is used*/

  for(pos = 0; pos < size; pos++)

  {

    /*Phase 1: doxygen images often have long runs of the same color, try to find them*/

    const int minLength = 4; // Minimum length for a run to make sense

    if(pos < size - minLength * 4)

    {

      size_t p, fp;

      size_t current_length;

      /*RGBA pixel run?*/

      p  = pos;

      fp = pos + 4;

      current_length = 0;

      while(fp < size && in[p] == in[fp] && current_length < MAX_SUPPORTED_DEFLATE_LENGTH)

      {

        ++p;

        ++fp;

        ++current_length;

      }

      if (current_length > (minLength - 1 ) * 4) /*worth using?*/

      {

        uivector_push_back(out, in[pos    ]);

        uivector_push_back(out, in[pos + 1]);

        uivector_push_back(out, in[pos + 2]);

        uivector_push_back(out, in[pos + 3]);

        addLengthDistance(out, current_length, 4);

        pos += current_length + 4 - 1; /*-1 for loop's pos++*/

        continue;

      }

      /*RGB pixel run?*/

      p  = pos;

      fp = pos + 3;

      current_length = 0;

      while(fp < size && in[p] == in[fp] && current_length < MAX_SUPPORTED_DEFLATE_LENGTH)

      {

        ++p;

        ++fp;

        ++current_length;

      }

      if (current_length > (minLength - 1 ) * 3) /*worth using?*/

      {

        uivector_push_back(out, in[pos    ]);

        uivector_push_back(out, in[pos + 1]);

        uivector_push_back(out, in[pos + 2]);

        addLengthDistance(out, current_length, 3);

        pos += current_length + 3 - 1; /*-1 for loop's pos++*/

        continue;

      }

    }

    size_t length = 0, offset = 0; /*the length and offset found for the current position*/

    size_t max_offset = pos < windowSize ? pos : windowSize; /*how far back to test*/

    size_t current_offset;

    /**search for the longest string**/

    for(current_offset = 1; current_offset < max_offset; current_offset++) /*search backwards through all possible distances (=offsets)*/

    {

      size_t backpos = pos - current_offset;

      if(in[backpos] == in[pos])

      {

        /*test the next characters*/

        size_t current_length = 1;

        size_t backtest = backpos + 1;

        size_t foretest = pos + 1;

        while(foretest < size && in[backtest] == in[foretest] && current_length < MAX_SUPPORTED_DEFLATE_LENGTH) /*maximum support length by deflate is max length*/

        {

          if(backpos >= pos) backpos -= current_offset; /*continue as if we work on the decoded bytes after pos by jumping back before pos*/

          current_length++;

          backtest++;

          foretest++;

        }

        if(current_length > length)

        {

          length = current_length; /*the longest length*/

          offset = current_offset; /*the offset that is related to this longest length*/

          if(current_length == MAX_SUPPORTED_DEFLATE_LENGTH) break; /*you can jump out of this for loop once a length of max length is found (gives significant speed gain)*/

        }

      }

    }

    /**encode it as length/distance pair or literal value**/

    if(length < 3) /*only lengths of 3 or higher are supported as length/distance pair*/

    {

      uivector_push_back(out, in[pos]);

    }

    else

    {

      addLengthDistance(out, length, offset);

      pos += (length - 1);

    }

  } /*end of the loop through each character of input*/

  return 0;

}

#endif

/*

static const unsigned HASH_NUM_VALUES = 65536;

static const unsigned HASH_NUM_CHARACTERS = 6;

static const unsigned HASH_SHIFT = 2;

Good and fast values: HASH_NUM_VALUES=65536, HASH_NUM_CHARACTERS=6, HASH_SHIFT=2

making HASH_NUM_CHARACTERS larger (like 8), makes the file size larger but is a bit faster

making HASH_NUM_CHARACTERS smaller (like 3), makes the file size smaller but is slower

*/

#if !defined(USE_BRUTE_FORCE_ENCODING)

static unsigned getHash(const unsigned char* data, size_t size, size_t pos)

{

  unsigned result = 0;

  size_t amount, i;

  if(pos >= size) return 0;

  amount = HASH_NUM_CHARACTERS; if(pos + amount >= size) amount = size - pos;

  for(i = 0; i < amount; i++) result ^= (data[pos + i] << (i * HASH_SHIFT));

  return result % HASH_NUM_VALUES;

}

/*LZ77-encode the data using a hash table technique to let it encode faster. Return value is error code*/

static unsigned encodeLZ77(uivector* out, const unsigned char* in, size_t size, unsigned windowSize)

{

  /**generate hash table**/

  vector table; /*HASH_NUM_VALUES uivectors; this represents what would be an std::vector<std::vector<unsigned> > in C++*/

  uivector tablepos1, tablepos2;

  unsigned pos, i, error = 0;

  vector_init(&table, sizeof(uivector));

  if(!vector_resize(&table, HASH_NUM_VALUES)) return 9917;

  for(i = 0; i < HASH_NUM_VALUES; i++)

  {

    uivector* v = (uivector*)vector_get(&table, i);

    uivector_init(v);

  }

  /*remember start and end positions in the tables to searching in*/

  uivector_init(&tablepos1);

  uivector_init(&tablepos2);

  if(!uivector_resizev(&tablepos1, HASH_NUM_VALUES, 0)) error = 9918;

  if(!uivector_resizev(&tablepos2, HASH_NUM_VALUES, 0)) error = 9919;

  if(!error)

  {

    for(pos = 0; pos < size; pos++)

    {

      unsigned length = 0, offset = 0; /*the length and offset found for the current position*/

      unsigned max_offset = pos < windowSize ? pos : windowSize; /*how far back to test*/

      unsigned tablepos;

      /*/search for the longest string*/

      /*first find out where in the table to start (the first value that is in the range from "pos - max_offset" to "pos")*/

      unsigned hash = getHash(in, size, pos);

      if(!uivector_push_back((uivector*)vector_get(&table, hash), pos))  { error = 9920; break; }

      while(((uivector*)vector_get(&table, hash))->data[tablepos1.data[hash]] < pos - max_offset) tablepos1.data[hash]++; /*it now points to the first value in the table for which the index is larger than or equal to pos - max_offset*/

      while(((uivector*)vector_get(&table, hash))->data[tablepos2.data[hash]] < pos) tablepos2.data[hash]++; /*it now points to the first value in the table for which the index is larger than or equal to pos*/

      for(tablepos = tablepos2.data[hash] - 1; tablepos >= tablepos1.data[hash] && tablepos < tablepos2.data[hash]; tablepos--)

      {

        unsigned backpos = ((uivector*)vector_get(&table, hash))->data[tablepos];

        unsigned current_offset = pos - backpos;

        /*test the next characters*/