Index: courgette/third_party/bsdiff_create.cc |
diff --git a/courgette/third_party/bsdiff_create.cc b/courgette/third_party/bsdiff_create.cc |
deleted file mode 100644 |
index 87b8ab4eca54b93710931f0eed926f4968f9e42e..0000000000000000000000000000000000000000 |
--- a/courgette/third_party/bsdiff_create.cc |
+++ /dev/null |
@@ -1,306 +0,0 @@ |
-/* |
- bsdiff.c -- Binary patch generator. |
- |
- Copyright 2003 Colin Percival |
- |
- For the terms under which this work may be distributed, please see |
- the adjoining file "LICENSE". |
- |
- ChangeLog: |
- 2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit |
- values throughout. |
- --Benjamin Smedberg <benjamin@smedbergs.us> |
- 2005-05-18 - Use the same CRC algorithm as bzip2, and leverage the CRC table |
- provided by libbz2. |
- --Darin Fisher <darin@meer.net> |
- 2007-11-14 - Changed to use Crc from Lzma library instead of Bzip library |
- --Rahul Kuchhal |
- 2009-03-31 - Change to use Streams. Added lots of comments. |
- --Stephen Adams <sra@chromium.org> |
- 2010-05-26 - Use a paged array for V and I. The address space may be too |
- fragmented for these big arrays to be contiguous. |
- --Stephen Adams <sra@chromium.org> |
- 2015-08-03 - Extract qsufsort portion to a separate file. |
- --Samuel Huang <huangs@chromium.org> |
- 2015-08-12 - Interface change to qsufsort search(). |
- --Samuel Huang <huangs@chromium.org> |
-*/ |
- |
-#include "courgette/third_party/bsdiff.h" |
- |
-#include <stddef.h> |
-#include <stdint.h> |
-#include <stdlib.h> |
-#include <algorithm> |
- |
-#include "base/logging.h" |
-#include "base/strings/string_util.h" |
-#include "base/time/time.h" |
- |
-#include "courgette/crc.h" |
-#include "courgette/streams.h" |
-#include "courgette/third_party/paged_array.h" |
-#include "courgette/third_party/qsufsort.h" |
- |
-namespace courgette { |
- |
-static CheckBool WriteHeader(SinkStream* stream, MBSPatchHeader* header) { |
- bool ok = stream->Write(header->tag, sizeof(header->tag)); |
- ok &= stream->WriteVarint32(header->slen); |
- ok &= stream->WriteVarint32(header->scrc32); |
- ok &= stream->WriteVarint32(header->dlen); |
- return ok; |
-} |
- |
-BSDiffStatus CreateBinaryPatch(SourceStream* old_stream, |
- SourceStream* new_stream, |
- SinkStream* patch_stream) |
-{ |
- base::Time start_bsdiff_time = base::Time::Now(); |
- VLOG(1) << "Start bsdiff"; |
- size_t initial_patch_stream_length = patch_stream->Length(); |
- |
- SinkStreamSet patch_streams; |
- SinkStream* control_stream_copy_counts = patch_streams.stream(0); |
- SinkStream* control_stream_extra_counts = patch_streams.stream(1); |
- SinkStream* control_stream_seeks = patch_streams.stream(2); |
- SinkStream* diff_skips = patch_streams.stream(3); |
- SinkStream* diff_bytes = patch_streams.stream(4); |
- SinkStream* extra_bytes = patch_streams.stream(5); |
- |
- const uint8_t* old = old_stream->Buffer(); |
- const int oldsize = static_cast<int>(old_stream->Remaining()); |
- |
- uint32_t pending_diff_zeros = 0; |
- |
- PagedArray<int> I; |
- PagedArray<int> V; |
- |
- if (!I.Allocate(oldsize + 1)) { |
- LOG(ERROR) << "Could not allocate I[], " << ((oldsize + 1) * sizeof(int)) |
- << " bytes"; |
- return MEM_ERROR; |
- } |
- |
- if (!V.Allocate(oldsize + 1)) { |
- LOG(ERROR) << "Could not allocate V[], " << ((oldsize + 1) * sizeof(int)) |
- << " bytes"; |
- return MEM_ERROR; |
- } |
- |
- base::Time q_start_time = base::Time::Now(); |
- qsuf::qsufsort<PagedArray<int>&>(I, V, old, oldsize); |
- VLOG(1) << " done qsufsort " |
- << (base::Time::Now() - q_start_time).InSecondsF(); |
- V.clear(); |
- |
- const uint8_t* newbuf = new_stream->Buffer(); |
- const int newsize = static_cast<int>(new_stream->Remaining()); |
- |
- int control_length = 0; |
- int diff_bytes_length = 0; |
- int diff_bytes_nonzero = 0; |
- int extra_bytes_length = 0; |
- |
- // The patch format is a sequence of triples <copy,extra,seek> where 'copy' is |
- // the number of bytes to copy from the old file (possibly with mistakes), |
- // 'extra' is the number of bytes to copy from a stream of fresh bytes, and |
- // 'seek' is an offset to move to the position to copy for the next triple. |
- // |
- // The invariant at the top of this loop is that we are committed to emitting |
- // a triple for the part of |newbuf| surrounding a 'seed' match near |
- // |lastscan|. We are searching for a second match that will be the 'seed' of |
- // the next triple. As we scan through |newbuf|, one of four things can |
- // happen at the current position |scan|: |
- // |
- // 1. We find a nice match that appears to be consistent with the current |
- // seed. Continue scanning. It is likely that this match will become |
- // part of the 'copy'. |
- // |
- // 2. We find match which does much better than extending the current seed |
- // old match. Emit a triple for the current seed and take this match as |
- // the new seed for a new triple. By 'much better' we remove 8 mismatched |
- // bytes by taking the new seed. |
- // |
- // 3. There is not a good match. Continue scanning. These bytes will likely |
- // become part of the 'extra'. |
- // |
- // 4. There is no match because we reached the end of the input, |newbuf|. |
- |
- // This is how the loop advances through the bytes of |newbuf|: |
- // |
- // ...012345678901234567890123456789... |
- // ssssssssss Seed at |lastscan| |
- // xxyyyxxyyxy |scan| forward, cases (3)(x) & (1)(y) |
- // mmmmmmmm New match will start new seed case (2). |
- // fffffffffffffff |lenf| = scan forward from |lastscan| |
- // bbbb |lenb| = scan back from new seed |scan|. |
- // ddddddddddddddd Emit diff bytes for the 'copy'. |
- // xx Emit extra bytes. |
- // ssssssssssss |lastscan = scan - lenb| is new seed. |
- // x Cases (1) and (3) .... |
- |
- |
- int lastscan = 0, lastpos = 0, lastoffset = 0; |
- |
- int scan = 0; |
- int match_length = 0; |
- |
- while (scan < newsize) { |
- int pos = 0; |
- int oldscore = 0; // Count of how many bytes of the current match at |scan| |
- // extend the match at |lastscan|. |
- |
- scan += match_length; |
- for (int scsc = scan; scan < newsize; ++scan) { |
- match_length = qsuf::search<PagedArray<int>&>( |
- I, old, oldsize, newbuf + scan, newsize - scan, &pos); |
- |
- for ( ; scsc < scan + match_length ; scsc++) |
- if ((scsc + lastoffset < oldsize) && |
- (old[scsc + lastoffset] == newbuf[scsc])) |
- oldscore++; |
- |
- if ((match_length == oldscore) && (match_length != 0)) |
- break; // Good continuing match, case (1) |
- if (match_length > oldscore + 8) |
- break; // New seed match, case (2) |
- |
- if ((scan + lastoffset < oldsize) && |
- (old[scan + lastoffset] == newbuf[scan])) |
- oldscore--; |
- // Case (3) continues in this loop until we fall out of the loop (4). |
- } |
- |
- if ((match_length != oldscore) || (scan == newsize)) { // Cases (2) and (4) |
- // This next chunk of code finds the boundary between the bytes to be |
- // copied as part of the current triple, and the bytes to be copied as |
- // part of the next triple. The |lastscan| match is extended forwards as |
- // far as possible provided doing to does not add too many mistakes. The |
- // |scan| match is extended backwards in a similar way. |
- |
- // Extend the current match (if any) backwards. |lenb| is the maximal |
- // extension for which less than half the byte positions in the extension |
- // are wrong. |
- int lenb = 0; |
- if (scan < newsize) { // i.e. not case (4); there is a match to extend. |
- int score = 0, Sb = 0; |
- for (int i = 1; (scan >= lastscan + i) && (pos >= i); i++) { |
- if (old[pos - i] == newbuf[scan - i]) score++; |
- if (score*2 - i > Sb*2 - lenb) { Sb = score; lenb = i; } |
- } |
- } |
- |
- // Extend the lastscan match forward; |lenf| is the maximal extension for |
- // which less than half of the byte positions in entire lastscan match are |
- // wrong. There is a subtle point here: |lastscan| points to before the |
- // seed match by |lenb| bytes from the previous iteration. This is why |
- // the loop measures the total number of mistakes in the the match, not |
- // just the from the match. |
- int lenf = 0; |
- { |
- int score = 0, Sf = 0; |
- for (int i = 0; (lastscan + i < scan) && (lastpos + i < oldsize); ) { |
- if (old[lastpos + i] == newbuf[lastscan + i]) score++; |
- i++; |
- if (score*2 - i > Sf*2 - lenf) { Sf = score; lenf = i; } |
- } |
- } |
- |
- // If the extended scans overlap, pick a position in the overlap region |
- // that maximizes the exact matching bytes. |
- if (lastscan + lenf > scan - lenb) { |
- int overlap = (lastscan + lenf) - (scan - lenb); |
- int score = 0; |
- int Ss = 0, lens = 0; |
- for (int i = 0; i < overlap; i++) { |
- if (newbuf[lastscan + lenf - overlap + i] == |
- old[lastpos + lenf - overlap + i]) score++; |
- if (newbuf[scan - lenb + i] == old[pos - lenb + i]) score--; |
- if (score > Ss) { Ss = score; lens = i + 1; } |
- } |
- |
- lenf += lens - overlap; |
- lenb -= lens; |
- }; |
- |
- for (int i = 0; i < lenf; i++) { |
- uint8_t diff_byte = newbuf[lastscan + i] - old[lastpos + i]; |
- if (diff_byte) { |
- ++diff_bytes_nonzero; |
- if (!diff_skips->WriteVarint32(pending_diff_zeros)) |
- return MEM_ERROR; |
- pending_diff_zeros = 0; |
- if (!diff_bytes->Write(&diff_byte, 1)) |
- return MEM_ERROR; |
- } else { |
- ++pending_diff_zeros; |
- } |
- } |
- int gap = (scan - lenb) - (lastscan + lenf); |
- for (int i = 0; i < gap; i++) { |
- if (!extra_bytes->Write(&newbuf[lastscan + lenf + i], 1)) |
- return MEM_ERROR; |
- } |
- |
- diff_bytes_length += lenf; |
- extra_bytes_length += gap; |
- |
- uint32_t copy_count = lenf; |
- uint32_t extra_count = gap; |
- int32_t seek_adjustment = ((pos - lenb) - (lastpos + lenf)); |
- |
- if (!control_stream_copy_counts->WriteVarint32(copy_count) || |
- !control_stream_extra_counts->WriteVarint32(extra_count) || |
- !control_stream_seeks->WriteVarint32Signed(seek_adjustment)) { |
- return MEM_ERROR; |
- } |
- |
- ++control_length; |
-#ifdef DEBUG_bsmedberg |
- VLOG(1) << StringPrintf("Writing a block: copy: %-8u extra: %-8u seek: " |
- "%+-9d", copy_count, extra_count, |
- seek_adjustment); |
-#endif |
- |
- lastscan = scan - lenb; // Include the backward extension in seed. |
- lastpos = pos - lenb; // ditto. |
- lastoffset = lastpos - lastscan; |
- } |
- } |
- |
- if (!diff_skips->WriteVarint32(pending_diff_zeros)) |
- return MEM_ERROR; |
- |
- I.clear(); |
- |
- MBSPatchHeader header; |
- // The string will have a null terminator that we don't use, hence '-1'. |
- static_assert(sizeof(MBS_PATCH_HEADER_TAG) - 1 == sizeof(header.tag), |
- "MBS_PATCH_HEADER_TAG must match header field size"); |
- memcpy(header.tag, MBS_PATCH_HEADER_TAG, sizeof(header.tag)); |
- header.slen = oldsize; |
- header.scrc32 = CalculateCrc(old, oldsize); |
- header.dlen = newsize; |
- |
- if (!WriteHeader(patch_stream, &header)) |
- return MEM_ERROR; |
- |
- size_t diff_skips_length = diff_skips->Length(); |
- if (!patch_streams.CopyTo(patch_stream)) |
- return MEM_ERROR; |
- |
- VLOG(1) << "Control tuples: " << control_length |
- << " copy bytes: " << diff_bytes_length |
- << " mistakes: " << diff_bytes_nonzero |
- << " (skips: " << diff_skips_length << ")" |
- << " extra bytes: " << extra_bytes_length |
- << "\nUncompressed bsdiff patch size " |
- << patch_stream->Length() - initial_patch_stream_length |
- << "\nEnd bsdiff " |
- << (base::Time::Now() - start_bsdiff_time).InSecondsF(); |
- |
- return OK; |
-} |
- |
-} // namespace courgette |