Implement Play Store's "endsley" patching format generator.
Android's Play Store uses, among other options, a bsdiff patch format
similar to Matthew Endsley's bsdiff implementation. The main difference
is that Play Store's version doesn't do any compression in the patch
format itself, but instead the compression is handled at a higher
level.
This CL introduces a new PatchWriterInterface derived class to write to
this (uncompressed) format.
See https://github.com/mendsley/bsdiff for the original implementation
of this format. See also Google's APK patch size estimator for more
information on the file-by-file format used by Play Store:
https://github.com/googlesamples/apk-patch-size-estimator
Bug: 67458097
Test: Added simple unittests for the generated files.
Change-Id: I3b048abf2220e2cb3af0a95e27efe1c0f241046a
diff --git a/endsley_patch_writer.cc b/endsley_patch_writer.cc
new file mode 100644
index 0000000..4e4a3f1
--- /dev/null
+++ b/endsley_patch_writer.cc
@@ -0,0 +1,178 @@
+// Copyright 2017 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "bsdiff/endsley_patch_writer.h"
+
+#include <string.h>
+
+#include <algorithm>
+
+#include "bsdiff/logging.h"
+
+using std::endl;
+
+namespace {
+
+constexpr uint8_t kEndsleyMagicHeader[] = "ENDSLEY/BSDIFF43";
+
+void EncodeInt64(int64_t x, uint8_t* buf) {
+ uint64_t y = x < 0 ? (1ULL << 63ULL) - x : x;
+ for (int i = 0; i < 8; ++i) {
+ buf[i] = y & 0xff;
+ y /= 256;
+ }
+}
+
+// The minimum size that we would consider flushing out.
+constexpr size_t kMinimumFlushSize = 1024 * 1024; // 1 MiB
+
+} // namespace
+
+namespace bsdiff {
+
+bool EndsleyPatchWriter::Init(size_t new_size) {
+ // The patch is uncompressed and it will need exactly:
+ // new_size + 24 * len(control_entries) + sizeof(header)
+ // We don't know the length of the control entries yet, but we can reserve
+ // enough space to hold at least |new_size|.
+ patch_->clear();
+ patch_->reserve(new_size);
+
+ // Header is the magic followed by the new length.
+ uint8_t header[24];
+ memcpy(header, kEndsleyMagicHeader, 16);
+ EncodeInt64(new_size, header + 16);
+ EmitBuffer(header, sizeof(header));
+ return true;
+}
+
+bool EndsleyPatchWriter::WriteDiffStream(const uint8_t* data, size_t size) {
+ if (!size)
+ return true;
+ // Speed-up the common case where the diff stream data is added right after
+ // the control entry that refers to it.
+ if (control_.empty() && pending_diff_ >= size) {
+ pending_diff_ -= size;
+ EmitBuffer(data, size);
+ return true;
+ }
+
+ diff_data_.insert(diff_data_.end(), data, data + size);
+ return true;
+}
+
+bool EndsleyPatchWriter::WriteExtraStream(const uint8_t* data, size_t size) {
+ if (!size)
+ return true;
+ // Speed-up the common case where the extra stream data is added right after
+ // the diff stream data and the control entry that refers to it. Note that
+ // the diff data comes first so we need to make sure it is all out.
+ if (control_.empty() && !pending_diff_ && pending_extra_ >= size) {
+ pending_extra_ -= size;
+ EmitBuffer(data, size);
+ return true;
+ }
+
+ extra_data_.insert(extra_data_.end(), data, data + size);
+ return true;
+}
+
+bool EndsleyPatchWriter::AddControlEntry(const ControlEntry& entry) {
+ // Speed-up the common case where the control entry is added when there's
+ // nothing else pending.
+ if (control_.empty() && diff_data_.empty() && extra_data_.empty() &&
+ !pending_diff_ && !pending_extra_) {
+ pending_diff_ = entry.diff_size;
+ pending_extra_ = entry.extra_size;
+ EmitControlEntry(entry);
+ return true;
+ }
+
+ control_.push_back(entry);
+ pending_control_data_ += entry.diff_size + entry.extra_size;
+
+ // Check whether it is worth Flushing the entries now that the we have more
+ // control entries. We need control entries to write enough output data, and
+ // we need that output data to be at least 50% of the available diff and extra
+ // data. This last requirement is to reduce the overhead of removing the
+ // flushed data.
+ if (pending_control_data_ > kMinimumFlushSize &&
+ (diff_data_.size() + extra_data_.size()) / 2 <= pending_control_data_) {
+ Flush();
+ }
+
+ return true;
+}
+
+bool EndsleyPatchWriter::Close() {
+ // Flush any pending data.
+ Flush();
+
+ if (pending_diff_ || pending_extra_ || !control_.empty()) {
+ LOG(ERROR) << "Insufficient data sent to diff/extra streams" << endl;
+ return false;
+ }
+
+ if (!diff_data_.empty() || !extra_data_.empty()) {
+ LOG(ERROR) << "Pending data to diff/extra not flushed out on Close()"
+ << endl;
+ return false;
+ }
+ return true;
+}
+
+void EndsleyPatchWriter::EmitControlEntry(const ControlEntry& entry) {
+ // Generate the 24 byte control entry.
+ uint8_t buf[24];
+ EncodeInt64(entry.diff_size, buf);
+ EncodeInt64(entry.extra_size, buf + 8);
+ EncodeInt64(entry.offset_increment, buf + 16);
+ EmitBuffer(buf, sizeof(buf));
+}
+
+void EndsleyPatchWriter::EmitBuffer(const uint8_t* data, size_t size) {
+ patch_->insert(patch_->end(), data, data + size);
+}
+
+void EndsleyPatchWriter::Flush() {
+ size_t used_diff = 0;
+ size_t used_extra = 0;
+ size_t used_control = 0;
+ do {
+ if (!pending_diff_ && !pending_extra_ && used_control < control_.size()) {
+ // We can emit a control entry in these conditions.
+ const ControlEntry& entry = control_[used_control];
+ used_control++;
+
+ pending_diff_ = entry.diff_size;
+ pending_extra_ = entry.extra_size;
+ pending_control_data_ -= entry.extra_size + entry.diff_size;
+ EmitControlEntry(entry);
+ }
+
+ if (pending_diff_) {
+ size_t diff_size = std::min(diff_data_.size() - used_diff, pending_diff_);
+ EmitBuffer(diff_data_.data() + used_diff, diff_size);
+ pending_diff_ -= diff_size;
+ used_diff += diff_size;
+ }
+
+ if (!pending_diff_ && pending_extra_) {
+ size_t extra_size =
+ std::min(extra_data_.size() - used_extra, pending_extra_);
+ EmitBuffer(extra_data_.data() + used_extra, extra_size);
+ pending_extra_ -= extra_size;
+ used_extra += extra_size;
+ }
+ } while (!pending_diff_ && !pending_extra_ && used_control < control_.size());
+
+ if (used_diff)
+ diff_data_.erase(diff_data_.begin(), diff_data_.begin() + used_diff);
+ if (used_extra)
+ extra_data_.erase(extra_data_.begin(), extra_data_.begin() + used_extra);
+ if (used_control)
+ control_.erase(control_.begin(), control_.begin() + used_control);
+}
+
+} // namespace bsdiff