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