include/cryptopp/zinflate.h

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

0002
0003 /// \file zinflate.h

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

0005
0006 #ifndef CRYPTOPP_ZINFLATE_H
0007 #define CRYPTOPP_ZINFLATE_H
0008
0009 #include "cryptlib.h"
0010 #include "secblock.h"
0011 #include "filters.h"
0012 #include "stdcpp.h"
0013
0014 NAMESPACE_BEGIN(CryptoPP)
0015
0016 /// \since Crypto++ 1.0

0017 class LowFirstBitReader
0018 {
0019 public:
0020     LowFirstBitReader(BufferedTransformation &store)
0021         : m_store(store), m_buffer(0), m_bitsBuffered(0) {}
0022     unsigned int BitsBuffered() const {return m_bitsBuffered;}
0023     unsigned long PeekBuffer() const {return m_buffer;}
0024     bool FillBuffer(unsigned int length);
0025     unsigned long PeekBits(unsigned int length);
0026     void SkipBits(unsigned int length);
0027     unsigned long GetBits(unsigned int length);
0028
0029 private:
0030     BufferedTransformation &m_store;
0031     unsigned long m_buffer;
0032     unsigned int m_bitsBuffered;
0033 };
0034
0035 struct CodeLessThan;
0036
0037 /// \brief Huffman Decoder

0038 /// \since Crypto++ 1.0

0039 class HuffmanDecoder
0040 {
0041 public:
0042     typedef unsigned int code_t;
0043     typedef unsigned int value_t;
0044     enum {MAX_CODE_BITS = sizeof(code_t)*8};
0045
0046     class Err : public Exception {public: Err(const std::string &what) : Exception(INVALID_DATA_FORMAT, "HuffmanDecoder: " + what) {}};
0047
0048     HuffmanDecoder() : m_maxCodeBits(0), m_cacheBits(0), m_cacheMask(0), m_normalizedCacheMask(0) {}
0049     HuffmanDecoder(const unsigned int *codeBitLengths, unsigned int nCodes)
0050         : m_maxCodeBits(0), m_cacheBits(0), m_cacheMask(0), m_normalizedCacheMask(0)
0051             {Initialize(codeBitLengths, nCodes);}
0052
0053     void Initialize(const unsigned int *codeBitLengths, unsigned int nCodes);
0054     unsigned int Decode(code_t code, /* out */ value_t &value) const;
0055     bool Decode(LowFirstBitReader &reader, value_t &value) const;
0056
0057 private:
0058     friend struct CodeLessThan;
0059
0060     struct CodeInfo
0061     {
0062         CodeInfo(code_t code=0, unsigned int len=0, value_t value=0) : code(code), len(len), value(value) {}
0063         inline bool operator<(const CodeInfo &rhs) const {return code < rhs.code;}
0064         code_t code;
0065         unsigned int len;
0066         value_t value;
0067     };
0068
0069     struct LookupEntry
0070     {
0071         unsigned int type;
0072         union
0073         {
0074             value_t value;
0075             const CodeInfo *begin;
0076         };
0077         union
0078         {
0079             unsigned int len;
0080             const CodeInfo *end;
0081         };
0082     };
0083
0084     static code_t NormalizeCode(code_t code, unsigned int codeBits);
0085     void FillCacheEntry(LookupEntry &entry, code_t normalizedCode) const;
0086
0087     unsigned int m_maxCodeBits, m_cacheBits, m_cacheMask, m_normalizedCacheMask;
0088     std::vector<CodeInfo, AllocatorWithCleanup<CodeInfo> > m_codeToValue;
0089     mutable std::vector<LookupEntry, AllocatorWithCleanup<LookupEntry> > m_cache;
0090 };
0091
0092 /// \brief DEFLATE decompressor (RFC 1951)

0093 /// \since Crypto++ 1.0

0094 class Inflator : public AutoSignaling<Filter>
0095 {
0096 public:
0097     class Err : public Exception
0098     {
0099     public:
0100         Err(ErrorType e, const std::string &s)
0101             : Exception(e, s) {}
0102     };
0103     /// \brief Exception thrown when a truncated stream is encountered

0104     class UnexpectedEndErr : public Err {public: UnexpectedEndErr() : Err(INVALID_DATA_FORMAT, "Inflator: unexpected end of compressed block") {}};
0105     /// \brief Exception thrown when a bad block is encountered

0106     class BadBlockErr : public Err {public: BadBlockErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in compressed block") {}};
0107     /// \brief Exception thrown when an invalid distance is encountered

0108     class BadDistanceErr : public Err {public: BadDistanceErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in bit distance") {}};
0109
0110     /// \brief RFC 1951 Decompressor

0111     /// \param attachment the filter's attached transformation

0112     /// \param repeat decompress multiple compressed streams in series

0113     /// \param autoSignalPropagation 0 to turn off MessageEnd signal

0114     Inflator(BufferedTransformation *attachment = NULLPTR, bool repeat = false, int autoSignalPropagation = -1);
0115
0116     void IsolatedInitialize(const NameValuePairs &parameters);
0117     size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking);
0118     bool IsolatedFlush(bool hardFlush, bool blocking);
0119
0120     virtual unsigned int GetLog2WindowSize() const {return 15;}
0121
0122 protected:
0123     ByteQueue m_inQueue;
0124
0125 private:
0126     virtual unsigned int MaxPrestreamHeaderSize() const {return 0;}
0127     virtual void ProcessPrestreamHeader() {}
0128     virtual void ProcessDecompressedData(const byte *string, size_t length)
0129         {AttachedTransformation()->Put(string, length);}
0130     virtual unsigned int MaxPoststreamTailSize() const {return 0;}
0131     virtual void ProcessPoststreamTail() {}
0132
0133     void ProcessInput(bool flush);
0134     void DecodeHeader();
0135     bool DecodeBody();
0136     void FlushOutput();
0137     void OutputByte(byte b);
0138     void OutputString(const byte *string, size_t length);
0139     void OutputPast(unsigned int length, unsigned int distance);
0140
0141     void CreateFixedDistanceDecoder();
0142     void CreateFixedLiteralDecoder();
0143
0144     const HuffmanDecoder& GetLiteralDecoder();
0145     const HuffmanDecoder& GetDistanceDecoder();
0146
0147     enum State {PRE_STREAM, WAIT_HEADER, DECODING_BODY, POST_STREAM, AFTER_END};
0148     State m_state;
0149     bool m_repeat, m_eof, m_wrappedAround;
0150     byte m_blockType;
0151     word16 m_storedLen;
0152     enum NextDecode {LITERAL, LENGTH_BITS, DISTANCE, DISTANCE_BITS};
0153     NextDecode m_nextDecode;
0154     unsigned int m_literal, m_distance; // for LENGTH_BITS or DISTANCE_BITS

0155     HuffmanDecoder m_dynamicLiteralDecoder, m_dynamicDistanceDecoder;
0156     member_ptr<HuffmanDecoder> m_fixedLiteralDecoder, m_fixedDistanceDecoder;
0157     LowFirstBitReader m_reader;
0158     SecByteBlock m_window;
0159     size_t m_current, m_lastFlush;
0160 };
0161
0162 NAMESPACE_END
0163
0164 #endif