1 // 2 // Copyright (c) 2016-2019 Vinnie Falco (vinnie dot falco at gmail dot com) 3 // 4 // Distributed under the Boost Software License, Version 1.0. (See accompanying 5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 // 7 // Official repository: https://github.com/boostorg/beast 8 // 9 // This is a derivative work based on Zlib, copyright below: 10 /* 11 Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler 12 13 This software is provided 'as-is', without any express or implied 14 warranty. In no event will the authors be held liable for any damages 15 arising from the use of this software. 16 17 Permission is granted to anyone to use this software for any purpose, 18 including commercial applications, and to alter it and redistribute it 19 freely, subject to the following restrictions: 20 21 1. The origin of this software must not be misrepresented; you must not 22 claim that you wrote the original software. If you use this software 23 in a product, an acknowledgment in the product documentation would be 24 appreciated but is not required. 25 2. Altered source versions must be plainly marked as such, and must not be 26 misrepresented as being the original software. 27 3. This notice may not be removed or altered from any source distribution. 28 29 Jean-loup Gailly Mark Adler 30 jloup@gzip.org madler@alumni.caltech.edu 31 32 The data format used by the zlib library is described by RFCs (Request for 33 Comments) 1950 to 1952 in the files http://tools.ietf.org/html/rfc1950 34 (zlib format), rfc1951 (deflate format) and rfc1952 (gzip format). 35 */ 36 37 #ifndef BOOST_BEAST_ZLIB_DETAIL_INFLATE_STREAM_HPP 38 #define BOOST_BEAST_ZLIB_DETAIL_INFLATE_STREAM_HPP 39 40 #include <boost/beast/zlib/error.hpp> 41 #include <boost/beast/zlib/zlib.hpp> 42 #include <boost/beast/zlib/detail/bitstream.hpp> 43 #include <boost/beast/zlib/detail/ranges.hpp> 44 #include <boost/beast/zlib/detail/window.hpp> 45 #if 0 46 #include <boost/beast/core/detail/type_traits.hpp> 47 #include <boost/throw_exception.hpp> 48 #include <algorithm> 49 #include <array> 50 #include <cstdint> 51 #include <cstring> 52 #include <stdexcept> 53 #endif 54 55 namespace boost { 56 namespace beast { 57 namespace zlib { 58 namespace detail { 59 60 class inflate_stream 61 { 62 protected: inflate_stream()63 inflate_stream() 64 { 65 w_.reset(15); 66 } 67 68 BOOST_BEAST_DECL 69 void 70 doClear(); 71 72 BOOST_BEAST_DECL 73 void 74 doReset(int windowBits); 75 76 BOOST_BEAST_DECL 77 void 78 doWrite(z_params& zs, Flush flush, error_code& ec); 79 80 void doReset()81 doReset() 82 { 83 doReset(w_.bits()); 84 } 85 86 private: 87 enum Mode 88 { 89 HEAD, // i: waiting for magic header 90 FLAGS, // i: waiting for method and flags (gzip) 91 TIME, // i: waiting for modification time (gzip) 92 OS, // i: waiting for extra flags and operating system (gzip) 93 EXLEN, // i: waiting for extra length (gzip) 94 EXTRA, // i: waiting for extra bytes (gzip) 95 NAME, // i: waiting for end of file name (gzip) 96 COMMENT, // i: waiting for end of comment (gzip) 97 HCRC, // i: waiting for header crc (gzip) 98 TYPE, // i: waiting for type bits, including last-flag bit 99 TYPEDO, // i: same, but skip check to exit inflate on new block 100 STORED, // i: waiting for stored size (length and complement) 101 COPY_, // i/o: same as COPY below, but only first time in 102 COPY, // i/o: waiting for input or output to copy stored block 103 TABLE, // i: waiting for dynamic block table lengths 104 LENLENS, // i: waiting for code length code lengths 105 CODELENS, // i: waiting for length/lit and distance code lengths 106 LEN_, // i: same as LEN below, but only first time in 107 LEN, // i: waiting for length/lit/eob code 108 LENEXT, // i: waiting for length extra bits 109 DIST, // i: waiting for distance code 110 DISTEXT,// i: waiting for distance extra bits 111 MATCH, // o: waiting for output space to copy string 112 LIT, // o: waiting for output space to write literal 113 CHECK, // i: waiting for 32-bit check value 114 LENGTH, // i: waiting for 32-bit length (gzip) 115 DONE, // finished check, done -- remain here until reset 116 BAD, // got a data error -- remain here until reset 117 SYNC // looking for synchronization bytes to restart inflate() 118 }; 119 120 /* Structure for decoding tables. Each entry provides either the 121 information needed to do the operation requested by the code that 122 indexed that table entry, or it provides a pointer to another 123 table that indexes more bits of the code. op indicates whether 124 the entry is a pointer to another table, a literal, a length or 125 distance, an end-of-block, or an invalid code. For a table 126 pointer, the low four bits of op is the number of index bits of 127 that table. For a length or distance, the low four bits of op 128 is the number of extra bits to get after the code. bits is 129 the number of bits in this code or part of the code to drop off 130 of the bit buffer. val is the actual byte to output in the case 131 of a literal, the base length or distance, or the offset from 132 the current table to the next table. Each entry is four bytes. 133 134 op values as set by inflate_table(): 135 136 00000000 - literal 137 0000tttt - table link, tttt != 0 is the number of table index bits 138 0001eeee - length or distance, eeee is the number of extra bits 139 01100000 - end of block 140 01000000 - invalid code 141 */ 142 struct code 143 { 144 std::uint8_t op; // operation, extra bits, table bits 145 std::uint8_t bits; // bits in this part of the code 146 std::uint16_t val; // offset in table or code value 147 }; 148 149 /* Maximum size of the dynamic table. The maximum number of code 150 structures is 1444, which is the sum of 852 for literal/length codes 151 and 592 for distance codes. These values were found by exhaustive 152 searches using the program examples/enough.c found in the zlib 153 distribtution. The arguments to that program are the number of 154 symbols, the initial root table size, and the maximum bit length 155 of a code. "enough 286 9 15" for literal/length codes returns 156 returns 852, and "enough 30 6 15" for distance codes returns 592. 157 The initial root table size (9 or 6) is found in the fifth argument 158 of the inflate_table() calls in inflate.c and infback.c. If the 159 root table size is changed, then these maximum sizes would be need 160 to be recalculated and updated. 161 */ 162 static std::uint16_t constexpr kEnoughLens = 852; 163 static std::uint16_t constexpr kEnoughDists = 592; 164 static std::uint16_t constexpr kEnough = kEnoughLens + kEnoughDists; 165 166 struct codes 167 { 168 code const* lencode; 169 code const* distcode; 170 unsigned lenbits; // VFALCO use std::uint8_t 171 unsigned distbits; 172 }; 173 174 // Type of code to build for inflate_table() 175 enum class build 176 { 177 codes, 178 lens, 179 dists 180 }; 181 182 BOOST_BEAST_DECL 183 static 184 void 185 inflate_table( 186 build type, 187 std::uint16_t* lens, 188 std::size_t codes, 189 code** table, 190 unsigned *bits, 191 std::uint16_t* work, 192 error_code& ec); 193 194 BOOST_BEAST_DECL 195 static 196 codes const& 197 get_fixed_tables(); 198 199 BOOST_BEAST_DECL 200 void 201 fixedTables(); 202 203 BOOST_BEAST_DECL 204 void 205 inflate_fast(ranges& r, error_code& ec); 206 207 bitstream bi_; 208 209 Mode mode_ = HEAD; // current inflate mode 210 int last_ = 0; // true if processing last block 211 unsigned dmax_ = 32768U; // zlib header max distance (INFLATE_STRICT) 212 213 // sliding window 214 window w_; 215 216 // for string and stored block copying 217 unsigned length_; // literal or length of data to copy 218 unsigned offset_; // distance back to copy string from 219 220 // for table and code decoding 221 unsigned extra_; // extra bits needed 222 223 // dynamic table building 224 unsigned ncode_; // number of code length code lengths 225 unsigned nlen_; // number of length code lengths 226 unsigned ndist_; // number of distance code lengths 227 unsigned have_; // number of code lengths in lens[] 228 unsigned short lens_[320]; // temporary storage for code lengths 229 unsigned short work_[288]; // work area for code table building 230 code codes_[kEnough]; // space for code tables 231 code *next_ = codes_; // next available space in codes[] 232 int back_ = -1; // bits back of last unprocessed length/lit 233 unsigned was_; // initial length of match 234 235 // fixed and dynamic code tables 236 code const* lencode_ = codes_ ; // starting table for length/literal codes 237 code const* distcode_ = codes_; // starting table for distance codes 238 unsigned lenbits_; // index bits for lencode 239 unsigned distbits_; // index bits for distcode 240 }; 241 242 } // detail 243 } // zlib 244 } // beast 245 } // boost 246 247 #ifdef BOOST_BEAST_HEADER_ONLY 248 #include <boost/beast/zlib/detail/inflate_stream.ipp> 249 #endif 250 251 #endif 252