LZW壓縮算法-TIFF版本

LZW壓縮算法, 三位發眀家『Lemple』『Ziv』『Welch』首字母組合而蒞.

LZW『壓縮』『解壓』算法極高速無損,算法基於『字符串表string_table』, 映射代碼Code』和『字符串string』,重要它極易實現. 易於嵌入程式, 壓縮數據.

LZW壓縮
STRING	字符/數據, 文本代表字符, 圖像代表數值
prefix	前綴字符串
suffix	後綴字符串
+	連接字符串
code	代碼,字符串代碼編號.
string_table	字典/字符串表存放–『代碼Code』和『字符串string』

首先定義『STRING字符串』結构.

typedef struct LZW_STRING_TYP {
int code;	代碼,代碼應盡量短,至多12Bit
BYTE data[64];	字符/數據
int length;	字符/數據長度
}LZW_STRING, * LZW_STRING_PTR;

CODE限制12BIT代碼, 字典至多4096個字符串.

#define LZW_MAX_STRING 4096

(2^12)

定義『LZW』結构.

typedef struct LZW_TYP
PBYTE sour;	蒞源數據
DWORD sour_position;	蒞源數據當前位置
DWORD sour_position_bit;	跟踪BIT邊界
DWORD sour_length;	蒞源數據長度
PBYTE dest;	目標數據緩存
DWORD dest_size;	目標緩存長度
DWORD dest_position;	目標數據當前位置
DWORD dest_position_bit;	跟踪BIT邊界
int string_count;	字典量
LZW_STRING string_table[LZW_MAX_STRING];	字典/字符串表
}LZW, * LZW_PTR;

初始字典/字符串表,初值有256個,編號係0~255, 字符/數據亦係0~255, 係255之後定義兩個代碼『清除碼ClearCode=256』仝『結束碼EoiCode=257』, 一共258.

#define LZW_CODE_CLEAR 0x0100	0x0100(256) 清除碼 ClearCode
#define LZW_CODE_EOI 0x0101	0x0101(257) 結束碼 EoiCode

初始字典/字符串表,

bool Init_StringTable_LZW(LZW_PTR lzw) {

for (index = 0; index < 256; ++index){

lzw->string_table[index].code = index;

lzw->string_table[index].length = 1;

lzw->string_table[index].data[0] = index;

}

code = LZW_CODE_CLEAR;

lzw->string_table[LZW_CODE_CLEAR].code = LZW_CODE_CLEAR; // 清除碼

lzw->string_table[LZW_CODE_CLEAR].length = 2;

memcpy(lzw->string_table[LZW_CODE_CLEAR].data, &code, 2);

code = LZW_CODE_EOI;

lzw->string_table[LZW_CODE_EOI].code = LZW_CODE_EOI; // 結束碼

lzw->string_table[LZW_CODE_EOI].length = 2;

memcpy(lzw->string_table[LZW_CODE_EOI].data, &code, 2);

lzw->string_count = 258;

}

將代碼CODE寫入輸出流,首個代碼係『ClearCode#256』, 以『EOICode#257』結束.

因為係壓縮數據,數據将吾以8BIT/16BIT對齊, 代碼Code以字典字符量跟踪Bit邊界.首個CODE將是9Bit代碼小於512. 字典量達係#510 之後10Bit代碼小於1024. 係#1022之後11Bit代碼小於2048. 係#2046之後12Bit代碼小於4096.代碼左移至高位,接連上個代碼.

bool Write_Code_LZW(LZW_PTR lzw, DWORD code) {

int bits = 9;

PBYTE data;

if (lzw->string_count <= LZW_MASK_9BIT)

bits = 9;

else

if (lzw->string_count <= LZW_MASK_10BIT)

bits = 10;

else

if (lzw->string_count <= LZW_MASK_11BIT)

bits = 11;

else

if (lzw->string_count <= LZW_MASK_12BIT)

bits = 12;

int byte_offset = lzw->dest_position_bit / 8;

int bis_offset = lzw->dest_position_bit % 8;

code = code << (32 – bits);

code = code >> bis_offset;

data = (PBYTE) &code;

for (int i = 0; i < 4; ++i){

*(lzw->dest + byte_offset + i) = *(lzw->dest + byte_offset + i) | data[4 – i – 1];

if (byte_offset + i >= lzw->sour_length)

break; // 數據尾,跳出

}

lzw->dest_position_bit = lzw->dest_position_bit + bits;// 蒞源數據當前位置

lzw->dest_position = lzw->dest_position_bit / 8;// 蒞源數據當前位置

return true;

}

加入字符串至字典.首個添加到字串將位於258.

bool Add_StringTable_LZW(LZW_PTR lzw, LZW_STRING_PTR string){

WORD index;

LZW_STRING_PTR str;

index = lzw->string_count;

++lzw->string_count;

str = &lzw->string_table[index];

str->code = index;// 代碼應盡量短,至多12Bit

str->length = string->length;

memcpy(str->data, string->data, string->length);

return true;

}

讀蒞源CHAR字符, 未壓縮數據

bool Read_NextChar_LZW(LZW_PTR lzw, LZW_STRING_PTR string){

BYTE data;

if (lzw->sour_position + 1 > lzw->sour_length)

return false; //

data = *(lzw->sour + lzw->sour_position);

lzw->sour_position = lzw->sour_position + 1;// 蒞源數據當前位置

string->data[0] = data;

string->length = 1;

return true;

}

壓縮算法步驟:

