メインページ | アルファベット順一覧 | 構成 | ファイル一覧 | 構成メンバ | ファイルメンバ | 関連ページ

dkcLZW.c

LZW圧縮アルゴリズム [詳細]

#include "dkcLZW.h"

dkcLZW.cのインクルード依存関係図

ソースコードを見る。

型定義

typedef int(* dkctLZW_ENCODE )(DKC_LZW *ptr, BYTE *dest, size_t dsize, const BYTE *src, size_t ssize, size_t *pcount)
typedef int(* dkctLZW_DECODE )(DKC_LZW *ptr, BYTE *dest, size_t dsize, DKC_BIT_MEMORYSTREAM *mbs, int origin_size)

関数

static DKC_INLINE void init_lzw (DKC_LZW *p)
 DKC_LZW構造体を初期化する
static DKC_INLINE void init_trie (DKC_LZW *p)
static void init_tst (DKC_LZW *p)
static DKC_INLINE DKC_LZW_NODEcalc_tst_node_ptr (DKC_LZW *ptr, int node)
static DKC_INLINE int calc_tst_node_offset (DKC_LZW *ptr, DKC_LZW_NODE *pt)
static DKC_INLINE DKC_LZW_NODEfind_child_node (DKC_LZW *ptr, int node, int c)
 子供ノードを見つける
static int find_child_node_number (DKC_LZW *ptr, int node, int c)
static DKC_LZW_NODEadd_node (DKC_LZW *ptr, int node, int c)
 ノードを追加する
static DKC_INLINE int output_tst_code (DKC_LZW *ptr, int node, DKC_MEMORYSTREAM_ADAPTER *pa, size_t *output_size, uint8 *buffer)
static DKC_INLINE int encode_tst (DKC_LZW *ptr, BYTE *dest, size_t dsize, const BYTE *src, size_t ssize, size_t *pcount)
 endian関係どうなっているのやら 。゚(゚´Д`゚)゚。
static DKC_INLINE int decode_tst (DKC_LZW *ptr, BYTE *dest, size_t dsize, DKC_BIT_MEMORYSTREAM *mbs, int origin_size)
static void free_hash (DKC_LZW *p)
static int alloc_hash (DKC_LZW *p)
static int init_hash (DKC_LZW *p)
static DKC_INLINE DKC_LZW_NODEadd_hash (DKC_LZW *p, int node, int c)
static DKC_INLINE dkcdLZW_DATA find_hash_node (DKC_LZW *p, int node, int c)
static DKC_INLINE int find_hash_node_number (DKC_LZW *ptr, int node, int c)
static DKC_INLINE int encode_hash (DKC_LZW *ptr, BYTE *dest, size_t dsize, const BYTE *src, size_t ssize, size_t *pcount)
static DKC_INLINE int output_hash_code (DKC_LZW *ptr, int node, DKC_MEMORYSTREAM_ADAPTER *pa, size_t *output_size, uint8 *buffer)
static DKC_INLINE int decode_hash (DKC_LZW *ptr, BYTE *dest, size_t dsize, DKC_BIT_MEMORYSTREAM *mbs, int origin_size)
DKC_INLINE DKC_LZW *WINAPI dkcAllocLZW (size_t output_block_size)
DKC_INLINE int WINAPI dkcFreeLZW (DKC_LZW **p)
DKC_INLINE int WINAPI dkcLZWDecode (DKC_LZW *ptr, DKC_LZW_HEADER *ph, BYTE *dest, size_t dsize, const BYTE *src, size_t ssize, ULONG sig)
DKC_INLINE int WINAPI dkcLZWEncode (DKC_LZW *ptr, DKC_LZW_HEADER *ph, BYTE *dest, size_t dsize, const BYTE *src, size_t ssize, size_t CloseProcessSize, ULONG sig, ULONG option)


説明

LZW圧縮アルゴリズム

作者:
d金魚 2005/07/16:ハッシュ法でのデコードがバグっている。 2005/08/11:ハッシュ法のエンコードがバグっていたのでそこを直したら直ったみたい。 2005/08/13:ハッシュ法のデコードがやっぱりバグっている。 2005/08/14:祝!完成 memory streamの関数とマクロの二十定義だったよ〜直ってよかった〜(泣)

dkcLZW.c で定義されています。


型定義

typedef int(* dkctLZW_DECODE)(DKC_LZW *ptr, BYTE *dest, size_t dsize, DKC_BIT_MEMORYSTREAM *mbs, int origin_size)
 

dkcLZW.c231 行で定義されています。

typedef int(* dkctLZW_ENCODE)(DKC_LZW *ptr, BYTE *dest, size_t dsize, const BYTE *src, size_t ssize, size_t *pcount)
 

dkcLZW.c160 行で定義されています。


関数

static DKC_INLINE DKC_LZW_NODE* add_hash DKC_LZW p,
int  node,
int  c
[static]
 

dkcLZW.c367 行で定義されています。

参照先 dkcdLZW_NUM, dkcmLZW_HASH_FUNC, dkcmNOT_ASSERT, dkc_LZW::hash_stack, dkc_LZW::hash_table, index(), dkc_LZW::node_count, NULL, と dkc_LZW::pool.

参照元 decode_hash(), と encode_hash().

00368 {//#error ここかな。add_nodeと一緒に^^add_hash内デadd_nodeを呼ぶ そんな感じで
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     //p->hash_table[index] = c;
00383     //End:
00384         //return it;
00385     }else{
00386         i = 0;
00387     }
00388 
00389     return NULL;
00390 }

static DKC_LZW_NODE* add_node DKC_LZW ptr,
int  node,
int  c
[static]
 

ノードを追加する

引数:
node[in] ノード番号
c[in] キー
戻り値:
dkcdLZW_NILだと追加できない…。゚(゚´Д`゚)゚。

