/*---------------------------------------------------------------------------*
  Project:  NitroSDK - tools - nitroCompLib
  File:     nitroCompLib.c

  Copyright 2003,2004 Nintendo.  All rights reserved.

  These coded instructions, statements, and computer programs contain
  proprietary information of Nintendo of America Inc. and/or Nintendo
  Company Ltd., and are protected by Federal copyright law.  They may
  not be disclosed to third parties or copied or duplicated in any form,
  in whole or in part, without the prior written consent of Nintendo.

  $Log: nitroCompLib.c,v $
  Revision 1.7  2004/10/08 04:31:52  takano_makoto
  Fixed bug in debug extraction routine.

  $NoKeywords: $
 *---------------------------------------------------------------------------*/

#include "nitroCompLib.h"

#undef _DEBUG
#ifdef _DEBUG
#define new DEBUG_NEW
#define DEBUG_PRINT
// #define DEBUG_PRINT_DIFFFILT
#define DEBUG_PRINT_RL
// #define DEBUG_PRINT_HUFF
// #define DEBUG_PRINT_LZ
// #define DEBUG_PRINT_DATAMATCH
#endif


#ifdef __cplusplus
#define EXTERN extern "C" 
#define STATIC
#else
#define EXTERN
#define STATIC static
#endif


#ifdef DEBUG_PRINT
#define dbg_printf fprintf
#else
#define dbg_printf dummy
#endif

#ifdef DEBUG_PRINT_DIFFFILT
#define dbg_printf_dif fprintf
#else
#define dbg_printf_dif dummy
#endif

#ifdef DEBUG_PRINT_RL
#define dbg_printf_rl fprintf
#else
#define dbg_printf_rl dummy
#endif

#ifdef DEBGU_PRINT_HUFF
#define dbg_printf_huff fprintf
#else
#define dbg_printf_huff dummy
#endif

#ifdef DEBGU_PRINT_LZ
#define dbg_printf_lz fprintf
#else
#define dbg_printf_lz dummy
#endif

#ifdef DEBUG_PRINT_DATAMATCH
#define dbg_printf_match fprintf
#else
#define dbg_printf_match dummy
#endif

void dummy(void *fp, ...) {}

#define DIFF_CODE_HEADER        (0x80)
#define RL_CODE_HEADER          (0x30)
#define LZ_CODE_HEADER          (0x10)
#define HUFF_CODE_HEADER        (0x20)
#define CODE_HEADER_MASK        (0xF0)



//==================================================================================
// Global Variable Declaration
//==================================================================================
static  u8      *pCompBuf[ 2 ];       // double buffer used during compression process
static  u8       compBufNo = 1;     // shows available double buffer
static  char    *pCompList;         // compList current reference point

//==================================================================================
// Prototype declaration
//==================================================================================
STATIC u32      RawWrite(       u8 *srcp, u32 size, u8 *dstp);
STATIC u32      DiffFiltWrite(  u8 *srcp, u32 size, u8 *dstp, u8 diffBitSize);
STATIC u32      RLCompWrite(    u8 *srcp, u32 size, u8 *dstp);
STATIC u32      LZCompWrite(    u8 *srcp, u32 size, u8 *dstp, u8 lzSearchOffset);
STATIC u32      HuffCompWrite(  u8 *srcp, u32 size, u8 *dstp, u8 huffBitSize);

STATIC s32      RawRead(        u8 *srcp, u32 size, u8 *dstp);
STATIC s32      DiffFiltRead(   u8 *srcp, u32 size, u8 *dstp, u8 diffBitSize);
STATIC s32      RLCompRead(     u8 *srcp, u32 size, u8 *dstp);
STATIC s32      LZCompRead(     u8 *srcp, u32 size, u8 *dstp);
STATIC s32      HuffCompRead(   u8 *srcp, u32 size, u8 *dstp, u8 huffBitSize);

/*
//==================================================================================
// Functions for DLL
//==================================================================================
EXTERN BOOL WINAPI DllMain( HINSTANCE hDLL, DWORD dwReason, LPVOID lpReserved)
{
    return TRUE;
}
*/

//----------------------------------------------------------------------------------
//  Secures memory region for putting data after compression
//    Secures an area twice the size of data before compression
//----------------------------------------------------------------------------------
EXTERN u8 * __stdcall nitroCompMalloc(u32 size) 
{
    return (u8 *)malloc( size * 3 + 512 );
}

//----------------------------------------------------------------------------------
//  Releases the memory area where the data was placed after compression
//----------------------------------------------------------------------------------
EXTERN void __stdcall nitroCompFree(u8 *p) 
{
    if ( p != NULL ) {
        free( (void *)p );
        p = NULL;
    }
}

//------------------------------------------------------------
//  Data compression
//------------------------------------------------------------
EXTERN u32  __stdcall nitroCompress(u8 *srcp, u32 size, u8 *dstp, char *compList, u8 rawHeaderFlag)
{
    u32      dataSize, nextDataSize;    // Compression data size (bytes)
    u8      *pReadBuf;                  // Pointer that indicates the first address of the compression data.
    u8       bitSize;                   // Unit suitable for difference filter, Huffman encoding.
    char     str[16];
    u16      i,j;
    u8       lzSearchOffset;

//  pCompBuf[0] = (u8 *)malloc(size*2 + 4 + 256*2);     // Because the worst Huffman size is size*2 + 4 + 256*2,
//  pCompBuf[1] = (u8 *)malloc(size*2 + 4 + 256*2);     // other compression or adding a data header could make											this insufficient.
    pCompBuf[0] = (u8 *)malloc( size * 3 + 256 * 2 );     
    pCompBuf[1] = (u8 *)malloc( size * 3 + 256 * 2 );
    pReadBuf    = pCompBuf[0];
    compBufNo   = 1;                // Important!! If you do not do this, you will have problems the second time you call nitroCompress.

    // malloc check
    if ( pCompBuf[0] == NULL || pCompBuf[1] == NULL ) {
        fprintf(stderr, "Error: Memory is not enough.\n");
        exit(1);
    }

    dataSize = size;

    // Process to add a NULL header (pseudo header for data before it is compressed)
    if ( rawHeaderFlag )  {
        dataSize        += 4;
        *(u32 *)pReadBuf =  size << 8 | 0;  // Data header
        memcpy( &pReadBuf[4], srcp, size );
    } else {
        memcpy( pReadBuf, srcp, size );
    }

    pCompList = compList;       // Points to the array that holds the compression sequence.

    // Loop while there are elements in the array that holds the compression sequence.
    while (1) {
        switch (*pCompList) {
        case 'd':  
            {
                pCompList++;            // 8 or 16 comes after 'd' 
                str[0] = *pCompList;
                if (*pCompList == '1') {
                    pCompList++;
                    str[1] = *pCompList;
                    str[2] = '\n';
                }
                bitSize = atoi(str);    // Stores in units that are suitable for the difference filter.
                str[0] = str[1] = '\n';
                        
                dbg_printf(stderr,"nitroCompress  Diff %d\n",bitSize);
                        
                if ((bitSize == 16) && (dataSize & 0x01)) {
                    fprintf(stderr, "16-bit differencial filter must be 2-byte allignment.\n");
                    exit(1);
                }
                nextDataSize = DiffFiltWrite(  pReadBuf,dataSize,pCompBuf[compBufNo],bitSize);
            }
            break;

        case 'r':   
            {
                dbg_printf( stderr,"nitroCompress  RL\n" );
                        
                nextDataSize = RLCompWrite( pReadBuf, dataSize, pCompBuf[ compBufNo ] );
            }
            break;

        case 'l':   
            {
                pCompList++;
                i = 0;
                while ( isdigit(*pCompList) ) {
                    str[i] = *pCompList;
                    pCompList++;
                    i++;
                    if ( i == 15 ) {
                        break;
                    }
                }
                str[i] = '\n';
                pCompList--;
                lzSearchOffset = (u8)atoi(str);   // Truncate to round large values.
                for ( j = 0; j < i; j++ ) {
                    str[j] = '\n';
                }
                dbg_printf( stderr, "nitroCompress  L %d\n", lzSearchOffset );

                nextDataSize = LZCompWrite( pReadBuf, dataSize, pCompBuf[compBufNo], lzSearchOffset );
            }
            break;

        case 'h':
            {
                pCompList++;            // 4 or 8 comes after 'h'
                str[0]  = *pCompList;
                str[1]  = '\n';
                bitSize = atoi(str);    // 4 or 8
                str[0] = '\n';

                dbg_printf( stderr, "nitroCompress  Huff %d\n", bitSize );

                nextDataSize = HuffCompWrite( pReadBuf, dataSize, pCompBuf[compBufNo], bitSize );
            }
            break;
        //-----------------------------------------
        // Compression end  (*CompTypeBufp is NULL)
        default:    
            {
                dbg_printf( stderr, "nitroCompress  raw\n" );

                RawWrite(pReadBuf, dataSize, dstp);
                if ( pCompBuf[0] != NULL ) { 
                    free( (void *)pCompBuf[0] ); 
                    pCompBuf[0] = NULL; 
                }
                if (pCompBuf[1] != NULL) { 
                    free( pCompBuf[1] ); 
                    pCompBuf[1] = NULL; 
                }
                return dataSize;
    
            }
        }
        // One more loop
        pReadBuf    =   pCompBuf[ compBufNo ];
        compBufNo   ^=  0x01;
        dataSize    =   nextDataSize;
        pCompList++;
    }
}


