diff options
Diffstat (limited to 'xdelta3')
-rw-r--r-- | xdelta3/badcopy.vcproj | 218 | ||||
-rwxr-xr-x | xdelta3/xdelta3-main.h | 90 | ||||
-rwxr-xr-x | xdelta3/xdelta3-test.h | 2 | ||||
-rwxr-xr-x | xdelta3/xdelta3.c | 5024 | ||||
-rwxr-xr-x | xdelta3/xdelta3.vcproj | 4 |
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 | ||
559 | static void | 572 | static 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 | ||
569 | static void | 585 | static 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) | |||
641 | static int | 674 | static int |
642 | main_file_stat (main_file *xfile, xoff_t *size, int err_ifnoseek) | 675 | main_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 | ||
666 | static int | 702 | static 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 | |||
249 | compare_files (xd3_stream *stream, const char* tgt, const char *rec) | 249 | compare_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 | |||
335 | typedef 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 | |||
359 | typedef 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 | |||
364 | typedef 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 | |||
369 | typedef 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 | |||
375 | typedef 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 | |||
387 | XD3_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 | |||
477 | IF_BUILD_SOFT(static const xd3_smatcher __smatcher_soft;) | ||
478 | IF_BUILD_FAST(static const xd3_smatcher __smatcher_fast;) | ||
479 | IF_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 | ||
545 | static void* xd3_alloc0 (xd3_stream *stream, | ||
546 | usize_t elts, | ||
547 | usize_t size); | ||
548 | |||
549 | |||
550 | static xd3_output* xd3_alloc_output (xd3_stream *stream, | ||
551 | xd3_output *old_output); | ||
552 | |||
553 | |||
554 | |||
555 | static void xd3_free_output (xd3_stream *stream, | ||
556 | xd3_output *output); | ||
557 | |||
558 | static int xd3_emit_byte (xd3_stream *stream, | ||
559 | xd3_output **outputp, | ||
560 | uint8_t code); | ||
561 | |||
562 | static int xd3_emit_bytes (xd3_stream *stream, | ||
563 | xd3_output **outputp, | ||
564 | const uint8_t *base, | ||
565 | usize_t size); | ||
566 | |||
567 | static int xd3_emit_double (xd3_stream *stream, xd3_rinst *first, xd3_rinst *second, uint code); | ||
568 | static int xd3_emit_single (xd3_stream *stream, xd3_rinst *single, uint code); | ||
569 | |||
570 | static usize_t xd3_sizeof_output (xd3_output *output); | ||
571 | |||
572 | static int xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos); | ||
573 | static int xd3_source_extend_match (xd3_stream *stream); | ||
574 | static int xd3_srcwin_setup (xd3_stream *stream); | ||
575 | static int xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point); | ||
576 | static usize_t xd3_iopt_last_matched (xd3_stream *stream); | ||
577 | static int xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output, uint32_t num); | ||
578 | |||
579 | #endif /* XD3_ENCODER */ | ||
580 | |||
581 | static 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 | |||
585 | static void xd3_compute_code_table_string (const xd3_dinst *code_table, uint8_t *str); | ||
586 | static void* xd3_alloc (xd3_stream *stream, usize_t elts, usize_t size); | ||
587 | static void xd3_free (xd3_stream *stream, void *ptr); | ||
588 | |||
589 | static 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 | ||
593 | static 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 | |||
631 | const 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 | |||
661 | static 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 | |||
687 | static 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)) */ | ||
787 | struct _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. */ | ||
794 | struct _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: */ | ||
817 | static 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 | * --------------------------------------------------------------- */ | ||
860 | static 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. */ | ||
882 | static void | ||
883 | xd3_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. */ | ||
945 | static const xd3_dinst* | ||
946 | xd3_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. */ | ||
961 | static const xd3_dinst* | ||
962 | xd3_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. */ | ||
977 | static void | ||
978 | xd3_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. */ | ||
1056 | static void | ||
1057 | xd3_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. */ | ||
1133 | static 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, | ||
1135 | 0x01,0x03,0x00,0x01,0x00,0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e, | ||
1136 | 0x0f,0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x00,0x01,0x01,0x01,0x02,0x02,0x02,0x03,0x03,0x03,0x04, | ||
1137 | 0x04,0x04,0x04,0x00,0x04,0x05,0x06,0x01,0x02,0x03,0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x05,0x05,0x05, | ||
1138 | 0x06,0x06,0x06,0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x00,0x02,0x00,0x18,0x13,0x63,0x00,0x1b,0x00,0x54, | ||
1139 | 0x00,0x15,0x23,0x6f,0x00,0x28,0x13,0x54,0x00,0x15,0x01,0x1a,0x31,0x23,0x6c,0x0d,0x23,0x48,0x00,0x15, | ||
1140 | 0x93,0x6f,0x00,0x28,0x04,0x23,0x51,0x04,0x32,0x00,0x2b,0x00,0x12,0x00,0x12,0x00,0x12,0x00,0x12,0x00, | ||
1141 | 0x12,0x00,0x12,0x53,0x57,0x9c,0x07,0x43,0x6f,0x00,0x34,0x00,0x0c,0x00,0x0c,0x00,0x0c,0x00,0x0c,0x00, | ||
1142 | 0x0c,0x00,0x0c,0x00,0x15,0x00,0x82,0x6f,0x00,0x15,0x12,0x0c,0x00,0x03,0x03,0x00,0x06,0x00,}; | ||
1143 | |||
1144 | static int | ||
1145 | xd3_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. */ | ||
1155 | static uint8_t __alternate_code_table_compressed[CODE_TABLE_VCDIFF_SIZE]; | ||
1156 | static 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. */ | ||
1161 | int 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. */ | ||
1221 | static int | ||
1222 | xd3_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. */ | ||
1271 | void 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. */ | ||
1296 | static int | ||
1297 | xd3_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. */ | ||
1381 | static int | ||
1382 | xd3_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 | |||
1434 | static 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 | ||
1478 | static 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 | |||
1492 | static const usize_t __nprimes = SIZEOF_ARRAY (__primes); | ||
1493 | #endif | ||
1494 | |||
1495 | static INLINE uint32_t | ||
1496 | xd3_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 | |||
1511 | static INLINE void | ||
1512 | xd3_swap_uint8p (uint8_t** p1, uint8_t** p2) | ||
1513 | { | ||
1514 | uint8_t *t = (*p1); | ||
1515 | (*p1) = (*p2); | ||
1516 | (*p2) = t; | ||
1517 | } | ||
1518 | |||
1519 | static INLINE void | ||
1520 | xd3_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. */ | ||
1528 | static int | ||
1529 | xd3_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 | |||
1550 | static usize_t | ||
1551 | xd3_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 | ||
1562 | static usize_t | ||
1563 | xd3_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 | |||
1581 | static void | ||
1582 | xd3_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. */ | ||
1620 | static INLINE uint32_t | ||
1621 | xd3_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 | ||
1637 | static INLINE usize_t | ||
1638 | xd3_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 | |||
1662 | static 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 | |||
1701 | static INLINE int | ||
1702 | xd3_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 | |||
1722 | static int | ||
1723 | xd3_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 | |||
1737 | static int | ||
1738 | xd3_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 | ||
1767 | static int | ||
1768 | xd3_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 | |||
1791 | static int | ||
1792 | xd3_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 | ||
1914 | static uint | ||
1915 | xd3_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 | |||
1924 | static int | ||
1925 | xd3_decode_uint32_t (xd3_stream *stream, uint32_t *val) | ||
1926 | { DECODE_INTEGER_TYPE (stream->dec_32part, UINT32_OFLOW_MASK); } | ||
1927 | |||
1928 | static int | ||
1929 | xd3_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 | ||
1933 | static int | ||
1934 | xd3_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 | ||
1940 | static int | ||
1941 | xd3_decode_uint64_t (xd3_stream *stream, uint64_t *val) | ||
1942 | { DECODE_INTEGER_TYPE (stream->dec_64part, UINT64_OFLOW_MASK); } | ||
1943 | |||
1944 | #if XD3_ENCODER | ||
1945 | static int | ||
1946 | xd3_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 | ||
1952 | static int | ||
1953 | xd3_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 | |||
1956 | static uint | ||
1957 | xd3_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 | ||
1980 | static void | ||
1981 | xd3_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 | |||
1992 | static void | ||
1993 | xd3_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 | |||
2002 | static void | ||
2003 | xd3_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 | |||
2019 | static int | ||
2020 | xd3_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 | |||
2033 | static void | ||
2034 | xd3_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 | |||
2048 | static void | ||
2049 | xd3_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? */ | ||
2065 | static int | ||
2066 | xd3_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 | |||
2128 | static int | ||
2129 | xd3_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 | |||
2174 | static void* | ||
2175 | __xd3_alloc_func (void* opaque, usize_t items, usize_t size) | ||
2176 | { | ||
2177 | return malloc (items * size); | ||
2178 | } | ||
2179 | |||
2180 | static void | ||
2181 | __xd3_free_func (void* opaque, void* address) | ||
2182 | { | ||
2183 | free (address); | ||
2184 | } | ||
2185 | |||
2186 | static void* | ||
2187 | xd3_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 | |||
2205 | static void | ||
2206 | xd3_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 | ||
2218 | static void* | ||
2219 | xd3_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 | |||
2233 | static xd3_output* | ||
2234 | xd3_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 | |||
2274 | static usize_t | ||
2275 | xd3_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 | |||
2287 | static void | ||
2288 | xd3_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 | |||
2304 | static void | ||
2305 | xd3_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 | |||
2326 | void | ||
2327 | xd3_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) | ||
2384 | static const char* | ||
2385 | xd3_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 | |||
2422 | int | ||
2423 | xd3_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. */ | ||
2565 | static int | ||
2566 | xd3_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 | |||
2611 | int | ||
2612 | xd3_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 | |||
2632 | void | ||
2633 | xd3_abort_stream (xd3_stream *stream) | ||
2634 | { | ||
2635 | stream->dec_state = DEC_ABORTED; | ||
2636 | stream->enc_state = ENC_ABORTED; | ||
2637 | } | ||
2638 | |||
2639 | int | ||
2640 | xd3_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 | |||
2676 | int | ||
2677 | xd3_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 | ||
2703 | void | ||
2704 | xd3_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 | ||
2713 | static int | ||
2714 | xd3_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 | |||
2723 | static xd3_rinst* | ||
2724 | xd3_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 | |||
2731 | static void | ||
2732 | xd3_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. */ | ||
2743 | static int | ||
2744 | xd3_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. */ | ||
2878 | static int | ||
2879 | xd3_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. */ | ||
2898 | static int | ||
2899 | xd3_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. */ | ||
2912 | static int | ||
2913 | xd3_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. */ | ||
2934 | static int | ||
2935 | xd3_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 | |||
3113 | static int | ||
3114 | xd3_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. */ | ||
3139 | static void | ||
3140 | xd3_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. */ | ||
3167 | static usize_t | ||
3168 | xd3_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 | |||
3186 | static int | ||
3187 | xd3_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 | |||
3212 | static int | ||
3213 | xd3_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. */ | ||
3239 | static INLINE int | ||
3240 | xd3_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.. */ | ||
3259 | static INLINE int | ||
3260 | xd3_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 | |||
3278 | static int | ||
3279 | xd3_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 | |||
3431 | static int | ||
3432 | xd3_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. */ | ||
3489 | static int | ||
3490 | xd3_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 | ||
3552 | static int | ||
3553 | xd3_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.) */ | ||
3570 | static void | ||
3571 | xd3_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. */ | ||
3614 | int | ||
3615 | xd3_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. */ | ||
3809 | static int | ||
3810 | xd3_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 | |||
3862 | int | ||
3863 | xd3_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 | ||
3876 | int | ||
3877 | xd3_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). */ | ||
3897 | static int | ||
3898 | xd3_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. */ | ||
3962 | static int | ||
3963 | xd3_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. */ | ||
4062 | static xoff_t | ||
4063 | xd3_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. */ | ||
4085 | static int | ||
4086 | xd3_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. */ | ||
4148 | static int | ||
4149 | xd3_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. */ | ||
4251 | static int | ||
4252 | xd3_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). */ | ||
4455 | static void | ||
4456 | xd3_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 | ||
4518 | static int | ||
4519 | xd3_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 | */ | ||
4555 | static /*inline*/ usize_t | ||
4556 | xd3_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 | ||
4654 | static void | ||
4655 | xd3_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 | |||
4664 | static void | ||
4665 | xd3_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 | |||
4674 | static void | ||
4675 | xd3_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 | |||
4711 | static int XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream); | ||
4712 | |||
4713 | static 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 | |||
4725 | static int | ||
4726 | XD3_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" |