00001
00012 #include "dkcLZW.h"
00013
00014
00016 static DKC_INLINE void init_lzw(DKC_LZW *p){
00017
00018 memset(&(p->pool),0,sizeof((p->pool)));
00019 p->node_count = 256;
00020
00021 dkcmFORCE_NOT_ASSERT(DKUTIL_FAILED(dkcBitMemoryStreamSeekByte(p->mbs,0,edkcBitMemoryStreamSeekSet)));
00022 }
00023
00024
00025
00026 static DKC_INLINE void init_trie(DKC_LZW *p){
00027
00028 int i;
00029 init_lzw(p);
00030 for( i = 0; i < 256; i++ ){
00031 p->pool.trie[i].code = i;
00032 p->pool.trie[i].p = dkcdLZW_NIL_OFFSET;
00033 }
00034
00035 for(i=256;i<dkcdLZW_NUM;i++){
00036 p->pool.trie[i].code = 0;
00037 p->pool.trie[i].p = dkcdLZW_NIL_OFFSET;
00038 }
00039 }
00040
00041
00042
00043
00044 static void init_tst(DKC_LZW *p)
00045 {
00046
00047 int i;
00048
00049
00050 p->sentinel = &(p->pool.tst[dkcdLZW_NUM]);
00051
00052 for( i = 0; i < 256; i++ )
00053 {
00054 p->pool.tst[i].code = i;
00055 p->pool.tst[i].parent = p->pool.tst[i].left = p->pool.tst[i].middle = p->pool.tst[i].right = dkcdLZW_NIL(p);
00056 }
00057 for( i = 256; i < dkcdLZW_NUM; i++ )
00058 {
00059 p->pool.tst[i].parent = p->pool.tst[i].left = p->pool.tst[i].middle = p->pool.tst[i].right = dkcdLZW_NIL(p);
00060 }
00061
00062
00063
00064
00065 }
00066 static DKC_INLINE DKC_LZW_NODE *calc_tst_node_ptr(DKC_LZW *ptr,int node)
00067 {
00068 dkcmASSERT(node < dkcdLZW_NUM);
00069 return &(ptr->pool.tst[node]);
00070 }
00071 static DKC_INLINE int calc_tst_node_offset(DKC_LZW *ptr,DKC_LZW_NODE *pt)
00072 {
00073 int r;
00074 dkcmASSERT(pt >= ptr->pool.tst);
00075 r = (int)(DKC_LZW_NODE *)(pt - (ptr->pool.tst));
00076 dkcmASSERT(r >= 0);
00077 return r;
00078 }
00084
00085
00086 static DKC_INLINE DKC_LZW_NODE* find_child_node(DKC_LZW *ptr,int node,int c)
00087 {
00088 DKC_LZW_NODE* p = ptr->pool.tst[node].middle;
00089 while( p != dkcdLZW_NIL(ptr) ){
00090 if( p->code == c ) break;
00091 if( p->code > c ){
00092 p = p->left;
00093 } else {
00094 p = p->right;
00095 }
00096 }
00097 return p;
00098 }
00099
00100 static int find_child_node_number(DKC_LZW *ptr,int node,int c)
00101 {
00102 DKC_LZW_NODE *t = find_child_node(ptr,node,c);
00103 dkcmNOT_ASSERT(t < ptr->pool.tst);
00104 return (int)(t - (&ptr->pool.tst[0]));
00105 }
00106
00107
00113
00114 static DKC_LZW_NODE * add_node(DKC_LZW *ptr, int node, int c )
00115 {
00116 DKC_LZW_NODE* p = dkcdLZW_NIL(ptr);
00117 DKC_LZW_NODE *tst = ptr->pool.tst;
00118 if( ptr->node_count < dkcdLZW_NUM ){
00119 DKC_LZW_NODE* *place = &(tst[node].middle);
00120 p = &tst[ptr->node_count];
00121 ptr->node_count++;
00122 p->code = c;
00123 p->parent = &tst[node];
00124 while( *place != dkcdLZW_NIL(ptr) ){
00125 DKC_LZW_NODE* q = *place;
00126 if( q->code > c ){
00127 place = &(q->left);
00128 } else {
00129 place = &(q->right);
00130 }
00131 }
00132 *place = p;
00133 }
00134 return p;
00135 }
00136
00137
00138 static DKC_INLINE int output_tst_code( DKC_LZW *ptr,int node,
00139 DKC_MEMORYSTREAM_ADAPTER *pa ,
00140 size_t *output_size,uint8 *buffer)
00141 {
00142 int i;
00143 DKC_LZW_NODE *tst = ptr->pool.tst,*p;
00144 p = &(tst[node]);
00145 for( i = 0; p != dkcdLZW_NIL(ptr); p = p->parent
00146 )
00147 {
00148 dkcmASSERT(p->code >= 0 && p->code <= UCHAR_MAX);
00149 buffer[i++] = (uint8)p->code;
00150 }
00151 *output_size = i;
00152
00153 while( --i >= 0 ){
00154 int r = dkcMemoryStreamPut8(pa,(uint8)buffer[i]);
00155 if(DKUTIL_FAILED(r))
00156 return r;
00157 }
00158 return edk_SUCCEEDED;
00159 }
00160 typedef int (*dkctLZW_ENCODE)(DKC_LZW *ptr,BYTE *dest,size_t dsize,const BYTE *src,size_t ssize,size_t *pcount);
00161
00163 static DKC_INLINE int encode_tst(DKC_LZW *ptr,BYTE *dest,size_t dsize,const BYTE *src,size_t ssize,size_t *pcount)
00164 {
00165
00166
00167 int p = 0;
00168 int c = 0,q = 0;
00169
00170
00171 DKC_MEMORYSTREAM_ADAPTER asrc;
00172
00173 dkcMemoryStreamAdapterInit(&asrc,(BYTE*)src,ssize);
00174
00175
00176
00177
00178 if( DKUTIL_FAILED(dkcMemoryStreamGet8(&asrc,(BYTE *)&p)) )
00179 return edk_FAILED;
00180
00181
00182 for(;;){
00183
00184
00185
00186 if( DKUTIL_FAILED(dkcMemoryStreamGet8(&asrc,(BYTE *)&c)) )
00187 {
00188 if(dkcMemoryStreamIsEnd(&asrc)){
00189
00190 dkcBitMemoryStreamWrite(ptr->mbs,&p,dkcdLZW_CODE_SIZE);
00191 break;
00192 }else{
00193
00194 return edk_LogicError;
00195 }
00196 }
00197 q = find_child_node_number(ptr, p, c );
00198 if( q == dkcdLZW_NIL_OFFSET ){
00199
00200 dkcBitMemoryStreamWrite(ptr->mbs,&p,dkcdLZW_CODE_SIZE);
00201 if(dsize < dkcBitMemoryStreamTellByte(ptr->mbs))
00202 {
00203 return edk_BufferOverFlow;
00204 }
00205
00206
00207
00208 add_node(ptr, p, c );
00209
00210 p = c;
00211 } else {
00212 p = q;
00213 }
00214 }
00215 dkcBitMemoryStreamWriteLast(ptr->mbs);
00216
00217 *pcount = dkcBitMemoryStreamTellByte(ptr->mbs);
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227 return dkcBitMemoryStreamWriteToMemory(ptr->mbs,dest,dsize,edkcStreamBufferToNowOffset);
00228
00229 }
00230
00231 typedef int (*dkctLZW_DECODE)(DKC_LZW *ptr, BYTE *dest,size_t dsize,
00232 DKC_BIT_MEMORYSTREAM *mbs,int origin_size);
00233
00234 static DKC_INLINE int decode_tst(DKC_LZW *ptr, BYTE *dest,size_t dsize,
00235
00236 DKC_BIT_MEMORYSTREAM *mbs,int origin_size)
00237 {
00238
00239 int q = 0;
00240 int r;
00241 size_t len = 1;
00242
00243 int size = origin_size - 1;
00244
00245 DKC_MEMORYSTREAM_ADAPTER aw;
00246
00247 uint8 *buffer = NULL;
00248
00249 DKC_LZW_NODE *tst = ptr->pool.tst;
00250
00251 if( size < 0 )
00252 return edk_FAILED;
00253 buffer = dkcAllocateFast(dkcdLZW_NUM + 1);
00254 if(NULL==buffer)
00255 return edk_OutOfMemory;
00256
00257 dkcBitMemoryStreamRead(mbs,(uint32 *)&q,dkcdLZW_CODE_SIZE);
00258 buffer[0] = (uint8)tst[q].code;
00259
00260 dkcMemoryStreamAdapterInit(&aw,dest,dsize);
00261
00262 dkcMemoryStreamPut8(&aw,(uint8)tst[q].code);
00263
00264
00265
00266 while( size > 0 ){
00267 uint32 c;
00268
00269 r = dkcBitMemoryStreamRead(mbs ,(uint32 *)&c,dkcdLZW_CODE_SIZE);
00270 if(DKUTIL_FAILED(r))
00271 {
00272 goto Error;
00273 }
00274
00275
00276 if( (size_t)c < ptr->node_count ){
00277
00278
00279 output_tst_code( ptr,c, &aw,&len,buffer );
00280
00281 add_node( ptr,q, buffer[len - 1] );
00282 } else {
00283
00284
00285
00286 add_node( ptr,q, buffer[len - 1] );
00287
00288 output_tst_code( ptr,c, &aw,&len,buffer );
00289 }
00290 size -= (int)len;
00291 q = c;
00292 }
00293 r = edk_SUCCEEDED;
00294 Error:
00295 dkcFree(&buffer);
00296
00297
00298 return r;
00299 }
00300
00301
00302
00303
00304
00305
00306 static void free_hash(DKC_LZW *p){
00307 dkcFree((void **)&(p->hash_stack));
00308 dkcFree((void **)&(p->hash_table));
00309 }
00310
00311 static int alloc_hash(DKC_LZW *p){
00312 void *t = NULL;
00313
00314 size_t table_size = sizeof(dkcdLZW_DATA) * dkcdLZW_HASH_TABLE_SIZE;
00315 size_t stack_size = sizeof(dkcdLZW_DATA) * dkcdLZW_NUM;
00316
00317
00318 if(NULL==p->hash_table){
00319 t = dkcAllocate(table_size);
00320 p->hash_table = t;
00321 if(NULL==t) goto Error;
00322
00323 }
00324 if(NULL==p->hash_stack){
00325 t = dkcAllocate(stack_size);
00326 p->hash_stack = t;
00327 if(NULL==t) goto Error;
00328 }
00329
00330 return edk_SUCCEEDED;
00331 Error:
00332
00333
00334 free_hash(p);
00335 return edk_OutOfMemory;
00336 }
00337
00338 static int init_hash(DKC_LZW *p)
00339 {
00340 int i;
00341
00342 init_trie(p);
00343
00344
00345 i = alloc_hash(p);
00346 if(DKUTIL_FAILED(i)){
00347 return i;
00348 }
00349
00350
00351 for(i=0;i<dkcdLZW_HASH_TABLE_SIZE;i++){
00352 p->hash_table[i] = dkcdLZW_NIL_OFFSET;
00353 p->hash_stack[i] = dkcdLZW_NIL_OFFSET;
00354 }
00355
00356
00357
00358
00359
00360
00361
00362
00363 return edk_SUCCEEDED;
00364 }
00365
00366
00367 static DKC_INLINE DKC_LZW_NODE* add_hash(DKC_LZW *p, int node, int c )
00368 {
00369 int index;
00370 int i;
00371 if(p->node_count < dkcdLZW_NUM){
00372 i = p->node_count++;
00373 dkcmNOT_ASSERT(p->hash_table == NULL);
00374
00375 p->pool.trie[i].code = c;
00376 p->pool.trie[i].p = node;
00377
00378 index = dkcmLZW_HASH_FUNC(node,c);
00379
00380 p->hash_stack[i] = p->hash_table[index];
00381 p->hash_table[index] = i;
00382
00383
00384
00385 }else{
00386 i = 0;
00387 }
00388
00389 return NULL;
00390 }
00391
00392
00393 static DKC_INLINE dkcdLZW_DATA find_hash_node(DKC_LZW *p,int node, int c )
00394 {
00395 int index = dkcmLZW_HASH_FUNC( node, c );
00396 int n = p->hash_table[index];
00397
00398
00399
00400
00401 for( ; n != dkcdLZW_NIL_OFFSET;
00402 n = p->hash_stack[ n ] )
00403 {
00404 if( p->pool.trie[n].p == node && p->pool.trie[n].code == c ) break;
00405 }
00406
00407 return n;
00408 }
00409
00410
00411 static DKC_INLINE int find_hash_node_number(DKC_LZW *ptr,int node,int c)
00412 {
00413 dkcdLZW_DATA t = find_hash_node(ptr,node,c);
00414
00415
00416 return t;
00417 }
00418
00419
00420 static DKC_INLINE int encode_hash(DKC_LZW *ptr,BYTE *dest,size_t dsize,const BYTE *src,size_t ssize,size_t *pcount)
00421 {
00422
00423
00424 int p = 0;
00425 int c = 0,q = 0;
00426 int r = edk_FAILED;
00427
00428
00429 DKC_MEMORYSTREAM_ADAPTER asrc;
00430
00431 dkcMemoryStreamAdapterInit(&asrc,(BYTE*)src,ssize);
00432
00433 if( DKUTIL_FAILED(dkcMemoryStreamGet8(&asrc,(BYTE *)&p)) )
00434 return edk_FAILED;
00435
00436 for(;;){
00437
00438
00439
00440 if( DKUTIL_FAILED(dkcMemoryStreamGet8(&asrc,(BYTE *)&c)) )
00441 {
00442 if(dkcMemoryStreamIsEnd(&asrc)){
00443
00444 dkcBitMemoryStreamWrite(ptr->mbs,&p,dkcdLZW_CODE_SIZE);
00445 r = edk_SUCCEEDED;
00446 break;
00447 }else{
00448 return edk_LogicError;
00449 }
00450 }
00451 q = find_hash_node_number(ptr, p, c );
00452 {
00453 #ifdef DEBUG
00454 size_t ts = dkcBitMemoryStreamTellByte(ptr->mbs);
00455 dkcmNOT_ASSERT(2164==ts);
00456 #else
00457 dkcBitMemoryStreamTellByte(ptr->mbs);
00458 #endif
00459 }
00460 if( q == dkcdLZW_NIL_OFFSET ){
00461
00462 dkcBitMemoryStreamWrite(ptr->mbs,&p,dkcdLZW_CODE_SIZE);
00463 if(dsize < dkcBitMemoryStreamTellByte(ptr->mbs))
00464 {
00465 return edk_BufferOverFlow;
00466 }
00467
00468 add_hash(ptr, p, c );
00469
00470 p = c;
00471 } else {
00472 p = q;
00473 }
00474 }
00475 dkcBitMemoryStreamWriteLast(ptr->mbs);
00476
00477 *pcount = dkcBitMemoryStreamTellByte(ptr->mbs);
00478
00479
00480
00481 r = dkcBitMemoryStreamWriteToMemory(ptr->mbs,dest,dsize,edkcStreamBufferToNowOffset);
00482
00483 return r;
00484 }
00485
00486 static DKC_INLINE int output_hash_code(DKC_LZW *ptr,int node,
00487 DKC_MEMORYSTREAM_ADAPTER *pa ,
00488 size_t *output_size,uint8 *buffer)
00489 {
00490 int i = 0, a = node;
00491
00492 for(; a != dkcdLZW_NIL_OFFSET; a = ptr->pool.trie[a].p ){
00493 dkcmASSERT(ptr->pool.trie[a].code >= 0 && ptr->pool.trie[a].code <= UCHAR_MAX);
00494 buffer[i++] = (uint8)ptr->pool.trie[a].code;
00495 }
00496
00497 *output_size = i;
00498
00499 while( --i >= 0 ){
00500 int r = dkcMemoryStreamPut8(pa,(uint8)buffer[i]);
00501 if(DKUTIL_FAILED(r))
00502 return r;
00503 }
00504 return edk_SUCCEEDED;
00505
00506 }
00507
00508 static DKC_INLINE int decode_hash(DKC_LZW *ptr, BYTE *dest,size_t dsize,
00509
00510 DKC_BIT_MEMORYSTREAM *mbs,int origin_size)
00511 {
00512
00513 int q = 0;
00514 int r;
00515 size_t len = 1;
00516
00517 int size = origin_size - 1;
00518
00519 DKC_MEMORYSTREAM_ADAPTER aw;
00520
00521 uint8 *buffer = NULL;
00522
00523 DKC_LZW_TRIE *trie = ptr->pool.trie;
00524
00525 if( size < 0 )
00526 return edk_FAILED;
00527 buffer = dkcAllocateFast(dkcdLZW_NUM + 1);
00528 if(NULL==buffer)
00529 return edk_OutOfMemory;
00530
00531 dkcBitMemoryStreamRead(mbs,(uint32 *)&q,dkcdLZW_CODE_SIZE);
00532 buffer[0] = (uint8)trie[q].code;
00533
00534 dkcMemoryStreamAdapterInit(&aw,dest,dsize);
00535
00536 dkcMemoryStreamPut8(&aw,(uint8)trie[q].code);
00537
00538
00539
00540 while( size > 0 ){
00541 uint32 c;
00542
00543 r = dkcBitMemoryStreamRead(mbs ,(uint32 *)&c,dkcdLZW_CODE_SIZE);
00544 if(DKUTIL_FAILED(r))
00545 {
00546 goto Error;
00547 }
00548
00549
00550 if( (size_t)c < ptr->node_count ){
00551
00552 output_hash_code( ptr,c, &aw,&len,buffer );
00553
00554 add_hash( ptr,q, buffer[len - 1] );
00555 } else {
00556
00557
00558 add_hash( ptr,q, buffer[len - 1] );
00559
00560 output_hash_code( ptr,c, &aw,&len,buffer );
00561 }
00562 size -= (int)len;
00563 q = c;
00564 }
00565 r = edk_SUCCEEDED;
00566 Error:
00567 dkcFree(&buffer);
00568 dkcmNOT_ASSERT(dkcMemoryStreamTell(&aw) != (size_t)origin_size);
00569
00570 return r;
00571 }
00572
00573
00574
00575
00576 DKC_INLINE DKC_LZW *WINAPI dkcAllocLZW(size_t output_block_size){
00577 DKC_LZW *p = dkcAllocate(sizeof(DKC_LZW));
00578
00579 p->mbs = dkcAllocBitMemoryStream(output_block_size);
00580 if(NULL==p->mbs){
00581 dkcFree(&p);
00582 return NULL;
00583 }
00584
00585
00586 return p;
00587 }
00588
00589 DKC_INLINE int WINAPI dkcFreeLZW(DKC_LZW **p){
00590 if(NULL==p || NULL==*p) return edk_FAILED;
00591 free_hash(*p);
00592 dkcFreeBitMemoryStream(&((*p)->mbs));
00593 return dkcFree(p);
00594
00595 }
00596
00597
00598 DKC_INLINE int WINAPI dkcLZWDecode(DKC_LZW *ptr,DKC_LZW_HEADER *ph,
00599 BYTE *dest,size_t dsize,const BYTE *src,size_t ssize,ULONG sig)
00600 {
00601
00602 DKC_BIT_MEMORYSTREAM *mbs = ptr->mbs;
00603 {
00604 int r;
00605
00606
00607
00608
00609
00610 if(ph->mSignature != sig){
00611 return edk_SignatureException;
00612 }
00613 init_lzw(ptr);
00614
00615 r = dkcBitMemoryStreamLoadFromMemory(mbs,src,ssize);
00616 if(DKUTIL_FAILED(r)) return r;
00617 }
00618 {
00619 int r;
00620 uint32 t = ph->option;
00621 dkctLZW_DECODE func = decode_tst;
00622 for(;;){
00623
00624 if((t & edkcLZW_Default) || (t &edkcLZW_TST)){
00625 init_tst(ptr);
00626 func = decode_tst;
00627 }
00628 if(t & edkcLZW_HASH){
00629 int tr = init_hash(ptr);
00630 if(DKUTIL_FAILED(tr)) return tr;
00631 func = decode_hash;
00632 }
00633 break;
00634 }
00635 r = func(ptr,dest,dsize,mbs,ph->mOriginSize);
00636
00637
00638 return r;
00639 }
00640 }
00641
00642
00643 DKC_INLINE int WINAPI dkcLZWEncode(DKC_LZW *ptr,DKC_LZW_HEADER *ph,
00644 BYTE *dest,size_t dsize,const BYTE *src,size_t ssize,
00645 size_t CloseProcessSize,ULONG sig,ULONG option)
00646 {
00648 uint32 flag = 0;
00649 dkctLZW_ENCODE func = NULL;
00650 int tr;
00651
00652 ph->mOriginSize = ssize;
00653 ph->mSignature = sig;
00654 ph->option = option;
00655
00656
00657
00658 switch(option){
00659 case edkcLZW_Default:
00660 flag = edkcLZW_Variableness | edkcLZW_HASH;
00661 break;
00662 case edkcLZW_TST:
00663 flag = edkcLZW_TST;
00664 break;
00665 case edkcLZW_HASH:
00666 default:
00667 flag |= edkcLZW_HASH;
00668 }
00669
00670 init_lzw(ptr);
00671 if(flag & edkcLZW_HASH){
00672
00673 tr = init_hash(ptr);
00674
00675 if(DKUTIL_FAILED(tr)) return tr;
00676 func = encode_hash;
00677
00678 }else if(flag & edkcLZW_TST){
00679 init_tst(ptr);
00680 func = encode_tst;
00681 }
00682
00683
00684 {
00685 int r;
00686 r = func(ptr,dest,dsize,src,ssize,&(ph->mCompressedSize));
00687
00688
00689
00690 return r;
00691 }
00692
00693 }