1 /*
2  * Copyright (C) 2019 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 "deploy_patch_generator.h"
18 
19 #include <inttypes.h>
20 #include <stdio.h>
21 
22 #include <algorithm>
23 #include <fstream>
24 #include <functional>
25 #include <iostream>
26 #include <sstream>
27 #include <string>
28 #include <unordered_map>
29 
30 #include <openssl/md5.h>
31 
32 #include "adb_unique_fd.h"
33 #include "adb_utils.h"
34 #include "android-base/file.h"
35 #include "patch_utils.h"
36 #include "sysdeps.h"
37 
38 using namespace com::android::fastdeploy;
39 
40 void DeployPatchGenerator::Log(const char* fmt, ...) {
41     va_list ap;
42     va_start(ap, fmt);
43     vprintf(fmt, ap);
44     printf("\n");
45     va_end(ap);
46 }
47 
48 static std::string HexEncode(const void* in_buffer, unsigned int size) {
49     static const char kHexChars[] = "0123456789ABCDEF";
50 
51     // Each input byte creates two output hex characters.
52     std::string out_buffer(size * 2, '\0');
53 
54     for (unsigned int i = 0; i < size; ++i) {
55         char byte = ((const uint8_t*)in_buffer)[i];
56         out_buffer[(i << 1)] = kHexChars[(byte >> 4) & 0xf];
57         out_buffer[(i << 1) + 1] = kHexChars[byte & 0xf];
58     }
59     return out_buffer;
60 }
61 
62 void DeployPatchGenerator::APKEntryToLog(const APKEntry& entry) {
63     if (!is_verbose_) {
64         return;
65     }
66     Log("MD5: %s", HexEncode(entry.md5().data(), entry.md5().size()).c_str());
67     Log("Data Offset: %" PRId64, entry.dataoffset());
68     Log("Data Size: %" PRId64, entry.datasize());
69 }
70 
71 void DeployPatchGenerator::APKMetaDataToLog(const APKMetaData& metadata) {
72     if (!is_verbose_) {
73         return;
74     }
75     Log("APK Metadata: %s", metadata.absolute_path().c_str());
76     for (int i = 0; i < metadata.entries_size(); i++) {
77         const APKEntry& entry = metadata.entries(i);
78         APKEntryToLog(entry);
79     }
80 }
81 
82 void DeployPatchGenerator::ReportSavings(const std::vector<SimpleEntry>& identicalEntries,
83                                          uint64_t totalSize) {
84     uint64_t totalEqualBytes = 0;
85     uint64_t totalEqualFiles = 0;
86     for (size_t i = 0; i < identicalEntries.size(); i++) {
87         if (identicalEntries[i].deviceEntry != nullptr) {
88             totalEqualBytes += identicalEntries[i].localEntry->datasize();
89             totalEqualFiles++;
90         }
91     }
92     double savingPercent = (totalEqualBytes * 100.0f) / totalSize;
93     fprintf(stderr, "Detected %" PRIu64 " equal APK entries\n", totalEqualFiles);
94     fprintf(stderr, "%" PRIu64 " bytes are equal out of %" PRIu64 " (%.2f%%)\n", totalEqualBytes,
95             totalSize, savingPercent);
96 }
97 
98 struct PatchEntry {
99     int64_t deltaFromDeviceDataStart = 0;
100     int64_t deviceDataOffset = 0;
101     int64_t deviceDataLength = 0;
102 };
103 static void WritePatchEntry(const PatchEntry& patchEntry, borrowed_fd input, borrowed_fd output,
104                             size_t* realSizeOut) {
105     if (!(patchEntry.deltaFromDeviceDataStart | patchEntry.deviceDataOffset |
106           patchEntry.deviceDataLength)) {
107         return;
108     }
109 
110     PatchUtils::WriteLong(patchEntry.deltaFromDeviceDataStart, output);
111     if (patchEntry.deltaFromDeviceDataStart > 0) {
112         PatchUtils::Pipe(input, output, patchEntry.deltaFromDeviceDataStart);
113     }
114     auto hostDataLength = patchEntry.deviceDataLength;
115     adb_lseek(input, hostDataLength, SEEK_CUR);
116 
117     PatchUtils::WriteLong(patchEntry.deviceDataOffset, output);
118     PatchUtils::WriteLong(patchEntry.deviceDataLength, output);
119 
120     *realSizeOut += patchEntry.deltaFromDeviceDataStart + hostDataLength;
121 }
122 
123 void DeployPatchGenerator::GeneratePatch(const std::vector<SimpleEntry>& entriesToUseOnDevice,
124                                          const std::string& localApkPath,
125                                          const std::string& deviceApkPath, borrowed_fd output) {
126     unique_fd input(adb_open(localApkPath.c_str(), O_RDONLY | O_CLOEXEC));
127     size_t newApkSize = adb_lseek(input, 0L, SEEK_END);
128     adb_lseek(input, 0L, SEEK_SET);
129 
130     // Header.
131     PatchUtils::WriteSignature(output);
132     PatchUtils::WriteLong(newApkSize, output);
133     PatchUtils::WriteString(deviceApkPath, output);
134 
135     size_t currentSizeOut = 0;
136     size_t realSizeOut = 0;
137     // Write data from the host upto the first entry we have that matches a device entry. Then write
138     // the metadata about the device entry and repeat for all entries that match on device. Finally
139     // write out any data left. If the device and host APKs are exactly the same this ends up
140     // writing out zip metadata from the local APK followed by offsets to the data to use from the
141     // device APK.
142     PatchEntry patchEntry;
143     for (size_t i = 0, size = entriesToUseOnDevice.size(); i < size; ++i) {
144         auto&& entry = entriesToUseOnDevice[i];
145         int64_t hostDataOffset = entry.localEntry->dataoffset();
146         int64_t hostDataLength = entry.localEntry->datasize();
147         int64_t deviceDataOffset = entry.deviceEntry->dataoffset();
148         // Both entries are the same, using host data length.
149         int64_t deviceDataLength = hostDataLength;
150 
151         int64_t deltaFromDeviceDataStart = hostDataOffset - currentSizeOut;
152         if (deltaFromDeviceDataStart > 0) {
153             WritePatchEntry(patchEntry, input, output, &realSizeOut);
154             patchEntry.deltaFromDeviceDataStart = deltaFromDeviceDataStart;
155             patchEntry.deviceDataOffset = deviceDataOffset;
156             patchEntry.deviceDataLength = deviceDataLength;
157         } else {
158             patchEntry.deviceDataLength += deviceDataLength;
159         }
160 
161         currentSizeOut += deltaFromDeviceDataStart + hostDataLength;
162     }
163     WritePatchEntry(patchEntry, input, output, &realSizeOut);
164     if (realSizeOut != currentSizeOut) {
165         fprintf(stderr, "Size mismatch current %lld vs real %lld\n",
166                 static_cast<long long>(currentSizeOut), static_cast<long long>(realSizeOut));
167         error_exit("Aborting");
168     }
169 
170     if (newApkSize > currentSizeOut) {
171         PatchUtils::WriteLong(newApkSize - currentSizeOut, output);
172         PatchUtils::Pipe(input, output, newApkSize - currentSizeOut);
173         PatchUtils::WriteLong(0, output);
174         PatchUtils::WriteLong(0, output);
175     }
176 }
177 
178 bool DeployPatchGenerator::CreatePatch(const char* localApkPath, APKMetaData deviceApkMetadata,
179                                        android::base::borrowed_fd output) {
180     return CreatePatch(PatchUtils::GetHostAPKMetaData(localApkPath), std::move(deviceApkMetadata),
181                        output);
182 }
183 
184 bool DeployPatchGenerator::CreatePatch(APKMetaData localApkMetadata, APKMetaData deviceApkMetadata,
185                                        borrowed_fd output) {
186     // Log metadata info.
187     APKMetaDataToLog(deviceApkMetadata);
188     APKMetaDataToLog(localApkMetadata);
189 
190     const std::string localApkPath = localApkMetadata.absolute_path();
191     const std::string deviceApkPath = deviceApkMetadata.absolute_path();
192 
193     std::vector<SimpleEntry> identicalEntries;
194     uint64_t totalSize =
195             BuildIdenticalEntries(identicalEntries, localApkMetadata, deviceApkMetadata);
196     ReportSavings(identicalEntries, totalSize);
197     GeneratePatch(identicalEntries, localApkPath, deviceApkPath, output);
198 
199     return true;
200 }
201 
202 uint64_t DeployPatchGenerator::BuildIdenticalEntries(std::vector<SimpleEntry>& outIdenticalEntries,
203                                                      const APKMetaData& localApkMetadata,
204                                                      const APKMetaData& deviceApkMetadata) {
205     outIdenticalEntries.reserve(
206             std::min(localApkMetadata.entries_size(), deviceApkMetadata.entries_size()));
207 
208     using md5Digest = std::pair<uint64_t, uint64_t>;
209     struct md5Hash {
210         size_t operator()(const md5Digest& digest) const {
211             std::hash<uint64_t> hasher;
212             size_t seed = 0;
213             seed ^= hasher(digest.first) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
214             seed ^= hasher(digest.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
215             return seed;
216         }
217     };
218     static_assert(sizeof(md5Digest) == MD5_DIGEST_LENGTH);
219     std::unordered_map<md5Digest, std::vector<const APKEntry*>, md5Hash> deviceEntries;
220     for (const auto& deviceEntry : deviceApkMetadata.entries()) {
221         md5Digest md5;
222         memcpy(&md5, deviceEntry.md5().data(), deviceEntry.md5().size());
223 
224         deviceEntries[md5].push_back(&deviceEntry);
225     }
226 
227     uint64_t totalSize = 0;
228     for (const auto& localEntry : localApkMetadata.entries()) {
229         totalSize += localEntry.datasize();
230 
231         md5Digest md5;
232         memcpy(&md5, localEntry.md5().data(), localEntry.md5().size());
233 
234         auto deviceEntriesIt = deviceEntries.find(md5);
235         if (deviceEntriesIt == deviceEntries.end()) {
236             continue;
237         }
238 
239         for (const auto* deviceEntry : deviceEntriesIt->second) {
240             if (deviceEntry->md5() == localEntry.md5()) {
241                 SimpleEntry simpleEntry;
242                 simpleEntry.localEntry = &localEntry;
243                 simpleEntry.deviceEntry = deviceEntry;
244                 APKEntryToLog(localEntry);
245                 outIdenticalEntries.push_back(simpleEntry);
246                 break;
247             }
248         }
249     }
250     std::sort(outIdenticalEntries.begin(), outIdenticalEntries.end(),
251               [](const SimpleEntry& lhs, const SimpleEntry& rhs) {
252                   return lhs.localEntry->dataoffset() < rhs.localEntry->dataoffset();
253               });
254     return totalSize;
255 }
256