bool Compress_Data_LZW(PBYTE dest, DWORD* dest_length, PBYTE sour, DWORD sour_length){

LZW lzw;

LZW_STRING prefix;// 前綴字符

LZW_STRING suffix;// 後綴字符

LZW_STRING string;

WORD code;// 代碼

Init_LZW(&lzw, dest, *dest_length, sour, sour_length); // 初始LZW

Init_StringTable_LZW(&lzw); // 初始字典

Write_Code_LZW(&lzw,LZW_CODE_CLEAR); // 寫目標

Zero_String_LZW(&prefix);// 前綴字符串清零

while (Read_NextChar_LZW(&lzw, &suffix)) { // 讀下一字符,後綴字符

Copy_String_LZW(&string, &prefix); // 前綴

Cat_String_LZW(&string, &suffix);// 前綴+後綴

if ( Find_StringTable_LZW(&lzw, &string, &code) ){ // 字符串查代碼

Cat_String_LZW(&prefix, &suffix);// 後綴 = 前綴+後綴

}

else

{

Find_StringTable_LZW(&lzw, &prefix, &code);// 查找前綴

Write_Code_LZW(&lzw, code);// 將CODE代碼寫入輸出流

// 前綴+後綴

Copy_String_LZW(&string, &prefix); // 前綴

Cat_String_LZW(&string, &suffix);// 前綴+後綴

Add_StringTable_LZW(&lzw,&string);// 加入字符串至條目表

Copy_String_LZW(&prefix, &suffix); // 後綴變前綴

}

Find_StringTable_LZW(&lzw, &prefix, &code);// 查找前綴

Write_Code_LZW(&lzw, code);// 將CODE代碼寫入輸出流

Write_Code_LZW(&lzw, LZW_CODE_EOI);// 將CODE代碼寫入輸出流

*dest_length = lzw.dest_position; // 輸出压缩長度

if (lzw.dest_position_bit / 8 != 0)

++(*dest_length);

return true;

}

讀壓縮CODE代碼,必須跟踪Bit邊界. 代碼右移至低位,提取代碼. 代碼Code以字典字符量跟踪Bit邊界.首個CODE將是9Bit代碼小於512. 字典量達係#510 之後10Bit代碼小於1024. 係#1022之後11Bit代碼小於2048. 係#2046之後12Bit代碼小於4096.

WORD Read_NextCode_LZW(LZW_PTR lzw){

DWORD data;

int bits = 9;

if (lzw->string_count <= LZW_MASK_9BIT) // 小於512

bits = 9;

else

if (lzw->string_count <= LZW_MASK_10BIT) // 小於1024

bits = 10;

else

if (lzw->string_count <= LZW_MASK_11BIT) // 小於2048

bits = 11;

else

if (lzw->string_count <= LZW_MASK_12BIT) // 小於4096

bits = 12;

int byte_offset = lzw->sour_position_bit / 8;

int bis_offset = lzw->sour_position_bit % 8;

data = (*(lzw->sour + byte_offset)) << (24+bis_offset) |

(*(lzw->sour + byte_offset + 1)) << (16+bis_offset) |

(*(lzw->sour + byte_offset + 2)) << ( 8+bis_offset) ;

data = data >> (32 – bits);

lzw->sour_position_bit = lzw->sour_position_bit + bits;// 蒞源數據當前位置

lzw->sour_position = lzw->sour_position_bit / 8;// 蒞源數據當前位置

return (WORD)data;

}

壓縮算法步驟:

bool UnCompress_Data_LZW(PBYTE dest, DWORD* dest_length, PBYTE sour, DWORD sour_length){

LZW lzw;

WORD code = 0;

WORD OldCode = 0;

LZW_STRING string;

LZW_STRING OldString;

if ( dest == NULL || dest_length == NULL || sour == NULL || sour_length == 0)

return false;

Init_LZW(&lzw, dest, *dest_length, sour, sour_length); // 初始LZW

while (TRUE)

{

code = Read_NextCode_LZW(&lzw);// 讀蒞源數據

if (code == LZW_CODE_EOI)// 結束碼

break;// 數據結束

if (code == LZW_CODE_CLEAR) { // 清除碼

Init_StringTable_LZW(&lzw);// 初始字典

code = Read_NextCode_LZW(&lzw);// 讀蒞源數據

if (code == LZW_CODE_EOI)// 結束碼

break;// 數據結束

Find_StringTable_LZW(&lzw, code, &string);

Write_String_LZW(&lzw, &string);// 將字符串寫入輸出流

OldCode = code;

}

else

{

// 代碼稳查字符串

if (Find_StringTable_LZW(&lzw, code, &string)) {

Write_String_LZW(&lzw, &string); // 將字符串寫入輸出流

Find_StringTable_LZW(&lzw, OldCode, &OldString); // 代碼稳查字符串

Cat_String_LZW(&OldString, &string, 1); // 連接字符串

Add_StringTable_LZW(&lzw, &OldString); // 加入字符串至條目表

OldCode = code;

}

else{ // 代碼稳查字符串

Find_StringTable_LZW(&lzw, OldCode, &OldString);

Cat_String_LZW(&OldString, &OldString, 1); // 連接字符串

Write_String_LZW(&lzw, &OldString); // 將字符串寫入輸出流

Add_StringTable_LZW(&lzw, &OldString); // 加入字符串至條目表

OldCode = code;

}

*dest_length = lzw.dest_position; // 輸出压缩長度

return true;

}

分享此文：

發佈留言 取消回覆

發佈留言取消回覆