Lines Matching refs:tree
689 static void HuffmanTree_init(HuffmanTree * tree) in HuffmanTree_init() argument
691 tree->codes = 0; in HuffmanTree_init()
692 tree->lengths = 0; in HuffmanTree_init()
693 tree->table_len = 0; in HuffmanTree_init()
694 tree->table_value = 0; in HuffmanTree_init()
697 static void HuffmanTree_cleanup(HuffmanTree * tree) in HuffmanTree_cleanup() argument
699 lodepng_free(tree->codes); in HuffmanTree_cleanup()
700 lodepng_free(tree->lengths); in HuffmanTree_cleanup()
701 lodepng_free(tree->table_len); in HuffmanTree_cleanup()
702 lodepng_free(tree->table_value); in HuffmanTree_cleanup()
714 static unsigned HuffmanTree_makeTable(HuffmanTree * tree) in HuffmanTree_makeTable() argument
724 for(i = 0; i < tree->numcodes; i++) { in HuffmanTree_makeTable()
725 unsigned symbol = tree->codes[i]; in HuffmanTree_makeTable()
726 unsigned l = tree->lengths[i]; in HuffmanTree_makeTable()
739 tree->table_len = (unsigned char *)lodepng_malloc(size * sizeof(*tree->table_len)); in HuffmanTree_makeTable()
740 tree->table_value = (unsigned short *)lodepng_malloc(size * sizeof(*tree->table_value)); in HuffmanTree_makeTable()
741 if(!tree->table_len || !tree->table_value) { in HuffmanTree_makeTable()
747 for(i = 0; i < size; ++i) tree->table_len[i] = 16; in HuffmanTree_makeTable()
754 tree->table_len[i] = l; in HuffmanTree_makeTable()
755 tree->table_value[i] = (unsigned short)pointer; in HuffmanTree_makeTable()
762 for(i = 0; i < tree->numcodes; ++i) { in HuffmanTree_makeTable()
763 unsigned l = tree->lengths[i]; in HuffmanTree_makeTable()
766 symbol = tree->codes[i]; /*the huffman bit pattern. i itself is the value.*/ in HuffmanTree_makeTable()
778 …if(tree->table_len[index] != 16) return 55; /*invalid tree: long symbol shares prefix with short s… in HuffmanTree_makeTable()
779 tree->table_len[index] = l; in HuffmanTree_makeTable()
780 tree->table_value[index] = (unsigned short)i; in HuffmanTree_makeTable()
787 unsigned maxlen = tree->table_len[index]; in HuffmanTree_makeTable()
790 unsigned start = tree->table_value[index]; /*starting index in secondary table*/ in HuffmanTree_makeTable()
797 tree->table_len[index2] = l; in HuffmanTree_makeTable()
798 tree->table_value[index2] = (unsigned short)i; in HuffmanTree_makeTable()
811 if(tree->table_len[i] == 16) { in HuffmanTree_makeTable()
815 tree->table_len[i] = (i < headsize) ? 1 : (FIRSTBITS + 1); in HuffmanTree_makeTable()
816 tree->table_value[i] = INVALIDSYMBOL; in HuffmanTree_makeTable()
826 if(tree->table_len[i] == 16) return 55; in HuffmanTree_makeTable()
838 static unsigned HuffmanTree_makeFromLengths2(HuffmanTree * tree) in HuffmanTree_makeFromLengths2() argument
845 tree->codes = (unsigned *)lodepng_malloc(tree->numcodes * sizeof(unsigned)); in HuffmanTree_makeFromLengths2()
846 blcount = (unsigned *)lodepng_malloc((tree->maxbitlen + 1) * sizeof(unsigned)); in HuffmanTree_makeFromLengths2()
847 nextcode = (unsigned *)lodepng_malloc((tree->maxbitlen + 1) * sizeof(unsigned)); in HuffmanTree_makeFromLengths2()
848 if(!tree->codes || !blcount || !nextcode) error = 83; /*alloc fail*/ in HuffmanTree_makeFromLengths2()
851 for(n = 0; n != tree->maxbitlen + 1; n++) blcount[n] = nextcode[n] = 0; in HuffmanTree_makeFromLengths2()
853 for(bits = 0; bits != tree->numcodes; ++bits) ++blcount[tree->lengths[bits]]; in HuffmanTree_makeFromLengths2()
855 for(bits = 1; bits <= tree->maxbitlen; ++bits) { in HuffmanTree_makeFromLengths2()
859 for(n = 0; n != tree->numcodes; ++n) { in HuffmanTree_makeFromLengths2()
860 if(tree->lengths[n] != 0) { in HuffmanTree_makeFromLengths2()
861 tree->codes[n] = nextcode[tree->lengths[n]]++; in HuffmanTree_makeFromLengths2()
863 tree->codes[n] &= ((1u << tree->lengths[n]) - 1u); in HuffmanTree_makeFromLengths2()
871 if(!error) error = HuffmanTree_makeTable(tree); in HuffmanTree_makeFromLengths2()
880 static unsigned HuffmanTree_makeFromLengths(HuffmanTree * tree, const unsigned * bitlen, in HuffmanTree_makeFromLengths() argument
884 tree->lengths = (unsigned *)lodepng_malloc(numcodes * sizeof(unsigned)); in HuffmanTree_makeFromLengths()
885 if(!tree->lengths) return 83; /*alloc fail*/ in HuffmanTree_makeFromLengths()
886 for(i = 0; i != numcodes; ++i) tree->lengths[i] = bitlen[i]; in HuffmanTree_makeFromLengths()
887 tree->numcodes = (unsigned)numcodes; /*number of symbols*/ in HuffmanTree_makeFromLengths()
888 tree->maxbitlen = maxbitlen; in HuffmanTree_makeFromLengths()
889 return HuffmanTree_makeFromLengths2(tree); in HuffmanTree_makeFromLengths()
1083 static unsigned HuffmanTree_makeFromFrequencies(HuffmanTree * tree, const unsigned * frequencies, in HuffmanTree_makeFromFrequencies() argument
1088 tree->lengths = (unsigned *)lodepng_malloc(numcodes * sizeof(unsigned)); in HuffmanTree_makeFromFrequencies()
1089 if(!tree->lengths) return 83; /*alloc fail*/ in HuffmanTree_makeFromFrequencies()
1090 tree->maxbitlen = maxbitlen; in HuffmanTree_makeFromFrequencies()
1091 tree->numcodes = (unsigned)numcodes; /*number of symbols*/ in HuffmanTree_makeFromFrequencies()
1093 error = lodepng_huffman_code_lengths(tree->lengths, frequencies, numcodes, maxbitlen); in HuffmanTree_makeFromFrequencies()
1094 if(!error) error = HuffmanTree_makeFromLengths2(tree); in HuffmanTree_makeFromFrequencies()
1100 static unsigned generateFixedLitLenTree(HuffmanTree * tree) in generateFixedLitLenTree() argument
1112 error = HuffmanTree_makeFromLengths(tree, bitlen, NUM_DEFLATE_CODE_SYMBOLS, 15); in generateFixedLitLenTree()
1119 static unsigned generateFixedDistanceTree(HuffmanTree * tree) in generateFixedDistanceTree() argument
1127 error = HuffmanTree_makeFromLengths(tree, bitlen, NUM_DISTANCE_SYMBOLS, 15); in generateFixedDistanceTree()
3604 static void color_tree_init(ColorTree * tree) in color_tree_init() argument
3606 lodepng_memset(tree->children, 0, 16 * sizeof(*tree->children)); in color_tree_init()
3607 tree->index = -1; in color_tree_init()
3610 static void color_tree_cleanup(ColorTree * tree) in color_tree_cleanup() argument
3614 if(tree->children[i]) { in color_tree_cleanup()
3615 color_tree_cleanup(tree->children[i]); in color_tree_cleanup()
3616 lodepng_free(tree->children[i]); in color_tree_cleanup()
3622 static int color_tree_get(ColorTree * tree, unsigned char r, unsigned char g, unsigned char b, unsi… in color_tree_get() argument
3627 if(!tree->children[i]) return -1; in color_tree_get()
3628 else tree = tree->children[i]; in color_tree_get()
3630 return tree ? tree->index : -1; in color_tree_get()
3634 static int color_tree_has(ColorTree * tree, unsigned char r, unsigned char g, unsigned char b, unsi… in color_tree_has() argument
3636 return color_tree_get(tree, r, g, b, a) >= 0; in color_tree_has()
3643 static unsigned color_tree_add(ColorTree * tree, in color_tree_add() argument
3649 if(!tree->children[i]) { in color_tree_add()
3650 tree->children[i] = (ColorTree *)lodepng_malloc(sizeof(ColorTree)); in color_tree_add()
3651 if(!tree->children[i]) return 83; /*alloc fail*/ in color_tree_add()
3652 color_tree_init(tree->children[i]); in color_tree_add()
3654 tree = tree->children[i]; in color_tree_add()
3656 tree->index = (int)index; in color_tree_add()
3662 const LodePNGColorMode * mode, ColorTree * tree /*for palette*/, in rgba8ToPixel() argument
3688 int index = color_tree_get(tree, r, g, b, a); in rgba8ToPixel()
4073 ColorTree tree; in lodepng_convert() local
4107 color_tree_init(&tree); in lodepng_convert()
4110 error = color_tree_add(&tree, p[0], p[1], p[2], p[3], (unsigned)i); in lodepng_convert()
4133 error = rgba8ToPixel(out, i, mode_out, &tree, r, g, b, a); in lodepng_convert()
4140 color_tree_cleanup(&tree); in lodepng_convert()
4254 ColorTree tree; in lodepng_compute_color_stats() local
4273 color_tree_init(&tree); in lodepng_compute_color_stats()
4286 error = color_tree_add(&tree, color[0], color[1], color[2], color[3], (unsigned)i); in lodepng_compute_color_stats()
4395 if(!color_tree_has(&tree, r, g, b, a)) { in lodepng_compute_color_stats()
4396 error = color_tree_add(&tree, r, g, b, a, stats->numcolors); in lodepng_compute_color_stats()
4434 color_tree_cleanup(&tree); in lodepng_compute_color_stats()