#include "dkcOSIndependent.h"
#include "dkcRedBlackTree.h"
#include "dkcBit.h"
dkcLZW.hのインクルード依存関係図
このグラフは、どのファイルから直接、間接的にインクルードされているかを示しています。
構成 | |
struct | dkc_LZW_Node |
LZWのTernary Search Tree + Red Black Treeアルゴリズムに使うノード [詳細] | |
struct | dkc_LZW_Trie |
struct | dkc_LZW |
struct | dkc_LZW_Header |
マクロ定義 | |
#define | dkcdLZW_SIGNATURE edk_LZW_SIGNATURE |
LZWのシグネチャ(変更しても大丈夫だよ〜(多分)) | |
#define | dkcdLZW_CODE_SIZE 15 |
code size ? | |
#define | dkcdLZW_NUM (1 << dkcdLZW_CODE_SIZE) |
lzw buffer の数 | |
#define | dkcdLZW_NIL(objp) objp->sentinel |
NULLの代わり、sentinel | |
#define | dkcdLZW_NIL_OFFSET dkcdLZW_NUM |
#define | dkcdLZW_HASH_TABLE_SIZE 32749 |
65521もアリか | |
#define | dkcmLZW_HASH_FUNC(node, c) ((((node) << 8) + (c)) % dkcdLZW_HASH_TABLE_SIZE) |
#define | dkcdLZW_DATA int |
データタイプ | |
#define | dkcdLZW_COLOR uint8 |
red black treeで使う色保存用変数(int型にしても良い) | |
#define | dkcLZWDump(lzwobj, filename) dkcBitMemoryStreamDump(lzwobj->mbs,filename,edkcDumpNowOffset) |
型定義 | |
typedef dkc_LZW_Node | DKC_LZW_NODE |
LZWのTernary Search Tree + Red Black Treeアルゴリズムに使うノード | |
typedef dkc_LZW_Trie | DKC_LZW_TRIE |
typedef dkc_LZW | DKC_LZW |
typedef dkc_LZW_Header | DKC_LZW_HEADER |
列挙型 | |
enum | edk_LZW_Option { edkcLZW_Default = 0, edkcLZW_Variableness = 1, edkcLZW_TST = 2, edkcLZW_HASH = 4, edkcLZW_REDBLACK = 8, edkcLZW_TRIE = 16 } |
関数 | |
DKC_EXTERN DKC_LZW *WINAPI | dkcAllocLZW (size_t output_block_size) |
DKC_EXTERN int WINAPI | dkcFreeLZW (DKC_LZW **) |
DKC_EXTERN int WINAPI | dkcLZWDecode (DKC_LZW *ptr, DKC_LZW_HEADER *ph, BYTE *dest, size_t dsize, const BYTE *src, size_t ssize, ULONG sig) |
DKC_EXTERN 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) |
2005/03/27 M.Hiroi氏のHP(://www.geocities.jp/m_hiroi/ )で紹介されている http://www.geocities.jp/m_hiroi/zsaru/zsarub36.htmlのサイトを参考にし、 Hash + Ternary Search Tree + Red Black Treeのアルゴリズムを使用して実装する事にした。
dkcLZW.h で定義されています。
|
code size ?
参照元 decode_hash(), decode_tst(), encode_hash(), と encode_tst(). |
|
red black treeで使う色保存用変数(int型にしても良い)
|
|
データタイプ
参照元 alloc_hash(), と find_hash_node_number(). |
|
65521もアリか
参照元 alloc_hash(), と init_hash(). |
|
NULLの代わり、sentinel
参照元 add_node(), find_child_node(), init_tst(), と output_tst_code(). |
|
参照元 encode_hash(), encode_tst(), find_hash_node(), init_hash(), init_trie(), と output_hash_code(). |
|
lzw buffer の数
参照元 add_hash(), add_node(), alloc_hash(), calc_tst_node_ptr(), decode_hash(), decode_tst(), init_trie(), と init_tst(). |
|
LZWのシグネチャ(変更しても大丈夫だよ〜(多分))
|
|
|
|
参照元 add_hash(), と find_hash_node(). |
|
|
|
|
|
LZWのTernary Search Tree + Red Black Treeアルゴリズムに使うノード
|
|
|
|
00115 { 00117 edkcLZW_Default = 0, 00119 edkcLZW_Variableness = 1, 00121 edkcLZW_TST = 2, 00123 edkcLZW_HASH = 4, 00125 edkcLZW_REDBLACK = 8, 00127 edkcLZW_TRIE = 16, 00128 00129 };
|
|
参照先 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 }
|
|
参照先 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 }
|
|
参照先 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 }
|
|
デフォルトの設定 参照先 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 }
|