Here is a simple decompressor in C. 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 real novice and really eager to learn from people here, so fire away!
lzw.h:
/**
* lzw.h
* Function declarations for lzw decompression algorithm.
*/
#ifndef LZW_H
#define LZW_H
#include <stdio.h>
#include <stdlib.h>
/**
* Frees all blocks between 'from' and 'to' (inclusive) in the dict.
*/
void free_dict (unsigned char* dict[], int from, int to);
/**
* Enters the first 256 ASCII values into dict.
*/
void load_dict_defaults (unsigned char* dict[]);
/**
* 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:
/**
* decompress.c
* Implementation of LZW decompression algorithm using 12-bit fixed-width compression format.
*
* Usage: decompress
*/
#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 destination\n");
return 1;
}
// open compressed file
FILE* source = fopen(argv[1], "r");
if (source == NULL)
{
printf("Error: cannot open %s\n", argv[1]);
return 1;
}
// open destination file
FILE* dest = fopen(argv[2], "w");
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:
/**
* 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>
unsigned char* dictionary[4096];
/**
* Enters the first 256 ASCII values into dict.
*/
void load_dict_defaults (unsigned char* dict[])
{
unsigned char* temp;
unsigned char c = 0;
for (int i = 0; i < 256; i++)
{
temp = calloc(2, sizeof(unsigned char));
temp[0] = c++;
dict[i] = temp;
}
}
/**
* Frees all blocks between 'from' and 'to' (inclusive) in the dict.
*/
void free_dict (unsigned char* 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;
unsigned char buf[2];
if (left)
{
// if left, read two bytes and calculate int
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;
}
else
{
// if right, rewind source by one byte, read two bytes and calculate int
fseek(source, -1, SEEK_CUR);
if (fread(buf, 1, 2, source) != 2) {return 0;}
value = ((buf[0] & 0x0F) << 8) | buf[1];
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);
int dictPos = 256;
int prevCode, currCode;
unsigned char* prevString, *currString;
// read in the first character
currCode = fread_twelve(source);
if (dictionary[currCode] == NULL)
{
return 1;
}
size_t size;
size = strlen((char*)dictionary[currCode]);
currString = calloc(size + 2, sizeof(char)); //+2 for upcoming char and null
if (currString == NULL)
{
return 1;
}
memcpy(currString, dictionary[currCode], size+1);
fprintf(dest, "%s", currString);
prevCode = currCode;
prevString = currString;
// read in the rest of the characters
while ( (currCode = fread_twelve(source)) && currCode )
{
if (dictionary[currCode] == NULL)
{
return 1;
}
size = strlen((char*)dictionary[currCode]);
currString = calloc(size + 2, sizeof(char)); //+2 for upcoming char and null
if (currString == NULL)
{
return 1;
}
memcpy(currString, dictionary[currCode], size+1);
fprintf(dest, "%s", currString);
if (currCode > dictPos)
{
dictionary[dictPos++] = (unsigned char*) strncat((char*)prevString, (char*)prevString, 1);
}
else
{
dictionary[dictPos++] = (unsigned char*) strncat((char*)prevString, (char*)currString, 1);
}
// restart dict if full.
if (dictPos >= 4096)
{
free_dict(dictionary, 256, 4096);
dictPos = 256;
}
prevCode = currCode;
prevString = currString;
}
free_dict(dictionary, 0, dictPos-1);
return 0;
}
Link to the followup question: LZW decompressor in C (II)