测试模式提取及模式压缩软件设计,huffman编码与golomb码的比较.txt

从 Mentor Graphics 的自动测试图形生成（ATPG）工具 FastScan的 测试文档中提取出测试电路（CUT）的测试模式

  // Add "About..." menu item to system menu. 
 
  // IDM_ABOUTBOX must be in the system command range. 
  ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX); 
  ASSERT(IDM_ABOUTBOX < 0xF000); 
 
  CMenu* pSysMenu = GetSystemMenu(FALSE); 
  if (pSysMenu != NULL) 
 { 
  CString strAboutMenu; 
  strAboutMenu.LoadString(IDS_ABOUTBOX); 
  if (!strAboutMenu.IsEmpty()) 
  { 
   pSysMenu->AppendMenu(MF_SEPARATOR); 
   pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu); 
  } 
 } 
 
  // Set the icon for this dialog.    The framework does this automatically 
  //    when the application's main window is not a dialog 
 SetIcon(m_hIcon, TRUE);   // Set big icon 
  SetIcon(m_hIcon, FALSE);    // Set small icon 
  
  // TODO: Add extra initialization here 
  
  return TRUE;    // return TRUE    unless you set the focus to a control 
} 
 
void CServeDlg::OnSysCommand(UINT nID, LPARAM lParam) 
{ 
  if ((nID & 0xFFF0) == IDM_ABOUTBOX) 
 { 
  CAboutDlg dlgAbout; 
  dlgAbout.DoModal(); 
 } 
 else 
 { 
  CDialog::OnSysCommand(nID, lParam); 
 } 
} 
 
// If you add a minimize button to your dialog, you will need the code below 
//    to draw the icon.    For MFC applications using the document/view model, 
//    this is automatically done for you by the framework. 
 
void CServeDlg::OnPaint()   
{ 
 if (IsIconic()) 
 { 
    CPaintDC dc(this); // device context for painting 
 
  SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0); 
 
    // Center icon in client rectangle 
    int cxIcon = GetSystemMetrics(SM_CXICON); 
    int cyIcon = GetSystemMetrics(SM_CYICON); 
  CRect rect; 
  GetClientRect(&rect); 
    int x = (rect.Width() - cxIcon + 1) / 2; 
    int y = (rect.Height() - cyIcon + 1) / 2; 
 
    // Draw the icon 
  dc.DrawIcon(x, y, m_hIcon); 
 } 
 else 
 { 
  CDialog::OnPaint(); 
 } 
} 
 
// The system calls this to obtain the cursor to display while the user drags 
//  the minimized window. 
HCURSOR CServeDlg::OnQueryDragIcon() 
{ 
  return (HCURSOR) m_hIcon; 
} 
 
void CServeDlg::OnChangeEdit1()   
{ 
  // TODO: If this is a RICHEDIT control, the control will not 
  // send this notification unless you override the CDialog::OnInitDialog() 
  // function and call CRichEditCtrl().SetEventMask() 
  // with the ENM_CHANGE flag ORed into the mask. 
  
  // TODO: Add your control notification handler code here 
  
} 
 
