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

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

//模式提取 
 OnButton1()用于从测试文档中提取出测试模式，并且在图形界面中显示出来。 
 OnButton2()将提取出来的测试模式，以自己的文件格式保存。 
//模式压缩软件设计 
 OnButton1()从文档中读入测试数据，显示在图形界面上。 
 OnButton3()对于测试数据，使用 Huffman 编码进行压缩，并且将压缩后的数据以及结
果报告显示在界面上。 
 OnButton4()对于测试数据，使用 Golomb 编码进行压缩，并且将压缩后的数据以及结果
报告显示在界面上。 
 Gethafmtree()根据对码字出现频率的统计，建立哈夫曼树。 
 GetCode()  根据建好的哈夫曼树， 根据根结点到叶子结点的路径， 得到每种码字的编码。  
//模式提取： 
// serveDlg.cpp : implementation file 
// 


#include "stdafx.h" 
#include "serve.h" 
#include "serveDlg.h" 
#include <fstream.h> 
#include "m_input.h" 
#include "Dialog2.h" 
#include "math.h" 
#ifdef _DEBUG 
#define new DEBUG_NEW 
#undef THIS_FILE 
static char THIS_FILE[] = __FILE__; 
#endif 

///////////////////////////////////////////////////////////////////////////// 
// CAboutDlg dialog used for App About 
int chainnumber; 
float numberbeforecode; 
CString str[1000]; 
int width[1000],listnumber; 
int number=0; 
bool compareb(char b[]) 
  {  
   if(b[0]=='S'&&b[1]=='C'&&b[2]=='A'&&b[3]=='N') 
    return true; 
   else return false; 
  } 

bool comparec(char c[]) 
{ 
 if(c[0]=='p'&&c[1]=='a'&&c[2]=='t'&&c[3]=='t'&&c[4]=='e'&&c[5]=='r'&&c[6]=='n') 
  return true; 
  else return false; 
} 
bool compared(char d[]) 
{ 
 if(d[0]=='"'&&d[1]=='='&&d[2]=='"') 
  return true; 
  else return false; 
} 

bool comparee(char e[]) 
{ 
 if(e[0]=='e'&&e[1]=='n'&&e[2]=='d') 
  return true; 
  else return false; 
} 
 
class CAboutDlg : public CDialog 
{ 
public: 
 CAboutDlg(); 
 
// Dialog Data 
 //{{AFX_DATA(CAboutDlg) 
  enum { IDD = IDD_ABOUTBOX }; 
 //}}AFX_DATA 
 
  // ClassWizard generated virtual function overrides 
 //{{AFX_VIRTUAL(CAboutDlg) 
 protected: 
  virtual void DoDataExchange(CDataExchange* pDX);        // DDX/DDV support 
 //}}AFX_VIRTUAL 

// Implementation 
protected: 
 //{{AFX_MSG(CAboutDlg) 
 //}}AFX_MSG 
 DECLARE_MESSAGE_MAP() 
}; 
 
CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD) 
{ 
 //{{AFX_DATA_INIT(CAboutDlg) 
 //}}AFX_DATA_INIT 
} 
 
void CAboutDlg::DoDataExchange(CDataExchange* pDX) 
{ 
 CDialog::DoDataExchange(pDX); 
 //{{AFX_DATA_MAP(CAboutDlg) 
 //}}AFX_DATA_MAP 
} 

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog) 
 //{{AFX_MSG_MAP(CAboutDlg) 
    // No message handlers 
 //}}AFX_MSG_MAP 
END_MESSAGE_MAP() 
 
///////////////////////////////////////////////////////////////////////////// 
// CServeDlg dialog 
 
CServeDlg::CServeDlg(CWnd* pParent /*=NULL*/) 
 : CDialog(CServeDlg::IDD, pParent) 
{ 
 //{{AFX_DATA_INIT(CServeDlg) 
  m_edit = _T(""); 
  //}}AFX_DATA_INIT 
  // Note that LoadIcon does not require a subsequent DestroyIcon in Win32 
 m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME); 
} 
 
void CServeDlg::DoDataExchange(CDataExchange* pDX) 
{ 
 CDialog::DoDataExchange(pDX); 
 //{{AFX_DATA_MAP(CServeDlg) 
  DDX_Text(pDX, IDC_EDIT1, m_edit); 
 //}}AFX_DATA_MAP 
} 

BEGIN_MESSAGE_MAP(CServeDlg, CDialog) 
 //{{AFX_MSG_MAP(CServeDlg) 
 ON_WM_SYSCOMMAND() 
 ON_WM_PAINT() 
 ON_WM_QUERYDRAGICON() 
 ON_EN_CHANGE(IDC_EDIT1, OnChangeEdit1) 
 ON_BN_CLICKED(IDC_BUTTON1, OnButton1) 
 ON_BN_CLICKED(IDC_BUTTON3, OnButton3) 
 ON_BN_CLICKED(IDC_BUTTON4, OnButton4) 
 ON_BN_CLICKED(IDC_BUTTON2, OnButton2) 
 //}}AFX_MSG_MAP 
END_MESSAGE_MAP() 

