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