#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
   BinaryBitStream
      DebugBitstream
   0  x Output ASCII bitstream
   1  0 Output (packed) binary bitstream
      1 Output (human readable) binary bitstream
*/
#ifdef DEBUG 
    #define TRACING         1
    #define ASCII_BITSTREAM 1
    #define DEBUG_BITSTREAM 1
#else 
    #ifndef TRACING
    #define TRACING         0
    #endif
    #ifndef ASCII_BITSTREAM
    #define ASCII_BITSTREAM 0
    #endif
    #ifndef DEBUG_BITSTREAM
    #define DEBUG_BITSTREAM 0
    #endif 
#endif // DEBUG

#define $ if(TRACING) // Debug Info, Cache Stats

// 0 Fast hashed searching dictionary for <prefix,code>  Table is static size
// 1 Slow linear searching dictionary for <prefix,code>  Table is dynamic size
#define DICT_LINEAR_SEARCH 0

    typedef unsigned char  u8;
    typedef unsigned short u16;
    typedef unsigned int   u32;

    enum {  END_OF_BITSTREAM = 256 };
    enum {  HASH_SIZE  = 65537 }; // smallest prime > 16-bit 

// CRC32 ____________________________________________________________________________________________________ 

    u32 aCRC32[ 256 ];

    // ========================================================================
    void CRC32_Init()
    {
        const u32 CRC32_REVERSE = 0xEDB88320;
        for( u32 byte = 0; byte <= 0xFF; byte++ )
        {
            u32 crc = byte;
            for( char bit = 0; bit < 8; bit++ )
            {
                if( crc & 1 )   crc = (crc >> 1) ^ CRC32_REVERSE;
                else            crc = (crc >> 1);
            }
            aCRC32[ byte ] = crc;
        }
    }

    // ========================================================================
    inline u32 CRC32_Begin()
    {
        return (u32)-1;
    }

    // ========================================================================
    inline u32 CRC32_Next( u32 crc, u8 byte )
    {
        crc = (crc >> 8) ^ aCRC32[ (crc ^ byte) & 0xFF ];
        return crc;
    }

    // ========================================================================
    inline u32 CRC32_End( u32 crc )
    {
        return ~crc;
    }

// Encoding: Given "string", return O(1) entry offset (its code) in array
// Decoding: Given code    , return string
// ========================================================================
struct Entry // one Dictionary Entry
{
    u32 _nHash  ; // used to prime hash of string <Prefix,Byte>  
    u16 _nCode  ; // In hashed searching we need to return its code
    u16 _nPrefix; // Prefix "String"  (either 'code/index/pointer' of preceeding string or preceeding byte 0x00..0xFF
    u8  _nByte  ; // Suffix "Character" which is appended to prefix string

    Entry( u16 prefix, u8 byte, u16 code )
    {
        _nPrefix = prefix;
        _nByte   = byte;
        CRC32(); // Alternatives: FNV http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
        _nCode   = code;
    }

    // 3-byte CRC32, will be used in hashed searching
    // ========================================================================
    void CRC32()
    {
        u32      nHash = CRC32_Begin();
        /**/     nHash = CRC32_Next( nHash, (u8)((_nPrefix >> 0) & 0xFF) ); // assume MaxCode: 16-bit
        /**/     nHash = CRC32_Next( nHash, (u8)((_nPrefix >> 8) & 0xFF) );
        /**/     nHash = CRC32_Next( nHash,       _nByte                 );
        /**/     nHash = CRC32_End( nHash );
        _nHash = nHash;
    }

