Deflate for a block of type "dynamic", that is, with freely, optimally, created huffman trees*/
| 1722 | |
| 1723 | /*Deflate for a block of type "dynamic", that is, with freely, optimally, created huffman trees*/ |
| 1724 | static unsigned deflateDynamic(ucvector* out, size_t* bp, Hash* hash, |
| 1725 | const unsigned char* data, size_t datapos, size_t dataend, |
| 1726 | const LodePNGCompressSettings* settings, unsigned final) |
| 1727 | { |
| 1728 | unsigned error = 0; |
| 1729 | |
| 1730 | /* |
| 1731 | A block is compressed as follows: The PNG data is lz77 encoded, resulting in |
| 1732 | literal bytes and length/distance pairs. This is then huffman compressed with |
| 1733 | two huffman trees. One huffman tree is used for the lit and len values ("ll"), |
| 1734 | another huffman tree is used for the dist values ("d"). These two trees are |
| 1735 | stored using their code lengths, and to compress even more these code lengths |
| 1736 | are also run-length encoded and huffman compressed. This gives a huffman tree |
| 1737 | of code lengths "cl". The code lenghts used to describe this third tree are |
| 1738 | the code length code lengths ("clcl"). |
| 1739 | */ |
| 1740 | |
| 1741 | /*The lz77 encoded data, represented with integers since there will also be length and distance codes in it*/ |
| 1742 | uivector lz77_encoded; |
| 1743 | HuffmanTree tree_ll; /*tree for lit,len values*/ |
| 1744 | HuffmanTree tree_d; /*tree for distance codes*/ |
| 1745 | HuffmanTree tree_cl; /*tree for encoding the code lengths representing tree_ll and tree_d*/ |
| 1746 | uivector frequencies_ll; /*frequency of lit,len codes*/ |
| 1747 | uivector frequencies_d; /*frequency of dist codes*/ |
| 1748 | uivector frequencies_cl; /*frequency of code length codes*/ |
| 1749 | uivector bitlen_lld; /*lit,len,dist code lenghts (int bits), literally (without repeat codes).*/ |
| 1750 | uivector bitlen_lld_e; /*bitlen_lld encoded with repeat codes (this is a rudemtary run length compression)*/ |
| 1751 | /*bitlen_cl is the code length code lengths ("clcl"). The bit lengths of codes to represent tree_cl |
| 1752 | (these are written as is in the file, it would be crazy to compress these using yet another huffman |
| 1753 | tree that needs to be represented by yet another set of code lengths)*/ |
| 1754 | uivector bitlen_cl; |
| 1755 | size_t datasize = dataend - datapos; |
| 1756 | |
| 1757 | /* |
| 1758 | Due to the huffman compression of huffman tree representations ("two levels"), there are some anologies: |
| 1759 | bitlen_lld is to tree_cl what data is to tree_ll and tree_d. |
| 1760 | bitlen_lld_e is to bitlen_lld what lz77_encoded is to data. |
| 1761 | bitlen_cl is to bitlen_lld_e what bitlen_lld is to lz77_encoded. |
| 1762 | */ |
| 1763 | |
| 1764 | unsigned BFINAL = final; |
| 1765 | size_t numcodes_ll, numcodes_d, i; |
| 1766 | unsigned HLIT, HDIST, HCLEN; |
| 1767 | |
| 1768 | uivector_init(&lz77_encoded); |
| 1769 | HuffmanTree_init(&tree_ll); |
| 1770 | HuffmanTree_init(&tree_d); |
| 1771 | HuffmanTree_init(&tree_cl); |
| 1772 | uivector_init(&frequencies_ll); |
| 1773 | uivector_init(&frequencies_d); |
| 1774 | uivector_init(&frequencies_cl); |
| 1775 | uivector_init(&bitlen_lld); |
| 1776 | uivector_init(&bitlen_lld_e); |
| 1777 | uivector_init(&bitlen_cl); |
| 1778 | |
| 1779 | /*This while loop never loops due to a break at the end, it is here to |
| 1780 | allow breaking out of it to the cleanup phase on error conditions.*/ |
| 1781 | while(!error) |
no test coverage detected