/*
								+--------------------------------+
								|                                |
								|  ***   LamePak2 classes   ***  |
								|                                |
								|  Copyright © -tHE SWINe- 2008  |
								|                                |
								|          LamePak2.cpp          |
								|                                |
								+--------------------------------+
*/

/**
 *	@file LamePak2.cpp
 *	@author -tHE SWINe-
 *	@date 2008
 *	@brief simple compressed file format
 *
 *	@date 2007-02-25
 *
 *	this is first beta version if the file. todo - store path separator in pak header,
 *	re write TBuffer so it can realloc itself in a way std::vector can and try to avoid
 *	any (re)allocations while unpacking files. add function to purge block cache so
 *	it doesn't keep memory when no files are unpacked for longer periods of time
 *
 *	@date 2007-02-28
 *
 *	path separator is now in pak header and there's new packer verbose object.
 *	added compression method field to pak header.
 *
 *	@date 2008-08-08
 *
 *	added \#ifdef for windows 64
 *
 *	@date 2009-05-23
 *
 *	removed all instances of std::vector::reserve and replaced them by stl_ut::Reserve_*
 *
 *	@date 2009-10-20
 *
 *	fixed some warnings when compiling under VC 2005, implemented "Security
 *	Enhancements in the CRT" for VC 2008. compare against MyProjects_2009-10-19_
 *
 */

#include "NewFix.h"

#include "CallStack.h"
#include <vector>
#include <stdlib.h>
#include <limits.h>
#include <stdio.h>
#include <algorithm>
#include "Dir.h"
#include "Compress.h"
#include "MinMax.h"
#include "LamePak2.h"
#include "StlUtils.h"

/*
 *								=== compressors ===
 */

template <int n_method = method_BWT_A>
class CLegacy_Compressor : public CPak2PackerUtil::CCompressorIface {
protected:
	TBuffer &m_t_tmp, &m_t_tmp2, &m_t_tmp3;

public:
	CLegacy_Compressor(CPak2PackerUtil::CTempBufferPack &r_t_temp_buffers)
		:m_t_tmp(r_t_temp_buffers[0]), m_t_tmp2(r_t_temp_buffers[1]),
		m_t_tmp3(r_t_temp_buffers[2])
	{
		_ASSERTE(n_method >= method_BWT_A && n_method <= method_BWT_C);
	}

	static size_t n_TempBuffer_Num()
	{
		return 3;
	}

	virtual bool Compress(const TBuffer &r_t_in_buffer, TBuffer &r_t_out_buffer, bool b_skip_BWT = false)
	{
		if(!b_skip_BWT) {
			if(!CBurrowsWheelerTransform::Encode(r_t_in_buffer, m_t_tmp))
				return false;
			// just a single thread
		}
		// bwt

		if(n_method == method_BWT_A || n_method == method_BWT_B) {
			if(b_skip_BWT) {
				if(!CMoveToFrontTransform::Encode(r_t_in_buffer, m_t_tmp, (n_method == method_BWT_A)?
				   CMoveToFrontTransform::algo_MTF : CMoveToFrontTransform::algo_MTF_1))
					return false;
			} else {
				CMoveToFrontTransform::Encode(m_t_tmp, (n_method == method_BWT_A)?
					CMoveToFrontTransform::algo_MTF : CMoveToFrontTransform::algo_MTF_1);
			}
			// mtf

			if(!CRunLengthCodec::Encode(m_t_tmp, m_t_tmp2))
				return false;
			// rle
		} else if(n_method == method_BWT_C) {
			if(!CRunLengthCodec::Encode(m_t_tmp, m_t_tmp3))
				return false;
			// rle

			if(!CInversionFrequenciesCodec::Encode(m_t_tmp3, m_t_tmp2,
			   CInversionFrequenciesCodec::sort_FreqDescending))
				return false;
			// sif

#ifdef _DEBUG
			if(!CInversionFrequenciesCodec::Decode(m_t_tmp2, m_t_tmp))
				return false;
			_ASSERTE(m_t_tmp3.n_Size() == m_t_tmp.n_Size());
			_ASSERTE(!memcmp(m_t_tmp3.p_Data(), m_t_tmp.p_Data(), m_t_tmp.n_Size()));
#endif // _DEBUG
			// debug SIF
		}

		if(!CHuffmanCodec::Encode(m_t_tmp2, r_t_out_buffer))
			return false;
		// huff

		return true;
	}

	virtual bool Decompress(const TBuffer &r_t_in_buffer, TBuffer &r_t_out_buffer)
	{
		if(!CHuffmanCodec::Decode(r_t_in_buffer, m_t_tmp))
			return false;
		// ihuff

		if(n_method == method_BWT_A || n_method == method_BWT_B) {
			if(!CRunLengthCodec::Decode(m_t_tmp, m_t_tmp2))
				return false;
			// irle

			if(n_method == method_BWT_A)
				CMoveToFrontTransform::Decode(m_t_tmp2, CMoveToFrontTransform::algo_MTF);
			else /*if(m_t_header.n_method == method_BWT_B)*/ {
				_ASSERTE(n_method == method_BWT_B);
				CMoveToFrontTransform::Decode(m_t_tmp2, CMoveToFrontTransform::algo_MTF_1);
			}
			// imtf
		} else if(n_method == method_BWT_C) {
			if(!CInversionFrequenciesCodec::Decode(m_t_tmp, m_t_tmp3))
				return false;
			// isif

			if(!CRunLengthCodec::Decode(m_t_tmp3, m_t_tmp2))
				return false;
			// irle
		}

		if(!CBurrowsWheelerTransform::Decode(m_t_tmp2, r_t_out_buffer))
			return false;
		// ibwt

		return true;
	}
};

template <bool b_use_mtf_1 = false, class CRLE0_Codec = CRLE0_HuffmanCodec>
class CBWT_MTF_RLE0_Huff_Compressor : public CPak2PackerUtil::CCompressorIface {
protected:
	TBuffer &m_t_tmp, &m_t_tmp1;

public:
	CBWT_MTF_RLE0_Huff_Compressor(CPak2PackerUtil::CTempBufferPack &r_t_temp_buffers)
		:m_t_tmp(r_t_temp_buffers[0]), m_t_tmp1(r_t_temp_buffers[1])
	{}

	static size_t n_TempBuffer_Num()
	{
		return 2; // 2 because of decompress, compress would run with 1
	}

	virtual bool Compress(const TBuffer &r_t_src, TBuffer &r_t_dest, bool b_skip_BWT = false)
	{
		if(b_skip_BWT) {
			if(!CMoveToFrontTransform::Encode(r_t_src, m_t_tmp, (b_use_mtf_1)?
			   CMoveToFrontTransform::algo_MTF_1 : CMoveToFrontTransform::algo_MTF))
				return false; // un-MTF to m_t_tmp, RLE0 will pick it up there
		} else {
			if(!CBurrowsWheelerTransform::Encode(r_t_src, m_t_tmp))
				return false;
			CMoveToFrontTransform::Encode(m_t_tmp, (b_use_mtf_1)?
				CMoveToFrontTransform::algo_MTF_1 : CMoveToFrontTransform::algo_MTF);
		}
		if(!CRLE0_Codec::Encode(m_t_tmp, r_t_dest) || !CCRC32CheckCodec::Encode(r_t_dest))
			return false;
		return true;
	}

	virtual bool Decompress(const TBuffer &r_t_src, TBuffer &r_t_dest)
	{
		if(!CCRC32CheckCodec::Decode(r_t_src, m_t_tmp) || !CRLE0_Codec::Decode(m_t_tmp, m_t_tmp1))
			return false;
		CMoveToFrontTransform::Decode(m_t_tmp1, (b_use_mtf_1)?
			CMoveToFrontTransform::algo_MTF_1 : CMoveToFrontTransform::algo_MTF);
		if(!CBurrowsWheelerTransform::Decode(m_t_tmp1, r_t_dest))
			return false;
		return true;
	}
};

class CBWT_RLEExp_SIFMod_Huff_Compressor : public CPak2PackerUtil::CCompressorIface {
protected:
	TBuffer &m_t_tmp, &m_t_tmp2, &m_t_tmp3, &m_t_tmp4, &m_t_tmp5;

public:
	CBWT_RLEExp_SIFMod_Huff_Compressor(CPak2PackerUtil::CTempBufferPack &r_t_temp_buffers)
		:m_t_tmp(r_t_temp_buffers[0]), m_t_tmp2(r_t_temp_buffers[1]),
		m_t_tmp3(r_t_temp_buffers[2]), m_t_tmp4(r_t_temp_buffers[3]),
		m_t_tmp5(r_t_temp_buffers[4])
	{}

