/*<<<***************************************************************************
The MIT License (MIT)

Copyright(C) 2013 - 2015 Marc Mirti Mancinelli, Christophe Lardau and Philippe Pamart (xdcube.org)

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
////////////////////////////////////////////////////////////////////////////////
#Title: xbCompressLZSS
#Project: xdcBase
////////////////////////////////////////////////////////////////////////////////
#Author: Marc MIRTI MANCINELLI
#History:
<15/09/2013: creation.
12/02/2014: this notice inserted.
***************************************************************************>>>*/
#include "stdafx.h"

//
// lzss_compress.cpp / lzss_decompress.cpp
// (c)2002 Jonathan Bennett (jon@hiddensoft.com)
//
//

#include "xbCompressLZSS.h"

#pragma warning(push)
#pragma warning(disable: 4311) //'<function-style-cast>' : pointer truncation from 'uchar *' to 'xbNptr'

int xbLZSSfile_find(const xbLZSS_File &file1,const void *pFile2)
{
	const xbString &str2 = *(const xbString*)pFile2;
	return file1.path.Compare(str2);
}

int xbLZSSparam_find(const xbLZSS_Param &param1,const void *pParam2)
{
	const xbString &str2 = *(const xbString*)pParam2;
	return param1.name.Compare(str2);
}


//////////////////////////////////////////////////////////////////////////////////////////
// xbLZSS : base for compression and decompression
//////////////////////////////////////////////////////////////////////////////////////////
ulong xbLZSS::getCodePage() const
{
	if (m_cp == CP_ACP)
		m_cp = g_xbCfgEngine.GetRealCP(m_cp);
	return m_cp;
}

void xbLZSS::Close(bool bFreeMem)
{
	m_bStarted = false;
	m_bWriteTmpExt = false;
	m_bAcceptHeaderParam = m_bAcceptFileList = m_bAcceptFileParam = true;
	m_curFile = -1;
	m_cByteFile = -1;
	m_arrFile.Empty();
	m_arrParam.Empty();

	if (bFreeMem)
		resetMemory();
}

void xbLZSS::tmpDataWrite(const void *_pData,ulong DataLg)
{
//	if (DataLg == 0)
//		return;
	if (!m_bStarted)
	{
		onTmpDataStreamStart();
		m_bStarted = true;
	}
	if (m_bWriteTmpExt)
	{
		m_bWriteTmpExt = false;
		onTmpDataWriteTmpExt();
	}
	
	const uchar *pData = (const uchar *)_pData;
	while(DataLg > 0)
	{
		if (m_pTmpData + DataLg <= m_pTmpDataEnd)
		{
			memcpy(m_pTmpData,pData,DataLg);
			m_pTmpData += DataLg;
			return;
		}
		if (m_pTmpData < m_pTmpDataEnd)
		{
			int lg = int(xbNptr(m_pTmpDataEnd) - xbNptr(m_pTmpData));
			memcpy(m_pTmpData,pData,lg);
			m_pTmpData += lg;
			pData += lg;
			DataLg -= lg;
		}

		tmpDataFlush();
	}
}

void xbLZSS::dataInit(uint cByteBlock,uint cByteCompBlock)
{
	m_pTmpData = m_pTmpDataStart = (uchar*)m_tmpData.GetWritePtr(cByteBlock);
	m_pTmpDataEnd = m_pTmpDataStart + cByteBlock;

	m_pCompData = m_pCompDataStart = (uchar*)m_compData.GetWritePtr(cByteCompBlock);
	m_pCompDataEnd = m_pCompDataStart + cByteCompBlock;
}

void xbLZSS::tmpDataResize(uint cByte,bool bKeepPtr)
{
	ulong offs = 0;
	if (bKeepPtr)
		offs = ulong(xbNptr(m_pTmpData) - xbNptr(m_pTmpDataStart));
	if (cByte > uint(m_tmpData.Length))
	{
		m_pTmpDataStart = (uchar*)m_tmpData.GetWritePtr(cByte);
	}
	else
		m_pTmpDataStart = (uchar*)(LPCVOID)m_tmpData;
	m_pTmpDataEnd = m_pTmpDataStart + cByte;
	m_pTmpData = m_pTmpDataStart + offs;
}

void xbLZSS::tmpDataFlush(bool bEnd,bool bClose)
{
	if (m_pTmpData > m_pTmpDataStart)
	{
		onTmpDataToComp(bEnd,bClose);
	}
	onCompDataFlush(bEnd,bClose);
}

void xbLZSS::compDataResize(uint cByte,bool bKeepPtr)
{
	ulong offs = 0;
	if (bKeepPtr)
		offs = ulong(xbNptr(m_pCompData) - xbNptr(m_pCompDataStart));
	if (cByte > uint(m_compData.Length))
	{
		m_pCompDataStart = (uchar*)m_compData.GetWritePtr(cByte);
	}
	else
		m_pCompDataStart = (uchar*)(LPCVOID)m_compData;
	m_pCompDataEnd = m_pCompDataStart + cByte;
	m_pCompData = m_pCompDataStart + offs;
}

void xbLZSS::huffmanInit(bool bCompress)
{
	// Huffman stuff
	// Tree can be 2n-1 elements in size
	// Number of output codes = size of alphabet
	m_pHuffmanLiteralTree = (xbHuffmanNode*)m_huffmanLiteralTree.GetWritePtr(
		((2*xbLZSS_HUFF_LITERAL_ALPHABETSIZE)-1) * sizeof(xbHuffmanNode));
	if (bCompress)
		m_pHuffmanLiteralOutput = (xbHuffmanOutput*)m_huffmanLiteralOutput.GetWritePtr(
			xbLZSS_HUFF_LITERAL_ALPHABETSIZE * sizeof(xbHuffmanOutput));
	else
		m_pHuffmanLiteralOutput = NULL;

	m_pHuffmanOffsetTree = (xbHuffmanNode*)m_huffmanOffsetTree.GetWritePtr(
		((2*xbLZSS_HUFF_OFFSET_ALPHABETSIZE)-1) * sizeof (xbHuffmanNode));
	if (bCompress)
		m_pHuffmanOffsetOutput = (xbHuffmanOutput*)m_huffmanOffsetOutput.GetWritePtr(
			xbLZSS_HUFF_OFFSET_ALPHABETSIZE * sizeof (xbHuffmanOutput));
	else
		m_pHuffmanOffsetOutput = NULL;

	// Literal and match length tree
	xbHuffmanZero(m_pHuffmanLiteralTree, xbLZSS_HUFF_LITERAL_ALPHABETSIZE);
	xbHuffmanGenerate(m_pHuffmanLiteralTree, m_pHuffmanLiteralOutput, xbLZSS_HUFF_LITERAL_ALPHABETSIZE, 0);
	m_bHuffmanLiteralFullyActive = false;
	m_nHuffmanLiteralIncrement = (xbLZSS_HUFF_LITERAL_ALPHABETSIZE*3)/2;
	m_nHuffmanLiteralsLeft	= m_nHuffmanLiteralIncrement;

	// Offset tree
	xbHuffmanZero(m_pHuffmanOffsetTree, xbLZSS_HUFF_OFFSET_ALPHABETSIZE);
	xbHuffmanGenerate(m_pHuffmanOffsetTree, m_pHuffmanOffsetOutput, xbLZSS_HUFF_OFFSET_ALPHABETSIZE, 0);
	m_bHuffmanOffsetFullyActive = false;
	m_nHuffmanOffsetIncrement = (xbLZSS_HUFF_OFFSET_ALPHABETSIZE*3)/2;
	m_nHuffmanOffsetsLeft	= m_nHuffmanOffsetIncrement;
}

void xbHuffmanZero(xbHuffmanNode *pHuffTree, uint nAlphabetSize)
{
	// Reset the freqencies for all entries 
	// At the start all entries are equally probably for an unknown file
	// A frequency of zero at the start creates a worst case tree with 255 char codes :(
	xbHuffmanNode *pHuffTreeEnd = pHuffTree + nAlphabetSize;
	while (pHuffTree < pHuffTreeEnd)
	{
		pHuffTree->nFrequency	= 1;
		pHuffTree->pChildLeft	= pHuffTree;			// The children on the leaf node will ALWAYS
		pHuffTree->pChildRight	= pHuffTree;			// equal themselves to indicate a leaf!
		pHuffTree++;
	}
}



void xbHuffmanGenerate(xbHuffmanNode *pHuffTree, xbHuffmanOutput *pHuffOutput, uint nAlphabetSize, uint nFreqMod)
{
	// Reset the table so we can search the first set of elements
	// entries (actual bytes)
	xbHuffmanNode *pNodePtr = pHuffTree;
	xbHuffmanNode *pNodeEnd = pHuffTree + nAlphabetSize;

	while(pNodePtr < pNodeEnd)
	{
		pNodePtr->bSearchMe = true;
		pNodePtr++;
	}

	xbHuffmanNode *pNodeRoot = pHuffTree + (nAlphabetSize << 1) - 1;
	{
		// Next free entry in the array is now nAlphabetSize
		xbHuffmanNode *pNodeNextBlank = pHuffTree + nAlphabetSize;
		uint	nNextBlankEntry = nAlphabetSize;
		xbHuffmanNode	*pByte1, *pByte2;
		ulong	nByte1Freq, nByte2Freq;

		while (pNodeNextBlank < pNodeRoot )
		{
			// Get least 2 frequent entries
			pByte1		= pByte2		= pHuffTree;
			nByte1Freq	= nByte2Freq	= 0xffffffff;
			for (pNodePtr=pHuffTree; pNodePtr<pNodeNextBlank; pNodePtr++)
			{
				if ( pNodePtr->bSearchMe ) 
				{
					if ((pNodePtr->nFrequency <= nByte2Freq) 
						|| (pNodePtr->nFrequency <= nByte1Freq))
					{
						pByte2		= pByte1;
						nByte2Freq	= nByte1Freq;
						pByte1		= pNodePtr;
						nByte1Freq	= pNodePtr->nFrequency;
					}
				}
			}

			// Remove the two entries from the search list
			pByte1->bSearchMe = false;
			pByte2->bSearchMe = false;

			// Create a new parent entry with the combined frequency
			pNodeNextBlank->nFrequency	= pByte1->nFrequency + pByte2->nFrequency;
			pNodeNextBlank->bSearchMe		= true;	// Add to search list
			pNodeNextBlank->pChildLeft	= pByte1;
			pNodeNextBlank->pChildRight	= pByte2;
			pByte1->pParent				= pNodeNextBlank;
			pByte2->pParent				= pNodeNextBlank;
			pByte1->cValue					= 0;
			pByte2->cValue					= 1;

			pNodeNextBlank++;
		} // End while

		// The last array entry ((nAlphabetSize << 1) - 2) is now the parent node!
	}

	// Check our tree to see that no codes are too long
	//nAlphabetSize symbols to code
	pNodePtr = pHuffTree;
	pNodeRoot--;
	xbHuffmanNode *pParent;
	int cBitCode;
	while(pNodePtr < pNodeEnd)
	{
		pParent = pNodePtr;
		cBitCode = 0;									// Number of bits long the code is
		while (pParent != pNodeRoot)
		{
			cBitCode++;
			pParent = pParent->pParent;
		}

		// Ensure that codes are not too long, if they are divide the freqencies by 4 
		// then start again
		if (cBitCode > xbLZSS_HUFF_MAXCODEBITS)
		{
			pNodePtr = pHuffTree;
			while(pNodePtr < pNodeEnd)
			{
				pNodePtr->nFrequency = (pNodePtr->nFrequency >> 2) | 1;
				pNodePtr++;
			}
		
			xbHuffmanGenerate(pHuffTree, pHuffOutput, nAlphabetSize, nFreqMod);
			return;
		}
		pNodePtr++;
	}

	// Now fill our Huffman output table for each byte
	if (pHuffOutput)
	{
		pNodePtr = pHuffTree;
		xbHuffmanOutput *pOutputPtr = pHuffOutput;
		while(pNodePtr < pNodeEnd)
		{
			pParent = pNodePtr;
			cBitCode = 0;									// Number of bits long the code is
			while (pParent != pNodeRoot)
			{
				xbAssert(cBitCode < xbLZSS_HUFF_MAXCODEBITS);
				pOutputPtr->szOutput[cBitCode] = pParent->cValue;
				cBitCode++;
				pParent = pParent->pParent;
			}
			pOutputPtr->nNumBits = cBitCode;
			pOutputPtr++;
			pNodePtr++;
		}
	}

	// Finally, reduce the probability of all the freqencies of the individual
	// bytes so that "old" frequencies are worth less than any new data we get
	if (nFreqMod)
	{
		// Divide by freqency modifier, make sure is 1 or more (zeros do bad things...)
		pNodePtr = pHuffTree;
		while(pNodePtr < pNodeEnd)
		{
			pNodePtr->nFrequency = (pNodePtr->nFrequency >> nFreqMod) | 1;
			pNodePtr++;
		}
	}
}

ulong xbLZSS::GetCaps() const //cf xbCOMPRESSCAPS_
{
	ulong caps = 0;
	if (m_bAcceptHeaderParam)
		caps |= (xbCOMPRESSCAPS_HEADERPARAM|xbCOMPRESSCAPS_HEADERPARAM_ATSTART);
	if (m_bAcceptFileList)
		caps |= xbCOMPRESSCAPS_FILELIST;
	if (m_bAcceptFileParam)
		caps |= (xbCOMPRESSCAPS_FILEPARAM|xbCOMPRESSCAPS_FILEPARAM_ATSTART);
	return caps;
}

bool xbLZSS::EnumFile(int no, xbString *pPath, ulong *pLength,ulong cp) const
{
	if (no >= m_arrFile.Length)
		return false;

	if (pPath)
		xbCPconvert(getCodePage(),m_arrFile.GetAt(no).path,cp,pPath);
	if (pLength)
		*pLength = m_arrFile.GetAt(no).length;

	return true;
}

int xbLZSS::GetFileCount() const
{
	return m_arrFile.Length;
}

bool xbLZSS::EnumFileParam(int no, xbString *pName, xbString *pVal,ulong cp) const
{
	if (m_curFile < 0)
		return false;
	const xbLZSS_File &file = m_arrFile.GetAt(m_curFile);

	if (no >= file.params.Length)
		return false;

	if (pName)
		xbCPconvert(getCodePage(),file.params.GetAt(no).name,cp,pName);
	if (pVal)
		xbCPconvert(getCodePage(),file.params.GetAt(no).value,cp,pVal);

	return true;
}

bool xbLZSS::EnumHeaderParam(int no, xbString *pName, xbString *pVal,ulong cp) const
{
	if (no >= m_arrParam.Length)
		return false;

	if (pName)
		xbCPconvert(getCodePage(),m_arrParam.GetAt(no).name,cp,pName);
	if (pVal)
		xbCPconvert(getCodePage(),m_arrParam.GetAt(no).value,cp,pVal);

	return true;
}