    void Print(u16 code) const // <prefix,byte,code,hash>
    {
        char sFormat[ 33 ];
        memset( sFormat, 0, sizeof( sFormat ) );
        strcat( sFormat, "<" );
        strcat( sFormat, _nPrefix < END_OF_BITSTREAM
            ? " '%c',"
            : "%4d,"
        );
        strcat( sFormat, _nByte < ' '
            ? "x%02X"
            : "'%c'"
        );
        strcat( sFormat, ",#%4d,0x%08X> " );
        fprintf( stderr, sFormat, _nPrefix, _nByte, code, _nHash );
    }
};

    void DumpPrefixByte( u16 prefix, u8 byte )
    {
        if (prefix < END_OF_BITSTREAM)
        {
//            if (prefix == 0)
//                fprintf( stderr, "NULL:x00 " );
//            else
                if (prefix < ' ')
                    fprintf( stderr, "%4d:x%02X ", prefix, prefix );
                else
                    fprintf( stderr, "%4d:'%c' ", prefix, prefix );

            if( byte < ' ')
                fprintf( stderr, "%3d:x%02X ", byte, byte );
            else
                fprintf( stderr, "%3d:'%c' ", byte, byte );
        }
        else
        if (prefix == END_OF_BITSTREAM)
            fprintf( stderr, "%4d:EOF ---:--- ", prefix );
        else
        {
            fprintf( stderr, "%4d:[*] ", prefix );
            if( byte < ' ')
                fprintf( stderr, "%3d:x%02X ", byte, byte );
            else
                fprintf( stderr, "%3d:'%c' ", byte, byte );
        }
    }

// ========================================================================
class Dictionary
{
public:
    Dictionary( u32 size )
    {
        nEntry = 0;
        aEntry = (Entry*) malloc( HASH_SIZE * sizeof( Entry ) );
$       fprintf( stderr, "Dictionary size: %d bytes\n", (u32)(HASH_SIZE * sizeof( Entry )) );

        // OPTIMIZATION: It is not neccessary to pre-populate dictionary with all bytes 0x00 .. 0xFF
        // nCodeNext = 0;

        // Many codecs reserve one code/entry Code=256 in the dictionary to signal the end of the original data stream
        // The first available "string" of prefix+code starts at 257
        nCodeNext = END_OF_BITSTREAM + 1;
        nCodeBits = 0;
        nCodeMask = 0;

        nOutputBits = 0;
        tOutputCode = 0;

        nCRC32        = 0;
        nByteOriginal = 0;
        nByteCompress = 0;
        nBytePercent  = 0.0f;

        nBitsOriginal = 0;
        nBitsCompress = 0;
        nBitsPercent  = 0.0f;

        nCacheHits = 0;
        nCacheMiss = 0;
        nCacheSize = (float) HASH_SIZE; // static
        nCachePercent = 0.0f;

        nByteOriginal = size;
        nBitsOriginal = size * 8;
    }

    ~Dictionary()
    {
        if( aEntry )
            free( aEntry );
    }

    void Add( u16 prefix, u8 byte )
    {
        if( nEntry > HASH_SIZE )
            return;

        Entry e( prefix, byte, nCodeNext );

        // Fast hashed insert (random-access)
        u32 iEntry = e._nHash % HASH_SIZE; // starting entry
        int nHash  = HASH_SIZE; // max entries to search
        while( nHash-- > 0 )
        {
            if( !aEntry[ iEntry ]._nHash )
            {
                aEntry[ iEntry ] = e;
                break;
            }
            // Have a collision!  Check if next slot is available
            iEntry++;
            iEntry %= HASH_SIZE; 
        }

        // Keep track of how many bits we need to represent codes in the range [0,nCodeNext)
        // e.g.
        //    if   nCodeNext = 256
        //    then nCodeBits = 9
        //         nCodeMask = 2^9-1 = 0x1FF
        nCodeMask = 1;
        nCodeBits = 0;
        for( u32 t = nCodeNext; t > 0; t >>= 1, nCodeMask <<= 1 )
            nCodeBits++;
        nCodeMask--;

$       if( nCodeNext > END_OF_BITSTREAM)
        {
            fprintf( stderr, "+%4d  %2d &%04X ", nCodeNext, nCodeBits, nCodeMask );
            fprintf( stderr, "%5d ", nEntry );
            Entry *pEntry = &aEntry[ iEntry ];
            e.Print( pEntry->_nCode );
            fprintf( stderr, "->[%5d] ", iEntry );
        }

        nEntry++;
        nCodeNext++;
    }

