summaryrefslogtreecommitdiff
path: root/zinflate.h
blob: bebc0fdf6ffdc98baaaab3167c3a26a529c6d068 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
// zinflate.h - originally written and placed in the public domain by Wei Dai

/// \file zinflate.h
/// \brief DEFLATE compression and decompression (RFC 1951)

#ifndef CRYPTOPP_ZINFLATE_H
#define CRYPTOPP_ZINFLATE_H

#include "cryptlib.h"
#include "secblock.h"
#include "filters.h"
#include "stdcpp.h"

NAMESPACE_BEGIN(CryptoPP)

/// \since Crypto++ 1.0
class LowFirstBitReader
{
public:
	LowFirstBitReader(BufferedTransformation &store)
		: m_store(store), m_buffer(0), m_bitsBuffered(0) {}
	unsigned int BitsBuffered() const {return m_bitsBuffered;}
	unsigned long PeekBuffer() const {return m_buffer;}
	bool FillBuffer(unsigned int length);
	unsigned long PeekBits(unsigned int length);
	void SkipBits(unsigned int length);
	unsigned long GetBits(unsigned int length);

private:
	BufferedTransformation &m_store;
	unsigned long m_buffer;
	unsigned int m_bitsBuffered;
};

struct CodeLessThan;

/// \brief Huffman Decoder
/// \since Crypto++ 1.0
class HuffmanDecoder
{
public:
	typedef unsigned int code_t;
	typedef unsigned int value_t;
	enum {MAX_CODE_BITS = sizeof(code_t)*8};

	class Err : public Exception {public: Err(const std::string &what) : Exception(INVALID_DATA_FORMAT, "HuffmanDecoder: " + what) {}};

	HuffmanDecoder() : m_maxCodeBits(0), m_cacheBits(0), m_cacheMask(0), m_normalizedCacheMask(0) {}
	HuffmanDecoder(const unsigned int *codeBitLengths, unsigned int nCodes)
		: m_maxCodeBits(0), m_cacheBits(0), m_cacheMask(0), m_normalizedCacheMask(0)
			{Initialize(codeBitLengths, nCodes);}

	void Initialize(const unsigned int *codeBitLengths, unsigned int nCodes);
	unsigned int Decode(code_t code, /* out */ value_t &value) const;
	bool Decode(LowFirstBitReader &reader, value_t &value) const;

private:
	friend struct CodeLessThan;

	struct CodeInfo
	{
		CodeInfo(code_t code=0, unsigned int len=0, value_t value=0) : code(code), len(len), value(value) {}
		inline bool operator<(const CodeInfo &rhs) const {return code < rhs.code;}
		code_t code;
		unsigned int len;
		value_t value;
	};

	struct LookupEntry
	{
		unsigned int type;
		union
		{
			value_t value;
			const CodeInfo *begin;
		};
		union
		{
			unsigned int len;
			const CodeInfo *end;
		};
	};

	static code_t NormalizeCode(code_t code, unsigned int codeBits);
	void FillCacheEntry(LookupEntry &entry, code_t normalizedCode) const;

	unsigned int m_maxCodeBits, m_cacheBits, m_cacheMask, m_normalizedCacheMask;
	std::vector<CodeInfo, AllocatorWithCleanup<CodeInfo> > m_codeToValue;
	mutable std::vector<LookupEntry, AllocatorWithCleanup<LookupEntry> > m_cache;
};

/// \brief DEFLATE decompressor (RFC 1951)
/// \since Crypto++ 1.0
class Inflator : public AutoSignaling<Filter>
{
public:
	class Err : public Exception
	{
	public:
		Err(ErrorType e, const std::string &s)
			: Exception(e, s) {}
	};
	/// \brief Exception thrown when a truncated stream is encountered
	class UnexpectedEndErr : public Err {public: UnexpectedEndErr() : Err(INVALID_DATA_FORMAT, "Inflator: unexpected end of compressed block") {}};
	/// \brief Exception thrown when a bad block is encountered
	class BadBlockErr : public Err {public: BadBlockErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in compressed block") {}};
	/// \brief Exception thrown when an invalid distance is encountered
	class BadDistanceErr : public Err {public: BadDistanceErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in bit distance") {}};

	/// \brief RFC 1951 Decompressor
	/// \param attachment the filter's attached transformation
	/// \param repeat decompress multiple compressed streams in series
	/// \param autoSignalPropagation 0 to turn off MessageEnd signal
	Inflator(BufferedTransformation *attachment = NULLPTR, bool repeat = false, int autoSignalPropagation = -1);

	void IsolatedInitialize(const NameValuePairs &parameters);
	size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking);
	bool IsolatedFlush(bool hardFlush, bool blocking);

	virtual unsigned int GetLog2WindowSize() const {return 15;}

protected:
	ByteQueue m_inQueue;

private:
	virtual unsigned int MaxPrestreamHeaderSize() const {return 0;}
	virtual void ProcessPrestreamHeader() {}
	virtual void ProcessDecompressedData(const byte *string, size_t length)
		{AttachedTransformation()->Put(string, length);}
	virtual unsigned int MaxPoststreamTailSize() const {return 0;}
	virtual void ProcessPoststreamTail() {}

	void ProcessInput(bool flush);
	void DecodeHeader();
	bool DecodeBody();
	void FlushOutput();
	void OutputByte(byte b);
	void OutputString(const byte *string, size_t length);
	void OutputPast(unsigned int length, unsigned int distance);

	void CreateFixedDistanceDecoder();
	void CreateFixedLiteralDecoder();

	const HuffmanDecoder& GetLiteralDecoder();
	const HuffmanDecoder& GetDistanceDecoder();

	enum State {PRE_STREAM, WAIT_HEADER, DECODING_BODY, POST_STREAM, AFTER_END};
	State m_state;
	bool m_repeat, m_eof, m_wrappedAround;
	byte m_blockType;
	word16 m_storedLen;
	enum NextDecode {LITERAL, LENGTH_BITS, DISTANCE, DISTANCE_BITS};
	NextDecode m_nextDecode;
	unsigned int m_literal, m_distance;	// for LENGTH_BITS or DISTANCE_BITS
	HuffmanDecoder m_dynamicLiteralDecoder, m_dynamicDistanceDecoder;
	member_ptr<HuffmanDecoder> m_fixedLiteralDecoder, m_fixedDistanceDecoder;
	LowFirstBitReader m_reader;
	SecByteBlock m_window;
	size_t m_current, m_lastFlush;
};

NAMESPACE_END

#endif