mcs/class/ByteFX.Data/Common/HuffmanTree.cs

   1 using System;\r
   2 \r
   3 namespace ByteFX.Data.Common\r
   4 {\r
   5         /// <summary>\r
   6         /// Summary description for HuffmanTree.\r
   7         /// </summary>\r
   8         public class HuffmanTree\r
   9         {\r
  10                 const int MAX_BITS = 15;\r
  11                 int[]   codes;\r
  12 \r
  13                 public HuffmanTree(bool lit)\r
  14                 {\r
  15                         if (lit)\r
  16                                 BuildLitTree();\r
  17                         else\r
  18                                 BuildLenTree();\r
  19                 }\r
  20 \r
  21                 private void BuildLitTree()\r
  22                 {\r
  23                         codes = new int[288];\r
  24 \r
  25                         // fill the code slots with code lengths first\r
  26                         for (int x=0; x < 144; x++)\r
  27                                 codes[x] = 8;\r
  28                         for (int x=144; x < 256; x++)\r
  29                                 codes[x] = 9;\r
  30                         for (int x=256; x < 280; x++)\r
  31                                 codes[x] = 7;\r
  32                         for (int x=280; x < 288; x++)\r
  33                                 codes[x] = 8;\r
  34 \r
  35                         BuildTreeCommon();\r
  36                 }\r
  37 \r
  38 \r
  39                 private void BuildLenTree()\r
  40                 {\r
  41                         BuildTreeCommon();\r
  42                 }\r
  43 \r
  44                 private void BuildTreeCommon()\r
  45                 {\r
  46                         int[] codecounts = new int[MAX_BITS];\r
  47                         int[] codebase = new int[MAX_BITS];\r
  48 \r
  49                         for (int i = 0; i < codes.Length; i++) \r
  50                         {\r
  51                                 int bit_len = codes[i];\r
  52                                 if (bit_len > 0)\r
  53                                         codecounts[bit_len]++;\r
  54                         }\r
  55 \r
  56                         // now we compute the intial value for each code length\r
  57                         int code = 0;\r
  58                         codecounts[0] = 0;\r
  59                         for (int bits = 1; bits <= MAX_BITS; bits++) \r
  60                         {\r
  61                                 code = (code + codecounts[bits-1]) << 1;\r
  62                                 codebase[bits] = code;\r
  63                         }\r
  64 \r
  65                         // next we assign numerical values to each code\r
  66                         for (int x=0;  x <= codes.Length; x++) \r
  67                         {\r
  68                                 if (codes[x] == 0) continue;\r
  69                                 int blen = codes[x];\r
  70                                 codes[x] = codebase[ blen ];\r
  71                                 codebase[ blen ] ++;\r
  72                         }\r
  73                 }\r
  74 \r
  75         }\r
  76 }\r