#include Huffman.h

unsigned short us_Data_Count=64;
unsigned int fCount[256] = {0};
unsigned int data_num;
unsigned int code_size;
unsigned int last_bit;

void Test_Compress(void)
{
  int i,j,loop;
  HuffNode hfdata[2*us_Data_Count] = {{0, 0, 0, 0, 0}};//Huffman node
  HuffCode code_table[256] = {{0, 0}};    //code table will be searched by subscript
  unsigned char hfcode[2*us_Data_Count];       //output code
  time_t time1, time2;        
/*
//         (9)
//         / \
//         (8) \
//         / \  \
//       (7) \  \
//       / \  \  \
//      / (6) \  \
//       /  / \  \  \
//      03 03 03 07 48
//      4  3  2  1  0
//     (5)(4)(3)(2)(1)
*/
  unsigned char pixel[us_Data_Count] = {
  1,2,3,4, 1,2,3,4, 1,2,3,4, 1,1,1,1};

  FrequencyCount(pixel);
  //set huffman nodes data and weight, i=0:255, j=1:64
  for(i=0, j=1, data_num=0;
    i<256;
    i++)
  {
    if(fCount[i])
    {
      hfdata[j].weight = fCount[i];
      hfdata[j++].data = i;
      data_num ++;
    }
  }
  //build huffman tree and generate huffman code table
  HuffmanCodeTable(hfdata, code_table);
  //compress source data to huffman code using code table
  HuffmanCompress(pixel, hfcode, code_table);
  //initial hfdata and code_table
  for(j=0;
    j<2*us_Data_Count;
    j++)
  {
    hfdata[j].data=0;
    hfdata[j].lchild=0;
    hfdata[j].parent=0;
    hfdata[j].rchild=0;
    hfdata[j].weight=0;
  }
}
void BitPrint(unsigned char *hfcode)
{
  int i, j;
  int endbit = last_bit;
  unsigned char thebyte;
  for (i=0; i < code_size-1; i++) {
    thebyte = hfcode[i];
    for (j=0; j<8; j++) {
      printf("%d", ((thebyte<<j)&0x80)>>7);
    }
  }
  if (last_bit == 7) {
    endbit = -1;
  }
  thebyte = hfcode[i];
  for (j=7; j>endbit; j--) {
    printf("%d", ((thebyte<<(7-j))&0x80)>>7);
  }
}
void HuffmanCompress(unsigned char *pixel, unsigned char *hfcode, HuffCode * code_table)
{
  int i, j;
  int curbit=7; //current bit in _thebyte_
  unsigned int bytenum=0; //number of destination code can also be position of byte processed in destination
  unsigned int ptbyte=0; //position of byte processed in destination
  unsigned int curlength; //code's length of _curcode_
  unsigned char curcode; //current byte's huffman code
  unsigned char thebyte=0; //destination byte write
  unsigned char value; //current byte's value (pixel[])
  //process every byte
  for (i=0; i<us_Data_Count; i++) {
    value = pixel[i];
    curcode = (code_table[value]).code;
    curlength = (code_table[value]).codelength;
    //move out every bit from curcode to destination
    for (j=0;j<=curlength;j++)
    {
      if ((curcode<<j)&0x80)
      {
        thebyte |= (unsigned char)(0x01<<curbit);
      }
      curbit --;
      if (curbit < 0)
      {
        hfcode[ptbyte++] = thebyte;
        thebyte = 0;
        curbit=7;
        bytenum ++;
      }
    }
  }
  //think about which bit is the end
  if (curbit != 7)
  {
    hfcode[ptbyte] = thebyte;
    bytenum ++;
  }
  code_size = bytenum;
  last_bit= curbit;
}
void HuffmanCodeTable(HuffNode *hfdata, HuffCode *code_table)
{
  int i, j; //variable for loop
  int tree_num = 2*data_num - 1; //node of huffman tree
  int min1, min2; //two minimum weight
  int p; //the id of parent node
  unsigned char curcode; //current code being processing
  int curlength; //current code's length
  //build huffman tree
  for (i=data_num; i<tree_num; i++)
  {
    HuffSelect(hfdata, i, &min1, &min2);
    hfdata[min1].parent = i+1;
    hfdata[min2].parent = i+1;
    hfdata[i+1].lchild = min1;
    hfdata[i+1].rchild = min2;
    hfdata[i+1].weight = hfdata[min1].weight + hfdata[min2].weight;
  }
  //generate huffman code
  //i present the i th code, j present from leaf to root in huffman tree
  //hfdata[i].data (0:255) is a byte number
  //编码从叶读到根，按位从高往低压入一个字节，读编码从左向右
  for (i=1; i<=data_num; i++)
  {
    curcode = 0;
    curlength = 0;
    for (j=i, p=hfdata[j].parent; p!=0; j=p, p=hfdata[j].parent)
    {
      curlength ++;
      if (j==hfdata[p].lchild)
        curcode >>= 1;
      else
        curcode = (curcode >> 1) | 0x80; //0x80 = 128 = B1000 0000
    }
    code_table[hfdata[i].data].code = curcode;
    code_table[hfdata[i].data].codelength = curlength;
  }
}
void HuffSelect(HuffNode *hfdata, int end, int *min1, int *min2)
{
  int i; //variable for loop
  int s1, s2;
  HuffNode wath[30];
  for (i=0; i<30; i++)
  {
    wath[i] = hfdata[i];
  }
  s1 = s2 = 1;
  while (hfdata[s1].parent)
  {
    s1++;
  }
  for (i=2; i<=end; i++)
  {
    if (hfdata[i].parent == 0 && hfdata[i].weight < hfdata[s1].weight)
      {
      s1 = i;
    }
  }
  while (hfdata[s2].parent || s1 == s2)
  {
    s2++;
  }
  for (i=1; i<=end; i++)
  {
    if (hfdata[i].parent ==0 && hfdata[i].weight < hfdata[s2].weight && (i - s1))
    {
      s2 = i;
    }
  }
  *min1 = s1;
  *min2 = s2;
}
void FrequencyCount(unsigned char *chs)
{
  int i;
  for (i=0; i<us_Data_Count; i++)
    fCount[*(chs+i)]++;
}