1 /* 2 * Copyright (C) 2009 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 /* 18 * Most of this code comes from bsdiff.c from the bsdiff-4.3 19 * distribution, which is: 20 */ 21 22 /*- 23 * Copyright 2003-2005 Colin Percival 24 * All rights reserved 25 * 26 * Redistribution and use in source and binary forms, with or without 27 * modification, are permitted providing that the following conditions 28 * are met: 29 * 1. Redistributions of source code must retain the above copyright 30 * notice, this list of conditions and the following disclaimer. 31 * 2. Redistributions in binary form must reproduce the above copyright 32 * notice, this list of conditions and the following disclaimer in the 33 * documentation and/or other materials provided with the distribution. 34 * 35 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 36 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 37 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 38 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 39 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 40 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 41 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 42 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 43 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 44 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 45 * POSSIBILITY OF SUCH DAMAGE. 46 */ 47 48 #include <sys/types.h> 49 50 #include <bzlib.h> 51 #include <err.h> 52 #include <fcntl.h> 53 #include <stdio.h> 54 #include <stdlib.h> 55 #include <string.h> 56 #include <unistd.h> 57 58 #define MIN(x,y) (((x)<(y)) ? (x) : (y)) 59 60 static void split(off_t *I,off_t *V,off_t start,off_t len,off_t h) 61 { 62 off_t i,j,k,x,tmp,jj,kk; 63 64 if(len<16) { 65 for(k=start;k<start+len;k+=j) { 66 j=1;x=V[I[k]+h]; 67 for(i=1;k+i<start+len;i++) { 68 if(V[I[k+i]+h]<x) { 69 x=V[I[k+i]+h]; 70 j=0; 71 }; 72 if(V[I[k+i]+h]==x) { 73 tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp; 74 j++; 75 }; 76 }; 77 for(i=0;i<j;i++) V[I[k+i]]=k+j-1; 78 if(j==1) I[k]=-1; 79 }; 80 return; 81 }; 82 83 x=V[I[start+len/2]+h]; 84 jj=0;kk=0; 85 for(i=start;i<start+len;i++) { 86 if(V[I[i]+h]<x) jj++; 87 if(V[I[i]+h]==x) kk++; 88 }; 89 jj+=start;kk+=jj; 90 91 i=start;j=0;k=0; 92 while(i<jj) { 93 if(V[I[i]+h]<x) { 94 i++; 95 } else if(V[I[i]+h]==x) { 96 tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp; 97 j++; 98 } else { 99 tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp; 100 k++; 101 }; 102 }; 103 104 while(jj+j<kk) { 105 if(V[I[jj+j]+h]==x) { 106 j++; 107 } else { 108 tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp; 109 k++; 110 }; 111 }; 112 113 if(jj>start) split(I,V,start,jj-start,h); 114 115 for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1; 116 if(jj==kk-1) I[jj]=-1; 117 118 if(start+len>kk) split(I,V,kk,start+len-kk,h); 119 } 120 121 static void qsufsort(off_t *I,off_t *V,u_char *old,off_t oldsize) 122 { 123 off_t buckets[256]; 124 off_t i,h,len; 125 126 for(i=0;i<256;i++) buckets[i]=0; 127 for(i=0;i<oldsize;i++) buckets[old[i]]++; 128 for(i=1;i<256;i++) buckets[i]+=buckets[i-1]; 129 for(i=255;i>0;i--) buckets[i]=buckets[i-1]; 130 buckets[0]=0; 131 132 for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i; 133 I[0]=oldsize; 134 for(i=0;i<oldsize;i++) V[i]=buckets[old[i]]; 135 V[oldsize]=0; 136 for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1; 137 I[0]=-1; 138 139 for(h=1;I[0]!=-(oldsize+1);h+=h) { 140 len=0; 141 for(i=0;i<oldsize+1;) { 142 if(I[i]<0) { 143 len-=I[i]; 144 i-=I[i]; 145 } else { 146 if(len) I[i-len]=-len; 147 len=V[I[i]]+1-i; 148 split(I,V,i,len,h); 149 i+=len; 150 len=0; 151 }; 152 }; 153 if(len) I[i-len]=-len; 154 }; 155 156 for(i=0;i<oldsize+1;i++) I[V[i]]=i; 157 } 158 159 static off_t matchlen(u_char *old,off_t oldsize,u_char *new,off_t newsize) 160 { 161 off_t i; 162 163 for(i=0;(i<oldsize)&&(i<newsize);i++) 164 if(old[i]!=new[i]) break; 165 166 return i; 167 } 168 169 static off_t search(off_t *I,u_char *old,off_t oldsize, 170 u_char *new,off_t newsize,off_t st,off_t en,off_t *pos) 171 { 172 off_t x,y; 173 174 if(en-st<2) { 175 x=matchlen(old+I[st],oldsize-I[st],new,newsize); 176 y=matchlen(old+I[en],oldsize-I[en],new,newsize); 177 178 if(x>y) { 179 *pos=I[st]; 180 return x; 181 } else { 182 *pos=I[en]; 183 return y; 184 } 185 }; 186 187 x=st+(en-st)/2; 188 if(memcmp(old+I[x],new,MIN(oldsize-I[x],newsize))<0) { 189 return search(I,old,oldsize,new,newsize,x,en,pos); 190 } else { 191 return search(I,old,oldsize,new,newsize,st,x,pos); 192 }; 193 } 194 195 static void offtout(off_t x,u_char *buf) 196 { 197 off_t y; 198 199 if(x<0) y=-x; else y=x; 200 201 buf[0]=y%256;y-=buf[0]; 202 y=y/256;buf[1]=y%256;y-=buf[1]; 203 y=y/256;buf[2]=y%256;y-=buf[2]; 204 y=y/256;buf[3]=y%256;y-=buf[3]; 205 y=y/256;buf[4]=y%256;y-=buf[4]; 206 y=y/256;buf[5]=y%256;y-=buf[5]; 207 y=y/256;buf[6]=y%256;y-=buf[6]; 208 y=y/256;buf[7]=y%256; 209 210 if(x<0) buf[7]|=0x80; 211 } 212 213 // This is main() from bsdiff.c, with the following changes: 214 // 215 // - old, oldsize, new, newsize are arguments; we don't load this 216 // data from files. old and new are owned by the caller; we 217 // don't free them at the end. 218 // 219 // - the "I" block of memory is owned by the caller, who passes a 220 // pointer to *I, which can be NULL. This way if we call 221 // bsdiff() multiple times with the same 'old' data, we only do 222 // the qsufsort() step the first time. 223 // 224 int bsdiff(u_char* old, off_t oldsize, off_t** IP, u_char* new, off_t newsize, 225 const char* patch_filename) 226 { 227 int fd; 228 off_t *I; 229 off_t scan,pos,len; 230 off_t lastscan,lastpos,lastoffset; 231 off_t oldscore,scsc; 232 off_t s,Sf,lenf,Sb,lenb; 233 off_t overlap,Ss,lens; 234 off_t i; 235 off_t dblen,eblen; 236 u_char *db,*eb; 237 u_char buf[8]; 238 u_char header[32]; 239 FILE * pf; 240 BZFILE * pfbz2; 241 int bz2err; 242 243 if (*IP == NULL) { 244 off_t* V; 245 *IP = malloc((oldsize+1) * sizeof(off_t)); 246 V = malloc((oldsize+1) * sizeof(off_t)); 247 qsufsort(*IP, V, old, oldsize); 248 free(V); 249 } 250 I = *IP; 251 252 if(((db=malloc(newsize+1))==NULL) || 253 ((eb=malloc(newsize+1))==NULL)) err(1,NULL); 254 dblen=0; 255 eblen=0; 256 257 /* Create the patch file */ 258 if ((pf = fopen(patch_filename, "w")) == NULL) 259 err(1, "%s", patch_filename); 260 261 /* Header is 262 0 8 "BSDIFF40" 263 8 8 length of bzip2ed ctrl block 264 16 8 length of bzip2ed diff block 265 24 8 length of new file */ 266 /* File is 267 0 32 Header 268 32 ?? Bzip2ed ctrl block 269 ?? ?? Bzip2ed diff block 270 ?? ?? Bzip2ed extra block */ 271 memcpy(header,"BSDIFF40",8); 272 offtout(0, header + 8); 273 offtout(0, header + 16); 274 offtout(newsize, header + 24); 275 if (fwrite(header, 32, 1, pf) != 1) 276 err(1, "fwrite(%s)", patch_filename); 277 278 /* Compute the differences, writing ctrl as we go */ 279 if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL) 280 errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err); 281 scan=0;len=0; 282 lastscan=0;lastpos=0;lastoffset=0; 283 while(scan<newsize) { 284 oldscore=0; 285 286 for(scsc=scan+=len;scan<newsize;scan++) { 287 len=search(I,old,oldsize,new+scan,newsize-scan, 288 0,oldsize,&pos); 289 290 for(;scsc<scan+len;scsc++) 291 if((scsc+lastoffset<oldsize) && 292 (old[scsc+lastoffset] == new[scsc])) 293 oldscore++; 294 295 if(((len==oldscore) && (len!=0)) || 296 (len>oldscore+8)) break; 297 298 if((scan+lastoffset<oldsize) && 299 (old[scan+lastoffset] == new[scan])) 300 oldscore--; 301 }; 302 303 if((len!=oldscore) || (scan==newsize)) { 304 s=0;Sf=0;lenf=0; 305 for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) { 306 if(old[lastpos+i]==new[lastscan+i]) s++; 307 i++; 308 if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; }; 309 }; 310 311 lenb=0; 312 if(scan<newsize) { 313 s=0;Sb=0; 314 for(i=1;(scan>=lastscan+i)&&(pos>=i);i++) { 315 if(old[pos-i]==new[scan-i]) s++; 316 if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; }; 317 }; 318 }; 319 320 if(lastscan+lenf>scan-lenb) { 321 overlap=(lastscan+lenf)-(scan-lenb); 322 s=0;Ss=0;lens=0; 323 for(i=0;i<overlap;i++) { 324 if(new[lastscan+lenf-overlap+i]== 325 old[lastpos+lenf-overlap+i]) s++; 326 if(new[scan-lenb+i]== 327 old[pos-lenb+i]) s--; 328 if(s>Ss) { Ss=s; lens=i+1; }; 329 }; 330 331 lenf+=lens-overlap; 332 lenb-=lens; 333 }; 334 335 for(i=0;i<lenf;i++) 336 db[dblen+i]=new[lastscan+i]-old[lastpos+i]; 337 for(i=0;i<(scan-lenb)-(lastscan+lenf);i++) 338 eb[eblen+i]=new[lastscan+lenf+i]; 339 340 dblen+=lenf; 341 eblen+=(scan-lenb)-(lastscan+lenf); 342 343 offtout(lenf,buf); 344 BZ2_bzWrite(&bz2err, pfbz2, buf, 8); 345 if (bz2err != BZ_OK) 346 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err); 347 348 offtout((scan-lenb)-(lastscan+lenf),buf); 349 BZ2_bzWrite(&bz2err, pfbz2, buf, 8); 350 if (bz2err != BZ_OK) 351 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err); 352 353 offtout((pos-lenb)-(lastpos+lenf),buf); 354 BZ2_bzWrite(&bz2err, pfbz2, buf, 8); 355 if (bz2err != BZ_OK) 356 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err); 357 358 lastscan=scan-lenb; 359 lastpos=pos-lenb; 360 lastoffset=pos-scan; 361 }; 362 }; 363 BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL); 364 if (bz2err != BZ_OK) 365 errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err); 366 367 /* Compute size of compressed ctrl data */ 368 if ((len = ftello(pf)) == -1) 369 err(1, "ftello"); 370 offtout(len-32, header + 8); 371 372 /* Write compressed diff data */ 373 if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL) 374 errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err); 375 BZ2_bzWrite(&bz2err, pfbz2, db, dblen); 376 if (bz2err != BZ_OK) 377 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err); 378 BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL); 379 if (bz2err != BZ_OK) 380 errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err); 381 382 /* Compute size of compressed diff data */ 383 if ((newsize = ftello(pf)) == -1) 384 err(1, "ftello"); 385 offtout(newsize - len, header + 16); 386 387 /* Write compressed extra data */ 388 if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL) 389 errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err); 390 BZ2_bzWrite(&bz2err, pfbz2, eb, eblen); 391 if (bz2err != BZ_OK) 392 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err); 393 BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL); 394 if (bz2err != BZ_OK) 395 errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err); 396 397 /* Seek to the beginning, write the header, and close the file */ 398 if (fseeko(pf, 0, SEEK_SET)) 399 err(1, "fseeko"); 400 if (fwrite(header, 32, 1, pf) != 1) 401 err(1, "fwrite(%s)", patch_filename); 402 if (fclose(pf)) 403 err(1, "fclose"); 404 405 /* Free the memory we used */ 406 free(db); 407 free(eb); 408 409 return 0; 410 } 411
