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 "courgette/third_party/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 "courgette/crc.h" |
| 33 #include "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 |