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+lastoffset<oldsize;scsc++) 118 if(old_buf[scsc+lastoffset] == new_buf[scsc]) 119 oldscore++; 120 121 if(((len==oldscore) && (len!=0)) || 122 (len>oldscore+8 && len>=min_length)) break; 123 124 if((scan+lastoffset<oldsize) && 125 (old_buf[scan+lastoffset] == new_buf[scan])) 126 oldscore--; 127 128 const size_t fuzz = 8; 129 if (prev_len-fuzz<=len && len<=prev_len && 130 prev_oldscore-fuzz<=oldscore && 131 oldscore<=prev_oldscore && 132 prev_pos<=pos && pos <=prev_pos+fuzz && 133 oldscore<=len && len<=oldscore+fuzz) 134 ++num_less_than_eight; 135 else 136 num_less_than_eight=0; 137 if (num_less_than_eight > 100) break; 138 }; 139 140 if((len!=oldscore) || (scan==newsize)) { 141 s=0;Sf=0;lenf=0; 142 for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) { 143 if(old_buf[lastpos+i]==new_buf[lastscan+i]) s++; 144 i++; 145 if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; }; 146 }; 147 148 lenb=0; 149 if(scan<newsize) { 150 s=0;Sb=0; 151 for(i=1;(scan>=lastscan+i)&&(pos>=static_cast<uint64_t>(i));i++) { 152 if(old_buf[pos-i]==new_buf[scan-i]) s++; 153 if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; }; 154 }; 155 }; 156 157 if(lastscan+lenf>scan-lenb) { 158 overlap=(lastscan+lenf)-(scan-lenb); 159 s=0;Ss=0;lens=0; 160 for(i=0;i<overlap;i++) { 161 if(new_buf[lastscan+lenf-overlap+i]== 162 old_buf[lastpos+lenf-overlap+i]) s++; 163 if(new_buf[scan-lenb+i]== 164 old_buf[pos-lenb+i]) s--; 165 if(s>Ss) { Ss=s; lens=i+1; }; 166 }; 167 168 lenf+=lens-overlap; 169 lenb-=lens; 170 }; 171 172 if (!diff_encoder.AddControlEntry( 173 ControlEntry(lenf, 174 (scan - lenb) - (lastscan + lenf), 175 (pos - lenb) - (lastpos + lenf)))) 176 errx(1, "Writing a control entry"); 177 178 lastscan=scan-lenb; 179 lastpos=pos-lenb; 180 lastoffset=pos-scan; 181 }; 182 }; 183 if (!diff_encoder.Close()) 184 errx(1, "Closing the patch file"); 185 186 return 0; 187 } 188 189 } // namespace bsdiff 190