/*---------------------------------------------------------------------------*
  Project:     compress/uncompress library
  File:        CXUncompression.h
  Programmer:  Makoto Takano

  Copyright 2005 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.
 *---------------------------------------------------------------------------*/

#include <dolphin/types.h>
#include <revolution/os.h>
#include <revolution/cx/CXUncompression.h>
#include "CXUtil.h"


//======================================================================
//          Expanding compressed data
//======================================================================

/*---------------------------------------------------------------------------*
  Name:         CXGetUncompressedSize

  Description:  Gets the data size after decompression.
                This function can be used for data in all compression formats handled by CX.

  Arguments:    srcp :  starting address of the compressed data

  Returns:      Data size after expansion
 *---------------------------------------------------------------------------*/
u32 CXGetUncompressedSize( const void *srcp )
{
#if defined( CX_PLATFORM_IS_BIGENDIAN )
    return CXiConvertEndian_( *(u32*)srcp ) >> 8;
#else
    return ( *(u32*)srcp >> 8 );
#endif
}


/*---------------------------------------------------------------------------*
  Name:         CXUncompressAny

  Description:  Determines the compression type from the data header and
                runs the appropriate decompression process.
                As all the decompression for compression types are linked,
                it would be good to run this function for each compression type unless
                a special compression format is used.

  Arguments:    srcp          source address
                destp         destination address

  Returns:      None.
 *---------------------------------------------------------------------------*/
void CXUncompressAny( const void* srcp, void* destp )
{
    switch ( CXGetCompressionType( srcp ) )
    {
    // Run-length compressed data
    case CX_COMPRESSION_RL:
        CXUncompressRL( srcp, destp );
        break;
    // LZ77 compressed data
    case CX_COMPRESSION_LZ:
        CXUncompressLZ( srcp, destp );
        break;
    // Huffman compressed data
    case CX_COMPRESSION_HUFFMAN:
        CXUncompressHuffman( srcp, destp );
        break;
    // Difference filter
    case CX_COMPRESSION_DIFF:
        CXUnfilterDiff( srcp, destp );
        break;
    default:
        ASSERTMSG( 0, "Unknown compressed format" );
    }
}


/*---------------------------------------------------------------------------*
  Name:         CXUncompressRL

  Description:  8-bit expanding runlength compressed data

  * Expands runlength compressed data, and writes in 8-bit units.
  - Align source address to a 4-byte boundary.

  * Data header
      u32 :4                  reserved
          compType:4          compression type  ( = 3)
          destSize:24         Data size after decoding
  
  * Flag data format
      u8  length:7            Expansion data length - 1 (When not compressed)
                              Expansion data length - 3 (Only compress when the contiguous length is 3-bytes or greater)
          flag:1              (0, 1) = (not compressed, compressed)
  
  Arguments:    *srcp          source address
                *destp         destination address

  Returns:      None.
 *---------------------------------------------------------------------------*/
void CXUncompressRL( const void *srcp, void *destp )
{
    const u8 *pSrc  = srcp;
    u8       *pDst  = destp;
    u32      destCount = CXiConvertEndian_( *(u32*)pSrc ) >> 8;
    
    pSrc += 4;
    while ( destCount > 0 )
    {
        u8  flags  = *pSrc++;
        s32 length = flags & 0x7f;
        if ( !(flags & 0x80) )
        {   
            length++;
            destCount -= length;
            do
            {
                *pDst++ = *pSrc++;
            } while ( --length > 0 );
        }
        else
        {
            u8 srcTmp;
            
            length    += 3;
            destCount -= length;
            srcTmp    = *pSrc++;
            do
            {
                *pDst++ =  srcTmp;
            } while ( --length > 0 );
        }
    }
}


/*---------------------------------------------------------------------------*
  Name:         CXUncompressLZ
  
  Description:  8-bit expanding LZ77 compressed data
  
  * Expands LZ77 compressed data, and writes in 8-bit units.
  - Align source address to a 4-byte boundary.
  
  * Data header
      u32 :4                  reserved
          compType:4          compression type  ( = 1)
          destSize:24         Data size after decoding
  
  * Flag data format
      u8  flags               compression/no compression flag
                              (0, 1) = (not compressed, compressed)
  * Code data format (Big Endian)
      u16 length:4            Expansion data length - 3(Only compress when the match length is 3-bytes or greater)
          offset:12           match data offset - 1
  
  Arguments:    *srcp          source address
                *destp         destination address
  
  Returns:      None.
 *---------------------------------------------------------------------------*/
void CXUncompressLZ( const void *srcp, void *destp )
{
    const u8* pSrc      = srcp;
    u8*       pDst      = destp;
    u32       destCount = CXiConvertEndian_( *(u32 *)pSrc ) >> 8;
    
    pSrc += 4;
    while ( destCount > 0 )
    {
        u32 i;
        u32 flags = *pSrc++;
        for ( i = 0; i < 8; ++i )
        {
            if ( !(flags & 0x80) )
            {
                *pDst++ = *pSrc++;
                destCount--;
            }
            else
            {
                s32 length = (*pSrc >> 4) + 3;
                s32 offset = (*pSrc++ & 0x0f) << 8;
                offset = (offset | *pSrc++) + 1;
                destCount -= length;
                do
                {
                    *pDst++ = pDst[ -offset ];
                } while ( --length > 0);
            }
            if ( destCount <= 0 )
            {
                break;
            }
            flags <<= 1;
        }
    }
}