bool xbLZSS::addFile(const xbString &path,ulong length,ulong cp,xbOpMode addopm,bool bNoAdd)
{
	xbString cppath;
	xbCPconvert(cp,path,getCodePage(),&cppath);

	int pos;
	xbLZSS_File *pFile = m_arrFile.SortedFind(&cppath,xbLZSSfile_find,&pos);
	if (pFile)
	{
		if (addopm == xbOp_Required)
			xbThrow xbEcompress("EPLZSS compression: file '"+path+"' is already in list","xbLZSS::addFile()"); 
		if (length != -1 && pFile->length != length)
		{
			if (pFile->status & 0x1)
				xbThrow xbEcompress("EPLZSS compression: file '"+path+"' information is already written","xbLZSS::addFile()"); 
			pFile->length = length;
		}
		m_curFile = pos;
		m_cByteFile = pFile->length;
		return false;
	}

	if (bNoAdd)
		xbThrow xbEcompress("EPLZSS compression: file '"+path+"' not in list","xbLZSS::addFile()"); 

	m_arrFile.Insert(pos,xbLZSS_File(cppath,length));
	m_curFile = pos;
	m_cByteFile = length;
	return true;
}

bool xbLZSS::addHeaderParam(const xbString &name,const xbString &val,ulong cp,xbOpMode addopm)
{
	xbString cpname;
	xbCPconvert(cp,name,getCodePage(),&cpname);
	xbString cpval;
	xbCPconvert(cp,val,getCodePage(),&cpval);

	int pos;
	xbLZSS_Param *pParam = m_arrParam.SortedFind(&cpname,xbLZSSparam_find,&pos);
	if (pParam)
	{
		if (addopm == xbOp_Required)
			xbThrow xbEcompress("EPLZSS compression: header parameter '"+name+"' is already in list","xbLZSS::addHeaderParam()"); 
		pParam->value = cpval;
		return false;
	}

	m_arrParam.Insert(pos,xbLZSS_Param(cpname,cpval));
	return true;
}

bool xbLZSS::addFileParam(const xbString &name,const xbString &val,ulong cp,xbOpMode addopm)
{
	if (m_curFile < 0)
		xbThrow xbEcompress("EPLZSS compression: can't add file parameter '"+name+"' because there is no current file","xbLZSS::addFileParam()"); 

	xbLZSS_File &file = m_arrFile.GetAt(m_curFile);
	if (file.status & 0x1)
		xbThrow xbEcompress("EPLZSS compression: can't add file parameter '"+name+"' because current file information is already written","xbLZSS::addFileParam()"); 

	xbString cpname;
	xbCPconvert(cp,name,getCodePage(),&cpname);
	xbString cpval;
	xbCPconvert(cp,val,getCodePage(),&cpval);

	int pos;
	xbLZSS_Param *pParam = file.params.SortedFind(&cpname,xbLZSSparam_find,&pos);
	if (pParam)
	{
		if (addopm == xbOp_Required)
			xbThrow xbEcompress("EPLZSS compression: header parameter '"+name+"' is already in list","xbLZSS::addHeaderParam()"); 
		pParam->value = cpval;
		return false;
	}

	file.params.Insert(pos,xbLZSS_Param(cpname,cpval));
	return true;
}

bool xbLZSS::GetFileParam(const xbString &name, xbString *pVal,ulong cp,xbOpMode opm) const
{
	if (m_curFile < 0)
	{
		if (opm == xbOp_Required)
			xbThrow xbEcompress("EPLZSS compression: can't get file parameter '"+name+"' because there is no current file","xbLZSS::GetFileParam()"); 
		return false;
	}

	const xbLZSS_File &file = m_arrFile.GetAt(m_curFile);

	xbString cpname;
	xbCPconvert(cp,name,getCodePage(),&cpname);
	const xbLZSS_Param *pParam = file.params.SortedFind(&cpname,xbLZSSparam_find);
	if (!pParam)
	{
		if (opm == xbOp_Required)
			xbThrow xbEcompress("EPLZSS compression: file parameter '"+name+"' doesn't exist","xbLZSS::GetFileParam()"); 
		return false;
	}
	if (pVal)
		xbCPconvert(getCodePage(),pParam->value,cp,pVal);
	return true;
}

bool xbLZSS::GetHeaderParam(const xbString &name, xbString *pVal,ulong cp,xbOpMode opm) const
{
	xbString cpname;
	xbCPconvert(cp,name,getCodePage(),&cpname);

	const xbLZSS_Param *pParam = m_arrParam.SortedFind(&cpname,xbLZSSparam_find);
	if (!pParam)
	{
		if (opm == xbOp_Required)
			xbThrow xbEcompress("EPLZSS compression: header parameter '"+name+"' doesn't exist","xbLZSS::GetHeaderParam()"); 
		return false;
	}
	if (pVal)
		xbCPconvert(getCodePage(),pParam->value,cp,pVal);
	return true;
}
//////////////////////////////////////////////////////////////////////////////////////////
// xbLZSScompress : compression base
//////////////////////////////////////////////////////////////////////////////////////////
void xbLZSScompress::SetProgressCb(IxbCompressProgress *pProgressCb)
{
	if (pProgressCb)
	{
		m_prProgressCb = pProgressCb;
		m_bProgressCb = true;
		return;
	}
	m_prProgressCb.Empty();
	m_bProgressCb = false;
}

void xbLZSScompress::Close(bool bFreeMem)
{
	m_prProgressCb.Empty();
	m_bProgressCb = false;
	if (m_ppHashTable)
	{
#ifdef _DEBUG
		m_cByteRealOffset += xbLZSS_MAXWINDOWLENGTH;
		hashTablePrune(NULL,true);
		m_cByteRealOffset -= xbLZSS_MAXWINDOWLENGTH;
		xbAssert(m_nHashEntriesFree	== m_nHashEntriesMax);
#endif
	}
	xbLZSS::Close(bFreeMem);
}

xbString xbLZSScompress::GetCompressLabel(bool bShort) const
{
	xbString ret("EPLZSS compression");
	if (!bShort)
		ret += " (level: "+xbString(m_compressLevel)+")";
	return ret;
}

bool xbLZSScompress::GetCompressLevelRange(int *pMin, int *pMax, int *pDflt) const
{
	if (pMin) 
		*pMin = 0;
	if (pMax) 
		*pMax = 9;
	if (pDflt)
		*pDflt = 7;
	return true;
}

bool xbLZSScompress::GetCompressBlockRange(int *pMin, int *pMax, int *pDflt) const
{
	if (pMin) 
		*pMin = xbLZSS_BLOCKSIZE_MIN;
	if (pMax) 
		*pMax = xbLZSS_BLOCKSIZE_MAX;
	if (pDflt)
		*pDflt = xbLZSS_BLOCKSIZE;
	return true;
}

bool xbLZSScompress::EnumCompressSetting(int no, xbString *pName, xbString *pLabel, int *pMin, int *pMax, int *pDflt) const
{
	return false;
}

void xbLZSScompress::SetCompressLevel(int compressLevel)
{
	if (m_bStarted)
		xbThrow xbEcompress("EPLZSS compression: can't change compression level after compression is started","xbLZSScompressPush::SetCompressLevel("+xbString(compressLevel)+")"); 
	switch (compressLevel)
	{
		case xbCompressLow:
		case 0:
			m_nHashChainLimit	= 1;	// Fastest
			m_bLazyEvaluation	= false;
			compressLevel = 0;
			break;
		
		case 1:
			m_nHashChainLimit	= 4;	// Fast
			m_bLazyEvaluation	= true;
			break;
		
		case 2:							
			m_nHashChainLimit	= 8;	//Old default / Normal level
			m_bLazyEvaluation	= true;
			break;
		
		case 3:
			m_nHashChainLimit	= 16;
			m_bLazyEvaluation	= true;
			break;

		case xbCompressMid:
		case 4:
			m_nHashChainLimit	= 32;
			m_bLazyEvaluation	= true;
			compressLevel = 4;
			break;
		
		case 5:
			m_nHashChainLimit	= 64;
			m_bLazyEvaluation	= true;
			break;

		case 6:
			m_nHashChainLimit	= 128;
			m_bLazyEvaluation	= true;
			break;

		case 7:
			m_nHashChainLimit	= 256;	// Old best
			m_bLazyEvaluation	= true;
			compressLevel = 7;
			break;

		case xbCompressDefault:
		case 8:
			m_nHashChainLimit	= 512;
			m_bLazyEvaluation	= true;
			compressLevel = 8;
			break;

		case xbCompressHigh:
		case 9:
			m_nHashChainLimit	= 1024;	// Best
			m_bLazyEvaluation	= true;
			compressLevel = 9;
			break;

		default:
			xbThrow xbEcompress("EPLZSS compression: Bad compression level","xbLZSScompressPush::SetCompressionLevel("+xbString(compressLevel)+")"); 
	}
	m_compressLevel = compressLevel;
}

int xbLZSScompress::GetCompressLevel() const
{
	return m_compressLevel;
}

void xbLZSScompress::SetCompressBlock(int compressBlock)
{
	if (m_bStarted)
		xbThrow xbEcompress("EPLZSS compression: can't change compression block size after compression is started","xbLZSScompressPush::SetCompressBlock("+xbString(compressBlock)+")"); 
	switch (compressBlock)
	{
		case xbCompressLow:
			m_cByteBlock = xbLZSS_BLOCKSIZE_MIN;
			m_cByteCompBlock = -1;
			break;
		case xbCompressDefault:
			m_cByteBlock = xbLZSS_BLOCKSIZE;
			m_cByteCompBlock = -1;
			break;
		case xbCompressMid:
			m_cByteBlock = xbLZSS_BLOCKSIZE_MID;
			m_cByteCompBlock = -1;
			break;
		case xbCompressHigh:
			m_cByteBlock = xbLZSS_BLOCKSIZE_HIGH;
			m_cByteCompBlock = -1;
			m_windowCoeff = xbLZSS_ALGMODE_WINDOWCOEFF_DFLT+1;
			break;
		default:
			compressBlock = (compressBlock/4)*4;
			if (compressBlock < xbLZSS_BLOCKSIZE_MIN
				|| compressBlock > xbLZSS_BLOCKSIZE_MAX)
				xbThrow xbEcompress("EPLZSS compression: Bad compression block size","xbLZSScompressPush::SetCompressionLevel("+xbString(compressBlock)+")"); 
			m_cByteBlock = compressBlock;
			m_cByteCompBlock = -1 ;
			break;
	}
}

int xbLZSScompress::GetCompressBlock() const
{
	return m_cByteBlock;
}

bool xbLZSScompress::SetCompressSetting(LPCSTR pszName,int val,xbOpMode opm)
{
	if (opm == xbOp_Required)
		xbThrow xbEcompress(E_NOTIMPL,"EPLZSS compression: setting "+xbString(pszName)+" unknown","xbLZSScompressPush::SetCompressSetting()"); 
	return false;
}

int xbLZSScompress::GetCompressSetting(LPCSTR pszName,bool *pbExist) const
{
	if (!pbExist)
		xbThrow xbEcompress(E_NOTIMPL,"EPLZSS compression: setting "+xbString(pszName)+" unknown","xbLZSScompressPush::GetCompressSetting()"); 
	*pbExist = false;
	return -1;
}

void xbLZSScompress::ResetCompressSettings(int compressLevel)
{
	if (m_bStarted)
		xbThrow xbEcompress("EPLZSS compression: can't reset settings after compression is started","xbLZSScompressPush::ResetCompressSettings("+xbString(compressLevel)+")"); 
	m_cByteBlock = xbLZSS_BLOCKSIZE;
	m_cByteCompBlock = -1;
	SetCompressLevel(compressLevel);
}

void xbLZSScompress::SetCodePage(ulong cp)
{
	if (m_bStarted)
		xbThrow xbEcompress("EPLZSS compression: can't change code page after compression is started","xbLZSScompressPush::SetCodePage("+xbString(cp)+")"); 
	m_cp = g_xbCfgEngine.GetRealCP(cp);
}

// HashTableInit()
void xbLZSScompress::hashTableInit()
{
	// Hash table related
	if (!m_ppHashTable)
	{
		ulong cHash = m_cByteBlock*(m_windowCoeff - 1);
		if (cHash <= 0)
			cHash = m_cByteBlock;
		if (cHash > xbLZSS_HASHTABLE_SIZE)
			cHash = xbLZSS_HASHTABLE_SIZE;
		if (cHash > xbLZSS_MAXWINDOWLENGTH)
			cHash = xbLZSS_MAXWINDOWLENGTH;

		cHash *= 2;
		xbDbgOutput("LZSS max hash entries: "+xbString(cHash)+ " ("+xbString(cHash * (sizeof(xbLZSS_Hash) + sizeof(xbLZSS_Hash*)))+" bytes)");
		m_nHashEntriesMax	= cHash; //xbLZSS_HASHMEMLIMIT / sizeof(xbLZSS_Hash);
		m_ppHashMemAllocTable = (xbLZSS_Hash**)m_hashMemAllocTable.GetWritePtr(
			m_nHashEntriesMax * sizeof(xbLZSS_Hash*));
		m_pHashEntryMemPool = (xbLZSS_Hash*)m_hashEntryMemPool.GetWritePtr(
			m_nHashEntriesMax * sizeof(xbLZSS_Hash));

		m_pHashChainCounts = (uint*)m_hashChainCounts.GetWritePtr(
			xbLZSS_HASHTABLE_SIZE * sizeof(uint));
		m_ppHashTable = (xbLZSS_Hash**)m_hashTable.GetWritePtr(
			xbLZSS_HASHTABLE_SIZE * sizeof(xbLZSS_Hash*));
	}

	// Clear the hash table
	memset(m_ppHashTable,0,xbLZSS_HASHTABLE_SIZE * sizeof(xbLZSS_Hash*));
	memset(m_pHashChainCounts,0,xbLZSS_HASHTABLE_SIZE * sizeof(uint));

	// Pre-allocate all our hash entries
	m_nHashEntriesFree	= m_nHashEntriesMax;

	xbLZSS_Hash **ppHash = m_ppHashMemAllocTable;
	xbLZSS_Hash **ppHashEnd = m_ppHashMemAllocTable + m_nHashEntriesMax;
	xbLZSS_Hash *pMem = m_pHashEntryMemPool;

	while(ppHash < ppHashEnd)
	{
		*(ppHash++) = pMem++;
	}

	m_nHashTablePurgeCount	= xbLZSS_HASHPRUNEDELAY;	// Prune the hash table periodically
	m_bLastHash = false;
}


