Second step for the ...makeFromLengths and ...makeFromFrequencies functions. numcodes, lengths and maxbitlen must already be filled in correctly. return value is error. */
| 808 | value is error. |
| 809 | */ |
| 810 | static unsigned HuffmanTree_makeFromLengths2(HuffmanTree* tree) { |
| 811 | unsigned* blcount; |
| 812 | unsigned* nextcode; |
| 813 | unsigned error = 0; |
| 814 | unsigned bits, n; |
| 815 | |
| 816 | tree->codes = (unsigned*)lodepng_malloc(tree->numcodes * sizeof(unsigned)); |
| 817 | blcount = (unsigned*)lodepng_malloc((tree->maxbitlen + 1) * sizeof(unsigned)); |
| 818 | nextcode = (unsigned*)lodepng_malloc((tree->maxbitlen + 1) * sizeof(unsigned)); |
| 819 | if(!tree->codes || !blcount || !nextcode) error = 83; /*alloc fail*/ |
| 820 | |
| 821 | if(!error) { |
| 822 | for(n = 0; n != tree->maxbitlen + 1; n++) blcount[n] = nextcode[n] = 0; |
| 823 | /*step 1: count number of instances of each code length*/ |
| 824 | for(bits = 0; bits != tree->numcodes; ++bits) ++blcount[tree->lengths[bits]]; |
| 825 | /*step 2: generate the nextcode values*/ |
| 826 | for(bits = 1; bits <= tree->maxbitlen; ++bits) { |
| 827 | nextcode[bits] = (nextcode[bits - 1] + blcount[bits - 1]) << 1u; |
| 828 | } |
| 829 | /*step 3: generate all the codes*/ |
| 830 | for(n = 0; n != tree->numcodes; ++n) { |
| 831 | if(tree->lengths[n] != 0) { |
| 832 | tree->codes[n] = nextcode[tree->lengths[n]]++; |
| 833 | /*remove superfluous bits from the code*/ |
| 834 | tree->codes[n] &= ((1u << tree->lengths[n]) - 1u); |
| 835 | } |
| 836 | } |
| 837 | } |
| 838 | |
| 839 | lodepng_free(blcount); |
| 840 | lodepng_free(nextcode); |
| 841 | |
| 842 | if(!error) error = HuffmanTree_makeTable(tree); |
| 843 | return error; |
| 844 | } |
| 845 | |
| 846 | /* |
| 847 | given the code lengths (as stored in the PNG file), generate the tree as defined |
no test coverage detected