Initial revision

1 files changed, 736 insertions, 0 deletions

diff --git a/zdeflate.cpp b/zdeflate.cpp
new file mode 100644
index 00000000..98dcad39
--- /dev/null
+++ b/zdeflate.cpp
@@ -0,0 +1,736 @@
+// 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 *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
+{
+	unsigned int symbol;
+	union {unsigned int parent, 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;}
+};
+
+void HuffmanEncoder::GenerateCodeLengths(unsigned int *codeBits, unsigned int maxCodeBits, const unsigned int *codeCounts, unsigned int nCodes)
+{
+	assert(nCodes > 0);
+	assert(nCodes <= (unsigned int)(1 << maxCodeBits));
+
+	unsigned int 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());
+	unsigned int 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);
+
+	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;
+	SecBlockWithHint<unsigned int, 15+1> 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 > (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)
+	: LowFirstBitWriter(attachment)
+{
+	InitializeStaticEncoders();
+	IsolatedInitialize(MakeParameters("DeflateLevel", deflateLevel)("Log2WindowSize", log2WindowSize));
+}
+
+Deflator::Deflator(const NameValuePairs &parameters, BufferedTransformation *attachment)
+	: LowFirstBitWriter(attachment)
+{
+	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);
+
+	SetDeflateLevel(parameters.GetIntValueWithDefault("DeflateLevel", DEFAULT_DEFLATE_LEVEL));
+	Reset(true);
+}
+
+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_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(int deflateLevel)
+{
+	if (!(MIN_DEFLATE_LEVEL <= deflateLevel && deflateLevel <= MAX_DEFLATE_LEVEL))
+		throw InvalidArgument("Deflator: " + IntToString(deflateLevel) + " is an invalid deflate level");
+
+	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;
+
+		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);
+
+		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;
+				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)
+	{
+		while (m_lookahead > 0)
+		{
+			LiteralByte(m_byteBuffer[m_stringStart++]);
+			m_lookahead--;
+		}
+		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 = (m_previousLength > 0 && 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;
+				m_previousLength = 0;
+			}
+			else
+			{
+				m_previousLength = matchLength;
+				m_previousMatch = matchPosition;
+				LiteralByte(m_byteBuffer[m_stringStart-1]);
+				m_stringStart++;
+				m_lookahead--;
+			}
+		}
+		else
+		{
+			m_previousLength = LongestMatch(m_previousMatch);
+			m_matchAvailable = true;
+			m_stringStart++;
+			m_lookahead--;
+		}
+	}
+	assert(m_stringStart - (m_blockStart+m_blockLength) <= 1);
+	if (m_minLookahead == 0 && m_matchAvailable)
+	{
+		LiteralByte(m_byteBuffer[m_stringStart-1]);
+		m_matchAvailable = false;
+	}
+}
+
+unsigned int Deflator::Put2(const byte *str, unsigned int length, int messageEnd, bool blocking)
+{
+	if (!blocking)
+		throw BlockingInputOnly("Deflator");
+
+	unsigned int 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)
+{
+	m_matchBuffer[m_matchBufferEnd++].literalCode = b;
+	m_literalCounts[b]++;
+
+	if (m_blockStart+(++m_blockLength) == m_byteBuffer.size() || m_matchBufferEnd == m_matchBuffer.size())
+		EndBlock(false);
+}
+
+void Deflator::MatchFound(unsigned int distance, unsigned int length)
+{
+	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++];
+	unsigned int lengthCode = lengthCodes[length-3];
+	m.literalCode = lengthCode;
+	m.literalExtra = length - lengthBases[lengthCode-257];
+	unsigned int distanceCode = upper_bound(distanceBases, distanceBases+30, distance) - distanceBases - 1;
+	m.distanceCode = distanceCode;
+	m.distanceExtra = distance - distanceBases[distanceCode];
+
+	m_literalCounts[lengthCode]++;
+	m_distanceCounts[distanceCode]++;
+
+	if (m_blockStart+(m_blockLength+=length) == m_byteBuffer.size() || m_matchBufferEnd == m_matchBuffer.size())
+		EndBlock(false);
+}
+
+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 = 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 = 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());
+		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__)
+			// VC60 workaround: built-in reverse_iterator has two template parameters, Dinkumware only has one
+			typedef reverse_bidirectional_iterator<unsigned int *, 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 = 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 = 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_matchBufferEnd == 0 && !eof)
+		return;
+
+	if (m_deflateLevel == 0)
+		EncodeBlock(eof, STORED);
+	else if (m_blockLength < 128)
+		EncodeBlock(eof, STATIC);
+	else
+	{
+		unsigned int storedLen = 8*(m_blockLength+4) + RoundUpToMultipleOf(m_bitsBuffered+3, 8U)-m_bitsBuffered;
+		StartCounting();
+		EncodeBlock(eof, STATIC);
+		unsigned int staticLen = FinishCounting();
+		StartCounting();
+		EncodeBlock(eof, DYNAMIC);
+		unsigned int dynamicLen = FinishCounting();
+
+		if (storedLen <= staticLen && storedLen <= dynamicLen)
+			EncodeBlock(eof, STORED);
+		else if (staticLen <= dynamicLen)
+			EncodeBlock(eof, STATIC);
+		else
+			EncodeBlock(eof, DYNAMIC);
+	}
+
+	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