golomb_compress.txt

一种基于多扫描链相容 压缩的 Golomb 码的压缩方法。这种方法首先把原始测试集的测试向量转变成多扫 描链的形式

    trpt[i]=temp[i]; 
  temp.clear (); 
} 
//----―――-sort the vectors to make the diffrences between near  vectors least--------- 
void sort(vector<vector<int> >& graph,vector<int>& w,int len,int nrow) 
{ 
  int i,j,min; 
  int k; 
    int *flag=new int[nrow]; 
  for(i=0;i<nrow;i++) 
    flag[i]=0; 
    i=0; 
  k=0; 
  while(k!=nrow) 
 {  
    flag[i]=-1; 
    w[k]=i; 
    min=len+1; 
    for(j=0;j<nrow;j++) 
   if((flag[j]!=-1)&&(graph[i][j]<min)) 
   { 
    min=graph[i][j]; 
    i=j;                                 
   } 
  k++; 
 } 
  delete[] flag; 
} 
 
//-----------------------------XOR operration------------------------------ 
void xor(vector<char>& trpt,int len,int nrow) 
{ 
  int i,j; 
  vector<vector<char> > temp1; 
  for(i=0;i<nrow;i++) 
    { 
    vector<char> temp; 
    for(j=0;j<len;j++) 
        { 
   temp.insert(temp.end(),'0'); 
  } 
    temp1.insert(temp1.end(),temp); 
 } 
  for(i=1;i<nrow;i++) 
    for(j=0;j<len;j++) 
  { 
   if(trpt[i*len+j]=='-'||trpt[(i-1)*len+j]=='-') 
    temp1[i][j]='0'; 
   else 
    if(trpt[i*len+j]==trpt[(i-1)*len+j]) 
     temp1[i][j]='0'; 
    else 
     temp1[i][j]='1'; 
  } 
  for(i=1;i<nrow;i++) 
    for(j=0;j<len;j++) 
   trpt[i*len+j]=temp1[i][j]; 
  temp1.clear(); 
} 
 
void xorvector(vector<char>& trpt,int len,int nrow)         
{ 
  vector<vector<int> > graph; 
  int i,j,k,t; 
  int cost; 
  vector<int> w(nrow);                            
  vector<char> temp(len*nrow); 
  for(i=0;i<nrow;i++) 
    { 
    vector<int> temp; 
    for(j=0;j<nrow;j++) 
        { 
   temp.insert(temp.end(),len+1); 
  } 
    graph.insert(graph.end(),temp); 
 } 
  for(i=0;i<nrow;i++)                               //set the graph with costs                  
    for(j=0;j<nrow;j++) 
  { 
   k=0; 
   cost=0; 
   while (k<len) 
   { 
    if((trpt[i*len+k]!='-')&&(trpt[j*len+k]!='-')) 
     if(trpt[i*len+k]!=trpt[j*len+k]) 
     { 
      cost++; 
      k++; 
     } 
        else 
          k++; 
       else 
         k++; 
   } 
   if(i!=j) 
    graph[i][j]=cost; 
  } 
  /*for(i=0;i<nrow;i++) 
 {  
    for(j=0;j<nrow;j++) 
   cout<<graph[i][j]<<" ";     
    cout<<endl; 
 }*/ 
  sort(graph,w,len,nrow);             //sort the test vectors    
   /* for(i=0;i<nrow;i++) 
    cout<<w[i]<<" "; 
  cout<<endl;*/ 
  for(i=0;i<nrow;i++)                 //change the pattern  
 {                                
    t=w[i]; 
    for(j=0;j<len;j++) 
   temp[i*len+j]=trpt[t*len+j]; 
 } 
  for(i=0;i<nrow*len;i++) 
    trpt[i]=temp[i]; 
 
  for(i=0;i<len;i++)                             //first pattern set value 
 { 
    if((trpt[i]=='-')&&(trpt[len+i]=='0')) 
   trpt[i]='0'; 
  else 
   if((trpt[i]=='-')&&(trpt[len+i]=='1')) 
    trpt[i]='1'; 
   else 
    if((trpt[i]=='-')&&(trpt[len+i]=='-')) 
     trpt[i]='0'; 
 } 
 
    xor(trpt,len,nrow);               //xor operation 
 
  graph.clear(); 
  w.clear(); 
  temp.clear(); 
} 
 
