OLD | NEW |
1 /* | 1 // Copyright 2003, 2004 Colin Percival |
2 bsdiff.c -- Binary patch generator. | 2 // All rights reserved |
| 3 // |
| 4 // Redistribution and use in source and binary forms, with or without |
| 5 // modification, are permitted providing that the following conditions |
| 6 // are met: |
| 7 // 1. Redistributions of source code must retain the above copyright |
| 8 // notice, this list of conditions and the following disclaimer. |
| 9 // 2. Redistributions in binary form must reproduce the above copyright |
| 10 // notice, this list of conditions and the following disclaimer in the |
| 11 // documentation and/or other materials provided with the distribution. |
| 12 // |
| 13 // For the terms under which this work may be distributed, please see |
| 14 // the adjoining file "LICENSE". |
| 15 // |
| 16 // bsdiff_create.c -- Binary patch generator. |
| 17 // |
| 18 // ChangeLog: |
| 19 // 2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit |
| 20 // values throughout. |
| 21 // --Benjamin Smedberg <benjamin@smedbergs.us> |
| 22 // 2005-05-18 - Use the same CRC algorithm as bzip2, and leverage the CRC table |
| 23 // provided by libbz2. |
| 24 // --Darin Fisher <darin@meer.net> |
| 25 // 2007-11-14 - Changed to use Crc from Lzma library instead of Bzip library |
| 26 // --Rahul Kuchhal |
| 27 // 2009-03-31 - Change to use Streams. Added lots of comments. |
| 28 // --Stephen Adams <sra@chromium.org> |
| 29 // 2010-05-26 - Use a paged array for V and I. The address space may be too |
| 30 // fragmented for these big arrays to be contiguous. |
| 31 // --Stephen Adams <sra@chromium.org> |
| 32 // 2015-08-03 - Extract qsufsort portion to a separate file. |
| 33 // --Samuel Huang <huangs@chromium.org> |
| 34 // 2015-08-12 - Interface change to search(). |
| 35 // --Samuel Huang <huangs@chromium.org> |
3 | 36 |
4 Copyright 2003 Colin Percival | 37 // Copyright 2016 The Chromium Authors. All rights reserved. |
5 | 38 // Use of this source code is governed by a BSD-style license that can be |
6 For the terms under which this work may be distributed, please see | 39 // found in the LICENSE file. |
7 the adjoining file "LICENSE". | |
8 | |
9 ChangeLog: | |
10 2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit | |
11 values throughout. | |
12 --Benjamin Smedberg <benjamin@smedbergs.us> | |
13 2005-05-18 - Use the same CRC algorithm as bzip2, and leverage the CRC table | |
14 provided by libbz2. | |
15 --Darin Fisher <darin@meer.net> | |
16 2007-11-14 - Changed to use Crc from Lzma library instead of Bzip library | |
17 --Rahul Kuchhal | |
18 2009-03-31 - Change to use Streams. Added lots of comments. | |
19 --Stephen Adams <sra@chromium.org> | |
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. | |
22 --Stephen Adams <sra@chromium.org> | |
23 2015-08-03 - Extract qsufsort portion to a separate file. | |
24 --Samuel Huang <huangs@chromium.org> | |
25 2015-08-12 - Interface change to qsufsort search(). | |
26 --Samuel Huang <huangs@chromium.org> | |
27 */ | |
28 | 40 |
29 #include "courgette/third_party/bsdiff/bsdiff.h" | 41 #include "courgette/third_party/bsdiff/bsdiff.h" |
30 | 42 |
31 #include <stddef.h> | 43 #include <stddef.h> |
32 #include <stdint.h> | 44 #include <stdint.h> |
33 #include <stdlib.h> | 45 #include <stdlib.h> |
34 #include <algorithm> | 46 #include <algorithm> |
35 | 47 |
36 #include "base/logging.h" | 48 #include "base/logging.h" |
37 #include "base/strings/string_util.h" | 49 #include "base/strings/string_util.h" |
38 #include "base/time/time.h" | 50 #include "base/time/time.h" |
39 | 51 |
40 #include "courgette/crc.h" | 52 #include "courgette/crc.h" |
41 #include "courgette/streams.h" | 53 #include "courgette/streams.h" |
| 54 #include "courgette/third_party/bsdiff/bsdiff_search.h" |
42 #include "courgette/third_party/bsdiff/paged_array.h" | 55 #include "courgette/third_party/bsdiff/paged_array.h" |
43 #include "courgette/third_party/bsdiff/qsufsort.h" | 56 #include "courgette/third_party/bsdiff/qsufsort.h" |
44 | 57 |
45 namespace courgette { | 58 namespace { |
| 59 |
| 60 using courgette::CalculateCrc; |
| 61 using courgette::PagedArray; |
| 62 using courgette::SinkStream; |
| 63 using courgette::SinkStreamSet; |
| 64 using courgette::SourceStream; |
| 65 using courgette::SourceStreamSet; |
| 66 |
| 67 } // namespace |
| 68 |
| 69 namespace bsdiff { |
46 | 70 |
47 static CheckBool WriteHeader(SinkStream* stream, MBSPatchHeader* header) { | 71 static CheckBool WriteHeader(SinkStream* stream, MBSPatchHeader* header) { |
48 bool ok = stream->Write(header->tag, sizeof(header->tag)); | 72 bool ok = stream->Write(header->tag, sizeof(header->tag)); |
49 ok &= stream->WriteVarint32(header->slen); | 73 ok &= stream->WriteVarint32(header->slen); |
50 ok &= stream->WriteVarint32(header->scrc32); | 74 ok &= stream->WriteVarint32(header->scrc32); |
51 ok &= stream->WriteVarint32(header->dlen); | 75 ok &= stream->WriteVarint32(header->dlen); |
52 return ok; | 76 return ok; |
53 } | 77 } |
54 | 78 |
55 BSDiffStatus CreateBinaryPatch(SourceStream* old_stream, | 79 BSDiffStatus CreateBinaryPatch(SourceStream* old_stream, |
(...skipping 88 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
144 int scan = 0; | 168 int scan = 0; |
145 int match_length = 0; | 169 int match_length = 0; |
146 | 170 |
147 while (scan < newsize) { | 171 while (scan < newsize) { |
148 int pos = 0; | 172 int pos = 0; |
149 int oldscore = 0; // Count of how many bytes of the current match at |scan| | 173 int oldscore = 0; // Count of how many bytes of the current match at |scan| |
150 // extend the match at |lastscan|. | 174 // extend the match at |lastscan|. |
151 | 175 |
152 scan += match_length; | 176 scan += match_length; |
153 for (int scsc = scan; scan < newsize; ++scan) { | 177 for (int scsc = scan; scan < newsize; ++scan) { |
154 match_length = qsuf::search<PagedArray<int>&>( | 178 match_length = search<PagedArray<int>&>( |
155 I, old, oldsize, newbuf + scan, newsize - scan, &pos); | 179 I, old, oldsize, newbuf + scan, newsize - scan, &pos); |
156 | 180 |
157 for (; scsc < scan + match_length; scsc++) | 181 for (; scsc < scan + match_length; scsc++) |
158 if ((scsc + lastoffset < oldsize) && | 182 if ((scsc + lastoffset < oldsize) && |
159 (old[scsc + lastoffset] == newbuf[scsc])) | 183 (old[scsc + lastoffset] == newbuf[scsc])) |
160 oldscore++; | 184 oldscore++; |
161 | 185 |
162 if ((match_length == oldscore) && (match_length != 0)) | 186 if ((match_length == oldscore) && (match_length != 0)) |
163 break; // Good continuing match, case (1) | 187 break; // Good continuing match, case (1) |
164 if (match_length > oldscore + 8) | 188 if (match_length > oldscore + 8) |
(...skipping 144 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
309 << " (skips: " << diff_skips_length << ")" | 333 << " (skips: " << diff_skips_length << ")" |
310 << " extra bytes: " << extra_bytes_length | 334 << " extra bytes: " << extra_bytes_length |
311 << "\nUncompressed bsdiff patch size " | 335 << "\nUncompressed bsdiff patch size " |
312 << patch_stream->Length() - initial_patch_stream_length | 336 << patch_stream->Length() - initial_patch_stream_length |
313 << "\nEnd bsdiff " | 337 << "\nEnd bsdiff " |
314 << (base::Time::Now() - start_bsdiff_time).InSecondsF(); | 338 << (base::Time::Now() - start_bsdiff_time).InSecondsF(); |
315 | 339 |
316 return OK; | 340 return OK; |
317 } | 341 } |
318 | 342 |
319 } // namespace courgette | 343 } // namespace bsdiff |
OLD | NEW |