1 /*
2 * Copyright (C) 2020 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 "zip_cd_entry_map.h"
18
19 #include <android-base/logging.h>
20 #include <log/log.h>
21
22 /*
23 * Round up to the next highest power of 2.
24 *
25 * Found on http://graphics.stanford.edu/~seander/bithacks.html.
26 */
RoundUpPower2(uint32_t val)27 static uint32_t RoundUpPower2(uint32_t val) {
28 val--;
29 val |= val >> 1;
30 val |= val >> 2;
31 val |= val >> 4;
32 val |= val >> 8;
33 val |= val >> 16;
34 val++;
35
36 return val;
37 }
38
ComputeHash(std::string_view name)39 static uint32_t ComputeHash(std::string_view name) {
40 return static_cast<uint32_t>(std::hash<std::string_view>{}(name));
41 }
42
43 // Convert a ZipEntry to a hash table index, verifying that it's in a valid range.
GetCdEntryOffset(std::string_view name,const uint8_t * start) const44 std::pair<ZipError, uint64_t> CdEntryMapZip32::GetCdEntryOffset(std::string_view name,
45 const uint8_t* start) const {
46 const uint32_t hash = ComputeHash(name);
47
48 // NOTE: (hash_table_size - 1) is guaranteed to be non-negative.
49 uint32_t ent = hash & (hash_table_size_ - 1);
50 while (hash_table_[ent].name_offset != 0) {
51 if (hash_table_[ent].ToStringView(start) == name) {
52 return {kSuccess, hash_table_[ent].name_offset};
53 }
54 ent = (ent + 1) & (hash_table_size_ - 1);
55 }
56
57 ALOGV("Zip: Unable to find entry %.*s", static_cast<int>(name.size()), name.data());
58 return {kEntryNotFound, 0};
59 }
60
AddToMap(std::string_view name,const uint8_t * start)61 ZipError CdEntryMapZip32::AddToMap(std::string_view name, const uint8_t* start) {
62 const uint64_t hash = ComputeHash(name);
63 uint32_t ent = hash & (hash_table_size_ - 1);
64
65 /*
66 * We over-allocated the table, so we're guaranteed to find an empty slot.
67 * Further, we guarantee that the hashtable size is not 0.
68 */
69 while (hash_table_[ent].name_offset != 0) {
70 if (hash_table_[ent].ToStringView(start) == name) {
71 // We've found a duplicate entry. We don't accept duplicates.
72 ALOGW("Zip: Found duplicate entry %.*s", static_cast<int>(name.size()), name.data());
73 return kDuplicateEntry;
74 }
75 ent = (ent + 1) & (hash_table_size_ - 1);
76 }
77
78 // `name` has already been validated before entry.
79 const char* start_char = reinterpret_cast<const char*>(start);
80 hash_table_[ent].name_offset = static_cast<uint32_t>(name.data() - start_char);
81 hash_table_[ent].name_length = static_cast<uint16_t>(name.size());
82 return kSuccess;
83 }
84
ResetIteration()85 void CdEntryMapZip32::ResetIteration() {
86 current_position_ = 0;
87 }
88
Next(const uint8_t * cd_start)89 std::pair<std::string_view, uint64_t> CdEntryMapZip32::Next(const uint8_t* cd_start) {
90 while (current_position_ < hash_table_size_) {
91 const auto& entry = hash_table_[current_position_];
92 current_position_ += 1;
93
94 if (entry.name_offset != 0) {
95 return {entry.ToStringView(cd_start), entry.name_offset};
96 }
97 }
98 // We have reached the end of the hash table.
99 return {};
100 }
101
CdEntryMapZip32(uint16_t num_entries)102 CdEntryMapZip32::CdEntryMapZip32(uint16_t num_entries) {
103 /*
104 * Create hash table. We have a minimum 75% load factor, possibly as
105 * low as 50% after we round off to a power of 2. There must be at
106 * least one unused entry to avoid an infinite loop during creation.
107 */
108 hash_table_size_ = RoundUpPower2(1 + (num_entries * 4) / 3);
109 hash_table_ = {
110 reinterpret_cast<ZipStringOffset*>(calloc(hash_table_size_, sizeof(ZipStringOffset))), free};
111 }
112
Create(uint16_t num_entries)113 std::unique_ptr<CdEntryMapInterface> CdEntryMapZip32::Create(uint16_t num_entries) {
114 auto entry_map = new CdEntryMapZip32(num_entries);
115 CHECK(entry_map->hash_table_ != nullptr)
116 << "Zip: unable to allocate the " << entry_map->hash_table_size_
117 << " entry hash_table, entry size: " << sizeof(ZipStringOffset);
118 return std::unique_ptr<CdEntryMapInterface>(entry_map);
119 }
120
Create()121 std::unique_ptr<CdEntryMapInterface> CdEntryMapZip64::Create() {
122 return std::unique_ptr<CdEntryMapInterface>(new CdEntryMapZip64());
123 }
124
AddToMap(std::string_view name,const uint8_t * start)125 ZipError CdEntryMapZip64::AddToMap(std::string_view name, const uint8_t* start) {
126 const auto [it, added] =
127 entry_table_.insert({name, name.data() - reinterpret_cast<const char*>(start)});
128 if (!added) {
129 ALOGW("Zip: Found duplicate entry %.*s", static_cast<int>(name.size()), name.data());
130 return kDuplicateEntry;
131 }
132 return kSuccess;
133 }
134
GetCdEntryOffset(std::string_view name,const uint8_t *) const135 std::pair<ZipError, uint64_t> CdEntryMapZip64::GetCdEntryOffset(std::string_view name,
136 const uint8_t* /*cd_start*/) const {
137 const auto it = entry_table_.find(name);
138 if (it == entry_table_.end()) {
139 ALOGV("Zip: Could not find entry %.*s", static_cast<int>(name.size()), name.data());
140 return {kEntryNotFound, 0};
141 }
142
143 return {kSuccess, it->second};
144 }
145
ResetIteration()146 void CdEntryMapZip64::ResetIteration() {
147 iterator_ = entry_table_.begin();
148 }
149
Next(const uint8_t *)150 std::pair<std::string_view, uint64_t> CdEntryMapZip64::Next(const uint8_t* /*cd_start*/) {
151 if (iterator_ == entry_table_.end()) {
152 return {};
153 }
154
155 return *iterator_++;
156 }
157