Hi all,
this is the program which I saw in my colleagues book. the program was
run on turbo C++ 3.0 compiler
/*beginning of header file huff.h*/
#ifndef _HUFF_H_
#define _HUFF_H_
#include <io.h>
#include <conio.h>
#include<stdio. h>
typedef struct node
{
unsigned char c;
unsigned long int freq;
struct node *up,*left,*righ t;
}sn;
typedef struct ftable
{
unsigned long int freq;
}sft;
/*global variables*/
int buf[50],bc;
sft ft;
sn leaf[256];
sn *a,*t[256];
/*function prototypes*/
int initialize(char *);
/* operation: initialization function
post conditions: initializes all leaves to null values,barring the
character whose
frequency they point to.sets frequency values of the leaves
*/
int sortnode(int);
/* operation: sorting function
post conditions: sorts the pointer nodes in the decreasing order of
frequency*/
int getnodecount();
/* operation: get count of nodes with non zero frequency
post conditions: */
int createtree();
/* operation: creating the tree
post conditions: creats a non optimal huffman tree
to generate prefix codes
*/
int comparenode(sn* ,sn*);
/* operation: node comparison
post conditions: returns 0 if both pointers point to same data
else returns -1
*/
void addtobuffer(int );
/* operation: initializing the bit buffer
post conditions: holds prefix codes for each leave nodes
*/
void refreshbuffer(F ILE *);
/* operation: writing the coded prefix character
post conditions:
*/
/*void freetree(sn*);*/
char* getfilename(cha r *);
/* operation: obtaining the file name
post conditions: splits the file path to obtain the file name
*/
unsigned char getoddchar();
/* operation: same as that of refreshbuffer
pre conditions: bit buffer with less than 8 bits
*/
#endif
/*end of header file*/
/*
static version of huffman coding.
it is by no means optimal
compresses files above 3.25 kb
upper limit has not been determined upto 50K OK
usage of global variables
imperfect coding
usage of non standard functions lack of garbage collector leaves much
to be desired it might eat your memory if u are running this program on
old dos machines
*/
#include"huff.h "
int main(void)
{
FILE *fp,*fq;
int ch,i;
char fname[100],efile[100];
unsigned long int fsize,efsize;
clrscr(); /*non standard fn*/
printf("\nHuffm an encoder");
printf("\nEnter the name of the input file(to be compressed):");
fgets(fname,100 ,stdin);
fname[strlen(fname)-1]=0;
printf("\nEnter the output filename(compre ssed file):");
fgets(efile,100 ,stdin);
efile[strlen(efile)-1]=0;
if(initialize(f name)==-1)
{
printf("\nError Could not open input file..");
return -1;
}
printf("\nIniti alization over.\nPreparin g to compress...");
if(createtree() ==-1)
{
printf("\nMemor y allocation error..");
return -1;
}
fq=fopen(efile, "wb");
if(!fq)
{
printf("\nError Could not open output file..");
fclose(fq);
return -1;
}
fp=fopen(fname, "rb");
if(!fp)
{
printf("\nError Could not open input file...");
fclose(fp);
return -1;
}
fsize=filelengt h(fileno(fp)); /*non std fn*/
/****To write the decoding table */
for(i=0;i<256;i ++)
{
ft.freq=leaf[i].freq;
fwrite(&ft.freq ,sizeof(struct ftable),1,fq);
}
/*To write the character that denotes the size of filenamelength*/
fputc(strlen(ge tfilename(fname ))+1,fq);
/*To write the filename*/
fwrite(getfilen ame(fname),strl en(getfilename( fname))+1,1,fq) ;
/***Completed writing of decoding table*****/
printf("\nCompr essing...");
while(ch=fgetc( fp),ch!=EOF)
{
addtobuffer(ch) ;
refreshbuffer(f q);
}
fputc(getoddcha r(),fq);
fputc(bc,fq);
fclose(fq);
printf("\nCompr ession complete.");
/*****For display of compression summary****/
fp=fopen(efile, "rb");
if(!fp)
{
printf("\nCould not open output file for analysis");
printf("\nCompr ession summary cannot be displayed");
return -1;
}
efsize=fileleng th(fileno(fp)); fclose(fp);
printf("\n\nCom pression summary\n");
printf("\nInput filesize :%lu bytes",fsize);
printf("\nOutpu t filesize:%lu",e fsize);
printf("\nCompr essed to %Lf%% of original size",((long
double)efsize*1 00/fsize));
return 0;
}
int sortnode(int z)/*sorts upto t[z] and not t[z-1]*/
{
int j,k;
sn* b;
for(k=0;k<=z;k+ +)
for(j=(k+1);j<= z;j++)
{
if((t[k]->freq)<(t[j]->freq))
{
b = t[k];
t[k] = t[j];
t[j] = b;
}
}
return 0;
}
char *getfilename(ch ar *filepath)
{
char drive[4],dir[67],file[15],ext[5];
fnsplit(filepat h,drive,dir,fil e,ext); //non standard fn
strcat(file,ext );
return file;
}
unsigned char getoddchar()
{
int i;
for(i=bc;i<8;i+ +)
{ buf[i]=0;}
return
((1*buf[7])+(2*buf[6])+(4*buf[5])+(8*buf[4])+(16*buf[3])+(32*buf[2])+(64*buf[1])+(128*buf[0]));
}
void refreshbuffer(F ILE *p)
{
int i;
unsigned char q;
while(bc>=8)
{
q=(1*buf[7])+(2*buf[6])+(4*buf[5])+(8*buf[4])+(16*buf[3])+(32*buf[2])+(64*buf[1])+(128*buf[0]);
if(fputc(q,p)!= (unsigned)q || q<0 || q>255)printf("\ nError");
for(i=8;i<bc;i+ +)
{buf[i-8]=buf[i];}
bc-=8;
}
}
void addtobuffer(int r)
{
int i,buftv[15];
int bct = -1,buft[15];
if(r>255 || r<0)
{
printf("\nValue error...");
getch();
}
a = &leaf[r];
while((a->up)!=NULL)
{
/* temp = a;*/
if(comparenode( (a->up->left),a)==0)
{buft[++bct]=0;}
else if(comparenode( (a->up->right),a)==0 )
{ buft[++bct]=1;}
else
{printf("\nPare nt Error"); /*For debugging*/}
a=a->up;
}
for(i=0;i<=bct; i++)
{ buftv[bct-i]=buft[i];}
for(i=0;i<=bct; i++)
{buf[bc+i]=buftv[i];}
bc += bct+1;
return;
}
int createtree()
{
int i;
sortnode(255);
for(i=getnodeco unt();i>0;i--)
{
sortnode(i);
a = NULL;
a = (sn *)malloc(sizeof (sn));
if(!a)
{
printf("\nMemor y allocation error...");
printf("\npress any key to continue...");
getch();
return -1; /*Memory allocation error*/
}
/*Assingning values*/
a->freq = (t[i]->freq)+(t[i-1]->freq);
a->right = t[i];
a->left = t[i-1];
a->up = NULL;
a->c = '\0';
t[i]->up = a;
t[i-1]->up = a;
t[i-1]=a;
}
return 0;
}
int initialize(char *filename)
{
int i,j;
FILE *fp;
for(i=0;i<256;i ++)
{
leaf[i].c = i;
leaf[i].freq = 0;
leaf[i].up = NULL;
leaf[i].left = NULL;
leaf[i].right = NULL;
}
fp=fopen(filena me,"rb");
if(!fp)
{ return -1; /*Could not open file */}
while(j=fgetc(f p),j!=EOF)
{
leaf[j].freq++;
if(j<0 || j>255)
{
printf("\nError ..."); //should add a exit fn here
getch();
}
}
fclose(fp);
for(i=0;i<256;i ++)
{
t[i]=&leaf[i];
if((t[i]->up)!=NULL)
{
printf("\nError ..");
getch();
}
}
bc=0;
return 0;
}
int getnodecount()
{
int i,h=0;
for(i=0;i<256;i ++)
{
if(leaf[i].freq==0)
h++;
}
return (255-h);
}
int comparenode(sn *a,sn *b)
{
if(a->c==b->c && a->freq==b->freq && a->up==b->up &&a->left==b->left
&& a->right==b->right)
return 0;
return -1;
}
/* void freetree(sn* hd)
{
if(!hd)
return;
freetree(hd -> left);
freetree(hd -> right);
free(hd);
}*/
now my questions are
1) how can the function freetree be implemented properly.
2) can anybody explain refreshbuffer funcion
i mean refresh buffer function writes the encoded bit pattern
using
fputc function.
the function of fputc function is as follows
int fputc(int ch, FILE *stream);
Writes a character (an unsigned char) specified by the argument ch
to the specified stream and advances the position indicator for the
stream.On success the character is returned. If an error occurs,
the error indicator for the stream is set and EOF is returned.
now my question is how compression is achieved,if we are writing ints
3) what exactly is the purpose served by these two statements in this
program???
fputc(getoddcha r(),fq);
fputc(bc,fq);
this is the program which I saw in my colleagues book. the program was
run on turbo C++ 3.0 compiler
/*beginning of header file huff.h*/
#ifndef _HUFF_H_
#define _HUFF_H_
#include <io.h>
#include <conio.h>
#include<stdio. h>
typedef struct node
{
unsigned char c;
unsigned long int freq;
struct node *up,*left,*righ t;
}sn;
typedef struct ftable
{
unsigned long int freq;
}sft;
/*global variables*/
int buf[50],bc;
sft ft;
sn leaf[256];
sn *a,*t[256];
/*function prototypes*/
int initialize(char *);
/* operation: initialization function
post conditions: initializes all leaves to null values,barring the
character whose
frequency they point to.sets frequency values of the leaves
*/
int sortnode(int);
/* operation: sorting function
post conditions: sorts the pointer nodes in the decreasing order of
frequency*/
int getnodecount();
/* operation: get count of nodes with non zero frequency
post conditions: */
int createtree();
/* operation: creating the tree
post conditions: creats a non optimal huffman tree
to generate prefix codes
*/
int comparenode(sn* ,sn*);
/* operation: node comparison
post conditions: returns 0 if both pointers point to same data
else returns -1
*/
void addtobuffer(int );
/* operation: initializing the bit buffer
post conditions: holds prefix codes for each leave nodes
*/
void refreshbuffer(F ILE *);
/* operation: writing the coded prefix character
post conditions:
*/
/*void freetree(sn*);*/
char* getfilename(cha r *);
/* operation: obtaining the file name
post conditions: splits the file path to obtain the file name
*/
unsigned char getoddchar();
/* operation: same as that of refreshbuffer
pre conditions: bit buffer with less than 8 bits
*/
#endif
/*end of header file*/
/*
static version of huffman coding.
it is by no means optimal
compresses files above 3.25 kb
upper limit has not been determined upto 50K OK
usage of global variables
imperfect coding
usage of non standard functions lack of garbage collector leaves much
to be desired it might eat your memory if u are running this program on
old dos machines
*/
#include"huff.h "
int main(void)
{
FILE *fp,*fq;
int ch,i;
char fname[100],efile[100];
unsigned long int fsize,efsize;
clrscr(); /*non standard fn*/
printf("\nHuffm an encoder");
printf("\nEnter the name of the input file(to be compressed):");
fgets(fname,100 ,stdin);
fname[strlen(fname)-1]=0;
printf("\nEnter the output filename(compre ssed file):");
fgets(efile,100 ,stdin);
efile[strlen(efile)-1]=0;
if(initialize(f name)==-1)
{
printf("\nError Could not open input file..");
return -1;
}
printf("\nIniti alization over.\nPreparin g to compress...");
if(createtree() ==-1)
{
printf("\nMemor y allocation error..");
return -1;
}
fq=fopen(efile, "wb");
if(!fq)
{
printf("\nError Could not open output file..");
fclose(fq);
return -1;
}
fp=fopen(fname, "rb");
if(!fp)
{
printf("\nError Could not open input file...");
fclose(fp);
return -1;
}
fsize=filelengt h(fileno(fp)); /*non std fn*/
/****To write the decoding table */
for(i=0;i<256;i ++)
{
ft.freq=leaf[i].freq;
fwrite(&ft.freq ,sizeof(struct ftable),1,fq);
}
/*To write the character that denotes the size of filenamelength*/
fputc(strlen(ge tfilename(fname ))+1,fq);
/*To write the filename*/
fwrite(getfilen ame(fname),strl en(getfilename( fname))+1,1,fq) ;
/***Completed writing of decoding table*****/
printf("\nCompr essing...");
while(ch=fgetc( fp),ch!=EOF)
{
addtobuffer(ch) ;
refreshbuffer(f q);
}
fputc(getoddcha r(),fq);
fputc(bc,fq);
fclose(fq);
printf("\nCompr ession complete.");
/*****For display of compression summary****/
fp=fopen(efile, "rb");
if(!fp)
{
printf("\nCould not open output file for analysis");
printf("\nCompr ession summary cannot be displayed");
return -1;
}
efsize=fileleng th(fileno(fp)); fclose(fp);
printf("\n\nCom pression summary\n");
printf("\nInput filesize :%lu bytes",fsize);
printf("\nOutpu t filesize:%lu",e fsize);
printf("\nCompr essed to %Lf%% of original size",((long
double)efsize*1 00/fsize));
return 0;
}
int sortnode(int z)/*sorts upto t[z] and not t[z-1]*/
{
int j,k;
sn* b;
for(k=0;k<=z;k+ +)
for(j=(k+1);j<= z;j++)
{
if((t[k]->freq)<(t[j]->freq))
{
b = t[k];
t[k] = t[j];
t[j] = b;
}
}
return 0;
}
char *getfilename(ch ar *filepath)
{
char drive[4],dir[67],file[15],ext[5];
fnsplit(filepat h,drive,dir,fil e,ext); //non standard fn
strcat(file,ext );
return file;
}
unsigned char getoddchar()
{
int i;
for(i=bc;i<8;i+ +)
{ buf[i]=0;}
return
((1*buf[7])+(2*buf[6])+(4*buf[5])+(8*buf[4])+(16*buf[3])+(32*buf[2])+(64*buf[1])+(128*buf[0]));
}
void refreshbuffer(F ILE *p)
{
int i;
unsigned char q;
while(bc>=8)
{
q=(1*buf[7])+(2*buf[6])+(4*buf[5])+(8*buf[4])+(16*buf[3])+(32*buf[2])+(64*buf[1])+(128*buf[0]);
if(fputc(q,p)!= (unsigned)q || q<0 || q>255)printf("\ nError");
for(i=8;i<bc;i+ +)
{buf[i-8]=buf[i];}
bc-=8;
}
}
void addtobuffer(int r)
{
int i,buftv[15];
int bct = -1,buft[15];
if(r>255 || r<0)
{
printf("\nValue error...");
getch();
}
a = &leaf[r];
while((a->up)!=NULL)
{
/* temp = a;*/
if(comparenode( (a->up->left),a)==0)
{buft[++bct]=0;}
else if(comparenode( (a->up->right),a)==0 )
{ buft[++bct]=1;}
else
{printf("\nPare nt Error"); /*For debugging*/}
a=a->up;
}
for(i=0;i<=bct; i++)
{ buftv[bct-i]=buft[i];}
for(i=0;i<=bct; i++)
{buf[bc+i]=buftv[i];}
bc += bct+1;
return;
}
int createtree()
{
int i;
sortnode(255);
for(i=getnodeco unt();i>0;i--)
{
sortnode(i);
a = NULL;
a = (sn *)malloc(sizeof (sn));
if(!a)
{
printf("\nMemor y allocation error...");
printf("\npress any key to continue...");
getch();
return -1; /*Memory allocation error*/
}
/*Assingning values*/
a->freq = (t[i]->freq)+(t[i-1]->freq);
a->right = t[i];
a->left = t[i-1];
a->up = NULL;
a->c = '\0';
t[i]->up = a;
t[i-1]->up = a;
t[i-1]=a;
}
return 0;
}
int initialize(char *filename)
{
int i,j;
FILE *fp;
for(i=0;i<256;i ++)
{
leaf[i].c = i;
leaf[i].freq = 0;
leaf[i].up = NULL;
leaf[i].left = NULL;
leaf[i].right = NULL;
}
fp=fopen(filena me,"rb");
if(!fp)
{ return -1; /*Could not open file */}
while(j=fgetc(f p),j!=EOF)
{
leaf[j].freq++;
if(j<0 || j>255)
{
printf("\nError ..."); //should add a exit fn here
getch();
}
}
fclose(fp);
for(i=0;i<256;i ++)
{
t[i]=&leaf[i];
if((t[i]->up)!=NULL)
{
printf("\nError ..");
getch();
}
}
bc=0;
return 0;
}
int getnodecount()
{
int i,h=0;
for(i=0;i<256;i ++)
{
if(leaf[i].freq==0)
h++;
}
return (255-h);
}
int comparenode(sn *a,sn *b)
{
if(a->c==b->c && a->freq==b->freq && a->up==b->up &&a->left==b->left
&& a->right==b->right)
return 0;
return -1;
}
/* void freetree(sn* hd)
{
if(!hd)
return;
freetree(hd -> left);
freetree(hd -> right);
free(hd);
}*/
now my questions are
1) how can the function freetree be implemented properly.
2) can anybody explain refreshbuffer funcion
i mean refresh buffer function writes the encoded bit pattern
using
fputc function.
the function of fputc function is as follows
int fputc(int ch, FILE *stream);
Writes a character (an unsigned char) specified by the argument ch
to the specified stream and advances the position indicator for the
stream.On success the character is returned. If an error occurs,
the error indicator for the stream is set and EOF is returned.
now my question is how compression is achieved,if we are writing ints
3) what exactly is the purpose served by these two statements in this
program???
fputc(getoddcha r(),fq);
fputc(bc,fq);
Comment