Codestriker: "Topic Text: xdelta3"

nisse@hul...

Topic title: xdelta3

Tuesday November 20, 2012 11:45:26

Download topic text | View in monospace font | Tab width set to 8 (change to 4)

Files in topic:
[Jump to] xdelta3.c		{+5481,-0}

[Add General Comment] to topic.

File xdelta3.c (Revision 1.0)

[Add File Comment] [Top]


1	/* xdelta 3 - delta compression tools and library
2	* Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007,
3	* 2008, 2009, 2010. Joshua P. MacDonald
4	*
5	* This program is free software; you can redistribute it and/or modify
6	* it under the terms of the GNU General Public License as published by
7	* the Free Software Foundation; either version 2 of the License, or
8	* (at your option) any later version.
9	*
10	* This program is distributed in the hope that it will be useful,
11	* but WITHOUT ANY WARRANTY; without even the implied warranty of
12	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13	* GNU General Public License for more details.
14	*
15	* You should have received a copy of the GNU General Public License
16	* along with this program; if not, write to the Free Software
17	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19	-------------------------------------------------------------------
20
21	Xdelta 3
22
23	The goal of this library is to to implement both the (stand-alone)
24	data-compression and delta-compression aspects of VCDIFF encoding, and
25	to support a programming interface that works like Zlib
26	(http://www.gzip.org/zlib.html). See RFC3284: The VCDIFF Generic
27	Differencing and Compression Data Format.
28
29	VCDIFF is a unified encoding that combines data-compression and
30	delta-encoding ("differencing").
31
32	VCDIFF has a detailed byte-code instruction set with many features.
33	The instruction format supports an immediate size operand for small
34	COPYs and ADDs (e.g., under 18 bytes). There are also instruction
35	"modes", which are used to compress COPY addresses by using two
36	address caches. An instruction mode refers to slots in the NEAR
37	and SAME caches for recent addresses. NEAR remembers the
38	previous 4 (by default) COPY addresses, and SAME catches
39	frequent re-uses of the same address using a 3-way (by default)
40	256-entry associative cache of [ADDR mod 256], the encoded byte.
41	A hit in the NEAR/SAME cache requires 0/1 ADDR bytes.
42
43	VCDIFF has a default instruction table, but an alternate
44	instruction tables may themselves be be delta-compressed and
45	included in the encoding header. This allows even more freedom.
46	There are 9 instruction modes in the default code table, 4 near, 3
47	same, VCD_SELF (absolute encoding) and VCD_HERE (relative to the
48	current position).
49
50	----------------------------------------------------------------------
51
52	Algorithms
53
54	Aside from the details of encoding and decoding, there are a bunch
55	of algorithms needed.
56
57	1. STRING-MATCH. A two-level fingerprinting approach is used. A
58	single loop computes the two checksums -- small and large -- at
59	successive offsets in the TARGET file. The large checksum is more
60	accurate and is used to discover SOURCE matches, which are
61	potentially very long. The small checksum is used to discover
62	copies within the TARGET. Small matching, which is more expensive,
63	usually dominates the large STRING-MATCH costs in this code - the
64	more exhaustive the search, the better the results. Either of the
65	two string-matching mechanisms may be disabled.
66
67	2. INSTRUCTION SELECTION. The IOPT buffer here represents a queue
68	used to store overlapping copy instructions. There are two possible
69	optimizations that go beyond a greedy search. Both of these fall
70	into the category of "non-greedy matching" optimizations.
71
72	The first optimization stems from backward SOURCE-COPY matching.
73	When a new SOURCE-COPY instruction covers a previous instruction in
74	the target completely, it is erased from the queue. Randal Burns
75	originally analyzed these algorithms and did a lot of related work
76	(\cite the 1.5-pass algorithm).
77
78	The second optimization comes by the encoding of common very-small
79	COPY and ADD instructions, for which there are special DOUBLE-code
80	instructions, which code two instructions in a single byte.
81
82	The cost of bad instruction-selection overhead is relatively high
83	for data-compression, relative to delta-compression, so this second
84	optimization is fairly important. With "lazy" matching (the name
85	used in Zlib for a similar optimization), the string-match
86	algorithm searches after a match for potential overlapping copy
87	instructions. In Xdelta and by default, VCDIFF, the minimum match
88	size is 4 bytes, whereas Zlib searches with a 3-byte minimum. This
89	feature, combined with double instructions, provides a nice
90	challenge. Search in this file for "black magic", a heuristic.
91
92	3. STREAM ALIGNMENT. Stream alignment is needed to compress large
93	inputs in constant space. See xd3_srcwin_move_point().
94
95	4. WINDOW SELECTION. When the IOPT buffer flushes, in the first call
96	to xd3_iopt_finish_encoding containing any kind of copy instruction,
97	the parameters of the source window must be decided: the offset into
98	the source and the length of the window. Since the IOPT buffer is
99	finite, the program may be forced to fix these values before knowing
100	the best offset/length.
101
102	5. SECONDARY COMPRESSION. VCDIFF supports a secondary encoding to
103	be applied to the individual sections of the data format, which are
104	ADDRess, INSTruction, and DATA. Several secondary compressor
105	variations are implemented here, although none is standardized yet.
106
107	One is an adaptive huffman algorithm -- the FGK algorithm (Faller,
108	Gallager, and Knuth, 1985). This compressor is extremely slow.
109
110	The other is a simple static Huffman routine, which is the base
111	case of a semi-adaptive scheme published by D.J. Wheeler and first
112	widely used in bzip2 (by Julian Seward). This is a very
113	interesting algorithm, originally published in nearly cryptic form
114	by D.J. Wheeler. !!!NOTE!!! Because these are not standardized,
115	secondary compression remains off by default.
116	ftp://ftp.cl.cam.ac.uk/users/djw3/bred3.{c,ps}
117	--------------------------------------------------------------------
118
119	Other Features
120
121	1. USER CONVENIENCE
122
123	For user convenience, it is essential to recognize Gzip-compressed
124	files and automatically Gzip-decompress them prior to
125	delta-compression (or else no delta-compression will be achieved
126	unless the user manually decompresses the inputs). The compressed
127	represention competes with Xdelta, and this must be hidden from the
128	command-line user interface. The Xdelta-1.x encoding was simple, not
129	compressed itself, so Xdelta-1.x uses Zlib internally to compress the
130	representation.
131
132	This implementation supports external compression, which implements
133	the necessary fork() and pipe() mechanics. There is a tricky step
134	involved to support automatic detection of a compressed input in a
135	non-seekable input. First you read a bit of the input to detect
136	magic headers. When a compressed format is recognized, exec() the
137	external compression program and create a second child process to
138	copy the original input stream. [Footnote: There is a difficulty
139	related to using Gzip externally. It is not possible to decompress
140	and recompress a Gzip file transparently. If FILE.GZ had a
141	cryptographic signature, then, after: (1) Gzip-decompression, (2)
142	Xdelta-encoding, (3) Gzip-compression the signature could be
143	broken. The only way to solve this problem is to guess at Gzip's
144	compression level or control it by other means. I recommend that
145	specific implementations of any compression scheme store
146	information needed to exactly re-compress the input, that way
147	external compression is transparent - however, this won't happen
148	here until it has stabilized.]
149
150	2. APPLICATION-HEADER
151
152	This feature was introduced in RFC3284. It allows any application
153	to include a header within the VCDIFF file format. This allows
154	general inter-application data exchange with support for
155	application-specific extensions to communicate metadata.
156
157	3. VCDIFF CHECKSUM
158
159	An optional checksum value is included with each window, which can
160	be used to validate the final result. This verifies the correct source
161	file was used for decompression as well as the obvious advantage:
162	checking the implementation (and underlying) correctness.
163
164	4. LIGHT WEIGHT
165
166	The code makes efforts to avoid copying data more than necessary.
167	The code delays many initialization tasks until the first use, it
168	optimizes for identical (perfectly matching) inputs. It does not
169	compute any checksums until the first lookup misses. Memory usage
170	is reduced. String-matching is templatized (by slightly gross use
171	of CPP) to hard-code alternative compile-time defaults. The code
172	has few outside dependencies.
173	----------------------------------------------------------------------
174
175	The default rfc3284 instruction table:
176	(see RFC for the explanation)
177
178	TYPE SIZE MODE TYPE SIZE MODE INDEX
179	--------------------------------------------------------------------
180	1. Run 0 0 Noop 0 0 0
181	2. Add 0, [1,17] 0 Noop 0 0 [1,18]
182	3. Copy 0, [4,18] 0 Noop 0 0 [19,34]
183	4. Copy 0, [4,18] 1 Noop 0 0 [35,50]
184	5. Copy 0, [4,18] 2 Noop 0 0 [51,66]
185	6. Copy 0, [4,18] 3 Noop 0 0 [67,82]
186	7. Copy 0, [4,18] 4 Noop 0 0 [83,98]
187	8. Copy 0, [4,18] 5 Noop 0 0 [99,114]
188	9. Copy 0, [4,18] 6 Noop 0 0 [115,130]
189	10. Copy 0, [4,18] 7 Noop 0 0 [131,146]
190	11. Copy 0, [4,18] 8 Noop 0 0 [147,162]
191	12. Add [1,4] 0 Copy [4,6] 0 [163,174]
192	13. Add [1,4] 0 Copy [4,6] 1 [175,186]
193	14. Add [1,4] 0 Copy [4,6] 2 [187,198]
194	15. Add [1,4] 0 Copy [4,6] 3 [199,210]
195	16. Add [1,4] 0 Copy [4,6] 4 [211,222]
196	17. Add [1,4] 0 Copy [4,6] 5 [223,234]
197	18. Add [1,4] 0 Copy 4 6 [235,238]
198	19. Add [1,4] 0 Copy 4 7 [239,242]
199	20. Add [1,4] 0 Copy 4 8 [243,246]
200	21. Copy 4 [0,8] Add 1 0 [247,255]
201	--------------------------------------------------------------------
202
203	Reading the source: Overview
204
205	This file includes itself in several passes to macro-expand certain
206	sections with variable forms. Just read ahead, there's only a
207	little confusion. I know this sounds ugly, but hard-coding some of
208	the string-matching parameters results in a 10-15% increase in
209	string-match performance. The only time this hurts is when you have
210	unbalanced #if/endifs.
211
212	A single compilation unit tames the Makefile. In short, this is to
213	allow the above-described hack without an explodingMakefile. The
214	single compilation unit includes the core library features,
215	configurable string-match templates, optional main() command-line
216	tool, misc optional features, and a regression test. Features are
217	controled with CPP #defines, see Makefile.am.
218
219	The initial __XDELTA3_C_HEADER_PASS__ starts first, the _INLINE_ and
220	_TEMPLATE_ sections follow. Easy stuff first, hard stuff last.
221
222	Optional features include:
223
224	xdelta3-main.h The command-line interface, external compression
225	support, POSIX-specific, info & VCDIFF-debug tools.
226	xdelta3-second.h The common secondary compression routines.
227	xdelta3-decoder.h All decoding routines.
228	xdelta3-djw.h The semi-adaptive huffman secondary encoder.
229	xdelta3-fgk.h The adaptive huffman secondary encoder.
230	xdelta3-test.h The unit test covers major algorithms,
231	encoding and decoding. There are single-bit
232	error decoding tests. There are 32/64-bit file size
233	boundary tests. There are command-line tests.
234	There are compression tests. There are external
235	compression tests. There are string-matching tests.
236	There should be more tests...
237
238	Additional headers include:
239
240	xdelta3.h The public header file.
241	xdelta3-cfgs.h The default settings for default, built-in
242	encoders. These are hard-coded at
243	compile-time. There is also a single
244	soft-coded string matcher for experimenting
245	with arbitrary values.
246	xdelta3-list.h A cyclic list template
247
248	Misc little debug utilities:
249
250	badcopy.c Randomly modifies an input file based on two
251	parameters: (1) the probability that a byte in
252	the file is replaced with a pseudo-random value,
253	and (2) the mean change size. Changes are
254	generated using an expoential distribution
255	which approximates the expected error_prob
256	distribution.
257	--------------------------------------------------------------------
258
259	This file itself is unusually large. I hope to defend this layout
260	with lots of comments. Everything in this file is related to
261	encoding and decoding. I like it all together - the template stuff
262	is just a hack. */
263
264	#ifndef __XDELTA3_C_HEADER_PASS__
265	#define __XDELTA3_C_HEADER_PASS__
266
267	#include "xdelta3.h"
268
269	/***********************************************************************
270	STATIC CONFIGURATION
271	***********************************************************************/
272
273	#ifndef XD3_MAIN /* the main application */
274	#define XD3_MAIN 0
275	#endif
276
277	#ifndef VCDIFF_TOOLS
278	#define VCDIFF_TOOLS XD3_MAIN
279	#endif
280
281	#ifndef SECONDARY_FGK /* one from the algorithm preservation department: */
282	#define SECONDARY_FGK 0 /* adaptive Huffman routines */
283	#endif
284
285	#ifndef SECONDARY_DJW /* semi-adaptive/static Huffman for the eventual */
286	#define SECONDARY_DJW 0 /* standardization, off by default until such time. */
287	#endif
288
289	#ifdef HAVE_LZMA_H
290	#define SECONDARY_LZMA 1
291	#else
292	#define SECONDARY_LZMA 0
293	#endif
294
295	#ifndef GENERIC_ENCODE_TABLES /* These three are the RFC-spec app-specific */
296	#define GENERIC_ENCODE_TABLES 0 /* code features. This is tested but not */
297	#endif /* recommended unless there's a real use. */
298	#ifndef GENERIC_ENCODE_TABLES_COMPUTE
299	#define GENERIC_ENCODE_TABLES_COMPUTE 0
300	#endif
301	#ifndef GENERIC_ENCODE_TABLES_COMPUTE_PRINT
302	#define GENERIC_ENCODE_TABLES_COMPUTE_PRINT 0
303	#endif
304
305	#if XD3_ENCODER
306	#define IF_ENCODER(x) x
307	#else
308	#define IF_ENCODER(x)
309	#endif
310
311	/***********************************************************************/
312
313	/* header indicator bits */
314	#define VCD_SECONDARY (1U << 0) /* uses secondary compressor */
315	#define VCD_CODETABLE (1U << 1) /* supplies code table data */
316	#define VCD_APPHEADER (1U << 2) /* supplies application data */
317	#define VCD_INVHDR (~0x7U)
318
319	/* window indicator bits */
320	#define VCD_SOURCE (1U << 0) /* copy window in source file */
321	#define VCD_TARGET (1U << 1) /* copy window in target file */
322	#define VCD_ADLER32 (1U << 2) /* has adler32 checksum */
323	#define VCD_INVWIN (~0x7U)
324
325	#define VCD_SRCORTGT (VCD_SOURCE \| VCD_TARGET)
326
327	/* delta indicator bits */
328	#define VCD_DATACOMP (1U << 0)
329	#define VCD_INSTCOMP (1U << 1)
330	#define VCD_ADDRCOMP (1U << 2)
331	#define VCD_INVDEL (~0x7U)
332
333	typedef enum {
334	VCD_DJW_ID = 1,
335	VCD_LZMA_ID = 2,
336	VCD_FGK_ID = 16 /* Note: these are not standard IANA-allocated IDs! */
337	} xd3_secondary_ids;
338
339	typedef enum {
340	SEC_NOFLAGS = 0,
341
342	/* Note: SEC_COUNT_FREQS Not implemented (to eliminate 1st Huffman pass) */
343	SEC_COUNT_FREQS = (1 << 0)
344	} xd3_secondary_flags;
345
346	typedef enum {
347	DATA_SECTION, /* These indicate which section to the secondary
348	* compressor. */
349	INST_SECTION, /* The header section is not compressed, therefore not
350	* listed here. */
351	ADDR_SECTION
352	} xd3_section_type;
353
354	typedef unsigned int xd3_rtype;
355
356	/***********************************************************************/
357
358	#include "xdelta3-list.h"
359
360	XD3_MAKELIST(xd3_rlist, xd3_rinst, link);
361
362	/***********************************************************************/
363
364	#define SECONDARY_MIN_SAVINGS 2 /* Secondary compression has to save
365	at least this many bytes. */
366	#define SECONDARY_MIN_INPUT 10 /* Secondary compression needs at
367	least this many bytes. */
368
369	#define VCDIFF_MAGIC1 0xd6 /* 1st file byte */
370	#define VCDIFF_MAGIC2 0xc3 /* 2nd file byte */
371	#define VCDIFF_MAGIC3 0xc4 /* 3rd file byte */
372	#define VCDIFF_VERSION 0x00 /* 4th file byte */
373
374	#define VCD_SELF 0 /* 1st address mode */
375	#define VCD_HERE 1 /* 2nd address mode */
376
377	#define CODE_TABLE_STRING_SIZE (6 * 256) /* Should fit a code table string. */
378	#define CODE_TABLE_VCDIFF_SIZE (6 * 256) /* Should fit a compressed code
379	* table string */
380
381	#define SECONDARY_ANY (SECONDARY_DJW \|\| SECONDARY_FGK \|\| SECONDARY_LZMA)
382
383	#define ALPHABET_SIZE 256 /* Used in test code--size of the secondary
384	* compressor alphabet. */
385
386	#define HASH_PERMUTE 1 /* The input is permuted by random nums */
387	#define ADLER_LARGE_CKSUM 1 /* Adler checksum vs. RK checksum */
388
389	#define HASH_CKOFFSET 1U /* Table entries distinguish "no-entry" from
390	* offset 0 using this offset. */
391
392	#define MIN_SMALL_LOOK 2U /* Match-optimization stuff. */
393	#define MIN_LARGE_LOOK 2U
394	#define MIN_MATCH_OFFSET 1U
395	#define MAX_MATCH_SPLIT 18U /* VCDIFF code table: 18 is the default limit
396	* for direct-coded ADD sizes */
397
398	#define LEAST_MATCH_INCR 0 /* The least number of bytes an overlapping
399	* match must beat the preceding match by. This
400	* is a bias for the lazy match optimization. A
401	* non-zero value means that an adjacent match
402	* has to be better by more than the step
403	* between them. 0. */
404
405	#define MIN_MATCH 4U /* VCDIFF code table: MIN_MATCH=4 */
406	#define MIN_ADD 1U /* 1 */
407	#define MIN_RUN 8U /* The shortest run, if it is shorter than this
408	* an immediate add/copy will be just as good.
409	* ADD1/COPY6 = 1I+1D+1A bytes, RUN18 =
410	* 1I+1D+1A. */
411
412	#define MAX_MODES 9 /* Maximum number of nodes used for
413	* compression--does not limit decompression. */
414
415	#define ENC_SECTS 4 /* Number of separate output sections. */
416
417	#define HDR_TAIL(s) ((s)->enc_tails[0])
418	#define DATA_TAIL(s) ((s)->enc_tails[1])
419	#define INST_TAIL(s) ((s)->enc_tails[2])
420	#define ADDR_TAIL(s) ((s)->enc_tails[3])
421
422	#define HDR_HEAD(s) ((s)->enc_heads[0])
423	#define DATA_HEAD(s) ((s)->enc_heads[1])
424	#define INST_HEAD(s) ((s)->enc_heads[2])
425	#define ADDR_HEAD(s) ((s)->enc_heads[3])
426
427	#define TOTAL_MODES(x) (2+(x)->acache.s_same+(x)->acache.s_near)
428
429	/* Template instances. */
430	#if XD3_BUILD_SLOW
431	#define IF_BUILD_SLOW(x) x
432	#else
433	#define IF_BUILD_SLOW(x)
434	#endif
435	#if XD3_BUILD_FAST
436	#define IF_BUILD_FAST(x) x
437	#else
438	#define IF_BUILD_FAST(x)
439	#endif
440	#if XD3_BUILD_FASTER
441	#define IF_BUILD_FASTER(x) x
442	#else
443	#define IF_BUILD_FASTER(x)
444	#endif
445	#if XD3_BUILD_FASTEST
446	#define IF_BUILD_FASTEST(x) x
447	#else
448	#define IF_BUILD_FASTEST(x)
449	#endif
450	#if XD3_BUILD_SOFT
451	#define IF_BUILD_SOFT(x) x
452	#else
453	#define IF_BUILD_SOFT(x)
454	#endif
455	#if XD3_BUILD_DEFAULT
456	#define IF_BUILD_DEFAULT(x) x
457	#else
458	#define IF_BUILD_DEFAULT(x)
459	#endif
460
461	/* Consume N bytes of input, only used by the decoder. */
462	#define DECODE_INPUT(n) \
463	do { \
464	stream->total_in += (xoff_t) (n); \
465	stream->avail_in -= (n); \
466	stream->next_in += (n); \
467	} while (0)
468
469	/* Update the run-length state */
470	#define NEXTRUN(c) do { if ((c) == run_c) { run_l += 1; } \
471	else { run_c = (c); run_l = 1; } } while (0)
472
473	/* This CPP-conditional stuff can be cleaned up... */
474	#if REGRESSION_TEST
475	#define IF_REGRESSION(x) x
476	#else
477	#define IF_REGRESSION(x)
478	#endif
479
480	/***********************************************************************/
481
482	#if XD3_ENCODER
483	static void* xd3_alloc0 (xd3_stream *stream,
484	usize_t elts,
485	usize_t size);
486
487
488	static xd3_output* xd3_alloc_output (xd3_stream *stream,
489	xd3_output *old_output);
490
491	static int xd3_alloc_iopt (xd3_stream *stream, usize_t elts);
492
493	static void xd3_free_output (xd3_stream *stream,
494	xd3_output *output);
495
496	static int xd3_emit_byte (xd3_stream *stream,
497	xd3_output **outputp,
498	uint8_t code);
499
500	static int xd3_emit_bytes (xd3_stream *stream,
501	xd3_output **outputp,
502	const uint8_t *base,
503	usize_t size);
504
505	static int xd3_emit_double (xd3_stream stream, xd3_rinst first,
506	xd3_rinst *second, usize_t code);
507	static int xd3_emit_single (xd3_stream stream, xd3_rinst single,
508	usize_t code);
509
510	static usize_t xd3_sizeof_output (xd3_output *output);
511	static void xd3_encode_reset (xd3_stream *stream);
512
513	static int xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos);
514	static int xd3_source_extend_match (xd3_stream *stream);
515	static int xd3_srcwin_setup (xd3_stream *stream);
516	static usize_t xd3_iopt_last_matched (xd3_stream *stream);
517	static int xd3_emit_uint32_t (xd3_stream stream, xd3_output *output,
518	uint32_t num);
519
520	static usize_t xd3_smatch (xd3_stream *stream,
521	usize_t base,
522	usize_t scksum,
523	usize_t *match_offset);
524	static int xd3_string_match_init (xd3_stream *stream);
525	static uint32_t xd3_scksum (uint32_t state, const uint8_t seg,
526	const usize_t ln);
527	static usize_t xd3_comprun (const uint8_t seg, usize_t slook, uint8_t run_cp);
528	static int xd3_srcwin_move_point (xd3_stream *stream,
529	usize_t *next_move_point);
530
531	static int xd3_emit_run (xd3_stream *stream, usize_t pos,
532	usize_t size, uint8_t *run_c);
533	static usize_t xd3_checksum_hash (const xd3_hash_cfg *cfg,
534	const usize_t cksum);
535	static xoff_t xd3_source_cksum_offset(xd3_stream *stream, usize_t low);
536	static void xd3_scksum_insert (xd3_stream *stream,
537	usize_t inx,
538	usize_t scksum,
539	usize_t pos);
540
541
542	#if XD3_DEBUG
543	static void xd3_verify_run_state (xd3_stream *stream,
544	const uint8_t *inp,
545	usize_t x_run_l,
546	uint8_t *x_run_c);
547	static void xd3_verify_large_state (xd3_stream *stream,
548	const uint8_t *inp,
549	uint32_t x_cksum);
550	static void xd3_verify_small_state (xd3_stream *stream,
551	const uint8_t *inp,
552	uint32_t x_cksum);
553
554	#endif /* XD3_DEBUG */
555	#endif /* XD3_ENCODER */
556
557	static int xd3_decode_allocate (xd3_stream *stream, usize_t size,
558	uint8_t *copied1, usize_t alloc1);
559
560	static void xd3_compute_code_table_string (const xd3_dinst *code_table,
561	uint8_t *str);
562	static void* xd3_alloc (xd3_stream *stream, usize_t elts, usize_t size);
563	static void xd3_free (xd3_stream stream, void ptr);
564
565	static int xd3_read_uint32_t (xd3_stream stream, const uint8_t *inpp,
566	const uint8_t max, uint32_t valp);
567
568	#if REGRESSION_TEST
569	static int xd3_selftest (void);
570	#endif
571
572	/***********************************************************************/
573
574	#define UINT32_OFLOW_MASK 0xfe000000U
575	#define UINT64_OFLOW_MASK 0xfe00000000000000ULL
576
577	#if SIZEOF_USIZE_T == 4
578	#define USIZE_T_MAX UINT32_MAX
579	#define xd3_decode_size xd3_decode_uint32_t
580	#define xd3_emit_size xd3_emit_uint32_t
581	#define xd3_sizeof_size xd3_sizeof_uint32_t
582	#define xd3_read_size xd3_read_uint32_t
583	#elif SIZEOF_USIZE_T == 8
584	#define USIZE_T_MAX UINT64_MAX
585	#define xd3_decode_size xd3_decode_uint64_t
586	#define xd3_emit_size xd3_emit_uint64_t
587	#define xd3_sizeof_size xd3_sizeof_uint64_t
588	#define xd3_read_size xd3_read_uint64_t
589	#endif
590
591	#if SIZEOF_XOFF_T == 4
592	#define XOFF_T_MAX UINT32_MAX
593	#define xd3_decode_offset xd3_decode_uint32_t
594	#define xd3_emit_offset xd3_emit_uint32_t
595	#elif SIZEOF_XOFF_T == 8
596	#define XOFF_T_MAX UINT64_MAX
597	#define xd3_decode_offset xd3_decode_uint64_t
598	#define xd3_emit_offset xd3_emit_uint64_t
599	#endif
600
601	#define USIZE_T_OVERFLOW(a,b) ((USIZE_T_MAX - (usize_t) (a)) < (usize_t) (b))
602	#define XOFF_T_OVERFLOW(a,b) ((XOFF_T_MAX - (xoff_t) (a)) < (xoff_t) (b))
603
604	const char* xd3_strerror (int ret)
605	{
606	switch (ret)
607	{
608	case XD3_INPUT: return "XD3_INPUT";
609	case XD3_OUTPUT: return "XD3_OUTPUT";
610	case XD3_GETSRCBLK: return "XD3_GETSRCBLK";
611	case XD3_GOTHEADER: return "XD3_GOTHEADER";
612	case XD3_WINSTART: return "XD3_WINSTART";
613	case XD3_WINFINISH: return "XD3_WINFINISH";
614	case XD3_TOOFARBACK: return "XD3_TOOFARBACK";
615	case XD3_INTERNAL: return "XD3_INTERNAL";
616	case XD3_INVALID: return "XD3_INVALID";
617	case XD3_INVALID_INPUT: return "XD3_INVALID_INPUT";
618	case XD3_NOSECOND: return "XD3_NOSECOND";
619	case XD3_UNIMPLEMENTED: return "XD3_UNIMPLEMENTED";
620	}
621	return NULL;
622	}
623
624	/***********************************************************************/
625
626	#define xd3_sec_data(s) ((s)->sec_stream_d)
627	#define xd3_sec_inst(s) ((s)->sec_stream_i)
628	#define xd3_sec_addr(s) ((s)->sec_stream_a)
629
630	struct _xd3_sec_type
631	{
632	int id;
633	const char *name;
634	xd3_secondary_flags flags;
635
636	/* xd3_sec_stream is opaque to the generic code */
637	xd3_sec_stream* (alloc) (xd3_stream stream);
638	void (destroy) (xd3_stream stream,
639	xd3_sec_stream *sec);
640	int (init) (xd3_stream stream,
641	xd3_sec_stream *sec_stream,
642	int is_encode);
643	int (decode) (xd3_stream stream,
644	xd3_sec_stream *sec_stream,
645	const uint8_t **input,
646	const uint8_t *input_end,
647	uint8_t **output,
648	const uint8_t *output_end);
649	#if XD3_ENCODER
650	int (encode) (xd3_stream stream,
651	xd3_sec_stream *sec_stream,
652	xd3_output *input,
653	xd3_output *output,
654	xd3_sec_cfg *cfg);
655	#endif
656	};
657
658	#define BIT_STATE_ENCODE_INIT { 0, 1 }
659	#define BIT_STATE_DECODE_INIT { 0, 0x100 }
660
661	typedef struct _bit_state bit_state;
662	struct _bit_state
663	{
664	usize_t cur_byte;
665	usize_t cur_mask;
666	};
667
668	#if SECONDARY_ANY == 0
669	#define IF_SEC(x)
670	#define IF_NSEC(x) x
671	#else /* yuck */
672	#define IF_SEC(x) x
673	#define IF_NSEC(x)
674	static int
675	xd3_decode_secondary (xd3_stream *stream,
676	xd3_desect *sect,
677	xd3_sec_stream **sec_streamp);
678	#if XD3_ENCODER
679	static int
680	xd3_encode_secondary (xd3_stream *stream,
681	xd3_output **head,
682	xd3_output **tail,
683	xd3_sec_stream **sec_streamp,
684	xd3_sec_cfg *cfg,
685	int *did_it);
686	#endif
687	#endif /* SECONDARY_ANY */
688
689	#if SECONDARY_FGK
690	extern const xd3_sec_type fgk_sec_type;
691	#define IF_FGK(x) x
692	#define FGK_CASE(s) \
693	s->sec_type = & fgk_sec_type; \
694	break;
695	#else
696	#define IF_FGK(x)
697	#define FGK_CASE(s) \
698	s->msg = "unavailable secondary compressor: FGK Adaptive Huffman"; \
699	return XD3_INTERNAL;
700	#endif
701
702	#if SECONDARY_DJW
703	extern const xd3_sec_type djw_sec_type;
704	#define IF_DJW(x) x
705	#define DJW_CASE(s) \
706	s->sec_type = & djw_sec_type; \
707	break;
708	#else
709	#define IF_DJW(x)
710	#define DJW_CASE(s) \
711	s->msg = "unavailable secondary compressor: DJW Static Huffman"; \
712	return XD3_INTERNAL;
713	#endif
714
715	#if SECONDARY_LZMA
716	extern const xd3_sec_type lzma_sec_type;
717	#define IF_LZMA(x) x
718	#define LZMA_CASE(s) \
719	s->sec_type = & lzma_sec_type; \
720	break;
721	#else
722	#define IF_LZMA(x)
723	#define LZMA_CASE(s) \
724	s->msg = "unavailable secondary compressor: LZMA"; \
725	return XD3_INTERNAL;
726	#endif
727
728	/***********************************************************************/
729
730	#include "xdelta3-hash.h"
731
732	/* Process template passes - this includes xdelta3.c several times. */
733	#define __XDELTA3_C_TEMPLATE_PASS__
734	#include "xdelta3-cfgs.h"
735	#undef __XDELTA3_C_TEMPLATE_PASS__
736
737	/* Process the inline pass. */
738	#define __XDELTA3_C_INLINE_PASS__
739	#include "xdelta3.c"
740	#undef __XDELTA3_C_INLINE_PASS__
741
742	/* Secondary compression */
743	#if SECONDARY_ANY
744	#include "xdelta3-second.h"
745	#endif
746
747	#if SECONDARY_FGK
748	#include "xdelta3-fgk.h"
749	const xd3_sec_type fgk_sec_type =
750	{
751	VCD_FGK_ID,
752	"FGK Adaptive Huffman",
753	SEC_NOFLAGS,
754	(xd3_sec_stream* ()(xd3_stream)) fgk_alloc,
755	(void ()(xd3_stream, xd3_sec_stream*)) fgk_destroy,
756	(int ()(xd3_stream, xd3_sec_stream*, int)) fgk_init,
757	(int ()(xd3_stream, xd3_sec_stream, const uint8_t, const uint8_t,
758	uint8_t*, const uint8_t)) xd3_decode_fgk,
759	IF_ENCODER((int ()(xd3_stream, xd3_sec_stream, xd3_output,
760	xd3_output, xd3_sec_cfg)) xd3_encode_fgk)
761	};
762	#endif
763
764	#if SECONDARY_DJW
765	#include "xdelta3-djw.h"
766	const xd3_sec_type djw_sec_type =
767	{
768	VCD_DJW_ID,
769	"Static Huffman",
770	SEC_COUNT_FREQS,
771	(xd3_sec_stream* ()(xd3_stream)) djw_alloc,
772	(void ()(xd3_stream, xd3_sec_stream*)) djw_destroy,
773	(int ()(xd3_stream, xd3_sec_stream*, int)) djw_init,
774	(int ()(xd3_stream, xd3_sec_stream, const uint8_t, const uint8_t,
775	uint8_t*, const uint8_t)) xd3_decode_huff,
776	IF_ENCODER((int ()(xd3_stream, xd3_sec_stream, xd3_output,
777	xd3_output, xd3_sec_cfg)) xd3_encode_huff)
778	};
779	#endif
780
781	#if SECONDARY_LZMA
782	#include "xdelta3-lzma.h"
783	const xd3_sec_type lzma_sec_type =
784	{
785	VCD_LZMA_ID,
786	"lzma",
787	SEC_NOFLAGS,
788	(xd3_sec_stream* ()(xd3_stream)) xd3_lzma_alloc,
789	(void ()(xd3_stream, xd3_sec_stream*)) xd3_lzma_destroy,
790	(int ()(xd3_stream, xd3_sec_stream*, int)) xd3_lzma_init,
791	(int ()(xd3_stream, xd3_sec_stream, const uint8_t, const uint8_t,
792	uint8_t*, const uint8_t)) xd3_decode_lzma,
793	IF_ENCODER((int ()(xd3_stream, xd3_sec_stream, xd3_output,
794	xd3_output, xd3_sec_cfg)) xd3_encode_lzma)
795	};
796	#endif
797
798	#if XD3_MAIN \|\| PYTHON_MODULE \|\| SWIG_MODULE \|\| NOT_MAIN
799	#include "xdelta3-main.h"
800	#endif
801
802	#if REGRESSION_TEST
803	#include "xdelta3-test.h"
804	#endif
805
806	#endif /* __XDELTA3_C_HEADER_PASS__ */
807	#ifdef __XDELTA3_C_INLINE_PASS__
808
809	const uint16_t __single_hash[256] =
810	{
811	/* Random numbers generated using SLIB's pseudo-random number generator.
812	* This hashes the input alphabet. */
813	0xbcd1, 0xbb65, 0x42c2, 0xdffe, 0x9666, 0x431b, 0x8504, 0xeb46,
814	0x6379, 0xd460, 0xcf14, 0x53cf, 0xdb51, 0xdb08, 0x12c8, 0xf602,
815	0xe766, 0x2394, 0x250d, 0xdcbb, 0xa678, 0x02af, 0xa5c6, 0x7ea6,
816	0xb645, 0xcb4d, 0xc44b, 0xe5dc, 0x9fe6, 0x5b5c, 0x35f5, 0x701a,
817	0x220f, 0x6c38, 0x1a56, 0x4ca3, 0xffc6, 0xb152, 0x8d61, 0x7a58,
818	0x9025, 0x8b3d, 0xbf0f, 0x95a3, 0xe5f4, 0xc127, 0x3bed, 0x320b,
819	0xb7f3, 0x6054, 0x333c, 0xd383, 0x8154, 0x5242, 0x4e0d, 0x0a94,
820	0x7028, 0x8689, 0x3a22, 0x0980, 0x1847, 0xb0f1, 0x9b5c, 0x4176,
821	0xb858, 0xd542, 0x1f6c, 0x2497, 0x6a5a, 0x9fa9, 0x8c5a, 0x7743,
822	0xa8a9, 0x9a02, 0x4918, 0x438c, 0xc388, 0x9e2b, 0x4cad, 0x01b6,
823	0xab19, 0xf777, 0x365f, 0x1eb2, 0x091e, 0x7bf8, 0x7a8e, 0x5227,
824	0xeab1, 0x2074, 0x4523, 0xe781, 0x01a3, 0x163d, 0x3b2e, 0x287d,
825	0x5e7f, 0xa063, 0xb134, 0x8fae, 0x5e8e, 0xb7b7, 0x4548, 0x1f5a,
826	0xfa56, 0x7a24, 0x900f, 0x42dc, 0xcc69, 0x02a0, 0x0b22, 0xdb31,
827	0x71fe, 0x0c7d, 0x1732, 0x1159, 0xcb09, 0xe1d2, 0x1351, 0x52e9,
828	0xf536, 0x5a4f, 0xc316, 0x6bf9, 0x8994, 0xb774, 0x5f3e, 0xf6d6,
829	0x3a61, 0xf82c, 0xcc22, 0x9d06, 0x299c, 0x09e5, 0x1eec, 0x514f,
830	0x8d53, 0xa650, 0x5c6e, 0xc577, 0x7958, 0x71ac, 0x8916, 0x9b4f,
831	0x2c09, 0x5211, 0xf6d8, 0xcaaa, 0xf7ef, 0x287f, 0x7a94, 0xab49,
832	0xfa2c, 0x7222, 0xe457, 0xd71a, 0x00c3, 0x1a76, 0xe98c, 0xc037,
833	0x8208, 0x5c2d, 0xdfda, 0xe5f5, 0x0b45, 0x15ce, 0x8a7e, 0xfcad,
834	0xaa2d, 0x4b5c, 0xd42e, 0xb251, 0x907e, 0x9a47, 0xc9a6, 0xd93f,
835	0x085e, 0x35ce, 0xa153, 0x7e7b, 0x9f0b, 0x25aa, 0x5d9f, 0xc04d,
836	0x8a0e, 0x2875, 0x4a1c, 0x295f, 0x1393, 0xf760, 0x9178, 0x0f5b,
837	0xfa7d, 0x83b4, 0x2082, 0x721d, 0x6462, 0x0368, 0x67e2, 0x8624,
838	0x194d, 0x22f6, 0x78fb, 0x6791, 0xb238, 0xb332, 0x7276, 0xf272,
839	0x47ec, 0x4504, 0xa961, 0x9fc8, 0x3fdc, 0xb413, 0x007a, 0x0806,
840	0x7458, 0x95c6, 0xccaa, 0x18d6, 0xe2ae, 0x1b06, 0xf3f6, 0x5050,
841	0xc8e8, 0xf4ac, 0xc04c, 0xf41c, 0x992f, 0xae44, 0x5f1b, 0x1113,
842	0x1738, 0xd9a8, 0x19ea, 0x2d33, 0x9698, 0x2fe9, 0x323f, 0xcde2,
843	0x6d71, 0xe37d, 0xb697, 0x2c4f, 0x4373, 0x9102, 0x075d, 0x8e25,
844	0x1672, 0xec28, 0x6acb, 0x86cc, 0x186e, 0x9414, 0xd674, 0xd1a5
845	};
846
847	/****************************************************************
848	Instruction tables
849	*****************************************************************/
850
851	/* The following code implements a parametrized description of the
852	* code table given above for a few reasons. It is not necessary for
853	* implementing the standard, to support compression with variable
854	* tables, so an implementation is only required to know the default
855	* code table to begin decompression. (If the encoder uses an
856	* alternate table, the table is included in compressed form inside
857	* the VCDIFF file.)
858	*
859	* Before adding variable-table support there were two functions which
860	* were hard-coded to the default table above.
861	* xd3_compute_default_table() would create the default table by
862	* filling a 256-elt array of xd3_dinst values. The corresponding
863	* function, xd3_choose_instruction(), would choose an instruction
864	* based on the hard-coded parameters of the default code table.
865	*
866	* Notes: The parametrized code table description here only generates
867	* tables of a certain regularity similar to the default table by
868	* allowing to vary the distribution of single- and
869	* double-instructions and change the number of near and same copy
870	* modes. More exotic tables are only possible by extending this
871	* code.
872	*
873	* For performance reasons, both the parametrized and non-parametrized
874	* versions of xd3_choose_instruction remain. The parametrized
875	* version is only needed for testing multi-table decoding support.
876	* If ever multi-table encoding is required, this can be optimized by
877	* compiling static functions for each table.
878	*/
879
880	/* The XD3_CHOOSE_INSTRUCTION calls xd3_choose_instruction with the
881	* table description when GENERIC_ENCODE_TABLES are in use. The
882	* IF_GENCODETBL macro enables generic-code-table specific code. */
883	#if GENERIC_ENCODE_TABLES
884	#define XD3_CHOOSE_INSTRUCTION(stream,prev,inst) xd3_choose_instruction (stream->code_table_desc, prev, inst)
885	#define IF_GENCODETBL(x) x
886	#else
887	#define XD3_CHOOSE_INSTRUCTION(stream,prev,inst) xd3_choose_instruction (prev, inst)
888	#define IF_GENCODETBL(x)
889	#endif
890
891	/* This structure maintains information needed by
892	* xd3_choose_instruction to compute the code for a double instruction
893	* by first indexing an array of code_table_sizes by copy mode, then
894	* using (offset + (muliplier * X)) */
895	struct _xd3_code_table_sizes {
896	uint8_t cpy_max;
897	uint8_t offset;
898	uint8_t mult;
899	};
900
901	/* This contains a complete description of a code table. */
902	struct _xd3_code_table_desc
903	{
904	/* Assumes a single RUN instruction */
905	/* Assumes that MIN_MATCH is 4 */
906
907	uint8_t add_sizes; /* Number of immediate-size single adds (default 17) */
908	uint8_t near_modes; /* Number of near copy modes (default 4) */
909	uint8_t same_modes; /* Number of same copy modes (default 3) */
910	uint8_t cpy_sizes; /* Number of immediate-size single copies (default 15) */
911
912	uint8_t addcopy_add_max; /* Maximum add size for an add-copy double instruction,
913	all modes (default 4) */
914	uint8_t addcopy_near_cpy_max; /* Maximum cpy size for an add-copy double instruction,
915	up through VCD_NEAR modes (default 6) */
916	uint8_t addcopy_same_cpy_max; /* Maximum cpy size for an add-copy double instruction,
917	VCD_SAME modes (default 4) */
918
919	uint8_t copyadd_add_max; /* Maximum add size for a copy-add double instruction,
920	all modes (default 1) */
921	uint8_t copyadd_near_cpy_max; /* Maximum cpy size for a copy-add double instruction,
922	up through VCD_NEAR modes (default 4) */
923	uint8_t copyadd_same_cpy_max; /* Maximum cpy size for a copy-add double instruction,
924	VCD_SAME modes (default 4) */
925
926	xd3_code_table_sizes addcopy_max_sizes[MAX_MODES];
927	xd3_code_table_sizes copyadd_max_sizes[MAX_MODES];
928	};
929
930	/* The rfc3284 code table is represented: */
931	static const xd3_code_table_desc __rfc3284_code_table_desc = {
932	17, /* add sizes */
933	4, /* near modes */
934	3, /* same modes */
935	15, /* copy sizes */
936
937	4, /* add-copy max add */
938	6, /* add-copy max cpy, near */
939	4, /* add-copy max cpy, same */
940
941	1, /* copy-add max add */
942	4, /* copy-add max cpy, near */
943	4, /* copy-add max cpy, same */
944
945	/* addcopy */
946	{ {6,163,3},{6,175,3},{6,187,3},{6,199,3},{6,211,3},{6,223,3},{4,235,1},{4,239,1},{4,243,1} },
947	/* copyadd */
948	{ {4,247,1},{4,248,1},{4,249,1},{4,250,1},{4,251,1},{4,252,1},{4,253,1},{4,254,1},{4,255,1} },
949	};
950
951	#if GENERIC_ENCODE_TABLES
952	/* An alternate code table for testing (5 near, 0 same):
953	*
954	* TYPE SIZE MODE TYPE SIZE MODE INDEX
955	* ---------------------------------------------------------------
956	* 1. Run 0 0 Noop 0 0 0
957	* 2. Add 0, [1,23] 0 Noop 0 0 [1,24]
958	* 3. Copy 0, [4,20] 0 Noop 0 0 [25,42]
959	* 4. Copy 0, [4,20] 1 Noop 0 0 [43,60]
960	* 5. Copy 0, [4,20] 2 Noop 0 0 [61,78]
961	* 6. Copy 0, [4,20] 3 Noop 0 0 [79,96]
962	* 7. Copy 0, [4,20] 4 Noop 0 0 [97,114]
963	* 8. Copy 0, [4,20] 5 Noop 0 0 [115,132]
964	* 9. Copy 0, [4,20] 6 Noop 0 0 [133,150]
965	* 10. Add [1,4] 0 Copy [4,6] 0 [151,162]
966	* 11. Add [1,4] 0 Copy [4,6] 1 [163,174]
967	* 12. Add [1,4] 0 Copy [4,6] 2 [175,186]
968	* 13. Add [1,4] 0 Copy [4,6] 3 [187,198]
969	* 14. Add [1,4] 0 Copy [4,6] 4 [199,210]
970	* 15. Add [1,4] 0 Copy [4,6] 5 [211,222]
971	* 16. Add [1,4] 0 Copy [4,6] 6 [223,234]
972	* 17. Copy 4 [0,6] Add [1,3] 0 [235,255]
973	* --------------------------------------------------------------- */
974	static const xd3_code_table_desc __alternate_code_table_desc = {
975	23, /* add sizes */
976	5, /* near modes */
977	0, /* same modes */
978	17, /* copy sizes */
979
980	4, /* add-copy max add */
981	6, /* add-copy max cpy, near */
982	0, /* add-copy max cpy, same */
983
984	3, /* copy-add max add */
985	4, /* copy-add max cpy, near */
986	0, /* copy-add max cpy, same */
987
988	/* addcopy */
989	{ {6,151,3},{6,163,3},{6,175,3},{6,187,3},{6,199,3},{6,211,3},{6,223,3},{0,0,0},{0,0,0} },
990	/* copyadd */
991	{ {4,235,1},{4,238,1},{4,241,1},{4,244,1},{4,247,1},{4,250,1},{4,253,1},{0,0,0},{0,0,0} },
992	};
993	#endif
994
995	/* Computes code table entries of TBL using the specified description. */
996	static void
997	xd3_build_code_table (const xd3_code_table_desc desc, xd3_dinst tbl)
998	{
999	usize_t size1, size2, mode;
1000	usize_t cpy_modes = 2 + desc->near_modes + desc->same_modes;
1001	xd3_dinst *d = tbl;
1002
1003	(d++)->type1 = XD3_RUN;
1004	(d++)->type1 = XD3_ADD;
1005
1006	for (size1 = 1; size1 <= desc->add_sizes; size1 += 1, d += 1)
1007	{
1008	d->type1 = XD3_ADD;
1009	d->size1 = size1;
1010	}
1011
1012	for (mode = 0; mode < cpy_modes; mode += 1)
1013	{
1014	(d++)->type1 = XD3_CPY + mode;
1015
1016	for (size1 = MIN_MATCH; size1 < MIN_MATCH + desc->cpy_sizes; size1 += 1, d += 1)
1017	{
1018	d->type1 = XD3_CPY + mode;
1019	d->size1 = size1;
1020	}
1021	}
1022
1023	for (mode = 0; mode < cpy_modes; mode += 1)
1024	{
1025	for (size1 = 1; size1 <= desc->addcopy_add_max; size1 += 1)
1026	{
1027	usize_t max = (mode < 2U + desc->near_modes) ?
1028	desc->addcopy_near_cpy_max :
1029	desc->addcopy_same_cpy_max;
1030
1031	for (size2 = MIN_MATCH; size2 <= max; size2 += 1, d += 1)
1032	{
1033	d->type1 = XD3_ADD;
1034	d->size1 = size1;
1035	d->type2 = XD3_CPY + mode;
1036	d->size2 = size2;
1037	}
1038	}
1039	}
1040
1041	for (mode = 0; mode < cpy_modes; mode += 1)
1042	{
1043	usize_t max = (mode < 2U + desc->near_modes) ?
1044	desc->copyadd_near_cpy_max :
1045	desc->copyadd_same_cpy_max;
1046
1047	for (size1 = MIN_MATCH; size1 <= max; size1 += 1)
1048	{
1049	for (size2 = 1; size2 <= desc->copyadd_add_max; size2 += 1, d += 1)
1050	{
1051	d->type1 = XD3_CPY + mode;
1052	d->size1 = size1;
1053	d->type2 = XD3_ADD;
1054	d->size2 = size2;
1055	}
1056	}
1057	}
1058
1059	XD3_ASSERT (d - tbl == 256);
1060	}
1061
1062	/* This function generates the static default code table. */
1063	static const xd3_dinst*
1064	xd3_rfc3284_code_table (void)
1065	{
1066	static xd3_dinst __rfc3284_code_table[256];
1067
1068	if (__rfc3284_code_table[0].type1 != XD3_RUN)
1069	{
1070	xd3_build_code_table (& __rfc3284_code_table_desc, __rfc3284_code_table);
1071	}
1072
1073	return __rfc3284_code_table;
1074	}
1075
1076	#if XD3_ENCODER
1077	#if GENERIC_ENCODE_TABLES
1078	/* This function generates the alternate code table. */
1079	static const xd3_dinst*
1080	xd3_alternate_code_table (void)
1081	{
1082	static xd3_dinst __alternate_code_table[256];
1083
1084	if (__alternate_code_table[0].type1 != XD3_RUN)
1085	{
1086	xd3_build_code_table (& __alternate_code_table_desc, __alternate_code_table);
1087	}
1088
1089	return __alternate_code_table;
1090	}
1091
1092	/* This function computes the ideal second instruction INST based on
1093	* preceding instruction PREV. If it is possible to issue a double
1094	* instruction based on this pair it sets PREV->code2, otherwise it
1095	* sets INST->code1. */
1096	static void
1097	xd3_choose_instruction (const xd3_code_table_desc desc, xd3_rinst prev, xd3_rinst *inst)
1098	{
1099	switch (inst->type)
1100	{
1101	case XD3_RUN:
1102	/* The 0th instruction is RUN */
1103	inst->code1 = 0;
1104	break;
1105
1106	case XD3_ADD:
1107
1108	if (inst->size > desc->add_sizes)
1109	{
1110	/* The first instruction is non-immediate ADD */
1111	inst->code1 = 1;
1112	}
1113	else
1114	{
1115	/* The following ADD_SIZES instructions are immediate ADDs */
1116	inst->code1 = 1 + inst->size;
1117
1118	/* Now check for a possible COPY-ADD double instruction */
1119	if (prev != NULL)
1120	{
1121	int prev_mode = prev->type - XD3_CPY;
1122
1123	/* If previous is a copy. Note: as long as the previous
1124	* is not a RUN instruction, it should be a copy because
1125	* it cannot be an add. This check is more clear. */
1126	if (prev_mode >= 0 && inst->size <= desc->copyadd_add_max)
1127	{
1128	const xd3_code_table_sizes *sizes = & desc->copyadd_max_sizes[prev_mode];
1129
1130	/* This check and the inst->size-<= above are == in
1131	the default table. */
1132	if (prev->size <= sizes->cpy_max)
1133	{
1134	/* The second and third exprs are 0 in the
1135	default table. */
1136	prev->code2 = sizes->offset +
1137	(sizes->mult * (prev->size - MIN_MATCH)) +
1138	(inst->size - MIN_ADD);
1139	}
1140	}
1141	}
1142	}
1143	break;
1144
1145	default:
1146	{
1147	int mode = inst->type - XD3_CPY;
1148
1149	/* The large copy instruction is offset by the run, large add,
1150	* and immediate adds, then multipled by the number of
1151	* immediate copies plus one (the large copy) (i.e., if there
1152	* are 15 immediate copy instructions then there are 16 copy
1153	* instructions per mode). */
1154	inst->code1 = 2 + desc->add_sizes + (1 + desc->cpy_sizes) * mode;
1155
1156	/* Now if the copy is short enough for an immediate instruction. */
1157	if (inst->size < MIN_MATCH + desc->cpy_sizes &&
1158	/* TODO: there needs to be a more comprehensive test for this
1159	* boundary condition, merge is now exercising code in which
1160	* size < MIN_MATCH is possible and it's unclear if the above
1161	* size < (MIN_MATCH + cpy_sizes) should be a <= from inspection
1162	* of the default table version below. */
1163	inst->size >= MIN_MATCH)
1164	{
1165	inst->code1 += inst->size + 1 - MIN_MATCH;
1166
1167	/* Now check for a possible ADD-COPY double instruction. */
1168	if ( (prev != NULL) &&
1169	(prev->type == XD3_ADD) &&
1170	(prev->size <= desc->addcopy_add_max) )
1171	{
1172	const xd3_code_table_sizes *sizes = & desc->addcopy_max_sizes[mode];
1173
1174	if (inst->size <= sizes->cpy_max)
1175	{
1176	prev->code2 = sizes->offset +
1177	(sizes->mult * (prev->size - MIN_ADD)) +
1178	(inst->size - MIN_MATCH);
1179	}
1180	}
1181	}
1182	}
1183	}
1184	}
1185	#else /* GENERIC_ENCODE_TABLES */
1186
1187	/* This version of xd3_choose_instruction is hard-coded for the default
1188	table. */
1189	static void
1190	xd3_choose_instruction (xd3_rinst prev, xd3_rinst inst)
1191	{
1192	switch (inst->type)
1193	{
1194	case XD3_RUN:
1195	inst->code1 = 0;
1196	break;
1197
1198	case XD3_ADD:
1199	inst->code1 = 1;
1200
1201	if (inst->size <= 17)
1202	{
1203	inst->code1 += inst->size;
1204
1205	if ( (inst->size == 1) &&
1206	(prev != NULL) &&
1207	(prev->size == 4) &&
1208	(prev->type >= XD3_CPY) )
1209	{
1210	prev->code2 = 247 + (prev->type - XD3_CPY);
1211	}
1212	}
1213
1214	break;
1215
1216	default:
1217	{
1218	int mode = inst->type - XD3_CPY;
1219
1220	XD3_ASSERT (inst->type >= XD3_CPY && inst->type < 12);
1221
1222	inst->code1 = 19 + 16 * mode;
1223
1224	if (inst->size <= 18 && inst->size >= 4)
1225	{
1226	inst->code1 += inst->size - 3;
1227
1228	if ( (prev != NULL) &&
1229	(prev->type == XD3_ADD) &&
1230	(prev->size <= 4) )
1231	{
1232	if ( (inst->size <= 6) &&
1233	(mode <= 5) )
1234	{
1235	prev->code2 = 163 + (mode * 12) + (3 * (prev->size - 1)) + (inst->size - 4);
1236
1237	XD3_ASSERT (prev->code2 <= 234);
1238	}
1239	else if ( (inst->size == 4) &&
1240	(mode >= 6) )
1241	{
1242	prev->code2 = 235 + ((mode - 6) * 4) + (prev->size - 1);
1243
1244	XD3_ASSERT (prev->code2 <= 246);
1245	}
1246	}
1247	}
1248
1249	XD3_ASSERT (inst->code1 <= 162);
1250	}
1251	break;
1252	}
1253	}
1254	#endif /* GENERIC_ENCODE_TABLES */
1255
1256	/***********************************************************************
1257	Instruction table encoder/decoder
1258	***********************************************************************/
1259
1260	#if GENERIC_ENCODE_TABLES
1261	#if GENERIC_ENCODE_TABLES_COMPUTE == 0
1262
1263	/* In this case, we hard-code the result of
1264	* compute_code_table_encoding for each alternate code table,
1265	* presuming that saves time/space. This has been 131 bytes, but
1266	* secondary compression was turned off. */
1267	static const uint8_t __alternate_code_table_compressed[178] =
1268	{0xd6,0xc3,0xc4,0x00,0x00,0x01,0x8a,0x6f,0x40,0x81,0x27,0x8c,0x00,0x00,0x4a,0x4a,0x0d,0x02,0x01,0x03,
1269	0x01,0x03,0x00,0x01,0x00,0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,
1270	0x0f,0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x00,0x01,0x01,0x01,0x02,0x02,0x02,0x03,0x03,0x03,0x04,
1271	0x04,0x04,0x04,0x00,0x04,0x05,0x06,0x01,0x02,0x03,0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x05,0x05,0x05,
1272	0x06,0x06,0x06,0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x00,0x02,0x00,0x18,0x13,0x63,0x00,0x1b,0x00,0x54,
1273	0x00,0x15,0x23,0x6f,0x00,0x28,0x13,0x54,0x00,0x15,0x01,0x1a,0x31,0x23,0x6c,0x0d,0x23,0x48,0x00,0x15,
1274	0x93,0x6f,0x00,0x28,0x04,0x23,0x51,0x04,0x32,0x00,0x2b,0x00,0x12,0x00,0x12,0x00,0x12,0x00,0x12,0x00,
1275	0x12,0x00,0x12,0x53,0x57,0x9c,0x07,0x43,0x6f,0x00,0x34,0x00,0x0c,0x00,0x0c,0x00,0x0c,0x00,0x0c,0x00,
1276	0x0c,0x00,0x0c,0x00,0x15,0x00,0x82,0x6f,0x00,0x15,0x12,0x0c,0x00,0x03,0x03,0x00,0x06,0x00,};
1277
1278	static int
1279	xd3_compute_alternate_table_encoding (xd3_stream stream, const uint8_t data, usize_t size)
1280	{
1281	(*data) = __alternate_code_table_compressed;
1282	(*size) = sizeof (__alternate_code_table_compressed);
1283	return 0;
1284	}
1285
1286	#else
1287
1288	/* The alternate code table will be computed and stored here. */
1289	static uint8_t __alternate_code_table_compressed[CODE_TABLE_VCDIFF_SIZE];
1290	static usize_t __alternate_code_table_compressed_size;
1291
1292	/* This function generates a delta describing the code table for
1293	* encoding within a VCDIFF file. This function is NOT thread safe
1294	* because it is only intended that this function is used to generate
1295	* statically-compiled strings. "comp_string" must be sized
1296	* CODE_TABLE_VCDIFF_SIZE. */
1297	int xd3_compute_code_table_encoding (xd3_stream *in_stream,
1298	const xd3_dinst *code_table,
1299	uint8_t *comp_string,
1300	usize_t *comp_string_size)
1301	{
1302	/* Use DJW secondary compression if it is on by default. This saves
1303	* about 20 bytes. */
1304	uint8_t dflt_string[CODE_TABLE_STRING_SIZE];
1305	uint8_t code_string[CODE_TABLE_STRING_SIZE];
1306
1307	xd3_compute_code_table_string (xd3_rfc3284_code_table (), dflt_string);
1308	xd3_compute_code_table_string (code_table, code_string);
1309
1310	return xd3_encode_memory (code_string, CODE_TABLE_STRING_SIZE,
1311	dflt_string, CODE_TABLE_STRING_SIZE,
1312	comp_string, comp_string_size,
1313	CODE_TABLE_VCDIFF_SIZE,
1314	/* flags */ 0);
1315	}
1316
1317	/* Compute a delta between alternate and rfc3284 tables. As soon as
1318	* another alternate table is added, this code should become generic.
1319	* For now there is only one alternate table for testing. */
1320	static int
1321	xd3_compute_alternate_table_encoding (xd3_stream stream, const uint8_t data, usize_t size)
1322	{
1323	int ret;
1324
1325	if (__alternate_code_table_compressed[0] == 0)
1326	{
1327	if ((ret = xd3_compute_code_table_encoding (stream, xd3_alternate_code_table (),
1328	__alternate_code_table_compressed,
1329	& __alternate_code_table_compressed_size)))
1330	{
1331	return ret;
1332	}
1333
1334	/* During development of a new code table, enable this variable to print
1335	* the new static contents and determine its size. At run time the
1336	* table will be filled in appropriately, but at least it should have
1337	* the proper size beforehand. */
1338	#if GENERIC_ENCODE_TABLES_COMPUTE_PRINT
1339	{
1340	int i;
1341
1342	DP(RINT, "\nstatic const usize_t __alternate_code_table_compressed_size = %u;\n",
1343	__alternate_code_table_compressed_size);
1344
1345	DP(RINT, "static const uint8_t __alternate_code_table_compressed[%u] =\n{",
1346	__alternate_code_table_compressed_size);
1347
1348	for (i = 0; i < __alternate_code_table_compressed_size; i += 1)
1349	{
1350	DP(RINT, "0x%02x,", __alternate_code_table_compressed[i]);
1351	if ((i % 20) == 19) { DP(RINT, "\n"); }
1352	}
1353
1354	DP(RINT, "};\n");
1355	}
1356	#endif
1357	}
1358
1359	(*data) = __alternate_code_table_compressed;
1360	(*size) = __alternate_code_table_compressed_size;
1361
1362	return 0;
1363	}
1364	#endif /* GENERIC_ENCODE_TABLES_COMPUTE != 0 */
1365	#endif /* GENERIC_ENCODE_TABLES */
1366
1367	#endif /* XD3_ENCODER */
1368
1369	/* This function generates the 1536-byte string specified in sections 5.4 and
1370	* 7 of rfc3284, which is used to represent a code table within a VCDIFF
1371	* file. */
1372	void xd3_compute_code_table_string (const xd3_dinst code_table, uint8_t str)
1373	{
1374	int i, s;
1375
1376	XD3_ASSERT (CODE_TABLE_STRING_SIZE == 6 * 256);
1377
1378	for (s = 0; s < 6; s += 1)
1379	{
1380	for (i = 0; i < 256; i += 1)
1381	{
1382	switch (s)
1383	{
1384	case 0: *str++ = (code_table[i].type1 >= XD3_CPY ? XD3_CPY : code_table[i].type1); break;
1385	case 1: *str++ = (code_table[i].type2 >= XD3_CPY ? XD3_CPY : code_table[i].type2); break;
1386	case 2: *str++ = (code_table[i].size1); break;
1387	case 3: *str++ = (code_table[i].size2); break;
1388	case 4: *str++ = (code_table[i].type1 >= XD3_CPY ? code_table[i].type1 - XD3_CPY : 0); break;
1389	case 5: *str++ = (code_table[i].type2 >= XD3_CPY ? code_table[i].type2 - XD3_CPY : 0); break;
1390	}
1391	}
1392	}
1393	}
1394
1395	/* This function translates the code table string into the internal representation. The
1396	* stream's near and same-modes should already be set. */
1397	static int
1398	xd3_apply_table_string (xd3_stream stream, const uint8_t code_string)
1399	{
1400	int i, s;
1401	int modes = TOTAL_MODES (stream);
1402	xd3_dinst *code_table;
1403
1404	if ((code_table = stream->code_table_alloc =
1405	(xd3_dinst*) xd3_alloc (stream,
1406	(usize_t) sizeof (xd3_dinst),
1407	256)) == NULL)
1408	{
1409	return ENOMEM;
1410	}
1411
1412	for (s = 0; s < 6; s += 1)
1413	{
1414	for (i = 0; i < 256; i += 1)
1415	{
1416	switch (s)
1417	{
1418	case 0:
1419	if (*code_string > XD3_CPY)
1420	{
1421	stream->msg = "invalid code-table opcode";
1422	return XD3_INTERNAL;
1423	}
1424	code_table[i].type1 = *code_string++;
1425	break;
1426	case 1:
1427	if (*code_string > XD3_CPY)
1428	{
1429	stream->msg = "invalid code-table opcode";
1430	return XD3_INTERNAL;
1431	}
1432	code_table[i].type2 = *code_string++;
1433	break;
1434	case 2:
1435	if (*code_string != 0 && code_table[i].type1 == XD3_NOOP)
1436	{
1437	stream->msg = "invalid code-table size";
1438	return XD3_INTERNAL;
1439	}
1440	code_table[i].size1 = *code_string++;
1441	break;
1442	case 3:
1443	if (*code_string != 0 && code_table[i].type2 == XD3_NOOP)
1444	{
1445	stream->msg = "invalid code-table size";
1446	return XD3_INTERNAL;
1447	}
1448	code_table[i].size2 = *code_string++;
1449	break;
1450	case 4:
1451	if (*code_string >= modes)
1452	{
1453	stream->msg = "invalid code-table mode";
1454	return XD3_INTERNAL;
1455	}
1456	if (*code_string != 0 && code_table[i].type1 != XD3_CPY)
1457	{
1458	stream->msg = "invalid code-table mode";
1459	return XD3_INTERNAL;
1460	}
1461	code_table[i].type1 += *code_string++;
1462	break;
1463	case 5:
1464	if (*code_string >= modes)
1465	{
1466	stream->msg = "invalid code-table mode";
1467	return XD3_INTERNAL;
1468	}
1469	if (*code_string != 0 && code_table[i].type2 != XD3_CPY)
1470	{
1471	stream->msg = "invalid code-table mode";
1472	return XD3_INTERNAL;
1473	}
1474	code_table[i].type2 += *code_string++;
1475	break;
1476	}
1477	}
1478	}
1479
1480	stream->code_table = code_table;
1481	return 0;
1482	}
1483
1484	/* This function applies a code table delta and returns an actual code table. */
1485	static int
1486	xd3_apply_table_encoding (xd3_stream in_stream, const uint8_t data, usize_t size)
1487	{
1488	uint8_t dflt_string[CODE_TABLE_STRING_SIZE];
1489	uint8_t code_string[CODE_TABLE_STRING_SIZE];
1490	usize_t code_size;
1491	int ret;
1492
1493	xd3_compute_code_table_string (xd3_rfc3284_code_table (), dflt_string);
1494
1495	if ((ret = xd3_decode_memory (data, size,
1496	dflt_string, CODE_TABLE_STRING_SIZE,
1497	code_string, &code_size,
1498	CODE_TABLE_STRING_SIZE,
1499	0))) { return ret; }
1500
1501	if (code_size != sizeof (code_string))
1502	{
1503	in_stream->msg = "corrupt code-table encoding";
1504	return XD3_INTERNAL;
1505	}
1506
1507	return xd3_apply_table_string (in_stream, code_string);
1508	}
1509
1510	/***********************************************************************/
1511
1512	static inline void
1513	xd3_swap_uint8p (uint8_t p1, uint8_t p2)
1514	{
1515	uint8_t t = (p1);
1516	(p1) = (p2);
1517	(*p2) = t;
1518	}
1519
1520	static inline void
1521	xd3_swap_usize_t (usize_t* p1, usize_t* p2)
1522	{
1523	usize_t t = (*p1);
1524	(p1) = (p2);
1525	(*p2) = t;
1526	}
1527
1528	/* It's not constant time, but it computes the log. */
1529	static int
1530	xd3_check_pow2 (usize_t value, usize_t *logof)
1531	{
1532	usize_t x = 1;
1533	usize_t nolog;
1534	if (logof == NULL) {
1535	logof = &nolog;
1536	}
1537
1538	*logof = 0;
1539
1540	for (; x != 0; x <<= 1, *logof += 1)
1541	{
1542	if (x == value)
1543	{
1544	return 0;
1545	}
1546	}
1547
1548	return XD3_INTERNAL;
1549	}
1550
1551	static usize_t
1552	xd3_pow2_roundup (usize_t x)
1553	{
1554	usize_t i = 1;
1555	while (x > i) {
1556	i <<= 1U;
1557	}
1558	return i;
1559	}
1560
1561	static usize_t
1562	xd3_round_blksize (usize_t sz, usize_t blksz)
1563	{
1564	usize_t mod = sz & (blksz-1);
1565
1566	XD3_ASSERT (xd3_check_pow2 (blksz, NULL) == 0);
1567
1568	return mod ? (sz + (blksz - mod)) : sz;
1569	}
1570
1571	/***********************************************************************
1572	Adler32 stream function: code copied from Zlib, defined in RFC1950
1573	***********************************************************************/
1574
1575	#define A32_BASE 65521L /* Largest prime smaller than 2^16 */
1576	#define A32_NMAX 5552 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
1577
1578	#define A32_DO1(buf,i) {s1 += buf[i]; s2 += s1;}
1579	#define A32_DO2(buf,i) A32_DO1(buf,i); A32_DO1(buf,i+1);
1580	#define A32_DO4(buf,i) A32_DO2(buf,i); A32_DO2(buf,i+2);
1581	#define A32_DO8(buf,i) A32_DO4(buf,i); A32_DO4(buf,i+4);
1582	#define A32_DO16(buf) A32_DO8(buf,0); A32_DO8(buf,8);
1583
1584	static unsigned long adler32 (unsigned long adler, const uint8_t *buf,
1585	usize_t len)
1586	{
1587	unsigned long s1 = adler & 0xffff;
1588	unsigned long s2 = (adler >> 16) & 0xffff;
1589	int k;
1590
1591	while (len > 0)
1592	{
1593	k = (len < A32_NMAX) ? len : A32_NMAX;
1594	len -= k;
1595
1596	while (k >= 16)
1597	{
1598	A32_DO16(buf);
1599	buf += 16;
1600	k -= 16;
1601	}
1602
1603	if (k != 0)
1604	{
1605	do
1606	{
1607	s1 += *buf++;
1608	s2 += s1;
1609	}
1610	while (--k);
1611	}
1612
1613	s1 %= A32_BASE;
1614	s2 %= A32_BASE;
1615	}
1616
1617	return (s2 << 16) \| s1;
1618	}
1619
1620	/***********************************************************************
1621	Run-length function
1622	***********************************************************************/
1623
1624	#if XD3_ENCODER
1625	static usize_t
1626	xd3_comprun (const uint8_t seg, usize_t slook, uint8_t run_cp)
1627	{
1628	usize_t i;
1629	usize_t run_l = 0;
1630	uint8_t run_c = 0;
1631
1632	for (i = 0; i < slook; i += 1)
1633	{
1634	NEXTRUN(seg[i]);
1635	}
1636
1637	(*run_cp) = run_c;
1638
1639	return run_l;
1640	}
1641	#endif
1642
1643	/***********************************************************************
1644	Basic encoder/decoder functions
1645	***********************************************************************/
1646
1647	static inline int
1648	xd3_decode_byte (xd3_stream stream, usize_t val)
1649	{
1650	if (stream->avail_in == 0)
1651	{
1652	stream->msg = "further input required";
1653	return XD3_INPUT;
1654	}
1655
1656	(*val) = stream->next_in[0];
1657
1658	DECODE_INPUT (1);
1659	return 0;
1660	}
1661
1662	static inline int
1663	xd3_decode_bytes (xd3_stream stream, uint8_t buf, usize_t *pos, usize_t size)
1664	{
1665	usize_t want;
1666	usize_t take;
1667
1668	/* Note: The case where (*pos == size) happens when a zero-length
1669	* appheader or code table is transmitted, but there is nothing in
1670	* the standard against that. */
1671	while (*pos < size)
1672	{
1673	if (stream->avail_in == 0)
1674	{
1675	stream->msg = "further input required";
1676	return XD3_INPUT;
1677	}
1678
1679	want = size - *pos;
1680	take = min (want, stream->avail_in);
1681
1682	memcpy (buf + *pos, stream->next_in, (size_t) take);
1683
1684	DECODE_INPUT (take);
1685	(*pos) += take;
1686	}
1687
1688	return 0;
1689	}
1690
1691	#if XD3_ENCODER
1692	static inline int
1693	xd3_emit_byte (xd3_stream *stream,
1694	xd3_output **outputp,
1695	uint8_t code)
1696	{
1697	xd3_output output = (outputp);
1698
1699	if (output->next == output->avail)
1700	{
1701	xd3_output *aoutput;
1702
1703	if ((aoutput = xd3_alloc_output (stream, output)) == NULL)
1704	{
1705	return ENOMEM;
1706	}
1707
1708	output = (*outputp) = aoutput;
1709	}
1710
1711	output->base[output->next++] = code;
1712
1713	return 0;
1714	}
1715
1716	static inline int
1717	xd3_emit_bytes (xd3_stream *stream,
1718	xd3_output **outputp,
1719	const uint8_t *base,
1720	usize_t size)
1721	{
1722	xd3_output output = (outputp);
1723
1724	do
1725	{
1726	usize_t take;
1727
1728	if (output->next == output->avail)
1729	{
1730	xd3_output *aoutput;
1731
1732	if ((aoutput = xd3_alloc_output (stream, output)) == NULL)
1733	{
1734	return ENOMEM;
1735	}
1736
1737	output = (*outputp) = aoutput;
1738	}
1739
1740	take = min (output->avail - output->next, size);
1741
1742	memcpy (output->base + output->next, base, (size_t) take);
1743
1744	output->next += take;
1745	size -= take;
1746	base += take;
1747	}
1748	while (size > 0);
1749
1750	return 0;
1751	}
1752	#endif /* XD3_ENCODER */
1753
1754	/*********************************************************************
1755	Integer encoder/decoder functions
1756	**********************************************************************/
1757
1758	#define DECODE_INTEGER_TYPE(PART,OFLOW) \
1759	while (stream->avail_in != 0) \
1760	{ \
1761	usize_t next = stream->next_in[0]; \
1762	\
1763	DECODE_INPUT(1); \
1764	\
1765	if (PART & OFLOW) \
1766	{ \
1767	stream->msg = "overflow in decode_integer"; \
1768	return XD3_INVALID_INPUT; \
1769	} \
1770	\
1771	PART = (PART << 7) \| (next & 127); \
1772	\
1773	if ((next & 128) == 0) \
1774	{ \
1775	(*val) = PART; \
1776	PART = 0; \
1777	return 0; \
1778	} \
1779	} \
1780	\
1781	stream->msg = "further input required"; \
1782	return XD3_INPUT
1783
1784	#define READ_INTEGER_TYPE(TYPE, OFLOW) \
1785	TYPE val = 0; \
1786	const uint8_t inp = (inpp); \
1787	usize_t next; \
1788	\
1789	do \
1790	{ \
1791	if (inp == max) \
1792	{ \
1793	stream->msg = "end-of-input in read_integer"; \
1794	return XD3_INVALID_INPUT; \
1795	} \
1796	\
1797	if (val & OFLOW) \
1798	{ \
1799	stream->msg = "overflow in read_intger"; \
1800	return XD3_INVALID_INPUT; \
1801	} \
1802	\
1803	next = (*inp++); \
1804	val = (val << 7) \| (next & 127); \
1805	} \
1806	while (next & 128); \
1807	\
1808	(*valp) = val; \
1809	(*inpp) = inp; \
1810	\
1811	return 0
1812
1813	#define EMIT_INTEGER_TYPE() \
1814	/* max 64-bit value in base-7 encoding is 9.1 bytes */ \
1815	uint8_t buf[10]; \
1816	usize_t bufi = 10; \
1817	\
1818	/* This loop performs division and turns on all MSBs. */ \
1819	do \
1820	{ \
1821	buf[--bufi] = (num & 127) \| 128; \
1822	num >>= 7U; \
1823	} \
1824	while (num != 0); \
1825	\
1826	/* Turn off MSB of the last byte. */ \
1827	buf[9] &= 127; \
1828	\
1829	return xd3_emit_bytes (stream, output, buf + bufi, 10 - bufi)
1830
1831	#define IF_SIZEOF32(x) if (num < (1U << (7 * (x)))) return (x);
1832	#define IF_SIZEOF64(x) if (num < (1ULL << (7 * (x)))) return (x);
1833
1834	#if USE_UINT32
1835	static inline uint32_t
1836	xd3_sizeof_uint32_t (uint32_t num)
1837	{
1838	IF_SIZEOF32(1);
1839	IF_SIZEOF32(2);
1840	IF_SIZEOF32(3);
1841	IF_SIZEOF32(4);
1842	return 5;
1843	}
1844
1845	static inline int
1846	xd3_decode_uint32_t (xd3_stream stream, uint32_t val)
1847	{ DECODE_INTEGER_TYPE (stream->dec_32part, UINT32_OFLOW_MASK); }
1848
1849	static inline int
1850	xd3_read_uint32_t (xd3_stream stream, const uint8_t *inpp,
1851	const uint8_t max, uint32_t valp)
1852	{ READ_INTEGER_TYPE (uint32_t, UINT32_OFLOW_MASK); }
1853
1854	#if XD3_ENCODER
1855	static inline int
1856	xd3_emit_uint32_t (xd3_stream stream, xd3_output *output, uint32_t num)
1857	{ EMIT_INTEGER_TYPE (); }
1858	#endif
1859	#endif
1860
1861	#if USE_UINT64
1862	static inline int
1863	xd3_decode_uint64_t (xd3_stream stream, uint64_t val)
1864	{ DECODE_INTEGER_TYPE (stream->dec_64part, UINT64_OFLOW_MASK); }
1865
1866	#if XD3_ENCODER
1867	static inline int
1868	xd3_emit_uint64_t (xd3_stream stream, xd3_output *output, uint64_t num)
1869	{ EMIT_INTEGER_TYPE (); }
1870	#endif
1871
1872	/* These are tested but not used */
1873	#if REGRESSION_TEST
1874	static int
1875	xd3_read_uint64_t (xd3_stream stream, const uint8_t *inpp,
1876	const uint8_t max, uint64_t valp)
1877	{ READ_INTEGER_TYPE (uint64_t, UINT64_OFLOW_MASK); }
1878
1879	static uint32_t
1880	xd3_sizeof_uint64_t (uint64_t num)
1881	{
1882	IF_SIZEOF64(1);
1883	IF_SIZEOF64(2);
1884	IF_SIZEOF64(3);
1885	IF_SIZEOF64(4);
1886	IF_SIZEOF64(5);
1887	IF_SIZEOF64(6);
1888	IF_SIZEOF64(7);
1889	IF_SIZEOF64(8);
1890	IF_SIZEOF64(9);
1891
1892	return 10;
1893	}
1894	#endif
1895
1896	#endif
1897
1898	/***********************************************************************
1899	Address cache stuff
1900	***********************************************************************/
1901
1902	static int
1903	xd3_alloc_cache (xd3_stream *stream)
1904	{
1905	if (stream->acache.near_array != NULL)
1906	{
1907	xd3_free (stream, stream->acache.near_array);
1908	}
1909
1910	if (stream->acache.same_array != NULL)
1911	{
1912	xd3_free (stream, stream->acache.same_array);
1913	}
1914
1915	if (((stream->acache.s_near > 0) &&
1916	(stream->acache.near_array = (usize_t*)
1917	xd3_alloc (stream, stream->acache.s_near,
1918	(usize_t) sizeof (usize_t)))
1919	== NULL) \|\|
1920	((stream->acache.s_same > 0) &&
1921	(stream->acache.same_array = (usize_t*)
1922	xd3_alloc (stream, stream->acache.s_same * 256,
1923	(usize_t) sizeof (usize_t)))
1924	== NULL))
1925	{
1926	return ENOMEM;
1927	}
1928
1929	return 0;
1930	}
1931
1932	void
1933	xd3_init_cache (xd3_addr_cache* acache)
1934	{
1935	if (acache->s_near > 0)
1936	{
1937	memset (acache->near_array, 0, acache->s_near * sizeof (usize_t));
1938	acache->next_slot = 0;
1939	}
1940
1941	if (acache->s_same > 0)
1942	{
1943	memset (acache->same_array, 0, acache->s_same * 256 * sizeof (usize_t));
1944	}
1945	}
1946
1947	static void
1948	xd3_update_cache (xd3_addr_cache* acache, usize_t addr)
1949	{
1950	if (acache->s_near > 0)
1951	{
1952	acache->near_array[acache->next_slot] = addr;
1953	acache->next_slot = (acache->next_slot + 1) % acache->s_near;
1954	}
1955
1956	if (acache->s_same > 0)
1957	{
1958	acache->same_array[addr % (acache->s_same*256)] = addr;
1959	}
1960	}
1961
1962	#if XD3_ENCODER
1963	/* OPT: this gets called a lot, can it be optimized? */
1964	static int
1965	xd3_encode_address (xd3_stream *stream,
1966	usize_t addr,
1967	usize_t here,
1968	uint8_t* mode)
1969	{
1970	usize_t d, bestd;
1971	usize_t i, bestm, ret;
1972	xd3_addr_cache* acache = & stream->acache;
1973
1974	#define SMALLEST_INT(x) do { if (((x) & ~127U) == 0) { goto good; } } while (0)
1975
1976	/* Attempt to find the address mode that yields the smallest integer value
1977	* for "d", the encoded address value, thereby minimizing the encoded size
1978	* of the address. */
1979	bestd = addr;
1980	bestm = VCD_SELF;
1981
1982	XD3_ASSERT (addr < here);
1983
1984	SMALLEST_INT (bestd);
1985
1986	if ((d = here-addr) < bestd)
1987	{
1988	bestd = d;
1989	bestm = VCD_HERE;
1990
1991	SMALLEST_INT (bestd);
1992	}
1993
1994	for (i = 0; i < acache->s_near; i += 1)
1995	{
1996	/* Note: If we used signed computation here, we'd could compte d
1997	* and then check (d >= 0 && d < bestd). */
1998	if (addr >= acache->near_array[i])
1999	{
2000	d = addr - acache->near_array[i];
2001
2002	if (d < bestd)
2003	{
2004	bestd = d;
2005	bestm = i+2; /* 2 counts the VCD_SELF, VCD_HERE modes */
2006
2007	SMALLEST_INT (bestd);
2008	}
2009	}
2010	}
2011
2012	if (acache->s_same > 0 &&
2013	acache->same_array[d = addr%(acache->s_same*256)] == addr)
2014	{
2015	bestd = d%256;
2016	/* 2 + s_near offsets past the VCD_NEAR modes */
2017	bestm = acache->s_near + 2 + d/256;
2018
2019	if ((ret = xd3_emit_byte (stream, & ADDR_TAIL (stream), bestd)))
2020	{
2021	return ret;
2022	}
2023	}
2024	else
2025	{
2026	good:
2027
2028	if ((ret = xd3_emit_size (stream, & ADDR_TAIL (stream), bestd)))
2029	{
2030	return ret;
2031	}
2032	}
2033
2034	xd3_update_cache (acache, addr);
2035
2036	(*mode) += bestm;
2037
2038	return 0;
2039	}
2040	#endif
2041
2042	static int
2043	xd3_decode_address (xd3_stream *stream, usize_t here,
2044	usize_t mode, const uint8_t **inpp,
2045	const uint8_t max, uint32_t valp)
2046	{
2047	int ret;
2048	usize_t same_start = 2 + stream->acache.s_near;
2049
2050	if (mode < same_start)
2051	{
2052	if ((ret = xd3_read_size (stream, inpp, max, valp))) { return ret; }
2053
2054	switch (mode)
2055	{
2056	case VCD_SELF:
2057	break;
2058	case VCD_HERE:
2059	(valp) = here - (valp);
2060	break;
2061	default:
2062	(*valp) += stream->acache.near_array[mode - 2];
2063	break;
2064	}
2065	}
2066	else
2067	{
2068	if (*inpp == max)
2069	{
2070	stream->msg = "address underflow";
2071	return XD3_INVALID_INPUT;
2072	}
2073
2074	mode -= same_start;
2075
2076	(valp) = stream->acache.same_array[mode256 + (**inpp)];
2077
2078	(*inpp) += 1;
2079	}
2080
2081	xd3_update_cache (& stream->acache, *valp);
2082
2083	return 0;
2084	}
2085
2086	/***********************************************************************
2087	Alloc/free
2088	***********************************************************************/
2089
2090	static void*
2091	__xd3_alloc_func (void* opaque, usize_t items, usize_t size)
2092	{
2093	return malloc ((size_t) items * (size_t) size);
2094	}
2095
2096	static void
2097	__xd3_free_func (void* opaque, void* address)
2098	{
2099	free (address);
2100	}
2101
2102	static void*
2103	xd3_alloc (xd3_stream *stream,
2104	usize_t elts,
2105	usize_t size)
2106	{
2107	void *a = stream->alloc (stream->opaque, elts, size);
2108
2109	if (a != NULL)
2110	{
2111	IF_DEBUG (stream->alloc_cnt += 1);
2112	IF_DEBUG2 (DP(RINT "[stream %p malloc] size %u ptr %p\n",
2113	stream, elts * size, a));
2114	}
2115	else
2116	{
2117	stream->msg = "out of memory";
2118	}
2119
2120	return a;
2121	}
2122
2123	static void
2124	xd3_free (xd3_stream *stream,
2125	void *ptr)
2126	{
2127	if (ptr != NULL)
2128	{
2129	IF_DEBUG (stream->free_cnt += 1);
2130	XD3_ASSERT (stream->free_cnt <= stream->alloc_cnt);
2131	IF_DEBUG2 (DP(RINT "[stream %p free] %p\n",
2132	stream, ptr));
2133	stream->free (stream->opaque, ptr);
2134	}
2135	}
2136
2137	#if XD3_ENCODER
2138	static void*
2139	xd3_alloc0 (xd3_stream *stream,
2140	usize_t elts,
2141	usize_t size)
2142	{
2143	void *a = xd3_alloc (stream, elts, size);
2144
2145	if (a != NULL)
2146	{
2147	memset (a, 0, (size_t) (elts * size));
2148	}
2149
2150	return a;
2151	}
2152
2153	static xd3_output*
2154	xd3_alloc_output (xd3_stream *stream,
2155	xd3_output *old_output)
2156	{
2157	xd3_output *output;
2158	uint8_t *base;
2159
2160	if (stream->enc_free != NULL)
2161	{
2162	output = stream->enc_free;
2163	stream->enc_free = output->next_page;
2164	}
2165	else
2166	{
2167	if ((output = (xd3_output*) xd3_alloc (stream, 1,
2168	(usize_t) sizeof (xd3_output)))
2169	== NULL)
2170	{
2171	return NULL;
2172	}
2173
2174	if ((base = (uint8_t*) xd3_alloc (stream, XD3_ALLOCSIZE,
2175	sizeof (uint8_t))) == NULL)
2176	{
2177	xd3_free (stream, output);
2178	return NULL;
2179	}
2180
2181	output->base = base;
2182	output->avail = XD3_ALLOCSIZE;
2183	}
2184
2185	output->next = 0;
2186
2187	if (old_output)
2188	{
2189	old_output->next_page = output;
2190	}
2191
2192	output->next_page = NULL;
2193
2194	return output;
2195	}
2196
2197	static usize_t
2198	xd3_sizeof_output (xd3_output *output)
2199	{
2200	usize_t s = 0;
2201
2202	for (; output; output = output->next_page)
2203	{
2204	s += output->next;
2205	}
2206
2207	return s;
2208	}
2209
2210	static void
2211	xd3_freelist_output (xd3_stream *stream,
2212	xd3_output *output)
2213	{
2214	xd3_output *tmp;
2215
2216	while (output)
2217	{
2218	tmp = output;
2219	output = output->next_page;
2220
2221	tmp->next = 0;
2222	tmp->next_page = stream->enc_free;
2223	stream->enc_free = tmp;
2224	}
2225	}
2226
2227	static void
2228	xd3_free_output (xd3_stream *stream,
2229	xd3_output *output)
2230	{
2231	xd3_output *next;
2232
2233	again:
2234	if (output == NULL)
2235	{
2236	return;
2237	}
2238
2239	next = output->next_page;
2240
2241	xd3_free (stream, output->base);
2242	xd3_free (stream, output);
2243
2244	output = next;
2245	goto again;
2246	}
2247	#endif /* XD3_ENCODER */
2248
2249	void
2250	xd3_free_stream (xd3_stream *stream)
2251	{
2252	xd3_iopt_buflist *blist = stream->iopt_alloc;
2253
2254	while (blist != NULL)
2255	{
2256	xd3_iopt_buflist *tmp = blist;
2257	blist = blist->next;
2258	xd3_free (stream, tmp->buffer);
2259	xd3_free (stream, tmp);
2260	}
2261
2262	xd3_free (stream, stream->large_table);
2263	xd3_free (stream, stream->small_table);
2264	xd3_free (stream, stream->small_prev);
2265
2266	#if XD3_ENCODER
2267	{
2268	int i;
2269	for (i = 0; i < ENC_SECTS; i += 1)
2270	{
2271	xd3_free_output (stream, stream->enc_heads[i]);
2272	}
2273	xd3_free_output (stream, stream->enc_free);
2274	}
2275	#endif
2276
2277	xd3_free (stream, stream->acache.near_array);
2278	xd3_free (stream, stream->acache.same_array);
2279
2280	xd3_free (stream, stream->inst_sect.copied1);
2281	xd3_free (stream, stream->addr_sect.copied1);
2282	xd3_free (stream, stream->data_sect.copied1);
2283
2284	xd3_free (stream, stream->dec_buffer);
2285	xd3_free (stream, (uint8_t*) stream->dec_lastwin);
2286
2287	xd3_free (stream, stream->buf_in);
2288	xd3_free (stream, stream->dec_appheader);
2289	xd3_free (stream, stream->dec_codetbl);
2290	xd3_free (stream, stream->code_table_alloc);
2291
2292	#if SECONDARY_ANY
2293	xd3_free (stream, stream->inst_sect.copied2);
2294	xd3_free (stream, stream->addr_sect.copied2);
2295	xd3_free (stream, stream->data_sect.copied2);
2296
2297	if (stream->sec_type != NULL)
2298	{
2299	stream->sec_type->destroy (stream, stream->sec_stream_d);
2300	stream->sec_type->destroy (stream, stream->sec_stream_i);
2301	stream->sec_type->destroy (stream, stream->sec_stream_a);
2302	}
2303	#endif
2304
2305	xd3_free (stream, stream->whole_target.adds);
2306	xd3_free (stream, stream->whole_target.inst);
2307	xd3_free (stream, stream->whole_target.wininfo);
2308
2309	XD3_ASSERT (stream->alloc_cnt == stream->free_cnt);
2310
2311	memset (stream, 0, sizeof (xd3_stream));
2312	}
2313
2314	#if (XD3_DEBUG > 1 \|\| VCDIFF_TOOLS)
2315	static const char*
2316	xd3_rtype_to_string (xd3_rtype type, int print_mode)
2317	{
2318	switch (type)
2319	{
2320	case XD3_NOOP:
2321	return "NOOP ";
2322	case XD3_RUN:
2323	return "RUN ";
2324	case XD3_ADD:
2325	return "ADD ";
2326	default: break;
2327	}
2328	if (! print_mode)
2329	{
2330	return "CPY ";
2331	}
2332	switch (type)
2333	{
2334	case XD3_CPY + 0: return "CPY_0";
2335	case XD3_CPY + 1: return "CPY_1";
2336	case XD3_CPY + 2: return "CPY_2";
2337	case XD3_CPY + 3: return "CPY_3";
2338	case XD3_CPY + 4: return "CPY_4";
2339	case XD3_CPY + 5: return "CPY_5";
2340	case XD3_CPY + 6: return "CPY_6";
2341	case XD3_CPY + 7: return "CPY_7";
2342	case XD3_CPY + 8: return "CPY_8";
2343	case XD3_CPY + 9: return "CPY_9";
2344	default: return "CPY>9";
2345	}
2346	}
2347	#endif
2348
2349	/****************************************************************
2350	Stream configuration
2351	******************************************************************/
2352
2353	int
2354	xd3_config_stream(xd3_stream *stream,
2355	xd3_config *config)
2356	{
2357	int ret;
2358	xd3_config defcfg;
2359	xd3_smatcher *smatcher = &stream->smatcher;
2360
2361	if (config == NULL)
2362	{
2363	config = & defcfg;
2364	memset (config, 0, sizeof (*config));
2365	}
2366
2367	/* Initial setup: no error checks yet */
2368	memset (stream, 0, sizeof (*stream));
2369
2370	stream->winsize = config->winsize ? config->winsize : XD3_DEFAULT_WINSIZE;
2371	stream->sprevsz = config->sprevsz ? config->sprevsz : XD3_DEFAULT_SPREVSZ;
2372	stream->srcwin_maxsz = config->srcwin_maxsz ?
2373	config->srcwin_maxsz : XD3_DEFAULT_SRCWINSZ;
2374
2375	if (config->iopt_size == 0)
2376	{
2377	stream->iopt_size = XD3_ALLOCSIZE / sizeof(xd3_rinst);
2378	stream->iopt_unlimited = 1;
2379	}
2380	else
2381	{
2382	stream->iopt_size = config->iopt_size;
2383	}
2384
2385	stream->getblk = config->getblk;
2386	stream->alloc = config->alloc ? config->alloc : __xd3_alloc_func;
2387	stream->free = config->freef ? config->freef : __xd3_free_func;
2388	stream->opaque = config->opaque;
2389	stream->flags = config->flags;
2390
2391	/* Secondary setup. */
2392	stream->sec_data = config->sec_data;
2393	stream->sec_inst = config->sec_inst;
2394	stream->sec_addr = config->sec_addr;
2395
2396	stream->sec_data.data_type = DATA_SECTION;
2397	stream->sec_inst.data_type = INST_SECTION;
2398	stream->sec_addr.data_type = ADDR_SECTION;
2399
2400	/* Check static sizes. */
2401	if (sizeof (usize_t) != SIZEOF_USIZE_T \|\|
2402	sizeof (xoff_t) != SIZEOF_XOFF_T \|\|
2403	(ret = xd3_check_pow2(XD3_ALLOCSIZE, NULL)))
2404	{
2405	stream->msg = "incorrect compilation: wrong integer sizes";
2406	return XD3_INTERNAL;
2407	}
2408
2409	/* Check/set secondary compressor. */
2410	switch (stream->flags & XD3_SEC_TYPE)
2411	{
2412	case 0:
2413	if (stream->flags & XD3_SEC_NOALL)
2414	{
2415	stream->msg = "XD3_SEC flags require a secondary compressor type";
2416	return XD3_INTERNAL;
2417	}
2418	break;
2419	case XD3_SEC_FGK:
2420	FGK_CASE (stream);
2421	case XD3_SEC_DJW:
2422	DJW_CASE (stream);
2423	case XD3_SEC_LZMA:
2424	LZMA_CASE (stream);
2425	default:
2426	stream->msg = "too many secondary compressor types set";
2427	return XD3_INTERNAL;
2428	}
2429
2430	/* Check/set encoder code table. */
2431	switch (stream->flags & XD3_ALT_CODE_TABLE) {
2432	case 0:
2433	stream->code_table_desc = & __rfc3284_code_table_desc;
2434	stream->code_table_func = xd3_rfc3284_code_table;
2435	break;
2436	#if GENERIC_ENCODE_TABLES
2437	case XD3_ALT_CODE_TABLE:
2438	stream->code_table_desc = & __alternate_code_table_desc;
2439	stream->code_table_func = xd3_alternate_code_table;
2440	stream->comp_table_func = xd3_compute_alternate_table_encoding;
2441	break;
2442	#endif
2443	default:
2444	stream->msg = "alternate code table support was not compiled";
2445	return XD3_INTERNAL;
2446	}
2447
2448	/* Check sprevsz */
2449	if (smatcher->small_chain == 1 &&
2450	smatcher->small_lchain == 1)
2451	{
2452	stream->sprevsz = 0;
2453	}
2454	else
2455	{
2456	if ((ret = xd3_check_pow2 (stream->sprevsz, NULL)))
2457	{
2458	stream->msg = "sprevsz is required to be a power of two";
2459	return XD3_INTERNAL;
2460	}
2461
2462	stream->sprevmask = stream->sprevsz - 1;
2463	}
2464
2465	/* Default scanner settings. */
2466	#if XD3_ENCODER
2467	switch (config->smatch_cfg)
2468	{
2469	IF_BUILD_SOFT(case XD3_SMATCH_SOFT:
2470	{
2471	*smatcher = config->smatcher_soft;
2472	smatcher->string_match = __smatcher_soft.string_match;
2473	smatcher->name = __smatcher_soft.name;
2474	if (smatcher->large_look < MIN_MATCH \|\|
2475	smatcher->large_step < 1 \|\|
2476	smatcher->small_look < MIN_MATCH)
2477	{
2478	stream->msg = "invalid soft string-match config";
2479	return XD3_INVALID;
2480	}
2481	break;
2482	})
2483
2484	IF_BUILD_DEFAULT(case XD3_SMATCH_DEFAULT:
2485	*smatcher = __smatcher_default;
2486	break;)
2487	IF_BUILD_SLOW(case XD3_SMATCH_SLOW:
2488	*smatcher = __smatcher_slow;
2489	break;)
2490	IF_BUILD_FASTEST(case XD3_SMATCH_FASTEST:
2491	*smatcher = __smatcher_fastest;
2492	break;)
2493	IF_BUILD_FASTER(case XD3_SMATCH_FASTER:
2494	*smatcher = __smatcher_faster;
2495	break;)
2496	IF_BUILD_FAST(case XD3_SMATCH_FAST:
2497	*smatcher = __smatcher_fast;
2498	break;)
2499	default:
2500	stream->msg = "invalid string match config type";
2501	return XD3_INTERNAL;
2502	}
2503
2504	if (config->smatch_cfg == XD3_SMATCH_DEFAULT &&
2505	(stream->flags & XD3_COMPLEVEL_MASK) != 0)
2506	{
2507	int level = (stream->flags & XD3_COMPLEVEL_MASK) >> XD3_COMPLEVEL_SHIFT;
2508
2509	switch (level)
2510	{
2511	case 1:
2512	IF_BUILD_FASTEST(*smatcher = __smatcher_fastest;
2513	break;)
2514	case 2:
2515	IF_BUILD_FASTER(*smatcher = __smatcher_faster;
2516	break;)
2517	case 3: case 4: case 5:
2518	IF_BUILD_FAST(*smatcher = __smatcher_fast;
2519	break;)
2520	case 6:
2521	IF_BUILD_DEFAULT(*smatcher = __smatcher_default;
2522	break;)
2523	default:
2524	IF_BUILD_SLOW(*smatcher = __smatcher_slow;
2525	break;)
2526	IF_BUILD_DEFAULT(*smatcher = __smatcher_default;
2527	break;)
2528	IF_BUILD_FAST(*smatcher = __smatcher_fast;
2529	break;)
2530	IF_BUILD_FASTER(*smatcher = __smatcher_faster;
2531	break;)
2532	IF_BUILD_FASTEST(*smatcher = __smatcher_fastest;
2533	break;)
2534	}
2535	}
2536	#endif
2537
2538	return 0;
2539	}
2540
2541	/***********************************************************
2542	Getblk interface
2543	***********************************************************/
2544
2545	inline
2546	xoff_t xd3_source_eof(const xd3_source *src)
2547	{
2548	xoff_t r = (src->blksize * src->max_blkno) + (xoff_t)src->onlastblk;
2549	return r;
2550	}
2551
2552	inline
2553	usize_t xd3_bytes_on_srcblk (xd3_source *src, xoff_t blkno)
2554	{
2555	usize_t r = (blkno == src->max_blkno ?
2556	src->onlastblk :
2557	src->blksize);
2558	return r;
2559	}
2560
2561	/* This function interfaces with the client getblk function, checks
2562	* its results, updates frontier_blkno, max_blkno, onlastblk, eof_known. */
2563	static int
2564	xd3_getblk (xd3_stream *stream, xoff_t blkno)
2565	{
2566	int ret;
2567	xd3_source *source = stream->src;
2568
2569	if (source->curblk == NULL \|\| blkno != source->curblkno)
2570	{
2571	source->getblkno = blkno;
2572
2573	if (stream->getblk == NULL)
2574	{
2575	stream->msg = "getblk source input";
2576	return XD3_GETSRCBLK;
2577	}
2578
2579	ret = stream->getblk (stream, source, blkno);
2580	if (ret != 0)
2581	{
2582	IF_DEBUG1 (DP(RINT "[getblk] app error blkno %"Q"u: %s\n",
2583	blkno, xd3_strerror (ret)));
2584	return ret;
2585	}
2586	}
2587
2588	if (blkno >= source->frontier_blkno)
2589	{
2590	if (blkno > source->max_blkno)
2591	{
2592	source->max_blkno = blkno;
2593	source->onlastblk = source->onblk;
2594	}
2595
2596	if (source->onblk == source->blksize)
2597	{
2598	source->frontier_blkno = blkno + 1;
2599
2600	IF_DEBUG2 (DP(RINT "[getblk] full source blkno %"Q"u: "
2601	"source length unknown %"Q"u\n",
2602	blkno,
2603	xd3_source_eof (source)));
2604	}
2605	else
2606	{
2607	if (!source->eof_known)
2608	{
2609	IF_DEBUG2 (DP(RINT "[getblk] eof block has %d bytes; "
2610	"source length known %"Q"u\n",
2611	xd3_bytes_on_srcblk (source, blkno),
2612	xd3_source_eof (source)));
2613	source->eof_known = 1;
2614	}
2615
2616	source->frontier_blkno = blkno;
2617	}
2618	}
2619
2620	XD3_ASSERT (source->curblk != NULL);
2621	IF_DEBUG2 (DP(RINT "[getblk] read source block %"Q"u onblk %u blksize %u\n",
2622	blkno, source->onblk, source->blksize));
2623
2624	if (blkno == source->max_blkno)
2625	{
2626	/* In case the application sets the source as 1 block w/ a
2627	preset buffer. */
2628	source->onlastblk = source->onblk;
2629
2630	if (source->onblk == source->blksize)
2631	{
2632	source->frontier_blkno = blkno + 1;
2633	}
2634	}
2635	return 0;
2636	}
2637
2638	/***********************************************************
2639	Stream open/close
2640	***************************************************************/
2641
2642	int
2643	xd3_set_source (xd3_stream *stream,
2644	xd3_source *src)
2645	{
2646	usize_t shiftby;
2647
2648	stream->src = src;
2649	src->srclen = 0;
2650	src->srcbase = 0;
2651
2652	/* Enforce power-of-two blocksize so that source-block number
2653	* calculations are cheap. */
2654	if (!xd3_check_pow2 (src->blksize, &shiftby) == 0)
2655	{
2656	src->blksize = xd3_pow2_roundup(src->blksize);
2657	xd3_check_pow2 (src->blksize, &shiftby);
2658	IF_DEBUG1 (DP(RINT "raising srcblksz to %u\n", src->blksize));
2659	}
2660
2661	src->shiftby = shiftby;
2662	src->maskby = (1 << shiftby) - 1;
2663	return 0;
2664	}
2665
2666	int
2667	xd3_set_source_and_size (xd3_stream *stream,
2668	xd3_source *user_source,
2669	xoff_t source_size) {
2670	int ret = xd3_set_source (stream, user_source);
2671	if (ret == 0)
2672	{
2673	stream->src->eof_known = 1;
2674	IF_DEBUG2 (DP(RINT "[set source] size known %"Q"u\n",
2675	source_size));
2676
2677	xd3_blksize_div(source_size,
2678	stream->src,
2679	&stream->src->max_blkno,
2680	&stream->src->onlastblk);
2681	}
2682	return ret;
2683	}
2684
2685	void
2686	xd3_abort_stream (xd3_stream *stream)
2687	{
2688	stream->dec_state = DEC_ABORTED;
2689	stream->enc_state = ENC_ABORTED;
2690	}
2691
2692	int
2693	xd3_close_stream (xd3_stream *stream)
2694	{
2695	if (stream->enc_state != 0 && stream->enc_state != ENC_ABORTED)
2696	{
2697	if (stream->buf_leftover != NULL)
2698	{
2699	stream->msg = "encoding is incomplete";
2700	return XD3_INTERNAL;
2701	}
2702
2703	if (stream->enc_state == ENC_POSTWIN)
2704	{
2705	#if XD3_ENCODER
2706	xd3_encode_reset (stream);
2707	#endif
2708	stream->current_window += 1;
2709	stream->enc_state = ENC_INPUT;
2710	}
2711
2712	/* If encoding, should be ready for more input but not actually
2713	have any. */
2714	if (stream->enc_state != ENC_INPUT \|\| stream->avail_in != 0)
2715	{
2716	stream->msg = "encoding is incomplete";
2717	return XD3_INTERNAL;
2718	}
2719	}
2720	else
2721	{
2722	switch (stream->dec_state)
2723	{
2724	case DEC_VCHEAD:
2725	case DEC_WININD:
2726	/* TODO: Address the zero-byte ambiguity. Does the encoder
2727	* emit a window or not? If so, then catch an error here.
2728	* If not, need another routine to say
2729	* decode_at_least_one_if_empty. */
2730	case DEC_ABORTED:
2731	break;
2732	default:
2733	/* If decoding, should be ready for the next window. */
2734	stream->msg = "EOF in decode";
2735	return XD3_INTERNAL;
2736	}
2737	}
2738
2739	return 0;
2740	}
2741
2742	/**************************************************************
2743	Application header
2744	****************************************************************/
2745
2746	int
2747	xd3_get_appheader (xd3_stream *stream,
2748	uint8_t **data,
2749	usize_t *size)
2750	{
2751	if (stream->dec_state < DEC_WININD)
2752	{
2753	stream->msg = "application header not available";
2754	return XD3_INTERNAL;
2755	}
2756
2757	(*data) = stream->dec_appheader;
2758	(*size) = stream->dec_appheadsz;
2759	return 0;
2760	}
2761
2762	/**********************************************************
2763	Decoder stuff
2764	*************************************************/
2765
2766	#include "xdelta3-decode.h"
2767
2768	/****************************************************************
2769	Encoder stuff
2770	*****************************************************************/
2771
2772	#if XD3_ENCODER
2773	void
2774	xd3_set_appheader (xd3_stream *stream,
2775	const uint8_t *data,
2776	usize_t size)
2777	{
2778	stream->enc_appheader = data;
2779	stream->enc_appheadsz = size;
2780	}
2781
2782	#if XD3_DEBUG
2783	static int
2784	xd3_iopt_check (xd3_stream *stream)
2785	{
2786	usize_t ul = xd3_rlist_length (& stream->iopt_used);
2787	usize_t fl = xd3_rlist_length (& stream->iopt_free);
2788
2789	return (ul + fl + (stream->iout ? 1 : 0)) == stream->iopt_size;
2790	}
2791	#endif
2792
2793	static xd3_rinst*
2794	xd3_iopt_free (xd3_stream stream, xd3_rinst i)
2795	{
2796	xd3_rinst *n = xd3_rlist_remove (i);
2797	xd3_rlist_push_back (& stream->iopt_free, i);
2798	return n;
2799	}
2800
2801	static void
2802	xd3_iopt_free_nonadd (xd3_stream stream, xd3_rinst i)
2803	{
2804	if (i->type != XD3_ADD)
2805	{
2806	xd3_rlist_push_back (& stream->iopt_free, i);
2807	}
2808	}
2809
2810	/* When an instruction is ready to flush from the iopt buffer, this
2811	* function is called to produce an encoding. It writes the
2812	* instruction plus size, address, and data to the various encoding
2813	* sections. */
2814	static int
2815	xd3_iopt_finish_encoding (xd3_stream stream, xd3_rinst inst)
2816	{
2817	int ret;
2818
2819	/* Check for input overflow. */
2820	XD3_ASSERT (inst->pos + inst->size <= stream->avail_in);
2821
2822	switch (inst->type)
2823	{
2824	case XD3_CPY:
2825	{
2826	/* the address may have an offset if there is a source window. */
2827	usize_t addr;
2828	xd3_source *src = stream->src;
2829
2830	if (src != NULL)
2831	{
2832	/* If there is a source copy, the source must have its
2833	* source window decided before we can encode. This can
2834	* be bad -- we have to make this decision even if no
2835	* source matches have been found. */
2836	if (stream->srcwin_decided == 0)
2837	{
2838	if ((ret = xd3_srcwin_setup (stream))) { return ret; }
2839	}
2840	else
2841	{
2842	stream->srcwin_decided_early = (!stream->src->eof_known \|\|
2843	(stream->srcwin_cksum_pos <
2844	xd3_source_eof (stream->src)));
2845	}
2846
2847	/* xtra field indicates the copy is from the source */
2848	if (inst->xtra)
2849	{
2850	XD3_ASSERT (inst->addr >= src->srcbase);
2851	XD3_ASSERT (inst->addr + inst->size <=
2852	src->srcbase + src->srclen);
2853	addr = (usize_t)(inst->addr - src->srcbase);
2854	stream->n_scpy += 1;
2855	stream->l_scpy += (xoff_t) inst->size;
2856	}
2857	else
2858	{
2859	/* with source window: target copy address is offset
2860	* by taroff. */
2861	addr = stream->taroff + (usize_t) inst->addr;
2862	stream->n_tcpy += 1;
2863	stream->l_tcpy += (xoff_t) inst->size;
2864	}
2865	}
2866	else
2867	{
2868	addr = (usize_t) inst->addr;
2869	stream->n_tcpy += 1;
2870	stream->l_tcpy += inst->size;
2871	}
2872
2873	/* Note: used to assert inst->size >= MIN_MATCH, but not true
2874	* for merge operations & identical match heuristics. */
2875	/* the "here" position is always offset by taroff */
2876	if ((ret = xd3_encode_address (stream, addr, inst->pos + stream->taroff,
2877	& inst->type)))
2878	{
2879	return ret;
2880	}
2881
2882	IF_DEBUG2 ({
2883	static int cnt;
2884	DP(RINT "[iopt copy:%d] pos %"Q"u-%"Q"u addr %"Q"u-%"Q"u size %u\n",
2885	cnt++,
2886	stream->total_in + inst->pos,
2887	stream->total_in + inst->pos + inst->size,
2888	inst->addr, inst->addr + inst->size, inst->size);
2889	});
2890	break;
2891	}
2892	case XD3_RUN:
2893	{
2894	XD3_ASSERT (inst->size >= MIN_MATCH);
2895
2896	if ((ret = xd3_emit_byte (stream, & DATA_TAIL (stream), inst->xtra))) { return ret; }
2897
2898	stream->n_run += 1;
2899	stream->l_run += inst->size;
2900
2901	IF_DEBUG2 ({
2902	static int cnt;
2903	DP(RINT "[iopt run:%d] pos %"Q"u size %u\n", cnt++, stream->total_in + inst->pos, inst->size);
2904	});
2905	break;
2906	}
2907	case XD3_ADD:
2908	{
2909	if ((ret = xd3_emit_bytes (stream, & DATA_TAIL (stream),
2910	stream->next_in + inst->pos, inst->size))) { return ret; }
2911
2912	stream->n_add += 1;
2913	stream->l_add += inst->size;
2914
2915	IF_DEBUG2 ({
2916	static int cnt;
2917	DP(RINT "[iopt add:%d] pos %"Q"u size %u\n", cnt++, stream->total_in + inst->pos, inst->size);
2918	});
2919
2920	break;
2921	}
2922	}
2923
2924	/* This is the only place stream->unencoded_offset is incremented. */
2925	XD3_ASSERT (stream->unencoded_offset == inst->pos);
2926	stream->unencoded_offset += inst->size;
2927
2928	inst->code2 = 0;
2929
2930	XD3_CHOOSE_INSTRUCTION (stream, stream->iout, inst);
2931
2932	if (stream->iout != NULL)
2933	{
2934	if (stream->iout->code2 != 0)
2935	{
2936	if ((ret = xd3_emit_double (stream, stream->iout, inst, stream->iout->code2))) { return ret; }
2937
2938	xd3_iopt_free_nonadd (stream, stream->iout);
2939	xd3_iopt_free_nonadd (stream, inst);
2940	stream->iout = NULL;
2941	return 0;
2942	}
2943	else
2944	{
2945	if ((ret = xd3_emit_single (stream, stream->iout, stream->iout->code1))) { return ret; }
2946
2947	xd3_iopt_free_nonadd (stream, stream->iout);
2948	}
2949	}
2950
2951	stream->iout = inst;
2952
2953	return 0;
2954	}
2955
2956	/* This possibly encodes an add instruction, iadd, which must remain
2957	* on the stack until the following call to
2958	* xd3_iopt_finish_encoding. */
2959	static int
2960	xd3_iopt_add (xd3_stream stream, usize_t pos, xd3_rinst iadd)
2961	{
2962	int ret;
2963	usize_t off = stream->unencoded_offset;
2964
2965	if (pos > off)
2966	{
2967	iadd->type = XD3_ADD;
2968	iadd->pos = off;
2969	iadd->size = pos - off;
2970
2971	if ((ret = xd3_iopt_finish_encoding (stream, iadd))) { return ret; }
2972	}
2973
2974	return 0;
2975	}
2976
2977	/* This function calls xd3_iopt_finish_encoding to finish encoding an
2978	* instruction, and it may also produce an add instruction for an
2979	* unmatched region. */
2980	static int
2981	xd3_iopt_add_encoding (xd3_stream stream, xd3_rinst inst)
2982	{
2983	int ret;
2984	xd3_rinst iadd;
2985
2986	if ((ret = xd3_iopt_add (stream, inst->pos, & iadd))) { return ret; }
2987
2988	if ((ret = xd3_iopt_finish_encoding (stream, inst))) { return ret; }
2989
2990	return 0;
2991	}
2992
2993	/* Generates a final add instruction to encode the remaining input. */
2994	static int
2995	xd3_iopt_add_finalize (xd3_stream *stream)
2996	{
2997	int ret;
2998	xd3_rinst iadd;
2999
3000	if ((ret = xd3_iopt_add (stream, stream->avail_in, & iadd))) { return ret; }
3001
3002	if (stream->iout)
3003	{
3004	if ((ret = xd3_emit_single (stream, stream->iout, stream->iout->code1))) { return ret; }
3005
3006	xd3_iopt_free_nonadd (stream, stream->iout);
3007	stream->iout = NULL;
3008	}
3009
3010	return 0;
3011	}
3012
3013	/* Compact the instruction buffer by choosing the best non-overlapping
3014	* instructions when lazy string-matching. There are no ADDs in the
3015	* iopt buffer because those are synthesized in xd3_iopt_add_encoding
3016	* and during xd3_iopt_add_finalize. */
3017	static int
3018	xd3_iopt_flush_instructions (xd3_stream *stream, int force)
3019	{
3020	xd3_rinst *r1 = xd3_rlist_front (& stream->iopt_used);
3021	xd3_rinst *r2;
3022	xd3_rinst *r3;
3023	usize_t r1end;
3024	usize_t r2end;
3025	usize_t r2off;
3026	usize_t r2moff;
3027	usize_t gap;
3028	usize_t flushed;
3029	int ret;
3030
3031	XD3_ASSERT (xd3_iopt_check (stream));
3032
3033	/* Note: once tried to skip this step if it's possible to assert
3034	* there are no overlapping instructions. Doesn't work because
3035	* xd3_opt_erase leaves overlapping instructions. */
3036	while (! xd3_rlist_end (& stream->iopt_used, r1) &&
3037	! xd3_rlist_end (& stream->iopt_used, r2 = xd3_rlist_next (r1)))
3038	{
3039	r1end = r1->pos + r1->size;
3040
3041	/* If the instructions do not overlap, continue. */
3042	if (r1end <= r2->pos)
3043	{
3044	r1 = r2;
3045	continue;
3046	}
3047
3048	r2end = r2->pos + r2->size;
3049
3050	/* The min_match adjustments prevent this. */
3051	XD3_ASSERT (r2end > (r1end + LEAST_MATCH_INCR));
3052
3053	/* If r3 is available... */
3054	if (! xd3_rlist_end (& stream->iopt_used, r3 = xd3_rlist_next (r2)))
3055	{
3056	/* If r3 starts before r1 finishes or just about, r2 is irrelevant */
3057	if (r3->pos <= r1end + 1)
3058	{
3059	xd3_iopt_free (stream, r2);
3060	continue;
3061	}
3062	}
3063	else if (! force)
3064	{
3065	/* Unless force, end the loop when r3 is not available. */
3066	break;
3067	}
3068
3069	r2off = r2->pos - r1->pos;
3070	r2moff = r2end - r1end;
3071	gap = r2end - r1->pos;
3072
3073	/* If the two matches overlap almost entirely, choose the better match
3074	* and discard the other. The else branch can still create inefficient
3075	* copies, e.g., a 4-byte copy that takes 4 bytes to encode, which
3076	* xd3_smatch() wouldn't allow by its crude efficiency check. However,
3077	* in this case there are adjacent copies which mean the add would cost
3078	* one extra byte. Allow the inefficiency here. */
3079	if (gap < 2*MIN_MATCH \|\| r2moff <= 2 \|\| r2off <= 2)
3080	{
3081	/* Only one match should be used, choose the longer one. */
3082	if (r1->size < r2->size)
3083	{
3084	xd3_iopt_free (stream, r1);
3085	r1 = r2;
3086	}
3087	else
3088	{
3089	/* We are guaranteed that r1 does not overlap now, so advance past r2 */
3090	r1 = xd3_iopt_free (stream, r2);
3091	}
3092	continue;
3093	}
3094	else
3095	{
3096	/* Shorten one of the instructions -- could be optimized
3097	* based on the address cache. */
3098	usize_t average;
3099	usize_t newsize;
3100	usize_t adjust1;
3101
3102	XD3_ASSERT (r1end > r2->pos && r2end > r1->pos);
3103
3104	/* Try to balance the length of both instructions, but avoid
3105	* making both longer than MAX_MATCH_SPLIT . */
3106	average = gap / 2;
3107	newsize = min (MAX_MATCH_SPLIT, gap - average);
3108
3109	/* Should be possible to simplify this code. */
3110	if (newsize > r1->size)
3111	{
3112	/* shorten r2 */
3113	adjust1 = r1end - r2->pos;
3114	}
3115	else if (newsize > r2->size)
3116	{
3117	/* shorten r1 */
3118	adjust1 = r1end - r2->pos;
3119
3120	XD3_ASSERT (r1->size > adjust1);
3121
3122	r1->size -= adjust1;
3123
3124	/* don't shorten r2 */
3125	adjust1 = 0;
3126	}
3127	else
3128	{
3129	/* shorten r1 */
3130	adjust1 = r1->size - newsize;
3131
3132	if (r2->pos > r1end - adjust1)
3133	{
3134	adjust1 -= r2->pos - (r1end - adjust1);
3135	}
3136
3137	XD3_ASSERT (r1->size > adjust1);
3138
3139	r1->size -= adjust1;
3140
3141	/* shorten r2 */
3142	XD3_ASSERT (r1->pos + r1->size >= r2->pos);
3143
3144	adjust1 = r1->pos + r1->size - r2->pos;
3145	}
3146
3147	/* Fallthrough above if-else, shorten r2 */
3148	XD3_ASSERT (r2->size > adjust1);
3149
3150	r2->size -= adjust1;
3151	r2->pos += adjust1;
3152	r2->addr += adjust1;
3153
3154	XD3_ASSERT (r1->size >= MIN_MATCH);
3155	XD3_ASSERT (r2->size >= MIN_MATCH);
3156
3157	r1 = r2;
3158	}
3159	}
3160
3161	XD3_ASSERT (xd3_iopt_check (stream));
3162
3163	/* If forcing, pick instructions until the list is empty, otherwise
3164	* this empties 50% of the queue. */
3165	for (flushed = 0; ! xd3_rlist_empty (& stream->iopt_used); )
3166	{
3167	xd3_rinst *renc = xd3_rlist_pop_front (& stream->iopt_used);
3168	if ((ret = xd3_iopt_add_encoding (stream, renc)))
3169	{
3170	return ret;
3171	}
3172
3173	if (! force)
3174	{
3175	if (++flushed > stream->iopt_size / 2)
3176	{
3177	break;
3178	}
3179
3180	/* If there are only two instructions remaining, break,
3181	* because they were not optimized. This means there were
3182	* more than 50% eliminated by the loop above. */
3183	r1 = xd3_rlist_front (& stream->iopt_used);
3184	if (xd3_rlist_end(& stream->iopt_used, r1) \|\|
3185	xd3_rlist_end(& stream->iopt_used, r2 = xd3_rlist_next (r1)) \|\|
3186	xd3_rlist_end(& stream->iopt_used, r3 = xd3_rlist_next (r2)))
3187	{
3188	break;
3189	}
3190	}
3191	}
3192
3193	XD3_ASSERT (xd3_iopt_check (stream));
3194
3195	XD3_ASSERT (!force \|\| xd3_rlist_length (& stream->iopt_used) == 0);
3196
3197	return 0;
3198	}
3199
3200	static int
3201	xd3_iopt_get_slot (xd3_stream stream, xd3_rinst* iptr)
3202	{
3203	xd3_rinst *i;
3204	int ret;
3205
3206	if (xd3_rlist_empty (& stream->iopt_free))
3207	{
3208	if (stream->iopt_unlimited)
3209	{
3210	usize_t elts = XD3_ALLOCSIZE / sizeof(xd3_rinst);
3211
3212	if ((ret = xd3_alloc_iopt (stream, elts)))
3213	{
3214	return ret;
3215	}
3216
3217	stream->iopt_size += elts;
3218	}
3219	else
3220	{
3221	if ((ret = xd3_iopt_flush_instructions (stream, 0))) { return ret; }
3222
3223	XD3_ASSERT (! xd3_rlist_empty (& stream->iopt_free));
3224	}
3225	}
3226
3227	i = xd3_rlist_pop_back (& stream->iopt_free);
3228
3229	xd3_rlist_push_back (& stream->iopt_used, i);
3230
3231	(*iptr) = i;
3232
3233	++stream->i_slots_used;
3234
3235	return 0;
3236	}
3237
3238	/* A copy is about to be emitted that extends backwards to POS,
3239	* therefore it may completely cover some existing instructions in the
3240	* buffer. If an instruction is completely covered by this new match,
3241	* erase it. If the new instruction is covered by the previous one,
3242	* return 1 to skip it. */
3243	static void
3244	xd3_iopt_erase (xd3_stream *stream, usize_t pos, usize_t size)
3245	{
3246	while (! xd3_rlist_empty (& stream->iopt_used))
3247	{
3248	xd3_rinst *r = xd3_rlist_back (& stream->iopt_used);
3249
3250	/* Verify that greedy is working. The previous instruction
3251	* should end before the new one begins. */
3252	XD3_ASSERT ((stream->flags & XD3_BEGREEDY) == 0 \|\| (r->pos + r->size <= pos));
3253	/* Verify that min_match is working. The previous instruction
3254	* should end before the new one ends. */
3255	XD3_ASSERT ((stream->flags & XD3_BEGREEDY) != 0 \|\| (r->pos + r->size < pos + size));
3256
3257	/* See if the last instruction starts before the new
3258	* instruction. If so, there is nothing to erase. */
3259	if (r->pos < pos)
3260	{
3261	return;
3262	}
3263
3264	/* Otherwise, the new instruction covers the old one, delete it
3265	and repeat. */
3266	xd3_rlist_remove (r);
3267	xd3_rlist_push_back (& stream->iopt_free, r);
3268	--stream->i_slots_used;
3269	}
3270	}
3271
3272	/* This function tells the last matched input position. */
3273	static usize_t
3274	xd3_iopt_last_matched (xd3_stream *stream)
3275	{
3276	xd3_rinst *r;
3277
3278	if (xd3_rlist_empty (& stream->iopt_used))
3279	{
3280	return 0;
3281	}
3282
3283	r = xd3_rlist_back (& stream->iopt_used);
3284
3285	return r->pos + r->size;
3286	}
3287
3288	/*********************************************************
3289	Emit routines
3290	***********************************************************/
3291
3292	static int
3293	xd3_emit_single (xd3_stream stream, xd3_rinst single, usize_t code)
3294	{
3295	int has_size = stream->code_table[code].size1 == 0;
3296	int ret;
3297
3298	IF_DEBUG2 (DP(RINT "[emit1] %u %s (%u) code %u\n",
3299	single->pos,
3300	xd3_rtype_to_string ((xd3_rtype) single->type, 0),
3301	single->size,
3302	code));
3303
3304	if ((ret = xd3_emit_byte (stream, & INST_TAIL (stream), code)))
3305	{
3306	return ret;
3307	}
3308
3309	if (has_size)
3310	{
3311	if ((ret = xd3_emit_size (stream, & INST_TAIL (stream), single->size)))
3312	{
3313	return ret;
3314	}
3315	}
3316
3317	return 0;
3318	}
3319
3320	static int
3321	xd3_emit_double (xd3_stream stream, xd3_rinst first,
3322	xd3_rinst *second, usize_t code)
3323	{
3324	int ret;
3325
3326	/* All double instructions use fixed sizes, so all we need to do is
3327	* output the instruction code, no sizes. */
3328	XD3_ASSERT (stream->code_table[code].size1 != 0 &&
3329	stream->code_table[code].size2 != 0);
3330
3331	if ((ret = xd3_emit_byte (stream, & INST_TAIL (stream), code)))
3332	{
3333	return ret;
3334	}
3335
3336	IF_DEBUG2 (DP(RINT "[emit2]: %u %s (%u) %s (%u) code %u\n",
3337	first->pos,
3338	xd3_rtype_to_string ((xd3_rtype) first->type, 0),
3339	first->size,
3340	xd3_rtype_to_string ((xd3_rtype) second->type, 0),
3341	second->size,
3342	code));
3343
3344	return 0;
3345	}
3346
3347	/* This enters a potential run instruction into the iopt buffer. The
3348	* position argument is relative to the target window. */
3349	static int
3350	xd3_emit_run (xd3_stream stream, usize_t pos, usize_t size, uint8_t run_c)
3351	{
3352	xd3_rinst* ri;
3353	int ret;
3354
3355	if ((ret = xd3_iopt_get_slot (stream, & ri))) { return ret; }
3356
3357	ri->type = XD3_RUN;
3358	ri->xtra = *run_c;
3359	ri->pos = pos;
3360	ri->size = size;
3361
3362	return 0;
3363	}
3364
3365	/* This enters a potential copy instruction into the iopt buffer. The
3366	* position argument is relative to the target window.. */
3367	int
3368	xd3_found_match (xd3_stream *stream, usize_t pos,
3369	usize_t size, xoff_t addr, int is_source)
3370	{
3371	xd3_rinst* ri;
3372	int ret;
3373
3374	if ((ret = xd3_iopt_get_slot (stream, & ri))) { return ret; }
3375
3376	ri->type = XD3_CPY;
3377	ri->xtra = is_source;
3378	ri->pos = pos;
3379	ri->size = size;
3380	ri->addr = addr;
3381
3382	return 0;
3383	}
3384
3385	static int
3386	xd3_emit_hdr (xd3_stream *stream)
3387	{
3388	int ret;
3389	int use_secondary = stream->sec_type != NULL;
3390	int use_adler32 = stream->flags & (XD3_ADLER32 \| XD3_ADLER32_RECODE);
3391	int vcd_source = xd3_encoder_used_source (stream);
3392	usize_t win_ind = 0;
3393	usize_t del_ind = 0;
3394	usize_t enc_len;
3395	usize_t tgt_len;
3396	usize_t data_len;
3397	usize_t inst_len;
3398	usize_t addr_len;
3399
3400	if (stream->current_window == 0)
3401	{
3402	usize_t hdr_ind = 0;
3403	int use_appheader = stream->enc_appheader != NULL;
3404	int use_gencodetbl = GENERIC_ENCODE_TABLES &&
3405	(stream->code_table_desc != & __rfc3284_code_table_desc);
3406
3407	if (use_secondary) { hdr_ind \|= VCD_SECONDARY; }
3408	if (use_gencodetbl) { hdr_ind \|= VCD_CODETABLE; }
3409	if (use_appheader) { hdr_ind \|= VCD_APPHEADER; }
3410
3411	if ((ret = xd3_emit_byte (stream, & HDR_TAIL (stream),
3412	VCDIFF_MAGIC1)) != 0 \|\|
3413	(ret = xd3_emit_byte (stream, & HDR_TAIL (stream),
3414	VCDIFF_MAGIC2)) != 0 \|\|
3415	(ret = xd3_emit_byte (stream, & HDR_TAIL (stream),
3416	VCDIFF_MAGIC3)) != 0 \|\|
3417	(ret = xd3_emit_byte (stream, & HDR_TAIL (stream),
3418	VCDIFF_VERSION)) != 0 \|\|
3419	(ret = xd3_emit_byte (stream, & HDR_TAIL (stream), hdr_ind)) != 0)
3420	{
3421	return ret;
3422	}
3423
3424	/* Secondary compressor ID */
3425	#if SECONDARY_ANY
3426	if (use_secondary &&
3427	(ret = xd3_emit_byte (stream, & HDR_TAIL (stream),
3428	stream->sec_type->id)))
3429	{
3430	return ret;
3431	}
3432	#endif
3433
3434	/* Compressed code table */
3435	if (use_gencodetbl)
3436	{
3437	usize_t code_table_size;
3438	const uint8_t *code_table_data;
3439
3440	if ((ret = stream->comp_table_func (stream, & code_table_data,
3441	& code_table_size)))
3442	{
3443	return ret;
3444	}
3445
3446	if ((ret = xd3_emit_size (stream, & HDR_TAIL (stream),
3447	code_table_size + 2)) \|\|
3448	(ret = xd3_emit_byte (stream, & HDR_TAIL (stream),
3449	stream->code_table_desc->near_modes)) \|\|
3450	(ret = xd3_emit_byte (stream, & HDR_TAIL (stream),
3451	stream->code_table_desc->same_modes)) \|\|
3452	(ret = xd3_emit_bytes (stream, & HDR_TAIL (stream),
3453	code_table_data, code_table_size)))
3454	{
3455	return ret;
3456	}
3457	}
3458
3459	/* Application header */
3460	if (use_appheader)
3461	{
3462	if ((ret = xd3_emit_size (stream, & HDR_TAIL (stream),
3463	stream->enc_appheadsz)) \|\|
3464	(ret = xd3_emit_bytes (stream, & HDR_TAIL (stream),
3465	stream->enc_appheader,
3466	stream->enc_appheadsz)))
3467	{
3468	return ret;
3469	}
3470	}
3471	}
3472
3473	/* try to compress this window */
3474	#if SECONDARY_ANY
3475	if (use_secondary)
3476	{
3477	int data_sec = 0;
3478	int inst_sec = 0;
3479	int addr_sec = 0;
3480
3481	# define ENCODE_SECONDARY_SECTION(UPPER,LOWER) \
3482	((stream->flags & XD3_SEC_NO ## UPPER) == 0 && \
3483	(ret = xd3_encode_secondary (stream, \
3484	& UPPER ## _HEAD (stream), \
3485	& UPPER ## _TAIL (stream), \
3486	& xd3_sec_ ## LOWER (stream), \
3487	& stream->sec_ ## LOWER, \
3488	& LOWER ## _sec)))
3489
3490	if (ENCODE_SECONDARY_SECTION (DATA, data) \|\|
3491	ENCODE_SECONDARY_SECTION (INST, inst) \|\|
3492	ENCODE_SECONDARY_SECTION (ADDR, addr))
3493	{
3494	return ret;
3495	}
3496
3497	del_ind \|= (data_sec ? VCD_DATACOMP : 0);
3498	del_ind \|= (inst_sec ? VCD_INSTCOMP : 0);
3499	del_ind \|= (addr_sec ? VCD_ADDRCOMP : 0);
3500	}
3501	#endif
3502
3503	/* if (vcd_target) { win_ind \|= VCD_TARGET; } */
3504	if (vcd_source) { win_ind \|= VCD_SOURCE; }
3505	if (use_adler32) { win_ind \|= VCD_ADLER32; }
3506
3507	/* window indicator */
3508	if ((ret = xd3_emit_byte (stream, & HDR_TAIL (stream), win_ind)))
3509	{
3510	return ret;
3511	}
3512
3513	/* source window */
3514	if (vcd_source)
3515	{
3516	/* or (vcd_target) { ... } */
3517	if ((ret = xd3_emit_size (stream, & HDR_TAIL (stream),
3518	stream->src->srclen)) \|\|
3519	(ret = xd3_emit_offset (stream, & HDR_TAIL (stream),
3520	stream->src->srcbase))) { return ret; }
3521	}
3522
3523	tgt_len = stream->avail_in;
3524	data_len = xd3_sizeof_output (DATA_HEAD (stream));
3525	inst_len = xd3_sizeof_output (INST_HEAD (stream));
3526	addr_len = xd3_sizeof_output (ADDR_HEAD (stream));
3527
3528	/* The enc_len field is a redundency for future extensions.*/
3529	enc_len = (1 + (xd3_sizeof_size (tgt_len) +
3530	xd3_sizeof_size (data_len) +
3531	xd3_sizeof_size (inst_len) +
3532	xd3_sizeof_size (addr_len)) +
3533	data_len +
3534	inst_len +
3535	addr_len +
3536	(use_adler32 ? 4 : 0));
3537
3538	if ((ret = xd3_emit_size (stream, & HDR_TAIL (stream), enc_len)) \|\|
3539	(ret = xd3_emit_size (stream, & HDR_TAIL (stream), tgt_len)) \|\|
3540	(ret = xd3_emit_byte (stream, & HDR_TAIL (stream), del_ind)) \|\|
3541	(ret = xd3_emit_size (stream, & HDR_TAIL (stream), data_len)) \|\|
3542	(ret = xd3_emit_size (stream, & HDR_TAIL (stream), inst_len)) \|\|
3543	(ret = xd3_emit_size (stream, & HDR_TAIL (stream), addr_len)))
3544	{
3545	return ret;
3546	}
3547
3548	if (use_adler32)
3549	{
3550	uint8_t send[4];
3551	uint32_t a32;
3552
3553	if (stream->flags & XD3_ADLER32)
3554	{
3555	a32 = adler32 (1L, stream->next_in, stream->avail_in);
3556	}
3557	else
3558	{
3559	a32 = stream->recode_adler32;
3560	}
3561
3562	/* Four bytes. */
3563	send[0] = (uint8_t) (a32 >> 24);
3564	send[1] = (uint8_t) (a32 >> 16);
3565	send[2] = (uint8_t) (a32 >> 8);
3566	send[3] = (uint8_t) (a32 & 0x000000FFU);
3567
3568	if ((ret = xd3_emit_bytes (stream, & HDR_TAIL (stream), send, 4)))
3569	{
3570	return ret;
3571	}
3572	}
3573
3574	return 0;
3575	}
3576
3577	/****************************************************************
3578	Encode routines
3579	****************************************************************/
3580
3581	static int
3582	xd3_encode_buffer_leftover (xd3_stream *stream)
3583	{
3584	usize_t take;
3585	usize_t room;
3586
3587	/* Allocate the buffer. */
3588	if (stream->buf_in == NULL &&
3589	(stream->buf_in = (uint8_t*) xd3_alloc (stream, stream->winsize, 1)) == NULL)
3590	{
3591	return ENOMEM;
3592	}
3593
3594	IF_DEBUG2 (DP(RINT "[leftover] flush?=%s\n", (stream->flags & XD3_FLUSH) ? "yes" : "no"));
3595
3596	/* Take leftover input first. */
3597	if (stream->buf_leftover != NULL)
3598	{
3599	XD3_ASSERT (stream->buf_avail == 0);
3600	XD3_ASSERT (stream->buf_leftavail < stream->winsize);
3601
3602	IF_DEBUG2 (DP(RINT "[leftover] previous %u avail %u\n", stream->buf_leftavail, stream->avail_in));
3603
3604	memcpy (stream->buf_in, stream->buf_leftover, stream->buf_leftavail);
3605
3606	stream->buf_leftover = NULL;
3607	stream->buf_avail = stream->buf_leftavail;
3608	}
3609
3610	/* Copy into the buffer. */
3611	room = stream->winsize - stream->buf_avail;
3612	take = min (room, stream->avail_in);
3613
3614	memcpy (stream->buf_in + stream->buf_avail, stream->next_in, take);
3615
3616	stream->buf_avail += take;
3617
3618	if (take < stream->avail_in)
3619	{
3620	/* Buffer is full */
3621	stream->buf_leftover = stream->next_in + take;
3622	stream->buf_leftavail = stream->avail_in - take;
3623	}
3624	else if ((stream->buf_avail < stream->winsize) && !(stream->flags & XD3_FLUSH))
3625	{
3626	/* Buffer has space */
3627	IF_DEBUG2 (DP(RINT "[leftover] emptied %u\n", take));
3628	return XD3_INPUT;
3629	}
3630
3631	/* Use the buffer: */
3632	IF_DEBUG2 (DP(RINT "[leftover] take %u remaining %u\n", take, stream->buf_leftavail));
3633	stream->next_in = stream->buf_in;
3634	stream->avail_in = stream->buf_avail;
3635	stream->buf_avail = 0;
3636
3637	return 0;
3638	}
3639
3640	/* Allocates one block of xd3_rlist elements */
3641	static int
3642	xd3_alloc_iopt (xd3_stream *stream, usize_t elts)
3643	{
3644	usize_t i;
3645	xd3_iopt_buflist* last =
3646	(xd3_iopt_buflist*) xd3_alloc (stream, sizeof (xd3_iopt_buflist), 1);
3647
3648	if (last == NULL \|\|
3649	(last->buffer = (xd3_rinst*) xd3_alloc (stream, sizeof (xd3_rinst), elts)) == NULL)
3650	{
3651	return ENOMEM;
3652	}
3653
3654	last->next = stream->iopt_alloc;
3655	stream->iopt_alloc = last;
3656
3657	for (i = 0; i < elts; i += 1)
3658	{
3659	xd3_rlist_push_back (& stream->iopt_free, & last->buffer[i]);
3660	}
3661
3662	return 0;
3663	}
3664
3665	/* This function allocates all memory initially used by the encoder. */
3666	static int
3667	xd3_encode_init (xd3_stream *stream, int full_init)
3668	{
3669	int i;
3670
3671	if (full_init)
3672	{
3673	int large_comp = (stream->src != NULL);
3674	int small_comp = ! (stream->flags & XD3_NOCOMPRESS);
3675
3676	/* Memory allocations for checksum tables are delayed until
3677	* xd3_string_match_init in the first call to string_match--that way
3678	* identical or short inputs require no table allocation. */
3679	if (large_comp)
3680	{
3681	usize_t hash_values = (stream->srcwin_maxsz /
3682	stream->smatcher.large_step);
3683
3684	xd3_size_hashtable (stream,
3685	hash_values,
3686	& stream->large_hash);
3687	}
3688
3689	if (small_comp)
3690	{
3691	/* TODO: This is under devel: used to have min(sprevsz) here, which sort
3692	* of makes sense, but observed fast performance w/ larger tables, which
3693	* also sort of makes sense. @@@ */
3694	usize_t hash_values = stream->winsize;
3695
3696	xd3_size_hashtable (stream,
3697	hash_values,
3698	& stream->small_hash);
3699	}
3700	}
3701
3702	/* data buffers */
3703	for (i = 0; i < ENC_SECTS; i += 1)
3704	{
3705	if ((stream->enc_heads[i] =
3706	stream->enc_tails[i] =
3707	xd3_alloc_output (stream, NULL)) == NULL)
3708	{
3709	return ENOMEM;
3710	}
3711	}
3712
3713	/* iopt buffer */
3714	xd3_rlist_init (& stream->iopt_used);
3715	xd3_rlist_init (& stream->iopt_free);
3716
3717	if (xd3_alloc_iopt (stream, stream->iopt_size) != 0) { goto fail; }
3718
3719	XD3_ASSERT (xd3_rlist_length (& stream->iopt_free) == stream->iopt_size);
3720	XD3_ASSERT (xd3_rlist_length (& stream->iopt_used) == 0);
3721
3722	/* address cache, code table */
3723	stream->acache.s_near = stream->code_table_desc->near_modes;
3724	stream->acache.s_same = stream->code_table_desc->same_modes;
3725	stream->code_table = stream->code_table_func ();
3726
3727	return xd3_alloc_cache (stream);
3728
3729	fail:
3730
3731	return ENOMEM;
3732	}
3733
3734	int
3735	xd3_encode_init_full (xd3_stream *stream)
3736	{
3737	return xd3_encode_init (stream, 1);
3738	}
3739
3740	int
3741	xd3_encode_init_partial (xd3_stream *stream)
3742	{
3743	return xd3_encode_init (stream, 0);
3744	}
3745
3746	/* Called after the ENC_POSTOUT state, this puts the output buffers
3747	* back into separate lists and re-initializes some variables. (The
3748	* output lists were spliced together during the ENC_FLUSH state.) */
3749	static void
3750	xd3_encode_reset (xd3_stream *stream)
3751	{
3752	int i;
3753	xd3_output *olist;
3754
3755	stream->avail_in = 0;
3756	stream->small_reset = 1;
3757	stream->i_slots_used = 0;
3758
3759	if (stream->src != NULL)
3760	{
3761	stream->src->srcbase = 0;
3762	stream->src->srclen = 0;
3763	stream->srcwin_decided = 0;
3764	stream->srcwin_decided_early = 0;
3765	stream->match_minaddr = 0;
3766	stream->match_maxaddr = 0;
3767	stream->taroff = 0;
3768	}
3769
3770	/* Reset output chains. */
3771	olist = stream->enc_heads[0];
3772
3773	for (i = 0; i < ENC_SECTS; i += 1)
3774	{
3775	XD3_ASSERT (olist != NULL);
3776
3777	stream->enc_heads[i] = olist;
3778	stream->enc_tails[i] = olist;
3779	olist = olist->next_page;
3780
3781	stream->enc_heads[i]->next = 0;
3782	stream->enc_heads[i]->next_page = NULL;
3783
3784	stream->enc_tails[i]->next_page = NULL;
3785	stream->enc_tails[i] = stream->enc_heads[i];
3786	}
3787
3788	xd3_freelist_output (stream, olist);
3789	}
3790
3791	/* The main encoding routine. */
3792	int
3793	xd3_encode_input (xd3_stream *stream)
3794	{
3795	int ret, i;
3796
3797	if (stream->dec_state != 0)
3798	{
3799	stream->msg = "encoder/decoder transition";
3800	return XD3_INTERNAL;
3801	}
3802
3803	switch (stream->enc_state)
3804	{
3805	case ENC_INIT:
3806	/* Only reached on first time through: memory setup. */
3807	if ((ret = xd3_encode_init_full (stream))) { return ret; }
3808
3809	stream->enc_state = ENC_INPUT;
3810
3811	case ENC_INPUT:
3812
3813	/* If there is no input yet, just return. This checks for
3814	* next_in == NULL, not avail_in == 0 since zero bytes is a
3815	* valid input. There is an assertion in xd3_avail_input() that
3816	* next_in != NULL for this reason. By returning right away we
3817	* avoid creating an input buffer before the caller has supplied
3818	* its first data. It is possible for xd3_avail_input to be
3819	* called both before and after the first call to
3820	* xd3_encode_input(). */
3821	if (stream->next_in == NULL)
3822	{
3823	return XD3_INPUT;
3824	}
3825
3826	enc_flush:
3827	/* See if we should buffer the input: either if there is already
3828	* a leftover buffer, or if the input is short of winsize
3829	* without flush. The label at this point is reached by a goto
3830	* below, when there is leftover input after postout. */
3831	if ((stream->buf_leftover != NULL) \|\|
3832	(stream->buf_avail != 0) \|\|
3833	(stream->avail_in < stream->winsize && ! (stream->flags & XD3_FLUSH)))
3834	{
3835	if ((ret = xd3_encode_buffer_leftover (stream))) { return ret; }
3836	}
3837
3838	/* Initalize the address cache before each window. */
3839	xd3_init_cache (& stream->acache);
3840
3841	stream->input_position = 0;
3842	stream->min_match = MIN_MATCH;
3843	stream->unencoded_offset = 0;
3844
3845	stream->enc_state = ENC_SEARCH;
3846
3847	IF_DEBUG2 (DP(RINT "[WINSTART:%"Q"u] input bytes %u offset %"Q"u\n",
3848	stream->current_window, stream->avail_in,
3849	stream->total_in));
3850	return XD3_WINSTART;
3851
3852	case ENC_SEARCH:
3853	IF_DEBUG2 (DP(RINT "[SEARCH] match_state %d avail_in %u %s\n",
3854	stream->match_state, stream->avail_in,
3855	stream->src ? "source" : "no source"));
3856
3857	/* Reentrant matching. */
3858	if (stream->src != NULL)
3859	{
3860	switch (stream->match_state)
3861	{
3862	case MATCH_TARGET:
3863	/* Try matching forward at the start of the target.
3864	* This is entered the first time through, to check for
3865	* a perfect match, and whenever there is a source match
3866	* that extends to the end of the previous window. The
3867	* match_srcpos field is initially zero and later set
3868	* during xd3_source_extend_match. */
3869
3870	if (stream->avail_in > 0)
3871	{
3872	/* This call can't fail because the source window is
3873	* unrestricted. */
3874	ret = xd3_source_match_setup (stream, stream->match_srcpos);
3875	XD3_ASSERT (ret == 0);
3876	stream->match_state = MATCH_FORWARD;
3877	}
3878	else
3879	{
3880	stream->match_state = MATCH_SEARCHING;
3881	stream->match_fwd = 0;
3882	}
3883	XD3_ASSERT (stream->match_fwd == 0);
3884
3885	case MATCH_FORWARD:
3886	case MATCH_BACKWARD:
3887	if (stream->avail_in != 0)
3888	{
3889	if ((ret = xd3_source_extend_match (stream)) != 0)
3890	{
3891	return ret;
3892	}
3893
3894	/* The search has to make forward progress here
3895	* or else it can get stuck in a match-backward
3896	* (getsrcblk) then match-forward (getsrcblk),
3897	* find insufficient match length, then repeat
3898	* exactly the same search.
3899	*/
3900	stream->input_position += stream->match_fwd;
3901	}
3902
3903	case MATCH_SEARCHING:
3904	/* Continue string matching. (It's possible that the
3905	* initial match continued through the entire input, in
3906	* which case we're still in MATCH_FORWARD and should
3907	* remain so for the next input window.) */
3908	break;
3909	}
3910	}
3911
3912	/* String matching... */
3913	if (stream->avail_in != 0 &&
3914	(ret = stream->smatcher.string_match (stream)))
3915	{
3916	return ret;
3917	}
3918
3919	stream->enc_state = ENC_INSTR;
3920
3921	case ENC_INSTR:
3922	/* Note: Jump here to encode VCDIFF deltas w/o using this
3923	* string-matching code. Merging code code enters here. */
3924
3925	/* Flush the instrution buffer, then possibly add one more
3926	* instruction, then emit the header. */
3927	if ((ret = xd3_iopt_flush_instructions (stream, 1)) \|\|
3928	(ret = xd3_iopt_add_finalize (stream)))
3929	{
3930	return ret;
3931	}
3932
3933	stream->enc_state = ENC_FLUSH;
3934
3935	case ENC_FLUSH:
3936	/* Note: main_recode_func() bypasses string-matching by setting
3937	* ENC_FLUSH. */
3938	if ((ret = xd3_emit_hdr (stream)))
3939	{
3940	return ret;
3941	}
3942
3943	/* Begin output. */
3944	stream->enc_current = HDR_HEAD (stream);
3945
3946	/* Chain all the outputs together. After doing this, it looks
3947	* as if there is only one section. The other enc_heads are set
3948	* to NULL to avoid freeing them more than once. */
3949	for (i = 1; i < ENC_SECTS; i += 1)
3950	{
3951	stream->enc_tails[i-1]->next_page = stream->enc_heads[i];
3952	stream->enc_heads[i] = NULL;
3953	}
3954
3955	enc_output:
3956
3957	stream->enc_state = ENC_POSTOUT;
3958	stream->next_out = stream->enc_current->base;
3959	stream->avail_out = stream->enc_current->next;
3960	stream->total_out += (xoff_t) stream->avail_out;
3961
3962	/* If there is any output in this buffer, return it, otherwise
3963	* fall through to handle the next buffer or finish the window
3964	* after all buffers have been output. */
3965	if (stream->avail_out > 0)
3966	{
3967	/* This is the only place xd3_encode returns XD3_OUTPUT */
3968	return XD3_OUTPUT;
3969	}
3970
3971	case ENC_POSTOUT:
3972
3973	if (stream->avail_out != 0)
3974	{
3975	stream->msg = "missed call to consume output";
3976	return XD3_INTERNAL;
3977	}
3978
3979	/* Continue outputting one buffer at a time, until the next is NULL. */
3980	if ((stream->enc_current = stream->enc_current->next_page) != NULL)
3981	{
3982	goto enc_output;
3983	}
3984
3985	stream->total_in += (xoff_t) stream->avail_in;
3986	stream->enc_state = ENC_POSTWIN;
3987
3988	IF_DEBUG2 (DP(RINT "[WINFINISH:%"Q"u] in=%"Q"u\n",
3989	stream->current_window,
3990	stream->total_in));
3991	return XD3_WINFINISH;
3992
3993	case ENC_POSTWIN:
3994
3995	xd3_encode_reset (stream);
3996
3997	stream->current_window += 1;
3998	stream->enc_state = ENC_INPUT;
3999
4000	/* If there is leftover input to flush, repeat. */
4001	if (stream->buf_leftover != NULL)
4002	{
4003	goto enc_flush;
4004	}
4005
4006	/* Ready for more input. */
4007	return XD3_INPUT;
4008
4009	default:
4010	stream->msg = "invalid state";
4011	return XD3_INTERNAL;
4012	}
4013	}
4014	#endif /* XD3_ENCODER */
4015
4016	/*****************************************************************
4017	Client convenience functions
4018	******************************************************************/
4019
4020	static int
4021	xd3_process_stream (int is_encode,
4022	xd3_stream *stream,
4023	int (func) (xd3_stream ),
4024	int close_stream,
4025	const uint8_t *input,
4026	usize_t input_size,
4027	uint8_t *output,
4028	usize_t *output_size,
4029	usize_t output_size_max)
4030	{
4031	usize_t ipos = 0;
4032	usize_t n = min(stream->winsize, input_size);
4033
4034	(*output_size) = 0;
4035
4036	stream->flags \|= XD3_FLUSH;
4037
4038	xd3_avail_input (stream, input + ipos, n);
4039	ipos += n;
4040
4041	for (;;)
4042	{
4043	int ret;
4044	switch((ret = func (stream)))
4045	{
4046	case XD3_OUTPUT: { /* memcpy below */ break; }
4047	case XD3_INPUT: {
4048	n = min(stream->winsize, input_size - ipos);
4049	if (n == 0) {
4050	goto done;
4051	}
4052	xd3_avail_input (stream, input + ipos, n);
4053	ipos += n;
4054	continue;
4055	}
4056	case XD3_GOTHEADER: { /* ignore */ continue; }
4057	case XD3_WINSTART: { /* ignore */ continue; }
4058	case XD3_WINFINISH: { /* ignore */ continue; }
4059	case XD3_GETSRCBLK:
4060	{
4061	stream->msg = "stream requires source input";
4062	return XD3_INTERNAL;
4063	}
4064	case 0:
4065	{
4066	/* xd3_encode_input/xd3_decode_input never return 0 */
4067	stream->msg = "invalid return: 0";
4068	return XD3_INTERNAL;
4069	}
4070	default:
4071	return ret;
4072	}
4073
4074	if (*output_size + stream->avail_out > output_size_max)
4075	{
4076	stream->msg = "insufficient output space";
4077	return ENOSPC;
4078	}
4079
4080	memcpy (output + *output_size, stream->next_out, stream->avail_out);
4081
4082	*output_size += stream->avail_out;
4083
4084	xd3_consume_output (stream);
4085	}
4086	done:
4087	return (close_stream == 0) ? 0 : xd3_close_stream (stream);
4088	}
4089
4090	static int
4091	xd3_process_memory (int is_encode,
4092	int (func) (xd3_stream ),
4093	int close_stream,
4094	const uint8_t *input,
4095	usize_t input_size,
4096	const uint8_t *source,
4097	usize_t source_size,
4098	uint8_t *output,
4099	usize_t *output_size,
4100	usize_t output_size_max,
4101	int flags) {
4102	xd3_stream stream;
4103	xd3_config config;
4104	xd3_source src;
4105	int ret;
4106
4107	memset (& stream, 0, sizeof (stream));
4108	memset (& config, 0, sizeof (config));
4109
4110	if (input == NULL \|\| output == NULL) {
4111	stream.msg = "invalid input/output buffer";
4112	ret = XD3_INTERNAL;
4113	goto exit;
4114	}
4115
4116	config.flags = flags;
4117
4118	if (is_encode)
4119	{
4120	config.srcwin_maxsz = source_size;
4121	config.winsize = min(input_size, (usize_t) XD3_DEFAULT_WINSIZE);
4122	config.iopt_size = min(input_size / 32, XD3_DEFAULT_IOPT_SIZE);
4123	config.iopt_size = max(config.iopt_size, 128U);
4124	config.sprevsz = xd3_pow2_roundup (config.winsize);
4125	}
4126
4127	if ((ret = xd3_config_stream (&stream, &config)) != 0)
4128	{
4129	goto exit;
4130	}
4131
4132	if (source != NULL)
4133	{
4134	memset (& src, 0, sizeof (src));
4135
4136	src.blksize = source_size;
4137	src.onblk = source_size;
4138	src.curblk = source;
4139	src.curblkno = 0;
4140
4141	if ((ret = xd3_set_source_and_size (&stream, &src, source_size)) != 0)
4142	{
4143	goto exit;
4144	}
4145	}
4146
4147	if ((ret = xd3_process_stream (is_encode,
4148	& stream,
4149	func, 1,
4150	input, input_size,
4151	output,
4152	output_size,
4153	output_size_max)) != 0)
4154	{
4155	goto exit;
4156	}
4157
4158	exit:
4159	if (ret != 0)
4160	{
4161	IF_DEBUG2 (DP(RINT "process_memory: %d: %s\n", ret, stream.msg));
4162	}
4163	xd3_free_stream(&stream);
4164	return ret;
4165	}
4166
4167	int
4168	xd3_decode_stream (xd3_stream *stream,
4169	const uint8_t *input,
4170	usize_t input_size,
4171	uint8_t *output,
4172	usize_t *output_size,
4173	usize_t output_size_max)
4174	{
4175	return xd3_process_stream (0, stream, & xd3_decode_input, 1,
4176	input, input_size,
4177	output, output_size, output_size_max);
4178	}
4179
4180	int
4181	xd3_decode_memory (const uint8_t *input,
4182	usize_t input_size,
4183	const uint8_t *source,
4184	usize_t source_size,
4185	uint8_t *output,
4186	usize_t *output_size,
4187	usize_t output_size_max,
4188	int flags) {
4189	return xd3_process_memory (0, & xd3_decode_input, 1,
4190	input, input_size,
4191	source, source_size,
4192	output, output_size, output_size_max,
4193	flags);
4194	}
4195
4196
4197	#if XD3_ENCODER
4198	int
4199	xd3_encode_stream (xd3_stream *stream,
4200	const uint8_t *input,
4201	usize_t input_size,
4202	uint8_t *output,
4203	usize_t *output_size,
4204	usize_t output_size_max)
4205	{
4206	return xd3_process_stream (1, stream, & xd3_encode_input, 1,
4207	input, input_size,
4208	output, output_size, output_size_max);
4209	}
4210
4211	int
4212	xd3_encode_memory (const uint8_t *input,
4213	usize_t input_size,
4214	const uint8_t *source,
4215	usize_t source_size,
4216	uint8_t *output,
4217	usize_t *output_size,
4218	usize_t output_size_max,
4219	int flags) {
4220	return xd3_process_memory (1, & xd3_encode_input, 1,
4221	input, input_size,
4222	source, source_size,
4223	output, output_size, output_size_max,
4224	flags);
4225	}
4226	#endif
4227
4228
4229	/*************************************************************
4230	String matching helpers
4231	*************************************************************/
4232
4233	#if XD3_ENCODER
4234	/* Do the initial xd3_string_match() checksum table setup.
4235	* Allocations are delayed until first use to avoid allocation
4236	* sometimes (e.g., perfect matches, zero-length inputs). */
42