#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 )
{
for( int 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;
if( is->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;
};
};
};