make table for huffman decoding */
| 688 | |
| 689 | /* make table for huffman decoding */ |
| 690 | static unsigned HuffmanTree_makeTable(HuffmanTree* tree) { |
| 691 | static const unsigned headsize = 1u << FIRSTBITS; /*size of the first table*/ |
| 692 | static const unsigned mask = (1u << FIRSTBITS) /*headsize*/ - 1u; |
| 693 | size_t i, numpresent, pointer, size; /*total table size*/ |
| 694 | unsigned* maxlens = (unsigned*)lodepng_malloc(headsize * sizeof(unsigned)); |
| 695 | if(!maxlens) return 83; /*alloc fail*/ |
| 696 | |
| 697 | /* compute maxlens: max total bit length of symbols sharing prefix in the first table*/ |
| 698 | lodepng_memset(maxlens, 0, headsize * sizeof(*maxlens)); |
| 699 | for(i = 0; i < tree->numcodes; i++) { |
| 700 | unsigned symbol = tree->codes[i]; |
| 701 | unsigned l = tree->lengths[i]; |
| 702 | unsigned index; |
| 703 | if(l <= FIRSTBITS) continue; /*symbols that fit in first table don't increase secondary table size*/ |
| 704 | /*get the FIRSTBITS MSBs, the MSBs of the symbol are encoded first. See later comment about the reversing*/ |
| 705 | index = reverseBits(symbol >> (l - FIRSTBITS), FIRSTBITS); |
| 706 | maxlens[index] = LODEPNG_MAX(maxlens[index], l); |
| 707 | } |
| 708 | /* compute total table size: size of first table plus all secondary tables for symbols longer than FIRSTBITS */ |
| 709 | size = headsize; |
| 710 | for(i = 0; i < headsize; ++i) { |
| 711 | unsigned l = maxlens[i]; |
| 712 | if(l > FIRSTBITS) size += (1u << (l - FIRSTBITS)); |
| 713 | } |
| 714 | tree->table_len = (unsigned char*)lodepng_malloc(size * sizeof(*tree->table_len)); |
| 715 | tree->table_value = (unsigned short*)lodepng_malloc(size * sizeof(*tree->table_value)); |
| 716 | if(!tree->table_len || !tree->table_value) { |
| 717 | lodepng_free(maxlens); |
| 718 | /* freeing tree->table values is done at a higher scope */ |
| 719 | return 83; /*alloc fail*/ |
| 720 | } |
| 721 | /*initialize with an invalid length to indicate unused entries*/ |
| 722 | for(i = 0; i < size; ++i) tree->table_len[i] = 16; |
| 723 | |
| 724 | /*fill in the first table for long symbols: max prefix size and pointer to secondary tables*/ |
| 725 | pointer = headsize; |
| 726 | for(i = 0; i < headsize; ++i) { |
| 727 | unsigned l = maxlens[i]; |
| 728 | if(l <= FIRSTBITS) continue; |
| 729 | tree->table_len[i] = l; |
| 730 | tree->table_value[i] = pointer; |
| 731 | pointer += (1u << (l - FIRSTBITS)); |
| 732 | } |
| 733 | lodepng_free(maxlens); |
| 734 | |
| 735 | /*fill in the first table for short symbols, or secondary table for long symbols*/ |
| 736 | numpresent = 0; |
| 737 | for(i = 0; i < tree->numcodes; ++i) { |
| 738 | unsigned l = tree->lengths[i]; |
| 739 | unsigned symbol = tree->codes[i]; /*the huffman bit pattern. i itself is the value.*/ |
| 740 | /*reverse bits, because the huffman bits are given in MSB first order but the bit reader reads LSB first*/ |
| 741 | unsigned reverse = reverseBits(symbol, l); |
| 742 | if(l == 0) continue; |
| 743 | numpresent++; |
| 744 | |
| 745 | if(l <= FIRSTBITS) { |
| 746 | /*short symbol, fully in first table, replicated num times if l < FIRSTBITS*/ |
| 747 | unsigned num = 1u << (FIRSTBITS - l); |
no test coverage detected