    // if Dictionary[ iEntry ] == { code,prefix } then return Dictionary[ iEntry ].code
    bool Find( u16 prefix, u8 byte, u16 & iFoundCode )
    {
$       nCacheMiss = 0;
        Entry find( prefix, byte, 0 ); // only care about the hash value not the code

        // Fast hashed search (random-access)
        u32 iEntry = find._nHash % HASH_SIZE; // current/starting entry
        int nHash  = HASH_SIZE; // max entries to search
        while( nHash-- > 0 )
        {                                                   //
            if( aEntry[ iEntry ]._nHash == find._nHash )    //
            {                                               //
                iFoundCode = aEntry[ iEntry ]._nCode;       //
$               nCacheHits++;                               //
                return true;                                //
            }                                               //
$           nCacheMiss++;                                   //
            if( !aEntry[ iEntry ]._nHash )                  //
                break;                                      //
            iEntry++;                                       //
            iEntry %= HASH_SIZE;                            //
        }                                                   //
        return false;
    }

    void DumpCache( u16 prefix )
    {
        if( !nEntry )
            nCachePercent = 0.f; // cache efficiency number is meaningless when there are zero entries
        else
            nCachePercent = 100.f * (1.f - ((float)nCacheMiss / nCacheSize));

        if( nCacheMiss )
            fprintf( stderr, "miss:" );
        else
            fprintf( stderr, "Hit! " );

        fprintf( stderr, "%6d/%6d (%6.2f%%) ", nCacheMiss, (int)nCacheSize, nCachePercent );
        if( prefix )
            fprintf( stderr, "=%4d\n", prefix );
    }

    void Encode( u16 code )
    {
        nBitsCompress += nCodeBits;

#if ASCII_BITSTREAM
        if( DEBUG_BITSTREAM )
        {
            if( (code >= ' ') && (code < END_OF_BITSTREAM) )
                fprintf( stderr, " Out: '%c'", code );
            else
                fprintf( stderr, " Out:%4d", code );
        }
        printf( "%d ", code );
#else
        tOutputCode |= (((u32)(code & nCodeMask)) << nOutputBits);
        nOutputBits += nCodeBits;

$        if( DEBUG_BITSTREAM )
            fprintf( stderr, " Latch:%08X Bits:%2d ", tOutputCode, nOutputBits );

        // output Variable Bits (1-16 bits) ...
        while( nOutputBits >= 8 )
        {
            u8 byte = (tOutputCode & 0xFF);
            if( DEBUG_BITSTREAM )
                fprintf( stderr, "0x%02X %3d '%c' \n", byte, byte, byte < 32 ? '?' : byte ); // Output human readable bitstream
            else
                fputc( byte, stdout ); // Output raw binary bitstream
            tOutputCode >>= 8;
            nOutputBits -= 8;
        }
#endif // ASCII_BITSTREAM
        nByteCompress++;
$       fprintf( stderr, "\n" );
    }

    void Decode( u32 code )
    {
        u32 byte = code;
        while( byte > END_OF_BITSTREAM )
        {
            byte >>= 8;
        }
        if( DEBUG_BITSTREAM )
            fprintf( stderr, "Out: '%c'  ", byte );
        else
            fputc( byte, stdout );
    }

    void CalculateSizes()
    {
        nBytePercent = 100.f * ((float)nByteOriginal - ((float)nByteCompress)) / (float)nByteOriginal;
        nBitsPercent = 100.f * ((float)nBitsOriginal - ((float)nBitsCompress)) / (float)nBitsOriginal;
    }

    // Dynamic Array
        int    nEntry; // size
        Entry *aEntry; // data

    // Output Bits
        u32    nCodeNext; // The next entry in the dictionary will be this number ...
        u32    nCodeBits; // ... and take this many bits.  Log2( nCodeNext )
        u32    nCodeMask; // 2^nCodeBits - 1
        u32    nOutputBits; // num of bits in the tOutputCode latch
        u32    tOutputCode; // simple barrel shifter latch of the codes to output

    // Stats
        u32    nCRC32;
        u32    nByteOriginal;
        u32    nByteCompress;
        float  nBytePercent ; // Compression Ratio

        u32    nBitsOriginal;
        u32    nBitsCompress;
        float  nBitsPercent ; // Compression Ratio

        u32    nCacheHits; 
        u32    nCacheMiss; // The number of entries in the dictionary we searched looking for one entry lookup
        float  nCacheSize;
        float  nCachePercent;
};

