1 // Copyright 2017 The Chromium OS 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 "puffin/src/include/puffin/puffdiff.h"
6
7 #include <endian.h>
8 #include <inttypes.h>
9 #include <unistd.h>
10
11 #include <string>
12 #include <vector>
13
14 #include "bsdiff/bsdiff.h"
15 #include "bsdiff/patch_writer_factory.h"
16 #include "zucchini/buffer_view.h"
17 #include "zucchini/patch_writer.h"
18 #include "zucchini/zucchini.h"
19
20 #include "puffin/file_stream.h"
21 #include "puffin/src/include/puffin/brotli_util.h"
22 #include "puffin/src/include/puffin/common.h"
23 #include "puffin/src/include/puffin/puffer.h"
24 #include "puffin/src/include/puffin/puffpatch.h"
25 #include "puffin/src/include/puffin/utils.h"
26 #include "puffin/src/logging.h"
27 #include "puffin/memory_stream.h"
28 #include "puffin/src/puffin.pb.h"
29 #include "puffin/src/puffin_stream.h"
30
31 using std::string;
32 using std::vector;
33
34 namespace puffin {
35
36 namespace {
37 const int kBrotliCompressionQuality = 11;
38
39 template <typename T>
CopyVectorToRpf(const T & from,google::protobuf::RepeatedPtrField<metadata::BitExtent> * to,size_t coef)40 void CopyVectorToRpf(
41 const T& from,
42 google::protobuf::RepeatedPtrField<metadata::BitExtent>* to,
43 size_t coef) {
44 to->Reserve(from.size());
45 for (const auto& ext : from) {
46 auto tmp = to->Add();
47 tmp->set_offset(ext.offset * coef);
48 tmp->set_length(ext.length * coef);
49 }
50 }
51
52 // Structure of a puffin patch
53 // +-------+------------------+-------------+--------------+
54 // |P|U|F|1| PatchHeader Size | PatchHeader | raw patch |
55 // +-------+------------------+-------------+--------------+
CreatePatch(const Buffer & raw_patch,const vector<BitExtent> & src_deflates,const vector<BitExtent> & dst_deflates,const vector<ByteExtent> & src_puffs,const vector<ByteExtent> & dst_puffs,uint64_t src_puff_size,uint64_t dst_puff_size,PatchAlgorithm patchAlgorithm,Buffer * patch)56 bool CreatePatch(const Buffer& raw_patch,
57 const vector<BitExtent>& src_deflates,
58 const vector<BitExtent>& dst_deflates,
59 const vector<ByteExtent>& src_puffs,
60 const vector<ByteExtent>& dst_puffs,
61 uint64_t src_puff_size,
62 uint64_t dst_puff_size,
63 PatchAlgorithm patchAlgorithm,
64 Buffer* patch) {
65 metadata::PatchHeader header;
66 header.set_version(1);
67
68 CopyVectorToRpf(src_deflates, header.mutable_src()->mutable_deflates(), 1);
69 CopyVectorToRpf(dst_deflates, header.mutable_dst()->mutable_deflates(), 1);
70 CopyVectorToRpf(src_puffs, header.mutable_src()->mutable_puffs(), 8);
71 CopyVectorToRpf(dst_puffs, header.mutable_dst()->mutable_puffs(), 8);
72
73 header.mutable_src()->set_puff_length(src_puff_size);
74 header.mutable_dst()->set_puff_length(dst_puff_size);
75 header.set_type(static_cast<metadata::PatchHeader_PatchType>(patchAlgorithm));
76
77 const size_t header_size_long = header.ByteSizeLong();
78 TEST_AND_RETURN_FALSE(header_size_long <= UINT32_MAX);
79 const uint32_t header_size = header_size_long;
80
81 uint64_t offset = 0;
82 patch->resize(kMagicLength + sizeof(header_size) + header_size +
83 raw_patch.size());
84
85 memcpy(patch->data() + offset, kMagic, kMagicLength);
86 offset += kMagicLength;
87
88 // Read header size from big-endian mode.
89 uint32_t be_header_size = htobe32(header_size);
90 memcpy(patch->data() + offset, &be_header_size, sizeof(be_header_size));
91 offset += 4;
92
93 TEST_AND_RETURN_FALSE(
94 header.SerializeToArray(patch->data() + offset, header_size));
95 offset += header_size;
96
97 memcpy(patch->data() + offset, raw_patch.data(), raw_patch.size());
98
99 if (raw_patch.size() > patch->size()) {
100 LOG(ERROR) << "Puffin patch is invalid";
101 }
102 return true;
103 }
104
105 } // namespace
106
PuffDiff(UniqueStreamPtr src,UniqueStreamPtr dst,const vector<BitExtent> & src_deflates,const vector<BitExtent> & dst_deflates,const vector<bsdiff::CompressorType> & compressors,PatchAlgorithm patchAlgorithm,const string & tmp_filepath,Buffer * patch)107 bool PuffDiff(UniqueStreamPtr src,
108 UniqueStreamPtr dst,
109 const vector<BitExtent>& src_deflates,
110 const vector<BitExtent>& dst_deflates,
111 const vector<bsdiff::CompressorType>& compressors,
112 PatchAlgorithm patchAlgorithm,
113 const string& tmp_filepath,
114 Buffer* patch) {
115 auto puffer = std::make_shared<Puffer>();
116 auto puff_deflate_stream =
117 [&puffer](UniqueStreamPtr stream, const vector<BitExtent>& deflates,
118 Buffer* puff_buffer, vector<ByteExtent>* puffs) {
119 uint64_t puff_size;
120 TEST_AND_RETURN_FALSE(stream->Seek(0));
121 TEST_AND_RETURN_FALSE(
122 FindPuffLocations(stream, deflates, puffs, &puff_size));
123 TEST_AND_RETURN_FALSE(stream->Seek(0));
124 auto src_puffin_stream = PuffinStream::CreateForPuff(
125 std::move(stream), puffer, puff_size, deflates, *puffs);
126 puff_buffer->resize(puff_size);
127 TEST_AND_RETURN_FALSE(
128 src_puffin_stream->Read(puff_buffer->data(), puff_buffer->size()));
129 return true;
130 };
131
132 Buffer src_puff_buffer;
133 Buffer dst_puff_buffer;
134 vector<ByteExtent> src_puffs, dst_puffs;
135 TEST_AND_RETURN_FALSE(puff_deflate_stream(std::move(src), src_deflates,
136 &src_puff_buffer, &src_puffs));
137 TEST_AND_RETURN_FALSE(puff_deflate_stream(std::move(dst), dst_deflates,
138 &dst_puff_buffer, &dst_puffs));
139
140 if (patchAlgorithm == PatchAlgorithm::kBsdiff) {
141 auto bsdiff_patch_writer = bsdiff::CreateBSDF2PatchWriter(
142 tmp_filepath, compressors, kBrotliCompressionQuality);
143
144 TEST_AND_RETURN_FALSE(
145 0 == bsdiff::bsdiff(src_puff_buffer.data(), src_puff_buffer.size(),
146 dst_puff_buffer.data(), dst_puff_buffer.size(),
147 bsdiff_patch_writer.get(), nullptr));
148
149 auto bsdiff_patch = FileStream::Open(tmp_filepath, true, false);
150 TEST_AND_RETURN_FALSE(bsdiff_patch);
151 uint64_t patch_size;
152 TEST_AND_RETURN_FALSE(bsdiff_patch->GetSize(&patch_size));
153 Buffer bsdiff_patch_buf(patch_size);
154 TEST_AND_RETURN_FALSE(
155 bsdiff_patch->Read(bsdiff_patch_buf.data(), bsdiff_patch_buf.size()));
156 TEST_AND_RETURN_FALSE(bsdiff_patch->Close());
157
158 TEST_AND_RETURN_FALSE(CreatePatch(
159 bsdiff_patch_buf, src_deflates, dst_deflates, src_puffs, dst_puffs,
160 src_puff_buffer.size(), dst_puff_buffer.size(), patchAlgorithm, patch));
161 } else if (patchAlgorithm == PatchAlgorithm::kZucchini) {
162 zucchini::ConstBufferView src_bytes(src_puff_buffer.data(),
163 src_puff_buffer.size());
164 zucchini::ConstBufferView dst_bytes(dst_puff_buffer.data(),
165 dst_puff_buffer.size());
166
167 zucchini::EnsemblePatchWriter patch_writer(src_bytes, dst_bytes);
168 auto status = zucchini::GenerateBuffer(src_bytes, dst_bytes, &patch_writer);
169 TEST_AND_RETURN_FALSE(status == zucchini::status::kStatusSuccess);
170
171 Buffer zucchini_patch_buf(patch_writer.SerializedSize());
172 patch_writer.SerializeInto(
173 {zucchini_patch_buf.data(), zucchini_patch_buf.size()});
174
175 // Use brotli to compress the zucchini patch.
176 // TODO(197361113) respect the CompressorType parameter for zucchini.
177 Buffer compressed_patch;
178 TEST_AND_RETURN_FALSE(BrotliEncode(zucchini_patch_buf.data(),
179 zucchini_patch_buf.size(),
180 &compressed_patch));
181
182 TEST_AND_RETURN_FALSE(CreatePatch(
183 compressed_patch, src_deflates, dst_deflates, src_puffs, dst_puffs,
184 src_puff_buffer.size(), dst_puff_buffer.size(), patchAlgorithm, patch));
185 } else {
186 LOG(ERROR) << "unsupported type " << static_cast<int>(patchAlgorithm);
187 return false;
188 }
189
190 return true;
191 }
192
PuffDiff(UniqueStreamPtr src,UniqueStreamPtr dst,const std::vector<BitExtent> & src_deflates,const std::vector<BitExtent> & dst_deflates,const std::vector<bsdiff::CompressorType> & compressors,const std::string & tmp_filepath,Buffer * patch)193 bool PuffDiff(UniqueStreamPtr src,
194 UniqueStreamPtr dst,
195 const std::vector<BitExtent>& src_deflates,
196 const std::vector<BitExtent>& dst_deflates,
197 const std::vector<bsdiff::CompressorType>& compressors,
198 const std::string& tmp_filepath,
199 Buffer* patch) {
200 return PuffDiff(std::move(src), std::move(dst), src_deflates, dst_deflates,
201 compressors, PatchAlgorithm::kBsdiff, tmp_filepath, patch);
202 }
203
PuffDiff(const Buffer & src,const Buffer & dst,const vector<BitExtent> & src_deflates,const vector<BitExtent> & dst_deflates,const vector<bsdiff::CompressorType> & compressors,const string & tmp_filepath,Buffer * patch)204 bool PuffDiff(const Buffer& src,
205 const Buffer& dst,
206 const vector<BitExtent>& src_deflates,
207 const vector<BitExtent>& dst_deflates,
208 const vector<bsdiff::CompressorType>& compressors,
209 const string& tmp_filepath,
210 Buffer* patch) {
211 return PuffDiff(MemoryStream::CreateForRead(src),
212 MemoryStream::CreateForRead(dst), src_deflates, dst_deflates,
213 compressors, PatchAlgorithm::kBsdiff, tmp_filepath, patch);
214 }
215
PuffDiff(const Buffer & src,const Buffer & dst,const vector<BitExtent> & src_deflates,const vector<BitExtent> & dst_deflates,const string & tmp_filepath,Buffer * patch)216 bool PuffDiff(const Buffer& src,
217 const Buffer& dst,
218 const vector<BitExtent>& src_deflates,
219 const vector<BitExtent>& dst_deflates,
220 const string& tmp_filepath,
221 Buffer* patch) {
222 return PuffDiff(
223 src, dst, src_deflates, dst_deflates,
224 {bsdiff::CompressorType::kBZ2, bsdiff::CompressorType::kBrotli},
225 tmp_filepath, patch);
226 }
227
228 } // namespace puffin
229