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

# dkcLZSS.c

`#include "dkcLZSS.h"`
`#include "dkcStdio.h"`

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

ソースコードを見る。

## マクロ定義
#define | DKUTIL_C_LZSS_C
#define | NIL LZSS_RING_LENGTH
| 木の末端
## 関数
static void | InitTree (DKC_LZSS *pWork)
| 圧縮・解凍用の木のデータを初期化します。
static void | InsertNode (DKC_LZSS *pWork, long r)
| 節を木に挿入します。
static void | DeleteNode (DKC_LZSS *pWork, long p)
| 節を木から削除します。
static BOOL | Decode (DKC_LZSS *pWork, DKC_LZSS_HEADER *ph, const void *pSrc, void *pDst)
| LZSSで圧縮されたデータを解凍します。
static BOOL | Encode (DKC_LZSS *pWork, const void *pSrc, unsigned long SrcSize, void *pDst, size_t DstSize, unsigned long *pDstSize, size_t CloseProcessSize)
| データをLZSSで圧縮します。
DKC_LZSS *WINAPI | dkcAllocLZSS ()
int WINAPI | dkcFreeLZSS (DKC_LZSS **p)
int WINAPI | dkcLZSSDecode (DKC_LZSS *ptr, DKC_LZSS_HEADER *ph, BYTE *dest, size_t dsize, const BYTE *src, size_t ssize, ULONG sig)
int WINAPI | dkcLZSSEncode (DKC_LZSS *ptr, DKC_LZSS_HEADER *ph, BYTE *dest, size_t dsize, const BYTE *src, size_t ssize, size_t CloseProcessSize, ULONG sig)

## 説明

作者:
  d金魚

から:
  2004/04/20

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

## マクロ定義

#define DKUTIL_C_LZSS_C

| dkcLZSS.c の 8 行で定義されています。

#define NIL LZSS_RING_LENGTH

| 木の末端 dkcLZSS.c の 18 行で定義されています。 参照元 DeleteNode(), InitTree(), と InsertNode().

## 関数

static BOOL Decode | ( | DKC_LZSS * | pWork,
|  | DKC_LZSS_HEADER * | ph,
|  | const void * | pSrc,
|  | void * | pDst
| ) | `[static]`

  | LZSSで圧縮されたデータを解凍します。 引数:
  | pSrc | [in] 圧縮されたデータ
  | pDst | [out] 展開後のデータ
  戻り値:
  | TRUE | 成功
  | FALSE | 失敗
