From 2167870f7379daba93d3d93902da3f80c61d294c Mon Sep 17 00:00:00 2001 From: Alan Kennedy Date: Sat, 19 Jun 2004 23:07:16 +0000 Subject: [PATCH 1/1] Reordeno un poco el codigo para hacerlo mas modular, igualmente en cuanto vea el tema de multivolumen y de como me van a enviar los datos desde el MTF, seguramente va a sufrir algunos cambios lindos --- src/statichuff/statichuff.c | 221 +++++++++++++++++++++--------------- src/statichuff/statichuff.h | 16 +++ 2 files changed, 144 insertions(+), 93 deletions(-) create mode 100644 src/statichuff/statichuff.h diff --git a/src/statichuff/statichuff.c b/src/statichuff/statichuff.c index e91a367..540800d 100644 --- a/src/statichuff/statichuff.c +++ b/src/statichuff/statichuff.c @@ -1,27 +1,15 @@ -#include - -typedef unsigned long int t_freq; - -typedef struct t_freqnode { - unsigned short int symbol; - t_freq freq; - struct t_freqnode *lchild; - struct t_freqnode *rchild; -} HUFFNODE; - -typedef struct t_code { - unsigned long int code; - unsigned char codelength; -} CODE; +#include "statichuff.h" void putbit(char bit, char restart, char flush, FILE *fp) { static unsigned long int bits_buffer = 0; static unsigned char bits_used = 0; + int i; - /* me obligan a tirar el output */ + /* me obligan a emitir el output */ if ((flush == 1) && (bits_used > 0)) { + bits_buffer = bits_buffer << ((sizeof(unsigned long int)*8) - bits_used); fwrite(&bits_buffer,sizeof(unsigned long int),1,fp); bits_buffer = 0; bits_used = 0; @@ -46,7 +34,7 @@ void putbit(char bit, char restart, char flush, FILE *fp) return; } -void cpynode(HUFFNODE *node1, HUFFNODE *node2) +void shuff_cpynode(SHUFFNODE *node1, SHUFFNODE *node2) { node1->symbol = node2->symbol; node1->freq = node2->freq; @@ -54,37 +42,14 @@ void cpynode(HUFFNODE *node1, HUFFNODE *node2) node1->rchild = node2->rchild; } -int compnode(HUFFNODE *node1, HUFFNODE *node2) +int shuff_compnode(SHUFFNODE *node1, SHUFFNODE *node2) { if (node1->freq < node2->freq) return 1; if (node1->freq > node2->freq) return -1; return 0; } -HUFFNODE *buildlist(t_freq *freqtable, int *nonzerofreqs) -{ - int i,j = 0,nonzero = 0; - HUFFNODE *inputlist; - - /* Calculo cuantas frequencias > 0 hay y creo la tabla */ - for (i = 0; i < 256; ++i) if (freqtable[i] > 0) nonzero++; - inputlist = (HUFFNODE*)malloc(sizeof(HUFFNODE)*nonzero); - - /* Cargo la inputlist del huffman solo con freqs > 0 */ - for (i = 0; i < 256; ++i) - if (freqtable[i] > 0) { - inputlist[j].symbol = i; - inputlist[j].freq = freqtable[i]; - inputlist[j].lchild = NULL; - inputlist[j].rchild = NULL; - j++; - } - - *nonzerofreqs = nonzero; - return inputlist; -} - -int rescalefreq(t_freq *freqtable) +int shuff_rescalefreq(t_freq *freqtable) { int i; t_freq totalfreq = 0; @@ -99,14 +64,14 @@ int rescalefreq(t_freq *freqtable) return totalfreq; } -int scanfreq(char *inputfile, t_freq *freqtable) +int shuff_scanfreq(char *inputfile, t_freq *freqtable) { /* Locals */ FILE *fp; t_freq sumfreq = 0; int i,symbol; - /* Inicializamos la tabla de frecuencias */ + /* Inicializamos la tabla de frecuencias */ for (i = 0; i < 256; ++i) freqtable[i] = 0; /* Abrimos el file */ @@ -121,14 +86,64 @@ int scanfreq(char *inputfile, t_freq *freqtable) /* Si llegue al tope de freq acumulada, halve em */ if (sumfreq == 14930352) - sumfreq = rescalefreq(freqtable); + sumfreq = shuff_rescalefreq(freqtable); } fclose(fp); return 1; } -void printcodes(CODE *codetable,t_freq *freqtable) +SHUFFNODE *shuff_buildlist(t_freq *freqtable, int *nonzerofreqs) +{ + int i,j = 0,nonzero = 0; + SHUFFNODE *inputlist; + + /* Calculo cuantas frequencias > 0 hay y creo la tabla */ + for (i = 0; i < 256; ++i) if (freqtable[i] > 0) nonzero++; + inputlist = (SHUFFNODE*)malloc(sizeof(SHUFFNODE)*nonzero); + + /* Cargo la inputlist del huffman solo con freqs > 0 */ + for (i = 0; i < 256; ++i) + if (freqtable[i] > 0) { + inputlist[j].symbol = i; + inputlist[j].freq = freqtable[i]; + inputlist[j].lchild = NULL; + inputlist[j].rchild = NULL; + j++; + } + + *nonzerofreqs = nonzero; + return inputlist; +} + +SHUFFNODE *shuff_buildtree(SHUFFNODE *list, int listcount) +{ + SHUFFNODE *lastsymbol = list+(listcount-1); + SHUFFNODE *node1,*node2,*fictnode; + + /* Ordenamos inicialmente la inputlist para tomar las dos freqs min */ + while (lastsymbol > list) { + /* Ordeno la lista por frecuencia descendente */ + qsort(list,listcount,sizeof(SHUFFNODE),shuff_compnode); + /* Tomo los ultimos dos elementos, generando dos nodos del arbol */ + node1 = (SHUFFNODE*)malloc(sizeof(SHUFFNODE)); + node2 = (SHUFFNODE*)malloc(sizeof(SHUFFNODE)); + shuff_cpynode(node1,lastsymbol-1); + shuff_cpynode(node2,lastsymbol); + lastsymbol -= 1; + /* Nodo ficticio con la suma de las probs y los ptros a childs */ + lastsymbol->symbol = 256; + lastsymbol->freq = node1->freq + node2->freq; + lastsymbol->lchild = node1; + lastsymbol->rchild = node2; + --listcount; + } + + /* Devuelvo el puntero a la raiz del arbol de huffman */ + return lastsymbol; +} + +void shuff_printcodes(SHUFFCODE *codetable,t_freq *freqtable) { int i,j; unsigned short int auxcode; @@ -149,18 +164,18 @@ void printcodes(CODE *codetable,t_freq *freqtable) } } -void zerocodes(CODE *table) +void shuff_zerocodes(SHUFFCODE *table) { int i; - /* Inicializo los codigos prefijos */ + /* Inicializo los codigos prefijos */ for (i = 0; i < 256; ++i) { table[i].code = 0; table[i].codelength = 0; } } -void buildcodes(CODE *table, HUFFNODE *node, int level, int code) +void shuff_buildcodes(SHUFFCODE *table, SHUFFNODE *node, int level, int code) { if (node->symbol < 256) { /* Guardo el codigo en la tabla */ @@ -169,57 +184,41 @@ void buildcodes(CODE *table, HUFFNODE *node, int level, int code) } else { code = code << 1; - buildcodes(table,node->lchild,level+1,code); + shuff_buildcodes(table,node->lchild,level+1,code); code |= 1; - buildcodes(table,node->rchild,level+1,code); + shuff_buildcodes(table,node->rchild,level+1,code); } } -HUFFNODE *buildtree(HUFFNODE *list, int listcount) -{ - HUFFNODE *lastsymbol = list+(listcount-1); - HUFFNODE *node1,*node2,*fictnode; - /* Ordenamos inicialmente la inputlist para tomar las dos freqs min */ - while (lastsymbol > list) { - /* Ordeno la lista por frecuencia descendente */ - qsort(list,listcount,sizeof(HUFFNODE),compnode); - /* Tomo los ultimos dos elementos, generando dos nodos del arbol */ - node1 = (HUFFNODE*)malloc(sizeof(HUFFNODE)); - node2 = (HUFFNODE*)malloc(sizeof(HUFFNODE)); - cpynode(node1,lastsymbol-1); - cpynode(node2,lastsymbol); - lastsymbol -= 1; - /* Nodo ficticio con la suma de las probs y los ptros a childs */ - lastsymbol->symbol = 256; - lastsymbol->freq = node1->freq + node2->freq; - lastsymbol->lchild = node1; - lastsymbol->rchild = node2; - --listcount; - } - - /* Devuelvo el puntero a la raiz del arbol de huffman */ - return lastsymbol; -} -int encode(CODE *table, char* inputfile, char *outputfile) { +int shuff_encode_symbols(t_freq *ftable, SHUFFCODE *ctable, char* inputfile, char *outputfile) { FILE *fpsource,*fpdest; int symbol,i; + unsigned long int sourcesize; char bit; - CODE symbolcode; + SHUFFCODE symbolcode; /* Abrimos el file */ if ((fpsource = fopen(inputfile,"rb")) == NULL) return 0; if ((fpdest = fopen(outputfile,"wb")) == NULL) return 0; + + /* Guardamos el size el archivo original e inputlist como header */ + fseek(fpsource,0,SEEK_END); + sourcesize = ftell(fpsource); + fwrite(&sourcesize,sizeof(unsigned long int),1,fpdest); + fwrite(ftable,sizeof(t_freq),256,fpdest); - while (!feof(fpsource)) { + /* Encodeo */ + fseek(fpsource,0,SEEK_SET); + while (!feof(fpsource)) { /* Levanto un symbolo (byte) */ symbol = fgetc(fpsource); if (symbol == EOF) continue; /* Cargamos el codigo y lo emitimos */ - symbolcode = table[symbol]; + symbolcode = ctable[symbol]; for (i = symbolcode.codelength; i > 0; --i) { bit = (symbolcode.code >> (i-1)) & 1; putbit(bit,0,0,fpdest); @@ -233,28 +232,64 @@ int encode(CODE *table, char* inputfile, char *outputfile) { return 1; } -int main(int argc, char* argv[]) +int shuff_encode_file(char *inputfile, char *outputfile) { /* Locals */ t_freq *freqtable = (t_freq*)malloc(sizeof(t_freq)*256); - HUFFNODE *inputlist; - HUFFNODE *codetree; - CODE *codetable = (CODE*)malloc(sizeof(CODE)*256); + SHUFFNODE *inputlist; + SHUFFNODE *codetree; + SHUFFCODE *codetable = (SHUFFCODE*)malloc(sizeof(SHUFFCODE)*256); int freqcount = 0,i; - if (argc == 1) return -1; - /* Armamos la tabla de frecuencias */ - if (!scanfreq(argv[1],freqtable)) return -1; + if (!shuff_scanfreq(inputfile,freqtable)) return -1; /* Armo el input list y genero el arbol de huffman */ - inputlist = buildlist(freqtable, &freqcount); - codetree = buildtree(inputlist,freqcount); + inputlist = shuff_buildlist(freqtable, &freqcount); + codetree = shuff_buildtree(inputlist,freqcount); + /* Armo la tabla de codigos prefijos para el encoder */ - zerocodes(codetable); - buildcodes(codetable,codetree,0,0); - printcodes(codetable,freqtable); - encode(codetable,argv[1],"output.dat"); + shuff_zerocodes(codetable); + shuff_buildcodes(codetable,codetree,0,0); + shuff_printcodes(codetable,freqtable); + + /* Encodeo byte per byte */ + shuff_encode_symbols(freqtable,codetable,inputfile,outputfile); +} + +int shuff_decode(char *inputfile, char *outputfile) +{ + SHUFFNODE *inputlist; + SHUFFNODE *codetree; + t_freq *ftable = (t_freq*)malloc(sizeof(t_freq)*256); + unsigned long int bytesleft; + FILE *fpsource; + FILE *fpdest; + int i,freqcount = 0; + + /* Levanto cuantos bytes decodeo y la freq table */ + if ((fpsource = fopen(inputfile,"rb")) == NULL) return 0; + if ((fpdest = fopen(outputfile,"wb")) == NULL) return 0; + fread(&bytesleft,sizeof(unsigned long int),1,fpsource); + fread(ftable,sizeof(unsigned long int),256,fpsource); + inputlist = shuff_buildlist(ftable, &freqcount); + codetree = shuff_buildtree(inputlist,freqcount); + + fclose(fpsource); + fclose(fpdest); + + +} + +int main(int argc, char* argv[]) +{ + if (argc == 1) return -1; + + /* Comprimo */ + shuff_encode_file(argv[1],"output.shf"); + + /* Decodeo */ + shuff_decode("output.shf","decoded.dat"); return 0; } diff --git a/src/statichuff/statichuff.h b/src/statichuff/statichuff.h new file mode 100644 index 0000000..eac6505 --- /dev/null +++ b/src/statichuff/statichuff.h @@ -0,0 +1,16 @@ + +#include + +typedef unsigned long int t_freq; + +typedef struct t_freqnode { + unsigned short int symbol; + t_freq freq; + struct t_freqnode *lchild; + struct t_freqnode *rchild; +} SHUFFNODE; + +typedef struct t_code { + unsigned long int code; + unsigned char codelength; +} SHUFFCODE; -- 2.43.0