Tianjie Xu | 91caafe | 2020-03-13 16:16:24 -0700 | [diff] [blame] | 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 | */ |
| 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 | |
| 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. |
| 44 | 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 | |
| 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 | |
| 85 | void CdEntryMapZip32::ResetIteration() { |
| 86 | current_position_ = 0; |
| 87 | } |
| 88 | |
| 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 | |
| 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 | |
| 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 | |
| 121 | std::unique_ptr<CdEntryMapInterface> CdEntryMapZip64::Create() { |
| 122 | return std::unique_ptr<CdEntryMapInterface>(new CdEntryMapZip64()); |
| 123 | } |
| 124 | |
| 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 | |
| 135 | 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 | |
| 146 | void CdEntryMapZip64::ResetIteration() { |
| 147 | iterator_ = entry_table_.begin(); |
| 148 | } |
| 149 | |
| 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 | } |