/*

 * ZIP support routines for PhysicsFS.

 *

 * Please see the file LICENSE.txt in the source's root directory.

 *

 *  This file written by Ryan C. Gordon, with some peeking at "unzip.c"

 *   by Gilles Vollant.

 */

#define __PHYSICSFS_INTERNAL__

#include "physfs_internal.h"

#if PHYSFS_SUPPORTS_ZIP

#include <errno.h>

#include <time.h>

#include "physfs_miniz.h"

/*

 * A buffer of ZIP_READBUFSIZE is allocated for each compressed file opened,

 *  and is freed when you close the file; compressed data is read into

 *  this buffer, and then is decompressed into the buffer passed to

 *  PHYSFS_read().

 *

 * Uncompressed entries in a zipfile do not allocate this buffer; they just

 *  read data directly into the buffer passed to PHYSFS_read().

 *

 * Depending on your speed and memory requirements, you should tweak this

 *  value.

 */

#define ZIP_READBUFSIZE   (16 * 1024)

/*

 * Entries are "unresolved" until they are first opened. At that time,

 *  local file headers parsed/validated, data offsets will be updated to look

 *  at the actual file data instead of the header, and symlinks will be

 *  followed and optimized. This means that we don't seek and read around the

 *  archive until forced to do so, and after the first time, we had to do

 *  less reading and parsing, which is very CD-ROM friendly.

 */

typedef enum

{

    ZIP_UNRESOLVED_FILE,

    ZIP_UNRESOLVED_SYMLINK,

    ZIP_RESOLVING,

    ZIP_RESOLVED,

    ZIP_DIRECTORY,

    ZIP_BROKEN_FILE,

    ZIP_BROKEN_SYMLINK

} ZipResolveType;

/*

 * One ZIPentry is kept for each file in an open ZIP archive.

 */

typedef struct _ZIPentry

{

    char *name;                         /* Name of file in archive        */

    struct _ZIPentry *symlink;          /* NULL or file we symlink to     */

    ZipResolveType resolved;            /* Have we resolved file/symlink? */

    PHYSFS_uint64 offset;               /* offset of data in archive      */

    PHYSFS_uint16 version;              /* version made by                */

    PHYSFS_uint16 version_needed;       /* version needed to extract      */

    PHYSFS_uint16 general_bits;         /* general purpose bits           */

    PHYSFS_uint16 compression_method;   /* compression method             */

    PHYSFS_uint32 crc;                  /* crc-32                         */

    PHYSFS_uint64 compressed_size;      /* compressed size                */

    PHYSFS_uint64 uncompressed_size;    /* uncompressed size              */

    PHYSFS_sint64 last_mod_time;        /* last file mod time             */

    PHYSFS_uint32 dos_mod_time;         /* original MS-DOS style mod time */

    struct _ZIPentry *hashnext;         /* next item in this hash bucket  */

    struct _ZIPentry *children;         /* linked list of kids, if dir    */

    struct _ZIPentry *sibling;          /* next item in same dir          */

} ZIPentry;

/*

 * One ZIPinfo is kept for each open ZIP archive.

 */

typedef struct

{

    PHYSFS_Io *io;            /* the i/o interface for this archive.    */

    ZIPentry root;            /* root of directory tree.                */

    ZIPentry **hash;          /* all entries hashed for fast lookup.    */

    size_t hashBuckets;       /* number of buckets in hash.             */

    int zip64;                /* non-zero if this is a Zip64 archive.   */

    int has_crypto;           /* non-zero if any entry uses encryption. */

} ZIPinfo;

/*

 * One ZIPfileinfo is kept for each open file in a ZIP archive.

 */

typedef struct

{

    ZIPentry *entry;                      /* Info on file.              */

    PHYSFS_Io *io;                        /* physical file handle.      */

    PHYSFS_uint32 compressed_position;    /* offset in compressed data. */

    PHYSFS_uint32 uncompressed_position;  /* tell() position.           */

    PHYSFS_uint8 *buffer;                 /* decompression buffer.      */

    PHYSFS_uint32 crypto_keys[3];         /* for "traditional" crypto.  */

    PHYSFS_uint32 initial_crypto_keys[3]; /* for "traditional" crypto.  */

    z_stream stream;                      /* zlib stream state.         */

} ZIPfileinfo;

