饭中淹的避难所~~~~~

偶尔来避难的地方~

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  94 随笔 :: 0 文章 :: 257 评论 :: 0 Trackbacks
#pragma once

#include 
"xStream.h"

namespace xlibplus
{
    
namespace crypt{
        template 
<bool fValue, typename TThen, typename TElse>
        
struct if_then_else
        {
            typedef TThen result;
        };

        template 
<typename TThen, typename TElse>
        
struct if_then_else<false, TThen, TElse>
        {
            typedef TElse result;
        };

        template 
<int nBits>
        
struct UnsignedTypeSelector
        {
            typedef typename if_then_else
<(nBits<=8), unsigned char, typename if_then_else<(nBits<=16), unsigned short, unsigned int>::result >::result Type;
        };

        template 
<int nMaxCodeBits = 12>
        
class xLzwDict
        {
            typedef typename UnsignedTypeSelector
<nMaxCodeBits>::Type TCode;
            typedef 
struct tagEntry
            {
                TCode nPrefix;
                TCode nPostfix;
                TCode nFirstChild;
                TCode nNext;
            }t_Entry;
        
public:
            xLzwDict( 
int nCharBits ) : m_nCodeStartIndex( (1<<nCharBits)+2 ), m_nClearCode( (1<<nCharBits) ), m_nEndCode( (1<<nCharBits)+1 ), m_nCharBits(nCharBits)
            {
                Reset();
            }

            
~xLzwDict()
            {
            }

            
bool IsDefinedCode( TCode nValue ) const
            {
                
return (IsCode( nValue ) && m_Entries[nValue].nPostfix != m_nEndCode );
            }

            
bool IsCode( TCode nValue ) const
            {
                
return (nValue >= m_nCodeStartIndex);
            }

            TCode GetFirstChar( TCode nCode ) 
const
            {
                
while( IsCode( nCode ) )
                    nCode 
= m_Entries[nCode].nPrefix;
                
return nCode;
            }

            TCode Search( TCode nPrefix, TCode nPostfix ) 
const
            {
                t_Entry 
& top = m_Entries[nPrefix];

                TCode nCode 
= top.nFirstChild;

                
while( nCode != 0 )
                {
                    
if( m_Entries[nCode].nPostfix == nPostfix )return nCode;
                    nCode 
= m_Entries[nCode].nNext;
                }

                
return 0;
            }

            TCode Add( TCode nPrefix, TCode nPostfix )
            {
                
if( m_nCodeIndex >= (1<<nMaxCodeBits) )return 0;

                t_Entry 
& top = m_Entries[nPrefix];
                t_Entry 
& cur = m_Entries[m_nCodeIndex];

                cur.nPrefix 
= nPrefix;
                cur.nPostfix 
= nPostfix;
                cur.nNext 
= top.nFirstChild;
                cur.nFirstChild 
= 0;
                top.nFirstChild 
= m_nCodeIndex;

                TCode nCode 
= m_nCodeIndex;

                
++m_nCodeIndex;

                
if( m_nCodeIndex >= (1 << m_nCodeBits) && m_nCodeBits < nMaxCodeBits ) ++ m_nCodeBits;

                
return nCode;
            }

            
void Reset()
            {
                m_nCodeIndex 
= m_nCodeStartIndex;

                m_nCodeBits 
= _CalcCodeBits( m_nCodeIndex );

                UINT nCharCount 
= (1<<m_nCharBits);

                
for( UINT n = 0;n < nCharCount;n ++ )
                {
                    m_Entries[n].nPrefix 
= n;
                    m_Entries[n].nPostfix 
= 0;
                    m_Entries[n].nNext 
= 0;
                    m_Entries[n].nFirstChild 
= 0;
                }

                
for( UINT n = nCharCount;n < (1<<nMaxCodeBits); ++n )
                {
                    m_Entries[n].nPrefix 
= m_nEndCode;
                    m_Entries[n].nPostfix 
= m_nEndCode;
                    m_Entries[n].nFirstChild 
= 0;
                    m_Entries[n].nNext 
= 0;
                }
            }

            TCode GetPrefix( TCode nCode ) 
const { 
                
if( nCode >= m_nCodeIndex )return 0;
                
return m_Entries[nCode].nPrefix;
            }

            TCode GetPostfix( TCode nCode ) 
const {
                
if( nCode >= m_nCodeIndex )return 0;
                
return m_Entries[nCode].nPostfix;
            }

            
int GetCodeBits() const { return m_nCodeBits;}
            TCode GetClearCode() 
const { return m_nClearCode;}
            TCode GetEndCode() 
const { return m_nEndCode;}
            TCode GetCodeIndex() 
const { return m_nCodeIndex;}
        
protected:
            
int _CalcCodeBits( TCode nCode )
            {
                
forint i = 1;i <= nMaxCodeBits;i ++ )
                {
                    
if( nCode < (1<<i) )return i;
                }
                
return 1;
            }


