summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rwxr-xr-xxdelta3/Makefile2
-rwxr-xr-xxdelta3/xdelta3-fgk.h8
-rwxr-xr-xxdelta3/xdelta3-main.h14
-rwxr-xr-xxdelta3/xdelta3.c22
-rwxr-xr-xxdelta3/xdelta3.h1992
5 files changed, 1009 insertions, 1029 deletions
diff --git a/xdelta3/Makefile b/xdelta3/Makefile
index f65d38a..1bb4664 100755
--- a/xdelta3/Makefile
+++ b/xdelta3/Makefile
@@ -63,7 +63,7 @@ xdelta3: $(SOURCES)
63 63
64xdelta3-debug: $(SOURCES) 64xdelta3-debug: $(SOURCES)
65 $(CC) -g -Wall -Wshadow xdelta3.c -o xdelta3-debug -DXD3_MAIN=1 -DGENERIC_ENCODE_TABLES=1 \ 65 $(CC) -g -Wall -Wshadow xdelta3.c -o xdelta3-debug -DXD3_MAIN=1 -DGENERIC_ENCODE_TABLES=1 \
66 -DXD3_USE_LARGEFILE64=1 -DXD3_STDIO=1 -DREGRESSION_TEST=1 -DXD3_DEBUG=1 -DSECONDARY_DJW=1 -DSECONDARY_FGK=1 -lm 66 -DXD3_USE_LARGEFILE64=1 -DXD3_STDIO=1 -DREGRESSION_TEST=1 -DXD3_DEBUG=2 -DSECONDARY_DJW=1 -DSECONDARY_FGK=1 -lm
67 67
68$(PYTGT): $(SOURCES) 68$(PYTGT): $(SOURCES)
69 $(PYTHON) setup.py install --verbose --compile --force 69 $(PYTHON) setup.py install --verbose --compile --force
diff --git a/xdelta3/xdelta3-fgk.h b/xdelta3/xdelta3-fgk.h
index b3e25a5..343f0f3 100755
--- a/xdelta3/xdelta3-fgk.h
+++ b/xdelta3/xdelta3-fgk.h
@@ -755,14 +755,6 @@ static void fgk_destroy (xd3_stream *stream,
755{ 755{
756 if (h != NULL) 756 if (h != NULL)
757 { 757 {
758 IF_DEBUG1({
759 int i;
760 for (i = 0; i < ALPHABET_SIZE; i += 1)
761 {
762 XP(OF, "freq[%u] = %u\n", i, h->alphabet[i].weight);
763 }
764 });
765
766 xd3_free (stream, h->alphabet); 758 xd3_free (stream, h->alphabet);
767 xd3_free (stream, h->coded_bits); 759 xd3_free (stream, h->coded_bits);
768 xd3_free (stream, h->block_array); 760 xd3_free (stream, h->block_array);
diff --git a/xdelta3/xdelta3-main.h b/xdelta3/xdelta3-main.h
index 7932039..3dc5a5d 100755
--- a/xdelta3/xdelta3-main.h
+++ b/xdelta3/xdelta3-main.h
@@ -256,7 +256,6 @@ static const char *option_source_filename = NULL;
256 256
257static usize_t option_winsize = XD3_DEFAULT_WINSIZE; 257static usize_t option_winsize = XD3_DEFAULT_WINSIZE;
258static usize_t option_srcwinsz = XD3_DEFAULT_SRCWINSZ; 258static usize_t option_srcwinsz = XD3_DEFAULT_SRCWINSZ;
259static usize_t option_memsize = XD3_DEFAULT_MEMSIZE;
260 259
261/* This controls the number of times main repeats itself, only for profiling. */ 260/* This controls the number of times main repeats itself, only for profiling. */
262static int option_profile_cnt = 0; 261static int option_profile_cnt = 0;
@@ -338,7 +337,6 @@ main_config (void)
338 P(RINT "XD3_DEBUG=%d\n", XD3_DEBUG); 337 P(RINT "XD3_DEBUG=%d\n", XD3_DEBUG);
339 P(RINT "XD3_DEFAULT_CKSUM_SIZE=%d\n", XD3_DEFAULT_CKSUM_ADVANCE); 338 P(RINT "XD3_DEFAULT_CKSUM_SIZE=%d\n", XD3_DEFAULT_CKSUM_ADVANCE);
340 P(RINT "XD3_DEFAULT_IOPT_SIZE=%d\n", XD3_DEFAULT_IOPT_SIZE); 339 P(RINT "XD3_DEFAULT_IOPT_SIZE=%d\n", XD3_DEFAULT_IOPT_SIZE);
341 P(RINT "XD3_DEFAULT_MEMSIZE=%d\n", XD3_DEFAULT_MEMSIZE);
342 P(RINT "XD3_DEFAULT_SPREVSZ=%d\n", XD3_DEFAULT_SPREVSZ); 340 P(RINT "XD3_DEFAULT_SPREVSZ=%d\n", XD3_DEFAULT_SPREVSZ);
343 P(RINT "XD3_DEFAULT_SRCWINSZ=%d\n", XD3_DEFAULT_SRCWINSZ); 341 P(RINT "XD3_DEFAULT_SRCWINSZ=%d\n", XD3_DEFAULT_SRCWINSZ);
344 P(RINT "XD3_DEFAULT_WINSIZE=%d\n", XD3_DEFAULT_WINSIZE); 342 P(RINT "XD3_DEFAULT_WINSIZE=%d\n", XD3_DEFAULT_WINSIZE);
@@ -1916,7 +1914,6 @@ main_set_source (xd3_stream *stream, int cmd, main_file *sfile, xd3_source *sour
1916 1914
1917 if (option_verbose > 1) { XPR(NT "source window size: %u\n", option_srcwinsz); } 1915 if (option_verbose > 1) { XPR(NT "source window size: %u\n", option_srcwinsz); }
1918 if (option_verbose > 1) { XPR(NT "source block size: %u\n", source->blksize); } 1916 if (option_verbose > 1) { XPR(NT "source block size: %u\n", source->blksize); }
1919 if (option_verbose > 1) { XPR(NT "memory size: %u\n", option_memsize); }
1920 1917
1921 lru_size = (option_srcwinsz / source->blksize); 1918 lru_size = (option_srcwinsz / source->blksize);
1922 lru_size = max(1, lru_size); 1919 lru_size = max(1, lru_size);
@@ -2304,7 +2301,6 @@ main_input (xd3_cmd cmd,
2304 2301
2305 config.srcwin_maxsz = option_srcwinsz; 2302 config.srcwin_maxsz = option_srcwinsz;
2306 config.winsize = option_winsize; 2303 config.winsize = option_winsize;
2307 config.memsize = option_memsize;
2308 config.getblk = main_getblk_func; 2304 config.getblk = main_getblk_func;
2309 config.flags = stream_flags; 2305 config.flags = stream_flags;
2310 2306
@@ -2838,11 +2834,6 @@ main (int argc, char **argv)
2838 goto exit; 2834 goto exit;
2839 } 2835 }
2840 break; 2836 break;
2841 case 'M': if ((ret = main_atou (my_optarg, & option_memsize, XD3_ALLOCSIZE, 'M')))
2842 {
2843 goto exit;
2844 }
2845 break;
2846 case 'D': 2837 case 'D':
2847#if EXTERNAL_COMPRESSION == 0 2838#if EXTERNAL_COMPRESSION == 0
2848 if (! option_quiet) 2839 if (! option_quiet)
@@ -3039,9 +3030,8 @@ main_help (void)
3039 P(RINT " -V show version\n"); 3030 P(RINT " -V show version\n");
3040 3031
3041 P(RINT "memory options:\n"); 3032 P(RINT "memory options:\n");
3042 P(RINT " -B blksize source file block size\n"); 3033 P(RINT " -B bytes source window size\n");
3043 P(RINT " -M memsize memory budget for hash tables\n"); 3034 P(RINT " -W bytes input window size\n");
3044 P(RINT " -W winsize input window buffer size\n");
3045 3035
3046 P(RINT "compression options:\n"); 3036 P(RINT "compression options:\n");
3047 P(RINT " -s source source file to copy from (if any)\n"); 3037 P(RINT " -s source source file to copy from (if any)\n");
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c
index 92a87e4..146fc37 100755
--- a/xdelta3/xdelta3.c
+++ b/xdelta3/xdelta3.c
@@ -1178,7 +1178,6 @@ int xd3_compute_code_table_encoding (xd3_stream *in_stream, const xd3_dinst *cod
1178 1178
1179 /* Be exhaustive. */ 1179 /* Be exhaustive. */
1180 config.sprevsz = 1<<11; 1180 config.sprevsz = 1<<11;
1181 config.memsize = CODE_TABLE_STRING_SIZE;
1182 config.srcwin_size = CODE_TABLE_STRING_SIZE; 1181 config.srcwin_size = CODE_TABLE_STRING_SIZE;
1183 config.srcwin_maxsz = CODE_TABLE_STRING_SIZE; 1182 config.srcwin_maxsz = CODE_TABLE_STRING_SIZE;
1184 1183
@@ -1580,11 +1579,9 @@ xd3_size_log2 (usize_t slots)
1580 1579
1581static void 1580static void
1582xd3_size_hashtable (xd3_stream *stream, 1581xd3_size_hashtable (xd3_stream *stream,
1583 usize_t space, 1582 usize_t slots,
1584 xd3_hash_cfg *cfg) 1583 xd3_hash_cfg *cfg)
1585{ 1584{
1586 usize_t slots = space / sizeof (usize_t);
1587
1588 /* initialize ctable: the number of hash buckets is computed from the table of primes or 1585 /* initialize ctable: the number of hash buckets is computed from the table of primes or
1589 * the nearest power-of-two, in both cases rounding down in favor of using less 1586 * the nearest power-of-two, in both cases rounding down in favor of using less
1590 * memory. */ 1587 * memory. */
@@ -2436,7 +2433,6 @@ xd3_config_stream(xd3_stream *stream,
2436 /* Initial setup: no error checks yet */ 2433 /* Initial setup: no error checks yet */
2437 memset (stream, 0, sizeof (*stream)); 2434 memset (stream, 0, sizeof (*stream));
2438 2435
2439 stream->memsize = config->memsize ? config->memsize : XD3_DEFAULT_MEMSIZE;
2440 stream->winsize = config->winsize ? config->winsize : XD3_DEFAULT_WINSIZE; 2436 stream->winsize = config->winsize ? config->winsize : XD3_DEFAULT_WINSIZE;
2441 stream->sprevsz = config->sprevsz ? config->sprevsz : XD3_DEFAULT_SPREVSZ; 2437 stream->sprevsz = config->sprevsz ? config->sprevsz : XD3_DEFAULT_SPREVSZ;
2442 stream->iopt_size = config->iopt_size ? config->iopt_size : XD3_DEFAULT_IOPT_SIZE; 2438 stream->iopt_size = config->iopt_size ? config->iopt_size : XD3_DEFAULT_IOPT_SIZE;
@@ -3496,17 +3492,27 @@ xd3_encode_init (xd3_stream *stream)
3496 /* Memory allocations for checksum tables are delayed until xd3_string_match_init in the 3492 /* Memory allocations for checksum tables are delayed until xd3_string_match_init in the
3497 * first call to string_match--that way identical or short inputs require no table 3493 * first call to string_match--that way identical or short inputs require no table
3498 * allocation. */ 3494 * allocation. */
3495
3496 // TODO: experiments have to be done!!!
3499 if (large_comp) 3497 if (large_comp)
3500 { 3498 {
3501 xd3_size_hashtable (stream, stream->memsize, & stream->large_hash); 3499 usize_t hash_values = (stream->srcwin_maxsz / stream->smatcher.large_look);
3500
3501 xd3_size_hashtable (stream,
3502 hash_values,
3503 & stream->large_hash);
3504 IF_DEBUG1 (P(RINT "[encode_init] large hash %u slots\n", hash_values));
3502 } 3505 }
3503 3506
3504 if (small_comp) 3507 if (small_comp)
3505 { 3508 {
3506 /* Keep table small because small matches become less efficient after long. */ 3509 /* Hard-coded, keeps table small because small matches become inefficient. */
3510 usize_t hash_values = min(stream->winsize / stream->smatcher.small_look, 65536U);
3511
3507 xd3_size_hashtable (stream, 3512 xd3_size_hashtable (stream,
3508 min(stream->winsize, XD3_DEFAULT_MEMSIZE), 3513 hash_values,
3509 & stream->small_hash); 3514 & stream->small_hash);
3515 IF_DEBUG1 (P(RINT "[encode_init] small hash %u slots\n", hash_values));
3510 } 3516 }
3511 3517
3512 for (i = 0; i < ENC_SECTS; i += 1) 3518 for (i = 0; i < ENC_SECTS; i += 1)
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h
index 79723bf..e06a927 100755
--- a/xdelta3/xdelta3.h
+++ b/xdelta3/xdelta3.h
@@ -1,1000 +1,992 @@
1/* xdelta 3 - delta compression tools and library 1/* xdelta 3 - delta compression tools and library
2 * Copyright (C) 2001, 2003, 2004, 2005, 2006. Joshua P. MacDonald 2 * Copyright (C) 2001, 2003, 2004, 2005, 2006. Joshua P. MacDonald
3 * 3 *
4 * This program is free software; you can redistribute it and/or modify 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 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 6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version. 7 * (at your option) any later version.
8 * 8 *
9 * This program is distributed in the hope that it will be useful, 9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details. 12 * GNU General Public License for more details.
13 * 13 *
14 * You should have received a copy of the GNU General Public License 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 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 16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */ 17 */
18 18
19/* Welcome to Xdelta. If you want to know more about Xdelta, start by reading xdelta3.c. 19/* Welcome to Xdelta. If you want to know more about Xdelta, start by reading xdelta3.c.
20 * If you are ready to use the API, continue reading here. There are two interfaces -- 20 * If you are ready to use the API, continue reading here. There are two interfaces --
21 * xd3_encode_input and xd3_decode_input -- plus a dozen or so related calls. This 21 * xd3_encode_input and xd3_decode_input -- plus a dozen or so related calls. This
22 * interface is styled after Zlib. */ 22 * interface is styled after Zlib. */
23 23
24#ifndef _XDELTA3_H_ 24#ifndef _XDELTA3_H_
25#define _XDELTA3_H_ 25#define _XDELTA3_H_
26 26
27#include <stdlib.h> 27#include <stdlib.h>
28#include <string.h> 28#include <string.h>
29#include <sys/types.h> 29#include <sys/types.h>
30 30
31/**********************************************************************/ 31/**********************************************************************/
32 32
33/* Default configured value of stream->winsize. If the program supplies 33/* Default configured value of stream->winsize. If the program supplies
34 * xd3_encode_input() with data smaller than winsize the stream will 34 * xd3_encode_input() with data smaller than winsize the stream will
35 * automatically buffer the input, otherwise the input buffer is used directly. 35 * automatically buffer the input, otherwise the input buffer is used directly.
36 */ 36 */
37#ifndef XD3_DEFAULT_WINSIZE 37#ifndef XD3_DEFAULT_WINSIZE
38#define XD3_DEFAULT_WINSIZE (1U << 18) 38#define XD3_DEFAULT_WINSIZE (1U << 18)
39#endif 39#endif
40 40
41/* This is a unit of how far to advance the checksum position in one go. */ 41/* This is a unit of how far to advance the checksum position in one go. */
42#ifndef XD3_DEFAULT_CKSUM_ADVANCE 42#ifndef XD3_DEFAULT_CKSUM_ADVANCE
43#define XD3_DEFAULT_CKSUM_ADVANCE (1U << 14) 43#define XD3_DEFAULT_CKSUM_ADVANCE (1U << 14)
44#endif 44#endif
45 45
46/* Default total size of the source window used in xdelta3-main.h */ 46/* Default total size of the source window used in xdelta3-main.h */
47#ifndef XD3_DEFAULT_SRCWINSZ 47#ifndef XD3_DEFAULT_SRCWINSZ
48#define XD3_DEFAULT_SRCWINSZ (1U << 23) 48#define XD3_DEFAULT_SRCWINSZ (1U << 23)
49#endif 49#endif
50 50
51/* Default configured value of stream->memsize. This dictates how much memory Xdelta will 51/* When Xdelta requests a memory allocation for certain buffers, it rounds up to units of
52 * use for string-matching data structures. */ 52 * at least this size. The code assumes (and asserts) that this is a power-of-two. */
53#ifndef XD3_DEFAULT_MEMSIZE 53#ifndef XD3_ALLOCSIZE
54#define XD3_DEFAULT_MEMSIZE (1U << 18) 54#define XD3_ALLOCSIZE (1U<<14)
55#endif 55#endif
56 56
57/* When Xdelta requests a memory allocation for certain buffers, it rounds up to units of 57/* The XD3_HARDMAXWINSIZE parameter is a safety mechanism to protect decoders against
58 * at least this size. The code assumes (and asserts) that this is a power-of-two. */ 58 * malicious files. The decoder will never decode a window larger than this. If the file
59#ifndef XD3_ALLOCSIZE 59 * specifies VCD_TARGET the decoder may require two buffers of this size. Rationale for
60#define XD3_ALLOCSIZE (1U<<14) 60 * choosing 22-bits as a maximum: this means that in the worst case, any VCDIFF address
61#endif 61 * without a copy window will require 3 bytes to encode (7 bits per byte, HERE and SAME
62 62 * modes making every address within half the window away. */
63/* The XD3_HARDMAXWINSIZE parameter is a safety mechanism to protect decoders against 63#ifndef XD3_HARDMAXWINSIZE
64 * malicious files. The decoder will never decode a window larger than this. If the file 64#define XD3_HARDMAXWINSIZE (1U<<23)
65 * specifies VCD_TARGET the decoder may require two buffers of this size. Rationale for 65#endif
66 * choosing 22-bits as a maximum: this means that in the worst case, any VCDIFF address 66
67 * without a copy window will require 3 bytes to encode (7 bits per byte, HERE and SAME 67/* The XD3_NODECOMPRESSSIZE parameter tells the xdelta main routine not to try to
68 * modes making every address within half the window away. */ 68 * externally-decompress source inputs that are too large. Since these files must be
69#ifndef XD3_HARDMAXWINSIZE 69 * seekable, they are decompressed to a temporary file location and the user may not wish
70#define XD3_HARDMAXWINSIZE (1U<<23) 70 * for this. */
71#endif 71#ifndef XD3_NODECOMPRESSSIZE
72 72#define XD3_NODECOMPRESSSIZE (1U<<24)
73/* The XD3_NODECOMPRESSSIZE parameter tells the xdelta main routine not to try to 73#endif
74 * externally-decompress source inputs that are too large. Since these files must be 74
75 * seekable, they are decompressed to a temporary file location and the user may not wish 75/* The IOPT_SIZE value sets the size of a buffer used to batch overlapping copy
76 * for this. */ 76 * instructions before they are optimized by picking the best non-overlapping ranges. The
77#ifndef XD3_NODECOMPRESSSIZE 77 * larger this buffer, the longer a forced xd3_srcwin_setup() decision is held off. */
78#define XD3_NODECOMPRESSSIZE (1U<<24) 78#ifndef XD3_DEFAULT_IOPT_SIZE
79#endif 79#define XD3_DEFAULT_IOPT_SIZE 128
80 80#endif
81/* The IOPT_SIZE value sets the size of a buffer used to batch overlapping copy 81
82 * instructions before they are optimized by picking the best non-overlapping ranges. The 82/* The maximum distance backward to search for small matches */
83 * larger this buffer, the longer a forced xd3_srcwin_setup() decision is held off. */ 83#ifndef XD3_DEFAULT_SPREVSZ
84#ifndef XD3_DEFAULT_IOPT_SIZE 84#define XD3_DEFAULT_SPREVSZ (1U << 16)
85#define XD3_DEFAULT_IOPT_SIZE 128 85#endif
86#endif 86
87 87/* Sizes and addresses within VCDIFF windows are represented as usize_t
88/* The maximum distance backward to search for small matches */ 88 *
89#ifndef XD3_DEFAULT_SPREVSZ 89 * For source-file offsets and total file sizes, total input and output counts, the xoff_t
90#define XD3_DEFAULT_SPREVSZ (1U << 16) 90 * type is used. The decoder and encoder generally check for overflow of the xoff_t size,
91#endif 91 * and this is tested at the 32bit boundary [xdelta3-test.h].
92 92 */
93/* Sizes and addresses within VCDIFF windows are represented as usize_t 93#ifndef _WIN32
94 * 94typedef unsigned int usize_t;
95 * For source-file offsets and total file sizes, total input and output counts, the xoff_t 95typedef u_int8_t uint8_t;
96 * type is used. The decoder and encoder generally check for overflow of the xoff_t size, 96typedef u_int16_t uint16_t;
97 * and this is tested at the 32bit boundary [xdelta3-test.h]. 97typedef u_int32_t uint32_t;
98 */ 98typedef u_int64_t uint64_t;
99#ifndef _WIN32 99#else
100typedef unsigned int usize_t; 100// CRT_SECURE_NO_DEPRECATE silences warnings about sprintf() and strerror()
101typedef u_int8_t uint8_t; 101#define _CRT_SECURE_NO_DEPRECATE 1
102typedef u_int16_t uint16_t; 102#define _CRT_SECURE_COPP_OVERLOAD_STANDARD_NAMES 1
103typedef u_int32_t uint32_t; 103#define WIN32_LEAN_AND_MEAN
104typedef u_int64_t uint64_t; 104#include <windows.h>
105#else 105#define inline
106// CRT_SECURE_NO_DEPRECATE silences warnings about sprintf() and strerror() 106typedef unsigned int uint;
107#define _CRT_SECURE_NO_DEPRECATE 1 107typedef unsigned int usize_t;
108#define _CRT_SECURE_COPP_OVERLOAD_STANDARD_NAMES 1 108typedef unsigned char uint8_t;
109#define WIN32_LEAN_AND_MEAN 109typedef unsigned short uint16_t;
110#include <windows.h> 110typedef unsigned long uint32_t;
111#define inline 111typedef ULONGLONG uint64_t;
112typedef unsigned int uint; 112#endif
113typedef unsigned int usize_t; 113
114typedef unsigned char uint8_t; 114#define SIZEOF_USIZE_T 4
115typedef unsigned short uint16_t; 115
116typedef unsigned long uint32_t; 116#ifndef XD3_USE_LARGEFILE64
117typedef ULONGLONG uint64_t; 117#define XD3_USE_LARGEFILE64 1
118#endif 118#endif
119 119
120#define SIZEOF_USIZE_T 4 120#if XD3_USE_LARGEFILE64
121 121#define __USE_FILE_OFFSET64 1 /* GLIBC: for 64bit fileops, ... ? */
122#ifndef XD3_USE_LARGEFILE64 122typedef uint64_t xoff_t;
123#define XD3_USE_LARGEFILE64 1 123#define SIZEOF_XOFF_T 8
124#endif 124#else
125 125typedef uint32_t xoff_t;
126#if XD3_USE_LARGEFILE64 126#define SIZEOF_XOFF_T 4
127#define __USE_FILE_OFFSET64 1 /* GLIBC: for 64bit fileops, ... ? */ 127#endif
128typedef uint64_t xoff_t; 128
129#define SIZEOF_XOFF_T 8 129#define USE_UINT32 (SIZEOF_USIZE_T == 4 || SIZEOF_XOFF_T == 4 || REGRESSION_TEST)
130#else 130#define USE_UINT64 (SIZEOF_USIZE_T == 8 || SIZEOF_XOFF_T == 8 || REGRESSION_TEST)
131typedef uint32_t xoff_t; 131
132#define SIZEOF_XOFF_T 4 132/**********************************************************************/
133#endif 133
134 134#ifndef INLINE
135#define USE_UINT32 (SIZEOF_USIZE_T == 4 || SIZEOF_XOFF_T == 4 || REGRESSION_TEST) 135#define INLINE inline
136#define USE_UINT64 (SIZEOF_USIZE_T == 8 || SIZEOF_XOFF_T == 8 || REGRESSION_TEST) 136#endif
137 137
138/**********************************************************************/ 138/* Whether to build the encoder, otherwise only build the decoder. */
139 139#ifndef XD3_ENCODER
140#ifndef INLINE 140#define XD3_ENCODER 1
141#define INLINE inline 141#endif
142#endif 142
143 143/* The code returned when main() fails, also defined in system includes. */
144/* Whether to build the encoder, otherwise only build the decoder. */ 144#ifndef EXIT_FAILURE
145#ifndef XD3_ENCODER 145#define EXIT_FAILURE 1
146#define XD3_ENCODER 1 146#endif
147#endif 147
148 148/* REGRESSION TEST enables the "xdelta3 test" command, which runs a series of self-tests. */
149/* The code returned when main() fails, also defined in system includes. */ 149#ifndef REGRESSION_TEST
150#ifndef EXIT_FAILURE 150#define REGRESSION_TEST 0
151#define EXIT_FAILURE 1 151#endif
152#endif 152
153 153/* XD3_DEBUG=1 enables assertions and various statistics. Levels > 1 enable some
154/* REGRESSION TEST enables the "xdelta3 test" command, which runs a series of self-tests. */ 154 * additional output only useful during development and debugging. */
155#ifndef REGRESSION_TEST 155#ifndef XD3_DEBUG
156#define REGRESSION_TEST 0 156#define XD3_DEBUG 0
157#endif 157#endif
158 158
159/* XD3_DEBUG=1 enables assertions and various statistics. Levels > 1 enable some 159#ifndef PYTHON_MODULE
160 * additional output only useful during development and debugging. */ 160#define PYTHON_MODULE 0
161#ifndef XD3_DEBUG 161#endif
162#define XD3_DEBUG 0 162
163#endif 163/* There are three string matching functions supplied: one fast, one slow (default), and
164 164 * one soft-configurable. To disable any of these, use the following definitions. */
165#ifndef PYTHON_MODULE 165#ifndef XD3_BUILD_SLOW
166#define PYTHON_MODULE 0 166#define XD3_BUILD_SLOW 1
167#endif 167#endif
168 168#ifndef XD3_BUILD_FAST
169/* There are three string matching functions supplied: one fast, one slow (default), and 169#define XD3_BUILD_FAST 1
170 * one soft-configurable. To disable any of these, use the following definitions. */ 170#endif
171#ifndef XD3_BUILD_SLOW 171#ifndef XD3_BUILD_SOFT
172#define XD3_BUILD_SLOW 1 172#define XD3_BUILD_SOFT 1
173#endif 173#endif
174#ifndef XD3_BUILD_FAST 174
175#define XD3_BUILD_FAST 1 175#if XD3_DEBUG
176#endif 176#include <stdio.h>
177#ifndef XD3_BUILD_SOFT 177#endif
178#define XD3_BUILD_SOFT 1 178
179#endif 179/* XPRINT. Debug output and VCDIFF_TOOLS functions report to stderr. I have used an
180 180 * irregular style to abbreviate [fprintf(stderr, "] as [P(RINT "]. */
181#if XD3_DEBUG 181#define P fprintf
182#include <stdio.h> 182#define RINT stderr,
183#endif 183
184 184typedef struct _xd3_stream xd3_stream;
185/* XPRINT. Debug output and VCDIFF_TOOLS functions report to stderr. I have used an 185typedef struct _xd3_source xd3_source;
186 * irregular style to abbreviate [fprintf(stderr, "] as [P(RINT "]. */ 186typedef struct _xd3_hash_cfg xd3_hash_cfg;
187#define P fprintf 187typedef struct _xd3_smatcher xd3_smatcher;
188#define RINT stderr, 188typedef struct _xd3_rinst xd3_rinst;
189 189typedef struct _xd3_dinst xd3_dinst;
190typedef struct _xd3_stream xd3_stream; 190typedef struct _xd3_hinst xd3_hinst;
191typedef struct _xd3_source xd3_source; 191typedef struct _xd3_rpage xd3_rpage;
192typedef struct _xd3_hash_cfg xd3_hash_cfg; 192typedef struct _xd3_addr_cache xd3_addr_cache;
193typedef struct _xd3_smatcher xd3_smatcher; 193typedef struct _xd3_output xd3_output;
194typedef struct _xd3_rinst xd3_rinst; 194typedef struct _xd3_desect xd3_desect;
195typedef struct _xd3_dinst xd3_dinst; 195typedef struct _xd3_iopt_buf xd3_iopt_buf;
196typedef struct _xd3_hinst xd3_hinst; 196typedef struct _xd3_rlist xd3_rlist;
197typedef struct _xd3_rpage xd3_rpage; 197typedef struct _xd3_sec_type xd3_sec_type;
198typedef struct _xd3_addr_cache xd3_addr_cache; 198typedef struct _xd3_sec_cfg xd3_sec_cfg;
199typedef struct _xd3_output xd3_output; 199typedef struct _xd3_sec_stream xd3_sec_stream;
200typedef struct _xd3_desect xd3_desect; 200typedef struct _xd3_config xd3_config;
201typedef struct _xd3_iopt_buf xd3_iopt_buf; 201typedef struct _xd3_code_table_desc xd3_code_table_desc;
202typedef struct _xd3_rlist xd3_rlist; 202typedef struct _xd3_code_table_sizes xd3_code_table_sizes;
203typedef struct _xd3_sec_type xd3_sec_type; 203typedef struct _xd3_slist xd3_slist;
204typedef struct _xd3_sec_cfg xd3_sec_cfg; 204
205typedef struct _xd3_sec_stream xd3_sec_stream; 205/* The stream configuration has three callbacks functions, all of which may be supplied
206typedef struct _xd3_config xd3_config; 206 * with NULL values. If config->getblk is provided as NULL, the stream returns
207typedef struct _xd3_code_table_desc xd3_code_table_desc; 207 * XD3_GETSRCBLK. */
208typedef struct _xd3_code_table_sizes xd3_code_table_sizes; 208
209typedef struct _xd3_slist xd3_slist; 209typedef void* (xd3_alloc_func) (void *opaque,
210 210 usize_t items,
211/* The stream configuration has three callbacks functions, all of which may be supplied 211 usize_t size);
212 * with NULL values. If config->getblk is provided as NULL, the stream returns 212typedef void (xd3_free_func) (void *opaque,
213 * XD3_GETSRCBLK. */ 213 void *address);
214 214
215typedef void* (xd3_alloc_func) (void *opaque, 215typedef int (xd3_getblk_func) (xd3_stream *stream,
216 usize_t items, 216 xd3_source *source,
217 usize_t size); 217 xoff_t blkno);
218typedef void (xd3_free_func) (void *opaque, 218
219 void *address); 219/* These are internal functions to delay construction of encoding tables and support
220 220 * alternate code tables. See the comments & code enabled by GENERIC_ENCODE_TABLES. */
221typedef int (xd3_getblk_func) (xd3_stream *stream, 221
222 xd3_source *source, 222typedef const xd3_dinst* (xd3_code_table_func) (void);
223 xoff_t blkno); 223typedef int (xd3_comp_table_func) (xd3_stream *stream,
224 224 const uint8_t **data,
225/* These are internal functions to delay construction of encoding tables and support 225 usize_t *size);
226 * alternate code tables. See the comments & code enabled by GENERIC_ENCODE_TABLES. */ 226
227 227
228typedef const xd3_dinst* (xd3_code_table_func) (void); 228/* Some junk. */
229typedef int (xd3_comp_table_func) (xd3_stream *stream, 229
230 const uint8_t **data, 230#ifndef XD3_ASSERT
231 usize_t *size); 231#if XD3_DEBUG
232 232#define XD3_ASSERT(x) \
233 233 do { if (! (x)) { P(RINT "%s:%d: XD3 assertion failed: %s\n", __FILE__, __LINE__, #x); \
234/* Some junk. */ 234 abort (); } } while (0)
235 235#else
236#ifndef XD3_ASSERT 236#define XD3_ASSERT(x) (void)0
237#if XD3_DEBUG 237#endif
238#define XD3_ASSERT(x) \ 238#endif
239 do { if (! (x)) { P(RINT "%s:%d: XD3 assertion failed: %s\n", __FILE__, __LINE__, #x); \ 239
240 abort (); } } while (0) 240#ifdef __GNUC__
241#else 241/* As seen on linux-kernel. */
242#define XD3_ASSERT(x) (void)0 242#ifndef max
243#endif 243#define max(x,y) ({ \
244#endif 244 const typeof(x) _x = (x); \
245 245 const typeof(y) _y = (y); \
246#ifdef __GNUC__ 246 (void) (&_x == &_y); \
247/* As seen on linux-kernel. */ 247 _x > _y ? _x : _y; })
248#ifndef max 248#endif
249#define max(x,y) ({ \ 249
250 const typeof(x) _x = (x); \ 250#ifndef min
251 const typeof(y) _y = (y); \ 251#define min(x,y) ({ \
252 (void) (&_x == &_y); \ 252 const typeof(x) _x = (x); \
253 _x > _y ? _x : _y; }) 253 const typeof(y) _y = (y); \
254#endif 254 (void) (&_x == &_y); \
255 255 _x < _y ? _x : _y; })
256#ifndef min 256#endif
257#define min(x,y) ({ \ 257#else
258 const typeof(x) _x = (x); \ 258#ifndef max
259 const typeof(y) _y = (y); \ 259#define max(x,y) ((x) < (y) ? (y) : (x))
260 (void) (&_x == &_y); \ 260#endif
261 _x < _y ? _x : _y; }) 261#ifndef min
262#endif 262#define min(x,y) ((x) < (y) ? (x) : (y))
263#else 263#endif
264#ifndef max 264#endif
265#define max(x,y) ((x) < (y) ? (y) : (x)) 265
266#endif 266/******************************************************************************************
267#ifndef min 267 PUBLIC ENUMS
268#define min(x,y) ((x) < (y) ? (x) : (y)) 268 ******************************************************************************************/
269#endif 269
270#endif 270/* These are the five ordinary status codes returned by the xd3_encode_input() and
271 271 * xd3_decode_input() state machines. */
272/****************************************************************************************** 272typedef enum {
273 PUBLIC ENUMS 273
274 ******************************************************************************************/ 274 /* An application must be prepared to handle these five return values from either
275 275 * xd3_encode_input or xd3_decode_input, except in the case of no-source compression, in
276/* These are the five ordinary status codes returned by the xd3_encode_input() and 276 * which case XD3_GETSRCBLK is never returned. More detailed comments for these are
277 * xd3_decode_input() state machines. */ 277 * given in xd3_encode_input and xd3_decode_input comments, below. */
278typedef enum { 278 XD3_INPUT = -17703, /* need input */
279 279 XD3_OUTPUT = -17704, /* have output */
280 /* An application must be prepared to handle these five return values from either 280 XD3_GETSRCBLK = -17705, /* need a block of source input (with no xd3_getblk function),
281 * xd3_encode_input or xd3_decode_input, except in the case of no-source compression, in 281 * a chance to do non-blocking read. */
282 * which case XD3_GETSRCBLK is never returned. More detailed comments for these are 282 XD3_GOTHEADER = -17706, /* (decode-only) after the initial VCDIFF & first window header */
283 * given in xd3_encode_input and xd3_decode_input comments, below. */ 283 XD3_WINSTART = -17707, /* notification: returned before a window is processed, giving a
284 XD3_INPUT = -17703, /* need input */ 284 * chance to XD3_SKIP_WINDOW or not XD3_SKIP_EMIT that window. */
285 XD3_OUTPUT = -17704, /* have output */ 285 XD3_WINFINISH = -17708, /* notification: returned after encode/decode & output for a window */
286 XD3_GETSRCBLK = -17705, /* need a block of source input (with no xd3_getblk function), 286 XD3_TOOFARBACK = -17709, /* (encoder only) may be returned by getblk() if the block is too old */
287 * a chance to do non-blocking read. */ 287 XD3_INTERNAL = -17710, /* internal error */
288 XD3_GOTHEADER = -17706, /* (decode-only) after the initial VCDIFF & first window header */ 288
289 XD3_WINSTART = -17707, /* notification: returned before a window is processed, giving a 289} xd3_rvalues;
290 * chance to XD3_SKIP_WINDOW or not XD3_SKIP_EMIT that window. */ 290
291 XD3_WINFINISH = -17708, /* notification: returned after encode/decode & output for a window */ 291/* special values in config->flags */
292 XD3_TOOFARBACK = -17709, /* (encoder only) may be returned by getblk() if the block is too old */ 292typedef enum
293 XD3_INTERNAL = -17710, /* internal error */ 293{
294 294 XD3_JUST_HDR = (1 << 1), /* used by VCDIFF tools, see xdelta3-main.h. */
295} xd3_rvalues; 295 XD3_SKIP_WINDOW = (1 << 2), /* used by VCDIFF tools, see xdelta3-main.h. */
296 296 XD3_SKIP_EMIT = (1 << 3), /* used by VCDIFF tools, see xdelta3-main.h. */
297/* special values in config->flags */ 297 XD3_FLUSH = (1 << 4), /* flush the stream buffer to prepare for xd3_stream_close(). */
298typedef enum 298
299{ 299 XD3_SEC_DJW = (1 << 5), /* use DJW static huffman */
300 XD3_JUST_HDR = (1 << 1), /* used by VCDIFF tools, see xdelta3-main.h. */ 300 XD3_SEC_FGK = (1 << 6), /* use FGK adaptive huffman */
301 XD3_SKIP_WINDOW = (1 << 2), /* used by VCDIFF tools, see xdelta3-main.h. */ 301 XD3_SEC_TYPE = (XD3_SEC_DJW | XD3_SEC_FGK),
302 XD3_SKIP_EMIT = (1 << 3), /* used by VCDIFF tools, see xdelta3-main.h. */ 302
303 XD3_FLUSH = (1 << 4), /* flush the stream buffer to prepare for xd3_stream_close(). */ 303 XD3_SEC_NODATA = (1 << 7), /* disable secondary compression of the data section. */
304 304 XD3_SEC_NOINST = (1 << 8), /* disable secondary compression of the inst section. */
305 XD3_SEC_DJW = (1 << 5), /* use DJW static huffman */ 305 XD3_SEC_NOADDR = (1 << 9), /* disable secondary compression of the addr section. */
306 XD3_SEC_FGK = (1 << 6), /* use FGK adaptive huffman */ 306
307 XD3_SEC_TYPE = (XD3_SEC_DJW | XD3_SEC_FGK), 307 XD3_SEC_OTHER = (XD3_SEC_NODATA | XD3_SEC_NOINST | XD3_SEC_NOADDR),
308 308
309 XD3_SEC_NODATA = (1 << 7), /* disable secondary compression of the data section. */ 309 XD3_ADLER32 = (1 << 10), /* enable checksum computation in the encoder. */
310 XD3_SEC_NOINST = (1 << 8), /* disable secondary compression of the inst section. */ 310 XD3_ADLER32_NOVER = (1 << 11), /* disable checksum verification in the decoder. */
311 XD3_SEC_NOADDR = (1 << 9), /* disable secondary compression of the addr section. */ 311
312 312 XD3_ALT_CODE_TABLE = (1 << 12), /* for testing the alternate code table encoding. */
313 XD3_SEC_OTHER = (XD3_SEC_NODATA | XD3_SEC_NOINST | XD3_SEC_NOADDR), 313
314 314 XD3_NOCOMPRESS = (1 << 13), /* disable ordinary data compression feature,
315 XD3_ADLER32 = (1 << 10), /* enable checksum computation in the encoder. */ 315 * only search the source, not the target. */
316 XD3_ADLER32_NOVER = (1 << 11), /* disable checksum verification in the decoder. */ 316 XD3_BEGREEDY = (1 << 14), /* disable the "1.5-pass algorithm", instead use
317 317 * greedy matching. Greedy is off by default. */
318 XD3_ALT_CODE_TABLE = (1 << 12), /* for testing the alternate code table encoding. */ 318} xd3_flags;
319 319
320 XD3_NOCOMPRESS = (1 << 13), /* disable ordinary data compression feature, 320/* The values of this enumeration are set in xd3_config using the smatch_cfg variable. It
321 * only search the source, not the target. */ 321 * can be set to slow, fast, soft, or default. The fast and slow setting uses preset,
322 XD3_BEGREEDY = (1 << 14), /* disable the "1.5-pass algorithm", instead use 322 * hardcoded parameters and the soft setting is accompanied by user-supplied parameters.
323 * greedy matching. Greedy is off by default. */ 323 * If the user supplies 'default' the code selects one of the available string matchers.
324} xd3_flags; 324 * Due to compile-time settings (see XD3_SLOW_SMATCHER, XD3_FAST_SMATCHER,
325 325 * XD3_SOFT_SMATCHER variables), not all options may be available. */
326/* The values of this enumeration are set in xd3_config using the smatch_cfg variable. It 326typedef enum
327 * can be set to slow, fast, soft, or default. The fast and slow setting uses preset, 327{
328 * hardcoded parameters and the soft setting is accompanied by user-supplied parameters. 328 XD3_SMATCH_DEFAULT = 0,
329 * If the user supplies 'default' the code selects one of the available string matchers. 329 XD3_SMATCH_SLOW = 1,
330 * Due to compile-time settings (see XD3_SLOW_SMATCHER, XD3_FAST_SMATCHER, 330 XD3_SMATCH_FAST = 2,
331 * XD3_SOFT_SMATCHER variables), not all options may be available. */ 331 XD3_SMATCH_SOFT = 3,
332typedef enum 332} xd3_smatch_cfg;
333{ 333
334 XD3_SMATCH_DEFAULT = 0, 334/******************************************************************************************
335 XD3_SMATCH_SLOW = 1, 335 PRIVATE ENUMS
336 XD3_SMATCH_FAST = 2, 336 ******************************************************************************************/
337 XD3_SMATCH_SOFT = 3, 337
338} xd3_smatch_cfg; 338/* stream->match_state is part of the xd3_encode_input state machine for source matching:
339 339 *
340/****************************************************************************************** 340 * 1. the XD3_GETSRCBLK block-read mechanism means reentrant matching
341 PRIVATE ENUMS 341 * 2. this state spans encoder windows: a match and end-of-window will continue in the next
342 ******************************************************************************************/ 342 * 3. the initial target byte and source byte are a presumed match, to avoid some computation
343 343 * in case the inputs are identical.
344/* stream->match_state is part of the xd3_encode_input state machine for source matching: 344 */
345 * 345typedef enum {
346 * 1. the XD3_GETSRCBLK block-read mechanism means reentrant matching 346
347 * 2. this state spans encoder windows: a match and end-of-window will continue in the next 347 MATCH_TARGET = 0, /* in this state, attempt to match the start of the target with the
348 * 3. the initial target byte and source byte are a presumed match, to avoid some computation 348 * previously set source address (initially 0). */
349 * in case the inputs are identical. 349 MATCH_BACKWARD = 1, /* currently expanding a match backward in the source/target. */
350 */ 350 MATCH_FORWARD = 2, /* currently expanding a match forward in the source/target. */
351typedef enum { 351 MATCH_SEARCHING = 3, /* currently searching for a match. */
352 352
353 MATCH_TARGET = 0, /* in this state, attempt to match the start of the target with the 353} xd3_match_state;
354 * previously set source address (initially 0). */ 354
355 MATCH_BACKWARD = 1, /* currently expanding a match backward in the source/target. */ 355/* The xd3_encode_input state machine steps through these states in the following order.
356 MATCH_FORWARD = 2, /* currently expanding a match forward in the source/target. */ 356 * The matcher is reentrant and returns XD3_INPUT whenever it requires more data. After
357 MATCH_SEARCHING = 3, /* currently searching for a match. */ 357 * receiving XD3_INPUT, if the application reads EOF it should call xd3_stream_close().
358 358 */
359} xd3_match_state; 359typedef enum {
360 360
361/* The xd3_encode_input state machine steps through these states in the following order. 361 ENC_INIT = 0, /* xd3_encode_input has never been called. */
362 * The matcher is reentrant and returns XD3_INPUT whenever it requires more data. After 362 ENC_INPUT = 1, /* waiting for xd3_avail_input () to be called. */
363 * receiving XD3_INPUT, if the application reads EOF it should call xd3_stream_close(). 363 ENC_SEARCH = 2, /* currently searching for matches. */
364 */ 364 ENC_FLUSH = 3, /* currently emitting output. */
365typedef enum { 365 ENC_POSTOUT = 4, /* after an output section. */
366 366 ENC_POSTWIN = 5, /* after all output sections. */
367 ENC_INIT = 0, /* xd3_encode_input has never been called. */ 367 ENC_ABORTED = 6, /* abort. */
368 ENC_INPUT = 1, /* waiting for xd3_avail_input () to be called. */ 368} xd3_encode_state;
369 ENC_SEARCH = 2, /* currently searching for matches. */ 369
370 ENC_FLUSH = 3, /* currently emitting output. */ 370/* The xd3_decode_input state machine steps through these states in the following order.
371 ENC_POSTOUT = 4, /* after an output section. */ 371 * The matcher is reentrant and returns XD3_INPUT whenever it requires more data. After
372 ENC_POSTWIN = 5, /* after all output sections. */ 372 * receiving XD3_INPUT, if the application reads EOF it should call xd3_stream_close().
373 ENC_ABORTED = 6, /* abort. */ 373 *
374} xd3_encode_state; 374 * 0-8: the VCDIFF header
375 375 * 9-18: the VCDIFF window header
376/* The xd3_decode_input state machine steps through these states in the following order. 376 * 19-21: the three primary sections: data (which I think should have gone last), inst, addr
377 * The matcher is reentrant and returns XD3_INPUT whenever it requires more data. After 377 * 22: producing output: returns XD3_OUTPUT, possibly XD3_GETSRCBLK,
378 * receiving XD3_INPUT, if the application reads EOF it should call xd3_stream_close(). 378 * 23: return XD3_WINFINISH, set state=9 to decode more input
379 * 379 */
380 * 0-8: the VCDIFF header 380typedef enum {
381 * 9-18: the VCDIFF window header 381
382 * 19-21: the three primary sections: data (which I think should have gone last), inst, addr 382 DEC_VCHEAD = 0, /* VCDIFF header */
383 * 22: producing output: returns XD3_OUTPUT, possibly XD3_GETSRCBLK, 383 DEC_HDRIND = 1, /* header indicator */
384 * 23: return XD3_WINFINISH, set state=9 to decode more input 384
385 */ 385 DEC_SECONDID = 2, /* secondary compressor ID */
386typedef enum { 386
387 387 DEC_TABLEN = 3, /* code table length */
388 DEC_VCHEAD = 0, /* VCDIFF header */ 388 DEC_NEAR = 4, /* code table near */
389 DEC_HDRIND = 1, /* header indicator */ 389 DEC_SAME = 5, /* code table same */
390 390 DEC_TABDAT = 6, /* code table data */
391 DEC_SECONDID = 2, /* secondary compressor ID */ 391
392 392 DEC_APPLEN = 7, /* application data length */
393 DEC_TABLEN = 3, /* code table length */ 393 DEC_APPDAT = 8, /* application data */
394 DEC_NEAR = 4, /* code table near */ 394
395 DEC_SAME = 5, /* code table same */ 395 DEC_WININD = 9, /* window indicator */
396 DEC_TABDAT = 6, /* code table data */ 396
397 397 DEC_CPYLEN = 10, /* copy window length */
398 DEC_APPLEN = 7, /* application data length */ 398 DEC_CPYOFF = 11, /* copy window offset */
399 DEC_APPDAT = 8, /* application data */ 399
400 400 DEC_ENCLEN = 12, /* length of delta encoding */
401 DEC_WININD = 9, /* window indicator */ 401 DEC_TGTLEN = 13, /* length of target window */
402 402 DEC_DELIND = 14, /* delta indicator */
403 DEC_CPYLEN = 10, /* copy window length */ 403
404 DEC_CPYOFF = 11, /* copy window offset */ 404 DEC_DATALEN = 15, /* length of ADD+RUN data */
405 405 DEC_INSTLEN = 16, /* length of instruction data */
406 DEC_ENCLEN = 12, /* length of delta encoding */ 406 DEC_ADDRLEN = 17, /* length of address data */
407 DEC_TGTLEN = 13, /* length of target window */ 407
408 DEC_DELIND = 14, /* delta indicator */ 408 DEC_CKSUM = 18, /* window checksum */
409 409
410 DEC_DATALEN = 15, /* length of ADD+RUN data */ 410 DEC_DATA = 19, /* data section */
411 DEC_INSTLEN = 16, /* length of instruction data */ 411 DEC_INST = 20, /* instruction section */
412 DEC_ADDRLEN = 17, /* length of address data */ 412 DEC_ADDR = 21, /* address section */
413 413
414 DEC_CKSUM = 18, /* window checksum */ 414 DEC_EMIT = 22, /* producing data */
415 415
416 DEC_DATA = 19, /* data section */ 416 DEC_FINISH = 23, /* window finished */
417 DEC_INST = 20, /* instruction section */ 417
418 DEC_ADDR = 21, /* address section */ 418 DEC_ABORTED = 24, /* xd3_abort_stream */
419 419} xd3_decode_state;
420 DEC_EMIT = 22, /* producing data */ 420
421 421/* An application never sees these internal codes: */
422 DEC_FINISH = 23, /* window finished */ 422typedef enum {
423 423 XD3_NOSECOND = -17708, /* when secondary compression finds no improvement. */
424 DEC_ABORTED = 24, /* xd3_abort_stream */ 424} xd3_pvalues;
425} xd3_decode_state; 425
426 426/******************************************************************************************
427/* An application never sees these internal codes: */ 427 internal types
428typedef enum { 428 ******************************************************************************************/
429 XD3_NOSECOND = -17708, /* when secondary compression finds no improvement. */ 429
430} xd3_pvalues; 430/* instruction lists used in the IOPT buffer */
431 431struct _xd3_rlist
432/****************************************************************************************** 432{
433 internal types 433 xd3_rlist *next;
434 ******************************************************************************************/ 434 xd3_rlist *prev;
435 435};
436/* instruction lists used in the IOPT buffer */ 436
437struct _xd3_rlist 437/* the raw encoding of an instruction used in the IOPT buffer */
438{ 438struct _xd3_rinst
439 xd3_rlist *next; 439{
440 xd3_rlist *prev; 440 uint8_t type;
441}; 441 uint8_t xtra;
442 442 uint8_t code1;
443/* the raw encoding of an instruction used in the IOPT buffer */ 443 uint8_t code2;
444struct _xd3_rinst 444 usize_t pos;
445{ 445 usize_t size;
446 uint8_t type; 446 xoff_t addr;
447 uint8_t xtra; 447 xd3_rlist link;
448 uint8_t code1; 448};
449 uint8_t code2; 449
450 usize_t pos; 450/* the code-table form of an single- or double-instruction */
451 usize_t size; 451struct _xd3_dinst
452 xoff_t addr; 452{
453 xd3_rlist link; 453 uint8_t type1;
454}; 454 uint8_t size1;
455 455 uint8_t type2;
456/* the code-table form of an single- or double-instruction */ 456 uint8_t size2;
457struct _xd3_dinst 457};
458{ 458
459 uint8_t type1; 459/* the decoded form of a single (half) instruction. */
460 uint8_t size1; 460struct _xd3_hinst
461 uint8_t type2; 461{
462 uint8_t size2; 462 uint8_t type;
463}; 463 usize_t size;
464 464 usize_t addr;
465/* the decoded form of a single (half) instruction. */ 465};
466struct _xd3_hinst 466
467{ 467/* used by the encoder to buffer output in sections. list of blocks. */
468 uint8_t type; 468struct _xd3_output
469 usize_t size; 469{
470 usize_t addr; 470 uint8_t *base;
471}; 471 usize_t next;
472 472 usize_t avail;
473/* used by the encoder to buffer output in sections. list of blocks. */ 473 xd3_output *next_page;
474struct _xd3_output 474};
475{ 475
476 uint8_t *base; 476/* the VCDIFF address cache, see the RFC */
477 usize_t next; 477struct _xd3_addr_cache
478 usize_t avail; 478{
479 xd3_output *next_page; 479 uint s_near;
480}; 480 uint s_same;
481 481 usize_t next_slot; /* the circular index for near */
482/* the VCDIFF address cache, see the RFC */ 482 usize_t *near_array; /* array of size s_near */
483struct _xd3_addr_cache 483 usize_t *same_array; /* array of size s_same*256 */
484{ 484};
485 uint s_near; 485
486 uint s_same; 486/* the IOPT buffer has a used list of (ordered) instructions, possibly overlapping in
487 usize_t next_slot; /* the circular index for near */ 487 * target addresses, awaiting a flush */
488 usize_t *near_array; /* array of size s_near */ 488struct _xd3_iopt_buf
489 usize_t *same_array; /* array of size s_same*256 */ 489{
490}; 490 xd3_rlist used;
491 491 xd3_rlist free;
492/* the IOPT buffer has a used list of (ordered) instructions, possibly overlapping in 492 xd3_rinst *buffer;
493 * target addresses, awaiting a flush */ 493};
494struct _xd3_iopt_buf 494
495{ 495/* This is the record of a pre-compiled configuration, a subset of xd3_config. */
496 xd3_rlist used; 496struct _xd3_smatcher
497 xd3_rlist free; 497{
498 xd3_rinst *buffer; 498 const char *name;
499}; 499 int (*string_match) (xd3_stream *stream);
500 500 uint large_look;
501/* This is the record of a pre-compiled configuration, a subset of xd3_config. */ 501 uint large_step;
502struct _xd3_smatcher 502 uint small_look;
503{ 503 uint small_chain;
504 const char *name; 504 uint small_lchain;
505 int (*string_match) (xd3_stream *stream); 505 uint ssmatch;
506 uint large_look; 506 uint try_lazy;
507 uint large_step; 507 uint max_lazy;
508 uint small_look; 508 uint long_enough;
509 uint small_chain; 509 uint promote;
510 uint small_lchain; 510};
511 uint ssmatch; 511
512 uint try_lazy; 512/* hash table size & power-of-two hash function. */
513 uint max_lazy; 513struct _xd3_hash_cfg
514 uint long_enough; 514{
515 uint promote; 515 usize_t size;
516}; 516 usize_t shift;
517 517 usize_t mask;
518/* hash table size & power-of-two hash function. */ 518};
519struct _xd3_hash_cfg 519
520{ 520/* a hash-chain link in the small match table, embedded with position and checksum */
521 usize_t size; 521struct _xd3_slist
522 usize_t shift; 522{
523 usize_t mask; 523 xd3_slist *next;
524}; 524 xd3_slist *prev;
525 525 usize_t pos;
526/* a hash-chain link in the small match table, embedded with position and checksum */ 526 usize_t scksum;
527struct _xd3_slist 527};
528{ 528
529 xd3_slist *next; 529/* a decoder section (data, inst, or addr). there is an optimization to avoid copying
530 xd3_slist *prev; 530 * these sections if all the input is available, related to the copied field below.
531 usize_t pos; 531 * secondation compression uses the copied2 field. */
532 usize_t scksum; 532struct _xd3_desect
533}; 533{
534 534 const uint8_t *buf;
535/* a decoder section (data, inst, or addr). there is an optimization to avoid copying 535 const uint8_t *buf_max;
536 * these sections if all the input is available, related to the copied field below. 536 usize_t size;
537 * secondation compression uses the copied2 field. */ 537 usize_t pos;
538struct _xd3_desect 538 uint8_t *copied1;
539{ 539 usize_t alloc1;
540 const uint8_t *buf; 540 uint8_t *copied2;
541 const uint8_t *buf_max; 541 usize_t alloc2;
542 usize_t size; 542};
543 usize_t pos; 543
544 uint8_t *copied1; 544/******************************************************************************************
545 usize_t alloc1; 545 public types
546 uint8_t *copied2; 546 ******************************************************************************************/
547 usize_t alloc2; 547
548}; 548/* Settings for the secondary compressor. */
549 549struct _xd3_sec_cfg
550/****************************************************************************************** 550{
551 public types 551 int data_type; /* Which section. (set automatically) */
552 ******************************************************************************************/ 552 int ngroups; /* Number of DJW Huffman groups. */
553 553 int sector_size; /* Sector size. */
554/* Settings for the secondary compressor. */ 554 int inefficient; /* If true, ignore efficiency check [avoid XD3_NOSECOND]. */
555struct _xd3_sec_cfg 555};
556{ 556
557 int data_type; /* Which section. (set automatically) */ 557/* This is the user-visible stream configuration. */
558 int ngroups; /* Number of DJW Huffman groups. */ 558struct _xd3_config
559 int sector_size; /* Sector size. */ 559{
560 int inefficient; /* If true, ignore efficiency check [avoid XD3_NOSECOND]. */ 560 usize_t winsize; /* The encoder window size. */
561}; 561 usize_t sprevsz; /* How far back small string matching goes */
562 562 usize_t iopt_size; /* entries in the instruction-optimizing buffer */
563/* This is the user-visible stream configuration. */ 563 usize_t srcwin_size; /* Initial size of the source-window lookahead */
564struct _xd3_config 564 usize_t srcwin_maxsz; /* srcwin_size grows by a factor of 2 when no matches are found */
565{ 565
566 usize_t memsize; /* How much memory Xdelta may allocate */ 566 xd3_getblk_func *getblk; /* The three callbacks. */
567 usize_t winsize; /* The encoder window size. */ 567 xd3_alloc_func *alloc;
568 usize_t sprevsz; /* How far back small string matching goes */ 568 xd3_free_func *freef;
569 usize_t iopt_size; /* entries in the instruction-optimizing buffer */ 569 void *opaque; /* Not used. */
570 usize_t srcwin_size; /* Initial size of the source-window lookahead */ 570 int flags; /* stream->flags are initialized from xd3_config &
571 usize_t srcwin_maxsz; /* srcwin_size grows by a factor of 2 when no matches are found */ 571 * never modified by the library. Use xd3_set_flags
572 572 * to modify flags settings mid-stream. */
573 xd3_getblk_func *getblk; /* The three callbacks. */ 573
574 xd3_alloc_func *alloc; 574 xd3_sec_cfg sec_data; /* Secondary compressor config: data */
575 xd3_free_func *freef; 575 xd3_sec_cfg sec_inst; /* Secondary compressor config: inst */
576 void *opaque; /* Not used. */ 576 xd3_sec_cfg sec_addr; /* Secondary compressor config: addr */
577 int flags; /* stream->flags are initialized from xd3_config & 577
578 * never modified by the library. Use xd3_set_flags 578 xd3_smatch_cfg smatch_cfg; /* See enum: use fields below for soft config */
579 * to modify flags settings mid-stream. */ 579 xd3_smatcher smatcher_soft;
580 580};
581 xd3_sec_cfg sec_data; /* Secondary compressor config: data */ 581
582 xd3_sec_cfg sec_inst; /* Secondary compressor config: inst */ 582/* The primary source file object. You create one of these objects and initialize the
583 xd3_sec_cfg sec_addr; /* Secondary compressor config: addr */ 583 * first four fields. This library maintains the next 5 fields. The configured getblk
584 584 * implementation is responsible for setting the final 3 fields when called (and/or when
585 xd3_smatch_cfg smatch_cfg; /* See enum: use fields below for soft config */ 585 * XD3_GETSRCBLK is returned).
586 xd3_smatcher smatcher_soft; 586 */
587}; 587struct _xd3_source
588 588{
589/* The primary source file object. You create one of these objects and initialize the 589 /* you set */
590 * first four fields. This library maintains the next 5 fields. The configured getblk 590 xoff_t size; /* size of this source */
591 * implementation is responsible for setting the final 3 fields when called (and/or when 591 usize_t blksize; /* block size */
592 * XD3_GETSRCBLK is returned). 592 const char *name; /* its name, for debug/print purposes */
593 */ 593 void *ioh; /* opaque handle */
594struct _xd3_source 594
595{ 595 /* xd3 sets */
596 /* you set */ 596 usize_t srclen; /* length of this source window */
597 xoff_t size; /* size of this source */ 597 xoff_t srcbase; /* offset of this source window in the source itself */
598 usize_t blksize; /* block size */ 598 xoff_t blocks; /* the total number of blocks in this source */
599 const char *name; /* its name, for debug/print purposes */ 599 usize_t cpyoff_blocks; /* offset of copy window in blocks */
600 void *ioh; /* opaque handle */ 600 usize_t cpyoff_blkoff; /* offset of copy window in blocks, remainder */
601 601 xoff_t getblkno; /* request block number: xd3 sets current getblk request */
602 /* xd3 sets */ 602
603 usize_t srclen; /* length of this source window */ 603 /* getblk sets */
604 xoff_t srcbase; /* offset of this source window in the source itself */ 604 xoff_t curblkno; /* current block number: client sets after getblk request */
605 xoff_t blocks; /* the total number of blocks in this source */ 605 usize_t onblk; /* number of bytes on current block: client sets, xd3 verifies */
606 usize_t cpyoff_blocks; /* offset of copy window in blocks */ 606 const uint8_t *curblk; /* current block array: client sets after getblk request */
607 usize_t cpyoff_blkoff; /* offset of copy window in blocks, remainder */ 607};
608 xoff_t getblkno; /* request block number: xd3 sets current getblk request */ 608
609 609/* The primary xd3_stream object, used for encoding and decoding. You may access only two
610 /* getblk sets */ 610 * fields: avail_out, next_out. Use the methods above to operate on xd3_stream. */
611 xoff_t curblkno; /* current block number: client sets after getblk request */ 611struct _xd3_stream
612 usize_t onblk; /* number of bytes on current block: client sets, xd3 verifies */ 612{
613 const uint8_t *curblk; /* current block array: client sets after getblk request */ 613 /* input state */
614}; 614 const uint8_t *next_in; /* next input byte */
615 615 usize_t avail_in; /* number of bytes available at next_in */
616/* The primary xd3_stream object, used for encoding and decoding. You may access only two 616 xoff_t total_in; /* how many bytes in */
617 * fields: avail_out, next_out. Use the methods above to operate on xd3_stream. */ 617
618struct _xd3_stream 618 /* output state */
619{ 619 uint8_t *next_out; /* next output byte */
620 /* input state */ 620 usize_t avail_out; /* number of bytes available at next_out */
621 const uint8_t *next_in; /* next input byte */ 621 usize_t space_out; /* total out space */
622 usize_t avail_in; /* number of bytes available at next_in */ 622 xoff_t current_window; /* number of windows encoded/decoded */
623 xoff_t total_in; /* how many bytes in */ 623 xoff_t total_out; /* how many bytes out */
624 624
625 /* output state */ 625 /* to indicate an error, xd3 sets */
626 uint8_t *next_out; /* next output byte */ 626 const char *msg; /* last error message, NULL if no error */
627 usize_t avail_out; /* number of bytes available at next_out */ 627
628 usize_t space_out; /* total out space */ 628 /* source configuration */
629 xoff_t current_window; /* number of windows encoded/decoded */ 629 xd3_source *src; /* source array */
630 xoff_t total_out; /* how many bytes out */ 630
631 631 /* encoder memory configuration */
632 /* to indicate an error, xd3 sets */ 632 usize_t winsize; /* suggested window size */
633 const char *msg; /* last error message, NULL if no error */ 633 usize_t sprevsz; /* small string, previous window size (power of 2) */
634 634 usize_t sprevmask; /* small string, previous window size mask */
635 /* source configuration */ 635 uint iopt_size;
636 xd3_source *src; /* source array */ 636 uint srcwin_size;
637 637 uint srcwin_maxsz;
638 /* encoder memory configuration */ 638
639 usize_t winsize; /* suggested window size */ 639 /* general configuration */
640 usize_t memsize; /* memory size parameter */ 640 xd3_getblk_func *getblk; /* set nxtblk, nxtblkno to scanblkno */
641 usize_t sprevsz; /* small string, previous window size (power of 2) */ 641 xd3_alloc_func *alloc; /* malloc function */
642 usize_t sprevmask; /* small string, previous window size mask */ 642 xd3_free_func *free; /* free function */
643 uint iopt_size; 643 void* opaque; /* private data object passed to alloc, free, and getblk */
644 uint srcwin_size; 644 int flags; /* various options */
645 uint srcwin_maxsz; 645
646 646 /* secondary compressor configuration */
647 /* general configuration */ 647 xd3_sec_cfg sec_data; /* Secondary compressor config: data */
648 xd3_getblk_func *getblk; /* set nxtblk, nxtblkno to scanblkno */ 648 xd3_sec_cfg sec_inst; /* Secondary compressor config: inst */
649 xd3_alloc_func *alloc; /* malloc function */ 649 xd3_sec_cfg sec_addr; /* Secondary compressor config: addr */
650 xd3_free_func *free; /* free function */ 650
651 void* opaque; /* private data object passed to alloc, free, and getblk */ 651 xd3_smatcher smatcher;
652 int flags; /* various options */ 652
653 653 usize_t *large_table; /* table of large checksums */
654 /* secondary compressor configuration */ 654 xd3_hash_cfg large_hash; /* large hash config */
655 xd3_sec_cfg sec_data; /* Secondary compressor config: data */ 655
656 xd3_sec_cfg sec_inst; /* Secondary compressor config: inst */ 656 usize_t *small_table; /* table of small checksums */
657 xd3_sec_cfg sec_addr; /* Secondary compressor config: addr */ 657 xd3_slist *small_prev; /* table of previous offsets, circular linked list */
658 658 int small_reset; /* true if small table should be reset */
659 xd3_smatcher smatcher; 659
660 660 xd3_hash_cfg small_hash; /* small hash config */
661 usize_t *large_table; /* table of large checksums */ 661 xd3_addr_cache acache; /* the vcdiff address cache */
662 xd3_hash_cfg large_hash; /* large hash config */ 662 xd3_encode_state enc_state; /* state of the encoder */
663 663
664 usize_t *small_table; /* table of small checksums */ 664 usize_t taroff; /* base offset of the target input */
665 xd3_slist *small_prev; /* table of previous offsets, circular linked list */ 665 usize_t input_position; /* current input position */
666 int small_reset; /* true if small table should be reset */ 666 usize_t min_match; /* current minimum match length, avoids redundent matches */
667 667 usize_t unencoded_offset; /* current input, first unencoded offset. this value is <= the first
668 xd3_hash_cfg small_hash; /* small hash config */ 668 * instruction's position in the iopt buffer, if there is at least one
669 xd3_addr_cache acache; /* the vcdiff address cache */ 669 * match in the buffer. */
670 xd3_encode_state enc_state; /* state of the encoder */ 670
671 671 // SRCWIN
672 usize_t taroff; /* base offset of the target input */ 672 // these variables plus srcwin_size, srcwin_maxsz above (set by config)
673 usize_t input_position; /* current input position */ 673 int srcwin_decided; /* boolean: true if the srclen,srcbase have been decided. */
674 usize_t min_match; /* current minimum match length, avoids redundent matches */ 674 xoff_t srcwin_cksum_pos; /* Source checksum position */
675 usize_t unencoded_offset; /* current input, first unencoded offset. this value is <= the first 675
676 * instruction's position in the iopt buffer, if there is at least one 676 // MATCH
677 * match in the buffer. */ 677 xd3_match_state match_state; /* encoder match state */
678 678 xoff_t match_srcpos; /* current match source position relative to srcbase */
679 // SRCWIN 679 xoff_t match_minaddr; /* smallest matching address to set window params
680 // these variables plus srcwin_size, srcwin_maxsz above (set by config) 680 * (reset each window xd3_encode_reset) */
681 int srcwin_decided; /* boolean: true if the srclen,srcbase have been decided. */ 681 xoff_t match_maxaddr; /* largest matching address to set window params
682 xoff_t srcwin_cksum_pos; /* Source checksum position */ 682 * (reset each window xd3_encode_reset) */
683 683 usize_t match_back; /* match extends back so far */
684 // MATCH 684 usize_t match_maxback; /* match extends back maximum */
685 xd3_match_state match_state; /* encoder match state */ 685 usize_t match_fwd; /* match extends forward so far */
686 xoff_t match_srcpos; /* current match source position relative to srcbase */ 686 usize_t match_maxfwd; /* match extends forward maximum */
687 xoff_t match_minaddr; /* smallest matching address to set window params 687
688 * (reset each window xd3_encode_reset) */ 688 xoff_t maxsrcaddr; /* address of the last source match (across windows) */
689 xoff_t match_maxaddr; /* largest matching address to set window params 689
690 * (reset each window xd3_encode_reset) */ 690 uint8_t *buf_in; /* for saving buffered input */
691 usize_t match_back; /* match extends back so far */ 691 usize_t buf_avail; /* amount of saved input */
692 usize_t match_maxback; /* match extends back maximum */ 692 const uint8_t *buf_leftover; /* leftover content of next_in (i.e., user's buffer) */
693 usize_t match_fwd; /* match extends forward so far */ 693 usize_t buf_leftavail; /* amount of leftover content */
694 usize_t match_maxfwd; /* match extends forward maximum */ 694
695 695 xd3_output *enc_current; /* current output buffer */
696 xoff_t maxsrcaddr; /* address of the last source match (across windows) */ 696 xd3_output *enc_free; /* free output buffers */
697 697 xd3_output *enc_heads[4]; /* array of encoded outputs: head of chain */
698 uint8_t *buf_in; /* for saving buffered input */ 698 xd3_output *enc_tails[4]; /* array of encoded outputs: tail of chain */
699 usize_t buf_avail; /* amount of saved input */ 699
700 const uint8_t *buf_leftover; /* leftover content of next_in (i.e., user's buffer) */ 700 xd3_iopt_buf iopt; /* instruction optimizing buffer */
701 usize_t buf_leftavail; /* amount of leftover content */ 701 xd3_rinst *iout; /* next single instruction */
702 702
703 xd3_output *enc_current; /* current output buffer */ 703 const uint8_t *enc_appheader; /* application header to encode */
704 xd3_output *enc_free; /* free output buffers */ 704 usize_t enc_appheadsz; /* application header size */
705 xd3_output *enc_heads[4]; /* array of encoded outputs: head of chain */ 705
706 xd3_output *enc_tails[4]; /* array of encoded outputs: tail of chain */ 706 /* decoder stuff */
707 707 xd3_decode_state dec_state; /* current DEC_XXX value */
708 xd3_iopt_buf iopt; /* instruction optimizing buffer */ 708 uint dec_hdr_ind; /* VCDIFF header indicator */
709 xd3_rinst *iout; /* next single instruction */ 709 uint dec_win_ind; /* VCDIFF window indicator */
710 710 uint dec_del_ind; /* VCDIFF delta indicator */
711 const uint8_t *enc_appheader; /* application header to encode */ 711
712 usize_t enc_appheadsz; /* application header size */ 712 uint8_t dec_magic[4]; /* First four bytes */
713 713 usize_t dec_magicbytes; /* Magic position. */
714 /* decoder stuff */ 714
715 xd3_decode_state dec_state; /* current DEC_XXX value */ 715 uint dec_secondid; /* Optional secondary compressor ID. */
716 uint dec_hdr_ind; /* VCDIFF header indicator */ 716
717 uint dec_win_ind; /* VCDIFF window indicator */ 717 usize_t dec_codetblsz; /* Optional code table: length. */
718 uint dec_del_ind; /* VCDIFF delta indicator */ 718 uint8_t *dec_codetbl; /* Optional code table: storage. */
719 719 usize_t dec_codetblbytes; /* Optional code table: position. */
720 uint8_t dec_magic[4]; /* First four bytes */ 720
721 usize_t dec_magicbytes; /* Magic position. */ 721 usize_t dec_appheadsz; /* Optional application header: size. */
722 722 uint8_t *dec_appheader; /* Optional application header: storage */
723 uint dec_secondid; /* Optional secondary compressor ID. */ 723 usize_t dec_appheadbytes; /* Optional application header: position. */
724 724
725 usize_t dec_codetblsz; /* Optional code table: length. */ 725 usize_t dec_cksumbytes; /* Optional checksum: position. */
726 uint8_t *dec_codetbl; /* Optional code table: storage. */ 726 uint8_t dec_cksum[4]; /* Optional checksum: storage. */
727 usize_t dec_codetblbytes; /* Optional code table: position. */ 727 uint32_t dec_adler32; /* Optional checksum: value. */
728 728
729 usize_t dec_appheadsz; /* Optional application header: size. */ 729 usize_t dec_cpylen; /* length of copy window (VCD_SOURCE or VCD_TARGET) */
730 uint8_t *dec_appheader; /* Optional application header: storage */ 730 xoff_t dec_cpyoff; /* offset of copy window (VCD_SOURCE or VCD_TARGET) */
731 usize_t dec_appheadbytes; /* Optional application header: position. */ 731 usize_t dec_enclen; /* length of delta encoding */
732 732 usize_t dec_tgtlen; /* length of target window */
733 usize_t dec_cksumbytes; /* Optional checksum: position. */ 733
734 uint8_t dec_cksum[4]; /* Optional checksum: storage. */ 734#if USE_UINT64
735 uint32_t dec_adler32; /* Optional checksum: value. */ 735 uint64_t dec_64part; /* part of a decoded uint64_t */
736 736#endif
737 usize_t dec_cpylen; /* length of copy window (VCD_SOURCE or VCD_TARGET) */ 737#if USE_UINT32
738 xoff_t dec_cpyoff; /* offset of copy window (VCD_SOURCE or VCD_TARGET) */ 738 uint32_t dec_32part; /* part of a decoded uint32_t */
739 usize_t dec_enclen; /* length of delta encoding */ 739#endif
740 usize_t dec_tgtlen; /* length of target window */ 740
741 741 xoff_t dec_winstart; /* offset of the start of current target window */
742#if USE_UINT64 742 xoff_t dec_window_count; /* == current_window + 1 in DEC_FINISH */
743 uint64_t dec_64part; /* part of a decoded uint64_t */ 743 usize_t dec_winbytes; /* bytes of the three sections so far consumed */
744#endif 744 usize_t dec_hdrsize; /* VCDIFF + app header size */
745#if USE_UINT32 745
746 uint32_t dec_32part; /* part of a decoded uint32_t */ 746 const uint8_t *dec_tgtaddrbase; /* Base of decoded target addresses (addr >= dec_cpylen). */
747#endif 747 const uint8_t *dec_cpyaddrbase; /* Base of decoded copy addresses (addr < dec_cpylen). */
748 748
749 xoff_t dec_winstart; /* offset of the start of current target window */ 749 usize_t dec_position; /* current decoder position counting the cpylen offset */
750 xoff_t dec_window_count; /* == current_window + 1 in DEC_FINISH */ 750 usize_t dec_maxpos; /* maximum decoder position counting the cpylen offset */
751 usize_t dec_winbytes; /* bytes of the three sections so far consumed */ 751 xd3_hinst dec_current1; /* current instruction */
752 usize_t dec_hdrsize; /* VCDIFF + app header size */ 752 xd3_hinst dec_current2; /* current instruction */
753 753
754 const uint8_t *dec_tgtaddrbase; /* Base of decoded target addresses (addr >= dec_cpylen). */ 754 uint8_t *dec_buffer; /* Decode buffer */
755 const uint8_t *dec_cpyaddrbase; /* Base of decoded copy addresses (addr < dec_cpylen). */ 755 uint8_t *dec_lastwin; /* In case of VCD_TARGET, the last target window. */
756 756 usize_t dec_lastlen; /* length of the last target window */
757 usize_t dec_position; /* current decoder position counting the cpylen offset */ 757 xoff_t dec_laststart; /* offset of the start of last target window */
758 usize_t dec_maxpos; /* maximum decoder position counting the cpylen offset */ 758 usize_t dec_lastspace; /* allocated space of last target window, for reuse */
759 xd3_hinst dec_current1; /* current instruction */ 759
760 xd3_hinst dec_current2; /* current instruction */ 760 xd3_desect inst_sect; /* staging area for decoding window sections */
761 761 xd3_desect addr_sect;
762 uint8_t *dec_buffer; /* Decode buffer */ 762 xd3_desect data_sect;
763 uint8_t *dec_lastwin; /* In case of VCD_TARGET, the last target window. */ 763
764 usize_t dec_lastlen; /* length of the last target window */ 764 xd3_code_table_func *code_table_func;
765 xoff_t dec_laststart; /* offset of the start of last target window */ 765 xd3_comp_table_func *comp_table_func;
766 usize_t dec_lastspace; /* allocated space of last target window, for reuse */ 766 const xd3_dinst *code_table;
767 767 const xd3_code_table_desc *code_table_desc;
768 xd3_desect inst_sect; /* staging area for decoding window sections */ 768 xd3_dinst *code_table_alloc;
769 xd3_desect addr_sect; 769
770 xd3_desect data_sect; 770 /* secondary compression */
771 771 const xd3_sec_type *sec_type;
772 xd3_code_table_func *code_table_func; 772 xd3_sec_stream *sec_stream_d;
773 xd3_comp_table_func *comp_table_func; 773 xd3_sec_stream *sec_stream_i;
774 const xd3_dinst *code_table; 774 xd3_sec_stream *sec_stream_a;
775 const xd3_code_table_desc *code_table_desc; 775
776 xd3_dinst *code_table_alloc; 776#if XD3_DEBUG
777 777 /* statistics */
778 /* secondary compression */ 778 usize_t n_cpy;
779 const xd3_sec_type *sec_type; 779 usize_t n_add;
780 xd3_sec_stream *sec_stream_d; 780 usize_t n_run;
781 xd3_sec_stream *sec_stream_i; 781
782 xd3_sec_stream *sec_stream_a; 782 usize_t n_ibytes;
783 783 usize_t n_sbytes;
784#if XD3_DEBUG 784 usize_t n_dbytes;
785 /* statistics */ 785
786 usize_t n_cpy; 786 usize_t l_cpy;
787 usize_t n_add; 787 usize_t l_add;
788 usize_t n_run; 788 usize_t l_run;
789 789
790 usize_t n_ibytes; 790 usize_t sh_searches;
791 usize_t n_sbytes; 791 usize_t sh_compares;
792 usize_t n_dbytes; 792
793 793 usize_t *i_freqs;
794 usize_t l_cpy; 794 usize_t *i_modes;
795 usize_t l_add; 795 usize_t *i_sizes;
796 usize_t l_run; 796
797 797 usize_t large_ckcnt;
798 usize_t sh_searches; 798
799 usize_t sh_compares; 799 /* memory usage */
800 800 usize_t alloc_cnt;
801 usize_t *i_freqs; 801 usize_t free_cnt;
802 usize_t *i_modes; 802
803 usize_t *i_sizes; 803 xoff_t n_emit;
804 804#endif
805 usize_t large_ckcnt; 805};
806 806
807 /* memory usage */ 807/******************************************************************************************
808 usize_t alloc_cnt; 808 PUBLIC FUNCTIONS
809 usize_t free_cnt; 809 ******************************************************************************************/
810 810
811 xoff_t n_emit; 811/* The two I/O disciplines, encode and decode, have similar stream semantics. It is
812#endif 812 * recommended that applications use the same code for compression and decompression -
813}; 813 * because there are only a few differences in handling encoding/decoding.
814 814 *
815/****************************************************************************************** 815 * See also the xd3_avail_input() and xd3_consume_output() routines, inlined below.
816 PUBLIC FUNCTIONS 816 *
817 ******************************************************************************************/ 817 * XD3_INPUT: the process requires more input: call xd3_avail_input() then repeat
818 818 * XD3_OUTPUT: the process has more output: read stream->next_out, stream->avail_out,
819/* The two I/O disciplines, encode and decode, have similar stream semantics. It is 819 * then call xd3_consume_output(), then repeat
820 * recommended that applications use the same code for compression and decompression - 820 * XD3_GOTHEADER: (decoder-only) notification returned following the VCDIFF header and
821 * because there are only a few differences in handling encoding/decoding. 821 * first window header. the decoder may use the header to configure itself.
822 * 822 * XD3_WINSTART: a general notification returned once for each window except the 0-th
823 * See also the xd3_avail_input() and xd3_consume_output() routines, inlined below. 823 * window, which is implied by XD3_GOTHEADER. It is recommended to
824 * 824 * use a switch-stmt such as:
825 * XD3_INPUT: the process requires more input: call xd3_avail_input() then repeat 825 * ...
826 * XD3_OUTPUT: the process has more output: read stream->next_out, stream->avail_out, 826 * again:
827 * then call xd3_consume_output(), then repeat 827 * switch ((ret = xd3_decode_input (stream))) {
828 * XD3_GOTHEADER: (decoder-only) notification returned following the VCDIFF header and 828 * case XD3_GOTHEADER: {
829 * first window header. the decoder may use the header to configure itself. 829 * assert(stream->current_window == 0);
830 * XD3_WINSTART: a general notification returned once for each window except the 0-th 830 * stuff;
831 * window, which is implied by XD3_GOTHEADER. It is recommended to 831 * }
832 * use a switch-stmt such as: 832 * // fallthrough
833 * ... 833 * case XD3_WINSTART: {
834 * again: 834 * something(stream->current_window);
835 * switch ((ret = xd3_decode_input (stream))) { 835 * goto again;
836 * case XD3_GOTHEADER: { 836 * }
837 * assert(stream->current_window == 0); 837 * ...
838 * stuff; 838 * XD3_WINFINISH: a general notification, following the complete input & output of a
839 * } 839 * window. at this point, stream->total_in and stream->total_out are
840 * // fallthrough 840 * consistent for either encoding or decoding.
841 * case XD3_WINSTART: { 841 * XD3_GETSRCBLK: If the xd3_getblk() callback is NULL, this value is returned to
842 * something(stream->current_window); 842 * initiate a non-blocking source read.
843 * goto again; 843 *
844 * } 844 * For simple usage, see the xd3_process_completely() function, which underlies
845 * ... 845 * xd3_encode_completely() and xd3_decode_completely() [xdelta3.c]. For real application
846 * XD3_WINFINISH: a general notification, following the complete input & output of a 846 * usage, including the application header, the see command-line utility [xdelta3-main.h].
847 * window. at this point, stream->total_in and stream->total_out are 847 *
848 * consistent for either encoding or decoding. 848 * main_input() implements the command-line encode and decode as well as the optional
849 * XD3_GETSRCBLK: If the xd3_getblk() callback is NULL, this value is returned to 849 * VCDIFF_TOOLS printhdr, printhdrs, and printdelta with a single loop [xdelta3-main.h].
850 * initiate a non-blocking source read. 850 */
851 * 851int xd3_decode_input (xd3_stream *stream);
852 * For simple usage, see the xd3_process_completely() function, which underlies 852int xd3_encode_input (xd3_stream *stream);
853 * xd3_encode_completely() and xd3_decode_completely() [xdelta3.c]. For real application 853
854 * usage, including the application header, the see command-line utility [xdelta3-main.h]. 854/* The xd3_config structure is used to initialize a stream - all data is copied into
855 * 855 * stream so config may be a temporary variable. See the [documentation] or comments on
856 * main_input() implements the command-line encode and decode as well as the optional 856 * the xd3_config structure. */
857 * VCDIFF_TOOLS printhdr, printhdrs, and printdelta with a single loop [xdelta3-main.h]. 857int xd3_config_stream (xd3_stream *stream,
858 */ 858 xd3_config *config);
859int xd3_decode_input (xd3_stream *stream); 859
860int xd3_encode_input (xd3_stream *stream); 860/* Since Xdelta3 doesn't open any files, xd3_close_stream is just an error check that the
861 861 * stream is in a proper state to be closed: this means the encoder is flushed and the
862/* The xd3_config structure is used to initialize a stream - all data is copied into 862 * decoder is at a window boundary. The application is responsible for freeing any of the
863 * stream so config may be a temporary variable. See the [documentation] or comments on 863 * resources it supplied. */
864 * the xd3_config structure. */ 864int xd3_close_stream (xd3_stream *stream);
865int xd3_config_stream (xd3_stream *stream, 865
866 xd3_config *config); 866/* This unconditionally closes/frees the stream, future close() will succeed.*/
867 867void xd3_abort_stream (xd3_stream *stream);
868/* Since Xdelta3 doesn't open any files, xd3_close_stream is just an error check that the 868
869 * stream is in a proper state to be closed: this means the encoder is flushed and the 869/* xd3_free_stream frees all memory allocated for the stream. The application is
870 * decoder is at a window boundary. The application is responsible for freeing any of the 870 * responsible for freeing any of the resources it supplied. */
871 * resources it supplied. */ 871void xd3_free_stream (xd3_stream *stream);
872int xd3_close_stream (xd3_stream *stream); 872
873 873/* This function informs the encoder or decoder that source matching (i.e.,
874/* This unconditionally closes/frees the stream, future close() will succeed.*/ 874 * delta-compression) is possible. For encoding, this should be called before the first
875void xd3_abort_stream (xd3_stream *stream); 875 * xd3_encode_input. A NULL source is ignored. For decoding, this should be called
876 876 * before the first window is decoded, but the appheader may be read first
877/* xd3_free_stream frees all memory allocated for the stream. The application is 877 * (XD3_GOTHEADER). At this point, consult xd3_decoder_needs_source(), inlined below, to
878 * responsible for freeing any of the resources it supplied. */ 878 * determine if a source is expected by the decoder. */
879void xd3_free_stream (xd3_stream *stream); 879int xd3_set_source (xd3_stream *stream,
880 880 xd3_source *source);
881/* This function informs the encoder or decoder that source matching (i.e., 881
882 * delta-compression) is possible. For encoding, this should be called before the first 882/* This function invokes xd3_encode_input using whole-file, in-memory inputs. The output
883 * xd3_encode_input. A NULL source is ignored. For decoding, this should be called 883 * array must be large enough to hold the output or else ENOSPC is returned. */
884 * before the first window is decoded, but the appheader may be read first 884int xd3_encode_completely (xd3_stream *stream,
885 * (XD3_GOTHEADER). At this point, consult xd3_decoder_needs_source(), inlined below, to 885 const uint8_t *input,
886 * determine if a source is expected by the decoder. */ 886 usize_t input_size,
887int xd3_set_source (xd3_stream *stream, 887 uint8_t *output,
888 xd3_source *source); 888 usize_t *output_size,
889 889 usize_t avail_output);
890/* This function invokes xd3_encode_input using whole-file, in-memory inputs. The output 890
891 * array must be large enough to hold the output or else ENOSPC is returned. */ 891/* This function invokes xd3_decode_input using whole-file, in-memory inputs. The output
892int xd3_encode_completely (xd3_stream *stream, 892 * array must be large enough to hold the output or else ENOSPC is returned. */
893 const uint8_t *input, 893int xd3_decode_completely (xd3_stream *stream,
894 usize_t input_size, 894 const uint8_t *input,
895 uint8_t *output, 895 usize_t input_size,
896 usize_t *output_size, 896 uint8_t *output,
897 usize_t avail_output); 897 usize_t *output_size,
898 898 usize_t avail_size);
899/* This function invokes xd3_decode_input using whole-file, in-memory inputs. The output 899
900 * array must be large enough to hold the output or else ENOSPC is returned. */ 900/* This should be called before the first call to xd3_encode_input() to include
901int xd3_decode_completely (xd3_stream *stream, 901 * application-specific data in the VCDIFF header. */
902 const uint8_t *input, 902void xd3_set_appheader (xd3_stream *stream,
903 usize_t input_size, 903 const uint8_t *data,
904 uint8_t *output, 904 usize_t size);
905 usize_t *output_size, 905
906 usize_t avail_size); 906/* xd3_get_appheader may be called in the decoder after XD3_GOTHEADER. For convenience,
907 907 * the decoder always adds a single byte padding to the end of the application header,
908/* This should be called before the first call to xd3_encode_input() to include 908 * which is set to zero in case the application header is a string. */
909 * application-specific data in the VCDIFF header. */ 909int xd3_get_appheader (xd3_stream *stream,
910void xd3_set_appheader (xd3_stream *stream, 910 uint8_t **data,
911 const uint8_t *data, 911 usize_t *size);
912 usize_t size); 912
913 913/* After receiving XD3_GOTHEADER, the decoder should check this function which returns 1
914/* xd3_get_appheader may be called in the decoder after XD3_GOTHEADER. For convenience, 914 * if the decoder will require source data. */
915 * the decoder always adds a single byte padding to the end of the application header, 915int xd3_decoder_needs_source (xd3_stream *stream);
916 * which is set to zero in case the application header is a string. */ 916
917int xd3_get_appheader (xd3_stream *stream, 917/* Gives an error string for xdelta3-speficic errors, returns NULL for system errors */
918 uint8_t **data, 918const char* xd3_strerror (int ret);
919 usize_t *size); 919
920 920/* For convenience, zero & initialize the xd3_config structure with specified flags. */
921/* After receiving XD3_GOTHEADER, the decoder should check this function which returns 1 921static inline
922 * if the decoder will require source data. */ 922void xd3_init_config (xd3_config *config,
923int xd3_decoder_needs_source (xd3_stream *stream); 923 int flags)
924 924{
925/* Gives an error string for xdelta3-speficic errors, returns NULL for system errors */ 925 memset (config, 0, sizeof (*config));
926const char* xd3_strerror (int ret); 926 config->flags = flags;
927 927}
928/* For convenience, zero & initialize the xd3_config structure with specified flags. */ 928
929static inline 929/* This supplies some input to the stream. */
930void xd3_init_config (xd3_config *config, 930static inline
931 int flags) 931void xd3_avail_input (xd3_stream *stream,
932{ 932 const uint8_t *idata,
933 memset (config, 0, sizeof (*config)); 933 usize_t isize)
934 config->flags = flags; 934{
935} 935 /* Even if isize is zero, the code expects a non-NULL idata. Why? It uses this value
936 936 * to determine whether xd3_avail_input has ever been called. If xd3_encode_input is
937/* This supplies some input to the stream. */ 937 * called before xd3_avail_input it will return XD3_INPUT right away without allocating
938static inline 938 * a stream->winsize buffer. This is to avoid an unwanted allocation. */
939void xd3_avail_input (xd3_stream *stream, 939 XD3_ASSERT (idata != NULL);
940 const uint8_t *idata, 940
941 usize_t isize) 941 stream->next_in = idata;
942{ 942 stream->avail_in = isize;
943 /* Even if isize is zero, the code expects a non-NULL idata. Why? It uses this value 943}
944 * to determine whether xd3_avail_input has ever been called. If xd3_encode_input is 944
945 * called before xd3_avail_input it will return XD3_INPUT right away without allocating 945/* This acknowledges receipt of output data, must be called after any XD3_OUTPUT
946 * a stream->winsize buffer. This is to avoid an unwanted allocation. */ 946 * return. */
947 XD3_ASSERT (idata != NULL); 947static inline
948 948void xd3_consume_output (xd3_stream *stream)
949 stream->next_in = idata; 949{
950 stream->avail_in = isize; 950 stream->avail_out = 0;
951} 951}
952 952
953/* This acknowledges receipt of output data, must be called after any XD3_OUTPUT 953/* These are set for each XD3_WINFINISH return. */
954 * return. */ 954static inline
955static inline 955int xd3_encoder_used_source (xd3_stream *stream) { return stream->src != NULL && stream->src->srclen > 0; }
956void xd3_consume_output (xd3_stream *stream) 956static inline
957{ 957xoff_t xd3_encoder_srcbase (xd3_stream *stream) { return stream->src->srcbase; }
958 stream->avail_out = 0; 958static inline
959} 959usize_t xd3_encoder_srclen (xd3_stream *stream) { return stream->src->srclen; }
960 960
961/* These are set for each XD3_WINFINISH return. */ 961/* Checks for legal flag changes. */
962static inline 962static inline
963int xd3_encoder_used_source (xd3_stream *stream) { return stream->src != NULL && stream->src->srclen > 0; } 963void xd3_set_flags (xd3_stream *stream, int flags)
964static inline 964{
965xoff_t xd3_encoder_srcbase (xd3_stream *stream) { return stream->src->srcbase; } 965 /* The bitwise difference should contain only XD3_FLUSH or XD3_SKIP_WINDOW */
966static inline 966 XD3_ASSERT(((flags ^ stream->flags) & ~(XD3_FLUSH | XD3_SKIP_WINDOW)) == 0);
967usize_t xd3_encoder_srclen (xd3_stream *stream) { return stream->src->srclen; } 967 stream->flags = flags;
968 968}
969/* Checks for legal flag changes. */ 969
970static inline 970/* Gives some extra information about the latest library error, if any is known. */
971void xd3_set_flags (xd3_stream *stream, int flags) 971static inline
972{ 972const char* xd3_errstring (xd3_stream *stream)
973 /* The bitwise difference should contain only XD3_FLUSH or XD3_SKIP_WINDOW */ 973{
974 XD3_ASSERT(((flags ^ stream->flags) & ~(XD3_FLUSH | XD3_SKIP_WINDOW)) == 0); 974 return stream->msg ? stream->msg : "";
975 stream->flags = flags; 975}
976} 976
977 977/* This function tells the number of bytes expected to be set in source->onblk after a
978/* Gives some extra information about the latest library error, if any is known. */ 978 * getblk request. This is for convenience of handling a partial last block. */
979static inline 979static inline
980const char* xd3_errstring (xd3_stream *stream) 980usize_t xd3_bytes_on_srcblk (xd3_source *source, xoff_t blkno)
981{ 981{
982 return stream->msg ? stream->msg : ""; 982 XD3_ASSERT (blkno < source->blocks);
983} 983
984 984 if (blkno != source->blocks - 1)
985/* This function tells the number of bytes expected to be set in source->onblk after a 985 {
986 * getblk request. This is for convenience of handling a partial last block. */ 986 return source->blksize;
987static inline 987 }
988usize_t xd3_bytes_on_srcblk (xd3_source *source, xoff_t blkno) 988
989{ 989 return (usize_t)((source->size - 1) % source->blksize) + 1;
990 XD3_ASSERT (blkno < source->blocks); 990}
991 991
992 if (blkno != source->blocks - 1) 992#endif /* _XDELTA3_H_ */
993 {
994 return source->blksize;
995 }
996
997 return (usize_t)((source->size - 1) % source->blksize) + 1;
998}
999
1000#endif /* _XDELTA3_H_ */
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-10 07:17:53 +0000