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

dkcLZSS.c

説明を見る。
00001 
00008 #define DKUTIL_C_LZSS_C
00009 
00010 #include "dkcLZSS.h"
00011 #include "dkcStdio.h"
00012 
00013 /*BOOL WINAPI dkcLZSSIsLZSS(DKC_LZSS_HEADER *p){
00014     return p->mSignature ==  dkcdLZSS_SIGNATURE;
00015 }*/
00016 
00017 
00018 #define NIL                     LZSS_RING_LENGTH                                                            
00019 
00020 #ifdef _MSC_VER
00021 #   pragma warning(disable:4127)
00022 #endif
00023 
00024 
00025 //=============================================================================
00033 //=============================================================================
00034 /*static BOOL GetOriginalSize( void *pSrc )
00035 {
00036     //-------------------------------------------------------------------
00037     // ヘッダ取得
00038     //-------------------------------------------------------------------
00039     LZSS_HEADER *pHeader = (LZSS_HEADER*)pSrc;
00040 
00041     //-------------------------------------------------------------------
00042     // ファイル正しいのん?
00043     //-------------------------------------------------------------------
00044     if ( pHeader->Guid[0] != 'L' ) return -1;
00045     if ( pHeader->Guid[1] != 'Z' ) return -1;
00046     if ( pHeader->Guid[2] != 'S' ) return -1;
00047     if ( pHeader->Guid[3] != 'S' ) return -1;
00048 
00049     return pHeader->OriginalSize;
00050 }
00051 */
00052 
00053 
00054 
00055 
00056 //=============================================================================
00061 //=============================================================================
00062 static void InitTree( DKC_LZSS *pWork )
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 }
00075 
00076 //=============================================================================
00082 //=============================================================================
00083 static void InsertNode( DKC_LZSS *pWork,long r )
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 }
00160 
00161 //=============================================================================
00167 //=============================================================================
00168 static void DeleteNode( DKC_LZSS *pWork,long p )    
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 }
00212 
00213 
00214 
00215 //=============================================================================
00225 //=============================================================================
00226 static BOOL Decode(DKC_LZSS *pWork,DKC_LZSS_HEADER *ph,
00227                                      const void *pSrc, void *pDst )
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 }
00297 
00298 //=============================================================================
00310 //=============================================================================
00311 static BOOL Encode(DKC_LZSS *pWork,
00312                                      const void *pSrc,unsigned long SrcSize,
00313                                      void *pDst,size_t DstSize
00314                                      , unsigned long *pDstSize,
00315                                      size_t CloseProcessSize)
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 }
00490 
00491 
00492 #ifdef _MSC_VER
00493 #   pragma warning(default:4127)
00494 #endif
00495 
00496 
00497 DKC_LZSS *WINAPI dkcAllocLZSS()
00498 {
00499     DKC_LZSS *p = dkcAllocate(sizeof(DKC_LZSS));
00500     return p;
00501 }
00502 
00503 int WINAPI dkcFreeLZSS(DKC_LZSS **p){
00504     if(NULL==p || NULL==*p) return edk_FAILED;
00505     return dkcFree((void **)p);
00506 }
00507 
00508 
00509 int WINAPI dkcLZSSDecode(DKC_LZSS *ptr,DKC_LZSS_HEADER *ph,
00510     BYTE *dest,size_t dsize,const BYTE *src,size_t ssize,ULONG sig)
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 }
00530 
00531 int WINAPI dkcLZSSEncode(DKC_LZSS *ptr,DKC_LZSS_HEADER *ph,
00532     BYTE *dest,size_t dsize,const BYTE *src,size_t ssize,
00533     size_t CloseProcessSize,ULONG sig)
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 }
00556 

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