-------------------------------------------------------------- ヘッダチェック -------------------------------------------------------------- if ( ((LZSS_HEADER*)pSrc)->Guid[0] != 'L' ) return FALSE; if ( ((LZSS_HEADER*)pSrc)->Guid[1] != 'Z' ) return FALSE; if ( ((LZSS_HEADER*)pSrc)->Guid[2] != 'S' ) return FALSE; if ( ((LZSS_HEADER*)pSrc)->Guid[3] != 'S' ) return FALSE; dkcLZSS.c の 226 行で定義されています。 参照先 LZSS_LONGEST_MATCH, LZSS_RING_LENGTH, dkc_LZSS_Header::mOriginSize, dkc_LZSS::Text, と TRUE. 参照元 dkcLZSSDecode().
    00228 {
    00229     long r = LZSS_RING_LENGTH - LZSS_LONGEST_MATCH;
    00230     unsigned long Flags = 0;
    00231     unsigned char c;
    00232
    00233     unsigned char *pDstData = (unsigned char*)pDst;
    00234     //unsigned char *pSrcData = (unsigned char*)pSrc + sizeof(LZSS_HEADER);
    00235     unsigned char *pSrcData = (unsigned char*)pSrc;
    00236     //--------------------------------------------------------------
    00237     // 展開後サイズ取得
    00238     //--------------------------------------------------------------
    00239     //unsigned long DstSize = ((LZSS_HEADER*)pSrc)->OriginalSize;
    00240     unsigned long DstSize = ph->mOriginSize;
    00241
    00242     long k = 0;
    00243     //MemoryClear( pWork->Text, sizeof(pWork->Text) );
    00244     memset(pWork->Text,0,sizeof(pWork->Text) );
    00254     //--------------------------------------------------------------
    00255     // デコード処理
    00256     //--------------------------------------------------------------
    00257     while ( TRUE )
    00258     {
    00259         Flags >>= 1;
    00260         if ( (Flags & 256) == 0 )
    00261         {
    00262             c = *( pSrcData++ );
    00263             Flags = c | 0xff00;
    00264         }
    00265
    00266         if ( Flags & 1 )
    00267         {
    00268             c = *(pSrcData++);
    00269             *(pDstData++) = c;
    00270             if ( --DstSize == 0 ) return TRUE;
    00271
    00272             pWork->Text[r++] = c;
    00273             r &= (LZSS_RING_LENGTH - 1);
    00274         }
    00275         else
    00276         {
    00277             long i = *(pSrcData++);
    00278             long j = *(pSrcData++);
    00279             i |= ((j & 0xF0) << 4);
    00280             j = (j & 0x0F) + 2;
    00281
    00282             //for ( long k = 0; k <= j; k++ )
    00283             for ( k = 0; k <= j; k++ )
    00284             {
    00285                 c = pWork->Text[(i + k) & (LZSS_RING_LENGTH - 1)];
    00286                 *(pDstData++) = c;
    00287                 if ( --DstSize == 0 ) return TRUE;
    00288
    00289                 pWork->Text[r++] = c;
    00290                 r &= (LZSS_RING_LENGTH - 1);
    00291             }
    00292         }
    00293     }
    00294
    00295     //return FALSE;
    00296 }

static void DeleteNode | ( | DKC_LZSS * | pWork,
|  | long | p
| ) | `[static]`

  | 節を木から削除します。 引数:
  | p | [in] 削除するデータ
dkcLZSS.c の 168 行で定義されています。 参照先 dkc_LZSS::Dad, dkc_LZSS::LSon, NIL, と dkc_LZSS::RSon. 参照元 Encode().
    00169 {
    00170     long q = -1;
    00171
    00172     if ( pWork->Dad[p]  == NIL ) return;
    00173
    00174     if ( pWork->RSon[p] == NIL )
    00175     {
    00176         q = pWork->LSon[p];
    00177     }
    00178     else if( pWork->LSon[p] == NIL )
    00179     {
    00180         q = pWork->RSon[p];
    00181     }
    00182     else
    00183     {
    00184         q = pWork->LSon[p];
    00185
    00186         if ( pWork->RSon[q] != NIL )
    00187         {
    00188             do { q = pWork->RSon[q]; } while ( pWork->RSon[q] != NIL );
    00189
    00190             pWork->RSon[pWork->Dad[q]]  = pWork->LSon[q];
    00191             pWork->Dad[pWork->LSon[q]]  = pWork->Dad[q];
    00192             pWork->LSon[q]              = pWork->LSon[p];
    00193             pWork->Dad[pWork->LSon[p]]  = q;
    00194         }
    00195
    00196         pWork->RSon[q] = pWork->RSon[p];
    00197         pWork->Dad[pWork->RSon[p]]  = q;
    00198     }
    00199
    00200     pWork->Dad[q] = pWork->Dad[p];
    00201     if ( pWork->RSon[pWork->Dad[p]] == p )
    00202     {
    00203         pWork->RSon[pWork->Dad[p]] = q;
    00204     }
    00205     else
    00206     {
    00207         pWork->LSon[pWork->Dad[p]] = q;
    00208     }
    00209
    00210     pWork->Dad[p] = NIL;
    00211 }

DKC_LZSS* WINAPI dkcAllocLZSS | ( |  | ) |

| dkcLZSS.c の 497 行で定義されています。 参照先 dkcAllocate().
    00498 {
    00499     DKC_LZSS *p = dkcAllocate(sizeof(DKC_LZSS));
    00500     return p;
    00501 }

