666 static void HuffmanTree_init(HuffmanTree* tree) {  in HuffmanTree_init()  argument
667   tree->codes = 0;  in HuffmanTree_init()
668   tree->lengths = 0;  in HuffmanTree_init()
669   tree->table_len = 0;  in HuffmanTree_init()
670   tree->table_value = 0;  in HuffmanTree_init()
673 static void HuffmanTree_cleanup(HuffmanTree* tree) {  in HuffmanTree_cleanup()  argument
674   lodepng_free(tree->codes);  in HuffmanTree_cleanup()
675   lodepng_free(tree->lengths);  in HuffmanTree_cleanup()
676   lodepng_free(tree->table_len);  in HuffmanTree_cleanup()
677   lodepng_free(tree->table_value);  in HuffmanTree_cleanup()
689 static unsigned HuffmanTree_makeTable(HuffmanTree* tree) {  in HuffmanTree_makeTable()  argument
698   for(i = 0; i < tree->numcodes; i++) {  in HuffmanTree_makeTable()
699     unsigned symbol = tree->codes[i];  in HuffmanTree_makeTable()
700     unsigned l = tree->lengths[i];  in HuffmanTree_makeTable()
713   tree->table_len = (unsigned char*)lodepng_malloc(size * sizeof(*tree->table_len));  in HuffmanTree_makeTable()
714   tree->table_value = (unsigned short*)lodepng_malloc(size * sizeof(*tree->table_value));  in HuffmanTree_makeTable()
715   if(!tree->table_len || !tree->table_value) {  in HuffmanTree_makeTable()
721   for(i = 0; i < size; ++i) tree->table_len[i] = 16;  in HuffmanTree_makeTable()
728     tree->table_len[i] = l;  in HuffmanTree_makeTable()
729     tree->table_value[i] = pointer;  in HuffmanTree_makeTable()
736   for(i = 0; i < tree->numcodes; ++i) {  in HuffmanTree_makeTable()
737     unsigned l = tree->lengths[i];  in HuffmanTree_makeTable()
738     unsigned symbol = tree->codes[i]; /*the huffman bit pattern. i itself is the value.*/  in HuffmanTree_makeTable()
751 …if(tree->table_len[index] != 16) return 55; /*invalid tree: long symbol shares prefix with short s…  in HuffmanTree_makeTable()
752         tree->table_len[index] = l;  in HuffmanTree_makeTable()
753         tree->table_value[index] = i;  in HuffmanTree_makeTable()
759       unsigned maxlen = tree->table_len[index];  in HuffmanTree_makeTable()
762       unsigned start = tree->table_value[index]; /*starting index in secondary table*/  in HuffmanTree_makeTable()
769         tree->table_len[index2] = l;  in HuffmanTree_makeTable()
770         tree->table_value[index2] = i;  in HuffmanTree_makeTable()
783       if(tree->table_len[i] == 16) {  in HuffmanTree_makeTable()
787         tree->table_len[i] = (i < headsize) ? 1 : (FIRSTBITS + 1);  in HuffmanTree_makeTable()
788         tree->table_value[i] = INVALIDSYMBOL;  in HuffmanTree_makeTable()
797       if(tree->table_len[i] == 16) return 55;  in HuffmanTree_makeTable()
809 static unsigned HuffmanTree_makeFromLengths2(HuffmanTree* tree) {  in HuffmanTree_makeFromLengths2()  argument
815   tree->codes = (unsigned*)lodepng_malloc(tree->numcodes * sizeof(unsigned));  in HuffmanTree_makeFromLengths2()
816   blcount = (unsigned*)lodepng_malloc((tree->maxbitlen + 1) * sizeof(unsigned));  in HuffmanTree_makeFromLengths2()
817   nextcode = (unsigned*)lodepng_malloc((tree->maxbitlen + 1) * sizeof(unsigned));  in HuffmanTree_makeFromLengths2()
818   if(!tree->codes || !blcount || !nextcode) error = 83; /*alloc fail*/  in HuffmanTree_makeFromLengths2()
821     for(n = 0; n != tree->maxbitlen + 1; n++) blcount[n] = nextcode[n] = 0;  in HuffmanTree_makeFromLengths2()
823     for(bits = 0; bits != tree->numcodes; ++bits) ++blcount[tree->lengths[bits]];  in HuffmanTree_makeFromLengths2()
825     for(bits = 1; bits <= tree->maxbitlen; ++bits) {  in HuffmanTree_makeFromLengths2()
829     for(n = 0; n != tree->numcodes; ++n) {  in HuffmanTree_makeFromLengths2()
830       if(tree->lengths[n] != 0) {  in HuffmanTree_makeFromLengths2()
831         tree->codes[n] = nextcode[tree->lengths[n]]++;  in HuffmanTree_makeFromLengths2()
833         tree->codes[n] &= ((1u << tree->lengths[n]) - 1u);  in HuffmanTree_makeFromLengths2()
841   if(!error) error = HuffmanTree_makeTable(tree);  in HuffmanTree_makeFromLengths2()
850 static unsigned HuffmanTree_makeFromLengths(HuffmanTree* tree, const unsigned* bitlen,  in HuffmanTree_makeFromLengths()  argument
853   tree->lengths = (unsigned*)lodepng_malloc(numcodes * sizeof(unsigned));  in HuffmanTree_makeFromLengths()
854   if(!tree->lengths) return 83; /*alloc fail*/  in HuffmanTree_makeFromLengths()
855   for(i = 0; i != numcodes; ++i) tree->lengths[i] = bitlen[i];  in HuffmanTree_makeFromLengths()
856   tree->numcodes = (unsigned)numcodes; /*number of symbols*/  in HuffmanTree_makeFromLengths()
857   tree->maxbitlen = maxbitlen;  in HuffmanTree_makeFromLengths()
858   return HuffmanTree_makeFromLengths2(tree);  in HuffmanTree_makeFromLengths()
1045 static unsigned HuffmanTree_makeFromFrequencies(HuffmanTree* tree, const unsigned* frequencies,  in HuffmanTree_makeFromFrequencies()  argument
1049   tree->lengths = (unsigned*)lodepng_malloc(numcodes * sizeof(unsigned));  in HuffmanTree_makeFromFrequencies()
1050   if(!tree->lengths) return 83; /*alloc fail*/  in HuffmanTree_makeFromFrequencies()
1051   tree->maxbitlen = maxbitlen;  in HuffmanTree_makeFromFrequencies()
1052   tree->numcodes = (unsigned)numcodes; /*number of symbols*/  in HuffmanTree_makeFromFrequencies()
1054   error = lodepng_huffman_code_lengths(tree->lengths, frequencies, numcodes, maxbitlen);  in HuffmanTree_makeFromFrequencies()
1055   if(!error) error = HuffmanTree_makeFromLengths2(tree);  in HuffmanTree_makeFromFrequencies()
1061 static unsigned generateFixedLitLenTree(HuffmanTree* tree) {  in generateFixedLitLenTree()  argument
1072   error = HuffmanTree_makeFromLengths(tree, bitlen, NUM_DEFLATE_CODE_SYMBOLS, 15);  in generateFixedLitLenTree()
1079 static unsigned generateFixedDistanceTree(HuffmanTree* tree) {  in generateFixedDistanceTree()  argument
1086   error = HuffmanTree_makeFromLengths(tree, bitlen, NUM_DISTANCE_SYMBOLS, 15);  in generateFixedDistanceTree()
3118 static void color_tree_init(ColorTree* tree) {  in color_tree_init()  argument
3119   lodepng_memset(tree->children, 0, 16 * sizeof(*tree->children));  in color_tree_init()
3120   tree->index = -1;  in color_tree_init()
3123 static void color_tree_cleanup(ColorTree* tree) {  in color_tree_cleanup()  argument
3126     if(tree->children[i]) {  in color_tree_cleanup()
3127       color_tree_cleanup(tree->children[i]);  in color_tree_cleanup()
3128       lodepng_free(tree->children[i]);  in color_tree_cleanup()
3134 static int color_tree_get(ColorTree* tree, unsigned char r, unsigned char g, unsigned char b, unsig…  in color_tree_get()  argument
3138     if(!tree->children[i]) return -1;  in color_tree_get()
3139     else tree = tree->children[i];  in color_tree_get()
3141   return tree ? tree->index : -1;  in color_tree_get()
3145 static int color_tree_has(ColorTree* tree, unsigned char r, unsigned char g, unsigned char b, unsig…  in color_tree_has()  argument
3146   return color_tree_get(tree, r, g, b, a) >= 0;  in color_tree_has()
3153 static unsigned color_tree_add(ColorTree* tree,  in color_tree_add()  argument
3158     if(!tree->children[i]) {  in color_tree_add()
3159       tree->children[i] = (ColorTree*)lodepng_malloc(sizeof(ColorTree));  in color_tree_add()
3160       if(!tree->children[i]) return 83; /*alloc fail*/  in color_tree_add()
3161       color_tree_init(tree->children[i]);  in color_tree_add()
3163     tree = tree->children[i];  in color_tree_add()
3165   tree->index = (int)index;  in color_tree_add()
3171                              const LodePNGColorMode* mode, ColorTree* tree /*for palette*/,  in rgba8ToPixel()  argument
3193     int index = color_tree_get(tree, r, g, b, a);  in rgba8ToPixel()
3531   ColorTree tree;  in lodepng_convert()  local
3565     color_tree_init(&tree);  in lodepng_convert()
3568       error = color_tree_add(&tree, p[0], p[1], p[2], p[3], (unsigned)i);  in lodepng_convert()
3588         error = rgba8ToPixel(out, i, mode_out, &tree, r, g, b, a);  in lodepng_convert()
3595     color_tree_cleanup(&tree);  in lodepng_convert()
3699   ColorTree tree;  in lodepng_compute_color_stats()  local
3718   color_tree_init(&tree);  in lodepng_compute_color_stats()
3731       error = color_tree_add(&tree, color[0], color[1], color[2], color[3], i);  in lodepng_compute_color_stats()
3835         if(!color_tree_has(&tree, r, g, b, a)) {  in lodepng_compute_color_stats()
3836           error = color_tree_add(&tree, r, g, b, a, stats->numcolors);  in lodepng_compute_color_stats()
3874   color_tree_cleanup(&tree);  in lodepng_compute_color_stats()