1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 // StuffIt parsing based on http://code.google.com/p/theunarchiver/wiki/StuffItFormat
24 // Compression 14 based on libxad (http://sourceforge.net/projects/libxad/)
25
26 #include "common/stuffit.h"
27
28 #include "common/archive.h"
29 #include "common/bitstream.h"
30 #include "common/debug.h"
31 #include "common/hash-str.h"
32 #include "common/hashmap.h"
33 #include "common/memstream.h"
34 #include "common/substream.h"
35
36 namespace Common {
37
38 struct SIT14Data;
39
40 class StuffItArchive : public Common::Archive {
41 public:
42 StuffItArchive();
43 ~StuffItArchive() override;
44
45 bool open(const Common::String &filename);
46 void close();
isOpen() const47 bool isOpen() const { return _stream != 0; }
48
49 // Common::Archive API implementation
50 bool hasFile(const Common::Path &path) const override;
51 int listMembers(Common::ArchiveMemberList &list) const override;
52 const Common::ArchiveMemberPtr getMember(const Common::Path &path) const override;
53 Common::SeekableReadStream *createReadStreamForMember(const Common::Path &path) const override;
54
55 private:
56 struct FileEntry {
57 byte compression;
58 uint32 uncompressedSize;
59 uint32 compressedSize;
60 uint32 offset;
61 };
62
63 Common::SeekableReadStream *_stream;
64
65 typedef Common::HashMap<Common::String, FileEntry, Common::IgnoreCase_Hash, Common::IgnoreCase_EqualTo> FileMap;
66 FileMap _map;
67
68 // Decompression Functions
69 Common::SeekableReadStream *decompress14(Common::SeekableReadStream *src, uint32 uncompressedSize) const;
70
71 // Decompression Helpers
72 void update14(uint16 first, uint16 last, byte *code, uint16 *freq) const;
73 void readTree14(Common::BitStream8LSB *bits, SIT14Data *dat, uint16 codesize, uint16 *result) const;
74 };
75
StuffItArchive()76 StuffItArchive::StuffItArchive() : Common::Archive() {
77 _stream = nullptr;
78 }
79
~StuffItArchive()80 StuffItArchive::~StuffItArchive() {
81 close();
82 }
83
84 // Some known values of StuffIt FourCC's
85 // 11H Mac in particular uses ST46, while EMI Mac uses ST65
86 static const uint32 s_magicNumbers[] = {
87 MKTAG('S', 'I', 'T', '!'), MKTAG('S', 'T', '6', '5'), MKTAG('S', 'T', '5', '0'),
88 MKTAG('S', 'T', '6', '0'), MKTAG('S', 'T', 'i', 'n'), MKTAG('S', 'T', 'i', '2'),
89 MKTAG('S', 'T', 'i', '3'), MKTAG('S', 'T', 'i', '4'), MKTAG('S', 'T', '4', '6')
90 };
91
open(const Common::String & filename)92 bool StuffItArchive::open(const Common::String &filename) {
93 close();
94
95 _stream = SearchMan.createReadStreamForMember(filename);
96
97 if (!_stream)
98 return false;
99
100 uint32 tag = _stream->readUint32BE();
101
102 // Check all the possible FourCC's
103 bool found = false;
104 for (int i = 0; i < ARRAYSIZE(s_magicNumbers); i++) {
105 if (tag == s_magicNumbers[i]) {
106 found = true;
107 break;
108 }
109 }
110
111 // Didn't find one, let's bail out
112 if (!found) {
113 close();
114 return false;
115 }
116
117 /* uint16 fileCount = */ _stream->readUint16BE();
118 /* uint32 archiveSize = */ _stream->readUint32BE();
119
120 // Some sort of second magic number
121 if (_stream->readUint32BE() != MKTAG('r', 'L', 'a', 'u')) {
122 close();
123 return false;
124 }
125
126 /* byte version = */ _stream->readByte(); // meaning not clear
127
128 _stream->skip(7); // unknown
129
130 while (_stream->pos() < _stream->size() && !_stream->eos()) {
131 byte resForkCompression = _stream->readByte();
132 byte dataForkCompression = _stream->readByte();
133
134 byte fileNameLength = _stream->readByte();
135 Common::String name;
136
137 for (byte i = 0; i < fileNameLength; i++)
138 name += (char)_stream->readByte();
139
140 // Skip remaining bytes
141 _stream->skip(63 - fileNameLength);
142
143 /* uint32 fileType = */ _stream->readUint32BE();
144 /* uint32 fileCreator = */ _stream->readUint32BE();
145 /* uint16 finderFlags = */ _stream->readUint16BE();
146 /* uint32 creationDate = */ _stream->readUint32BE();
147 /* uint32 modificationDate = */ _stream->readUint32BE();
148 uint32 resForkUncompressedSize = _stream->readUint32BE();
149 uint32 dataForkUncompressedSize = _stream->readUint32BE();
150 uint32 resForkCompressedSize = _stream->readUint32BE();
151 uint32 dataForkCompressedSize = _stream->readUint32BE();
152 /* uint16 resForkCRC = */ _stream->readUint16BE();
153 /* uint16 dataForkCRC = */ _stream->readUint16BE();
154 _stream->skip(6); // unknown
155 /* uint16 headerCRC = */ _stream->readUint16BE();
156
157 // Ignore directories for now
158 if (dataForkCompression == 32 || dataForkCompression == 33)
159 continue;
160
161 if (dataForkUncompressedSize != 0) {
162 // We have a data fork
163
164 FileEntry entry;
165 entry.compression = dataForkCompression;
166 entry.uncompressedSize = dataForkUncompressedSize;
167 entry.compressedSize = dataForkCompressedSize;
168 entry.offset = _stream->pos() + resForkCompressedSize;
169 _map[name] = entry;
170
171 debug(0, "StuffIt file '%s', Compression = %d", name.c_str(), entry.compression);
172 }
173
174 if (resForkUncompressedSize != 0) {
175 // We have a resource fork
176
177 // Add a .rsrc extension so we know it's the resource fork
178 name += ".rsrc";
179
180 FileEntry entry;
181 entry.compression = resForkCompression;
182 entry.uncompressedSize = resForkUncompressedSize;
183 entry.compressedSize = resForkCompressedSize;
184 entry.offset = _stream->pos();
185 _map[name] = entry;
186
187 debug(0, "StuffIt file '%s', Compression = %d", name.c_str(), entry.compression);
188 }
189
190 // Go to the next entry
191 _stream->skip(dataForkCompressedSize + resForkCompressedSize);
192 }
193
194 return true;
195 }
196
close()197 void StuffItArchive::close() {
198 delete _stream; _stream = nullptr;
199 _map.clear();
200 }
201
hasFile(const Common::Path & path) const202 bool StuffItArchive::hasFile(const Common::Path &path) const {
203 Common::String name = path.toString();
204 return _map.contains(name);
205 }
206
listMembers(Common::ArchiveMemberList & list) const207 int StuffItArchive::listMembers(Common::ArchiveMemberList &list) const {
208 for (FileMap::const_iterator it = _map.begin(); it != _map.end(); it++)
209 list.push_back(getMember(it->_key));
210
211 return _map.size();
212 }
213
getMember(const Common::Path & path) const214 const Common::ArchiveMemberPtr StuffItArchive::getMember(const Common::Path &path) const {
215 Common::String name = path.toString();
216 return Common::ArchiveMemberPtr(new Common::GenericArchiveMember(name, this));
217 }
218
createReadStreamForMember(const Common::Path & path) const219 Common::SeekableReadStream *StuffItArchive::createReadStreamForMember(const Common::Path &path) const {
220 Common::String name = path.toString();
221 if (!_stream || !_map.contains(name))
222 return nullptr;
223
224 const FileEntry &entry = _map[name];
225
226 if (entry.compression & 0xF0)
227 error("Unhandled StuffIt encryption");
228
229 Common::SeekableSubReadStream subStream(_stream, entry.offset, entry.offset + entry.compressedSize);
230
231 // We currently only support type 14 compression
232 switch (entry.compression) {
233 case 0: // Uncompressed
234 return subStream.readStream(subStream.size());
235 case 14: // Installer
236 return decompress14(&subStream, entry.uncompressedSize);
237 default:
238 error("Unhandled StuffIt compression %d", entry.compression);
239 }
240
241 return nullptr;
242 }
243
update14(uint16 first,uint16 last,byte * code,uint16 * freq) const244 void StuffItArchive::update14(uint16 first, uint16 last, byte *code, uint16 *freq) const {
245 uint16 i, j;
246
247 while (last - first > 1) {
248 i = first;
249 j = last;
250
251 do {
252 while (++i < last && code[first] > code[i])
253 ;
254
255 while (--j > first && code[first] < code[j])
256 ;
257
258 if (j > i) {
259 SWAP(code[i], code[j]);
260 SWAP(freq[i], freq[j]);
261 }
262 } while (j > i);
263
264 if (first != j) {
265 SWAP(code[first], code[j]);
266 SWAP(freq[first], freq[j]);
267
268 i = j + 1;
269
270 if (last - i <= j - first) {
271 update14(i, last, code, freq);
272 last = j;
273 } else {
274 update14(first, j, code, freq);
275 first = i;
276 }
277 } else {
278 ++first;
279 }
280 }
281 }
282
283 struct SIT14Data {
284 byte code[308];
285 byte codecopy[308];
286 uint16 freq[308];
287 uint32 buff[308];
288
289 byte var1[52];
290 uint16 var2[52];
291 uint16 var3[75 * 2];
292
293 byte var4[76];
294 uint32 var5[75];
295 byte var6[1024];
296 uint16 var7[308 * 2];
297 byte var8[0x4000];
298
299 byte window[0x40000];
300 };
301
302 // Realign to a byte boundary
303 #define ALIGN_BITS(b) \
304 if (b->pos() & 7) \
305 b->skip(8 - (b->pos() & 7))
306
readTree14(Common::BitStream8LSB * bits,SIT14Data * dat,uint16 codesize,uint16 * result) const307 void StuffItArchive::readTree14(Common::BitStream8LSB *bits, SIT14Data *dat, uint16 codesize, uint16 *result) const {
308 uint32 i, l, n;
309 uint32 k = bits->getBit();
310 uint32 j = bits->getBits(2) + 2;
311 uint32 o = bits->getBits(3) + 1;
312 uint32 size = 1 << j;
313 uint32 m = size - 1;
314 k = k ? (m - 1) : 0xFFFFFFFF;
315
316 if (bits->getBits(2) & 1) { // skip 1 bit!
317 // requirements for this call: dat->buff[32], dat->code[32], dat->freq[32*2]
318 readTree14(bits, dat, size, dat->freq);
319
320 for (i = 0; i < codesize; ) {
321 l = 0;
322
323 do {
324 l = dat->freq[l + bits->getBit()];
325 n = size << 1;
326 } while (n > l);
327
328 l -= n;
329
330 if (k != l) {
331 if (l == m) {
332 l = 0;
333
334 do {
335 l = dat->freq[l + bits->getBit()];
336 n = size << 1;
337 } while (n > l);
338
339 l += 3 - n;
340
341 while (l--) {
342 dat->code[i] = dat->code[i - 1];
343 ++i;
344 }
345 } else {
346 dat->code[i++] = l + o;
347 }
348 } else {
349 dat->code[i++] = 0;
350 }
351 }
352 } else {
353 for (i = 0; i < codesize; ) {
354 l = bits->getBits(j);
355
356 if (k != l) {
357 if (l == m) {
358 l = bits->getBits(j) + 3;
359
360 while (l--) {
361 dat->code[i] = dat->code[i - 1];
362 ++i;
363 }
364 } else {
365 dat->code[i++] = l + o;
366 }
367 } else {
368 dat->code[i++] = 0;
369 }
370 }
371 }
372
373 for (i = 0; i < codesize; ++i) {
374 dat->codecopy[i] = dat->code[i];
375 dat->freq[i] = i;
376 }
377
378 update14(0, codesize, dat->codecopy, dat->freq);
379
380 for (i = 0; i < codesize && !dat->codecopy[i]; ++i)
381 ; // find first nonempty
382
383 for (j = 0; i < codesize; ++i, ++j) {
384 if (i)
385 j <<= (dat->codecopy[i] - dat->codecopy[i - 1]);
386
387 k = dat->codecopy[i];
388 m = 0;
389
390 for (l = j; k--; l >>= 1)
391 m = (m << 1) | (l & 1);
392
393 dat->buff[dat->freq[i]] = m;
394 }
395
396 for (i = 0; i < (uint32)codesize * 2; ++i)
397 result[i] = 0;
398
399 j = 2;
400
401 for (i = 0; i < codesize; ++i) {
402 l = 0;
403 m = dat->buff[i];
404
405 for (k = 0; k < dat->code[i]; ++k) {
406 l += (m & 1);
407
408 if (dat->code[i] - 1 <= (int32)k) {
409 result[l] = codesize * 2 + i;
410 } else {
411 if (!result[l]) {
412 result[l] = j;
413 j += 2;
414 }
415
416 l = result[l];
417 }
418
419 m >>= 1;
420 }
421 }
422
423 ALIGN_BITS(bits);
424 }
425
426 #define OUTPUT_VAL(x) \
427 out.writeByte(x); \
428 dat->window[j++] = x; \
429 j &= 0x3FFFF
430
decompress14(Common::SeekableReadStream * src,uint32 uncompressedSize) const431 Common::SeekableReadStream *StuffItArchive::decompress14(Common::SeekableReadStream *src, uint32 uncompressedSize) const {
432 byte *dst = (byte *)malloc(uncompressedSize);
433 Common::MemoryWriteStream out(dst, uncompressedSize);
434
435 Common::BitStream8LSB *bits = new Common::BitStream8LSB(src);
436
437 uint32 i, j, k, l, m, n;
438
439 SIT14Data *dat = new SIT14Data();
440
441 // initialization
442 for (i = k = 0; i < 52; ++i) {
443 dat->var2[i] = k;
444 k += (1 << (dat->var1[i] = ((i >= 4) ? ((i - 4) >> 2) : 0)));
445 }
446
447 for (i = 0; i < 4; ++i)
448 dat->var8[i] = i;
449
450 for (m = 1, l = 4; i < 0x4000; m <<= 1) // i is 4
451 for (n = l + 4; l < n; ++l)
452 for (j = 0; j < m; ++j)
453 dat->var8[i++] = l;
454
455 for (i = 0, k = 1; i < 75; ++i) {
456 dat->var5[i] = k;
457 k += (1 << (dat->var4[i] = (i >= 3 ? ((i - 3) >> 2) : 0)));
458 }
459
460 for (i = 0; i < 4; ++i)
461 dat->var6[i] = i - 1;
462
463 for (m = 1, l = 3; i < 0x400; m <<= 1) // i is 4
464 for (n = l + 4; l < n; ++l)
465 for (j = 0; j < m; ++j)
466 dat->var6[i++] = l;
467
468 m = bits->getBits(16); // number of blocks
469 j = 0; // window position
470
471 while (m-- && !bits->eos()) {
472 bits->getBits(16); // skip crunched block size
473 bits->getBits(16);
474 n = bits->getBits(16); // number of uncrunched bytes
475 n |= bits->getBits(16) << 16;
476 readTree14(bits, dat, 308, dat->var7);
477 readTree14(bits, dat, 75, dat->var3);
478
479 while (n && !bits->eos()) {
480 for (i = 0; i < 616;)
481 i = dat->var7[i + bits->getBit()];
482
483 i -= 616;
484
485 if (i < 0x100) {
486 OUTPUT_VAL(i);
487 --n;
488 } else {
489 i -= 0x100;
490 k = dat->var2[i] + 4;
491 i = dat->var1[i];
492
493 if (i)
494 k += bits->getBits(i);
495
496 for (i = 0; i < 150;)
497 i = dat->var3[i + bits->getBit()];
498
499 i -= 150;
500 l = dat->var5[i];
501 i = dat->var4[i];
502
503 if (i)
504 l += bits->getBits(i);
505
506 n -= k;
507 l = j + 0x40000 - l;
508
509 while (k--) {
510 l &= 0x3FFFF;
511 OUTPUT_VAL(dat->window[l]);
512 l++;
513 }
514 }
515 }
516
517 ALIGN_BITS(bits);
518 }
519
520 delete dat;
521 delete bits;
522
523 return new Common::MemoryReadStream(dst, uncompressedSize, DisposeAfterUse::YES);
524 }
525
526 #undef OUTPUT_VAL
527 #undef ALIGN_BITS
528
createStuffItArchive(const Common::String & fileName)529 Common::Archive *createStuffItArchive(const Common::String &fileName) {
530 StuffItArchive *archive = new StuffItArchive();
531
532 if (!archive->open(fileName)) {
533 delete archive;
534 return 0;
535 }
536
537 return archive;
538 }
539
540 } // End of namespace Common
541