// HashTableAdd() pData + 3 <= m_pTmpData
// Adds a hash entry of "nPos" at index "nHash"
void xbLZSScompress::hashTableAdd(const uchar *pData)
{
	xbAssert(pData >= m_pTmpDataStart);
	xbAssert(pData + 3 <= m_pTmpData);

	// Get hash at current position
	uint nHash = ( ( *pData ^ *(pData+1)<<7) ^ *(pData+2)<<11) & 0xffff;

	//Bugjon : not a bug but loss for binaries seems great
	// Avoid long runs of the same hash (for very little loss in compression)
//	if (m_bLastHash && nHash == m_nLastHash)
//		return;

	m_bLastHash = true;
	m_nLastHash = nHash;

	// Get our first entry at this hash index
	xbAssert(nHash < xbLZSS_HASHTABLE_SIZE);
	xbLZSS_Hash *pTempHash = m_ppHashTable[nHash];			

	xbAssert(m_nHashEntriesFree>0);
	ulong stmPos = ulong(xbNptr(pData) - xbNptr(m_pTmpDataStart) + m_cByteRealOffset);
	if (!pTempHash)
	{
		// Initial entry, check if we have the memory first!
		if (!m_nHashEntriesFree)
			return;

		pTempHash				= hashEntryAlloc();
		pTempHash->pNext		= NULL;
		pTempHash->pPrev		= pTempHash;	// Pointer to prev, OR if head of list, points to tail entry
		pTempHash->stmPos		= stmPos;
		pTempHash->pMemPos		= pData;
		m_ppHashTable[nHash]	= pTempHash;
		m_pHashChainCounts[nHash]= 1;
		return;
	}

	// If we are here, there is at least one entry already
	
	if (m_nHashChainLimit == 1 
		|| ((m_pHashChainCounts[nHash] == 1) && (!m_nHashEntriesFree)))
	{
		pTempHash->stmPos  = stmPos;
		pTempHash->pMemPos = pData;
		return;
	}

	// If at chain limit, or no free memory left for hashing, starting overwriting the
	// oldest entries with the new entries
	if ((m_pHashChainCounts[nHash] == m_nHashChainLimit) || (!m_nHashEntriesFree))
	{
		// Get the last entry
		xbLZSS_Hash *pTempLast = m_ppHashTable[nHash]->pPrev;

		// Make next to last entry in list the last entry
		pTempLast->pPrev->pNext = NULL;

		// Use last entry, then move it to the top of the list
		pTempLast->pNext	= m_ppHashTable[nHash];
		pTempLast->stmPos	= stmPos;
		pTempLast->pMemPos  = pData;
		m_ppHashTable[nHash]= pTempLast;
		return;
	}


	// Add an entry to the top of the list
	// First get a new entry
	pTempHash = hashEntryAlloc();
	pTempHash->stmPos = stmPos;
	pTempHash->pMemPos  = pData;

	// Get last entry and modify lpNext
	xbLZSS_Hash *pTempLast = m_ppHashTable[nHash]->pPrev;
	pTempLast->pNext = NULL;	// Need this for entries == 1

	// Modify current top of list so that previous is our new entry
	m_ppHashTable[nHash]->pPrev = pTempHash;
	pTempHash->pNext = m_ppHashTable[nHash];
	pTempHash->pPrev = pTempLast;

	// Make new entry top of list
	m_ppHashTable[nHash] = pTempHash;
	m_pHashChainCounts[nHash]++;
}


// HashTablePrune()
// Removes entries in the linked list that are too old
void xbLZSScompress::hashTablePrune(const uchar *pData,bool bForce)
{
	if (!bForce && (--m_nHashTablePurgeCount) > 0)
		return;
	m_nHashTablePurgeCount = xbLZSS_HASHPRUNEDELAY;

	if (!bForce && m_nHashEntriesFree > 32)
		return;

	// Get the start of the window offset (to help remove old hash entries)
	if (!pData) 
		pData = m_pTmpDataStart;
	xbAssert(pData <= m_pTmpData);
	xbAssert(pData >= m_pTmpDataStart);
	ulong tooOldPos;

	if (m_pRealDataBusyEnd)
	{
		tooOldPos = m_cByteRealBusyEnd - ulong(xbNptr(m_pRealDataBusyEnd) - xbNptr(m_pTmpData));
		ulong curPos = ulong(xbNptr(pData) - xbNptr(m_pTmpDataStart) + m_cByteRealOffset);
		if (tooOldPos + xbLZSS_MAXWINDOWLENGTH < curPos)
			tooOldPos = curPos - xbLZSS_MAXWINDOWLENGTH;
	}
	else
	{
		tooOldPos = ulong(xbNptr(pData) - xbNptr(m_pTmpDataStart) + m_cByteRealOffset);
		if (tooOldPos < xbLZSS_MAXWINDOWLENGTH)
			tooOldPos = m_cByteRealOffset;
		else
			tooOldPos -= xbLZSS_MAXWINDOWLENGTH;
	}

	xbLZSS_Hash **ppHash = m_ppHashTable;
	uint		*pHashCnt = m_pHashChainCounts;
	xbLZSS_Hash **ppHashEnd = ppHash + xbLZSS_HASHTABLE_SIZE;
	xbLZSS_Hash *pTempHash,*pTempPrev,*pTempNext;
	while(ppHash < ppHashEnd)
	{
		// Find the oldest entry at this hash value, then delete it and the rest
		pTempPrev = pTempHash = *ppHash;
		while (pTempHash)
		{
			if (pTempHash->stmPos <= tooOldPos)
			{
				// Found an old entry, all following entries will also be too old, delete
				// them from the tail backwards
				
				while(pTempHash)
				{
					pTempNext = pTempHash->pNext;
					hashEntryFree(pTempHash);
					pTempHash = pTempNext;
					
					xbAssert(*pHashCnt > 0);
					(*pHashCnt)--;
				}

				if (*pHashCnt == 0)
					*ppHash = NULL;
				else
				{
					pTempPrev->pNext = NULL;
					(*ppHash)->pPrev = pTempPrev;
				}
				
				break;
			}

			pTempPrev = pTempHash;
			pTempHash = pTempHash->pNext;
		}
		ppHash++;
		pHashCnt++;
	}

}


// HashEntryAlloc()
// malloc() is really really slow when allocating and freeing lots of tiny
// 4bytes chunks of memory.  This function acts as a buffer to speed things along
xbLZSS_Hash* xbLZSScompress::hashEntryAlloc()
{
	if (m_nHashEntriesFree <= 0)
		xbThrow xbEmem();
	m_nHashEntriesFree--;
	return m_ppHashMemAllocTable[m_nHashEntriesFree];
}


// HashEntryFree()
void xbLZSScompress::hashEntryFree(xbLZSS_Hash *pHash)
{
	if (m_nHashEntriesFree >= m_nHashEntriesMax)
		xbThrow xbEmem();

	m_ppHashMemAllocTable[m_nHashEntriesFree] = pHash;
	m_nHashEntriesFree++;
}

// FindMatches()
void xbLZSScompress::hashTableFind(const uchar *pInitialDataPos, uint *pnOffset, uint *pnLen, uint nBestLen)
{
	// Get our window start position, if the window would take us beyond
	// the start of the file, just use 0
	xbAssert(pInitialDataPos >= m_pTmpDataStart);
	xbAssert(pInitialDataPos + 3 <= m_pTmpData);

	// Reset all variables
	ulong curPos = ulong(xbNptr(pInitialDataPos) - xbNptr(m_pTmpDataStart) + m_cByteRealOffset);
	ulong tooOldPos;

	if (m_pRealDataBusyEnd)
	{
		tooOldPos = m_cByteRealBusyEnd - ulong(xbNptr(m_pRealDataBusyEnd) - xbNptr(m_pTmpData));
		if (tooOldPos + xbLZSS_MAXWINDOWLENGTH < curPos)
			tooOldPos = curPos - xbLZSS_MAXWINDOWLENGTH;
	}
	else
	{
		tooOldPos = curPos;
		if (tooOldPos < xbLZSS_MAXWINDOWLENGTH)
			tooOldPos = m_cByteRealOffset;
		else
			tooOldPos -= xbLZSS_MAXWINDOWLENGTH;
	}

	ulong bestOffset = -1;

	// Generate a hash of the next three chars
	uint nHash = ( ( *pInitialDataPos ^ (*(pInitialDataPos+1)<<7)) ^ (*(pInitialDataPos+2)<<11)) & 0xffff;

	// Main loop
	xbAssert(nHash < xbLZSS_HASHTABLE_SIZE);
	xbLZSS_Hash *pTempHash = m_ppHashTable[nHash];			// Get our match from the hash table

	const uchar *pTempWPos;
	uint		nTempLen;
	const uchar *pDPos;
	while (pTempHash && (nBestLen < xbLZSS_MAXMATCHLEN))
	{

		// Is this entry too old, any remaining entries will also be too old!
		if (pTempHash->stmPos <= tooOldPos)
			break;

		// Is this entry too near? 
		if (pTempHash->stmPos + xbLZSS_HASHORDER > curPos)
		{
			pTempHash = pTempHash->pNext;
			continue;
		}

		pTempWPos = pTempHash->pMemPos;

		//Match method :
		// pTempWPos   pInitialDataPos
		// |           | 
		// 00 00 00 00 00 BA AC DE ... -> nLen = 1
		// AB BC DE EF AB BC DE EF FF ... -> nLen = 4

		// First, check the byte at the current bestlen match, if this doesn't 
		// match then let's not waste any time with it
		if (nBestLen)
		{
			const uchar *pPos1 = pTempWPos + nBestLen - 1;
			if (m_pRealDataBusyEnd && pPos1 >= m_pRealDataBusyEnd)
			{
				pPos1 = m_pRealDataStart + (xbNptr(pPos1) - xbNptr(m_pRealDataBusyEnd));
				xbAssert(pPos1 >= m_pRealDataStart && pPos1 < m_pTmpData);
			}
			if (pPos1+xbLZSS_HASHORDER >= pInitialDataPos)
			{
				pTempHash = pTempHash->pNext;
				continue;
			}
			const uchar *pPos2 = pInitialDataPos + nBestLen - 1;
//			xbAssert(pPos2 <= m_pTmpData);
			if ( pPos2 >= m_pTmpData)
				break;
			if (*pPos1 != *pPos2)
			{
				pTempHash = pTempHash->pNext;
				continue;
			}
		}

		nTempLen	= 0;
		pDPos		= pInitialDataPos;

		bool bHighBlock = (pTempWPos >= m_pTmpData);
		xbAssert((!bHighBlock && pTempWPos <= pInitialDataPos - xbLZSS_HASHORDER && pTempWPos >= m_pRealDataStart)
			|| (bHighBlock  && pTempWPos < m_pRealDataBusyEnd));

		while ( (pDPos < m_pTmpData) && (nTempLen < xbLZSS_MAXMATCHLEN) )
		{
			if (*(pTempWPos++) != *(pDPos++))
				break;
			if (bHighBlock && pTempWPos >= m_pRealDataBusyEnd)
			{
				pTempWPos = m_pRealDataStart;
				xbAssert(pTempWPos < m_pTmpData);
				bHighBlock = false;
			}
			else
			{
				xbAssert(bHighBlock || pTempWPos < m_pTmpData);
			}

			nTempLen++;	
		} 

		// See if this match was better than previous match (favor small offsets)
		if (nTempLen > nBestLen)
		{
			nBestLen	= nTempLen;
			bestOffset = pTempHash->stmPos;
		}

		pTempHash = pTempHash->pNext;

	}

	// Setup our return values of bestoffset and bestlen
	if (bestOffset == -1 || nBestLen < xbLZSS_MINMATCHLEN)
		*pnLen = 0;
	else
	{
		xbAssert(curPos > bestOffset);
		*pnOffset	= curPos - bestOffset;			// Return value
		*pnLen		= nBestLen;						// Return value
	}

} // FindMatches()

//////////////////////////////////////////////////////////////////////////////////////////
// xbLZSScompressPush : push compression
//////////////////////////////////////////////////////////////////////////////////////////
void xbLZSScompressPush::New(IxbOutputStream *pStm)
{
	Close(false);
	m_prStm = pStm;
}

void xbLZSScompressPush::SetOutputStream(IxbOutputStream *pStm)
{
	m_prStm = pStm;
}

void xbLZSScompressPush::SetNotifCb(IxbCompressNotif *pNotifCb)
{
	if (pNotifCb)
	{
		m_prNotifCb = pNotifCb;
		m_bNotifCb = true;
		return;
	}
	m_prNotifCb.Empty();
	m_bNotifCb = false;
}

bool xbLZSScompressPush::GetOutputStream(xbRefPtr<IxbOutputStream> *pprStm,xbOpMode opm)
{
	if (m_prStm.IsEmpty())
	{
		if (opm == xbOp_Required)
			xbThrow xbEcompress("EPLZSS compression: no output stream defined","xbLZSScompressPush::GetOutputStream()"); 
		return false;
	}
	if (pprStm)
		*pprStm = m_prStm;
	return true;
}

void xbLZSScompressPush::CompressFlush()
{
	flush();
}

void xbLZSScompressPush::Close(bool bFreeMem)
{
	if (m_prStm.IsValid() && m_bStarted)
	{
		flush(true,true);
		
		if (initNotifCb())
			m_prNotifCb->onCompressClose(this);
	}
	m_prStm.Empty();
	m_prNotifCb.Empty();
	m_bNotifCb = false;
	xbLZSScompress::Close(bFreeMem);
}

bool xbLZSScompressPush::NewFile(const xbString &path,ulong length,ulong cp,xbOpMode addopm) //return false if file is already in list, in this case seek only 
{
	if (!m_bAcceptFileList && (addopm == xbOp_Required || m_arrFile.IsEmpty()))
		xbThrow xbEcompress("EPLZSS compression: multiple files not allowed or list closed","xbLZSScompressPush::NewFile()"); 

	ulong oldCurFile = m_curFile;
	bool bFlush = (!m_bWriteTmpExt && m_curFile >= 0);
	bool bRet = addFile(path,length,cp,addopm,!m_bAcceptFileList);
	xbLZSS_File &file = m_arrFile.GetAt(m_curFile);
	if (file.status & 0x1)
	{
		m_curFile = oldCurFile;
		xbThrow xbEcompress("EPLZSS compression: file '"+path+"' information is already written","xbLZSS::addFile()"); 
	}
	if (bFlush)
		flush(true);
	m_bWriteTmpExt = true;
	m_bAcceptFileParam = true;
	if (initNotifCb())
		m_prNotifCb->onCompressNewFile(this,cp,path,length);
	return bRet;
}

bool xbLZSScompressPush::AddFileParam(const xbString &name, const xbString &val,ulong cp,xbOpMode addopm)
{
	if (!m_bAcceptFileParam)
		xbThrow xbEcompress("EPLZSS compression: file parameters not allowed here","xbLZSScompressPush::AddFileParam()"); 
	return addFileParam(name,val,cp,addopm);
}

bool xbLZSScompressPush::AddHeaderParam(const xbString &name, const xbString &val,ulong cp,xbOpMode addopm)
{
	if (!m_bAcceptHeaderParam)
		xbThrow xbEcompress("EPLZSS compression: file parameters not allowed here","xbLZSScompressPush::AddFileParam()"); 
	return addHeaderParam(name,val,cp,addopm);
}

bool xbLZSScompressPush::CanWrite() const
{
	return true;
}

ulong xbLZSScompressPush::Write(const void *pData,ulong DataLg,bool DataLg_Required)
{
	tmpDataWrite(pData,DataLg);
	return DataLg;
}