///////////////////////////////////////////////////////////////////////////// 
// CServeDlg message handlers 
 
BOOL CServeDlg::OnInitDialog() 
{ 
 CDialog::OnInitDialog(); 
 
  // 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()   
{ 
 bool config,config1,config2; 
 char a,b[4],c[7],d[3],e[3],tempb; 
 link p; 
 CString temp0=CString(""); 
 CString temp1=CString(""); 
 int i,j,k,m,num; 
 i=j=k=num=0; 
 config=config1=config2=false; 
 numberbeforecode=0; 
 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); 
   
  for(i=0;i<1000;i++) 
  { 
   str[i]=CString("CHAIN"); 
  } 

 
  m_edit=CString(""); 
 while(!in.eof()) 
 {  
  in>>a; 

  if(i<4) 
   b[i]=a; 
  else 
  { 
   for(m=0;m<3;m++) 
    b[m]=b[m+1]; 
            b[3]=a; 
  } 
  if(i<7) 
   c[i]=a; 
  else 
  { 
   for(m=0;m<6;m++) 
    c[m]=c[m+1]; 
            c[6]=a; 
  } 
  if(i<3) 
   d[i]=a; 
  else 
  { 
   for(m=0;m<2;m++) 
    d[m]=d[m+1]; 
            d[2]=a; 
  } 
if(i<3) 
   e[i]=a; 
  else 
  { 
   for(m=0;m<2;m++) 
    e[m]=e[m+1]; 
            e[2]=a; 
  } 
  i++; 
  if(compareb(b)==true) 
  { 
   config=true; 
    
  } 
  if(comparec(c)==true&&config==true) 
  { 
   config1=true; 
   number++; 
  } 
  if(compared(d)==true&&config1==true)
   config2=true; 
  if((a=='1'||a=='0'||a=='X'||a=='x')&&config2==true) 
  {  
   str[k]=str[k]+a; 
   num++; 
   numberbeforecode++; 
  } 
        
if(a=='"'&&config2==true&&comparee(e)!=true&&compared(d)!=true&&comparec(c)!=true&&
compareb(b)!=true) 
  {  
   config2=false; 
   width[k]=num; 
   k++; 
   num=0; 
  } 
  if(config2==false&&comparee(e)==true&&config==true&&config1==true) 
  { 
   chainnumber=k; 
   k=0; 
   config1=false; 
  } 
 
 } 
  
 for(i=0;i<chainnumber;i++) 
 { 
      str[i]=str[i]+"\r\n"; 
  temp1="number:"; 
  str[i]+=temp1; 
  temp0=""; 
  temp0.Format("%d",number); 
  temp0=temp0+"\r\n"; 
  str[i]+=temp0; 
  temp1="width:"; 
  str[i]+=temp1; 
  temp0=""; 
  temp0.Format("%d",width[i]); 
  temp0=temp0+"\r\n"; 
  str[i]=str[i]+temp0; 
 } 
  
 for(i=0;i<chainnumber;i++) 
      m_edit+=str[i]; 
  
 }  
 UpdateData(false);  
 } 