//===========================================================================
//  Copy compression data
//===========================================================================
STATIC u32 RawWrite(u8 *srcp, u32 size, u8 *dstp)
{
    u32 i;

    dbg_printf( stderr, "RawWrite\tsize=%d\n\n",size );

    for ( i = 0; i < size - 1; i++ ) {
        *dstp = *srcp;
        dstp++; 
        srcp++;
    }
    *dstp = *srcp;

    return size;
}


//===========================================================================
//  Difference filter
//===========================================================================
STATIC u32 DiffFiltWrite( u8 *srcp, u32 size, u8 *dstp, u8 diffBitSize )
{
    u32  DiffCount;     // Compression data size in bytes
    u32  i;

    u16 *src16p = (u16 *)srcp;
    u16 *dst16p = (u16 *)dstp;

    dbg_printf_dif( stderr, "DiffFiltWrite\tsize=%d\tdiffBitSize=%d\n", size, diffBitSize );

    *(u32 *)dstp = size << 8 | ( DIFF_CODE_HEADER | diffBitSize / 8 );    // data header

    DiffCount = 4;

    if (diffBitSize == 8) 
    {
#ifdef DEBUG_PRINT_DIFFFILT
        for ( i = 0; i < 16; i++ ) {
            dbg_printf_dif(stderr, "srcp[%d] = %x\n",i,srcp[i]);
        }
#endif
        dstp[DiffCount] = srcp[0];                  // top table only without diffs
        DiffCount++;
        for ( i = 1; i < size; i++, DiffCount++ ) 
        {
            dbg_printf_dif( stderr, "dstp[%x] = srcp[%d]-srcp[%d] = %x - %x = %x\n", 
                            DiffCount, i, i - 1, srcp[i], srcp[i-1], srcp[i] - srcp[i-1] );
            
            dstp[DiffCount]     = srcp[i] - srcp[ i - 1 ];  // diff data storage
        }
    } 
    else // 16-bit size 
    {
        dst16p[DiffCount/2] = src16p[0];
        DiffCount += 2;
        for ( i = 1; i < size / 2; i++, DiffCount += 2 ) {
            dst16p[DiffCount/2] = src16p[i] - src16p[i-1];  
        }
    }

    // 4-byte border alignment
    //    0 data for alignment is not included in the data size.
    i = 0;
    while ((DiffCount+i) & 0x3) {
        dstp[DiffCount+i] = 0;
        i++;
    }

    return DiffCount;
}


//===========================================================================
//  Run length encoding (bytes)
//===========================================================================
STATIC u32 RLCompWrite      (u8 *srcp, u32 size, u8 *dstp)
{   
    u32  RLDstCount;    // Compression data size in bytes
    u32  RLSrcCount;    // Size of data that is the targeted for compression, after processing is complete (bytes)
    u8   RLCompFlag;    // For run length encoding use 1
    u8   runLength;     // Run length
    u8   rawDataLength; // Length of data that is not run
    u32  i;

    u8  *startp;        // Points to the beginning of data that is the compression target for one process loop.
    
    dbg_printf_rl( stderr, "RLCompWrite\tsize=%d\n", size );

    //  data header       (size is after extraction)
    *(u32 *)dstp    = size << 8 | RL_CODE_HEADER;     // data header
    RLDstCount      = 4;

    RLSrcCount      = 0;
    rawDataLength   = 0;
    RLCompFlag      = 0;
    
    while ( RLSrcCount < size ) 
    {
        startp = &srcp[ RLSrcCount ]; // Setting the compression target data
        
        for ( i = 0; i < 128; i++ )   // Data sized 0-127 can be expressed as 7-bit
        {
            // Reached the end of the compression target data.
            if ( RLSrcCount + rawDataLength >= size ) {
                rawDataLength = (u8)(size - RLSrcCount);
                break;
            }
            
            if ( RLSrcCount + rawDataLength + 2 < size ) {
                if ( startp[ i ] == startp[ i + 1 ] && 
                     startp[i] == startp[i+2] ) 
                {
                    RLCompFlag = 1;
                    break;
                }
            }
            rawDataLength++;
        }

        // Store data that will not be encoded.
        // If the 8th bit of the data length storage byte is 0, it not an encoding data sequence.
        // Data length is the number -1. Therefore 0-127 becomes 1-128.
        if ( rawDataLength ) {
            dstp[ RLDstCount++ ] = rawDataLength - 1;     // "Data length -1" storage (7 bits)
            for ( i = 0; i < rawDataLength; i++ ) {
                dstp[ RLDstCount++ ] = srcp[ RLSrcCount++ ];
            }
            rawDataLength = 0;
        }

        // Run length encoding
        if ( RLCompFlag )
        {
            runLength = 3;
            for ( i = 3; i < 128 + 2; i++ ) {
                // Reached the end of the data for compression
                if ( RLSrcCount + runLength >= size ) {
                    runLength = (u8)( size - RLSrcCount );
                    break;
                }
                
                // If there is a pause in the run
                if ( srcp[ RLSrcCount ] != srcp[ RLSrcCount + runLength ] ) {
                    break;
                }
                // Continuing the run
                runLength++;
            }

            // If the 8th bit of the data length storage byte is 1, it is an encoded data sequence.
            dstp[ RLDstCount++ ] = 0x80 | ( runLength - 3 );  // Add 3 from the bottom and store 3-130
            dstp[ RLDstCount++ ] = srcp[ RLSrcCount ];
            RLSrcCount          += runLength;
            RLCompFlag           = 0;
        }
    }
        
    // 4-byte border alignment
    //   0 data for alignment is not included in the data size
    i = 0;
    while ( ( RLDstCount+i ) & 0x3 ) {
        dstp[RLDstCount+i] = 0;
        i++;
    }

    return RLDstCount;
}