dkcLZW.c114 行で定義されています。

参照先 dkc_LZW_Node::code, dkcdLZW_NIL, dkcdLZW_NUM, dkc_LZW_Node::left, dkc_LZW_Node::middle, dkc_LZW::node_count, dkc_LZW_Node::parent, dkc_LZW::pool, と dkc_LZW_Node::right.

参照元 decode_tst(), と encode_tst().

00115 {
00116   DKC_LZW_NODE*  p = dkcdLZW_NIL(ptr);
00117     DKC_LZW_NODE *tst = ptr->pool.tst;
00118   if( ptr->node_count < /*N*/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 }

static int alloc_hash DKC_LZW p  )  [static]
 

dkcLZW.c311 行で定義されています。

参照先 dkcAllocate(), dkcdLZW_DATA, dkcdLZW_HASH_TABLE_SIZE, dkcdLZW_NUM, free_hash(), dkc_LZW::hash_stack, dkc_LZW::hash_table, と NULL.

参照元 init_hash().

00311                                  {
00312     void *t = NULL;
00313     //dkcmNOT_ASSERT(p->hash_stack != NULL && p->hash_table != NULL);
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     //dkcFree((void **)&(p->hash_table));
00333     //dkcFree((void **)&(p->hash_stack));
00334     free_hash(p);
00335     return edk_OutOfMemory;
00336 }

static DKC_INLINE int calc_tst_node_offset DKC_LZW ptr,
DKC_LZW_NODE pt
[static]
 

dkcLZW.c71 行で定義されています。

参照先 dkcmASSERT, と dkc_LZW::pool.

00072 {
00073     int r;
00074     dkcmASSERT(pt >= ptr->pool.tst);
00075     r = (int)(DKC_LZW_NODE *)(pt - (ptr->pool.tst));// / (int)sizeof(ptr->pool.tst[0]);
00076     dkcmASSERT(r >= 0);
00077     return r;
00078 }

static DKC_INLINE DKC_LZW_NODE* calc_tst_node_ptr DKC_LZW ptr,
int  node
[static]
 

dkcLZW.c66 行で定義されています。

参照先 dkcdLZW_NUM, dkcmASSERT, と dkc_LZW::pool.

00067 {
00068     dkcmASSERT(node < dkcdLZW_NUM);
00069     return &(ptr->pool.tst[node]);
00070 }

static DKC_INLINE int decode_hash DKC_LZW ptr,
BYTE dest,
size_t  dsize,
DKC_BIT_MEMORYSTREAM mbs,
int  origin_size
[static]
 

dkcLZW.c508 行で定義されています。

参照先 add_hash(), dkc_LZW_Trie::code, dkcAllocateFast(), dkcBitMemoryStreamRead(), dkcdLZW_CODE_SIZE, dkcdLZW_NUM, dkcFree(), dkcMemoryStreamAdapterInit(), dkcMemoryStreamPut8(), dkcMemoryStreamTell, dkcmNOT_ASSERT, dkc_LZW::node_count, NULL, output_hash_code(), と dkc_LZW::pool.

