ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

stuffit.cpp

Go to the documentation of this file.
00001 /* ResidualVM - A 3D game interpreter
00002  *
00003  * ResidualVM is the legal property of its developers, whose names
00004  * are too numerous to list here. Please refer to the AUTHORS
00005  * file distributed with this source distribution.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 // StuffIt parsing based on http://code.google.com/p/theunarchiver/wiki/StuffItFormat
00024 // Compression 14 based on libxad (http://sourceforge.net/projects/libxad/)
00025 
00026 #include "engines/grim/stuffit.h"
00027 
00028 #include "common/debug.h"
00029 #include "common/memstream.h"
00030 #include "common/substream.h"
00031 
00032 namespace Grim {
00033 
00034 StuffItArchive::StuffItArchive() : Common::Archive() {
00035     _stream = nullptr;
00036 }
00037 
00038 StuffItArchive::~StuffItArchive() {
00039     close();
00040 }
00041 
00042 // Some known values of StuffIt FourCC's
00043 // EMI Mac in particular uses ST65
00044 static const uint32 s_magicNumbers[] = {
00045     MKTAG('S', 'I', 'T', '!'), MKTAG('S', 'T', '6', '5'), MKTAG('S', 'T', '5', '0'),
00046     MKTAG('S', 'T', '6', '0'), MKTAG('S', 'T', 'i', 'n'), MKTAG('S', 'T', 'i', '2'),
00047     MKTAG('S', 'T', 'i', '3'), MKTAG('S', 'T', 'i', '4'), MKTAG('S', 'T', '4', '6')
00048 };
00049 
00050 bool StuffItArchive::open(const Common::String &filename) {
00051     close();
00052 
00053     _stream = SearchMan.createReadStreamForMember(filename);
00054 
00055     if (!_stream)
00056         return false;
00057 
00058     uint32 tag = _stream->readUint32BE();
00059 
00060     // Check all the possible FourCC's
00061     bool found = false;
00062     for (int i = 0; i < ARRAYSIZE(s_magicNumbers); i++) {
00063         if (tag == s_magicNumbers[i]) {
00064             found = true;
00065             break;
00066         }
00067     }
00068 
00069     // Didn't find one, let's bail out
00070     if (!found) {
00071         close();
00072         return false;
00073     }
00074 
00075     /* uint16 fileCount = */ _stream->readUint16BE();
00076     /* uint32 archiveSize = */ _stream->readUint32BE();
00077 
00078     // Some sort of second magic number
00079     if (_stream->readUint32BE() != MKTAG('r', 'L', 'a', 'u')) {
00080         close();
00081         return false;
00082     }
00083 
00084     /* byte version = */ _stream->readByte(); // meaning not clear
00085 
00086     _stream->skip(7); // unknown
00087 
00088     while (_stream->pos() < _stream->size() && !_stream->eos()) {
00089         byte resForkCompression = _stream->readByte();
00090         byte dataForkCompression = _stream->readByte();
00091 
00092         byte fileNameLength = _stream->readByte();
00093         Common::String name;
00094 
00095         for (byte i = 0; i < fileNameLength; i++)
00096             name += (char)_stream->readByte();
00097 
00098         // Skip remaining bytes
00099         _stream->skip(63 - fileNameLength);
00100 
00101         /* uint32 fileType = */ _stream->readUint32BE();
00102         /* uint32 fileCreator = */ _stream->readUint32BE();
00103         /* uint16 finderFlags = */ _stream->readUint16BE();
00104         /* uint32 creationDate = */ _stream->readUint32BE();
00105         /* uint32 modificationDate = */ _stream->readUint32BE();
00106         uint32 resForkUncompressedSize = _stream->readUint32BE();
00107         uint32 dataForkUncompressedSize = _stream->readUint32BE();
00108         uint32 resForkCompressedSize = _stream->readUint32BE();
00109         uint32 dataForkCompressedSize = _stream->readUint32BE();
00110         /* uint16 resForkCRC = */ _stream->readUint16BE();
00111         /* uint16 dataForkCRC = */ _stream->readUint16BE();
00112         _stream->skip(6); // unknown
00113         /* uint16 headerCRC = */ _stream->readUint16BE();
00114 
00115         // Ignore directories for now
00116         if (dataForkCompression == 32 || dataForkCompression == 33)
00117             continue;
00118 
00119         if (dataForkUncompressedSize != 0) {
00120             // We have a data fork
00121 
00122             FileEntry entry;
00123             entry.compression = dataForkCompression;
00124             entry.uncompressedSize = dataForkUncompressedSize;
00125             entry.compressedSize = dataForkCompressedSize;
00126             entry.offset = _stream->pos() + resForkCompressedSize;
00127             _map[name] = entry;
00128 
00129             debug(0, "StuffIt file '%s', Compression = %d", name.c_str(), entry.compression);
00130         }
00131 
00132         if (resForkUncompressedSize != 0) {
00133             // We have a resource fork
00134 
00135             // Add a .rsrc extension so we know it's the resource fork
00136             name += ".rsrc";
00137 
00138             FileEntry entry;
00139             entry.compression = resForkCompression;
00140             entry.uncompressedSize = resForkUncompressedSize;
00141             entry.compressedSize = resForkCompressedSize;
00142             entry.offset = _stream->pos();
00143             _map[name] = entry;
00144 
00145             debug(0, "StuffIt file '%s', Compression = %d", name.c_str(), entry.compression);
00146         }
00147 
00148         // Go to the next entry
00149         _stream->skip(dataForkCompressedSize + resForkCompressedSize);
00150     }
00151 
00152     return true;
00153 }
00154 
00155 void StuffItArchive::close() {
00156     delete _stream; _stream = nullptr;
00157     _map.clear();
00158 }
00159 
00160 bool StuffItArchive::hasFile(const Common::String &name) const {
00161     return _map.contains(name);
00162 }
00163 
00164 int StuffItArchive::listMembers(Common::ArchiveMemberList &list) const {
00165     for (FileMap::const_iterator it = _map.begin(); it != _map.end(); it++)
00166         list.push_back(getMember(it->_key));
00167 
00168     return _map.size();
00169 }
00170 
00171 const Common::ArchiveMemberPtr StuffItArchive::getMember(const Common::String &name) const {
00172     return Common::ArchiveMemberPtr(new Common::GenericArchiveMember(name, this));
00173 }
00174 
00175 Common::SeekableReadStream *StuffItArchive::createReadStreamForMember(const Common::String &name) const {
00176     if (!_stream || !_map.contains(name))
00177         return nullptr;
00178 
00179     const FileEntry &entry = _map[name];
00180 
00181     if (entry.compression & 0xF0)
00182         error("Unhandled StuffIt encryption");
00183 
00184     Common::SeekableSubReadStream subStream(_stream, entry.offset, entry.offset + entry.compressedSize);
00185 
00186     // We currently only support type 14 compression
00187     switch (entry.compression) {
00188     case 14: // Installer
00189         return decompress14(&subStream, entry.uncompressedSize);
00190     default:
00191         error("Unhandled StuffIt compression %d", entry.compression);
00192     }
00193 
00194     return nullptr;
00195 }
00196 
00197 void StuffItArchive::update14(uint16 first, uint16 last, byte *code, uint16 *freq) const {
00198     uint16 i, j;
00199 
00200     while (last - first > 1) {
00201         i = first;
00202         j = last;
00203 
00204         do {
00205             while (++i < last && code[first] > code[i])
00206                 ;
00207 
00208             while (--j > first && code[first] < code[j])
00209                 ;
00210 
00211             if (j > i) {
00212                 SWAP(code[i], code[j]);
00213                 SWAP(freq[i], freq[j]);
00214             }
00215         } while (j > i);
00216 
00217         if (first != j) {
00218             SWAP(code[first], code[j]);
00219             SWAP(freq[first], freq[j]);
00220 
00221             i = j + 1;
00222 
00223             if (last - i <= j - first) {
00224                 update14(i, last, code, freq);
00225                 last = j;
00226             } else {
00227                 update14(first, j, code, freq);
00228                 first = i;
00229             }
00230         } else {
00231             ++first;
00232         }
00233     }
00234 }
00235 
00236 struct SIT14Data {
00237     byte code[308];
00238     byte codecopy[308];
00239     uint16 freq[308];
00240     uint32 buff[308];
00241 
00242     byte var1[52];
00243     uint16 var2[52];
00244     uint16 var3[75 * 2];
00245 
00246     byte var4[76];
00247     uint32 var5[75];
00248     byte var6[1024];
00249     uint16 var7[308 * 2];
00250     byte var8[0x4000];
00251 
00252     byte window[0x40000];
00253 };
00254 
00255 // Realign to a byte boundary
00256 #define ALIGN_BITS(b) \
00257     if (b->pos() & 7) \
00258         b->skip(8 - (b->pos() & 7))
00259 
00260 void StuffItArchive::readTree14(Common::BitStream8LSB *bits, SIT14Data *dat, uint16 codesize, uint16 *result) const {
00261     uint32 i, l, n;
00262     uint32 k = bits->getBit();
00263     uint32 j = bits->getBits(2) + 2;
00264     uint32 o = bits->getBits(3) + 1;
00265     uint32 size = 1 << j;
00266     uint32 m = size - 1;
00267     k = k ? (m - 1) : 0xFFFFFFFF;
00268 
00269     if (bits->getBits(2) & 1) { // skip 1 bit!
00270         // requirements for this call: dat->buff[32], dat->code[32], dat->freq[32*2]
00271         readTree14(bits, dat, size, dat->freq);
00272 
00273         for (i = 0; i < codesize; ) {
00274             l = 0;
00275 
00276             do {
00277                 l = dat->freq[l + bits->getBit()];
00278                 n = size << 1;
00279             } while (n > l);
00280 
00281             l -= n;
00282 
00283             if (k != l) {
00284                 if (l == m) {
00285                     l = 0;
00286 
00287                     do {
00288                         l = dat->freq[l + bits->getBit()];
00289                         n = size <<  1;
00290                     } while (n > l);
00291 
00292                     l += 3 - n;
00293 
00294                     while (l--) {
00295                         dat->code[i] = dat->code[i - 1];
00296                         ++i;
00297                     }
00298                 } else {
00299                     dat->code[i++] = l + o;
00300                 }
00301             } else {
00302                 dat->code[i++] = 0;
00303             }
00304         }
00305     } else {
00306         for (i = 0; i < codesize; ) {
00307             l = bits->getBits(j);
00308 
00309             if (k != l) {
00310                 if (l == m) {
00311                     l = bits->getBits(j) + 3;
00312 
00313                     while (l--) {
00314                         dat->code[i] = dat->code[i - 1];
00315                         ++i;
00316                     }
00317                 } else {
00318                     dat->code[i++] = l + o;
00319                 }
00320             } else {
00321                 dat->code[i++] = 0;
00322             }
00323         }
00324     }
00325 
00326     for (i = 0; i < codesize; ++i) {
00327         dat->codecopy[i] = dat->code[i];
00328         dat->freq[i] = i;
00329     }
00330 
00331     update14(0, codesize, dat->codecopy, dat->freq);
00332 
00333     for (i = 0; i < codesize && !dat->codecopy[i]; ++i)
00334         ; // find first nonempty
00335 
00336     for (j = 0; i < codesize; ++i, ++j) {
00337         if (i)
00338             j <<= (dat->codecopy[i] - dat->codecopy[i - 1]);
00339 
00340         k = dat->codecopy[i];
00341         m = 0;
00342 
00343         for (l = j; k--; l >>= 1)
00344             m = (m << 1) | (l & 1);
00345 
00346         dat->buff[dat->freq[i]] = m;
00347     }
00348 
00349     for (i = 0; i < (uint32)codesize * 2; ++i)
00350         result[i] = 0;
00351 
00352     j = 2;
00353 
00354     for (i = 0; i < codesize; ++i) {
00355         l = 0;
00356         m = dat->buff[i];
00357 
00358         for (k = 0; k < dat->code[i]; ++k) {
00359             l += (m & 1);
00360 
00361             if (dat->code[i] - 1 <= (int32)k) {
00362                 result[l] = codesize * 2 + i;
00363             } else {
00364                 if (!result[l]) {
00365                     result[l] = j;
00366                     j += 2;
00367                 }
00368 
00369                 l = result[l];
00370             }
00371 
00372             m >>= 1;
00373         }
00374     }
00375 
00376     ALIGN_BITS(bits);
00377 }
00378 
00379 #define OUTPUT_VAL(x) \
00380     out.writeByte(x); \
00381     dat->window[j++] = x; \
00382     j &= 0x3FFFF
00383 
00384 Common::SeekableReadStream *StuffItArchive::decompress14(Common::SeekableReadStream *src, uint32 uncompressedSize) const {
00385     byte *dst = new byte[uncompressedSize];
00386     Common::MemoryWriteStream out(dst, uncompressedSize);
00387 
00388     Common::BitStream8LSB *bits = new Common::BitStream8LSB(src);
00389 
00390     uint32 i, j, k, l, m, n;
00391 
00392     SIT14Data *dat = new SIT14Data();
00393 
00394     // initialization
00395     for (i = k = 0; i < 52; ++i) {
00396         dat->var2[i] = k;
00397         k += (1 << (dat->var1[i] = ((i >= 4) ? ((i - 4) >> 2) : 0)));
00398     }
00399 
00400     for (i = 0; i < 4; ++i)
00401         dat->var8[i] = i;
00402 
00403     for (m = 1, l = 4; i < 0x4000; m <<= 1) // i is 4
00404         for (n = l + 4; l < n; ++l)
00405             for (j = 0; j < m; ++j)
00406                 dat->var8[i++] = l;
00407 
00408     for (i = 0, k = 1; i < 75; ++i) {
00409         dat->var5[i] = k;
00410         k += (1 << (dat->var4[i] = (i >= 3 ? ((i - 3) >> 2) : 0)));
00411     }
00412 
00413     for (i = 0; i < 4; ++i)
00414         dat->var6[i] = i - 1;
00415 
00416     for (m = 1, l = 3; i < 0x400; m <<= 1) // i is 4
00417         for (n = l + 4; l < n; ++l)
00418             for (j = 0; j < m; ++j)
00419                 dat->var6[i++] = l;
00420 
00421     m = bits->getBits(16); // number of blocks
00422     j = 0; // window position
00423 
00424     while (m-- && !bits->eos()) {
00425         bits->getBits(16); // skip crunched block size
00426         bits->getBits(16);
00427         n = bits->getBits(16); // number of uncrunched bytes
00428         n |= bits->getBits(16) << 16;
00429         readTree14(bits, dat, 308, dat->var7);
00430         readTree14(bits, dat, 75, dat->var3);
00431 
00432         while (n && !bits->eos()) {
00433             for (i = 0; i < 616;)
00434                 i = dat->var7[i + bits->getBit()];
00435 
00436             i -= 616;
00437 
00438             if (i < 0x100) {
00439                 OUTPUT_VAL(i);
00440                 --n;
00441             } else {
00442                 i -= 0x100;
00443                 k = dat->var2[i] + 4;
00444                 i = dat->var1[i];
00445 
00446                 if (i)
00447                     k += bits->getBits(i);
00448 
00449                 for (i = 0; i < 150;)
00450                     i = dat->var3[i + bits->getBit()];
00451 
00452                 i -= 150;
00453                 l = dat->var5[i];
00454                 i = dat->var4[i];
00455 
00456                 if (i)
00457                     l += bits->getBits(i);
00458 
00459                 n -= k;
00460                 l = j + 0x40000 - l;
00461 
00462                 while (k--) {
00463                     l &= 0x3FFFF;
00464                     OUTPUT_VAL(dat->window[l]);
00465                     l++;
00466                 }
00467             }
00468         }
00469 
00470         ALIGN_BITS(bits);
00471     }
00472 
00473     delete dat;
00474     delete bits;
00475 
00476     return new Common::MemoryReadStream(dst, uncompressedSize, DisposeAfterUse::YES);
00477 }
00478 
00479 #undef OUTPUT_VAL
00480 #undef ALIGN_BITS
00481 
00482 } // End of namespace Grim


Generated on Sat May 25 2019 05:00:54 for ResidualVM by doxygen 1.7.1
curved edge   curved edge