zdeflate.cpp

lots Elliptic curve cryptography codes. Use Visual c++ to compile

				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
			{
				extraBits = repeat-11;
				extraBitsLength = 7;
				return 18;
			}
		}
		else if (p!=begin && v==p[-1] && v==p[1] && v==p[2])
		{
			for (p=p+3; p!=end && *p==v && p!=oldp+6; p++) {}
			unsigned int repeat = (unsigned int)(p - oldp);
			extraBits = repeat-3;
			extraBitsLength = 2;
			return 16;
		}
	}
	p++;
	extraBits = 0;
	extraBitsLength = 0;
	return v;
}

void Deflator::EncodeBlock(bool eof, unsigned int blockType)
{
	PutBits(eof, 1);
	PutBits(blockType, 2);

	if (blockType == STORED)
	{
		assert(m_blockStart + m_blockLength <= m_byteBuffer.size());
		assert(m_blockLength <= 0xffff);
		FlushBitBuffer();
		AttachedTransformation()->PutWord16(m_blockLength, LITTLE_ENDIAN_ORDER);
		AttachedTransformation()->PutWord16(~m_blockLength, LITTLE_ENDIAN_ORDER);
		AttachedTransformation()->Put(m_byteBuffer + m_blockStart, m_blockLength);
	}
	else
	{
		if (blockType == DYNAMIC)
		{
#if defined(_MSC_VER) && !defined(__MWERKS__) && (_MSC_VER <= 1300)
			// VC60 and VC7 workaround: built-in reverse_iterator has two template parameters, Dinkumware only has one
			typedef reverse_bidirectional_iterator<unsigned int *, unsigned int> RevIt;
#elif defined(_RWSTD_NO_CLASS_PARTIAL_SPEC)
	typedef reverse_iterator<unsigned int *, random_access_iterator_tag, unsigned int> RevIt;
#else
			typedef reverse_iterator<unsigned int *> RevIt;
#endif

			FixedSizeSecBlock<unsigned int, 286> literalCodeLengths;
			FixedSizeSecBlock<unsigned int, 30> distanceCodeLengths;

			m_literalCounts[256] = 1;
			HuffmanEncoder::GenerateCodeLengths(literalCodeLengths, 15, m_literalCounts, 286);
			m_dynamicLiteralEncoder.Initialize(literalCodeLengths, 286);
			unsigned int hlit = (unsigned int)(find_if(RevIt(literalCodeLengths.end()), RevIt(literalCodeLengths.begin()+257), bind2nd(not_equal_to<unsigned int>(), 0)).base() - (literalCodeLengths.begin()+257));

			HuffmanEncoder::GenerateCodeLengths(distanceCodeLengths, 15, m_distanceCounts, 30);
			m_dynamicDistanceEncoder.Initialize(distanceCodeLengths, 30);
			unsigned int hdist = (unsigned int)(find_if(RevIt(distanceCodeLengths.end()), RevIt(distanceCodeLengths.begin()+1), bind2nd(not_equal_to<unsigned int>(), 0)).base() - (distanceCodeLengths.begin()+1));

			SecBlockWithHint<unsigned int, 286+30> combinedLengths(hlit+257+hdist+1);
			memcpy(combinedLengths, literalCodeLengths, (hlit+257)*sizeof(unsigned int));
			memcpy(combinedLengths+hlit+257, distanceCodeLengths, (hdist+1)*sizeof(unsigned int));

			FixedSizeSecBlock<unsigned int, 19> codeLengthCodeCounts, codeLengthCodeLengths;
			fill(codeLengthCodeCounts.begin(), codeLengthCodeCounts.end(), 0);
			const unsigned int *p = combinedLengths.begin(), *begin = combinedLengths.begin(), *end = combinedLengths.end();
			while (p != end)
			{
				unsigned int code, extraBits, extraBitsLength;
				code = CodeLengthEncode(begin, end, p, extraBits, extraBitsLength);
				codeLengthCodeCounts[code]++;
			}
			HuffmanEncoder::GenerateCodeLengths(codeLengthCodeLengths, 7, codeLengthCodeCounts, 19);
			HuffmanEncoder codeLengthEncoder(codeLengthCodeLengths, 19);
			static const unsigned int border[] = {    // Order of the bit length code lengths
				16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
			unsigned int hclen = 19;
			while (hclen > 4 && codeLengthCodeLengths[border[hclen-1]] == 0)
				hclen--;
			hclen -= 4;

			PutBits(hlit, 5);
			PutBits(hdist, 5);
			PutBits(hclen, 4);

			for (unsigned int i=0; i<hclen+4; i++)
				PutBits(codeLengthCodeLengths[border[i]], 3);

			p = combinedLengths.begin();
			while (p != end)
			{
				unsigned int code, extraBits, extraBitsLength;
				code = CodeLengthEncode(begin, end, p, extraBits, extraBitsLength);
				codeLengthEncoder.Encode(*this, code);
				PutBits(extraBits, extraBitsLength);
			}
		}

		static const unsigned int lengthExtraBits[] = {
			0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
			3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
		static const unsigned int distanceExtraBits[] = {
			0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
			7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
			12, 12, 13, 13};

		const HuffmanEncoder &literalEncoder = (blockType == STATIC) ? m_staticLiteralEncoder : m_dynamicLiteralEncoder;
		const HuffmanEncoder &distanceEncoder = (blockType == STATIC) ? m_staticDistanceEncoder : m_dynamicDistanceEncoder;

		for (unsigned int i=0; i<m_matchBufferEnd; i++)
		{
			unsigned int literalCode = m_matchBuffer[i].literalCode;
			literalEncoder.Encode(*this, literalCode);
			if (literalCode >= 257)
			{
				assert(literalCode <= 285);
				PutBits(m_matchBuffer[i].literalExtra, lengthExtraBits[literalCode-257]);
				unsigned int distanceCode = m_matchBuffer[i].distanceCode;
				distanceEncoder.Encode(*this, distanceCode);
				PutBits(m_matchBuffer[i].distanceExtra, distanceExtraBits[distanceCode]);
			}
		}
		literalEncoder.Encode(*this, 256);	// end of block
	}
}

void Deflator::EndBlock(bool eof)
{
	if (m_blockLength == 0 && !eof)
		return;

	if (m_deflateLevel == 0)
	{
		EncodeBlock(eof, STORED);

		if (m_compressibleDeflateLevel > 0 && ++m_detectCount == m_detectSkip)
		{
			m_deflateLevel = m_compressibleDeflateLevel;
			m_detectCount = 1;
		}
	}
	else
	{
		unsigned long storedLen = 8*((unsigned long)m_blockLength+4) + RoundUpToMultipleOf(m_bitsBuffered+3, 8U)-m_bitsBuffered;

		StartCounting();
		EncodeBlock(eof, STATIC);
		unsigned long staticLen = FinishCounting();

		unsigned long dynamicLen;
		if (m_blockLength < 128 && m_deflateLevel < 8)
			dynamicLen = ULONG_MAX;
		else
		{
			StartCounting();
			EncodeBlock(eof, DYNAMIC);
			dynamicLen = FinishCounting();
		}

		if (storedLen <= staticLen && storedLen <= dynamicLen)
		{
			EncodeBlock(eof, STORED);

			if (m_compressibleDeflateLevel > 0)
			{
				if (m_detectSkip)
					m_deflateLevel = 0;
				m_detectSkip = m_detectSkip ? STDMIN(2*m_detectSkip, 128U) : 1;
			}
		}
		else
		{
			if (staticLen <= dynamicLen)
				EncodeBlock(eof, STATIC);
			else
				EncodeBlock(eof, DYNAMIC);

			if (m_compressibleDeflateLevel > 0)
				m_detectSkip = 0;
		}
	}

	m_matchBufferEnd = 0;
	m_blockStart += m_blockLength;
	m_blockLength = 0;
	fill(m_literalCounts.begin(), m_literalCounts.end(), 0);
	fill(m_distanceCounts.begin(), m_distanceCounts.end(), 0);
}

NAMESPACE_END