ulong xbLZSScompressPush::WriteStream(IxbInputStream *pstm)
{
	if (!pstm->CanRead()) xbThrow xbEcompress(STG_E_ACCESSDENIED,"EPLZSS compression: WriteStream failed, permission denied reading stream");
	if (!CanWrite()) xbThrow xbEcompress(STG_E_ACCESSDENIED,"EPLZSS compression: WriteStream failed, permission denied writing stream");

	ulong	data_wr = 0;
	char	buf[xbSTREAM_BUFSIZE];

	for(;;)
	{
		ulong	data_rd;
		if ((data_rd = pstm->Read(buf,xbSTREAM_BUFSIZE,false)) <= 0) break;
		tmpDataWrite(buf,data_rd);
		data_wr += data_rd;
	}
	if (m_bWriteTmpExt && data_wr == 0)
		tmpDataWrite(NULL,0);

	return data_wr;
}

ulong xbLZSScompressPush::WriteStream(IxbInputStream *pstm,ulong DataLg,bool DataLg_Required)
{
	if (!pstm->CanRead()) xbThrow xbEcompress(STG_E_ACCESSDENIED,"EPLZSS compression: WriteStream failed, permission denied reading stream");
	if (!CanWrite()) xbThrow xbEcompress(STG_E_ACCESSDENIED,"EPLZSS compression: WriteStream failed, permission denied writing stream");

	ulong data_towr = DataLg;
	char	buf[xbSTREAM_BUFSIZE];

	while(data_towr>0)
	{
		ulong	data_wr = data_towr>xbSTREAM_BUFSIZE?xbSTREAM_BUFSIZE:data_towr;
		if ((data_wr = pstm->Read(buf,data_wr,false)) <= 0) break;
		tmpDataWrite(buf,data_wr);
		data_towr -= data_wr;
	}
	if (DataLg_Required && data_towr != 0)
		xbThrow xbEcompress(STG_E_WRITEFAULT,"EPLZSS compression: WriteStream failed");

	if (m_bWriteTmpExt && data_towr == DataLg)
		tmpDataWrite(NULL,0);

	return DataLg - data_towr;
}

ulong xbLZSScompressPush::WriteString(const char *pStr,ulong lgStr,bool bAddLf,IxbStreamMode *pMode)
{
	if (!bAddLf && (!pMode || !pMode->CRLFasLF))
		return Write(pStr,lgStr);

	xbString str(pStr,lgStr);
	if (bAddLf) str += '\n';
	if (pMode && pMode->CRLFasLF)
	{
		int pos = -1;
		while((pos = str.IndexOf('\n',pos+1)) >= 0)
		{
			if (pos > 0 && str.GetAt(pos-1) == '\r') continue;
			str.Insert(pos,'\r');
		}
	}

	tmpDataWrite((LPCSTR)str,str.Length);
	return str.Length;
}

ulong xbLZSScompressPush::WriteStringW(const wchar *pStr,ulong lgStr,bool bAddLf,IxbStreamMode *pMode)
{
	xbThrow xbEcompress(E_NOTIMPL,"EPLZSS compression: WriteStringW not supported","xbLZSScompressPush::WriteStringW()"); 
	return false;
}

bool xbLZSScompressPush::initNotifCb()
{
	if (m_bNotifCb)
		return m_prNotifCb.IsValid();
	m_bNotifCb = true;
	m_prNotifCb = xbRefQIPtr<IxbCompressNotif>(m_prStm,xbOp_Optional);
	return m_prNotifCb.IsValid();
}

bool xbLZSScompressPush::initProgressCb()
{
	if (m_bProgressCb)
		return m_prProgressCb.IsValid();
	m_bProgressCb = true;
	m_prProgressCb = xbRefQIPtr<IxbCompressProgress>(m_prStm,xbOp_Optional);
	return m_prProgressCb.IsValid();
}

void xbLZSScompressPush::flush(bool bEnd,bool bClose)
{
	if (m_bWriteTmpExt)
	{
		m_bWriteTmpExt = false;
		onTmpDataWriteTmpExt();
	}
	tmpDataFlush(bEnd,bClose);
	if (initNotifCb())
		m_prNotifCb->onCompressFlush(this,bEnd,bClose);
}


void xbLZSScompressPush::onTmpDataStreamStart()
{
	xbDbgOutput("LZSS max window length: "+xbString(xbLZSS_MAXWINDOWLENGTH));
	xbDbgOutput("LZSS max match length: "+xbString(xbLZSS_MAXMATCHLEN));
	xbAssert(xbLZSS_HUFF_LITERAL_ALPHABETSIZE != 292
		|| xbLZSS_MAXMATCHLEN == (1023 + xbLZSS_MINMATCHLEN));
	xbAssert(xbLZSS_HUFF_OFFSET_ALPHABETSIZE != 30
		|| xbLZSS_MAXWINDOWLENGTH == (32767 + xbLZSS_MINMATCHLEN));
	if (m_cByteCompBlock == -1)
		m_cByteCompBlock = xbLZSS_COMPBLOCKSIZE(m_cByteBlock);

	xbAssert(m_windowCoeff >= 1 && m_cByteBlock);
	dataInit(m_cByteBlock*m_windowCoeff,m_cByteCompBlock);
	m_pRealDataEnd = m_pTmpDataEnd;
	m_pRealDataStart = m_pTmpDataStart;
	m_pRealDataBusyEnd = NULL;
	m_pTmpDataEnd = m_pTmpDataStart + m_cByteBlock;

	m_cByteReal = 0;
	m_cByteRealBusyEnd = 0;
	m_cByteRealOffset = 0;
	m_cByteComp = 0;

	// Write header in output stream
	xbLZSS_Header hdr;
	if (m_cByteBlock <= xbLZSS_BLOCKSIZE_SETTING_SHORTMAX)
	{
		m_bShortBlock = true;
		hdr.m_mode |= xbLZSS_ALGMODE_SHORTBLOCK;
	}
	else
	{
		m_bShortBlock = false;
	}
#ifdef _RELDBG
	hdr.m_mode |= xbLZSS_ALGMODE_DEBUGMARKER;
	m_bDebugMarker = true;
#else
	m_bDebugMarker = false;
#endif
	if (!m_bWriteTmpExt)
	{
		m_bAcceptHeaderParam = m_bAcceptFileList = m_bAcceptFileParam = false;
	}
	else
	{
		if (m_arrParam.IsValid())
		{
			hdr.m_mode |= xbLZSS_ALGMODE_HEADERPARAM;
		}
		if (m_arrFile.IsValid())
		{
			hdr.m_mode |= xbLZSS_ALGMODE_FILELIST;
		}
		else
		{
			m_bAcceptFileList = false;
		}
		m_bAcceptHeaderParam = false;
		m_bAcceptFileParam = false;
	}
	xbAssert(m_windowCoeff >= xbLZSS_ALGMODE_WINDOWCOEFF_START);
	hdr.m_mode |= (m_windowCoeff - xbLZSS_ALGMODE_WINDOWCOEFF_START);
	hdr.m_cByteBlockReal = m_cByteBlock;

	compDataWrite(&hdr,sizeof(hdr));
	m_cByteComp += sizeof(hdr);

	// At the start huffman coding is off
	huffmanInit(true);

	if (initProgressCb())
		m_prProgressCb->onCompressProgress(this,NULL,"EPLZSS compression",m_cByteReal,m_cByteComp,m_cByteFile);

	if (!m_bWriteTmpExt)
		return;
	
	m_bStarted = true;
	if (m_cp == CP_ACP)
		getCodePage();
	m_bWriteTmpExt = false;
	tmpDataWrite(&m_cp,sizeof(ulong));
	m_bWriteTmpExt = true;
}

void xbLZSScompressPush::onTmpDataWriteTmpExt()
{
	m_bAcceptFileParam = false;
	xbAssert(!m_bAcceptHeaderParam);
	if (m_arrParam.IsValid() && !(m_arrParam.First().status & 0x1))
	{
		m_arrParam.First().status |= 0x1;
		ulong lg = m_arrParam.Length;
		tmpDataWrite(&lg,sizeof(ulong));

		while(lg > 0)
		{
			ulong sz,sz2;
			xbString &str1 = m_arrParam.GetAt(lg-1).name;
			sz = str1.Length;
			tmpDataWrite(&sz,sizeof(ulong));
			xbString &str2 = m_arrParam.GetAt(lg-1).value;
			sz2 = str2.Length;
			tmpDataWrite(&sz2,sizeof(ulong));

			tmpDataWrite(str1,sz);
			tmpDataWrite(str2,sz2);
			lg--;
		}
	}

	if (m_curFile >= 0)
	{
		xbLZSS_File &file = m_arrFile.GetAt(m_curFile);
		if (file.status & 0x1)
			xbThrow xbEcompress("EPLZSS compression: current file information is already written","xbLZSS::onTmpDataWriteTmpExt()"); 
		file.status |= 0x1;
		ulong lg = file.params.Length;
		tmpDataWrite(&lg,sizeof(ulong));
		tmpDataWrite(&file.status,sizeof(ulong));
		tmpDataWrite(&file.length,sizeof(ulong));

		ulong sz;
		{
			xbString &str = file.path;
			sz = str.Length;
			tmpDataWrite(&sz,sizeof(ulong));
			tmpDataWrite(str,sz);
		}

		ulong sz2;
		while(lg > 0)
		{
			xbString &str1 = file.params.GetAt(lg-1).name;
			sz = str1.Length;
			tmpDataWrite(&sz,sizeof(ulong));
			xbString &str2 = file.params.GetAt(lg-1).value;
			sz2 = str2.Length;
			tmpDataWrite(&sz2,sizeof(ulong));

			tmpDataWrite(str1,sz);
			tmpDataWrite(str2,sz2);
			lg--;
		}
	}
}

void xbLZSScompressPush::onCompDataFlush(bool bEnd,bool bClose)
{
	if (bEnd)
	{
		if (m_bDebugMarker)
		{
			compDataWriteUint64(xbLZSSMARKER_BLOCKEND);
		}
		if (m_bShortBlock)
		{
			compDataWriteUshort(0);
			m_cByteComp += sizeof(ushort);
		}
		else
		{
			compDataWriteUlong(0);
			m_cByteComp += sizeof(ulong);
		}
		if (bClose && !m_bWriteTmpExt && m_curFile >= 0)
		{
			if (m_bDebugMarker)
			{
				compDataWriteUint64(xbLZSSMARKER_BLOCKEND);
			}
			if (m_bShortBlock)
			{
				compDataWriteUshort(0);
				m_cByteComp += sizeof(ushort);
			}
			else
			{
				compDataWriteUlong(0);
				m_cByteComp += sizeof(ulong);
			}
			m_curFile = -1;
		}
	}
	if (m_pCompData <= m_pCompDataStart)
		return;
	if (m_prStm.IsValid())
		m_prStm->Write(m_pCompDataStart,ulong(xbNptr(m_pCompData) - xbNptr(m_pCompDataStart)));

	m_pCompData = m_pCompDataStart;
}

//CompressBlock and CompressLoop
void xbLZSScompressPush::onTmpDataToComp(bool bEnd,bool bClose)
{
	if (!m_ppHashTable || m_windowCoeff <= 1)
		hashTableInit();
	else
		hashTablePrune(NULL,true);
	m_nCompressedLong		= 0;				// Compressed stream temporary 32bit value
	m_nCompressedBitsFree	= 32;				// Number of bits unused in temporary value

	xbLZSS_LongBlockHeader	*pCompLongBlockHdr;
	xbLZSS_ShortBlockHeader *pCompShortBlockHdr;

	ulong cByteRealData = ulong(xbNptr(m_pTmpData) - xbNptr(m_pTmpDataStart));
	xbAssert(cByteRealData <= m_cByteBlock && cByteRealData > 0);
	if (m_bDebugMarker)
	{
		compDataWriteUint64(xbLZSSMARKER_BLOCKSTART);
	}
	if (m_bShortBlock)
	{
		// Check for possible overrun (compressed buffer is larger than input thankfully)
		if (m_pCompData + sizeof(xbLZSS_ShortBlockHeader) > m_pCompDataEnd)
			xbThrow xbEcompress("EPLZSS compression : compressed output is larger than buffer","xbLZSScompressPush::tmpDataCompress()");
		xbAssert(cByteRealData <= 0xFFFF);
		pCompShortBlockHdr = (xbLZSS_ShortBlockHeader*)m_pCompData;

		if (cByteRealData != m_cByteBlock)
		{
			m_pCompData += sizeof(xbLZSS_ShortBlockHeader);
			pCompShortBlockHdr->m_cByteReal = ushort(cByteRealData);
		}
		else
			m_pCompData += sizeof(ushort);
		pCompLongBlockHdr = NULL;
	}
	else
	{
		// Check for possible overrun (compressed buffer is larger than input thankfully)
		if (m_pCompData + sizeof(xbLZSS_LongBlockHeader) > m_pCompDataEnd)
			xbThrow xbEcompress("EPLZSS compression : compressed output is larger than buffer","xbLZSScompressPush::tmpDataCompress()");

		pCompLongBlockHdr = (xbLZSS_LongBlockHeader*)m_pCompData;
		if (cByteRealData != m_cByteBlock)
		{
			m_pCompData += sizeof(xbLZSS_LongBlockHeader);
			pCompLongBlockHdr->m_cByteReal = cByteRealData;
		}
		else
			m_pCompData += sizeof(ulong);
		pCompShortBlockHdr = NULL;
	}

	
	// Loop around until there is no more data, stop matching HASHORDER from the
	// end of the block so that we can remove some overrun code in the loop
	const uchar *pMaxPos		= m_pTmpData - (xbLZSS_HASHORDER+1);
	const uchar *pBlockPos		= m_pTmpDataStart;
	uint		nOffset1,nLen1;
	uint		nOffset2,nLen2;
	uint		nIncrement;
	while ( pBlockPos < pMaxPos )
	{
		// Check for a match at the current position
		hashTableFind(pBlockPos, &nOffset1, &nLen1, 0);	// Search for matches for current position

		// Did we get a match?
		if (nLen1)
		{
			// Do a match at next position to see if it's better?
			if (m_bLazyEvaluation)
				hashTableFind(pBlockPos+1, &nOffset2, &nLen2, nLen1);
			else
				nLen2 = 0;						// Fake a non-match

			if ( nLen2 > (nLen1+1) )			// Len2 match must be 1 byte better to make up for the skipped literal
			{
				// Match at +1 is better, write a literal then this match
				compDataWriteLiteral(*pBlockPos);	// Literal
				compDataWriteLen(nLen2 - xbLZSS_MINMATCHLEN);		// Match Len
				compDataWriteOffset(nOffset2 - xbLZSS_MINMATCHLEN);// Match offset
				nIncrement = nLen2+1;			// Move forwards matched len
			}
			else
			{
				compDataWriteLen( nLen1 - xbLZSS_MINMATCHLEN );	// Match Len
				compDataWriteOffset(nOffset1 - xbLZSS_MINMATCHLEN);// Match offset
				nIncrement = nLen1;				// Move forwards matched len
			}
		}
		else
		{
			// No matches, just store the literal byte
			compDataWriteLiteral(*pBlockPos);
			nIncrement = 1;						// Move forward 1 literal
		}

		// We have skipped forwards either 1 byte or xxx bytes (if matched) we must now
		// add entries in the hash table for all the entries we've skipped
		while (nIncrement)
		{
			//Bugjon 
			if (pBlockPos > pMaxPos)
			{
				pBlockPos += nIncrement;
				break;
			}
			hashTableAdd(pBlockPos);						// Hashes at CURRENT POSITION
			pBlockPos++;
			nIncrement--;
		}  // End while

		// Prune the hash table if required
//		if (m_windowCoeff <= 1)
		hashTablePrune(pBlockPos);
	} // End while

	// We will have stopped just short of the end of data because of the way the 
	// hashing function/lazy eval needs to work, now output the remaining data as literals
	while ( pBlockPos < m_pTmpData )
		compDataWriteLiteral(*pBlockPos++);

	xbAssert ( pBlockPos == m_pTmpData );

	// Flush the compressed bitstream (pad with zeros if required)
	// Output stream will be 32bit aligned, possibly a little wasteful...
	compDataWriteBitsFlush();

	m_cByteReal += cByteRealData;
	m_cByteRealOffset += cByteRealData;
	if (pCompShortBlockHdr)
	{
		//Write compressed size of current block in header);
		ulong cByteComp = ulong(xbNptr(m_pCompData) - xbNptr(pCompShortBlockHdr));
		if ((cByteComp % 2) != 0 || cByteComp > xbLZSS_BLOCKSIZE_SHORTMAX)
			xbThrow xbEcompress("EPLZSS compression : compressed result is larger than expected","xbLZSScompressPush::onTmpDataToComp(lg compressed="+xbString(cByteComp)+", lg before compression="+xbString(cByteRealData)+")");
		m_cByteComp += cByteComp;
		if (cByteRealData != m_cByteBlock)
		{
			cByteComp -= sizeof(*pCompShortBlockHdr);
			cByteComp >>= 1;
			cByteComp |= 0x8000;
		}
		else
		{
			cByteComp -= sizeof(ushort);
			cByteComp >>= 1;
		}
		pCompShortBlockHdr->m_cByteComp = ushort(cByteComp);

	}
	else
	{
		//Write compressed size of current block in header);
		ulong cByteComp = ulong(xbNptr(m_pCompData) - xbNptr(pCompLongBlockHdr));
		m_cByteComp += cByteComp;
		if ((cByteComp % 2) != 0)
			xbThrow xbEcompress("EPLZSS compression : compressed result has an invalid length","xbLZSScompressPush::onTmpDataToComp(lg compressed="+xbString(cByteComp)+", lg before compression="+xbString(cByteRealData)+")");
		if (cByteRealData != m_cByteBlock)
		{
			cByteComp -= sizeof(*pCompLongBlockHdr);
			cByteComp >>= 1;
			cByteComp |= 0x80000000;
		}
		else
		{
			cByteComp -= sizeof(ulong);
			cByteComp >>= 1;
		}
		pCompLongBlockHdr->m_cByteComp = cByteComp;
	}

	if (initProgressCb())
		m_prProgressCb->onCompressProgress(this,NULL,"EPLZSS compression",m_cByteReal,m_cByteComp,m_cByteFile);

	if (m_windowCoeff <= 1)
	{
		m_pTmpDataStart = m_pTmpData = m_pRealDataStart;
		m_pTmpDataEnd = m_pTmpDataStart + m_cByteBlock;
		xbAssert(m_pTmpDataEnd <= m_pRealDataEnd);
		return;
	}
	if (m_pTmpData + m_cByteBlock <= m_pRealDataEnd)
	{
		m_pTmpDataStart = m_pTmpData;
		m_pTmpDataEnd = m_pTmpData + m_cByteBlock;
		return;
	}

	m_pRealDataBusyEnd = m_pTmpData;
	m_cByteRealBusyEnd = m_cByteRealOffset;
	m_pTmpDataStart = m_pTmpData = m_pRealDataStart;
	m_pTmpDataEnd = m_pTmpDataStart + m_cByteBlock;
	xbAssert(m_pTmpDataEnd <= m_pRealDataEnd);
}