//===========================================================================
//  LZ77 compression
//===========================================================================
STATIC u32 LZCompWrite( u8 *srcp, u32 size, u8 *dstp, u8 lzSearchOffset )
{
    u32  LZDstCount;    // Compression data size in bytes
    u32  LZSrcCount;    // Size of data that is the target of compression, after processing is complete (bytes)
    u8   LZCompFlags;   // Flag sequence that indicates whether compression or not.
    u8  *LZCompFlagsp;  // Points to the memory region that stores LZCompFlags
    u8  *compressingDataHeadp;  // Beginning address of the current data region that is targeted for compression.
    u8  *searchp;       // Beginning address of the matching data search region
    u16  tmpOffset;     // Offset to the matching data (mid-search data)
    u8   tmpLength;     // Matching data length (mid-search data)
    u16  lastOffset;    // Offset to matching data (longest matching data at that time) 
    u8   lastLength;    // Matching data length (longest matching data at that time)
    u8   i;

    dbg_printf_lz( stderr, "LZCompWrite\tsize=%d\tlzSearchOffset=%d\n", size, lzSearchOffset );

    *(u32 *)dstp = size << 8 | LZ_CODE_HEADER;                 // data header
    LZDstCount   = 4;
    
    LZSrcCount = 0;
    while ( LZSrcCount < size )
    {
        LZCompFlags     = 0;
        LZCompFlagsp    = &dstp[ LZDstCount++ ];          // storage target of flag series
    
        // flag series is stored as 8-bit data, so 8-time loop
        for ( i = 0; i < 8; i++ )
        {
            LZCompFlags <<= 1;  // the first time (i=0) carries no special significance
            lastOffset  = 0;
            lastLength  = 0;
            compressingDataHeadp = &srcp[ LZSrcCount ];

            // VRAM is two-byte access so (since there are cases where data is read from VRAM)
            // search target data must be data from before two byte.
            //
            // offset is stored as 12-bit so less than 4096
            for ( tmpOffset = lzSearchOffset; tmpOffset <= LZSrcCount && tmpOffset <= 4096; tmpOffset++ )
            {
                if ( LZSrcCount >= size ) {
                    break;
                }
                searchp = &srcp[ LZSrcCount - tmpOffset ];    // search data region setting
                if (*searchp == *compressingDataHeadp)      // matching data found
                {
                    // data length is stored with four bits, so less than 18 (put on the 3 clog)
                    for ( tmpLength = 1; tmpLength <= 16 + 2; tmpLength++ ) {
                        if ( searchp[ tmpLength ] != compressingDataHeadp[ tmpLength ] ) {
                            break;
                        }
                    }
                    if ( tmpLength > 16 + 2 ) {
                        tmpLength = 18; // so it doesn't become 19
                    }
                    if ( LZSrcCount + tmpLength >= size ) {
                        tmpLength = (u8)(size - LZSrcCount);
                    }
                    // update the longest matching data
                    if ( tmpLength >= 3 && tmpLength > lastLength ) {
                        lastOffset   = tmpOffset;
                        lastLength   = tmpLength;
                        LZCompFlags |= 0x01;
                    }
                }
            }
            // storage of LZCompFlags one compressed data
            if ( LZSrcCount < size ) {
                if ( (LZCompFlags & 0x01) == 0 ) {  // no compression
                    dstp[ LZDstCount++ ]  = srcp[ LZSrcCount++ ];
                } else {
                    // offset is separated into top four bits and bottom eight bits and stored
                    dstp[ LZDstCount++ ]   = (lastLength - 3) << 4 | (lastOffset - 1) >> 8;
                    dstp[ LZDstCount++ ]   = (lastOffset - 1) & 0xff;
                    LZSrcCount          += lastLength;
                }
            }
        }   // 8-time loop ends
        *LZCompFlagsp   = LZCompFlags;                  // store flag series
    }

    // four byte boundary alignment
    //   don't include data 0 for alignment in data size
    i = 0;
    while ( (LZDstCount + i) & 0x3 ) {
        dstp[ LZDstCount + i ] = 0;
        i++;
    }

    return LZDstCount;
}

//===========================================================================
//  Huffman Encoding
//===========================================================================
#define HUFF_END_L  0x80
#define HUFF_END_R  0x40

STATIC void HuffUpdateParentDepth(u16 leftNo, u16 rightNo);
STATIC void HuffMakeCode(u16 nodeNo, u32 paHuffCode);
STATIC u8    HuffCountHWord(u16 nodeNo);
STATIC void HuffMakeHuffTree(void);
STATIC void HuffMakeSubsetHuffTree(u16 huffTreeNo, u8 rightNodeFlag);
STATIC u8    HuffRemainingNodeCanSetOffset(u8 costHWord);
STATIC void HuffSetOneNodeOffset(u16 huffTreeNo, u8 rightNodeFlag);

typedef struct {
    u16 No;         // Data No
    u32 Freq;       // Frequency it appears
    s16 PaNo;       // Parent No 
    s16 ChNo[2];    // Child No (0: left side, 1: right side)
    u16 PaDepth;    // Parent node depth
    u16 LeafDepth;  // Depth to leaf
    u32 HuffCode;   // Huffman code
    u8  Bit;        // Node bit data
    u16 HWord;      // For each intermediate node, the memory capacity required to Hufftree store the portion of the tree that uses the node as a root.
} HuffData;

static  HuffData    HuffTable[512];
static  HuffData    HuffTableInitData   = {0, 0, 0, {-1, -1}, 0, 0, 0, 0, 0};

static  u8          HuffTreeTop;        // HuffTreeTop number
static  u8          HuffTree[256][2];
typedef struct {
    u8  leftOffsetNeed;     // If offset is required to left child node, 1
    u8  rightOffsetNeed;    // Right...
    u16 leftNodeNo;         // Left child node No
    u16 rightNodeNo;        // Right...
} HuffTreeCtrlData;
static  HuffTreeCtrlData    HuffTreeCtrl[256];
static  HuffTreeCtrlData    HuffTreeCtrlInitData = {1, 1, 0, 0};

static  u16         huffDataNum;    // encoded data type  16 if 4-bit encoded  256 if 8-bit
static  u16         rootNo;         // root No of binary tree


