Topic Text   Topic Comments (0)   Topic Properties   Topic Information nisse@hul...
Topic title: xdelta3 Tuesday November 20, 2012 11:45:26

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

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

[Add General Comment] to topic.

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