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++)
118 if((scsc+lastoffset<oldsize) &&
119 (old_buf[scsc+lastoffset] == new_buf[scsc]))
120 oldscore++;
121
122 if(((len==oldscore) && (len!=0)) ||
123 (len>oldscore+8 && len>=min_length)) break;
124
125 if((scan+lastoffset<oldsize) &&
126 (old_buf[scan+lastoffset] == new_buf[scan]))
127 oldscore--;
128
129 const size_t fuzz = 8;
130 if (prev_len-fuzz<=len && len<=prev_len &&
131 prev_oldscore-fuzz<=oldscore &&
132 oldscore<=prev_oldscore &&
133 prev_pos<=pos && pos <=prev_pos+fuzz &&
134 oldscore<=len && len<=oldscore+fuzz)
135 ++num_less_than_eight;
136 else
137 num_less_than_eight=0;
138 if (num_less_than_eight > 100) break;
139 };
140
141 if((len!=oldscore) || (scan==newsize)) {
142 s=0;Sf=0;lenf=0;
143 for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) {
144 if(old_buf[lastpos+i]==new_buf[lastscan+i]) s++;
145 i++;
146 if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; };
147 };
148
149 lenb=0;
150 if(scan<newsize) {
151 s=0;Sb=0;
152 for(i=1;(scan>=lastscan+i)&&(pos>=static_cast<uint64_t>(i));i++) {
153 if(old_buf[pos-i]==new_buf[scan-i]) s++;
154 if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; };
155 };
156 };
157
158 if(lastscan+lenf>scan-lenb) {
159 overlap=(lastscan+lenf)-(scan-lenb);
160 s=0;Ss=0;lens=0;
161 for(i=0;i<overlap;i++) {
162 if(new_buf[lastscan+lenf-overlap+i]==
163 old_buf[lastpos+lenf-overlap+i]) s++;
164 if(new_buf[scan-lenb+i]==
165 old_buf[pos-lenb+i]) s--;
166 if(s>Ss) { Ss=s; lens=i+1; };
167 };
168
169 lenf+=lens-overlap;
170 lenb-=lens;
171 };
172
173 if (!diff_encoder.AddControlEntry(
174 ControlEntry(lenf,
175 (scan - lenb) - (lastscan + lenf),
176 (pos - lenb) - (lastpos + lenf))))
177 errx(1, "Writing a control entry");
178
179 lastscan=scan-lenb;
180 lastpos=pos-lenb;
181 lastoffset=pos-scan;
182 };
183 };
184 if (!diff_encoder.Close())
185 errx(1, "Closing the patch file");
186
187 return 0;
188 }
189
190 } // namespace bsdiff
191