~zooko/cryptopp/trunk

// zdeflate.cpp - written and placed in the public domain by Wei Dai

// Many of the algorithms and tables used here came from the deflate implementation

// by Jean-loup Gailly, which was included in Crypto++ 4.0 and earlier. I completely

// rewrote it in order to fix a bug that I could not figure out. This code

// is less clever, but hopefully more understandable and maintainable.

#include "pch.h"

#include "zdeflate.h"

#include <functional>

#if _MSC_VER >= 1600

// for make_unchecked_array_iterator

#include <iterator>

#endif

NAMESPACE_BEGIN(CryptoPP)

using namespace std;

LowFirstBitWriter::LowFirstBitWriter(BufferedTransformation *attachment)

	: Filter(attachment), m_counting(false), m_buffer(0), m_bitsBuffered(0), m_bytesBuffered(0)

{

}

void LowFirstBitWriter::StartCounting()

{

	assert(!m_counting);

	m_counting = true;

	m_bitCount = 0;

}

unsigned long LowFirstBitWriter::FinishCounting()

{

	assert(m_counting);

	m_counting = false;

	return m_bitCount;

}

void LowFirstBitWriter::PutBits(unsigned long value, unsigned int length)

{

	if (m_counting)

		m_bitCount += length;

	else

	{

		m_buffer |= value << m_bitsBuffered;

		m_bitsBuffered += length;

		assert(m_bitsBuffered <= sizeof(unsigned long)*8);

		while (m_bitsBuffered >= 8)

		{

			m_outputBuffer[m_bytesBuffered++] = (byte)m_buffer;

			if (m_bytesBuffered == m_outputBuffer.size())

			{

				AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered);

				m_bytesBuffered = 0;

			}

			m_buffer >>= 8;

			m_bitsBuffered -= 8;

		}

	}

}

void LowFirstBitWriter::FlushBitBuffer()

{

	if (m_counting)

		m_bitCount += 8*(m_bitsBuffered > 0);

	else

	{

		if (m_bytesBuffered > 0)

		{

			AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered);

			m_bytesBuffered = 0;

		}

		if (m_bitsBuffered > 0)

		{

			AttachedTransformation()->Put((byte)m_buffer);

			m_buffer = 0;

			m_bitsBuffered = 0;

		}

	}

}

void LowFirstBitWriter::ClearBitBuffer()

{

	m_buffer = 0;

	m_bytesBuffered = 0;

	m_bitsBuffered = 0;

}

HuffmanEncoder::HuffmanEncoder(const unsigned int *codeBits, unsigned int nCodes)

{

	Initialize(codeBits, nCodes);

}

struct HuffmanNode

{

	size_t symbol;

	union {size_t parent; unsigned depth, freq;};

};

struct FreqLessThan

{

	inline bool operator()(unsigned int lhs, const HuffmanNode &rhs) {return lhs < rhs.freq;}

	inline bool operator()(const HuffmanNode &lhs, const HuffmanNode &rhs) const {return lhs.freq < rhs.freq;}

	// needed for MSVC .NET 2005

	inline bool operator()(const HuffmanNode &lhs, unsigned int rhs) {return lhs.freq < rhs;}

};

void HuffmanEncoder::GenerateCodeLengths(unsigned int *codeBits, unsigned int maxCodeBits, const unsigned int *codeCounts, size_t nCodes)

