mirror of
https://github.com/scummvm/scummvm.git
synced 2025-04-02 10:52:32 -04:00
317 lines
11 KiB
C++
317 lines
11 KiB
C++
/* ScummVM - Graphic Adventure Engine
|
|
*
|
|
* ScummVM is the legal property of its developers, whose names
|
|
* are too numerous to list here. Please refer to the COPYRIGHT
|
|
* file distributed with this source distribution.
|
|
*
|
|
* This program is free software: you can redistribute it and/or modify
|
|
* it under the terms of the GNU General Public License as published by
|
|
* the Free Software Foundation, either version 3 of the License, or
|
|
* (at your option) any later version.
|
|
*
|
|
* This program is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
* GNU General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU General Public License
|
|
* along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
*
|
|
*/
|
|
|
|
#include "immortal/immortal.h"
|
|
|
|
/* Decompression:
|
|
* This decompression algorithm follows the source assembly very closely,
|
|
* which is itself a modification to LZW (a derivative of LZ78).
|
|
* In: Source data as File, size of data
|
|
* Out: Pointer to uncompressed data as SeekableReadStream
|
|
*/
|
|
namespace Immortal {
|
|
|
|
enum codeMask {
|
|
kMaskMSBS = 0xF000, // Code link is Most significant bits
|
|
kMaskLSBS = 0xFF00, // K link is Least significant bits
|
|
kMaskCode = 0x0FFF // Code is 12 bit
|
|
};
|
|
|
|
Common::SeekableReadStream *ImmortalEngine::unCompress(Common::File *source, int lSource) {
|
|
/* Note: this function does not seek() in the file, which means
|
|
* that if there is a header on the data, the expectation is that
|
|
* seek() was already used to move past the header before this function.
|
|
*/
|
|
|
|
/* Other notes:
|
|
* Tk is k in (w,k)
|
|
* Link is spread out between code and tk, where code has the most significant 4 bits, and tk has the least significant 8
|
|
* Codes contains the keys (plus link codes) for the substring values of the dictionary and can be up to 12 bits (4096 total entries) in size
|
|
* Tk contains byte values from the compressed data (plus link codes)
|
|
* Stack contains the currently being recreated string before it gets sent to the output
|
|
*/
|
|
|
|
// In the source, the data allocated here is a pointer passed to the function, but it's only used by this anyway
|
|
uint16 *pCodes = (uint16 *)malloc(k8K); // The Codes stack has 8 * 1024 bytes allocated
|
|
uint16 *pTk = (uint16 *)malloc(k8K); // The Tk has 8 * 1024 bytes allocated
|
|
uint16 pStack[k8K]; // In the source, the stack has the rest of the 20K. That's way more than it needs though, so we're just giving it 8k for now
|
|
|
|
uint16 oldCode = 0;
|
|
uint16 finChar = 0;
|
|
uint16 topStack = 0;
|
|
uint16 evenOdd = 0;
|
|
uint16 myCode = 0;
|
|
uint16 inCode = 0;
|
|
uint16 findEmpty = 0;
|
|
uint16 index = 0;
|
|
|
|
// If the source data has no length, we certainly do not want to decompress it
|
|
if (lSource == 0) {
|
|
return nullptr;
|
|
}
|
|
|
|
/* This will be the dynamically re-allocated writeable memory stream.
|
|
* We do not want it to be deleted from scope, as this location is where
|
|
* the readstream being returned will point to.
|
|
*/
|
|
Common::MemoryWriteStreamDynamic dest(DisposeAfterUse::NO);
|
|
|
|
/* In the source we save a backup of the starting pointer to the destination, which is increased
|
|
* as more data is added to it, so that the final length can be dest - destBkp. However in
|
|
* our case, the MemoryReadStream already has a size associated with it.
|
|
*/
|
|
|
|
// Clear the dictionary
|
|
setUpDictionary(pCodes, pTk, findEmpty);
|
|
evenOdd = 0;
|
|
topStack = 0;
|
|
|
|
// Get the initial input (always 0?)
|
|
inputCode(finChar, lSource, source, evenOdd);
|
|
oldCode = finChar;
|
|
myCode = oldCode;
|
|
|
|
// (byte) is basically the same as the SEP #$20 : STA : REP #$20
|
|
dest.writeByte((byte)myCode);
|
|
|
|
// Loops until it gets no more input codes (ie. length of source is 0)
|
|
while (inputCode(inCode, lSource, source, evenOdd) == 0) {
|
|
myCode = inCode;
|
|
|
|
// The source uses the Y register for this
|
|
// We can rearrange this a little to avoid using an extra variable, but for now we're pretending index is the register
|
|
index = inCode;
|
|
|
|
/* Check if the code is defined (has links for the linked list).
|
|
* We do this by grabbing the link portion from the code,
|
|
* then adding the Tk, and grabbing just the link portion.
|
|
* This way, if either of the link codes exists, we know it's defined,
|
|
* otherwise you just get zeros.
|
|
* This special case is for a string which is the same as the last string,
|
|
* but with the first char duplicated and added to the end (how common can that possibly be??)
|
|
*/
|
|
if ((((pCodes[index] & kMaskMSBS) | pTk[index]) & kMaskLSBS) == 0) {
|
|
// Push the last char of this string, which is the same as the first of the previous one
|
|
pStack[topStack] = finChar;
|
|
topStack++;
|
|
myCode = oldCode;
|
|
}
|
|
|
|
// The code is defined, but it could be either a single char or a multi char
|
|
// If the index into the dictionary is above 100, it's a multi character substring
|
|
while ((myCode) >= 0x100) {
|
|
index = myCode;
|
|
myCode = pCodes[index] & kMaskCode;
|
|
pStack[topStack] = pTk[index] & kMaskLow;
|
|
topStack++;
|
|
}
|
|
|
|
// Otherwise, it's a single char
|
|
finChar = myCode;
|
|
|
|
// which we write to the output
|
|
dest.writeByte((byte)myCode);
|
|
|
|
// Dump the stack
|
|
index = topStack;
|
|
index--;
|
|
while (index < 0x8000) {
|
|
dest.writeByte((byte)pStack[index]);
|
|
index--;
|
|
}
|
|
topStack = 0;
|
|
|
|
// Hash the old code with the current char, if it isn't in the dictionary, append it
|
|
member(oldCode, finChar, pCodes, pTk, findEmpty, index);
|
|
|
|
// Set up the current code as the old code for the next code
|
|
oldCode = inCode;
|
|
}
|
|
|
|
/* Return a readstream with a pointer to the data in the write stream.
|
|
* This one we do want to dispose after using, because it will be in the scope of the engine itself
|
|
*/
|
|
return new Common::MemoryReadStream(dest.getData(), dest.size(), DisposeAfterUse::YES);
|
|
|
|
}
|
|
|
|
/* Clear the tables and mark the first 256 bytes of the char table as used */
|
|
void ImmortalEngine::setUpDictionary(uint16 *pCodes, uint16 *pTk, uint16 &findEmpty) {
|
|
// Clear the tables completely (4095 entries, same as the mask for codes)
|
|
for (int i = kMaskCode; i >= 0; i -= 1) {
|
|
pCodes[i] = 0;
|
|
pTk[i] = 0;
|
|
}
|
|
|
|
// Mark the first 0x100 as used for uncompress
|
|
for (int i = 0xFF; i >= 0; i -= 1) {
|
|
pTk[i] = 0x100;
|
|
}
|
|
|
|
// findEmpty is a pointer for finding empty slots, so it starts at the end of the data (data is 2 bytes wide, so it's 4k instead of 8k)
|
|
findEmpty = k4K;
|
|
}
|
|
|
|
/* Get a code from the input stream. 1 = no more codes, 0 = got code
|
|
* On even iterations, we grab the first word.
|
|
* On odd iterations, we grab the word starting from the second byte of the previous word
|
|
*/
|
|
int ImmortalEngine::inputCode(uint16 &outCode, int &lSource, Common::File *source, uint16 &evenOdd) {
|
|
// If length is 0, we're done getting codes
|
|
if (lSource == 0) {
|
|
// No more codes
|
|
return 1;
|
|
}
|
|
|
|
// Even
|
|
if (evenOdd == 0) {
|
|
lSource -= 2; // Even number of bytes, decrease by 2
|
|
evenOdd++; // Next alignment will be odd
|
|
|
|
/* The codes are stored in 12 bits, so 3 bytes = 2 codes
|
|
* nnnn nnnn [nnnn cccc cccc cccc] & 0x0FFF
|
|
* nnnn nnnn [0000 cccc cccc cccc]
|
|
*/
|
|
outCode = source->readUint16LE() & kMaskCode;
|
|
source->seek(-1, SEEK_CUR);
|
|
|
|
// Odd
|
|
} else {
|
|
lSource--;
|
|
evenOdd--;
|
|
/* This grabs the next code which is made up of the previous code's second byte
|
|
* plus the current code's byte + the next 2 byte value
|
|
* [nnnn nnnn nnnn cccc] cccc cccc >> 3
|
|
* [000n nnnn nnnn nnnc] cccc cccc & 0xFFFE <- this is done so the Y register has code * 2
|
|
* [000n nnnn nnnn nnn0] cccc cccc >> 1 <- in our case, we could have just done code >> 4
|
|
* [0000 nnnn nnnn nnnn]
|
|
*/
|
|
outCode = ((source->readUint16LE() >> 3) & 0xFFFE) >> 1;
|
|
}
|
|
|
|
// We have a good code, no error
|
|
return 0;
|
|
}
|
|
|
|
int ImmortalEngine::member(uint16 &codeW, uint16 &k, uint16 *pCodes, uint16 *pTk, uint16 &findEmpty, uint16 &index) {
|
|
// Step one is to make a hash value out of W (oldCode) and k (finChar)
|
|
index = ((((((k << 3) ^ k) << 1) ^ k) ^ codeW));
|
|
|
|
// The hash value has to be larger than 200 because that's where the single chars are
|
|
if (index < 0x100) {
|
|
index += 0x100;
|
|
}
|
|
|
|
if ((((pCodes[index] & kMaskMSBS) | pTk[index]) & kMaskLSBS) == 0) {
|
|
// There was no link, so we insert the key, mark the table as used, with no link
|
|
pCodes[index] = codeW;
|
|
pTk[index] = k | 0x100;
|
|
|
|
// Code not found, return error
|
|
return 1;
|
|
}
|
|
|
|
// There is a link, so it's not empty
|
|
// This is a bad loop, because there is no safe way out if the data isn't right, but it's the source logic
|
|
// If there is anything corrupted in the data, the game will get stuck forever
|
|
while (true) {
|
|
uint16 tmp = 0;
|
|
|
|
// If the code matches
|
|
if ((pCodes[index] & kMaskCode) == codeW) {
|
|
// And k also matches
|
|
if ((pTk[index] & kMaskLow) == k) {
|
|
// Then entry is found, return no error
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
// Entry was used, but it is not holding the desired key
|
|
// Follow link to next entry, if there is no next entry, append to the list
|
|
if ((pCodes[index] & kMaskMSBS) == 0) {
|
|
// Find an empty entry and link it to the last entry in the chain, then put the data in the new entry
|
|
uint16 prev = index;
|
|
if (findEmpty >= 0x100) {
|
|
// Table is not full, keep looking
|
|
do {
|
|
findEmpty--;
|
|
// This is slightly more redundant than the source, but I trust the compiler to add a branch here
|
|
if (findEmpty < 0x100) {
|
|
setUpDictionary(pCodes, pTk, findEmpty);
|
|
return 1;
|
|
}
|
|
// We decrease the index and check the entry until we find an empty entry or the end of the table
|
|
} while ((((pCodes[findEmpty] & kMaskMSBS) | pTk[findEmpty]) & kMaskLSBS) != 0);
|
|
|
|
// The link is zero, therefor we have found an empty entry
|
|
|
|
pCodes[findEmpty] = codeW;
|
|
pTk[findEmpty] = k | 0x100; // Marked as used, but still no link because this is the end of the list
|
|
|
|
// Now we attach a link to this entry from the previous one in the list
|
|
uint16 link = findEmpty;
|
|
|
|
// Get the link of this entry
|
|
/* 0000 llll llll llll xba
|
|
* llll llll 0000 llll & kMaskLSBS
|
|
* llll llll 0000 0000
|
|
*/
|
|
tmp = xba(link) & kMaskLSBS;
|
|
|
|
// On the previous entry, take out the K and add the new link onto it
|
|
/* xxxx xxxx xxxx xxxx & kMaskLow
|
|
* 0000 0000 xxxx xxxx | tmp
|
|
* llll llll xxxx xxxx
|
|
*/
|
|
pTk[prev] = (pTk[prev] & kMaskLow) | tmp;
|
|
|
|
// And now the code gets it's half of the link written in
|
|
/* 0000 llll llll llll << 4
|
|
* llll llll llll llll & kMaskMSBS
|
|
* llll 0000 0000 0000 | pCodes[Prev]
|
|
* llll xxxx xxxx xxxx
|
|
*/
|
|
pCodes[prev] = ((link << 4) & kMaskMSBS) | pCodes[prev];
|
|
|
|
// Done
|
|
return 1;
|
|
|
|
} else {
|
|
// Table is full, reset dictionary
|
|
setUpDictionary(pCodes, pTk, findEmpty);
|
|
return 1;
|
|
}
|
|
|
|
} else {
|
|
// Put the link code together by combining the MSBS of the code and the LSBS of k
|
|
/* code = l000 >> 4
|
|
* = 0l00
|
|
* k = ll00 xba
|
|
* = 00ll
|
|
* k | code = 0lll
|
|
*/
|
|
tmp = (pCodes[index] & kMaskMSBS) >> 4;
|
|
index = ((xba(pTk[index]) & kMaskLow) | tmp);// << 1;
|
|
}
|
|
}
|
|
}
|
|
|
|
} // namespace Immortal
|