// CompressedStreamWriteBits()
//
// Will write a number of bits (variable) into the compressed data stream
//
// When there are no more bits to send, you should call the function with the
// parameters 0, 0 to make sure that any left over bits are flushed into the
// compressed stream
//
// Note 16 bits is the maximum allowed value for this function!!!!!
// ================================================================
// This equates to a maximum window size of 65535
void xbLZSScompressPush::compDataWriteBits(register const uint nValue,register uint nNumBits)
{
	xbAssert(m_nCompressedBitsFree > 0);
	while (nNumBits)
	{
		nNumBits--;

		// Make room for another bit (shift left once)
		m_nCompressedLong <<= 1;

		// Merge (OR) our value into the temporary long
		m_nCompressedLong |= ((nValue >> nNumBits) & 0x00000001);

		// Update how many bits remain unused (sub 1)
		m_nCompressedBitsFree--;

		// Now check if we have filled our temporary long with bits (32bits)
		if (!m_nCompressedBitsFree)
		{
			// Check for possible overrun (compressed buffer is larger than input thankfully)
			if (m_pCompData + 2 > m_pCompDataEnd)
				xbThrow xbEcompress("EPLZSS compression : compressed output is larger than buffer","xbLZSScompressPush::compDataWriteBits()");

			// We now need to dump the highest 16 bits into our compressed
			// stream.  Highest order 8 bits first
			*m_pCompData++ = (uchar)(m_nCompressedLong >> 24);
			*m_pCompData++ = (uchar)(m_nCompressedLong >> 16);

			// We've now written out 16 bits so make more room (16 bits more room :) )
			m_nCompressedBitsFree += 16;
		}

	} // End while

}


// CompressedStreamWriteBitsFlush()
void xbLZSScompressPush::compDataWriteBitsFlush()
{
	// We have been asked to finish, flush remaining by using up remaining
	// unused bits with zeros
	// Means that all bit output functions result in a 32bit aligned data stream

	// Shift left by number of Bits remaining
	m_nCompressedLong = m_nCompressedLong << m_nCompressedBitsFree;

	// Check for possible overrun (compressed buffer is larger than input thankfully)
	if (m_pCompData + 2 > m_pCompDataEnd)
		xbThrow xbEcompress("EPLZSS compression : compressed output is larger than buffer","xbLZSScompressPush::compDataWriteBitsFlush()");

	// Now write out all 32 bits
	*m_pCompData++ = (uchar)(m_nCompressedLong >> 24);
	*m_pCompData++ = (uchar)(m_nCompressedLong >> 16);
	if (/*!m_bShortBlock ||*/ m_nCompressedBitsFree < 16)
	{
		// Check for possible overrun (compressed buffer is larger than input thankfully)
		if (m_pCompData + 2 > m_pCompDataEnd)
			xbThrow xbEcompress("EPLZSS compression : compressed output is larger than buffer","xbLZSScompressPush::compDataWriteBitsFlush(2)");
		*m_pCompData++ = (uchar)(m_nCompressedLong >> 8);
		*m_pCompData++ = (uchar)(m_nCompressedLong);
	}

	// All done
	m_nCompressedBitsFree = 32;
}

// CompressedStreamWriteHuffman()
void xbLZSScompressPush::compDataWriteHuffman(xbHuffmanOutput *pHuffOutputCode)
{
	// Get the number of bits for this code and write out in reverse
	uint nLen = pHuffOutputCode->nNumBits;
	xbAssert(nLen > 0 && nLen <= sizeof(pHuffOutputCode->szOutput));
	const uchar *szOutput = &pHuffOutputCode->szOutput[nLen-1];

	uint nTemp = 0;
	uint nNumBits = 16;
	while(nLen > 0)
	{
		nTemp = nTemp << 1;

		nTemp = nTemp | *szOutput--;
		nNumBits--;
		nLen--;
		if (!nNumBits)
		{
			nNumBits = 16;
			compDataWriteBits(nTemp, 16);
			nTemp = 0;
		}
	}
	if (nNumBits)
		compDataWriteBits(nTemp, 16-nNumBits);

}


// CompressedStreamWriteLiteral()
void xbLZSScompressPush::compDataWriteLiteral(const uint nChar)
{
	// Write the huffman code for this value
	xbAssert(nChar < xbLZSS_HUFF_LITERAL_ALPHABETSIZE);
	compDataWriteHuffman(m_pHuffmanLiteralOutput + nChar);

	// Update the frequency of this character
	m_pHuffmanLiteralTree[nChar].nFrequency++;
	m_nHuffmanLiteralsLeft--;

	// If we have coded enough literals, then generate/regenerate the huffman tree
	if (!m_nHuffmanLiteralsLeft)
	{
		if (m_bHuffmanLiteralFullyActive)
		{
			m_nHuffmanLiteralsLeft	= xbLZSS_HUFF_DELAY;
			xbHuffmanGenerate(m_pHuffmanLiteralTree, m_pHuffmanLiteralOutput, xbLZSS_HUFF_LITERAL_ALPHABETSIZE, xbLZSS_HUFF_LITERAL_FREQMOD);
		}
		else
		{
			m_nHuffmanLiteralIncrement += (xbLZSS_HUFF_LITERAL_ALPHABETSIZE*3)/2;
			if (m_nHuffmanLiteralIncrement >= xbLZSS_HUFF_DELAY)
				m_bHuffmanLiteralFullyActive = true;

			m_nHuffmanLiteralsLeft	= (xbLZSS_HUFF_LITERAL_ALPHABETSIZE*3)/2;
			xbHuffmanGenerate(m_pHuffmanLiteralTree, m_pHuffmanLiteralOutput, xbLZSS_HUFF_LITERAL_ALPHABETSIZE, xbLZSS_HUFF_LITERAL_FREQMOD);
		}
	}

}


// CompressedStreamWriteLen()
void xbLZSScompressPush::compDataWriteLen(const uint nLength)
{
	uint nValue,nCode,nExtraBits,nMSBValue;
	// First 8 bits are unique, then goes in 4 codes per bit
	if (nLength <= 7)
	{
		nValue		= nLength;
		nCode		= nLength + 256;
		nExtraBits	= 0;
	}
	else
	{
		nExtraBits	= 1;						// Base number of bits
		nMSBValue	= 1 << (nExtraBits+2);		// MSB value
		nValue		= nLength - nMSBValue;
		nCode		= 264;						// Base code 

		while (nValue >= (nMSBValue))
		{
			nExtraBits++;
			nMSBValue	= nMSBValue << 1;			// MSB value
			nCode		= nCode + 4;				// Base code 
			nValue		= nValue - (nMSBValue>>1);
		}

		// Now work out the proper code
		nValue		= nLength - nMSBValue;
		nCode		= (nValue>>nExtraBits) + nCode;
		nValue		= nValue & ((1 << nExtraBits)-1);
	}

	// Write the huffman code for this value
	xbAssert(nCode < xbLZSS_HUFF_LITERAL_ALPHABETSIZE);
	compDataWriteHuffman(m_pHuffmanLiteralOutput+nCode);

	// Now write out the remaining value and bits
	if (nExtraBits)
		compDataWriteBits(nValue, nExtraBits);

	// Update the frequency of this character
	m_pHuffmanLiteralTree[nCode].nFrequency++;
	m_nHuffmanLiteralsLeft--;

	// If we have coded enough literals, then generate/regenerate the huffman tree
	if (!m_nHuffmanLiteralsLeft)
	{
		if (m_bHuffmanLiteralFullyActive)
		{
			m_nHuffmanLiteralsLeft	= xbLZSS_HUFF_DELAY;
			xbHuffmanGenerate(m_pHuffmanLiteralTree, m_pHuffmanLiteralOutput, xbLZSS_HUFF_LITERAL_ALPHABETSIZE, xbLZSS_HUFF_LITERAL_FREQMOD);
		}
		else
		{
			m_nHuffmanLiteralIncrement += (xbLZSS_HUFF_LITERAL_ALPHABETSIZE*3)/2;
			if (m_nHuffmanLiteralIncrement >= xbLZSS_HUFF_DELAY)
				m_bHuffmanLiteralFullyActive = true;

			m_nHuffmanLiteralsLeft	= (xbLZSS_HUFF_LITERAL_ALPHABETSIZE*3)/2;
			xbHuffmanGenerate(m_pHuffmanLiteralTree, m_pHuffmanLiteralOutput, xbLZSS_HUFF_LITERAL_ALPHABETSIZE, xbLZSS_HUFF_LITERAL_FREQMOD);
		}
	}
}


// CompressedStreamWriteOffset()
void xbLZSScompressPush::compDataWriteOffset(const uint nOffset)
{
	uint nValue,nCode,nExtraBits,nMSBValue;

	// First 4 bits are unique, then goes in 2 codes per bit
	if (nOffset <= 3)
	{
		nValue		= nOffset;
		nCode		= nOffset;
		nExtraBits	= 0;
	}
	else
	{
		nExtraBits	= 1;						// Base number of bits
		nMSBValue	= 1 << (nExtraBits+1);		// MSB value
		nValue		= nOffset - nMSBValue;
		nCode		= 4;						// Base code 

		while (nValue >= (nMSBValue))
		{
			nExtraBits++;
			nMSBValue	= nMSBValue << 1;			// MSB value
			nCode		= nCode + 2;				// Base code 
			nValue		= nValue - (nMSBValue>>1);
		}

		// Now work out the proper code
		nValue		= nOffset - nMSBValue;
		nCode		= (nValue>>nExtraBits) + nCode;
		nValue		= nValue & ((1 << nExtraBits)-1);
	}

	// Write the huffman code for this value
	xbAssert(nCode < xbLZSS_HUFF_OFFSET_ALPHABETSIZE);
	compDataWriteHuffman(m_pHuffmanOffsetOutput+nCode);

	// Now write out the remaining value and bits
	if (nExtraBits)
		compDataWriteBits(nValue, nExtraBits);

	// Update the frequency of this character
	m_pHuffmanOffsetTree[nCode].nFrequency++;
	m_nHuffmanOffsetsLeft--;

	// If we have coded enough literals, then generate/regenerate the huffman tree
	if (!m_nHuffmanOffsetsLeft)
	{
		if (m_bHuffmanOffsetFullyActive)
		{
			m_nHuffmanOffsetsLeft	= xbLZSS_HUFF_DELAY;
			xbHuffmanGenerate(m_pHuffmanOffsetTree, m_pHuffmanOffsetOutput, xbLZSS_HUFF_OFFSET_ALPHABETSIZE, xbLZSS_HUFF_OFFSET_FREQMOD);
		}
		else
		{
			m_nHuffmanOffsetIncrement += (xbLZSS_HUFF_OFFSET_ALPHABETSIZE*3)/2;
			if (m_nHuffmanOffsetIncrement >= xbLZSS_HUFF_DELAY)
				m_bHuffmanOffsetFullyActive = true;

			m_nHuffmanOffsetsLeft	= (xbLZSS_HUFF_OFFSET_ALPHABETSIZE*3)/2;
			xbHuffmanGenerate(m_pHuffmanOffsetTree, m_pHuffmanOffsetOutput, xbLZSS_HUFF_OFFSET_ALPHABETSIZE, xbLZSS_HUFF_OFFSET_FREQMOD);
		}
	}

}







