libdex/ZipArchive.c

   1 /*
   2  * Copyright (C) 2008 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 /*
  17  * Read-only access to Zip archives, with minimal heap allocation.
  18  */
  19 #include "ZipArchive.h"
  20
  21 #include <zlib.h>
  22
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <fcntl.h>
  26 #include <errno.h>
  27
  28
  29 /*
  30  * Zip file constants.
  31  */
  32 #define kEOCDSignature      0x06054b50
  33 #define kEOCDLen            22
  34 #define kEOCDNumEntries     8               // offset to #of entries in file
  35 #define kEOCDFileOffset     16              // offset to central directory
  36
  37 #define kMaxCommentLen      65535           // longest possible in ushort
  38 #define kMaxEOCDSearch      (kMaxCommentLen + kEOCDLen)
  39
  40 #define kLFHSignature       0x04034b50
  41 #define kLFHLen             30              // excluding variable-len fields
  42 #define kLFHNameLen         26              // offset to filename length
  43 #define kLFHExtraLen        28              // offset to extra length
  44
  45 #define kCDESignature       0x02014b50
  46 #define kCDELen             46              // excluding variable-len fields
  47 #define kCDEMethod          10              // offset to compression method
  48 #define kCDEModWhen         12              // offset to modification timestamp
  49 #define kCDECRC             16              // offset to entry CRC
  50 #define kCDECompLen         20              // offset to compressed length
  51 #define kCDEUncompLen       24              // offset to uncompressed length
  52 #define kCDENameLen         28              // offset to filename length
  53 #define kCDEExtraLen        30              // offset to extra length
  54 #define kCDECommentLen      32              // offset to comment length
  55 #define kCDELocalOffset     42              // offset to local hdr
  56
  57 /*
  58  * The values we return for ZipEntry use 0 as an invalid value, so we
  59  * want to adjust the hash table index by a fixed amount.  Using a large
  60  * value helps insure that people don't mix & match arguments, e.g. with
  61  * entry indices.
  62  */
  63 #define kZipEntryAdj        10000
  64
  65 /*
  66  * Convert a ZipEntry to a hash table index, verifying that it's in a
  67  * valid range.
  68  */
  69 static int entryToIndex(const ZipArchive* pArchive, const ZipEntry entry)
  70 {
  71     long ent = ((long) entry) - kZipEntryAdj;
  72     if (ent < 0 || ent >= pArchive->mHashTableSize ||
  73         pArchive->mHashTable[ent].name == NULL)
  74     {
  75         LOGW("Invalid ZipEntry %p (%ld)\n", entry, ent);
  76         return -1;
  77     }
  78     return ent;
  79 }
  80
  81 /*
  82  * Simple string hash function for non-null-terminated strings.
  83  */
  84 static unsigned int computeHash(const char* str, int len)
  85 {
  86     unsigned int hash = 0;
  87
  88     while (len--)
  89         hash = hash * 31 + *str++;
  90
  91     return hash;
  92 }
  93
  94 /*
  95  * Add a new entry to the hash table.
  96  */
  97 static void addToHash(ZipArchive* pArchive, const char* str, int strLen,
  98     unsigned int hash)
  99 {
 100     const int hashTableSize = pArchive->mHashTableSize;
 101     int ent = hash & (hashTableSize - 1);
 102
 103     /*
 104      * We over-allocated the table, so we're guaranteed to find an empty slot.
 105      */
 106     while (pArchive->mHashTable[ent].name != NULL)
 107         ent = (ent + 1) & (hashTableSize-1);
 108
 109     pArchive->mHashTable[ent].name = str;
 110     pArchive->mHashTable[ent].nameLen = strLen;
 111 }
 112
 113 /*
 114  * Get 2 little-endian bytes.
 115  */
 116 static u2 get2LE(unsigned char const* pSrc)
 117 {
 118     return pSrc[0] | (pSrc[1] << 8);
 119 }
 120
 121 /*
 122  * Get 4 little-endian bytes.
 123  */
 124 static u4 get4LE(unsigned char const* pSrc)
 125 {
 126     u4 result;
 127
 128     result = pSrc[0];
 129     result |= pSrc[1] << 8;
 130     result |= pSrc[2] << 16;
 131     result |= pSrc[3] << 24;
 132
 133     return result;
 134 }
 135
 136 /*
 137  * Parse the Zip archive, verifying its contents and initializing internal
 138  * data structures.
 139  */
 140 static bool parseZipArchive(ZipArchive* pArchive, const MemMapping* pMap)
 141 {
 142 #define CHECK_OFFSET(_off) {                                                \
 143         if ((unsigned int) (_off) >= maxOffset) {                           \
 144             LOGE("ERROR: bad offset %u (max %d): %s\n",                     \
 145                 (unsigned int) (_off), maxOffset, #_off);                   \
 146             goto bail;                                                      \
 147         }                                                                   \
 148     }
 149     bool result = false;
 150     const unsigned char* basePtr = (const unsigned char*)pMap->addr;
 151     const unsigned char* ptr;
 152     size_t length = pMap->length;
 153     unsigned int i, numEntries, cdOffset;
 154     unsigned int val;
 155
 156     /*
 157      * The first 4 bytes of the file will either be the local header
 158      * signature for the first file (kLFHSignature) or, if the archive doesn't
 159      * have any files in it, the end-of-central-directory signature
 160      * (kEOCDSignature).
 161      */
 162     val = get4LE(basePtr);
 163     if (val == kEOCDSignature) {
 164         LOGI("Found Zip archive, but it looks empty\n");
 165         goto bail;
 166     } else if (val != kLFHSignature) {
 167         LOGV("Not a Zip archive (found 0x%08x)\n", val);
 168         goto bail;
 169     }
 170
 171     /*
 172      * Find the EOCD.  We'll find it immediately unless they have a file
 173      * comment.
 174      */
 175     ptr = basePtr + length - kEOCDLen;
 176
 177     while (ptr >= basePtr) {
 178         if (*ptr == (kEOCDSignature & 0xff) && get4LE(ptr) == kEOCDSignature)
 179             break;
 180         ptr--;
 181     }
 182     if (ptr < basePtr) {
 183         LOGI("Could not find end-of-central-directory in Zip\n");
 184         goto bail;
 185     }
 186
 187     /*
 188      * There are two interesting items in the EOCD block: the number of
 189      * entries in the file, and the file offset of the start of the
 190      * central directory.
 191      *
 192      * (There's actually a count of the #of entries in this file, and for
 193      * all files which comprise a spanned archive, but for our purposes
 194      * we're only interested in the current file.  Besides, we expect the
 195      * two to be equivalent for our stuff.)
 196      */
 197     numEntries = get2LE(ptr + kEOCDNumEntries);
 198     cdOffset = get4LE(ptr + kEOCDFileOffset);
 199
 200     /* valid offsets are [0,EOCD] */
 201     unsigned int maxOffset;
 202     maxOffset = (ptr - basePtr) +1;
 203
 204     LOGV("+++ numEntries=%d cdOffset=%d\n", numEntries, cdOffset);
 205     if (numEntries == 0 || cdOffset >= length) {
 206         LOGW("Invalid entries=%d offset=%d (len=%zd)\n",
 207             numEntries, cdOffset, length);
 208         goto bail;
 209     }
 210
 211     /*
 212      * Create hash table.  We have a minimum 75% load factor, possibly as
 213      * low as 50% after we round off to a power of 2.  There must be at
 214      * least one unused entry to avoid an infinite loop during creation.
 215      */
 216     pArchive->mNumEntries = numEntries;
 217     pArchive->mHashTableSize = dexRoundUpPower2(1 + (numEntries * 4) / 3);
 218     pArchive->mHashTable = (ZipHashEntry*)
 219             calloc(pArchive->mHashTableSize, sizeof(ZipHashEntry));
 220
 221     /*
 222      * Walk through the central directory, adding entries to the hash
 223      * table.
 224      */
 225     ptr = basePtr + cdOffset;
 226     for (i = 0; i < numEntries; i++) {
 227         unsigned int fileNameLen, extraLen, commentLen, localHdrOffset;
 228         const unsigned char* localHdr;
 229         unsigned int hash;
 230
 231         if (get4LE(ptr) != kCDESignature) {
 232             LOGW("Missed a central dir sig (at %d)\n", i);
 233             goto bail;
 234         }
 235         if (ptr + kCDELen > basePtr + length) {
 236             LOGW("Ran off the end (at %d)\n", i);
 237             goto bail;
 238         }
 239
 240         localHdrOffset = get4LE(ptr + kCDELocalOffset);
 241         CHECK_OFFSET(localHdrOffset);
 242         fileNameLen = get2LE(ptr + kCDENameLen);
 243         extraLen = get2LE(ptr + kCDEExtraLen);
 244         commentLen = get2LE(ptr + kCDECommentLen);
 245
 246         //LOGV("+++ %d: localHdr=%d fnl=%d el=%d cl=%d\n",
 247         //    i, localHdrOffset, fileNameLen, extraLen, commentLen);
 248         //LOGV(" '%.*s'\n", fileNameLen, ptr + kCDELen);
 249
 250         /* add the CDE filename to the hash table */
 251         hash = computeHash((const char*)ptr + kCDELen, fileNameLen);
 252         addToHash(pArchive, (const char*)ptr + kCDELen, fileNameLen, hash);
 253
 254         localHdr = basePtr + localHdrOffset;
 255         if (get4LE(localHdr) != kLFHSignature) {
 256             LOGW("Bad offset to local header: %d (at %d)\n",
 257                 localHdrOffset, i);
 258             goto bail;
 259         }
 260
 261         ptr += kCDELen + fileNameLen + extraLen + commentLen;
 262         CHECK_OFFSET(ptr - basePtr);
 263     }
 264
 265     result = true;
 266
 267 bail:
 268     return result;
 269 #undef CHECK_OFFSET
 270 }
 271
 272 /*
 273  * Open the specified file read-only.  We memory-map the entire thing and
 274  * parse the contents.
 275  *
 276  * This will be called on non-Zip files, especially during VM startup, so
 277  * we don't want to be too noisy about certain types of failure.  (Do
 278  * we want a "quiet" flag?)
 279  *
 280  * On success, we fill out the contents of "pArchive" and return 0.
 281  */
 282 int dexZipOpenArchive(const char* fileName, ZipArchive* pArchive)
 283 {
 284     int fd, err;
 285
 286     LOGV("Opening archive '%s' %p\n", fileName, pArchive);
 287
 288     fd = open(fileName, O_RDONLY, 0);
 289     if (fd < 0) {
 290         err = errno ? errno : -1;
 291         LOGV("Unable to open '%s': %s\n", fileName, strerror(err));
 292         return err;
 293     }
 294
 295     return dexZipPrepArchive(fd, fileName, pArchive);
 296 }
 297
 298 /*
 299  * Prepare to access a ZipArchive in an open file descriptor.
 300  */
 301 int dexZipPrepArchive(int fd, const char* debugFileName, ZipArchive* pArchive)
 302 {
 303     MemMapping map;
 304     int err;
 305
 306     map.addr = NULL;
 307     memset(pArchive, 0, sizeof(*pArchive));
 308
 309     pArchive->mFd = fd;
 310
 311     if (sysMapFileInShmem(pArchive->mFd, &map) != 0) {
 312         err = -1;
 313         LOGW("Map of '%s' failed\n", debugFileName);
 314         goto bail;
 315     }
 316
 317     if (map.length < kEOCDLen) {
 318         err = -1;
 319         LOGV("File '%s' too small to be zip (%zd)\n", debugFileName,map.length);
 320         goto bail;
 321     }
 322
 323     if (!parseZipArchive(pArchive, &map)) {
 324         err = -1;
 325         LOGV("Parsing '%s' failed\n", debugFileName);
 326         goto bail;
 327     }
 328
 329     /* success */
 330     err = 0;
 331     sysCopyMap(&pArchive->mMap, &map);
 332     map.addr = NULL;
 333
 334 bail:
 335     if (err != 0)
 336         dexZipCloseArchive(pArchive);
 337     if (map.addr != NULL)
 338         sysReleaseShmem(&map);
 339     return err;
 340 }
 341
 342
 343 /*
 344  * Close a ZipArchive, closing the file and freeing the contents.
 345  *
 346  * NOTE: the ZipArchive may not have been fully created.
 347  */
 348 void dexZipCloseArchive(ZipArchive* pArchive)
 349 {
 350     LOGV("Closing archive %p\n", pArchive);
 351
 352     if (pArchive->mFd >= 0)
 353         close(pArchive->mFd);
 354
 355     sysReleaseShmem(&pArchive->mMap);
 356
 357     free(pArchive->mHashTable);
 358
 359     pArchive->mFd = -1;
 360     pArchive->mNumEntries = -1;
 361     pArchive->mHashTableSize = -1;
 362     pArchive->mHashTable = NULL;
 363 }
 364
 365
 366 /*
 367  * Find a matching entry.
 368  *
 369  * Returns 0 if not found.
 370  */
 371 ZipEntry dexZipFindEntry(const ZipArchive* pArchive, const char* entryName)
 372 {
 373     int nameLen = strlen(entryName);
 374     unsigned int hash = computeHash(entryName, nameLen);
 375     const int hashTableSize = pArchive->mHashTableSize;
 376     int ent = hash & (hashTableSize-1);
 377
 378     while (pArchive->mHashTable[ent].name != NULL) {
 379         if (pArchive->mHashTable[ent].nameLen == nameLen &&
 380             memcmp(pArchive->mHashTable[ent].name, entryName, nameLen) == 0)
 381         {
 382             /* match */
 383             return (ZipEntry) (ent + kZipEntryAdj);
 384         }
 385
 386         ent = (ent + 1) & (hashTableSize-1);
 387     }
 388
 389     return NULL;
 390 }
 391
 392 #if 0
 393 /*
 394  * Find the Nth entry.
 395  *
 396  * This currently involves walking through the sparse hash table, counting
 397  * non-empty entries.  If we need to speed this up we can either allocate
 398  * a parallel lookup table or (perhaps better) provide an iterator interface.
 399  */
 400 ZipEntry findEntryByIndex(ZipArchive* pArchive, int idx)
 401 {
 402     if (idx < 0 || idx >= pArchive->mNumEntries) {
 403         LOGW("Invalid index %d\n", idx);
 404         return NULL;
 405     }
 406
 407     int ent;
 408     for (ent = 0; ent < pArchive->mHashTableSize; ent++) {
 409         if (pArchive->mHashTable[ent].name != NULL) {
 410             if (idx-- == 0)
 411                 return (ZipEntry) (ent + kZipEntryAdj);
 412         }
 413     }
 414
 415     return NULL;
 416 }
 417 #endif
 418
 419 /*
 420  * Get the useful fields from the zip entry.
 421  *
 422  * Returns "false" if the offsets to the fields or the contents of the fields
 423  * appear to be bogus.
 424  */
 425 bool dexZipGetEntryInfo(const ZipArchive* pArchive, ZipEntry entry,
 426     int* pMethod, long* pUncompLen, long* pCompLen, off_t* pOffset,
 427     long* pModWhen, long* pCrc32)
 428 {
 429     int ent = entryToIndex(pArchive, entry);
 430     if (ent < 0)
 431         return false;
 432
 433     /*
 434      * Recover the start of the central directory entry from the filename
 435      * pointer.
 436      */
 437     const unsigned char* basePtr = (const unsigned char*)
 438         pArchive->mMap.addr;
 439     const unsigned char* ptr = (const unsigned char*)
 440         pArchive->mHashTable[ent].name;
 441     size_t zipLength =
 442         pArchive->mMap.length;
 443
 444     ptr -= kCDELen;
 445
 446     int method = get2LE(ptr + kCDEMethod);
 447     if (pMethod != NULL)
 448         *pMethod = method;
 449
 450     if (pModWhen != NULL)
 451         *pModWhen = get4LE(ptr + kCDEModWhen);
 452     if (pCrc32 != NULL)
 453         *pCrc32 = get4LE(ptr + kCDECRC);
 454
 455     /*
 456      * We need to make sure that the lengths are not so large that somebody
 457      * trying to map the compressed or uncompressed data runs off the end
 458      * of the mapped region.
 459      */
 460     unsigned long localHdrOffset = get4LE(ptr + kCDELocalOffset);
 461     if (localHdrOffset + kLFHLen >= zipLength) {
 462         LOGE("ERROR: bad local hdr offset in zip\n");
 463         return false;
 464     }
 465     const unsigned char* localHdr = basePtr + localHdrOffset;
 466     off_t dataOffset = localHdrOffset + kLFHLen
 467         + get2LE(localHdr + kLFHNameLen) + get2LE(localHdr + kLFHExtraLen);
 468     if ((unsigned long) dataOffset >= zipLength) {
 469         LOGE("ERROR: bad data offset in zip\n");
 470         return false;
 471     }
 472
 473     if (pCompLen != NULL) {
 474         *pCompLen = get4LE(ptr + kCDECompLen);
 475         if (*pCompLen < 0 || (size_t)(dataOffset + *pCompLen) >= zipLength) {
 476             LOGE("ERROR: bad compressed length in zip\n");
 477             return false;
 478         }
 479     }
 480     if (pUncompLen != NULL) {
 481         *pUncompLen = get4LE(ptr + kCDEUncompLen);
 482         if (*pUncompLen < 0) {
 483             LOGE("ERROR: negative uncompressed length in zip\n");
 484             return false;
 485         }
 486         if (method == kCompressStored &&
 487             (size_t)(dataOffset + *pUncompLen) >= zipLength)
 488         {
 489             LOGE("ERROR: bad uncompressed length in zip\n");
 490             return false;
 491         }
 492     }
 493
 494     if (pOffset != NULL) {
 495         *pOffset = dataOffset;
 496     }
 497     return true;
 498 }
 499
 500 /*
 501  * Uncompress "deflate" data from one buffer to an open file descriptor.
 502  */
 503 static bool inflateToFile(int fd, const void* inBuf, long uncompLen,
 504     long compLen)
 505 {
 506     bool result = false;
 507     const int kWriteBufSize = 32768;
 508     unsigned char writeBuf[kWriteBufSize];
 509     z_stream zstream;
 510     int zerr;
 511
 512     /*
 513      * Initialize the zlib stream struct.
 514      */
 515         memset(&zstream, 0, sizeof(zstream));
 516     zstream.zalloc = Z_NULL;
 517     zstream.zfree = Z_NULL;
 518     zstream.opaque = Z_NULL;
 519     zstream.next_in = (Bytef*)inBuf;
 520     zstream.avail_in = compLen;
 521     zstream.next_out = (Bytef*) writeBuf;
 522     zstream.avail_out = sizeof(writeBuf);
 523     zstream.data_type = Z_UNKNOWN;
 524
 525         /*
 526          * Use the undocumented "negative window bits" feature to tell zlib
 527          * that there's no zlib header waiting for it.
 528          */
 529     zerr = inflateInit2(&zstream, -MAX_WBITS);
 530     if (zerr != Z_OK) {
 531         if (zerr == Z_VERSION_ERROR) {
 532             LOGE("Installed zlib is not compatible with linked version (%s)\n",
 533                 ZLIB_VERSION);
 534         } else {
 535             LOGE("Call to inflateInit2 failed (zerr=%d)\n", zerr);
 536         }
 537         goto bail;
 538     }
 539
 540     /*
 541      * Loop while we have more to do.
 542      */
 543     do {
 544         /*
 545          * Expand data.
 546          */
 547         zerr = inflate(&zstream, Z_NO_FLUSH);
 548         if (zerr != Z_OK && zerr != Z_STREAM_END) {
 549             LOGW("zlib inflate: zerr=%d (nIn=%p aIn=%u nOut=%p aOut=%u)\n",
 550                 zerr, zstream.next_in, zstream.avail_in,
 551                 zstream.next_out, zstream.avail_out);
 552             goto z_bail;
 553         }
 554
 555         /* write when we're full or when we're done */
 556         if (zstream.avail_out == 0 ||
 557             (zerr == Z_STREAM_END && zstream.avail_out != sizeof(writeBuf)))
 558         {
 559             long writeSize = zstream.next_out - writeBuf;
 560             int cc = write(fd, writeBuf, writeSize);
 561             if (cc != (int) writeSize) {
 562                 if (cc < 0) {
 563                     LOGW("write failed in inflate: %s\n", strerror(errno));
 564                 } else {
 565                     LOGW("partial write in inflate (%d vs %ld)\n",
 566                         cc, writeSize);
 567                 }
 568                 goto z_bail;
 569             }
 570
 571             zstream.next_out = writeBuf;
 572             zstream.avail_out = sizeof(writeBuf);
 573         }
 574     } while (zerr == Z_OK);
 575
 576     assert(zerr == Z_STREAM_END);       /* other errors should've been caught */
 577
 578     /* paranoia */
 579     if ((long) zstream.total_out != uncompLen) {
 580         LOGW("Size mismatch on inflated file (%ld vs %ld)\n",
 581             zstream.total_out, uncompLen);
 582         goto z_bail;
 583     }
 584
 585     result = true;
 586
 587 z_bail:
 588     inflateEnd(&zstream);        /* free up any allocated structures */
 589
 590 bail:
 591     return result;
 592 }
 593
 594 /*
 595  * Uncompress an entry, in its entirety, to an open file descriptor.
 596  *
 597  * TODO: this doesn't verify the data's CRC, but probably should (especially
 598  * for uncompressed data).
 599  */
 600 bool dexZipExtractEntryToFile(const ZipArchive* pArchive,
 601     const ZipEntry entry, int fd)
 602 {
 603     bool result = false;
 604     int ent = entryToIndex(pArchive, entry);
 605     if (ent < 0)
 606         return -1;
 607
 608     const unsigned char* basePtr = (const unsigned char*)pArchive->mMap.addr;
 609     int method;
 610     long uncompLen, compLen;
 611     off_t offset;
 612
 613     if (!dexZipGetEntryInfo(pArchive, entry, &method, &uncompLen, &compLen,
 614             &offset, NULL, NULL))
 615     {
 616         goto bail;
 617     }
 618
 619     if (method == kCompressStored) {
 620         ssize_t actual;
 621
 622         actual = write(fd, basePtr + offset, uncompLen);
 623         if (actual < 0) {
 624             LOGE("Write failed: %s\n", strerror(errno));
 625             goto bail;
 626         } else if (actual != uncompLen) {
 627             LOGE("Partial write during uncompress (%d of %ld)\n",
 628                 (int) actual, uncompLen);
 629             goto bail;
 630         } else {
 631             LOGI("+++ successful write\n");
 632         }
 633     } else {
 634         if (!inflateToFile(fd, basePtr+offset, uncompLen, compLen))
 635             goto bail;
 636     }
 637
 638     result = true;
 639
 640 bail:
 641     return result;
 642 }
 643