//-------------------golomb code(the second compression)---------------------------- 
 
int count0s(vector<char>& trpt,vector<int>& count,int len,int nrow) 
{ 
  int i,t,k; 
  int length=len*nrow; 
  i=len; 
  t=0;      // the number of "0" 
  k=0; 
  while(i<length) 
 { 
    if(trpt[i]!='1') 
  { 
   i++; 
   t++; 
  } 
  else                             
  { 
   count.insert(count.end(),t); 
   t=0; 
   k++; 
   i++; 
  } 
 } 
    count.insert(count.end(),t); 
  if(t==0) 
  k--; 
  /*for(int j=0;j<=k;j++) 
    cout<<count[j]<<" "; 
  cout<<endl;*/ 
 
  return k; 
} 
 
int golomb(FILE *fo,vector<int>& count,int n,int k) 
{ 
  int i,j,s,t,u; 
  int ren=0;          //the sizes of the test vectors 
  int l; 
  for(i=0;i<=k;i++) 
 { 
  t=0; 
    l=count[i]; 
    if((l+1)%n!=0) 
   s=((l+1)/n)+1; 
  else 
   s=(l+1)/n; 
    //cout<<s<<endl; 
    for(j=1;j<s;j++) 
  { 
   fprintf(fo,"%c",'1'); 
   ren++; 
  } 
    fprintf(fo,"%c",'0'); 
  ren++; 
    l=l-n*(s-1); 
    u=int(log10(n)/log10(2)); 
    for(j=u-1;j>=0;j--) 
  { 
   t=l/int(pow(2,j));                               
   fprintf(fo,"%d",t); 
   ren++; 
   l=l-int(t*pow(2,j)); 
  }  
    fprintf(fo,"%s\n"," "); 
 }  
  return ren; 
} 
//-------------------main function--------------------------------------- 
void main() 
{ 
  char inputfile[40],outputfile[40];          //file of input,file of output  
  char resultfile[40];                      //file of result 
  FILE *fi,*fo;                //the point of the input,the output 
  FILE *fr;                  //the point of the result file 
  int width;                   //the width of the pattern 
  int nrow;                    //the row number of the pattern 
    int m;                       //the number of the scan chains 
    int d,wf;                    //d is the length of subvector,wf is the width of 
transfered pattern 
  int sum;                     //the number of vectors after the first compression   
  int len;                     //the length of the vectors having been reseted 
  int ren;                     //the sizes of the test vectors after the second 
compression 
//open the file  
  cout<<"input file:"; 
  cin>>inputfile; 
  if((fi=fopen(inputfile,"r"))==NULL) 
 { 
    cout<<inputfile<<"could not be opened"<<endl; 
    exit(0); 
 } 
  
  cout<<"the file of output:"; 
  cin>>outputfile; 
  if((fo=fopen(outputfile,"w"))==NULL) 
 { 
    cout<<"could not open"<<outputfile<<endl; 
    exit(0); 
 } 
  
  cout<<"the file of result:"; 
  cin>>resultfile;                             
  if((fr=fopen(resultfile,"w"))==NULL) 
 { 
    cout<<"could not open"<<resultfile<<endl; 
    exit(0); 
 } 
//read the width and the row number of the pattern 
 
  fscanf(fi,"%d",&width); 
  if(width==0) 
 { 
    cout<<"there are no patterns"; 
    exit(0); 
 } 
  fscanf(fi,"%d",&nrow); 
  if(nrow==0) 
 { 
      cout<<"there are no patterns"; 
    exit(0); 
    }    
  fprintf(fo,"%s","the width and the row number of the pattern:"); 
  fprintf(fo,"width="); 
  fprintf(fo,"%d%s",width,"  "); 
  fprintf(fo,"nrow="); 
  fprintf(fo,"%d\n",nrow);   
//input the number of the scan chains 
 
    cout << "input the number of the scan chains m(width):"; 
    cin >> m; 
    fprintf(fo,"%s","the number of the scan chains m:"); 
    fprintf(fo,"%d\n",m); 
 
  if(width%m==0) 
    d=width/m; 
  else 
    d=width/m+1; 
  wf=d*nrow; 
  fprintf(fo,"%s","the length of subvector d: "); 
  fprintf(fo,"%d\n",d); 
 
  vector<char> trpt(wf*m); 
  char *pt=new char[width*nrow];                 //read datas in the file    
  char ch; 
  int i=0;                                
  while((ch=fgetc(fi))!=EOF) 
 { 
    if(ch!='\n') 
  { 
   pt[i]=ch; 
   i++; 
  } 
    }    
    //fprintf(fo,"%s",pt);   
//transfer the pattern to the multiscan chains     
   transferpattern(pt,trpt,m,width,nrow); 
  /* for(i=0;i<(wf*m);i++) 
       fprintf(fo,"%c",trpt[i]);*/ 
   fprintf(fo,"%s","the number of the all test vector before the compression: "); 
   fprintf(fo,"%d\n",nrow*width); 
 
//compatible compression (the first compression) 
 
   sum=compatipression(fo,trpt,wf,m); 
   fprintf(fo,"%s","the number of the test vectors after the compatible compression: 
"); 
   fprintf(fo,"%d\n",sum); 
   fprintf(fo,"%s","the  number of  the  all test  vector after the compatible compression: 
"); 
   fprintf(fo,"%d\n",sum*wf); 
 
//output the result 
 
     fprintf(fr,"%s\n","the vectors after first compression:"); 
   compatioutput(fr,trpt,sum,wf); 
   fprintf(fr,"%s\n"," "); 
 
//reset the test vectors 
   reset(trpt,wf,sum); 
   len=sum*d; 
   fprintf(fr,"%s\n","the vectors after reseting:"); 
   compatioutput(fr,trpt,nrow,len); 
   fprintf(fr,"%s\n"," "); 
   
//the second compression(GOLOMB CODE commpression) 
 
//one,seek the sequence of the different vectors(差分向量) of the test streems  
  xorvector(trpt,len,nrow);                                     //including  set                             
graph with values,sort and "XOR" operation 
    fprintf(fr,"%s\n","the pattern after xor operation:"); 
    compatioutput(fr,trpt,nrow,len); 
  fprintf(fr,"%s\n"," "); 
 
//two,the compression (GOLOMB CODE) 
 
  int n;             //the GOLOMB code parameter m 
  vector<int> count; 
  int k; 
  cout<<"the golomb code parameter n(2,4,8,16....):"; 
  cin>>n;            //usually m=4; 
  fprintf(fo,"%s","the golomb code parameter n: "); 
  fprintf(fo,"%d\n",n); 
  fprintf(fr,"%s\n","the vectors after the second compression using GOLOMB codes:"); 
  for(i=0;i<len;i++) 
     fprintf(fr,"%c",trpt[i]); 
    fprintf(fr,"%s\n"," ");   
  k=count0s(trpt,count,len,nrow);  //count the number of "0" 
  ren=golomb(fr,count,n,k);        //compression using GOLOMB codes 
  fprintf(fo,"%s","the size of the vectors after compression using GOLOMB codes is:"); 
  fprintf(fo,"%d\n",ren+len); 
  float rate; 
  rate=(float(width*nrow-ren-len)/float(width*nrow)); 
  fprintf(fo,"%s","the rate of the compression is:"); 
  fprintf(fo,"%f\n",rate); 
 
// close the file  
  fclose(fi); 
  fclose(fo); 
  fclose(fr); 
  count.clear(); 
  trpt.clear(); 
 
}