Huffman coding

這幾天不小心看到學生時代寫的影像處理程式huffman coding
畢業後工作到現在總覺得那時候是寫程式的巔峰
回頭看看程式發現，原來這幾年還是有進步的

那時候對bitwise的運算掌握很差
很多運算都是搬 % / * 甚至數學的 pow 來做
原本幾十行幾百行的code經過整理竟然還可以整理到只有十幾行
也難怪啦！畢竟待在硬體的公司這方面會熟悉也不意外



這次重新想了一下發現decoder部分還寫錯
會發生decode錯的問題，以前助教竟然沒發現

把code改寫整理起來
過幾年再來看是否又有新的心得

class TreeNode
{
public:
 int data;
 int frequency;

 TreeNode *OwnNode;
 TreeNode *ParentNode;
 TreeNode *LeftChildNode;
 TreeNode *RightChildNode;
};

/* structures for defining HUFFMAN */
typedef struct tagHUFFMANINFOHEADER
{
 WORD hiType;    // Specifies the file type, must be HF.
 LONG hiWidth;   // Specifies the width of the huffman, in pixels.
 LONG hiHeight;   // Specifies the height of the huffman, in pixels.
 WORD hiBitCount;   // Specifies the number of bits-per-pixel.
} HUFFMANINFOHEADER, *PHUFFMANINFOHEADER;

typedef struct tagCODEBOOK
{
 BYTE cbBitCount;
 WORD cbCompression;
} CODEBOOK;

typedef struct tagHUFFMANINFO
{ 
 HUFFMANINFOHEADER hfiHeader;
 CODEBOOK   hfiCodeBook[256];
} HUFFMANINFO, *PHUFFMANINFO;

void print (int y, int x, char* s) {
 COORD p = { x, y };
 SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), p);
 printf("%s", s);
}

void dump_tree(TreeNode *treenode, int y, int x) {
 char buffer[50];
 sprintf(buffer, "%d", treenode->data);

 if (treenode->data == -1)
  print(y, x, "x");
 else
  print(y, x, buffer);

 int offset = 16>>(y/2+1);
 if (treenode->LeftChildNode != NULL)
 {
  print(y+1, x-offset, "/");
  dump_tree(treenode->LeftChildNode, y+2, x-2*offset);
 }

 if (treenode->RightChildNode != NULL)
 {
  print(y+1, x+offset, "\\");
  dump_tree(treenode->RightChildNode, y+2, x+2*offset);
 }
}

TreeNode* root;
CODEBOOK CodeBook[256];
char CompressionData[1000];
int cmp_count;