STATIC u32 HuffCompWrite( u8 *srcp, u32 size, u8 *dstp, u8 huffBitSize )
{
    u32 HuffDstCount;       // compressed data byte size
    u8  tmp;
    u16 nodeNum;            // Number of valid nodes
    u16 tableTop;           // Table top number when the table was created
    s32 leftNo, rightNo;    // Node No when the binary tree was created.
    u32 i,ii,iii;
    u8  srcTmp;
    u32 bitStream = 0;
    u32 streamLength = 0;

    dbg_printf_huff( stderr, "HuffCompWrite\tsize=%d\thuffBitSize=%d\n", size, huffBitSize );

    huffDataNum = 1 << huffBitSize; // 8->256, 4->16
    tableTop    = huffDataNum;

    // table initialization
    //  subscript :   0  ~ 15(255)    : encoding target data information (8-bit encoding)
    //              16 ~ 31(511)    : information for creating binary tree 
    for ( i = 0; i < (u16)(huffDataNum * 2); i++ ) 
    {
        HuffTable[i]    = HuffTableInitData;
        HuffTable[i].No = (u16)i;
    }
    
    // occurrence rate check
    if ( huffBitSize == 8 ) 
    {                 
        for (i=0; i<size; i++) 
        {
            HuffTable[srcp[i]].Freq++;          // 8-bit encoding
        }
    }
    else 
    {                    
        for ( i = 0; i < size; i++ ) 
        {                                                           // 4-bit encoding        
//          tmp =  srcp[i] & 0x0f;          HuffTable[tmp].Freq++;  // stores from bottom four bits to destination
//          tmp = (srcp[i] & 0xf0) >> 4;    HuffTable[tmp].Freq++;
            tmp = (srcp[i] & 0xf0) >> 4;    HuffTable[tmp].Freq++;  // Begin storing from upper 4 bits// either is OK
            tmp =  srcp[i] & 0x0f;          HuffTable[tmp].Freq++;  // The concern is the encoding floor
        }
    }

    // Create tree table
    leftNo = rightNo = -1;
    while (1) 
    {
        // Find 2 partial tree vertexes with the lowest Freq. You should always be able to find 1.
        // Search for a child vertex (left)
        for ( i = 0; i < tableTop; i++ ) {
            if ( (HuffTable[i].Freq != 0) && (HuffTable[i].PaNo == 0) ) {
                leftNo = i; 
                break;
            }
        }
        for ( i = (u16)leftNo; i < tableTop; i++ ) {
            if ( (HuffTable[i].Freq != 0) &&
                 (HuffTable[i].PaNo == 0) &&
                 (HuffTable[i].Freq < HuffTable[leftNo].Freq) ) 
            {
                leftNo = i;
            }
        }
        // Search for a child vertex (right)
        for ( i = 0; i < tableTop; i++ ) {
            if ( (HuffTable[i].Freq != 0) && 
                 (HuffTable[i].PaNo == 0) && 
                 (i != leftNo) ) 
            {
                rightNo = i; 
                break;
            }
        }
        for ( i = (u16)rightNo; i < tableTop; i++ ) {
            if ( (HuffTable[i].Freq != 0) &&
                 (HuffTable[i].PaNo == 0) && 
                 (HuffTable[i].Freq < HuffTable[rightNo].Freq) && 
                 (i != leftNo) ) 
            {
                rightNo = i;
            }
        }
        // If only found 1 stop creating table.
        if (rightNo < 0) {
            tableTop--;     
            rootNo  = tableTop; 
            nodeNum = (rootNo - huffDataNum + 1) * 2 + 1;
            break;
        }

        // Create vertex that combines left partial tree and right partial tree.
        HuffTable[tableTop].Freq    = HuffTable[leftNo].Freq + HuffTable[rightNo].Freq;
        HuffTable[tableTop].ChNo[0] = (s16)leftNo;
        HuffTable[tableTop].ChNo[1] = (s16)rightNo;
        if ( HuffTable[leftNo].LeafDepth > HuffTable[rightNo].LeafDepth ) {
            HuffTable[tableTop].LeafDepth = HuffTable[leftNo].LeafDepth + 1;
        } else {
            HuffTable[tableTop].LeafDepth = HuffTable[rightNo].LeafDepth + 1;
        }

        HuffTable[leftNo].PaNo  = HuffTable[rightNo].PaNo = tableTop;
        HuffTable[leftNo].Bit   = 0;
        HuffTable[rightNo].Bit  = 1;

        HuffUpdateParentDepth( (u16)leftNo, (u16)rightNo );

        tableTop++;
        leftNo = rightNo = -1;
    }

    // Generate Huffman code ( to HuffTable[i].HuffCode )
    HuffMakeCode( rootNo, 0x00 ); // The Huffman code is the HuffCode lower order bits masked with only the PaDepth bit number

    // For each intermediate node, calculate the memory capacity required to Hufftree store the portion of the tree that uses the node as a root.
    HuffCountHWord(rootNo);

    dbg_printf_huff( stderr, "No Freq PaNo ChNo[0] ChNo[1] PaDepth LeafDepth  HuffCode Bit HWord\n" );
#ifdef DEBUG_PRINT_HUFF
    for ( i = 0; i < (u16)(huffDataNum * 2); i++ ) 
    {
        dbg_printf_huff( stderr, "%2d %4d %4d   %4d %4d\t%d\t%d\t0x%2x\t%d\t%d\n",
                         HuffTable[i].No, 
                         HuffTable[i].Freq, 
                         HuffTable[i].PaNo, 
                         HuffTable[i].ChNo[0], 
                         HuffTable[i].ChNo[1],
                         HuffTable[i].PaDepth, 
                         HuffTable[i].LeafDepth, 
                         HuffTable[i].HuffCode, H
                         uffTable[i].Bit, 
                         HuffTable[i].HWord );
    }
#endif

    // creating HuffTree
    HuffMakeHuffTree();
    HuffTree[0][0] = --HuffTreeTop;

    dbg_printf_huff(stderr,"rootNo = %d\n",rootNo);
    dbg_printf_huff(stderr,"                 0  1\n");
#ifdef DEBUG_PRINT_HUFF
    for ( i = 0; i < 256; i++ ) 
    {
        dbg_printf_huff( stderr, "HuffTree[%3d] = %2x %2x\n", i, HuffTree[i][0], HuffTree[i][1] );
    }
#endif

    // data header
    *(u32 *)dstp = size << 8 | HUFF_CODE_HEADER | huffBitSize;
    HuffDstCount = 4;
    
    for ( i = 0; i < (u16)( (HuffTreeTop + 1) * 2 ); i++ )      // tree table
    {
        dstp[HuffDstCount++] = ((u8 *)HuffTree)[i];
    }
    
    // 4-byte boundary alignment
    //   data 0 for alignment is included in data size (by decoder algorithm)
    while ( HuffDstCount & 0x3 ) {
        if ( HuffDstCount & 0x1 ) {
            HuffTreeTop++;
            dstp[4] = dstp[4] + 1;
        }
        dstp[HuffDstCount++] = 0;
    }

    // Huffman encoding
    for ( i = 0; i < size; i++ ) {       // data compression
        if ( huffBitSize == 8 ) {         // 8-bit Huffman
            bitStream     = (bitStream << HuffTable[srcp[i]].PaDepth) | HuffTable[srcp[i]].HuffCode;
            streamLength += HuffTable[srcp[i]].PaDepth; 
            for ( ii = 0; ii < streamLength / 8; ii++ ) {
                dstp[HuffDstCount++] = (u8)(bitStream >> (streamLength - (ii + 1) * 8));
            }
            streamLength %= 8;
        }
        else // 4-bit Huffman
        {                          
            for ( ii = 0; ii < 2; ii++ ) {
//              if (ii) srcTmp = srcp[i] & 0x0f;    // lower-order four bits
//              else    srcTmp = srcp[i] >> 4;      // higher-order four bits
                if (ii) {
                    srcTmp = srcp[i] >> 4;      // higher-order four bits
                } else {
                    srcTmp = srcp[i] & 0x0F;    // lower-order four bits
                }
                bitStream     = ( bitStream << HuffTable[srcTmp].PaDepth ) | HuffTable[srcTmp].HuffCode;
                streamLength += HuffTable[srcTmp].PaDepth;  
                for ( iii = 0; iii < streamLength / 8; iii++ ) {
                    dstp[HuffDstCount++] = (u8)(bitStream >> ( streamLength - (iii + 1) * 8 ));
                }   
                streamLength %= 8;
            }
        }
    }
    if ( streamLength != 0 ) {
        dstp[ HuffDstCount++ ] = (u8)(bitStream << (8 - streamLength));
    }
    
    // 4-byte boundary alignment
    //   data 0 for alignment is included in data size 
    //   Only Huffman coding is special! To do little endian conversion, data is stored after alignment boundary data
    while ( HuffDstCount & 0x3 ) {
        dstp[HuffDstCount++] = 0;
    }
    
    for ( i = 1 + (HuffTreeTop + 1) * 2 / 4; i < (HuffDstCount / 4) + 1; i++ )  {           // little endian conversion
        tmp = dstp[i * 4 + 0];  dstp[i * 4 + 0] = dstp[i * 4 + 3];  dstp[i * 4 + 3] = tmp;  // swap
        tmp = dstp[i * 4 + 1];  dstp[i * 4 + 1] = dstp[i * 4 + 2];  dstp[i * 4 + 2] = tmp;  // swap
    }   
    
    return HuffDstCount;
}



