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
39namespace 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
52static void
53split(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
114static void
115qsufsort(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
153static int
154matchlen(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
164static int
165search(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
194static 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
202BSDiffStatus 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