	static size_t n_TempBuffer_Num()
	{
		return 5; // 5 because of decompress, if b_skip_BWT is set, compress could run with 4
	}

	virtual bool Compress(const TBuffer &r_t_src, TBuffer &r_t_dest, bool b_skip_BWT = false)
	{
		if((!b_skip_BWT && !CBurrowsWheelerTransform::Encode(r_t_src, m_t_tmp)) ||
		   !CModifiedRLECodec::Encode((b_skip_BWT)? r_t_src : m_t_tmp, m_t_tmp2, m_t_tmp3) ||
		   !CInversionFrequenciesCodec::ModifiedEncode(m_t_tmp2, m_t_tmp,
		   m_t_tmp4, m_t_tmp5, CInversionFrequenciesCodec::sort_FreqDescending))
			return false;
		// m_t_tmp3 contains run lengths
		// m_t_tmp contains encoded IF (not compressible)
		// m_t_tmp4 contains IF permutation table
		// m_t_tmp2 is unused
		// m_t_tmp5 is filled with rubbish

		uint32_t n_rle_size = m_t_tmp3.n_Size();
		if(!AppendBuffer(m_t_tmp4, m_t_tmp3) ||
		   !AppendBuffer(m_t_tmp4, &n_rle_size, sizeof(uint32_t)))
			return false;
		// append run lengths to the IF permutation table, append size of the run lengths at the end

		uint32_t n_IF_stage_size = m_t_tmp.n_Size();
		if(!CHuffmanCodec::Encode(m_t_tmp4, r_t_dest) ||
		   !AppendBuffer(r_t_dest, m_t_tmp) || // append (incompressible) IF stage
		   !AppendBuffer(r_t_dest, &n_IF_stage_size, sizeof(uint32_t)) || // append IF stage length
		   !CCRC32CheckCodec::Encode(r_t_dest)) // calculate CRC
			return false;
		// encode compressible parts

		return true;
	}

	virtual bool Decompress(const TBuffer &r_t_src, TBuffer &r_t_dest)
	{
		if(!CCRC32CheckCodec::Decode(r_t_src, m_t_tmp5))
			return false;
		// check compressed CRC

		if(m_t_tmp5.n_Size() < sizeof(uint32_t))
			return false;
		uint32_t n_IF_stage_size = *(uint32_t*)(m_t_tmp5.p_Data() + (m_t_tmp5.n_Size() - sizeof(uint32_t)));
		// read IF stage size

		if(!SliceBuffer(m_t_tmp5, m_t_tmp, m_t_tmp2, n_IF_stage_size + sizeof(uint32_t)))
			return false;
		m_t_tmp2.Resize(n_IF_stage_size, true); // erase the uint32_t at the end
		// m_t_tmp contains huffman-encoded data
		// m_t_tmp2 contains IF stage

		if(!CHuffmanCodec::Decode(m_t_tmp, m_t_tmp3) || m_t_tmp3.n_Size() < sizeof(uint32_t))
			return false;
		// m_t_tmp3 contains IF permutation table and the run lenngths

		uint32_t n_rl_size = *(uint32_t*)(m_t_tmp3.p_Data() + (m_t_tmp3.n_Size() - sizeof(uint32_t)));
		// read length of RLE run lengths buffer

		if(!SliceBuffer(m_t_tmp3, m_t_tmp, m_t_tmp4, n_rl_size + sizeof(uint32_t)))
			return false;
		m_t_tmp4.Resize(n_rl_size, true); // erase the uint32_t at the end
		// m_t_tmp contains IF permutation table
		// m_t_tmp4 contains run lengths

		if(!CInversionFrequenciesCodec::ModifiedDecode(m_t_tmp2, m_t_tmp, m_t_tmp3, m_t_tmp5) ||
		   !CModifiedRLECodec::Decode(m_t_tmp3, m_t_tmp4, m_t_tmp) ||
		   !CBurrowsWheelerTransform::Decode(m_t_tmp, r_t_dest))
			return false;
		// m_t_tmp5 is temporary rubbish
		return true;
	}

protected:
	static inline bool AppendBuffer(TBuffer &r_t_dest, const TBuffer &r_t_src)
	{
		return AppendBuffer(r_t_dest, r_t_src.p_Data(), r_t_src.n_Size());
	}

	static bool AppendBuffer(TBuffer &r_t_dest, const void *p_data, size_t n_size)
	{
		if(!r_t_dest.Grow(n_size))
			return false;
		memcpy(r_t_dest.p_Data() + (r_t_dest.n_Size() - n_size),
			p_data, n_size);
		return true;
	}

	static bool SliceBuffer(const TBuffer &r_t_src, TBuffer &r_t_first, TBuffer &r_t_second, size_t n_second_size)
	{
		if(n_second_size > r_t_src.n_Size() ||
		   !r_t_first.Resize(r_t_src.n_Size() - n_second_size, false) ||
		   !r_t_second.Resize(n_second_size))
			return false;
		// alloc

		memcpy(r_t_first.p_Data(), r_t_src.p_Data(), r_t_first.n_Size());
		memcpy(r_t_second.p_Data(), r_t_src.p_Data() + r_t_first.n_Size(), n_second_size);

		return true;
	}
};

/*
 *								=== ~compressors ===
 */

/*
 *								=== CPak2PackerUtil::CCodecBank ===
 */

bool CPak2PackerUtil::CCodecBank::Compress(const TBuffer &r_t_in_buffer,
	TBuffer &r_t_out_buffer, bool b_skip_BWT /*= false*/)
{
	return Run(m_r_temp_buffers, r_t_in_buffer, r_t_out_buffer, b_skip_BWT, m_n_codec, true);
}

bool CPak2PackerUtil::CCodecBank::Decompress(const TBuffer &r_t_in_buffer, TBuffer &r_t_out_buffer)
{
	return Run(m_r_temp_buffers, r_t_in_buffer, r_t_out_buffer, false, m_n_codec, false);
}

bool CPak2PackerUtil::CCodecBank::Run(CTempBufferPack &temp_buffers, const TBuffer &r_t_in_buffer,
	TBuffer &r_t_out_buffer, bool b_skip_BWT, int n_codec, bool b_compress)
{
	CCompressorIface *p_compressor_list[method_Max];
	memset(p_compressor_list, 0, sizeof(p_compressor_list));
	// null everything

	CLegacy_Compressor<method_BWT_A> BWT_A(temp_buffers);
	CLegacy_Compressor<method_BWT_B> BWT_B(temp_buffers);
	CLegacy_Compressor<method_BWT_C> BWT_C(temp_buffers);
	_ASSERTE(CHuffmanCodec::max_CodeBitNum == 16);
	_ASSERTE(CRunLengthCodec::min_RunLength == 3);
	p_compressor_list[method_BWT_A] = &BWT_A;
	p_compressor_list[method_BWT_B] = &BWT_B;
	p_compressor_list[method_BWT_C] = &BWT_C;
	// legacy codecs

	CBWT_MTF_RLE0_Huff_Compressor<true, CRLE0_HuffmanCodec> BWT_B0(temp_buffers);
	_ASSERTE(CRLE0_HuffmanCodec::max_CodeBitNum == 16);
	CBWT_MTF_RLE0_Huff_Compressor<false, CRLE0_HuffmanCodec_1> BWT_A0_1(temp_buffers);
	CBWT_MTF_RLE0_Huff_Compressor<true, CRLE0_HuffmanCodec_1> BWT_B0_1(temp_buffers);
	_ASSERTE(CRLE0_HuffmanCodec_1::max_CodeBitNum == 16);
	_ASSERTE(CRLE0_HuffmanCodec_1::run_Chaining == 2);
	_ASSERTE(sizeof(CRLE0_HuffmanCodec_1::CHuffRL::_TySymbol) == sizeof(uint8_t));
	CBWT_MTF_RLE0_Huff_Compressor<false, CRLE0_HuffmanCodec_3> BWT_A0_3(temp_buffers);
	CBWT_MTF_RLE0_Huff_Compressor<true, CRLE0_HuffmanCodec_3> BWT_B0_3(temp_buffers);
	_ASSERTE(CRLE0_HuffmanCodec_3::max_CodeBitNum == 16);
	p_compressor_list[method_BWT_B0] = &BWT_B0;
	p_compressor_list[method_BWT_A0_1] = &BWT_A0_1;
	p_compressor_list[method_BWT_B0_1] = &BWT_B0_1;
	p_compressor_list[method_BWT_A0_3] = &BWT_A0_3;
	p_compressor_list[method_BWT_B0_3] = &BWT_B0_3;
	// after 205: MTF codecs

	CBWT_RLEExp_SIFMod_Huff_Compressor BWT_E(temp_buffers);
	_ASSERTE(CModifiedRLECodec::min_RunLength == 3);
	_ASSERTE(CModifiedRLECodec::expCode_BitGranularity == 1);
	_ASSERTE(CModifiedRLECodec::expCode_MinWidth == 2);
	_ASSERTE(CInversionFrequenciesCodec::symbol_FreqThresh == 8);
	_ASSERTE(CInversionFrequenciesCodec::max_CodeBitNum8 == 16);
	_ASSERTE(CInversionFrequenciesCodec::max_CodeBitNum16 == 17);
	_ASSERTE(CInversionFrequenciesCodec::max_CodeBitNum32 == 24);
	p_compressor_list[method_BWT_E] = &BWT_E;
	// after 205: SIF-mod codec

	if(n_codec < 0 || n_codec >= method_Max || !p_compressor_list[n_codec])
		return false;
	// no codec

	if(b_compress)
		return p_compressor_list[n_codec]->Compress(r_t_in_buffer, r_t_out_buffer, b_skip_BWT);
	else
		return p_compressor_list[n_codec]->Decompress(r_t_in_buffer, r_t_out_buffer);
	// run the codec
}

