zdeflate.cpp

一个DES,RSA,MD5,RC4等加密算法的源码

// 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>

NAMESPACE_BEGIN(CryptoPP)

using namespace std;

LowFirstBitWriter::LowFirstBitWriter(BufferedTransformation *outQ)
	: Filter(outQ), m_counting(false), m_buffer(0), m_bitsBuffered(0)
	, m_bytesBuffered(0), m_outputBuffer(256)
{
}

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()->Put(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()->Put(m_outputBuffer, m_bytesBuffered);
			m_bytesBuffered = 0;
		}
		if (m_bitsBuffered > 0)
		{
			AttachedTransformation()->Put((byte)m_buffer);
			m_buffer = 0;
			m_bitsBuffered = 0;
		}
	}
}

HuffmanEncoder::HuffmanEncoder(const unsigned int *codeBits, unsigned int nCodes)
{
	Initialize(codeBits, nCodes);
}

struct HuffmanNode
{
	inline bool operator<(const HuffmanNode &rhs) const {return freq < rhs.freq;}
	unsigned int symbol;
	union {unsigned int parent, depth, freq;};
};

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

void HuffmanEncoder::GenerateCodeLengths(unsigned int *codeBits, unsigned int maxCodeBits, const unsigned int *codeCounts, unsigned int nCodes)
{
	assert(nCodes > 0);
	assert(nCodes <= (1 << maxCodeBits));

	unsigned int i;
	SecBlock<HuffmanNode> tree(nCodes);
	for (i=0; i<nCodes; i++)
	{
		tree[i].symbol = i;
		tree[i].freq = codeCounts[i];
	}
	sort(tree.Begin(), tree.End());
	unsigned int treeBegin = upper_bound(tree.Begin(), tree.End(), 0) - tree.Begin();
	if (treeBegin == nCodes)
	{	// special case for no codes
		fill(codeBits, codeBits+nCodes, 0);
		return;
	}
	tree.Resize(nCodes + nCodes - treeBegin - 1);

	unsigned int leastLeaf = treeBegin, leastInterior = nCodes;
	for (i=nCodes; i<tree.size; i++)
	{
		unsigned int 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;
	SecBlock<unsigned int> blCount(maxCodeBits+1);
	fill(blCount.Begin(), blCount.End(), 0);
	for (i=treeBegin; i<nCodes; i++)
	{
		unsigned int depth = STDMIN(maxCodeBits, tree[tree[i].parent].depth + 1);
		blCount[depth]++;
		sum += 1 << (maxCodeBits - depth);
	}

	unsigned int overflow = sum > (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

	SecBlock<unsigned int> 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;
	SecBlock<code_t> 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 *outQ, unsigned int deflateLevel, unsigned int log2WindowSize)
	: LowFirstBitWriter(outQ)
	, m_log2WindowSize(log2WindowSize)
	, m_literalCounts(286), m_distanceCounts(30)
	, DSIZE(1<<log2WindowSize), DMASK(DSIZE-1), HSIZE(1<<log2WindowSize), HMASK(HSIZE-1)
	, m_head(HSIZE), m_prev(DSIZE)
	, m_byteBuffer(2*DSIZE), m_matchBuffer(DSIZE/2)
{
	assert(0 <= deflateLevel && deflateLevel <= 9);
	assert(9 <= log2WindowSize && log2WindowSize <= 15);

	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);

	SetDeflateLevel(deflateLevel);
	Reset();
}

void Deflator::Reset()
{
	assert(m_bitsBuffered == 0);

	m_headerWritten = false;
	m_matchAvailable = false;
	m_dictionaryEnd = 0;
	m_stringStart = 0;
	m_lookahead = 0;
	m_minLookahead = MAX_MATCH;
	m_previousMatch = 0;
	m_previousLength = 0;
	m_matchBufferEnd = 0;
	m_blockStart = 0;
	m_blockLength = 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(unsigned int deflateLevel)
{
	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, unsigned int length)
{
	unsigned int accepted = STDMIN(length, 2*DSIZE-(m_stringStart+m_lookahead));

	if (m_stringStart >= 2*DSIZE - 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_previousMatch >= DSIZE || m_previousLength < MIN_MATCH);
		m_previousMatch -= DSIZE;
		assert(m_blockStart >= DSIZE);
		m_blockStart -= DSIZE;

		unsigned int i, j;

		for (i=0; i<HSIZE; i++)
			m_head[i] = (j=m_head[i]) < DSIZE ? 0 : j-DSIZE;

		for (i=0; i<DSIZE; i++)
			m_prev[i] = (j=m_prev[i]) < DSIZE ? 0 : j-DSIZE;

		accepted = STDMIN(accepted + DSIZE, 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 = std::mismatch(scan+3, scanEnd, match+3).first - scan;
			assert(len != bestLength);
			if (len > bestLength)
			{
				bestLength = len;