the tree representation used by the decoder. return value is error*/
| 544 | |
| 545 | /*the tree representation used by the decoder. return value is error*/ |
| 546 | static unsigned HuffmanTree_make2DTree(HuffmanTree* tree) |
| 547 | { |
| 548 | unsigned nodefilled = 0; /*up to which node it is filled*/ |
| 549 | unsigned treepos = 0; /*position in the tree (1 of the numcodes columns)*/ |
| 550 | unsigned n, i; |
| 551 | |
| 552 | tree->tree2d = (unsigned*)lodepng_malloc(tree->numcodes * 2 * sizeof(unsigned)); |
| 553 | if(!tree->tree2d) return 83; /*alloc fail*/ |
| 554 | |
| 555 | /* |
| 556 | convert tree1d[] to tree2d[][]. In the 2D array, a value of 32767 means |
| 557 | uninited, a value >= numcodes is an address to another bit, a value < numcodes |
| 558 | is a code. The 2 rows are the 2 possible bit values (0 or 1), there are as |
| 559 | many columns as codes - 1. |
| 560 | A good huffman tree has N * 2 - 1 nodes, of which N - 1 are internal nodes. |
| 561 | Here, the internal nodes are stored (what their 0 and 1 option point to). |
| 562 | There is only memory for such good tree currently, if there are more nodes |
| 563 | (due to too long length codes), error 55 will happen |
| 564 | */ |
| 565 | for(n = 0; n < tree->numcodes * 2; ++n) |
| 566 | { |
| 567 | tree->tree2d[n] = 32767; /*32767 here means the tree2d isn't filled there yet*/ |
| 568 | } |
| 569 | |
| 570 | for(n = 0; n < tree->numcodes; ++n) /*the codes*/ |
| 571 | { |
| 572 | for(i = 0; i != tree->lengths[n]; ++i) /*the bits for this code*/ |
| 573 | { |
| 574 | unsigned char bit = (unsigned char)((tree->tree1d[n] >> (tree->lengths[n] - i - 1)) & 1); |
| 575 | /*oversubscribed, see comment in lodepng_error_text*/ |
| 576 | if(treepos > 2147483647 || treepos + 2 > tree->numcodes) return 55; |
| 577 | if(tree->tree2d[2 * treepos + bit] == 32767) /*not yet filled in*/ |
| 578 | { |
| 579 | if(i + 1 == tree->lengths[n]) /*last bit*/ |
| 580 | { |
| 581 | tree->tree2d[2 * treepos + bit] = n; /*put the current code in it*/ |
| 582 | treepos = 0; |
| 583 | } |
| 584 | else |
| 585 | { |
| 586 | /*put address of the next step in here, first that address has to be found of course |
| 587 | (it's just nodefilled + 1)...*/ |
| 588 | ++nodefilled; |
| 589 | /*addresses encoded with numcodes added to it*/ |
| 590 | tree->tree2d[2 * treepos + bit] = nodefilled + tree->numcodes; |
| 591 | treepos = nodefilled; |
| 592 | } |
| 593 | } |
| 594 | else treepos = tree->tree2d[2 * treepos + bit] - tree->numcodes; |
| 595 | } |
| 596 | } |
| 597 | |
| 598 | for(n = 0; n < tree->numcodes * 2; ++n) |
| 599 | { |
| 600 | if(tree->tree2d[n] == 32767) tree->tree2d[n] = 0; /*remove possible remaining 32767's*/ |
| 601 | } |
| 602 | |
| 603 | return 0; |
no test coverage detected