1 /*-
2 * Copyright 2003-2005 Colin Percival
3 * All rights reserved
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted providing that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
22 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
23 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24 * POSSIBILITY OF SUCH DAMAGE.
25 */
26
27 #if 0
28 __FBSDID("$FreeBSD: src/usr.bin/bsdiff/bsdiff/bsdiff.c,v 1.1 2005/08/06 01:59:05 cperciva Exp $");
29 #endif
30
31 #include "bsdiff/bsdiff.h"
32
33 #include <sys/types.h>
34
35 #include <err.h>
36 #include <string.h>
37
38 #include <algorithm>
39
40 #include "bsdiff/diff_encoder.h"
41 #include "bsdiff/patch_writer.h"
42 #include "bsdiff/suffix_array_index.h"
43
44 namespace bsdiff {
45
46 // TODO(deymo): Deprecate this version of the interface and move all callers
47 // to the underlying version using PatchWriterInterface instead. This allows
48 // more flexible options including different encodings.
bsdiff(const uint8_t * old_buf,size_t oldsize,const uint8_t * new_buf,size_t newsize,const char * patch_filename,SuffixArrayIndexInterface ** sai_cache)49 int bsdiff(const uint8_t* old_buf, size_t oldsize, const uint8_t* new_buf,
50 size_t newsize, const char* patch_filename,
51 SuffixArrayIndexInterface** sai_cache) {
52 BsdiffPatchWriter patch(patch_filename);
53 return bsdiff(old_buf, oldsize, new_buf, newsize, 0, &patch,
54 sai_cache);
55 }
56
bsdiff(const uint8_t * old_buf,size_t oldsize,const uint8_t * new_buf,size_t newsize,PatchWriterInterface * patch,SuffixArrayIndexInterface ** sai_cache)57 int bsdiff(const uint8_t* old_buf, size_t oldsize, const uint8_t* new_buf,
58 size_t newsize, PatchWriterInterface* patch,
59 SuffixArrayIndexInterface** sai_cache) {
60 return bsdiff(old_buf, oldsize, new_buf, newsize, 0, patch,
61 sai_cache);
62 }
63
bsdiff(const uint8_t * old_buf,size_t oldsize,const uint8_t * new_buf,size_t newsize,size_t min_length,PatchWriterInterface * patch,SuffixArrayIndexInterface ** sai_cache)64 int bsdiff(const uint8_t* old_buf, size_t oldsize, const uint8_t* new_buf,
65 size_t newsize, size_t min_length, PatchWriterInterface* patch,
66 SuffixArrayIndexInterface** sai_cache) {
67 size_t scsc, scan;
68 uint64_t pos=0;
69 size_t len;
70 size_t lastscan,lastpos,lastoffset;
71 uint64_t oldscore;
72 ssize_t s,Sf,lenf,Sb,lenb;
73 ssize_t overlap,Ss,lens;
74 ssize_t i;
75
76 std::unique_ptr<SuffixArrayIndexInterface> local_sai;
77 SuffixArrayIndexInterface* sai;
78
79 if (sai_cache && *sai_cache) {
80 sai = *sai_cache;
81 } else {
82 local_sai = CreateSuffixArrayIndex(old_buf, oldsize);
83 if (!local_sai)
84 return 1;
85 sai = local_sai.get();
86
87 // Transfer ownership to the caller.
88 if (sai_cache)
89 *sai_cache = local_sai.release();
90 }
91
92 /* Initialize the patch file encoder */
93 DiffEncoder diff_encoder(patch, old_buf, oldsize, new_buf, newsize);
94 if (!diff_encoder.Init())
95 return 1;
96
97 /* Compute the differences, writing ctrl as we go */
98 scan=0;len=0;
99 lastscan=0;lastpos=0;lastoffset=0;
100 while(scan<newsize) {
101 oldscore=0;
102
103 /* If we come across a large block of data that only differs
104 * by less than 8 bytes, this loop will take a long time to
105 * go past that block of data. We need to track the number of
106 * times we're stuck in the block and break out of it. */
107 int num_less_than_eight = 0;
108 size_t prev_len;
109 uint64_t prev_pos, prev_oldscore;
110 for(scsc=scan+=len;scan<newsize;scan++) {
111 prev_len=len;
112 prev_oldscore=oldscore;
113 prev_pos=pos;
114
115 sai->SearchPrefix(new_buf + scan, newsize - scan, &len, &pos);
116
117 for(;scsc<scan+len && scsc+lastoffset<oldsize;scsc++)
118 if(old_buf[scsc+lastoffset] == new_buf[scsc])
119 oldscore++;
120
121 if(((len==oldscore) && (len!=0)) ||
122 (len>oldscore+8 && len>=min_length)) break;
123
124 if((scan+lastoffset<oldsize) &&
125 (old_buf[scan+lastoffset] == new_buf[scan]))
126 oldscore--;
127
128 const size_t fuzz = 8;
129 if (prev_len-fuzz<=len && len<=prev_len &&
130 prev_oldscore-fuzz<=oldscore &&
131 oldscore<=prev_oldscore &&
132 prev_pos<=pos && pos <=prev_pos+fuzz &&
133 oldscore<=len && len<=oldscore+fuzz)
134 ++num_less_than_eight;
135 else
136 num_less_than_eight=0;
137 if (num_less_than_eight > 100) break;
138 };
139
140 if((len!=oldscore) || (scan==newsize)) {
141 s=0;Sf=0;lenf=0;
142 for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) {
143 if(old_buf[lastpos+i]==new_buf[lastscan+i]) s++;
144 i++;
145 if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; };
146 };
147
148 lenb=0;
149 if(scan<newsize) {
150 s=0;Sb=0;
151 for(i=1;(scan>=lastscan+i)&&(pos>=static_cast<uint64_t>(i));i++) {
152 if(old_buf[pos-i]==new_buf[scan-i]) s++;
153 if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; };
154 };
155 };
156
157 if(lastscan+lenf>scan-lenb) {
158 overlap=(lastscan+lenf)-(scan-lenb);
159 s=0;Ss=0;lens=0;
160 for(i=0;i<overlap;i++) {
161 if(new_buf[lastscan+lenf-overlap+i]==
162 old_buf[lastpos+lenf-overlap+i]) s++;
163 if(new_buf[scan-lenb+i]==
164 old_buf[pos-lenb+i]) s--;
165 if(s>Ss) { Ss=s; lens=i+1; };
166 };
167
168 lenf+=lens-overlap;
169 lenb-=lens;
170 };
171
172 if (!diff_encoder.AddControlEntry(
173 ControlEntry(lenf,
174 (scan - lenb) - (lastscan + lenf),
175 (pos - lenb) - (lastpos + lenf))))
176 errx(1, "Writing a control entry");
177
178 lastscan=scan-lenb;
179 lastpos=pos-lenb;
180 lastoffset=pos-scan;
181 };
182 };
183 if (!diff_encoder.Close())
184 errx(1, "Closing the patch file");
185
186 return 0;
187 }
188
189 } // namespace bsdiff
190