From 23580ca27a0a8109312fdd36cc363ad1f4719889 Mon Sep 17 00:00:00 2001 From: The Android Open Source Project Date: Tue, 21 Oct 2008 07:00:00 -0700 Subject: Initial Contribution --- minzip/Android.mk | 19 + minzip/Bits.h | 357 ++++++++++++++++ minzip/DirUtil.c | 280 +++++++++++++ minzip/DirUtil.h | 51 +++ minzip/Hash.c | 390 ++++++++++++++++++ minzip/Hash.h | 186 +++++++++ minzip/Inlines.c | 25 ++ minzip/Log.h | 207 ++++++++++ minzip/SysUtil.c | 212 ++++++++++ minzip/SysUtil.h | 61 +++ minzip/Zip.c | 1098 +++++++++++++++++++++++++++++++++++++++++++++++++ minzip/Zip.h | 206 ++++++++++ minzip/inline_magic.h | 26 ++ 13 files changed, 3118 insertions(+) create mode 100644 minzip/Android.mk create mode 100644 minzip/Bits.h create mode 100644 minzip/DirUtil.c create mode 100644 minzip/DirUtil.h create mode 100644 minzip/Hash.c create mode 100644 minzip/Hash.h create mode 100644 minzip/Inlines.c create mode 100644 minzip/Log.h create mode 100644 minzip/SysUtil.c create mode 100644 minzip/SysUtil.h create mode 100644 minzip/Zip.c create mode 100644 minzip/Zip.h create mode 100644 minzip/inline_magic.h (limited to 'minzip') diff --git a/minzip/Android.mk b/minzip/Android.mk new file mode 100644 index 0000000..b1ee674 --- /dev/null +++ b/minzip/Android.mk @@ -0,0 +1,19 @@ +LOCAL_PATH := $(call my-dir) +include $(CLEAR_VARS) + +LOCAL_SRC_FILES := \ + Hash.c \ + SysUtil.c \ + DirUtil.c \ + Inlines.c \ + Zip.c + +LOCAL_C_INCLUDES += \ + external/zlib \ + external/safe-iop/include + +LOCAL_MODULE := libminzip + +LOCAL_CFLAGS += -Wall + +include $(BUILD_STATIC_LIBRARY) diff --git a/minzip/Bits.h b/minzip/Bits.h new file mode 100644 index 0000000..f96e6c4 --- /dev/null +++ b/minzip/Bits.h @@ -0,0 +1,357 @@ +/* + * Copyright 2006 The Android Open Source Project + * + * Some handy functions for manipulating bits and bytes. + */ +#ifndef _MINZIP_BITS +#define _MINZIP_BITS + +#include "inline_magic.h" + +#include +#include + +/* + * Get 1 byte. (Included to make the code more legible.) + */ +INLINE unsigned char get1(unsigned const char* pSrc) +{ + return *pSrc; +} + +/* + * Get 2 big-endian bytes. + */ +INLINE unsigned short get2BE(unsigned char const* pSrc) +{ + unsigned short result; + + result = *pSrc++ << 8; + result |= *pSrc++; + + return result; +} + +/* + * Get 4 big-endian bytes. + */ +INLINE unsigned int get4BE(unsigned char const* pSrc) +{ + unsigned int result; + + result = *pSrc++ << 24; + result |= *pSrc++ << 16; + result |= *pSrc++ << 8; + result |= *pSrc++; + + return result; +} + +/* + * Get 8 big-endian bytes. + */ +INLINE unsigned long long get8BE(unsigned char const* pSrc) +{ + unsigned long long result; + + result = (unsigned long long) *pSrc++ << 56; + result |= (unsigned long long) *pSrc++ << 48; + result |= (unsigned long long) *pSrc++ << 40; + result |= (unsigned long long) *pSrc++ << 32; + result |= (unsigned long long) *pSrc++ << 24; + result |= (unsigned long long) *pSrc++ << 16; + result |= (unsigned long long) *pSrc++ << 8; + result |= (unsigned long long) *pSrc++; + + return result; +} + +/* + * Get 2 little-endian bytes. + */ +INLINE unsigned short get2LE(unsigned char const* pSrc) +{ + unsigned short result; + + result = *pSrc++; + result |= *pSrc++ << 8; + + return result; +} + +/* + * Get 4 little-endian bytes. + */ +INLINE unsigned int get4LE(unsigned char const* pSrc) +{ + unsigned int result; + + result = *pSrc++; + result |= *pSrc++ << 8; + result |= *pSrc++ << 16; + result |= *pSrc++ << 24; + + return result; +} + +/* + * Get 8 little-endian bytes. + */ +INLINE unsigned long long get8LE(unsigned char const* pSrc) +{ + unsigned long long result; + + result = (unsigned long long) *pSrc++; + result |= (unsigned long long) *pSrc++ << 8; + result |= (unsigned long long) *pSrc++ << 16; + result |= (unsigned long long) *pSrc++ << 24; + result |= (unsigned long long) *pSrc++ << 32; + result |= (unsigned long long) *pSrc++ << 40; + result |= (unsigned long long) *pSrc++ << 48; + result |= (unsigned long long) *pSrc++ << 56; + + return result; +} + +/* + * Grab 1 byte and advance the data pointer. + */ +INLINE unsigned char read1(unsigned const char** ppSrc) +{ + return *(*ppSrc)++; +} + +/* + * Grab 2 big-endian bytes and advance the data pointer. + */ +INLINE unsigned short read2BE(unsigned char const** ppSrc) +{ + unsigned short result; + + result = *(*ppSrc)++ << 8; + result |= *(*ppSrc)++; + + return result; +} + +/* + * Grab 4 big-endian bytes and advance the data pointer. + */ +INLINE unsigned int read4BE(unsigned char const** ppSrc) +{ + unsigned int result; + + result = *(*ppSrc)++ << 24; + result |= *(*ppSrc)++ << 16; + result |= *(*ppSrc)++ << 8; + result |= *(*ppSrc)++; + + return result; +} + +/* + * Get 8 big-endian bytes. + */ +INLINE unsigned long long read8BE(unsigned char const** ppSrc) +{ + unsigned long long result; + + result = (unsigned long long) *(*ppSrc)++ << 56; + result |= (unsigned long long) *(*ppSrc)++ << 48; + result |= (unsigned long long) *(*ppSrc)++ << 40; + result |= (unsigned long long) *(*ppSrc)++ << 32; + result |= (unsigned long long) *(*ppSrc)++ << 24; + result |= (unsigned long long) *(*ppSrc)++ << 16; + result |= (unsigned long long) *(*ppSrc)++ << 8; + result |= (unsigned long long) *(*ppSrc)++; + + return result; +} + +/* + * Grab 2 little-endian bytes and advance the data pointer. + */ +INLINE unsigned short read2LE(unsigned char const** ppSrc) +{ + unsigned short result; + + result = *(*ppSrc)++; + result |= *(*ppSrc)++ << 8; + + return result; +} + +/* + * Grab 4 little-endian bytes and advance the data pointer. + */ +INLINE unsigned int read4LE(unsigned char const** ppSrc) +{ + unsigned int result; + + result = *(*ppSrc)++; + result |= *(*ppSrc)++ << 8; + result |= *(*ppSrc)++ << 16; + result |= *(*ppSrc)++ << 24; + + return result; +} + +/* + * Get 8 little-endian bytes. + */ +INLINE unsigned long long read8LE(unsigned char const** ppSrc) +{ + unsigned long long result; + + result = (unsigned long long) *(*ppSrc)++; + result |= (unsigned long long) *(*ppSrc)++ << 8; + result |= (unsigned long long) *(*ppSrc)++ << 16; + result |= (unsigned long long) *(*ppSrc)++ << 24; + result |= (unsigned long long) *(*ppSrc)++ << 32; + result |= (unsigned long long) *(*ppSrc)++ << 40; + result |= (unsigned long long) *(*ppSrc)++ << 48; + result |= (unsigned long long) *(*ppSrc)++ << 56; + + return result; +} + +/* + * Skip over a UTF-8 string. + */ +INLINE void skipUtf8String(unsigned char const** ppSrc) +{ + unsigned int length = read4BE(ppSrc); + + (*ppSrc) += length; +} + +/* + * Read a UTF-8 string into a fixed-size buffer, and null-terminate it. + * + * Returns the length of the original string. + */ +INLINE int readUtf8String(unsigned char const** ppSrc, char* buf, size_t bufLen) +{ + unsigned int length = read4BE(ppSrc); + size_t copyLen = (length < bufLen) ? length : bufLen-1; + + memcpy(buf, *ppSrc, copyLen); + buf[copyLen] = '\0'; + + (*ppSrc) += length; + return length; +} + +/* + * Read a UTF-8 string into newly-allocated storage, and null-terminate it. + * + * Returns the string and its length. (The latter is probably unnecessary + * for the way we're using UTF8.) + */ +INLINE char* readNewUtf8String(unsigned char const** ppSrc, size_t* pLength) +{ + unsigned int length = read4BE(ppSrc); + char* buf; + + buf = (char*) malloc(length+1); + + memcpy(buf, *ppSrc, length); + buf[length] = '\0'; + + (*ppSrc) += length; + + *pLength = length; + return buf; +} + + +/* + * Set 1 byte. (Included to make the code more legible.) + */ +INLINE void set1(unsigned char* buf, unsigned char val) +{ + *buf = (unsigned char)(val); +} + +/* + * Set 2 big-endian bytes. + */ +INLINE void set2BE(unsigned char* buf, unsigned short val) +{ + *buf++ = (unsigned char)(val >> 8); + *buf = (unsigned char)(val); +} + +/* + * Set 4 big-endian bytes. + */ +INLINE void set4BE(unsigned char* buf, unsigned int val) +{ + *buf++ = (unsigned char)(val >> 24); + *buf++ = (unsigned char)(val >> 16); + *buf++ = (unsigned char)(val >> 8); + *buf = (unsigned char)(val); +} + +/* + * Set 8 big-endian bytes. + */ +INLINE void set8BE(unsigned char* buf, unsigned long long val) +{ + *buf++ = (unsigned char)(val >> 56); + *buf++ = (unsigned char)(val >> 48); + *buf++ = (unsigned char)(val >> 40); + *buf++ = (unsigned char)(val >> 32); + *buf++ = (unsigned char)(val >> 24); + *buf++ = (unsigned char)(val >> 16); + *buf++ = (unsigned char)(val >> 8); + *buf = (unsigned char)(val); +} + +/* + * Set 2 little-endian bytes. + */ +INLINE void set2LE(unsigned char* buf, unsigned short val) +{ + *buf++ = (unsigned char)(val); + *buf = (unsigned char)(val >> 8); +} + +/* + * Set 4 little-endian bytes. + */ +INLINE void set4LE(unsigned char* buf, unsigned int val) +{ + *buf++ = (unsigned char)(val); + *buf++ = (unsigned char)(val >> 8); + *buf++ = (unsigned char)(val >> 16); + *buf = (unsigned char)(val >> 24); +} + +/* + * Set 8 little-endian bytes. + */ +INLINE void set8LE(unsigned char* buf, unsigned long long val) +{ + *buf++ = (unsigned char)(val); + *buf++ = (unsigned char)(val >> 8); + *buf++ = (unsigned char)(val >> 16); + *buf++ = (unsigned char)(val >> 24); + *buf++ = (unsigned char)(val >> 32); + *buf++ = (unsigned char)(val >> 40); + *buf++ = (unsigned char)(val >> 48); + *buf = (unsigned char)(val >> 56); +} + +/* + * Stuff a UTF-8 string into the buffer. + */ +INLINE void setUtf8String(unsigned char* buf, const unsigned char* str) +{ + unsigned int strLen = strlen((const char*)str); + + set4BE(buf, strLen); + memcpy(buf + sizeof(unsigned int), str, strLen); +} + +#endif /*_MINZIP_BITS*/ diff --git a/minzip/DirUtil.c b/minzip/DirUtil.c new file mode 100644 index 0000000..20c89cd --- /dev/null +++ b/minzip/DirUtil.c @@ -0,0 +1,280 @@ +/* + * 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. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "DirUtil.h" + +typedef enum { DMISSING, DDIR, DILLEGAL } DirStatus; + +static DirStatus +getPathDirStatus(const char *path) +{ + struct stat st; + int err; + + err = stat(path, &st); + if (err == 0) { + /* Something's there; make sure it's a directory. + */ + if (S_ISDIR(st.st_mode)) { + return DDIR; + } + errno = ENOTDIR; + return DILLEGAL; + } else if (errno != ENOENT) { + /* Something went wrong, or something in the path + * is bad. Can't do anything in this situation. + */ + return DILLEGAL; + } + return DMISSING; +} + +int +dirCreateHierarchy(const char *path, int mode, + const struct utimbuf *timestamp, bool stripFileName) +{ + DirStatus ds; + + /* Check for an empty string before we bother + * making any syscalls. + */ + if (path[0] == '\0') { + errno = ENOENT; + return -1; + } + + /* Allocate a path that we can modify; stick a slash on + * the end to make things easier. + */ + size_t pathLen = strlen(path); + char *cpath = (char *)malloc(pathLen + 2); + if (cpath == NULL) { + errno = ENOMEM; + return -1; + } + memcpy(cpath, path, pathLen); + if (stripFileName) { + /* Strip everything after the last slash. + */ + char *c = cpath + pathLen - 1; + while (c != cpath && *c != '/') { + c--; + } + if (c == cpath) { +//xxx test this path + /* No directory component. Act like the path was empty. + */ + errno = ENOENT; + free(cpath); + return -1; + } + c[1] = '\0'; // Terminate after the slash we found. + } else { + /* Make sure that the path ends in a slash. + */ + cpath[pathLen] = '/'; + cpath[pathLen + 1] = '\0'; + } + + /* See if it already exists. + */ + ds = getPathDirStatus(cpath); + if (ds == DDIR) { + return 0; + } else if (ds == DILLEGAL) { + return -1; + } + + /* Walk up the path from the root and make each level. + * If a directory already exists, no big deal. + */ + char *p = cpath; + while (*p != '\0') { + /* Skip any slashes, watching out for the end of the string. + */ + while (*p != '\0' && *p == '/') { + p++; + } + if (*p == '\0') { + break; + } + + /* Find the end of the next path component. + * We know that we'll see a slash before the NUL, + * because we added it, above. + */ + while (*p != '/') { + p++; + } + *p = '\0'; + + /* Check this part of the path and make a new directory + * if necessary. + */ + ds = getPathDirStatus(cpath); + if (ds == DILLEGAL) { + /* Could happen if some other process/thread is + * messing with the filesystem. + */ + free(cpath); + return -1; + } else if (ds == DMISSING) { + int err; + + err = mkdir(cpath, mode); + if (err != 0) { + free(cpath); + return -1; + } + if (timestamp != NULL && utime(cpath, timestamp)) { + free(cpath); + return -1; + } + } + // else, this directory already exists. + + /* Repair the path and continue. + */ + *p = '/'; + } + free(cpath); + + return 0; +} + +int +dirUnlinkHierarchy(const char *path) +{ + struct stat st; + DIR *dir; + struct dirent *de; + int fail = 0; + + /* is it a file or directory? */ + if (lstat(path, &st) < 0) { + return -1; + } + + /* a file, so unlink it */ + if (!S_ISDIR(st.st_mode)) { + return unlink(path); + } + + /* a directory, so open handle */ + dir = opendir(path); + if (dir == NULL) { + return -1; + } + + /* recurse over components */ + errno = 0; + while ((de = readdir(dir)) != NULL) { +//TODO: don't blow the stack + char dn[PATH_MAX]; + if (!strcmp(de->d_name, "..") || !strcmp(de->d_name, ".")) { + continue; + } + snprintf(dn, sizeof(dn), "%s/%s", path, de->d_name); + if (dirUnlinkHierarchy(dn) < 0) { + fail = 1; + break; + } + errno = 0; + } + /* in case readdir or unlink_recursive failed */ + if (fail || errno < 0) { + int save = errno; + closedir(dir); + errno = save; + return -1; + } + + /* close directory handle */ + if (closedir(dir) < 0) { + return -1; + } + + /* delete target directory */ + return rmdir(path); +} + +int +dirSetHierarchyPermissions(const char *path, + int uid, int gid, int dirMode, int fileMode) +{ + struct stat st; + if (lstat(path, &st)) { + return -1; + } + + /* ignore symlinks */ + if (S_ISLNK(st.st_mode)) { + return 0; + } + + /* directories and files get different permissions */ + if (chown(path, uid, gid) || + chmod(path, S_ISDIR(st.st_mode) ? dirMode : fileMode)) { + return -1; + } + + /* recurse over directory components */ + if (S_ISDIR(st.st_mode)) { + DIR *dir = opendir(path); + if (dir == NULL) { + return -1; + } + + errno = 0; + const struct dirent *de; + while (errno == 0 && (de = readdir(dir)) != NULL) { + if (!strcmp(de->d_name, "..") || !strcmp(de->d_name, ".")) { + continue; + } + + char dn[PATH_MAX]; + snprintf(dn, sizeof(dn), "%s/%s", path, de->d_name); + if (!dirSetHierarchyPermissions(dn, uid, gid, dirMode, fileMode)) { + errno = 0; + } else if (errno == 0) { + errno = -1; + } + } + + if (errno != 0) { + int save = errno; + closedir(dir); + errno = save; + return -1; + } + + if (closedir(dir)) { + return -1; + } + } + + return 0; +} diff --git a/minzip/DirUtil.h b/minzip/DirUtil.h new file mode 100644 index 0000000..5d881f5 --- /dev/null +++ b/minzip/DirUtil.h @@ -0,0 +1,51 @@ +/* + * 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. + */ + +#ifndef MINZIP_DIRUTIL_H_ +#define MINZIP_DIRUTIL_H_ + +#include +#include + +/* Like "mkdir -p", try to guarantee that all directories + * specified in path are present, creating as many directories + * as necessary. The specified mode is passed to all mkdir + * calls; no modifications are made to umask. + * + * If stripFileName is set, everything after the final '/' + * is stripped before creating the directory hierarchy. + * + * If timestamp is non-NULL, new directories will be timestamped accordingly. + * + * Returns 0 on success; returns -1 (and sets errno) on failure + * (usually if some element of path is not a directory). + */ +int dirCreateHierarchy(const char *path, int mode, + const struct utimbuf *timestamp, bool stripFileName); + +/* rm -rf + */ +int dirUnlinkHierarchy(const char *path); + +/* chown -R : + * chmod -R + * + * Sets directories to and files to . Skips symlinks. + */ +int dirSetHierarchyPermissions(const char *path, + int uid, int gid, int dirMode, int fileMode); + +#endif // MINZIP_DIRUTIL_H_ diff --git a/minzip/Hash.c b/minzip/Hash.c new file mode 100644 index 0000000..8c6ca9b --- /dev/null +++ b/minzip/Hash.c @@ -0,0 +1,390 @@ +/* + * Copyright 2006 The Android Open Source Project + * + * Hash table. The dominant calls are add and lookup, with removals + * happening very infrequently. We use probing, and don't worry much + * about tombstone removal. + */ +#include +#include + +#define LOG_TAG "minzip" +#include "Log.h" +#include "Hash.h" + +/* table load factor, i.e. how full can it get before we resize */ +//#define LOAD_NUMER 3 // 75% +//#define LOAD_DENOM 4 +#define LOAD_NUMER 5 // 62.5% +#define LOAD_DENOM 8 +//#define LOAD_NUMER 1 // 50% +//#define LOAD_DENOM 2 + +/* + * Compute the capacity needed for a table to hold "size" elements. + */ +size_t mzHashSize(size_t size) { + return (size * LOAD_DENOM) / LOAD_NUMER +1; +} + +/* + * Round up to the next highest power of 2. + * + * Found on http://graphics.stanford.edu/~seander/bithacks.html. + */ +unsigned int roundUpPower2(unsigned int val) +{ + val--; + val |= val >> 1; + val |= val >> 2; + val |= val >> 4; + val |= val >> 8; + val |= val >> 16; + val++; + + return val; +} + +/* + * Create and initialize a hash table. + */ +HashTable* mzHashTableCreate(size_t initialSize, HashFreeFunc freeFunc) +{ + HashTable* pHashTable; + + assert(initialSize > 0); + + pHashTable = (HashTable*) malloc(sizeof(*pHashTable)); + if (pHashTable == NULL) + return NULL; + + pHashTable->tableSize = roundUpPower2(initialSize); + pHashTable->numEntries = pHashTable->numDeadEntries = 0; + pHashTable->freeFunc = freeFunc; + pHashTable->pEntries = + (HashEntry*) calloc((size_t)pHashTable->tableSize, sizeof(HashTable)); + if (pHashTable->pEntries == NULL) { + free(pHashTable); + return NULL; + } + + return pHashTable; +} + +/* + * Clear out all entries. + */ +void mzHashTableClear(HashTable* pHashTable) +{ + HashEntry* pEnt; + int i; + + pEnt = pHashTable->pEntries; + for (i = 0; i < pHashTable->tableSize; i++, pEnt++) { + if (pEnt->data == HASH_TOMBSTONE) { + // nuke entry + pEnt->data = NULL; + } else if (pEnt->data != NULL) { + // call free func then nuke entry + if (pHashTable->freeFunc != NULL) + (*pHashTable->freeFunc)(pEnt->data); + pEnt->data = NULL; + } + } + + pHashTable->numEntries = 0; + pHashTable->numDeadEntries = 0; +} + +/* + * Free the table. + */ +void mzHashTableFree(HashTable* pHashTable) +{ + if (pHashTable == NULL) + return; + mzHashTableClear(pHashTable); + free(pHashTable->pEntries); + free(pHashTable); +} + +#ifndef NDEBUG +/* + * Count up the number of tombstone entries in the hash table. + */ +static int countTombStones(HashTable* pHashTable) +{ + int i, count; + + for (count = i = 0; i < pHashTable->tableSize; i++) { + if (pHashTable->pEntries[i].data == HASH_TOMBSTONE) + count++; + } + return count; +} +#endif + +/* + * Resize a hash table. We do this when adding an entry increased the + * size of the table beyond its comfy limit. + * + * This essentially requires re-inserting all elements into the new storage. + * + * If multiple threads can access the hash table, the table's lock should + * have been grabbed before issuing the "lookup+add" call that led to the + * resize, so we don't have a synchronization problem here. + */ +static bool resizeHash(HashTable* pHashTable, int newSize) +{ + HashEntry* pNewEntries; + int i; + + assert(countTombStones(pHashTable) == pHashTable->numDeadEntries); + //LOGI("before: dead=%d\n", pHashTable->numDeadEntries); + + pNewEntries = (HashEntry*) calloc(newSize, sizeof(HashTable)); + if (pNewEntries == NULL) + return false; + + for (i = 0; i < pHashTable->tableSize; i++) { + void* data = pHashTable->pEntries[i].data; + if (data != NULL && data != HASH_TOMBSTONE) { + int hashValue = pHashTable->pEntries[i].hashValue; + int newIdx; + + /* probe for new spot, wrapping around */ + newIdx = hashValue & (newSize-1); + while (pNewEntries[newIdx].data != NULL) + newIdx = (newIdx + 1) & (newSize-1); + + pNewEntries[newIdx].hashValue = hashValue; + pNewEntries[newIdx].data = data; + } + } + + free(pHashTable->pEntries); + pHashTable->pEntries = pNewEntries; + pHashTable->tableSize = newSize; + pHashTable->numDeadEntries = 0; + + assert(countTombStones(pHashTable) == 0); + return true; +} + +/* + * Look up an entry. + * + * We probe on collisions, wrapping around the table. + */ +void* mzHashTableLookup(HashTable* pHashTable, unsigned int itemHash, void* item, + HashCompareFunc cmpFunc, bool doAdd) +{ + HashEntry* pEntry; + HashEntry* pEnd; + void* result = NULL; + + assert(pHashTable->tableSize > 0); + assert(item != HASH_TOMBSTONE); + assert(item != NULL); + + /* jump to the first entry and probe for a match */ + pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)]; + pEnd = &pHashTable->pEntries[pHashTable->tableSize]; + while (pEntry->data != NULL) { + if (pEntry->data != HASH_TOMBSTONE && + pEntry->hashValue == itemHash && + (*cmpFunc)(pEntry->data, item) == 0) + { + /* match */ + //LOGD("+++ match on entry %d\n", pEntry - pHashTable->pEntries); + break; + } + + pEntry++; + if (pEntry == pEnd) { /* wrap around to start */ + if (pHashTable->tableSize == 1) + break; /* edge case - single-entry table */ + pEntry = pHashTable->pEntries; + } + + //LOGI("+++ look probing %d...\n", pEntry - pHashTable->pEntries); + } + + if (pEntry->data == NULL) { + if (doAdd) { + pEntry->hashValue = itemHash; + pEntry->data = item; + pHashTable->numEntries++; + + /* + * We've added an entry. See if this brings us too close to full. + */ + if ((pHashTable->numEntries+pHashTable->numDeadEntries) * LOAD_DENOM + > pHashTable->tableSize * LOAD_NUMER) + { + if (!resizeHash(pHashTable, pHashTable->tableSize * 2)) { + /* don't really have a way to indicate failure */ + LOGE("Dalvik hash resize failure\n"); + abort(); + } + /* note "pEntry" is now invalid */ + } else { + //LOGW("okay %d/%d/%d\n", + // pHashTable->numEntries, pHashTable->tableSize, + // (pHashTable->tableSize * LOAD_NUMER) / LOAD_DENOM); + } + + /* full table is bad -- search for nonexistent never halts */ + assert(pHashTable->numEntries < pHashTable->tableSize); + result = item; + } else { + assert(result == NULL); + } + } else { + result = pEntry->data; + } + + return result; +} + +/* + * Remove an entry from the table. + * + * Does NOT invoke the "free" function on the item. + */ +bool mzHashTableRemove(HashTable* pHashTable, unsigned int itemHash, void* item) +{ + HashEntry* pEntry; + HashEntry* pEnd; + + assert(pHashTable->tableSize > 0); + + /* jump to the first entry and probe for a match */ + pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)]; + pEnd = &pHashTable->pEntries[pHashTable->tableSize]; + while (pEntry->data != NULL) { + if (pEntry->data == item) { + //LOGI("+++ stepping on entry %d\n", pEntry - pHashTable->pEntries); + pEntry->data = HASH_TOMBSTONE; + pHashTable->numEntries--; + pHashTable->numDeadEntries++; + return true; + } + + pEntry++; + if (pEntry == pEnd) { /* wrap around to start */ + if (pHashTable->tableSize == 1) + break; /* edge case - single-entry table */ + pEntry = pHashTable->pEntries; + } + + //LOGI("+++ del probing %d...\n", pEntry - pHashTable->pEntries); + } + + return false; +} + +/* + * Execute a function on every entry in the hash table. + * + * If "func" returns a nonzero value, terminate early and return the value. + */ +int mzHashForeach(HashTable* pHashTable, HashForeachFunc func, void* arg) +{ + int i, val; + + for (i = 0; i < pHashTable->tableSize; i++) { + HashEntry* pEnt = &pHashTable->pEntries[i]; + + if (pEnt->data != NULL && pEnt->data != HASH_TOMBSTONE) { + val = (*func)(pEnt->data, arg); + if (val != 0) + return val; + } + } + + return 0; +} + + +/* + * Look up an entry, counting the number of times we have to probe. + * + * Returns -1 if the entry wasn't found. + */ +int countProbes(HashTable* pHashTable, unsigned int itemHash, const void* item, + HashCompareFunc cmpFunc) +{ + HashEntry* pEntry; + HashEntry* pEnd; + int count = 0; + + assert(pHashTable->tableSize > 0); + assert(item != HASH_TOMBSTONE); + assert(item != NULL); + + /* jump to the first entry and probe for a match */ + pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)]; + pEnd = &pHashTable->pEntries[pHashTable->tableSize]; + while (pEntry->data != NULL) { + if (pEntry->data != HASH_TOMBSTONE && + pEntry->hashValue == itemHash && + (*cmpFunc)(pEntry->data, item) == 0) + { + /* match */ + break; + } + + pEntry++; + if (pEntry == pEnd) { /* wrap around to start */ + if (pHashTable->tableSize == 1) + break; /* edge case - single-entry table */ + pEntry = pHashTable->pEntries; + } + + count++; + } + if (pEntry->data == NULL) + return -1; + + return count; +} + +/* + * Evaluate the amount of probing required for the specified hash table. + * + * We do this by running through all entries in the hash table, computing + * the hash value and then doing a lookup. + * + * The caller should lock the table before calling here. + */ +void mzHashTableProbeCount(HashTable* pHashTable, HashCalcFunc calcFunc, + HashCompareFunc cmpFunc) +{ + int numEntries, minProbe, maxProbe, totalProbe; + HashIter iter; + + numEntries = maxProbe = totalProbe = 0; + minProbe = 65536*32767; + + for (mzHashIterBegin(pHashTable, &iter); !mzHashIterDone(&iter); + mzHashIterNext(&iter)) + { + const void* data = (const void*)mzHashIterData(&iter); + int count; + + count = countProbes(pHashTable, (*calcFunc)(data), data, cmpFunc); + + numEntries++; + + if (count < minProbe) + minProbe = count; + if (count > maxProbe) + maxProbe = count; + totalProbe += count; + } + + LOGI("Probe: min=%d max=%d, total=%d in %d (%d), avg=%.3f\n", + minProbe, maxProbe, totalProbe, numEntries, pHashTable->tableSize, + (float) totalProbe / (float) numEntries); +} diff --git a/minzip/Hash.h b/minzip/Hash.h new file mode 100644 index 0000000..8194537 --- /dev/null +++ b/minzip/Hash.h @@ -0,0 +1,186 @@ +/* + * Copyright 2007 The Android Open Source Project + * + * General purpose hash table, used for finding classes, methods, etc. + * + * When the number of elements reaches 3/4 of the table's capacity, the + * table will be resized. + */ +#ifndef _MINZIP_HASH +#define _MINZIP_HASH + +#include "inline_magic.h" + +#include +#include +#include + +/* compute the hash of an item with a specific type */ +typedef unsigned int (*HashCompute)(const void* item); + +/* + * Compare a hash entry with a "loose" item after their hash values match. + * Returns { <0, 0, >0 } depending on ordering of items (same semantics + * as strcmp()). + */ +typedef int (*HashCompareFunc)(const void* tableItem, const void* looseItem); + +/* + * This function will be used to free entries in the table. This can be + * NULL if no free is required, free(), or a custom function. + */ +typedef void (*HashFreeFunc)(void* ptr); + +/* + * Used by mzHashForeach(). + */ +typedef int (*HashForeachFunc)(void* data, void* arg); + +/* + * One entry in the hash table. "data" values are expected to be (or have + * the same characteristics as) valid pointers. In particular, a NULL + * value for "data" indicates an empty slot, and HASH_TOMBSTONE indicates + * a no-longer-used slot that must be stepped over during probing. + * + * Attempting to add a NULL or tombstone value is an error. + * + * When an entry is released, we will call (HashFreeFunc)(entry->data). + */ +typedef struct HashEntry { + unsigned int hashValue; + void* data; +} HashEntry; + +#define HASH_TOMBSTONE ((void*) 0xcbcacccd) // invalid ptr value + +/* + * Expandable hash table. + * + * This structure should be considered opaque. + */ +typedef struct HashTable { + int tableSize; /* must be power of 2 */ + int numEntries; /* current #of "live" entries */ + int numDeadEntries; /* current #of tombstone entries */ + HashEntry* pEntries; /* array on heap */ + HashFreeFunc freeFunc; +} HashTable; + +/* + * Create and initialize a HashTable structure, using "initialSize" as + * a basis for the initial capacity of the table. (The actual initial + * table size may be adjusted upward.) If you know exactly how many + * elements the table will hold, pass the result from mzHashSize() in.) + * + * Returns "false" if unable to allocate the table. + */ +HashTable* mzHashTableCreate(size_t initialSize, HashFreeFunc freeFunc); + +/* + * Compute the capacity needed for a table to hold "size" elements. Use + * this when you know ahead of time how many elements the table will hold. + * Pass this value into mzHashTableCreate() to ensure that you can add + * all elements without needing to reallocate the table. + */ +size_t mzHashSize(size_t size); + +/* + * Clear out a hash table, freeing the contents of any used entries. + */ +void mzHashTableClear(HashTable* pHashTable); + +/* + * Free a hash table. + */ +void mzHashTableFree(HashTable* pHashTable); + +/* + * Get #of entries in hash table. + */ +INLINE int mzHashTableNumEntries(HashTable* pHashTable) { + return pHashTable->numEntries; +} + +/* + * Get total size of hash table (for memory usage calculations). + */ +INLINE int mzHashTableMemUsage(HashTable* pHashTable) { + return sizeof(HashTable) + pHashTable->tableSize * sizeof(HashEntry); +} + +/* + * Look up an entry in the table, possibly adding it if it's not there. + * + * If "item" is not found, and "doAdd" is false, NULL is returned. + * Otherwise, a pointer to the found or added item is returned. (You can + * tell the difference by seeing if return value == item.) + * + * An "add" operation may cause the entire table to be reallocated. + */ +void* mzHashTableLookup(HashTable* pHashTable, unsigned int itemHash, void* item, + HashCompareFunc cmpFunc, bool doAdd); + +/* + * Remove an item from the hash table, given its "data" pointer. Does not + * invoke the "free" function; just detaches it from the table. + */ +bool mzHashTableRemove(HashTable* pHashTable, unsigned int hash, void* item); + +/* + * Execute "func" on every entry in the hash table. + * + * If "func" returns a nonzero value, terminate early and return the value. + */ +int mzHashForeach(HashTable* pHashTable, HashForeachFunc func, void* arg); + +/* + * An alternative to mzHashForeach(), using an iterator. + * + * Use like this: + * HashIter iter; + * for (mzHashIterBegin(hashTable, &iter); !mzHashIterDone(&iter); + * mzHashIterNext(&iter)) + * { + * MyData* data = (MyData*)mzHashIterData(&iter); + * } + */ +typedef struct HashIter { + void* data; + HashTable* pHashTable; + int idx; +} HashIter; +INLINE void mzHashIterNext(HashIter* pIter) { + int i = pIter->idx +1; + int lim = pIter->pHashTable->tableSize; + for ( ; i < lim; i++) { + void* data = pIter->pHashTable->pEntries[i].data; + if (data != NULL && data != HASH_TOMBSTONE) + break; + } + pIter->idx = i; +} +INLINE void mzHashIterBegin(HashTable* pHashTable, HashIter* pIter) { + pIter->pHashTable = pHashTable; + pIter->idx = -1; + mzHashIterNext(pIter); +} +INLINE bool mzHashIterDone(HashIter* pIter) { + return (pIter->idx >= pIter->pHashTable->tableSize); +} +INLINE void* mzHashIterData(HashIter* pIter) { + assert(pIter->idx >= 0 && pIter->idx < pIter->pHashTable->tableSize); + return pIter->pHashTable->pEntries[pIter->idx].data; +} + + +/* + * Evaluate hash table performance by examining the number of times we + * have to probe for an entry. + * + * The caller should lock the table beforehand. + */ +typedef unsigned int (*HashCalcFunc)(const void* item); +void mzHashTableProbeCount(HashTable* pHashTable, HashCalcFunc calcFunc, + HashCompareFunc cmpFunc); + +#endif /*_MINZIP_HASH*/ diff --git a/minzip/Inlines.c b/minzip/Inlines.c new file mode 100644 index 0000000..91f8775 --- /dev/null +++ b/minzip/Inlines.c @@ -0,0 +1,25 @@ +/* + * 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. + */ + +/* Make sure that non-inlined versions of INLINED-marked functions + * exist so that debug builds (which don't generally do inlining) + * don't break. + */ +#define MINZIP_GENERATE_INLINES 1 +#include "Bits.h" +#include "Hash.h" +#include "SysUtil.h" +#include "Zip.h" diff --git a/minzip/Log.h b/minzip/Log.h new file mode 100644 index 0000000..36e62f5 --- /dev/null +++ b/minzip/Log.h @@ -0,0 +1,207 @@ +// +// Copyright 2005 The Android Open Source Project +// +// C/C++ logging functions. See the logging documentation for API details. +// +// We'd like these to be available from C code (in case we import some from +// somewhere), so this has a C interface. +// +// The output will be correct when the log file is shared between multiple +// threads and/or multiple processes so long as the operating system +// supports O_APPEND. These calls have mutex-protected data structures +// and so are NOT reentrant. Do not use LOG in a signal handler. +// +#ifndef _MINZIP_LOG_H +#define _MINZIP_LOG_H + +#include + +// --------------------------------------------------------------------- + +/* + * Normally we strip LOGV (VERBOSE messages) from release builds. + * You can modify this (for example with "#define LOG_NDEBUG 0" + * at the top of your source file) to change that behavior. + */ +#ifndef LOG_NDEBUG +#ifdef NDEBUG +#define LOG_NDEBUG 1 +#else +#define LOG_NDEBUG 0 +#endif +#endif + +/* + * This is the local tag used for the following simplified + * logging macros. You can change this preprocessor definition + * before using the other macros to change the tag. + */ +#ifndef LOG_TAG +#define LOG_TAG NULL +#endif + +// --------------------------------------------------------------------- + +/* + * Simplified macro to send a verbose log message using the current LOG_TAG. + */ +#ifndef LOGV +#if LOG_NDEBUG +#define LOGV(...) ((void)0) +#else +#define LOGV(...) ((void)LOG(LOG_VERBOSE, LOG_TAG, __VA_ARGS__)) +#endif +#endif + +#define CONDITION(cond) (__builtin_expect((cond)!=0, 0)) + +#ifndef LOGV_IF +#if LOG_NDEBUG +#define LOGV_IF(cond, ...) ((void)0) +#else +#define LOGV_IF(cond, ...) \ + ( (CONDITION(cond)) \ + ? ((void)LOG(LOG_VERBOSE, LOG_TAG, __VA_ARGS__)) \ + : (void)0 ) +#endif +#endif + +#define LOGVV LOGV +#define LOGVV_IF LOGV_IF + +/* + * Simplified macro to send a debug log message using the current LOG_TAG. + */ +#ifndef LOGD +#define LOGD(...) ((void)LOG(LOG_DEBUG, LOG_TAG, __VA_ARGS__)) +#endif + +#ifndef LOGD_IF +#define LOGD_IF(cond, ...) \ + ( (CONDITION(cond)) \ + ? ((void)LOG(LOG_DEBUG, LOG_TAG, __VA_ARGS__)) \ + : (void)0 ) +#endif + +/* + * Simplified macro to send an info log message using the current LOG_TAG. + */ +#ifndef LOGI +#define LOGI(...) ((void)LOG(LOG_INFO, LOG_TAG, __VA_ARGS__)) +#endif + +#ifndef LOGI_IF +#define LOGI_IF(cond, ...) \ + ( (CONDITION(cond)) \ + ? ((void)LOG(LOG_INFO, LOG_TAG, __VA_ARGS__)) \ + : (void)0 ) +#endif + +/* + * Simplified macro to send a warning log message using the current LOG_TAG. + */ +#ifndef LOGW +#define LOGW(...) ((void)LOG(LOG_WARN, LOG_TAG, __VA_ARGS__)) +#endif + +#ifndef LOGW_IF +#define LOGW_IF(cond, ...) \ + ( (CONDITION(cond)) \ + ? ((void)LOG(LOG_WARN, LOG_TAG, __VA_ARGS__)) \ + : (void)0 ) +#endif + +/* + * Simplified macro to send an error log message using the current LOG_TAG. + */ +#ifndef LOGE +#define LOGE(...) ((void)LOG(LOG_ERROR, LOG_TAG, __VA_ARGS__)) +#endif + +#ifndef LOGE_IF +#define LOGE_IF(cond, ...) \ + ( (CONDITION(cond)) \ + ? ((void)LOG(LOG_ERROR, LOG_TAG, __VA_ARGS__)) \ + : (void)0 ) +#endif + + +/* + * Conditional based on whether the current LOG_TAG is enabled at + * verbose priority. + */ +#ifndef IF_LOGV +#if LOG_NDEBUG +#define IF_LOGV() if (false) +#else +#define IF_LOGV() IF_LOG(LOG_VERBOSE, LOG_TAG) +#endif +#endif + +/* + * Conditional based on whether the current LOG_TAG is enabled at + * debug priority. + */ +#ifndef IF_LOGD +#define IF_LOGD() IF_LOG(LOG_DEBUG, LOG_TAG) +#endif + +/* + * Conditional based on whether the current LOG_TAG is enabled at + * info priority. + */ +#ifndef IF_LOGI +#define IF_LOGI() IF_LOG(LOG_INFO, LOG_TAG) +#endif + +/* + * Conditional based on whether the current LOG_TAG is enabled at + * warn priority. + */ +#ifndef IF_LOGW +#define IF_LOGW() IF_LOG(LOG_WARN, LOG_TAG) +#endif + +/* + * Conditional based on whether the current LOG_TAG is enabled at + * error priority. + */ +#ifndef IF_LOGE +#define IF_LOGE() IF_LOG(LOG_ERROR, LOG_TAG) +#endif + +// --------------------------------------------------------------------- + +/* + * Basic log message macro. + * + * Example: + * LOG(LOG_WARN, NULL, "Failed with error %d", errno); + * + * The second argument may be NULL or "" to indicate the "global" tag. + * + * Non-gcc probably won't have __FUNCTION__. It's not vital. gcc also + * offers __PRETTY_FUNCTION__, which is rather more than we need. + */ +#ifndef LOG +#define LOG(priority, tag, ...) \ + LOG_PRI(ANDROID_##priority, tag, __VA_ARGS__) +#endif + +/* + * Log macro that allows you to specify a number for the priority. + */ +#ifndef LOG_PRI +#define LOG_PRI(priority, tag, ...) \ + printf(tag ": " __VA_ARGS__) +#endif + +/* + * Conditional given a desired logging priority and tag. + */ +#ifndef IF_LOG +#define IF_LOG(priority, tag) \ + if (1) +#endif + +#endif // _MINZIP_LOG_H diff --git a/minzip/SysUtil.c b/minzip/SysUtil.c new file mode 100644 index 0000000..49a2522 --- /dev/null +++ b/minzip/SysUtil.c @@ -0,0 +1,212 @@ +/* + * Copyright 2006 The Android Open Source Project + * + * System utilities. + */ +#include +#include +#include +#include +#include +#include +#include +#include + +#define LOG_TAG "minzip" +#include "Log.h" +#include "SysUtil.h" + +/* + * Having trouble finding a portable way to get this. sysconf(_SC_PAGE_SIZE) + * seems appropriate, but we don't have that on the device. Some systems + * have getpagesize(2), though the linux man page has some odd cautions. + */ +#define DEFAULT_PAGE_SIZE 4096 + + +/* + * Create an anonymous shared memory segment large enough to hold "length" + * bytes. The actual segment may be larger because mmap() operates on + * page boundaries (usually 4K). + */ +static void* sysCreateAnonShmem(size_t length) +{ + void* ptr; + + ptr = mmap(NULL, length, PROT_READ | PROT_WRITE, + MAP_SHARED | MAP_ANON, -1, 0); + if (ptr == MAP_FAILED) { + LOGW("mmap(%d, RW, SHARED|ANON) failed: %s\n", (int) length, + strerror(errno)); + return NULL; + } + + return ptr; +} + +static int getFileStartAndLength(int fd, off_t *start_, size_t *length_) +{ + off_t start, end; + size_t length; + + assert(start_ != NULL); + assert(length_ != NULL); + + start = lseek(fd, 0L, SEEK_CUR); + end = lseek(fd, 0L, SEEK_END); + (void) lseek(fd, start, SEEK_SET); + + if (start == (off_t) -1 || end == (off_t) -1) { + LOGE("could not determine length of file\n"); + return -1; + } + + length = end - start; + if (length == 0) { + LOGE("file is empty\n"); + return -1; + } + + *start_ = start; + *length_ = length; + + return 0; +} + +/* + * Pull the contents of a file into an new shared memory segment. We grab + * everything from fd's current offset on. + * + * We need to know the length ahead of time so we can allocate a segment + * of sufficient size. + */ +int sysLoadFileInShmem(int fd, MemMapping* pMap) +{ + off_t start; + size_t length, actual; + void* memPtr; + + assert(pMap != NULL); + + if (getFileStartAndLength(fd, &start, &length) < 0) + return -1; + + memPtr = sysCreateAnonShmem(length); + if (memPtr == NULL) + return -1; + + actual = read(fd, memPtr, length); + if (actual != length) { + LOGE("only read %d of %d bytes\n", (int) actual, (int) length); + sysReleaseShmem(pMap); + return -1; + } + + pMap->baseAddr = pMap->addr = memPtr; + pMap->baseLength = pMap->length = length; + + return 0; +} + +/* + * Map a file (from fd's current offset) into a shared, read-only memory + * segment. The file offset must be a multiple of the page size. + * + * On success, returns 0 and fills out "pMap". On failure, returns a nonzero + * value and does not disturb "pMap". + */ +int sysMapFileInShmem(int fd, MemMapping* pMap) +{ + off_t start; + size_t length; + void* memPtr; + + assert(pMap != NULL); + + if (getFileStartAndLength(fd, &start, &length) < 0) + return -1; + + memPtr = mmap(NULL, length, PROT_READ, MAP_FILE | MAP_SHARED, fd, start); + if (memPtr == MAP_FAILED) { + LOGW("mmap(%d, R, FILE|SHARED, %d, %d) failed: %s\n", (int) length, + fd, (int) start, strerror(errno)); + return -1; + } + + pMap->baseAddr = pMap->addr = memPtr; + pMap->baseLength = pMap->length = length; + + return 0; +} + +/* + * Map part of a file (from fd's current offset) into a shared, read-only + * memory segment. + * + * On success, returns 0 and fills out "pMap". On failure, returns a nonzero + * value and does not disturb "pMap". + */ +int sysMapFileSegmentInShmem(int fd, off_t start, long length, + MemMapping* pMap) +{ + off_t dummy; + size_t fileLength, actualLength; + off_t actualStart; + int adjust; + void* memPtr; + + assert(pMap != NULL); + + if (getFileStartAndLength(fd, &dummy, &fileLength) < 0) + return -1; + + if (start + length > (long)fileLength) { + LOGW("bad segment: st=%d len=%ld flen=%d\n", + (int) start, length, (int) fileLength); + return -1; + } + + /* adjust to be page-aligned */ + adjust = start % DEFAULT_PAGE_SIZE; + actualStart = start - adjust; + actualLength = length + adjust; + + memPtr = mmap(NULL, actualLength, PROT_READ, MAP_FILE | MAP_SHARED, + fd, actualStart); + if (memPtr == MAP_FAILED) { + LOGW("mmap(%d, R, FILE|SHARED, %d, %d) failed: %s\n", + (int) actualLength, fd, (int) actualStart, strerror(errno)); + return -1; + } + + pMap->baseAddr = memPtr; + pMap->baseLength = actualLength; + pMap->addr = (char*)memPtr + adjust; + pMap->length = length; + + LOGVV("mmap seg (st=%d ln=%d): bp=%p bl=%d ad=%p ln=%d\n", + (int) start, (int) length, + pMap->baseAddr, (int) pMap->baseLength, + pMap->addr, (int) pMap->length); + + return 0; +} + +/* + * Release a memory mapping. + */ +void sysReleaseShmem(MemMapping* pMap) +{ + if (pMap->baseAddr == NULL && pMap->baseLength == 0) + return; + + if (munmap(pMap->baseAddr, pMap->baseLength) < 0) { + LOGW("munmap(%p, %d) failed: %s\n", + pMap->baseAddr, (int)pMap->baseLength, strerror(errno)); + } else { + LOGV("munmap(%p, %d) succeeded\n", pMap->baseAddr, pMap->baseLength); + pMap->baseAddr = NULL; + pMap->baseLength = 0; + } +} + diff --git a/minzip/SysUtil.h b/minzip/SysUtil.h new file mode 100644 index 0000000..ec3a4bc --- /dev/null +++ b/minzip/SysUtil.h @@ -0,0 +1,61 @@ +/* + * Copyright 2006 The Android Open Source Project + * + * System utilities. + */ +#ifndef _MINZIP_SYSUTIL +#define _MINZIP_SYSUTIL + +#include "inline_magic.h" + +#include + +/* + * Use this to keep track of mapped segments. + */ +typedef struct MemMapping { + void* addr; /* start of data */ + size_t length; /* length of data */ + + void* baseAddr; /* page-aligned base address */ + size_t baseLength; /* length of mapping */ +} MemMapping; + +/* copy a map */ +INLINE void sysCopyMap(MemMapping* dst, const MemMapping* src) { + *dst = *src; +} + +/* + * Load a file into a new shared memory segment. All data from the current + * offset to the end of the file is pulled in. + * + * The segment is read-write, allowing VM fixups. (It should be modified + * to support .gz/.zip compressed data.) + * + * On success, "pMap" is filled in, and zero is returned. + */ +int sysLoadFileInShmem(int fd, MemMapping* pMap); + +/* + * Map a file (from fd's current offset) into a shared, + * read-only memory segment. + * + * On success, "pMap" is filled in, and zero is returned. + */ +int sysMapFileInShmem(int fd, MemMapping* pMap); + +/* + * Like sysMapFileInShmem, but on only part of a file. + */ +int sysMapFileSegmentInShmem(int fd, off_t start, long length, + MemMapping* pMap); + +/* + * Release the pages associated with a shared memory segment. + * + * This does not free "pMap"; it just releases the memory. + */ +void sysReleaseShmem(MemMapping* pMap); + +#endif /*_MINZIP_SYSUTIL*/ diff --git a/minzip/Zip.c b/minzip/Zip.c new file mode 100644 index 0000000..100c833 --- /dev/null +++ b/minzip/Zip.c @@ -0,0 +1,1098 @@ +/* + * Copyright 2006 The Android Open Source Project + * + * Simple Zip file support. + */ +#include "safe_iop.h" +#include "zlib.h" + +#include +#include +#include +#include // for uintptr_t +#include +#include // for S_ISLNK() +#include + +#define LOG_TAG "minzip" +#include "Zip.h" +#include "Bits.h" +#include "Log.h" +#include "DirUtil.h" + +#undef NDEBUG // do this after including Log.h +#include + +#define SORT_ENTRIES 1 + +/* + * Offset and length constants (java.util.zip naming convention). + */ +enum { + CENSIG = 0x02014b50, // PK12 + CENHDR = 46, + + CENVEM = 4, + CENVER = 6, + CENFLG = 8, + CENHOW = 10, + CENTIM = 12, + CENCRC = 16, + CENSIZ = 20, + CENLEN = 24, + CENNAM = 28, + CENEXT = 30, + CENCOM = 32, + CENDSK = 34, + CENATT = 36, + CENATX = 38, + CENOFF = 42, + + ENDSIG = 0x06054b50, // PK56 + ENDHDR = 22, + + ENDSUB = 8, + ENDTOT = 10, + ENDSIZ = 12, + ENDOFF = 16, + ENDCOM = 20, + + EXTSIG = 0x08074b50, // PK78 + EXTHDR = 16, + + EXTCRC = 4, + EXTSIZ = 8, + EXTLEN = 12, + + LOCSIG = 0x04034b50, // PK34 + LOCHDR = 30, + + LOCVER = 4, + LOCFLG = 6, + LOCHOW = 8, + LOCTIM = 10, + LOCCRC = 14, + LOCSIZ = 18, + LOCLEN = 22, + LOCNAM = 26, + LOCEXT = 28, + + STORED = 0, + DEFLATED = 8, + + CENVEM_UNIX = 3 << 8, // the high byte of CENVEM +}; + + +/* + * For debugging, dump the contents of a ZipEntry. + */ +#if 0 +static void dumpEntry(const ZipEntry* pEntry) +{ + LOGI(" %p '%.*s'\n", pEntry->fileName,pEntry->fileNameLen,pEntry->fileName); + LOGI(" off=%ld comp=%ld uncomp=%ld how=%d\n", pEntry->offset, + pEntry->compLen, pEntry->uncompLen, pEntry->compression); +} +#endif + +/* + * (This is a mzHashTableLookup callback.) + * + * Compare two ZipEntry structs, by name. + */ +static int hashcmpZipEntry(const void* ventry1, const void* ventry2) +{ + const ZipEntry* entry1 = (const ZipEntry*) ventry1; + const ZipEntry* entry2 = (const ZipEntry*) ventry2; + + if (entry1->fileNameLen != entry2->fileNameLen) + return entry1->fileNameLen - entry2->fileNameLen; + return memcmp(entry1->fileName, entry2->fileName, entry1->fileNameLen); +} + +/* + * (This is a mzHashTableLookup callback.) + * + * find a ZipEntry struct by name. + */ +static int hashcmpZipName(const void* ventry, const void* vname) +{ + const ZipEntry* entry = (const ZipEntry*) ventry; + const char* name = (const char*) vname; + unsigned int nameLen = strlen(name); + + if (entry->fileNameLen != nameLen) + return entry->fileNameLen - nameLen; + return memcmp(entry->fileName, name, nameLen); +} + +/* + * Compute the hash code for a ZipEntry filename. + * + * Not expected to be compatible with any other hash function, so we init + * to 2 to ensure it doesn't happen to match. + */ +static unsigned int computeHash(const char* name, int nameLen) +{ + unsigned int hash = 2; + + while (nameLen--) + hash = hash * 31 + *name++; + + return hash; +} + +static void addEntryToHashTable(HashTable* pHash, ZipEntry* pEntry) +{ + unsigned int itemHash = computeHash(pEntry->fileName, pEntry->fileNameLen); + const ZipEntry* found; + + found = (const ZipEntry*)mzHashTableLookup(pHash, + itemHash, pEntry, hashcmpZipEntry, true); + if (found != pEntry) { + LOGW("WARNING: duplicate entry '%.*s' in Zip\n", + found->fileNameLen, found->fileName); + /* keep going */ + } +} + +static int validFilename(const char *fileName, unsigned int fileNameLen) +{ + // Forbid super long filenames. + if (fileNameLen >= PATH_MAX) { + LOGW("Filename too long (%d chatacters)\n", fileNameLen); + return 0; + } + + // Require all characters to be printable ASCII (no NUL, no UTF-8, etc). + unsigned int i; + for (i = 0; i < fileNameLen; ++i) { + if (fileName[i] < 32 || fileName[i] >= 127) { + LOGW("Filename contains invalid character '\%03o'\n", fileName[i]); + return 0; + } + } + + return 1; +} + +/* + * Parse the contents of a Zip archive. After confirming that the file + * is in fact a Zip, we scan out the contents of the central directory and + * store it in a hash table. + * + * Returns "true" on success. + */ +static bool parseZipArchive(ZipArchive* pArchive, const MemMapping* pMap) +{ + bool result = false; + const unsigned char* ptr; + 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 (LOCSIG) or, if the archive doesn't + * have any files in it, the end-of-central-directory signature (ENDSIG). + */ + val = get4LE(pMap->addr); + if (val == ENDSIG) { + LOGI("Found Zip archive, but it looks empty\n"); + goto bail; + } else if (val != LOCSIG) { + 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 = pMap->addr + pMap->length - ENDHDR; + + while (ptr >= (const unsigned char*) pMap->addr) { + if (*ptr == (ENDSIG & 0xff) && get4LE(ptr) == ENDSIG) + break; + ptr--; + } + if (ptr < (const unsigned char*) pMap->addr) { + 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. + */ + numEntries = get2LE(ptr + ENDSUB); + cdOffset = get4LE(ptr + ENDOFF); + + LOGVV("numEntries=%d cdOffset=%d\n", numEntries, cdOffset); + if (numEntries == 0 || cdOffset >= pMap->length) { + LOGW("Invalid entries=%d offset=%d (len=%zd)\n", + numEntries, cdOffset, pMap->length); + goto bail; + } + + /* + * Create data structures to hold entries. + */ + pArchive->numEntries = numEntries; + pArchive->pEntries = (ZipEntry*) calloc(numEntries, sizeof(ZipEntry)); + pArchive->pHash = mzHashTableCreate(mzHashSize(numEntries), NULL); + if (pArchive->pEntries == NULL || pArchive->pHash == NULL) + goto bail; + + ptr = pMap->addr + cdOffset; + for (i = 0; i < numEntries; i++) { + ZipEntry* pEntry; + unsigned int fileNameLen, extraLen, commentLen, localHdrOffset; + const unsigned char* localHdr; + const char *fileName; + + if (ptr + CENHDR > (const unsigned char*)pMap->addr + pMap->length) { + LOGW("Ran off the end (at %d)\n", i); + goto bail; + } + if (get4LE(ptr) != CENSIG) { + LOGW("Missed a central dir sig (at %d)\n", i); + goto bail; + } + + localHdrOffset = get4LE(ptr + CENOFF); + fileNameLen = get2LE(ptr + CENNAM); + extraLen = get2LE(ptr + CENEXT); + commentLen = get2LE(ptr + CENCOM); + fileName = (const char*)ptr + CENHDR; + if (fileName + fileNameLen > (const char*)pMap->addr + pMap->length) { + LOGW("Filename ran off the end (at %d)\n", i); + goto bail; + } + if (!validFilename(fileName, fileNameLen)) { + LOGW("Invalid filename (at %d)\n", i); + goto bail; + } + +#if SORT_ENTRIES + /* Figure out where this entry should go (binary search). + */ + if (i > 0) { + int low, high; + + low = 0; + high = i - 1; + while (low <= high) { + int mid; + int diff; + int diffLen; + + mid = low + ((high - low) / 2); // avoid overflow + + if (pArchive->pEntries[mid].fileNameLen < fileNameLen) { + diffLen = pArchive->pEntries[mid].fileNameLen; + } else { + diffLen = fileNameLen; + } + diff = strncmp(pArchive->pEntries[mid].fileName, fileName, + diffLen); + if (diff == 0) { + diff = pArchive->pEntries[mid].fileNameLen - fileNameLen; + } + if (diff < 0) { + low = mid + 1; + } else if (diff > 0) { + high = mid - 1; + } else { + high = mid; + break; + } + } + + unsigned int target = high + 1; + assert(target <= i); + if (target != i) { + /* It belongs somewhere other than at the end of + * the list. Make some room at [target]. + */ + memmove(pArchive->pEntries + target + 1, + pArchive->pEntries + target, + (i - target) * sizeof(ZipEntry)); + } + pEntry = &pArchive->pEntries[target]; + } else { + pEntry = &pArchive->pEntries[0]; + } +#else + pEntry = &pArchive->pEntries[i]; +#endif + + //LOGI("%d: localHdr=%d fnl=%d el=%d cl=%d\n", + // i, localHdrOffset, fileNameLen, extraLen, commentLen); + + pEntry->fileNameLen = fileNameLen; + pEntry->fileName = fileName; + + pEntry->compLen = get4LE(ptr + CENSIZ); + pEntry->uncompLen = get4LE(ptr + CENLEN); + pEntry->compression = get2LE(ptr + CENHOW); + pEntry->modTime = get4LE(ptr + CENTIM); + pEntry->crc32 = get4LE(ptr + CENCRC); + + /* These two are necessary for finding the mode of the file. + */ + pEntry->versionMadeBy = get2LE(ptr + CENVEM); + if ((pEntry->versionMadeBy & 0xff00) != 0 && + (pEntry->versionMadeBy & 0xff00) != CENVEM_UNIX) + { + LOGW("Incompatible \"version made by\": 0x%02x (at %d)\n", + pEntry->versionMadeBy >> 8, i); + goto bail; + } + pEntry->externalFileAttributes = get4LE(ptr + CENATX); + + // Perform pMap->addr + localHdrOffset, ensuring that it won't + // overflow. This is needed because localHdrOffset is untrusted. + if (!safe_add((uintptr_t *)&localHdr, (uintptr_t)pMap->addr, + (uintptr_t)localHdrOffset)) { + LOGW("Integer overflow adding in parseZipArchive\n"); + goto bail; + } + if ((uintptr_t)localHdr + LOCHDR > + (uintptr_t)pMap->addr + pMap->length) { + LOGW("Bad offset to local header: %d (at %d)\n", localHdrOffset, i); + goto bail; + } + if (get4LE(localHdr) != LOCSIG) { + LOGW("Missed a local header sig (at %d)\n", i); + goto bail; + } + pEntry->offset = localHdrOffset + LOCHDR + + get2LE(localHdr + LOCNAM) + get2LE(localHdr + LOCEXT); + if (!safe_add(NULL, pEntry->offset, pEntry->compLen)) { + LOGW("Integer overflow adding in parseZipArchive\n"); + goto bail; + } + if ((size_t)pEntry->offset + pEntry->compLen > pMap->length) { + LOGW("Data ran off the end (at %d)\n", i); + goto bail; + } + +#if !SORT_ENTRIES + /* Add to hash table; no need to lock here. + * Can't do this now if we're sorting, because entries + * will move around. + */ + addEntryToHashTable(pArchive->pHash, pEntry); +#endif + + //dumpEntry(pEntry); + ptr += CENHDR + fileNameLen + extraLen + commentLen; + } + +#if SORT_ENTRIES + /* If we're sorting, we have to wait until all entries + * are in their final places, otherwise the pointers will + * probably point to the wrong things. + */ + for (i = 0; i < numEntries; i++) { + /* Add to hash table; no need to lock here. + */ + addEntryToHashTable(pArchive->pHash, &pArchive->pEntries[i]); + } +#endif + + result = true; + +bail: + if (!result) { + mzHashTableFree(pArchive->pHash); + pArchive->pHash = NULL; + } + return result; +} + +/* + * Open a Zip archive and scan out the contents. + * + * The easiest way to do this is to mmap() the whole thing and do the + * traditional backward scan for central directory. Since the EOCD is + * a relatively small bit at the end, we should end up only touching a + * small set of pages. + * + * This will be called on non-Zip files, especially during startup, so + * we don't want to be too noisy about failures. (Do we want a "quiet" + * flag?) + * + * On success, we fill out the contents of "pArchive". + */ +int mzOpenZipArchive(const char* fileName, ZipArchive* pArchive) +{ + MemMapping map; + int err; + + LOGV("Opening archive '%s' %p\n", fileName, pArchive); + + map.addr = NULL; + memset(pArchive, 0, sizeof(*pArchive)); + + pArchive->fd = open(fileName, O_RDONLY, 0); + if (pArchive->fd < 0) { + err = errno ? errno : -1; + LOGV("Unable to open '%s': %s\n", fileName, strerror(err)); + goto bail; + } + + if (sysMapFileInShmem(pArchive->fd, &map) != 0) { + err = -1; + LOGW("Map of '%s' failed\n", fileName); + goto bail; + } + + if (map.length < ENDHDR) { + err = -1; + LOGV("File '%s' too small to be zip (%zd)\n", fileName, map.length); + goto bail; + } + + if (!parseZipArchive(pArchive, &map)) { + err = -1; + LOGV("Parsing '%s' failed\n", fileName); + goto bail; + } + + err = 0; + sysCopyMap(&pArchive->map, &map); + map.addr = NULL; + +bail: + if (err != 0) + mzCloseZipArchive(pArchive); + if (map.addr != NULL) + sysReleaseShmem(&map); + return err; +} + +/* + * Close a ZipArchive, closing the file and freeing the contents. + * + * NOTE: the ZipArchive may not have been fully created. + */ +void mzCloseZipArchive(ZipArchive* pArchive) +{ + LOGV("Closing archive %p\n", pArchive); + + if (pArchive->fd >= 0) + close(pArchive->fd); + if (pArchive->map.addr != NULL) + sysReleaseShmem(&pArchive->map); + + free(pArchive->pEntries); + + mzHashTableFree(pArchive->pHash); + + pArchive->fd = -1; + pArchive->pHash = NULL; + pArchive->pEntries = NULL; +} + +/* + * Find a matching entry. + * + * Returns NULL if no matching entry found. + */ +const ZipEntry* mzFindZipEntry(const ZipArchive* pArchive, + const char* entryName) +{ + unsigned int itemHash = computeHash(entryName, strlen(entryName)); + + return (const ZipEntry*)mzHashTableLookup(pArchive->pHash, + itemHash, (char*) entryName, hashcmpZipName, false); +} + +/* + * Return true if the entry is a symbolic link. + */ +bool mzIsZipEntrySymlink(const ZipEntry* pEntry) +{ + if ((pEntry->versionMadeBy & 0xff00) == CENVEM_UNIX) { + return S_ISLNK(pEntry->externalFileAttributes >> 16); + } + return false; +} + +/* Call processFunction on the uncompressed data of a STORED entry. + */ +static bool processStoredEntry(const ZipArchive *pArchive, + const ZipEntry *pEntry, ProcessZipEntryContentsFunction processFunction, + void *cookie) +{ + size_t bytesLeft = pEntry->compLen; + while (bytesLeft > 0) { + unsigned char buf[32 * 1024]; + ssize_t n; + size_t count; + bool ret; + + count = bytesLeft; + if (count > sizeof(buf)) { + count = sizeof(buf); + } + n = read(pArchive->fd, buf, count); + if (n < 0 || (size_t)n != count) { + LOGE("Can't read %zu bytes from zip file: %ld\n", count, n); + return false; + } + ret = processFunction(buf, n, cookie); + if (!ret) { + return false; + } + bytesLeft -= count; + } + return true; +} + +static bool processDeflatedEntry(const ZipArchive *pArchive, + const ZipEntry *pEntry, ProcessZipEntryContentsFunction processFunction, + void *cookie) +{ + long result = -1; + unsigned char readBuf[32 * 1024]; + unsigned char procBuf[32 * 1024]; + z_stream zstream; + int zerr; + long compRemaining; + + compRemaining = pEntry->compLen; + + /* + * Initialize the zlib stream. + */ + memset(&zstream, 0, sizeof(zstream)); + zstream.zalloc = Z_NULL; + zstream.zfree = Z_NULL; + zstream.opaque = Z_NULL; + zstream.next_in = NULL; + zstream.avail_in = 0; + zstream.next_out = (Bytef*) procBuf; + zstream.avail_out = sizeof(procBuf); + 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 data. + */ + do { + /* read as much as we can */ + if (zstream.avail_in == 0) { + long getSize = (compRemaining > (long)sizeof(readBuf)) ? + (long)sizeof(readBuf) : compRemaining; + LOGVV("+++ reading %ld bytes (%ld left)\n", + getSize, compRemaining); + + int cc = read(pArchive->fd, readBuf, getSize); + if (cc != (int) getSize) { + LOGW("inflate read failed (%d vs %ld)\n", cc, getSize); + goto z_bail; + } + + compRemaining -= getSize; + + zstream.next_in = readBuf; + zstream.avail_in = getSize; + } + + /* uncompress the data */ + zerr = inflate(&zstream, Z_NO_FLUSH); + if (zerr != Z_OK && zerr != Z_STREAM_END) { + LOGD("zlib inflate call failed (zerr=%d)\n", zerr); + 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(procBuf))) + { + long procSize = zstream.next_out - procBuf; + LOGVV("+++ processing %d bytes\n", (int) procSize); + bool ret = processFunction(procBuf, procSize, cookie); + if (!ret) { + LOGW("Process function elected to fail (in inflate)\n"); + goto z_bail; + } + + zstream.next_out = procBuf; + zstream.avail_out = sizeof(procBuf); + } + } while (zerr == Z_OK); + + assert(zerr == Z_STREAM_END); /* other errors should've been caught */ + + // success! + result = zstream.total_out; + +z_bail: + inflateEnd(&zstream); /* free up any allocated structures */ + +bail: + if (result != pEntry->uncompLen) { + if (result != -1) // error already shown? + LOGW("Size mismatch on inflated file (%ld vs %ld)\n", + result, pEntry->uncompLen); + return false; + } + return true; +} + +/* + * Stream the uncompressed data through the supplied function, + * passing cookie to it each time it gets called. processFunction + * may be called more than once. + * + * If processFunction returns false, the operation is abandoned and + * mzProcessZipEntryContents() immediately returns false. + * + * This is useful for calculating the hash of an entry's uncompressed contents. + */ +bool mzProcessZipEntryContents(const ZipArchive *pArchive, + const ZipEntry *pEntry, ProcessZipEntryContentsFunction processFunction, + void *cookie) +{ + bool ret = false; + off_t oldOff; + + /* save current offset */ + oldOff = lseek(pArchive->fd, 0, SEEK_CUR); + + /* Seek to the beginning of the entry's compressed data. */ + lseek(pArchive->fd, pEntry->offset, SEEK_SET); + + switch (pEntry->compression) { + case STORED: + ret = processStoredEntry(pArchive, pEntry, processFunction, cookie); + break; + case DEFLATED: + ret = processDeflatedEntry(pArchive, pEntry, processFunction, cookie); + break; + default: + LOGE("Unsupported compression type %d for entry '%s'\n", + pEntry->compression, pEntry->fileName); + break; + } + + /* restore file offset */ + lseek(pArchive->fd, oldOff, SEEK_SET); + return ret; +} + +static bool crcProcessFunction(const unsigned char *data, int dataLen, + void *crc) +{ + *(unsigned long *)crc = crc32(*(unsigned long *)crc, data, dataLen); + return true; +} + +/* + * Check the CRC on this entry; return true if it is correct. + * May do other internal checks as well. + */ +bool mzIsZipEntryIntact(const ZipArchive *pArchive, const ZipEntry *pEntry) +{ + unsigned long crc; + bool ret; + + crc = crc32(0L, Z_NULL, 0); + ret = mzProcessZipEntryContents(pArchive, pEntry, crcProcessFunction, + (void *)&crc); + if (!ret) { + LOGE("Can't calculate CRC for entry\n"); + return false; + } + if (crc != (unsigned long)pEntry->crc32) { + LOGW("CRC for entry %.*s (0x%08lx) != expected (0x%08lx)\n", + pEntry->fileNameLen, pEntry->fileName, crc, pEntry->crc32); + return false; + } + return true; +} + +typedef struct { + char *buf; + int bufLen; +} CopyProcessArgs; + +static bool copyProcessFunction(const unsigned char *data, int dataLen, + void *cookie) +{ + CopyProcessArgs *args = (CopyProcessArgs *)cookie; + if (dataLen <= args->bufLen) { + memcpy(args->buf, data, dataLen); + args->buf += dataLen; + args->bufLen -= dataLen; + return true; + } + return false; +} + +/* + * Read an entry into a buffer allocated by the caller. + */ +bool mzReadZipEntry(const ZipArchive* pArchive, const ZipEntry* pEntry, + char *buf, int bufLen) +{ + CopyProcessArgs args; + bool ret; + + args.buf = buf; + args.bufLen = bufLen; + ret = mzProcessZipEntryContents(pArchive, pEntry, copyProcessFunction, + (void *)&args); + if (!ret) { + LOGE("Can't extract entry to buffer.\n"); + return false; + } + return true; +} + +static bool writeProcessFunction(const unsigned char *data, int dataLen, + void *fd) +{ + ssize_t n = write((int)fd, data, dataLen); + if (n != dataLen) { + LOGE("Can't write %d bytes (only %ld) from zip file: %s\n", + dataLen, n, strerror(errno)); + return false; + } + return true; +} + +/* + * Uncompress "pEntry" in "pArchive" to "fd" at the current offset. + */ +bool mzExtractZipEntryToFile(const ZipArchive *pArchive, + const ZipEntry *pEntry, int fd) +{ + bool ret = mzProcessZipEntryContents(pArchive, pEntry, writeProcessFunction, + (void *)fd); + if (!ret) { + LOGE("Can't extract entry to file.\n"); + return false; + } + return true; +} + +/* Helper state to make path translation easier and less malloc-happy. + */ +typedef struct { + const char *targetDir; + const char *zipDir; + char *buf; + int targetDirLen; + int zipDirLen; + int bufLen; +} MzPathHelper; + +/* Given the values of targetDir and zipDir in the helper, + * return the target filename of the provided entry. + * The helper must be initialized first. + */ +static const char *targetEntryPath(MzPathHelper *helper, ZipEntry *pEntry) +{ + int needLen; + bool firstTime = (helper->buf == NULL); + + /* target file <-- targetDir + / + entry[zipDirLen:] + */ + needLen = helper->targetDirLen + 1 + + pEntry->fileNameLen - helper->zipDirLen + 1; + if (needLen > helper->bufLen) { + char *newBuf; + + needLen *= 2; + newBuf = (char *)realloc(helper->buf, needLen); + if (newBuf == NULL) { + return NULL; + } + helper->buf = newBuf; + helper->bufLen = needLen; + } + + /* Every path will start with the target path and a slash. + */ + if (firstTime) { + char *p = helper->buf; + memcpy(p, helper->targetDir, helper->targetDirLen); + p += helper->targetDirLen; + if (p == helper->buf || p[-1] != '/') { + helper->targetDirLen += 1; + *p++ = '/'; + } + } + + /* Replace the custom part of the path with the appropriate + * part of the entry's path. + */ + char *epath = helper->buf + helper->targetDirLen; + memcpy(epath, pEntry->fileName + helper->zipDirLen, + pEntry->fileNameLen - helper->zipDirLen); + epath += pEntry->fileNameLen - helper->zipDirLen; + *epath = '\0'; + + return helper->buf; +} + +/* + * Inflate all entries under zipDir to the directory specified by + * targetDir, which must exist and be a writable directory. + * + * The immediate children of zipDir will become the immediate + * children of targetDir; e.g., if the archive contains the entries + * + * a/b/c/one + * a/b/c/two + * a/b/c/d/three + * + * and mzExtractRecursive(a, "a/b/c", "/tmp") is called, the resulting + * files will be + * + * /tmp/one + * /tmp/two + * /tmp/d/three + * + * Returns true on success, false on failure. + */ +bool mzExtractRecursive(const ZipArchive *pArchive, + const char *zipDir, const char *targetDir, + int flags, const struct utimbuf *timestamp, + void (*callback)(const char *fn, void *), void *cookie) +{ + if (zipDir[0] == '/') { + LOGE("mzExtractRecursive(): zipDir must be a relative path.\n"); + return false; + } + if (targetDir[0] != '/') { + LOGE("mzExtractRecursive(): targetDir must be an absolute path.\n"); + return false; + } + + unsigned int zipDirLen; + char *zpath; + + zipDirLen = strlen(zipDir); + zpath = (char *)malloc(zipDirLen + 2); + if (zpath == NULL) { + LOGE("Can't allocate %d bytes for zip path\n", zipDirLen + 2); + return false; + } + /* If zipDir is empty, we'll extract the entire zip file. + * Otherwise, canonicalize the path. + */ + if (zipDirLen > 0) { + /* Make sure there's (hopefully, exactly one) slash at the + * end of the path. This way we don't need to worry about + * accidentally extracting "one/twothree" when a path like + * "one/two" is specified. + */ + memcpy(zpath, zipDir, zipDirLen); + if (zpath[zipDirLen-1] != '/') { + zpath[zipDirLen++] = '/'; + } + } + zpath[zipDirLen] = '\0'; + + /* Set up the helper structure that we'll use to assemble paths. + */ + MzPathHelper helper; + helper.targetDir = targetDir; + helper.targetDirLen = strlen(helper.targetDir); + helper.zipDir = zpath; + helper.zipDirLen = strlen(helper.zipDir); + helper.buf = NULL; + helper.bufLen = 0; + + /* Walk through the entries and extract anything whose path begins + * with zpath. +//TODO: since the entries are sorted, binary search for the first match +// and stop after the first non-match. + */ + unsigned int i; + bool seenMatch = false; + int ok = true; + for (i = 0; i < pArchive->numEntries; i++) { + ZipEntry *pEntry = pArchive->pEntries + i; + if (pEntry->fileNameLen < zipDirLen) { +//TODO: look out for a single empty directory entry that matches zpath, but +// missing the trailing slash. Most zip files seem to include +// the trailing slash, but I think it's legal to leave it off. +// e.g., zpath "a/b/", entry "a/b", with no children of the entry. + /* No chance of matching. + */ +#if SORT_ENTRIES + if (seenMatch) { + /* Since the entries are sorted, we can give up + * on the first mismatch after the first match. + */ + break; + } +#endif + continue; + } + /* If zpath is empty, this strncmp() will match everything, + * which is what we want. + */ + if (strncmp(pEntry->fileName, zpath, zipDirLen) != 0) { +#if SORT_ENTRIES + if (seenMatch) { + /* Since the entries are sorted, we can give up + * on the first mismatch after the first match. + */ + break; + } +#endif + continue; + } + /* This entry begins with zipDir, so we'll extract it. + */ + seenMatch = true; + + /* Find the target location of the entry. + */ + const char *targetFile = targetEntryPath(&helper, pEntry); + if (targetFile == NULL) { + LOGE("Can't assemble target path for \"%.*s\"\n", + pEntry->fileNameLen, pEntry->fileName); + ok = false; + break; + } + + /* With DRY_RUN set, invoke the callback but don't do anything else. + */ + if (flags & MZ_EXTRACT_DRY_RUN) { + if (callback != NULL) callback(targetFile, cookie); + continue; + } + + /* Create the file or directory. + */ +#define UNZIP_DIRMODE 0755 +#define UNZIP_FILEMODE 0644 + if (pEntry->fileName[pEntry->fileNameLen-1] == '/') { + if (!(flags & MZ_EXTRACT_FILES_ONLY)) { + int ret = dirCreateHierarchy( + targetFile, UNZIP_DIRMODE, timestamp, false); + if (ret != 0) { + LOGE("Can't create containing directory for \"%s\": %s\n", + targetFile, strerror(errno)); + ok = false; + break; + } + LOGD("Extracted dir \"%s\"\n", targetFile); + } + } else { + /* This is not a directory. First, make sure that + * the containing directory exists. + */ + int ret = dirCreateHierarchy( + targetFile, UNZIP_DIRMODE, timestamp, true); + if (ret != 0) { + LOGE("Can't create containing directory for \"%s\": %s\n", + targetFile, strerror(errno)); + ok = false; + break; + } + + /* With FILES_ONLY set, we need to ignore metadata entirely, + * so treat symlinks as regular files. + */ + if (!(flags & MZ_EXTRACT_FILES_ONLY) && mzIsZipEntrySymlink(pEntry)) { + /* The entry is a symbolic link. + * The relative target of the symlink is in the + * data section of this entry. + */ + if (pEntry->uncompLen == 0) { + LOGE("Symlink entry \"%s\" has no target\n", + targetFile); + ok = false; + break; + } + char *linkTarget = malloc(pEntry->uncompLen + 1); + if (linkTarget == NULL) { + ok = false; + break; + } + ok = mzReadZipEntry(pArchive, pEntry, linkTarget, + pEntry->uncompLen); + if (!ok) { + LOGE("Can't read symlink target for \"%s\"\n", + targetFile); + free(linkTarget); + break; + } + linkTarget[pEntry->uncompLen] = '\0'; + + /* Make the link. + */ + ret = symlink(linkTarget, targetFile); + if (ret != 0) { + LOGE("Can't symlink \"%s\" to \"%s\": %s\n", + targetFile, linkTarget, strerror(errno)); + free(linkTarget); + ok = false; + break; + } + LOGD("Extracted symlink \"%s\" -> \"%s\"\n", + targetFile, linkTarget); + free(linkTarget); + } else { + /* The entry is a regular file. + * Open the target for writing. + */ + int fd = creat(targetFile, UNZIP_FILEMODE); + if (fd < 0) { + LOGE("Can't create target file \"%s\": %s\n", + targetFile, strerror(errno)); + ok = false; + break; + } + + bool ok = mzExtractZipEntryToFile(pArchive, pEntry, fd); + close(fd); + if (!ok) { + LOGE("Error extracting \"%s\"\n", targetFile); + ok = false; + break; + } + + if (timestamp != NULL && utime(targetFile, timestamp)) { + LOGE("Error touching \"%s\"\n", targetFile); + ok = false; + break; + } + + LOGD("Extracted file \"%s\"\n", targetFile); + } + } + + if (callback != NULL) callback(targetFile, cookie); + } + + free(helper.buf); + free(zpath); + + return ok; +} diff --git a/minzip/Zip.h b/minzip/Zip.h new file mode 100644 index 0000000..1c1df2f --- /dev/null +++ b/minzip/Zip.h @@ -0,0 +1,206 @@ +/* + * Copyright 2006 The Android Open Source Project + * + * Simple Zip archive support. + */ +#ifndef _MINZIP_ZIP +#define _MINZIP_ZIP + +#include "inline_magic.h" + +#include +#include + +#include "Hash.h" +#include "SysUtil.h" + +/* + * One entry in the Zip archive. Treat this as opaque -- use accessors below. + * + * TODO: we're now keeping the pages mapped so we don't have to copy the + * filename. We can change the accessors to retrieve the various pieces + * directly from the source file instead of copying them out, for a very + * slight speed hit and a modest reduction in memory usage. + */ +typedef struct ZipEntry { + unsigned int fileNameLen; + const char* fileName; // not null-terminated + long offset; + long compLen; + long uncompLen; + int compression; + long modTime; + long crc32; + int versionMadeBy; + long externalFileAttributes; +} ZipEntry; + +/* + * One Zip archive. Treat as opaque. + */ +typedef struct ZipArchive { + int fd; + unsigned int numEntries; + ZipEntry* pEntries; + HashTable* pHash; // maps file name to ZipEntry + MemMapping map; +} ZipArchive; + +/* + * Represents a non-NUL-terminated string, + * which is how entry names are stored. + */ +typedef struct { + const char *str; + size_t len; +} UnterminatedString; + +/* + * Open a Zip archive. + * + * On success, returns 0 and populates "pArchive". Returns nonzero errno + * value on failure. + */ +int mzOpenZipArchive(const char* fileName, ZipArchive* pArchive); + +/* + * Close archive, releasing resources associated with it. + * + * Depending on the implementation this could unmap pages used by classes + * stored in a Jar. This should only be done after unloading classes. + */ +void mzCloseZipArchive(ZipArchive* pArchive); + + +/* + * Find an entry in the Zip archive, by name. + */ +const ZipEntry* mzFindZipEntry(const ZipArchive* pArchive, + const char* entryName); + +/* + * Get the number of entries in the Zip archive. + */ +INLINE unsigned int mzZipEntryCount(const ZipArchive* pArchive) { + return pArchive->numEntries; +} + +/* + * Get an entry by index. Returns NULL if the index is out-of-bounds. + */ +INLINE const ZipEntry* +mzGetZipEntryAt(const ZipArchive* pArchive, unsigned int index) +{ + if (index < pArchive->numEntries) { + return pArchive->pEntries + index; + } + return NULL; +} + +/* + * Get the index number of an entry in the archive. + */ +INLINE unsigned int +mzGetZipEntryIndex(const ZipArchive *pArchive, const ZipEntry *pEntry) { + return pEntry - pArchive->pEntries; +} + +/* + * Simple accessors. + */ +INLINE UnterminatedString mzGetZipEntryFileName(const ZipEntry* pEntry) { + UnterminatedString ret; + ret.str = pEntry->fileName; + ret.len = pEntry->fileNameLen; + return ret; +} +INLINE long mzGetZipEntryOffset(const ZipEntry* pEntry) { + return pEntry->offset; +} +INLINE long mzGetZipEntryUncompLen(const ZipEntry* pEntry) { + return pEntry->uncompLen; +} +INLINE long mzGetZipEntryModTime(const ZipEntry* pEntry) { + return pEntry->modTime; +} +INLINE long mzGetZipEntryCrc32(const ZipEntry* pEntry) { + return pEntry->crc32; +} +bool mzIsZipEntrySymlink(const ZipEntry* pEntry); + + +/* + * Type definition for the callback function used by + * mzProcessZipEntryContents(). + */ +typedef bool (*ProcessZipEntryContentsFunction)(const unsigned char *data, + int dataLen, void *cookie); + +/* + * Stream the uncompressed data through the supplied function, + * passing cookie to it each time it gets called. processFunction + * may be called more than once. + * + * If processFunction returns false, the operation is abandoned and + * mzProcessZipEntryContents() immediately returns false. + * + * This is useful for calculating the hash of an entry's uncompressed contents. + */ +bool mzProcessZipEntryContents(const ZipArchive *pArchive, + const ZipEntry *pEntry, ProcessZipEntryContentsFunction processFunction, + void *cookie); + +/* + * Read an entry into a buffer allocated by the caller. + */ +bool mzReadZipEntry(const ZipArchive* pArchive, const ZipEntry* pEntry, + char* buf, int bufLen); + +/* + * Check the CRC on this entry; return true if it is correct. + * May do other internal checks as well. + */ +bool mzIsZipEntryIntact(const ZipArchive *pArchive, const ZipEntry *pEntry); + +/* + * Inflate and write an entry to a file. + */ +bool mzExtractZipEntryToFile(const ZipArchive *pArchive, + const ZipEntry *pEntry, int fd); + +/* + * Inflate all entries under zipDir to the directory specified by + * targetDir, which must exist and be a writable directory. + * + * The immediate children of zipDir will become the immediate + * children of targetDir; e.g., if the archive contains the entries + * + * a/b/c/one + * a/b/c/two + * a/b/c/d/three + * + * and mzExtractRecursive(a, "a/b/c", "/tmp", ...) is called, the resulting + * files will be + * + * /tmp/one + * /tmp/two + * /tmp/d/three + * + * flags is zero or more of the following: + * + * MZ_EXTRACT_FILES_ONLY - only unpack files, not directories or symlinks + * MZ_EXTRACT_DRY_RUN - don't do anything, but do invoke the callback + * + * If timestamp is non-NULL, file timestamps will be set accordingly. + * + * If callback is non-NULL, it will be invoked with each unpacked file. + * + * Returns true on success, false on failure. + */ +enum { MZ_EXTRACT_FILES_ONLY = 1, MZ_EXTRACT_DRY_RUN = 2 }; +bool mzExtractRecursive(const ZipArchive *pArchive, + const char *zipDir, const char *targetDir, + int flags, const struct utimbuf *timestamp, + void (*callback)(const char *fn, void*), void *cookie); + +#endif /*_MINZIP_ZIP*/ diff --git a/minzip/inline_magic.h b/minzip/inline_magic.h new file mode 100644 index 0000000..8c185e1 --- /dev/null +++ b/minzip/inline_magic.h @@ -0,0 +1,26 @@ +/* + * 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. + */ + +#ifndef MINZIP_INLINE_MAGIC_H_ +#define MINZIP_INLINE_MAGIC_H_ + +#ifndef MINZIP_GENERATE_INLINES +#define INLINE extern __inline__ +#else +#define INLINE +#endif + +#endif // MINZIP_INLINE_MAGIC_H_ -- cgit v1.1