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-2018 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_DEFLATE_STREAM_IPP
38	#define BOOST_BEAST_ZLIB_DETAIL_DEFLATE_STREAM_IPP
39
40	#include <boost/beast/zlib/detail/deflate_stream.hpp>
41	#include <boost/beast/zlib/detail/ranges.hpp>
42	#include <boost/assert.hpp>
43	#include <boost/config.hpp>
44	#include <boost/make_unique.hpp>
45	#include <boost/optional.hpp>
46	#include <boost/throw_exception.hpp>
47	#include <cstdint>
48	#include <cstdlib>
49	#include <cstring>
50	#include <memory>
51	#include <stdexcept>
52	#include <type_traits>
53
54	namespace boost {
55	namespace beast {
56	namespace zlib {
57	namespace detail {
58
59	/*
60	* ALGORITHM
61	*
62	* The "deflation" process depends on being able to identify portions
63	* of the input text which are identical to earlier input (within a
64	* sliding window trailing behind the input currently being processed).
65	*
66	* Each code tree is stored in a compressed form which is itself
67	* a Huffman encoding of the lengths of all the code strings (in
68	* ascending order by source values). The actual code strings are
69	* reconstructed from the lengths in the inflate process, as described
70	* in the deflate specification.
71	*
72	* The most straightforward technique turns out to be the fastest for
73	* most input files: try all possible matches and select the longest.
74	* The key feature of this algorithm is that insertions into the string
75	* dictionary are very simple and thus fast, and deletions are avoided
76	* completely. Insertions are performed at each input character, whereas
77	* string matches are performed only when the previous match ends. So it
78	* is preferable to spend more time in matches to allow very fast string
79	* insertions and avoid deletions. The matching algorithm for small
80	* strings is inspired from that of Rabin & Karp. A brute force approach
81	* is used to find longer strings when a small match has been found.
82	* A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
83	* (by Leonid Broukhis).
84	* A previous version of this file used a more sophisticated algorithm
85	* (by Fiala and Greene) which is guaranteed to run in linear amortized
86	* time, but has a larger average cost, uses more memory and is patented.
87	* However the F&G algorithm may be faster for some highly redundant
88	* files if the parameter max_chain_length (described below) is too large.
89	*
90	* ACKNOWLEDGEMENTS
91	*
92	* The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
93	* I found it in 'freeze' written by Leonid Broukhis.
94	* Thanks to many people for bug reports and testing.
95	*
96	* REFERENCES
97	*
98	* Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
99	* Available in http://tools.ietf.org/html/rfc1951
100	*
101	* A description of the Rabin and Karp algorithm is given in the book
102	* "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
103	*
104	* Fiala,E.R., and Greene,D.H.
105	* Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
106	*
107	*/
108
109	/* Generate the codes for a given tree and bit counts (which need not be optimal).
110	IN assertion: the array bl_count contains the bit length statistics for
111	the given tree and the field len is set for all tree elements.
112	OUT assertion: the field code is set for all tree elements of non
113	zero code length.
114	*/
115	void
116	deflate_stream::
117	gen_codes(ct_data *tree, int max_code, std::uint16_t *bl_count)
118	{
119	std::uint16_t next_code[maxBits+1]; /* next code value for each bit length */
120	std::uint16_t code = 0; /* running code value */
121	int bits; /* bit index */
122	int n; /* code index */
123
124	// The distribution counts are first used to
125	// generate the code values without bit reversal.
126	for(bits = 1; bits <= maxBits; bits++)
127	{
128	code = (code + bl_count[bits-1]) << 1;
129	next_code[bits] = code;
130	}
131	// Check that the bit counts in bl_count are consistent.
132	// The last code must be all ones.
133	BOOST_ASSERT(code + bl_count[maxBits]-1 == (1<<maxBits)-1);
134	for(n = 0; n <= max_code; n++)
135	{
136	int len = tree[n].dl;
137	if(len == 0)
138	continue;
139	tree[n].fc = bi_reverse(code: next_code[len]++, len);
140	}
141	}
142
143	auto
144	deflate_stream::get_lut() ->
145	lut_type const&
146	{
147	struct init
148	{
149	lut_type tables;
150
151	init()
152	{
153	// number of codes at each bit length for an optimal tree
154	//std::uint16_t bl_count[maxBits+1];
155
156	// Initialize the mapping length (0..255) -> length code (0..28)
157	std::uint8_t length = 0;
158	for(std::uint8_t code = 0; code < lengthCodes-1; ++code)
159	{
160	tables.base_length[code] = length;
161	auto const run = 1U << tables.extra_lbits[code];
162	for(unsigned n = 0; n < run; ++n)
163	tables.length_code[length++] = code;
164	}
165	BOOST_ASSERT(length == 0);
166	// Note that the length 255 (match length 258) can be represented
167	// in two different ways: code 284 + 5 bits or code 285, so we
168	// overwrite length_code[255] to use the best encoding:
169	tables.length_code[255] = lengthCodes-1;
170
171	// Initialize the mapping dist (0..32K) -> dist code (0..29)
172	{
173	std::uint8_t code;
174	std::uint16_t dist = 0;
175	for(code = 0; code < 16; code++)
176	{
177	tables.base_dist[code] = dist;
178	auto const run = 1U << tables.extra_dbits[code];
179	for(unsigned n = 0; n < run; ++n)
180	tables.dist_code[dist++] = code;
181	}
182	BOOST_ASSERT(dist == 256);
183	// from now on, all distances are divided by 128
184	dist >>= 7;
185	for(; code < dCodes; ++code)
186	{
187	tables.base_dist[code] = dist << 7;
188	auto const run = 1U << (tables.extra_dbits[code]-7);
189	for(std::size_t n = 0; n < run; ++n)
190	tables.dist_code[256 + dist++] = code;
191	}
192	BOOST_ASSERT(dist == 256);
193	}
194
195	// Construct the codes of the static literal tree
196	std::uint16_t bl_count[maxBits+1];
197	std::memset(s: bl_count, c: 0, n: sizeof(bl_count));
198	unsigned n = 0;
199	while (n <= 143)
200	tables.ltree[n++].dl = 8;
201	bl_count[8] += 144;
202	while (n <= 255)
203	tables.ltree[n++].dl = 9;
204	bl_count[9] += 112;
205	while (n <= 279)
206	tables.ltree[n++].dl = 7;
207	bl_count[7] += 24;
208	while (n <= 287)
209	tables.ltree[n++].dl = 8;
210	bl_count[8] += 8;
211	// Codes 286 and 287 do not exist, but we must include them in the tree
212	// construction to get a canonical Huffman tree (longest code all ones)
213	gen_codes(tree: tables.ltree, max_code: lCodes+1, bl_count);
214
215	for(n = 0; n < dCodes; ++n)
216	{
217	tables.dtree[n].dl = 5;
218	tables.dtree[n].fc =
219	static_cast<std::uint16_t>(bi_reverse(code: n, len: 5));
220	}
221	}
222	};
223	static init const data;
224	return data.tables;
225	}
226
227	void
228	deflate_stream::
229	doReset(
230	int level,
231	int windowBits,
232	int memLevel,
233	Strategy strategy)
234	{
235	if(level == default_size)
236	level = 6;
237
238	// VFALCO What do we do about this?
239	// until 256-byte window bug fixed
240	if(windowBits == 8)
241	windowBits = 9;
242
243	if(level < 0 || level > 9)
244	BOOST_THROW_EXCEPTION(std::invalid_argument{
245	"invalid level"});
246
247	if(windowBits < 8 || windowBits > 15)
248	BOOST_THROW_EXCEPTION(std::invalid_argument{
249	"invalid windowBits"});
250
251	if(memLevel < 1 || memLevel > max_mem_level)
252	BOOST_THROW_EXCEPTION(std::invalid_argument{
253	"invalid memLevel"});
254
255	w_bits_ = windowBits;
256
257	hash_bits_ = memLevel + 7;
258
259	// 16K elements by default
260	lit_bufsize_ = 1 << (memLevel + 6);
261
262	level_ = level;
263	strategy_ = strategy;
264	inited_ = false;
265	}
266
267	void
268	deflate_stream::
269	doReset()
270	{
271	inited_ = false;
272	}
273
274	void
275	deflate_stream::
276	doClear()
277	{
278	inited_ = false;
279	buf_.reset();
280	}
281
282	std::size_t
283	deflate_stream::
284	doUpperBound(std::size_t sourceLen) const
285	{
286	std::size_t complen;
287	std::size_t wraplen;
288
289	/* conservative upper bound for compressed data */
290	complen = sourceLen +
291	((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
292
293	/* compute wrapper length */
294	wraplen = 0;
295
296	/* if not default parameters, return conservative bound */
297	if(w_bits_ != 15 || hash_bits_ != 8 + 7)
298	return complen + wraplen;
299
300	/* default settings: return tight bound for that case */
301	return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
302	(sourceLen >> 25) + 13 - 6 + wraplen;
303	}
304
305	void
306	deflate_stream::
307	doTune(
308	int good_length,
309	int max_lazy,
310	int nice_length,
311	int max_chain)
312	{
313	good_match_ = good_length;
314	nice_match_ = nice_length;
315	max_lazy_match_ = max_lazy;
316	max_chain_length_ = max_chain;
317	}
318
319	void
320	deflate_stream::
321	doParams(z_params& zs, int level, Strategy strategy, error_code& ec)
322	{
323	compress_func func;
324
325	if(level == default_size)
326	level = 6;
327	if(level < 0 || level > 9)
328	{
329	BOOST_BEAST_ASSIGN_EC(ec, error::stream_error);
330	return;
331	}
332	func = get_config(level: level_).func;
333
334	if((strategy != strategy_ || func != get_config(level).func) &&
335	zs.total_in != 0)
336	{
337	// Flush the last buffer:
338	doWrite(zs, flush: Flush::block, ec);
339	if(ec == error::need_buffers && pending_ == 0)
340	ec = {};
341	}
342	if(level_ != level)
343	{
344	level_ = level;
345	max_lazy_match_ = get_config(level).max_lazy;
346	good_match_ = get_config(level).good_length;
347	nice_match_ = get_config(level).nice_length;
348	max_chain_length_ = get_config(level).max_chain;
349	}
350	strategy_ = strategy;
351	}
352
353	// VFALCO boost::optional param is a workaround for
354	// gcc "maybe uninitialized" warning
355	// https://github.com/boostorg/beast/issues/532
356	//
357	void
358	deflate_stream::
359	doWrite(z_params& zs, boost::optional<Flush> flush, error_code& ec)
360	{
361	maybe_init();
362
363	if(zs.next_in == nullptr && zs.avail_in != 0)
364	BOOST_THROW_EXCEPTION(std::invalid_argument{"invalid input"});
365
366	if(zs.next_out == nullptr ||
367	(status_ == finish_state && flush != Flush::finish))
368	{
369	BOOST_BEAST_ASSIGN_EC(ec, error::stream_error);
370	return;
371	}
372	if(zs.avail_out == 0)
373	{
374	BOOST_BEAST_ASSIGN_EC(ec, error::need_buffers);
375	return;
376	}
377
378	// value of flush param for previous deflate call
379	auto old_flush = boost::make_optional<Flush>(
380	cond: last_flush_.is_initialized(),
381	v: last_flush_ ? *last_flush_ : Flush::none);
382
383	last_flush_ = flush;
384
385	// Flush as much pending output as possible
386	if(pending_ != 0)
387	{
388	flush_pending(zs);
389	if(zs.avail_out == 0)
390	{
391	/* Since avail_out is 0, deflate will be called again with
392	* more output space, but possibly with both pending and
393	* avail_in equal to zero. There won't be anything to do,
394	* but this is not an error situation so make sure we
395	* return OK instead of BUF_ERROR at next call of deflate:
396	*/
397	last_flush_ = boost::none;
398	return;
399	}
400	}
401	else if(zs.avail_in == 0 && (
402	old_flush && flush <= *old_flush // Caution: depends on enum order
403	) && flush != Flush::finish)
404	{
405	/* Make sure there is something to do and avoid duplicate consecutive
406	* flushes. For repeated and useless calls with Flush::finish, we keep
407	* returning Z_STREAM_END instead of Z_BUF_ERROR.
408	*/
409	BOOST_BEAST_ASSIGN_EC(ec, error::need_buffers);
410	return;
411	}
412
413	// User must not provide more input after the first FINISH:
414	if(status_ == finish_state && zs.avail_in != 0)
415	{
416	BOOST_BEAST_ASSIGN_EC(ec, error::need_buffers);
417	return;
418	}
419
420	/* Start a new block or continue the current one.
421	*/
422	if(zs.avail_in != 0 || lookahead_ != 0 ||
423	(flush != Flush::none && status_ != finish_state))
424	{
425	block_state bstate;
426
427	switch(strategy_)
428	{
429	case Strategy::huffman:
430	bstate = deflate_huff(zs, flush: flush.get());
431	break;
432	case Strategy::rle:
433	bstate = deflate_rle(zs, flush: flush.get());
434	break;
435	default:
436	{
437	bstate = (this->*(get_config(level: level_).func))(zs, flush.get());
438	break;
439	}
440	}
441
442	if(bstate == finish_started || bstate == finish_done)
443	{
444	status_ = finish_state;
445	}
446	if(bstate == need_more || bstate == finish_started)
447	{
448	if(zs.avail_out == 0)
449	{
450	last_flush_ = boost::none; /* avoid BUF_ERROR next call, see above */
451	}
452	return;
453	/* If flush != Flush::none && avail_out == 0, the next call
454	of deflate should use the same flush parameter to make sure
455	that the flush is complete. So we don't have to output an
456	empty block here, this will be done at next call. This also
457	ensures that for a very small output buffer, we emit at most
458	one empty block.
459	*/
460	}
461	if(bstate == block_done)
462	{
463	if(flush == Flush::partial)
464	{
465	tr_align();
466	}
467	else if(flush != Flush::block)
468	{
469	/* FULL_FLUSH or SYNC_FLUSH */
470	tr_stored_block(bu: nullptr, stored_len: 0L, last: 0);
471	/* For a full flush, this empty block will be recognized
472	* as a special marker by inflate_sync().
473	*/
474	if(flush == Flush::full)
475	{
476	clear_hash(); // forget history
477	if(lookahead_ == 0)
478	{
479	strstart_ = 0;
480	block_start_ = 0L;
481	insert_ = 0;
482	}
483	}
484	}
485	flush_pending(zs);
486	if(zs.avail_out == 0)
487	{
488	last_flush_ = boost::none; /* avoid BUF_ERROR at next call, see above */
489	return;
490	}
491	}
492	}
493
494	if(flush == Flush::finish)
495	{
496	BOOST_BEAST_ASSIGN_EC(ec, error::end_of_stream);
497	return;
498	}
499	}
500
501	// VFALCO Warning: untested
502	void
503	deflate_stream::
504	doDictionary(Byte const* dict, uInt dictLength, error_code& ec)
505	{
506	if(lookahead_)
507	{
508	BOOST_BEAST_ASSIGN_EC(ec, error::stream_error);
509	return;
510	}
511
512	maybe_init();
513
514	/* if dict would fill window, just replace the history */
515	if(dictLength >= w_size_)
516	{
517	clear_hash();
518	strstart_ = 0;
519	block_start_ = 0L;
520	insert_ = 0;
521	dict += dictLength - w_size_; /* use the tail */
522	dictLength = w_size_;
523	}
524
525	/* insert dict into window and hash */
526	z_params zs;
527	zs.avail_in = dictLength;
528	zs.next_in = (const Byte *)dict;
529	zs.avail_out = 0;
530	zs.next_out = 0;
531	fill_window(zs);
532	while(lookahead_ >= minMatch)
533	{
534	uInt str = strstart_;
535	uInt n = lookahead_ - (minMatch-1);
536	do
537	{
538	update_hash(h&: ins_h_, c: window_[str + minMatch-1]);
539	prev_[str & w_mask_] = head_[ins_h_];
540	head_[ins_h_] = (std::uint16_t)str;
541	str++;
542	}
543	while(--n);
544	strstart_ = str;
545	lookahead_ = minMatch-1;
546	fill_window(zs);
547	}
548	strstart_ += lookahead_;
549	block_start_ = (long)strstart_;
550	insert_ = lookahead_;
551	lookahead_ = 0;
552	match_length_ = prev_length_ = minMatch-1;
553	match_available_ = 0;
554	}
555
556	void
557	deflate_stream::
558	doPrime(int bits, int value, error_code& ec)
559	{
560	maybe_init();
561
562	if((Byte *)(sym_buf_) < pending_out_ + ((Buf_size + 7) >> 3))
563	{
564	BOOST_BEAST_ASSIGN_EC(ec, error::need_buffers);
565	return;
566	}
567
568	do
569	{
570	int put = Buf_size - bi_valid_;
571	if(put > bits)
572	put = bits;
573	bi_buf_ |= (std::uint16_t)((value & ((1 << put) - 1)) << bi_valid_);
574	bi_valid_ += put;
575	tr_flush_bits();
576	value >>= put;
577	bits -= put;
578	}
579	while(bits);
580	}
581
582	void
583	deflate_stream::
584	doPending(unsigned* value, int* bits)
585	{
586	if(value != 0)
587	*value = pending_;
588	if(bits != 0)
589	*bits = bi_valid_;
590	}
591
592	//--------------------------------------------------------------------------
593
594	// Do lazy initialization
595	void
596	deflate_stream::
597	init()
598	{
599	// Caller must set these:
600	// w_bits_
601	// hash_bits_
602	// lit_bufsize_
603	// level_
604	// strategy_
605
606	w_size_ = 1 << w_bits_;
607	w_mask_ = w_size_ - 1;
608
609	hash_size_ = 1 << hash_bits_;
610	hash_mask_ = hash_size_ - 1;
611	hash_shift_ = ((hash_bits_+minMatch-1)/minMatch);
612
613	auto const nwindow = w_size_ * 2*sizeof(Byte);
614	auto const nprev = w_size_ * sizeof(std::uint16_t);
615	auto const nhead = hash_size_ * sizeof(std::uint16_t);
616	auto const noverlay = lit_bufsize_ * (sizeof(std::uint16_t)+2);
617	auto const needed = nwindow + nprev + nhead + noverlay;
618
619	if(! buf_ || buf_size_ != needed)
620	{
621	buf_ = boost::make_unique_noinit<
622	std::uint8_t[]>(size: needed);
623	buf_size_ = needed;
624	}
625
626	window_ = reinterpret_cast<Byte*>(buf_.get());
627	prev_ = reinterpret_cast<std::uint16_t*>(buf_.get() + nwindow);
628	std::memset(s: prev_, c: 0, n: nprev);
629	head_ = reinterpret_cast<std::uint16_t*>(buf_.get() + nwindow + nprev);
630
631	// nothing written to window_ yet
632	high_water_ = 0;
633
634
635	/* We overlay pending_buf and sym_buf. This works since the average size
636	for length/distance pairs over any compressed block is assured to be 31
637	bits or less.
638
639	Analysis: The longest fixed codes are a length code of 8 bits plus 5
640	extra bits, for lengths 131 to 257. The longest fixed distance codes are
641	5 bits plus 13 extra bits, for distances 16385 to 32768. The longest
642	possible fixed-codes length/distance pair is then 31 bits total.
643
644	sym_buf starts one-fourth of the way into pending_buf. So there are
645	three bytes in sym_buf for every four bytes in pending_buf. Each symbol
646	in sym_buf is three bytes -- two for the distance and one for the
647	literal/length. As each symbol is consumed, the pointer to the next
648	sym_buf value to read moves forward three bytes. From that symbol, up to
649	31 bits are written to pending_buf. The closest the written pending_buf
650	bits gets to the next sym_buf symbol to read is just before the last
651	code is written. At that time, 31*(n-2) bits have been written, just
652	after 24*(n-2) bits have been consumed from sym_buf. sym_buf starts at
653	8*n bits into pending_buf. (Note that the symbol buffer fills when n-1
654	symbols are written.) The closest the writing gets to what is unread is
655	then n+14 bits. Here n is lit_bufsize, which is 16384 by default, and
656	can range from 128 to 32768.
657
658	Therefore, at a minimum, there are 142 bits of space between what is
659	written and what is read in the overlain buffers, so the symbols cannot
660	be overwritten by the compressed data. That space is actually 139 bits,
661	due to the three-bit fixed-code block header.
662
663	That covers the case where either Z_FIXED is specified, forcing fixed
664	codes, or when the use of fixed codes is chosen, because that choice
665	results in a smaller compressed block than dynamic codes. That latter
666	condition then assures that the above analysis also covers all dynamic
667	blocks. A dynamic-code block will only be chosen to be emitted if it has
668	fewer bits than a fixed-code block would for the same set of symbols.
669	Therefore its average symbol length is assured to be less than 31. So
670	the compressed data for a dynamic block also cannot overwrite the
671	symbols from which it is being constructed.
672	*/
673	pending_buf_ =
674	buf_.get() + nwindow + nprev + nhead;
675	pending_buf_size_ =
676	static_cast<std::uint32_t>(lit_bufsize_) * 4;
677
678	sym_buf_ = pending_buf_ + lit_bufsize_;
679	sym_end_ = (lit_bufsize_ - 1) * 3;
680
681	pending_ = 0;
682	pending_out_ = pending_buf_;
683
684	status_ = busy_state;
685	last_flush_ = Flush::none;
686
687	tr_init();
688	lm_init();
689
690	inited_ = true;
691	}
692
693	/* Initialize the "longest match" routines for a new zlib stream
694	*/
695	void
696	deflate_stream::
697	lm_init()
698	{
699	window_size_ = (std::uint32_t)2L*w_size_;
700
701	clear_hash();
702
703	/* Set the default configuration parameters:
704	*/
705	// VFALCO TODO just copy the config struct
706	max_lazy_match_ = get_config(level: level_).max_lazy;
707	good_match_ = get_config(level: level_).good_length;
708	nice_match_ = get_config(level: level_).nice_length;
709	max_chain_length_ = get_config(level: level_).max_chain;
710
711	strstart_ = 0;
712	block_start_ = 0L;
713	lookahead_ = 0;
714	insert_ = 0;
715	match_length_ = prev_length_ = minMatch-1;
716	match_available_ = 0;
717	ins_h_ = 0;
718	}
719
720	// Initialize a new block.
721	//
722	void
723	deflate_stream::
724	init_block()
725	{
726	for(int n = 0; n < lCodes; n++)
727	dyn_ltree_[n].fc = 0;
728	for(int n = 0; n < dCodes; n++)
729	dyn_dtree_[n].fc = 0;
730	for(int n = 0; n < blCodes; n++)
731	bl_tree_[n].fc = 0;
732	dyn_ltree_[end_block].fc = 1;
733	opt_len_ = 0L;
734	static_len_ = 0L;
735	sym_next_ = 0;
736	matches_ = 0;
737	}
738
739	/* Restore the heap property by moving down the tree starting at node k,
740	exchanging a node with the smallest of its two sons if necessary,
741	stopping when the heap property is re-established (each father smaller
742	than its two sons).
743	*/
744	void
745	deflate_stream::
746	pqdownheap(
747	ct_data const* tree, // the tree to restore
748	int k) // node to move down
749	{
750	int v = heap_[k];
751	int j = k << 1; // left son of k
752	while(j <= heap_len_)
753	{
754	// Set j to the smallest of the two sons:
755	if(j < heap_len_ &&
756	smaller(tree, n: heap_[j+1], m: heap_[j]))
757	j++;
758	// Exit if v is smaller than both sons
759	if(smaller(tree, n: v, m: heap_[j]))
760	break;
761
762	// Exchange v with the smallest son
763	heap_[k] = heap_[j];
764	k = j;
765
766	// And continue down the tree,
767	// setting j to the left son of k
768	j <<= 1;
769	}
770	heap_[k] = v;
771	}
772
773	/* Remove the smallest element from the heap and recreate the heap
774	with one less element. Updates heap and heap_len.
775	*/
776	void
777	deflate_stream::
778	pqremove(ct_data const* tree, int& top)
779	{
780	top = heap_[kSmallest];
781	heap_[kSmallest] = heap_[heap_len_--];
782	pqdownheap(tree, k: kSmallest);
783	}
784
785	/* Compute the optimal bit lengths for a tree and update the total bit length
786	for the current block.
787	IN assertion: the fields freq and dad are set, heap[heap_max] and
788	above are the tree nodes sorted by increasing frequency.
789	OUT assertions: the field len is set to the optimal bit length, the
790	array bl_count contains the frequencies for each bit length.
791	The length opt_len is updated; static_len is also updated if stree is
792	not null.
793	*/
794	void
795	deflate_stream::
796	gen_bitlen(tree_desc *desc)
797	{
798	ct_data *tree = desc->dyn_tree;
799	int max_code = desc->max_code;
800	ct_data const* stree = desc->stat_desc->static_tree;
801	std::uint8_t const *extra = desc->stat_desc->extra_bits;
802	int base = desc->stat_desc->extra_base;
803	int max_length = desc->stat_desc->max_length;
804	int h; // heap index
805	int n, m; // iterate over the tree elements
806	int bits; // bit length
807	int xbits; // extra bits
808	std::uint16_t f; // frequency
809	int overflow = 0; // number of elements with bit length too large
810
811	std::fill(first: &bl_count_[0], last: &bl_count_[maxBits+1], value: std::uint16_t{0});
812
813	/* In a first pass, compute the optimal bit lengths (which may
814	* overflow in the case of the bit length tree).
815	*/
816	tree[heap_[heap_max_]].dl = 0; // root of the heap
817
818	for(h = heap_max_+1; h < heap_size; h++) {
819	n = heap_[h];
820	bits = tree[tree[n].dl].dl + 1;
821	if(bits > max_length) bits = max_length, overflow++;
822	// We overwrite tree[n].dl which is no longer needed
823	tree[n].dl = (std::uint16_t)bits;
824
825	if(n > max_code)
826	continue; // not a leaf node
827
828	bl_count_[bits]++;
829	xbits = 0;
830	if(n >= base)
831	xbits = extra[n-base];
832	f = tree[n].fc;
833	opt_len_ += (std::uint32_t)f * (bits + xbits);
834	if(stree)
835	static_len_ += (std::uint32_t)f * (stree[n].dl + xbits);
836	}
837	if(overflow == 0)
838	return;
839
840	// Find the first bit length which could increase:
841	do
842	{
843	bits = max_length-1;
844	while(bl_count_[bits] == 0)
845	bits--;
846	bl_count_[bits]--; // move one leaf down the tree
847	bl_count_[bits+1] += 2; // move one overflow item as its brother
848	bl_count_[max_length]--;
849	/* The brother of the overflow item also moves one step up,
850	* but this does not affect bl_count[max_length]
851	*/
852	overflow -= 2;
853	}
854	while(overflow > 0);
855
856	/* Now recompute all bit lengths, scanning in increasing frequency.
857	* h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
858	* lengths instead of fixing only the wrong ones. This idea is taken
859	* from 'ar' written by Haruhiko Okumura.)
860	*/
861	for(bits = max_length; bits != 0; bits--)
862	{
863	n = bl_count_[bits];
864	while(n != 0)
865	{
866	m = heap_[--h];
867	if(m > max_code)
868	continue;
869	if((unsigned) tree[m].dl != (unsigned) bits)
870	{
871	opt_len_ += ((long)bits - (long)tree[m].dl) *(long)tree[m].fc;
872	tree[m].dl = (std::uint16_t)bits;
873	}
874	n--;
875	}
876	}
877	}
878
879	/* Construct one Huffman tree and assigns the code bit strings and lengths.
880	Update the total bit length for the current block.
881	IN assertion: the field freq is set for all tree elements.
882	OUT assertions: the fields len and code are set to the optimal bit length
883	and corresponding code. The length opt_len is updated; static_len is
884	also updated if stree is not null. The field max_code is set.
885	*/
886	void
887	deflate_stream::
888	build_tree(tree_desc *desc)
889	{
890	ct_data *tree = desc->dyn_tree;
891	ct_data const* stree = desc->stat_desc->static_tree;
892	int elems = desc->stat_desc->elems;
893	int n, m; // iterate over heap elements
894	int max_code = -1; // largest code with non zero frequency
895	int node; // new node being created
896
897	/* Construct the initial heap, with least frequent element in
898	* heap[kSmallest]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
899	* heap[0] is not used.
900	*/
901	heap_len_ = 0;
902	heap_max_ = heap_size;
903
904	for(n = 0; n < elems; n++)
905	{
906	if(tree[n].fc != 0)
907	{
908	heap_[++(heap_len_)] = max_code = n;
909	depth_[n] = 0;
910	}
911	else
912	{
913	tree[n].dl = 0;
914	}
915	}
916
917	/* The pkzip format requires that at least one distance code exists,
918	* and that at least one bit should be sent even if there is only one
919	* possible code. So to avoid special checks later on we force at least
920	* two codes of non zero frequency.
921	*/
922	while(heap_len_ < 2)
923	{
924	node = heap_[++(heap_len_)] = (max_code < 2 ? ++max_code : 0);
925	tree[node].fc = 1;
926	depth_[node] = 0;
927	opt_len_--;
928	if(stree)
929	static_len_ -= stree[node].dl;
930	// node is 0 or 1 so it does not have extra bits
931	}
932	desc->max_code = max_code;
933
934	/* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
935	* establish sub-heaps of increasing lengths:
936	*/
937	for(n = heap_len_/2; n >= 1; n--)
938	pqdownheap(tree, k: n);
939
940	/* Construct the Huffman tree by repeatedly combining the least two
941	* frequent nodes.
942	*/
943	node = elems; /* next internal node of the tree */
944	do
945	{
946	pqremove(tree, top&: n); /* n = node of least frequency */
947	m = heap_[kSmallest]; /* m = node of next least frequency */
948
949	heap_[--(heap_max_)] = n; /* keep the nodes sorted by frequency */
950	heap_[--(heap_max_)] = m;
951
952	/* Create a new node father of n and m */
953	tree[node].fc = tree[n].fc + tree[m].fc;
954	depth_[node] = (std::uint8_t)((depth_[n] >= depth_[m] ?
955	depth_[n] : depth_[m]) + 1);
956	tree[n].dl = tree[m].dl = (std::uint16_t)node;
957	/* and insert the new node in the heap */
958	heap_[kSmallest] = node++;
959	pqdownheap(tree, k: kSmallest);
960
961	}
962	while(heap_len_ >= 2);
963
964	heap_[--(heap_max_)] = heap_[kSmallest];
965
966	/* At this point, the fields freq and dad are set. We can now
967	* generate the bit lengths.
968	*/
969	gen_bitlen(desc: (tree_desc *)desc);
970
971	/* The field len is now set, we can generate the bit codes */
972	gen_codes(tree, max_code, bl_count: bl_count_);
973	}
974
975	/* Scan a literal or distance tree to determine the frequencies
976	of the codes in the bit length tree.
977	*/
978	void
979	deflate_stream::
980	scan_tree(
981	ct_data *tree, // the tree to be scanned
982	int max_code) // and its largest code of non zero frequency
983	{
984	int n; // iterates over all tree elements
985	int prevlen = -1; // last emitted length
986	int curlen; // length of current code
987	int nextlen = tree[0].dl; // length of next code
988	std::uint16_t count = 0; // repeat count of the current code
989	int max_count = 7; // max repeat count
990	int min_count = 4; // min repeat count
991
992	if(nextlen == 0)
993	{
994	max_count = 138;
995	min_count = 3;
996	}
997	tree[max_code+1].dl = (std::uint16_t)0xffff; // guard
998
999	for(n = 0; n <= max_code; n++)
1000	{
1001	curlen = nextlen; nextlen = tree[n+1].dl;
1002	if(++count < max_count && curlen == nextlen)
1003	{
1004	continue;
1005	}
1006	else if(count < min_count)
1007	{
1008	bl_tree_[curlen].fc += count;
1009	}
1010	else if(curlen != 0)
1011	{
1012	if(curlen != prevlen) bl_tree_[curlen].fc++;
1013	bl_tree_[rep_3_6].fc++;
1014	}
1015	else if(count <= 10)
1016	{
1017	bl_tree_[repz_3_10].fc++;
1018	}
1019	else
1020	{
1021	bl_tree_[repz_11_138].fc++;
1022	}
1023	count = 0;
1024	prevlen = curlen;
1025	if(nextlen == 0)
1026	{
1027	max_count = 138;
1028	min_count = 3;
1029	}
1030	else if(curlen == nextlen)
1031	{
1032	max_count = 6;
1033	min_count = 3;
1034	}
1035	else
1036	{
1037	max_count = 7;
1038	min_count = 4;
1039	}
1040	}
1041	}
1042
1043	/* Send a literal or distance tree in compressed form,
1044	using the codes in bl_tree.
1045	*/
1046	void
1047	deflate_stream::
1048	send_tree(
1049	ct_data *tree, // the tree to be scanned
1050	int max_code) // and its largest code of non zero frequency
1051	{
1052	int n; // iterates over all tree elements
1053	int prevlen = -1; // last emitted length
1054	int curlen; // length of current code
1055	int nextlen = tree[0].dl; // length of next code
1056	int count = 0; // repeat count of the current code
1057	int max_count = 7; // max repeat count
1058	int min_count = 4; // min repeat count
1059
1060	// tree[max_code+1].dl = -1; // guard already set
1061	if(nextlen == 0)
1062	{
1063	max_count = 138;
1064	min_count = 3;
1065	}
1066
1067	for(n = 0; n <= max_code; n++)
1068	{
1069	curlen = nextlen;
1070	nextlen = tree[n+1].dl;
1071	if(++count < max_count && curlen == nextlen)
1072	{
1073	continue;
1074	}
1075	else if(count < min_count)
1076	{
1077	do
1078	{
1079	send_code(value: curlen, tree: bl_tree_);
1080	}
1081	while (--count != 0);
1082	}
1083	else if(curlen != 0)
1084	{
1085	if(curlen != prevlen)
1086	{
1087	send_code(value: curlen, tree: bl_tree_);
1088	count--;
1089	}
1090	BOOST_ASSERT(count >= 3 && count <= 6);
1091	send_code(value: rep_3_6, tree: bl_tree_);
1092	send_bits(value: count-3, length: 2);
1093	}
1094	else if(count <= 10)
1095	{
1096	send_code(value: repz_3_10, tree: bl_tree_);
1097	send_bits(value: count-3, length: 3);
1098	}
1099	else
1100	{
1101	send_code(value: repz_11_138, tree: bl_tree_);
1102	send_bits(value: count-11, length: 7);
1103	}
1104	count = 0;
1105	prevlen = curlen;
1106	if(nextlen == 0)
1107	{
1108	max_count = 138;
1109	min_count = 3;
1110	}
1111	else if(curlen == nextlen)
1112	{
1113	max_count = 6;
1114	min_count = 3;
1115	}
1116	else
1117	{
1118	max_count = 7;
1119	min_count = 4;
1120	}
1121	}
1122	}
1123
1124	/* Construct the Huffman tree for the bit lengths and return
1125	the index in bl_order of the last bit length code to send.
1126	*/
1127	int
1128	deflate_stream::
1129	build_bl_tree()
1130	{
1131	int max_blindex; // index of last bit length code of non zero freq
1132
1133	// Determine the bit length frequencies for literal and distance trees
1134	scan_tree(tree: (ct_data *)dyn_ltree_, max_code: l_desc_.max_code);
1135	scan_tree(tree: (ct_data *)dyn_dtree_, max_code: d_desc_.max_code);
1136
1137	// Build the bit length tree:
1138	build_tree(desc: (tree_desc *)(&(bl_desc_)));
1139	/* opt_len now includes the length of the tree representations, except
1140	* the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
1141	*/
1142
1143	/* Determine the number of bit length codes to send. The pkzip format
1144	* requires that at least 4 bit length codes be sent. (appnote.txt says
1145	* 3 but the actual value used is 4.)
1146	*/
1147	for(max_blindex = blCodes-1; max_blindex >= 3; max_blindex--)
1148	{
1149	if(bl_tree_[lut_.bl_order[max_blindex]].dl != 0)
1150	break;
1151	}
1152	// Update opt_len to include the bit length tree and counts
1153	opt_len_ += 3*(max_blindex+1) + 5+5+4;
1154	return max_blindex;
1155	}
1156
1157	/* Send the header for a block using dynamic Huffman trees: the counts,
1158	the lengths of the bit length codes, the literal tree and the distance
1159	tree.
1160	IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
1161	*/
1162	void
1163	deflate_stream::
1164	send_all_trees(
1165	int lcodes,
1166	int dcodes,
1167	int blcodes) // number of codes for each tree
1168	{
1169	int rank; // index in bl_order
1170
1171	BOOST_ASSERT(lcodes >= 257 && dcodes >= 1 && blcodes >= 4);
1172	BOOST_ASSERT(lcodes <= lCodes && dcodes <= dCodes && blcodes <= blCodes);
1173	send_bits(value: lcodes-257, length: 5); // not +255 as stated in appnote.txt
1174	send_bits(value: dcodes-1, length: 5);
1175	send_bits(value: blcodes-4, length: 4); // not -3 as stated in appnote.txt
1176	for(rank = 0; rank < blcodes; rank++)
1177	send_bits(value: bl_tree_[lut_.bl_order[rank]].dl, length: 3);
1178	send_tree(tree: (ct_data *)dyn_ltree_, max_code: lcodes-1); // literal tree
1179	send_tree(tree: (ct_data *)dyn_dtree_, max_code: dcodes-1); // distance tree
1180	}
1181
1182	/* Send the block data compressed using the given Huffman trees
1183	*/
1184	void
1185	deflate_stream::
1186	compress_block(
1187	ct_data const* ltree, // literal tree
1188	ct_data const* dtree) // distance tree
1189	{
1190	unsigned dist; /* distance of matched string */
1191	int lc; /* match length or unmatched char (if dist == 0) */
1192	unsigned sx = 0; /* running index in sym_buf */
1193	unsigned code; /* the code to send */
1194	int extra; /* number of extra bits to send */
1195
1196	if(sym_next_ != 0)
1197	{
1198	do
1199	{
1200	dist = sym_buf_[sx++] & 0xff;
1201	dist += (unsigned)(sym_buf_[sx++] & 0xff) << 8;
1202	lc = sym_buf_[sx++];
1203	if(dist == 0)
1204	{
1205	send_code(value: lc, tree: ltree); /* send a literal byte */
1206	}
1207	else
1208	{
1209	/* Here, lc is the match length - minMatch */
1210	code = lut_.length_code[lc];
1211	send_code(value: code+literals+1, tree: ltree); /* send the length code */
1212	extra = lut_.extra_lbits[code];
1213	if(extra != 0)
1214	{
1215	lc -= lut_.base_length[code];
1216	send_bits(value: lc, length: extra); /* send the extra length bits */
1217	}
1218	dist--; /* dist is now the match distance - 1 */
1219	code = d_code(dist);
1220	BOOST_ASSERT(code < dCodes);
1221
1222	send_code(value: code, tree: dtree); /* send the distance code */
1223	extra = lut_.extra_dbits[code];
1224	if(extra != 0)
1225	{
1226	dist -= lut_.base_dist[code];
1227	send_bits(value: dist, length: extra); /* send the extra distance bits */
1228	}
1229	} /* literal or match pair ? */
1230
1231	/* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
1232	BOOST_ASSERT((uInt)(pending_) < lit_bufsize_ + sx);
1233	}
1234	while(sx < sym_next_);
1235	}
1236
1237	send_code(value: end_block, tree: ltree);
1238	}
1239
1240	/* Check if the data type is TEXT or BINARY, using the following algorithm:
1241	- TEXT if the two conditions below are satisfied:
1242	a) There are no non-portable control characters belonging to the
1243	"block list" (0..6, 14..25, 28..31).
1244	b) There is at least one printable character belonging to the
1245	"allow list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255).
1246	- BINARY otherwise.
1247	- The following partially-portable control characters form a
1248	"gray list" that is ignored in this detection algorithm:
1249	(7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}).
1250	IN assertion: the fields fc of dyn_ltree are set.
1251	*/
1252	int
1253	deflate_stream::
1254	detect_data_type()
1255	{
1256	/* block_mask is the bit mask of block-listed bytes
1257	* set bits 0..6, 14..25, and 28..31
1258	* 0xf3ffc07f = binary 11110011111111111100000001111111
1259	*/
1260	unsigned long block_mask = 0xf3ffc07fUL;
1261	int n;
1262
1263	// Check for non-textual ("block-listed") bytes.
1264	for(n = 0; n <= 31; n++, block_mask >>= 1)
1265	if((block_mask & 1) && (dyn_ltree_[n].fc != 0))
1266	return binary;
1267
1268	// Check for textual ("allow-listed") bytes. */
1269	if(dyn_ltree_[9].fc != 0 || dyn_ltree_[10].fc != 0
1270	|| dyn_ltree_[13].fc != 0)
1271	return text;
1272	for(n = 32; n < literals; n++)
1273	if(dyn_ltree_[n].fc != 0)
1274	return text;
1275
1276	/* There are no "block-listed" or "white-listed" bytes:
1277	* this stream either is empty or has tolerated ("gray-listed") bytes only.
1278	*/
1279	return binary;
1280	}
1281
1282	/* Flush the bit buffer and align the output on a byte boundary
1283	*/
1284	void
1285	deflate_stream::
1286	bi_windup()
1287	{
1288	if(bi_valid_ > 8)
1289	put_short(w: bi_buf_);
1290	else if(bi_valid_ > 0)
1291	put_byte(c: (Byte)bi_buf_);
1292	bi_buf_ = 0;
1293	bi_valid_ = 0;
1294	}
1295
1296	/* Flush the bit buffer, keeping at most 7 bits in it.
1297	*/
1298	void
1299	deflate_stream::
1300	bi_flush()
1301	{
1302	if(bi_valid_ == 16)
1303	{
1304	put_short(w: bi_buf_);
1305	bi_buf_ = 0;
1306	bi_valid_ = 0;
1307	}
1308	else if(bi_valid_ >= 8)
1309	{
1310	put_byte(c: (Byte)bi_buf_);
1311	bi_buf_ >>= 8;
1312	bi_valid_ -= 8;
1313	}
1314	}
1315
1316	/* Copy a stored block, storing first the length and its
1317	one's complement if requested.
1318	*/
1319	void
1320	deflate_stream::
1321	copy_block(
1322	char *buf, // the input data
1323	unsigned len, // its length
1324	int header) // true if block header must be written
1325	{
1326	bi_windup(); // align on byte boundary
1327
1328	if(header)
1329	{
1330	put_short(w: (std::uint16_t)len);
1331	put_short(w: (std::uint16_t)~len);
1332	}
1333	if(buf)
1334	std::memcpy(dest: &pending_buf_[pending_], src: buf, n: len);
1335	pending_ += len;
1336	}
1337
1338	//------------------------------------------------------------------------------
1339
1340	/* Initialize the tree data structures for a new zlib stream.
1341	*/
1342	void
1343	deflate_stream::
1344	tr_init()
1345	{
1346	l_desc_.dyn_tree = dyn_ltree_;
1347	l_desc_.stat_desc = &lut_.l_desc;
1348
1349	d_desc_.dyn_tree = dyn_dtree_;
1350	d_desc_.stat_desc = &lut_.d_desc;
1351
1352	bl_desc_.dyn_tree = bl_tree_;
1353	bl_desc_.stat_desc = &lut_.bl_desc;
1354
1355	bi_buf_ = 0;
1356	bi_valid_ = 0;
1357
1358	// Initialize the first block of the first file:
1359	init_block();
1360	}
1361
1362	/* Send one empty static block to give enough lookahead for inflate.
1363	This takes 10 bits, of which 7 may remain in the bit buffer.
1364	*/
1365	void
1366	deflate_stream::
1367	tr_align()
1368	{
1369	send_bits(value: static_trees<<1, length: 3);
1370	send_code(value: end_block, tree: lut_.ltree);
1371	bi_flush();
1372	}
1373
1374	/* Flush the bits in the bit buffer to pending output (leaves at most 7 bits)
1375	*/
1376	void
1377	deflate_stream::
1378	tr_flush_bits()
1379	{
1380	bi_flush();
1381	}
1382
1383	/* Send a stored block
1384	*/
1385	void
1386	deflate_stream::
1387	tr_stored_block(
1388	char *buf, // input block
1389	std::uint32_t stored_len, // length of input block
1390	int last) // one if this is the last block for a file
1391	{
1392	send_bits(value: (stored_block<<1)+last, length: 3); // send block type
1393	copy_block(buf, len: (unsigned)stored_len, header: 1); // with header
1394	}
1395
1396	void
1397	deflate_stream::
1398	tr_tally_dist(std::uint16_t dist, std::uint8_t len, bool& flush)
1399	{
1400	sym_buf_[sym_next_++] = dist & 0xFF;
1401	sym_buf_[sym_next_++] = dist >> 8;
1402	sym_buf_[sym_next_++] = len;
1403	dist--;
1404	dyn_ltree_[lut_.length_code[len]+literals+1].fc++;
1405	dyn_dtree_[d_code(dist)].fc++;
1406	flush = (sym_next_ == sym_end_);
1407	}
1408
1409	void
1410	deflate_stream::
1411	tr_tally_lit(std::uint8_t c, bool& flush)
1412	{
1413	sym_buf_[sym_next_++] = 0;
1414	sym_buf_[sym_next_++] = 0;
1415	sym_buf_[sym_next_++] = c;
1416	dyn_ltree_[c].fc++;
1417	flush = (sym_next_ == sym_end_);
1418	}
1419
1420	//------------------------------------------------------------------------------
1421
1422	/* Determine the best encoding for the current block: dynamic trees,
1423	static trees or store, and output the encoded block to the zip file.
1424	*/
1425	void
1426	deflate_stream::
1427	tr_flush_block(
1428	z_params& zs,
1429	char *buf, // input block, or NULL if too old
1430	std::uint32_t stored_len, // length of input block
1431	int last) // one if this is the last block for a file
1432	{
1433	std::uint32_t opt_lenb;
1434	std::uint32_t static_lenb; // opt_len and static_len in bytes
1435	int max_blindex = 0; // index of last bit length code of non zero freq
1436
1437	// Build the Huffman trees unless a stored block is forced
1438	if(level_ > 0)
1439	{
1440	// Check if the file is binary or text
1441	if(zs.data_type == unknown)
1442	zs.data_type = detect_data_type();
1443
1444	// Construct the literal and distance trees
1445	build_tree(desc: (tree_desc *)(&(l_desc_)));
1446
1447	build_tree(desc: (tree_desc *)(&(d_desc_)));
1448	/* At this point, opt_len and static_len are the total bit lengths of
1449	* the compressed block data, excluding the tree representations.
1450	*/
1451
1452	/* Build the bit length tree for the above two trees, and get the index
1453	* in bl_order of the last bit length code to send.
1454	*/
1455	max_blindex = build_bl_tree();
1456
1457	/* Determine the best encoding. Compute the block lengths in bytes. */
1458	opt_lenb = (opt_len_+3+7)>>3;
1459	static_lenb = (static_len_+3+7)>>3;
1460
1461	if(static_lenb <= opt_lenb)
1462	opt_lenb = static_lenb;
1463	}
1464	else
1465	{
1466	// VFALCO This assertion fails even in the original ZLib,
1467	// happens with strategy == Z_HUFFMAN_ONLY, see:
1468	// https://github.com/madler/zlib/issues/172
1469
1470	#if 0
1471	BOOST_ASSERT(buf);
1472	#endif
1473	opt_lenb = static_lenb = stored_len + 5; // force a stored block
1474	}
1475
1476	#ifdef FORCE_STORED
1477	if(buf != (char*)0) { /* force stored block */
1478	#else
1479	if(stored_len+4 <= opt_lenb && buf != (char*)0) {
1480	/* 4: two words for the lengths */
1481	#endif
1482	/* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
1483	* Otherwise we can't have processed more than WSIZE input bytes since
1484	* the last block flush, because compression would have been
1485	* successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
1486	* transform a block into a stored block.
1487	*/
1488	tr_stored_block(buf, stored_len, last);
1489
1490	#ifdef FORCE_STATIC
1491	}
1492	else if(static_lenb >= 0)
1493	{
1494	// force static trees
1495	#else
1496	}
1497	else if(strategy_ == Strategy::fixed || static_lenb == opt_lenb)
1498	{
1499	#endif
1500	send_bits(value: (static_trees<<1)+last, length: 3);
1501	compress_block(ltree: lut_.ltree, dtree: lut_.dtree);
1502	}
1503	else
1504	{
1505	send_bits(value: (dyn_trees<<1)+last, length: 3);
1506	send_all_trees(lcodes: l_desc_.max_code+1, dcodes: d_desc_.max_code+1,
1507	blcodes: max_blindex+1);
1508	compress_block(ltree: (const ct_data *)dyn_ltree_,
1509	dtree: (const ct_data *)dyn_dtree_);
1510	}
1511	/* The above check is made mod 2^32, for files larger than 512 MB
1512	* and std::size_t implemented on 32 bits.
1513	*/
1514	init_block();
1515
1516	if(last)
1517	bi_windup();
1518	}
1519
1520	void
1521	deflate_stream::
1522	fill_window(z_params& zs)
1523	{
1524	unsigned n, m;
1525	unsigned more; // Amount of free space at the end of the window.
1526	std::uint16_t *p;
1527	uInt wsize = w_size_;
1528
1529	do
1530	{
1531	more = (unsigned)(window_size_ -
1532	(std::uint32_t)lookahead_ -(std::uint32_t)strstart_);
1533
1534	// VFALCO We don't support systems below 32-bit
1535	#if 0
1536	// Deal with !@#$% 64K limit:
1537	if(sizeof(int) <= 2)
1538	{
1539	if(more == 0 && strstart_ == 0 && lookahead_ == 0)
1540	{
1541	more = wsize;
1542	}
1543	else if(more == (unsigned)(-1))
1544	{
1545	/* Very unlikely, but possible on 16 bit machine if
1546	* strstart == 0 && lookahead == 1 (input done a byte at time)
1547	*/
1548	more--;
1549	}
1550	}
1551	#endif
1552
1553	/* If the window is almost full and there is insufficient lookahead,
1554	move the upper half to the lower one to make room in the upper half.
1555	*/
1556	if(strstart_ >= wsize+max_dist())
1557	{
1558	std::memcpy(dest: window_, src: window_+wsize, n: (unsigned)wsize);
1559	match_start_ -= wsize;
1560	strstart_ -= wsize; // we now have strstart >= max_dist
1561	block_start_ -= (long) wsize;
1562	if (insert_ > strstart_)
1563	insert_ = strstart_;
1564
1565	/* Slide the hash table (could be avoided with 32 bit values
1566	at the expense of memory usage). We slide even when level == 0
1567	to keep the hash table consistent if we switch back to level > 0
1568	later. (Using level 0 permanently is not an optimal usage of
1569	zlib, so we don't care about this pathological case.)
1570	*/
1571	n = hash_size_;
1572	p = &head_[n];
1573	do
1574	{
1575	m = *--p;
1576	*p = (std::uint16_t)(m >= wsize ? m-wsize : 0);
1577	}
1578	while(--n);
1579
1580	n = wsize;
1581	p = &prev_[n];
1582	do
1583	{
1584	m = *--p;
1585	*p = (std::uint16_t)(m >= wsize ? m-wsize : 0);
1586	/* If n is not on any hash chain, prev[n] is garbage but
1587	its value will never be used.
1588	*/
1589	}
1590	while(--n);
1591	more += wsize;
1592	}
1593	if(zs.avail_in == 0)
1594	break;
1595
1596	/* If there was no sliding:
1597	strstart <= WSIZE+max_dist-1 && lookahead <= kMinLookahead - 1 &&
1598	more == window_size - lookahead - strstart
1599	=> more >= window_size - (kMinLookahead-1 + WSIZE + max_dist-1)
1600	=> more >= window_size - 2*WSIZE + 2
1601	In the BIG_MEM or MMAP case (not yet supported),
1602	window_size == input_size + kMinLookahead &&
1603	strstart + lookahead_ <= input_size => more >= kMinLookahead.
1604	Otherwise, window_size == 2*WSIZE so more >= 2.
1605	If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1606	*/
1607	n = read_buf(zs, buf: window_ + strstart_ + lookahead_, size: more);
1608	lookahead_ += n;
1609
1610	// Initialize the hash value now that we have some input:
1611	if(lookahead_ + insert_ >= minMatch)
1612	{
1613	uInt str = strstart_ - insert_;
1614	ins_h_ = window_[str];
1615	update_hash(h&: ins_h_, c: window_[str + 1]);
1616	while(insert_)
1617	{
1618	update_hash(h&: ins_h_, c: window_[str + minMatch-1]);
1619	prev_[str & w_mask_] = head_[ins_h_];
1620	head_[ins_h_] = (std::uint16_t)str;
1621	str++;
1622	insert_--;
1623	if(lookahead_ + insert_ < minMatch)
1624	break;
1625	}
1626	}
1627	/* If the whole input has less than minMatch bytes, ins_h is garbage,
1628	but this is not important since only literal bytes will be emitted.
1629	*/
1630	}
1631	while(lookahead_ < kMinLookahead && zs.avail_in != 0);
1632
1633	/* If the kWinInit bytes after the end of the current data have never been
1634	written, then zero those bytes in order to avoid memory check reports of
1635	the use of uninitialized (or uninitialised as Julian writes) bytes by
1636	the longest match routines. Update the high water mark for the next
1637	time through here. kWinInit is set to maxMatch since the longest match
1638	routines allow scanning to strstart + maxMatch, ignoring lookahead.
1639	*/
1640	if(high_water_ < window_size_)
1641	{
1642	std::uint32_t curr = strstart_ + (std::uint32_t)(lookahead_);
1643	std::uint32_t winit;
1644
1645	if(high_water_ < curr)
1646	{
1647	/* Previous high water mark below current data -- zero kWinInit
1648	bytes or up to end of window, whichever is less.
1649	*/
1650	winit = window_size_ - curr;
1651	if(winit > kWinInit)
1652	winit = kWinInit;
1653	std::memset(s: window_ + curr, c: 0, n: (unsigned)winit);
1654	high_water_ = curr + winit;
1655	}
1656	else if(high_water_ < (std::uint32_t)curr + kWinInit)
1657	{
1658	/* High water mark at or above current data, but below current data
1659	plus kWinInit -- zero out to current data plus kWinInit, or up
1660	to end of window, whichever is less.
1661	*/
1662	winit = (std::uint32_t)curr + kWinInit - high_water_;
1663	if(winit > window_size_ - high_water_)
1664	winit = window_size_ - high_water_;
1665	std::memset(s: window_ + high_water_, c: 0, n: (unsigned)winit);
1666	high_water_ += winit;
1667	}
1668	}
1669	}
1670
1671	/* Flush as much pending output as possible. All write() output goes
1672	through this function so some applications may wish to modify it
1673	to avoid allocating a large strm->next_out buffer and copying into it.
1674	(See also read_buf()).
1675	*/
1676	void
1677	deflate_stream::
1678	flush_pending(z_params& zs)
1679	{
1680	tr_flush_bits();
1681	auto len = clamp(u: pending_, v: zs.avail_out);
1682	if(len == 0)
1683	return;
1684
1685	std::memcpy(dest: zs.next_out, src: pending_out_, n: len);
1686	zs.next_out =
1687	static_cast<std::uint8_t*>(zs.next_out) + len;
1688	pending_out_ += len;
1689	zs.total_out += len;
1690	zs.avail_out -= len;
1691	pending_ -= len;
1692	if(pending_ == 0)
1693	pending_out_ = pending_buf_;
1694	}
1695
1696	/* Flush the current block, with given end-of-file flag.
1697	IN assertion: strstart is set to the end of the current match.
1698	*/
1699	void
1700	deflate_stream::
1701	flush_block(z_params& zs, bool last)
1702	{
1703	tr_flush_block(zs,
1704	buf: (block_start_ >= 0L ?
1705	(char *)&window_[(unsigned)block_start_] :
1706	(char *)0),
1707	stored_len: (std::uint32_t)((long)strstart_ - block_start_),
1708	last);
1709	block_start_ = strstart_;
1710	flush_pending(zs);
1711	}
1712
1713	/* Read a new buffer from the current input stream, update the adler32
1714	and total number of bytes read. All write() input goes through
1715	this function so some applications may wish to modify it to avoid
1716	allocating a large strm->next_in buffer and copying from it.
1717	(See also flush_pending()).
1718	*/
1719	int
1720	deflate_stream::
1721	read_buf(z_params& zs, Byte *buf, unsigned size)
1722	{
1723	auto len = clamp(u: zs.avail_in, v: size);
1724	if(len == 0)
1725	return 0;
1726
1727	zs.avail_in -= len;
1728
1729	std::memcpy(dest: buf, src: zs.next_in, n: len);
1730	zs.next_in = static_cast<
1731	std::uint8_t const*>(zs.next_in) + len;
1732	zs.total_in += len;
1733	return (int)len;
1734	}
1735
1736	/* Set match_start to the longest match starting at the given string and
1737	return its length. Matches shorter or equal to prev_length are discarded,
1738	in which case the result is equal to prev_length and match_start is
1739	garbage.
1740	IN assertions: cur_match is the head of the hash chain for the current
1741	string (strstart) and its distance is <= max_dist, and prev_length >= 1
1742	OUT assertion: the match length is not greater than s->lookahead_.
1743
1744	For 80x86 and 680x0, an optimized version will be provided in match.asm or
1745	match.S. The code will be functionally equivalent.
1746	*/
1747	uInt
1748	deflate_stream::
1749	longest_match(IPos cur_match)
1750	{
1751	unsigned chain_length = max_chain_length_;/* max hash chain length */
1752	Byte *scan = window_ + strstart_; /* current string */
1753	Byte *match; /* matched string */
1754	int len; /* length of current match */
1755	int best_len = prev_length_; /* best match length so far */
1756	int nice_match = nice_match_; /* stop if match long enough */
1757	IPos limit = strstart_ > (IPos)max_dist() ?
1758	strstart_ - (IPos)max_dist() : 0;
1759	/* Stop when cur_match becomes <= limit. To simplify the code,
1760	* we prevent matches with the string of window index 0.
1761	*/
1762	std::uint16_t *prev = prev_;
1763	uInt wmask = w_mask_;
1764
1765	Byte *strend = window_ + strstart_ + maxMatch;
1766	Byte scan_end1 = scan[best_len-1];
1767	Byte scan_end = scan[best_len];
1768
1769	/* The code is optimized for HASH_BITS >= 8 and maxMatch-2 multiple of 16.
1770	* It is easy to get rid of this optimization if necessary.
1771	*/
1772	BOOST_ASSERT(hash_bits_ >= 8 && maxMatch == 258);
1773
1774	/* Do not waste too much time if we already have a good match: */
1775	if(prev_length_ >= good_match_) {
1776	chain_length >>= 2;
1777	}
1778	/* Do not look for matches beyond the end of the input. This is necessary
1779	* to make deflate deterministic.
1780	*/
1781	if((uInt)nice_match > lookahead_)
1782	nice_match = lookahead_;
1783
1784	BOOST_ASSERT((std::uint32_t)strstart_ <= window_size_-kMinLookahead);
1785
1786	do {
1787	BOOST_ASSERT(cur_match < strstart_);
1788	match = window_ + cur_match;
1789
1790	/* Skip to next match if the match length cannot increase
1791	* or if the match length is less than 2. Note that the checks below
1792	* for insufficient lookahead only occur occasionally for performance
1793	* reasons. Therefore uninitialized memory will be accessed, and
1794	* conditional jumps will be made that depend on those values.
1795	* However the length of the match is limited to the lookahead, so
1796	* the output of deflate is not affected by the uninitialized values.
1797	*/
1798	if( match[best_len] != scan_end ||
1799	match[best_len-1] != scan_end1 ||
1800	*match != *scan ||
1801	*++match != scan[1])
1802	continue;
1803
1804	/* The check at best_len-1 can be removed because it will be made
1805	* again later. (This heuristic is not always a win.)
1806	* It is not necessary to compare scan[2] and match[2] since they
1807	* are always equal when the other bytes match, given that
1808	* the hash keys are equal and that HASH_BITS >= 8.
1809	*/
1810	scan += 2, match++;
1811	BOOST_ASSERT(*scan == *match);
1812
1813	/* We check for insufficient lookahead only every 8th comparison;
1814	* the 256th check will be made at strstart+258.
1815	*/
1816	do
1817	{
1818	}
1819	while( *++scan == *++match && *++scan == *++match &&
1820	*++scan == *++match && *++scan == *++match &&
1821	*++scan == *++match && *++scan == *++match &&
1822	*++scan == *++match && *++scan == *++match &&
1823	scan < strend);
1824
1825	BOOST_ASSERT(scan <= window_+(unsigned)(window_size_-1));
1826
1827	len = maxMatch - (int)(strend - scan);
1828	scan = strend - maxMatch;
1829
1830	if(len > best_len) {
1831	match_start_ = cur_match;
1832	best_len = len;
1833	if(len >= nice_match) break;
1834	scan_end1 = scan[best_len-1];
1835	scan_end = scan[best_len];
1836	}
1837	}
1838	while((cur_match = prev[cur_match & wmask]) > limit
1839	&& --chain_length != 0);
1840
1841	if((uInt)best_len <= lookahead_)
1842	return (uInt)best_len;
1843	return lookahead_;
1844	}
1845
1846	//------------------------------------------------------------------------------
1847
1848	/* Copy without compression as much as possible from the input stream, return
1849	the current block state.
1850	This function does not insert new strings in the dictionary since
1851	uncompressible data is probably not useful. This function is used
1852	only for the level=0 compression option.
1853	NOTE: this function should be optimized to avoid extra copying from
1854	window to pending_buf.
1855	*/
1856	auto
1857	deflate_stream::
1858	f_stored(z_params& zs, Flush flush) ->
1859	block_state
1860	{
1861	/* Stored blocks are limited to 0xffff bytes, pending_buf is limited
1862	* to pending_buf_size, and each stored block has a 5 byte header:
1863	*/
1864	std::uint32_t max_block_size = 0xffff;
1865	std::uint32_t max_start;
1866
1867	if(max_block_size > pending_buf_size_ - 5) {
1868	max_block_size = pending_buf_size_ - 5;
1869	}
1870
1871	/* Copy as much as possible from input to output: */
1872	for(;;) {
1873	/* Fill the window as much as possible: */
1874	if(lookahead_ <= 1) {
1875
1876	BOOST_ASSERT(strstart_ < w_size_+max_dist() ||
1877	block_start_ >= (long)w_size_);
1878
1879	fill_window(zs);
1880	if(lookahead_ == 0 && flush == Flush::none)
1881	return need_more;
1882
1883	if(lookahead_ == 0) break; /* flush the current block */
1884	}
1885	BOOST_ASSERT(block_start_ >= 0L);
1886
1887	strstart_ += lookahead_;
1888	lookahead_ = 0;
1889
1890	/* Emit a stored block if pending_buf will be full: */
1891	max_start = block_start_ + max_block_size;
1892	if(strstart_ == 0 || (std::uint32_t)strstart_ >= max_start) {
1893	/* strstart == 0 is possible when wraparound on 16-bit machine */
1894	lookahead_ = (uInt)(strstart_ - max_start);
1895	strstart_ = (uInt)max_start;
1896	flush_block(zs, last: false);
1897	if(zs.avail_out == 0)
1898	return need_more;
1899	}
1900	/* Flush if we may have to slide, otherwise block_start may become
1901	* negative and the data will be gone:
1902	*/
1903	if(strstart_ - (uInt)block_start_ >= max_dist()) {
1904	flush_block(zs, last: false);
1905	if(zs.avail_out == 0)
1906	return need_more;
1907	}
1908	}
1909	insert_ = 0;
1910	if(flush == Flush::finish)
1911	{
1912	flush_block(zs, last: true);
1913	if(zs.avail_out == 0)
1914	return finish_started;
1915	return finish_done;
1916	}
1917	if((long)strstart_ > block_start_)
1918	{
1919	flush_block(zs, last: false);
1920	if(zs.avail_out == 0)
1921	return need_more;
1922	}
1923	return block_done;
1924	}
1925
1926	/* Compress as much as possible from the input stream, return the current
1927	block state.
1928	This function does not perform lazy evaluation of matches and inserts
1929	new strings in the dictionary only for unmatched strings or for short
1930	matches. It is used only for the fast compression options.
1931	*/
1932	auto
1933	deflate_stream::
1934	f_fast(z_params& zs, Flush flush) ->
1935	block_state
1936	{
1937	IPos hash_head; /* head of the hash chain */
1938	bool bflush; /* set if current block must be flushed */
1939
1940	for(;;)
1941	{
1942	/* Make sure that we always have enough lookahead, except
1943	* at the end of the input file. We need maxMatch bytes
1944	* for the next match, plus minMatch bytes to insert the
1945	* string following the next match.
1946	*/
1947	if(lookahead_ < kMinLookahead)
1948	{
1949	fill_window(zs);
1950	if(lookahead_ < kMinLookahead && flush == Flush::none)
1951	return need_more;
1952	if(lookahead_ == 0)
1953	break; /* flush the current block */
1954	}
1955
1956	/* Insert the string window[strstart .. strstart+2] in the
1957	* dictionary, and set hash_head to the head of the hash chain:
1958	*/
1959	hash_head = 0;
1960	if(lookahead_ >= minMatch) {
1961	insert_string(hash_head);
1962	}
1963
1964	/* Find the longest match, discarding those <= prev_length.
1965	* At this point we have always match_length < minMatch
1966	*/
1967	if(hash_head != 0 && strstart_ - hash_head <= max_dist()) {
1968	/* To simplify the code, we prevent matches with the string
1969	* of window index 0 (in particular we have to avoid a match
1970	* of the string with itself at the start of the input file).
1971	*/
1972	match_length_ = longest_match (cur_match: hash_head);
1973	/* longest_match() sets match_start */
1974	}
1975	if(match_length_ >= minMatch)
1976	{
1977	tr_tally_dist(dist: static_cast<std::uint16_t>(strstart_ - match_start_),
1978	len: static_cast<std::uint8_t>(match_length_ - minMatch), flush&: bflush);
1979
1980	lookahead_ -= match_length_;
1981
1982	/* Insert new strings in the hash table only if the match length
1983	* is not too large. This saves time but degrades compression.
1984	*/
1985	if(match_length_ <= max_lazy_match_ &&
1986	lookahead_ >= minMatch) {
1987	match_length_--; /* string at strstart already in table */
1988	do
1989	{
1990	strstart_++;
1991	insert_string(hash_head);
1992	/* strstart never exceeds WSIZE-maxMatch, so there are
1993	* always minMatch bytes ahead.
1994	*/
1995	}
1996	while(--match_length_ != 0);
1997	strstart_++;
1998	}
1999	else
2000	{
2001	strstart_ += match_length_;
2002	match_length_ = 0;
2003	ins_h_ = window_[strstart_];
2004	update_hash(h&: ins_h_, c: window_[strstart_+1]);
2005	/* If lookahead < minMatch, ins_h is garbage, but it does not
2006	* matter since it will be recomputed at next deflate call.
2007	*/
2008	}
2009	}
2010	else
2011	{
2012	/* No match, output a literal byte */
2013	tr_tally_lit(c: window_[strstart_], flush&: bflush);
2014	lookahead_--;
2015	strstart_++;
2016	}
2017	if(bflush)
2018	{
2019	flush_block(zs, last: false);
2020	if(zs.avail_out == 0)
2021	return need_more;
2022	}
2023	}
2024	insert_ = strstart_ < minMatch-1 ? strstart_ : minMatch-1;
2025	if(flush == Flush::finish)
2026	{
2027	flush_block(zs, last: true);
2028	if(zs.avail_out == 0)
2029	return finish_started;
2030	return finish_done;
2031	}
2032	if(sym_next_)
2033	{
2034	flush_block(zs, last: false);
2035	if(zs.avail_out == 0)
2036	return need_more;
2037	}
2038	return block_done;
2039	}
2040
2041	/* Same as above, but achieves better compression. We use a lazy
2042	evaluation for matches: a match is finally adopted only if there is
2043	no better match at the next window position.
2044	*/
2045	auto
2046	deflate_stream::
2047	f_slow(z_params& zs, Flush flush) ->
2048	block_state
2049	{
2050	IPos hash_head; /* head of hash chain */
2051	bool bflush; /* set if current block must be flushed */
2052
2053	/* Process the input block. */
2054	for(;;)
2055	{
2056	/* Make sure that we always have enough lookahead, except
2057	* at the end of the input file. We need maxMatch bytes
2058	* for the next match, plus minMatch bytes to insert the
2059	* string following the next match.
2060	*/
2061	if(lookahead_ < kMinLookahead)
2062	{
2063	fill_window(zs);
2064	if(lookahead_ < kMinLookahead && flush == Flush::none)
2065	return need_more;
2066	if(lookahead_ == 0)
2067	break; /* flush the current block */
2068	}
2069
2070	/* Insert the string window[strstart .. strstart+2] in the
2071	* dictionary, and set hash_head to the head of the hash chain:
2072	*/
2073	hash_head = 0;
2074	if(lookahead_ >= minMatch)
2075	insert_string(hash_head);
2076
2077	/* Find the longest match, discarding those <= prev_length.
2078	*/
2079	prev_length_ = match_length_, prev_match_ = match_start_;
2080	match_length_ = minMatch-1;
2081
2082	if(hash_head != 0 && prev_length_ < max_lazy_match_ &&
2083	strstart_ - hash_head <= max_dist())
2084	{
2085	/* To simplify the code, we prevent matches with the string
2086	* of window index 0 (in particular we have to avoid a match
2087	* of the string with itself at the start of the input file).
2088	*/
2089	match_length_ = longest_match(cur_match: hash_head);
2090	/* longest_match() sets match_start */
2091
2092	if(match_length_ <= 5 && (strategy_ == Strategy::filtered
2093	|| (match_length_ == minMatch &&
2094	strstart_ - match_start_ > kTooFar)
2095	))
2096	{
2097	/* If prev_match is also minMatch, match_start is garbage
2098	* but we will ignore the current match anyway.
2099	*/
2100	match_length_ = minMatch-1;
2101	}
2102	}
2103	/* If there was a match at the previous step and the current
2104	* match is not better, output the previous match:
2105	*/
2106	if(prev_length_ >= minMatch && match_length_ <= prev_length_)
2107	{
2108	/* Do not insert strings in hash table beyond this. */
2109	uInt max_insert = strstart_ + lookahead_ - minMatch;
2110
2111	tr_tally_dist(
2112	dist: static_cast<std::uint16_t>(strstart_ -1 - prev_match_),
2113	len: static_cast<std::uint8_t>(prev_length_ - minMatch), flush&: bflush);
2114
2115	/* Insert in hash table all strings up to the end of the match.
2116	* strstart-1 and strstart are already inserted. If there is not
2117	* enough lookahead, the last two strings are not inserted in
2118	* the hash table.
2119	*/
2120	lookahead_ -= prev_length_-1;
2121	prev_length_ -= 2;
2122	do {
2123	if(++strstart_ <= max_insert)
2124	insert_string(hash_head);
2125	}
2126	while(--prev_length_ != 0);
2127	match_available_ = 0;
2128	match_length_ = minMatch-1;
2129	strstart_++;
2130
2131	if(bflush)
2132	{
2133	flush_block(zs, last: false);
2134	if(zs.avail_out == 0)
2135	return need_more;
2136	}
2137
2138	}
2139	else if(match_available_)
2140	{
2141	/* If there was no match at the previous position, output a
2142	* single literal. If there was a match but the current match
2143	* is longer, truncate the previous match to a single literal.
2144	*/
2145	tr_tally_lit(c: window_[strstart_-1], flush&: bflush);
2146	if(bflush)
2147	flush_block(zs, last: false);
2148	strstart_++;
2149	lookahead_--;
2150	if(zs.avail_out == 0)
2151	return need_more;
2152	}
2153	else
2154	{
2155	/* There is no previous match to compare with, wait for
2156	* the next step to decide.
2157	*/
2158	match_available_ = 1;
2159	strstart_++;
2160	lookahead_--;
2161	}
2162	}
2163	BOOST_ASSERT(flush != Flush::none);
2164	if(match_available_)
2165	{
2166	tr_tally_lit(c: window_[strstart_-1], flush&: bflush);
2167	match_available_ = 0;
2168	}
2169	insert_ = strstart_ < minMatch-1 ? strstart_ : minMatch-1;
2170	if(flush == Flush::finish)
2171	{
2172	flush_block(zs, last: true);
2173	if(zs.avail_out == 0)
2174	return finish_started;
2175	return finish_done;
2176	}
2177	if(sym_next_)
2178	{
2179	flush_block(zs, last: false);
2180	if(zs.avail_out == 0)
2181	return need_more;
2182	}
2183	return block_done;
2184	}
2185
2186	/* For Strategy::rle, simply look for runs of bytes, generate matches only of distance
2187	one. Do not maintain a hash table. (It will be regenerated if this run of
2188	deflate switches away from Strategy::rle.)
2189	*/
2190	auto
2191	deflate_stream::
2192	f_rle(z_params& zs, Flush flush) ->
2193	block_state
2194	{
2195	bool bflush; // set if current block must be flushed
2196	uInt prev; // byte at distance one to match
2197	Byte *scan, *strend; // scan goes up to strend for length of run
2198
2199	for(;;)
2200	{
2201	/* Make sure that we always have enough lookahead, except
2202	* at the end of the input file. We need maxMatch bytes
2203	* for the longest run, plus one for the unrolled loop.
2204	*/
2205	if(lookahead_ <= maxMatch) {
2206	fill_window(zs);
2207	if(lookahead_ <= maxMatch && flush == Flush::none) {
2208	return need_more;
2209	}
2210	if(lookahead_ == 0) break; /* flush the current block */
2211	}
2212
2213	/* See how many times the previous byte repeats */
2214	match_length_ = 0;
2215	if(lookahead_ >= minMatch && strstart_ > 0) {
2216	scan = window_ + strstart_ - 1;
2217	prev = *scan;
2218	if(prev == *++scan && prev == *++scan && prev == *++scan) {
2219	strend = window_ + strstart_ + maxMatch;
2220	do {
2221	} while(prev == *++scan && prev == *++scan &&
2222	prev == *++scan && prev == *++scan &&
2223	prev == *++scan && prev == *++scan &&
2224	prev == *++scan && prev == *++scan &&
2225	scan < strend);
2226	match_length_ = maxMatch - (int)(strend - scan);
2227	if(match_length_ > lookahead_)
2228	match_length_ = lookahead_;
2229	}
2230	BOOST_ASSERT(scan <= window_+(uInt)(window_size_-1));
2231	}
2232
2233	/* Emit match if have run of minMatch or longer, else emit literal */
2234	if(match_length_ >= minMatch) {
2235	tr_tally_dist(dist: std::uint16_t{1},
2236	len: static_cast<std::uint8_t>(match_length_ - minMatch),
2237	flush&: bflush);
2238
2239	lookahead_ -= match_length_;
2240	strstart_ += match_length_;
2241	match_length_ = 0;
2242	} else {
2243	/* No match, output a literal byte */
2244	tr_tally_lit(c: window_[strstart_], flush&: bflush);
2245	lookahead_--;
2246	strstart_++;
2247	}
2248	if(bflush)
2249	{
2250	flush_block(zs, last: false);
2251	if(zs.avail_out == 0)
2252	return need_more;
2253	}
2254	}
2255	insert_ = 0;
2256	if(flush == Flush::finish)
2257	{
2258	flush_block(zs, last: true);
2259	if(zs.avail_out == 0)
2260	return finish_started;
2261	return finish_done;
2262	}
2263	if(sym_next_)
2264	{
2265	flush_block(zs, last: false);
2266	if(zs.avail_out == 0)
2267	return need_more;
2268	}
2269	return block_done;
2270	}
2271
2272	/* ===========================================================================
2273	* For Strategy::huffman, do not look for matches. Do not maintain a hash table.
2274	* (It will be regenerated if this run of deflate switches away from Huffman.)
2275	*/
2276	auto
2277	deflate_stream::
2278	f_huff(z_params& zs, Flush flush) ->
2279	block_state
2280	{
2281	bool bflush; // set if current block must be flushed
2282
2283	for(;;)
2284	{
2285	// Make sure that we have a literal to write.
2286	if(lookahead_ == 0)
2287	{
2288	fill_window(zs);
2289	if(lookahead_ == 0)
2290	{
2291	if(flush == Flush::none)
2292	return need_more;
2293	break; // flush the current block
2294	}
2295	}
2296
2297	// Output a literal byte
2298	match_length_ = 0;
2299	tr_tally_lit(c: window_[strstart_], flush&: bflush);
2300	lookahead_--;
2301	strstart_++;
2302	if(bflush)
2303	{
2304	flush_block(zs, last: false);
2305	if(zs.avail_out == 0)
2306	return need_more;
2307	}
2308	}
2309	insert_ = 0;
2310	if(flush == Flush::finish)
2311	{
2312	flush_block(zs, last: true);
2313	if(zs.avail_out == 0)
2314	return finish_started;
2315	return finish_done;
2316	}
2317	if(sym_next_)
2318	{
2319	flush_block(zs, last: false);
2320	if(zs.avail_out == 0)
2321	return need_more;
2322	}
2323	return block_done;
2324	}
2325
2326	} // detail
2327	} // zlib
2328	} // beast
2329	} // boost
2330
2331	#endif
2332