?? lzw.cpp
字號:
// LZW.cpp: 實現CLZW類.
//
#include "LZW.h"
//---------------------------------------------------------------------------
CLZW::CLZW()
{
hash_code = 0;
hash_prefix = 0;
hash_suffix = 0;
symbol_head = 0;
symbol_tail = 0;
symbol_stack= 0;
}
//---------------------------------------------------------------------------
CLZW::~CLZW()
{
if(hash_code) free(hash_code);
if(hash_prefix) free(hash_prefix);
if(hash_suffix) free(hash_suffix);
if(symbol_head) free(symbol_head);
if(symbol_tail) free(symbol_tail);
if(symbol_stack) free(symbol_stack);
}
//---------------------------------------------------------------------------
// 一個零長度的塊標志數據塊序列的結束.
int CLZW::GetDataBlock (char *buf)
{
int count;
if ((count = getc(infile)) != EOF)
{
if (count > 0) {
if (fread(buf, 1, count,infile)!=(size_t)count)
return -1;
}
}
return count;
}
//---------------------------------------------------------------------------
// 跳過一序列數據塊直到找到塊結尾.
void CLZW::SkipDataBlocks ()
{
char buf[256];
while (GetDataBlock(buf) > 0);
}
//---------------------------------------------------------------------------
// （重新）初始化LZW 狀態.
void CLZW::ReInitLZW()
{
n_bits = init_bits;
maxcode = ClearCode << 1; // 2^code_size.
code_counter = ClearCode + 2; // 第一個未用的代碼值.
sp = symbol_stack; // 初始化堆棧使其為空.
}
//---------------------------------------------------------------------------
// 初始化,以便 LZWReadByte和GetCode的調用.
void CLZW::InitLZWCode (FILE* file, int ibits)
{
printf("decompress size %d\n",ibits);
// GetCode 初始化.
symbol_head = (code_int *)malloc(LZW_TABLE_SIZE * sizeof(code_int));
symbol_tail = (UINT8 *) malloc(LZW_TABLE_SIZE * sizeof(UINT8));
symbol_stack = (UINT8 *) malloc(LZW_TABLE_SIZE * sizeof(UINT8));
infile=file;
init_bits=ibits;
last_byte = 2; // 保證重新拷貝最后兩個字節.
last_bit = 0; // 緩沖區為空.
cur_bits = 0; // 緩沖區的第一個字符.
out_of_blocks = false;
// LZWReadByte 初始化.
ClearCode = ((code_int) 1 << (init_bits-1));
EOFCode = ClearCode + 1;
first_byte = true;
ReInitLZW();
}
//---------------------------------------------------------------------------
// 從壓縮數據中提取以后的 code_size 個比特,假定code_size 小于16.
int CLZW::GetCode ()
{
int offs, ret, count;
if ( (cur_bits+n_bits) > last_bit) { // 重新裝載緩沖區.
if (out_of_blocks) {
return EOFCode;
}
// 保持最后兩個字節- 假定 code_size <= 16.
code_buf[0] = code_buf[last_byte-2];
code_buf[1] = code_buf[last_byte-1];
// 裝載更多的字節; 如果到達終止，設置標識.
if ((count = GetDataBlock(&code_buf[2])) == 0) {
out_of_blocks = true;
return EOFCode;
}
// 重置計數器.
cur_bits = (cur_bits - last_bit) + 16;
last_byte = 2 + count;
last_bit = last_byte * 8;
}
// 形成積累下一個24 bits的字符.
offs = cur_bits >> 3; // 字節包含 cur_bit.
cur_accum = code_buf[offs+2] & 0xFF;
cur_accum <<= 8;
cur_accum |= code_buf[offs+1] & 0xFF;
cur_accum <<= 8;
cur_accum |= code_buf[offs] & 0xFF;
// 向右積累排列cur_bit, 然后通過掩碼得到需要的bits數.
cur_accum >>= (cur_bits & 7);
ret = ((int) cur_accum) & ((1 << n_bits) - 1);
cur_bits += n_bits;
return ret;
}
//---------------------------------------------------------------------------
// 讀取一個 LZW 壓縮的字節.
int CLZW::LZWReadByte ()
{
static int oldcode; // 前一個 LZW 符.
static int firstcode; // 原碼擴展后的第一個字節.
register int code; // 當前工作代碼.
int incode; // 保存實際的輸入代碼.
if (first_byte) {
first_byte = false;
code = ClearCode;
} else {
// 如果堆棧有以前讀過的符號，返回它.
if (sp > symbol_stack)
return (int) *(--sp);
// 讀入新的符號.
code = GetCode();
}
if (code == ClearCode) {
ReInitLZW();
do {
code = GetCode();
} while (code == ClearCode);
if (code > ClearCode) { // 保證它是一個未壓縮的字節.
printf("Corrupt data in LZWReadByte check 1.\n");
code = 0;
}
firstcode = oldcode = code; // 使 firstcode, oldcode 有效.
return code;
}
if (code == EOFCode) {
if (! out_of_blocks) {
SkipDataBlocks();
out_of_blocks = true;
}
// 沒有足夠的數據.
printf("Premature end of file!\n");
return 257;
}
// 得到正常未壓縮的字節或LZW 符號.
incode = code;
if (code >= code_counter) {
if (code > code_counter) {
printf("Corrupt data in LZWReadByte check 2.\n");
incode = 0; // 以免在符號表中產生循環.
}
*sp++ = (UINT8) firstcode;
code = oldcode;
}
// 如果是一個符號, 把它擴展后放入堆棧.
while (code >= ClearCode) {
// 符號尾: 一個簡單的字節值.
*sp++ = symbol_tail[code];
// 符號頭: 另一個LZW 符號.
code = symbol_head[code];
}
// 表示的是一個未被壓縮的字節.
firstcode = code;
// 判別表中是否有空間.
if ((code = code_counter) < LZW_TABLE_SIZE) {
// 定義一個新符號 = 原來的符號 + 這個符號擴展后的頭字節.
symbol_head[code] = oldcode;
symbol_tail[code] = (UINT8) firstcode;
code_counter++;
// 增加 n_bits.
if ((code_counter >= maxcode) && (n_bits < MAX_LZW_BITS)) {
n_bits++;
// 保持等于 2^code_size.
maxcode <<= 1;
}
}
oldcode = incode; // 保存最后的輸入符號，以便以后使用.
return firstcode; // 返回符號擴展后的第一個字節.
}
//---------------------------------------------------------------------------
// flush any accumulated data.
void CLZW::flush_packet ()
{
if (bytesinpkt > 0) { // never write zero-length packet.
packetbuf[0] = (char) bytesinpkt++;
if (fwrite(packetbuf, 1, bytesinpkt,outfile)
!= (size_t) bytesinpkt)
printf("Output file write error.\n");
bytesinpkt = 0;
}
}
//---------------------------------------------------------------------------
// 在現有的緩沖區增加一個字節，同時在有必要時向磁盤寫保存數據.
void CLZW::CHAR_OUT (int c)
{
packetbuf[++bytesinpkt] = (char) (c);
if (bytesinpkt >= 255)
flush_packet();
}
//---------------------------------------------------------------------------
// 發送一個n_bits比特的代碼,
// 用 cur_accum 和 cur_bits 重新組成新的 8-bit 字節.
void CLZW::output (code_int code)
{
cur_accum |= ((INT32) code) << cur_bits;
cur_bits += n_bits;
while (cur_bits >= 8) {
CHAR_OUT(cur_accum & 0xFF);
cur_accum >>= 8;
cur_bits -= 8;
}
//如果下一個輸入比最大的代碼大，則增加它,
// 這樣做是為了保證與解壓時同步.
if (free_code > maxcode) {
n_bits++;
if (n_bits == MAX_LZW_BITS)
maxcode = LZW_TABLE_SIZE;
else
maxcode = MAXCODE(n_bits);
}
}
//---------------------------------------------------------------------------
// 清空hash表.
void CLZW::clear_hash ()
{
memset((void *) hash_code,0, HSIZE * sizeof(code_int));
}
//---------------------------------------------------------------------------
// 重置壓縮并發送一個清除碼.
void CLZW::clear_block ()
{
clear_hash(); // 刪除所有標識符.
free_code = ClearCode + 2;
output(ClearCode); // 壓縮.
n_bits = init_bits; // 重置代碼長度.
maxcode = MAXCODE(n_bits);
}
//---------------------------------------------------------------------------
// 初始化LZW 壓縮.
void CLZW::compress_init (FILE* file,int ibits)
{
printf("compress size %d\n",ibits);
// 初始化所有的靜態變量,給hash表分配內存.
hash_code = (code_int *) malloc(HSIZE * sizeof(code_int));
hash_prefix = (code_int *) malloc(HSIZE * sizeof(code_int));
hash_suffix = (UINT8 *) malloc(HSIZE * sizeof(UINT8));
outfile=file;
n_bits = init_bits = ibits;
maxcode = MAXCODE(n_bits);
ClearCode = ((code_int) 1 << (init_bits - 1));
EOFCode = ClearCode + 1;
free_code = ClearCode + 2;
first_byte = true;
// 初始化輸出緩沖區變量.
bytesinpkt = 0;
cur_accum = 0;
cur_bits = 0;
// 清理hash表.
clear_hash();
// 給定一個初始清理字符.
output(ClearCode);
}
//---------------------------------------------------------------------------
// 得到和壓縮一個 8-bit 字節.
void CLZW::compress_byte (int c)
{
register hash_int i;
register hash_int disp;
if (first_byte) { // 需要初始化一個等待碼.
waiting_code = c;
first_byte = false;
return;
}
i = ((hash_int) c << (MAX_LZW_BITS-8)) + waiting_code;
// i 小于兩倍的 2**MAX_LZW_BITS, 因此 小于兩倍的HSIZE.
if (i >= HSIZE)
i -= HSIZE;
if (hash_code[i] != 0) {
if (hash_prefix[i] == waiting_code && hash_suffix[i] == (UINT8) c) {
waiting_code = hash_code[i];
return;
}
if (i == 0) // 第二個hash碼 (根據 G. Knott).
disp = 1;
else
disp = HSIZE - i;
while (1) {
i -= disp;
if (i < 0) i += HSIZE;
if (hash_code[i] == 0) break;
if (hash_prefix[i] == waiting_code && hash_suffix[i] == (UINT8) c) {
waiting_code = hash_code[i];
return;
}
}
}
// 如果 hashtable[i] 是一個空的, 期望的符號不在表中.
output(waiting_code);
if (free_code < LZW_TABLE_SIZE) {
// 在hash表里增加一個符號.
hash_code[i] = free_code++;
hash_prefix[i] = waiting_code;
hash_suffix[i] = (UINT8) c;
} else
clear_block();
waiting_code = c;
}
//---------------------------------------------------------------------------
// 結尾保存.
void CLZW::compress_term ()
{
// 保存緩沖區里的代碼.
if (! first_byte)
output(waiting_code);
// 發送一個結束代碼.
output(EOFCode);
// 保存 bit-packing 緩沖區數據.
if (cur_bits > 0) {
CHAR_OUT(cur_accum & 0xFF);
}
// 保存緩沖區里的代碼.
flush_packet();
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -