huffman1.c

基于MPI 的网络并行计算环境的哈夫曼编码的并行程序

#include "mpi.h"
#include <stdio.h>
#include <math.h>
//#include <conio.h>
#include <stdlib.h>

#define LEN 256
#define BUFFERMAX 4196
#define HUFFMANCODELEN 16


int main( int argc, char *argv[])
 {
    double startwtime, endwtime, stime, rtime;
    
    FILE * fp, * fp1;

    int i;

    int Row=1, Line=108576;
    
    int myid,numprocs,namelen;
     
    int root=0; 
    
    char processor_name[MPI_MAX_PROCESSOR_NAME];
    
    MPI_Status status;
    
   
    MPI_Init(&argc,&argv);
    MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
    MPI_Comm_rank(MPI_COMM_WORLD,&myid);
    MPI_Get_processor_name(processor_name,&namelen);

    printf("Process %d on %s\n", myid, processor_name);
    
    int Points=Row*Line, MPI_Points=(Row*Line)/numprocs;
    
    float * sbuf=(float*)malloc(sizeof(float)*Points);
	  
    float * rbuf=(float*)malloc(sizeof(float)*MPI_Points);
	  
	  
    
    if(myid==0)
       {
       	  startwtime=MPI_Wtime();
       	  
          if((fp=fopen("wavelet.dat","r"))==NULL)
            {
             printf("cannot open this file\n");
             exit(0);
            }
           for(i=0;i<Points;i++)
	
		           fread(&sbuf[i],sizeof(float),1,fp);    ////压缩前数据文件读入数组buffer[]
          	      
	        fclose(fp);
       }
    
     
     MPI_Scatter(sbuf,MPI_Points,MPI_FLOAT,rbuf,MPI_Points,MPI_FLOAT,root,MPI_COMM_WORLD);
     
    // MPI_Barrier(MPI_COMM_WORLD);
     
     if(myid==0)
    	{
            FILE * fpread;
             
            if((fpread=fopen("wavelet1.dat","wb"))==NULL)
             {
              printf("cannot open this file\n");
              exit(0);
             }   
    	 for(i=0;i<MPI_Points;i++)
	
		          fwrite(&rbuf[i],sizeof(float),1,fpread);
    	  
    struct tree_table

    {
      struct tree_table *head;
      struct htree *treeptr;
    };

    struct _huffmancode
    {
      unsigned char huffmancodebyte[HUFFMANCODELEN];
    };

    struct _huffmanhashptr
    {
       struct htree* htreeptr;
    };

    struct htree
    {
    struct htree *lchild;
    struct htree *rchild;
    unsigned char code;
    struct _huffmancode huffmancode;
    float weigth;
    unsigned char bit;//huffmancode位数 
    char leaf;    //1是叶子 
    };

FILE *infile,*outfile;
unsigned char infilebuffer[BUFFERMAX],outfilebuffer[BUFFERMAX];
int read_len;

struct htree g[LEN];
struct _huffmanhashptr hhptr[LEN];
//int testdata[]={10,20,1,2,4,2,0,5,4,2,5,4,2,1,3,6,3,0,1,3,0};
//int testdata[]={1,1,1,2,2,3,4,5,5,6};
int length=0;
struct tree_table *table_head;
struct htree *forest;
int test;

void static readdata();
void static sort();
void static set_table();
void static huffmantree();
void static readfile();
void static writefile();
void static write_huffmancode();

void searchtree(struct htree *f)
{
    static unsigned char deep=0;
    if(f==NULL)return;
    if(f->leaf==1)
    {
        f->bit=deep--;
        hhptr[f->code].htreeptr=f;
        //printf("BBB:%d\tcode:%d\n",f->bit,f->code);
        return;    
    }
    f->lchild->huffmancode=f->huffmancode;
    f->rchild->huffmancode=f->huffmancode;
    f->rchild->huffmancode.huffmancodebyte[deep/8]|=(0x01<<(7-(deep%8)));
    deep++;
    searchtree(f->lchild);
    deep++;
    searchtree(f->rchild);
    deep--;
}

void  static readfile()
{
     int i;
     infile=fopen("wavelet1.dat","rb");
     //fseek(infile,0,2);
     //printf("KKKK:%d\n",ftell(infile));
     do{
       read_len=fread(infilebuffer,sizeof(char),BUFFERMAX,infile);
       readdata();//统计code出现的次数 
     }while(read_len==BUFFERMAX);
     fclose(infile);
     for(i=0;i<length;i++)printf("code:%d\tweigth:%f\n",g[i].code,g[i].weigth);
}

/*
*
*/
void  static write_huffmancode()
{
     int i,j,k;
     unsigned char cc[100];
     outfile=fopen("2.dat","ab");
     for(i=0,k=0;i<length;i++)
     {
        cc[k++]=g[i].code;
        cc[k++]=g[i].bit;
        for(j=0;j<((g[i].bit-1)/8+1);j++)
        {
           cc[k+j]=g[i].huffmancode.huffmancodebyte[j];
           k++;
        }
        k=0;
        fwrite(cc,sizeof(char),3+(g[i].bit-1)/8,outfile);
     }
     fclose(outfile);
}

#define HUFFMANCODEBYTE(code,i) hhptr[code].htreeptr->huffmancode.huffmancodebyte[i]

void writefile()
{
     int i,j;
     unsigned char temp[9];
     int tempcode;
     unsigned char code;
     int bufferptr=0,tempbit=0;
     infile=fopen("wavelet1.dat","rb");
     outfile=fopen("2.dat","ab");
     while((tempcode=getc(infile))!=EOF)
     {
         code=tempcode;
         tempbit=hhptr[code].htreeptr->bit;
         for(i=0;i<9;i++) temp[i]=0;
         for(i=0;i<9;i++)
         {
             temp[i]|=HUFFMANCODEBYTE(code,i)>>(bufferptr%8);
             tempbit-=bufferptr%8;
             if(tempbit<0)
                 break;
             temp[i+1]|=HUFFMANCODEBYTE(code,i)<<(7-(bufferptr%8));
             tempbit-=7-(bufferptr%8);
             if(tempbit<0)
                 break;
         }
         for(j=i;j>=0;j--)
         {
             outfilebuffer[bufferptr/8]|=temp[i-j];
         }
         bufferptr+=hhptr[code].htreeptr->bit;
         if(bufferptr/8>BUFFERMAX-8)
         {
             fwrite(outfilebuffer,sizeof(char),bufferptr/8+1,outfile);
                 for(i=0;i<BUFFERMAX;i++)outfilebuffer[i]=0;
             bufferptr=0;
         }
     }
     /*
     for(i=0;i<bufferptr/8;i++)
     {
        printf("bbb:%d\n",outfilebuffer[i]);
     }
     */
     fwrite(outfilebuffer,sizeof(char),bufferptr/8+1,outfile);
     bufferptr=0;
     fclose(infile);
     fclose(outfile);
}

void readdata()
{
    int i,j;
    int exist;
    for(i=0;i<read_len;i++)
    {
        exist=0;
        for(j=0;j<length;j++)
        {
            if(infilebuffer[i]==g[j].code)
            {
                g[j].weigth++;
                exist=1;
                break;
            }
        }
        if(exist==0)
        {
            g[length].code=infilebuffer[i];
            g[length].weigth=1;
            g[length].leaf=1;
            g[length].lchild=NULL;
            g[length].rchild=NULL;
            //g[length].huffmancode=0;
            length++;
        }
    }
}      

void sort(){
    int i,j;
    struct htree temp;
    for(i=0;i<length-1;i++)
    {
        for(j=length-1;j>i;j--)
        {
            if(g[j].weigth>g[j-1].weigth)
            {
                temp=g[j];
                g[j]=g[j-1];
                g[j-1]=temp;
            }
        }
    }
}

void set_table()//按大小顺序建立链表 
{
    int i;
    struct tree_table *tt;
    tt=(struct tree_table *)malloc(sizeof(struct tree_table));
    tt->head=NULL;
    tt->treeptr=g;
    table_head=tt;
    for(i=1;i<length;i++)
    {
        tt=(struct tree_table *)malloc(sizeof(struct tree_table));
        tt->head=table_head;
        tt->treeptr=g+i;
        table_head=tt;
    }
}

void insert_tree(struct htree *ht,struct tree_table **head)
{
     struct tree_table *tableptr;
     tableptr=*head;
     struct tree_table *temp;
     temp=(struct tree_table *)malloc(sizeof(struct tree_table));
     temp->treeptr=ht;
     if(ht->weigth<=tableptr->treeptr->weigth)
     {
       //新树为最小应加在表头 
         *head=temp;
         temp->head=tableptr;
     }else{
           while(tableptr->head!=NULL) 
           {
               if(ht->weigth>tableptr->head->treeptr->weigth)
               {
                   tableptr=tableptr->head;
               }else
               {
                   break;
               } 
           }
           temp->head=tableptr->head;
           tableptr->head=temp;
     }
}

void clean_code(struct htree* ht)
{
     struct _huffmancode temp;
     int i;
     for(i=0;i<16;i++)
     {
     temp.huffmancodebyte[i]=0;
     }
     ht->huffmancode=temp;
}

void huffmantree()
{
    struct htree *temptree;
    while(1)
    {
        temptree=(struct htree *)malloc(sizeof(struct htree));
        //temptree 两个子树或叶子生成的新树 
        temptree->lchild=table_head->treeptr;
        temptree->rchild=table_head->head->treeptr;
        temptree->weigth=temptree->lchild->weigth+temptree->rchild->weigth;
        //temptree->code=-1;
        temptree->leaf=0;
        clean_code(temptree);
        //temptree->huffmancode=0;
        table_head=table_head->head->head;
        if(table_head==NULL)break;
        insert_tree(temptree,&table_head);
    }
    forest=temptree;
}
            endwtime=MPI_Wtime();
            stime=endwtime-startwtime;
            printf("elasped clock time = %f\n",stime);
       
   void all()
    {
     readfile();
     sort();
    set_table();
    huffmantree();
    searchtree(forest);
    write_huffmancode();
    writefile();
    }
    
}
    
  
    MPI_Reduce(&stime,&rtime, 1, MPI_DOUBLE, MPI_SUM, root, MPI_COMM_WORLD);
    
    if(myid==0)
    	{
    		printf("the total elasped clock time = %f\n",rtime);
    	}
    
    MPI_Finalize();

    return 0;
}