// ========================================================================
void CompressBlock( u32 nSize, u8* pSrc )
{
    if( pSrc && (nSize > 0) )
    {
        u16        code;
        u16        prefix = *pSrc++;
        u8         byte;
        u32        crc    = CRC32_Next( CRC32_Begin(), (u8)prefix );
        u32        len    = nSize - 1;
        Dictionary dict( nSize );

$       fprintf( stderr, " Prefix  Byte   #Dict[]looks/max   Efficiency Code  #Bit Mask Entries\n" );

        while( len-- > 0 )
        {
            byte = *pSrc++;
            crc = CRC32_Next( crc, byte );
$           DumpPrefixByte( prefix, byte );

            if( dict.Find( prefix, byte, code ) )
            {
                prefix = code;
$               dict.DumpCache( prefix );
            } else {
$               dict.DumpCache( 0 );
                dict.Add( prefix, byte );
                dict.Encode( prefix );
                prefix = byte;
            }
        }
        dict.nCRC32 = CRC32_End( crc );

        byte = 0;
$       DumpPrefixByte( prefix, byte );
        dict.Encode( prefix ); // output last prefix

/*      Optimization: It is not necessary to output an End Of File marker!
        prefix = END_OF_BITSTREAM;
$       DumpPrefixByte( prefix, byte );
        dict.Encode( prefix ); // output End Of File marker
*/
        prefix = 0;
$       DumpPrefixByte( prefix, byte );
        dict.Encode( prefix ); // force flushing of END_OF_BITSTREAM

        dict.CalculateSizes();
        fprintf( stderr, "Bytes: %6.2f%%, %d -> %d \n", dict.nBytePercent, dict.nByteOriginal, dict.nByteCompress );
        fprintf( stderr, "Bits : %6.2f%%, %d -> %d \n", dict.nBitsPercent, dict.nBitsOriginal, dict.nBitsCompress );
        fprintf( stderr, "CRC32: 0x%08X\n", dict.nCRC32 );
    }
}

// ========================================================================
void Compress( u32 size, u8 *data )
{
    CompressBlock( size, data );
}

// ========================================================================
void Decompress( u32 nSize, u8 *pBuffer )
{
    if( pBuffer && (nSize > 0) )
    {
        u16        prefix = *pBuffer++;
        u8         byte = 0;
        u16        code = 0;
        Dictionary dict( 0 );

        while( prefix != END_OF_BITSTREAM )
        {
            byte = *pBuffer++;
            if( dict.Find(  prefix, byte, code ) )
            {
                // expand code
                prefix = code;
            }
            else
            {
                dict.Add( prefix, byte );
                dict.Decode( prefix );
                prefix = byte;
            }
        }
    }
}

// ========================================================================
int main( int nArg, char *aArg[] )
{
    CRC32_Init();

    fprintf( stderr, "Args: %d\n", nArg );
    fprintf( stderr, "Debug messages  : %s\n", TRACING ? "yes" : "NO" );
    fprintf( stderr, "Binary bitstream: %s\n", ASCII_BITSTREAM ? "no" : "YES" );
    if ( !ASCII_BITSTREAM )
        fprintf( stderr, "Debug  bitstream: %s\n", DEBUG_BITSTREAM ? "yes" : "NO" );
    fprintf( stderr, "String searching: %s\n", DICT_LINEAR_SEARCH ? "Linear (slow)" : "Hashed (fast)" );

    if (nArg > 1) 
    {
        for ( int iArg = 1; iArg < nArg; iArg++ )
        {
            if (strcmp( aArg[ iArg ], "-d" ) == 0) // decode
            {
                iArg++;
                u8 *pBuffer = (u8*) aArg[ iArg ];
                u32 nLen = strlen( (const char*) pBuffer );
            }
            else // encode
            {
                u8 *pBuffer = (u8*) aArg[ iArg ];
                u32 nLen = strlen( (const char*) pBuffer );

                FILE * pSrcFile = fopen( aArg[ iArg ], "rb" );
                if ( pSrcFile )
                {
                    fseek( pSrcFile, 0, SEEK_END ); 
                    nLen = ftell( pSrcFile );
                    fseek( pSrcFile, 0, SEEK_SET );
                    pBuffer = (u8*) malloc( nLen );
                    fread( (void*) pBuffer, (size_t) nLen, 1, pSrcFile );
                    fclose( pSrcFile );
                }

                Compress( nLen, pBuffer );

                if (pBuffer != (u8*)aArg[ iArg ] )
                    free( pBuffer );
            }
        }
   }
}