Mastering Algorithms With C - Kyle Loudon [166]
**compressed, int size) {
BiTree *tree;
HuffCode table[UCHAR_MAX + 1];
int freqs[UCHAR_MAX + 1],
max,
scale,
hsize,
ipos,
opos,
cpos,
c,
i;
unsigned char *comp,
*temp;
/*****************************************************************************
* *
* Initially, there is no buffer of compressed data. *
* *
*****************************************************************************/
*compressed = NULL;
/*****************************************************************************
* *
* Get the frequency of each symbol in the original data. *
* *
*****************************************************************************/
for (c = 0; c <= UCHAR_MAX; c++)
freqs[c] = 0;
ipos = 0;
if (size > 0) {
while (ipos < size) {
freqs[original[ipos]]++;
ipos++;
}
}
/*****************************************************************************
* *
* Scale the frequencies to fit into one byte. *
* *
*****************************************************************************/
max = UCHAR_MAX;
for (c = 0; c <= UCHAR_MAX; c++) {
if (freqs[c] > max)
max = freqs[c];
}
for (c = 0; c <= UCHAR_MAX; c++) {
scale = (int)(freqs[c] / ((double)max / (double)UCHAR_MAX));
if (scale == 0 && freqs[c] != 0)
freqs[c] = 1;
else
freqs[c] = scale;
}
/*****************************************************************************
* *
* Build the Huffman tree and table of codes for the data. *
* *
*****************************************************************************/
if (build_tree(freqs, &tree) != 0)
return -1;
for (c = 0; c <= UCHAR_MAX; c++)
memset(&table[c], 0, sizeof(HuffCode));
build_table(bitree_root(tree), 0x0000, 0, table);
bitree_destroy(tree);
free(tree);
/*****************************************************************************
* *
* Write the header information. *
* *
*****************************************************************************/
hsize = sizeof(int) + (UCHAR_MAX + 1);
if ((comp = (unsigned char *)malloc(hsize)) == NULL)
return -1;
memcpy(comp, &size, sizeof(int));
for (c = 0; c <= UCHAR_MAX; c++)
comp[sizeof(int) + c] = (unsigned char)freqs[c];
/*****************************************************************************
* *
* Compress the data. *
* *
*****************************************************************************/
ipos = 0;
opos = hsize * 8;
while (ipos < size) {
/**************************************************************************
* *
* Get the next symbol in the original data. *
* *
**************************************************************************/
c = original[ipos];
/**************************************************************************
* *
* Write the code for the symbol to the buffer of compressed data. *
* *
**************************************************************************/
for (i = 0; i < table[c].size; i++) {
if (opos % 8 == 0) {
/********************************************************************
* *
* Allocate another byte for the buffer of compressed data. *
* *
********************************************************************/
if ((temp = (unsigned char *)realloc(comp,(opos / 8) + 1)) == NULL) {
free(comp);
return -1;
}
comp = temp;
}
cpos = (sizeof(short) * 8) - table[c].size + i;
bit_set(comp, opos, bit_get((unsigned char *)&table[c].code, cpos));
opos++;
}
ipos++;
}
/*****************************************************************************
* *
* Point to the buffer of compressed data. *
* *
*****************************************************************************/
*compressed = comp;
/*****************************************************************************
* *
* Return the number of bytes in the compressed data. *
* *
*****************************************************************************/
return ((opos - 1) / 8) + 1;
}
/*****************************************************************************