1 //
2 // Copyright (C) 2021 The Android Open Source Project
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 // http://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 //
16
17 #include "lz4diff.h"
18 #include "lz4diff_compress.h"
19
20 #include <bsdiff/bsdiff.h>
21 #include <bsdiff/constants.h>
22 #include <bsdiff/patch_writer_factory.h>
23 #include <bsdiff/patch_writer.h>
24 #include <puffin/common.h>
25 #include <puffin/puffdiff.h>
26 #include <lz4.h>
27 #include <lz4hc.h>
28
29 #include "update_engine/common/utils.h"
30 #include "update_engine/common/hash_calculator.h"
31 #include "update_engine/payload_generator/deflate_utils.h"
32 #include "update_engine/payload_generator/delta_diff_generator.h"
33 #include "lz4diff/lz4diff.pb.h"
34 #include "lz4diff_format.h"
35
36 namespace chromeos_update_engine {
37
StoreDstCompressedFileInfo(std::string_view recompressed_blob,std::string_view target_blob,const CompressedFile & dst_file_info,Lz4diffHeader * output)38 bool StoreDstCompressedFileInfo(std::string_view recompressed_blob,
39 std::string_view target_blob,
40 const CompressedFile& dst_file_info,
41 Lz4diffHeader* output) {
42 *output->mutable_dst_info()->mutable_algo() = dst_file_info.algo;
43 output->mutable_dst_info()->set_zero_padding_enabled(
44 dst_file_info.zero_padding_enabled);
45 const auto& block_info = dst_file_info.blocks;
46 auto& dst_block_info = *output->mutable_dst_info()->mutable_block_info();
47 dst_block_info.Clear();
48 size_t offset = 0;
49 for (const auto& block : block_info) {
50 auto& pb_block = *dst_block_info.Add();
51 pb_block.set_uncompressed_offset(block.uncompressed_offset);
52 pb_block.set_uncompressed_length(block.uncompressed_length);
53 pb_block.set_compressed_length(block.compressed_length);
54 CHECK_LT(offset, recompressed_blob.size());
55 auto s1 = recompressed_blob.substr(offset, block.compressed_length);
56 auto s2 = target_blob.substr(offset, block.compressed_length);
57 if (s1 != s2) {
58 ScopedTempFile patch;
59 int err =
60 bsdiff::bsdiff(reinterpret_cast<const unsigned char*>(s1.data()),
61 s1.size(),
62 reinterpret_cast<const unsigned char*>(s2.data()),
63 s2.size(),
64 patch.path().c_str(),
65 nullptr);
66 CHECK_EQ(err, 0);
67 LOG(WARNING) << "Recompress Postfix patch size: "
68 << utils::FileSize(patch.path());
69 std::string patch_content;
70 TEST_AND_RETURN_FALSE(utils::ReadFile(patch.path(), &patch_content));
71 pb_block.set_postfix_bspatch(std::move(patch_content));
72 }
73 // Include recompressed blob hash, so we can determine if the device
74 // produces same compressed output
75 Blob recompressed_blob_hash;
76 TEST_AND_RETURN_FALSE(HashCalculator::RawHashOfBytes(
77 s1.data(), s1.length(), &recompressed_blob_hash));
78 pb_block.set_sha256_hash(recompressed_blob_hash.data(),
79 recompressed_blob_hash.size());
80
81 offset += block.compressed_length;
82 }
83 return true;
84 }
85
86 template <typename Blob>
TryBsdiff(Blob src,Blob dst,Blob * output)87 static bool TryBsdiff(Blob src, Blob dst, Blob* output) noexcept {
88 static constexpr auto kLz4diffDefaultBrotliQuality = 9;
89 CHECK_NE(output, nullptr);
90 ScopedTempFile patch;
91
92 Blob bsdiff_delta;
93 bsdiff::BsdiffPatchWriter patch_writer(patch.path(),
94 {bsdiff::CompressorType::kBrotli},
95 kLz4diffDefaultBrotliQuality);
96 TEST_AND_RETURN_FALSE(0 == bsdiff::bsdiff(src.data(),
97 src.size(),
98 dst.data(),
99 dst.size(),
100 &patch_writer,
101 nullptr));
102
103 TEST_AND_RETURN_FALSE(utils::ReadFile(patch.path(), &bsdiff_delta));
104 TEST_AND_RETURN_FALSE(!bsdiff_delta.empty());
105 *output = std::move(bsdiff_delta);
106 return true;
107 }
108
TryFindDeflates(puffin::Buffer data,std::vector<puffin::BitExtent> * deflates)109 bool TryFindDeflates(puffin::Buffer data,
110 std::vector<puffin::BitExtent>* deflates) {
111 if (puffin::LocateDeflatesInZipArchive(data, deflates)) {
112 return true;
113 }
114 deflates->clear();
115 if (puffin::LocateDeflatesInGzip(data, deflates)) {
116 return true;
117 }
118 deflates->clear();
119 return false;
120 }
121
ConstructLz4diffPatch(Blob inner_patch,const Lz4diffHeader & header,Blob * output)122 static bool ConstructLz4diffPatch(Blob inner_patch,
123 const Lz4diffHeader& header,
124 Blob* output) {
125 Blob patch(kLz4diffHeaderSize);
126 std::memcpy(patch.data(), kLz4diffMagic.data(), kLz4diffMagic.size());
127 *reinterpret_cast<uint32_t*>(patch.data() + kLz4diffMagic.size()) =
128 htobe32(kLz4diffVersion);
129
130 std::string serialized_pb;
131 TEST_AND_RETURN_FALSE(header.SerializeToString(&serialized_pb));
132 *reinterpret_cast<uint32_t*>(patch.data() + kLz4diffMagic.size() + 4) =
133 htobe32(serialized_pb.size());
134 patch.insert(patch.end(), serialized_pb.begin(), serialized_pb.end());
135 patch.insert(patch.end(), inner_patch.begin(), inner_patch.end());
136
137 *output = std::move(patch);
138 return true;
139 }
140
TryPuffdiff(puffin::Buffer src,puffin::Buffer dst,Blob * output)141 static bool TryPuffdiff(puffin::Buffer src,
142 puffin::Buffer dst,
143 Blob* output) noexcept {
144 CHECK_NE(output, nullptr);
145 std::vector<puffin::BitExtent> src_deflates;
146 TEST_AND_RETURN_FALSE(TryFindDeflates(src, &src_deflates));
147 std::vector<puffin::BitExtent> dst_deflates;
148 TEST_AND_RETURN_FALSE(TryFindDeflates(dst, &dst_deflates));
149 if (src_deflates.empty() || dst_deflates.empty()) {
150 return false;
151 }
152
153 Blob puffdiff_delta;
154 ScopedTempFile temp_file("puffdiff-delta.XXXXXX");
155 // Perform PuffDiff operation.
156 TEST_AND_RETURN_FALSE(puffin::PuffDiff(
157 src, dst, src_deflates, dst_deflates, temp_file.path(), &puffdiff_delta));
158 TEST_AND_RETURN_FALSE(!puffdiff_delta.empty());
159
160 *output = std::move(puffdiff_delta);
161 return true;
162 }
163
StoreSrcCompressedFileInfo(const CompressedFile & src_file_info,Lz4diffHeader * header)164 static void StoreSrcCompressedFileInfo(const CompressedFile& src_file_info,
165 Lz4diffHeader* header) {
166 *header->mutable_src_info()->mutable_algo() = src_file_info.algo;
167 header->mutable_src_info()->set_zero_padding_enabled(
168 src_file_info.zero_padding_enabled);
169 auto& src_blocks = *header->mutable_src_info()->mutable_block_info();
170 src_blocks.Clear();
171 for (const auto& block : src_file_info.blocks) {
172 auto& block_info = *src_blocks.Add();
173 block_info.set_uncompressed_length(block.uncompressed_length);
174 block_info.set_uncompressed_offset(block.uncompressed_offset);
175 block_info.set_compressed_length(block.compressed_length);
176 }
177 return;
178 }
179
Lz4Diff(std::string_view src,std::string_view dst,const CompressedFile & src_file_info,const CompressedFile & dst_file_info,Blob * output,InstallOperation::Type * op_type)180 bool Lz4Diff(std::string_view src,
181 std::string_view dst,
182 const CompressedFile& src_file_info,
183 const CompressedFile& dst_file_info,
184 Blob* output,
185 InstallOperation::Type* op_type) noexcept {
186 const auto& src_block_info = src_file_info.blocks;
187 const auto& dst_block_info = dst_file_info.blocks;
188
189 auto decompressed_src = TryDecompressBlob(
190 src, src_block_info, src_file_info.zero_padding_enabled);
191 auto decompressed_dst = TryDecompressBlob(
192 dst, dst_block_info, dst_file_info.zero_padding_enabled);
193 if (decompressed_src.empty() || decompressed_dst.empty()) {
194 LOG(ERROR) << "Failed to decompress input data";
195 return false;
196 }
197
198 Lz4diffHeader header;
199 // BSDIFF isn't supposed to fail, so return error if BSDIFF failed.
200 Blob patch_data;
201 TEST_AND_RETURN_FALSE(
202 TryBsdiff(decompressed_src, decompressed_dst, &patch_data));
203 header.set_inner_type(InnerPatchType::BSDIFF);
204 if (op_type) {
205 *op_type = InstallOperation::LZ4DIFF_BSDIFF;
206 }
207 // PUFFDIFF might fail, as the input data might not be deflate compressed.
208
209 Blob puffdiff_delta;
210 if (TryPuffdiff(decompressed_src, decompressed_dst, &puffdiff_delta) &&
211 puffdiff_delta.size() < patch_data.size()) {
212 patch_data = std::move(puffdiff_delta);
213 header.set_inner_type(InnerPatchType::PUFFDIFF);
214 if (op_type) {
215 *op_type = InstallOperation::LZ4DIFF_PUFFDIFF;
216 }
217 }
218 // Free up memory used by |decompressed_src| , as we don't need it anymore.
219 decompressed_src = {};
220
221 auto recompressed_blob = TryCompressBlob(ToStringView(decompressed_dst),
222 dst_block_info,
223 dst_file_info.zero_padding_enabled,
224 dst_file_info.algo);
225 TEST_AND_RETURN_FALSE(recompressed_blob.size() > 0);
226
227 StoreSrcCompressedFileInfo(src_file_info, &header);
228 StoreDstCompressedFileInfo(
229 ToStringView(recompressed_blob), dst, dst_file_info, &header);
230 return ConstructLz4diffPatch(std::move(patch_data), header, output);
231 }
232
Lz4Diff(const Blob & src,const Blob & dst,const CompressedFile & src_file_info,const CompressedFile & dst_file_info,Blob * output,InstallOperation::Type * op_type)233 bool Lz4Diff(const Blob& src,
234 const Blob& dst,
235 const CompressedFile& src_file_info,
236 const CompressedFile& dst_file_info,
237 Blob* output,
238 InstallOperation::Type* op_type) noexcept {
239 return Lz4Diff(ToStringView(src),
240 ToStringView(dst),
241 src_file_info,
242 dst_file_info,
243 output,
244 op_type);
245 }
246
247 } // namespace chromeos_update_engine
248