blob: 6c701dd0b67347a58f906475b4e5715471b566ab [file] [log] [blame]
/*
* Copyright (C) 2007 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.
*/
//
// Read-only access to Zip archives, with minimal heap allocation.
//
#define LOG_TAG "zipro"
//#define LOG_NDEBUG 0
#include <utils/ZipFileRO.h>
#include <utils/Log.h>
#include <utils/misc.h>
#include <zlib.h>
#include <string.h>
#include <fcntl.h>
#include <errno.h>
#include <assert.h>
using namespace android;
/*
* Zip file constants.
*/
#define kEOCDSignature 0x06054b50
#define kEOCDLen 22
#define kEOCDNumEntries 8 // offset to #of entries in file
#define kEOCDFileOffset 16 // offset to central directory
#define kMaxCommentLen 65535 // longest possible in ushort
#define kMaxEOCDSearch (kMaxCommentLen + kEOCDLen)
#define kLFHSignature 0x04034b50
#define kLFHLen 30 // excluding variable-len fields
#define kLFHNameLen 26 // offset to filename length
#define kLFHExtraLen 28 // offset to extra length
#define kCDESignature 0x02014b50
#define kCDELen 46 // excluding variable-len fields
#define kCDEMethod 10 // offset to compression method
#define kCDEModWhen 12 // offset to modification timestamp
#define kCDECRC 16 // offset to entry CRC
#define kCDECompLen 20 // offset to compressed length
#define kCDEUncompLen 24 // offset to uncompressed length
#define kCDENameLen 28 // offset to filename length
#define kCDEExtraLen 30 // offset to extra length
#define kCDECommentLen 32 // offset to comment length
#define kCDELocalOffset 42 // offset to local hdr
/*
* The values we return for ZipEntryRO use 0 as an invalid value, so we
* want to adjust the hash table index by a fixed amount. Using a large
* value helps insure that people don't mix & match arguments, e.g. to
* findEntryByIndex().
*/
#define kZipEntryAdj 10000
/*
* Convert a ZipEntryRO to a hash table index, verifying that it's in a
* valid range.
*/
int ZipFileRO::entryToIndex(const ZipEntryRO entry) const
{
long ent = ((long) entry) - kZipEntryAdj;
if (ent < 0 || ent >= mHashTableSize || mHashTable[ent].name == NULL) {
LOGW("Invalid ZipEntryRO %p (%ld)\n", entry, ent);
return -1;
}
return ent;
}
/*
* Open the specified file read-only. We memory-map the entire thing and
* close the file before returning.
*/
status_t ZipFileRO::open(const char* zipFileName)
{
int fd = -1;
off_t length;
assert(mFileMap == NULL);
/*
* Open and map the specified file.
*/
fd = ::open(zipFileName, O_RDONLY);
if (fd < 0) {
LOGW("Unable to open zip '%s': %s\n", zipFileName, strerror(errno));
return NAME_NOT_FOUND;
}
length = lseek(fd, 0, SEEK_END);
if (length < 0) {
close(fd);
return UNKNOWN_ERROR;
}
mFileMap = new FileMap();
if (mFileMap == NULL) {
close(fd);
return NO_MEMORY;
}
if (!mFileMap->create(zipFileName, fd, 0, length, true)) {
LOGW("Unable to map '%s': %s\n", zipFileName, strerror(errno));
close(fd);
return UNKNOWN_ERROR;
}
mFd = fd;
/*
* Got it mapped, verify it and create data structures for fast access.
*/
if (!parseZipArchive()) {
mFileMap->release();
mFileMap = NULL;
return UNKNOWN_ERROR;
}
return OK;
}
/*
* Parse the Zip archive, verifying its contents and initializing internal
* data structures.
*/
bool ZipFileRO::parseZipArchive(void)
{
#define CHECK_OFFSET(_off) { \
if ((unsigned int) (_off) >= maxOffset) { \
LOGE("ERROR: bad offset %u (max %d): %s\n", \
(unsigned int) (_off), maxOffset, #_off); \
goto bail; \
} \
}
const unsigned char* basePtr = (const unsigned char*)mFileMap->getDataPtr();
const unsigned char* ptr;
size_t length = mFileMap->getDataLength();
bool result = false;
unsigned int i, numEntries, cdOffset;
unsigned int val;
/*
* The first 4 bytes of the file will either be the local header
* signature for the first file (kLFHSignature) or, if the archive doesn't
* have any files in it, the end-of-central-directory signature
* (kEOCDSignature).
*/
val = get4LE(basePtr);
if (val == kEOCDSignature) {
LOGI("Found Zip archive, but it looks empty\n");
goto bail;
} else if (val != kLFHSignature) {
LOGV("Not a Zip archive (found 0x%08x)\n", val);
goto bail;
}
/*
* Find the EOCD. We'll find it immediately unless they have a file
* comment.
*/
ptr = basePtr + length - kEOCDLen;
while (ptr >= basePtr) {
if (*ptr == (kEOCDSignature & 0xff) && get4LE(ptr) == kEOCDSignature)
break;
ptr--;
}
if (ptr < basePtr) {
LOGI("Could not find end-of-central-directory in Zip\n");
goto bail;
}
/*
* There are two interesting items in the EOCD block: the number of
* entries in the file, and the file offset of the start of the
* central directory.
*
* (There's actually a count of the #of entries in this file, and for
* all files which comprise a spanned archive, but for our purposes
* we're only interested in the current file. Besides, we expect the
* two to be equivalent for our stuff.)
*/
numEntries = get2LE(ptr + kEOCDNumEntries);
cdOffset = get4LE(ptr + kEOCDFileOffset);
/* valid offsets are [0,EOCD] */
unsigned int maxOffset;
maxOffset = (ptr - basePtr) +1;
LOGV("+++ numEntries=%d cdOffset=%d\n", numEntries, cdOffset);
if (numEntries == 0 || cdOffset >= length) {
LOGW("Invalid entries=%d offset=%d (len=%zd)\n",
numEntries, cdOffset, length);
goto bail;
}
/*
* Create hash table. We have a minimum 75% load factor, possibly as
* low as 50% after we round off to a power of 2.
*/
mNumEntries = numEntries;
mHashTableSize = roundUpPower2(1 + ((numEntries * 4) / 3));
mHashTable = (HashEntry*) calloc(1, sizeof(HashEntry) * mHashTableSize);
/*
* Walk through the central directory, adding entries to the hash
* table.
*/
ptr = basePtr + cdOffset;
for (i = 0; i < numEntries; i++) {
unsigned int fileNameLen, extraLen, commentLen, localHdrOffset;
const unsigned char* localHdr;
unsigned int hash;
if (get4LE(ptr) != kCDESignature) {
LOGW("Missed a central dir sig (at %d)\n", i);
goto bail;
}
if (ptr + kCDELen > basePtr + length) {
LOGW("Ran off the end (at %d)\n", i);
goto bail;
}
localHdrOffset = get4LE(ptr + kCDELocalOffset);
CHECK_OFFSET(localHdrOffset);
fileNameLen = get2LE(ptr + kCDENameLen);
extraLen = get2LE(ptr + kCDEExtraLen);
commentLen = get2LE(ptr + kCDECommentLen);
//LOGV("+++ %d: localHdr=%d fnl=%d el=%d cl=%d\n",
// i, localHdrOffset, fileNameLen, extraLen, commentLen);
//LOGV(" '%.*s'\n", fileNameLen, ptr + kCDELen);
/* add the CDE filename to the hash table */
hash = computeHash((const char*)ptr + kCDELen, fileNameLen);
addToHash((const char*)ptr + kCDELen, fileNameLen, hash);
localHdr = basePtr + localHdrOffset;
if (get4LE(localHdr) != kLFHSignature) {
LOGW("Bad offset to local header: %d (at %d)\n",
localHdrOffset, i);
goto bail;
}
ptr += kCDELen + fileNameLen + extraLen + commentLen;
CHECK_OFFSET(ptr - basePtr);
}
result = true;
bail:
return result;
#undef CHECK_OFFSET
}
/*
* Simple string hash function for non-null-terminated strings.
*/
/*static*/ unsigned int ZipFileRO::computeHash(const char* str, int len)
{
unsigned int hash = 0;
while (len--)
hash = hash * 31 + *str++;
return hash;
}
/*
* Add a new entry to the hash table.
*/
void ZipFileRO::addToHash(const char* str, int strLen, unsigned int hash)
{
int ent = hash & (mHashTableSize-1);
/*
* We over-allocate the table, so we're guaranteed to find an empty slot.
*/
while (mHashTable[ent].name != NULL)
ent = (ent + 1) & (mHashTableSize-1);
mHashTable[ent].name = str;
mHashTable[ent].nameLen = strLen;
}
/*
* Find a matching entry.
*
* Returns 0 if not found.
*/
ZipEntryRO ZipFileRO::findEntryByName(const char* fileName) const
{
int nameLen = strlen(fileName);
unsigned int hash = computeHash(fileName, nameLen);
int ent = hash & (mHashTableSize-1);
while (mHashTable[ent].name != NULL) {
if (mHashTable[ent].nameLen == nameLen &&
memcmp(mHashTable[ent].name, fileName, nameLen) == 0)
{
/* match */
return (ZipEntryRO) (ent + kZipEntryAdj);
}
ent = (ent + 1) & (mHashTableSize-1);
}
return NULL;
}
/*
* Find the Nth entry.
*
* This currently involves walking through the sparse hash table, counting
* non-empty entries. If we need to speed this up we can either allocate
* a parallel lookup table or (perhaps better) provide an iterator interface.
*/
ZipEntryRO ZipFileRO::findEntryByIndex(int idx) const
{
if (idx < 0 || idx >= mNumEntries) {
LOGW("Invalid index %d\n", idx);
return NULL;
}
for (int ent = 0; ent < mHashTableSize; ent++) {
if (mHashTable[ent].name != NULL) {
if (idx-- == 0)
return (ZipEntryRO) (ent + kZipEntryAdj);
}
}
return NULL;
}
/*
* Get the useful fields from the zip entry.
*
* Returns "false" if the offsets to the fields or the contents of the fields
* appear to be bogus.
*/
bool ZipFileRO::getEntryInfo(ZipEntryRO entry, int* pMethod, long* pUncompLen,
long* pCompLen, off_t* pOffset, long* pModWhen, long* pCrc32) const
{
int ent = entryToIndex(entry);
if (ent < 0)
return false;
/*
* Recover the start of the central directory entry from the filename
* pointer.
*/
const unsigned char* basePtr = (const unsigned char*)mFileMap->getDataPtr();
const unsigned char* ptr = (const unsigned char*) mHashTable[ent].name;
size_t zipLength = mFileMap->getDataLength();
ptr -= kCDELen;
int method = get2LE(ptr + kCDEMethod);
if (pMethod != NULL)
*pMethod = method;
if (pModWhen != NULL)
*pModWhen = get4LE(ptr + kCDEModWhen);
if (pCrc32 != NULL)
*pCrc32 = get4LE(ptr + kCDECRC);
/*
* We need to make sure that the lengths are not so large that somebody
* trying to map the compressed or uncompressed data runs off the end
* of the mapped region.
*/
unsigned long localHdrOffset = get4LE(ptr + kCDELocalOffset);
if (localHdrOffset + kLFHLen >= zipLength) {
LOGE("ERROR: bad local hdr offset in zip\n");
return false;
}
const unsigned char* localHdr = basePtr + localHdrOffset;
off_t dataOffset = localHdrOffset + kLFHLen
+ get2LE(localHdr + kLFHNameLen) + get2LE(localHdr + kLFHExtraLen);
if ((unsigned long) dataOffset >= zipLength) {
LOGE("ERROR: bad data offset in zip\n");
return false;
}
if (pCompLen != NULL) {
*pCompLen = get4LE(ptr + kCDECompLen);
if (*pCompLen < 0 || (size_t)(dataOffset + *pCompLen) >= zipLength) {
LOGE("ERROR: bad compressed length in zip\n");
return false;
}
}
if (pUncompLen != NULL) {
*pUncompLen = get4LE(ptr + kCDEUncompLen);
if (*pUncompLen < 0) {
LOGE("ERROR: negative uncompressed length in zip\n");
return false;
}
if (method == kCompressStored &&
(size_t)(dataOffset + *pUncompLen) >= zipLength)
{
LOGE("ERROR: bad uncompressed length in zip\n");
return false;
}
}
if (pOffset != NULL) {
*pOffset = dataOffset;
}
return true;
}
/*
* Copy the entry's filename to the buffer.
*/
int ZipFileRO::getEntryFileName(ZipEntryRO entry, char* buffer, int bufLen)
const
{
int ent = entryToIndex(entry);
if (ent < 0)
return -1;
int nameLen = mHashTable[ent].nameLen;
if (bufLen < nameLen+1)
return nameLen+1;
memcpy(buffer, mHashTable[ent].name, nameLen);
buffer[nameLen] = '\0';
return 0;
}
/*
* Create a new FileMap object that spans the data in "entry".
*/
FileMap* ZipFileRO::createEntryFileMap(ZipEntryRO entry) const
{
/*
* TODO: the efficient way to do this is to modify FileMap to allow
* sub-regions of a file to be mapped. A reference-counting scheme
* can manage the base memory mapping. For now, we just create a brand
* new mapping off of the Zip archive file descriptor.
*/
FileMap* newMap;
long compLen;
off_t offset;
if (!getEntryInfo(entry, NULL, NULL, &compLen, &offset, NULL, NULL))
return NULL;
newMap = new FileMap();
if (!newMap->create(mFileMap->getFileName(), mFd, offset, compLen, true)) {
newMap->release();
return NULL;
}
return newMap;
}
/*
* Uncompress an entry, in its entirety, into the provided output buffer.
*
* This doesn't verify the data's CRC, which might be useful for
* uncompressed data. The caller should be able to manage it.
*/
bool ZipFileRO::uncompressEntry(ZipEntryRO entry, void* buffer) const
{
const int kSequentialMin = 32768;
bool result = false;
int ent = entryToIndex(entry);
if (ent < 0)
return -1;
const unsigned char* basePtr = (const unsigned char*)mFileMap->getDataPtr();
int method;
long uncompLen, compLen;
off_t offset;
getEntryInfo(entry, &method, &uncompLen, &compLen, &offset, NULL, NULL);
/*
* Experiment with madvise hint. When we want to uncompress a file,
* we pull some stuff out of the central dir entry and then hit a
* bunch of compressed or uncompressed data sequentially. The CDE
* visit will cause a limited amount of read-ahead because it's at
* the end of the file. We could end up doing lots of extra disk
* access if the file we're prying open is small. Bottom line is we
* probably don't want to turn MADV_SEQUENTIAL on and leave it on.
*
* So, if the compressed size of the file is above a certain minimum
* size, temporarily boost the read-ahead in the hope that the extra
* pair of system calls are negated by a reduction in page faults.
*/
if (compLen > kSequentialMin)
mFileMap->advise(FileMap::SEQUENTIAL);
if (method == kCompressStored) {
memcpy(buffer, basePtr + offset, uncompLen);
} else {
if (!inflateBuffer(buffer, basePtr + offset, uncompLen, compLen))
goto bail;
}
if (compLen > kSequentialMin)
mFileMap->advise(FileMap::NORMAL);
result = true;
bail:
return result;
}
/*
* Uncompress an entry, in its entirety, to an open file descriptor.
*
* This doesn't verify the data's CRC, but probably should.
*/
bool ZipFileRO::uncompressEntry(ZipEntryRO entry, int fd) const
{
bool result = false;
int ent = entryToIndex(entry);
if (ent < 0)
return -1;
const unsigned char* basePtr = (const unsigned char*)mFileMap->getDataPtr();
int method;
long uncompLen, compLen;
off_t offset;
getEntryInfo(entry, &method, &uncompLen, &compLen, &offset, NULL, NULL);
if (method == kCompressStored) {
ssize_t actual;
actual = write(fd, basePtr + offset, uncompLen);
if (actual < 0) {
LOGE("Write failed: %s\n", strerror(errno));
goto bail;
} else if (actual != uncompLen) {
LOGE("Partial write during uncompress (%d of %ld)\n",
(int)actual, uncompLen);
goto bail;
} else {
LOGI("+++ successful write\n");
}
} else {
if (!inflateBuffer(fd, basePtr+offset, uncompLen, compLen))
goto bail;
}
result = true;
bail:
return result;
}
/*
* Uncompress "deflate" data from one buffer to another.
*/
/*static*/ bool ZipFileRO::inflateBuffer(void* outBuf, const void* inBuf,
long uncompLen, long compLen)
{
bool result = false;
z_stream zstream;
int zerr;
/*
* Initialize the zlib stream struct.
*/
memset(&zstream, 0, sizeof(zstream));
zstream.zalloc = Z_NULL;
zstream.zfree = Z_NULL;
zstream.opaque = Z_NULL;
zstream.next_in = (Bytef*)inBuf;
zstream.avail_in = compLen;
zstream.next_out = (Bytef*) outBuf;
zstream.avail_out = uncompLen;
zstream.data_type = Z_UNKNOWN;
/*
* Use the undocumented "negative window bits" feature to tell zlib
* that there's no zlib header waiting for it.
*/
zerr = inflateInit2(&zstream, -MAX_WBITS);
if (zerr != Z_OK) {
if (zerr == Z_VERSION_ERROR) {
LOGE("Installed zlib is not compatible with linked version (%s)\n",
ZLIB_VERSION);
} else {
LOGE("Call to inflateInit2 failed (zerr=%d)\n", zerr);
}
goto bail;
}
/*
* Expand data.
*/
zerr = inflate(&zstream, Z_FINISH);
if (zerr != Z_STREAM_END) {
LOGW("Zip inflate failed, zerr=%d (nIn=%p aIn=%u nOut=%p aOut=%u)\n",
zerr, zstream.next_in, zstream.avail_in,
zstream.next_out, zstream.avail_out);
goto z_bail;
}
/* paranoia */
if ((long) zstream.total_out != uncompLen) {
LOGW("Size mismatch on inflated file (%ld vs %ld)\n",
zstream.total_out, uncompLen);
goto z_bail;
}
result = true;
z_bail:
inflateEnd(&zstream); /* free up any allocated structures */
bail:
return result;
}
/*
* Uncompress "deflate" data from one buffer to an open file descriptor.
*/
/*static*/ bool ZipFileRO::inflateBuffer(int fd, const void* inBuf,
long uncompLen, long compLen)
{
bool result = false;
const int kWriteBufSize = 32768;
unsigned char writeBuf[kWriteBufSize];
z_stream zstream;
int zerr;
/*
* Initialize the zlib stream struct.
*/
memset(&zstream, 0, sizeof(zstream));
zstream.zalloc = Z_NULL;
zstream.zfree = Z_NULL;
zstream.opaque = Z_NULL;
zstream.next_in = (Bytef*)inBuf;
zstream.avail_in = compLen;
zstream.next_out = (Bytef*) writeBuf;
zstream.avail_out = sizeof(writeBuf);
zstream.data_type = Z_UNKNOWN;
/*
* Use the undocumented "negative window bits" feature to tell zlib
* that there's no zlib header waiting for it.
*/
zerr = inflateInit2(&zstream, -MAX_WBITS);
if (zerr != Z_OK) {
if (zerr == Z_VERSION_ERROR) {
LOGE("Installed zlib is not compatible with linked version (%s)\n",
ZLIB_VERSION);
} else {
LOGE("Call to inflateInit2 failed (zerr=%d)\n", zerr);
}
goto bail;
}
/*
* Loop while we have more to do.
*/
do {
/*
* Expand data.
*/
zerr = inflate(&zstream, Z_NO_FLUSH);
if (zerr != Z_OK && zerr != Z_STREAM_END) {
LOGW("zlib inflate: zerr=%d (nIn=%p aIn=%u nOut=%p aOut=%u)\n",
zerr, zstream.next_in, zstream.avail_in,
zstream.next_out, zstream.avail_out);
goto z_bail;
}
/* write when we're full or when we're done */
if (zstream.avail_out == 0 ||
(zerr == Z_STREAM_END && zstream.avail_out != sizeof(writeBuf)))
{
long writeSize = zstream.next_out - writeBuf;
int cc = write(fd, writeBuf, writeSize);
if (cc != (int) writeSize) {
LOGW("write failed in inflate (%d vs %ld)\n", cc, writeSize);
goto z_bail;
}
zstream.next_out = writeBuf;
zstream.avail_out = sizeof(writeBuf);
}
} while (zerr == Z_OK);
assert(zerr == Z_STREAM_END); /* other errors should've been caught */
/* paranoia */
if ((long) zstream.total_out != uncompLen) {
LOGW("Size mismatch on inflated file (%ld vs %ld)\n",
zstream.total_out, uncompLen);
goto z_bail;
}
result = true;
z_bail:
inflateEnd(&zstream); /* free up any allocated structures */
bail:
return result;
}