void huffman_encode(int n, unsigned char *input) {
 int i, j;
 const int LevelCount = 256;
 const int SearchCount = 2*LevelCount-1;

 int FrequencyTable[LevelCount]={0};
 TreeNode *SearchList[SearchCount]={NULL};

 // Step1：統計各 gray level 的 frequency
 for (i=0; idata = i;
   SearchList[i]->frequency = FrequencyTable[i];
   SearchList[i]->OwnNode = SearchList[i];
   SearchList[i]->ParentNode = NULL;
   SearchList[i]->LeftChildNode = NULL;
   SearchList[i]->RightChildNode = NULL;
  }
  else
   SearchList[i] = NULL;
 }

 // Step3：建立樹
 int ParentNullNode;
 do
 {
  // 3.1 找兩筆最小 frequency 的
  int min, min2;
  int selectnode1, selectnode2;
  min = 1024*1024;
  min2 = min;
  for (i=0; iParentNode == NULL)
   {
    if (SearchList[i]->frequency <= min)
    {
     if (min <= min2)
     {
      min2 = min;
      selectnode2 = selectnode1;
     }
     min = SearchList[i]->frequency;
     selectnode1 = i;
    }
    else if (SearchList[i]->frequency <= min2)
    {
     min2 = SearchList[i]->frequency;
     selectnode2 = i;
    }
   }
  }
  // 3.2 從 256 以後找個空位置新增 node merge 這兩筆資料並且修改此兩筆資料的 parent 欄位
  for (i=LevelCount;idata = -1; // NULL
    SearchList[i]->frequency = SearchList[selectnode1]->frequency + SearchList[selectnode2]->frequency;
    SearchList[i]->OwnNode = SearchList[i];
    SearchList[i]->ParentNode = NULL;
    SearchList[i]->LeftChildNode = SearchList[selectnode2]->OwnNode;
    SearchList[i]->RightChildNode = SearchList[selectnode1]->OwnNode;

    SearchList[selectnode1]->ParentNode = SearchList[i];
    SearchList[selectnode2]->ParentNode = SearchList[i];
    break;
   }
  }
  // 3.3 判斷是否只剩下一個 node 沒有 parent (就是 root 沒有 parent) 則跳出
  ParentNullNode=0;
  for (i=0;iParentNode == NULL)
   {
    ParentNullNode++;
    root = SearchList[i]->OwnNode;
   }
  }
 } while (ParentNullNode != 1);
 
 // 印出樹
 //dump_tree(SearchList[SearchCount-1]->OwnNode, 0, 32);
 //print(20, 0, "");
 //for (i=0;i %d:(%d)%d:%d\n", i+1, SearchList[i]->LeftChildNode, SearchList[i]->OwnNode, SearchList[i]->ParentNode, SearchList[i]->RightChildNode);
 
 // Step4：產生編碼
 int NodeCount;
 int code;
 TreeNode *ptrnode;
 for (i=0;iOwnNode;
   code = 0;
   while (ptrnode->ParentNode != NULL)
   {
    if (ptrnode->ParentNode->LeftChildNode == ptrnode)
     code += (1<ParentNode;
   };

   // 4.2 把 code 反向從 root 到 leaf 的格式給 decoder 用
   int new_code = 0;
   for (j=0; j>j & 0x1)<<(NodeCount-1-j);

   CodeBook[i].cbBitCount = NodeCount;
   CodeBook[i].cbCompression = new_code;
   printf("%d => %d:%x\n", SearchList[i]->data, NodeCount, (int)code);
  }
 }

 // Step5：開始編碼
 int buffer = 0;
 int ptrbuf = 0;

 for (i=0; i 255)
  {
   BYTE byte = buffer & 0xff;
   buffer >>= 8;
   ptrbuf -= 8;

   printf("%d,", byte);
   CompressionData[cmp_count] = byte;
   cmp_count++;
  }
 }
 if (buffer > 0)
 {
  printf("%d\n", buffer);
  CompressionData[cmp_count] = buffer;
 }
}

void huffman_decode(int n) {
 int i, j;

 int code = 0;
 char buffer = CompressionData[0], cmp_ptr = 0;
 int ptrbuf = 7, ptr = 0;
 i = 0;
 TreeNode* current = root->OwnNode;
 do 
 {
  code = buffer & 0x1;
  buffer >>= 1;
  ptr++;

  if (code)
   current = current->LeftChildNode;
  else
   current = current->RightChildNode;

  if (current->LeftChildNode == NULL && current->RightChildNode == NULL)
  {
   printf("%d,", current->data);

   current = root->OwnNode;
   ptrbuf -= ptr;
   ptr = 0;
   code = 0;
   i++;
  }

  if (ptr > ptrbuf)
  {
   cmp_ptr++;
   buffer = CompressionData[cmp_ptr];
   ptrbuf = 7;
   ptr = 0;
  }

 } while (i < n);
}

int _tmain(int argc, _TCHAR* argv[])
{
 // assume data is a gray level from 0 to 255
 unsigned char data[] = {0,0,1,2,3,4,5,1,1,1,1,1,1,1,1,1,2,2,2,2,3,3,4,4,4,4,4,150,255,255,255,255};

 huffman_encode(sizeof(data)/sizeof(unsigned char), data);

 huffman_decode(sizeof(data)/sizeof(char));

 return 0;
}