D:/Zythum/DinoKod/Common/Lzw.cpp

//---------------------------------------------------------------------------------------------
//      This file is a part of "DinoKod".
//      Copyright © 2003 Dino Productions. All Rights Reserved.
//      
//      File                    : Lzw.h
//      Author                  : Sebastien LEIX        sebastien.leix@wanadoo.fr
//      Date                    : 01/01/2003
//      Modification    :
//
//---------------------------------------------------------------------------------------------
#include "Common/Assert.h"
#include "Common/Error.h"
#include "Common/Lzw.h"

KLZW    g_Lzw;

//--------------------------------------------------------------------------------------------------------------------------
KLZW::KLZW()
{
        Flush();
}

//--------------------------------------------------------------------------------------------------------------------------
KLZW::~KLZW()
{
}

//--------------------------------------------------------------------------------------------------------------------------
void KLZW::Flush()
{
        // Reset l'IO
        m_Bit = 0;
        m_nBit = 0;

        // Flush le dictionnaire
//#if _DEBUG
        memset( m_pDictionnary, 0, sizeof( m_pDictionnary ) );
//#endif _DEBUG
        m_nDictionnary = 0;
}

//--------------------------------------------------------------------------------------------------------------------------
void KLZW::Output( u8* pBufferOut, s32& OutSize, s32 MaxSize, s32 Code )
{
        KASSERT( Code <= ( pow( 2, LZW_NBITS ) - 1 ) );

        if( Code == LZW_MAX_VALUE )
        {
                if( m_nBit )
                {
                        // Flush
                        m_Bit |= 0 << ( (sizeof( m_Bit ) * 8) - (8 - m_nBit) );
                        m_nBit = 8;
                }
        }
        else
        {
                m_Bit |= Code << ( (sizeof( m_Bit ) * 8) - m_nBit - LZW_NBITS );
                m_nBit += LZW_NBITS;
        }

        while( m_nBit >= 8 )
        {
                KASSERT( OutSize < MaxSize );
                pBufferOut[OutSize++] = (u8)(( m_Bit >> ( sizeof( m_Bit ) * 8 - 8 ) ) & 0xFF);
                m_Bit <<= 8;
                m_nBit -= 8;
        }
}

//--------------------------------------------------------------------------------------------------------------------------
s32 KLZW::Input( u8* pBufferIn, s32 Size, s32 &Pos )
{
        while( m_nBit < LZW_NBITS )
        {
                m_Bit |= ( (s32)pBufferIn[Pos++] & 0xFF ) << ( ( sizeof( m_Bit ) * 8) - m_nBit - 8 );
                m_nBit += 8;
        }
        
        s32 Code = ( m_Bit >> (sizeof( m_Bit ) * 8 - LZW_NBITS ) );
        m_Bit <<= LZW_NBITS;
        m_nBit -= LZW_NBITS;

        return Code;
}

//--------------------------------------------------------------------------------------------------------------------------
void KLZW::AddBufferToDictionnary( u8* pBuffer, s32 Size )
{
        KASSERT( Size > 0 );
        KASSERT( Size < 256 );
        KASSERT( sizeof( m_pDictionnary ) > ( m_nDictionnary + Size + 1 ) );

        // Ecrit la taille
        m_pDictionnary[m_nDictionnary] = (u8)Size;
        // Puis le buffer
        memcpy( &m_pDictionnary[m_nDictionnary + 1], pBuffer, Size );
        // Incremente le pointeur de dico
        m_nDictionnary += Size + 1;
}

//--------------------------------------------------------------------------------------------------------------------------
bool KLZW::IsStringIsInDictionnary( u8* pBuffer, s32 Size )
{
        s32     n = 0;

        while( n < m_nDictionnary )
        {
                // Recherche dans le dico un buffer de meme taille
                if( m_pDictionnary[n] ==  Size )
                        if( memcmp( &m_pDictionnary[n + 1], pBuffer, Size ) == 0 )
                                return true;
                // Va au buffer suivant
                n += m_pDictionnary[n] + 1;
        }

        return false;
}

//--------------------------------------------------------------------------------------------------------------------------
s32 KLZW::GetCode( u8* pBuffer, s32 Size )
{
        s32     n = 0;
        s32     c = 0;
        
        while( n < m_nDictionnary )
        {
                // Recherche dans le dico un buffer de meme taille
                if( m_pDictionnary[n] == Size )
                        if( memcmp( &m_pDictionnary[n + 1], pBuffer, Size ) == 0 )
                                if( c < LZW_MAX_CODE )
                                        return c;
                                else
                                        KError::FatalError( NULL, "KLZW::GetCode(...) : Dictionnary full, LZW_MAX_CODE reached!" );

                // Va au buffer suivant
                n += m_pDictionnary[n] + 1;
                c ++;
        }

        return -1;
}