/*
 *								=== ~CPak2PackerUtil::CCodecBank ===
 */

/*
 *								=== CPak2PackerUtil ===
 */

//const char CPak2PackerUtil::n_path_separator = CDirectory::path_Separator;
//const short CPak2PackerUtil::n_pak_version = 205;
const uint32_t CPak2PackerUtil::n_raw_data_flag = uint32_t(1) << (8 * sizeof(uint32_t) - 1);

/*
 *	class CPak2PackerUtil::CBlockCounter
 *		- simple counter of blocks and block offsets
 */
class CPak2PackerUtil::CBlockCounter {
protected:
	const unsigned int m_n_block_size;
	unsigned int m_n_block, m_n_block_offset;

public:
	/*
	 *	CPak2PackerUtil::CBlockCounter::CBlockCounter(unsigned int n_block_size)
	 *		- default constructor; sets up block size
	 */
	CBlockCounter(unsigned int n_block_size)
		:m_n_block_size(n_block_size), m_n_block(0), m_n_block_offset(0)
	{}

	/*
	 *	boolCPak2PackerUtil::CBlockCounter:: operator +=(uint64_t n_size)
	 *		- allocate n_size bytes of space
	 *		- returns true on success, false on overflow (maximal size limit reached)
	 *		- note maximal size is block-size * UINT_MAX
	 */
	bool operator +=(uint64_t n_size)
	{
		_ASSERTE(m_n_block_offset < m_n_block_size);

		uint64_t n_block_num = n_size / m_n_block_size;
		unsigned int n_block_offset = n_size % m_n_block_size + m_n_block_offset;
		if(n_block_offset >= m_n_block_size) {
			++ n_block_num;
			n_block_offset -= m_n_block_size;
			_ASSERTE(n_block_offset < m_n_block_size);
		}
		// calculate new block offset and number of blocks

		if(m_n_block > UINT_MAX - n_block_num)
			return false;
		m_n_block = unsigned int(m_n_block + n_block_num);
		m_n_block_offset = n_block_offset;
		// increment counters

		return true;
	}

	/*
	 *	unsigned int CPak2PackerUtil::CBlockCounter::n_Block_Index() const
	 *		- returns zero-based index of first block with free space left in it
	 */
	unsigned int n_Block_Index() const
	{
		return m_n_block;
	}

	/*
	 *	unsigned int CPak2PackerUtil::CBlockCounter::n_Block_Offset() const
	 *		- returns offset in bytes to first free byte in the last block
	 */
	unsigned int n_Block_Offset() const
	{
		return m_n_block_offset;
	}

	/*
	 *	unsigned int CPak2PackerUtil::CBlockCounter::n_Block_Num() const
	 *		- returns number of blocks currently needed
	 */
	unsigned int n_Block_Num() const
	{
		return m_n_block + ((m_n_block_offset)? 1 : 0);
	}
};

/*
 *	CPak2PackerUtil::CPak2PackerUtil()
 *		- default constructor, sets default packer options
 */
CPak2PackerUtil::CPak2PackerUtil()
	:m_n_block_size(4 * 1048576), m_n_compression_level(level_Compress),
	m_p_verbose_obj(0), m_n_thread_num(1), m_b_test_decompress(true),
	m_n_compression_method(method_Default)
{}

bool CPak2PackerUtil::b_TestDecompress() const
{
	return m_b_test_decompress;
}

void CPak2PackerUtil::Enable_TestDecompress(bool b_enable)
{
	m_b_test_decompress = b_enable;
}

int CPak2PackerUtil::n_CompressionMethod() const
{
	return m_n_compression_method;
}

bool CPak2PackerUtil::Set_CompressionMethod(int n_method)
{
	if(n_method < method_BWT_A || n_method >= method_Max)
		return false;
	m_n_compression_method = n_method;
	return true;
}

/*
 *	unsigned int CPak2PackerUtil::n_BlockSize() const
 *		- returns block size
 */
size_t CPak2PackerUtil::n_BlockSize() const
{
	return m_n_block_size;
}

/*
 *	bool CPak2PackerUtil::Set_BlockSize(unsigned int n_block_size)
 *		- sets new block size, valid values are 1k - 100M
 *		- returns true for valid values, false for invalid values
 *		  (invalid values aren't set)
 */
bool CPak2PackerUtil::Set_BlockSize(size_t n_block_size)
{
	if(n_block_size < 1024 || n_block_size > 100 * 1048576)
		return false;
	m_n_block_size = n_block_size;
	return true;
}

/*
 *	int CPak2PackerUtil::n_CompressionLevel() const
 *		- returns compression level option (the only valid compression
 *		  levels at the time are 0: store and 1: compress (default))
 */
int CPak2PackerUtil::n_CompressionLevel() const
{
	return m_n_compression_level;
}

/*
 *	bool CPak2PackerUtil::Set_CompressionLevel(int n_compression_level)
 *		- sets compression level, the only valid compression
 *		  levels at the time are 0: store and 1: compress (default)
 *		- returns true upon accepting valid value,
 *		  false when rejecting given n_compression_level
 */
bool CPak2PackerUtil::Set_CompressionLevel(int n_compression_level)
{
	if(n_compression_level < level_Store || n_compression_level > level_ForceCompress)
		return false;
	m_n_compression_level = n_compression_level;
	return true;
}

/*
 *	CVerboseObject *CPak2PackerUtil::p_VerboseObject() const
 *		- returns current verbose object
 */
CPak2PackerUtil::CVerboseObject *CPak2PackerUtil::p_VerboseObject() const
{
	return m_p_verbose_obj;
}

/*
 *	void CPak2PackerUtil::Set_VerboseFunc(CVerboseObject *p_verbose)
 *		- p_verbose is verbose object which gets (differential) amounts of packer input
 *		  and output data; can be 0
 */
void CPak2PackerUtil::Set_VerboseFunc(CVerboseObject *p_verbose)
{
	m_p_verbose_obj = p_verbose;
}

/*
 *	int CPak2PackerUtil::n_Thread_Num() const
 *		- certain parts of compressor can run in parallel
 *		- returns number of threads
 */
int CPak2PackerUtil::n_Thread_Num() const
{
	return m_n_thread_num;
}

/*
 *	bool CPak2PackerUtil::Set_Thread_Num(int n_thread_num)
 *		- certain parts of compressor can run in parallel
 *		- sets number of threads, valid values are 1 to 64
 *		- returns true upon accepting valid value,
 *		  false when rejecting given n_thread_num
 */
