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 (at) 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 (at) 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 (at) 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 (at) 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 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 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 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 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 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 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