int WINAPI dkcFreeLZSS | ( | DKC_LZSS ** | p | ) |

| dkcLZSS.c の 503 行で定義されています。 参照先 dkcFree(), と NULL.
    00503                                     {
    00504     if(NULL==p || NULL==*p) return edk_FAILED;
    00505     return dkcFree((void **)p);
    00506 }

int WINAPI dkcLZSSDecode | ( | DKC_LZSS * | ptr,
|  | DKC_LZSS_HEADER * | ph,
|  | BYTE * | dest,
|  | size_t | dsize,
|  | const BYTE * | src,
|  | size_t | ssize,
|  | ULONG | sig
| ) |

  | 引数:
  | ptr[in][out] | dkcAllocLZSS()で取得したポインタ
  | ph[out] | DKC_LZSS_HEADERへのポインタ
  | dest[out] | デコードされたデータの書き出しバッファへのポインタ
  | dsize[in] | destのサイズ
  | src[in] | バッファへのポインタ
  | ssize[in] | srcのサイズ
  | sig[in] | dkcLZSSEncode()の時、指定したシグネチャID
戻り値: edk_Resultのどれかが返る。 覚え書き: DKC_LZSS_HEADERのメンバのmOriginSizeよりdsizeが小さいとこの関数は失敗します。 dkcLZSS.c の 509 行で定義されています。 参照先 Decode(), FALSE, dkc_LZSS_Header::mOriginSize, dkc_LZSS_Header::mSignature, と NULL.
    00511 {
    00512     if(NULL==ptr || NULL==ph)
    00513         return edk_ArgumentException;
    00514
    00515     if(ph->mOriginSize > dsize){
    00516         return edk_BufferOverFlow;
    00517         }
    00518     //if(dkcLZSSIsLZSS(ph)==FALSE){
    00519     if(ph->mSignature != sig){
    00520         return edk_FAILED;
    00521         }
    00522
    00523     if(FALSE==Decode(ptr,ph,src,dest)){
    00524         return edk_FAILED;
    00525         }
    00526
    00527     return edk_SUCCEEDED;
    00528
    00529 }

int WINAPI dkcLZSSEncode | ( | DKC_LZSS * | ptr,
|  | DKC_LZSS_HEADER * | ph,
|  | BYTE * | dest,
|  | size_t | dsize,
|  | const BYTE * | src,
|  | size_t | ssize,
|  | size_t | CloseProcessSize,
|  | ULONG | sig
| ) |

  | 引数:
  | ptr[in][out] | dkcAllocLZSS()で取得したポインタ
  | ph[out] | DKC_LZSS_HEADERへのポインタ
  | dest[out] | LZSSで圧縮されたデータの書き出しバッファへのポインタ
  | dsize[in] | destのサイズ
  | src[in] | バッファへのポインタ
  | ssize[in] | srcのサイズ
  | CloseProcessSize[in] | 処理を打ち切りにするサイズ dsizeより小さくするのがセオリー
  | sig[in] | LZSSだと証明するシグネチャ
戻り値: edk_Resultのどれかが返る。圧縮する価値の無い場合はedk_NoValueToProcessが返る。 dkcLZSS.c の 531 行で定義されています。 参照先 dkcmNOT_ASSERT, Encode(), dkc_LZSS_Header::mCompressedSize, dkc_LZSS_Header::mOriginSize, dkc_LZSS_Header::mSignature, と NULL.
    00534 {
    00535     unsigned long comped;
    00536     int result;
    00537
    00538     if(NULL==ptr || NULL==ph)
    00539         return edk_ArgumentException;
    00540
    00541     dkcmNOT_ASSERT(NULL==dest || 0==dsize);
    00542
    00543
    00544     result = Encode(ptr,src,ssize,dest,dsize,&comped,CloseProcessSize);
    00545     if(DKUTIL_FAILED(result))
    00546     {
    00547         return result;
    00548     }
    00549     ph->mOriginSize = (size_t)ssize;
    00550     ph->mCompressedSize = comped;
    00551     ph->mSignature =  sig;
    00552
    00553     return result;
    00554
    00555 }

