| 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 |