Here is an update to my previous thread which you can find here (thanks @JS1 for the brilliant advice!). Again, I'd very much appreciate any advice or comments about the structure/logic of the program, style of the code, or reusability of the features. I'm a novice and really eager to learn from people here, so fire away!
Edit: I'm not sure whether I'm dealing with the eof properly in fread_twelve(). The last code is padded to 16 bits, and I don't think I'm reading it properly because feof never returns true... Would really appreciate any tips!
Edit2: I'm also eager to hear how I can balance the heap. Valgrind says I have "778 allocs, 354 frees" on one run, but I thought I'd freed all my allocations!
lzw.h :
/**
* file: lzw.h
*
* function declarations for lzw decompression algorithm.
*/
#ifndef LZW_H
#define LZW_H
#include <stdio.h>
#include <stdlib.h>
typedef uint8_t byte;
/**
* Frees all blocks between 'from' and 'to' (inclusive) in the dict.
*/
void free_dict (byte* dict[], int from, int to);
/**
* Enters the first 256 ASCII values into dict, and their respective sizes into sizes.
*/
void load_dict_defaults (byte* dict[], int sizes[]);
/**
* Reads 12 bits from source and returns them as an int.
*/
int fread_twelve(FILE* source);
/**
* LZW decompression of source to dest.
* Returns 0 if successful, a positive integer otherwise.
*/
int decompress (FILE* source, FILE* dest);
#endif // LZW_H
decompress.c :
/**
* file: decompress.c
*
* implementation of LZW decompression algorithm using 12-bit fixed-width compression format.
*
* usage: decompress source output
*/
#include "lzw.h"
#include <stdio.h>
#include <stdlib.h>
int main (int argc, char* argv[])
{
// check for correct number of args
if (argc != 3)
{
printf("Usage: decompress source output\n");
return 1;
}
// open compressed file
FILE* source = fopen(argv[1], "rb");
if (source == NULL)
{
printf("Error: cannot open %s\n", argv[1]);
return 1;
}
// open destination file
FILE* dest = fopen(argv[2], "wb");
if (dest == NULL)
{
printf("Error: cannot open %s\n", argv[2]);
return 1;
}
// decompress
if (decompress(source, dest) == 1)
{
printf("Decompression failed\n");
fclose(source);
fclose(dest);
return 1;
}
else
{
fclose(source);
fclose(dest);
return 0;
}
}
lzw.c :
/**
* file: lzw.c
*
* Implementation of LZW decompression algorithm using 12-bit fixed-width compression format.
*
*/
#include "lzw.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
byte* dictionary[4096];
int dict_entry_sizes[4096];
/**
* Enters the first 256 ASCII values into dict.
*/
void load_dict_defaults (byte* dict[], int sizes[])
{
byte* temp;
byte c = 0;
for (int i = 0; i < 256; i++)
{
temp = malloc(1);
temp[0] = c++;
dict[i] = temp;
dict_entry_sizes[i] = 1;
}
}
/**
* Frees all blocks between 'from' and 'to' (inclusive) in the dict.
*/
void free_dict (byte* dict[], int from, int to)
{
for (int i = from; i <= to; i++)
{
free(dict[i]);
}
}
/**
* Reads 12 bits from source and returns them as an int.
* Returns 0 on an error or EOF.
*/
int fread_twelve(FILE* source)
{
int value;
static bool left = true;
static byte prevByte = 0;
byte buf[2];
if (left)
{
if (fread(buf, 1, 2, source) != 2)
{
return 0;
}
if (feof(source)) // we're at a 16-bit end!
{
value = (buf[0] << 8) | buf[1];
}
else
{
value = (buf[0] << 4) | (buf[1] >> 4);
}
left = false;
prevByte = buf[1];
}
else
{
if (fread(buf, 1, 1, source) != 1)
{
return 0;
}
value = ((prevByte & 0x0F) << 8) | buf[0];
left = true;
}
return value;
}
/**
* LZW decompression of source to dest.
* Returns 0 if successful, a positive integer otherwise.
*/
int decompress (FILE* source, FILE* dest)
{
load_dict_defaults(dictionary, dict_entry_sizes);
int dictPos = 256;
int prevCode, currCode;
byte* prevString, *currString;
// read in the first character
currCode = fread_twelve(source);
size_t size = dict_entry_sizes[currCode];
currString = malloc(size + 1); //+1 for upcoming char
if (currString == NULL)
{
fprintf(stderr, "decompress: error assigning currString.\n");
return 1;
}
memcpy(currString, dictionary[currCode], size);
fwrite(currString, size, 1, dest);
prevCode = currCode;
prevString = currString;
// read in the rest of the characters
size_t oldSize;
while ( (currCode = fread_twelve(source)) && currCode )
{
if (currCode > dictPos)
{
fprintf(stderr, "decompress: currCode out of dictionary range.\n");
return 1;
}
oldSize = dict_entry_sizes[prevCode];
if (currCode < dictPos) // code in dict
{
size = dict_entry_sizes[currCode];
currString = malloc(size + 1); // +1 for adding char on next loop
if (currString == NULL)
{
fprintf(stderr, "decompress: error assigning currString.\n");
return 1;
}
memcpy(currString, dictionary[currCode], size);
fwrite(currString, size, 1, dest);
memcpy(prevString + oldSize, currString, 1);
dictionary[dictPos] = prevString;
dict_entry_sizes[dictPos++] = oldSize + 1;
// restart dict if full.
if (dictPos >= 4096)
{
free_dict(dictionary, 256, 4095);
dictPos = 256;
}
}
else // code not in dict until this pass
{
memmove(prevString + oldSize, prevString, 1); // memmove allows overlap
size = oldSize + 1;
fwrite(prevString, size, 1, dest);
dictionary[dictPos] = prevString;
dict_entry_sizes[dictPos++] = size;
currString = malloc(size + 1); // +1 for adding char on next loop
if (currString == NULL)
{
fprintf(stderr, "decompress: error assigning currString.\n");
return 1;
}
memcpy(currString, prevString, size);
}
prevCode = currCode;
prevString = currString;
}
free(prevString);
free_dict(dictionary, 0, dictPos-1);
return 0;
}