Here is an update to my previous thread which you can find here. 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.
The fread_twelve function has been heavily modified to deal with detecting and reading the last entry, which is padded from 12 to 16 bits. Let me know what you think!
I'm also quite 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!
/**
* file: lzw.h
*
* function declarations for lempel ziv-welch 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
/**
* file: decompress.c
*
* implementation of lempel ziv-welch 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;
}
}
/**
* file: lzw.c
*
*
* Implementation of lempel ziv-welch 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]);
}
}
/**
* Gets 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 prevBytes[2];
byte buf[3];
if (left)
{
if (fread(buf, 1, 2, source) != 2)
{
// reached eof: even number of entries
return 0;
}
if (fread(buf+2, 1, 1, source) != 1)
{
// reached eof: buf[0] and buf[1] are the padded last entry
value = (buf[0] << 8) | buf[1];
}
else
{
value = (buf[0] << 4) | (buf[1] >> 4);
left = false;
prevBytes[0] = buf[1];
prevBytes[1] = buf[2];
}
}
else
{
value = ((prevBytes[0] & 0x0F) << 8) | prevBytes[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, 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;
}
--leak-check=full\$\endgroup\$compresstool using-b 12to set the bit width, but running your program on it fails with "decompress: currCode out of dictionary range." Do you know what might be the cause? What tool are you using for compressing test files? \$\endgroup\$