/////////////////////////////////////////////////////////////////////////////
//                                                                         //
//         用途 : LZW For GIF 壓縮算法                                     //
//         創建 : [Sck007] / 2003-03-30                                    //
//         更新 : 2003-08-18                                               //
//         主頁 : www.tcsy.net                                             //
//         郵箱 : sck007@163.com                                           //
//                                     (c) 1996 - 2008 =TCSY= 單成坤       //
/////////////////////////////////////////////////////////////////////////////
#ifndef  __SCK_LZW_COMPRESS_H__
#define  __SCK_LZW_COMPRESS_H__
#pragma once

// 編碼程序只用到Hash表, 不需要String Table(編碼表), 因為它不需要知道
// String Table中的內容。只需要知道wPrefix + wSuffix字串是否在表中和表中的index
#define LZW_MAX_TABLE_SIZE  0x1000    // String Table(編碼表)的最大長度 (12_Bit)

// Hash表設計為:  (Prefix << 8) + Suffix 中存放的是String Table的Index
#define LZW_MAX_HASH_SIZE   0x1000FF  // (0x1000 << 8) + 0xFF (20_Bit)

#define LZW_MIN_CODE_LEN    8         // 最小代碼長度
#define LZW_CLEAR           0x100     // Clear字典重置(256)
#define LZW_END             0x101     // End編碼結束(257)

//===========================================================================
// LZW - 壓縮算法類 - Sck007
//===========================================================================
class CSckLzw
{
private:

	// 解碼程序要用到String Table - String 結構節點
	// 每個String可以形成一棵二叉樹, 此二叉樹僅有一個右節點
	// 因為wPrefix總是指向String Table中的另一位置, 而wSuffix指向0 ~ (Clear - 1)
	typedef struct tagLZW_STRING
	{
		WORD    wPrefix;              // 前綴：Old
		WORD    wSuffix;              // 后綴：Old/Code
	}
	LZW_STRING, *PLZW_STRING;

	const BYTE *m_pCurrIn;            // 輸入流當前位置
	BYTE *m_pCurrOut;                 // 輸出流當前位置
	BYTE m_byCurrBits;                // 當前階段碼長：從9位開始編碼
	WORD m_wTableIndex;               // 當前的String Table(編碼表) Index

	void Encode_WriteIndexOut(DWORD dwIndex, BYTE &byOutBit);
	WORD Decode_GetNextCode(BYTE &byInBit);
	void Decode_WriteStringOut(LZW_STRING * pString, WORD wPrefix, DWORD &dwCurrPixel);

public:

	DWORD LZW_Encode(const BYTE *InBuffer, DWORD dwLength, BYTE *OutBuffer);
	DWORD LZW_Decode(const BYTE *InBuffer, BYTE *OutBuffer);
};

// 壓縮寫String Index，最長為12位(4096，最多跨越2_BYTE)。有預留內存，須預清零
inline void CSckLzw::Encode_WriteIndexOut(DWORD dwIndex, BYTE &byOutBit)
{
	*((DWORD *)m_pCurrOut) |= (dwIndex << byOutBit); // 輸出壓縮數據
	register UINT dwSumAdd = m_byCurrBits + byOutBit;// 需要偏移數量
	m_pCurrOut += dwSumAdd / 8;                      // 直接跨越字節
	byOutBit   = dwSumAdd % 8;                       // 下次移位數量
}

// 與寫入String Index是相對應的, 最長為12位(最多跨越2-BYTE)
inline WORD CSckLzw::Decode_GetNextCode(BYTE &byInBit)
{
	register DWORD dwRet    = 0;
	register UINT  dwSumAdd = m_byCurrBits + byInBit;// 碼長至少為9

	if(dwSumAdd <= 8)                                // 在當前BYTE內
		dwRet |= *m_pCurrIn;
	else if(dwSumAdd <= 16)                          // 跨越1-BYTE
		dwRet |= *((WORD *)m_pCurrIn);
	else                                             // 跨越2-BYTE
	{
		dwRet |= *(m_pCurrIn + 2);
		dwRet <<= 16;
		dwRet |= *((WORD *)m_pCurrIn);               // 延伸的處理
	}

	m_pCurrIn += dwSumAdd / 8;                       // 跨越字節數
	byInBit    = dwSumAdd % 8;
	dwRet <<= 32 - dwSumAdd;
	dwRet >>= 32 - m_byCurrBits;                     // 左右的清零
	return (WORD)dwRet;
}

/////////////////////////////////////////////////////////////////////////////
#endif