bool CPak2PackerUtil::Set_Thread_Num(int n_thread_num)
{
	if(m_n_thread_num < 1 || m_n_thread_num > 64)
		return false;
	m_n_thread_num = n_thread_num;
	return true;
}

/*
 *	static int CPak2PackerUtil::n_Version()
 *		- returns packer version, which is stored as major * 100 + minor
 */
int CPak2PackerUtil::n_Version()
{
	return pak_Version;
}

/*
 *	bool CPak2PackerUtil::CreatePak(const char *p_s_filename,
 *		const std::vector<TFileInfo*> &r_file_list, const char *p_s_base_dir = 0)
 *		- creates archive in p_s_filename
 *		- r_file_list is list of input files, n_block_size is compression
 *		  block size (couple of megabytes is ideal for compression, but
 *		  smaller blocks compress faster)
 *		- p_s_base_dir is base directory, path to it will not be included in pak file names
 *		- returns true on success, false on failure
 *		- note if PAK2_PACKER_USE_STDERR is defined, error messages are printed to stderr
 */
bool CPak2PackerUtil::CreatePak(const char *p_s_filename,
	const std::vector<TFileInfo*> &r_file_list, const char *p_s_base_dir)
{
	std::vector<TNamedPak2FileInfo> file_info;
	unsigned int n_block_num;
	if(!CreateFileHeaders(r_file_list, p_s_base_dir, file_info, n_block_num))
		return false;
	// create file headers

	TBuffer t_toc;
	if(!Assemble_TOC(file_info, t_toc))
		return false;
	// assemble table of contents

	TBuffer t_packed_toc;
	if(!PackBuffer(t_toc, t_packed_toc)) {
#ifdef PAK2_PACKER_USE_STDERR
		fprintf(stderr, "error: failed to compress table of contents\n");
#endif
		return false;
	}
	// compress table of contents

	bool b_packed_toc = m_n_compression_level == level_ForceCompress ||
		(m_n_compression_level != level_Store && t_packed_toc.n_Size() < t_toc.n_Size());
	//bool b_packed_toc = t_packed_toc.n_Size() < t_toc.n_Size();
	unsigned int n_stored_toc_size = (b_packed_toc)? t_packed_toc.n_Size() : t_toc.n_Size();
	TPak2Header t_header = {
		pak_Version, m_n_compression_method, file_info.size(),
		CDirectory::path_Separator, m_n_block_size, n_block_num,
		n_stored_toc_size | ((!b_packed_toc)? n_raw_data_flag : 0)
	};
	// create file header

	FILE *p_fw;
#if defined(_MSC_VER) && !defined(__MWERKS__) && _MSC_VER >= 1400
	if(fopen_s(&p_fw, p_s_filename, "wb")) {
#else // _MSC_VER && !__MWERKS__ && _MSC_VER >= 1400
	if(!(p_fw = fopen(p_s_filename, "wb"))) {
#endif // _MSC_VER && !__MWERKS__ && _MSC_VER >= 1400
#ifdef PAK2_PACKER_USE_STDERR
		fprintf(stderr, "error: error opening file \'%s\' for writing\n", p_s_filename);
#endif
		return false;
	}
	// open output file

	if(fwrite(&t_header, sizeof(TPak2Header), 1, p_fw) != 1 ||
	   (!b_packed_toc && fwrite(t_toc.p_Data(), t_toc.n_Size(), 1, p_fw) != 1) ||
	   (b_packed_toc && fwrite(t_packed_toc.p_Data(),
	   t_packed_toc.n_Size(), 1, p_fw) != 1)) {
#ifdef PAK2_PACKER_USE_STDERR
		fprintf(stderr, "error: error writing header\n");
#endif
		fclose(p_fw);
		return false;
	}
	// write header

	if(m_p_verbose_obj) {
		uint16_t n_method = (m_n_compression_method != method_Adaptive)? m_n_compression_method :
			(t_packed_toc.n_Size() >= sizeof(uint16_t))? *(uint16_t*)t_packed_toc.p_Data() : -1;
		// get method

		m_p_verbose_obj->On_TOCCompress(t_toc.n_Size(), n_stored_toc_size, n_method);
	}
	// write 

	bool b_result = PackFiles(r_file_list, p_fw);
	// main procedure

	fclose(p_fw);
	// close output file

	m_t_comp_state.temp_buffers.Free_Memory();
	// clear temporary compression buffers

	return b_result;
}

/*
 *	bool CPak2PackerUtil::PackBuffer(const TBuffer &r_t_in_buffer,
 *		TBuffer &r_t_out_buffer)
 *		- packs r_t_in_buffer, outputs to r_t_out_buffer
 *		  which doesn't have to be allocated
 *		- returns true on success, false on failure
 */
bool CPak2PackerUtil::PackBuffer(const TBuffer &r_t_in_buffer, TBuffer &r_t_out_buffer)
{
#if 0
#ifdef __BWT_ENABLE_THREADED_ENCODE
	if(m_n_thread_num > 1) {
		if(!CBurrowsWheelerTransform::ThreadedEncode(r_t_in_buffer, m_t_tmp, m_n_thread_num))
			return false;
	} else {
		if(!CBurrowsWheelerTransform::Encode(r_t_in_buffer, m_t_tmp))
			return false;
	}
#else // __BWT_ENABLE_THREADED_ENCODE
	if(!CBurrowsWheelerTransform::Encode(r_t_in_buffer, m_t_tmp))
		return false;
	// just a single thread
#endif // __BWT_ENABLE_THREADED_ENCODE
	// bwt

	const int p_methods[] = {method_BWT_A, method_BWT_B, method_BWT_C};

	int n_method = PAK2_PACKER_METHOD;
	if(PAK2_PACKER_METHOD == method_Adaptive)
		method_BWT_C;
	// adaptively choose method (todo)

	if(n_method == method_BWT_A || n_method == method_BWT_B) {
		CMoveToFrontTransform::Encode(m_t_tmp, (n_method == method_BWT_A)?
			CMoveToFrontTransform::algo_MTF : CMoveToFrontTransform::algo_MTF_1);
		// mtf

		if(!CRunLengthCodec::Encode(m_t_tmp, m_t_tmp2))
			return false;
		// rle
	} else if(n_method == method_BWT_C) {
		if(!CRunLengthCodec::Encode(m_t_tmp, m_t_tmp3))
			return false;
		// rle

		if(!CInversionFrequenciesCodec::Encode(m_t_tmp3, m_t_tmp2,
		   CInversionFrequenciesCodec::sort_FreqDescending))
			return false;
		// sif

#ifdef _DEBUG
		if(!CInversionFrequenciesCodec::Decode(m_t_tmp2, m_t_tmp))
			return false;
		_ASSERTE(m_t_tmp3.n_Size() == m_t_tmp.n_Size());
		_ASSERTE(!memcmp(m_t_tmp3.p_Data(), m_t_tmp.p_Data(), m_t_tmp.n_Size()));
#endif // _DEBUG
		// debug SIF
	}

	if(!CHuffmanCodec::Encode(m_t_tmp2, r_t_out_buffer))
		return false;
	// huff
#endif // 0

	int n_method = m_n_compression_method;
	if(n_method == method_Adaptive) {
		if(!CBurrowsWheelerTransform::Encode(r_t_in_buffer, m_t_comp_state.t_bwt))
			return false;
		if(method_BWT_B0 >= method_Max)
			return false; // no methods to choose from
		for(int i = method_BWT_B0; i < method_Max; ++ i) {
			if(!CCodecBank(m_t_comp_state.temp_buffers, i).Compress(m_t_comp_state.t_bwt, r_t_out_buffer, true)) // common BWT
				return false;
			if(n_method == method_Adaptive || m_t_comp_state.t_best.n_Size() > r_t_out_buffer.n_Size()) {
				m_t_comp_state.t_best.Swap(r_t_out_buffer);
				n_method = i;
			}
		}
		// choose the best method, try them all

		m_t_comp_state.t_best.Swap(r_t_out_buffer);
		// swap back
	} else {
		if(!CCodecBank(m_t_comp_state.temp_buffers, n_method).Compress(r_t_in_buffer, r_t_out_buffer))
			return false;
		// compress using the selected method
	}

	if(m_b_test_decompress) {
		if(!CCodecBank(m_t_comp_state.temp_buffers, n_method).Decompress(r_t_out_buffer, m_t_comp_state.t_best)) {
#ifdef PAK2_PACKER_USE_STDERR
			fprintf(stderr, "error: decompress test failed: codec decompress error\n");
#endif // PAK2_PACKER_USE_STDERR
			return false;
		}
		if(r_t_in_buffer.n_Size() != m_t_comp_state.t_best.n_Size() ||
		   memcmp(r_t_in_buffer.p_Data(), m_t_comp_state.t_best.p_Data(), r_t_in_buffer.n_Size())) {
#ifdef PAK2_PACKER_USE_STDERR
			fprintf(stderr, "error: decompress test failed: the data is different\n");
#endif // PAK2_PACKER_USE_STDERR
			return false;
		}
	}
	// test decompress

	if(m_n_compression_method == method_Adaptive) {
		if(!r_t_out_buffer.Grow(sizeof(int16_t)))
			return false;
		uint8_t *p_data = r_t_out_buffer.p_Data();
		for(size_t i = r_t_out_buffer.n_Size() - sizeof(int16_t); i;) {
			-- i;
			p_data[i] = p_data[i - sizeof(int16_t)];
		}
		*(int16_t*)p_data = n_method;
	}
	// in case adaptive method is chosen, prepend the output buffer with the method for this block

	return true;
}

/*
 *	bool CPak2PackerUtil::PackFiles(const std::vector<TFileInfo*> &r_file_list, FILE *p_fw)
 *		- packs all files in r_file_list list and writes them to p_fw
 *		- returns true on success, false on failure
 */
bool CPak2PackerUtil::PackFiles(const std::vector<TFileInfo*> &r_file_list, FILE *p_fw)
{
	TBuffer t_buffer(m_n_block_size);
	if(t_buffer.b_Empty()) {
#ifdef PAK2_PACKER_USE_STDERR
		fprintf(stderr, "error: not enough memory\n");
#endif
		return false;
	}
	// alloc data buffer

	/*
	// an example of parallel stream processing
	const size_t n_worker_num = m_n_thread_num;
	const size_t n_queue_size = max(n_worker_num, 32); // at least 32, but not less than there are threads
	CProducerConsumerQueue<std::pair<int, TWorkItem> > work_queue(n_queue_size);
	COrderedProducerConsumerQueue<TWorkItem, int> ordered_queue(n_queue_size);
	std::vector<CWorker> workers(n_worker_num);

	_ASSERTE(work_queue.n_Size() == ordered_queue.n_Size());
	// avoid deadlock

	for(size_t i = 0, n = workers.size(); i < n; ++ i) {
		workers[i].Set(work_queue, ordered_queue);
		if(!workers[i].Start()) {
			fprintf(stderr, "error: failed to start a thread\n");
			return -1;
		}
	}
	// start workers that "process" work

	CTimer t;

	CInputStream is;
	COutputStream os;

	int n_work_id = 0, n_consumed_id = 0;
	for(int n_enqueued = 0;; ++ n_work_id) {
		TWorkItem t_wi;
		if(!is.ReadStream(t_wi))
			break;
		if(!work_queue.Put(std::make_pair(n_work_id, t_wi))) { // put the item along with the task id
			fprintf(stderr, "error: queue put failed\n");
			return -1;
		}
		++ n_enqueued;
		// put work to be done (blocks if all the workers are busy and the queue fills up)

		TWorkItem t_processed;
		if(n_enqueued >= n_queue_size && !ordered_queue.Get(t_processed)) { // will block
			fprintf(stderr, "error: queue get failed\n");
			return -1;
		}
		if(n_enqueued >= n_queue_size || ordered_queue.TryGet(t_processed)) {
			//os.WriteStream(t_processed);
			-- n_enqueued;
			++ n_consumed_id;
			// get a processed work item
		}
		// process any finished work (does not block)
	}
	// produce work

	work_queue.Signal_Finished();
	// there's not going to be any more work

	for(; n_consumed_id != n_work_id; ++ n_consumed_id) {
		TWorkItem t_processed;
		if(!ordered_queue.Get(t_processed)) {
			fprintf(stderr, "error: queue get failed\n");
			return -1;
		}
		//os.WriteStream(t_processed);
	}
	printf("\ndone. it took %f sec\n", t.f_Time());
	// process the rest of the queue (need to know how many there are)

	// alternately the workers may keep track of their number (e.g. via an atomic counter,
	// and when the last worker finishes, it calls Signal_Finished() on the result queue)

	// alternately, the consumption of work cound be in yet another thread, and the main
	// thread would 1) produce work, 2) signal the work queue finished, 3) wait for all
	// the workers to finish, 4) signal the return queue finished

	for(size_t i = 0, n = workers.size(); i < n; ++ i) {
		if(!workers[i].WaitForFinish()) {
			fprintf(stderr, "error: failed to join a thread");
			return -1;
		}
	}
	// join the workers (now they finished by themselves so it is fast)
	*/
	// todo - alloc workers and thread contexts, make queue

	size_t n_block_used = 0;
	for(int i = 0, n = r_file_list.size(); i < n; ++ i) {
		const char *p_s_path = r_file_list[i]->p_s_Path();
		_ASSERTE(p_s_path);
		// get file and it's source path

		FILE *p_fr;
#if defined(_MSC_VER) && !defined(__MWERKS__) && _MSC_VER >= 1400
		if(fopen_s(&p_fr, p_s_path, "rb")) {
#else // _MSC_VER && !__MWERKS__ && _MSC_VER >= 1400
		if(!(p_fr = fopen(p_s_path, "rb"))) {
#endif // _MSC_VER && !__MWERKS__ && _MSC_VER >= 1400
#ifdef PAK2_PACKER_USE_STDERR
			fprintf(stderr, "error: error opening file \'%s\'\n", p_s_path);
#endif
			return false;
		}
		// open source file

		for(;;) {
			size_t n_buffer_space = m_n_block_size - n_block_used;
			size_t n_read;
			if(!(n_read = fread(t_buffer.p_Data() + n_block_used, 1, n_buffer_space, p_fr))) {
				if(ferror(p_fr)) {
					fclose(p_fr);
#ifdef PAK2_PACKER_USE_STDERR
					fprintf(stderr, "error: error reading file \'%s\'\n", p_s_path);
#endif
					return false;
				}
				_ASSERTE(feof(p_fr));
				break;
			}
			n_block_used += n_read;
			// read something

			_ASSERTE(n_block_used <= m_n_block_size);
			if(n_block_used == m_n_block_size) {
				n_block_used = 0;

				if(!PackWriteBlock(t_buffer, p_fw)) {
#ifdef PAK2_PACKER_USE_STDERR
					fprintf(stderr, "error: failed to write block\n");
#endif
					fclose(p_fr);
					return false;
				}
				// write block
			}
			// compress now
		}

		fclose(p_fr);
		// close source file
	}
	// read and compress source files

	if(n_block_used) {
		t_buffer.Resize(n_block_used);
		// resize the buffer so it contains meaningful data only

		if(!PackWriteBlock(t_buffer, p_fw)) {
#ifdef PAK2_PACKER_USE_STDERR
			fprintf(stderr, "error: failed to write block\n");
#endif
			return false;
		}
		// write block, maintain average packing ratio
	}
	// compress the final block (leftover)

	// todo - wait for threads

	uint32_t n_terminator = 0;
	if(fwrite(&n_terminator, sizeof(uint32_t), 1, p_fw) != 1) {
#ifdef PAK2_PACKER_USE_STDERR
		fprintf(stderr, "error: error writing block terminator\n");
#endif
		return false;
	}
	// write terminating 0 after the last block

	return true;
}

/*
 *	static bool CPak2PackerUtil::PackWriteBlock(const TBuffer &r_t_block, FILE *p_fw)
 *		- compress data block r_t_block and write it to p_fw
 *		- note the block is preceded by it's size in the file
 *		- in case compressed block is actually larger than original block,
 *		  original block is written instead and it's size is written
 *		  with raised most significant bit
 *		- returns true on success, false on failure
 */
bool CPak2PackerUtil::PackWriteBlock(const TBuffer &r_t_block, FILE *p_fw)
{
	if(m_n_compression_level != level_Store &&
	   !PackBuffer(r_t_block, m_t_comp_state.t_compressed_block)) {
#ifdef PAK2_PACKER_USE_STDERR
		fprintf(stderr, "\nerror: error packing block\n");
#endif
		return false;
	}
	// pack

	TBuffer &t_packed = m_t_comp_state.t_compressed_block;
	// this is packed

	bool b_pack = m_n_compression_level == level_ForceCompress ||
		(m_n_compression_level != level_Store && t_packed.n_Size() < r_t_block.n_Size());
	// choose which one to write (may choose compressed even if it is larger, as a form of data obfuscation)

	const TBuffer &r_t_output = (b_pack)? t_packed : r_t_block;
	// output buffer

	_ASSERTE(r_t_output.n_Size() <= INT_MAX);
	uint32_t n_size = r_t_output.n_Size();
	if(!b_pack)
		n_size |= n_raw_data_flag; // set MSB to flag unpacked block
	// output size

	uint16_t n_method = (m_n_compression_method != method_Adaptive)? m_n_compression_method :
		(t_packed.n_Size() >= sizeof(uint16_t))? *(uint16_t*)t_packed.p_Data() : -1;
	// get method

	if(m_p_verbose_obj &&
	   !m_p_verbose_obj->On_BlockCompress(r_t_block.n_Size(), r_t_output.n_Size(), (b_pack)? n_method : -1)) {
#ifdef PAK2_PACKER_USE_STDERR
		fprintf(stderr, "error: packing interrupted\n");
#endif
		return false;
	}
	// call verbose function

	return fwrite(&n_size, sizeof(uint32_t), 1, p_fw) == 1 &&
		fwrite(r_t_output.p_Data(), r_t_output.n_Size(), 1, p_fw) == 1;
	// write output size and data
}

/*
 *	static int CPak2PackerUtil::n_TOC_Size(const std::vector<TNamedPak2FileInfo> &r_file_info)
 *		- calculates size of table of contents
 *		- returns toc size or -1 in case size was greater than INT_MAX
 */
int CPak2PackerUtil::n_TOC_Size(const std::vector<TNamedPak2FileInfo> &r_file_info)
{
	unsigned int n_toc_size = 0;
	for(int i = 0, n = r_file_info.size(); i < n; ++ i) {
		const TPak2FileInfo &r_t_file = r_file_info[i].first;
		// get file ...

		unsigned int n_file_record_size = sizeof(TPak2FileInfo) +
			r_t_file.n_filename_length * sizeof(char);
		if(n_toc_size > UINT_MAX - n_file_record_size)
			return -1;
		n_toc_size += n_file_record_size;
	}
	// calculate size of file table

	return n_toc_size;
}

/*
 *	static bool CPak2PackerUtil::Assemble_TOC(const std::vector<TNamedPak2FileInfo> &r_file_info,
 *		TBuffer &r_t_toc)
 *		- createss buffer with TOC data
 *		- r_file_info contains list of pak files
 *		- r_t_toc (output) is buffer where TOC is generated
 *		- returns true on success, false on failure
 */
bool CPak2PackerUtil::Assemble_TOC(const std::vector<TNamedPak2FileInfo> &r_file_info,
	TBuffer &r_t_toc)
{
	int n_toc_size;
	if((n_toc_size = n_TOC_Size(r_file_info)) < 0) {
#ifdef PAK2_PACKER_USE_STDERR
		fprintf(stderr, "error: too much files to pack\n");
#endif
		return false;
	}
	if(!r_t_toc.Resize(n_toc_size)) {
#ifdef PAK2_PACKER_USE_STDERR
		fprintf(stderr, "error: not enough memory\n");
#endif
		return false;
	}
	// allocate buffer for TOC

	uint8_t *p_toc_ptr = r_t_toc.p_Data();
	for(int i = 0, n = r_file_info.size(); i < n; ++ i) {
		TPak2FileInfo t_file = r_file_info[i].first;
		const char *p_s_filename = r_file_info[i].second;

		memcpy(p_toc_ptr, &t_file, sizeof(TPak2FileInfo));
		p_toc_ptr += sizeof(TPak2FileInfo);
		memcpy(p_toc_ptr, p_s_filename, t_file.n_filename_length * sizeof(char));
		p_toc_ptr += t_file.n_filename_length;
	}
	_ASSERTE(p_toc_ptr == r_t_toc.p_Data() + r_t_toc.n_Size()); // make sure we're efficient
	// fill the TOC buffer

	return true;
}

/*
 *	static const char *CPak2PackerUtil::p_s_SameDirName(const char *p_s_path,
 *		const char *p_s_prev_path)
 *		- p_s_path is current file path, p_s_prev_path is previous file path
 *		  or 0 in case this is the first file
 *		- if current file lies in the same directory as previous one, returns
 *		  current filename (without any directories preceding it), otherwise
 *		  returns 0
 */
const char *CPak2PackerUtil::p_s_SameDirName(const char *p_s_path, const char *p_s_prev_path)
{
	if(!p_s_prev_path)
		return 0;
	// first name; can't be in the same dir

	const char *p_s_filename = strrchr(p_s_path, CDirectory::path_Separator);
	const char *p_s_last_filename = strrchr(p_s_prev_path, CDirectory::path_Separator);
	if(!p_s_filename || !p_s_last_filename ||
	   p_s_filename - p_s_path != p_s_last_filename - p_s_prev_path ||
	   strncmp(p_s_path, p_s_prev_path, p_s_filename - p_s_path))
		return 0;
	// files aren't in the same dir

	// todo - find a common prefix instead

	return p_s_filename + 1;
	// files are in the same dir, return filename of the last file only
}

/*
 *	static TNamedPak2FileInfo CPak2PackerUtil::t_FileInfo(const char *p_s_path,
 *		const char *p_s_prev_path, const CBlockCounter &r_block_counter,
 *		const TFileInfo &r_t_file_info)
 *		- fills TNamedPak2FileInfo structure with file information
 *		- p_s_path is current file path, p_s_prev_path is previous file path
 *		  or 0 in case this is the first file
 *		- r_block_counter is block counter (contains address of unallocated space)
 *		- r_t_file_info is file information (contains various informations,
 *		  what is needed is 64bit hi-lo file size)
 *		- returns TNamedPak2FileInfo filled with current file info
 */
CPak2PackerUtil::TNamedPak2FileInfo CPak2PackerUtil::t_FileInfo(const char *p_s_path,
	const char *p_s_prev_path, const CBlockCounter &r_block_counter, const TFileInfo &r_t_file_info)
{
	const char *p_s_filename;
	bool b_same_dir = true;
	if(!(p_s_filename = p_s_SameDirName(p_s_path, p_s_prev_path))) {
		b_same_dir = false;
		p_s_filename = p_s_path;
		// use full name
	}
	// decide wheter use full path or just filename

	_ASSERTE(strlen(p_s_filename) <= 65535);
	// make sure filenames aren't too long

	TPak2FileInfo t_file = {
		b_same_dir,
		r_t_file_info.n_size_lo, r_t_file_info.n_size_hi,
		r_block_counter.n_Block_Index(), r_block_counter.n_Block_Offset(),
		uint16_t(strlen(p_s_filename))
	};
	// fill the structure

	return TNamedPak2FileInfo(t_file, p_s_filename);
}

/*
 *	bool CPak2PackerUtil::CreateFileHeaders(
 *		const std::vector<TFileInfo*> &r_file_list,
 *		const char *p_s_base_dir, std::vector<TNamedPak2FileInfo> &r_file_info,
 *		unsigned int &r_n_block_num)
 *		- creates file headers and determines number of blocks
 *		- r_file_list is list of files to be packed, n_block_size is block size
 *		- r_file_info (output) is list of generated file headers
 *		- r_n_block_num (output) is number of blocks, required for files
 *		- returns true on success, false on failure
 */
bool CPak2PackerUtil::CreateFileHeaders(const std::vector<TFileInfo*> &r_file_list,
	const char *p_s_base_dir, std::vector<TNamedPak2FileInfo> &r_file_info,
	unsigned int &r_n_block_num)
{
	std::vector<TNamedPak2FileInfo> file_info(r_file_list.size());
	if(file_info.size() != r_file_list.size()) {
#ifdef PAK2_PACKER_USE_STDERR
		fprintf(stderr, "error: not enough memory\n");
#endif
		return false;
	}
	// alloc file list

	CBlockCounter block_counter(m_n_block_size);
	const char *p_s_prev_path = 0;
	for(int i = 0, n = r_file_list.size(); i < n; ++ i) {
		const TFileInfo *p_file = r_file_list[i];
		const char *p_s_path = p_file->p_s_Path();
		_ASSERTE(p_s_path);
		// get filename

		if(p_s_base_dir) {
			if(strstr(p_s_path, p_s_base_dir))
				p_s_path = strstr(p_s_path, p_s_base_dir) + strlen(p_s_base_dir);
			else {
#ifdef PAK2_PACKER_USE_STDERR
				fprintf(stderr, "warning: filename doesn't contain base directory\n");
#endif
			}
			if(*p_s_path == CDirectory::path_Separator)
				++ p_s_path;
			_ASSERTE(strlen(p_s_path));
		}
		// get filename inside secified dir (ie. without it's name)

		file_info[i] = t_FileInfo(p_s_path, p_s_prev_path,
			block_counter, *p_file);
		p_s_prev_path = p_s_path;
		// create file info structure

		uint64_t n_size = (uint64_t(p_file->n_size_hi) << 32) |
			p_file->n_size_lo;
		if(!(block_counter += n_size)) {
#ifdef PAK2_PACKER_USE_STDERR
			fprintf(stderr, "error: too much files to pack\n");
#endif
			return false;
		}
		// increment block counter
	}
	// fill file-info list

	r_file_info.swap(file_info);
	// swap lists

	r_n_block_num = block_counter.n_Block_Num();
	// output block num

	return true;
}

/*
 *								=== ~CPak2PackerUtil ===
 */

/*
 *								=== CLamePak2 ===
 */

const short CLamePak2::n_pak_version = 205;
const uint32_t CLamePak2::n_raw_data_flag = 1 << (8 * sizeof(uint32_t) - 1);

/*
 *	CLamePak2::CLamePak2(const char *p_s_filename)
 *		- opens lame pak p_s_filename
 *		- check b_Status() to see if it was successful
 */
CLamePak2::CLamePak2(const char *p_s_filename)
	:m_n_cur_block(UINT_MAX)
{
#if defined(_MSC_VER) && !defined(__MWERKS__) && _MSC_VER >= 1400
	if(fopen_s(&m_p_fr, p_s_filename, "rb"))
#else // _MSC_VER && !__MWERKS__ && _MSC_VER >= 1400
	if(!(m_p_fr = fopen(p_s_filename, "rb")))
#endif // _MSC_VER && !__MWERKS__ && _MSC_VER >= 1400
		return;
	if(!Read_TOC()) {
		fclose(m_p_fr);
		m_p_fr = 0;
	}
	// open file and read table of contents
}

/*
 *	CLamePak2::~CLamePak2()
 *		- destructor
 */
CLamePak2::~CLamePak2()
{
	if(m_p_fr)
		fclose(m_p_fr);
	std::for_each(m_toc.begin(), m_toc.end(), DeleteName);
}

/*
 *	bool CLamePak2::b_Status() const
 *		- returns true if pak file was opened successfully, otherwise returns false
 */
bool CLamePak2::b_Status() const
{
	return m_p_fr != 0;
}

/*
 *	int CLamePak2::n_Pak_Version() const
 *		- returns pak file version or 0 in case pak failed to open
 */
int CLamePak2::n_Pak_Version() const
{
	return (b_Status())? m_t_header.n_version : 0;
}

/*
 *	char CLamePak2::n_Path_Separator() const
 *		- returns used path separator character (ie. backslash)
 *		  or 0 in case pak failed to open
 */
char CLamePak2::n_Path_Separator() const
{
	return (b_Status())? m_t_header.n_path_separator : 0;
}

/*
 *	int CLamePak2::n_File_Num() const
 *		- returns number of files or 0 in case pak file was not opened successfully
 */
int CLamePak2::n_File_Num() const
{
	return m_toc.size();
}

/*
 *	const char *CLamePak2::p_s_FileName(int n_index) const
 *		- returns filename of file with zero-based index n_index
 */
const char *CLamePak2::p_s_FileName(int n_index) const
{
	if(n_index < 0 || unsigned(n_index) >= m_toc.size())
		return 0;
	return m_toc[n_index].second;
}

/*
 *	uint64_t CLamePak2::n_FileSize(int n_index) const
 *		- returns size of file with zero-based index n_index
 */
uint64_t CLamePak2::n_FileSize(int n_index) const
{
	if(n_index < 0 || unsigned(n_index) >= m_toc.size())
		return 0;
	const TPak2FileInfo &r_t_file = m_toc[n_index].first;
	return r_t_file.n_size_lo | (uint64_t(r_t_file.n_size_hi) << 32);
}

/*
 *	bool CLamePak2::UnpackFile(int n_index, TBuffer &r_t_file_data)
 *		- unpacks file with zero-based index n_index, outputs to r_t_file_data
 *		  (doesn't have to be allocated)
 *		- unpacks only files up to 4GB. other files need to be unpacked to stream
 *		- returns true on success, false on failure
 */
bool CLamePak2::UnpackFile(int n_index, TBuffer &r_t_file_data)
{
	if(n_index < 0 || unsigned(n_index) >= m_toc.size())
		return false;
	TPak2FileInfo t_file = m_toc[n_index].first;
	// get file info

	if(t_file.n_size_hi)
		return false;
	// don't unpack large files to memory

	if(!t_file.n_size_lo) {
		r_t_file_data.Clear();
		return true;
	}
	// handle empty files

	bool b_have_block = false;
	if(m_n_cur_block != t_file.n_block || m_t_cur_block.b_Empty()) {
		if(!Seek_Block(t_file.n_block))
			return false;
	} else
		b_have_block = true;
	// seek first file block

	if(!r_t_file_data.Resize(t_file.n_size_lo))
		return false;
	// alloc buffer for file data (up to 4GB)

	uint8_t *p_out_ptr = r_t_file_data.p_Data();
	const unsigned int n_block_size = m_t_header.n_block_size;
	for(unsigned int n_block = t_file.n_block, n_off = t_file.n_block_offset,
	   n_file_size = t_file.n_size_lo; n_file_size; n_off = 0, ++ n_block) {
		if(!Fetch_Block(n_block))
			return false;
		// fetch block

		unsigned int n_block_data = min(n_block_size - n_off, n_file_size);
		// how much data do we want do copy

		memcpy(p_out_ptr, m_t_cur_block.p_Data() + n_off, n_block_data * sizeof(unsigned char));
		// copy (part of) decompressed data to file

		n_file_size -= n_block_data;
		p_out_ptr += n_block_data;
		// offset pointer
	}
	_ASSERTE(p_out_ptr == r_t_file_data.p_Data() + r_t_file_data.n_Size());
	// unpacking loop

	return true;
}

bool CLamePak2::Fetch_Block(unsigned int n_block)
{
	if(n_block == m_n_cur_block && !m_t_cur_block.b_Empty())
		return true;
	// have this block read and unpacked already

	if(!Seek_Block(n_block)) {
		_ASSERTE(m_n_cur_block == UINT_MAX);
		return false;
	}
	// seek block

	unsigned int n_block_size;
	if(fread(&n_block_size, sizeof(unsigned int), 1, m_p_fr) != 1) {
		m_n_cur_block = UINT_MAX;
		return false;
	}
	bool b_compressed = !(n_block_size & n_raw_data_flag);
	// read block size and decide wheter it's compressed

	n_block_size &= ~n_raw_data_flag;
	if(m_t_header.n_method == method_Adaptive)
		n_block_size += sizeof(int16_t);
	// skip method description

	if(!m_t_cur_block.Resize(n_block_size)) {
		m_n_cur_block = UINT_MAX;
		return false;
	}
	// alloc read buffer (todo - make block realloc
	// function to minimize allocation count)

	int16_t n_block_method = m_t_header.n_method;
	if((m_t_header.n_method == method_Adaptive && b_compressed &&
	   fread(&n_block_method, sizeof(int16_t), 1, m_p_fr) != 1) ||
	   fread(m_t_cur_block.p_Data(), n_block_size, 1, m_p_fr) != 1) {
		m_n_cur_block = UINT_MAX;
		return false;
	}
	// read block method / data

	if(b_compressed && !UnpackBuffer(m_t_cur_block, m_t_cur_block, n_block_method)) {
		m_n_cur_block = UINT_MAX;
		return false;
	}
	// decompress to cache

	m_n_cur_block = n_block;
	// we have this block

	return true;
}

bool CLamePak2::Seek_Block(unsigned int n_block)
{
	_ASSERTE(m_p_fr);
	_ASSERTE(n_block < m_t_header.n_block_num);

	if(n_block == m_n_cur_block + 1 && !m_t_cur_block.b_Empty())
		return true;
	// have this block focused already

	if(fseek(m_p_fr, sizeof(TPak2Header) + m_t_header.n_toc_size, SEEK_SET)) {
		m_n_cur_block = UINT_MAX;
		return false;
	}
	// seek to block 0

	for(; n_block; -- n_block) {
		unsigned int n_block_size;
		if(fread(&n_block_size, sizeof(unsigned int), 1, m_p_fr) != 1) {
			m_n_cur_block = UINT_MAX;
			return false;
		}
		n_block_size &= ~n_raw_data_flag; // kept for backward compatibility
		if(fseek(m_p_fr, n_block_size, SEEK_CUR)) {
			m_n_cur_block = UINT_MAX;
			return false;
		}
		// seek to next block
	}
	// jump block by block

	return true;
}

/*
 *	bool CLamePak2::Read_TOC()
 *		- invoked by constructor only
 *		- reads table of contents and unpacks filenames
 *		- returns true on success, false on failure
 */
bool CLamePak2::Read_TOC()
{
	_ASSERTE(m_p_fr && m_toc.empty());

	if(fread(&m_t_header, sizeof(TPak2Header), 1, m_p_fr) != 1)
		return false;
	if((m_t_header.n_version & 0xff00) != (n_pak_version & 0xff00) || // compare only major
	   m_t_header.n_block_size < 1024 || m_t_header.n_block_size > 100 * 1048576 ||
	   m_t_header.n_block_num == UINT_MAX || !m_t_header.n_file_num || !m_t_header.n_toc_size)
		return false;
	// read header, check it's version and other values sanity
	// (UINT_MAX limit is because of caching)

	if(m_t_header.n_method != method_BWT_A &&
	   m_t_header.n_method != method_BWT_B &&
	   m_t_header.n_method != method_BWT_C &&
	   m_t_header.n_method != method_Adaptive)
		return false;
	// unknown method

	bool b_packed_toc = !(m_t_header.n_toc_size & n_raw_data_flag);
	TBuffer t_toc(m_t_header.n_toc_size &= ~n_raw_data_flag);
	if(t_toc.b_Empty())
		return false;
	int16_t n_toc_method = m_t_header.n_method;
	if((m_t_header.n_method == method_Adaptive && b_packed_toc &&
	   fread(&n_toc_method, sizeof(int16_t), 1, m_p_fr) != 1) ||
	   fread(t_toc.p_Data(), t_toc.n_Size(), 1, m_p_fr) != 1)
		return false;
	// read TOC

	if(b_packed_toc && !UnpackBuffer(t_toc, t_toc, n_toc_method))
		return false;
	// unpack TOC if necessary

	_ASSERTE(m_toc.empty());
	if(!stl_ut::Reserve_N(m_toc, m_t_header.n_file_num))
		return false;
	// alloc memory for list of files

	TBuffer t_path;
	unsigned int n_path_length = 0;
	// temporary buffer for filenames

	const char n_path_separator = m_t_header.n_path_separator;
	// use path separator, written in header

	uint8_t *p_toc_ptr = t_toc.p_Data();
	const uint8_t *p_toc_end = t_toc.p_Data() + t_toc.n_Size();
	for(unsigned int i = 0; i < m_t_header.n_file_num; ++ i) {
		TPak2FileInfo t_file_info;
		if(p_toc_ptr + sizeof(TPak2FileInfo) > p_toc_end)
			return false;
		memcpy(&t_file_info, p_toc_ptr, sizeof(TPak2FileInfo));
		p_toc_ptr += sizeof(TPak2FileInfo);
		// get file info

		if((t_file_info.b_same_dir && !i) || !t_file_info.n_filename_length ||
		   t_file_info.n_block > m_t_header.n_block_num ||
		   (t_file_info.n_block == m_t_header.n_block_num && // litit block num for not-empty files only
		   (t_file_info.n_size_hi || t_file_info.n_size_lo)) ||
		   t_file_info.n_block_offset >= m_t_header.n_block_size ||
		   p_toc_ptr + t_file_info.n_filename_length > p_toc_end)
			return false;
		// check data sanity

		if(t_file_info.b_same_dir) {
			if(!t_path.p_Data())
				return false;
			bool b_found = false;
			for(uint8_t *p_ptr = t_path.p_Data() + n_path_length - 1; p_ptr > t_path.p_Data(); -- p_ptr) {
				if(*p_ptr == n_path_separator) {
					b_found = true;
					n_path_length = p_ptr - t_path.p_Data() + 1;
					// erase everything from backslash on
					break;
				}
			}
			if(!b_found)
				n_path_length = 0;
		} else
			n_path_length = 0;
		// modify path so it contains beginning of file path

		if(!t_path.Resize(n_path_length + t_file_info.n_filename_length))
			return false;
		// alloc enough space for the whole filename

		memcpy(t_path.p_Data() + n_path_length, p_toc_ptr, t_file_info.n_filename_length);
		p_toc_ptr += t_file_info.n_filename_length;
		// note we already checked for buffer overrun  before
		// create string with full name (no terminating zero)

		n_path_length += t_file_info.n_filename_length;
		char *p_s_path;
		if(!(p_s_path = new(std::nothrow) char[n_path_length + 1]))
			return false;
		memcpy(p_s_path, t_path.p_Data(), n_path_length * sizeof(unsigned char));
		p_s_path[n_path_length] = 0;
		// alloc new string

		m_toc.push_back(TNamedPak2FileInfo(t_file_info, p_s_path));
		// put it to the list
	}
	// read files from TOC

	return p_toc_ptr == p_toc_end;
	// must be equal
}

/*
 *	static bool CLamePak2::UnpackBuffer(const TBuffer &r_t_in_buffer,
 *		TBuffer &r_t_out_buffer)
 *		- unpacks r_t_in_buffer, outputs to r_t_out_buffer
 *		  which doesn't have to be allocated
 *		- returns true on success, false on failure
 */
bool CLamePak2::UnpackBuffer(const TBuffer &r_t_in_buffer, TBuffer &r_t_out_buffer, int n_method)
{
#if 0
	if(!CHuffmanCodec::Decode(r_t_in_buffer, m_t_tmp))
		return false;
	// ihuff

	if(n_method == method_BWT_A || n_method == method_BWT_B) {
		if(!CRunLengthCodec::Decode(m_t_tmp, m_t_tmp2))
			return false;
		// irle

		if(n_method == method_BWT_A)
			CMoveToFrontTransform::Decode(m_t_tmp2, CMoveToFrontTransform::algo_MTF);
		else /*if(m_t_header.n_method == method_BWT_B)*/ {
			_ASSERTE(m_t_header.n_method == method_BWT_B);
			CMoveToFrontTransform::Decode(m_t_tmp2, CMoveToFrontTransform::algo_MTF_1);
		}
		// imtf
	} else if(n_method == method_BWT_C) {
		if(!CInversionFrequenciesCodec::Decode(m_t_tmp, m_t_tmp3))
			return false;
		// isif

		if(!CRunLengthCodec::Decode(m_t_tmp3, m_t_tmp2))
			return false;
		// irle
	}

	if(!CBurrowsWheelerTransform::Decode(m_t_tmp2, r_t_out_buffer))
		return false;
	// ibwt
#endif // 0

	if(!CPak2PackerUtil::CCodecBank(m_temp_buffers, n_method).Decompress(r_t_in_buffer, r_t_out_buffer))
		return false;
	// use the shared codec bank to decompress using the correct codec, also checks configuration

	return true;
}

/*
 *	static inline void CLamePak2::DeleteName(TNamedPak2FileInfo &r_t_file_info)
 *		- destructor helper function
 */
inline void CLamePak2::DeleteName(TNamedPak2FileInfo &r_t_file_info)
{
	delete[] r_t_file_info.second;
}

/*
 *								=== ~CLamePak2 ===
 */
