Program Segmentation Faults on return 0/fclose/free. I think I have memory leaks but can't find them. Please help!

Question

I am trying to write a Huffman encoding program to compress a text file. Upon completetion, the program will terminate at the return statement, or when I attempt to close a file I was reading from. I assume I have memory leaks, but I cannot find them. If you can spot them, let me know (and a method for fixing them would be appreciated!).

(note: small1.txt is any standard text file)

Here is the main program

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define ASCII 255

struct link {
 int freq;
 char ch[ASCII];
 struct link* right;
 struct link* left;
};

typedef struct link node;
typedef char * string;
FILE * ofp;
FILE * ifp;
int writebit(unsigned char);
void sort(node *[], int);
node* create(char[], int);
void sright(node *[], int);
void Assign_Code(node*, int[], int, string *);
void Delete_Tree(node *);

int main(int argc, char *argv[]) {
 //Hard-coded variables
 //Counters

 int a, b, c = 0;
 //Arrays
 char *key = (char*) malloc(ASCII * sizeof(char*));
 int *value = (int*) malloc(ASCII * sizeof(int*));

 //File pointers

 FILE *fp = fopen(argv[1], "r");
 if (fp == NULL) {
  fprintf(stderr, "can't open %s\n", argv[1]);
  return 0;
 }
 //Nodes
 node* ptr;//, *head;
 node* array[ASCII];

 //
 int u, carray[ASCII];
 char str[ASCII];

 //Variables
 char car = 0;
 int inList = 0;
 int placeinList = -1;
 int numofKeys;

 if (argc < 2) {
  printf("Usage: huff <.txt file> \n");
  return 0;
 }

 for (a = 0; a < ASCII; a++) {
  key[a] = -1;
  value[a] = 0;
 }

 car = fgetc(fp);
 while (!feof(fp)) {
  for (a = 0; a < ASCII; a++) {
   if (key[a] == car) {
    inList = 1;
    placeinList = a;
   }
  }
  if (inList) {
   //increment value array
   value[placeinList]++;
   inList = 0;
  } else {
   for (b = 0; b < ASCII; b++) {
    if (key[b] == -1) {
     key[b] = car;
     break;
    }
   }
  }
  car = fgetc(fp);
 }
 fclose(fp);
 c = 0;
 for (a = 0; a < ASCII; a++) {
  if (key[a] != -1) {
   array[c] = create(&key[a], value[a]);
   numofKeys = c;
   c++;
  }
 }

 string code_string[numofKeys];

 while (numofKeys > 1) {
  sort(array, numofKeys);
  u = array[0]->freq + array[1]->freq;
  strcpy(str, array[0]->ch);
  strcat(str, array[1]->ch);
  ptr = create(str, u);
  ptr->right = array[1];
  ptr->left = array[0];
  array[0] = ptr;
  sright(array, numofKeys);
  numofKeys--;
 }

 Assign_Code(array[0], carray, 0, code_string);

 ofp = fopen("small1.txt.huff", "w");

 ifp = fopen("small1.txt", "r");

 car = fgetc(ifp);
 while (!feof(ifp)) {
  for (a = 0; a < ASCII; a++) {
   if (key[a] == car) {
    for (b = 0; b < strlen(code_string[a]); b++) {
     if (code_string[a][b] == 48) {
      writebit(0);
     } else if (code_string[a][b] == 49) {
      writebit(1);
     }
    }
   }
  }
  car = fgetc(ifp);
 }
 writebit(255);
 fclose(ofp);
 ifp = fopen("small1.txt", "r");
 fclose(ifp);
 free(key);
 //free(value);
 //free(code_string);
 printf("here1\n");
 return 0;
}

int writebit(unsigned char bitval) {

 static unsigned char bitstogo = 8;
 static unsigned char x = 0;

 if ((bitval == 0) || (bitval == 1)) {
  if (bitstogo == 0) {
   fputc(x, ofp);
   x = 0;
   bitstogo = 8;
  }
  x = (x << 1) | bitval;
  bitstogo--;
 } else {
  x = (x << bitstogo);
  fputc(x, ofp);
 }

 return 0;
}
void Assign_Code(node* tree, int c[], int n, string * s) {
 int i;
 static int cnt = 0;
 string buf = malloc(ASCII);
 if ((tree->left == NULL) && (tree->right == NULL)) {
  for (i = 0; i < n; i++) {
   sprintf(buf, "%s%d", buf, c[i]);
  }
  s[cnt] = buf;
  cnt++;
 } else {
  c[n] = 1;
  n++;
  Assign_Code(tree->left, c, n, s);
  c[n - 1] = 0;
  Assign_Code(tree->right, c, n, s);
 }
}
node* create(char a[], int x) {
 node* ptr;
 ptr = (node *) malloc(sizeof(node));
 ptr->freq = x;
 strcpy(ptr->ch, a);
 ptr->right = ptr->left = NULL;
 return (ptr);
}