//-----------------------------------------------------------------------
// Create Huffman code table
//-----------------------------------------------------------------------
STATIC void HuffMakeHuffTree(void)
{
    u16 i,tmp;
    s16 costHWord, tmpCostHWord;    // Cost when partial tree code table is not created. Creates partial tree code table for maximum value nodes.
    s16 costOffsetNeed, tmpCostOffsetNeed;
    s16 costMaxKey, costMaxRightFlag;       // Information for identifying minimum cost nodes from HuffTree.
    u8  offsetNeedNum;
    u8  tmpKey, tmpRightFlag;
    
    // HuffTreeCtrl initialization
    for ( i = 0; i < 256; i++ ) { HuffTree[i][0]  = HuffTree[i][1] = 0; }
    for ( i = 0; i < 256; i++ ) { HuffTreeCtrl[i] = HuffTreeCtrlInitData; }
    HuffTreeTop     = 1;
    costOffsetNeed  = 0;

    HuffTreeCtrl[0].leftOffsetNeed = 0; // Do not use (use as table size)
    HuffTreeCtrl[0].rightNodeNo = rootNo;

    while ( 1 )       // before returning 
    {   
        // node number calculation necessary for setting offset
        offsetNeedNum   = 0;
        for ( i = 0; i < HuffTreeTop; i++ ) {
            if ( HuffTreeCtrl[ i ].leftOffsetNeed ) {
                offsetNeedNum++;
            }
            if ( HuffTreeCtrl[ i ].rightOffsetNeed ) {
                offsetNeedNum++;
            }
        }

        // search for node with greatest cost
        costHWord       = -1;
        costMaxKey      = -1;
        tmpKey          = 0;
        tmpRightFlag    = 0;

        for ( i = 0; i < HuffTreeTop; i++ ) {

            tmpCostOffsetNeed   = HuffTreeTop - i;

            // cost evaluation of left child node
            if ( HuffTreeCtrl[i].leftOffsetNeed ) 
            {
                tmpCostHWord        = HuffTable[ HuffTreeCtrl[ i ].leftNodeNo ].HWord;
                
                if ( (tmpCostHWord + offsetNeedNum) > 64 ) { 
                    goto leftCostEvaluationEnd; 
                }
                if ( ! HuffRemainingNodeCanSetOffset((u8)tmpCostHWord) ) { 
                    goto leftCostEvaluationEnd; 
                }
                if ( tmpCostHWord > costHWord ) {
                    costMaxKey          = i;
                    costMaxRightFlag    = 0;
                } else if ((tmpCostHWord == costHWord) && (tmpCostOffsetNeed > costOffsetNeed)) {
                    costMaxKey          = i;
                    costMaxRightFlag    = 0;
                }
            }
leftCostEvaluationEnd: {}

            // cost evaluation of right child node
            if ( HuffTreeCtrl[ i ].rightOffsetNeed ) 
            {
                tmpCostHWord        = HuffTable[ HuffTreeCtrl[ i ].rightNodeNo ].HWord;
                
                if ( (tmpCostHWord + offsetNeedNum) > 64 ) {
                    goto rightCostEvaluationEnd;
                }
                if ( ! (HuffRemainingNodeCanSetOffset((u8)tmpCostHWord)) ) {
                    goto rightCostEvaluationEnd;
                }
                if ( tmpCostHWord > costHWord ) {
                    costMaxKey          = i;
                    costMaxRightFlag    = 1;
                } else if ( (tmpCostHWord == costHWord) && (tmpCostOffsetNeed > costOffsetNeed) ) {
                    costMaxKey          = i;
                    costMaxRightFlag    = 1;
                }
            }
rightCostEvaluationEnd: {}
        }
            
        // store parts tree in full HuffTree
        if ( costMaxKey >= 0 ) {
            HuffMakeSubsetHuffTree( (u8)costMaxKey, (u8)costMaxRightFlag );
            goto nextTreeMaking;
        } else {
            // search for necessary offset maximum node
            for ( i = 0; i < HuffTreeTop; i++ ) {
                tmp = 0;
                tmpRightFlag = 0;
                if ( HuffTreeCtrl[ i ].leftOffsetNeed ) {
                    tmp = HuffTable[ HuffTreeCtrl[ i ].leftNodeNo ].HWord;
                }
                if ( HuffTreeCtrl[ i ].rightOffsetNeed ) {
                    if ( HuffTable[ HuffTreeCtrl[ i ].rightNodeNo ].HWord > tmp ) {
                        tmpRightFlag = 1;
                    }
                }
                if ( (tmp != 0) || (tmpRightFlag) ) {
                    HuffSetOneNodeOffset((u8)i, tmpRightFlag);
                    goto nextTreeMaking;
                }
            }
        }
        return;
nextTreeMaking: {}
    }
}

//-----------------------------------------------------------------------
// Completely store partial tree in HuffTree
//-----------------------------------------------------------------------
STATIC void HuffMakeSubsetHuffTree( u16 huffTreeNo, u8 rightNodeFlag )
{
    u8 i;

    i = HuffTreeTop;
    HuffSetOneNodeOffset( huffTreeNo, rightNodeFlag );

    if ( rightNodeFlag ) {
        HuffTreeCtrl[ huffTreeNo ].rightOffsetNeed = 0;
    } else {
        HuffTreeCtrl[ huffTreeNo ].leftOffsetNeed = 0;
    }

    while ( i < HuffTreeTop ) {
        if ( HuffTreeCtrl[i].leftOffsetNeed ) {
            HuffSetOneNodeOffset( i, 0 );
            HuffTreeCtrl[i].leftOffsetNeed = 0;
        }
        if ( HuffTreeCtrl[i].rightOffsetNeed ) {
            HuffSetOneNodeOffset( i, 1 );
            HuffTreeCtrl[i].rightOffsetNeed = 0;
        }
        i++;
    }
}

