[Zucchini] Introduce ReferenceBytesMixer.

Some architectures (e.g., ARM) have references that mix operation bits
with payload bits. ReferenceBytesMixer is a class to isloate operation
bit changes to Layer 1 patching.

This CL introduces only the stub for ReferenceBytesMixer (the remainder
would require ARM support). Having this now brings Zucchini-gen closer
to trunk code, and sets up upcoming work for a mock disassembler.

Change-Id: I2e1aa56bf265e4b61b33d323be2ed9a456e14f3b
Reviewed-on: https://chromium-review.googlesource.com/1021650
Commit-Queue: Samuel Huang <huangs@chromium.org>
Reviewed-by: Samuel Huang <huangs@chromium.org>
Reviewed-by: Greg Thompson <grt@chromium.org>
Cr-Commit-Position: refs/heads/master@{#552373}
NOKEYCHECK=True
GitOrigin-RevId: fdb4806d8d03c52ffe4ca7b14076f483384eedfb

5 files changed, 182 insertions, 11 deletions

diff --git a/BUILD.gn b/BUILD.gn
index 6adbc9e..58db302 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -50,6 +50,8 @@ static_library("zucchini_lib") {
     "patch_utils.h",
     "patch_writer.cc",
     "patch_writer.h",
+    "reference_bytes_mixer.cc",
+    "reference_bytes_mixer.h",
     "reference_set.cc",
     "reference_set.h",
     "rel32_finder.cc",
diff --git a/reference_bytes_mixer.cc b/reference_bytes_mixer.cc
new file mode 100644
index 0000000..c0d5ca3
--- /dev/null
+++ b/reference_bytes_mixer.cc
@@ -0,0 +1,48 @@
+// Copyright 2018 The Chromium 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 "components/zucchini/reference_bytes_mixer.h"
+
+#include "base/logging.h"
+#include "components/zucchini/disassembler.h"
+
+namespace zucchini {
+
+/******** ReferenceBytesMixer ********/
+
+// Default implementation is a stub, i.e., for architectures whose references
+// have operation bits and payload bits stored in separate bytes. So during
+// patch application, payload bits are copied for matched blocks, ignored by
+// bytewise corrections, and fixed by reference target corrections.
+ReferenceBytesMixer::ReferenceBytesMixer() {}
+
+ReferenceBytesMixer::~ReferenceBytesMixer() = default;
+
+// static.
+std::unique_ptr<ReferenceBytesMixer> ReferenceBytesMixer::Create(
+    const Disassembler& src_dis,
+    const Disassembler& dst_dis) {
+  ExecutableType exe_type = src_dis.GetExeType();
+  DCHECK_EQ(exe_type, dst_dis.GetExeType());
+  // TODO(huangs): Add ARM handling code when ARM is ready.
+  return std::make_unique<ReferenceBytesMixer>();
+}
+
+// Stub implementation.
+int ReferenceBytesMixer::NumBytes(uint8_t type) const {
+  return 0;
+}
+
+// Base class implementation is a stub that should not be called.
+ConstBufferView ReferenceBytesMixer::Mix(
+    uint8_t type,
+    ConstBufferView::const_iterator old_base,
+    offset_t old_offset,
+    ConstBufferView::const_iterator new_base,
+    offset_t new_offset) {
+  NOTREACHED() << "Stub.";
+  return ConstBufferView();
+}
+
+}  // namespace zucchini
diff --git a/reference_bytes_mixer.h b/reference_bytes_mixer.h
new file mode 100644
index 0000000..9bc8f2d
--- /dev/null
+++ b/reference_bytes_mixer.h
@@ -0,0 +1,91 @@
+// Copyright 2018 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef COMPONENTS_ZUCCHINI_REFERENCE_BYTES_MIXER_H_
+#define COMPONENTS_ZUCCHINI_REFERENCE_BYTES_MIXER_H_
+
+#include <stdint.h>
+
+#include <memory>
+#include <vector>
+
+#include "base/macros.h"
+#include "components/zucchini/buffer_view.h"
+#include "components/zucchini/image_utils.h"
+
+namespace zucchini {
+
+class Disassembler;
+
+// References encoding may be quite complex in some architectures (e.g., ARM),
+// requiring bit-level manipulation. In general, bits in a reference body fall
+// under 2 categories:
+// - Operation bits: Instruction op code, conditionals, or structural data.
+// - Payload bits: Actual target data of the reference. These may be absolute,
+//   or be displacements relative to instruction pointer / program counter.
+// During patch application,
+//   Old reference bytes = {old operation, old payload},
+// is transformed to
+//   New reference bytes = {new operation, new payload}.
+// New image bytes are written by three sources:
+//   (1) Direct copy from old image to new image for matched blocks.
+//   (2) Bytewise diff correction.
+//   (3) Dedicated reference target correction.
+//
+// For references whose operation and payload bits are stored in easily
+// separable bytes (e.g., rel32 reference in X86), (2) can exclude payload bits.
+// So during patch application, (1) naively copies everything, (2) fixes
+// operation bytes only, and (3) fixes payload bytes only.
+//
+// For architectures with references whose operation and payload bits may mix
+// within shared bytes (e.g., ARM rel32), a dilemma arises:
+// - (2) cannot ignores shared bytes, since otherwise new operation bits not
+//   properly transfer.
+// - Having (2) always overwrite these bytes would reduce the benefits of
+//   reference correction, since references are likely to change.
+//
+// Our solution applies a hybrid approach: For each matching old / new reference
+// pair, define:
+//   Mixed reference bytes = {new operation, old payload},
+//
+// During patch generation, we compute bytewise correction from old reference
+// bytes to the mixed reference bytes. So during patch application, (2) only
+// corrects operation bit changes (and skips if they don't change), and (3)
+// overwrites old payload bits to new payload bits.
+
+// A base class for (stateful) mixed reference byte generation. This base class
+// serves as a stub. Architectures whose references store operation bits and
+// payload bits can share common bytes (e.g., ARM rel32) should override this.
+class ReferenceBytesMixer {
+ public:
+  ReferenceBytesMixer();
+  virtual ~ReferenceBytesMixer();
+
+  // Returns a new ReferenceBytesMixer instance that's owned by the caller.
+  static std::unique_ptr<ReferenceBytesMixer> Create(
+      const Disassembler& src_dis,
+      const Disassembler& dst_dis);
+
+  // Returns the number of bytes that need to be mixed for references with given
+  // |type|. Returns 0 if no mixing is required.
+  virtual int NumBytes(uint8_t type) const;
+
+  // Computes mixed reference bytes by combining (a) "payload bits" from an
+  // "old" reference of |type| at |old_base[old_offset]| with (b) "operation
+  // bits" from a "new" reference of |type| at |new_base[new_offset]|. Returns
+  // the result as ConstBufferView, which is valid only until the next call to
+  // Mix().
+  virtual ConstBufferView Mix(uint8_t type,
+                              ConstBufferView::const_iterator old_base,
+                              offset_t old_offset,
+                              ConstBufferView::const_iterator new_base,
+                              offset_t new_offset);
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(ReferenceBytesMixer);
+};
+
+}  // namespace zucchini
+
+#endif  // COMPONENTS_ZUCCHINI_REFERENCE_BYTES_MIXER_H_
diff --git a/zucchini_gen.cc b/zucchini_gen.cc
index af7c7dd..e88d37b 100644
--- a/zucchini_gen.cc
+++ b/zucchini_gen.cc
@@ -22,6 +22,7 @@
 #include "components/zucchini/heuristic_ensemble_matcher.h"
 #include "components/zucchini/image_index.h"
 #include "components/zucchini/patch_writer.h"
+#include "components/zucchini/reference_bytes_mixer.h"
 #include "components/zucchini/suffix_array.h"
 #include "components/zucchini/targets_affinity.h"
 
@@ -120,6 +121,7 @@ bool GenerateRawDelta(ConstBufferView old_image,
                       ConstBufferView new_image,
                       const EquivalenceMap& equivalence_map,
                       const ImageIndex& new_image_index,
+                      ReferenceBytesMixer* reference_bytes_mixer,
                       PatchElementWriter* patch_writer) {
   RawDeltaSink raw_delta_sink;
 
@@ -130,14 +132,37 @@ bool GenerateRawDelta(ConstBufferView old_image,
     Equivalence equivalence = candidate.eq;
     // For each bytewise delta from |old_image| to |new_image|, compute "copy
     // offset" and pass it along with delta to the sink.
-    for (offset_t i = 0; i < equivalence.length; ++i) {
-      if (new_image_index.IsReference(equivalence.dst_offset + i))
-        continue;  // Skip references since they're handled elsewhere.
-
-      int8_t diff = new_image[equivalence.dst_offset + i] -
-                    old_image[equivalence.src_offset + i];
-      if (diff)
-        raw_delta_sink.PutNext({base_copy_offset + i, diff});
+    for (offset_t i = 0; i < equivalence.length;) {
+      if (new_image_index.IsReference(equivalence.dst_offset + i)) {
+        DCHECK(new_image_index.IsToken(equivalence.dst_offset + i));
+        TypeTag type_tag =
+            new_image_index.LookupType(equivalence.dst_offset + i);
+
+        // Reference delta has its own flow. On some architectures (e.g., x86)
+        // this does not involve raw delta, so we skip. On other architectures
+        // (e.g., ARM) references are mixed with other bits that may change, so
+        // we need to "mix" data and store some changed bits into raw delta.
+        int num_bytes = reference_bytes_mixer->NumBytes(type_tag.value());
+        if (num_bytes) {
+          ConstBufferView mixed_ref_bytes = reference_bytes_mixer->Mix(
+              type_tag.value(), old_image.begin(), equivalence.src_offset + i,
+              new_image.begin(), equivalence.dst_offset + i);
+          for (int j = 0; j < num_bytes; ++j) {
+            int8_t diff =
+                mixed_ref_bytes[j] - old_image[equivalence.src_offset + i + j];
+            if (diff)
+              raw_delta_sink.PutNext({base_copy_offset + i + j, diff});
+          }
+        }
+        i += new_image_index.refs(type_tag).width();
+        DCHECK_LE(i, equivalence.length);
+      } else {
+        int8_t diff = new_image[equivalence.dst_offset + i] -
+                      old_image[equivalence.src_offset + i];
+        if (diff)
+          raw_delta_sink.PutNext({base_copy_offset + i, diff});
+        ++i;
+      }
     }
     base_copy_offset += equivalence.length;
   }
@@ -225,10 +250,12 @@ bool GenerateRawElement(const std::vector<offset_t>& old_sa,
                      kMinEquivalenceSimilarity);
 
   patch_writer->SetReferenceDeltaSink({});
+
+  ReferenceBytesMixer no_op_bytes_mixer;
   return GenerateEquivalencesAndExtraData(new_image, equivalences,
                                           patch_writer) &&
          GenerateRawDelta(old_image, new_image, equivalences, new_image_index,
-                          patch_writer);
+                          &no_op_bytes_mixer, patch_writer);
 }
 
 bool GenerateExecutableElement(ExecutableType exe_type,
@@ -282,11 +309,12 @@ bool GenerateExecutableElement(ExecutableType exe_type,
     }
   }
   patch_writer->SetReferenceDeltaSink(std::move(reference_delta_sink));
-
+  std::unique_ptr<ReferenceBytesMixer> reference_bytes_mixer =
+      ReferenceBytesMixer::Create(*old_disasm, *new_disasm);
   return GenerateEquivalencesAndExtraData(new_image, equivalences,
                                           patch_writer) &&
          GenerateRawDelta(old_image, new_image, equivalences, new_image_index,
-                          patch_writer);
+                          reference_bytes_mixer.get(), patch_writer);
 }
 
 /******** Exported Functions ********/
diff --git a/zucchini_gen.h b/zucchini_gen.h
index a0f3630..17f1fd4 100644
--- a/zucchini_gen.h
+++ b/zucchini_gen.h
@@ -18,6 +18,7 @@ class EquivalenceMap;
 class OffsetMapper;
 class ImageIndex;
 class PatchElementWriter;
+class ReferenceBytesMixer;
 class ReferenceDeltaSink;
 class ReferenceSet;
 class TargetPool;
@@ -48,6 +49,7 @@ bool GenerateRawDelta(ConstBufferView old_image,
                       ConstBufferView new_image,
                       const EquivalenceMap& equivalence_map,
                       const ImageIndex& new_image_index,
+                      ReferenceBytesMixer* reference_bytes_mixer,
                       PatchElementWriter* patch_writer);
 
 // Writes reference delta between references from |old_refs| and from