You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
115 lines
4.6 KiB
115 lines
4.6 KiB
/*
|
|
* Copyright (C) 2020 The Android Open Source Project
|
|
*
|
|
* Licensed under the Apache License, Version 2.0 (the "License");
|
|
* you may not use this file except in compliance with the License.
|
|
* You may obtain a copy of the License at
|
|
*
|
|
* http://www.apache.org/licenses/LICENSE-2.0
|
|
*
|
|
* Unless required by applicable law or agreed to in writing, software
|
|
* distributed under the License is distributed on an "AS IS" BASIS,
|
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
* See the License for the specific language governing permissions and
|
|
* limitations under the License.
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
#include <stdint.h>
|
|
|
|
#include <map>
|
|
#include <memory>
|
|
#include <string_view>
|
|
#include <utility>
|
|
|
|
#include "zip_error.h"
|
|
|
|
// This class is the interface of the central directory entries map. The map
|
|
// helps to locate a particular cd entry based on the filename.
|
|
class CdEntryMapInterface {
|
|
public:
|
|
virtual ~CdEntryMapInterface() = default;
|
|
// Adds an entry to the map. The |name| should internally points to the
|
|
// filename field of a cd entry. And |start| points to the beginning of the
|
|
// central directory. Returns 0 on success.
|
|
virtual ZipError AddToMap(std::string_view name, const uint8_t* start) = 0;
|
|
// For the zip entry |entryName|, finds the offset of its filename field in
|
|
// the central directory. Returns a pair of [status, offset]. The value of
|
|
// the status is 0 on success.
|
|
virtual std::pair<ZipError, uint64_t> GetCdEntryOffset(std::string_view name,
|
|
const uint8_t* cd_start) const = 0;
|
|
// Resets the iterator to the beginning of the map.
|
|
virtual void ResetIteration() = 0;
|
|
// Returns the [name, cd offset] of the current element. Also increments the
|
|
// iterator to points to the next element. Returns an empty pair we have read
|
|
// past boundary.
|
|
virtual std::pair<std::string_view, uint64_t> Next(const uint8_t* cd_start) = 0;
|
|
};
|
|
|
|
/**
|
|
* More space efficient string representation of strings in an mmaped zipped
|
|
* file than std::string_view. Using std::string_view as an entry in the
|
|
* ZipArchive hash table wastes space. std::string_view stores a pointer to a
|
|
* string (on 64 bit, 8 bytes) and the length to read from that pointer,
|
|
* 2 bytes. Because of alignment, the structure consumes 16 bytes, wasting
|
|
* 6 bytes.
|
|
*
|
|
* ZipStringOffset stores a 4 byte offset from a fixed location in the memory
|
|
* mapped file instead of the entire address, consuming 8 bytes with alignment.
|
|
*/
|
|
struct ZipStringOffset {
|
|
uint32_t name_offset;
|
|
uint16_t name_length;
|
|
|
|
const std::string_view ToStringView(const uint8_t* start) const {
|
|
return std::string_view{reinterpret_cast<const char*>(start + name_offset), name_length};
|
|
}
|
|
};
|
|
|
|
// This implementation of CdEntryMap uses an array hash table. It uses less
|
|
// memory than std::map; and it's used as the default implementation for zip
|
|
// archives without zip64 extension.
|
|
class CdEntryMapZip32 : public CdEntryMapInterface {
|
|
public:
|
|
static std::unique_ptr<CdEntryMapInterface> Create(uint16_t num_entries);
|
|
|
|
ZipError AddToMap(std::string_view name, const uint8_t* start) override;
|
|
std::pair<ZipError, uint64_t> GetCdEntryOffset(std::string_view name,
|
|
const uint8_t* cd_start) const override;
|
|
void ResetIteration() override;
|
|
std::pair<std::string_view, uint64_t> Next(const uint8_t* cd_start) override;
|
|
|
|
private:
|
|
explicit CdEntryMapZip32(uint16_t num_entries);
|
|
|
|
// We know how many entries are in the Zip archive, so we can have a
|
|
// fixed-size hash table. We define a load factor of 0.75 and over
|
|
// allocate so the maximum number entries can never be higher than
|
|
// ((4 * UINT16_MAX) / 3 + 1) which can safely fit into a uint32_t.
|
|
uint32_t hash_table_size_{0};
|
|
std::unique_ptr<ZipStringOffset[], decltype(&free)> hash_table_{nullptr, free};
|
|
|
|
// The position of element for the current iteration.
|
|
uint32_t current_position_{0};
|
|
};
|
|
|
|
// This implementation of CdEntryMap uses a std::map
|
|
class CdEntryMapZip64 : public CdEntryMapInterface {
|
|
public:
|
|
static std::unique_ptr<CdEntryMapInterface> Create();
|
|
|
|
ZipError AddToMap(std::string_view name, const uint8_t* start) override;
|
|
std::pair<ZipError, uint64_t> GetCdEntryOffset(std::string_view name,
|
|
const uint8_t* cd_start) const override;
|
|
void ResetIteration() override;
|
|
std::pair<std::string_view, uint64_t> Next(const uint8_t* cd_start) override;
|
|
|
|
private:
|
|
CdEntryMapZip64() = default;
|
|
|
|
std::map<std::string_view, uint64_t> entry_table_;
|
|
|
|
std::map<std::string_view, uint64_t>::iterator iterator_;
|
|
};
|