参照元 dkcLZWDecode().

00511 {
00512         //bit temporary
00513   int q = 0;
00514     int r;
00515   size_t len = 1;
00516     //元サイズ
00517     int size = origin_size - 1;
00518     //memory stream adapter
00519     DKC_MEMORYSTREAM_ADAPTER aw;
00520     //dynamic buffer
00521     uint8 *buffer = NULL;
00522     //trie temp
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   //fputc( tst[q].code, fp );
00538     //dkcmASSERT(q == q2);
00539 
00540   while( size > 0 ){
00541     uint32 c;
00542         //uint32 out;
00543         r = dkcBitMemoryStreamRead(mbs ,(uint32 *)&c,dkcdLZW_CODE_SIZE);
00544         if(DKUTIL_FAILED(r))
00545         {
00546             goto Error;
00547         }
00548     //dkcmASSERT(c == c2);
00549         //dkcAddLogFile("decode_dev.log","%0x",c);
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://error 時
00567     dkcFree(&buffer);
00568     dkcmNOT_ASSERT(dkcMemoryStreamTell(&aw) != (size_t)origin_size);
00569 
00570     return r;
00571 }

static DKC_INLINE int decode_tst DKC_LZW ptr,
BYTE dest,
size_t  dsize,
DKC_BIT_MEMORYSTREAM mbs,
int  origin_size
[static]
 

dkcLZW.c234 行で定義されています。

参照先 add_node(), dkc_LZW_Node::code, dkcAllocateFast(), dkcBitMemoryStreamRead(), dkcdLZW_CODE_SIZE, dkcdLZW_NUM, dkcFree(), dkcMemoryStreamAdapterInit(), dkcMemoryStreamPut8(), dkc_LZW::node_count, NULL, output_tst_code(), と dkc_LZW::pool.

参照元 dkcLZWDecode().

00237 {
00238     //bit temporary
00239   int q = 0;
00240     int r;
00241   size_t len = 1;
00242     //元サイズ
00243     int size = origin_size - 1;
00244     //memory stream adapter
00245     DKC_MEMORYSTREAM_ADAPTER aw;
00246     //dynamic buffer
00247     uint8 *buffer = NULL;
00248     //tst temp
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   //fputc( tst[q].code, fp );
00264     //dkcmASSERT(q == q2);
00265 
00266   while( size > 0 ){
00267     uint32 c;
00268         //uint32 out;
00269         r = dkcBitMemoryStreamRead(mbs ,(uint32 *)&c,dkcdLZW_CODE_SIZE);
00270         if(DKUTIL_FAILED(r))
00271         {
00272             goto Error;
00273         }
00274     //dkcmASSERT(c == c2);
00275         //dkcAddLogFile("decode_dev.log","%0x",c);
00276         if( (size_t)c < ptr->node_count ){
00277       /* 出力する */
00278       //len = output_code( c, fp );
00279       output_tst_code( ptr,c, &aw,&len,buffer );
00280             /* tst に追加する */
00281       add_node( ptr,q, buffer[len - 1] );
00282     } else {
00283             
00284       /* 辞書範囲外の場合 */
00285       /* tst に追加する */
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://error 時
00295     dkcFree(&buffer);
00296 
00297 
00298     return r;
00299 }

DKC_INLINE DKC_LZW* WINAPI dkcAllocLZW size_t  output_block_size  ) 
 

引数:
output_block_size[in] 一回のエンコード、デコードに処理するサイズ

dkcLZW.c576 行で定義されています。

参照先 dkcAllocate(), dkcAllocBitMemoryStream(), dkcFree(), dkc_LZW::mbs, と NULL.

00576                                                                 {
00577     DKC_LZW *p = dkcAllocate(sizeof(DKC_LZW));
00578     //memset(p,0,sizeof(*p));
00579     p->mbs = dkcAllocBitMemoryStream(output_block_size);
00580     if(NULL==p->mbs){
00581         dkcFree(&p);
00582         return NULL;
00583     }
00584     //encodeとdecode時に行うのならば必要ない。
00585     //init_lzw(p);
00586     return p;
00587 }

DKC_INLINE int WINAPI dkcFreeLZW DKC_LZW **  p  ) 
 

dkcLZW.c589 行で定義されています。

参照先 dkcFree(), dkcFreeBitMemoryStream(), free_hash(), と NULL.

00589                                              {
00590     if(NULL==p || NULL==*p) return edk_FAILED;
00591     free_hash(*p);
00592     dkcFreeBitMemoryStream(&((*p)->mbs));
00593     return dkcFree(p);
00594 
00595 }

DKC_INLINE int WINAPI dkcLZWDecode DKC_LZW ptr,
DKC_LZW_HEADER ph,
BYTE dest,
size_t  dsize,
const BYTE src,
size_t  ssize,
ULONG  sig
 

引数:
ptr[in][out] dkcAllocLZW()で取得したポインタ
ph[out] DKC_LZW_HEADERへのポインタ
dest[out] デコードされたデータの書き出しバッファへのポインタ
dsize[in] destのサイズ
src[in] バッファへのポインタ
ssize[in] srcのサイズ
sig[in] dkcLZWEncode()の時、指定したシグネチャID
戻り値:
edk_Resultのどれかが返る。
覚え書き:
DKC_LZW_HEADERのメンバのmOriginSizeよりdsizeが小さいとこの関数は失敗します。

dkcLZW.c598 行で定義されています。

参照先 decode_hash(), decode_tst(), dkcBitMemoryStreamLoadFromMemory, edkcLZW_Default, edkcLZW_HASH, edkcLZW_TST, init_hash(), init_lzw(), init_tst(), dkc_LZW::mbs, dkc_LZW_Header::mOriginSize, dkc_LZW_Header::mSignature, と dkc_LZW_Header::option.

00600 {   
00601     
00602     DKC_BIT_MEMORYSTREAM *mbs = ptr->mbs;
00603     {
00604         int r;
00605         /*init_lzw内
00606         r = dkcBitMemoryStreamSeekByte(mbs,0,edkcSeekSet);
00607     
00608         
00609         if(DKUTIL_FAILED(r)) return r;*/
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(;;){//break 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 }

DKC_INLINE int WINAPI dkcLZWEncode DKC_LZW ptr,
DKC_LZW_HEADER ph,
BYTE dest,
size_t  dsize,
const BYTE src,
size_t  ssize,
size_t  CloseProcessSize,
ULONG  sig,
ULONG  option
 

デフォルトの設定

dkcLZW.c643 行で定義されています。

参照先 edkcLZW_Default, edkcLZW_HASH, edkcLZW_TST, edkcLZW_Variableness, encode_hash(), encode_tst(), init_hash(), init_lzw(), init_tst(), dkc_LZW_Header::mCompressedSize, dkc_LZW_Header::mOriginSize, dkc_LZW_Header::mSignature, NULL, と dkc_LZW_Header::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     //flag = option;
00670     init_lzw(ptr);
00671     if(flag & edkcLZW_HASH){
00672         
00673         tr = init_hash(ptr);
00674         //error check
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 }

static DKC_INLINE int encode_hash DKC_LZW ptr,
BYTE dest,
size_t  dsize,
const BYTE src,
size_t  ssize,
size_t *  pcount
[static]
 

dkcLZW.c420 行で定義されています。

参照先 add_hash(), BYTE, dkcBitMemoryStreamTellByte, dkcBitMemoryStreamWrite(), dkcBitMemoryStreamWriteLast(), dkcBitMemoryStreamWriteToMemory, dkcdLZW_CODE_SIZE, dkcdLZW_NIL_OFFSET, dkcMemoryStreamAdapterInit(), dkcMemoryStreamGet8(), dkcMemoryStreamIsEnd, dkcmNOT_ASSERT, edkcStreamBufferToNowOffset, find_hash_node_number(), と dkc_LZW::mbs.

参照元 dkcLZWEncode().

00421 {
00422     
00423     //bit temp
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         //c = target q = find child temp
00438     
00439         //if( DKUTIL_FAILED(dkcMemoryStreamRead(&asrc,&c,1,&read_size)) )
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       /* p が最長一致位置 */
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     //todo:overflow check
00477     *pcount = dkcBitMemoryStreamTellByte(ptr->mbs);
00478 
00479     //20050812修正:
00480     //r = dkcBitMemoryStreamWriteToMemory(ptr->mbs,dest,dsize,edkcStreamBufferAll);
00481     r = dkcBitMemoryStreamWriteToMemory(ptr->mbs,dest,dsize,edkcStreamBufferToNowOffset);
00482 
00483     return r;
00484 }

static DKC_INLINE int encode_tst DKC_LZW ptr,
BYTE dest,
size_t  dsize,
const BYTE src,
size_t  ssize,
size_t *  pcount
[static]
 

endian関係どうなっているのやら 。゚(゚´Д`゚)゚。

dkcLZW.c163 行で定義されています。

参照先 add_node(), BYTE, dkcBitMemoryStreamTellByte, dkcBitMemoryStreamWrite(), dkcBitMemoryStreamWriteLast(), dkcBitMemoryStreamWriteToMemory, dkcdLZW_CODE_SIZE, dkcdLZW_NIL_OFFSET, dkcMemoryStreamAdapterInit(), dkcMemoryStreamGet8(), dkcMemoryStreamIsEnd, edkcStreamBufferToNowOffset, find_child_node_number(), と dkc_LZW::mbs.

参照元 dkcLZWEncode().

00164 {
00165 
00166     //bit temp
00167     int p = 0;
00168     int c = 0,q = 0;
00169     //size_t read_size;
00170 
00171     DKC_MEMORYSTREAM_ADAPTER asrc;
00172 
00173     dkcMemoryStreamAdapterInit(&asrc,(BYTE*)src,ssize);
00174 
00175 
00176   //ぉーど
00177   //if( DKUTIL_FAILED(dkcMemoryStreamRead(&asrc,&p,1,&read_size)) )
00178     if( DKUTIL_FAILED(dkcMemoryStreamGet8(&asrc,(BYTE *)&p)) )
00179         return edk_FAILED;
00180 
00181   //tstをたどって圧縮
00182   for(;;){
00183         //c = target q = find child temp
00184     
00185         //if( DKUTIL_FAILED(dkcMemoryStreamRead(&asrc,&c,1,&read_size)) )
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                 //init_lzw(ptr);
00194                 return edk_LogicError;
00195             }
00196     }
00197         q = find_child_node_number(ptr, p, c );
00198     if( q == dkcdLZW_NIL_OFFSET ){
00199       /* p が最長一致位置 */
00200             dkcBitMemoryStreamWrite(ptr->mbs,&p,dkcdLZW_CODE_SIZE);
00201             if(dsize < dkcBitMemoryStreamTellByte(ptr->mbs))
00202             {//バッファが足りない
00203                 return edk_BufferOverFlow;
00204             }
00205 
00206       //putbits( dkcdLZW_CODE_SIZE, p );
00207       /* 辞書の更新 */
00208       add_node(ptr, p, c );
00209       /* 不一致文字を先頭文字にする */
00210       p = c;
00211     } else {
00212       p = q;
00213     }
00214   }
00215     dkcBitMemoryStreamWriteLast(ptr->mbs);
00216     //todo:overflow check
00217     *pcount = dkcBitMemoryStreamTellByte(ptr->mbs);
00218     /*if(dsize < *pcount)
00219     {//バッファが足りない
00220         return edk_BufferOverFlow;
00221     }
00222 
00223     
00224     
00225     return edk_SUCCEEDED;*/
00226     //return dkcBitMemoryStreamWriteToMemory(ptr->mbs,dest,dsize,edkcStreamBufferAll);
00227     return dkcBitMemoryStreamWriteToMemory(ptr->mbs,dest,dsize,edkcStreamBufferToNowOffset);
00228 
00229 }

static DKC_INLINE DKC_LZW_NODE* find_child_node DKC_LZW ptr,
int  node,
int  c
[static]
 

子供ノードを見つける

引数:
node[in] ノード番号
c[in] キー
戻り値:
dkcdLZW_NILだと見つからない…。゚(゚´Д`゚)゚。

dkcLZW.c86 行で定義されています。

参照先 dkc_LZW_Node::code, dkcdLZW_NIL, dkc_LZW_Node::left, dkc_LZW::pool, と dkc_LZW_Node::right.

参照元 find_child_node_number().

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 }

static int find_child_node_number DKC_LZW ptr,
int  node,
int  c
[static]
 

dkcLZW.c100 行で定義されています。

参照先 dkcmNOT_ASSERT, find_child_node(), と dkc_LZW::pool.

参照元 encode_tst().

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 }

static DKC_INLINE dkcdLZW_DATA find_hash_node DKC_LZW p,
int  node,
int  c
[static]
 

dkcLZW.c393 行で定義されています。

参照先 dkcdLZW_NIL_OFFSET, dkcmLZW_HASH_FUNC, dkc_LZW::hash_stack, dkc_LZW::hash_table, index(), と dkc_LZW::pool.

参照元 find_hash_node_number().

00394 {
00395   int index = dkcmLZW_HASH_FUNC( node, c );
00396   int n =   p->hash_table[index];
00397     /*if(dkcdLZW_NIL_OFFSET==n){
00398         return n;
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   //return p->hash_table[n];
00407         return n;
00408 }

static DKC_INLINE int find_hash_node_number DKC_LZW ptr,
int  node,
int  c
[static]
 

dkcLZW.c411 行で定義されています。

参照先 dkcdLZW_DATA, と find_hash_node().

参照元 encode_hash().

00412 {
00413     dkcdLZW_DATA t = find_hash_node(ptr,node,c);
00414     //dkcmNOT_ASSERT(t < ptr->pool.tst);
00415     //return (int)(t - (&ptr->pool.tst[0]));
00416     return t;
00417 }

static void free_hash DKC_LZW p  )  [static]
 

dkcLZW.c306 行で定義されています。

参照先 dkcFree(), dkc_LZW::hash_stack, と dkc_LZW::hash_table.

参照元 alloc_hash(), と dkcFreeLZW().

00306                                  {
00307     dkcFree((void **)&(p->hash_stack));
00308     dkcFree((void **)&(p->hash_table));
00309 }

static int init_hash DKC_LZW p  )  [static]
 

dkcLZW.c338 行で定義されています。

参照先 alloc_hash(), dkcdLZW_HASH_TABLE_SIZE, dkcdLZW_NIL_OFFSET, dkc_LZW::hash_stack, dkc_LZW::hash_table, と init_trie().

参照元 dkcLZWDecode(), と dkcLZWEncode().

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     //initialize memory
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     /*for(i=0;i<dkcdLZW_HASH_TABLE_SIZE;i++){
00357         p->hash_table[i] = dkcdLZW_NIL(p);
00358         p->hash_stack[i] = dkcdLZW_NIL(p);
00359     }*/
00360     //memset(p->hash_stack,dkcdLZW_NIL(p),stack_size);
00361     //memset(p->hash_table,NULL,table_size);
00362     //memset(p->hash_stack,NULL,stack_size);
00363     return edk_SUCCEEDED;
00364 }

static DKC_INLINE void init_lzw DKC_LZW p  )  [static]
 

DKC_LZW構造体を初期化する

dkcLZW.c16 行で定義されています。

参照先 dkcBitMemoryStreamSeekByte(), dkcmFORCE_NOT_ASSERT, edkcBitMemoryStreamSeekSet, dkc_LZW::mbs, dkc_LZW::node_count, と dkc_LZW::pool.

参照元 dkcLZWDecode(), dkcLZWEncode(), と init_trie().

00016                                            {
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 }

static DKC_INLINE void init_trie DKC_LZW p  )  [static]
 

