From 512536a54a1a211a9f582e76cbf12850dc7d5466 Mon Sep 17 00:00:00 2001 From: Doug Zongker Date: Wed, 17 Feb 2010 16:11:44 -0800 Subject: relocate applypatch; add type system and new functions to edify - Move applypatch to this package (from build). - Add a rudimentary type system to edify: instead of just returning a char*, functions now return a Value*, which is a struct that can carry different types of value (currently just STRING and BLOB). Convert all functions to this new scheme. - Change the one-argument form of package_extract_file to return a Value of the new BLOB type. - Add read_file() to load a local file and return a blob, and sha1_check() to test a blob (or string) against a set of possible sha1s. read_file() uses the file-loading code from applypatch so it can read MTD partitions as well. This is the start of better integration between applypatch and the rest of edify. b/2361316 - VZW Issue PP628: Continuous reset to Droid logo: framework-res.apk update failed (CR LIBtt59130) Change-Id: Ibd038074749a4d515de1f115c498c6c589ee91e5 --- applypatch/bsdiff.c | 410 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 410 insertions(+) create mode 100644 applypatch/bsdiff.c (limited to 'applypatch/bsdiff.c') diff --git a/applypatch/bsdiff.c b/applypatch/bsdiff.c new file mode 100644 index 0000000..b6d342b --- /dev/null +++ b/applypatch/bsdiff.c @@ -0,0 +1,410 @@ +/* + * Copyright (C) 2009 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/* + * Most of this code comes from bsdiff.c from the bsdiff-4.3 + * distribution, which is: + */ + +/*- + * Copyright 2003-2005 Colin Percival + * All rights reserved + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted providing that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include + +#include +#include +#include +#include +#include +#include +#include + +#define MIN(x,y) (((x)<(y)) ? (x) : (y)) + +static void split(off_t *I,off_t *V,off_t start,off_t len,off_t h) +{ + off_t i,j,k,x,tmp,jj,kk; + + if(len<16) { + for(k=start;kstart) split(I,V,start,jj-start,h); + + for(i=0;ikk) split(I,V,kk,start+len-kk,h); +} + +static void qsufsort(off_t *I,off_t *V,u_char *old,off_t oldsize) +{ + off_t buckets[256]; + off_t i,h,len; + + for(i=0;i<256;i++) buckets[i]=0; + for(i=0;i0;i--) buckets[i]=buckets[i-1]; + buckets[0]=0; + + for(i=0;iy) { + *pos=I[st]; + return x; + } else { + *pos=I[en]; + return y; + } + }; + + x=st+(en-st)/2; + if(memcmp(old+I[x],new,MIN(oldsize-I[x],newsize))<0) { + return search(I,old,oldsize,new,newsize,x,en,pos); + } else { + return search(I,old,oldsize,new,newsize,st,x,pos); + }; +} + +static void offtout(off_t x,u_char *buf) +{ + off_t y; + + if(x<0) y=-x; else y=x; + + buf[0]=y%256;y-=buf[0]; + y=y/256;buf[1]=y%256;y-=buf[1]; + y=y/256;buf[2]=y%256;y-=buf[2]; + y=y/256;buf[3]=y%256;y-=buf[3]; + y=y/256;buf[4]=y%256;y-=buf[4]; + y=y/256;buf[5]=y%256;y-=buf[5]; + y=y/256;buf[6]=y%256;y-=buf[6]; + y=y/256;buf[7]=y%256; + + if(x<0) buf[7]|=0x80; +} + +// This is main() from bsdiff.c, with the following changes: +// +// - old, oldsize, new, newsize are arguments; we don't load this +// data from files. old and new are owned by the caller; we +// don't free them at the end. +// +// - the "I" block of memory is owned by the caller, who passes a +// pointer to *I, which can be NULL. This way if we call +// bsdiff() multiple times with the same 'old' data, we only do +// the qsufsort() step the first time. +// +int bsdiff(u_char* old, off_t oldsize, off_t** IP, u_char* new, off_t newsize, + const char* patch_filename) +{ + int fd; + off_t *I; + off_t scan,pos,len; + off_t lastscan,lastpos,lastoffset; + off_t oldscore,scsc; + off_t s,Sf,lenf,Sb,lenb; + off_t overlap,Ss,lens; + off_t i; + off_t dblen,eblen; + u_char *db,*eb; + u_char buf[8]; + u_char header[32]; + FILE * pf; + BZFILE * pfbz2; + int bz2err; + + if (*IP == NULL) { + off_t* V; + *IP = malloc((oldsize+1) * sizeof(off_t)); + V = malloc((oldsize+1) * sizeof(off_t)); + qsufsort(*IP, V, old, oldsize); + free(V); + } + I = *IP; + + if(((db=malloc(newsize+1))==NULL) || + ((eb=malloc(newsize+1))==NULL)) err(1,NULL); + dblen=0; + eblen=0; + + /* Create the patch file */ + if ((pf = fopen(patch_filename, "w")) == NULL) + err(1, "%s", patch_filename); + + /* Header is + 0 8 "BSDIFF40" + 8 8 length of bzip2ed ctrl block + 16 8 length of bzip2ed diff block + 24 8 length of new file */ + /* File is + 0 32 Header + 32 ?? Bzip2ed ctrl block + ?? ?? Bzip2ed diff block + ?? ?? Bzip2ed extra block */ + memcpy(header,"BSDIFF40",8); + offtout(0, header + 8); + offtout(0, header + 16); + offtout(newsize, header + 24); + if (fwrite(header, 32, 1, pf) != 1) + err(1, "fwrite(%s)", patch_filename); + + /* Compute the differences, writing ctrl as we go */ + if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL) + errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err); + scan=0;len=0; + lastscan=0;lastpos=0;lastoffset=0; + while(scanoldscore+8)) break; + + if((scan+lastoffsetSf*2-lenf) { Sf=s; lenf=i; }; + }; + + lenb=0; + if(scan=lastscan+i)&&(pos>=i);i++) { + if(old[pos-i]==new[scan-i]) s++; + if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; }; + }; + }; + + if(lastscan+lenf>scan-lenb) { + overlap=(lastscan+lenf)-(scan-lenb); + s=0;Ss=0;lens=0; + for(i=0;iSs) { Ss=s; lens=i+1; }; + }; + + lenf+=lens-overlap; + lenb-=lens; + }; + + for(i=0;i