//////////////////////////////////////////////////////////////////////////////////////////
// xbLZSSdecompress : decompression base
//////////////////////////////////////////////////////////////////////////////////////////
void xbLZSSdecompress::SetProgressCb(IxbDecompressProgress *pProgressCb)
{
	if (pProgressCb)
	{
		m_prProgressCb = pProgressCb;
		m_bProgressCb = true;
		return;
	}
	m_prProgressCb.Empty();
	m_bProgressCb = false;
}

void xbLZSSdecompress::Close(bool bFreeMem)
{
	m_prProgressCb.Empty();
	m_bProgressCb = false;
	xbLZSS::Close(bFreeMem);
}

xbString xbLZSSdecompress::GetCompressLabel(bool bShort) const
{
	xbString ret("EPLZSS decompression");
	return ret;
}

//////////////////////////////////////////////////////////////////////////////////////////
// xbLZSSdecompressPush : decompression
//////////////////////////////////////////////////////////////////////////////////////////
void xbLZSSdecompressPush::New()
{
	Close(false);
}

void xbLZSSdecompressPush::SetOutputStream(IxbOutputStream *pStm)
{
	m_prStm = pStm;
}

void xbLZSSdecompressPush::SetNotifCb(IxbDecompressNotif *pNotifCb)
{
	if (pNotifCb)
	{
		m_prNotifCb = pNotifCb;
		m_bNotifCb = true;
		return;
	}
	m_prNotifCb.Empty();
	m_bNotifCb = false;
}

bool xbLZSSdecompressPush::GetOutputStream(xbRefPtr<IxbOutputStream> *pprStm,xbOpMode opm)
{
	if (m_prStm.IsEmpty())
	{
		if (opm == xbOp_Required)
			xbThrow xbEcompress("EPLZSS decompression: no output stream defined","xbLZSScompressPush::GetOutputStream()"); 
		return false;
	}
	if (pprStm)
		*pprStm = m_prStm;
	return true;
}

void xbLZSSdecompressPush::DecompressFlush()
{
	flush();
}

void xbLZSSdecompressPush::Close(bool bFreeMem)
{
	if (m_prStm.IsValid() && m_bStarted)
	{
		flush(true,true);
		
		if (initNotifCb())
			m_prNotifCb->onDecompressClose(this);
	}
	m_prStm.Empty();
	m_prNotifCb.Empty();
	m_bNotifCb = false;
	xbLZSSdecompress::Close(bFreeMem);
}

bool xbLZSSdecompressPush::CanWrite() const
{
	return true;
}

ulong xbLZSSdecompressPush::Write(const void *pData,ulong DataLg,bool DataLg_Required)
{
	tmpDataWrite(pData,DataLg);
	return DataLg;
}

ulong xbLZSSdecompressPush::WriteStream(IxbInputStream *pstm)
{
	if (!pstm->CanRead()) xbThrow xbEcompress(STG_E_ACCESSDENIED,"EPLZSS decompression: WriteStream failed, permission denied reading stream");
	if (!CanWrite()) xbThrow xbEcompress(STG_E_ACCESSDENIED,"EPLZSS decompression: WriteStream failed, permission denied writing stream");

	ulong	data_wr = 0;
	char	buf[xbSTREAM_BUFSIZE];

	for(;;)
	{
		ulong	data_rd;
		if ((data_rd = pstm->Read(buf,xbSTREAM_BUFSIZE,false)) <= 0) break;
		tmpDataWrite(buf,data_rd);
		data_wr += data_rd;
	}

	return data_wr;
}

ulong xbLZSSdecompressPush::WriteStream(IxbInputStream *pstm,ulong DataLg,bool DataLg_Required)
{
	if (!pstm->CanRead()) xbThrow xbEcompress(STG_E_ACCESSDENIED,"EPLZSS decompression: WriteStream failed, permission denied reading stream");
	if (!CanWrite()) xbThrow xbEcompress(STG_E_ACCESSDENIED,"EPLZSS decompression: WriteStream failed, permission denied writing stream");

	if (DataLg<=0) return 0;

	ulong data_towr = DataLg;
	char	buf[xbSTREAM_BUFSIZE];

	while(data_towr>0)
	{
		ulong	data_wr = data_towr>xbSTREAM_BUFSIZE?xbSTREAM_BUFSIZE:data_towr;
		if ((data_wr = pstm->Read(buf,data_wr,false)) <= 0) break;
		tmpDataWrite(buf,data_wr);
		data_towr -= data_wr;
	}
	if (DataLg_Required && data_towr != 0)
		xbThrow xbEcompress(STG_E_WRITEFAULT,"EPLZSS decompression: WriteStream failed");

	return DataLg - data_towr;
}

ulong xbLZSSdecompressPush::WriteString(const char *pStr,ulong lgStr,bool bAddLf,IxbStreamMode *pMode)
{
	if (!bAddLf && (!pMode || !pMode->CRLFasLF))
		return Write(pStr,lgStr);

	xbString str(pStr,lgStr);
	if (bAddLf) str += '\n';
	if (pMode && pMode->CRLFasLF)
	{
		int pos = -1;
		while((pos = str.IndexOf('\n',pos+1)) > 0)
		{
			if (pos > 0 && str.GetAt(pos-1) == '\r') continue;
			str.Insert(pos,'\r');
		}
	}

	tmpDataWrite((LPCSTR)str,str.Length);
	return str.Length;
}

ulong xbLZSSdecompressPush::WriteStringW(const wchar *pStr,ulong lgStr,bool bAddLf,IxbStreamMode *pMode)
{
	xbThrow xbEcompress(E_NOTIMPL,"EPLZSS decompression: WriteStringW not supported","xbLZSSdecompressPush::WriteStringW()"); 
	return false;
}

bool xbLZSSdecompressPush::initNotifCb()
{
	if (m_bNotifCb)
		return m_prNotifCb.IsValid();
	m_bNotifCb = true;
	m_prNotifCb = xbRefQIPtr<IxbDecompressNotif>(m_prStm,xbOp_Optional);
	return m_prNotifCb.IsValid();
}

bool xbLZSSdecompressPush::initProgressCb()
{
	if (m_bProgressCb)
		return m_prProgressCb.IsValid();
	m_bProgressCb = true;
	m_prProgressCb = xbRefQIPtr<IxbDecompressProgress>(m_prStm,xbOp_Optional);
	return m_prProgressCb.IsValid();
}

void xbLZSSdecompressPush::flush(bool bEnd,bool bClose)
{
	tmpDataFlush(bEnd,bClose);
	outpDataFlush(bEnd,bClose);
}

void xbLZSSdecompressPush::onTmpDataStreamStart()
{
	m_cByteReal = 0;
	m_cByteRealOffset = 0;
	m_cByteComp = 0;
	m_mode = 0;
	m_pOutpDataEnd = m_pOutpData = m_pOutpDataStart = NULL;
	m_outpStep = outpStream;
	m_outpCnt = 0;

	// At the start huffman coding is off
	huffmanInit(false);

	m_readStep = readHeader;
	tmpDataResize(sizeof(xbLZSS_Header),false);

	m_pCompDataEnd = m_pCompDataStart = m_pCompData = NULL;
	m_pCompDataToWrite = m_pRealDataStart = m_pRealDataEnd = m_pRealDataBusyEnd = NULL;
	m_cByteRealBusyEnd = 0;

	if (initProgressCb())
		m_prProgressCb->onDecompressProgress(this,NULL,"EPLZSS decompression",m_cByteReal,m_cByteComp,m_cByteFile);
}

void xbLZSSdecompressPush::onTmpDataToComp(bool bEnd,bool bClose)
{
	try
	{
		ulong cByteData = ulong(xbNptr(m_pTmpData) - xbNptr(m_pTmpDataStart));
		switch(m_readStep)
		{
		case readHeader :
			if (cByteData < sizeof(xbLZSS_Header))
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream header invalid (size)");
				return;
			}
			if (memcmp(((xbLZSS_Header*)m_pTmpDataStart)->m_algid,xbLZSS_ALGID,4) != 0)
				xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream header invalid (algid)");
			m_mode = ((xbLZSS_Header*)m_pTmpDataStart)->m_mode;
			if (!xbLZSS_ALGMODE_VALID(m_mode))
				xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream header invalid (mode)");
			m_bShortBlock = (m_mode & xbLZSS_ALGMODE_SHORTBLOCK)?true:false;
			m_windowCoeff = (m_mode & xbLZSS_ALGMODE_WINDOWCOEFF)+xbLZSS_ALGMODE_WINDOWCOEFF_START;
			m_cByteBlock = ((xbLZSS_Header*)m_pTmpDataStart)->m_cByteBlockReal;
			m_bDebugMarker = (m_mode & xbLZSS_ALGMODE_DEBUGMARKER)?true:false;

			m_bAcceptHeaderParam = (m_mode & xbLZSS_ALGMODE_HEADERPARAM)?true:false;
			m_bAcceptFileList = (m_mode & xbLZSS_ALGMODE_FILELIST)?true:false;
			m_bAcceptFileParam = false;

			if (m_cByteBlock < xbLZSS_BLOCKSIZE_MIN || m_cByteBlock > xbLZSS_BLOCKSIZE_MAX)
				xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream header invalid (block size)");
			
			compDataResize(m_cByteBlock * m_windowCoeff,false);
			m_pCompDataToWrite = m_pRealDataStart = m_pCompDataStart;
			m_pRealDataEnd = m_pCompDataEnd;
			m_pRealDataBusyEnd = NULL;
			m_cByteRealBusyEnd = 0;

			{
				int lgMarker = (m_bDebugMarker?sizeof(uint64):0);
				if (m_bShortBlock)
				{
					tmpDataResize(lgMarker+sizeof(ushort),false);
					m_readStep = readShortBlockHeader;
				}
				else
				{
					tmpDataResize(lgMarker+sizeof(ulong),false);
					m_readStep = readLongBlockHeader;
				}
			}
			xbAssert(m_outpStep == outpStream);
			if (m_bAcceptHeaderParam)
			{
				outpDataAskRead(outpHeader,sizeof(ulong)*2); //code page + nb hdr param
			}
			else if (m_bAcceptFileList)
			{
				outpDataAskRead(outpHeaderFile,sizeof(ulong)*5); //code page + nb param + status + length + name length
			}
			else
			{
				m_pOutpDataEnd = m_pOutpData = m_pOutpDataStart = NULL;
				m_outpStep = outpStream;
				if (initNotifCb())
					m_prNotifCb->onDecompressStart(this);
			}
			return;
		case readShortBlockHeader :
		case readShortBlockHeaderClose :
			if (cByteData < (m_bDebugMarker?sizeof(uint64)+sizeof(ushort):sizeof(ushort)))
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream block invalid (header size)");
				return;
			}
			if (m_bDebugMarker)
			{
				uint64 dbg = *(uint64*)m_pTmpDataStart;
				if (dbg != xbLZSSMARKER_BLOCKSTART && dbg != xbLZSSMARKER_BLOCKEND)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream block signature invalid");
				m_pTmpDataStart+=sizeof(uint64);
			}
			m_readBlock.m_cByteComp = *(ushort*)m_pTmpDataStart;
			if (m_readBlock.m_cByteComp == 0)
			{
				if (m_bAcceptFileList && m_readStep == readShortBlockHeader)
				{
					onCompDataFlush(true,false);
					outpDataFlush(true,false);
					xbAssert(m_outpStep == outpStream);
					m_readStep = readShortBlockHeaderClose;
					m_pTmpData = m_pTmpDataStart;
					if (initNotifCb())
						m_prNotifCb->onDecompressEnd(this,false);
					return;
				}
				m_readStep = readNone;
				m_pTmpData = m_pTmpDataStart;
				onCompDataFlush(true,true);
				outpDataFlush(true,true);
				if (initNotifCb())
					m_prNotifCb->onDecompressEnd(this,true);
				return;
			}
			if (m_readStep == readShortBlockHeaderClose)
			{
				onCompDataFlush(true,false);
				outpDataFlush(true,false);
				xbAssert(m_outpStep == outpStream);
				outpDataAskRead(outpFile,sizeof(ulong)*4); //nb param + status + length + name length
			}
			if (m_readBlock.m_cByteComp & 0x8000)
			{
				m_readBlock.m_cByteComp &= ~0x8000;
				m_readBlock.m_cByteReal = 0;
				m_readStep = readShortBlockHeaderReal;
			}
			else
			{
				m_readBlock.m_cByteReal = m_cByteBlock;
				m_readStep = readBlockData;
			}
			m_readBlock.m_cByteComp <<= 1;
			if (m_readBlock.m_cByteComp == 0 || m_readBlock.m_cByteComp > xbLZSS_COMPBLOCKSIZE(m_cByteBlock))
				xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream block invalid (block size)");

			if (m_readStep == readBlockData)
				tmpDataResize(m_readBlock.m_cByteComp,false);
			else
				tmpDataResize(sizeof(ushort),false);
			return;
		case readShortBlockHeaderReal :
			if (cByteData < sizeof(ushort))
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream block invalid (header real size)");
				return;
			}
			m_readBlock.m_cByteReal = *(ushort*)m_pTmpDataStart;
			if (m_readBlock.m_cByteReal == 0 || m_readBlock.m_cByteReal >= m_cByteBlock)
				xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream block invalid (block size)");
			m_readStep = readBlockData;
			tmpDataResize(m_readBlock.m_cByteComp,false);
			return;
		case readLongBlockHeader :
		case readLongBlockHeaderClose :
			if (cByteData < (m_bDebugMarker?sizeof(uint64)+sizeof(ulong):sizeof(ulong)))
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream block invalid (header size)");
				return;
			}
			if (m_bDebugMarker)
			{
				uint64 dbg = *(uint64*)m_pTmpDataStart;
				if (dbg != xbLZSSMARKER_BLOCKSTART && dbg != xbLZSSMARKER_BLOCKEND)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream block signature invalid");
				m_pTmpDataStart+=sizeof(uint64);
			}
			m_readBlock.m_cByteComp = *(ulong*)m_pTmpDataStart;
			if (m_readBlock.m_cByteComp == 0)
			{
				if (m_bAcceptFileList && m_readStep == readLongBlockHeader)
				{
					onCompDataFlush(true,false);
					outpDataFlush(true,false);
					xbAssert(m_outpStep == outpStream);
					m_readStep = readLongBlockHeaderClose;
					m_pTmpData = m_pTmpDataStart;
					if (initNotifCb())
						m_prNotifCb->onDecompressEnd(this,false);
					return;
				}
				m_readStep = readNone;
				m_pTmpData = m_pTmpDataStart;
				onCompDataFlush(true,true);
				outpDataFlush(true,true);
				if (initNotifCb())
					m_prNotifCb->onDecompressEnd(this,true);
				return;
			}
			if (m_readStep == readLongBlockHeaderClose)
				outpDataAskRead(outpFile,sizeof(ulong)*4); //nb param + status + length + name length
			if (m_readBlock.m_cByteComp & 0x80000000)
			{
				m_readBlock.m_cByteComp &= ~0x80000000;
				m_readBlock.m_cByteReal = 0;
				m_readStep = readLongBlockHeaderReal;
			}
			else
			{
				m_readBlock.m_cByteReal = m_cByteBlock;
				m_readStep = readBlockData;
			}
			m_readBlock.m_cByteComp <<= 1;
			if (m_readBlock.m_cByteComp == 0 || m_readBlock.m_cByteComp > m_cByteBlock)
				xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream block invalid (block size)");
			if (m_readStep == readBlockData)
				tmpDataResize(m_readBlock.m_cByteComp,false);
			else
				tmpDataResize(sizeof(ulong),false);
			return;
		case readLongBlockHeaderReal :
			if (cByteData < sizeof(ulong))
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream block invalid (header real size)");
				return;
			}
			m_readBlock.m_cByteReal = *(ulong*)m_pTmpDataStart;
			if (m_readBlock.m_cByteReal == 0 || m_readBlock.m_cByteReal >= m_cByteBlock)
				xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream block invalid (block size)");
			m_readStep = readBlockData;
			tmpDataResize(m_readBlock.m_cByteComp,false);
			return;
		case readBlockData :
			if (cByteData < m_readBlock.m_cByteComp)
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: unexpected end of stream reading block data");
				return;
			}
			break;
		default:
			xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream invalid (step)");
		}

		if (!m_pCompDataStart)
			xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: unexpected block data");

		m_pCompDataEnd = m_pCompDataStart + m_readBlock.m_cByteReal;
		m_pCompDataToWrite = m_pCompData = m_pCompDataStart;

		decompressBlock();

		m_cByteReal += m_readBlock.m_cByteReal;
		m_cByteRealOffset += m_readBlock.m_cByteReal;
		m_cByteComp += m_readBlock.m_cByteComp;

		if (initProgressCb())
			m_prProgressCb->onDecompressProgress(this,NULL,"EPLZSS decompression",m_cByteReal,m_cByteComp,m_cByteFile);

		int lgMarker = (m_bDebugMarker?sizeof(uint64):0);
		if (m_bShortBlock)
		{
			tmpDataResize(lgMarker+sizeof(ushort),false);
			m_readStep = readShortBlockHeader;
		}
		else
		{
			tmpDataResize(lgMarker+sizeof(ulong),false);
			m_readStep = readLongBlockHeader;
		}

		if (m_windowCoeff <= 1)
		{
			m_pCompDataStart = m_pRealDataStart;
			xbAssert(m_pCompDataStart + m_cByteBlock <= m_pRealDataEnd);
			return;
		}
		if (m_pCompData + m_cByteBlock <= m_pRealDataEnd)
		{
			m_pCompDataStart = m_pCompData;
			return;
		}

		m_pRealDataBusyEnd = m_pCompData;
		m_cByteRealBusyEnd = m_cByteRealOffset;
		m_pCompDataStart = m_pRealDataStart;
		xbAssert(m_pCompDataStart + m_cByteBlock <= m_pRealDataEnd);
	}
	catch(...)
	{
		m_readStep = readNone;
		throw;
	}
}