{

	assert(nCodes > 0);

	assert(nCodes <= ((size_t)1 << maxCodeBits));

	size_t i;

	SecBlockWithHint<HuffmanNode, 2*286> tree(nCodes);

	for (i=0; i<nCodes; i++)

	{

		tree[i].symbol = i;

		tree[i].freq = codeCounts[i];

	}

	sort(tree.begin(), tree.end(), FreqLessThan());

	size_t treeBegin = upper_bound(tree.begin(), tree.end(), 0, FreqLessThan()) - tree.begin();

	if (treeBegin == nCodes)

	{	// special case for no codes

		fill(codeBits, codeBits+nCodes, 0);

		return;

	}

	tree.resize(nCodes + nCodes - treeBegin - 1);

	size_t leastLeaf = treeBegin, leastInterior = nCodes;

	for (i=nCodes; i<tree.size(); i++)

	{

		size_t least;

		least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++;

		tree[i].freq = tree[least].freq;

		tree[least].parent = i;

		least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++;

		tree[i].freq += tree[least].freq;

		tree[least].parent = i;

	}

	tree[tree.size()-1].depth = 0;

	if (tree.size() >= 2)

		for (i=tree.size()-2; i>=nCodes; i--)

			tree[i].depth = tree[tree[i].parent].depth + 1;

	unsigned int sum = 0;

	SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1);

	fill(blCount.begin(), blCount.end(), 0);

	for (i=treeBegin; i<nCodes; i++)

	{

		size_t depth = STDMIN(maxCodeBits, tree[tree[i].parent].depth + 1);

		blCount[depth]++;

		sum += 1 << (maxCodeBits - depth);

	}

	unsigned int overflow = sum > (unsigned int)(1 << maxCodeBits) ? sum - (1 << maxCodeBits) : 0;

	while (overflow--)

	{

		unsigned int bits = maxCodeBits-1;

		while (blCount[bits] == 0)

			bits--;

		blCount[bits]--;

		blCount[bits+1] += 2;

		assert(blCount[maxCodeBits] > 0);

		blCount[maxCodeBits]--;

	}

	for (i=0; i<treeBegin; i++)

		codeBits[tree[i].symbol] = 0;

	unsigned int bits = maxCodeBits;

	for (i=treeBegin; i<nCodes; i++)

	{

		while (blCount[bits] == 0)

			bits--;

		codeBits[tree[i].symbol] = bits;

		blCount[bits]--;

	}

	assert(blCount[bits] == 0);

}

void HuffmanEncoder::Initialize(const unsigned int *codeBits, unsigned int nCodes)

{

	assert(nCodes > 0);

	unsigned int maxCodeBits = *max_element(codeBits, codeBits+nCodes);

	if (maxCodeBits == 0)

		return;		// assume this object won't be used

	SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1);

	fill(blCount.begin(), blCount.end(), 0);

	unsigned int i;

	for (i=0; i<nCodes; i++)

		blCount[codeBits[i]]++;

	code_t code = 0;

	SecBlockWithHint<code_t, 15+1> nextCode(maxCodeBits+1);

	nextCode[1] = 0;

	for (i=2; i<=maxCodeBits; i++)

	{

		code = (code + blCount[i-1]) << 1;

		nextCode[i] = code;

	}

	assert(maxCodeBits == 1 || code == (1 << maxCodeBits) - blCount[maxCodeBits]);

	m_valueToCode.resize(nCodes);

	for (i=0; i<nCodes; i++)

	{

		unsigned int len = m_valueToCode[i].len = codeBits[i];

		if (len != 0)

			m_valueToCode[i].code = BitReverse(nextCode[len]++) >> (8*sizeof(code_t)-len);

	}

}

inline void HuffmanEncoder::Encode(LowFirstBitWriter &writer, value_t value) const

{

	assert(m_valueToCode[value].len > 0);

	writer.PutBits(m_valueToCode[value].code, m_valueToCode[value].len);

}

Deflator::Deflator(BufferedTransformation *attachment, int deflateLevel, int log2WindowSize, bool detectUncompressible)

	: LowFirstBitWriter(attachment)

	, m_deflateLevel(-1)

{

	InitializeStaticEncoders();

	IsolatedInitialize(MakeParameters("DeflateLevel", deflateLevel)("Log2WindowSize", log2WindowSize)("DetectUncompressible", detectUncompressible));

}

Deflator::Deflator(const NameValuePairs &parameters, BufferedTransformation *attachment)

	: LowFirstBitWriter(attachment)

	, m_deflateLevel(-1)

{

	InitializeStaticEncoders();

	IsolatedInitialize(parameters);

}

void Deflator::InitializeStaticEncoders()

{

	unsigned int codeLengths[288];

	fill(codeLengths + 0, codeLengths + 144, 8);

	fill(codeLengths + 144, codeLengths + 256, 9);

	fill(codeLengths + 256, codeLengths + 280, 7);

	fill(codeLengths + 280, codeLengths + 288, 8);

	m_staticLiteralEncoder.Initialize(codeLengths, 288);

	fill(codeLengths + 0, codeLengths + 32, 5);

	m_staticDistanceEncoder.Initialize(codeLengths, 32);

}

void Deflator::IsolatedInitialize(const NameValuePairs &parameters)

