1 // zdeflate.h - originally written and placed in the public domain by Wei Dai
2
3 /// \file zdeflate.h
4 /// \brief DEFLATE compression and decompression (RFC 1951)
5
6 #ifndef CRYPTOPP_ZDEFLATE_H
7 #define CRYPTOPP_ZDEFLATE_H
8
9 #include "cryptlib.h"
10 #include "filters.h"
11 #include "misc.h"
12
NAMESPACE_BEGIN(CryptoPP)13 NAMESPACE_BEGIN(CryptoPP)
14
15 /// \brief Encoding table writer
16 /// \since Crypto++ 1.0
17 class LowFirstBitWriter : public Filter
18 {
19 public:
20 /// \brief Construct a LowFirstBitWriter
21 /// \param attachment an attached transformation
22 LowFirstBitWriter(BufferedTransformation *attachment);
23
24 void PutBits(unsigned long value, unsigned int length);
25 void FlushBitBuffer();
26 void ClearBitBuffer();
27
28 void StartCounting();
29 unsigned long FinishCounting();
30
31 protected:
32 bool m_counting;
33 unsigned long m_bitCount;
34 unsigned long m_buffer;
35 unsigned int m_bitsBuffered, m_bytesBuffered;
36 FixedSizeSecBlock<byte, 256> m_outputBuffer;
37 };
38
39 /// \brief Huffman Encoder
40 /// \since Crypto++ 1.0
41 class HuffmanEncoder
42 {
43 public:
44 typedef unsigned int code_t;
45 typedef unsigned int value_t;
46
47 /// \brief Construct a HuffmanEncoder
HuffmanEncoder()48 HuffmanEncoder() {}
49
50 /// \brief Construct a HuffmanEncoder
51 /// \param codeBits a table of code bits
52 /// \param nCodes the number of codes in the table
53 HuffmanEncoder(const unsigned int *codeBits, unsigned int nCodes);
54
55 /// \brief Initialize or reinitialize this object
56 /// \param codeBits a table of code bits
57 /// \param nCodes the number of codes in the table
58 void Initialize(const unsigned int *codeBits, unsigned int nCodes);
59
60 static void GenerateCodeLengths(unsigned int *codeBits, unsigned int maxCodeBits, const unsigned int *codeCounts, size_t nCodes);
61
62 void Encode(LowFirstBitWriter &writer, value_t value) const;
63
64 struct Code
65 {
66 unsigned int code;
67 unsigned int len;
68 };
69
70 SecBlock<Code> m_valueToCode;
71 };
72
73 /// \brief DEFLATE compressor (RFC 1951)
74 /// \since Crypto++ 1.0
75 class Deflator : public LowFirstBitWriter
76 {
77 public:
78 /// \brief Deflate level as enumerated values.
79 enum {
80 /// \brief Minimum deflation level, fastest speed (0)
81 MIN_DEFLATE_LEVEL = 0,
82 /// \brief Default deflation level, compromise between speed (6)
83 DEFAULT_DEFLATE_LEVEL = 6,
84 /// \brief Minimum deflation level, slowest speed (9)
85 MAX_DEFLATE_LEVEL = 9};
86
87 /// \brief Windows size as enumerated values.
88 enum {
89 /// \brief Minimum window size, smallest table (9)
90 MIN_LOG2_WINDOW_SIZE = 9,
91 /// \brief Default window size (15)
92 DEFAULT_LOG2_WINDOW_SIZE = 15,
93 /// \brief Maximum window size, largest table (15)
94 MAX_LOG2_WINDOW_SIZE = 15};
95
96 /// \brief Construct a Deflator compressor
97 /// \param attachment an attached transformation
98 /// \param deflateLevel the deflate level
99 /// \param log2WindowSize the window size
100 /// \param detectUncompressible flag to detect if data is compressible
101 /// \details detectUncompressible makes it faster to process uncompressible files, but
102 /// if a file has both compressible and uncompressible parts, it may fail to compress
103 /// some of the compressible parts.
104 Deflator(BufferedTransformation *attachment=NULLPTR, int deflateLevel=DEFAULT_DEFLATE_LEVEL, int log2WindowSize=DEFAULT_LOG2_WINDOW_SIZE, bool detectUncompressible=true);
105 /// \brief Construct a Deflator compressor
106 /// \param parameters a set of NameValuePairs to initialize this object
107 /// \param attachment an attached transformation
108 /// \details Possible parameter names: Log2WindowSize, DeflateLevel, DetectUncompressible
109 Deflator(const NameValuePairs ¶meters, BufferedTransformation *attachment=NULLPTR);
110
111 /// \brief Sets the deflation level
112 /// \param deflateLevel the level of deflation
113 /// \details SetDeflateLevel can be used to set the deflate level in the middle of compression
114 void SetDeflateLevel(int deflateLevel);
115
116 /// \brief Retrieves the deflation level
117 /// \return the level of deflation
GetDeflateLevel()118 int GetDeflateLevel() const {return m_deflateLevel;}
119
120 /// \brief Retrieves the window size
121 /// \return the windows size
GetLog2WindowSize()122 int GetLog2WindowSize() const {return m_log2WindowSize;}
123
124 void IsolatedInitialize(const NameValuePairs ¶meters);
125 size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking);
126 bool IsolatedFlush(bool hardFlush, bool blocking);
127
128 protected:
WritePrestreamHeader()129 virtual void WritePrestreamHeader() {}
ProcessUncompressedData(const byte * string,size_t length)130 virtual void ProcessUncompressedData(const byte *string, size_t length)
131 {CRYPTOPP_UNUSED(string), CRYPTOPP_UNUSED(length);}
WritePoststreamTail()132 virtual void WritePoststreamTail() {}
133
134 enum {STORED = 0, STATIC = 1, DYNAMIC = 2};
135 enum {MIN_MATCH = 3, MAX_MATCH = 258};
136
137 void InitializeStaticEncoders();
138 void Reset(bool forceReset = false);
139 unsigned int FillWindow(const byte *str, size_t length);
140 unsigned int ComputeHash(const byte *str) const;
141 unsigned int LongestMatch(unsigned int &bestMatch) const;
142 void InsertString(unsigned int start);
143 void ProcessBuffer();
144
145 void LiteralByte(byte b);
146 void MatchFound(unsigned int distance, unsigned int length);
147 void EncodeBlock(bool eof, unsigned int blockType);
148 void EndBlock(bool eof);
149
150 struct EncodedMatch
151 {
152 unsigned literalCode : 9;
153 unsigned literalExtra : 5;
154 unsigned distanceCode : 5;
155 unsigned distanceExtra : 13;
156 };
157
158 int m_deflateLevel, m_log2WindowSize, m_compressibleDeflateLevel;
159 unsigned int m_detectSkip, m_detectCount;
160 unsigned int DSIZE, DMASK, HSIZE, HMASK, GOOD_MATCH, MAX_LAZYLENGTH, MAX_CHAIN_LENGTH;
161 bool m_headerWritten, m_matchAvailable;
162 unsigned int m_dictionaryEnd, m_stringStart, m_lookahead, m_minLookahead, m_previousMatch, m_previousLength;
163 HuffmanEncoder m_staticLiteralEncoder, m_staticDistanceEncoder, m_dynamicLiteralEncoder, m_dynamicDistanceEncoder;
164 SecByteBlock m_byteBuffer;
165 SecBlock<word16> m_head, m_prev;
166 FixedSizeSecBlock<unsigned int, 286> m_literalCounts;
167 FixedSizeSecBlock<unsigned int, 30> m_distanceCounts;
168 SecBlock<EncodedMatch> m_matchBuffer;
169 unsigned int m_matchBufferEnd, m_blockStart, m_blockLength;
170 };
171
172 NAMESPACE_END
173
174 #endif
175