]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // |
2 | // Copyright (c) 2013-2017 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 | // This is a derivative work based on Zlib, copyright below: | |
8 | /* | |
9 | Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler | |
10 | ||
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. | |
14 | ||
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: | |
18 | ||
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. | |
26 | ||
27 | Jean-loup Gailly Mark Adler | |
28 | jloup@gzip.org madler@alumni.caltech.edu | |
29 | ||
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). | |
33 | */ | |
34 | ||
35 | #ifndef BEAST_ZLIB_DETAIL_INFLATE_STREAM_HPP | |
36 | #define BEAST_ZLIB_DETAIL_INFLATE_STREAM_HPP | |
37 | ||
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> | |
44 | #include <algorithm> | |
45 | #include <array> | |
46 | #include <cstdint> | |
47 | #include <cstring> | |
48 | #include <stdexcept> | |
49 | ||
50 | namespace beast { | |
51 | namespace zlib { | |
52 | namespace detail { | |
53 | ||
54 | class inflate_stream | |
55 | { | |
56 | protected: | |
57 | inflate_stream() | |
58 | { | |
59 | w_.reset(15); | |
60 | } | |
61 | ||
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); | |
65 | ||
66 | void | |
67 | doReset() | |
68 | { | |
69 | doReset(w_.bits()); | |
70 | } | |
71 | ||
72 | private: | |
73 | enum Mode | |
74 | { | |
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() | |
104 | }; | |
105 | ||
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. | |
119 | ||
120 | op values as set by inflate_table(): | |
121 | ||
122 | 00000000 - literal | |
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 | |
127 | */ | |
128 | struct code | |
129 | { | |
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 | |
133 | }; | |
134 | ||
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. | |
147 | */ | |
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; | |
151 | ||
152 | struct codes | |
153 | { | |
154 | code const* lencode; | |
155 | code const* distcode; | |
156 | unsigned lenbits; // VFALCO use std::uint8_t | |
157 | unsigned distbits; | |
158 | }; | |
159 | ||
160 | // Type of code to build for inflate_table() | |
161 | enum class build | |
162 | { | |
163 | codes, | |
164 | lens, | |
165 | dists | |
166 | }; | |
167 | ||
168 | template<class = void> | |
169 | static | |
170 | void | |
171 | inflate_table( | |
172 | build type, | |
173 | std::uint16_t* lens, | |
174 | std::size_t codes, | |
175 | code** table, | |
176 | unsigned *bits, | |
177 | std::uint16_t* work, | |
178 | error_code& ec); | |
179 | ||
180 | template<class = void> | |
181 | static | |
182 | codes const& | |
183 | get_fixed_tables(); | |
184 | ||
185 | template<class = void> | |
186 | void | |
187 | fixedTables(); | |
188 | ||
189 | template<class = void> | |
190 | void | |
191 | inflate_fast(ranges& r, error_code& ec); | |
192 | ||
193 | bitstream bi_; | |
194 | ||
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) | |
198 | ||
199 | // sliding window | |
200 | window w_; | |
201 | ||
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 | |
205 | ||
206 | // for table and code decoding | |
207 | unsigned extra_; // extra bits needed | |
208 | ||
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 | |
220 | ||
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 | |
226 | }; | |
227 | ||
228 | //------------------------------------------------------------------------------ | |
229 | ||
230 | template<class> | |
231 | void | |
232 | inflate_stream:: | |
233 | doReset(int windowBits) | |
234 | { | |
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); | |
239 | ||
240 | bi_.flush(); | |
241 | mode_ = HEAD; | |
242 | last_ = 0; | |
243 | dmax_ = 32768U; | |
244 | lencode_ = codes_; | |
245 | distcode_ = codes_; | |
246 | next_ = codes_; | |
247 | back_ = -1; | |
248 | } | |
249 | ||
250 | template<class> | |
251 | void | |
252 | inflate_stream:: | |
253 | doClear() | |
254 | { | |
255 | } | |
256 | ||
257 | template<class> | |
258 | void | |
259 | inflate_stream:: | |
260 | doWrite(z_params& zs, Flush flush, error_code& ec) | |
261 | { | |
262 | ranges r; | |
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; | |
271 | ||
272 | auto const done = | |
273 | [&] | |
274 | { | |
275 | /* | |
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. | |
280 | */ | |
281 | ||
282 | ||
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()); | |
287 | ||
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); | |
297 | ||
298 | if(((! r.in.used() && ! r.out.used()) || | |
299 | flush == Flush::finish) && ! ec) | |
300 | ec = error::need_buffers; | |
301 | }; | |
302 | auto const err = | |
303 | [&](error e) | |
304 | { | |
305 | ec = e; | |
306 | mode_ = BAD; | |
307 | }; | |
308 | ||
309 | if(mode_ == TYPE) | |
310 | mode_ = TYPEDO; | |
311 | ||
312 | for(;;) | |
313 | { | |
314 | switch(mode_) | |
315 | { | |
316 | case HEAD: | |
317 | mode_ = TYPEDO; | |
318 | break; | |
319 | ||
320 | case TYPE: | |
321 | if(flush == Flush::block || flush == Flush::trees) | |
322 | return done(); | |
323 | // fall through | |
324 | ||
325 | case TYPEDO: | |
326 | { | |
327 | if(last_) | |
328 | { | |
329 | bi_.flush_byte(); | |
330 | mode_ = CHECK; | |
331 | break; | |
332 | } | |
333 | if(! bi_.fill(3, r.in.next, r.in.last)) | |
334 | return done(); | |
335 | std::uint8_t v; | |
336 | bi_.read(v, 1); | |
337 | last_ = v != 0; | |
338 | bi_.read(v, 2); | |
339 | switch(v) | |
340 | { | |
341 | case 0: | |
342 | // uncompressed block | |
343 | mode_ = STORED; | |
344 | break; | |
345 | case 1: | |
346 | // fixed Huffman table | |
347 | fixedTables(); | |
348 | mode_ = LEN_; /* decode codes */ | |
349 | if(flush == Flush::trees) | |
350 | return done(); | |
351 | break; | |
352 | case 2: | |
353 | // dynamic Huffman table | |
354 | mode_ = TABLE; | |
355 | break; | |
356 | ||
357 | default: | |
358 | return err(error::invalid_block_type); | |
359 | } | |
360 | break; | |
361 | } | |
362 | ||
363 | case STORED: | |
364 | { | |
365 | bi_.flush_byte(); | |
366 | std::uint32_t v; | |
367 | if(! bi_.fill(32, r.in.next, r.in.last)) | |
368 | return done(); | |
369 | bi_.peek(v, 32); | |
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. | |
375 | bi_.flush(); | |
376 | mode_ = COPY_; | |
377 | if(flush == Flush::trees) | |
378 | return done(); | |
379 | // fall through | |
380 | } | |
381 | ||
382 | case COPY_: | |
383 | mode_ = COPY; | |
384 | // fall through | |
385 | ||
386 | case COPY: | |
387 | { | |
388 | auto copy = length_; | |
389 | if(copy == 0) | |
390 | { | |
391 | mode_ = TYPE; | |
392 | break; | |
393 | } | |
394 | copy = clamp(copy, r.in.avail()); | |
395 | copy = clamp(copy, r.out.avail()); | |
396 | if(copy == 0) | |
397 | return done(); | |
398 | std::memcpy(r.out.next, r.in.next, copy); | |
399 | r.in.next += copy; | |
400 | r.out.next += copy; | |
401 | length_ -= copy; | |
402 | break; | |
403 | } | |
404 | ||
405 | case TABLE: | |
406 | if(! bi_.fill(5 + 5 + 4, r.in.next, r.in.last)) | |
407 | return done(); | |
408 | bi_.read(nlen_, 5); | |
409 | nlen_ += 257; | |
410 | bi_.read(ndist_, 5); | |
411 | ndist_ += 1; | |
412 | bi_.read(ncode_, 4); | |
413 | ncode_ += 4; | |
414 | if(nlen_ > 286 || ndist_ > 30) | |
415 | return err(error::too_many_symbols); | |
416 | have_ = 0; | |
417 | mode_ = LENLENS; | |
418 | // fall through | |
419 | ||
420 | case LENLENS: | |
421 | { | |
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_) | |
425 | { | |
426 | if(! bi_.fill(3, r.in.next, r.in.last)) | |
427 | return done(); | |
428 | bi_.read(lens_[order[have_]], 3); | |
429 | ++have_; | |
430 | } | |
431 | while(have_ < order.size()) | |
432 | lens_[order[have_++]] = 0; | |
433 | ||
434 | next_ = &codes_[0]; | |
435 | lencode_ = next_; | |
436 | lenbits_ = 7; | |
437 | inflate_table(build::codes, &lens_[0], | |
438 | order.size(), &next_, &lenbits_, work_, ec); | |
439 | if(ec) | |
440 | { | |
441 | mode_ = BAD; | |
442 | break; | |
443 | } | |
444 | have_ = 0; | |
445 | mode_ = CODELENS; | |
446 | // fall through | |
447 | } | |
448 | ||
449 | case CODELENS: | |
450 | { | |
451 | while(have_ < nlen_ + ndist_) | |
452 | { | |
453 | std::uint16_t v; | |
454 | if(! bi_.fill(lenbits_, r.in.next, r.in.last)) | |
455 | return done(); | |
456 | bi_.peek(v, lenbits_); | |
457 | auto cp = &lencode_[v]; | |
458 | if(cp->val < 16) | |
459 | { | |
460 | bi_.drop(cp->bits); | |
461 | lens_[have_++] = cp->val; | |
462 | } | |
463 | else | |
464 | { | |
465 | std::uint16_t len; | |
466 | std::uint16_t copy; | |
467 | if(cp->val == 16) | |
468 | { | |
469 | if(! bi_.fill(cp->bits + 2, r.in.next, r.in.last)) | |
470 | return done(); | |
471 | bi_.drop(cp->bits); | |
472 | if(have_ == 0) | |
473 | return err(error::invalid_bit_length_repeat); | |
474 | bi_.read(copy, 2); | |
475 | len = lens_[have_ - 1]; | |
476 | copy += 3; | |
477 | ||
478 | } | |
479 | else if(cp->val == 17) | |
480 | { | |
481 | if(! bi_.fill(cp->bits + 3, r.in.next, r.in.last)) | |
482 | return done(); | |
483 | bi_.drop(cp->bits); | |
484 | bi_.read(copy, 3); | |
485 | len = 0; | |
486 | copy += 3; | |
487 | } | |
488 | else | |
489 | { | |
490 | if(! bi_.fill(cp->bits + 7, r.in.next, r.in.last)) | |
491 | return done(); | |
492 | bi_.drop(cp->bits); | |
493 | bi_.read(copy, 7); | |
494 | len = 0; | |
495 | copy += 11; | |
496 | } | |
497 | if(have_ + copy > nlen_ + ndist_) | |
498 | return err(error::invalid_bit_length_repeat); | |
499 | std::fill(&lens_[have_], &lens_[have_ + copy], len); | |
500 | have_ += copy; | |
501 | copy = 0; | |
502 | } | |
503 | } | |
504 | // handle error breaks in while | |
505 | if(mode_ == BAD) | |
506 | break; | |
507 | // check for end-of-block code (better have one) | |
508 | if(lens_[256] == 0) | |
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 */ | |
513 | next_ = &codes_[0]; | |
514 | lencode_ = next_; | |
515 | lenbits_ = 9; | |
516 | inflate_table(build::lens, &lens_[0], | |
517 | nlen_, &next_, &lenbits_, work_, ec); | |
518 | if(ec) | |
519 | { | |
520 | mode_ = BAD; | |
521 | return; | |
522 | } | |
523 | distcode_ = next_; | |
524 | distbits_ = 6; | |
525 | inflate_table(build::dists, lens_ + nlen_, | |
526 | ndist_, &next_, &distbits_, work_, ec); | |
527 | if(ec) | |
528 | { | |
529 | mode_ = BAD; | |
530 | return; | |
531 | } | |
532 | mode_ = LEN_; | |
533 | if(flush == Flush::trees) | |
534 | return done(); | |
535 | // fall through | |
536 | } | |
537 | ||
538 | case LEN_: | |
539 | mode_ = LEN; | |
540 | // fall through | |
541 | ||
542 | case LEN: | |
543 | { | |
544 | if(r.in.avail() >= 6 && r.out.avail() >= 258) | |
545 | { | |
546 | inflate_fast(r, ec); | |
547 | if(ec) | |
548 | { | |
549 | mode_ = BAD; | |
550 | return; | |
551 | } | |
552 | if(mode_ == TYPE) | |
553 | back_ = -1; | |
554 | break; | |
555 | } | |
556 | if(! bi_.fill(lenbits_, r.in.next, r.in.last)) | |
557 | return done(); | |
558 | std::uint16_t v; | |
559 | back_ = 0; | |
560 | bi_.peek(v, lenbits_); | |
561 | auto cp = &lencode_[v]; | |
562 | if(cp->op && (cp->op & 0xf0) == 0) | |
563 | { | |
564 | auto prev = cp; | |
565 | if(! bi_.fill(prev->bits + prev->op, r.in.next, r.in.last)) | |
566 | return done(); | |
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; | |
571 | } | |
572 | else | |
573 | { | |
574 | bi_.drop(cp->bits); | |
575 | back_ += cp->bits; | |
576 | } | |
577 | length_ = cp->val; | |
578 | if(cp->op == 0) | |
579 | { | |
580 | mode_ = LIT; | |
581 | break; | |
582 | } | |
583 | if(cp->op & 32) | |
584 | { | |
585 | back_ = -1; | |
586 | mode_ = TYPE; | |
587 | break; | |
588 | } | |
589 | if(cp->op & 64) | |
590 | return err(error::invalid_literal_length); | |
591 | extra_ = cp->op & 15; | |
592 | mode_ = LENEXT; | |
593 | // fall through | |
594 | } | |
595 | ||
596 | case LENEXT: | |
597 | if(extra_) | |
598 | { | |
599 | if(! bi_.fill(extra_, r.in.next, r.in.last)) | |
600 | return done(); | |
601 | std::uint16_t v; | |
602 | bi_.read(v, extra_); | |
603 | length_ += v; | |
604 | back_ += extra_; | |
605 | } | |
606 | was_ = length_; | |
607 | mode_ = DIST; | |
608 | // fall through | |
609 | ||
610 | case DIST: | |
611 | { | |
612 | if(! bi_.fill(distbits_, r.in.next, r.in.last)) | |
613 | return done(); | |
614 | std::uint16_t v; | |
615 | bi_.peek(v, distbits_); | |
616 | auto cp = &distcode_[v]; | |
617 | if((cp->op & 0xf0) == 0) | |
618 | { | |
619 | auto prev = cp; | |
620 | if(! bi_.fill(prev->bits + prev->op, r.in.next, r.in.last)) | |
621 | return done(); | |
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; | |
626 | } | |
627 | else | |
628 | { | |
629 | bi_.drop(cp->bits); | |
630 | back_ += cp->bits; | |
631 | } | |
632 | if(cp->op & 64) | |
633 | return err(error::invalid_distance_code); | |
634 | offset_ = cp->val; | |
635 | extra_ = cp->op & 15; | |
636 | mode_ = DISTEXT; | |
637 | // fall through | |
638 | } | |
639 | ||
640 | case DISTEXT: | |
641 | if(extra_) | |
642 | { | |
643 | std::uint16_t v; | |
644 | if(! bi_.fill(extra_, r.in.next, r.in.last)) | |
645 | return done(); | |
646 | bi_.read(v, extra_); | |
647 | offset_ += v; | |
648 | back_ += extra_; | |
649 | } | |
650 | #ifdef INFLATE_STRICT | |
651 | if(offset_ > dmax_) | |
652 | return err(error::invalid_distance); | |
653 | #endif | |
654 | mode_ = MATCH; | |
655 | // fall through | |
656 | ||
657 | case MATCH: | |
658 | { | |
659 | if(! r.out.avail()) | |
660 | return done(); | |
661 | if(offset_ > r.out.used()) | |
662 | { | |
663 | // copy from window | |
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); | |
671 | r.out.next += n; | |
672 | length_ -= n; | |
673 | } | |
674 | else | |
675 | { | |
676 | // copy from output | |
677 | auto in = r.out.next - offset_; | |
678 | auto n = clamp(length_, r.out.avail()); | |
679 | length_ -= n; | |
680 | while(n--) | |
681 | *r.out.next++ = *in++; | |
682 | } | |
683 | if(length_ == 0) | |
684 | mode_ = LEN; | |
685 | break; | |
686 | } | |
687 | ||
688 | case LIT: | |
689 | { | |
690 | if(! r.out.avail()) | |
691 | return done(); | |
692 | auto const v = static_cast<std::uint8_t>(length_); | |
693 | *r.out.next++ = v; | |
694 | mode_ = LEN; | |
695 | break; | |
696 | } | |
697 | ||
698 | case CHECK: | |
699 | mode_ = DONE; | |
700 | // fall through | |
701 | ||
702 | case DONE: | |
703 | ec = error::end_of_stream; | |
704 | return done(); | |
705 | ||
706 | case BAD: | |
707 | return done(); | |
708 | ||
709 | case SYNC: | |
710 | default: | |
711 | throw beast::detail::make_exception<std::logic_error>( | |
712 | "stream error", __FILE__, __LINE__); | |
713 | } | |
714 | } | |
715 | } | |
716 | ||
717 | //------------------------------------------------------------------------------ | |
718 | ||
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 | |
729 | the shortest code. | |
730 | */ | |
731 | template<class> | |
732 | void | |
733 | inflate_stream:: | |
734 | inflate_table( | |
735 | build type, | |
736 | std::uint16_t* lens, | |
737 | std::size_t codes, | |
738 | code** table, | |
739 | unsigned *bits, | |
740 | std::uint16_t* work, | |
741 | error_code& ec) | |
742 | { | |
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 | |
763 | ||
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}; | |
768 | ||
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}; | |
773 | ||
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}; | |
779 | ||
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}; | |
785 | ||
786 | /* | |
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. | |
798 | ||
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. | |
803 | ||
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 | |
808 | the caller. | |
809 | ||
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 | |
814 | decoding tables. | |
815 | */ | |
816 | ||
817 | /* accumulate lengths for codes (assumes lens[] all in 0..15) */ | |
818 | for (len = 0; len <= 15; len++) | |
819 | count[len] = 0; | |
820 | for (sym = 0; sym < codes; sym++) | |
821 | count[lens[sym]]++; | |
822 | ||
823 | /* bound code lengths, force root to be within code lengths */ | |
824 | root = *bits; | |
825 | for (max = 15; max >= 1; max--) | |
826 | if (count[max] != 0) | |
827 | break; | |
828 | if (root > max) | |
829 | root = max; | |
830 | if (max == 0) | |
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 */ | |
836 | *(*table)++ = here; | |
837 | *bits = 1; | |
838 | return; /* no symbols, but wait for decoding to report error */ | |
839 | } | |
840 | for (min = 1; min < max; min++) | |
841 | if (count[min] != 0) | |
842 | break; | |
843 | if (root < min) | |
844 | root = min; | |
845 | ||
846 | /* check for an over-subscribed or incomplete set of lengths */ | |
847 | left = 1; | |
848 | for (len = 1; len <= 15; len++) | |
849 | { | |
850 | left <<= 1; | |
851 | left -= count[len]; | |
852 | if (left < 0) | |
853 | { | |
854 | ec = error::over_subscribed_length; | |
855 | return; | |
856 | } | |
857 | } | |
858 | if (left > 0 && (type == build::codes || max != 1)) | |
859 | { | |
860 | ec = error::incomplete_length_set; | |
861 | return; | |
862 | } | |
863 | ||
864 | /* generate offsets into symbol table for each length for sorting */ | |
865 | offs[1] = 0; | |
866 | for (len = 1; len < 15; len++) | |
867 | offs[len + 1] = offs[len] + count[len]; | |
868 | ||
869 | /* sort symbols by length, by symbol order within each length */ | |
870 | for (sym = 0; sym < codes; sym++) | |
871 | if (lens[sym] != 0) | |
872 | work[offs[lens[sym]]++] = (std::uint16_t)sym; | |
873 | ||
874 | /* | |
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. | |
881 | ||
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. | |
887 | ||
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. | |
892 | ||
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. | |
898 | ||
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. | |
903 | */ | |
904 | ||
905 | /* set up for code type */ | |
906 | switch (type) | |
907 | { | |
908 | case build::codes: | |
909 | base = extra = work; /* dummy value--not used */ | |
910 | end = 19; | |
911 | break; | |
912 | case build::lens: | |
913 | base = lbase; | |
914 | base -= 257; | |
915 | extra = lext; | |
916 | extra -= 257; | |
917 | end = 256; | |
918 | break; | |
919 | default: /* build::dists */ | |
920 | base = dbase; | |
921 | extra = dext; | |
922 | end = -1; | |
923 | } | |
924 | ||
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 */ | |
935 | ||
936 | auto const not_enough = [] | |
937 | { | |
938 | throw beast::detail::make_exception<std::logic_error>( | |
939 | "insufficient output size when inflating tables", __FILE__, __LINE__); | |
940 | }; | |
941 | ||
942 | // check available table space | |
943 | if ((type == build::lens && used > kEnoughLens) || | |
944 | (type == build::dists && used > kEnoughDists)) | |
945 | return not_enough(); | |
946 | ||
947 | /* process all codes and make table entries */ | |
948 | for (;;) | |
949 | { | |
950 | /* create table entry */ | |
951 | here.bits = (std::uint8_t)(len - drop); | |
952 | if ((int)(work[sym]) < end) | |
953 | { | |
954 | here.op = (std::uint8_t)0; | |
955 | here.val = work[sym]; | |
956 | } | |
957 | else if ((int)(work[sym]) > end) | |
958 | { | |
959 | here.op = (std::uint8_t)(extra[work[sym]]); | |
960 | here.val = base[work[sym]]; | |
961 | } | |
962 | else | |
963 | { | |
964 | here.op = (std::uint8_t)(32 + 64); /* end of block */ | |
965 | here.val = 0; | |
966 | } | |
967 | ||
968 | /* replicate for those indices with low len bits equal to huff */ | |
969 | incr = 1U << (len - drop); | |
970 | fill = 1U << curr; | |
971 | min = fill; /* save offset to next table */ | |
972 | do | |
973 | { | |
974 | fill -= incr; | |
975 | next[(huff >> drop) + fill] = here; | |
976 | } while (fill != 0); | |
977 | ||
978 | /* backwards increment the len-bit code huff */ | |
979 | incr = 1U << (len - 1); | |
980 | while (huff & incr) | |
981 | incr >>= 1; | |
982 | if (incr != 0) | |
983 | { | |
984 | huff &= incr - 1; | |
985 | huff += incr; | |
986 | } | |
987 | else | |
988 | huff = 0; | |
989 | ||
990 | /* go to next symbol, update count, len */ | |
991 | sym++; | |
992 | if (--(count[len]) == 0) | |
993 | { | |
994 | if (len == max) break; | |
995 | len = lens[work[sym]]; | |
996 | } | |
997 | ||
998 | /* create new sub-table if needed */ | |
999 | if (len > root && (huff & mask) != low) | |
1000 | { | |
1001 | /* if first time, transition to sub-tables */ | |
1002 | if (drop == 0) | |
1003 | drop = root; | |
1004 | ||
1005 | /* increment past last table */ | |
1006 | next += min; /* here min is 1 << curr */ | |
1007 | ||
1008 | /* determine length of next table */ | |
1009 | curr = len - drop; | |
1010 | left = (int)(1 << curr); | |
1011 | while (curr + drop < max) | |
1012 | { | |
1013 | left -= count[curr + drop]; | |
1014 | if (left <= 0) break; | |
1015 | curr++; | |
1016 | left <<= 1; | |
1017 | } | |
1018 | ||
1019 | /* check for enough space */ | |
1020 | used += 1U << curr; | |
1021 | if ((type == build::lens && used > kEnoughLens) || | |
1022 | (type == build::dists && used > kEnoughDists)) | |
1023 | return not_enough(); | |
1024 | ||
1025 | /* point entry in root table to sub-table */ | |
1026 | low = huff & mask; | |
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); | |
1030 | } | |
1031 | } | |
1032 | ||
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) */ | |
1036 | if (huff != 0) | |
1037 | { | |
1038 | here.op = 64; // invalid code marker | |
1039 | here.bits = (std::uint8_t)(len - drop); | |
1040 | here.val = 0; | |
1041 | next[huff] = here; | |
1042 | } | |
1043 | ||
1044 | *table += used; | |
1045 | *bits = root; | |
1046 | } | |
1047 | ||
1048 | template<class> | |
1049 | auto | |
1050 | inflate_stream:: | |
1051 | get_fixed_tables() -> | |
1052 | codes const& | |
1053 | { | |
1054 | struct fixed_codes : codes | |
1055 | { | |
1056 | code len_[512]; | |
1057 | code dist_[32]; | |
1058 | ||
1059 | fixed_codes() | |
1060 | { | |
1061 | lencode = len_; | |
1062 | lenbits = 9; | |
1063 | distcode = dist_; | |
1064 | distbits = 5; | |
1065 | ||
1066 | std::uint16_t lens[320]; | |
1067 | std::uint16_t work[288]; | |
1068 | ||
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); | |
1073 | ||
1074 | { | |
1075 | error_code ec; | |
1076 | auto next = &len_[0]; | |
1077 | inflate_table(build::lens, | |
1078 | lens, 288, &next, &lenbits, work, ec); | |
1079 | if(ec) | |
1080 | throw std::logic_error{ec.message()}; | |
1081 | } | |
1082 | ||
1083 | // VFALCO These fixups are from ZLib | |
1084 | len_[ 99].op = 64; | |
1085 | len_[227].op = 64; | |
1086 | len_[355].op = 64; | |
1087 | len_[483].op = 64; | |
1088 | ||
1089 | { | |
1090 | error_code ec; | |
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); | |
1095 | if(ec) | |
1096 | throw std::logic_error{ec.message()}; | |
1097 | } | |
1098 | } | |
1099 | }; | |
1100 | ||
1101 | static fixed_codes const fc; | |
1102 | return fc; | |
1103 | } | |
1104 | ||
1105 | template<class> | |
1106 | void | |
1107 | inflate_stream:: | |
1108 | fixedTables() | |
1109 | { | |
1110 | auto const fc = get_fixed_tables(); | |
1111 | lencode_ = fc.lencode; | |
1112 | lenbits_ = fc.lenbits; | |
1113 | distcode_ = fc.distcode; | |
1114 | distbits_ = fc.distbits; | |
1115 | } | |
1116 | ||
1117 | /* | |
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. | |
1124 | ||
1125 | Entry assumptions: | |
1126 | ||
1127 | state->mode_ == LEN | |
1128 | zs.avail_in >= 6 | |
1129 | zs.avail_out >= 258 | |
1130 | start >= zs.avail_out | |
1131 | state->bits_ < 8 | |
1132 | ||
1133 | On return, state->mode_ is one of: | |
1134 | ||
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 | |
1138 | ||
1139 | Notes: | |
1140 | ||
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. | |
1146 | ||
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 | |
1150 | output space. | |
1151 | ||
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 | |
1163 | */ | |
1164 | template<class> | |
1165 | void | |
1166 | inflate_stream:: | |
1167 | inflate_fast(ranges& r, error_code& ec) | |
1168 | { | |
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 | |
1178 | ||
1179 | last = r.in.next + (r.in.avail() - 5); | |
1180 | end = r.out.next + (r.out.avail() - 257); | |
1181 | ||
1182 | /* decode literals and length/distances until end-of-block or not enough | |
1183 | input data or output space */ | |
1184 | do | |
1185 | { | |
1186 | if(bi_.size() < 15) | |
1187 | bi_.fill_16(r.in.next); | |
1188 | auto cp = &lencode_[bi_.peek_fast() & lmask]; | |
1189 | dolen: | |
1190 | bi_.drop(cp->bits); | |
1191 | op = (unsigned)(cp->op); | |
1192 | if(op == 0) | |
1193 | { | |
1194 | // literal | |
1195 | *r.out.next++ = (unsigned char)(cp->val); | |
1196 | } | |
1197 | else if(op & 16) | |
1198 | { | |
1199 | // length base | |
1200 | len = (unsigned)(cp->val); | |
1201 | op &= 15; // number of extra bits | |
1202 | if(op) | |
1203 | { | |
1204 | if(bi_.size() < op) | |
1205 | bi_.fill_8(r.in.next); | |
1206 | len += (unsigned)bi_.peek_fast() & ((1U << op) - 1); | |
1207 | bi_.drop(op); | |
1208 | } | |
1209 | if(bi_.size() < 15) | |
1210 | bi_.fill_16(r.in.next); | |
1211 | cp = &distcode_[bi_.peek_fast() & dmask]; | |
1212 | dodist: | |
1213 | bi_.drop(cp->bits); | |
1214 | op = (unsigned)(cp->op); | |
1215 | if(op & 16) | |
1216 | { | |
1217 | // distance base | |
1218 | dist = (unsigned)(cp->val); | |
1219 | op &= 15; // number of extra bits | |
1220 | if(bi_.size() < op) | |
1221 | { | |
1222 | bi_.fill_8(r.in.next); | |
1223 | if(bi_.size() < op) | |
1224 | bi_.fill_8(r.in.next); | |
1225 | } | |
1226 | dist += (unsigned)bi_.peek_fast() & ((1U << op) - 1); | |
1227 | #ifdef INFLATE_STRICT | |
1228 | if(dist > dmax_) | |
1229 | { | |
1230 | ec = error::invalid_distance; | |
1231 | mode_ = BAD; | |
1232 | break; | |
1233 | } | |
1234 | #endif | |
1235 | bi_.drop(op); | |
1236 | ||
1237 | op = r.out.used(); | |
1238 | if(dist > op) | |
1239 | { | |
1240 | // copy from window | |
1241 | op = dist - op; // distance back in window | |
1242 | if(op > w_.size()) | |
1243 | { | |
1244 | ec = error::invalid_distance; | |
1245 | mode_ = BAD; | |
1246 | break; | |
1247 | } | |
1248 | auto const n = clamp(len, op); | |
1249 | w_.read(r.out.next, op, n); | |
1250 | r.out.next += n; | |
1251 | len -= n; | |
1252 | } | |
1253 | if(len > 0) | |
1254 | { | |
1255 | // copy from output | |
1256 | auto in = r.out.next - dist; | |
1257 | auto n = clamp(len, r.out.avail()); | |
1258 | len -= n; | |
1259 | while(n--) | |
1260 | *r.out.next++ = *in++; | |
1261 | } | |
1262 | } | |
1263 | else if((op & 64) == 0) | |
1264 | { | |
1265 | // 2nd level distance code | |
1266 | cp = &distcode_[cp->val + (bi_.peek_fast() & ((1U << op) - 1))]; | |
1267 | goto dodist; | |
1268 | } | |
1269 | else | |
1270 | { | |
1271 | ec = error::invalid_distance_code; | |
1272 | mode_ = BAD; | |
1273 | break; | |
1274 | } | |
1275 | } | |
1276 | else if((op & 64) == 0) | |
1277 | { | |
1278 | // 2nd level length code | |
1279 | cp = &lencode_[cp->val + (bi_.peek_fast() & ((1U << op) - 1))]; | |
1280 | goto dolen; | |
1281 | } | |
1282 | else if(op & 32) | |
1283 | { | |
1284 | // end-of-block | |
1285 | mode_ = TYPE; | |
1286 | break; | |
1287 | } | |
1288 | else | |
1289 | { | |
1290 | ec = error::invalid_literal_length; | |
1291 | mode_ = BAD; | |
1292 | break; | |
1293 | } | |
1294 | } | |
1295 | while(r.in.next < last && r.out.next < end); | |
1296 | ||
1297 | // return unused bytes (on entry, bits < 8, so in won't go too far back) | |
1298 | bi_.rewind(r.in.next); | |
1299 | } | |
1300 | ||
1301 | } // detail | |
1302 | } // zlib | |
1303 | } // beast | |
1304 | ||
1305 | #endif |