//-----------------------------------------------------------------------
//Expand partial trees for the amount of data supplied, to check if the HuffTree structure is sound
//-----------------------------------------------------------------------
STATIC u8 HuffRemainingNodeCanSetOffset(u8 costHWord)
{
    u8 i;
    s16 capacity;

    capacity = 64 - costHWord; 

    // Offset number is as big as i is small, so it's good if you calculate with i=0 -> HuffTreeTop without sorting
    for ( i = 0; i < HuffTreeTop; i++ ) {
        if ( HuffTreeCtrl[ i ].leftOffsetNeed ) {
            if ( (HuffTreeTop - i) <= capacity ) {
                capacity--;
            } else {
                return 0;
            }
        }
        if ( HuffTreeCtrl[ i ].rightOffsetNeed ) {
            if ( (HuffTreeTop - i) <= capacity ) {
                capacity--;
            } else {
                return 0;
            }
        }
    }
    
    return 1;
}

//-----------------------------------------------------------------------
// Create 1 node and a Huffman code table
//-----------------------------------------------------------------------
STATIC void HuffSetOneNodeOffset( u16 huffTreeNo, u8 rightNodeFlag ) 
{
    u16 nodeNo;
    u8  offsetData = 0;

    if ( rightNodeFlag ) {
        nodeNo = HuffTreeCtrl[ huffTreeNo ].rightNodeNo;
        HuffTreeCtrl[ huffTreeNo ].rightOffsetNeed = 0;
    } else {
        nodeNo = HuffTreeCtrl[ huffTreeNo ].leftNodeNo;
        HuffTreeCtrl[ huffTreeNo ].leftOffsetNeed = 0;
    }

    // left child node
    if ( HuffTable[ HuffTable[ nodeNo ].ChNo[0] ].LeafDepth == 0 ) {
        offsetData |= 0x80;
        HuffTree[ HuffTreeTop ][0]                    = (u8)HuffTable[ nodeNo ].ChNo[0];
        HuffTreeCtrl[ HuffTreeTop ].leftNodeNo        = (u8)HuffTable[ nodeNo ].ChNo[0];
        HuffTreeCtrl[ HuffTreeTop ].leftOffsetNeed    = 0;    // offset becomes unnecessary
    } else {
        HuffTreeCtrl[ HuffTreeTop ].leftNodeNo        = HuffTable[ nodeNo ].ChNo[0];    // offset is necessary
    }

    // right child node
    if ( HuffTable[ HuffTable[ nodeNo ].ChNo[1] ].LeafDepth == 0 ) {
        offsetData |= 0x40;
        HuffTree[ HuffTreeTop ][1]                    = (u8)HuffTable[ nodeNo ].ChNo[1];
        HuffTreeCtrl[ HuffTreeTop ].rightNodeNo       = (u8)HuffTable[ nodeNo ].ChNo[1];
        HuffTreeCtrl[ HuffTreeTop ].rightOffsetNeed   = 0;    // offset becomes unnecessary
    } else {
        HuffTreeCtrl[ HuffTreeTop ].rightNodeNo       = HuffTable[ nodeNo ].ChNo[1];    // offset is necessary
    }

    offsetData |= (u8)(HuffTreeTop - huffTreeNo - 1);
    HuffTree[ huffTreeNo ][ rightNodeFlag ] = offsetData;

    HuffTreeTop++;
}


//-----------------------------------------------------------------------
// When making binary trees, when combining partial trees, add 1 to the depth of each structural node of the partial trees.
//-----------------------------------------------------------------------
STATIC void HuffUpdateParentDepth( u16 leftNo, u16 rightNo )
{
    HuffTable[ leftNo ].PaDepth++;
    HuffTable[ rightNo ].PaDepth++;
    
    if ( HuffTable[ leftNo ].LeafDepth != 0 ) {  
        HuffUpdateParentDepth( HuffTable[ leftNo ].ChNo[ 0 ], HuffTable[ leftNo ].ChNo[ 1 ] );
    }
    if ( HuffTable[ rightNo ].LeafDepth != 0) {
        HuffUpdateParentDepth( HuffTable[ rightNo ].ChNo[ 0 ], HuffTable[rightNo].ChNo[ 1 ] );
    }
}

//-----------------------------------------------------------------------
// Creating Huffman code
//-----------------------------------------------------------------------
STATIC void HuffMakeCode(u16 nodeNo, u32 paHuffCode)
{
    HuffTable[nodeNo].HuffCode = (paHuffCode << 1) | HuffTable[nodeNo].Bit;
    
    if (HuffTable[nodeNo].LeafDepth != 0) {
        HuffMakeCode(HuffTable[nodeNo].ChNo[0], HuffTable[nodeNo].HuffCode);
        HuffMakeCode(HuffTable[nodeNo].ChNo[1], HuffTable[nodeNo].HuffCode);
    }
}

//-----------------------------------------------------------------------
// Amount of data required by intermediate nodes to create HuffTree.
//-----------------------------------------------------------------------
STATIC u8 HuffCountHWord(u16 nodeNo)
{
    u8 leftHWord, rightHWord;

    switch (HuffTable[nodeNo].LeafDepth) {
    case 0:     
        return 0;
    case 1:     
        leftHWord = rightHWord = 0;
        break;
    default:    
        leftHWord   = HuffCountHWord(HuffTable[nodeNo].ChNo[0]);        
        rightHWord  = HuffCountHWord(HuffTable[nodeNo].ChNo[1]);
        break;
    }

    HuffTable[nodeNo].HWord = leftHWord + rightHWord + 1;
    return leftHWord + rightHWord + 1;
}

//##############################################################################################
//##############################################################################################
// Expansion related functions follow
//##############################################################################################
//##############################################################################################

//==================================================================================
// Expand Raw data
//==================================================================================
STATIC s32  RawRead(u8 *srcp, u32 size, u8 *dstp)
{
//  memcpy(dstp, srcp, size);
    u32 i;

    for ( i = 0; i < size - 1; i++ ) {
        *dstp = *srcp;
        dstp++; 
        srcp++;
    }
    *dstp = *srcp;

    return size;
}

//==================================================================================
// Expand difference compression data
//==================================================================================
STATIC s32  DiffFiltRead(u8 *srcp, u32 size, u8 *dstp, u8 diffBitSize)
{
    s32  DiffCount = 0;     // byte size of extracted data
    u32  i;

    u16 *src16p = (u16 *)srcp;
    u16 *dst16p = (u16 *)dstp;

    if (diffBitSize == 8) 
    {
#ifdef DEBUG_PRINT_DIFFFILT
        for ( i = 0; i < 16; i++ ) {
            dbg_printf_dif( stderr, "srcp[%d] = %x\n", i, srcp[i] );
        }
#endif
        dstp[DiffCount]     = srcp[0];                  // top data only without diff
        DiffCount++;
        for ( i = 1; i < size; i++, DiffCount++ ) {
            dbg_printf_dif( stderr, "dstp[%x] = srcp[%d]+dstp[%d] = %x + %x = %x\n",
                            DiffCount, 
                            i, 
                            i - 1, 
                            srcp[i], 
                            dstp[i - 1], 
                            srcp[i] - dstp[i - 1] );
            dstp[DiffCount]     = srcp[i] + dstp[i-1];  // diff data storage
        }
    } 
    else // 16 bit size 
    {
        dst16p[DiffCount/2] = src16p[0];
        DiffCount += 2;
        for (i=1; i<size/2; i++, DiffCount += 2) 
            dst16p[DiffCount/2] = src16p[i] + dst16p[i-1];  
    }

    // 4-byte border alignment
    //   0 data for alignment is not included in the data size.
    i = 0;
    while ((DiffCount+i) & 0x3) {
        dstp[DiffCount+i] = 0;
        i++;
    }

    return DiffCount;
}

