#include "stdafx.h" #include "Huffman.h" 1 /* 비트의부분을뽑아내는함수 */ unsigned HF::bits(unsigned x, int k, int j) return (x >> k) & ~(~0 << j); /* 파일에존재하는문자들의빈도를구해서 freq[] 에저장 */ void HF::get_freq(FILE *fp) for (i = 0; i < 256; i++) freq[i] = 0L; rewind(fp); while (!feof(fp)) freq[getc(fp)]++; /* 최소빈도수를찾는함수 */ int HF::find_minimum(void) int mindex; mindex = 0; for (i = 1; i < nhead; i++) if (head[i]->count < head[mindex]->count) mindex = i; return mindex; /* freq[] 로 Huffman Tree를구성하는함수 */ void HF::construct_trie(void) int m; huf *h, *h1, *h2; /* 초기단계 */ for (i = nhead = 0; i < 256; i++) if (freq[i]!= 0) if ((h = (huf*)malloc(sizeof(huf))) == NULL) h->count = freq[i]; h->data = i; h->left = h->right = NULL; head[nhead++] = h; /* 생성단계 */ while (nhead > 1) m = find_minimum(); h1 = head[m]; head[m] = head[--nhead]; m = find_minimum(); h2 = head[m];
if ((h = (huf*)malloc(sizeof(huf))) == NULL) h->count = h1->count + h2->count; h->data = 0; h->left = h1; h->right = h2; head[m] = h; 2 huf_head = head[0]; /* Huffman Tree를제거 */ void HF::destruct_trie(huf *h) if (h!= NULL) destruct_trie(h->left); destruct_trie(h->right); free(h); /* Huffman Tree에서코드를얻어냄. code[] 와 len[] 의설정 */ void HF::_make_code(huf *h, unsigned c, int l) if (h->left!= NULL h->right!= NULL) c <<= 1; l++; _make_code(h->left, c, l); c = 1u; _make_code(h->right, c, l); c >>= 1; l--; else code[h->data] = c; len[h->data] = l; /* _make_code() 함수의입구함수 */ void HF::make_code(void) for (i = 0; i < 256; i++) code[i] = len[i] = 0; _make_code(huf_head, 0u, 0); /* srcname[] 에서확장자를 huf 로바꿈 */ void HF::make_dstname(char dstname[], char srcname[]) char temp[256]; int check=0; strcpy(temp,srcname); strcat(temp,".huf"); strcpy(dstname,temp); /* 파일의이름을받아그파일의길이를되돌림 */ long HF::file_length(char filename[])
FILE *fp; long l; if ((fp = fopen(filename, "rb")) == NULL) return 0L; 3 fseek(fp, 0, SEEK_END); l = ftell(fp); fclose(fp); return l; #define NORMAL 0 #define FLUSH 1 /* 파일에한비트씩출력하도록캡슐화한함수 */ void HF::put_bitseq(unsigned i, FILE *dst, int flag) static unsigned wbyte = 0; if (bitloc < 0 flag == FLUSH) putc(wbyte, dst); bitloc = 7; wbyte = 0; wbyte = i << (bitloc--); /* Huffman 압축함수 */ void HF::huffman_comp(FILE *src, char *srcname) int cur; int max; union long lenl; int leni[2]; length; char dstname[13]; FILE *dst; char temp[20]; int b; fseek(src, 0L, SEEK_END); length.lenl = ftell(src); rewind(src); make_dstname(dstname, srcname); /* 출력파일이름만듬 */ if ((dst = fopen(dstname, "wb")) == NULL) printf(" n Error : Can't create file."); fcloseall(); /* 압축파일의헤더작성 */ putc(ident1, dst); /* 출력파일에식별자삽입 */ putc(ident2, dst); fputs(srcname, dst); /* 출력파일에파일이름삽입 */ putc(null, dst); /* NULL 문자열삽입 */ putw(length.leni[0], dst); /* 파일의길이출력 */ //putw(length.leni[1], dst); get_freq(src); construct_trie(); make_code(); /* code[] 와 len[] 을출력 */ for (i = 0; i < 128; i++) putw(code[i*2], dst); cur = len[i*2] << 4; cur = len[i*2+1]; putc(cur, dst);
putw(code[i*2+1], dst); destruct_trie(huf_head); rewind(src); bitloc = 7; while (1) cur = getc(src); 4 if (feof(src)) break; for (b = len[cur] - 1; b >= 0; b--) put_bitseq(bits(code[cur], b, 1), dst, NORMAL); put_bitseq(0, dst, FLUSH); fclose(dst); /* len[] 와 code[] 를이용하여 Huffman Tree 를구성 */ void HF::trie_insert(int data) int b = len[data] - 1; huf *p, *t; if (huf_head == NULL) if ((huf_head = (huf*)malloc(sizeof(huf))) == NULL) huf_head->left = huf_head->right = NULL; p = t = huf_head; while (b >= 0) if (bits(code[data], b, 1) == 0) t = t->left; if (t == NULL) if ((t = (huf*)malloc(sizeof(huf))) == NULL) t->left = t->right = NULL; p->left = t; else t = t->right; if (t == NULL) if ((t = (huf*)malloc(sizeof(huf))) == NULL) t->left = t->right = NULL; p->right = t; p = t;
b--; t->data = data; /* trie_insert() 의입구함수 */ void HF::restruct_trie(void) 5 huf_head = NULL; for (i = 0; i < 256; i++) if (len[i] > 0) trie_insert(i); /* 파일에서한비트씩읽는것처럼캡슐화한함수 */ int HF::get_bitseq(FILE *fp) static int cur = 0; if (bitloc < 0) cur = getc(fp); bitloc = 7; return bits(cur, bitloc--, 1); /* Huffman 압축복원알고리즘 */ void HF::huffman_decomp(FILE *src) int cur; char srcname[13]; FILE *dst; union long lenl; int leni[2]; length; long n; huf *h; int i = 0; rewind(src); cur = getc(src); if (cur!= IDENT1 getc(src)!= IDENT2) printf(" n Error : That file is not Run-Length Encoding file"); fcloseall(); while ((cur = getc(src))!= NULL) srcname[i++] = cur; srcname[i] = NULL; if ((dst = fopen(srcname, "wb")) == NULL) printf(" n Error : Disk full? "); fcloseall(); length.leni[0] = getw(src); //length.leni[1] = getw(src); for (i = 0; i < 128; i++) /* code[] 와 len[] 을읽어들임 */ code[i*2] = getw(src); cur = getc(src); code[i*2+1] = getw(src); len[i*2] = bits(cur, 4, 4); len[i*2+1] = bits(cur, 0, 4); restruct_trie(); /* 헤더를읽어서 Huffman Tree 재구성 */
n = 0; bitloc = -1; while (n < length.lenl) h = huf_head; while (h->left && h->right) if (get_bitseq(src) == 1) h = h->right; else h = h->left; putc(h->data, dst); n++; destruct_trie(huf_head); fclose(dst); 6 void HF::main(char filename[], int mode) FILE *src; long s, d; char dstname[13]; clock_t tstart, tend; tstart = clock(); /* 시작시각기록 */ if (mode == 1) /* 압축 */ s = file_length(filename); /* 원래파일의크기구함 */ src = fopen(filename, "rb"); huffman_comp(src, filename); make_dstname(dstname, filename); d = file_length(dstname); /* 압축파일의크기를구함 */ printf(" nfile compressed to %d%%.", (int)((double)d/s*100.)); else if (mode == 2) /* 압축의해제 */ src = fopen(filename, "rb"); huffman_decomp(src); printf(" nfile decompressed & created."); fclose(src); tend = clock(); /* 종료시각저장 */ printf(" ntime elapsed %d ticks", tend - tstart); /* 수행시간출력 : 단위 tick */