相容+fdr.txt

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

     for(j=0;j<sum;j++)
     temp[i*sum+j]=trpt[j*wf+i];
      for(i=0;i<wf*sum;i++)
        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();
}

//-------------------FDR 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 FDR(FILE *fo,vector<int>& count,int k)
{ int i,j;
  int ren=0;
  int l,m;
  for(m=0;m<=k;m++)
   { 
     int s=0;
	 l=count[m];
     if ((log10(l+3)/log10(2)-1)==int((log10(l+3)/log10(2)-1)))
             j=int((log10(l+3)/log10(2)-1));
     else
             j=int((log10(l+3)/log10(2)-1))+1;
     for(i=1;i<j;i++) 
	 {
	   fprintf(fo,"%c",'1');
       ren++;
       s=s+pow(2,i);
	 }
     fprintf(fo,"%c",'0');
     ren++;
     l=l-s;
     for(i=(j-1);i>=0;i--)
	 {
       s=int(l/pow(2,i));
       fprintf(fo,"%d",s);
       ren++;
       l=l-s*int(pow(2,i));
	 }
     fprintf(fo,"%s\n"," ");//cout<<" ";
  }
	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(FDR CODE commpression)
//one,seek the sequence of the different vectors(差分向量) 
//of the test streems xorvector(trpt,len,nrow);
//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"," ");
fprintf(fr,"%s\n","the pattern after xorvector operation:");
xorvector(trpt,nrow,len);
compatioutput(fr,trpt,nrow,len);
fprintf(fr,"%s\n"," ");
//two,the compression (FDR CODE)
vector<int> count;
int k;
fprintf(fr,"%s\n","the vectors after the second compression using FDR codes:");
for(i=0;i<len;i++)
fprintf(fr,"%c",trpt[i]);
fprintf(fr,"%s\n"," ");
k=count0s(trpt,count,len,nrow);                                  
ren=FDR(fr,count,k);                      //compression using FDR codes
fprintf(fo,"%s","the size of the vectors after compression using FDR 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();
}