image_utils.h 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275
  1. // Copyright 2017 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef COMPONENTS_ZUCCHINI_IMAGE_UTILS_H_
  5. #define COMPONENTS_ZUCCHINI_IMAGE_UTILS_H_
  6. #include <stddef.h>
  7. #include <stdint.h>
  8. #include <string>
  9. #include "base/format_macros.h"
  10. #include "base/numerics/safe_conversions.h"
  11. #include "base/strings/stringprintf.h"
  12. #include "components/zucchini/buffer_view.h"
  13. #include "components/zucchini/typed_value.h"
  14. #include "third_party/abseil-cpp/absl/types/optional.h"
  15. namespace zucchini {
  16. // offset_t is used to describe an offset in an image.
  17. // Files bigger than 4GB are not supported.
  18. using offset_t = uint32_t;
  19. // Divide by 2 since label marking uses the most significant bit.
  20. constexpr offset_t kOffsetBound = static_cast<offset_t>(-1) / 2;
  21. // Use 0xFFFFFFF*E*, since 0xFFFFFFF*F* is a sentinel value for Dex references.
  22. constexpr offset_t kInvalidOffset = static_cast<offset_t>(-2);
  23. // key_t is used to identify an offset in a table.
  24. using key_t = uint32_t;
  25. enum Bitness : uint8_t {
  26. // The numerical values are intended to simplify WidthOf() below.
  27. kBit32 = 4,
  28. kBit64 = 8
  29. };
  30. inline uint32_t WidthOf(Bitness bitness) {
  31. return static_cast<uint32_t>(bitness);
  32. }
  33. // Used to uniquely identify a reference type.
  34. // Strongly typed objects are used to avoid ambiguitees with PoolTag.
  35. struct TypeTag : public TypedValue<TypeTag, uint8_t> {
  36. // inheriting constructor:
  37. using TypedValue<TypeTag, uint8_t>::TypedValue;
  38. };
  39. // Used to uniquely identify a pool.
  40. struct PoolTag : public TypedValue<PoolTag, uint8_t> {
  41. // inheriting constructor:
  42. using TypedValue<PoolTag, uint8_t>::TypedValue;
  43. };
  44. constexpr TypeTag kNoTypeTag(0xFF); // Typically used to identify raw data.
  45. constexpr PoolTag kNoPoolTag(0xFF);
  46. // Specification of references in an image file.
  47. struct ReferenceTypeTraits {
  48. constexpr ReferenceTypeTraits(offset_t width_in,
  49. TypeTag type_tag_in,
  50. PoolTag pool_tag_in)
  51. : width(width_in), type_tag(type_tag_in), pool_tag(pool_tag_in) {}
  52. // |width| specifies number of bytes covered by the reference's binary
  53. // encoding.
  54. const offset_t width;
  55. // |type_tag| identifies the reference type being described.
  56. const TypeTag type_tag;
  57. // |pool_tag| identifies the pool this type belongs to.
  58. const PoolTag pool_tag;
  59. };
  60. // There is no need to store |type| because references of the same type are
  61. // always aggregated into the same container, and so during iteration we'd have
  62. // |type| already.
  63. struct Reference {
  64. offset_t location;
  65. offset_t target;
  66. };
  67. inline bool operator==(const Reference& a, const Reference& b) {
  68. return a.location == b.location && a.target == b.target;
  69. }
  70. // Interface for extracting References through member function GetNext().
  71. // This is used by Disassemblers to extract references from an image file.
  72. // Typically, a Reader lazily extracts values and does not hold any storage.
  73. class ReferenceReader {
  74. public:
  75. virtual ~ReferenceReader() = default;
  76. // Returns the next available Reference, or nullopt_t if exhausted.
  77. // Extracted References must be ordered by their location in the image.
  78. virtual absl::optional<Reference> GetNext() = 0;
  79. };
  80. // Interface for writing References through member function
  81. // PutNext(reference). This is used by Disassemblers to write new References
  82. // in the image file.
  83. class ReferenceWriter {
  84. public:
  85. virtual ~ReferenceWriter() = default;
  86. // Writes |reference| in the underlying image file. This operation always
  87. // succeeds.
  88. virtual void PutNext(Reference reference) = 0;
  89. };
  90. // References encoding may be quite complex in some architectures (e.g., ARM),
  91. // requiring bit-level manipulation. In general, bits in a reference body fall
  92. // under 2 categories:
  93. // * Operation bits: Instruction op code, conditionals, or structural data.
  94. // * Payload bits: Actual target data of the reference. These may be absolute,
  95. // or be displacements relative to instruction pointer / program counter.
  96. // During patch application,
  97. // Old reference bytes = {old operation, old payload},
  98. // is transformed to
  99. // New reference bytes = {new operation, new payload}.
  100. // New image bytes are written by three sources:
  101. // (1) Direct copy from old image to new image for matched blocks.
  102. // (2) Bytewise diff correction.
  103. // (3) Dedicated reference target correction.
  104. //
  105. // For references whose operation and payload bits are stored in easily
  106. // separable bytes (e.g., rel32 reference in X86), (2) can exclude payload bits.
  107. // So during patch application, (1) naively copies everything, (2) fixes
  108. // operation bytes only, and (3) fixes payload bytes only.
  109. //
  110. // For architectures with references whose operation and payload bits may mix
  111. // within shared bytes (e.g., ARM rel32), a dilemma arises:
  112. // * (2) cannot ignores shared bytes, since otherwise new operation bits would
  113. // not properly transfer.
  114. // * Having (2) always overwrite these bytes would reduce the benefits of
  115. // reference correction, since references are likely to change.
  116. //
  117. // Our solution applies a hybrid approach: For each matching old / new reference
  118. // pair, define:
  119. // Mixed reference bytes = {new operation, old payload},
  120. //
  121. // During patch generation, we compute bytewise correction from old reference
  122. // bytes to the mixed reference bytes. So during patch application, (2) only
  123. // corrects operation bit changes (and skips if they don't change), and (3)
  124. // overwrites old payload bits to new payload bits.
  125. // Interface for mixed reference byte generation. This base class
  126. // serves as a stub. Architectures whose references store operation bits and
  127. // payload bits can share common bytes (e.g., ARM rel32) should override this.
  128. class ReferenceMixer {
  129. public:
  130. virtual ~ReferenceMixer() = default;
  131. // Computes mixed reference bytes by combining (a) "payload bits" from an
  132. // "old" reference at |old_offset| with (b) "operation bits" from a "new"
  133. // reference at |new_offset|. Returns the result as ConstBufferView, which is
  134. // valid only until the next call to Mix().
  135. virtual ConstBufferView Mix(offset_t old_offset, offset_t new_offset) = 0;
  136. };
  137. // An Equivalence is a block of length |length| that approximately match in
  138. // |old_image| at an offset of |src_offset| and in |new_image| at an offset of
  139. // |dst_offset|.
  140. struct Equivalence {
  141. offset_t src_offset;
  142. offset_t dst_offset;
  143. offset_t length;
  144. offset_t src_end() const { return src_offset + length; }
  145. offset_t dst_end() const { return dst_offset + length; }
  146. };
  147. inline bool operator==(const Equivalence& a, const Equivalence& b) {
  148. return a.src_offset == b.src_offset && a.dst_offset == b.dst_offset &&
  149. a.length == b.length;
  150. }
  151. // Same as Equivalence, but with a similarity score. This is only used when
  152. // generating the patch.
  153. struct EquivalenceCandidate {
  154. Equivalence eq;
  155. double similarity;
  156. };
  157. template <size_t N>
  158. inline constexpr uint32_t ExeTypeToUint32(const char (&exe_type)[N]) {
  159. static_assert(N == 5, "Expected ExeType of length 4 + 1 null byte.");
  160. return (exe_type[3] << 24) | (exe_type[2] << 16) | (exe_type[1] << 8) |
  161. exe_type[0];
  162. }
  163. // Enumerations for supported executables. Values in this enum must be distinct.
  164. // Once present, values should never be altered or removed to ensure backwards
  165. // compatibility and patch type collision avoidance.
  166. enum ExecutableType : uint32_t {
  167. kExeTypeUnknown = UINT32_MAX,
  168. kExeTypeNoOp = ExeTypeToUint32("NoOp"),
  169. kExeTypeWin32X86 = ExeTypeToUint32("Px86"),
  170. kExeTypeWin32X64 = ExeTypeToUint32("Px64"),
  171. kExeTypeElfX86 = ExeTypeToUint32("Ex86"),
  172. kExeTypeElfX64 = ExeTypeToUint32("Ex64"),
  173. kExeTypeElfAArch32 = ExeTypeToUint32("EA32"),
  174. kExeTypeElfAArch64 = ExeTypeToUint32("EA64"),
  175. kExeTypeDex = ExeTypeToUint32("DEX "),
  176. kExeTypeZtf = ExeTypeToUint32("ZTF "),
  177. };
  178. constexpr ExecutableType CastToExecutableType(uint32_t possible_exe_type) {
  179. switch (static_cast<ExecutableType>(possible_exe_type)) {
  180. case kExeTypeNoOp: // Falls through.
  181. case kExeTypeWin32X86: // Falls through.
  182. case kExeTypeWin32X64: // Falls through.
  183. case kExeTypeElfX86: // Falls through.
  184. case kExeTypeElfX64: // Falls through.
  185. case kExeTypeElfAArch32: // Falls through.
  186. case kExeTypeElfAArch64: // Falls through.
  187. case kExeTypeDex: // Falls through.
  188. case kExeTypeZtf: // Falls through.
  189. case kExeTypeUnknown:
  190. return static_cast<ExecutableType>(possible_exe_type);
  191. default:
  192. return kExeTypeUnknown;
  193. }
  194. }
  195. inline std::string CastExecutableTypeToString(ExecutableType exe_type) {
  196. uint32_t v = static_cast<uint32_t>(exe_type);
  197. char result[] = {static_cast<char>(v), static_cast<char>(v >> 8),
  198. static_cast<char>(v >> 16), static_cast<char>(v >> 24), 0};
  199. return result;
  200. }
  201. // A region in an image with associated executable type |exe_type|. If
  202. // |exe_type == kExeTypeNoOp|, then the Element represents a region of raw data.
  203. struct Element : public BufferRegion {
  204. Element() = default;
  205. constexpr Element(const BufferRegion& region_in, ExecutableType exe_type_in)
  206. : BufferRegion(region_in), exe_type(exe_type_in) {}
  207. constexpr explicit Element(const BufferRegion& region_in)
  208. : BufferRegion(region_in), exe_type(kExeTypeNoOp) {}
  209. // Similar to lo() and hi(), but returns values in offset_t.
  210. offset_t BeginOffset() const { return base::checked_cast<offset_t>(lo()); }
  211. offset_t EndOffset() const { return base::checked_cast<offset_t>(hi()); }
  212. BufferRegion region() const { return {offset, size}; }
  213. friend bool operator==(const Element& a, const Element& b) {
  214. return a.exe_type == b.exe_type && a.offset == b.offset && a.size == b.size;
  215. }
  216. ExecutableType exe_type;
  217. };
  218. // A matched pair of Elements.
  219. struct ElementMatch {
  220. bool IsValid() const { return old_element.exe_type == new_element.exe_type; }
  221. ExecutableType exe_type() const { return old_element.exe_type; }
  222. // Represents match as "#+#=#+#", where "#" denotes the integers:
  223. // [offset in "old", size in "old", offset in "new", size in "new"].
  224. // Note that element type is omitted.
  225. std::string ToString() const {
  226. return base::StringPrintf("%" PRIuS "+%" PRIuS "=%" PRIuS "+%" PRIuS "",
  227. old_element.offset, old_element.size,
  228. new_element.offset, new_element.size);
  229. }
  230. Element old_element;
  231. Element new_element;
  232. };
  233. } // namespace zucchini
  234. #endif // COMPONENTS_ZUCCHINI_IMAGE_UTILS_H_