{

	int log2WindowSize = parameters.GetIntValueWithDefault("Log2WindowSize", DEFAULT_LOG2_WINDOW_SIZE);

	if (!(MIN_LOG2_WINDOW_SIZE <= log2WindowSize && log2WindowSize <= MAX_LOG2_WINDOW_SIZE))

		throw InvalidArgument("Deflator: " + IntToString(log2WindowSize) + " is an invalid window size");

	m_log2WindowSize = log2WindowSize;

	DSIZE = 1 << m_log2WindowSize;

	DMASK = DSIZE - 1;

	HSIZE = 1 << m_log2WindowSize;

	HMASK = HSIZE - 1;

	m_byteBuffer.New(2*DSIZE);

	m_head.New(HSIZE);

	m_prev.New(DSIZE);

	m_matchBuffer.New(DSIZE/2);

	Reset(true);

	SetDeflateLevel(parameters.GetIntValueWithDefault("DeflateLevel", DEFAULT_DEFLATE_LEVEL));

	bool detectUncompressible = parameters.GetValueWithDefault("DetectUncompressible", true);

	m_compressibleDeflateLevel = detectUncompressible ? m_deflateLevel : 0;

}

void Deflator::Reset(bool forceReset)

{

	if (forceReset)

		ClearBitBuffer();

	else

		assert(m_bitsBuffered == 0);

	m_headerWritten = false;

	m_matchAvailable = false;

	m_dictionaryEnd = 0;

	m_stringStart = 0;

	m_lookahead = 0;

	m_minLookahead = MAX_MATCH;

	m_matchBufferEnd = 0;

	m_blockStart = 0;

	m_blockLength = 0;

	m_detectCount = 1;

	m_detectSkip = 0;

	// m_prev will be initialized automaticly in InsertString

	fill(m_head.begin(), m_head.end(), 0);

	fill(m_literalCounts.begin(), m_literalCounts.end(), 0);

	fill(m_distanceCounts.begin(), m_distanceCounts.end(), 0);

}

void Deflator::SetDeflateLevel(int deflateLevel)

{

	if (!(MIN_DEFLATE_LEVEL <= deflateLevel && deflateLevel <= MAX_DEFLATE_LEVEL))

		throw InvalidArgument("Deflator: " + IntToString(deflateLevel) + " is an invalid deflate level");

	if (deflateLevel == m_deflateLevel)

		return;

	EndBlock(false);

	static const unsigned int configurationTable[10][4] = {

		/*      good lazy nice chain */

		/* 0 */ {0,    0,  0,    0},  /* store only */

		/* 1 */ {4,    3,  8,    4},  /* maximum speed, no lazy matches */

		/* 2 */ {4,    3, 16,    8},

		/* 3 */ {4,    3, 32,   32},

		/* 4 */ {4,    4, 16,   16},  /* lazy matches */

		/* 5 */ {8,   16, 32,   32},

		/* 6 */ {8,   16, 128, 128},

		/* 7 */ {8,   32, 128, 256},

		/* 8 */ {32, 128, 258, 1024},

		/* 9 */ {32, 258, 258, 4096}}; /* maximum compression */

	GOOD_MATCH = configurationTable[deflateLevel][0];

	MAX_LAZYLENGTH = configurationTable[deflateLevel][1];

	MAX_CHAIN_LENGTH = configurationTable[deflateLevel][3];

	m_deflateLevel = deflateLevel;

}

unsigned int Deflator::FillWindow(const byte *str, size_t length)

{

	unsigned int maxBlockSize = (unsigned int)STDMIN(2UL*DSIZE, 0xffffUL);

	if (m_stringStart >= maxBlockSize - MAX_MATCH)

	{

		if (m_blockStart < DSIZE)

			EndBlock(false);

		memcpy(m_byteBuffer, m_byteBuffer + DSIZE, DSIZE);

		m_dictionaryEnd = m_dictionaryEnd < DSIZE ? 0 : m_dictionaryEnd-DSIZE;

		assert(m_stringStart >= DSIZE);

		m_stringStart -= DSIZE;

		assert(!m_matchAvailable || m_previousMatch >= DSIZE);

		m_previousMatch -= DSIZE;

		assert(m_blockStart >= DSIZE);

		m_blockStart -= DSIZE;

		unsigned int i;

		for (i=0; i<HSIZE; i++)

			m_head[i] = SaturatingSubtract(m_head[i], DSIZE);

		for (i=0; i<DSIZE; i++)

			m_prev[i] = SaturatingSubtract(m_prev[i], DSIZE);

	}

	assert(maxBlockSize > m_stringStart+m_lookahead);

	unsigned int accepted = UnsignedMin(maxBlockSize-(m_stringStart+m_lookahead), length);

	assert(accepted > 0);

	memcpy(m_byteBuffer + m_stringStart + m_lookahead, str, accepted);

	m_lookahead += accepted;

	return accepted;

}