dkcLZW.c26 行で定義されています。

参照先 dkcdLZW_NIL_OFFSET, dkcdLZW_NUM, init_lzw(), と dkc_LZW::pool.

参照元 init_hash().

00026                                             {
00027     //memset(p,0,sizeof(*p));
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 }

static void init_tst DKC_LZW p  )  [static]
 

dkcLZW.c44 行で定義されています。

参照先 dkcdLZW_NIL, dkcdLZW_NUM, dkc_LZW::pool, と dkc_LZW::sentinel.

参照元 dkcLZWDecode(), と dkcLZWEncode().

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 }

static DKC_INLINE int output_hash_code DKC_LZW ptr,
int  node,
DKC_MEMORYSTREAM_ADAPTER pa,
size_t *  output_size,
uint8 *  buffer
[static]
 

dkcLZW.c486 行で定義されています。

参照先 dkcdLZW_NIL_OFFSET, dkcmASSERT, dkcMemoryStreamPut8(), と dkc_LZW::pool.

参照元 decode_hash().

00489 {
00490   int i = 0, a = node;
00491     //dkcOutputDebugString("dkcdLZW_NIL_OFFSET = %d",dkcdLZW_NIL_OFFSET);
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 }

static DKC_INLINE int output_tst_code DKC_LZW ptr,
int  node,
DKC_MEMORYSTREAM_ADAPTER pa,
size_t *  output_size,
uint8 *  buffer
[static]
 

dkcLZW.c138 行で定義されています。

参照先 dkcdLZW_NIL, dkcmASSERT, dkcMemoryStreamPut8(), と dkc_LZW::pool.

参照元 decode_tst().

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//tst[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 }


dkutil_cに対してSat Sep 10 09:24:31 2005に生成されました。  doxygen 1.4.4