// 제 목: Huffman Code Encoder
// 작성자: 김영대 ( http://www.howto.pe.kr )
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <math.h>
main(int argc, char **argv) {
int ifd, ofd, fsize;
unsigned char *src_data;
int i, j;
int Min, Max, Range, Pos, MinProb;
int Buffer, BufLen;
int *Prob, *Parent;
char *Bit, *BitCode;
int Len, TotalLen=0;
char outfile[255];
int debug = 0;
if (argc != 2) {
fprintf(stderr, "사용법: %s 파일명n", argv[0]);
exit(1);
}
if ((ifd = open(argv[1], O_RDONLY)) < 0) {
fprintf(stderr, "%s 파일을 읽을 수 없습니다n", argv[1]);
exit(1);
}
// source file 의 크기를 구하여 저장할 버퍼를 할당 받는다
fsize = lseek(ifd, 0L, 2); // 파일크기
lseek(ifd, 0L, 0); // 파일 포인터를 맨 앞으로 이동
src_data = (char *)malloc(fsize);
// source파일을 읽는다
if (read(ifd, src_data, fsize) < fsize)
exit(1);
// target파일을 생성한다
strcpy(outfile, argv[1]);
strcat(outfile, ".huf"); // 확장자는 .huf
if ((ofd = creat(outfile, 0644)) < 0) {
fprintf(stderr, "%s 파일을 만들 수 없습니다n", outfile);
exit(1);
}
// min,max byte 값을 구한다
Min = Max = src_data[0];
for (i = 1; i < fsize; i++) {
if (Min > src_data[i])
Min = src_data[i];
else if (Max < src_data[i])
Max = src_data[i];
}
Range = Max - Min + 1; // 분포된 byte 값들의 범위
// 초기화
Bit = (char *)malloc(2*Range-1); // 코드로 할당할 bit를 저장(0 or 1)
BitCode = (char *)malloc(2*Range-1); // 코드로 할당할 bit의 ASCII 저장('0' or '1')
Prob = (int *)malloc(sizeof(int)*2*Range-1); // 확률(0..Range-1), 모든 Prob를 더하면 Max 가 된다
Parent = (int *)malloc(sizeof(int)*2*Range-1);
memset(Bit, 0, 2*Range-1);
memset(BitCode, 0, 2*Range-1);
memset(Prob, 0, sizeof(int)*2*Range-1);
memset(Parent, -1, sizeof(int)*2*Range-1);
/* Example
source data: 3 4 4 5 6 6 6 7 7 10
src_data: 0 1 1 2 3 3 3 4 4 7
Min: 3
Max: 10
Range: 10-3+1 = 8
Probability:
index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Prob: 1 2 1 3 2 0 0 1 0 1 2 3 4 6 10
parent: 9 11 10 13 12 8 8 10 9 11 12 13 14 14 -1
*/
for (i = 0; i < fsize; i++) {
// byte 값에서 min을 빼서 0..Max-Min(= Range-1) 로 환산한다
// 그 이유는 Prob[]의 index를 0 부터 쓰기 위해서
src_data[i] -= Min;
Prob[src_data[i]]++; // byte 값이 나타난 횟수(확률)을 구한다
}
// Huffman code tree 를 만든다
for (i = 0; i < (Range-1); i++) {
/* 가장 작은 첫번째 확률을 구한다 */
Pos = -1;
MinProb = fsize; // 단지 가장 작은수를 구하기 위한 큰수
// 이전에 구한 두 byte 의 확률도 loop 에 포함시킨다
for (j = 0; j < Range+i; j++)
if ((Prob[j] < MinProb) && (Parent[j] == -1)) {
MinProb = Prob[j];
Pos = j;
}
Bit[Pos] = 0; // 비트할당
Parent[Pos] = Range + i; // tree로 가정할경우 상위(두 byte 의 확률을 가지고 있는) 노드의 위치
Prob[Parent[Pos]] += MinProb; // 첫번째 가장 작은것과 두번째 가장 작은 두 byte 의 확률을 더한다
/* 가장 작은 두번째 확률을 구한다 */
Pos = -1;
MinProb = fsize;
for (j = 0; j < Range+i; j++)
if ((Prob[j] < MinProb) && (Parent[j] == -1)) {
MinProb = Prob[j];
Pos = j;
}
Bit[Pos] = 1;
Parent[Pos] = Range + i;
Prob[Parent[Pos]] += MinProb;
}
/* Print Huffman code tree */
if (debug) {
for (i = 0; i < Range; i++) {
// 확률이 0 인것도 코드가 부여되지만 의미가 없으므로 제외
if (Prob[i] == 0)
continue;
// leaf 노드부터 parent 로 올라가면서 huffman code를 구한다
Len = 0;
Pos = i;
printf("값 %.2X, 확률 %d/%d, 코드 ", i+Min, Prob[i], fsize);
while (Parent[Pos] >= 0) {
BitCode[Len++] = Bit[Pos]; // leaf의 bit부터 들어가지만 실제 사용시는 반대
Pos = Parent[Pos]; // 상위 노드로 이동
}
// Huffman code로 encoding 하였을때의 소요되는 bit수 합산
TotalLen += Len * Prob[i];
// leaf의 bit부터 들어가 있으므로 역으로 출력
while (Len > 0)
printf("%c", '0' + BitCode[--Len]);
printf("n");
}
printf("코드의 평균길이 %f bitsn", TotalLen / (float)(fsize));
}
// Huffman encoded 파일의 헤더를 출력한다
write(ofd, "HM", 2); // ASCII "HM"
write(ofd, &Min, sizeof(Min)); // min Byte 값
write(ofd, &Max, sizeof(Max)); // max Byte 값, Range 는 Max-Min+1 로 계산하여 구한다
write(ofd, Prob, Range*sizeof(Prob[0])); // 확률
// Huffman codes 를 이용하여 실제로 Encoding 하여 출력한다
Buffer = 0;
BufLen = 0;
for (i = 0; i < fsize; i++) {
// leaf 노드부터 parent 로 올라가면서 huffman code를 구한다
Len = 0;
Pos = src_data[i];
while (Parent[Pos] >= 0) {
BitCode[Len++] = Bit[Pos];
Pos = Parent[Pos];
}
// Write Huffman code one bit at a time
while (Len > 0) {
// 이전 bit를 left shift(상위 bit로 이동) 시키고 현재 bit를 or 시킨다
Buffer = (Buffer << 1) | BitCode[--Len];
BufLen++;
// Buffer full = 4 byte boundary
if (BufLen == sizeof(Buffer)) {
write(ofd, &Buffer, 1, sizeof(Buffer));
Buffer = 0;
BufLen = 0;
}
}
}
// Buffer 에 남아있으면 4 byte boundary 시켜 출력
if (BufLen != 0) {
// left most shift(상위 bit로 이동)
Buffer = Buffer << (32 - BufLen);
write(ofd, &Buffer, 1, sizeof(Buffer));
}
free(src_data);
free(Bit);
free(BitCode);
free(Prob);
free(Parent);
close(ifd);
close(ofd);
} |
|