static BOOL Encode | ( | DKC_LZSS * | pWork,
|  | const void * | pSrc,
|  | unsigned long | SrcSize,
|  | void * | pDst,
|  | size_t | DstSize,
|  | unsigned long * | pDstSize,
|  | size_t | CloseProcessSize
| ) | `[static]`

  | データをLZSSで圧縮します。 引数:
  | pSrc | [in] 圧縮するデータ
  | SrcSize | [in] 圧縮元データ(pSrc)のサイズ
  | pDst | [out] 圧縮後のデータ格納先
  | DstSize[in] | pDstバッファのサイズ
  | pDstSize | [out] 圧縮後のデータサイズ
  | CloseProcessSize[in] | 処理を打ち切りするサイズ SrcSizeより小さくするのがセオリー
戻り値: edk_Resultのどれか。詳しくは実装を見よう！（オイ 圧縮したサイズ？を取得 dkcLZSS.c の 311 行で定義されています。 参照先 DeleteNode(), FALSE, InitTree(), InsertNode(), LZSS_LONGEST_MATCH, LZSS_RING_LENGTH, dkc_LZSS::MatchLen, dkc_LZSS::MatchPos, と dkc_LZSS::Text. 参照元 dkcLZSSEncode().
    00316 {
    00317     unsigned char   Code[17]        = { 0 };
    00318     unsigned char   Mask            = 1;
    00319     long            i               = 0;
    00320     long            Len             = 0;
    00321     long            CodePtr         = 1;
    00322     long            LastMatchLen    = 0;
    00323     long            s               = 0;
    00324     long            r               = LZSS_RING_LENGTH - LZSS_LONGEST_MATCH;
    00325
    00326     //バッファ漏れとかのチェック変数だと思う。
    00327     //圧縮率100％以上じゃないと認めない。
    00328     //unsigned long SrcCheckSize    = SrcSize;//SrcSize * 2;
    00329     unsigned long SrcCheckSize = CloseProcessSize;
    00330
    00331     //unsigned char *pDstData = (unsigned char *)pDst + sizeof(LZSS_HEADER);
    00332     unsigned char *pDstData = (unsigned char *)pDst;
    00333     unsigned char *pSrcData = (unsigned char *)pSrc;
    00334
    00335
    00336
    00337     unsigned char c;
    00338     //圧縮する価値があるかどうかカウント
    00339     ULONG CompressByte = 0;
    00340
    00341     //--------------------------------------------------------------
    00342     // LZSSヘッダの作成
    00343     //--------------------------------------------------------------
    00344     /*
    00345     ((LZSS_HEADER*)pDst)->Guid[0] = 'L';
    00346     ((LZSS_HEADER*)pDst)->Guid[1] = 'Z';
    00347     ((LZSS_HEADER*)pDst)->Guid[2] = 'S';
    00348     ((LZSS_HEADER*)pDst)->Guid[3] = 'S';
    00349     ((LZSS_HEADER*)pDst)->OriginalSize = SrcSize;
    00350     */
    00351     //pHeader->mOriginSize = SrcSize;
    00352     //--------------------------------------------------------------
    00353     // 転送先サイズ
    00354     //--------------------------------------------------------------
    00355     //(*pDstSize) = sizeof(LZSS_HEADER);
    00356     (*pDstSize) = 0;
    00357     //--------------------------------------------------------------
    00358     // 木を初期化
    00359     //--------------------------------------------------------------
    00360     InitTree(pWork );
    00361
    00362     //--------------------------------------------------------------
    00363     // バッファを初期化
    00364     //--------------------------------------------------------------
    00365     for ( i = s; i < r; i++ ) pWork->Text[i] = 0;
    00366
    00367     for ( Len = 0; Len < LZSS_LONGEST_MATCH ; Len++ )
    00368     {
    00369         unsigned char c = *(pSrcData++);
    00370         if ( --SrcSize <= 0 ) break;
    00371         pWork->Text[r + Len] = c;
    00372     }
    00373
    00374     if ( Len == 0 ) return FALSE;
    00375
    00376     for ( i = 1; i <= LZSS_LONGEST_MATCH; i++ )
    00377     {
    00378         InsertNode(pWork, r - i );
    00379     }
    00380
    00381     InsertNode(pWork, r );
    00382
    00383     //--------------------------------------------------------------
    00384     // エンコード処理
    00385     //--------------------------------------------------------------
    00386     do
    00387     {
    00388         if ( pWork->MatchLen > Len )
    00389         {
    00390             pWork->MatchLen = Len;
    00391         }
    00392
    00393         if ( pWork->MatchLen < 3 )
    00394         {
    00395             pWork->MatchLen = 1;
    00396             Code[0] |= Mask;
    00397             Code[CodePtr++] = pWork->Text[r];
    00398         }
    00399         else
    00400         {
    00401             Code[CodePtr++] = (unsigned char)pWork->MatchPos;
    00402             Code[CodePtr++] = (unsigned char)(((pWork->MatchPos >> 4) & 0xF0) | (pWork->MatchLen - 3) );
    00403         }
    00404
    00405         if ( (Mask <<= 1) == 0 )
    00406         {
    00407             (*pDstSize) += CodePtr;
    00408
    00409             if ( SrcCheckSize <= (*pDstSize) )
    00410             {
    00411                 //goto EXIT;
    00412                 //圧縮する価値は無いよ！
    00413                 return edk_NoValueToProcess;
    00414             }
    00415
    00416             CompressByte += CodePtr;
    00417             if(CompressByte >= DstSize)
    00418             {//バッファが漏れる也！
    00419                 return edk_BufferOverFlow;
    00420             }
    00421
    00422             for ( i = 0; i < CodePtr; i++ )
    00423             {//多分、コピーする処理。
    00424                 *(pDstData++) = Code[i];
    00425
    00426
    00427             }
    00428             Code[0] = 0;
    00429             CodePtr = Mask = 1;
    00430         }
    00431
    00432         LastMatchLen = pWork->MatchLen;
    00433
    00434         for ( i = 0; i < LastMatchLen; i++ )
    00435         {
    00436             if ( SrcSize == 0 ) break;
    00437             SrcSize--;
    00438
    00439             //unsigned char c = *(pSrcData++);
    00440             c = *(pSrcData++);
    00441             //DeleteNode( s );
    00442             DeleteNode(pWork,s);
    00443             pWork->Text[s] = c;
    00444             if ( s < LZSS_LONGEST_MATCH - 1 )
    00445             {
    00446                 pWork->Text[s + LZSS_RING_LENGTH] = c;
    00447             }
    00448             s = (s + 1) & (LZSS_RING_LENGTH - 1);
    00449             r = (r + 1) & (LZSS_RING_LENGTH - 1);
    00450             InsertNode(pWork, r );
    00451         }
    00452
    00453         while ( i++ < LastMatchLen )
    00454         {
    00455             DeleteNode(pWork, s );
    00456             s = (s + 1) & (LZSS_RING_LENGTH - 1);
    00457             r = (r + 1) & (LZSS_RING_LENGTH - 1);
    00458             if ( --Len ) InsertNode(pWork, r );
    00459         }
    00460     }
    00461     while ( Len > 0 );
    00462
    00463     //--------------------------------------------------------------
    00464     // 後処理
    00465     //--------------------------------------------------------------
    00466     if ( CodePtr > 1 )
    00467     {
    00468         (*pDstSize) += CodePtr;
    00469         // 展開先バッファ溢れ
    00470         if ( SrcCheckSize > (*pDstSize) )
    00471         {
    00472             //バッファが漏れているツーに
    00473             CompressByte += CodePtr;
    00474             if(CompressByte >= DstSize){
    00475                 return edk_BufferOverFlow;
    00476             }
    00477             for ( i = 0; i < CodePtr; i++ )
    00478             {
    00479                 *(pDstData++) = Code[i];
    00480
    00481             }
    00482         }
    00483     }
    00484
    00485 //EXIT:
    00487     //*CompressedByte = CompressByte;
    00488     return edk_SUCCEEDED;
    00489 }