inline unsigned int Deflator::ComputeHash(const byte *str) const

{

	assert(str+3 <= m_byteBuffer + m_stringStart + m_lookahead);

	return ((str[0] << 10) ^ (str[1] << 5) ^ str[2]) & HMASK;

}

unsigned int Deflator::LongestMatch(unsigned int &bestMatch) const

{

	assert(m_previousLength < MAX_MATCH);

	bestMatch = 0;

	unsigned int bestLength = STDMAX(m_previousLength, (unsigned int)MIN_MATCH-1);

	if (m_lookahead <= bestLength)

		return 0;

	const byte *scan = m_byteBuffer + m_stringStart, *scanEnd = scan + STDMIN((unsigned int)MAX_MATCH, m_lookahead);

	unsigned int limit = m_stringStart > (DSIZE-MAX_MATCH) ? m_stringStart - (DSIZE-MAX_MATCH) : 0;

	unsigned int current = m_head[ComputeHash(scan)];

	unsigned int chainLength = MAX_CHAIN_LENGTH;

	if (m_previousLength >= GOOD_MATCH)

		chainLength >>= 2;

	while (current > limit && --chainLength > 0)

	{

		const byte *match = m_byteBuffer + current;

		assert(scan + bestLength < m_byteBuffer + m_stringStart + m_lookahead);

		if (scan[bestLength-1] == match[bestLength-1] && scan[bestLength] == match[bestLength] && scan[0] == match[0] && scan[1] == match[1])

		{

			assert(scan[2] == match[2]);

			unsigned int len = (unsigned int)(

#if defined(_STDEXT_BEGIN) && !(defined(_MSC_VER) && (_MSC_VER < 1400 || _MSC_VER >= 1600)) && !defined(_STLPORT_VERSION)

				stdext::unchecked_mismatch

#else

				std::mismatch

#endif

#if _MSC_VER >= 1600

				(stdext::make_unchecked_array_iterator(scan)+3, stdext::make_unchecked_array_iterator(scanEnd), stdext::make_unchecked_array_iterator(match)+3).first - stdext::make_unchecked_array_iterator(scan));

#else

				(scan+3, scanEnd, match+3).first - scan);

#endif

			assert(len != bestLength);

			if (len > bestLength)

			{

				bestLength = len;

				bestMatch = current;

				if (len == (scanEnd - scan))

					break;

			}

		}

		current = m_prev[current & DMASK];

	}

	return (bestMatch > 0) ? bestLength : 0;

}

inline void Deflator::InsertString(unsigned int start)

{

	unsigned int hash = ComputeHash(m_byteBuffer + start);

	m_prev[start & DMASK] = m_head[hash];

	m_head[hash] = start;

}

void Deflator::ProcessBuffer()

{

	if (!m_headerWritten)

	{

		WritePrestreamHeader();

		m_headerWritten = true;

	}

	if (m_deflateLevel == 0)

	{

		m_stringStart += m_lookahead;

		m_lookahead = 0;

		m_blockLength = m_stringStart - m_blockStart;

		m_matchAvailable = false;

		return;

	}

	while (m_lookahead > m_minLookahead)

	{

		while (m_dictionaryEnd < m_stringStart && m_dictionaryEnd+3 <= m_stringStart+m_lookahead)

			InsertString(m_dictionaryEnd++);

		if (m_matchAvailable)

		{

			unsigned int matchPosition, matchLength;

			bool usePreviousMatch;

			if (m_previousLength >= MAX_LAZYLENGTH)

				usePreviousMatch = true;

			else

			{

				matchLength = LongestMatch(matchPosition);

				usePreviousMatch = (matchLength == 0);

			}

			if (usePreviousMatch)

			{

				MatchFound(m_stringStart-1-m_previousMatch, m_previousLength);

				m_stringStart += m_previousLength-1;

				m_lookahead -= m_previousLength-1;

				m_matchAvailable = false;

			}

			else

			{

				m_previousLength = matchLength;

				m_previousMatch = matchPosition;

				LiteralByte(m_byteBuffer[m_stringStart-1]);

				m_stringStart++;

				m_lookahead--;

			}

		}

		else

		{

			m_previousLength = 0;

			m_previousLength = LongestMatch(m_previousMatch);

			if (m_previousLength)

				m_matchAvailable = true;

			else

				LiteralByte(m_byteBuffer[m_stringStart]);

			m_stringStart++;

			m_lookahead--;

		}

		assert(m_stringStart - (m_blockStart+m_blockLength) == (unsigned int)m_matchAvailable);

	}

	if (m_minLookahead == 0 && m_matchAvailable)

	{

		LiteralByte(m_byteBuffer[m_stringStart-1]);

		m_matchAvailable = false;

	}

}

