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
5 #include "components/zucchini/zucchini_apply.h"
6
7 #include <algorithm>
8 #include <map>
9 #include <memory>
10 #include <utility>
11
12 #include "base/logging.h"
13 #include "base/numerics/safe_conversions.h"
14 #include "components/zucchini/disassembler.h"
15 #include "components/zucchini/element_detection.h"
16 #include "components/zucchini/equivalence_map.h"
17 #include "components/zucchini/image_index.h"
18
19 namespace zucchini {
20
ApplyEquivalenceAndExtraData(ConstBufferView old_image,const PatchElementReader & patch_reader,MutableBufferView new_image)21 bool ApplyEquivalenceAndExtraData(ConstBufferView old_image,
22 const PatchElementReader& patch_reader,
23 MutableBufferView new_image) {
24 EquivalenceSource equiv_source = patch_reader.GetEquivalenceSource();
25 ExtraDataSource extra_data_source = patch_reader.GetExtraDataSource();
26 MutableBufferView::iterator dst_it = new_image.begin();
27
28 for (auto equivalence = equiv_source.GetNext(); equivalence.has_value();
29 equivalence = equiv_source.GetNext()) {
30 MutableBufferView::iterator next_dst_it =
31 new_image.begin() + equivalence->dst_offset;
32 CHECK(next_dst_it >= dst_it);
33
34 offset_t gap = static_cast<offset_t>(next_dst_it - dst_it);
35 std::optional<ConstBufferView> extra_data = extra_data_source.GetNext(gap);
36 if (!extra_data) {
37 LOG(ERROR) << "Error reading extra_data";
38 return false;
39 }
40 // |extra_data| length is based on what was parsed from the patch so this
41 // copy should be valid.
42 dst_it = std::copy(extra_data->begin(), extra_data->end(), dst_it);
43 CHECK_EQ(dst_it, next_dst_it);
44 dst_it = std::copy_n(old_image.begin() + equivalence->src_offset,
45 equivalence->length, dst_it);
46 CHECK_EQ(dst_it, next_dst_it + equivalence->length);
47 }
48 offset_t gap = static_cast<offset_t>(new_image.end() - dst_it);
49 std::optional<ConstBufferView> extra_data = extra_data_source.GetNext(gap);
50 if (!extra_data) {
51 LOG(ERROR) << "Error reading extra_data";
52 return false;
53 }
54 std::copy(extra_data->begin(), extra_data->end(), dst_it);
55 if (!equiv_source.Done() || !extra_data_source.Done()) {
56 LOG(ERROR) << "Found trailing equivalence and extra_data";
57 return false;
58 }
59 return true;
60 }
61
ApplyRawDelta(const PatchElementReader & patch_reader,MutableBufferView new_image)62 bool ApplyRawDelta(const PatchElementReader& patch_reader,
63 MutableBufferView new_image) {
64 EquivalenceSource equiv_source = patch_reader.GetEquivalenceSource();
65 RawDeltaSource raw_delta_source = patch_reader.GetRawDeltaSource();
66 // Traverse |equiv_source| and |raw_delta_source| in lockstep.
67 auto equivalence = equiv_source.GetNext();
68 offset_t base_copy_offset = 0;
69 for (auto delta = raw_delta_source.GetNext(); delta.has_value();
70 delta = raw_delta_source.GetNext()) {
71 while (equivalence.has_value() &&
72 base_copy_offset + equivalence->length <= delta->copy_offset) {
73 base_copy_offset += equivalence->length;
74 equivalence = equiv_source.GetNext();
75 }
76 if (!equivalence.has_value()) {
77 LOG(ERROR) << "Error reading equivalences";
78 return false;
79 }
80 CHECK_GE(delta->copy_offset, base_copy_offset);
81 CHECK_LT(delta->copy_offset, base_copy_offset + equivalence->length);
82
83 // Invert byte diff.
84 new_image[equivalence->dst_offset - base_copy_offset +
85 delta->copy_offset] += delta->diff;
86 }
87 if (!raw_delta_source.Done()) {
88 LOG(ERROR) << "Found trailing raw_delta";
89 return false;
90 }
91 return true;
92 }
93
ApplyReferencesCorrection(ExecutableType exe_type,ConstBufferView old_image,const PatchElementReader & patch,MutableBufferView new_image)94 bool ApplyReferencesCorrection(ExecutableType exe_type,
95 ConstBufferView old_image,
96 const PatchElementReader& patch,
97 MutableBufferView new_image) {
98 auto old_disasm = MakeDisassemblerOfType(old_image, exe_type);
99 auto new_disasm =
100 MakeDisassemblerOfType(ConstBufferView(new_image), exe_type);
101 if (!old_disasm || !new_disasm) {
102 LOG(ERROR) << "Failed to create Disassembler";
103 return false;
104 }
105 if (old_disasm->size() != old_image.size() ||
106 new_disasm->size() != new_image.size()) {
107 LOG(ERROR) << "Disassembler and element size mismatch";
108 return false;
109 }
110
111 ReferenceDeltaSource ref_delta_source = patch.GetReferenceDeltaSource();
112 std::map<PoolTag, std::vector<ReferenceGroup>> pool_groups;
113 for (const auto& ref_group : old_disasm->MakeReferenceGroups())
114 pool_groups[ref_group.pool_tag()].push_back(ref_group);
115
116 OffsetMapper offset_mapper(patch.GetEquivalenceSource(),
117 base::checked_cast<offset_t>(old_image.size()),
118 base::checked_cast<offset_t>(new_image.size()));
119
120 std::vector<ReferenceGroup> new_groups = new_disasm->MakeReferenceGroups();
121 for (const auto& pool_and_sub_groups : pool_groups) {
122 PoolTag pool_tag = pool_and_sub_groups.first;
123 const std::vector<ReferenceGroup>& sub_groups = pool_and_sub_groups.second;
124
125 TargetPool targets;
126 // Load "old" targets, then filter and map them to "new" targets.
127 for (ReferenceGroup group : sub_groups)
128 targets.InsertTargets(std::move(*group.GetReader(old_disasm.get())));
129 targets.FilterAndProject(offset_mapper);
130
131 // Load extra targets from patch.
132 TargetSource target_source = patch.GetExtraTargetSource(pool_tag);
133 targets.InsertTargets(&target_source);
134 if (!target_source.Done()) {
135 LOG(ERROR) << "Found trailing extra_targets";
136 return false;
137 }
138
139 // Correct all new references, and write results to |new_disasm|.
140 for (ReferenceGroup group : sub_groups) {
141 std::unique_ptr<ReferenceWriter> ref_writer =
142 new_groups[group.type_tag().value()].GetWriter(new_image,
143 new_disasm.get());
144
145 EquivalenceSource equiv_source = patch.GetEquivalenceSource();
146 for (auto equivalence = equiv_source.GetNext(); equivalence.has_value();
147 equivalence = equiv_source.GetNext()) {
148 std::unique_ptr<ReferenceReader> ref_gen = group.GetReader(
149 equivalence->src_offset, equivalence->src_end(), old_disasm.get());
150 for (auto ref = ref_gen->GetNext(); ref.has_value();
151 ref = ref_gen->GetNext()) {
152 DCHECK_GE(ref->location, equivalence->src_offset);
153 DCHECK_LT(ref->location, equivalence->src_end());
154
155 offset_t projected_target =
156 offset_mapper.ExtendedForwardProject(ref->target);
157 offset_t expected_key = targets.KeyForNearestOffset(projected_target);
158 auto delta = ref_delta_source.GetNext();
159 if (!delta.has_value()) {
160 LOG(ERROR) << "Error reading reference_delta";
161 return false;
162 }
163 const key_t key = expected_key + delta.value();
164 if (!targets.KeyIsValid(key)) {
165 LOG(ERROR) << "Invalid reference_delta";
166 return false;
167 }
168 ref->target = targets.OffsetForKey(expected_key + delta.value());
169 ref->location =
170 ref->location - equivalence->src_offset + equivalence->dst_offset;
171 ref_writer->PutNext(*ref);
172 }
173 }
174 }
175 }
176 if (!ref_delta_source.Done()) {
177 LOG(ERROR) << "Found trailing ref_delta_source";
178 return false;
179 }
180 return true;
181 }
182
ApplyElement(ExecutableType exe_type,ConstBufferView old_image,const PatchElementReader & patch_reader,MutableBufferView new_image)183 bool ApplyElement(ExecutableType exe_type,
184 ConstBufferView old_image,
185 const PatchElementReader& patch_reader,
186 MutableBufferView new_image) {
187 return ApplyEquivalenceAndExtraData(old_image, patch_reader, new_image) &&
188 ApplyRawDelta(patch_reader, new_image) &&
189 ApplyReferencesCorrection(exe_type, old_image, patch_reader,
190 new_image);
191 }
192
193 /******** Exported Functions ********/
194
ApplyBuffer(ConstBufferView old_image,const EnsemblePatchReader & patch_reader,MutableBufferView new_image)195 status::Code ApplyBuffer(ConstBufferView old_image,
196 const EnsemblePatchReader& patch_reader,
197 MutableBufferView new_image) {
198 if (!patch_reader.CheckOldFile(old_image)) {
199 LOG(ERROR) << "Invalid old_image.";
200 return status::kStatusInvalidOldImage;
201 }
202
203 for (const auto& element_patch : patch_reader.elements()) {
204 ElementMatch match = element_patch.element_match();
205 if (!ApplyElement(match.exe_type(), old_image[match.old_element.region()],
206 element_patch, new_image[match.new_element.region()]))
207 return status::kStatusFatal;
208 }
209
210 if (!patch_reader.CheckNewFile(ConstBufferView(new_image))) {
211 LOG(ERROR) << "Invalid new_image.";
212 return status::kStatusInvalidNewImage;
213 }
214 return status::kStatusSuccess;
215 }
216
217 } // namespace zucchini
218