3.1.1.1.3.1 PrefixCodeTreeRebuild

Rebuilds the Huffman prefix code tree that will be used to decode symbols during decompression.

Parameters

  • in UCHAR input[256]: A 256-byte buffer that contains the canonical encoding of the Huffman prefix code tree that was used to compress the data.

  • inout PREFIX_CODE_NODE treeNodes[1024]: A 1024-element PREFIX_CODE_NODE array in which the procedure rebuilds the Huffman prefix code tree.

Return Value

Returns the PREFIX_CODE_NODE in treeNodes that represents the root of the rebuilt Huffman prefix code tree

Algorithm

 PREFIX_CODE_NODE root
 PREFIX_CODE_SYMBOL symbolInfo[512]
 ULONG i
 ULONG j
 ULONG mask
 ULONG bits
  
 for i from 0 to 1023
     treeNodes[i].symbol := 0
     treeNodes[i].leaf := FALSE
     treeNodes[i].child[0] := NIL
     treeNodes[i].child[1] := NIL
 endfor
  
 for i from 0 to 255
     symbolInfo[2*i].symbol := 2*i
     symbolInfo[2*i].length := input[i] & 15
  
     symbolInfo[2*i+1].symbol := 2*i+1
     symbolInfo[2*i+1].length := input[i] >> 4
 endfor
  
 SortSymbols(symbolInfo)
  
 i := 0
 while (i < 512) and (symbolInfo[i].length = 0)
     i := i + 1
 endwhile
  
 mask := 0
 bits := 1
  
 root := treeNodes[0]
 root.leaf := FALSE
  
 j := 1
 for i from i to 511
     treeNodes[j].symbol := symbolInfo[i].symbol
     treeNodes[j].leaf := TRUE
     mask := mask << (symbolInfo[i].length – bits)
     bits := symbolInfo[i].length
     j := PrefixCodeTreeAddLeaf(treeNodes, j, mask, bits)
     mask := mask + 1
 endfor
  
 return root