/* Magic numbers... */

#define ZIP_LOCAL_FILE_SIG                          0x04034b50

#define ZIP_CENTRAL_DIR_SIG                         0x02014b50

#define ZIP_END_OF_CENTRAL_DIR_SIG                  0x06054b50

#define ZIP64_END_OF_CENTRAL_DIR_SIG                0x06064b50

#define ZIP64_END_OF_CENTRAL_DIRECTORY_LOCATOR_SIG  0x07064b50

#define ZIP64_EXTENDED_INFO_EXTRA_FIELD_SIG         0x0001

/* compression methods... */

#define COMPMETH_NONE 0

/* ...and others... */

#define UNIX_FILETYPE_MASK    0170000

#define UNIX_FILETYPE_SYMLINK 0120000

#define ZIP_GENERAL_BITS_TRADITIONAL_CRYPTO   (1 << 0)

#define ZIP_GENERAL_BITS_IGNORE_LOCAL_HEADER  (1 << 3)

/* support for "traditional" PKWARE encryption. */

static int zip_entry_is_tradional_crypto(const ZIPentry *entry)

{

    return (entry->general_bits & ZIP_GENERAL_BITS_TRADITIONAL_CRYPTO) != 0;

} /* zip_entry_is_traditional_crypto */

static int zip_entry_ignore_local_header(const ZIPentry *entry)

{

    return (entry->general_bits & ZIP_GENERAL_BITS_IGNORE_LOCAL_HEADER) != 0;

} /* zip_entry_is_traditional_crypto */

static PHYSFS_uint32 zip_crypto_crc32(const PHYSFS_uint32 crc, const PHYSFS_uint8 val)

{

    int i;

    PHYSFS_uint32 xorval = (crc ^ ((PHYSFS_uint32) val)) & 0xFF;

    for (i = 0; i < 8; i++)

        xorval = ((xorval & 1) ? (0xEDB88320 ^ (xorval >> 1)) : (xorval >> 1));

    return xorval ^ (crc >> 8);

} /* zip_crc32 */

static void zip_update_crypto_keys(PHYSFS_uint32 *keys, const PHYSFS_uint8 val)

{

    keys[0] = zip_crypto_crc32(keys[0], val);

    keys[1] = keys[1] + (keys[0] & 0x000000FF);

    keys[1] = (keys[1] * 134775813) + 1;

    keys[2] = zip_crypto_crc32(keys[2], (PHYSFS_uint8) ((keys[1] >> 24) & 0xFF));

} /* zip_update_crypto_keys */

static PHYSFS_uint8 zip_decrypt_byte(const PHYSFS_uint32 *keys)

{

    const PHYSFS_uint16 tmp = keys[2] | 2;

    return (PHYSFS_uint8) ((tmp * (tmp ^ 1)) >> 8);

} /* zip_decrypt_byte */

static PHYSFS_sint64 zip_read_decrypt(ZIPfileinfo *finfo, void *buf, PHYSFS_uint64 len)

{

    PHYSFS_Io *io = finfo->io;

    const PHYSFS_sint64 br = io->read(io, buf, len);

    /* Decompression the new data if necessary. */

    if (zip_entry_is_tradional_crypto(finfo->entry) && (br > 0))

    {

        PHYSFS_uint32 *keys = finfo->crypto_keys;

        PHYSFS_uint8 *ptr = (PHYSFS_uint8 *) buf;

        PHYSFS_sint64 i;

        for (i = 0; i < br; i++, ptr++)

        {

            const PHYSFS_uint8 ch = *ptr ^ zip_decrypt_byte(keys);

            zip_update_crypto_keys(keys, ch);

            *ptr = ch;

        } /* for */

    } /* if  */

    return br;

} /* zip_read_decrypt */

static int zip_prep_crypto_keys(ZIPfileinfo *finfo, const PHYSFS_uint8 *crypto_header, const PHYSFS_uint8 *password)

{

    /* It doesn't appear to be documented in PKWare's APPNOTE.TXT, but you

       need to use a different byte in the header to verify the password

       if general purpose bit 3 is set. Discovered this from Info-Zip.

       That's what the (verifier) value is doing, below. */

    PHYSFS_uint32 *keys = finfo->crypto_keys;

    const ZIPentry *entry = finfo->entry;

    const int usedate = zip_entry_ignore_local_header(entry);

    const PHYSFS_uint8 verifier = (PHYSFS_uint8) ((usedate ? (entry->dos_mod_time >> 8) : (entry->crc >> 24)) & 0xFF);

    PHYSFS_uint8 finalbyte = 0;

    int i = 0;

    /* initialize vector with defaults, then password, then header. */

    keys[0] = 305419896;

    keys[1] = 591751049;

    keys[2] = 878082192;

    while (*password)

        zip_update_crypto_keys(keys, *(password++));

    for (i = 0; i < 12; i++)

    {

        const PHYSFS_uint8 c = crypto_header[i] ^ zip_decrypt_byte(keys);

        zip_update_crypto_keys(keys, c);

        finalbyte = c;

    } /* for */

    /* you have a 1/256 chance of passing this test incorrectly. :/ */

    if (finalbyte != verifier)

        BAIL_MACRO(PHYSFS_ERR_BAD_PASSWORD, 0);

    /* save the initial vector for seeking purposes. Not secure!! */

    memcpy(finfo->initial_crypto_keys, finfo->crypto_keys, 12);

    return 1;

} /* zip_prep_crypto_keys */

/*

 * Bridge physfs allocation functions to zlib's format...

 */

static voidpf zlibPhysfsAlloc(voidpf opaque, uInt items, uInt size)

{

    return ((PHYSFS_Allocator *) opaque)->Malloc(items * size);

} /* zlibPhysfsAlloc */

/*

 * Bridge physfs allocation functions to zlib's format...

 */

static void zlibPhysfsFree(voidpf opaque, voidpf address)

{

    ((PHYSFS_Allocator *) opaque)->Free(address);

} /* zlibPhysfsFree */

/*

 * Construct a new z_stream to a sane state.

 */

static void initializeZStream(z_stream *pstr)

{

    memset(pstr, '\0', sizeof (z_stream));

    pstr->zalloc = zlibPhysfsAlloc;

    pstr->zfree = zlibPhysfsFree;

    pstr->opaque = &allocator;

} /* initializeZStream */

static PHYSFS_ErrorCode zlib_error_code(int rc)

{

    switch (rc)

    {

        case Z_OK: return PHYSFS_ERR_OK;  /* not an error. */

        case Z_STREAM_END: return PHYSFS_ERR_OK; /* not an error. */

        case Z_ERRNO: return PHYSFS_ERR_IO;

        case Z_MEM_ERROR: return PHYSFS_ERR_OUT_OF_MEMORY;

        default: return PHYSFS_ERR_CORRUPT;

    } /* switch */

} /* zlib_error_string */

/*

 * Wrap all zlib calls in this, so the physfs error state is set appropriately.

 */

static int zlib_err(const int rc)

{

    PHYSFS_setErrorCode(zlib_error_code(rc));

    return rc;

} /* zlib_err */

/*

 * Hash a string for lookup an a ZIPinfo hashtable.

 */

static inline PHYSFS_uint32 zip_hash_string(const ZIPinfo *info, const char *s)

{

    return __PHYSFS_hashString(s, strlen(s)) % info->hashBuckets;

} /* zip_hash_string */

/*

 * Read an unsigned 64-bit int and swap to native byte order.

 */

static int readui64(PHYSFS_Io *io, PHYSFS_uint64 *val)

{

    PHYSFS_uint64 v;

    BAIL_IF_MACRO(!__PHYSFS_readAll(io, &v, sizeof (v)), ERRPASS, 0);

    *val = PHYSFS_swapULE64(v);

    return 1;

} /* readui64 */

/*

 * Read an unsigned 32-bit int and swap to native byte order.

 */

static int readui32(PHYSFS_Io *io, PHYSFS_uint32 *val)

{

    PHYSFS_uint32 v;

    BAIL_IF_MACRO(!__PHYSFS_readAll(io, &v, sizeof (v)), ERRPASS, 0);

    *val = PHYSFS_swapULE32(v);

    return 1;

} /* readui32 */

/*

 * Read an unsigned 16-bit int and swap to native byte order.

 */

static int readui16(PHYSFS_Io *io, PHYSFS_uint16 *val)

{

    PHYSFS_uint16 v;

    BAIL_IF_MACRO(!__PHYSFS_readAll(io, &v, sizeof (v)), ERRPASS, 0);

    *val = PHYSFS_swapULE16(v);

    return 1;

} /* readui16 */

static PHYSFS_sint64 ZIP_read(PHYSFS_Io *_io, void *buf, PHYSFS_uint64 len)

{

    ZIPfileinfo *finfo = (ZIPfileinfo *) _io->opaque;

    ZIPentry *entry = finfo->entry;

    PHYSFS_sint64 retval = 0;

    PHYSFS_sint64 maxread = (PHYSFS_sint64) len;

    PHYSFS_sint64 avail = entry->uncompressed_size -

                          finfo->uncompressed_position;

    if (avail < maxread)

        maxread = avail;

    BAIL_IF_MACRO(maxread == 0, ERRPASS, 0);    /* quick rejection. */

    if (entry->compression_method == COMPMETH_NONE)

        retval = zip_read_decrypt(finfo, buf, maxread);

    else

    {

        finfo->stream.next_out = buf;

        finfo->stream.avail_out = (uInt) maxread;

        while (retval < maxread)

        {

            PHYSFS_uint32 before = finfo->stream.total_out;

            int rc;

            if (finfo->stream.avail_in == 0)

            {

                PHYSFS_sint64 br;

                br = entry->compressed_size - finfo->compressed_position;

                if (br > 0)

                {

                    if (br > ZIP_READBUFSIZE)

                        br = ZIP_READBUFSIZE;

                    br = zip_read_decrypt(finfo, finfo->buffer, (PHYSFS_uint64) br);

                    if (br <= 0)

                        break;

                    finfo->compressed_position += (PHYSFS_uint32) br;

                    finfo->stream.next_in = finfo->buffer;

                    finfo->stream.avail_in = (PHYSFS_uint32) br;

                } /* if */

            } /* if */

            rc = zlib_err(inflate(&finfo->stream, Z_SYNC_FLUSH));

            retval += (finfo->stream.total_out - before);

            if (rc != Z_OK)

                break;

        } /* while */

    } /* else */

    if (retval > 0)

        finfo->uncompressed_position += (PHYSFS_uint32) retval;

    return retval;

} /* ZIP_read */

static PHYSFS_sint64 ZIP_write(PHYSFS_Io *io, const void *b, PHYSFS_uint64 len)

{

    BAIL_MACRO(PHYSFS_ERR_READ_ONLY, -1);

} /* ZIP_write */

static PHYSFS_sint64 ZIP_tell(PHYSFS_Io *io)

{

    return ((ZIPfileinfo *) io->opaque)->uncompressed_position;

} /* ZIP_tell */

static int ZIP_seek(PHYSFS_Io *_io, PHYSFS_uint64 offset)

{

    ZIPfileinfo *finfo = (ZIPfileinfo *) _io->opaque;

    ZIPentry *entry = finfo->entry;

    PHYSFS_Io *io = finfo->io;

    const int encrypted = zip_entry_is_tradional_crypto(entry);

    BAIL_IF_MACRO(offset > entry->uncompressed_size, PHYSFS_ERR_PAST_EOF, 0);

    if (!encrypted && (entry->compression_method == COMPMETH_NONE))

    {

        PHYSFS_sint64 newpos = offset + entry->offset;

        BAIL_IF_MACRO(!io->seek(io, newpos), ERRPASS, 0);

        finfo->uncompressed_position = (PHYSFS_uint32) offset;

    } /* if */

    else

    {

        /*

         * If seeking backwards, we need to redecode the file

         *  from the start and throw away the compressed bits until we hit

         *  the offset we need. If seeking forward, we still need to

         *  decode, but we don't rewind first.

         */

        if (offset < finfo->uncompressed_position)

        {

            /* we do a copy so state is sane if inflateInit2() fails. */

            z_stream str;

            initializeZStream(&str);

            if (zlib_err(inflateInit2(&str, -MAX_WBITS)) != Z_OK)

                return 0;

            if (!io->seek(io, entry->offset + (encrypted ? 12 : 0)))

                return 0;

            inflateEnd(&finfo->stream);

            memcpy(&finfo->stream, &str, sizeof (z_stream));

            finfo->uncompressed_position = finfo->compressed_position = 0;

            if (encrypted)

                memcpy(finfo->crypto_keys, finfo->initial_crypto_keys, 12);

        } /* if */

        while (finfo->uncompressed_position != offset)

        {

            PHYSFS_uint8 buf[512];

            PHYSFS_uint32 maxread;

            maxread = (PHYSFS_uint32) (offset - finfo->uncompressed_position);

            if (maxread > sizeof (buf))

                maxread = sizeof (buf);

            if (ZIP_read(_io, buf, maxread) != maxread)

                return 0;

        } /* while */

    } /* else */

    return 1;

} /* ZIP_seek */

static PHYSFS_sint64 ZIP_length(PHYSFS_Io *io)

{

    const ZIPfileinfo *finfo = (ZIPfileinfo *) io->opaque;

    return (PHYSFS_sint64) finfo->entry->uncompressed_size;

} /* ZIP_length */

static PHYSFS_Io *zip_get_io(PHYSFS_Io *io, ZIPinfo *inf, ZIPentry *entry);

static PHYSFS_Io *ZIP_duplicate(PHYSFS_Io *io)

{

    ZIPfileinfo *origfinfo = (ZIPfileinfo *) io->opaque;

    PHYSFS_Io *retval = (PHYSFS_Io *) allocator.Malloc(sizeof (PHYSFS_Io));

    ZIPfileinfo *finfo = (ZIPfileinfo *) allocator.Malloc(sizeof (ZIPfileinfo));

    GOTO_IF_MACRO(!retval, PHYSFS_ERR_OUT_OF_MEMORY, failed);

    GOTO_IF_MACRO(!finfo, PHYSFS_ERR_OUT_OF_MEMORY, failed);

    memset(finfo, '\0', sizeof (*finfo));

    finfo->entry = origfinfo->entry;

    finfo->io = zip_get_io(origfinfo->io, NULL, finfo->entry);

    GOTO_IF_MACRO(!finfo->io, ERRPASS, failed);

    if (finfo->entry->compression_method != COMPMETH_NONE)

    {

        finfo->buffer = (PHYSFS_uint8 *) allocator.Malloc(ZIP_READBUFSIZE);

        GOTO_IF_MACRO(!finfo->buffer, PHYSFS_ERR_OUT_OF_MEMORY, failed);

        if (zlib_err(inflateInit2(&finfo->stream, -MAX_WBITS)) != Z_OK)

            goto failed;

    } /* if */

    memcpy(retval, io, sizeof (PHYSFS_Io));

    retval->opaque = finfo;

    return retval;

failed:

    if (finfo != NULL)

    {

        if (finfo->io != NULL)

            finfo->io->destroy(finfo->io);

        if (finfo->buffer != NULL)

        {

            allocator.Free(finfo->buffer);

            inflateEnd(&finfo->stream);

        } /* if */

        allocator.Free(finfo);

    } /* if */

    if (retval != NULL)

        allocator.Free(retval);

    return NULL;

} /* ZIP_duplicate */

static int ZIP_flush(PHYSFS_Io *io) { return 1;  /* no write support. */ }

static void ZIP_destroy(PHYSFS_Io *io)

{

    ZIPfileinfo *finfo = (ZIPfileinfo *) io->opaque;

    finfo->io->destroy(finfo->io);

    if (finfo->entry->compression_method != COMPMETH_NONE)

        inflateEnd(&finfo->stream);

    if (finfo->buffer != NULL)

        allocator.Free(finfo->buffer);

    allocator.Free(finfo);

    allocator.Free(io);