| 700 | } |
| 701 | |
| 702 | void HuffmanProcessor::buildTables() |
| 703 | { |
| 704 | AssertFatal(m_tablesBuilt == false, "Cannot build tables twice!"); |
| 705 | m_tablesBuilt = true; |
| 706 | |
| 707 | S32 i; |
| 708 | |
| 709 | // First, construct the array of wraps... |
| 710 | // |
| 711 | m_huffLeaves.setSize(256); |
| 712 | m_huffNodes.reserve(256); |
| 713 | m_huffNodes.increment(); |
| 714 | for (i = 0; i < 256; i++) { |
| 715 | HuffLeaf& rLeaf = m_huffLeaves[i]; |
| 716 | |
| 717 | rLeaf.pop = csm_charFreqs[i] + 1; |
| 718 | rLeaf.symbol = U8(i); |
| 719 | |
| 720 | dMemset(&rLeaf.code, 0, sizeof(rLeaf.code)); |
| 721 | rLeaf.numBits = 0; |
| 722 | } |
| 723 | |
| 724 | S32 currWraps = 256; |
| 725 | HuffWrap* pWrap = new HuffWrap[256]; |
| 726 | for (i = 0; i < 256; i++) { |
| 727 | pWrap[i].set(&m_huffLeaves[i]); |
| 728 | } |
| 729 | |
| 730 | while (currWraps != 1) { |
| 731 | U32 min1 = 0xfffffffe, min2 = 0xffffffff; |
| 732 | S32 index1 = -1, index2 = -1; |
| 733 | |
| 734 | for (i = 0; i < currWraps; i++) { |
| 735 | if (pWrap[i].getPop() < min1) { |
| 736 | min2 = min1; |
| 737 | index2 = index1; |
| 738 | |
| 739 | min1 = pWrap[i].getPop(); |
| 740 | index1 = i; |
| 741 | } else if (pWrap[i].getPop() < min2) { |
| 742 | min2 = pWrap[i].getPop(); |
| 743 | index2 = i; |
| 744 | } |
| 745 | } |
| 746 | AssertFatal(index1 != -1 && index2 != -1 && index1 != index2, "hrph"); |
| 747 | |
| 748 | // Create a node for this... |
| 749 | m_huffNodes.increment(); |
| 750 | HuffNode& rNode = m_huffNodes.last(); |
| 751 | rNode.pop = pWrap[index1].getPop() + pWrap[index2].getPop(); |
| 752 | rNode.index0 = determineIndex(pWrap[index1]); |
| 753 | rNode.index1 = determineIndex(pWrap[index2]); |
| 754 | |
| 755 | S32 mergeIndex = index1 > index2 ? index2 : index1; |
| 756 | S32 nukeIndex = index1 > index2 ? index1 : index2; |
| 757 | pWrap[mergeIndex].set(&rNode); |
| 758 | |
| 759 | if (index2 != (currWraps - 1)) { |