標籤: 電腦

LZW壓縮

STRING

字符/數據, 文本代表字符, 圖像代表數值

prefix

前綴字符串

suffix

後綴字符串

+

連接字符串

code

代碼,字符串代碼編號.

string_table

字典/字符串表存放–『代碼Code』和『字符串string』

typedef struct LZW_STRING_TYP {

        int code;

代碼,代碼應盡量短,至多12Bit

        BYTE data[64];

字符/數據 

        int  length;

字符/數據長度

}LZW_STRING, * LZW_STRING_PTR;

#define   LZW_MAX_STRING      4096  

(2^12)

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;

#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;

}

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;

}

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;

}

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;

}

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;

}