#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef struct tmp_node
{
unsigned char uch;
unsigned int weight;
}tmpNode;
typedef struct huf_node
{
unsigned char uch;
unsigned int weight;
int parent, lchild, rchild;
char* code;
}hufNode, *hufPtr;
void select(hufPtr huf_tree, int n, int* s1, int* s2)
{
int i = 0;
unsigned long min = ULONG_MAX;
for (; i < n; ++i)
{
if ( !huf_tree[i].parent && huf_tree[i].weight < min)
{
min = huf_tree[i].weight;
*s1 = i;
}
}
huf_tree[*s1].parent = 1;
min = ULONG_MAX;
for (i = 0; i < n; ++i)
{
if (!huf_tree[i].parent && huf_tree[i].weight < min)
{
min = huf_tree[i].weight;
*s2 = i;
}
}
}
void create_huf_tree(hufPtr huf_tree, int char_kinds, int node_num)
{
int s1, s2;
int i = char_kinds;
for (; i < node_num; ++i)
{
select(huf_tree, i, &s1, &s2);
huf_tree[s1].parent = huf_tree[s2].parent = i;
huf_tree[i].lchild = s1;
huf_tree[i].rchild = s2;
huf_tree[i].weight = huf_tree[s1].weight + huf_tree[s2].weight;
}
}
void huf_code(hufPtr huf_tree, int char_kinds)
{
int cur, next;
int i;
char code_tmp[256] = { 0 };
int index;
for (i = 0; i < char_kinds; i++)
{
code_tmp[255] = '\0';
index = 255;
for (cur = i, next = huf_tree[cur].parent; next != 0; cur = next, next = huf_tree[next].parent)
{
if (cur == huf_tree[next].lchild)
{
code_tmp[--index] = '0';
}
else
{
code_tmp[--index] = '1';
}
}
huf_tree[i].code = (char*)malloc( (256 - index) * sizeof(char));
assert(huf_tree[i].code != NULL);
strcpy(huf_tree[i].code, code_tmp + index);
}
}
void compress(const char* infile, const char* outfile)
{
tmpNode* tmp_node = (tmpNode*)malloc(sizeof(tmpNode) * 256);
assert(tmp_node != NULL);
for (int i = 0; i < 256; ++i)
{
tmp_node[i].uch = (unsigned char)i;
tmp_node[i].weight = 0;
}
FILE* inf = fopen(infile, "rb");
assert(inf != NULL);
unsigned char char_tmp;
unsigned int file_len = 0;
while (!feof(inf))
{
fread((char*)&char_tmp, sizeof(unsigned char), 1, inf);
++tmp_node[char_tmp].weight;
++file_len;
}
fclose(inf);
tmpNode swap_node;
for (int i = 0; i < 255; ++i)
{
for (int j = i + 1; j < 256; ++j)
{
if (tmp_node[i].weight < tmp_node[j].weight)
{
swap_node = tmp_node[i];
tmp_node[i] = tmp_node[j];
tmp_node[j] = swap_node;
}
}
}
int i = 0;
for (; i < 256; ++i)
{
if (!tmp_node[i].weight)
{
break;
}
}
int char_kinds = i;
if (char_kinds == 1)
{
FILE* outf = fopen(outfile, "wb");
assert(outf != NULL);
fwrite((char*)&char_kinds, sizeof(char_kinds), 1, outf);
fwrite((char*)&file_len, sizeof(file_len), 1, outf);
fwrite((char*)&tmp_node[0].uch, sizeof(unsigned char), 1, outf);
free(tmp_node);
fclose(outf);
}
else
{
int node_num = char_kinds * 2 - 1;
hufPtr huf_tree = (hufPtr)malloc(sizeof(hufNode) * node_num);
assert(huf_tree != NULL);
int i;
for (i = 0; i < char_kinds; ++i)
{
huf_tree[i].uch = tmp_node[i].uch;
huf_tree[i].weight = tmp_node[i].weight;
huf_tree[i].parent = 0;
}
free(tmp_node);
for (; i < node_num; ++i)
{
huf_tree[i].parent = 0;
huf_tree[i].weight = 0;
}
create_huf_tree(huf_tree, char_kinds, node_num);
huf_code(huf_tree, char_kinds);
FILE* outf = fopen(outfile, "wb");
assert(outf != NULL);
fwrite((char*)&char_kinds, sizeof(char_kinds), 1, outf);
for (i = 0; i < char_kinds; ++i)
{
fwrite((char*)&huf_tree[i].uch, sizeof(unsigned char), 1, outf);
fwrite((char*)&huf_tree[i].weight, sizeof(unsigned int), 1, outf);
}
fwrite((char*)&file_len, sizeof(file_len), 1, outf);
inf = fopen(infile, "rb");
assert(inf != NULL);
char code_buf[256] = { 0 };
while (!feof(inf))
{
fread((char*)&char_tmp, sizeof(char_tmp), 1, inf);
for (i = 0; i < char_kinds; ++i)
{
if (huf_tree[i].uch == char_tmp)
{
strcat(code_buf, huf_tree[i].code);
}
}
while (strlen(code_buf) >= 8)
{
char_tmp = '\0';
for (i = 0; i < 8; ++i)
{
char_tmp <<= 1;
if (code_buf[i] == '1')
{
char_tmp |= 1;
}
}
fwrite((char*)&char_tmp, sizeof(char_tmp), 1, outf);
strcpy(code_buf, code_buf + 8);
}
}
int code_len = strlen(code_buf);
if (code_len > 0)
{
char_tmp = '\0';
for (i = 0; i < code_len; ++i)
{
char_tmp <<= 1;
if (code_buf[i] == '1')
{
char_tmp |= 1;
}
}
char_tmp <<= (8 - code_len);
fwrite((char*)&char_tmp, sizeof(char_tmp), 1, outf);
}
fclose(inf);
fclose(outf);
for (i = 0; i < char_kinds; ++i)
{
free(huf_tree[i].code);
}
free(huf_tree);
}
}
void extract(const char* infile, const char* outfile)
{
FILE* inf = fopen(infile, "rb");
assert(inf != NULL);
int char_kinds;
fread((char*)&char_kinds, sizeof(char_kinds), 1, inf);
unsigned int file_len;
unsigned char char_tmp;
if (char_kinds == 1)
{
fread((char*)& file_len, sizeof(file_len), 1, inf);
fread((char*)&char_tmp, sizeof(char_tmp), 1, inf);
FILE* outf = fopen(outfile, "wb");
assert(outf != NULL);
fwrite((char*)&char_tmp, sizeof(char_tmp), file_len, outf);
fclose(outf);
fclose(inf);
return;
}
else
{
int node_num = char_kinds * 2 - 1;
hufPtr huf_tree = (hufPtr)malloc(sizeof(hufNode) * node_num);
assert(huf_tree != NULL);
int i;
for (i = 0; i < char_kinds; ++i)
{
fread((char*)&huf_tree[i].uch, sizeof(unsigned char), 1, inf);
fread((char*)&huf_tree[i].weight, sizeof(unsigned int), 1, inf);
huf_tree[i].parent = 0;
}
for (; i < node_num; ++i)
{
huf_tree[i].parent = 0;
huf_tree[i].weight = 0;
}
create_huf_tree(huf_tree, char_kinds, node_num);
fread((char*)&file_len, sizeof(file_len), 1, inf);
unsigned int write_len = 0;
int root = node_num - 1;
FILE* outf = fopen(outfile, "wb");
assert(outf != NULL);
while (1)
{
fread((char*)&char_tmp, sizeof(char_tmp), 1, inf);
for (int i = 0; i < 8; ++i)
{
if (char_tmp & 128)
{
root = huf_tree[root].rchild;
}
else
{
root = huf_tree[root].lchild;
}
if (root < char_kinds)
{
fwrite((char*)&huf_tree[root].uch, sizeof(unsigned char), 1, outf);
root = node_num - 1;
if (++write_len == file_len)
{
break;
}
}
char_tmp <<= 1;
}
if (write_len == file_len)
{
break;
}
}
fclose(inf);
fclose(outf);
free(huf_tree);
}
}
int main(void)
{
system("pause");
return 0;
}
|