Reputation: 11
I have a c program that attempts implementing Huffman encryption. The problem is that the program runs indefinity after asking for the file containing the string to be encrypted is entered.
i'm not sure what' causing this isue. I have included the file with the string in the same directory as the program.
Below is the program:
#include <stdio.h> /*rewind, */
#include <string.h>
#include <stdlib.h> /*system, */
/*Please change name of *node*/
typedef struct node_t {
char c;
int frequency;
struct node_t *left, *right;
} *node;
/*global variable: track num of nodes,, end of que, pool of nodes?
string array for codes of each letter*/
int n_nodes = 0;
int qend = 1;
struct node_t pool[256] = {{0}};
node qqq[255], *q = qqq - 1;
char *code[128]= {0};
char buffer[1024];
int input_data = 0;
int output_data = 0;
/*function prototypes*/
node newNode(int frequency, char c, node a, node b);
void qinsert(node n);
node qremove();
void buildCode(node n, char *s, int len);
void importFile(FILE *fp_in, unsigned int *frequency);
void encode(FILE* fp_in, FILE* fp_out, unsigned int *frequency);
int printable(int c);
void printCode(unsigned int *frequency);
int main(int argc, char* argv[]){
FILE *fp_in, *fp_out;
char file_name[50] = {0};
unsigned int frequency[128] = {0}, i;
/*System functinon executes a shell command in a C function*/
system("clear");
printf("**************************************************************\n");
printf("**************************************************************\n");
if (argc == 2) {
/*commandline argument directly allows to compress the file*/
strcpy(file_name, argv[1]);
}
else if (argc > 2){
printf("Too many arguments supplied. \n");
}
else {
printf("Please enter the file to be compressed: ");
scanf("%s", file_name);
}
if (strlen(file_name)>= 50){
printf("ERROR: Enter a filename less than 50 chars");
return 0;
}
/*import the file into the program and update the huffman tree*/
if((fp_in = fopen(file_name, "r")) == NULL){
printf("\nError: No such file\n");
return 0;
}
importFile(fp_in, frequency);
printCode(frequency);
/*Encode and save the encoded file under the .huffman extension*/
strcat(file_name, ".huffman");
fp_out = fopen(file_name, "w");
encode(fp_in, fp_out, frequency);
fclose(fp_in);
fclose(fp_out);
strcat(file_name, ".table");
fp_out = fopen(file_name, "w");
for(i = 0; i < 128; i++){
fprintf(fp_out, "%c", (char)frequency[i]);
}
fclose(fp_out);
printf("\nInput bytes: %d\n", input_data);
output_data = (output_data % 8)? (output_data / 8) + 1: (output_data / 8);
printf("Output bytes: %d\n", output_data);
printf("\nCompression ratio: %.2f%%\n\n\n", ((double)(input_data-output_data)/input_data)*100);
return 0;
}
/*Fucntion to creatre a new node*/
node newNode(int frequency, char c, node a, node b){
node n = pool + n_nodes++;
if (frequency != 0){
/*Assign character 'c' to the character of the node,
assign frequency*/
n->c = c;
n->frequency = frequency;
}
else {
/*If there is no frequency provided, removed nodes at the end of
the que will be added to left and right*/
n->left = a;
n->right = b;
n->frequency = a->frequency + b->frequency;
}
return n;
}
/*Function to insert a node into the priority que*/
void qinsert(node n){
int j, i = qend++;
while ((j = i/2)){
if (q[j]->frequency <= n->frequency){
break;
}
q[i] = q[j];
i = j;
}
q[i] = n;
}
node qremove(){
int i, l;
node n = q[i = 1];
if (qend < 2){
return 0;
}
qend--;
while ((l = i * 2) < qend){
if (l + 1 < qend && q[l + 1]->frequency < q[l]->frequency){
l++;
q[i] = q[l];
i = l;
}
}
q[i] = q[qend];
return n;
}
/*Assign the code for each char of the input string*/
void buildCode(node n, char *s, int len){
static char *output = buffer;
if (n->c){
s[len] = 0;
strcpy(output, s);
code[(int)n->c] = output;
output += len + 1;
return;
}
/*Recursion is used to write out the code, if right add 1, if right add a 0*/
s[len] = '0';
buildCode(n->left, s, len + 1);
s[len] = '1';
buildCode(n->right, s, len + 1);
}
void importFile(FILE* fp_in, unsigned int *frequency){
/*temporary variables*/
char c, s[20] = {0};
int i = 0;
printf("Read file: \n");
while((c = fgetc(fp_in)) != EOF){
/*Read the file character by character and increment the frequency*/
frequency[(int)c]++;
putchar(c);
}
for (i = 0; i < 128; i++){
if (frequency[i]){
/*If there is a frequency, insert new node*/
qinsert(newNode(frequency[i], i, 0, 0 ));
}
}
while (qend > 1){
/*Build tree*/
qinsert(newNode(0, 0, qremove(), qremove()));
/*Build the code for the characters*/
buildCode(q[1], s, 0);
}
}
void encode(FILE* fp_in, FILE* fp_out, unsigned int *frequency){
unsigned char buffer = 0;
int bits = 0;
int lim = 0;
int i;
rewind(fp_in);
for(i = 0; i < 128; i++){
if(frequency[i]){
lim += (frequency[i]*strlen(code[i]));
}
}
output_data = lim;
fprintf(fp_out, "%04d\n", lim);
printf("\nEncoded: \n");
int in;
while ((in = fgetc(fp_in)) != EOF){
char *temp = code[in];
for (i = 0; temp[i] != '\0'; i++){
if (temp[i] == '1'){
buffer |= (1 << (7-bits));
}
bits++;
if(bits == 8){
fputc(buffer, fp_out);
buffer = 0;
bits = 0;
}
}
printf("%s", code[in]);
}
if(bits > 0){
fputc(buffer, fp_out);
}
else if (in == EOF && bits > 0){
fputc(buffer, fp_out);
}
}
int printable(int c){
return (c >= 32 && c <= 126);
}
void printCode(unsigned int *frequency){
int i;
printf("\n--------------CODE TABLE--------------\n --------------"
"--------------\n CHAR FREQ CODE\n --------------\n");
for(i = 0; i < 128; i++){
if(printable(i) && code[i] != NULL && i != ' '){
printf("%-4c %-4d %16s\n", i, frequency[i], code[i]);
}
else if (code[i]!= NULL){
switch(i){
case '\n':
printf("\\n ");
case ' ':
printf("\' \' ");
break;
case '\t':
printf("\\t ");
break;
default:
printf("%0X ", (char)i);
break;
}
printf(" %-4d %16s\n", frequency[i], code[i]);
}
}
printf("--------------\n");
}
Upvotes: 0
Views: 44