/*---------------------------------------------------------------------------*
  Name:         CXUncompressHuffman
  
  Description:  Expanding Huffman compressed data
  
  * Expands Huffman compressed data, and writes in 32-bit units.
  - Align source address to a 4-byte boundary.
  - Align the destination address to a four byte boundary.
  - The compression buffer size must be prepared in 4-byte multiples.
  
  * Data header
      u32 bitSize:4           1 data bit size (Normally 4|8)
          compType:4          compression type  ( = 2)
          destSize:24         Data size after decoding
  
  * Tree table
      u8           treeSize        tree table size/2 - 1
      TreeNodeData nodeRoot        root node
  
      TreeNodeData nodeLeft        root left node
      TreeNodeData nodeRight       root right node
  
      TreeNodeData nodeLeftLeft    left left node
      TreeNodeData nodeLeftRight   left ride node
  
      TreeNodeData nodeRightLeft   right left node
      TreeNodeData nodeRightRight  right right node
  
              �E
              �E
  
    The compress data structure follows
  
  * TreeNodeData structure
      u8  nodeNextOffset:6    Offset to the next node data - 1 (2-byte units)
          rightEndFlag:1      right node end flag
          leftEndzflag:1       Left node end flag
                              when end flag is set
                              there is data in next node
  
  Arguments:    *srcp          source address
                *destp         destination address

  Returns:      None.
 *---------------------------------------------------------------------------*/
void CXUncompressHuffman( const void *srcp, void *destp )
{
#define TREE_END 0x80
    const u32 *pSrc          = srcp;
    u32       *pDst          = destp;
    u8        *treep         = (u8 *)pSrc + 4;
    u8        *treeStartp    = treep + 1;
    u32       dataBit        = *(u8*)pSrc & 0x0FU;
    u32       destTmp        = 0;
    u32       destTmpCount   = 0;
    u32       destTmpDataNum = 4 + ( dataBit & 0x7 );
    s32       destCount      = (s32)( CXiConvertEndian_( *pSrc ) >> 8 );
    
    pSrc  = (u32*)( treep + ((*treep + 1) << 1) );
    treep = treeStartp;
    
    while ( destCount > 0 )
    {
        s32 srcCount = 32;
        u32 srcTmp   = CXiConvertEndian_( *pSrc++ );      // endian strategy
        while ( --srcCount >= 0 )
        {
            u32 treeShift = (srcTmp >> 31) & 0x1;
            u32 treeCheck = *treep;
            treeCheck <<= treeShift;
            treep = (u8*)( (((u32)treep >> 1) << 1) + (((*treep & 0x3f) + 1) << 1) + treeShift );
            if ( treeCheck & TREE_END )
            {
                destTmp >>= dataBit;
                destTmp |= *treep << (32 - dataBit);
                treep = treeStartp;
                if ( ++destTmpCount == destTmpDataNum )
                {
                    // over-access until the end of the decompression buffer is 4-byte aligned
                    *pDst++ = CXiConvertEndian_(destTmp); // endian strategy
                    destCount -= 4;
                    destTmpCount = 0;
                }
            }
            if ( destCount <= 0 )
            {
                break;
            }
            srcTmp <<= 1;
        }
    }
}


/*---------------------------------------------------------------------------*
  Name:         CXUnfilterDiff

  Description:  Decode differential filter conversion. Use 8-bit decoding.
  
    - Decodes a differential filter. Writes in 8-bit units.
    - Align source address to a 4-byte boundary.

  Arguments:    *srcp          source address
                *destp         destination address

  Returns:      None.
 *---------------------------------------------------------------------------*/
void CXUnfilterDiff( register const void *srcp, register void *destp )
{
    const u8* pSrc = srcp;
    u8*       pDst = destp;
    u32 bitSize    = *pSrc & 0xFU;
    s32 destCount  = (s32)( CXiConvertEndian_( *(u32*)pSrc ) >> 8 );
    u32 sum = 0;
    
    pSrc += 4;
    
    if ( bitSize != 1 )
    {
        // diff calculation in units of 8 bits
        do 
        {
            u8 tmp = *(pSrc++);
            destCount--;
            sum += tmp;
            *(pDst++) = (u8)sum;
        } while ( destCount > 0 );
    }
    else
    {
        // diff calculation in units of 16 bits
        do 
        {
            u16 tmp = CXiConvertEndian16_( *(u16*)pSrc );
            pSrc += 2;
            destCount -= 2;
            sum += tmp;
            *(u16*)pDst = CXiConvertEndian16_( (u16)sum );
            pDst += 2;
        } while ( destCount > 0 );
    }
}


/*---------------------------------------------------------------------------*
  Name:         CXGetCompressionHeader

  Description:  Gets header information from the first four bytes in the compression data

  Arguments:    data	a pointer to the first four bytes of data in the compressed data

  Returns:      None.
 *---------------------------------------------------------------------------*/
CXCompressionHeader CXGetCompressionHeader( const void* data )
{
#if defined( CX_PLATFORM_IS_BIGENDIAN )
    CXCompressionHeader ret;
    
    ret.compType  = (*(u8*)data & 0xF0) >> 4;
    ret.compParam = *(u8*)data & 0x0F;
    ret.destSize  = CXiConvertEndian_( *(u32*)data ) >> 8;
    return ret;
#else
    return *(CXCompressionHeader*)data;
#endif
}