//==================================================================================
// Expanding run length compressed data
//==================================================================================
STATIC s32  RLCompRead( u8 *srcp, u32 size, u8 *dstp )
{
    u32  RLDstCount;    // Expansion data size in bytes
    u32  RLSrcCount;    // Size of data that is targeted for expansion in bytes--after processing (bytes).
    u8   length;        // Data length
    u32  i;

    RLSrcCount  = 0;
    RLDstCount  = 0;
    while ( RLDstCount < size ) 
    {
        if ( srcp[ RLSrcCount ] & 0x80 )    // decoding process (run length encoded)
        {
            length = srcp[ RLSrcCount++ ] & 0x7f; // store data length (three geta are worn, so consider it actually +3)
            dstp[ RLDstCount++ ]  = srcp[ RLSrcCount ];
            dstp[ RLDstCount++ ]  = srcp[ RLSrcCount ];
            dstp[ RLDstCount++ ]  = srcp[ RLSrcCount ];
            for ( i = 3; i < (u8)(length + 3); i++ ) {
                dstp[ RLDstCount++ ] = srcp[ RLSrcCount ];
            }
            RLSrcCount++;
        }
        else // Copy raw data (not run length encoded)
        {
            length = srcp[ RLSrcCount++ ];    //  (same as srcp[RLSrcCount] & 0x7f)
            for ( i = 0; i < (u8)(length + 1); i++ ) {  //  +1 because data length is stored -1.
                dstp[ RLDstCount ] = srcp[ RLSrcCount ];
                RLDstCount++;
                RLSrcCount++;
            }
        }
    }
        
    // 4-byte border alignment
    //   0 data for alignment is not included in the data size.
    i = 0;
    while ( (RLDstCount + i) & 0x3 ) {
        dstp[ RLDstCount + i ] = 0;
        i++;
    }

    return RLDstCount;
}

//==================================================================================
// LZ77Compressed data extraction
//==================================================================================
STATIC s32 LZCompRead( u8 *srcp, u32 size, u8 *dstp)
{
    u32  LZDstCount;    // byte size of extracted data
    u32  LZSrcCount;    // processed data amount of extraction target data (in bytes)
    u8   compFlags;     // flag line showing presence or absence of compression
    u8   length;        // target data length  (wearing clog 3)
    u16  offset;        // matching data offset - 1 (always 2 or more)
    u8  *startp;        // matching data start address
    u32  i, j;

    LZSrcCount  = 0;
    LZDstCount  = 0;
    offset      = 0;
    length      = 0;
    
    while ( LZDstCount < size ) 
    {
        compFlags = srcp[ LZSrcCount++ ];
        for ( i = 0; i < 8; i++ ) {
            if ( compFlags & 0x80 ) // compressed
            {
                length  = (srcp[ LZSrcCount ] >> 4) + 3;      // higher order four bit, clog 3
                offset  = (srcp[ LZSrcCount ] & 0x0f) << 8;   // lower order four bit, in 11-8th bit in offset
                LZSrcCount++;
                offset |= srcp[ LZSrcCount ];
                offset++;
                LZSrcCount++;
                compFlags <<= 1;

                // extraction process
                startp  = &dstp[ LZDstCount - offset ];
                for ( j = 0; j < length; j++ ) {
                    dstp[ LZDstCount++ ] = startp[ j ];
                }
            }
            else // no compression
            {
                dstp[ LZDstCount++ ] = srcp[ LZSrcCount++ ];
                compFlags <<= 1;
            }
            // end when size reached
            if ( LZDstCount >= size )
            {
                break;
            }
        }
}
        
    // four byte boundary alignment
    //   data 0 for alignment is not included in data size
    i = 0;
    while ( (LZDstCount + i) & 0x3 ) {
        dstp[ LZDstCount + i ] = 0;
        i++;
    }
    return LZDstCount;
}

//==================================================================================
// Huffman encoded data extraction
//==================================================================================
STATIC s32  HuffCompRead( u8 *srcp, u32 size, u8 *dstp, u8 huffBitSize )
{
    u16  treeSize;  // HuffTree size * 2
    u32  HuffSrcCount;  // Size of the data that is targeted for expansion--after processing (bytes).
    u32  HuffDstCount;  // Expanded data
    u32  currentBitStream;
    u8   currentBit;
    u16  i;
    u16  treeAddr;
    u8   treeData;
    u8   preTreeData;
    u8   isUpper4bits = 0;

    treeSize        = ((*srcp) + 1) * 2;
    HuffSrcCount    = treeSize;         // Get beginning of data
    HuffDstCount    = 0;
    treeAddr        = 1;
    preTreeData     = srcp[1];

    dbg_printf_huff( stderr, "HuffSrcCount = %d\n", HuffSrcCount );

    //  Expansion process
    while (1)       // until return
    {
        currentBitStream  = srcp[HuffSrcCount++];
        currentBitStream |= srcp[HuffSrcCount++] << 8;
        currentBitStream |= srcp[HuffSrcCount++] << 16;
        currentBitStream |= srcp[HuffSrcCount++] << 24;

        for (i=0; i<32; i++) {
            currentBit  = (u8)(currentBitStream >> 31);
            currentBitStream <<= 1;

            if ( ((currentBit == 0) && (preTreeData & 0x80)) ||
                 ((currentBit == 1) && (preTreeData & 0x40)) )
            {   
                if (huffBitSize == 8) {
                    treeData     = srcp[(treeAddr*2) + currentBit];     // code data
                    dstp[HuffDstCount++] = treeData;
                } else if (isUpper4bits) {
                    treeData    |= (srcp[(treeAddr*2) + currentBit]) << 4;
                    dstp[HuffDstCount++] = treeData;
                    isUpper4bits = 0;
                } else {
                    treeData    = srcp[(treeAddr*2) + currentBit];
                    isUpper4bits = 1;
                }

                if (HuffDstCount >= size) {
                    return HuffDstCount;
                }

                treeAddr     = 1;
                preTreeData  = srcp[1];
            }
            else {                                              
                preTreeData  = srcp[(treeAddr*2) + currentBit];     // offset data
                treeAddr    += (preTreeData & 0x3f) + 1;
            }
        }
    }
}

