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 |
(...skipping 10 matching lines...) Expand all Loading... |
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(). | 25 2015-08-12 - Interface change to qsufsort search(). |
26 --Samuel Huang <huangs@chromium.org> | 26 --Samuel Huang <huangs@chromium.org> |
27 */ | 27 */ |
28 | 28 |
29 #include "courgette/third_party/bsdiff.h" | 29 #include "courgette/third_party/bsdiff.h" |
30 | 30 |
| 31 #include <stddef.h> |
| 32 #include <stdint.h> |
31 #include <stdlib.h> | 33 #include <stdlib.h> |
32 #include <algorithm> | 34 #include <algorithm> |
33 | 35 |
34 #include "base/logging.h" | 36 #include "base/logging.h" |
35 #include "base/memory/scoped_ptr.h" | 37 #include "base/memory/scoped_ptr.h" |
36 #include "base/strings/string_util.h" | 38 #include "base/strings/string_util.h" |
37 #include "base/time/time.h" | 39 #include "base/time/time.h" |
38 | 40 |
39 #include "courgette/crc.h" | 41 #include "courgette/crc.h" |
40 #include "courgette/streams.h" | 42 #include "courgette/streams.h" |
(...skipping 19 matching lines...) Expand all Loading... |
60 size_t initial_patch_stream_length = patch_stream->Length(); | 62 size_t initial_patch_stream_length = patch_stream->Length(); |
61 | 63 |
62 SinkStreamSet patch_streams; | 64 SinkStreamSet patch_streams; |
63 SinkStream* control_stream_copy_counts = patch_streams.stream(0); | 65 SinkStream* control_stream_copy_counts = patch_streams.stream(0); |
64 SinkStream* control_stream_extra_counts = patch_streams.stream(1); | 66 SinkStream* control_stream_extra_counts = patch_streams.stream(1); |
65 SinkStream* control_stream_seeks = patch_streams.stream(2); | 67 SinkStream* control_stream_seeks = patch_streams.stream(2); |
66 SinkStream* diff_skips = patch_streams.stream(3); | 68 SinkStream* diff_skips = patch_streams.stream(3); |
67 SinkStream* diff_bytes = patch_streams.stream(4); | 69 SinkStream* diff_bytes = patch_streams.stream(4); |
68 SinkStream* extra_bytes = patch_streams.stream(5); | 70 SinkStream* extra_bytes = patch_streams.stream(5); |
69 | 71 |
70 const uint8* old = old_stream->Buffer(); | 72 const uint8_t* old = old_stream->Buffer(); |
71 const int oldsize = static_cast<int>(old_stream->Remaining()); | 73 const int oldsize = static_cast<int>(old_stream->Remaining()); |
72 | 74 |
73 uint32 pending_diff_zeros = 0; | 75 uint32_t pending_diff_zeros = 0; |
74 | 76 |
75 PagedArray<int> I; | 77 PagedArray<int> I; |
76 PagedArray<int> V; | 78 PagedArray<int> V; |
77 | 79 |
78 if (!I.Allocate(oldsize + 1)) { | 80 if (!I.Allocate(oldsize + 1)) { |
79 LOG(ERROR) << "Could not allocate I[], " << ((oldsize + 1) * sizeof(int)) | 81 LOG(ERROR) << "Could not allocate I[], " << ((oldsize + 1) * sizeof(int)) |
80 << " bytes"; | 82 << " bytes"; |
81 return MEM_ERROR; | 83 return MEM_ERROR; |
82 } | 84 } |
83 | 85 |
84 if (!V.Allocate(oldsize + 1)) { | 86 if (!V.Allocate(oldsize + 1)) { |
85 LOG(ERROR) << "Could not allocate V[], " << ((oldsize + 1) * sizeof(int)) | 87 LOG(ERROR) << "Could not allocate V[], " << ((oldsize + 1) * sizeof(int)) |
86 << " bytes"; | 88 << " bytes"; |
87 return MEM_ERROR; | 89 return MEM_ERROR; |
88 } | 90 } |
89 | 91 |
90 base::Time q_start_time = base::Time::Now(); | 92 base::Time q_start_time = base::Time::Now(); |
91 qsuf::qsufsort<PagedArray<int>&>(I, V, old, oldsize); | 93 qsuf::qsufsort<PagedArray<int>&>(I, V, old, oldsize); |
92 VLOG(1) << " done qsufsort " | 94 VLOG(1) << " done qsufsort " |
93 << (base::Time::Now() - q_start_time).InSecondsF(); | 95 << (base::Time::Now() - q_start_time).InSecondsF(); |
94 V.clear(); | 96 V.clear(); |
95 | 97 |
96 const uint8* newbuf = new_stream->Buffer(); | 98 const uint8_t* newbuf = new_stream->Buffer(); |
97 const int newsize = static_cast<int>(new_stream->Remaining()); | 99 const int newsize = static_cast<int>(new_stream->Remaining()); |
98 | 100 |
99 int control_length = 0; | 101 int control_length = 0; |
100 int diff_bytes_length = 0; | 102 int diff_bytes_length = 0; |
101 int diff_bytes_nonzero = 0; | 103 int diff_bytes_nonzero = 0; |
102 int extra_bytes_length = 0; | 104 int extra_bytes_length = 0; |
103 | 105 |
104 // The patch format is a sequence of triples <copy,extra,seek> where 'copy' is | 106 // The patch format is a sequence of triples <copy,extra,seek> where 'copy' is |
105 // the number of bytes to copy from the old file (possibly with mistakes), | 107 // the number of bytes to copy from the old file (possibly with mistakes), |
106 // 'extra' is the number of bytes to copy from a stream of fresh bytes, and | 108 // 'extra' is the number of bytes to copy from a stream of fresh bytes, and |
(...skipping 110 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
217 old[lastpos + lenf - overlap + i]) score++; | 219 old[lastpos + lenf - overlap + i]) score++; |
218 if (newbuf[scan - lenb + i] == old[pos - lenb + i]) score--; | 220 if (newbuf[scan - lenb + i] == old[pos - lenb + i]) score--; |
219 if (score > Ss) { Ss = score; lens = i + 1; } | 221 if (score > Ss) { Ss = score; lens = i + 1; } |
220 } | 222 } |
221 | 223 |
222 lenf += lens - overlap; | 224 lenf += lens - overlap; |
223 lenb -= lens; | 225 lenb -= lens; |
224 }; | 226 }; |
225 | 227 |
226 for (int i = 0; i < lenf; i++) { | 228 for (int i = 0; i < lenf; i++) { |
227 uint8 diff_byte = newbuf[lastscan + i] - old[lastpos + i]; | 229 uint8_t diff_byte = newbuf[lastscan + i] - old[lastpos + i]; |
228 if (diff_byte) { | 230 if (diff_byte) { |
229 ++diff_bytes_nonzero; | 231 ++diff_bytes_nonzero; |
230 if (!diff_skips->WriteVarint32(pending_diff_zeros)) | 232 if (!diff_skips->WriteVarint32(pending_diff_zeros)) |
231 return MEM_ERROR; | 233 return MEM_ERROR; |
232 pending_diff_zeros = 0; | 234 pending_diff_zeros = 0; |
233 if (!diff_bytes->Write(&diff_byte, 1)) | 235 if (!diff_bytes->Write(&diff_byte, 1)) |
234 return MEM_ERROR; | 236 return MEM_ERROR; |
235 } else { | 237 } else { |
236 ++pending_diff_zeros; | 238 ++pending_diff_zeros; |
237 } | 239 } |
238 } | 240 } |
239 int gap = (scan - lenb) - (lastscan + lenf); | 241 int gap = (scan - lenb) - (lastscan + lenf); |
240 for (int i = 0; i < gap; i++) { | 242 for (int i = 0; i < gap; i++) { |
241 if (!extra_bytes->Write(&newbuf[lastscan + lenf + i], 1)) | 243 if (!extra_bytes->Write(&newbuf[lastscan + lenf + i], 1)) |
242 return MEM_ERROR; | 244 return MEM_ERROR; |
243 } | 245 } |
244 | 246 |
245 diff_bytes_length += lenf; | 247 diff_bytes_length += lenf; |
246 extra_bytes_length += gap; | 248 extra_bytes_length += gap; |
247 | 249 |
248 uint32 copy_count = lenf; | 250 uint32_t copy_count = lenf; |
249 uint32 extra_count = gap; | 251 uint32_t extra_count = gap; |
250 int32 seek_adjustment = ((pos - lenb) - (lastpos + lenf)); | 252 int32_t seek_adjustment = ((pos - lenb) - (lastpos + lenf)); |
251 | 253 |
252 if (!control_stream_copy_counts->WriteVarint32(copy_count) || | 254 if (!control_stream_copy_counts->WriteVarint32(copy_count) || |
253 !control_stream_extra_counts->WriteVarint32(extra_count) || | 255 !control_stream_extra_counts->WriteVarint32(extra_count) || |
254 !control_stream_seeks->WriteVarint32Signed(seek_adjustment)) { | 256 !control_stream_seeks->WriteVarint32Signed(seek_adjustment)) { |
255 return MEM_ERROR; | 257 return MEM_ERROR; |
256 } | 258 } |
257 | 259 |
258 ++control_length; | 260 ++control_length; |
259 #ifdef DEBUG_bsmedberg | 261 #ifdef DEBUG_bsmedberg |
260 VLOG(1) << StringPrintf("Writing a block: copy: %-8u extra: %-8u seek: " | 262 VLOG(1) << StringPrintf("Writing a block: copy: %-8u extra: %-8u seek: " |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
296 << " extra bytes: " << extra_bytes_length | 298 << " extra bytes: " << extra_bytes_length |
297 << "\nUncompressed bsdiff patch size " | 299 << "\nUncompressed bsdiff patch size " |
298 << patch_stream->Length() - initial_patch_stream_length | 300 << patch_stream->Length() - initial_patch_stream_length |
299 << "\nEnd bsdiff " | 301 << "\nEnd bsdiff " |
300 << (base::Time::Now() - start_bsdiff_time).InSecondsF(); | 302 << (base::Time::Now() - start_bsdiff_time).InSecondsF(); |
301 | 303 |
302 return OK; | 304 return OK; |
303 } | 305 } |
304 | 306 |
305 } // namespace courgette | 307 } // namespace courgette |
OLD | NEW |