            t_Entry m_Entries[(
1<<nMaxCodeBits)];

            TCode m_nCodeIndex;
            
const TCode m_nCodeStartIndex;
            
const TCode m_nClearCode;
            
const TCode m_nEndCode;
            
int m_nCodeBits;
            
const int m_nCharBits;
        };


        template 
<int nMaxCodeBits, bool fDynamicBits = true>
        
class xLzw
        {
            typedef xLzwDict
<nMaxCodeBits> TDict;
            typedef typename UnsignedTypeSelector
<nMaxCodeBits>::Type TCode;

            template 
<bool fDynamic>
            inline 
int _GetCodeBits(TDict & dict) const 
            {
                
return dict.GetCodeBits();
            }
            template 
<>
            inline 
int _GetCodeBits<false>(TDict & dict) const 
            {
                
return nMaxCodeBits;
            }
        
public:
            xLzw( 
int nCharBits ) : m_nCharBits( nCharBits ) {}
            
~xLzw() {}

            
void Encode( IIStream * is, IOStream * os, TDict & dict )
            {
                TCode nPrefix;
                TCode nPostfix;
                TCode nCode;

                
ifis->Eof() )return;

                xIBitStream bis( 
is );
                xOBitStream bos( os );

                bis.Read( 
&nPrefix, m_nCharBits );

                
while!bis.Eof() )
                {
                    bis.Read( 
&nPostfix, m_nCharBits );
                    
                    nCode 
= dict.Search( nPrefix, nPostfix );

                    
if( nCode == 0 )
                    {
                        bos.Write( nPrefix, _GetCodeBits
<fDynamicBits>(dict) );
                        nCode 
= dict.Add( nPrefix, nPostfix );
                        
if( nCode == 0 )
                        {
                            bos.Write( dict.GetClearCode(), _GetCodeBits
<fDynamicBits>(dict) );
                            dict.Reset();
                        }
                        nPrefix 
= nPostfix;
                    }
                    
else
                    {
                        nPrefix 
= nCode;
                    }
                }

                bos.Write( nPrefix, _GetCodeBits
<fDynamicBits>(dict) );
                bos.Flush();
            }

            
void OutputCode( TCode nCode, xOBitStream & os, TDict & dict )
            {
                
if( nCode > dict.GetEndCode() )
                {
                    OutputCode( dict.GetPrefix( nCode ), os, dict );
                    OutputCode( dict.GetPostfix( nCode ), os, dict );
                }
                
else
                    os.Write( nCode, m_nCharBits );
            }

            
void Decode( IIStream * is, IOStream * os, TDict & dict )
            {
                TCode nCode 
= 0;
                TCode nOldCode 
= dict.GetEndCode();
                TCode nResult 
= 0;
                TCode nClearCode 
= dict.GetClearCode();
                TCode nEndCode 
= dict.GetEndCode();

                xIBitStream bis( 
is );
                xOBitStream bos( os );

                
while!bis.Eof() )
                {
                    bis.Read( 
&nCode, _GetCodeBits<fDynamicBits>(dict) );

                    
if( nCode == nEndCode )
                        
break;
                    
else if( nCode == nClearCode )
                    {
                        dict.Reset();
                        nOldCode 
= nEndCode;
                        
continue;
                    }
                    
else
                    {
                        
if( nCode < dict.GetCodeIndex() )
                        {
                            OutputCode( nCode, bos, dict );
                            
if( nOldCode != nEndCode )
                                nResult 
= dict.Add( nOldCode, dict.GetFirstChar( nCode ) );
                        }
                        
else if( nCode > dict.GetCodeIndex() )
                        {
                            
return;
                        }
                        
else
                        {
                            TCode nFirstChar 
= dict.GetFirstChar( nOldCode );
                            OutputCode( nOldCode, bos, dict );
                            OutputCode( nFirstChar, bos, dict );
                            nResult 
= dict.Add( nOldCode, dict.GetFirstChar( nOldCode ) );
                        }
                    }
                    nOldCode 
= nCode;
                }

                bos.Flush();
            }
        
private:
            
const int m_nCharBits;
        };
    };
};
posted on 2009-01-09 09:15 饭中淹 阅读(1519) 评论(1)  编辑 收藏 引用

评论

# re: xLibPlus专题(2) - LZW算法 可用于GIF編解碼 2009-01-11 23:55 silvasaga
头儿, 我来支持你下
这是你最近写的吗?  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理