The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 1 | /*- |
| 2 | * Copyright 2003-2005 Colin Percival |
| 3 | * All rights reserved |
| 4 | * |
| 5 | * Redistribution and use in source and binary forms, with or without |
Alex Deymo | a5cff22 | 2015-04-08 14:10:30 -0700 | [diff] [blame] | 6 | * modification, are permitted providing that the following conditions |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 7 | * are met: |
| 8 | * 1. Redistributions of source code must retain the above copyright |
| 9 | * notice, this list of conditions and the following disclaimer. |
| 10 | * 2. Redistributions in binary form must reproduce the above copyright |
| 11 | * notice, this list of conditions and the following disclaimer in the |
| 12 | * documentation and/or other materials provided with the distribution. |
| 13 | * |
| 14 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| 15 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
| 16 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| 17 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY |
| 18 | * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| 19 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
| 20 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 21 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| 22 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING |
| 23 | * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| 24 | * POSSIBILITY OF SUCH DAMAGE. |
| 25 | */ |
| 26 | |
| 27 | #if 0 |
| 28 | __FBSDID("$FreeBSD: src/usr.bin/bsdiff/bsdiff/bsdiff.c,v 1.1 2005/08/06 01:59:05 cperciva Exp $"); |
| 29 | #endif |
| 30 | |
Alex Deymo | ddf9db5 | 2017-03-02 16:10:41 -0800 | [diff] [blame] | 31 | #include "bsdiff/bsdiff.h" |
Sen Jiang | 9b93e6a | 2016-05-03 15:09:15 -0700 | [diff] [blame] | 32 | |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 33 | #include <sys/types.h> |
| 34 | |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 35 | #include <err.h> |
| 36 | #include <fcntl.h> |
| 37 | #include <stdio.h> |
| 38 | #include <stdlib.h> |
| 39 | #include <string.h> |
| 40 | #include <unistd.h> |
| 41 | |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 42 | #include <algorithm> |
| 43 | |
Alex Deymo | dcd423b | 2017-09-13 20:54:24 +0200 | [diff] [blame] | 44 | #include "bsdiff/patch_writer.h" |
Alex Deymo | a28e019 | 2017-09-08 14:21:05 +0200 | [diff] [blame] | 45 | |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 46 | namespace bsdiff { |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 47 | |
Sen Jiang | 9b93e6a | 2016-05-03 15:09:15 -0700 | [diff] [blame] | 48 | static off_t matchlen(const u_char* old, off_t oldsize, const u_char* new_buf, |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 49 | off_t newsize) { |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 50 | off_t i; |
| 51 | |
| 52 | for(i=0;(i<oldsize)&&(i<newsize);i++) |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 53 | if(old[i]!=new_buf[i]) break; |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 54 | |
| 55 | return i; |
| 56 | } |
| 57 | |
Sen Jiang | 01a8c86 | 2016-05-06 14:17:25 -0700 | [diff] [blame] | 58 | // This is a binary search of the string |new_buf| of size |newsize| (or a |
| 59 | // prefix of it) in the |old| string with size |oldsize| using the suffix array |
| 60 | // |I|. |st| and |en| is the start and end of the search range (inclusive). |
| 61 | // Returns the length of the longest prefix found and stores the position of the |
| 62 | // string found in |*pos|. |
Sen Jiang | 9b93e6a | 2016-05-03 15:09:15 -0700 | [diff] [blame] | 63 | static off_t search(saidx_t* I, const u_char* old, off_t oldsize, |
| 64 | const u_char* new_buf, off_t newsize, off_t st, off_t en, |
| 65 | off_t* pos) { |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 66 | off_t x,y; |
| 67 | |
| 68 | if(en-st<2) { |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 69 | x=matchlen(old+I[st],oldsize-I[st],new_buf,newsize); |
| 70 | y=matchlen(old+I[en],oldsize-I[en],new_buf,newsize); |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 71 | |
| 72 | if(x>y) { |
| 73 | *pos=I[st]; |
| 74 | return x; |
| 75 | } else { |
| 76 | *pos=I[en]; |
| 77 | return y; |
| 78 | } |
| 79 | }; |
| 80 | |
| 81 | x=st+(en-st)/2; |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 82 | if(memcmp(old+I[x],new_buf,std::min(oldsize-I[x],newsize))<=0) { |
| 83 | return search(I,old,oldsize,new_buf,newsize,x,en,pos); |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 84 | } else { |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 85 | return search(I,old,oldsize,new_buf,newsize,st,x,pos); |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 86 | }; |
| 87 | } |
| 88 | |
Alex Deymo | a5cff22 | 2015-04-08 14:10:30 -0700 | [diff] [blame] | 89 | int bsdiff(const char* old_filename, const char* new_filename, |
| 90 | const char* patch_filename) { |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 91 | int fd; |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 92 | u_char *old_buf,*new_buf; |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 93 | off_t oldsize,newsize; |
Sen Jiang | 9b93e6a | 2016-05-03 15:09:15 -0700 | [diff] [blame] | 94 | |
| 95 | /* Allocate oldsize+1 bytes instead of oldsize bytes to ensure |
| 96 | that we never try to malloc(0) and get a NULL pointer */ |
| 97 | if(((fd=open(old_filename,O_RDONLY,0))<0) || |
| 98 | ((oldsize=lseek(fd,0,SEEK_END))==-1) || |
| 99 | ((old_buf=static_cast<u_char*>(malloc(oldsize+1)))==NULL) || |
| 100 | (lseek(fd,0,SEEK_SET)!=0) || |
| 101 | (read(fd,old_buf,oldsize)!=oldsize) || |
| 102 | (close(fd)==-1)) err(1,"%s",old_filename); |
| 103 | |
| 104 | /* Allocate newsize+1 bytes instead of newsize bytes to ensure |
| 105 | that we never try to malloc(0) and get a NULL pointer */ |
| 106 | if(((fd=open(new_filename,O_RDONLY,0))<0) || |
| 107 | ((newsize=lseek(fd,0,SEEK_END))==-1) || |
| 108 | ((new_buf = static_cast<u_char*>(malloc(newsize+1)))==NULL) || |
| 109 | (lseek(fd,0,SEEK_SET)!=0) || |
| 110 | (read(fd,new_buf,newsize)!=newsize) || |
| 111 | (close(fd)==-1)) err(1,"%s",new_filename); |
| 112 | |
Sen Jiang | 10df267 | 2017-01-18 17:43:51 -0800 | [diff] [blame] | 113 | int ret = bsdiff(old_buf, oldsize, new_buf, newsize, patch_filename, nullptr); |
Sen Jiang | 9b93e6a | 2016-05-03 15:09:15 -0700 | [diff] [blame] | 114 | |
| 115 | free(old_buf); |
| 116 | free(new_buf); |
| 117 | |
| 118 | return ret; |
| 119 | } |
| 120 | |
Alex Deymo | 538a75d | 2017-09-27 15:34:59 +0200 | [diff] [blame^] | 121 | // TODO(deymo): Deprecate this version of the interface and move all callers |
| 122 | // to the underlying version using PatchWriterInterface instead. This allows |
| 123 | // more flexible options including different encodings. |
Sen Jiang | 9b93e6a | 2016-05-03 15:09:15 -0700 | [diff] [blame] | 124 | int bsdiff(const u_char* old_buf, off_t oldsize, const u_char* new_buf, |
Sen Jiang | 10df267 | 2017-01-18 17:43:51 -0800 | [diff] [blame] | 125 | off_t newsize, const char* patch_filename, saidx_t** I_cache) { |
Alex Deymo | 538a75d | 2017-09-27 15:34:59 +0200 | [diff] [blame^] | 126 | BsdiffPatchWriter patch(patch_filename); |
| 127 | return bsdiff(old_buf, oldsize, new_buf, newsize, &patch, I_cache); |
| 128 | } |
| 129 | |
| 130 | int bsdiff(const u_char* old_buf, off_t oldsize, const u_char* new_buf, |
| 131 | off_t newsize, PatchWriterInterface* patch, saidx_t** I_cache) { |
Thieu Le | c2c68a7 | 2011-05-17 16:43:07 -0700 | [diff] [blame] | 132 | saidx_t *I; |
Gilad Arnold | 99b5374 | 2013-04-30 09:24:14 -0700 | [diff] [blame] | 133 | off_t scan,pos=0,len; |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 134 | off_t lastscan,lastpos,lastoffset; |
| 135 | off_t oldscore,scsc; |
| 136 | off_t s,Sf,lenf,Sb,lenb; |
| 137 | off_t overlap,Ss,lens; |
| 138 | off_t i; |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 139 | |
Sen Jiang | 10df267 | 2017-01-18 17:43:51 -0800 | [diff] [blame] | 140 | if (I_cache && *I_cache) { |
| 141 | I = *I_cache; |
| 142 | } else { |
| 143 | if ((I=static_cast<saidx_t*>(malloc((oldsize+1)*sizeof(saidx_t))))==NULL) |
| 144 | err(1,NULL); |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 145 | |
Sen Jiang | 10df267 | 2017-01-18 17:43:51 -0800 | [diff] [blame] | 146 | if (divsufsort(old_buf, I, oldsize)) err(1, "divsufsort"); |
| 147 | if (I_cache) |
| 148 | *I_cache = I; |
| 149 | } |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 150 | |
Alex Deymo | 538a75d | 2017-09-27 15:34:59 +0200 | [diff] [blame^] | 151 | /* Initialize the patch file */ |
| 152 | if (!patch->InitializeBuffers(old_buf, oldsize, new_buf, newsize)) |
Alex Deymo | a28e019 | 2017-09-08 14:21:05 +0200 | [diff] [blame] | 153 | return 1; |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 154 | |
| 155 | /* Compute the differences, writing ctrl as we go */ |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 156 | scan=0;len=0; |
| 157 | lastscan=0;lastpos=0;lastoffset=0; |
| 158 | while(scan<newsize) { |
| 159 | oldscore=0; |
| 160 | |
Thieu Le | 1f40292 | 2011-06-14 15:30:25 -0700 | [diff] [blame] | 161 | /* If we come across a large block of data that only differs |
| 162 | * by less than 8 bytes, this loop will take a long time to |
| 163 | * go past that block of data. We need to track the number of |
| 164 | * times we're stuck in the block and break out of it. */ |
| 165 | int num_less_than_eight = 0; |
| 166 | off_t prev_len, prev_oldscore, prev_pos; |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 167 | for(scsc=scan+=len;scan<newsize;scan++) { |
Thieu Le | 1f40292 | 2011-06-14 15:30:25 -0700 | [diff] [blame] | 168 | prev_len=len; |
| 169 | prev_oldscore=oldscore; |
| 170 | prev_pos=pos; |
| 171 | |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 172 | len=search(I,old_buf,oldsize,new_buf+scan,newsize-scan, |
Sen Jiang | 01a8c86 | 2016-05-06 14:17:25 -0700 | [diff] [blame] | 173 | 0,oldsize-1,&pos); |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 174 | |
| 175 | for(;scsc<scan+len;scsc++) |
| 176 | if((scsc+lastoffset<oldsize) && |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 177 | (old_buf[scsc+lastoffset] == new_buf[scsc])) |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 178 | oldscore++; |
| 179 | |
Alex Deymo | a5cff22 | 2015-04-08 14:10:30 -0700 | [diff] [blame] | 180 | if(((len==oldscore) && (len!=0)) || |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 181 | (len>oldscore+8)) break; |
| 182 | |
| 183 | if((scan+lastoffset<oldsize) && |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 184 | (old_buf[scan+lastoffset] == new_buf[scan])) |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 185 | oldscore--; |
Thieu Le | 1f40292 | 2011-06-14 15:30:25 -0700 | [diff] [blame] | 186 | |
Thieu Le | d172820 | 2012-03-28 17:12:42 -0700 | [diff] [blame] | 187 | const off_t fuzz = 8; |
| 188 | if (prev_len-fuzz<=len && len<=prev_len && |
| 189 | prev_oldscore-fuzz<=oldscore && |
| 190 | oldscore<=prev_oldscore && |
| 191 | prev_pos<=pos && pos <=prev_pos+fuzz && |
| 192 | oldscore<=len && len<=oldscore+fuzz) |
Thieu Le | 1f40292 | 2011-06-14 15:30:25 -0700 | [diff] [blame] | 193 | ++num_less_than_eight; |
| 194 | else |
| 195 | num_less_than_eight=0; |
| 196 | if (num_less_than_eight > 100) break; |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 197 | }; |
| 198 | |
| 199 | if((len!=oldscore) || (scan==newsize)) { |
| 200 | s=0;Sf=0;lenf=0; |
| 201 | for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) { |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 202 | if(old_buf[lastpos+i]==new_buf[lastscan+i]) s++; |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 203 | i++; |
| 204 | if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; }; |
| 205 | }; |
| 206 | |
| 207 | lenb=0; |
| 208 | if(scan<newsize) { |
| 209 | s=0;Sb=0; |
| 210 | for(i=1;(scan>=lastscan+i)&&(pos>=i);i++) { |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 211 | if(old_buf[pos-i]==new_buf[scan-i]) s++; |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 212 | if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; }; |
| 213 | }; |
| 214 | }; |
| 215 | |
| 216 | if(lastscan+lenf>scan-lenb) { |
| 217 | overlap=(lastscan+lenf)-(scan-lenb); |
| 218 | s=0;Ss=0;lens=0; |
| 219 | for(i=0;i<overlap;i++) { |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 220 | if(new_buf[lastscan+lenf-overlap+i]== |
| 221 | old_buf[lastpos+lenf-overlap+i]) s++; |
| 222 | if(new_buf[scan-lenb+i]== |
| 223 | old_buf[pos-lenb+i]) s--; |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 224 | if(s>Ss) { Ss=s; lens=i+1; }; |
| 225 | }; |
| 226 | |
| 227 | lenf+=lens-overlap; |
| 228 | lenb-=lens; |
| 229 | }; |
| 230 | |
Alex Deymo | 538a75d | 2017-09-27 15:34:59 +0200 | [diff] [blame^] | 231 | if (!patch->AddControlEntry( |
| 232 | ControlEntry(lenf, |
| 233 | (scan - lenb) - (lastscan + lenf), |
| 234 | (pos - lenb) - (lastpos + lenf)))) |
Alex Deymo | a28e019 | 2017-09-08 14:21:05 +0200 | [diff] [blame] | 235 | errx(1, "Writing a control entry"); |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 236 | |
| 237 | lastscan=scan-lenb; |
| 238 | lastpos=pos-lenb; |
| 239 | lastoffset=pos-scan; |
| 240 | }; |
| 241 | }; |
Alex Deymo | 538a75d | 2017-09-27 15:34:59 +0200 | [diff] [blame^] | 242 | if (!patch->Close()) |
Alex Deymo | a28e019 | 2017-09-08 14:21:05 +0200 | [diff] [blame] | 243 | errx(1, "Closing the patch file"); |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 244 | |
Sen Jiang | 10df267 | 2017-01-18 17:43:51 -0800 | [diff] [blame] | 245 | if (I_cache == nullptr) |
| 246 | free(I); |
The Android Open Source Project | c285fea | 2009-03-03 19:29:20 -0800 | [diff] [blame] | 247 | |
| 248 | return 0; |
| 249 | } |
Alex Deymo | 20891f9 | 2015-10-12 17:28:04 -0700 | [diff] [blame] | 250 | |
| 251 | } // namespace bsdiff |