compression12.cpp

对流数据的压缩

// compression12.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "math.h"

void patternfmat(char *,char *,int,int,int);

int compgraphset(char *,int *,int,int);
int maxcliquegreedy(FILE *,int *,int *,int,int);
int comppatdelete(char *,int *,int,int,int);
int rowcompalg(FILE *,char *,int,int);//first compression

void matrixoutput(FILE *,char *,int,int);

//int alterrunlen(FILE *,char *,int);
//int shiftedfdr(FILE *,int);





//***********************main function*************************


int main(int argc, char* argv[])
{

	char sourcename[35];       //filename for input
	char destinationname[35];  //filename for output(related information)
	char resultname[35];       //filename for result
    int width = 0;             //the width of test patterns
    int number = 0;            //the number of test patterns
    int m=0;                   //the number of the scan chains
	int l=0;                   //the length of the subvectors
    int wfmp=0;                //the width of the formatted test data
	int tm=0;                  //the number of the vectors in the array in which the compatible patterns have been deleted
	int nw=0;                  //the width of the new test patterns
	int total;                 //the size of the compressed test set
	int i,j;
	FILE *fpp,*fp,*fr;         //the point of the input file and the output file


//open the file

    cout << "Filename input:";
    cin >> sourcename;
	fpp=fopen(sourcename,"r");
	if (!fpp)
	{
		cout << sourcename << " could not be opened" << endl;
		return 1;
	} 
//*********************************	
    cout << "Filename output:";
    cin >> destinationname;
    fp=fopen(destinationname,"w");
    if (!fp)
    {
	     cout<< destinationname << "not created" << endl;
         return 1;
	}
//*****************************
	cout << "Filename for result:";
    cin >> resultname;
    fr=fopen(resultname,"w");
    if (!fr)
    {
	     cout<< resultname << "not created" << endl;
         return 1;
	}
 
	
//read the width and the number of the patterns

	fscanf(fpp,"%d", &width);
    if (width==0)
    {
         cout << "no patterns!";
         return 1;
    }
    fscanf(fpp,"%d", &number);
	fprintf(fp,"%s","the width and number of test patterns : ");
    fprintf(fp,"%d ",width);
	fprintf(fp,"%d\n",number);
	fprintf(fp,"%s\n","it is hard to make a \n");

	
//read and output the number of the scan chains

    cout << "please input the number of the scan chains m(<width):";
    cin >> m;
    fprintf(fp,"%s","the number of the scan chains m:");
    fprintf(fp,"%d\n",m);
	fprintf(fp,"%s\n","");


//calculate l and wfmp

    if ( width%m==0 )    	l=width/m;
    else            		l=width/m+1;
    wfmp=number*l;



    char *patterns=new char[width*number];  //the heap for the original patterns
                                            //many times we use the heap as two dimensions array
    char *ptemp;                            //the point of the array patterns
	char *fmatpat=new char[wfmp*m];         //the heap for the formatted test data
	char *tfmat=new char[wfmp*m];           //temp fmatpat
    ptemp=patterns;

   
//read the original patterns

    while(!feof(fpp))
    {
	    fscanf(fpp,"%c",ptemp);
        if(*ptemp!='\n') ptemp++;
    }
    fclose(fpp);
  

//first compression

	patternfmat(patterns,fmatpat,width,number,m);

    tm=rowcompalg(fp,fmatpat,wfmp,m);
    fprintf(fp,"%s ","the number of the vectors after the compatible vectors have been deleted:");
    fprintf(fp,"%d\n",tm);
    fprintf(fp,"%s\n","");


//rearrange the array fmatpat to tfmat(nw,number)

    for ( i=0;i<wfmp;i++ )
	    for ( j=0;j<tm;j++ )
		    tfmat[i*tm+j]=fmatpat[j*wfmp+i];

    nw=tm*l;        //the width of the tfmat,and also the length of the CSR
    fprintf(fp,"%s ","the length of the CSR (the width of the new patterns): ");
    fprintf(fp,"%d\n",nw);
    fprintf(fp,"%s\n","");
/*	fprintf(fp,"%s\n","the rearranged fmatpat:");
    matrixoutput(fp,tfmat,nw,number);*/

/*  
//second compression.process the new patterns and output the result using position-mark method
	
	total=alterrunlen(fr,tfmat,nw*number);
	delete[]tfmat;
	fprintf(fp,"%s","the total size of the compressed test set: ");
	fprintf(fp,"%d\n",total);
    
*/
//close the file

    fclose(fp);
	fclose(fr);

	return 0;


}