void xbLZSSdecompressPush::onCompDataFlush(bool bEnd,bool bClose)
{
	if (m_pCompData > m_pCompDataToWrite)
	{
		outpDataWrite(m_pCompDataToWrite,ulong(xbNptr(m_pCompData) - xbNptr(m_pCompDataToWrite)));

		m_pCompDataToWrite = m_pCompData;
	}
}

void xbLZSSdecompress::decompressBlock()
{
	// Set up initial values
	m_nCompressedLong		= 0;				// Compressed stream temporary 32bit value
	m_nCompressedBitsUsed	= 0;				// Number of bits used in temporary value
	m_pTmpBlockPos = m_pTmpDataStart;

	// Perform decompression until we fill our predicted buffer
	register uchar *pCompBlockPos = m_pCompData;
	uint nTemp,nLen,nOffset;

	while(pCompBlockPos < m_pCompDataEnd)
	{
		// Read in a literal
		nTemp = tmpDataReadLiteral();

		// Was it a literal byte, or a  match len?
		if (nTemp < xbLZSS_HUFF_MATCHLEN)	// 0-255 are literals, 256-283 are lengths
		{
			// Store the literal byte
			if (pCompBlockPos >= m_pCompDataEnd)
				xbThrow xbEcompress("EPLZSS decompression : compressed output is larger than buffer","xbLZSSdecompress::decompressBlock()");
			*pCompBlockPos++ = nTemp;
			continue;
		}
		// Decode (and read more if required) to get the length of the match
		nLen = tmpDataReadLen(nTemp) + xbLZSS_MINMATCHLEN;

		// Read the offset
		nOffset = tmpDataReadOffset() + xbLZSS_MINMATCHLEN;

		// Write out our match
		if (pCompBlockPos + nLen> m_pCompDataEnd)
			xbThrow xbEcompress("EPLZSS decompression : compressed output is larger than buffer","xbLZSSdecompress::decompressBlock() : invalid copy, bad len");
		if (nOffset == 0 || nLen == 0)
			xbThrow xbEcompress("EPLZSS decompression : compressed stream is invalid","xbLZSSdecompress::decompressBlock() : invalid copy, null len or offset");
		if (pCompBlockPos < m_pRealDataStart + nOffset)
		{
			if (!m_pRealDataBusyEnd)
				xbThrow xbEcompress("EPLZSS decompression : compressed stream is invalid","xbLZSSdecompress::decompressBlock() : invalid copy, bad offset");
			register uchar *pSrce = m_pRealDataBusyEnd
				 - (nOffset - (xbNptr(pCompBlockPos) - xbNptr(m_pRealDataStart)));
			if (pSrce < m_pCompDataEnd || pSrce >= m_pRealDataBusyEnd)
				xbThrow xbEcompress("EPLZSS decompression : compressed stream is invalid","xbLZSSdecompress::decompressBlock() : invalid copy, bad offset");
			while(nLen > 0)
			{
				*(pCompBlockPos++) = *(pSrce++);
				if (pSrce >= m_pRealDataBusyEnd)
					pSrce = m_pRealDataStart;
				nLen--;
			}
			continue;
		}
		if (nOffset >= nLen)
		{
			memcpy(pCompBlockPos,pCompBlockPos - nOffset,nLen);
			pCompBlockPos += nLen;
			continue;
		}

		if (nOffset > 2)
		{
			while(nLen >= nOffset)
			{
				memcpy(pCompBlockPos,pCompBlockPos - nOffset,nOffset);
				pCompBlockPos += nOffset;
				nLen -= nOffset;
			}
			if (nLen <= 0)
				continue;
		}

		register uchar *pSrce = pCompBlockPos - nOffset;
		while(nLen > 0)
		{
			*(pCompBlockPos++) = *(pSrce++);
			nLen--;
		}
	}

	m_pCompData = pCompBlockPos;
}

// CompressedStreamReadHuffman()
xbHuffmanNode *xbLZSSdecompress::tmpDataReadHuffman(xbHuffmanNode *pHuffTree, uint nAlphabetSize)
{
	// Start with Root node of the tree, if a child is a pointer to itself
	// then it is the leaf and we stop
	xbHuffmanNode *pNodeRoot = pHuffTree + (nAlphabetSize << 1) - 2;
	uint nTemp;
	while (pNodeRoot->pChildLeft != pNodeRoot)
	{
		nTemp = tmpDataReadBits(1);
		if (!nTemp)
			pNodeRoot = pNodeRoot->pChildLeft;
		else
			pNodeRoot = pNodeRoot->pChildRight;
	}

	return pNodeRoot;

}

uint xbLZSSdecompress::tmpDataReadBits(uint nNumBits)
{
	// Ensure that the high order word of our bit buffer is blank 
	m_nCompressedLong = m_nCompressedLong & 0x0000ffff;

	uint nTemp;
	while (nNumBits--)
	{
		// Check if we need to refill our decoding bit buffer
		if (!m_nCompressedBitsUsed)
		{
			if (m_pTmpBlockPos + 2 > m_pTmpData)
				xbThrow xbEcompress("EPLZSS decompression : compressed stream invalid","xbLZSSdecompress::tmpDataReadBits()");
			// Fill the low order 16 bits of our long buffer
			nTemp = (ULONG)*m_pTmpBlockPos++;
			m_nCompressedLong = m_nCompressedLong | (nTemp << 8);
			nTemp = (ULONG)*m_pTmpBlockPos++;
			m_nCompressedLong = m_nCompressedLong | nTemp;
			m_nCompressedBitsUsed = 16;
		}

		// Shift the data into the high part of the long
		m_nCompressedLong = m_nCompressedLong << 1;
		m_nCompressedBitsUsed--;
	}

	return (uint)(m_nCompressedLong >> 16);

}

// CompressedStreamReadLiteral()
uint xbLZSSdecompress::tmpDataReadLiteral()
{
	// Read in a huffman code from the compressed stream
	xbHuffmanNode *pLiteral = tmpDataReadHuffman(m_pHuffmanLiteralTree, xbLZSS_HUFF_LITERAL_ALPHABETSIZE);

	// Update the frequency of this character
	pLiteral->nFrequency++;
	m_nHuffmanLiteralsLeft--;

	// If we have coded enough literals, then generate/regenerate the huffman tree
	if (!m_nHuffmanLiteralsLeft)
	{
		if (m_bHuffmanLiteralFullyActive)
		{
			m_nHuffmanLiteralsLeft	= xbLZSS_HUFF_DELAY;
			xbHuffmanGenerate(m_pHuffmanLiteralTree, NULL, xbLZSS_HUFF_LITERAL_ALPHABETSIZE, xbLZSS_HUFF_LITERAL_FREQMOD);
		}
		else
		{
			m_nHuffmanLiteralIncrement += (xbLZSS_HUFF_LITERAL_ALPHABETSIZE*3)/2;
			if (m_nHuffmanLiteralIncrement >= xbLZSS_HUFF_DELAY)
				m_bHuffmanLiteralFullyActive = true;

			m_nHuffmanLiteralsLeft	= (xbLZSS_HUFF_LITERAL_ALPHABETSIZE*3)/2;
			xbHuffmanGenerate(m_pHuffmanLiteralTree, NULL, xbLZSS_HUFF_LITERAL_ALPHABETSIZE, xbLZSS_HUFF_LITERAL_FREQMOD);
		}
	}

	xbAssert((xbNptr(pLiteral) - xbNptr(m_pHuffmanLiteralTree)) % sizeof(xbHuffmanNode) == 0);
	xbAssert(pLiteral >= m_pHuffmanLiteralTree && pLiteral < m_pHuffmanLiteralTree + ((2*xbLZSS_HUFF_LITERAL_ALPHABETSIZE)-1));
	return ulong((xbNptr(pLiteral) - xbNptr(m_pHuffmanLiteralTree)) / sizeof(xbHuffmanNode));
}


// CompressedStreamReadLen()
uint xbLZSSdecompress::tmpDataReadLen(uint nCode)
{
	if (nCode <= 263)
		return nCode - 256;

	xbAssert(nCode < xbLZSS_HUFF_LITERAL_ALPHABETSIZE); // nCode < 292
	// nCode increases by 4 for every extra bit added, 
	// 264 = 0x008 + 2 bits in nCode + 1 bit to read =  4 bits	-> range: 0x008 - 0x00F 
	// 288 = 0x200 + 2 bits in nCode + 7 bit to read = 10 bits	-> range: 0x200 - 0x3FF
	nCode = nCode - 264;
	uint nExtraBits	= (nCode >> 2) + 1;
	uint nMSBValue	= 1 << (nExtraBits+2);
	nCode = nCode & 0x0003;

	// Read in the extra bits
	uint nValue = tmpDataReadBits(nExtraBits);

	return nValue + nMSBValue + (nCode << nExtraBits);
}


// CompressedStreamReadOffset()
uint xbLZSSdecompress::tmpDataReadOffset()
{
	// Read in a huffman code from the compressed stream
	xbHuffmanNode *pCode = tmpDataReadHuffman(m_pHuffmanOffsetTree, xbLZSS_HUFF_OFFSET_ALPHABETSIZE);

	xbAssert((xbNptr(pCode) - xbNptr(m_pHuffmanOffsetTree)) % sizeof(xbHuffmanNode) == 0);
	xbAssert(pCode >= m_pHuffmanOffsetTree && pCode < m_pHuffmanOffsetTree + xbLZSS_HUFF_OFFSET_ALPHABETSIZE);

	// Update the frequency of this character
	pCode->nFrequency++;

	uint nCode = uint((xbNptr(pCode) - xbNptr(m_pHuffmanOffsetTree)) / sizeof(xbHuffmanNode));

	uint nValue;
	if (nCode <= 3)
		nValue = nCode;
	else
	{
		// nCode increases by 2 for every extra bit added, 4 = 1 bit
		//  4 = 0x00004 + 1 bit in nCode +  1 bit to read =  3 bits	-> range: 0x4 - 0x7 
		//  6 = 0x00008 + 1 bit in nCode +  2 bit to read =  4 bits	-> range: 0x8 - 0xF 
		// 28 = 0x04000 + 1 bit in nCode + 13 bit to read = 15 bits	-> range: 0x4000 - 0x7FFF
		nCode = nCode - 4;
		uint nExtraBits	= (nCode >> 1) + 1;
		uint nMSBValue	= 1 << (nExtraBits+1);
		nCode = nCode & 0x0001;

		// Read in the extra bits
		nValue = tmpDataReadBits(nExtraBits);
		nValue = nValue + nMSBValue + (nCode << nExtraBits);
	}

	// Update the frequency (above)
	m_nHuffmanOffsetsLeft--;

	// If we have coded enough literals, then generate/regenerate the huffman tree
	if (!m_nHuffmanOffsetsLeft)
	{
		if (m_bHuffmanOffsetFullyActive)
		{
			m_nHuffmanOffsetsLeft	= xbLZSS_HUFF_DELAY;
			xbHuffmanGenerate(m_pHuffmanOffsetTree, NULL, xbLZSS_HUFF_OFFSET_ALPHABETSIZE, xbLZSS_HUFF_OFFSET_FREQMOD);
		}
		else
		{
			m_nHuffmanOffsetIncrement += (xbLZSS_HUFF_OFFSET_ALPHABETSIZE*3)/2;
			if (m_nHuffmanOffsetIncrement >= xbLZSS_HUFF_DELAY)
				m_bHuffmanOffsetFullyActive = true;

			m_nHuffmanOffsetsLeft	= (xbLZSS_HUFF_OFFSET_ALPHABETSIZE*3)/2;
			xbHuffmanGenerate(m_pHuffmanOffsetTree, NULL, xbLZSS_HUFF_OFFSET_ALPHABETSIZE, xbLZSS_HUFF_OFFSET_FREQMOD);
		}
	}

	return nValue;

}

void xbLZSSdecompressPush::outpDataAskRead(outpStep step,uint cByte)
{
	if (cByte > uint(m_outpData.Length))
	{
		m_pOutpDataStart = (uchar*)m_outpData.GetWritePtr(cByte);
	}
	else
		m_pOutpDataStart = (uchar*)(LPCVOID)m_outpData;
	m_pOutpDataEnd = m_pOutpDataStart + cByte;
	m_pOutpData = m_pOutpDataStart;
	m_outpStep = step;
}

