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