/* File: dcodhuff.c Author: David Bourgin Creation date: 15/2/94 Last update: 24/7/95 Purpose: Example of Huffman decoding with a file source to decompress. */ #include /* For routines printf,fgetc and fputc */ #include /* For routine memset */ #include /* For routines malloc and free */ #include /* For routine exit */ /* Error codes returned to the caller */ #define NO_ERROR 0 #define BAD_FILE_NAME 1 #define BAD_ARGUMENT 2 #define BAD_MEM_ALLOC 3 /* Useful constants */ #define FALSE 0 #define TRUE 1 typedef struct s_tree { unsigned int byte; /* A byte has to be coded as an unsigned integer to allow a node to have a value over 255 */ struct s_tree *left_ptr, *right_ptr; } t_tree,*p_tree; #define TREE_BYTE(ptr_tree) ((*(ptr_tree)).byte) #define LEFTPTR_OF_TREE(ptr_tree) ((*(ptr_tree)).left_ptr) #define RIGHTPTR_OF_TREE(ptr_tree) ((*(ptr_tree)).right_ptr) typedef struct { unsigned char bits[32]; unsigned int bits_nb; unsigned char presence; } t_bin_val; #define BITS_BIN_VAL(x) ((x).bits) #define NB_BITS_BIN_VAL(x) ((x).bits_nb) #define PRESENCE_BIN_VAL(x) ((x).presence) #include "tiny.h" u_char *srce2_p; /* ptr to data to be compressed */ u_char *end2_p; /* ptr to last byte of uncompressed data */ u_char *dest2_p; /* ptr to buffer for compressed data */ int buflen2 = 0; int errval2 = 0; /* errval2 is returned if malloc fails (T_MEM_ERROR) */ int bytecount2 = 0; /* if no errors, number of bytes written is returned */ int write_byte(u_char byte); /* check for buffer overrun before writing byte */ /* Global variables */ //FILE *source_file,*dest_file; /* Being that fgetc=EOF only after an access then 'byte_stored_status' is 'TRUE' if a byte has been stored by 'fgetc' or 'FALSE' if there's no valid byte not handled in 'val_byte_stored' */ //int byte_stored_status=FALSE; //int byte_stored_val; /* Pseudo procedures */ #define end_of_data() (srce2_p > end2_p) #define read_byte() (*(srce2_p++)) //#define write_byte(byte) { ((*dest2_p++) = (byte)); bytecount2++; } unsigned char bit_counter_to_read=0; unsigned int val_to_read=0; unsigned char read_code_1_bit() /* Returned parameters: Returns an unsigned integer with the 0-bit (on the right of the integer) valid Action: Reads the next bit in the stream of data to compress Errors: An input/output error could disturb the running of the program The source must have enough bits to read */ { unsigned int result; if (bit_counter_to_read) { bit_counter_to_read--; result=(val_to_read >> bit_counter_to_read) & 1; } else { val_to_read=read_byte(); bit_counter_to_read=7; result=(val_to_read >> 7) & 1; } val_to_read &= 127; return result; } unsigned int read_code_n_bits(n) /* Returned parameters: Returns an unsigned integer with the n-bits (on the right of the integer) valid Action: Reads the next n bits in the stream of data to compress Errors: An input/output error could disturb the running of the program The source must have enough bits to read */ unsigned char n; { unsigned int result; while ((bit_counter_to_read> bit_counter_to_read; val_to_read &= ((1< Present bytes coded on n*8 bits =1 => Present bytes coded on 256 bits */ for (i=0;i<=255;i++) PRESENCE_BIN_VAL(codes_table[i])=read_code_1_bit(); else { i=read_code_n_bits(5)+1; while (i) { PRESENCE_BIN_VAL(codes_table[read_code_n_bits(8)])=1; i--; } } PRESENCE_BIN_VAL(codes_table[256])=1; /* Presence of a fictive 256-byte is enforced! */ /* == Decoding the second part of the header == */ for (i=0;i<=256;i++) if PRESENCE_BIN_VAL(codes_table[i]) { if (read_code_1_bit()) /* First bit=0 => 5 bits of binary length-1 followed by a binary word =1 => 8 bits of binary length-1 followed by a binary word */ j=read_code_n_bits(8)+1; else j=read_code_n_bits(5)+1; NB_BITS_BIN_VAL(codes_table[i])=j; /* Reading of a binary word */ byte_nb=(j+7) >> 3; if (j & 7) { /* Reads the bits that takes less than one byte */ byte_nb--; BITS_BIN_VAL(codes_table[i])[byte_nb]=(unsigned char)read_code_n_bits(j & 7); } while (byte_nb) { /* Reads the bits that takes one byte, at least */ byte_nb--; BITS_BIN_VAL(codes_table[i])[byte_nb]=(unsigned char)read_code_n_bits(8); } } } void suppress_tree2(tree) /* Returned parameters: None Action: Suppresses the allocated memory for the tree Errors: None if the tree has been build with dynamical allocations! */ p_tree tree; { if (tree!=NULL) { suppress_tree2(LEFTPTR_OF_TREE(tree)); suppress_tree2(RIGHTPTR_OF_TREE(tree)); free(tree); } } p_tree tree_encoding(codes_table) /* Returned parameters: A binary tree is returned Action: Returns the decoding binary tree built from 'codes_table' Errors: None */ t_bin_val codes_table[257]; { register unsigned int i; unsigned int j; p_tree ptr_tree,current_node; if ((ptr_tree=(p_tree)malloc(sizeof(t_tree)))==NULL) { // exit(BAD_MEM_ALLOC); errval2 = T_MEM_ERROR; return NULL; } TREE_BYTE(ptr_tree)=257; LEFTPTR_OF_TREE(ptr_tree)=NULL; RIGHTPTR_OF_TREE(ptr_tree)=NULL; for (i=0;i<=256;i++) { for (current_node=ptr_tree,j=NB_BITS_BIN_VAL(codes_table[i]);j;j--) { if (BITS_BIN_VAL(codes_table[i])[(j-1) >> 3] & (1 << ((j-1) & 7))) if (LEFTPTR_OF_TREE(current_node)==NULL) { if ((LEFTPTR_OF_TREE(current_node)=(p_tree)malloc(sizeof(t_tree)))==NULL) { suppress_tree2(ptr_tree); // exit(BAD_MEM_ALLOC); errval2 = T_MEM_ERROR; return NULL; } current_node=LEFTPTR_OF_TREE(current_node); LEFTPTR_OF_TREE(current_node)=NULL; RIGHTPTR_OF_TREE(current_node)=NULL; } else current_node=LEFTPTR_OF_TREE(current_node); else if (RIGHTPTR_OF_TREE(current_node)==NULL) { if ((RIGHTPTR_OF_TREE(current_node)=(p_tree)malloc(sizeof(t_tree)))==NULL) { suppress_tree2(ptr_tree); // exit(BAD_MEM_ALLOC); errval2 = T_MEM_ERROR; return NULL; } current_node=RIGHTPTR_OF_TREE(current_node); LEFTPTR_OF_TREE(current_node)=NULL; RIGHTPTR_OF_TREE(current_node)=NULL; } else current_node=RIGHTPTR_OF_TREE(current_node); if (j==1) TREE_BYTE(current_node)=i; else TREE_BYTE(current_node)=257; } }; return (ptr_tree); } int huffmandecoding() /* Returned parameters: None Action: Decompresses with Huffman method all bytes read by the function 'read_code_1_bit' and 'read_code_n_bits' Errors: An input/output error could disturb the running of the program */ { t_bin_val encoding_table[257]; p_tree ptr_tree,current_node; if (!end_of_data()) /* Are there data to compress? */ { read_header(encoding_table); if(ptr_tree=tree_encoding(encoding_table)) { do { current_node=ptr_tree; while (TREE_BYTE(current_node)==257) if (read_code_1_bit()) /* Bit=1 => Got to left in the node of the tree =0 => Got to right in the node of the tree */ current_node=LEFTPTR_OF_TREE(current_node); else current_node=RIGHTPTR_OF_TREE(current_node); if (TREE_BYTE(current_node)<=255) { if(!write_byte((u_char)TREE_BYTE(current_node))) { errval2 = T_BUF_ERROR; break; } } } while (TREE_BYTE(current_node)!=256); } suppress_tree2(ptr_tree); } if(errval2) return errval2; else return bytecount2; } /* write raw data byte, first check for buffer overrun */ int write_byte(u_char byte) { if(bytecount2 == buflen2) return NG; else { *(dest2_p++) = byte; bytecount2++; } return OK; } //void aide() /* Returned parameters: None Action: Displays the help of the program and then stops its running Errors: None *//* { printf("This utility enables you to decompress a file by using Huffman method\n"); printf("as given 'La Video et Les Imprimantes sur PC'\n"); printf("\nUse: dcodhuff source target\n"); printf("source: Name of the file to decompress\n"); printf("target: Name of the restored file\n"); }*/ //int main(argc,argv) /* Returned parameters: Returns an error code (0=None) Action: Main procedure Errors: Detected, handled and an error code is returned, if any *//* int argc; char *argv[]; { if (argc!=3) { aide(); exit(BAD_ARGUMENT); } else if ((source_file=fopen(argv[1],"rb"))==NULL) { aide(); exit(BAD_FILE_NAME); } else if ((dest_file=fopen(argv[2],"wb"))==NULL) { aide(); exit(BAD_FILE_NAME); } else { huffmandecoding(); fclose(source_file); fclose(dest_file); } printf("Execution of dcodhuff completed.\n"); return (NO_ERROR); } */