void CServeDlg::OnButton1()   
{ 
 m_edit=""; 
 str=""; 
 char a,tempb; 
 int k=0; 
 int num=0; 
 int line,row,m; 
 link p; 
 CFileDialog 
fdlg(TRUE,NULL,NULL,OFN_HIDEREADONLY|OFN_OVERWRITEPROMPT,_T("TXT 
Files(*.txt)|*.txt||"),NULL); 
 if(fdlg.DoModal()==IDOK) 
 { 
  CString strFilePath; 
  strFilePath=fdlg.GetPathName(); 
        ifstream in(strFilePath); 
  in>>line>>row; 
  numberbeforecode=line*row; 
  width=row; 
  while(!in.eof()) 
  { 
   in>>a; 
   if(a=='1'||a=='0'||a=='-') 
   { 
    str=str+a; 
    k++; 
    num++; 
   } 
  } 
 } 
 str=str+"\r\n"; 
 m_edit+=str; 
 UpdateData(false); 
  
    
  link c=new node; 
 c->data='#'; 
 c->next=NULL; 
 list=c; 
 p=list; 
 for(m=0;m<str.GetLength();m++) 
 { 
  tempb=str.GetAt(m); 
  if(tempb=='1'||tempb=='0'||tempb=='-') 
    { 
     link c=new node; 
     c->data=tempb; 
     p->next=c; 
     p=c; 
    } 
  p->next=NULL; 
  }  
} 
 
void CServeDlg::OnButton3()   
{   
 vec.erase(vec.begin(),vec.end()); 
 vec1.erase(vec1.begin(),vec1.end()); 
 freqence.erase(freqence.begin(),freqence.end()); 
 str1=""; 
 str6=""; 
 int bt; 
 for(bt=0;bt<1000;bt++) 
 { 
  cod[bt]=""; 
 } 
 str2=CString("********************************using  haffman 
code*****************************\r\n"); 
 m_edit+=str2; 
 Cm_input m_input; 
    if(m_input.DoModal()==IDOK) 
 { 
  int blocksize; 
  blocksize=m_input.m_edit1; 
  int i; 
  int j,k,m; 
  char b; 
  CString temp=CString(""); 
  k=0; 
  int temp1; 
  for(i=0;i<str.GetLength();i++) 
  { 
   b=str.GetAt(i); 
   k++; 
   if(k>blocksize) 
   { 
    k=1; 
    vec.push_back(temp); 
    freqence.push_back(1); 
    temp=""; 
   } 
   temp=temp+b; 
   
   
  } 
  if(k<blocksize) 
  { 
   for(i=k;i<blocksize;i++) 
    temp=temp+'-'; 
   vec.push_back(temp); 
   freqence.push_back(1); 
  }  
  
//--------------------------------------------------------- right!  
  vec1=vec; 
  int dddd=0; 
  for(i=0;i<vec1.size();i++) 
  { 
   j=i+1; 
   while(j<vec1.size()) 
   { 
    if(vec1[i]==vec1[j]) 
    {    
     dddd++; 
     freqence[i]=freqence[i]+freqence[j]; 
     freqence.erase(freqence.begin()+j); 
     vec1.erase(vec1.begin()+j); 
    } 
    else 
     j++; 
   } 
  } 
 
//------------------------------------------------right; 
 
  for(i=0;i<freqence.size();i++) 
  { 
   for(j=i+1;j<freqence.size();j++) 
   { 
    if(freqence[i]<freqence[j]) 
    { 
     temp1=freqence[i]; 
     freqence[i]=freqence[j]; 
     freqence[j]=temp1; 
     temp=vec[i]; 
     vec[i]=vec[j]; 
     vec[j]=temp; 
    } 
   } 
  } 
//------------------------------------------------------right 
  for(i=0;i<vec1.size();i++) 
  { 
   j=i+1; 
   while(j<vec1.size()) 
   { 
    bool xiangrong=true; 
    for(m=0;m<blocksize;m++) 
    { 
if((vec1[i].GetAt(m)=='1'&&vec1[j].GetAt(m)=='0')||(vec1[i].GetAt(m)=='0'&&vec1[j].GetA    
t(m)=='1')) 
      xiangrong=false; 
    } 
    if(xiangrong==true) 
    { 
     temp=CString(""); 
     for(m=0;m<blocksize;m++) 
     { 
      if(vec1[i].GetAt(m)==vec1[j].GetAt(m)) 
      { 
       temp=temp+vec1[i].GetAt(m); 
      } 
      else 
      { 
       if(vec1[i].GetAt(m)=='-') 
        temp=temp+vec1[j].GetAt(m); 
       if(vec1[j].GetAt(m)=='-') 
        temp=temp+vec1[i].GetAt(m); 
      } 
     } 
     for(m=0;m<vec.size();m++) 
     { 
      if(vec[m]==vec1[i]||vec[m]==vec1[j]) 
       vec[m]=temp; 
     } 
     vec1.erase(vec1.begin()+j); 
     freqence[i]=freqence[i]+freqence[j]; 
     freqence.erase(freqence.begin()+j); 
     vec1[i]=temp; 
    } 
    else 
     j++; 
    
   } 
  } 
  
  for(i=0;i<freqence.size();i++) 
  { 
   bnode[i]=freqence[i]; 
  } 
  length=freqence.size(); 
  tree roott; 
  roott=Gethafmtree(bnode,length); 
  Getcode(roott,0); 
  for(i=0;i<vec.size();i++) 
  { 
   for(j=0;j<vec1.size();j++) 
   { 
    if(vec[i]==vec1[j]) 
    { 
     str1=str1+cod[j]; 
    } 
   } 
  } 
  str1=str1+"\r\n"; 
  m_edit+=str1; 
  float numberafterHuffmancode=0; 
  float xyz; 
  CString xyz1; 
  numberafterHuffmancode=numberafterHuffmancode+str1.GetLength(); 
  xyz=(numberbeforecode-numberafterHuffmancode)/numberbeforecode; 
  xyz1=CString(""); 
  xyz1.Format("%d",blocksize); 
  str6+="blocksize:"; 
  str6+=xyz1; 
  str6=str6+"\r\n"; 
  xyz1=CString(""); 
  xyz1.Format("%f",numberbeforecode); 
  str6+="numberbeforecode:"; 
  str6+=xyz1; 
  str6=str6+"\r\n"; 
  xyz1=CString(""); 
  xyz1.Format("%f",numberafterHuffmancode); 
  str6+="numberafterHuffmancode:"; 
  str6+=xyz1; 
  str6=str6+"\r\n"; 
  xyz1=CString(""); 
  xyz1.Format("%f",xyz); 
  str6+="compression:"; 
  str6+=xyz1; 
  str6=str6+"\r\n"; 
  m_edit+=str6; 
  UpdateData(false); 
 } 
} 
//----------------------------------------------------------------> Golomb Code 
void CServeDlg::OnButton4()   
{ 
 str4=""; 
 str5=""; 
  
 str3=CString("********************************using  Golomb 
code*****************************\r\n"); 
 m_edit+=str3; 
 CDialog2 Dialog2; 
 if(Dialog2.DoModal()==IDOK) 
 { 
  int m_value; 
  m_value=Dialog2.m_edit2; 
  int i,j,m; 
  link temp[10000],p,p1,p2,p3,ordered_list[10000],or_list[10000]; 
   for(j=0;j<10000;j++) 
   {  
    link a=new node; 
    a->data='#'; 
    a->next=NULL; 
    temp[j]=a; 
   } 
   for(j=0;j<10000;j++) 
   {  
    link a=new node; 
    a->data='#'; 
    a->next=NULL; 
    or_list[j]=a; 
   } 
   p=list->next; 
   int k=0; 
    
   j=0; 
   p1=temp[j]; 
   while(p!=NULL) 
   { 
    link a=new node; 
    a->data=p->data; 
    a->next=NULL; 
    if(k<width) 
    { 
     p1->next=a; 
     p1=a; 
    } 
    else 
    { 
     k=0; 
     j++; 
     p1=temp[j]; 
     p1->next=a; 
     p1=a; 
    } 
    k++; 
    p=p->next; 
   } 
//-------------------------------------------------------------------------------// 
   int tempnumber=j,the_next_input;// 排序。 
   p=temp[0]->next; 
   k=0; 
   while(p!=NULL)//第一行测试向量的初始化。 
   { 
    if(p->data!='1'&&p->data!='0') 
     p->data='0'; 
    p=p->next; 
   } 
   ordered_list[0]=temp[0]->next; 
   temp[0]->next=NULL; 
   while(tempnumber>=0) 
   {  
    int MIN=1000000; 
    for(m=1;m<=j;m++) 
    {  
     p=ordered_list[k]; 
     p1=temp[m]->next; 
     if(p1!=NULL) 
     { 
      int hmjl=0; 
      while(p!=NULL&&p1!= NULL) 
      { 
      
 if((p->data=='1'&&p1->data=='0')||(p->data=='0'&&p1->data=='1')) 
        hmjl++; 
       p=p->next; 
       p1=p1->next; 
      } 
      if(hmjl<=MIN) 
      { 
       MIN=hmjl; 
       the_next_input=m; 
     } 
     } 
    } 
    k++; 
    ordered_list[k]=temp[the_next_input]->next; 
    temp[the_next_input]->next=NULL; 
    p2=ordered_list[k-1]; 
    p3=ordered_list[k]; 
    while(p2!=NULL&&p3!=NULL) 
    { 
     if(p3->data=='-') 
      p3->data=p2->data; 
     p2=p2->next; 
     p3=p3->next; 
    } 
    tempnumber--; 
   } 
//----------------------------------------------------------------------------------------// 
   or_list[0]->next=ordered_list[0];//异或。 
   for(m=1;m<=j;m++) 
   { 
    p=ordered_list[m]; 
    p1=ordered_list[m-1]; 
    p2=or_list[m]; 
    while(p!=NULL&&p1!=NULL) 
    { 
     if(p->data==p1->data) 
     { 
      link a=new node; 
      a->data='0'; 
      p2->next=a; 
      p2=a; 
     } 
     else 
     { 
      link a=new node; 
      a->data='1'; 
      p2->next=a; 
      p2=a; 
     } 
     p2->next=NULL; 
     p=p->next; 
     p1=p1->next; 
    } 
   } 
//-----------------------------------------------------------------------------------// 
//编码： 
   for(m=0;m<j;m++) 
   { 
    p=or_list[m]->next; 
    while(p->next!=NULL) 
    { 
     p=p->next; 
    } 
    p->next=or_list[m+1]->next; 
   } 
   int serialnumber=0; 
   int come,in,fly,pala,paladin; 
   CString ctt; 
   ctt=""; 
   p=or_list[0]->next; 
   while(p!=NULL) 
   { 
    if(p->data=='0') 
     serialnumber++; 
    if(p->data=='1') 
    { 
     come=serialnumber/m_value; 
     for(m=0;m<come;m++) 
     { 
      ctt=ctt+'1'; 
     } 
     ctt=ctt+"0"; 
     in=serialnumber%m_value; 
     fly=m_value; 
     paladin=ctt.GetLength(); 
     while(fly>2) 
     { 
      pala=in%2; 
      if(pala==0) 
       ctt.Insert(paladin,"0"); 
      if(pala==1) 
       ctt.Insert(paladin,"1"); 
      in=in/2; 
      fly=fly/2; 
     } 
     if(in==1) 
      ctt.Insert(paladin,"1"); 
     if(in==0) 
      ctt.Insert(paladin,"0"); 
     str4+=ctt; 
     ctt=""; 
     serialnumber=0; 
    } 
    p=p->next; 
   } 
   if(serialnumber!=0) 
   { 
    come=serialnumber/m_value; 
    for(m=0;m<come;m++) 
     { 
      ctt=ctt+'1'; 
     } 
     ctt=ctt+"0"; 
     in=serialnumber%m_value; 
     fly=m_value; 
     paladin=ctt.GetLength(); 
     while(fly>2) 
     { 
      pala=in%2; 
      if(pala==0) 
       ctt.Insert(paladin,"0"); 
      if(pala==1) 
       ctt.Insert(paladin,"1"); 
      in=in/2; 
      fly=fly/2; 
     } 
     if(in==1) 
      ctt.Insert(paladin,"1"); 
     if(in==0) 
      ctt.Insert(paladin,"0"); 
     str4+=ctt; 
     ctt=""; 
   } 
   str4=str4+"\r\n"; 
   m_edit+=str4; 
  float numberafterGolombcode=0; 
  float xyz; 
  CString xyz1; 
  numberafterGolombcode=numberafterGolombcode+str4.GetLength(); 
  xyz=(numberbeforecode-numberafterGolombcode)/numberbeforecode; 
  xyz1=CString(""); 
  xyz1.Format("%d",m_value); 
    str5+="the value of m:"; 
  str5+=xyz1; 
  str5=str5+"\r\n"; 
  xyz1=CString(""); 
  xyz1.Format("%f",numberbeforecode); 
  str5+="numberbeforecode:"; 
  str5+=xyz1; 
  str5=str5+"\r\n"; 
  xyz1=CString(""); 
  xyz1.Format("%f",numberafterGolombcode); 
  str5+="numberafterGolombcode:"; 
  str5+=xyz1; 
  str5=str5+"\r\n"; 
  xyz1=CString(""); 
  xyz1.Format("%f",xyz); 
  str5+="compression:"; 
  str5+=xyz1; 
  str5=str5+"\r\n"; 
  m_edit+=str5; 
  UpdateData(false); 
  //chainnumber=chainnumber+listnumber+2; 
   
  } 
}