static void InitTree | ( | DKC_LZSS * | pWork | ) | `[static]`

| 圧縮・解凍用の木のデータを初期化します。 dkcLZSS.c の 62 行で定義されています。 参照先 dkc_LZSS::Dad, LZSS_RING_LENGTH, NIL, と dkc_LZSS::RSon. 参照元 Encode().
    00063 {
    00064     long i;
    00065     for (i = LZSS_RING_LENGTH+1; i <= LZSS_RING_LENGTH+256; i++ )
    00066     {
    00067         pWork->RSon[i] = NIL;
    00068     }
    00069
    00070     for (i = 0; i < LZSS_RING_LENGTH; i++ )
    00071     {
    00072         pWork->Dad[i] = NIL;
    00073     }
    00074 }

static void InsertNode | ( | DKC_LZSS * | pWork,
|  | long | r
| ) | `[static]`

  | 節を木に挿入します。 引数:
  | r | [in] 挿入するデータ
dkcLZSS.c の 83 行で定義されています。 参照先 dkc_LZSS::Dad, dkc_LZSS::LSon, LZSS_LONGEST_MATCH, LZSS_RING_LENGTH, dkc_LZSS::MatchLen, dkc_LZSS::MatchPos, NIL, dkc_LZSS::RSon, dkc_LZSS::Text, と TRUE. 参照元 Encode().
    00084 {
    00085     long cmp = 1;
    00086     unsigned char *pKey = &pWork->Text[r];
    00087     long p = LZSS_RING_LENGTH + 1 + pKey[0];
    00088     long i = 0;
    00089
    00090     pWork->RSon[r] = pWork->LSon[r] = NIL;
    00091     pWork->MatchLen = 0;
    00092
    00093     while( TRUE )
    00094     {
    00095         if ( cmp >= 0 )
    00096         {
    00097             if ( pWork->RSon[p] != NIL )
    00098             {
    00099                 p = pWork->RSon[p];
    00100             }
    00101             else
    00102             {
    00103                 pWork->RSon[p] = r;
    00104                 pWork->Dad[r] = p;
    00105                 return;
    00106             }
    00107         }
    00108         else
    00109         {
    00110             if ( pWork->LSon[p] != NIL )
    00111             {
    00112                 p = pWork->LSon[p];
    00113             }
    00114             else
    00115             {
    00116                 pWork->LSon[p] = r;
    00117                 pWork->Dad[r] = p;
    00118                 return;
    00119             }
    00120         }
    00121
    00122
    00123         for ( i = 1; i < LZSS_LONGEST_MATCH; i++ )
    00124         {
    00125             cmp = pKey[i] - pWork->Text[p + i];
    00126             if ( cmp != 0 )
    00127             {
    00128                 break;
    00129             }
    00130         }
    00131
    00132         if ( i > pWork->MatchLen )
    00133         {
    00134             pWork->MatchPos = p;
    00135             pWork->MatchLen = i;
    00136             if ( pWork->MatchLen >= LZSS_LONGEST_MATCH )
    00137             {
    00138                 break;
    00139             }
    00140         }
    00141     }
    00142
    00143     pWork->Dad[r]           = pWork->Dad[p];
    00144     pWork->LSon[r]          = pWork->LSon[p];
    00145     pWork->RSon[r]          = pWork->RSon[p];
    00146     pWork->Dad[pWork->LSon[p]]  = r;
    00147     pWork->Dad[pWork->RSon[p]]  = r;
    00148
    00149     if ( pWork->RSon[pWork->Dad[p]] == p )
    00150     {
    00151         pWork->RSon[pWork->Dad[p]] = r;
    00152     }
    00153     else
    00154     {
    00155         pWork->LSon[pWork->Dad[p]] = r;
    00156     }
    00157
    00158     pWork->Dad[p] = NIL;
    00159 }