//--------------------------------------------------------------------------------------------------------------------------
s32 KLZW::GetBuffer( s32 Code, u8* pBuffer )
{
        s32     n = 0;
        s32     c = 0;
        while( c < Code )
        {
                if( n >= m_nDictionnary )
                {
                        pBuffer = NULL;
                        return 0;
                }

                KASSERT( n < m_nDictionnary );
                // Va au buffer suivant
                n += m_pDictionnary[n] + 1;
                c++;
        }

        memcpy( pBuffer, &m_pDictionnary[n + 1], m_pDictionnary[n] );
        return m_pDictionnary[n];
}

//--------------------------------------------------------------------------------------------------------------------------
void KLZW::Compress( u8* pBuffer, s32 Size, u8* pOutBuffer, s32* pOutSize )
{
        u8              p[1024];
        s32             s;
        s32             n;
        s32             MaxSize;

        // Init
        Flush();
        MaxSize = *pOutSize;
        *pOutSize = 0;

        // Initialise le dico
        n = 0;
        while( n < 256 )
        {
                AddBufferToDictionnary( (u8*)&n, 1 );
                n++;
        }

        n = 0;
        s = 0;
        while( n < Size )
        {
                KASSERT( sizeof( p ) > s );
                p[s++] = pBuffer[n++];
                // Est ce que la chaine est dans le dico ?
                if( !IsStringIsInDictionnary( p, s ) )
                {
                        // Sort le buffer
                        Output( pOutBuffer, *pOutSize, MaxSize, GetCode( p, s - 1 ) );
                        // Ajoute dans le dico
                        AddBufferToDictionnary( p, s );
                        p[0] = p[s-1];
                        s = 1;
                }
        }

        // Flush
        Output( pOutBuffer, *pOutSize, MaxSize, GetCode( p, s ) );
        Output( pOutBuffer, *pOutSize, MaxSize, LZW_MAX_VALUE );
        Flush();
}

//--------------------------------------------------------------------------------------------------------------------------
void KLZW::Expand( u8* pBuffer, s32 Size, u8* pOutBuffer, s32* pOutSize )
{
        u8              p[1024];
        s32             s;
        u8              P[1024];
        s32             SP;
        u8              C;
        s32             cW;
        s32             pW;

        s32             n;
        s32             Pos;
        s32             MaxSize;

        // Init
        Flush();
        MaxSize = *pOutSize;
        *pOutSize = 0;

        // Initialise le dico
        // 1
        n = 0;
        while( n < 256 )
        {
                AddBufferToDictionnary( (u8*)&n, 1 );
                n++;
        }

        n = 0;
        SP = 0;
        Pos = 0;

        // 2
        cW = Input( pBuffer, Size, Pos );

        // 3
        s = GetBuffer( cW, p );
        KASSERT( *pOutSize + s < MaxSize );
        memcpy( &pOutBuffer[*pOutSize], p, s );
        *pOutSize += s;

        while( Pos < Size )
        {
                // 4
                pW = cW;

                // 5
                cW = Input( pBuffer, Size, Pos );

                // 6
                s = GetBuffer( cW, p );
                if( IsStringIsInDictionnary( p, s ) )
                {
                        // i. Output
                        KASSERT( *pOutSize + s < MaxSize );
                        memcpy( &pOutBuffer[*pOutSize], p, s );
                        *pOutSize += s;
                        
                        // ii.
                        s = GetBuffer( pW, p );
                        memcpy( P, p, s );
                        SP = s;

                        // iii.
                        s = GetBuffer( cW, p );
                        C = p[0];
                        
                        // iv.
                        P[SP++] = C;
                        AddBufferToDictionnary( P, SP );
                }
                else
                {
                        // i.
                        s = GetBuffer( pW, p );
                        memcpy( P, p, s );
                        SP = s;

                        // ii. 
                        s = GetBuffer( cW, p );
                        C = p[0];

                        // iii.
                        P[SP++] = C;
                        AddBufferToDictionnary( P, SP );
                        KASSERT( *pOutSize + s < MaxSize );
                        memcpy( &pOutBuffer[*pOutSize], P, SP );
                        *pOutSize += SP;
                }
        }
        Flush();
}

---