//==================================================================================
// Data expansion control function (Because it auto expands, it will not run if at the end there is no header for raw data expansion.)
//==================================================================================
EXTERN u32 __stdcall nitroDecompress(u8 *srcp, u32 size, u8 *dstp, s8 depth)
{
    // rawData      // Data header
    // *(u32 *)pReadBuf = size << 8 | 0;
    //                      [i+3] [i+2] [i+1](size)  |  [0000 0000]
    // DiffFilt
    // *(u32 *)dstp     = size << 8 | 0x80 | diffBitSize/8;
    //                      [i+3] [i+2] [i+1](size)  |  [1000 00XX]
    // RL
    // *(u32 *)dstp     = size << 8 | 0x30;
    //                      [i+3] [i+2] [i+1](size)  |  [0011 0000]
    // LZ77
    // *(u32 *)dstp     = size << 8 | 0x10;
    //                      [i+3] [i+2] [i+1](size)  |  [0001 0000]
    // Huffman
    // *(u32 *)dstp     = size << 8 | 0x20 | huffBitSize;
    //                      [i+3] [i+2] [i+1](size)  |  [0010 XX00]
    u32 header;
    u32 srcSize, dstSize = size;
    u32 memSize = size * 3 + 256 * 2;
    u8  *pReadBuf;                  // pointer showing top locatoin of compressed data
    s8  curDepth = 0;
    s8  targetDepth;

    pCompBuf[0] = (u8 *)malloc( memSize );
    pCompBuf[1] = (u8 *)malloc( memSize );
    pReadBuf    = pCompBuf[ 0 ];

    // malloc check
    if ( pCompBuf[0] == NULL || pCompBuf[1] == NULL ) 
    {
        fprintf( stderr, "Error: Memory is not enough.\n" );
        exit(1);
    }

    compBufNo = 1;
    memcpy( pReadBuf, srcp, size );

    if ( depth < 1 ) {
        targetDepth = -1;
    } else {
        targetDepth = depth;
    }
    dbg_printf( stderr,"nitroCompress    \t(Compressed   size      is 0x%x)\n", size );

    while ( 1 ) 
    {
        // end condition when specifying targetDepth
        if ( curDepth == targetDepth ) 
        {
            dbg_printf( stderr, "nitroDecompress  Raw \t(Decompressed size will be 0x%x)\n", dstSize );
            dstSize = RawRead( pReadBuf, srcSize, dstp );

            if ( pCompBuf[0] != NULL ) { 
                free( pCompBuf[0] ); 
                pCompBuf[0] = NULL; 
            }
            if ( pCompBuf[1] != NULL ) { 
                free( pCompBuf[1] ); 
                pCompBuf[1] = NULL; 
            }
            return dstSize;
        }

        header  = *(u32 *)pReadBuf;
        srcSize = header >> 8;  // size not including header, passes to extraction function also without including header
        
        if ( memSize < srcSize ) {
            memSize = srcSize * 3 + 256 * 2;
            pCompBuf[0] = (u8 *)realloc( pCompBuf[0], memSize );
            pCompBuf[1] = (u8 *)realloc( pCompBuf[1], memSize );
            pReadBuf = pCompBuf[ compBufNo ^ 0x1 ];

        }

        switch ( header & CODE_HEADER_MASK )
        {
        case DIFF_CODE_HEADER:
            {
                dbg_printf( stderr, "nitroDecompress  Diff %d \t(Decompressed size will be 0x%x)\n", ((u8)header & 0x03) * 8, srcSize );
                dstSize = DiffFiltRead( &pReadBuf[4], srcSize, pCompBuf[compBufNo], ((u8)header & 0x03) * 8 );
            }
            break;
        case HUFF_CODE_HEADER:
            {
                dbg_printf( stderr,"nitroDecompress  Huff %d \t(Decompressed size will be 0x%x)\n",((u8)header & 0x0f), srcSize );
                dstSize = HuffCompRead( &pReadBuf[4], srcSize, pCompBuf[compBufNo], (u8)header & 0x0f );
            }
            break;
        case LZ_CODE_HEADER:
            {
                dbg_printf( stderr,"nitroDecompress  LZ \t(Decompressed size will be 0x%x)\n",srcSize );
                dstSize = LZCompRead( &pReadBuf[4], srcSize, pCompBuf[compBufNo] );
            }
            break;
        case RL_CODE_HEADER:
            {
                dbg_printf(stderr,"nitroDecompress  RL \t(Decompressed size will be 0x%x)\n",srcSize);
                dstSize = RLCompRead( &pReadBuf[4], srcSize, pCompBuf[compBufNo] );
            }
            break;
        default:
            {
                dbg_printf( stderr, "nitroDecompress  Raw \t(Decompressed size will be 0x%x)\n", srcSize );
                
                dstSize = RawRead( &pReadBuf[4], srcSize, dstp );
                if (pCompBuf[0] != NULL) 
                {
                    free(pCompBuf[0]); 
                    pCompBuf[0] = NULL; 
                }
                if (pCompBuf[1] != NULL) 
                {
                    free(pCompBuf[1]); 
                    pCompBuf[1] = NULL; 
                }
                return dstSize;
            }
        }
        // already once around
        pReadBuf    = pCompBuf[ compBufNo ];
        compBufNo  ^= 0x01;
        srcSize     = dstSize;
        curDepth++;
    }
}

//==================================================================================
// Output memory content in hex
//==================================================================================
EXTERN void __stdcall debugMemPrint(FILE* fp, u8 *str, u32 size)
{
    u32 i = 0;

    while (str) {
        fprintf(fp, "%4lx:\t0x%2x\n",i,*str);
        str++;
        i++;
        if (i >= size) {
            break;
        }
    }
}

//==================================================================================
// Output memory content in binary
//==================================================================================
EXTERN void __stdcall debugMemBitPrint( FILE* fp, u8 *str, u32 size )
{
    u32 i=0;
    u8  j;

    while ( str ) 
    {
        if ( i >= size ) {
            break;
        }
        
        fprintf( fp, "%4lx:\t0x%2x\t(binary\t", i, *str );
        for ( j = 0; j < 8; j++ ) {
            fprintf( fp, "%d", *str >> (7 - j) & 0x01 );
        }
        fprintf(fp, " )\n");
        str++;
        i++;
    }
}

//==================================================================================
// Compares data before compression and after expansion. (If expansion is done correctly, will output "DATA match".)
//==================================================================================
EXTERN int __stdcall matchingCheck( u8 *srcp, u32 srcSize, u8 *dstp, u32 dstSize )
{
    u32 minSize, i;
    u8  dataMatchFlag = 1;
    u8  sizeMatchFlag;

    sizeMatchFlag = ( srcSize == dstSize );
    if ( srcSize < dstSize ) 
    {
        minSize = srcSize;
    }
    else 
    {
        minSize = dstSize;
    }
    
    for ( i = 0; i < minSize; i++ ) 
    {
        dbg_printf_match( stderr,"src[%3x], dst[%3x] = %2x , %2x", i, i, srcp[i], dstp[i] );
        if ( srcp[i] != dstp[i] ) {
            dataMatchFlag = 0; 
            dbg_printf_match( stderr,"\t; mismatch here!" );
        }
        dbg_printf_match( stderr,"\n" );
    }

    if ( sizeMatchFlag ) { 
        fprintf(stderr, "\nSIZE match.\n");
    } else {
        fprintf(stderr, "\nSIZE mismatch!\n");
    }

    if ( dataMatchFlag ) { 
        fprintf(stderr,"DATA match.\n");
    } else { 
        fprintf(stderr,"DATA mismatch!\n"); 
    }

    if ( dataMatchFlag && sizeMatchFlag ) {
        return 1;
    } else {
        return 0;
    }
}