void xbLZSSdecompressPush::outpDataFlush(bool bEnd,bool bClose)
{
	if (m_pOutpData > m_pOutpDataStart)
	{
		onOutpDataReady(bEnd,bClose);
		xbAssert(m_pOutpData == m_pOutpDataStart);
	}

	if (initNotifCb())
		m_prNotifCb->onDecompressFlush(this,bEnd,bClose);
}

void xbLZSSdecompressPush::outpDataWrite(const void *_pData,ulong DataLg)
{
	if (DataLg == 0)
		return;

	if (m_outpStep == outpStream)
	{
		xbAssert(m_outpStep == outpStream);
		m_prStm->Write(_pData,DataLg);
		return;
	}
	
	const uchar *pData = (const uchar *)_pData;
	while(DataLg > 0)
	{
		if (m_pOutpData + DataLg <= m_pOutpDataEnd)
		{
			memcpy(m_pOutpData,pData,DataLg);
			m_pOutpData += DataLg;
			return;
		}
		if (m_pOutpData < m_pOutpDataEnd)
		{
			int lg = int(xbNptr(m_pOutpDataEnd) - xbNptr(m_pOutpData));
			memcpy(m_pOutpData,pData,lg);
			m_pOutpData += lg;
			pData += lg;
			DataLg -= lg;
		}

		outpDataFlush();
		if (m_outpStep == outpStream)
		{
			xbAssert(m_pOutpData == m_pOutpDataStart);
			m_prStm->Write(pData,DataLg);
			return;
		}
	}
}

void xbLZSSdecompressPush::onOutpDataReady(bool bEnd,bool bClose)
{
	try
	{
		ulong cByteData = ulong(xbNptr(m_pOutpData) - xbNptr(m_pOutpDataStart));
		switch(m_outpStep)
		{
		case outpHeader :  //code page + nb hdr param
			if (cByteData < (sizeof(ulong) * 2))
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream header invalid (size)");
				return;
			}

			m_cp = *(ulong*)m_pOutpDataStart;
			m_pOutpDataStart += 4;

			m_outpCnt = *(ulong*)m_pOutpDataStart;
			m_pOutpDataStart += 4;
			if (m_outpCnt <= 0)
				goto headerEnd;
			outpDataAskRead(outpHeaderLengths,sizeof(ulong)*2); // name length + val length
			return;
		case outpHeaderLengths :  // name length + val length
			if (cByteData < (sizeof(ulong) * 2))
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream header invalid (size)");
				return;
			}
			xbAssert(m_outpCnt > 0);
			m_outpCnt--;
			m_outpParam.name.Length = *(ulong*)m_pOutpDataStart;
			m_pOutpDataStart += 4;

			m_outpParam.value.Length = *(ulong*)m_pOutpDataStart;
			m_pOutpDataStart += 4;
			if (m_outpParam.name.Length + m_outpParam.value.Length <= 0)
				goto headerStringVoid;
			outpDataAskRead(outpHeaderStrings,m_outpParam.name.Length + m_outpParam.value.Length); // length = (name length + val length)
			return;
		case outpHeaderStrings :  // length = (name length + val length)
			if (cByteData < ulong(m_outpParam.name.Length + m_outpParam.value.Length))
			{
				if (bEnd)
					xbThrow xbEcompress(STG_E_WRITEFAULT,"EPLZSS decompression: stream header invalid (size)");
				return;
			}

			if (m_outpParam.name.IsValid())
			{
				memcpy((void*)(LPCSTR)m_outpParam.name,m_pOutpDataStart,m_outpParam.name.Length);
				m_pOutpDataStart += m_outpParam.name.Length;
			}
			if (m_outpParam.value.IsValid())
			{
				memcpy((void*)(LPCSTR)m_outpParam.value,m_pOutpDataStart,m_outpParam.value.Length);
				m_pOutpDataStart += m_outpParam.value.Length;
			}
	headerStringVoid:
			addHeaderParam(m_outpParam.name,m_outpParam.value,m_cp);
			if (m_outpCnt <= 0)
				goto headerEnd;
			outpDataAskRead(outpHeaderLengths,sizeof(ulong)*2); // name length + val length
			return;
	headerEnd:
			if (m_bAcceptFileList)
				outpDataAskRead(outpFile,sizeof(ulong)*4); //nb param + status + length + name length
			else
			{
				m_pOutpDataEnd = m_pOutpData = m_pOutpDataStart = NULL;
				m_outpStep = outpStream;
			}
			if (initNotifCb())
				m_prNotifCb->onDecompressStart(this);
			return;
		case outpHeaderFile ://code page + nb param + status + length + name length
			if (cByteData < (sizeof(ulong) * 5))
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream header invalid (size)");
				return;
			}

			m_cp = *(ulong*)m_pOutpDataStart;
			m_pOutpDataStart += 4;
			cByteData -= 4;
			if (initNotifCb())
				m_prNotifCb->onDecompressStart(this);
		case outpFile ://nb param + status + length + name length
			if (cByteData < (sizeof(ulong) * 4))
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream header invalid (size)");
				return;
			}
			{
				m_outpCnt = *(ulong*)m_pOutpDataStart;
				m_pOutpDataStart += 4;
			}
			{
				m_outpFile.status = *(ulong*)m_pOutpDataStart;
				m_pOutpDataStart += 4;
			}
			{
				m_outpFile.length = *(ulong*)m_pOutpDataStart;
				m_pOutpDataStart += 4;
			}
			{
				m_outpFile.path.Length = *(ulong*)m_pOutpDataStart;
				m_pOutpDataStart += 4;
			}
			if (m_outpFile.path.Length > 0)
			{
				outpDataAskRead(outpFilePath,m_outpFile.path.Length);// length = (path length)
				return;
			}
			goto fileEnd;
		case outpFilePath :  // length = (path length)
			if (cByteData < ulong(m_outpFile.path.Length))
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream header invalid (size)");
				return;
			}

			xbAssert(m_outpFile.path.IsValid());
			memcpy((void*)(LPCSTR)m_outpFile.path,m_pOutpDataStart,m_outpFile.path.Length);
			m_pOutpDataStart += m_outpFile.path.Length;
			goto fileEnd;
		case outpFileLengths :  // name length + val length
			if (cByteData < (sizeof(ulong) * 2))
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream header invalid (size)");
				return;
			}
			xbAssert(m_outpCnt > 0);
			m_outpCnt--;
			m_outpParam.name.Length = *(ulong*)m_pOutpDataStart;
			m_pOutpDataStart += 4;

			m_outpParam.value.Length = *(ulong*)m_pOutpDataStart;
			m_pOutpDataStart += 4;
			if (m_outpParam.name.Length + m_outpParam.value.Length <= 0)
				goto fileStringVoid;
			outpDataAskRead(outpFileStrings,m_outpParam.name.Length + m_outpParam.value.Length); // length = (name length + val length)
			return;
		case outpFileStrings :  // length = (name length + val length)
			if (cByteData < ulong(m_outpParam.name.Length + m_outpParam.value.Length))
			{
				if (bEnd)
					xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream header invalid (size)");
				return;
			}

			if (m_outpParam.name.IsValid())
			{
				memcpy((void*)(LPCSTR)m_outpParam.name,m_pOutpDataStart,m_outpParam.name.Length);
				m_pOutpDataStart += m_outpParam.name.Length;
			}
			if (m_outpParam.value.IsValid())
			{
				memcpy((void*)(LPCSTR)m_outpParam.value,m_pOutpDataStart,m_outpParam.value.Length);
				m_pOutpDataStart += m_outpParam.value.Length;
			}
	fileStringVoid:
			addFileParam(m_outpParam.name,m_outpParam.value,m_cp);
			if (m_outpCnt <= 0)
				goto fileHeaderEnd;
			outpDataAskRead(outpFileLengths,sizeof(ulong)*2); // name length + val length
			return;
	fileEnd:
			addFile(m_outpFile.path,m_outpFile.length,m_cp);
			if (m_outpCnt <= 0)
				goto fileHeaderEnd;
			outpDataAskRead(outpFileLengths,sizeof(ulong)*2); // name length + val length
			return;
	fileHeaderEnd:
			m_pOutpDataEnd = m_pOutpData = m_pOutpDataStart = NULL;
			m_outpStep = outpStream;
			if (initNotifCb())
				m_prNotifCb->onDecompressNewFile(this,m_cp,m_outpFile.path,m_outpFile.length);
			return;
		default:
			xbThrow xbEcompressCorrupt(STG_E_WRITEFAULT,"EPLZSS decompression: stream invalid (step)");
		}
	}
	catch(...)
	{
		m_outpStep = outpNone;
		throw;
	}
}




//////////////////////////////////////////////////////////////////////////////////////////
// xbLZSSplug : plugin for compression and decompression
//////////////////////////////////////////////////////////////////////////////////////////
bool xbLZSSplug::CanWorkWithType(LPCSTR pszType, IxbInputStream *pStm) const
{
	if ((!pszType || !*pszType) && !pStm)
		xbThrow xbEcompress("EPLZSS compression : invalid argument for type detection","xbLZSSplug::CanWorkWithType()");
	if (m_bDestruction)
		throwEnd("type detection aborted","CanWorkWithType()");
	if (pStm)
	{
		xbRefQIPtr<IxbSeekStream>	prSkStm(pStm,xbOp_Optional);

		if (prSkStm.IsEmpty())
		{
			if (!pszType || !*pszType)
				return false;
		}
		else
		{
			ulong pos = prSkStm->GetPosition();
			bool bRet = false;
			for(;;)
			{
				xbLZSS_Header hdr;
				if (pStm->Read(&hdr,sizeof(hdr),false) != sizeof(hdr))
					break;

				if (memcmp(hdr.m_algid,xbLZSS_ALGID,sizeof(hdr.m_algid)) != 0)
					break;
				if (!xbLZSS_ALGMODE_VALID(hdr.m_mode))
					break;
				if (hdr.m_cByteBlockReal < xbLZSS_BLOCKSIZE_MIN || hdr.m_cByteBlockReal > xbLZSS_BLOCKSIZE_MAX)
					break;
				bRet = true;
			}
			prSkStm->Seek(pos);
			return bRet;
		}
	}

	if (xbStricmp(pszType,"eplzss") == 0)
		return true;
	if (xbStricmp(pszType,"eplz") == 0)
		return true;
	return false;
}

bool xbLZSSplug::Decompress(IxbInputStream *pStm, ulong caps, xbRefPtr<IxbDecompressPull> *pprUncompStm,xbOpMode opm)
{
	if (m_bDestruction)
		throwEnd("decompression aborted","Decompress(pull)");
	if (opm == xbOp_Required)
		xbThrow xbEcompress(E_NOTIMPL,"EPLZSS compression : decompression in pull mode not supported","xbLZSSplug::Decompress(pull)");
	return false;
}

bool xbLZSSplug::Decompress(IxbOutputStream *pStm, ulong caps, xbRefPtr<IxbDecompressPush> *pprUncompStm,xbOpMode opm)
{
	if (m_bDestruction)
		throwEnd("decompression aborted","Decompress(push)");
	if (caps != 0)
	{
		if (opm == xbOp_Required)
			xbThrow xbEcompress(E_NOTIMPL,"EPLZSS compression : invalid mode for decompression","xbLZSSplug::Decompress(push)");
		return false;
	}
	xbLZSSdecompressPush *plg = xbDnew xbLZSSdecompressPush();
	try
	{
//		plg->setFactory(pFactory);
		plg->Create();

		if (pStm)
		{
			plg->New();
			plg->SetOutputStream(pStm);
		}

		(*pprUncompStm) = plg;

		plg->Release();
	}
	catch(...)
	{
		plg->Release();
		throw;
	}
	return true;
}

bool xbLZSSplug::Compress(IxbOutputStream *pStm, ulong caps, xbRefPtr<IxbCompressPush> *pprCompStm,xbOpMode opm)
{
	if (m_bDestruction)
		throwEnd("compression aborted","Compress(push)");
	if (caps != 0)
	{
		if (opm == xbOp_Required)
			xbThrow xbEcompress(E_NOTIMPL,"EPLZSS compression : invalid mode for compression","xbLZSSplug::Compress(push)");
		return false;
	}
	xbLZSScompressPush *plg = xbDnew xbLZSScompressPush();
	try
	{
//		plg->setFactory(pFactory);
		plg->Create();

		if (pStm)
		{
			plg->New(pStm);
		}

		(*pprCompStm) = plg;

		plg->Release();
	}
	catch(...)
	{
		plg->Release();
		throw;
	}
	return true;
}

bool xbLZSSplug::Compress(IxbInputStream *pStm, ulong caps, xbRefPtr<IxbCompressPull> *pprCompStm,xbOpMode opm)
{
	if (m_bDestruction)
		throwEnd("compression aborted","Compress(pull)");
	if (opm == xbOp_Required)
		xbThrow xbEcompress(E_NOTIMPL,"EPLZSS compression : compression in pull mode not supported","xbLZSSplug::Compress(pull)");
	return false;
}

void xbLZSSplug::askClose(LPCSTR pReason)
{
	{
		xbSectLock lck(&m_sectPtr);
		if (pReason && m_closeReason.IsEmpty())
			m_closeReason = pReason;
	}
	Destroy();
}

xbString xbLZSSplug::getCloseReason() const
{
	xbSectLock lck(&m_sectPtr);
	xbString ret(m_closeReason);
	ret.OwnData();
	return ret;
}

xbString xbLZSSplug::GetCompressLabel(bool bShort) const
{
	xbString ret("EPLZSS compression");
	return ret;
}

bool xbLZSSplug::GetCompressLevelRange(int *pMin, int *pMax, int *pDflt) const
{
	if (pMin) 
		*pMin = 0;
	if (pMax) 
		*pMax = 9;
	if (pDflt)
		*pDflt = 7;
	return true;
}

bool xbLZSSplug::GetCompressBlockRange(int *pMin, int *pMax, int *pDflt) const
{
	if (pMin) 
		*pMin = xbLZSS_BLOCKSIZE_MIN;
	if (pMax) 
		*pMax = xbLZSS_BLOCKSIZE_MAX;
	if (pDflt)
		*pDflt = xbLZSS_BLOCKSIZE;
	return true;
}


bool xbLZSSplug::EnumCompressSetting(int no, xbString *pName, xbString *pLabel, int *pMin, int *pMax, int *pDflt) const
{
	return false;
}

ulong xbLZSSplug::GetCaps() const
{
	return xbCOMPRESSCAPS_HEADERPARAM|xbCOMPRESSCAPS_HEADERPARAM_ATSTART
		|xbCOMPRESSCAPS_FILELIST
		|xbCOMPRESSCAPS_FILEPARAM|xbCOMPRESSCAPS_FILEPARAM_ATSTART;

}

void xbLZSSplug::throwEnd(const xbString &strEnd,const xbString &strCtx) const
{
	if (!g_xbCompressPlugType.isNowStarted())
		xbThrow xbEhotPlug(E_ABORT,"EPLZSS compression : "+strEnd+", plugin in destruction",closeReasonLabel()+"xbLZSSplug::"+strCtx);
	xbThrow xbEcompressUser(E_ABORT,"EPLZSS compression : "+strEnd+", operation cancelled by application",closeReasonLabel()+"xbLZSSplug::"+strCtx);
}
#pragma warning(pop)









