Merge pull request #243 from ladislav-zezula/LZ_DefragmentHashTableBug

HashTableDefragmentationRemoved

6 files changed, 84 insertions, 56 deletions

diff --git a/src/SBaseCommon.cpp b/src/SBaseCommon.cpp
index 5b81bad..1209719 100644
--- a/src/SBaseCommon.cpp
+++ b/src/SBaseCommon.cpp
@@ -992,7 +992,7 @@ void * LoadMpqTable(
     DWORD dwCompressedSize,

     DWORD dwTableSize,

     DWORD dwKey,

-    bool * pbTableIsCut)

+    DWORD * PtrRealTableSize)

 {

     ULONGLONG FileSize = 0;

     LPBYTE pbCompressed = NULL;

@@ -1037,13 +1037,15 @@ void * LoadMpqTable(
                 // Fill the extra data with zeros

                 dwBytesToRead = (DWORD)(FileSize - ByteOffset);

                 memset(pbMpqTable + dwBytesToRead, 0, (dwTableSize - dwBytesToRead));

-

-                // Give the caller information that the table was cut

-                if(pbTableIsCut != NULL)

-                    pbTableIsCut[0] = true;

             }

         }

 

+        // Give the caller information that the table was cut

+        if(PtrRealTableSize != NULL)

+        {

+            PtrRealTableSize[0] = dwBytesToRead;

+        }

