include/cryptopp/zdeflate.h

0001 // zdeflate.h - originally written and placed in the public domain by Wei Dai

0002
0003 /// \file zdeflate.h

0004 /// \brief DEFLATE compression and decompression (RFC 1951)

0005
0006 #ifndef CRYPTOPP_ZDEFLATE_H
0007 #define CRYPTOPP_ZDEFLATE_H
0008
0009 #include "cryptlib.h"
0010 #include "filters.h"
0011 #include "misc.h"
0012
0013 NAMESPACE_BEGIN(CryptoPP)
0014
0015 /// \brief Encoding table writer

0016 /// \since Crypto++ 1.0

0017 class LowFirstBitWriter : public Filter
0018 {
0019 public:
0020     /// \brief Construct a LowFirstBitWriter

0021     /// \param attachment an attached transformation

0022     LowFirstBitWriter(BufferedTransformation *attachment);
0023
0024     void PutBits(unsigned long value, unsigned int length);
0025     void FlushBitBuffer();
0026     void ClearBitBuffer();
0027
0028     void StartCounting();
0029     unsigned long FinishCounting();
0030
0031 protected:
0032     bool m_counting;
0033     unsigned long m_bitCount;
0034     unsigned long m_buffer;
0035     unsigned int m_bitsBuffered, m_bytesBuffered;
0036     FixedSizeSecBlock<byte, 256> m_outputBuffer;
0037 };
0038
0039 /// \brief Huffman Encoder

0040 /// \since Crypto++ 1.0

0041 class HuffmanEncoder
0042 {
0043 public:
0044     typedef unsigned int code_t;
0045     typedef unsigned int value_t;
0046
0047     /// \brief Construct a HuffmanEncoder

0048     HuffmanEncoder() {}
0049
0050     /// \brief Construct a HuffmanEncoder

0051     /// \param codeBits a table of code bits

0052     /// \param nCodes the number of codes in the table

0053     HuffmanEncoder(const unsigned int *codeBits, unsigned int nCodes);
0054
0055     /// \brief Initialize or reinitialize this object

0056     /// \param codeBits a table of code bits

0057     /// \param nCodes the number of codes in the table

0058     void Initialize(const unsigned int *codeBits, unsigned int nCodes);
0059
0060     static void GenerateCodeLengths(unsigned int *codeBits, unsigned int maxCodeBits, const unsigned int *codeCounts, size_t nCodes);
0061
0062     void Encode(LowFirstBitWriter &writer, value_t value) const;
0063
0064     struct Code
0065     {
0066         unsigned int code;
0067         unsigned int len;
0068     };
0069
0070     SecBlock<Code> m_valueToCode;
0071 };
0072
0073 /// \brief DEFLATE compressor (RFC 1951)

0074 /// \since Crypto++ 1.0

