• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2   bsdiff.c -- Binary patch generator.
3 
4   Copyright 2003 Colin Percival
5 
6   For the terms under which this work may be distributed, please see
7   the adjoining file "LICENSE".
8 
9   ChangeLog:
10   2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit
11                values throughout.
12                  --Benjamin Smedberg <benjamin@smedbergs.us>
13   2005-05-18 - Use the same CRC algorithm as bzip2, and leverage the CRC table
14                provided by libbz2.
15                  --Darin Fisher <darin@meer.net>
16   2007-11-14 - Changed to use Crc from Lzma library instead of Bzip library
17                  --Rahul Kuchhal
18   2009-03-31 - Change to use Streams.  Added lots of comments.
19                  --Stephen Adams <sra@chromium.org>
20   2010-05-26 - Use a paged array for V and I. The address space may be too
21                fragmented for these big arrays to be contiguous.
22                  --Stephen Adams <sra@chromium.org>
23 */
24 
25 #include "courgette/third_party/bsdiff.h"
26 
27 #include <stdlib.h>
28 #include <algorithm>
29 
30 #include "base/logging.h"
31 #include "base/memory/scoped_ptr.h"
32 #include "base/strings/string_util.h"
33 #include "base/time/time.h"
34 
35 #include "courgette/crc.h"
36 #include "courgette/streams.h"
37 #include "courgette/third_party/paged_array.h"
38 
39 namespace courgette {
40 
41 // ------------------------------------------------------------------------
42 //
43 // The following code is taken verbatim from 'bsdiff.c'. Please keep all the
44 // code formatting and variable names.  The changes from the original are (1)
45 // replacing tabs with spaces, (2) indentation, (3) using 'const', and (4)
46 // changing the V and I parameters from int* to PagedArray<int>&.
47 //
48 // The code appears to be a rewritten version of the suffix array algorithm
49 // presented in "Faster Suffix Sorting" by N. Jesper Larsson and Kunihiko
50 // Sadakane, special cased for bytes.
51 
52 static void
split(PagedArray<int> & I,PagedArray<int> & V,int start,int len,int h)53 split(PagedArray<int>& I,PagedArray<int>& V,int start,int len,int h)
54 {
55   int i,j,k,x,tmp,jj,kk;
56 
57   if(len<16) {
58     for(k=start;k<start+len;k+=j) {
59       j=1;x=V[I[k]+h];
60       for(i=1;k+i<start+len;i++) {
61         if(V[I[k+i]+h]<x) {
62           x=V[I[k+i]+h];
63           j=0;
64         };
65         if(V[I[k+i]+h]==x) {
66           tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp;
67           j++;
68         };
69       };
70       for(i=0;i<j;i++) V[I[k+i]]=k+j-1;
71       if(j==1) I[k]=-1;
72     };
73     return;
74   };
75 
76   x=V[I[start+len/2]+h];
77   jj=0;kk=0;
78   for(i=start;i<start+len;i++) {
79     if(V[I[i]+h]<x) jj++;
80     if(V[I[i]+h]==x) kk++;
81   };
82   jj+=start;kk+=jj;
83 
84   i=start;j=0;k=0;
85   while(i<jj) {
86     if(V[I[i]+h]<x) {
87       i++;
88     } else if(V[I[i]+h]==x) {
89       tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp;
90       j++;
91     } else {
92       tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp;
93       k++;
94     };
95   };
96 
97   while(jj+j<kk) {
98     if(V[I[jj+j]+h]==x) {
99       j++;
100     } else {
101       tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp;
102       k++;
103     };
104   };
105 
106   if(jj>start) split(I,V,start,jj-start,h);
107 
108   for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1;
109   if(jj==kk-1) I[jj]=-1;
110 
111   if(start+len>kk) split(I,V,kk,start+len-kk,h);
112 }
113 
114 static void
qsufsort(PagedArray<int> & I,PagedArray<int> & V,const unsigned char * old,int oldsize)115 qsufsort(PagedArray<int>& I, PagedArray<int>& V,const unsigned char *old,int oldsize)
116 {
117   int buckets[256];
118   int i,h,len;
119 
120   for(i=0;i<256;i++) buckets[i]=0;
121   for(i=0;i<oldsize;i++) buckets[old[i]]++;
122   for(i=1;i<256;i++) buckets[i]+=buckets[i-1];
123   for(i=255;i>0;i--) buckets[i]=buckets[i-1];
124   buckets[0]=0;
125 
126   for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i;
127   I[0]=oldsize;
128   for(i=0;i<oldsize;i++) V[i]=buckets[old[i]];
129   V[oldsize]=0;
130   for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1;
131   I[0]=-1;
132 
133   for(h=1;I[0]!=-(oldsize+1);h+=h) {
134     len=0;
135     for(i=0;i<oldsize+1;) {
136       if(I[i]<0) {
137         len-=I[i];
138         i-=I[i];
139       } else {
140         if(len) I[i-len]=-len;
141         len=V[I[i]]+1-i;
142         split(I,V,i,len,h);
143         i+=len;
144         len=0;
145       };
146     };
147     if(len) I[i-len]=-len;
148   };
149 
150   for(i=0;i<oldsize+1;i++) I[V[i]]=i;
151 }
152 
153 static int
matchlen(const unsigned char * old,int oldsize,const unsigned char * newbuf,int newsize)154 matchlen(const unsigned char *old,int oldsize,const unsigned char *newbuf,int newsize)
155 {
156   int i;
157 
158   for(i=0;(i<oldsize)&&(i<newsize);i++)
159     if(old[i]!=newbuf[i]) break;
160 
161   return i;
162 }
163 
164 static int
search(PagedArray<int> & I,const unsigned char * old,int oldsize,const unsigned char * newbuf,int newsize,int st,int en,int * pos)165 search(PagedArray<int>& I,const unsigned char *old,int oldsize,
166        const unsigned char *newbuf,int newsize,int st,int en,int *pos)
167 {
168   int x,y;
169 
170   if(en-st<2) {
171     x=matchlen(old+I[st],oldsize-I[st],newbuf,newsize);
172     y=matchlen(old+I[en],oldsize-I[en],newbuf,newsize);
173 
174     if(x>y) {
175       *pos=I[st];
176       return x;
177     } else {
178       *pos=I[en];
179       return y;
180     }
181   }
182 
183   x=st+(en-st)/2;
184   if(memcmp(old+I[x],newbuf,std::min(oldsize-I[x],newsize))<0) {
185     return search(I,old,oldsize,newbuf,newsize,x,en,pos);
186   } else {
187     return search(I,old,oldsize,newbuf,newsize,st,x,pos);
188   }
189 }
190 
191 //  End of 'verbatim' code.
192 // ------------------------------------------------------------------------
193 
WriteHeader(SinkStream * stream,MBSPatchHeader * header)194 static CheckBool WriteHeader(SinkStream* stream, MBSPatchHeader* header) {
195   bool ok = stream->Write(header->tag, sizeof(header->tag));
196   ok &= stream->WriteVarint32(header->slen);
197   ok &= stream->WriteVarint32(header->scrc32);
198   ok &= stream->WriteVarint32(header->dlen);
199   return ok;
200 }
201 
CreateBinaryPatch(SourceStream * old_stream,SourceStream * new_stream,SinkStream * patch_stream)202 BSDiffStatus CreateBinaryPatch(SourceStream* old_stream,
203                                SourceStream* new_stream,
204                                SinkStream* patch_stream)
205 {
206   base::Time start_bsdiff_time = base::Time::Now();
207   VLOG(1) << "Start bsdiff";
208   size_t initial_patch_stream_length = patch_stream->Length();
209 
210   SinkStreamSet patch_streams;
211   SinkStream* control_stream_copy_counts = patch_streams.stream(0);
212   SinkStream* control_stream_extra_counts = patch_streams.stream(1);
213   SinkStream* control_stream_seeks = patch_streams.stream(2);
214   SinkStream* diff_skips = patch_streams.stream(3);
215   SinkStream* diff_bytes = patch_streams.stream(4);
216   SinkStream* extra_bytes = patch_streams.stream(5);
217 
218   const uint8* old = old_stream->Buffer();
219   const int oldsize = static_cast<int>(old_stream->Remaining());
220 
221   uint32 pending_diff_zeros = 0;
222 
223   PagedArray<int> I;
224   PagedArray<int> V;
225 
226   if (!I.Allocate(oldsize + 1)) {
227     LOG(ERROR) << "Could not allocate I[], " << ((oldsize + 1) * sizeof(int))
228                << " bytes";
229     return MEM_ERROR;
230   }
231 
232   if (!V.Allocate(oldsize + 1)) {
233     LOG(ERROR) << "Could not allocate V[], " << ((oldsize + 1) * sizeof(int))
234                << " bytes";
235     return MEM_ERROR;
236   }
237 
238   base::Time q_start_time = base::Time::Now();
239   qsufsort(I, V, old, oldsize);
240   VLOG(1) << " done qsufsort "
241           << (base::Time::Now() - q_start_time).InSecondsF();
242   V.clear();
243 
244   const uint8* newbuf = new_stream->Buffer();
245   const int newsize = static_cast<int>(new_stream->Remaining());
246 
247   int control_length = 0;
248   int diff_bytes_length = 0;
249   int diff_bytes_nonzero = 0;
250   int extra_bytes_length = 0;
251 
252   // The patch format is a sequence of triples <copy,extra,seek> where 'copy' is
253   // the number of bytes to copy from the old file (possibly with mistakes),
254   // 'extra' is the number of bytes to copy from a stream of fresh bytes, and
255   // 'seek' is an offset to move to the position to copy for the next triple.
256   //
257   // The invariant at the top of this loop is that we are committed to emitting
258   // a triple for the part of |newbuf| surrounding a 'seed' match near
259   // |lastscan|.  We are searching for a second match that will be the 'seed' of
260   // the next triple.  As we scan through |newbuf|, one of four things can
261   // happen at the current position |scan|:
262   //
263   //  1. We find a nice match that appears to be consistent with the current
264   //     seed.  Continue scanning.  It is likely that this match will become
265   //     part of the 'copy'.
266   //
267   //  2. We find match which does much better than extending the current seed
268   //     old match.  Emit a triple for the current seed and take this match as
269   //     the new seed for a new triple.  By 'much better' we remove 8 mismatched
270   //     bytes by taking the new seed.
271   //
272   //  3. There is not a good match.  Continue scanning.  These bytes will likely
273   //     become part of the 'extra'.
274   //
275   //  4. There is no match because we reached the end of the input, |newbuf|.
276 
277   // This is how the loop advances through the bytes of |newbuf|:
278   //
279   // ...012345678901234567890123456789...
280   //    ssssssssss                      Seed at |lastscan|
281   //              xxyyyxxyyxy           |scan| forward, cases (3)(x) & (1)(y)
282   //                         mmmmmmmm   New match will start new seed case (2).
283   //    fffffffffffffff                 |lenf| = scan forward from |lastscan|
284   //                     bbbb           |lenb| = scan back from new seed |scan|.
285   //    ddddddddddddddd                 Emit diff bytes for the 'copy'.
286   //                   xx               Emit extra bytes.
287   //                     ssssssssssss   |lastscan = scan - lenb| is new seed.
288   //                                 x  Cases (1) and (3) ....
289 
290 
291   int lastscan = 0, lastpos = 0, lastoffset = 0;
292 
293   int scan = 0;
294   int match_length = 0;
295 
296   while (scan < newsize) {
297     int pos = 0;
298     int oldscore = 0;  // Count of how many bytes of the current match at |scan|
299                        // extend the match at |lastscan|.
300 
301     scan += match_length;
302     for (int scsc = scan;  scan < newsize;  ++scan) {
303       match_length = search(I, old, oldsize,
304                             newbuf + scan, newsize - scan,
305                             0, oldsize, &pos);
306 
307       for ( ; scsc < scan + match_length ; scsc++)
308         if ((scsc + lastoffset < oldsize) &&
309             (old[scsc + lastoffset] == newbuf[scsc]))
310           oldscore++;
311 
312       if ((match_length == oldscore) && (match_length != 0))
313         break;  // Good continuing match, case (1)
314       if (match_length > oldscore + 8)
315         break;  // New seed match, case (2)
316 
317       if ((scan + lastoffset < oldsize) &&
318           (old[scan + lastoffset] == newbuf[scan]))
319         oldscore--;
320       // Case (3) continues in this loop until we fall out of the loop (4).
321     }
322 
323     if ((match_length != oldscore) || (scan == newsize)) {  // Cases (2) and (4)
324       // This next chunk of code finds the boundary between the bytes to be
325       // copied as part of the current triple, and the bytes to be copied as
326       // part of the next triple.  The |lastscan| match is extended forwards as
327       // far as possible provided doing to does not add too many mistakes.  The
328       // |scan| match is extended backwards in a similar way.
329 
330       // Extend the current match (if any) backwards.  |lenb| is the maximal
331       // extension for which less than half the byte positions in the extension
332       // are wrong.
333       int lenb = 0;
334       if (scan < newsize) {  // i.e. not case (4); there is a match to extend.
335         int score = 0, Sb = 0;
336         for (int i = 1;  (scan >= lastscan + i) && (pos >= i);  i++) {
337           if (old[pos - i] == newbuf[scan - i]) score++;
338           if (score*2 - i > Sb*2 - lenb) { Sb = score; lenb = i; }
339         }
340       }
341 
342       // Extend the lastscan match forward; |lenf| is the maximal extension for
343       // which less than half of the byte positions in entire lastscan match are
344       // wrong.  There is a subtle point here: |lastscan| points to before the
345       // seed match by |lenb| bytes from the previous iteration.  This is why
346       // the loop measures the total number of mistakes in the the match, not
347       // just the from the match.
348       int lenf = 0;
349       {
350         int score = 0, Sf = 0;
351         for (int i = 0;  (lastscan + i < scan) && (lastpos + i < oldsize);  ) {
352           if (old[lastpos + i] == newbuf[lastscan + i]) score++;
353           i++;
354           if (score*2 - i > Sf*2 - lenf) { Sf = score; lenf = i; }
355         }
356       }
357 
358       // If the extended scans overlap, pick a position in the overlap region
359       // that maximizes the exact matching bytes.
360       if (lastscan + lenf > scan - lenb) {
361         int overlap = (lastscan + lenf) - (scan - lenb);
362         int score = 0;
363         int Ss = 0, lens = 0;
364         for (int i = 0;  i < overlap;  i++) {
365           if (newbuf[lastscan + lenf - overlap + i] ==
366               old[lastpos + lenf - overlap + i]) score++;
367           if (newbuf[scan - lenb + i] ==  old[pos - lenb + i]) score--;
368           if (score > Ss) { Ss = score; lens = i + 1; }
369         }
370 
371         lenf += lens - overlap;
372         lenb -= lens;
373       };
374 
375       for (int i = 0;  i < lenf;  i++) {
376         uint8 diff_byte = newbuf[lastscan + i] - old[lastpos + i];
377         if (diff_byte) {
378           ++diff_bytes_nonzero;
379           if (!diff_skips->WriteVarint32(pending_diff_zeros))
380             return MEM_ERROR;
381           pending_diff_zeros = 0;
382           if (!diff_bytes->Write(&diff_byte, 1))
383             return MEM_ERROR;
384         } else {
385           ++pending_diff_zeros;
386         }
387       }
388       int gap = (scan - lenb) - (lastscan + lenf);
389       for (int i = 0;  i < gap;  i++) {
390         if (!extra_bytes->Write(&newbuf[lastscan + lenf + i], 1))
391           return MEM_ERROR;
392       }
393 
394       diff_bytes_length += lenf;
395       extra_bytes_length += gap;
396 
397       uint32 copy_count = lenf;
398       uint32 extra_count = gap;
399       int32 seek_adjustment = ((pos - lenb) - (lastpos + lenf));
400 
401       if (!control_stream_copy_counts->WriteVarint32(copy_count) ||
402           !control_stream_extra_counts->WriteVarint32(extra_count) ||
403           !control_stream_seeks->WriteVarint32Signed(seek_adjustment)) {
404         return MEM_ERROR;
405       }
406 
407       ++control_length;
408 #ifdef DEBUG_bsmedberg
409       VLOG(1) << StringPrintf("Writing a block:  copy: %-8u extra: %-8u seek: "
410                               "%+-9d", copy_count, extra_count,
411                               seek_adjustment);
412 #endif
413 
414       lastscan = scan - lenb;   // Include the backward extension in seed.
415       lastpos = pos - lenb;     //  ditto.
416       lastoffset = lastpos - lastscan;
417     }
418   }
419 
420   if (!diff_skips->WriteVarint32(pending_diff_zeros))
421     return MEM_ERROR;
422 
423   I.clear();
424 
425   MBSPatchHeader header;
426   // The string will have a null terminator that we don't use, hence '-1'.
427   COMPILE_ASSERT(sizeof(MBS_PATCH_HEADER_TAG) - 1 == sizeof(header.tag),
428                  MBS_PATCH_HEADER_TAG_must_match_header_field_size);
429   memcpy(header.tag, MBS_PATCH_HEADER_TAG, sizeof(header.tag));
430   header.slen     = oldsize;
431   header.scrc32   = CalculateCrc(old, oldsize);
432   header.dlen     = newsize;
433 
434   if (!WriteHeader(patch_stream, &header))
435     return MEM_ERROR;
436 
437   size_t diff_skips_length = diff_skips->Length();
438   if (!patch_streams.CopyTo(patch_stream))
439     return MEM_ERROR;
440 
441   VLOG(1) << "Control tuples: " << control_length
442           << "  copy bytes: " << diff_bytes_length
443           << "  mistakes: " << diff_bytes_nonzero
444           << "  (skips: " << diff_skips_length << ")"
445           << "  extra bytes: " << extra_bytes_length
446           << "\nUncompressed bsdiff patch size "
447           << patch_stream->Length() - initial_patch_stream_length
448           << "\nEnd bsdiff "
449           << (base::Time::Now() - start_bsdiff_time).InSecondsF();
450 
451   return OK;
452 }
453 
454 }  // namespace
455