/* */ /* LZWIN.C : Lempel-Ziv compression using Sliding Window */ /* */ #include "stdafx.h" #include "Lempel-Ziv.h" 1 /* 큐를초기화 */ void LZ::init_queue(void) front = rear = 0; /* 큐가꽉찼으면 1 을되돌림 */ int LZ::queue_full(void) return (rear + 1) % SIZE == front; /* 큐가비었으면 1 을되돌림 */ int LZ::queue_empty(void) return front == rear; /* 큐에문자를집어넣음 */ int LZ::put(int k) queue[rear] = k; rear = ++rear % SIZE; return k; /* 큐에서문자를꺼냄 */ int LZ::get(void) i = queue[front]; queue[front] = 0; front = ++front % SIZE; return i; /* k 를큐의첨자로변환, 범위에서벗어나는것을범위내로조정 */ int LZ::qx(int k) return (k + SIZE) % SIZE; /* srcname[] 에서확장자를 lzw 로바꿈 */ void LZ::make_dstname(char dstname[], char srcname[]) char temp[256]; int check=0; //fnsplit(srcname, temp, temp, dstname, temp); strcpy(temp,srcname); strcat(temp,".lzw"); strcpy(dstname,temp);
2 /* 파일의이름을받아그파일의길이를되돌림 */ long LZ::file_length(char filename[]) FILE *fp; long l; if ((fp = fopen(filename, "rb")) == NULL) return 0L; fseek(fp, 0, SEEK_END); l = ftell(fp); fclose(fp); return l; /* jump_table[] 의모든노드를제거 */ void LZ::delete_all_jump(void) jump *j, *d; for (i = 0; i < 256; i++) j = jump_table[i].next; while (j!= NULL) d = j; j = j->next; free(d); jump_table[i].next = NULL; /* jump_table[] 에새로운문자의위치를삽입 */ void LZ::put_jump(int c, int ptr) jump *j; if ((j = (jump*)malloc(sizeof(jump))) == NULL) printf(" nerror : Out of memory."); j->next = jump_table[c].next; /* 선두에삽입 */ jump_table[c].next = j; j->index = ptr; /* ptr 위치를가지는노드를삭제 */ void LZ::del_jump(int c, int ptr) jump *j, *p; p = jump_table + c; j = p->next; while (j && j->index!= ptr) /* 노드검색 */
p = j; j = j->next; 3 p->next = j->next; free(j); /* cp 와 length 로주어진패턴을해시법으로찾아서되돌림 */ int LZ::qmatch(int length) jump *t, *p; int cp, sp; cp = qx(rear - length); /* cp 의위치를얻음 */ p = jump_table + queue[cp]; t = p->next; while (t!= NULL) sp = t->index; /* 첫문자는비교할필요없음. -> i =1; */ for (i = 1; i < length && queue[qx(sp+i)] == queue[qx(cp+i)]; i++); if (i == length) return sp; /* 패턴을찾았음 */ t = t->next; return FAIL; /* 문자 c 를출력파일에씀 */ int LZ::putc1(int c, FILE *dst) if (c == ESCAPE) /* 탈출문자이면 < 탈출문자 0x00> 쌍으로치환 */ putc(escape, dst); putc(0x00, dst); putc(c, dst); return c; /* 패턴을압축해서출력파일에씀 */ void LZ::encode(int sp, int cp, int length, FILE *dst) /* jump_table[] 에패턴의문자들을기록 */ put_jump(queue[qx(cp+i)], qx(cp+i)); putc(escape, dst); /* 탈출문자 */ putc(qx(cp-sp), dst); /* 상대위치 */ putc(length, dst); /* 패턴길이 */ /* Sliding Window 를이용한 LZ 압축함수 */ void LZ::lzwin_comp(FILE *src, char *srcname)
int length; char dstname[13]; FILE *dst; int sp, cp; int i, j; int written; 4 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 문자삽입 */ for (i = 0; i < 256; i++) /* jump_table[] 초기화 */ jump_table[i].next = NULL; rewind(src); init_queue(); put(getc(src)); while (!feof(src)) if (queue_full()) /* 큐가꽉찼으면 */ if (sp == front) /* sp 의패턴이넘어가려고하면현재의정보로출력파일에씀 */ if (length > 3) encode(sp, cp, length, dst); put_jump(queue[qx(cp+i)], qx(cp+i)); putc1(queue[qx(cp+i)], dst); /* 큐에서빠져나가는문자의위치를 jump_table[] 에서삭제 */ del_jump(queue[front], front); get(); /* 큐에서한문자삭제 */ if (length == 0) cp = qx(rear-1); sp = qmatch(length+1); if (sp == FAIL) putc1(queue[cp], dst); put_jump(queue[cp], cp);
length++; 5 put(getc(src)); if (length > 0) if (queue[qx(cp+length)]!= queue[qx(sp+length)]) j = qmatch(length+1); j = sp; if (j == FAIL length > SIZE - 3) if (length > 3) encode(sp, cp, length, dst); put_jump(queue[qx(cp+i)], qx(cp+i)); putc1(queue[qx(cp+i)], dst); sp = j; length++; put(getc(src)); /* 큐에남은문자출력 */ if (length > 3) encode(sp, cp, length, dst); putc1(queue[qx(cp+i)], dst); delete_all_jump(); fclose(dst); /* 큐에문자를넣고, 만일꽉찼다면큐에서빠져나온문자를출력 */ void LZ::put_byte(int c, FILE *dst) if (queue_full()) putc(get(), dst); put(c); /* Sliding Window 를이용한 LZ 압축법의복원함수 */ void LZ::lzwin_decomp(FILE *src) int c; char srcname[13]; FILE *dst; int length; int i = 0, j; int sp;
rewind(src); c = getc(src); if (c!= IDENT1 getc(src)!= IDENT2) /* 헤더확인 */ printf(" n Error : That file is not Lempel-Ziv Encoding file"); fcloseall(); 6 while ((c = getc(src))!= NULL) /* 파일이름을얻음 */ srcname[i++] = c; srcname[i] = NULL; if ((dst = fopen(srcname, "wb")) == NULL) printf(" n Error : Disk full? "); fcloseall(); init_queue(); c = getc(src); while (!feof(src)) if (c == ESCAPE) /* 탈출문자이면 */ if ((c = getc(src)) == 0) /* < 탈출문자 0x00> 이면 */ put_byte(escape, dst); /* < 탈출문자상대위치패턴길이 > 이면 */ length = getc(src); sp = qx(rear - c); put_byte(queue[qx(sp+i)], dst); /* 일반적인문자의경우 */ put_byte(c, dst); c = getc(src); while (!queue_empty()) /* 큐에남아있는모든문자를출력 */ putc(get(), dst); fclose(dst); void LZ::main(char filename[], int mode) FILE *src; long s, d; char dstname[13]; clock_t tstart, tend; tstart = clock(); /* 시작시간기록 */ // 압축 if(mode == 1) if ((src = fopen(filename, "rb")) == NULL)
printf(" n Error : That file does not exist."); lzwin_comp(src, filename); make_dstname(dstname, filename); 7 s = file_length(filename); /* 원래파일의크기를구함 */ d = file_length(dstname); /* 압축파일의크기를구함 */ printf(" nfile compressed to %d%%.", (int)((double)d/s*100.)); // 압축해제 if(mode == 2) src = fopen(filename, "rb"); lzwin_decomp(src); printf(" nfile decompressed & created."); fclose(src); tend = clock(); /* 종료시간기록 */ printf(" ntime elapsed %d ticks", tend - tstart); /* 수행시간출력 : 단위 tick */