0075 class Deflator : public LowFirstBitWriter
0076 {
0077 public:
0078     /// \brief Deflate level as enumerated values.

0079     enum {
0080         /// \brief Minimum deflation level, fastest speed (0)

0081         MIN_DEFLATE_LEVEL = 0,
0082         /// \brief Default deflation level, compromise between speed (6)

0083         DEFAULT_DEFLATE_LEVEL = 6,
0084         /// \brief Minimum deflation level, slowest speed (9)

0085         MAX_DEFLATE_LEVEL = 9};
0086
0087     /// \brief Windows size as enumerated values.

0088     enum {
0089         /// \brief Minimum window size, smallest table (9)

0090         MIN_LOG2_WINDOW_SIZE = 9,
0091         /// \brief Default window size (15)

0092         DEFAULT_LOG2_WINDOW_SIZE = 15,
0093         /// \brief Maximum window size, largest table (15)

0094         MAX_LOG2_WINDOW_SIZE = 15};
0095
0096     /// \brief Construct a Deflator compressor

0097     /// \param attachment an attached transformation

0098     /// \param deflateLevel the deflate level

0099     /// \param log2WindowSize the window size

0100     /// \param detectUncompressible flag to detect if data is compressible

0101     /// \details detectUncompressible makes it faster to process uncompressible files, but

0102     ///   if a file has both compressible and uncompressible parts, it may fail to compress

0103     ///   some of the compressible parts.

0104     Deflator(BufferedTransformation *attachment=NULLPTR, int deflateLevel=DEFAULT_DEFLATE_LEVEL, int log2WindowSize=DEFAULT_LOG2_WINDOW_SIZE, bool detectUncompressible=true);
0105     /// \brief Construct a Deflator compressor

0106     /// \param parameters a set of NameValuePairs to initialize this object

0107     /// \param attachment an attached transformation

0108     /// \details Possible parameter names: Log2WindowSize, DeflateLevel, DetectUncompressible

0109     Deflator(const NameValuePairs &parameters, BufferedTransformation *attachment=NULLPTR);
0110
0111     /// \brief Sets the deflation level

0112     /// \param deflateLevel the level of deflation

0113     /// \details SetDeflateLevel can be used to set the deflate level in the middle of compression

0114     void SetDeflateLevel(int deflateLevel);
0115
0116     /// \brief Retrieves the deflation level

0117     /// \return the level of deflation

0118     int GetDeflateLevel() const {return m_deflateLevel;}
0119
0120     /// \brief Retrieves the window size

0121     /// \return the windows size

0122     int GetLog2WindowSize() const {return m_log2WindowSize;}
0123
0124     void IsolatedInitialize(const NameValuePairs &parameters);
0125     size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking);
0126     bool IsolatedFlush(bool hardFlush, bool blocking);
0127
0128 protected:
0129     virtual void WritePrestreamHeader() {}
0130     virtual void ProcessUncompressedData(const byte *string, size_t length)
0131         {CRYPTOPP_UNUSED(string), CRYPTOPP_UNUSED(length);}
0132     virtual void WritePoststreamTail() {}
0133
0134     enum {STORED = 0, STATIC = 1, DYNAMIC = 2};
0135     enum {MIN_MATCH = 3, MAX_MATCH = 258};
0136
0137     void InitializeStaticEncoders();
0138     void Reset(bool forceReset = false);
0139     unsigned int FillWindow(const byte *str, size_t length);
0140     unsigned int ComputeHash(const byte *str) const;
0141     unsigned int LongestMatch(unsigned int &bestMatch) const;
0142     void InsertString(unsigned int start);
0143     void ProcessBuffer();
0144
0145     void LiteralByte(byte b);
0146     void MatchFound(unsigned int distance, unsigned int length);
0147     void EncodeBlock(bool eof, unsigned int blockType);
0148     void EndBlock(bool eof);
0149
0150     struct EncodedMatch
0151     {
0152         unsigned literalCode : 9;
0153         unsigned literalExtra : 5;
0154         unsigned distanceCode : 5;
0155         unsigned distanceExtra : 13;
0156     };
0157
0158     int m_deflateLevel, m_log2WindowSize, m_compressibleDeflateLevel;
0159     unsigned int m_detectSkip, m_detectCount;
0160     unsigned int DSIZE, DMASK, HSIZE, HMASK, GOOD_MATCH, MAX_LAZYLENGTH, MAX_CHAIN_LENGTH;
0161     bool m_headerWritten, m_matchAvailable;
0162     unsigned int m_dictionaryEnd, m_stringStart, m_lookahead, m_minLookahead, m_previousMatch, m_previousLength;
0163     HuffmanEncoder m_staticLiteralEncoder, m_staticDistanceEncoder, m_dynamicLiteralEncoder, m_dynamicDistanceEncoder;
0164     SecByteBlock m_byteBuffer;
0165     SecBlock<word16> m_head, m_prev;
0166     FixedSizeSecBlock<unsigned int, 286> m_literalCounts;
0167     FixedSizeSecBlock<unsigned int, 30> m_distanceCounts;
0168     SecBlock<EncodedMatch> m_matchBuffer;
0169     unsigned int m_matchBufferEnd, m_blockStart, m_blockLength;
0170 };
0171
0172 NAMESPACE_END
0173
0174 #endif