1 // zinflate.h - originally written and placed in the public domain by Wei Dai
2
3 /// \file zinflate.h
4 /// \brief DEFLATE compression and decompression (RFC 1951)
5
6 #ifndef CRYPTOPP_ZINFLATE_H
7 #define CRYPTOPP_ZINFLATE_H
8
9 #include "cryptlib.h"
10 #include "secblock.h"
11 #include "filters.h"
12 #include "stdcpp.h"
13
NAMESPACE_BEGIN(CryptoPP)14 NAMESPACE_BEGIN(CryptoPP)
15
16 /// \since Crypto++ 1.0
17 class LowFirstBitReader
18 {
19 public:
20 LowFirstBitReader(BufferedTransformation &store)
21 : m_store(store), m_buffer(0), m_bitsBuffered(0) {}
22 unsigned int BitsBuffered() const {return m_bitsBuffered;}
23 unsigned long PeekBuffer() const {return m_buffer;}
24 bool FillBuffer(unsigned int length);
25 unsigned long PeekBits(unsigned int length);
26 void SkipBits(unsigned int length);
27 unsigned long GetBits(unsigned int length);
28
29 private:
30 BufferedTransformation &m_store;
31 unsigned long m_buffer;
32 unsigned int m_bitsBuffered;
33 };
34
35 struct CodeLessThan;
36
37 /// \brief Huffman Decoder
38 /// \since Crypto++ 1.0
39 class HuffmanDecoder
40 {
41 public:
42 typedef unsigned int code_t;
43 typedef unsigned int value_t;
44 enum {MAX_CODE_BITS = sizeof(code_t)*8};
45
Err(const std::string & what)46 class Err : public Exception {public: Err(const std::string &what) : Exception(INVALID_DATA_FORMAT, "HuffmanDecoder: " + what) {}};
47
HuffmanDecoder()48 HuffmanDecoder() : m_maxCodeBits(0), m_cacheBits(0), m_cacheMask(0), m_normalizedCacheMask(0) {}
HuffmanDecoder(const unsigned int * codeBitLengths,unsigned int nCodes)49 HuffmanDecoder(const unsigned int *codeBitLengths, unsigned int nCodes)
50 : m_maxCodeBits(0), m_cacheBits(0), m_cacheMask(0), m_normalizedCacheMask(0)
51 {Initialize(codeBitLengths, nCodes);}
52
53 void Initialize(const unsigned int *codeBitLengths, unsigned int nCodes);
54 unsigned int Decode(code_t code, /* out */ value_t &value) const;
55 bool Decode(LowFirstBitReader &reader, value_t &value) const;
56
57 private:
58 friend struct CodeLessThan;
59
60 struct CodeInfo
61 {
codeCodeInfo62 CodeInfo(code_t code=0, unsigned int len=0, value_t value=0) : code(code), len(len), value(value) {}
63 inline bool operator<(const CodeInfo &rhs) const {return code < rhs.code;}
64 code_t code;
65 unsigned int len;
66 value_t value;
67 };
68
69 struct LookupEntry
70 {
71 unsigned int type;
72 union
73 {
74 value_t value;
75 const CodeInfo *begin;
76 };
77 union
78 {
79 unsigned int len;
80 const CodeInfo *end;
81 };
82 };
83
84 static code_t NormalizeCode(code_t code, unsigned int codeBits);
85 void FillCacheEntry(LookupEntry &entry, code_t normalizedCode) const;
86
87 unsigned int m_maxCodeBits, m_cacheBits, m_cacheMask, m_normalizedCacheMask;
88 std::vector<CodeInfo, AllocatorWithCleanup<CodeInfo> > m_codeToValue;
89 mutable std::vector<LookupEntry, AllocatorWithCleanup<LookupEntry> > m_cache;
90 };
91
92 /// \brief DEFLATE decompressor (RFC 1951)
93 /// \since Crypto++ 1.0
94 class Inflator : public AutoSignaling<Filter>
95 {
96 public:
97 class Err : public Exception
98 {
99 public:
Err(ErrorType e,const std::string & s)100 Err(ErrorType e, const std::string &s)
101 : Exception(e, s) {}
102 };
103 /// \brief Exception thrown when a truncated stream is encountered
UnexpectedEndErr()104 class UnexpectedEndErr : public Err {public: UnexpectedEndErr() : Err(INVALID_DATA_FORMAT, "Inflator: unexpected end of compressed block") {}};
105 /// \brief Exception thrown when a bad block is encountered
BadBlockErr()106 class BadBlockErr : public Err {public: BadBlockErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in compressed block") {}};
107 /// \brief Exception thrown when an invalid distance is encountered
BadDistanceErr()108 class BadDistanceErr : public Err {public: BadDistanceErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in bit distance") {}};
109
110 /// \brief RFC 1951 Decompressor
111 /// \param attachment the filter's attached transformation
112 /// \param repeat decompress multiple compressed streams in series
113 /// \param autoSignalPropagation 0 to turn off MessageEnd signal
114 Inflator(BufferedTransformation *attachment = NULLPTR, bool repeat = false, int autoSignalPropagation = -1);
115
116 void IsolatedInitialize(const NameValuePairs ¶meters);
117 size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking);
118 bool IsolatedFlush(bool hardFlush, bool blocking);
119
GetLog2WindowSize()120 virtual unsigned int GetLog2WindowSize() const {return 15;}
121
122 protected:
123 ByteQueue m_inQueue;
124
125 private:
MaxPrestreamHeaderSize()126 virtual unsigned int MaxPrestreamHeaderSize() const {return 0;}
ProcessPrestreamHeader()127 virtual void ProcessPrestreamHeader() {}
ProcessDecompressedData(const byte * string,size_t length)128 virtual void ProcessDecompressedData(const byte *string, size_t length)
129 {AttachedTransformation()->Put(string, length);}
MaxPoststreamTailSize()130 virtual unsigned int MaxPoststreamTailSize() const {return 0;}
ProcessPoststreamTail()131 virtual void ProcessPoststreamTail() {}
132
133 void ProcessInput(bool flush);
134 void DecodeHeader();
135 bool DecodeBody();
136 void FlushOutput();
137 void OutputByte(byte b);
138 void OutputString(const byte *string, size_t length);
139 void OutputPast(unsigned int length, unsigned int distance);
140
141 void CreateFixedDistanceDecoder();
142 void CreateFixedLiteralDecoder();
143
144 const HuffmanDecoder& GetLiteralDecoder();
145 const HuffmanDecoder& GetDistanceDecoder();
146
147 enum State {PRE_STREAM, WAIT_HEADER, DECODING_BODY, POST_STREAM, AFTER_END};
148 State m_state;
149 bool m_repeat, m_eof, m_wrappedAround;
150 byte m_blockType;
151 word16 m_storedLen;
152 enum NextDecode {LITERAL, LENGTH_BITS, DISTANCE, DISTANCE_BITS};
153 NextDecode m_nextDecode;
154 unsigned int m_literal, m_distance; // for LENGTH_BITS or DISTANCE_BITS
155 HuffmanDecoder m_dynamicLiteralDecoder, m_dynamicDistanceDecoder;
156 member_ptr<HuffmanDecoder> m_fixedLiteralDecoder, m_fixedDistanceDecoder;
157 LowFirstBitReader m_reader;
158 SecByteBlock m_window;
159 size_t m_current, m_lastFlush;
160 };
161
162 NAMESPACE_END
163
164 #endif
165