size_t Deflator::Put2(const byte *str, size_t length, int messageEnd, bool blocking)

{

	if (!blocking)

		throw BlockingInputOnly("Deflator");

	size_t accepted = 0;

	while (accepted < length)

	{

		unsigned int newAccepted = FillWindow(str+accepted, length-accepted);

		ProcessBuffer();

		// call ProcessUncompressedData() after WritePrestreamHeader()

		ProcessUncompressedData(str+accepted, newAccepted);

		accepted += newAccepted;

	}

	assert(accepted == length);

	if (messageEnd)

	{

		m_minLookahead = 0;

		ProcessBuffer();

		EndBlock(true);

		FlushBitBuffer();

		WritePoststreamTail();

		Reset();

	}

	Output(0, NULL, 0, messageEnd, blocking);

	return 0;

}

bool Deflator::IsolatedFlush(bool hardFlush, bool blocking)

{

	if (!blocking)

		throw BlockingInputOnly("Deflator");

	m_minLookahead = 0;

	ProcessBuffer();

	m_minLookahead = MAX_MATCH;

	EndBlock(false);

	if (hardFlush)

		EncodeBlock(false, STORED);

	return false;

}

void Deflator::LiteralByte(byte b)

{

	if (m_matchBufferEnd == m_matchBuffer.size())

		EndBlock(false);

	m_matchBuffer[m_matchBufferEnd++].literalCode = b;

	m_literalCounts[b]++;

	m_blockLength++;

}

void Deflator::MatchFound(unsigned int distance, unsigned int length)

{

	if (m_matchBufferEnd == m_matchBuffer.size())

		EndBlock(false);

	static const unsigned int lengthCodes[] = {

		257, 258, 259, 260, 261, 262, 263, 264, 265, 265, 266, 266, 267, 267, 268, 268,

		269, 269, 269, 269, 270, 270, 270, 270, 271, 271, 271, 271, 272, 272, 272, 272,

		273, 273, 273, 273, 273, 273, 273, 273, 274, 274, 274, 274, 274, 274, 274, 274,

		275, 275, 275, 275, 275, 275, 275, 275, 276, 276, 276, 276, 276, 276, 276, 276,

		277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277,

		278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278,

		279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279,

		280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280,

		281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281,

		281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281,

		282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282,

		282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282,

		283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283,

		283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283,

		284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284,

		284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 285};

	static const unsigned int lengthBases[] = {3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43,51,59,67,83,99,115,131,163,195,227,258};

	static const unsigned int distanceBases[30] = 

		{1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577};

	EncodedMatch &m = m_matchBuffer[m_matchBufferEnd++];

	assert(length >= 3);

	unsigned int lengthCode = lengthCodes[length-3];

	m.literalCode = lengthCode;

	m.literalExtra = length - lengthBases[lengthCode-257];

	unsigned int distanceCode = (unsigned int)(upper_bound(distanceBases, distanceBases+30, distance) - distanceBases - 1);

	m.distanceCode = distanceCode;

	m.distanceExtra = distance - distanceBases[distanceCode];

	m_literalCounts[lengthCode]++;

	m_distanceCounts[distanceCode]++;

	m_blockLength += length;

}

inline unsigned int CodeLengthEncode(const unsigned int *begin, 

									 const unsigned int *end, 

									 const unsigned int *& p, 

									 unsigned int &extraBits, 

									 unsigned int &extraBitsLength)

{

	unsigned int v = *p;

	if ((end-p) >= 3)

	{

		const unsigned int *oldp = p;

		if (v==0 && p[1]==0 && p[2]==0)

		{

			for (p=p+3; p!=end && *p==0 && p!=oldp+138; p++) {}

			unsigned int repeat = (unsigned int)(p - oldp);

			if (repeat <= 10)

			{

				extraBits = repeat-3;

				extraBitsLength = 3;

				return 17;

			}

			else

			{