1 /*- 2 * Copyright 2003-2005 Colin Percival 3 * All rights reserved 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted providing that the following conditions 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 31 #include "bsdiff/bsdiff.h" 32 33 #include <sys/types.h> 34 35 #include <err.h> 36 #include <string.h> 37 38 #include <algorithm> 39 40 #include "bsdiff/diff_encoder.h" 41 #include "bsdiff/patch_writer.h" 42 #include "bsdiff/suffix_array_index.h" 43 44 namespace bsdiff { 45 46 // TODO(deymo): Deprecate this version of the interface and move all callers 47 // to the underlying version using PatchWriterInterface instead. This allows 48 // more flexible options including different encodings. 49 int bsdiff(const uint8_t* old_buf, size_t oldsize, const uint8_t* new_buf, 50 size_t newsize, const char* patch_filename, 51 SuffixArrayIndexInterface** sai_cache) { 52 BsdiffPatchWriter patch(patch_filename); 53 return bsdiff(old_buf, oldsize, new_buf, newsize, 0, &patch, 54 sai_cache); 55 } 56 57 int bsdiff(const uint8_t* old_buf, size_t oldsize, const uint8_t* new_buf, 58 size_t newsize, PatchWriterInterface* patch, 59 SuffixArrayIndexInterface** sai_cache) { 60 return bsdiff(old_buf, oldsize, new_buf, newsize, 0, patch, 61 sai_cache); 62 } 63 64 int bsdiff(const uint8_t* old_buf, size_t oldsize, const uint8_t* new_buf, 65 size_t newsize, size_t min_length, PatchWriterInterface* patch, 66 SuffixArrayIndexInterface** sai_cache) { 67 size_t scsc, scan; 68 uint64_t pos=0; 69 size_t len; 70 size_t lastscan,lastpos,lastoffset; 71 uint64_t oldscore; 72 ssize_t s,Sf,lenf,Sb,lenb; 73 ssize_t overlap,Ss,lens; 74 ssize_t i; 75 76 std::unique_ptr<SuffixArrayIndexInterface> local_sai; 77 SuffixArrayIndexInterface* sai; 78 79 if (sai_cache && *sai_cache) { 80 sai = *sai_cache; 81 } else { 82 local_sai = CreateSuffixArrayIndex(old_buf, oldsize); 83 if (!local_sai) 84 return 1; 85 sai = local_sai.get(); 86 87 // Transfer ownership to the caller. 88 if (sai_cache) 89 *sai_cache = local_sai.release(); 90 } 91 92 /* Initialize the patch file encoder */ 93 DiffEncoder diff_encoder(patch, old_buf, oldsize, new_buf, newsize); 94 if (!diff_encoder.Init()) 95 return 1; 96 97 /* Compute the differences, writing ctrl as we go */ 98 scan=0;len=0; 99 lastscan=0;lastpos=0;lastoffset=0; 100 while(scan<newsize) { 101 oldscore=0; 102 103 /* If we come across a large block of data that only differs 104 * by less than 8 bytes, this loop will take a long time to 105 * go past that block of data. We need to track the number of 106 * times we're stuck in the block and break out of it. */ 107 int num_less_than_eight = 0; 108 size_t prev_len; 109 uint64_t prev_pos, prev_oldscore; 110 for(scsc=scan+=len;scan<newsize;scan++) { 111 prev_len=len; 112 prev_oldscore=oldscore; 113 prev_pos=pos; 114 115 sai->SearchPrefix(new_buf + scan, newsize - scan, &len, &pos); 116 117 for(;scsc<scan+len;scsc++) 118 if((scsc+lastoffset<oldsize) && 119 (old_buf[scsc+lastoffset] == new_buf[scsc])) 120 oldscore++; 121 122 if(((len==oldscore) && (len!=0)) || 123 (len>oldscore+8 && len>=min_length)) break; 124 125 if((scan+lastoffset<oldsize) && 126 (old_buf[scan+lastoffset] == new_buf[scan])) 127 oldscore--; 128 129 const size_t fuzz = 8; 130 if (prev_len-fuzz<=len && len<=prev_len && 131 prev_oldscore-fuzz<=oldscore && 132 oldscore<=prev_oldscore && 133 prev_pos<=pos && pos <=prev_pos+fuzz && 134 oldscore<=len && len<=oldscore+fuzz) 135 ++num_less_than_eight; 136 else 137 num_less_than_eight=0; 138 if (num_less_than_eight > 100) break; 139 }; 140 141 if((len!=oldscore) || (scan==newsize)) { 142 s=0;Sf=0;lenf=0; 143 for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) { 144 if(old_buf[lastpos+i]==new_buf[lastscan+i]) s++; 145 i++; 146 if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; }; 147 }; 148 149 lenb=0; 150 if(scan<newsize) { 151 s=0;Sb=0; 152 for(i=1;(scan>=lastscan+i)&&(pos>=static_cast<uint64_t>(i));i++) { 153 if(old_buf[pos-i]==new_buf[scan-i]) s++; 154 if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; }; 155 }; 156 }; 157 158 if(lastscan+lenf>scan-lenb) { 159 overlap=(lastscan+lenf)-(scan-lenb); 160 s=0;Ss=0;lens=0; 161 for(i=0;i<overlap;i++) { 162 if(new_buf[lastscan+lenf-overlap+i]== 163 old_buf[lastpos+lenf-overlap+i]) s++; 164 if(new_buf[scan-lenb+i]== 165 old_buf[pos-lenb+i]) s--; 166 if(s>Ss) { Ss=s; lens=i+1; }; 167 }; 168 169 lenf+=lens-overlap; 170 lenb-=lens; 171 }; 172 173 if (!diff_encoder.AddControlEntry( 174 ControlEntry(lenf, 175 (scan - lenb) - (lastscan + lenf), 176 (pos - lenb) - (lastpos + lenf)))) 177 errx(1, "Writing a control entry"); 178 179 lastscan=scan-lenb; 180 lastpos=pos-lenb; 181 lastoffset=pos-scan; 182 }; 183 }; 184 if (!diff_encoder.Close()) 185 errx(1, "Closing the patch file"); 186 187 return 0; 188 } 189 190 } // namespace bsdiff 191
