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