void CServeDlg::OnButton2()   
{ 
 CFileDialog 
fdlg(FALSE,NULL,NULL,OFN_HIDEREADONLY|OFN_OVERWRITEPROMPT,_T("TXT 
Files(*.txt)|*.txt||"),NULL); 
 if(fdlg.DoModal()==IDOK) 
 {  
  CString strFilePath; 
  strFilePath=fdlg.GetPathName(); 
        ofstream fout(strFilePath); 
  int i,m,n; 
  char b; 
  for(i=0;i<chainnumber;i++) 
  { 
   m=0; 
   fout<<number<<" "; 
   fout<<width[i]<<endl; 
   for(n=0;n<str[i].GetLength();n++) 
   { 
    b=str[i].GetAt(n); 
    if(b=='1'||b=='0'||b=='X'||b=='x') 
    { 
     if(m<width[i]*number) 
     { 
      fout<<b; 
      m++; 
     } 
    } 
   } 
   fout<<endl; 
  } 
 } 
   
} 
/模式压缩软件设计 
// serveDlg.cpp : implementation file 
// 
 
#include "stdafx.h" 
#include "serve.h" 
#include "serveDlg.h" 
#include "m_input.h" 
#include "Dialog2.h" 
#include "math.h" 
#include "fstream" 
#include "vector" 
using namespace std; 
#ifdef _DEBUG 
#define new DEBUG_NEW 
#undef THIS_FILE 
static char THIS_FILE[] = __FILE__; 
#endif 
 
///////////////////////////////////////////////////////////////////////////// 
// CAboutDlg dialog used for App About 
CString str,str1,str2,str3,str4,str5,str6; 
CString cod[1000]; 
vector<CString> vec; 
vector<CString> vec1; 
vector<int>     freqence; 
int bnode[10000]; 
float numberbeforecode; 
int width; 
int length; 
//结构定义； 
struct node 
{ 
 char data; 
  struct node *next; 
}; 
typedef node *link; 
link list; 
struct tnode 
{ 
 int num; 
 int freq; 
 tnode *next; 
 tnode *lchild,*rchild; 
}; 
typedef tnode *tree; 
tree roott; 
 
//  建立哈夫曼树； 
tree Gethafmtree(int bnode[],int length) 
 { 
  tnode head; 
  tree pre,p; 
  head.next=NULL;  
  int w; 
  for(w=0;w<length;w++) 
  { 
   pre=&head; 
   p=head.next; 
   while(p!=NULL&&p->freq<bnode[w]) 
   { 
    pre=p; 
    p=p->next; 
   } 
   tree newtree=new tnode; 
   newtree->freq=bnode[w]; 
   newtree->lchild=NULL; 
   newtree->rchild=NULL; 
   newtree->num=w; 
   pre->next=newtree; 
   newtree->next=p; 
  } 
  for(w=1;w<length;w++) 
  { 
   tree newtree=new tnode; 
   tree first,second; 
   first=head.next; 
   second=first->next; 
   head.next=second->next; 
   newtree->freq=first->freq+second->freq; 
   newtree->lchild=first; 
   newtree->rchild=second; 
   newtree->num=-1; 
   pre=&head; 
   p=head.next; 
   while(p!=NULL&&p->freq<newtree->freq) 
   { 
     pre=p; 
    p=p->next; 
   } 
   pre->next=newtree; 
   newtree->next=p; 
  } 
  return head.next; 
 } 
//遍历哈夫曼树，得到每种码字对应的编码； 
char A[100]; 
void Getcode(tree t,int m) 
{ 
 if(t!=NULL) 
 { 
  if(t->lchild==NULL&&t->rchild==NULL) 
  {  
   int w; 
   for(w=0;w<m;w++) 
   { 
    cod[t->num]=cod[t->num]+A[w]; 
   } 
  } 
  if(t->lchild!=NULL) 
  { 
   A[m]='0'; 
   Getcode(t->lchild,m+1); 
  } 
  if(t->rchild!=NULL) 
  { 
   A[m]='1'; 
   Getcode(t->rchild,m+1); 
  } 
         
 } 
} 
 
 
class CAboutDlg : public CDialog 
{ 
public: 
 CAboutDlg(); 
 
// Dialog Data 
 //{{AFX_DATA(CAboutDlg) 
  enum { IDD = IDD_ABOUTBOX }; 
 //}}AFX_DATA 
 
  // ClassWizard generated virtual function overrides 
 //{{AFX_VIRTUAL(CAboutDlg) 
 protected: 
  virtual void DoDataExchange(CDataExchange* pDX);        // DDX/DDV support 
 //}}AFX_VIRTUAL 
 
// Implementation 
protected: 
 //{{AFX_MSG(CAboutDlg) 
 //}}AFX_MSG 
 DECLARE_MESSAGE_MAP() 
}; 
 
CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD) 
{ 
 //{{AFX_DATA_INIT(CAboutDlg) 
 //}}AFX_DATA_INIT 
} 
 
void CAboutDlg::DoDataExchange(CDataExchange* pDX) 
{ 
 CDialog::DoDataExchange(pDX); 
 //{{AFX_DATA_MAP(CAboutDlg) 
 //}}AFX_DATA_MAP 
} 
 
BEGIN_MESSAGE_MAP(CAboutDlg, CDialog) 
 //{{AFX_MSG_MAP(CAboutDlg) 
    // No message handlers 
 //}}AFX_MSG_MAP 
END_MESSAGE_MAP() 
 
///////////////////////////////////////////////////////////////////////////// 
// CServeDlg dialog 
 
CServeDlg::CServeDlg(CWnd* pParent /*=NULL*/) 
 : CDialog(CServeDlg::IDD, pParent) 
{ 
 //{{AFX_DATA_INIT(CServeDlg) 
  m_edit = _T(""); 
 //}}AFX_DATA_INIT 
  // Note that LoadIcon does not require a subsequent DestroyIcon in Win32 
 m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME); 
} 

void CServeDlg::DoDataExchange(CDataExchange* pDX) 
{ 
 CDialog::DoDataExchange(pDX); 


//{{AFX_DATA_MAP(CServeDlg) 
  DDX_Text(pDX, IDC_EDIT1, m_edit); 
 //}}AFX_DATA_MAP 
} 
 
BEGIN_MESSAGE_MAP(CServeDlg, CDialog) 
 //{{AFX_MSG_MAP(CServeDlg) 
 ON_WM_SYSCOMMAND() 
 ON_WM_PAINT() 
 ON_WM_QUERYDRAGICON() 
 ON_EN_CHANGE(IDC_EDIT1, OnChangeEdit1) 
 ON_BN_CLICKED(IDC_BUTTON1, OnButton1) 
 ON_BN_CLICKED(IDC_BUTTON3, OnButton3) 
 ON_BN_CLICKED(IDC_BUTTON4, OnButton4) 
 ON_BN_CLICKED(IDC_BUTTON2, OnButton2) 
 //}}AFX_MSG_MAP 
END_MESSAGE_MAP() 
 
///////////////////////////////////////////////////////////////////////////// 
// CServeDlg message handlers 
 
BOOL CServeDlg::OnInitDialog() 
{ 
 CDialog::OnInitDialog();