OLD | NEW |
1 /* | 1 /* |
2 bsdiff.c -- Binary patch generator. | 2 bsdiff.c -- Binary patch generator. |
3 | 3 |
4 Copyright 2003 Colin Percival | 4 Copyright 2003 Colin Percival |
5 | 5 |
6 For the terms under which this work may be distributed, please see | 6 For the terms under which this work may be distributed, please see |
7 the adjoining file "LICENSE". | 7 the adjoining file "LICENSE". |
8 | 8 |
9 ChangeLog: | 9 ChangeLog: |
10 2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit | 10 2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit |
11 values throughout. | 11 values throughout. |
12 --Benjamin Smedberg <benjamin@smedbergs.us> | 12 --Benjamin Smedberg <benjamin@smedbergs.us> |
13 2005-05-18 - Use the same CRC algorithm as bzip2, and leverage the CRC table | 13 2005-05-18 - Use the same CRC algorithm as bzip2, and leverage the CRC table |
14 provided by libbz2. | 14 provided by libbz2. |
15 --Darin Fisher <darin@meer.net> | 15 --Darin Fisher <darin@meer.net> |
16 2007-11-14 - Changed to use Crc from Lzma library instead of Bzip library | 16 2007-11-14 - Changed to use Crc from Lzma library instead of Bzip library |
17 --Rahul Kuchhal | 17 --Rahul Kuchhal |
18 2009-03-31 - Change to use Streams. Added lots of comments. | 18 2009-03-31 - Change to use Streams. Added lots of comments. |
19 --Stephen Adams <sra@chromium.org> | 19 --Stephen Adams <sra@chromium.org> |
20 2010-05-26 - Use a paged array for V and I. The address space may be too | 20 2010-05-26 - Use a paged array for V and I. The address space may be too |
21 fragmented for these big arrays to be contiguous. | 21 fragmented for these big arrays to be contiguous. |
22 --Stephen Adams <sra@chromium.org> | 22 --Stephen Adams <sra@chromium.org> |
23 2015-08-03 - Extract qsufsort portion to a separate file. | 23 2015-08-03 - Extract qsufsort portion to a separate file. |
24 --Samuel Huang <huangs@chromium.org> | 24 --Samuel Huang <huangs@chromium.org> |
| 25 2015-08-12 - Interface change to qsufsort search(). |
| 26 --Samuel Huang <huangs@chromium.org> |
25 */ | 27 */ |
26 | 28 |
27 #include "courgette/third_party/bsdiff.h" | 29 #include "courgette/third_party/bsdiff.h" |
28 | 30 |
29 #include <stdlib.h> | 31 #include <stdlib.h> |
30 #include <algorithm> | 32 #include <algorithm> |
31 | 33 |
32 #include "base/logging.h" | 34 #include "base/logging.h" |
33 #include "base/memory/scoped_ptr.h" | 35 #include "base/memory/scoped_ptr.h" |
34 #include "base/strings/string_util.h" | 36 #include "base/strings/string_util.h" |
(...skipping 109 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
144 int match_length = 0; | 146 int match_length = 0; |
145 | 147 |
146 while (scan < newsize) { | 148 while (scan < newsize) { |
147 int pos = 0; | 149 int pos = 0; |
148 int oldscore = 0; // Count of how many bytes of the current match at |scan| | 150 int oldscore = 0; // Count of how many bytes of the current match at |scan| |
149 // extend the match at |lastscan|. | 151 // extend the match at |lastscan|. |
150 | 152 |
151 scan += match_length; | 153 scan += match_length; |
152 for (int scsc = scan; scan < newsize; ++scan) { | 154 for (int scsc = scan; scan < newsize; ++scan) { |
153 match_length = qsuf::search<PagedArray<int>&>( | 155 match_length = qsuf::search<PagedArray<int>&>( |
154 I, old, oldsize, newbuf + scan, newsize - scan, 0, oldsize, &pos); | 156 I, old, oldsize, newbuf + scan, newsize - scan, &pos); |
155 | 157 |
156 for ( ; scsc < scan + match_length ; scsc++) | 158 for ( ; scsc < scan + match_length ; scsc++) |
157 if ((scsc + lastoffset < oldsize) && | 159 if ((scsc + lastoffset < oldsize) && |
158 (old[scsc + lastoffset] == newbuf[scsc])) | 160 (old[scsc + lastoffset] == newbuf[scsc])) |
159 oldscore++; | 161 oldscore++; |
160 | 162 |
161 if ((match_length == oldscore) && (match_length != 0)) | 163 if ((match_length == oldscore) && (match_length != 0)) |
162 break; // Good continuing match, case (1) | 164 break; // Good continuing match, case (1) |
163 if (match_length > oldscore + 8) | 165 if (match_length > oldscore + 8) |
164 break; // New seed match, case (2) | 166 break; // New seed match, case (2) |
(...skipping 129 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
294 << " extra bytes: " << extra_bytes_length | 296 << " extra bytes: " << extra_bytes_length |
295 << "\nUncompressed bsdiff patch size " | 297 << "\nUncompressed bsdiff patch size " |
296 << patch_stream->Length() - initial_patch_stream_length | 298 << patch_stream->Length() - initial_patch_stream_length |
297 << "\nEnd bsdiff " | 299 << "\nEnd bsdiff " |
298 << (base::Time::Now() - start_bsdiff_time).InSecondsF(); | 300 << (base::Time::Now() - start_bsdiff_time).InSecondsF(); |
299 | 301 |
300 return OK; | 302 return OK; |
301 } | 303 } |
302 | 304 |
303 } // namespace courgette | 305 } // namespace courgette |
OLD | NEW |