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