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

dkcLZW.h

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

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


説明

LZW圧縮アルゴリズム

作者:
d金魚
覚え書き:
gifに準拠した圧縮方式にするか、 M.Hiroi氏のHPで紹介されているトリッキーな手法で圧縮率を稼ぐか… どちらにしよう?
でも、今の所、実装する気無し ○| ̄|_ 2005/03/20 d金魚

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 で定義されています。


マクロ定義

#define dkcdLZW_CODE_SIZE   15
 

code size ?

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

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

#define dkcdLZW_COLOR   uint8
 

red black treeで使う色保存用変数(int型にしても良い)

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

#define dkcdLZW_DATA   int
 

データタイプ

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

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

#define dkcdLZW_HASH_TABLE_SIZE   32749
 

65521もアリか

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

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

#define dkcdLZW_NIL objp   )     objp->sentinel
 

NULLの代わり、sentinel

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

参照元 add_node(), find_child_node(), init_tst(), と output_tst_code().

#define dkcdLZW_NIL_OFFSET   dkcdLZW_NUM
 

参照:
dkcdLZW_NIL()

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

参照元 encode_hash(), encode_tst(), find_hash_node(), init_hash(), init_trie(), と output_hash_code().

#define dkcdLZW_NUM   (1 << dkcdLZW_CODE_SIZE)
 

lzw buffer の数

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

参照元 add_hash(), add_node(), alloc_hash(), calc_tst_node_ptr(), decode_hash(), decode_tst(), init_trie(), と init_tst().

#define dkcdLZW_SIGNATURE   edk_LZW_SIGNATURE
 

LZWのシグネチャ(変更しても大丈夫だよ〜(多分))

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

#define dkcLZWDump lzwobj,
filename   )     dkcBitMemoryStreamDump(lzwobj->mbs,filename,edkcDumpNowOffset)
 

参照:
dkcBitMemoryStreamDump()

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

#define dkcmLZW_HASH_FUNC node,
 )     ((((node) << 8) + (c)) % dkcdLZW_HASH_TABLE_SIZE)
 

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

参照元 add_hash(), と find_hash_node().


型定義

typedef struct dkc_LZW DKC_LZW
 

typedef struct dkc_LZW_Header DKC_LZW_HEADER
 

typedef struct dkc_LZW_Node DKC_LZW_NODE
 

LZWのTernary Search Tree + Red Black Treeアルゴリズムに使うノード

typedef struct dkc_LZW_Trie DKC_LZW_TRIE
 


列挙型

enum edk_LZW_Option
 

列挙型の値:
edkcLZW_Default  デフォルトの設定
edkcLZW_Variableness  可変長辞書を使う
edkcLZW_TST  TSTを使う
edkcLZW_HASH  hash法を使う
edkcLZW_REDBLACK  red black treeを使う
edkcLZW_TRIE  trieを使う

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

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


関数

DKC_EXTERN 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_EXTERN int WINAPI dkcFreeLZW DKC_LZW **   ) 
 

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_EXTERN 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_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
 

デフォルトの設定

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 }


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