//**********************function patternfmat********************


//this function formats the test patterns according to the number of scan chains m
//the formatting details refer to lilei's dictionary-based test data compression
//the meaning of the function's parameters as follows:
//      patterns--the test patterns will be formatted
//      fmatpat--the heap room used to save the formatted test patterns
//      width,number--the width and the number of the patterns
//      m--the number of the scan chains


void patternfmat(char *patterns,char *fmatpat,int width,int number,int m)
{

	int i,j,k,p,l,t=0;
	int flag=0;  //here the flag show whether need or not to pad the don't care in the end.if flag=1,it means needing    
    int wfmp=0;  //the width of the fmatpat

	if ( width%m==0 )    l=width/m;
    else
	{
		l=width/m+1;
		flag=1;
	}
    wfmp=number*l;

	p=width/l;
	if ( flag==0 )
	{
		 for ( i=0;i<number;i++ )
		 {
			  for ( j=0;j<m;j++ )
			      for ( k=0;k<l;k++ )
				  {
			            fmatpat[j*wfmp+(k+i*l)]=patterns[t];
			            t++;
				  }
		 }
	}
	else
	{
		for ( i=0;i<number;i++ )
		{
		    for ( j=0;j<p;j++ )
		        for ( k=0;k<l;k++ )
				{
			         fmatpat[j*wfmp+(k+i*l)]=patterns[t];
			         t++;
				}
		    for ( k=0;k<(width-p*l);k++ )
			{
			    fmatpat[j*wfmp+(k+i*l)]=patterns[t];
			    t++;
			}
		    for ( k=(width-p*l);k<l;k++ )
			    fmatpat[j*wfmp+(k+i*l)]='-';
		    for ( j=p+1;j<m;j++ ) //do while width%m>l
			    for ( k=0;k<l;k++ )
					fmatpat[j*wfmp+(k+i*l)]='-';
		}
	}
}




//********************function compgraphset*********************


//this function sets up the compatible graph G of the test patterns
//if the two patterns are compatible,the corresponding position in the graph G equals 1;otherwise 0.
//we think the pattern is not compatible to itself
//the meaning of the function's parameters as follows:
//      patterns--the test patterns will be set up the compatible graph G
//      graphg--the heap room used to save the compatible graph G
//      width,number--the width and the number of the patterns
//this function will return the number of 1 in the graph G

//对分段后的测试集合建立图g
int compgraphset(char *patterns,int *graphg,int width,int number)
{

	int i,j,k,flag;
    int total=0;
	
	for ( i=0;i<number;i++ )
    {
		for ( j=0;j<number;j++ )
		{
			flag=0;//the flag of the compatible;if flag=1;it means the patterns are not compatible
		    k=0;
		    while ( k<width )
			{
			    if ((patterns[i*width+k]!='-')&&(patterns[j*width+k]!='-'))
				{
				    if (patterns[i*width+k]==patterns[j*width+k])  k++;
				    else
					{
					    graphg[i*number+j]=0;
					    flag=1;
					    break;
					}
				}
			    else k++;
			}
		    if ((flag==0)&&(i!=j))
			{
			    graphg[i*number+j]=1;
			    total++;//the total number of the compatible relationship
			}
		    if (i==j) graphg[i*number+j]=0;
		}
	}

	return total;
}




//*******************function maxcliquegreedy********************


//this fuction is the greedy algorithm to find the maximal clique in graph G.

//the first cycle is used to confirm the group of compatible vectors(clique).
//cycle one time comfirms a group of compatible vectors
//here we will output the positions of the compatible vectors(the positions of the shanchu lines)
//the meaning of the function's parameters as follows:
//      f--the point of the file to output the position value
//      graphg--the graph G show the compatible relationship
//      rcomp--a heap room to save compatible mark of every pattern
//      n--the number of the vertices in graph G
//      total--the number of 1 in the graph G
//this function will return the number of the cliques

 //图g中用贪心算法求最大相容类  
int maxcliquegreedy(FILE *f,int *graphg,int *rcomp,int n,int total)
{

   int *scl=new int[n];   //the temp array used to save the original position value
   int *tscl=new int[n];  //the temp array usd to save the changed position value
   int *gg=new int[n*n];  //G'
   int *tgg=new int[n*n]; //temp G'
   int *ncomp=new int[n]; //the degree of every vertex 
   int i,j,t,t1,t2,tmax,flag,pgg1,pgg2;

   if(gg==NULL)       cout<<"allocate error1"<<endl;