| 965 | } |
| 966 | |
| 967 | unsigned lodepng_huffman_code_lengths(unsigned* lengths, const unsigned* frequencies, |
| 968 | size_t numcodes, unsigned maxbitlen) { |
| 969 | unsigned error = 0; |
| 970 | unsigned i; |
| 971 | size_t numpresent = 0; /*number of symbols with non-zero frequency*/ |
| 972 | BPMNode* leaves; /*the symbols, only those with > 0 frequency*/ |
| 973 | |
| 974 | if(numcodes == 0) return 80; /*error: a tree of 0 symbols is not supposed to be made*/ |
| 975 | if((1u << maxbitlen) < (unsigned)numcodes) return 80; /*error: represent all symbols*/ |
| 976 | |
| 977 | leaves = (BPMNode*)lodepng_malloc(numcodes * sizeof(*leaves)); |
| 978 | if(!leaves) return 83; /*alloc fail*/ |
| 979 | |
| 980 | for(i = 0; i != numcodes; ++i) { |
| 981 | if(frequencies[i] > 0) { |
| 982 | leaves[numpresent].weight = (int)frequencies[i]; |
| 983 | leaves[numpresent].index = i; |
| 984 | ++numpresent; |
| 985 | } |
| 986 | } |
| 987 | |
| 988 | lodepng_memset(lengths, 0, numcodes * sizeof(*lengths)); |
| 989 | |
| 990 | /*ensure at least two present symbols. There should be at least one symbol |
| 991 | according to RFC 1951 section 3.2.7. Some decoders incorrectly require two. To |
| 992 | make these work as well ensure there are at least two symbols. The |
| 993 | Package-Merge code below also doesn't work correctly if there's only one |
| 994 | symbol, it'd give it the theoretical 0 bits but in practice zlib wants 1 bit*/ |
| 995 | if(numpresent == 0) { |
| 996 | lengths[0] = lengths[1] = 1; /*note that for RFC 1951 section 3.2.7, only lengths[0] = 1 is needed*/ |
| 997 | } else if(numpresent == 1) { |
| 998 | lengths[leaves[0].index] = 1; |
| 999 | lengths[leaves[0].index == 0 ? 1 : 0] = 1; |
| 1000 | } else { |
| 1001 | BPMLists lists; |
| 1002 | BPMNode* node; |
| 1003 | |
| 1004 | bpmnode_sort(leaves, numpresent); |
| 1005 | |
| 1006 | lists.listsize = maxbitlen; |
| 1007 | lists.memsize = 2 * maxbitlen * (maxbitlen + 1); |
| 1008 | lists.nextfree = 0; |
| 1009 | lists.numfree = lists.memsize; |
| 1010 | lists.memory = (BPMNode*)lodepng_malloc(lists.memsize * sizeof(*lists.memory)); |
| 1011 | lists.freelist = (BPMNode**)lodepng_malloc(lists.memsize * sizeof(BPMNode*)); |
| 1012 | lists.chains0 = (BPMNode**)lodepng_malloc(lists.listsize * sizeof(BPMNode*)); |
| 1013 | lists.chains1 = (BPMNode**)lodepng_malloc(lists.listsize * sizeof(BPMNode*)); |
| 1014 | if(!lists.memory || !lists.freelist || !lists.chains0 || !lists.chains1) error = 83; /*alloc fail*/ |
| 1015 | |
| 1016 | if(!error) { |
| 1017 | for(i = 0; i != lists.memsize; ++i) lists.freelist[i] = &lists.memory[i]; |
| 1018 | |
| 1019 | bpmnode_create(&lists, leaves[0].weight, 1, 0); |
| 1020 | bpmnode_create(&lists, leaves[1].weight, 2, 0); |
| 1021 | |
| 1022 | for(i = 0; i != lists.listsize; ++i) { |
| 1023 | lists.chains0[i] = &lists.memory[0]; |
| 1024 | lists.chains1[i] = &lists.memory[1]; |
no test coverage detected