2 // Copyright (c) 2013-2017 Vinnie Falco (vinnie dot falco at gmail dot com)
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)
7 // This is a derivative work based on Zlib, copyright below:
9 Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler
11 This software is provided 'as-is', without any express or implied
12 warranty. In no event will the authors be held liable for any damages
13 arising from the use of this software.
15 Permission is granted to anyone to use this software for any purpose,
16 including commercial applications, and to alter it and redistribute it
17 freely, subject to the following restrictions:
19 1. The origin of this software must not be misrepresented; you must not
20 claim that you wrote the original software. If you use this software
21 in a product, an acknowledgment in the product documentation would be
22 appreciated but is not required.
23 2. Altered source versions must be plainly marked as such, and must not be
24 misrepresented as being the original software.
25 3. This notice may not be removed or altered from any source distribution.
27 Jean-loup Gailly Mark Adler
28 jloup@gzip.org madler@alumni.caltech.edu
30 The data format used by the zlib library is described by RFCs (Request for
31 Comments) 1950 to 1952 in the files http://tools.ietf.org/html/rfc1950
32 (zlib format), rfc1951 (deflate format) and rfc1952 (gzip format).
35 #ifndef BEAST_ZLIB_DETAIL_INFLATE_STREAM_HPP
36 #define BEAST_ZLIB_DETAIL_INFLATE_STREAM_HPP
38 #include <beast/zlib/error.hpp>
39 #include <beast/zlib/zlib.hpp>
40 #include <beast/zlib/detail/bitstream.hpp>
41 #include <beast/zlib/detail/ranges.hpp>
42 #include <beast/zlib/detail/window.hpp>
43 #include <beast/core/detail/type_traits.hpp>
62 template<class = void> void doClear();
63 template<class = void> void doReset(int windowBits);
64 template<class = void> void doWrite(z_params& zs, Flush flush, error_code& ec);
75 HEAD, // i: waiting for magic header
76 FLAGS, // i: waiting for method and flags (gzip)
77 TIME, // i: waiting for modification time (gzip)
78 OS, // i: waiting for extra flags and operating system (gzip)
79 EXLEN, // i: waiting for extra length (gzip)
80 EXTRA, // i: waiting for extra bytes (gzip)
81 NAME, // i: waiting for end of file name (gzip)
82 COMMENT, // i: waiting for end of comment (gzip)
83 HCRC, // i: waiting for header crc (gzip)
84 TYPE, // i: waiting for type bits, including last-flag bit
85 TYPEDO, // i: same, but skip check to exit inflate on new block
86 STORED, // i: waiting for stored size (length and complement)
87 COPY_, // i/o: same as COPY below, but only first time in
88 COPY, // i/o: waiting for input or output to copy stored block
89 TABLE, // i: waiting for dynamic block table lengths
90 LENLENS, // i: waiting for code length code lengths
91 CODELENS, // i: waiting for length/lit and distance code lengths
92 LEN_, // i: same as LEN below, but only first time in
93 LEN, // i: waiting for length/lit/eob code
94 LENEXT, // i: waiting for length extra bits
95 DIST, // i: waiting for distance code
96 DISTEXT,// i: waiting for distance extra bits
97 MATCH, // o: waiting for output space to copy string
98 LIT, // o: waiting for output space to write literal
99 CHECK, // i: waiting for 32-bit check value
100 LENGTH, // i: waiting for 32-bit length (gzip)
101 DONE, // finished check, done -- remain here until reset
102 BAD, // got a data error -- remain here until reset
103 SYNC // looking for synchronization bytes to restart inflate()
106 /* Structure for decoding tables. Each entry provides either the
107 information needed to do the operation requested by the code that
108 indexed that table entry, or it provides a pointer to another
109 table that indexes more bits of the code. op indicates whether
110 the entry is a pointer to another table, a literal, a length or
111 distance, an end-of-block, or an invalid code. For a table
112 pointer, the low four bits of op is the number of index bits of
113 that table. For a length or distance, the low four bits of op
114 is the number of extra bits to get after the code. bits is
115 the number of bits in this code or part of the code to drop off
116 of the bit buffer. val is the actual byte to output in the case
117 of a literal, the base length or distance, or the offset from
118 the current table to the next table. Each entry is four bytes.
120 op values as set by inflate_table():
123 0000tttt - table link, tttt != 0 is the number of table index bits
124 0001eeee - length or distance, eeee is the number of extra bits
125 01100000 - end of block
126 01000000 - invalid code
130 std::uint8_t op; // operation, extra bits, table bits
131 std::uint8_t bits; // bits in this part of the code
132 std::uint16_t val; // offset in table or code value
135 /* Maximum size of the dynamic table. The maximum number of code
136 structures is 1444, which is the sum of 852 for literal/length codes
137 and 592 for distance codes. These values were found by exhaustive
138 searches using the program examples/enough.c found in the zlib
139 distribtution. The arguments to that program are the number of
140 symbols, the initial root table size, and the maximum bit length
141 of a code. "enough 286 9 15" for literal/length codes returns
142 returns 852, and "enough 30 6 15" for distance codes returns 592.
143 The initial root table size (9 or 6) is found in the fifth argument
144 of the inflate_table() calls in inflate.c and infback.c. If the
145 root table size is changed, then these maximum sizes would be need
146 to be recalculated and updated.
148 static std::uint16_t constexpr kEnoughLens = 852;
149 static std::uint16_t constexpr kEnoughDists = 592;
150 static std::uint16_t constexpr kEnough = kEnoughLens + kEnoughDists;
155 code const* distcode;
156 unsigned lenbits; // VFALCO use std::uint8_t
160 // Type of code to build for inflate_table()
168 template<class = void>
180 template<class = void>
185 template<class = void>
189 template<class = void>
191 inflate_fast(ranges& r, error_code& ec);
195 Mode mode_ = HEAD; // current inflate mode
196 int last_ = 0; // true if processing last block
197 unsigned dmax_ = 32768U; // zlib header max distance (INFLATE_STRICT)
202 // for string and stored block copying
203 unsigned length_; // literal or length of data to copy
204 unsigned offset_; // distance back to copy string from
206 // for table and code decoding
207 unsigned extra_; // extra bits needed
209 // dynamic table building
210 unsigned ncode_; // number of code length code lengths
211 unsigned nlen_; // number of length code lengths
212 unsigned ndist_; // number of distance code lengths
213 unsigned have_; // number of code lengths in lens[]
214 unsigned short lens_[320]; // temporary storage for code lengths
215 unsigned short work_[288]; // work area for code table building
216 code codes_[kEnough]; // space for code tables
217 code *next_ = codes_; // next available space in codes[]
218 int back_ = -1; // bits back of last unprocessed length/lit
219 unsigned was_; // initial length of match
221 // fixed and dynamic code tables
222 code const* lencode_ = codes_ ; // starting table for length/literal codes
223 code const* distcode_ = codes_; // starting table for distance codes
224 unsigned lenbits_; // index bits for lencode
225 unsigned distbits_; // index bits for distcode
228 //------------------------------------------------------------------------------
233 doReset(int windowBits)
235 if(windowBits < 8 || windowBits > 15)
236 throw beast::detail::make_exception<std::domain_error>(
237 "windowBits out of range", __FILE__, __LINE__);
238 w_.reset(windowBits);
260 doWrite(z_params& zs, Flush flush, error_code& ec)
263 r.in.first = reinterpret_cast<
264 std::uint8_t const*>(zs.next_in);
265 r.in.last = r.in.first + zs.avail_in;
266 r.in.next = r.in.first;
267 r.out.first = reinterpret_cast<
268 std::uint8_t*>(zs.next_out);
269 r.out.last = r.out.first + zs.avail_out;
270 r.out.next = r.out.first;
276 Return from inflate(), updating the total counts and the check value.
277 If there was no progress during the inflate() call, return a buffer
278 error. Call updatewindow() to create and/or update the window state.
279 Note: a memory error from inflate() is non-recoverable.
283 // VFALCO TODO Don't allocate update the window unless necessary
284 if(/*wsize_ ||*/ (r.out.used() && mode_ < BAD &&
285 (mode_ < CHECK || flush != Flush::finish)))
286 w_.write(r.out.first, r.out.used());
288 zs.next_in = r.in.next;
289 zs.avail_in = r.in.avail();
290 zs.next_out = r.out.next;
291 zs.avail_out = r.out.avail();
292 zs.total_in += r.in.used();
293 zs.total_out += r.out.used();
294 zs.data_type = bi_.size() + (last_ ? 64 : 0) +
295 (mode_ == TYPE ? 128 : 0) +
296 (mode_ == LEN_ || mode_ == COPY_ ? 256 : 0);
298 if(((! r.in.used() && ! r.out.used()) ||
299 flush == Flush::finish) && ! ec)
300 ec = error::need_buffers;
321 if(flush == Flush::block || flush == Flush::trees)
333 if(! bi_.fill(3, r.in.next, r.in.last))
342 // uncompressed block
346 // fixed Huffman table
348 mode_ = LEN_; /* decode codes */
349 if(flush == Flush::trees)
353 // dynamic Huffman table
358 return err(error::invalid_block_type);
367 if(! bi_.fill(32, r.in.next, r.in.last))
370 length_ = v & 0xffff;
371 if(length_ != ((v >> 16) ^ 0xffff))
372 return err(error::invalid_stored_length);
373 // flush instead of read, otherwise
374 // undefined right shift behavior.
377 if(flush == Flush::trees)
394 copy = clamp(copy, r.in.avail());
395 copy = clamp(copy, r.out.avail());
398 std::memcpy(r.out.next, r.in.next, copy);
406 if(! bi_.fill(5 + 5 + 4, r.in.next, r.in.last))
414 if(nlen_ > 286 || ndist_ > 30)
415 return err(error::too_many_symbols);
422 static std::array<std::uint8_t, 19> constexpr order = {{
423 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}};
424 while(have_ < ncode_)
426 if(! bi_.fill(3, r.in.next, r.in.last))
428 bi_.read(lens_[order[have_]], 3);
431 while(have_ < order.size())
432 lens_[order[have_++]] = 0;
437 inflate_table(build::codes, &lens_[0],
438 order.size(), &next_, &lenbits_, work_, ec);
451 while(have_ < nlen_ + ndist_)
454 if(! bi_.fill(lenbits_, r.in.next, r.in.last))
456 bi_.peek(v, lenbits_);
457 auto cp = &lencode_[v];
461 lens_[have_++] = cp->val;
469 if(! bi_.fill(cp->bits + 2, r.in.next, r.in.last))
473 return err(error::invalid_bit_length_repeat);
475 len = lens_[have_ - 1];
479 else if(cp->val == 17)
481 if(! bi_.fill(cp->bits + 3, r.in.next, r.in.last))
490 if(! bi_.fill(cp->bits + 7, r.in.next, r.in.last))
497 if(have_ + copy > nlen_ + ndist_)
498 return err(error::invalid_bit_length_repeat);
499 std::fill(&lens_[have_], &lens_[have_ + copy], len);
504 // handle error breaks in while
507 // check for end-of-block code (better have one)
509 return err(error::missing_eob);
510 /* build code tables -- note: do not change the lenbits or distbits
511 values here (9 and 6) without reading the comments in inftrees.hpp
512 concerning the kEnough constants, which depend on those values */
516 inflate_table(build::lens, &lens_[0],
517 nlen_, &next_, &lenbits_, work_, ec);
525 inflate_table(build::dists, lens_ + nlen_,
526 ndist_, &next_, &distbits_, work_, ec);
533 if(flush == Flush::trees)
544 if(r.in.avail() >= 6 && r.out.avail() >= 258)
556 if(! bi_.fill(lenbits_, r.in.next, r.in.last))
560 bi_.peek(v, lenbits_);
561 auto cp = &lencode_[v];
562 if(cp->op && (cp->op & 0xf0) == 0)
565 if(! bi_.fill(prev->bits + prev->op, r.in.next, r.in.last))
567 bi_.peek(v, prev->bits + prev->op);
568 cp = &lencode_[prev->val + (v >> prev->bits)];
569 bi_.drop(prev->bits + cp->bits);
570 back_ += prev->bits + cp->bits;
590 return err(error::invalid_literal_length);
591 extra_ = cp->op & 15;
599 if(! bi_.fill(extra_, r.in.next, r.in.last))
612 if(! bi_.fill(distbits_, r.in.next, r.in.last))
615 bi_.peek(v, distbits_);
616 auto cp = &distcode_[v];
617 if((cp->op & 0xf0) == 0)
620 if(! bi_.fill(prev->bits + prev->op, r.in.next, r.in.last))
622 bi_.peek(v, prev->bits + prev->op);
623 cp = &distcode_[prev->val + (v >> prev->bits)];
624 bi_.drop(prev->bits + cp->bits);
625 back_ += prev->bits + cp->bits;
633 return err(error::invalid_distance_code);
635 extra_ = cp->op & 15;
644 if(! bi_.fill(extra_, r.in.next, r.in.last))
650 #ifdef INFLATE_STRICT
652 return err(error::invalid_distance);
661 if(offset_ > r.out.used())
664 auto offset = static_cast<std::uint16_t>(
665 offset_ - r.out.used());
666 if(offset > w_.size())
667 return err(error::invalid_distance);
668 auto const n = clamp(clamp(
669 length_, offset), r.out.avail());
670 w_.read(r.out.next, offset, n);
677 auto in = r.out.next - offset_;
678 auto n = clamp(length_, r.out.avail());
681 *r.out.next++ = *in++;
692 auto const v = static_cast<std::uint8_t>(length_);
703 ec = error::end_of_stream;
711 throw beast::detail::make_exception<std::logic_error>(
712 "stream error", __FILE__, __LINE__);
717 //------------------------------------------------------------------------------
719 /* Build a set of tables to decode the provided canonical Huffman code.
720 The code lengths are lens[0..codes-1]. The result starts at *table,
721 whose indices are 0..2^bits-1. work is a writable array of at least
722 lens shorts, which is used as a work area. type is the type of code
723 to be generated, build::codes, build::lens, or build::dists. On
724 return, zero is success, -1 is an invalid code, and +1 means that
725 kEnough isn't enough. table on return points to the next available
726 entry's address. bits is the requested root table index bits, and
727 on return it is the actual root table index bits. It will differ if
728 the request is greater than the longest code or if it is less than
743 unsigned len; // a code's length in bits
744 unsigned sym; // index of code symbols
745 unsigned min, max; // minimum and maximum code lengths
746 unsigned root; // number of index bits for root table
747 unsigned curr; // number of index bits for current table
748 unsigned drop; // code bits to drop for sub-table
749 int left; // number of prefix codes available
750 unsigned used; // code entries in table used
751 unsigned huff; // Huffman code
752 unsigned incr; // for incrementing code, index
753 unsigned fill; // index for replicating entries
754 unsigned low; // low bits for current root entry
755 unsigned mask; // mask for low root bits
756 code here; // table entry for duplication
757 code *next; // next available space in table
758 std::uint16_t const* base; // base value table to use
759 std::uint16_t const* extra; // extra bits table to use
760 int end; // use base and extra for symbol > end
761 std::uint16_t count[15+1]; // number of codes of each length
762 std::uint16_t offs[15+1]; // offsets in table for each length
764 // Length codes 257..285 base
765 static std::uint16_t constexpr lbase[31] = {
766 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
767 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
769 // Length codes 257..285 extra
770 static std::uint16_t constexpr lext[31] = {
771 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
772 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 72, 78};
774 // Distance codes 0..29 base
775 static std::uint16_t constexpr dbase[32] = {
776 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
777 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
778 8193, 12289, 16385, 24577, 0, 0};
780 // Distance codes 0..29 extra
781 static std::uint16_t constexpr dext[32] = {
782 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
783 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
784 28, 28, 29, 29, 64, 64};
787 Process a set of code lengths to create a canonical Huffman code. The
788 code lengths are lens[0..codes-1]. Each length corresponds to the
789 symbols 0..codes-1. The Huffman code is generated by first sorting the
790 symbols by length from short to long, and retaining the symbol order
791 for codes with equal lengths. Then the code starts with all zero bits
792 for the first code of the shortest length, and the codes are integer
793 increments for the same length, and zeros are appended as the length
794 increases. For the deflate format, these bits are stored backwards
795 from their more natural integer increment ordering, and so when the
796 decoding tables are built in the large loop below, the integer codes
797 are incremented backwards.
799 This routine assumes, but does not check, that all of the entries in
800 lens[] are in the range 0..15. The caller must assure this.
801 1..15 is interpreted as that code length. zero means that that
802 symbol does not occur in this code.
804 The codes are sorted by computing a count of codes for each length,
805 creating from that a table of starting indices for each length in the
806 sorted table, and then entering the symbols in order in the sorted
807 table. The sorted table is work[], with that space being provided by
810 The length counts are used for other purposes as well, i.e. finding
811 the minimum and maximum length codes, determining if there are any
812 codes at all, checking for a valid set of lengths, and looking ahead
813 at length counts to determine sub-table sizes when building the
817 /* accumulate lengths for codes (assumes lens[] all in 0..15) */
818 for (len = 0; len <= 15; len++)
820 for (sym = 0; sym < codes; sym++)
823 /* bound code lengths, force root to be within code lengths */
825 for (max = 15; max >= 1; max--)
831 { /* no symbols to code at all */
832 here.op = (std::uint8_t)64; /* invalid code marker */
833 here.bits = (std::uint8_t)1;
834 here.val = (std::uint16_t)0;
835 *(*table)++ = here; /* make a table to force an error */
838 return; /* no symbols, but wait for decoding to report error */
840 for (min = 1; min < max; min++)
846 /* check for an over-subscribed or incomplete set of lengths */
848 for (len = 1; len <= 15; len++)
854 ec = error::over_subscribed_length;
858 if (left > 0 && (type == build::codes || max != 1))
860 ec = error::incomplete_length_set;
864 /* generate offsets into symbol table for each length for sorting */
866 for (len = 1; len < 15; len++)
867 offs[len + 1] = offs[len] + count[len];
869 /* sort symbols by length, by symbol order within each length */
870 for (sym = 0; sym < codes; sym++)
872 work[offs[lens[sym]]++] = (std::uint16_t)sym;
875 Create and fill in decoding tables. In this loop, the table being
876 filled is at next and has curr index bits. The code being used is huff
877 with length len. That code is converted to an index by dropping drop
878 bits off of the bottom. For codes where len is less than drop + curr,
879 those top drop + curr - len bits are incremented through all values to
880 fill the table with replicated entries.
882 root is the number of index bits for the root table. When len exceeds
883 root, sub-tables are created pointed to by the root entry with an index
884 of the low root bits of huff. This is saved in low to check for when a
885 new sub-table should be started. drop is zero when the root table is
886 being filled, and drop is root when sub-tables are being filled.
888 When a new sub-table is needed, it is necessary to look ahead in the
889 code lengths to determine what size sub-table is needed. The length
890 counts are used for this, and so count[] is decremented as codes are
891 entered in the tables.
893 used keeps track of how many table entries have been allocated from the
894 provided *table space. It is checked for build::lens and DIST tables against
895 the constants kEnoughLens and kEnoughDists to guard against changes in
896 the initial root table size constants. See the comments in inftrees.hpp
897 for more information.
899 sym increments through all symbols, and the loop terminates when
900 all codes of length max, i.e. all codes, have been processed. This
901 routine permits incomplete codes, so another loop after this one fills
902 in the rest of the decoding tables with invalid code markers.
905 /* set up for code type */
909 base = extra = work; /* dummy value--not used */
919 default: /* build::dists */
925 /* initialize state for loop */
926 huff = 0; /* starting code */
927 sym = 0; /* starting code symbol */
928 len = min; /* starting code length */
929 next = *table; /* current table to fill in */
930 curr = root; /* current table index bits */
931 drop = 0; /* current bits to drop from code for index */
932 low = (unsigned)(-1); /* trigger new sub-table when len > root */
933 used = 1U << root; /* use root table entries */
934 mask = used - 1; /* mask for comparing low */
936 auto const not_enough = []
938 throw beast::detail::make_exception<std::logic_error>(
939 "insufficient output size when inflating tables", __FILE__, __LINE__);
942 // check available table space
943 if ((type == build::lens && used > kEnoughLens) ||
944 (type == build::dists && used > kEnoughDists))
947 /* process all codes and make table entries */
950 /* create table entry */
951 here.bits = (std::uint8_t)(len - drop);
952 if ((int)(work[sym]) < end)
954 here.op = (std::uint8_t)0;
955 here.val = work[sym];
957 else if ((int)(work[sym]) > end)
959 here.op = (std::uint8_t)(extra[work[sym]]);
960 here.val = base[work[sym]];
964 here.op = (std::uint8_t)(32 + 64); /* end of block */
968 /* replicate for those indices with low len bits equal to huff */
969 incr = 1U << (len - drop);
971 min = fill; /* save offset to next table */
975 next[(huff >> drop) + fill] = here;
978 /* backwards increment the len-bit code huff */
979 incr = 1U << (len - 1);
990 /* go to next symbol, update count, len */
992 if (--(count[len]) == 0)
994 if (len == max) break;
995 len = lens[work[sym]];
998 /* create new sub-table if needed */
999 if (len > root && (huff & mask) != low)
1001 /* if first time, transition to sub-tables */
1005 /* increment past last table */
1006 next += min; /* here min is 1 << curr */
1008 /* determine length of next table */
1010 left = (int)(1 << curr);
1011 while (curr + drop < max)
1013 left -= count[curr + drop];
1014 if (left <= 0) break;
1019 /* check for enough space */
1021 if ((type == build::lens && used > kEnoughLens) ||
1022 (type == build::dists && used > kEnoughDists))
1023 return not_enough();
1025 /* point entry in root table to sub-table */
1027 (*table)[low].op = (std::uint8_t)curr;
1028 (*table)[low].bits = (std::uint8_t)root;
1029 (*table)[low].val = (std::uint16_t)(next - *table);
1033 /* fill in remaining table entry if code is incomplete (guaranteed to have
1034 at most one remaining entry, since if the code is incomplete, the
1035 maximum code length that was allowed to get this far is one bit) */
1038 here.op = 64; // invalid code marker
1039 here.bits = (std::uint8_t)(len - drop);
1051 get_fixed_tables() ->
1054 struct fixed_codes : codes
1066 std::uint16_t lens[320];
1067 std::uint16_t work[288];
1069 std::fill(&lens[ 0], &lens[144], 8);
1070 std::fill(&lens[144], &lens[256], 9);
1071 std::fill(&lens[256], &lens[280], 7);
1072 std::fill(&lens[280], &lens[288], 8);
1076 auto next = &len_[0];
1077 inflate_table(build::lens,
1078 lens, 288, &next, &lenbits, work, ec);
1080 throw std::logic_error{ec.message()};
1083 // VFALCO These fixups are from ZLib
1091 auto next = &dist_[0];
1092 std::fill(&lens[0], &lens[32], 5);
1093 inflate_table(build::dists,
1094 lens, 32, &next, &distbits, work, ec);
1096 throw std::logic_error{ec.message()};
1101 static fixed_codes const fc;
1110 auto const fc = get_fixed_tables();
1111 lencode_ = fc.lencode;
1112 lenbits_ = fc.lenbits;
1113 distcode_ = fc.distcode;
1114 distbits_ = fc.distbits;
1118 Decode literal, length, and distance codes and write out the resulting
1119 literal and match bytes until either not enough input or output is
1120 available, an end-of-block is encountered, or a data error is encountered.
1121 When large enough input and output buffers are supplied to inflate(), for
1122 example, a 16K input buffer and a 64K output buffer, more than 95% of the
1123 inflate execution time is spent in this routine.
1130 start >= zs.avail_out
1133 On return, state->mode_ is one of:
1135 LEN -- ran out of enough output space or enough available input
1136 TYPE -- reached end of block code, inflate() to interpret next block
1137 BAD -- error in block data
1141 - The maximum input bits used by a length/distance pair is 15 bits for the
1142 length code, 5 bits for the length extra, 15 bits for the distance code,
1143 and 13 bits for the distance extra. This totals 48 bits, or six bytes.
1144 Therefore if zs.avail_in >= 6, then there is enough input to avoid
1145 checking for available input while decoding.
1147 - The maximum bytes that a single length/distance pair can output is 258
1148 bytes, which is the maximum length that can be coded. inflate_fast()
1149 requires zs.avail_out >= 258 for each loop to avoid checking for
1152 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
1153 - Using bit fields for code structure
1154 - Different op definition to avoid & for extra bits (do & for table bits)
1155 - Three separate decoding do-loops for direct, window, and wnext == 0
1156 - Special case for distance > 1 copies to do overlapped load and store copy
1157 - Explicit branch predictions (based on measured branch probabilities)
1158 - Deferring match copy and interspersed it with decoding subsequent codes
1159 - Swapping literal/length else
1160 - Swapping window/direct else
1161 - Larger unrolled copy loops (three is about right)
1162 - Moving len -= 3 statement into middle of loop
1167 inflate_fast(ranges& r, error_code& ec)
1169 unsigned char const* last; // have enough input while in < last
1170 unsigned char *end; // while out < end, enough space available
1171 std::size_t op; // code bits, operation, extra bits, or window position, window bytes to copy
1172 unsigned len; // match length, unused bytes
1173 unsigned dist; // match distance
1174 unsigned const lmask =
1175 (1U << lenbits_) - 1; // mask for first level of length codes
1176 unsigned const dmask =
1177 (1U << distbits_) - 1; // mask for first level of distance codes
1179 last = r.in.next + (r.in.avail() - 5);
1180 end = r.out.next + (r.out.avail() - 257);
1182 /* decode literals and length/distances until end-of-block or not enough
1183 input data or output space */
1187 bi_.fill_16(r.in.next);
1188 auto cp = &lencode_[bi_.peek_fast() & lmask];
1191 op = (unsigned)(cp->op);
1195 *r.out.next++ = (unsigned char)(cp->val);
1200 len = (unsigned)(cp->val);
1201 op &= 15; // number of extra bits
1205 bi_.fill_8(r.in.next);
1206 len += (unsigned)bi_.peek_fast() & ((1U << op) - 1);
1210 bi_.fill_16(r.in.next);
1211 cp = &distcode_[bi_.peek_fast() & dmask];
1214 op = (unsigned)(cp->op);
1218 dist = (unsigned)(cp->val);
1219 op &= 15; // number of extra bits
1222 bi_.fill_8(r.in.next);
1224 bi_.fill_8(r.in.next);
1226 dist += (unsigned)bi_.peek_fast() & ((1U << op) - 1);
1227 #ifdef INFLATE_STRICT
1230 ec = error::invalid_distance;
1241 op = dist - op; // distance back in window
1244 ec = error::invalid_distance;
1248 auto const n = clamp(len, op);
1249 w_.read(r.out.next, op, n);
1256 auto in = r.out.next - dist;
1257 auto n = clamp(len, r.out.avail());
1260 *r.out.next++ = *in++;
1263 else if((op & 64) == 0)
1265 // 2nd level distance code
1266 cp = &distcode_[cp->val + (bi_.peek_fast() & ((1U << op) - 1))];
1271 ec = error::invalid_distance_code;
1276 else if((op & 64) == 0)
1278 // 2nd level length code
1279 cp = &lencode_[cp->val + (bi_.peek_fast() & ((1U << op) - 1))];
1290 ec = error::invalid_literal_length;
1295 while(r.in.next < last && r.out.next < end);
1297 // return unused bytes (on entry, bits < 8, so in won't go too far back)
1298 bi_.rewind(r.in.next);