+

         // If everything succeeded, read the raw table from the MPQ

         if(FileStream_Read(ha->pStream, &ByteOffset, pbToRead, dwBytesToRead))

         {

diff --git a/src/SBaseFileTable.cpp b/src/SBaseFileTable.cpp
index 90b7aa4..94e4469 100644
--- a/src/SBaseFileTable.cpp
+++ b/src/SBaseFileTable.cpp
@@ -769,7 +769,6 @@ static TMPQHash * GetHashEntryLocale(TMPQArchive * ha, const char * szFileName,
 {

     TMPQHash * pFirstHash = GetFirstHashEntry(ha, szFileName);

     TMPQHash * pBestEntry = NULL;

-    TMPQHash * p1stEntry = NULL;

     TMPQHash * pHash = pFirstHash;

 

     // Parse the found hashes

@@ -789,7 +788,6 @@ static TMPQHash * GetHashEntryLocale(TMPQArchive * ha, const char * szFileName,
         {

             if(pHash->Platform == 0 || pHash->Platform == Platform)

             {

-                p1stEntry = (p1stEntry != NULL) ? p1stEntry : pHash;

                 pBestEntry = pHash;

             }

         }

@@ -798,17 +796,7 @@ static TMPQHash * GetHashEntryLocale(TMPQArchive * ha, const char * szFileName,
         pHash = GetNextHashEntry(ha, pFirstHash, pHash);

     }

 

-    //

-    // Different processing (Starcraft vs. Warcraft III), abused by some protectors

-    // 

-    // * Starcraft I:  for an entry with locale&platform = 0, then the first entry is returned

-    //   Map: MPQ_2022_v1_Sniper.scx

-    // * Warcraft III: for an entry with locale&platform = 0, then the last entry is returned

-    //   Map: MPQ_2015_v1_ProtectedMap_Spazy.w3x

-    // 

-

-    if(ha->dwValidFileFlags == MPQ_FILE_VALID_FLAGS_SCX)

-        return p1stEntry;

+    // Return the best entry that we found

     return pBestEntry;

 }

 

@@ -840,6 +828,7 @@ static TMPQHash * GetHashEntryExact(TMPQArchive * ha, const char * szFileName, L
 // are not HASH_ENTRY_FREE, the startup search index does not matter.

 // Hash table is circular, so as long as there is no terminator,

 // all entries will be found.

+/*

 static TMPQHash * DefragmentHashTable(

     TMPQArchive * ha,

     TMPQHash  * pHashTable,

@@ -894,6 +883,7 @@ static TMPQHash * DefragmentHashTable(
 

     return pHashTable;

 }

+*/

 

 static DWORD BuildFileTableFromBlockTable(

     TMPQArchive * ha,

@@ -911,12 +901,24 @@ static DWORD BuildFileTableFromBlockTable(
     assert(ha->pFileTable != NULL);

     assert(ha->dwFileTableSize >= ha->dwMaxFileCount);

 

-    // Defragment the hash table, if needed

-    if(ha->dwFlags & MPQ_FLAG_HASH_TABLE_CUT)

-    {

-        ha->pHashTable = DefragmentHashTable(ha, ha->pHashTable, pBlockTable);

-        ha->dwMaxFileCount = pHeader->dwHashTableSize;

-    }

+    //

+    // Defragmentation of the hash table was removed. The reason is a MPQ protector,

+    // two hash entries with the same name, where only the second one is valid.

+    // The index of the first entry (HashString(szFileName, 0)) points to the second one:

+    //

+    //      NameA     NameB     BlkIdx    Name

+    //      B701656E  FCFB1EED  0000001C  staredit\scenario.chk (correct one)

+    // -->  B701656E  FCFB1EED  0000001D  staredit\scenario.chk (corrupt one)

+    //

+    // Defragmenting the hash table corrupts the order and "staredit\scenario.chk" can't be read

+    // Example MPQ: MPQ_2022_v1_Sniper.scx

+    //

+

+    //if(ha->dwFlags & MPQ_FLAG_HASH_TABLE_CUT)

+    //{

+    //    ha->pHashTable = DefragmentHashTable(ha, ha->pHashTable, pBlockTable);

+    //    ha->dwMaxFileCount = pHeader->dwHashTableSize;

+    //}

 

     // If the hash table or block table is cut,

     // we will defragment the block table

@@ -2327,7 +2329,7 @@ static TMPQHash * LoadHashTable(TMPQArchive * ha)
     TMPQHash * pHashTable = NULL;

     DWORD dwTableSize;

     DWORD dwCmpSize;

-    bool bHashTableIsCut = false;

+    DWORD dwRealTableSize = 0;

 

     // Note: It is allowed to load hash table if it is at offset 0.

     // Example: MPQ_2016_v1_ProtectedMap_HashOffsIsZero.w3x

@@ -2349,12 +2351,15 @@ static TMPQHash * LoadHashTable(TMPQArchive * ha)
             dwCmpSize = (DWORD)pHeader->HashTableSize64;

 

             // Read, decrypt and uncompress the hash table

-            pHashTable = (TMPQHash *)LoadMpqTable(ha, ByteOffset, pHeader->MD5_HashTable, dwCmpSize, dwTableSize, g_dwHashTableKey, &bHashTableIsCut);

+            pHashTable = (TMPQHash *)LoadMpqTable(ha, ByteOffset, pHeader->MD5_HashTable, dwCmpSize, dwTableSize, g_dwHashTableKey, &dwRealTableSize);

 //          DumpHashTable(pHashTable, pHeader->dwHashTableSize);

 

             // If the hash table was cut, we can/have to defragment it

-            if(pHashTable != NULL && bHashTableIsCut)

+            if(pHashTable != NULL && dwRealTableSize != 0 && dwRealTableSize < dwTableSize)

+            {

+                ha->dwRealHashTableSize = dwRealTableSize;

                 ha->dwFlags |= (MPQ_FLAG_MALFORMED | MPQ_FLAG_HASH_TABLE_CUT);

+            }

             break;

 

         case MPQ_SUBTYPE_SQP:

@@ -2388,7 +2393,7 @@ TMPQBlock * LoadBlockTable(TMPQArchive * ha, bool /* bDontFixEntries */)
     ULONGLONG ByteOffset;

     DWORD dwTableSize;

     DWORD dwCmpSize;

-    bool bBlockTableIsCut = false;

+    DWORD dwRealTableSize;

 

     // Note: It is possible that the block table starts at offset 0

     // Example: MPQ_2016_v1_ProtectedMap_HashOffsIsZero.w3x

@@ -2410,10 +2415,10 @@ TMPQBlock * LoadBlockTable(TMPQArchive * ha, bool /* bDontFixEntries */)
             dwCmpSize = (DWORD)pHeader->BlockTableSize64;

 

             // Read, decrypt and uncompress the block table

-            pBlockTable = (TMPQBlock * )LoadMpqTable(ha, ByteOffset, NULL, dwCmpSize, dwTableSize, g_dwBlockTableKey, &bBlockTableIsCut);

+            pBlockTable = (TMPQBlock * )LoadMpqTable(ha, ByteOffset, NULL, dwCmpSize, dwTableSize, g_dwBlockTableKey, &dwRealTableSize);

 

             // If the block table was cut, we need to remember it

-            if(pBlockTable != NULL && bBlockTableIsCut)

+            if(pBlockTable != NULL && dwRealTableSize && dwRealTableSize < dwTableSize)

                 ha->dwFlags |= (MPQ_FLAG_MALFORMED | MPQ_FLAG_BLOCK_TABLE_CUT);

             break;

 

diff --git a/src/SFileListFile.cpp b/src/SFileListFile.cpp
index a1e16b0..8ce9ae4 100644
--- a/src/SFileListFile.cpp
+++ b/src/SFileListFile.cpp
@@ -409,8 +409,10 @@ static LPBYTE CreateListFile(TMPQArchive * ha, DWORD * pcbListFile)
 static DWORD SListFileCreateNodeForAllLocales(TMPQArchive * ha, const char * szFileName)

 {

     TFileEntry * pFileEntry;

-    TMPQHash * pFirstHash;

+    TMPQHash * pHashEnd;

     TMPQHash * pHash;

+    DWORD dwName1;

+    DWORD dwName2;

 

     // If we have HET table, use that one

     if(ha->pHetTable != NULL)

@@ -428,17 +430,39 @@ static DWORD SListFileCreateNodeForAllLocales(TMPQArchive * ha, const char * szF
     // If we have hash table, we use it

     if(ha->pHashTable != NULL)

     {

-        // Go while we found something

-        pFirstHash = pHash = GetFirstHashEntry(ha, szFileName);

-        while(pHash != NULL)

+        // Get the end of the hash table and both names

+        pHashEnd = ha->pHashTable + ha->pHeader->dwHashTableSize;

+        dwName1 = ha->pfnHashString(szFileName, MPQ_HASH_NAME_A);

+        dwName2 = ha->pfnHashString(szFileName, MPQ_HASH_NAME_B);

+

+        // Some protectors set very high hash table size (0x00400000 items or more)

+        // in order to make this process very slow. We will ignore items

+        // in the hash table that would be beyond the end of the file.

+        // Example MPQ: MPQ_2022_v1_Sniper.scx

+        if(ha->dwFlags & MPQ_FLAG_HASH_TABLE_CUT)

+            pHashEnd = ha->pHashTable + (ha->dwRealHashTableSize / sizeof(TMPQHash));

+

+        // Go through the hash table and put the name in each item that has the same name pair

+        for(pHash = ha->pHashTable; pHash < pHashEnd; pHash++)

         {

-            // Allocate file name for the file entry

-            AllocateFileName(ha, ha->pFileTable + MPQ_BLOCK_INDEX(pHash), szFileName);

-

-            // Now find the next language version of the file

-            pHash = GetNextHashEntry(ha, pFirstHash, pHash);

+            if(pHash->dwName1 == dwName1 && pHash->dwName2 == dwName2 && MPQ_BLOCK_INDEX(pHash) < ha->dwFileTableSize)

+            {

+                // Allocate file name for the file entry

+                AllocateFileName(ha, ha->pFileTable + MPQ_BLOCK_INDEX(pHash), szFileName);

+            }

         }

 

+        // Go while we found something

+        //pFirstHash = pHash = GetFirstHashEntry(ha, szFileName);

+        //while(pHash != NULL)

+        //{

+        //    // Allocate file name for the file entry

+        //    AllocateFileName(ha, ha->pFileTable + MPQ_BLOCK_INDEX(pHash), szFileName);

+

+        //    // Now find the next language version of the file

+        //    pHash = GetNextHashEntry(ha, pFirstHash, pHash);

+        //}

+

         return ERROR_SUCCESS;

     }

 

diff --git a/src/StormCommon.h b/src/StormCommon.h
index f452112..865d975 100644
--- a/src/StormCommon.h
+++ b/src/StormCommon.h
@@ -318,7 +318,7 @@ int SCompDecompressMpk(void * pvOutBuffer, int * pcbOutBuffer, void * pvInBuffer
 

 TMPQFile * CreateFileHandle(TMPQArchive * ha, TFileEntry * pFileEntry);

 TMPQFile * CreateWritableHandle(TMPQArchive * ha, DWORD dwFileSize);

-void * LoadMpqTable(TMPQArchive * ha, ULONGLONG ByteOffset, LPBYTE pbTableHash, DWORD dwCompressedSize, DWORD dwRealSize, DWORD dwKey, bool * pbTableIsCut);

+void * LoadMpqTable(TMPQArchive * ha, ULONGLONG ByteOffset, LPBYTE pbTableHash, DWORD dwCompressedSize, DWORD dwRealSize, DWORD dwKey, DWORD * PtrRealTableSize);

 DWORD AllocateSectorBuffer(TMPQFile * hf);

 DWORD AllocatePatchInfo(TMPQFile * hf, bool bLoadFromFile);

 DWORD AllocateSectorOffsets(TMPQFile * hf, bool bLoadFromFile);

diff --git a/src/StormLib.h b/src/StormLib.h
index adfa616..d95c2a2 100644
--- a/src/StormLib.h
+++ b/src/StormLib.h
@@ -844,6 +844,7 @@ typedef struct _TMPQArchive
     DWORD          dwFileFlags3;                // Flags for (signature)
     DWORD          dwAttrFlags;                 // Flags for the (attributes) file, see MPQ_ATTRIBUTE_XXX
     DWORD          dwValidFileFlags;            // Valid flags for the current MPQ
+    DWORD          dwRealHashTableSize;         // Real size of the hash table, if MPQ_FLAG_HASH_TABLE_CUT is zet in dwFlags
     DWORD          dwFlags;                     // See MPQ_FLAG_XXXXX
     DWORD          dwSubType;                   // See MPQ_SUBTYPE_XXX
 
diff --git a/test/StormTest.cpp b/test/StormTest.cpp
index 4e8e600..53d2125 100644
--- a/test/StormTest.cpp
+++ b/test/StormTest.cpp
@@ -4269,18 +4269,18 @@ static const TEST_INFO Test_Mpqs[] =
     {_T("MPQ_2014_v1_ProtectedMap_Spazzler2.w3x"),           NULL, TEST_DATA("72d7963aa799a7fb4117c55b7beabaf9", 470)},     // Warcraft III map locked by the Spazzler protector

     {_T("MPQ_2014_v1_ProtectedMap_Spazzler3.w3x"),           NULL, TEST_DATA("e55aad2dd33cf68b372ca8e30dcb78a7", 130)},     // Warcraft III map locked by the Spazzler protector

     {_T("MPQ_2002_v1_ProtectedMap_BOBA.w3m"),                NULL, TEST_DATA("7b725d87e07a2173c42fe2314b95fa6c", 17)},      // Warcraft III map locked by the BOBA protector

-    {_T("MPQ_2015_v1_ProtectedMap_KangTooJee.w3x"),          NULL, TEST_DATA("c7ca4d2d0b1e58db5c784f522506c897", 1578)},

+    {_T("MPQ_2015_v1_ProtectedMap_KangTooJee.w3x"),          NULL, TEST_DATA("44111a3edf7645bc44bb1afd3a813576", 1715)},

     {_T("MPQ_2015_v1_ProtectedMap_Somj2hM16.w3x"),           NULL, TEST_DATA("b411f9a51a6e9a9a509150c8d66ba359", 92)},

     {_T("MPQ_2015_v1_ProtectedMap_Spazy.w3x"),               NULL, TEST_DATA("6e491bd055511435dcb4d9c8baed0516", 4089)},    // Warcraft III map locked by Spazy protector

     {_T("MPQ_2015_v1_MessListFile.mpq"),                     NULL, TEST_DATA("15e25d5be124d8ad71519f967997efc2", 8)},

     {_T("MPQ_2016_v1_ProtectedMap_TableSizeOverflow.w3x"),   NULL, TEST_DATA("ad81b43cbd37bbfa27e4bed4c17e6a81", 176)},

     {_T("MPQ_2016_v1_ProtectedMap_HashOffsIsZero.w3x"),      NULL, TEST_DATA("d6e712c275a26dc51f16b3a02f6187df", 228)},

     {_T("MPQ_2016_v1_ProtectedMap_Somj2.w3x"),               NULL, TEST_DATA("457cdbf97a9ca41cfe8ea130dafaa0bb", 21)},      // Something like Somj 2.0

-    {_T("MPQ_2016_v1_WME4_4.w3x"),                           NULL, TEST_DATA("e85e1c0ccb4465a30ffd07cae3260254", 382)},     // Protector from China (2016-05-27)

+    {_T("MPQ_2016_v1_WME4_4.w3x"),                           NULL, TEST_DATA("7ec2f4d0f3982d8b12d88bc08ef0c1fb", 640)},     // Protector from China (2016-05-27)

     {_T("MPQ_2016_v1_SP_(4)Adrenaline.w3x"),                 NULL, TEST_DATA("b6f6d56f4f8aaef04c2c4b1f08881a8b", 16)},

     {_T("MPQ_2016_v1_ProtectedMap_1.4.w3x"),                 NULL, TEST_DATA("3c7908b29d3feac9ec952282390a242d", 5027)},

     {_T("MPQ_2016_v1_KoreanFile.w3m"),                       NULL, TEST_DATA("805d1f75712472a81c6df27b2a71f946", 18)},

-    {_T("MPQ_2017_v1_Eden_RPG_S2_2.5J.w3x"),                 NULL, TEST_DATA("21c3dc3a66b76c57c84cc8c7e2dd846b", 16300)},   // Protected by PG1.11.973

+    {_T("MPQ_2017_v1_Eden_RPG_S2_2.5J.w3x"),                 NULL, TEST_DATA("cbe1fd7ed5ed2fc005fba9beafcefe40", 16334)},   // Protected by PG1.11.973

     {_T("MPQ_2017_v1_BigDummyFiles.w3x"),                    NULL, TEST_DATA("f4d2ee9d85d2c4107e0b2d00ff302dd7", 9086)},

     {_T("MPQ_2017_v1_TildeInFileName.mpq"),                  NULL, TEST_DATA("f203e3979247a4dbf7f3828695ac810c", 5)},

     {_T("MPQ_2018_v1_EWIX_v8_7.w3x"),                        NULL, TEST_DATA("12c0f4e15c7361b7c13acd37a181d83b", 857), "BlueCrystal.mdx"},

@@ -4290,7 +4290,8 @@ static const TEST_INFO Test_Mpqs[] =
     {_T("MPQ_2015_v1_flem1.w3x"),                            NULL, TEST_DATA("1c4c13e627658c473e84d94371e31f37", 20)},

     {_T("MPQ_2002_v1_ProtectedMap_HashTable_FakeValid.w3x"), NULL, TEST_DATA("5250975ed917375fc6540d7be436d4de", 114)},

     {_T("MPQ_2021_v1_CantExtractCHK.scx"),                   NULL, TEST_DATA("055fd548a789c910d9dd37472ecc1e66", 28)},

-    {_T("MPQ_2022_v1_Sniper.scx"),                           NULL, TEST_DATA("2e955271b70b79344ad85b698f6ce9d8", 63)},      // Multiple items in hash table for staredit\scenario.chk (locale=0, platform=0)

+    {_T("MPQ_2022_v1_Sniper.scx"),                           NULL, TEST_DATA("2e955271b70b79344ad85b698f6ce9d8", 64)},      // Multiple items in hash table for staredit\scenario.chk (locale=0, platform=0)

+    {_T("MPQ_2022_v1_OcOc_Bound_2.scx"),                     NULL, TEST_DATA("25cad16a2fb4e883767a1f512fc1dce7", 16)},

 };

 

 static const TEST_INFO Patched_Mpqs[] =

@@ -4330,7 +4331,7 @@ int _tmain(int argc, TCHAR * argv[])
 

     for(int i = 2; i < argc; i++)

     {

-        TestArchive(argv[i], NULL, TFLG_FILE_LOCALE | 0x0000, "staredit\\scenario.chk", NULL);

+        TestArchive(argv[i], Bliz, TFLG_FILE_LOCALE | 0x0409, "staredit\\scenario.chk", NULL);

     }

 

     //

@@ -4344,15 +4345,6 @@ int _tmain(int argc, TCHAR * argv[])
     }

 

     //

-    // Search all testing archives and verify their SHA1 hash

-    //

-

-    if(dwErrCode == ERROR_SUCCESS)

-    {

-        dwErrCode = FindFiles(ForEachFile_VerifyFileChecksum, szMpqSubDir);

-    }

-

-    //

     // Test file stream operations

     //

 

@@ -4421,14 +4413,18 @@ int _tmain(int argc, TCHAR * argv[])
         }

     }

 

-    // Open the multi-file archive with wrong prefix to see how StormLib deals with it

+    // Veryfy SHA1 of each MPQ that we have in the list

     if(dwErrCode == ERROR_SUCCESS)

-        dwErrCode = TestOpenArchive_WillFail(_T("flat-file://streaming/model.MPQ.0"));

+        dwErrCode = FindFiles(ForEachFile_VerifyFileChecksum, szMpqSubDir);

 

     // Open every MPQ that we have in the storage

     if(dwErrCode == ERROR_SUCCESS)

         dwErrCode = FindFiles(ForEachFile_OpenArchive, NULL);

 

+    // Open the multi-file archive with wrong prefix to see how StormLib deals with it

+    if(dwErrCode == ERROR_SUCCESS)

+        dwErrCode = TestOpenArchive_WillFail(_T("flat-file://streaming/model.MPQ.0"));

+

     // Test on an archive that has been invalidated by extending an old valid MPQ

     if(dwErrCode == ERROR_SUCCESS)

         dwErrCode = TestOpenArchive_Corrupt(_T("MPQ_2013_vX_Battle.net.MPQ"));