（建设中。。。）
#include <stdlib.h> #include <stdio.h> #include "bitio.h" #define MAX_CODE 65535 struct { int suffix; int parent, firstchild, nextsibling; } dictionary[MAX_CODE+1]; int next_code; int d_stack[MAX_CODE]; // stack for decoding a phrase #define input(f) ((int)BitsInput( f, 16)) #define output(f, x) BitsOutput( f, (unsigned long)(x), 16) int DecodeString( int start, int code); void InitDictionary( void); void PrintDictionary( void){ int n; int count; for( n=256; n<next_code; n++){ count = DecodeString( 0, n); printf( "M->", n); while( 0<count--) printf("%c", (char)(d_stack[count])); printf( "\n"); } } int DecodeString( int start, int code){ int count; count = start; while( 0<=code){ d_stack[ count] = dictionary[code].suffix; code = dictionary[code].parent; count ++; } return count; } void InitDictionary( void){ int i; for( i=0; i<256; i++){ dictionary[i].suffix = i; dictionary[i].parent = -1; dictionary[i].firstchild = -1; dictionary[i].nextsibling = i+1; } dictionary[255].nextsibling = -1; next_code = 256; } /* * Input: string represented by string_code in dictionary, * Output: the index of character+string in the dictionary * index = -1 if not found */ int InDictionary( int character, int string_code){ int sibling; if( 0>string_code) return character; sibling = dictionary[string_code].firstchild; while( -1<sibling){ if( character == dictionary[sibling].suffix) return sibling; sibling = dictionary[sibling].nextsibling; } return -1; } void AddToDictionary( int character, int string_code){ int firstsibling, nextsibling; if( 0>string_code) return; dictionary[next_code].suffix = character; dictionary[next_code].parent = string_code; dictionary[next_code].nextsibling = -1; dictionary[next_code].firstchild = -1; firstsibling = dictionary[string_code].firstchild; if( -1<firstsibling){ // the parent has child nextsibling = firstsibling; while( -1<dictionary[nextsibling].nextsibling ) nextsibling = dictionary[nextsibling].nextsibling; dictionary[nextsibling].nextsibling = next_code; }else{// no child before, modify it to be the first dictionary[string_code].firstchild = next_code; } next_code ++; } void LZWEncode( FILE *fp, BITFILE *bf){ int character; int string_code; int index; unsigned long file_length; fseek( fp, 0, SEEK_END); //把文件指针移到文件尾 file_length = ftell( fp); //得到文件字节数 fseek( fp, 0, SEEK_SET); //再移回文件头 BitsOutput( bf, file_length, 4*8); InitDictionary(); string_code = -1; while( EOF!=(character=fgetc( fp))){ index = InDictionary( character, string_code); if( 0<=index){ // string+character in dictionary string_code = index; }else{ // string+character not in dictionary output( bf, string_code); if( MAX_CODE > next_code){ // free space in dictionary // add string+character to dictionary AddToDictionary( character, string_code); } string_code = character; } } output( bf, string_code); } void LZWDecode( BITFILE *bf, FILE *fp){ int character; int new_code, last_code; int phrase_length; unsigned long file_length; file_length = BitsInput( bf, 4*8); if( -1 == file_length) file_length = 0; InitDictionary(); last_code = -1; while( 0<file_length){ new_code = input( bf); if( new_code >= next_code){ // this is the case CSCSC( not in dict) d_stack[0] = character; phrase_length = DecodeString( 1, last_code); }else{ phrase_length = DecodeString( 0, new_code); } character = d_stack[phrase_length-1]; while( 0<phrase_length){ phrase_length --; fputc( d_stack[ phrase_length], fp); file_length--; } if( MAX_CODE>next_code){ // add the new phrase to dictionary AddToDictionary( character, last_code); } last_code = new_code; } } int main( int argc, char **argv){ FILE *fp; BITFILE *bf; if( 4>argc){ fprintf( stdout, "usage: \n%s <o> <ifile> <ofile>\n", argv[0]); fprintf( stdout, "\t<o>: E or D reffers encode or decode\n"); fprintf( stdout, "\t<ifile>: input file name\n"); fprintf( stdout, "\t<ofile>: output file name\n"); system("pause"); return -1; } if( 'E' == argv[1][0]){ // do encoding fp = fopen( argv[2], "rb"); bf = OpenBitFileOutput( argv[3]); if( NULL!=fp && NULL!=bf){ LZWEncode( fp, bf); fclose( fp); CloseBitFileOutput( bf); fprintf( stdout, "encoding done\n"); } }else if( 'D' == argv[1][0]){ // do decoding bf = OpenBitFileInput( argv[2]); fp = fopen( argv[3], "wb"); if( NULL!=fp && NULL!=bf){ LZWDecode( bf, fp); fclose( fp); CloseBitFileInput( bf); fprintf( stdout, "decoding done\n"); } }else{ // otherwise fprintf( stderr, "not supported operation\n"); } system("pause"); return 0; }