Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log
Repository URL

xdelta3.c @ 185

Last change on this file since 185 was 185, checked in by geyser, 14 years ago

File size: 149.4 KB

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

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: nikanabo/current/xdelta/diy/xdelta3.c @ 185

Download in other formats: