/*---------------------------------------------------------------------------*

  Copyright (C) Nintendo.  All rights reserved.

  These coded instructions, statements, and computer programs contain
  proprietary information of Nintendo of America Inc. and/or Nintendo
  Company Ltd., and are protected by Federal copyright law.  They may
  not be disclosed to third parties or copied or duplicated in any form,
  in whole or in part, without the prior written consent of Nintendo.

 *---------------------------------------------------------------------------*/


/*


    THIS IS CROSS PLATFORM SOURCE CODE

    IF YOU MODIFY THIS SOURCE YOU *MUST* ENSURE IT STILL BUILDS ON BOTH
    WIN32 AND CAFE.


*/


#include <stdlib.h>
#include <string.h>
#include <cafe/zipfile.h>

#define ZIPFILE_ENDIAN_LITTLE   0
#define ZIPFILE_ENDIAN_BIG      1

#ifndef ZIP_MAKEID4
#define ZIP_MAKEID4(endian,a,b,c,d) ((endian==ZIPFILE_ENDIAN_LITTLE) ? \
    ((((UINT32)a)&0xFF) | ((((UINT32)b)&0xFF)<<8) | ((((UINT32)c)&0xFF)<<16) | ((((UINT32)d)&0xFF)<<24)) : \
    ((((UINT32)d)&0xFF) | ((((UINT32)c)&0xFF)<<8) | ((((UINT32)b)&0xFF)<<16) | ((((UINT32)a)&0xFF)<<24)))
#endif  

#ifndef ZIP_TARGETID4
#define ZIP_TARGETID4(a,b,c,d)  ZIP_MAKEID4(ZIPFILE_ENDIAN,a,b,c,d)
#endif

#define ZIP_RAW_FILEENTRY_MARKER    ZIP_TARGETID4('P','K',3,4)
#define ZIP_FILECDS_MARKER          ZIP_TARGETID4('P','K',1,2)
#define ZIP_FILECDS_TAIL_MARKER     ZIP_TARGETID4('P','K',5,6)

#define SWAP32(x)  (((((UINT32)(x))&0xFF)<<24) | ((((UINT32)(x))&0xFF00)<<8) | ((((UINT32)(x))&0xFF0000)>>8) | ((((UINT32)(x))&0xFF000000)>>24))
#define SWAP16(x)  (((((UINT16)(x))&0xFF)<<8) | ((((UINT16)(x))&0xFF00)>>8))

#ifdef _MSC_VER
#pragma pack (push, 1)
#define ZIPFILE_ENDIAN ZIPFILE_ENDIAN_LITTLE
#else
#ifdef EPPC
#pragma pack(1)
#define ZIPFILE_ENDIAN ZIPFILE_ENDIAN_BIG
#else
#error !!! Unknown compilation target
#endif
#endif

struct _ZIPFILE_RAW_FILEENTRY
{
    UINT32  mMarker;
    UINT16  mMinVer;
    UINT16  mFlags;
    UINT16  mCompressionMethod;
    UINT32  mDosDateTime;
    UINT32  mCRC;
    UINT32  mCompSizeBytes;
    UINT32  mUncompSizeBytes;
    UINT16  mFileNameLen;
    UINT16  mExtraLen;
    /* Filename for 'mFileNameLen' */
    /* Extra for 'mExtraLen' */
};
typedef struct _ZIPFILE_RAW_FILEENTRY ZIPFILE_RAW_FILEENTRY;

struct _ZIP_FILECDS
{   
    UINT32  mMarker;
    UINT8   mMadeBy;
    UINT8   mHostOS;
    UINT8   mMinVer;
    UINT8   mTargetOS;
    UINT16  mFlags;
    UINT16  mCompressionMethod;
    UINT16  mModFileTime;
    UINT16  mModFileDate;
    UINT32  mCRC;
    UINT32  mCompSizeBytes;
    UINT32  mUncompSizeBytes;
    UINT16  mFileNameLen;
    UINT16  mExtraLen;
    UINT16  mCommentLen;
    UINT16  mDiskNum;
    UINT16  mIntFileAttr;
    UINT32  mExtFileAttr;
    UINT32  mRelHdrOffset;
    /* Filename for 'mFileNameLen' */
    /* Extra for 'mExtraLen' */
    /* Comment for 'mCommentLen' */
};
typedef struct _ZIP_FILECDS ZIP_FILECDS;

struct _ZIP_FILECDS_TAIL
{
    UINT32  mMarker;
    UINT16  mDiskNum;
    UINT16  mDiskNumCDS;
    UINT16  mNumEntDisk;
    UINT16  mNumEntCDS;
    UINT32  mSizeCDS;
    UINT32  mDiskOffsetCDS;
    UINT16  mCommentLen;
    /* comment for 'mCommentLen' */
};
typedef struct _ZIP_FILECDS_TAIL ZIP_FILECDS_TAIL;

#ifdef WIN32
#pragma pack (pop)
#define STRNICMP    _strnicmp
#endif
#ifdef EPPC
#pragma pack ()
#define STRNICMP    _mystrnicmp

/* cafe doesn't have this function so it is provided here */
static int _mystrnicmp(char const *apStr1, char const *apStr2, size_t len)
{
    int c1;
    int c2;

    if (!len)
        return 0;
    do {
        c1 = (int)*apStr1; if ((c1 >='a') && (c1 <='z')) c1 -= ('a'-'A');
        c2 = (int)*apStr2; if ((c2 >='a') && (c2 <='z')) c2 -= ('a'-'A');
        if ((!c1) && (!c2))
            return 0;
        if (!c1)
            return -1;
        if (!c2)
            return 1;
        c1 -= c2;
        if (c1)
            return c1;
        apStr1++;
        apStr2++;
    } while (--len);
    return 0;
}
#endif

/* ---------------------------------------------------------------------- */

static const UINT32 sgCRC32_tab[] = 
{
    0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419,
    0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4,
    0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07,
    0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,
    0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856,
    0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
    0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4,
    0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
    0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3,
    0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC, 0x51DE003A,
    0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599,
    0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
    0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190,
    0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F,
    0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E,
    0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
    0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED,
    0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
    0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3,
    0xFBD44C65, 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,
    0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A,
    0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5,
    0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA, 0xBE0B1010,
    0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
    0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17,
    0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6,
    0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615,
    0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
    0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 0xF00F9344,
    0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
    0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A,
    0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
    0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1,
    0xA6BC5767, 0x3FB506DD, 0x48B2364B, 0xD80D2BDA, 0xAF0A1B4C,
    0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF,
    0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
    0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE,
    0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31,
    0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226, 0x756AA39C,
    0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
    0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B,
    0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
    0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1,
    0x18B74777, 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
    0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, 0xA00AE278,
    0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7,
    0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66,
    0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
    0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605,
    0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8,
    0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B,
    0x2D02EF8D
};                                                                       

UINT32 ZIPFILE_CalcCRC(UINT8 const *apData, UINT32 aDataBytes)
{
    UINT32 work;

    if (!aDataBytes)
        return 0;

    work = 0xFFFFFFFF;

    do {
        work = sgCRC32_tab[(work ^ (*apData)) & 0xFF] ^ (work >> 8);
        apData++;
    } while (--aDataBytes);

    return work ^ 0xFFFFFFFF;
}

/* ---------------------------------------------------------------------- */

static UINT32 sZIP_EntryBytes(ZIPFILE_RAW_FILEENTRY *apEntry)
{
    return sizeof(ZIPFILE_RAW_FILEENTRY) + apEntry->mCompSizeBytes + apEntry->mFileNameLen + apEntry->mExtraLen;
}

static UINT32 sZIP_CDSBytes(ZIP_FILECDS *apCDS)
{
    return sizeof(ZIP_FILECDS) + apCDS->mFileNameLen + apCDS->mExtraLen + apCDS->mCommentLen;
}

static void sZIP_SwapFILEENTRY(ZIPFILE_RAW_FILEENTRY *apEntry)
{
    apEntry->mMarker            = SWAP32(apEntry->mMarker);                
    apEntry->mMinVer            = SWAP16(apEntry->mMinVer);                
    apEntry->mFlags             = SWAP16(apEntry->mFlags);                 
    apEntry->mCompressionMethod = SWAP16(apEntry->mCompressionMethod);     
    apEntry->mDosDateTime       = SWAP32(apEntry->mDosDateTime);           
    apEntry->mCRC               = SWAP32(apEntry->mCRC);                   
    apEntry->mCompSizeBytes     = SWAP32(apEntry->mCompSizeBytes);         
    apEntry->mUncompSizeBytes   = SWAP32(apEntry->mUncompSizeBytes);       
    apEntry->mFileNameLen       = SWAP16(apEntry->mFileNameLen);           
    apEntry->mExtraLen          = SWAP16(apEntry->mExtraLen);              
}

static void sZIP_SwapCDS(ZIP_FILECDS *apCDS)
{
    apCDS->mMarker              = SWAP32(apCDS->mMarker);              
    apCDS->mFlags               = SWAP16(apCDS->mFlags);               
    apCDS->mCompressionMethod   = SWAP16(apCDS->mCompressionMethod);   
    apCDS->mModFileTime         = SWAP16(apCDS->mModFileTime);
    apCDS->mModFileDate         = SWAP16(apCDS->mModFileDate);
    apCDS->mCRC                 = SWAP32(apCDS->mCRC);
    apCDS->mCompSizeBytes       = SWAP32(apCDS->mCompSizeBytes);       
    apCDS->mUncompSizeBytes     = SWAP32(apCDS->mUncompSizeBytes);     
    apCDS->mFileNameLen         = SWAP16(apCDS->mFileNameLen);         
    apCDS->mExtraLen            = SWAP16(apCDS->mExtraLen);            
    apCDS->mCommentLen          = SWAP16(apCDS->mCommentLen);          
    apCDS->mDiskNum             = SWAP16(apCDS->mDiskNum);             
    apCDS->mIntFileAttr         = SWAP16(apCDS->mIntFileAttr);         
    apCDS->mExtFileAttr         = SWAP32(apCDS->mExtFileAttr);         
    apCDS->mRelHdrOffset        = SWAP32(apCDS->mRelHdrOffset);        
}

static void sZIP_SwapCDS_TAIL(ZIP_FILECDS_TAIL *apTail)
{
    apTail->mMarker             = SWAP32(apTail->mMarker);
    apTail->mDiskNum            = SWAP16(apTail->mDiskNum);
    apTail->mDiskNumCDS         = SWAP16(apTail->mDiskNumCDS);
    apTail->mNumEntDisk         = SWAP16(apTail->mNumEntDisk);
    apTail->mNumEntCDS          = SWAP16(apTail->mNumEntCDS);
    apTail->mSizeCDS            = SWAP32(apTail->mSizeCDS);
    apTail->mDiskOffsetCDS      = SWAP32(apTail->mDiskOffsetCDS);
    apTail->mCommentLen         = SWAP16(apTail->mCommentLen);
}

/* ---------------------------------------------------------------------- */

static int sEat_FileEntry(UINT8 const **appSrc, UINT32 *apBytesLeftInZipFile)
{
    ZIPFILE_RAW_FILEENTRY   entry;
    UINT32          chk;

    memcpy(&entry,*appSrc,sizeof(ZIPFILE_RAW_FILEENTRY));
#if (ZIPFILE_ENDIAN != ZIPFILE_ENDIAN_LITTLE)
    sZIP_SwapFILEENTRY(&entry);
#endif
    chk = sZIP_EntryBytes(&entry);
    if (chk > *apBytesLeftInZipFile)
        return ERRCODE_ZIPFILE_INVALID_FILEENTRY;
    if (entry.mUncompSizeBytes < entry.mCompSizeBytes)
        return ERRCODE_ZIPFILE_INVALID_FILEENTRY;
    *appSrc += chk;
    *apBytesLeftInZipFile -= chk;
    return 0;
}

static int sEat_CDS(UINT8 const **appSrc, UINT32 *apBytesLeftInZipFile)
{
    ZIP_FILECDS     cds;
    UINT32          chk;

    memcpy(&cds, *appSrc, sizeof(ZIP_FILECDS));
#if (ZIPFILE_ENDIAN != ZIPFILE_ENDIAN_LITTLE)
    sZIP_SwapCDS(&cds);
#endif
    chk = sZIP_CDSBytes(&cds);
    if (chk > *apBytesLeftInZipFile)
        return ERRCODE_ZIPFILE_INVALID_CDS;

    *appSrc += chk;
    *apBytesLeftInZipFile -= chk;

    return 0;
}

static int sEat_CDSTail(UINT8 const **appSrc, UINT32 *apBytesLeftInZipFile)
{
    ZIP_FILECDS_TAIL    cdsTail;
    UINT32              chk;

    memcpy(&cdsTail, *appSrc, sizeof(ZIP_FILECDS_TAIL));
#if (ZIPFILE_ENDIAN != ZIPFILE_ENDIAN_LITTLE)
    sZIP_SwapCDS_TAIL(&cdsTail);
#endif
    chk = sizeof(cdsTail) + cdsTail.mCommentLen;
    if (chk > *apBytesLeftInZipFile)
        return ERRCODE_ZIPFILE_INVALID_CDSTAIL;

    *appSrc += chk;
    *apBytesLeftInZipFile -= chk;

    return 0;
}

static int sZIP_ValidateFileStructure(UINT8 const *apFileData, UINT32 aFileBytes, UINT32 *apRetFileCount)
{
    int             err;
    UINT8 const *   pWork;
    UINT32          left;
    UINT32          chk;
    UINT32          fileCount;
    UINT32          cdsCount;

    if (apRetFileCount)
        *apRetFileCount = 0;
    fileCount = cdsCount = 0;

    if (aFileBytes < sizeof(UINT32))
        return ERRCODE_ZIPFILE_INVALID_BAD_FILESIZE;

    pWork = apFileData;
    left = aFileBytes;

    memcpy(&chk, pWork, sizeof(UINT32));
    if (chk != ZIP_RAW_FILEENTRY_MARKER)
        return ERRCODE_ZIPFILE_INVALID_NO_FILE_ENTRIES;

    /* file entries */
    do {
        if (left < sizeof(ZIPFILE_RAW_FILEENTRY))
            return ERRCODE_ZIPFILE_INVALID_UNEXPECTED_EOF;
        fileCount++;
        err = sEat_FileEntry(&pWork,&left);
        if (err)
            return err;
        if (left < sizeof(ZIP_FILECDS))
            return ERRCODE_ZIPFILE_INVALID_UNEXPECTED_EOF;
        memcpy(&chk, pWork, sizeof(UINT32));
    } while (chk == ZIP_RAW_FILEENTRY_MARKER);

    /* cds headers */
    if (chk != ZIP_FILECDS_MARKER)
        return ERRCODE_ZIPFILE_INVALID_NO_CDS;
    do {
        if ((left < sizeof(ZIP_FILECDS)) && (left < sizeof(ZIP_FILECDS_TAIL)))
            return ERRCODE_ZIPFILE_INVALID_UNEXPECTED_EOF;
        memcpy(&chk, pWork, sizeof(UINT32));
        if (chk != ZIP_FILECDS_MARKER)
            break;
        cdsCount++;
    } while (!sEat_CDS(&pWork,&left));

    if (fileCount != cdsCount)
        return ERRCODE_ZIPFILE_INVALID_BAD_FILE_COUNT;

    if (chk != ZIP_FILECDS_TAIL_MARKER)
        return ERRCODE_ZIPFILE_INVALID_NO_CDS_TAIL;

    err = sEat_CDSTail(&pWork,&left);
    if (err)
        return err;

    if (left)
        return ERRCODE_ZIPFILE_INVALID_JUNK_AT_EOF;

    if (apRetFileCount)
        *apRetFileCount = fileCount;

    return 0;
}

/* ---------------------------------------------------------------------- */

static int sCompStrLens(char const *pStr1, UINT32 strLen1, char const *pStr2, UINT32 strLen2)
{
    int c,v;

    c = ((int)strLen2) - ((int)strLen1);
    if (c > 0)
    {
        /* str2 longer than str1 */
        c = STRNICMP(pStr1, pStr2, strLen1);
        if (!c)
            return -1;
        return c;
    }
    v = STRNICMP(pStr1, pStr2, strLen2);
    if (c < 0)
    {
        /* str2 shorter than str1 name */
        if (!v)
            return 1;
    }
    return v;
}

static int sComparePaths(char const *pPath1, UINT32 path1Len, char const *pPath2, UINT32 path2Len)
{
    char const *pSlash1;
    char const *pSlash2;
    UINT32      left;
    int         c;

    pSlash1 = pPath1;
    left = path1Len;
    do {
        if (*pSlash1 == '/')
            break;
        pSlash1++;
    } while (--left);
    if (!left)
        pSlash1 = NULL;

    pSlash2 = pPath2;
    left = path2Len;
    do {
        if (*pSlash2 == '/')
            break;
        pSlash2++;
    } while (--left);
    if (!left)
        pSlash2 = NULL;

    if ((!pSlash1) && (!pSlash2))
        return sCompStrLens(pPath1,path1Len,pPath2,path2Len);

    if (pSlash1 && (!pSlash2))
        return 1;
    if ((!pSlash1) && (pSlash2))
        return -1;

    /* both have slashes */
    c = sCompStrLens(pPath1, (UINT32)(pSlash1-pPath1), pPath2, (UINT32)(pSlash2-pPath2));
    if (c)
        return c;

    /* both have slashes and are the same up to the first slash */
    left = (UINT32)(pSlash1 - pPath1);

    /* both have slashes and start with the same stuff */
    return sComparePaths(pPath1+left+1, path1Len - (left+1), pPath2+left+1, path2Len - (left+1));
}

static int sCompare(void const *p1, void const *p2)
{
    ZIPPED_FILE const * pFile1;
    ZIPPED_FILE const * pFile2;

    pFile1 = (ZIPPED_FILE const *)p1;
    pFile2 = (ZIPPED_FILE const *)p2;

    if ((!pFile1->mCompBytes) && (pFile2->mCompBytes))
        return -1;
    if ((pFile1->mCompBytes) && (!pFile2->mCompBytes))
        return 1;
    return sComparePaths(pFile1->mpNameOnly, pFile1->mNameOnlyLen, pFile2->mpNameOnly, pFile2->mNameOnlyLen);
}

static UINT32 sCountDirsNeeded(ZIPPED_FILE *apFiles, UINT32 aNumFiles)
{
    char const *    pLook;
    char const *    pComp;
    UINT32          left;
    ZIPPED_FILE *   pRest;
    UINT32          ret;
    UINT32          subLen;
    UINT32          numSub;

    /* don't need dir for files without a slash at beginning of sorted list */
    do {
        pLook = apFiles->mpNameOnly;
        left = apFiles->mNameOnlyLen;
        do {
            if (*pLook=='/')
                break;
            pLook++;
        } while (--left);
        if (left)
            break;
        apFiles++;
    } while (--aNumFiles);
    if (!aNumFiles)
        return 0;   /* no subdirs at this point */

    pLook++;
    subLen = (UINT32)(pLook-apFiles->mpNameOnly);
    if (aNumFiles==1)
    {
        apFiles->mpNameOnly += subLen;
        apFiles->mNameOnlyLen -= subLen;
        return 1 + sCountDirsNeeded(apFiles, 1);
    }

    ret = 1;
    pComp = apFiles->mpNameOnly;
    apFiles->mpNameOnly += subLen;
    apFiles->mNameOnlyLen -= subLen;
    pRest = apFiles+1;
    aNumFiles--;
    numSub = 1;
    do {
        if ((pRest->mNameOnlyLen < subLen) || (STRNICMP(pRest->mpNameOnly, pComp, subLen)))
            break;
        pRest->mpNameOnly += subLen;
        pRest->mNameOnlyLen -= subLen;
        numSub++;
        pRest++;
    } while (--aNumFiles);

    ret += sCountDirsNeeded(apFiles, numSub);

    if (aNumFiles)
        ret += sCountDirsNeeded(pRest, aNumFiles);

    return ret;
}

static void sDirify(ZIPPED_DIR *pThisDir, ZIPPED_FILE *apFiles, UINT32 aNumFiles, ZIPPED_DIR **ppFreeDir)
{
    char const *    pLook;
    char const *    pComp;
    UINT32          left;
    ZIPPED_FILE *   pRest;
    UINT32          subLen;
    UINT32          numSub;
    ZIPPED_DIR *    pNewDir;
    ZIPPED_DIR *    pPrev;

    /* don't need dir for files without a slash at beginning of sorted list */
    pRest = apFiles;
    subLen = 0;
    numSub = aNumFiles;
    do {
        pLook = pRest->mpNameOnly;
        left = pRest->mNameOnlyLen;
        do {
            if (*pLook=='/')
                break;
            pLook++;
        } while (--left);
        if (left)
            break;
        subLen++;
        pRest->mpParentDir = pThisDir;
        pRest++;
    } while (--numSub);

    if (subLen)
    {
        pThisDir->mpFilesArray = apFiles;
        pThisDir->mNumFiles = subLen;
        apFiles = pRest;
        aNumFiles -= subLen;
        if (!numSub)
            return; 
    }
    else
    {
        pThisDir->mpFilesArray = NULL;
        pThisDir->mNumFiles = 0;
    }

    /* subdirs found */

    pNewDir = *ppFreeDir;
    (*ppFreeDir)++;

    subLen = (UINT32)(pLook-apFiles->mpNameOnly);

    pNewDir->mpParentDir = pThisDir;
    pNewDir->mpNameOnly = apFiles->mpNameOnly;
    pNewDir->mNameOnlyLen = subLen;
    pNewDir->mpNextSib = NULL;
    if (!pThisDir->mpSubDirList)
        pThisDir->mpSubDirList = pNewDir;
    else
    {
        pPrev = pThisDir->mpSubDirList;
        while (pPrev->mpNextSib)
            pPrev = pPrev->mpNextSib;
        pPrev->mpNextSib = pNewDir;
    }

    pLook++;
    subLen++;

    if (aNumFiles==1)
    {
        apFiles->mpNameOnly += subLen;
        apFiles->mNameOnlyLen -= subLen;
        sDirify(pNewDir, apFiles, 1, ppFreeDir);
        return;
    }

    pComp = apFiles->mpNameOnly;
    apFiles->mpNameOnly += subLen;
    apFiles->mNameOnlyLen -= subLen;
    pRest = apFiles+1;
    aNumFiles--;
    numSub = 1;
    do {
        if ((pRest->mNameOnlyLen < subLen) || (STRNICMP(pRest->mpNameOnly, pComp, subLen)))
            break;
        pRest->mpNameOnly += subLen;
        pRest->mNameOnlyLen -= subLen;
        numSub++;
        pRest++;
    } while (--aNumFiles);

    sDirify(pNewDir, apFiles, numSub, ppFreeDir);

    if (aNumFiles)
        sDirify(pThisDir, pRest, aNumFiles, ppFreeDir);
}

int ZIPFILE_CreateDir(UINT8 const *apFileData, UINT32 aFileBytes, ZIPFILE_pf_Alloc afAlloc, ZIPFILE_pf_Free afFree, ZIPPED_DIR **appRetDir)
{
    UINT8 const *   pScan;
    int             err;
    UINT32          fileCount;
    UINT8 *         pAlloc;
    ZIPPED_FILE *   pFiles;
    ZIPPED_FILE *   pWorkFile;
    ZIPPED_DIR *    pDirs;
    ZIPFILE_RAW_FILEENTRY   entry;
    UINT32          ix;
    UINT32          dirCount;

    if (!appRetDir)
        return ERRCODE_ZIPFILE_ARG;
    *appRetDir = NULL;

    fileCount = 0;
    err = sZIP_ValidateFileStructure(apFileData, aFileBytes, &fileCount);
    if (err)
        return err;
    if (!fileCount)
        return ERRCODE_ZIPFILE_EMPTY;

    ix = sizeof(ZIPPED_FILE) * fileCount;
    pAlloc = (UINT8 *)afAlloc(ix);
    if (!pAlloc)
        return ERRCODE_ZIPFILE_OUTOFMEMORY;
    memset(pAlloc, 0, ix);
    pFiles = (ZIPPED_FILE *)pAlloc;

    pWorkFile = pFiles;
    pScan = apFileData;
    for(ix=0;ix<fileCount;ix++)
    {
        memcpy(&entry,pScan,sizeof(ZIPFILE_RAW_FILEENTRY));
#if (ZIPFILE_ENDIAN != ZIPFILE_ENDIAN_LITTLE)
        sZIP_SwapFILEENTRY(&entry);
#endif
        pWorkFile->mpNameOnly = ((char const *)pScan) + sizeof(ZIPFILE_RAW_FILEENTRY);
        pWorkFile->mNameOnlyLen = entry.mFileNameLen;
        pWorkFile->mCompBytes = entry.mCompSizeBytes;
        pWorkFile++;
        pScan += sZIP_EntryBytes(&entry);
    }

    qsort(pFiles, fileCount, sizeof(ZIPPED_FILE), sCompare);

    /* ignore empty files at the start of the sorted list */
    ix = fileCount;
    while (!pFiles->mCompBytes)
    {
        ix--;
        pFiles++;
        if (!ix)
            break;
    }
    if (!ix)
    {
        free(pAlloc);
        return ERRCODE_ZIPFILE_EMPTY;
    }

    dirCount = 1 + sCountDirsNeeded(pFiles,ix);

    /* reset and restart with a fresh allocation including the dirs we need */

    afFree(pAlloc);
    ix = (sizeof(ZIPPED_FILE)*fileCount)  + (sizeof(ZIPPED_DIR) * dirCount);
    pAlloc = (UINT8 *)afAlloc( ix );
    if (!pAlloc)
        return ERRCODE_ZIPFILE_OUTOFMEMORY;
    memset(pAlloc, 0, ix);

    pDirs = (ZIPPED_DIR *)pAlloc;
    pFiles = (ZIPPED_FILE *)(pAlloc + (sizeof(ZIPPED_DIR) * dirCount));
    *appRetDir = pDirs;
    pDirs->mpNameOnly = "";
    pDirs->mNameOnlyLen = 0;
    pDirs++;

    pWorkFile = pFiles;
    pScan = apFileData;
    for(ix=0;ix<fileCount;ix++)
    {
        memcpy(&entry,pScan,sizeof(ZIPFILE_RAW_FILEENTRY));
#if (ZIPFILE_ENDIAN != ZIPFILE_ENDIAN_LITTLE)
        sZIP_SwapFILEENTRY(&entry);
#endif
        pWorkFile->mpNameOnly = ((char const *)pScan) + sizeof(ZIPFILE_RAW_FILEENTRY);
        pWorkFile->mNameOnlyLen = entry.mFileNameLen;
        pWorkFile->mpCompData = ((UINT8 const *)pWorkFile->mpNameOnly) + entry.mFileNameLen + entry.mExtraLen;
        pWorkFile->mCompBytes = entry.mCompSizeBytes;
        pWorkFile->mUncompBytes = entry.mUncompSizeBytes;
        pWorkFile->mUncompCRC = entry.mCRC;
        pWorkFile++;
        pScan += sZIP_EntryBytes(&entry);
    }

    qsort(pFiles, fileCount, sizeof(ZIPPED_FILE), sCompare);

    /* ignore empty files at the start of the sorted list */
    while (!pFiles->mCompBytes)
    {
        fileCount--;
        pFiles++;
        if (!fileCount)
            break;
    }

    sDirify(*appRetDir, pFiles, fileCount, &pDirs);

    if (pDirs != ((*appRetDir)+dirCount))
    {
        afFree(pAlloc);
        return ERRCODE_ZIPFILE_INTERNAL;
    }

    return 0;
}

static int sFindInDir(ZIPPED_DIR *apDir, char const *apPath, ZIPPED_FILE **apRetEntryPtr)
{
    char const *    pSlash;
    char            c;
    int             partLen;
    int             err;
    UINT32          ix;
    ZIPPED_FILE *   pEntry;
    ZIPPED_DIR *    pSubDir;

    *apRetEntryPtr = NULL;

    if (!(*apPath))
        return ERRCODE_ZIPFILE_ARG;  // argument error

    pSlash = apPath;
    do {
        c = *pSlash;
        if ((!c) || (c=='/'))
            break;
        pSlash++;
    } while (1);
    partLen = (int)(pSlash - apPath);
    if (!c)
    {
        pEntry = apDir->mpFilesArray;
        for(ix=0;ix<apDir->mNumFiles;ix++)
        {
            if (pEntry->mNameOnlyLen == partLen)
            {
                if (!STRNICMP(apPath, apDir->mpFilesArray[ix].mpNameOnly, partLen))
                    break;
            }
            pEntry++;
        }
        if (ix != apDir->mNumFiles)
        {
            *apRetEntryPtr = pEntry;
            return 0;
        }
        return ERRCODE_ZIPFILE_FILENOTFOUND;  // file not found 
    }

    /* there is a slash, so this part is a subdirectory */
    pSubDir = apDir->mpSubDirList;
    if (pSubDir)
    {
        do {
            err = sFindInDir(pSubDir, apPath + partLen + 1, apRetEntryPtr);
            if (!err)
                return 0;
            pSubDir = pSubDir->mpNextSib;
        } while (pSubDir);
    }

    return ERRCODE_ZIPFILE_PATHNOTFOUND;  /* path not found */
}
int ZIPFILE_Find(ZIPPED_DIR *apDir, char const *apFileName, ZIPPED_FILE **apRetFilePtr)
{
    if ((!apDir) || (!apFileName) || (!apRetFilePtr))
        return ERRCODE_ZIPFILE_ARG;
    while (*apFileName=='/')
        apFileName++;
    return sFindInDir(apDir, apFileName, apRetFilePtr);
}