[Zucchini] Fix underflow / overflow for extended forward-projection.

Forward-projection is how Zucchini uses the equivalence map to create
estimated "new" targets from "old" targets. Extended forward-projection
is defined to transform non-covered offsets: Given an offset, it finds
the equivalence unit with nearest "old" block, then applies the
"old"-to-"new" displacement to the offset. However, this makes it
possible to map an "old" offset to an offset outside "new" image.

Another issue is that Zucchini uses "dangling targets" that use "fake
offsets" outside the image file to represent .bss data. These targets
also undergo forward-projection, and should be properly handled.

This CL fixes the existing behavior, where underflow / overflow go
unchecked (although these values are rendered benign downstream, since
the nearest actual "new" target is found). The updated extended
forward-projection specifies:
- For "old" targets with real offsets: Take nearest equivalence unit,
  clamp output to be inside [0, "new" image size).
- For "old" dangling targets with fake offsets: Use difference in
  file size as displacement.

The main impact w.r.t. patch is to reduce possible variance in patch
sizes -- dangling targets are now handled better. Extensive unit tests
are also added.

Bug: 832572
Change-Id: I41fea175e4c13585d14a97a712a191afc2fcc6d6
Reviewed-on: https://chromium-review.googlesource.com/1111467
Reviewed-by: Samuel Huang <huangs@chromium.org>
Reviewed-by: Greg Thompson <grt@chromium.org>
Commit-Queue: Samuel Huang <huangs@chromium.org>
Cr-Commit-Position: refs/heads/master@{#570401}
NOKEYCHECK=True
GitOrigin-RevId: ad7a5c086f00de62997714b84d6d6b5817ccc9d8

1 files changed, 33 insertions, 9 deletions

diff --git a/equivalence_map.h b/equivalence_map.h
index 91b215c..2ae8801 100644
--- a/equivalence_map.h
+++ b/equivalence_map.h
@@ -84,26 +84,46 @@ class OffsetMapper {
  public:
   using const_iterator = std::vector<Equivalence>::const_iterator;
 
-  // Constructors for various data sources.
+  // Constructors for various data sources. "Old" and "new" image sizes are
+  // needed for bounds checks and to handle dangling targets.
   // - From a list of |equivalences|, already sorted (by |src_offset|) and
   //   pruned, useful for tests.
-  explicit OffsetMapper(std::vector<Equivalence>&& equivalences);
+  OffsetMapper(std::vector<Equivalence>&& equivalences,
+               size_t old_image_size,
+               size_t new_image_size);
   // - From a generator, useful for Zucchini-apply.
-  explicit OffsetMapper(EquivalenceSource&& equivalence_source);
+  OffsetMapper(EquivalenceSource&& equivalence_source,
+               size_t old_image_size,
+               size_t new_image_size);
   // - From an EquivalenceMap that needs to be processed, useful for
   //   Zucchini-gen.
-  explicit OffsetMapper(const EquivalenceMap& equivalence_map);
+  OffsetMapper(const EquivalenceMap& equivalence_map,
+               size_t old_image_size,
+               size_t new_image_size);
   ~OffsetMapper();
 
   size_t size() const { return equivalences_.size(); }
   const_iterator begin() const { return equivalences_.begin(); }
   const_iterator end() const { return equivalences_.end(); }
 
+  // Returns naive extended forward-projection of "old" |offset| that follows
+  // |eq|'s delta. |eq| needs not cover |offset|.
+  // - Averts underflow / overflow by clamping to |[0, new_image_size_)|.
+  // - However, |offset| is *not* restricted to |[0, old_image_size_)|; the
+  //   caller must to make the check (hence "naive").
+  offset_t NaiveExtendedForwardProject(const Equivalence& unit,
+                                       offset_t offset) const;
+
   // Returns an offset in |new_image| corresponding to |offset| in |old_image|.
-  // If |offset| is not part of an equivalence, the equivalence nearest to
-  // |offset| is used as if it contained |offset|. This assumes |equivalences_|
-  // is not empty.
-  offset_t ForwardProject(offset_t offset) const;
+  // Assumes |equivalences_| to be non-empty. Cases:
+  // - If |offset| is covered (i.e., in an "old" block), then use the delta of
+  //   the (unique) equivalence unit that covers |offset|.
+  // - If |offset| is non-covered, but in |[0, old_image_size_)|, then find the
+  //   nearest "old" block, use its delta, and avert underflow / overflow by
+  //   clamping the result to |[0, new_image_size_)|.
+  // - If |offset| is >= |new_image_size_| (a "fake offset"), then use
+  //   |new_image_size_ - old_image_size_| as the delta.
+  offset_t ExtendedForwardProject(offset_t offset) const;
 
   // Given sorted |offsets|, applies a projection in-place of all offsets that
   // are part of a pruned equivalence from |old_image| to |new_image|. Other
@@ -123,7 +143,11 @@ class OffsetMapper {
       std::vector<Equivalence>* equivalences);
 
  private:
-  std::vector<Equivalence> equivalences_;
+  // |equivalences_| is pruned, i.e., no "old" blocks overlap (and no "new"
+  // block overlaps). Also, it is sorted by "old" offsets.
+  std::vector<Equivalence> equivalences_;  // P
+  const size_t old_image_size_;
+  const size_t new_image_size_;
 };
 
 // Container of equivalences between |old_image_index| and |new_image_index|,