void sort(node* a[], int n) {
 int i, j;
 node* temp;
 for (i = 0; i < n - 1; i++)
  for (j = i; j < n; j++)
   if (a[i]->freq > a[j]->freq) {
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
   }
}

void sright(node* a[], int n) {
 int i;
 for (i = 1; i < n - 1; i++)
  a[i] = a[i + 1];
}

Answer 1

If your program is crashing on what is otherwise a valid operation (like returning from a function or closing a file), I'll near-guarantee it's a buffer overflow problem rather than a memory leak.

Memory leaks just generally mean your mallocs will eventually fail, they do not mean that other operations will be affected. A buffer overflow of an item on the stack (for example) will most likely corrupt other items on the stack near it (such as a file handle variable or the return address from main).

Probably your best bet initially is to set up a conditional breakpoint on writes to the file handles. This should happen in the calls to fopen and nowhere else. If you detect a write after the fopen calls are finished, that will be where your problem occurred, so just examine the stack and the executing line to find out why.

---

Your first problem (this is not necessarily the only one) lies here:

c = 0;
for (a = 0; a < ASCII; a++) {
    if (key[a] != -1) {
        array[c] = create(&key[a], value[a]);
        numofKeys = c;  // DANGER,
        c++;            //   WILL ROBINSON !!
    }
}

string code_string[numofKeys];

You can see that you set the number of keys before you increment c. That means the number of keys is one less than you actually need so that, when you access the last element of code_string, you're actually accessing something else (which is unlikely to be a valid pointer).

Swap the numofKeys = c; and c++; around. When I do that, I at least get to the bit printing here1 and exit without a core dump. I can't vouch for the correctness of the rest of your code but this solves the segmentation violation so anything else should probably go in your next question (if need be).

Answer 2

I can see one problem:

strcpy(str, array[0]->ch);
strcat(str, array[1]->ch);

the ch field of struct link is a char array of size 255. It is not NUL terminated. So you cannot copy it using strcpy.

Also you have:

ofp = fopen("small1.txt.huff", "w");
ifp = fopen("small1.txt", "r");

If small1.txt.huff does not exist, it will be created. But if small1.txt it will not be created and fopen will return NULL, you must check the return value of fopen before you go and read from the file.

Answer 3

Just from counting, you have 4 separate malloc calls, but only one free call.

I would also be wary of your sprintf call, and how you are actually mallocing.

You do an sprintf(buf, "%s%d", buf, c[i]) but that can potentially be a buffer overflow if your final string is longer than ASCII bytes.

I advise you to step through with a debugger to see where it's throwing a segmentation fault, and then debug from there.

Answer 4

i compiled the program and ran it with it's source as that small1.txt file and got "can't open (null)" if the file doesn't exist or the file exist and you give it on the command like ./huf small1.txt the program crashes with:

Program terminated with signal 11, Segmentation fault.
#0  0x08048e47 in sort (a=0xbfd79688, n=68) at huf.c:195
195    if (a[i]->freq > a[j]->freq) {
(gdb) backtrace
#0  0x08048e47 in sort (a=0xbfd79688, n=68) at huf.c:195
#1  0x080489ba in main (argc=2, argv=0xbfd79b64) at huf.c:99

to get this from gdb you run

ulimit -c 100000000
./huf
gdb --core=./core ./huf

and type backtrace

Answer 5

You have various problems in your Code:

1.- mallocs (must be):

//Arrays
char *key = (char*) malloc(ASCII * sizeof(char));
int *value = (int*) malloc(ASCII * sizeof(int));

sizeof(char) == 1, sizeof(char *) == 4 or 8 (if 64 bits compiler is used).

2.- Buffer sizes 255 (ASCII) is too short to receive the contents of array[0]->ch + array[1]->ch + '\0'.

3.- Use strncpy instead of strcpy and strncat instead of strcat.

4.- key is an array of individuals chars or is a null terminated string ?, because you are using this variable in both ways in your code. In the characters counting loop you are using this variables as array of individuals chars, but in the creation of nodes you are passing the pointer of the array and copying as null terminated array.

5.- Finally always check your parameters before used it, you are checking if argc < 2 after trying to open argv[1].