/*

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"

#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.

*/

#ifdef LODEPNG_COMPILE_ZLIB

#ifdef LODEPNG_COMPILE_ENCODER

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];

}

#endif /*LODEPNG_COMPILE_ENCODER*/

#endif /*LODEPNG_COMPILE_ZLIB*/

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

#ifdef LODEPNG_COMPILE_ZLIB

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;

}

#ifdef LODEPNG_COMPILE_ENCODER

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;

}

#endif /*LODEPNG_COMPILE_ENCODER*/

#endif /*LODEPNG_COMPILE_ZLIB*/

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

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;

}

#ifdef LODEPNG_COMPILE_DECODER

#ifdef LODEPNG_COMPILE_PNG

static unsigned ucvector_resizev(ucvector* p, size_t size, unsigned char value) /*resize and give all new elements the value*/

{

  size_t oldsize = p->size, i;

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

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

  return 1;

}

#endif /*LODEPNG_COMPILE_PNG*/

#endif /*LODEPNG_COMPILE_DECODER*/

static void ucvector_init(ucvector* p)

{

  p->data = NULL;

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

}

#ifdef LODEPNG_COMPILE_ZLIB

/*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;

}

#endif /*LODEPNG_COMPILE_ZLIB*/

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;

}

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

#ifdef LODEPNG_COMPILE_PNG

#ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS

static unsigned string_resize(char** out, size_t size) /*returns 1 if success, 0 if failure ==> nothing done*/

{

  char* data = (char*)realloc(*out, size + 1);

  if(data)

  {

    data[size] = 0; /*null termination char*/

    *out = data;

  }

  return data != 0;

}

static void string_init(char** out) /*init a {char*, size_t} pair for use as string*/

{

  *out = NULL;

  string_resize(out, 0);

}

static void string_cleanup(char** out) /*free the above pair again*/

{

  free(*out);

  *out = NULL;

}

static void string_set(char** out, const char* in)

{

  size_t insize = strlen(in), i = 0;

  if(string_resize(out, insize)) for(i = 0; i < insize; i++) (*out)[i] = in[i];

}

#endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/

#endif /*LODEPNG_COMPILE_PNG*/

#ifdef LODEPNG_COMPILE_ZLIB

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

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

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

#ifdef LODEPNG_COMPILE_ENCODER

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));

}

#endif /*LODEPNG_COMPILE_ENCODER*/

#ifdef LODEPNG_COMPILE_DECODER

static unsigned char readBitFromStream(size_t* bitpointer, const unsigned char* bitstream)

{

  unsigned char result = (unsigned char)((bitstream[(*bitpointer) >> 3] >> ((*bitpointer) & 0x7)) & 1);

  (*bitpointer)++;

  return result;

}

static unsigned readBitsFromStream(size_t* bitpointer, const unsigned char* bitstream, size_t nbits)

{

  unsigned result = 0, i;

  for(i = 0; i < nbits; i++) result += ((unsigned)readBitFromStream(bitpointer, bitstream)) << i;

  return result;

}

#endif /*LODEPNG_COMPILE_DECODER*/

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

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

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

#ifdef LODEPNG_COMPILE_ENCODER

/*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;

      }

    }

  }

}

#endif /*LODEPNG_COMPILE_ENCODER*/

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];