The Legend of Zelda: The Minish Cap has a bug that causes your save file to have a (roughly) 1 in 65,536 chance of being rendered unplayable each and every single time you save your progress... and it happens before the save file is ever even read by the program.
If you're anything like me, there are three questions running through your mind right now:
- How does a bug like this happen?
- Why did they design the system in such a way to allow a bug like this to happen?
- How do we fix the bug?
Let's answer each of those questions one at a time.
Before diving into specifics, there's some background knowledge needed to understand the bug:
When a video game saves your progress it also calculates what is called a "checksum." This checksum is calculated by performing some operation or series of operations on the bytes located in the save data. The checksum is then stored somewhere in persistent storage, often alongside the save data. The idea is that when you go to load your save file, those same operations are run on the save data's bytes. If the save data wasn't corrupted the result will be equal to the checksum. This is a tried and true method of detecting save file corruption. If it ain't broke don't fix it, right?
Well, the developers of The Minish Cap disagree with you.
When saving a file the data is written twice, each to a different address. This isn't the strange part, in fact this is fairly common and significantly reduces the chance of permanently losing your save file. Accompanying the save data is a "SaveFileStatus" stuct, which contains two copies of the checksum. The first of the two copies is stored as is, while the other is negated and stored inside of an unsigned variable, becoming the two's complement negation of the original.
u32 DataDoubleWriteWithStatus(u32 index, const void* data) {
SaveFileStatus fileStatus;
...
checksum = CalculateChecksum((u16*)&fileStatus.status, 4);
checksum += CalculateChecksum((u16*)data, eepromAddresses->size);
fileStatus.checksum1 = checksum;
fileStatus.checksum2 = -(u32)checksum;
write1success = DataWrite(eepromAddresses->address1, data, eepromAddresses->size);
if (write1success) {
write1success = WriteSaveFileStatus(eepromAddresses->checksum1, &fileStatus);
}
write2success = DataWrite(eepromAddresses->address2, data, eepromAddresses->size);
if (write2success) {
write2success = WriteSaveFileStatus(eepromAddresses->checksum2, &fileStatus);
}
...
typedef struct SaveFileStatus {
u16 checksum1;
u16 checksum2;
u32 status;
} SaveFileStatus;
This leaves two copies of the save data, stored as such:
-Save Copy 1-
Save Data
SaveFileStatus
checksum1
checksum2
status
-Save Copy 2-
Save Data
SaveFileStatus
checksum1
checksum2
statusJust as the data is written twice when it comes time to save, the data also read twice when it comes time to load, once for each copy of the save.
Before the save data is ever accessed, the "SaveFileStatus" is checked first. This initial check is where the "corruption" occurs.
u32 DataDoubleReadWithStatus(u32 index, void* data) {
...
read1status = ReadSaveFileStatus(eepromAddresses->checksum1, &fileStatus);
if (read1status == 2) {
if ((DataRead(eepromAddresses->address1, data, eepromAddresses->size) == 0) ||
(VerifyChecksum(&fileStatus, (u16*)data, eepromAddresses->size) == 0)) {
// read 1 failed
read1status = 0;
} else {
return 1;
}
}
read2status = ReadSaveFileStatus(eepromAddresses->checksum2, &fileStatus);
if (read2status == 2) {
if ((DataRead(eepromAddresses->address2, data, eepromAddresses->size) != 0) &&
(VerifyChecksum(&fileStatus, (u16*)data, (u32)eepromAddresses->size) != 0)) {
return 1;
}
// read 2 failed
read2status = 0;
}
...
u32 ReadSaveFileStatus(u32 address, SaveFileStatus* fileStatus) {
u32 ret;
if (!DataRead(address, fileStatus, 8)) {
ret = 0;
} else {
ret = ParseSaveFileStatus(fileStatus);
}
if (!ret && DataRead(address + 8, fileStatus, 8)) {
ret = ParseSaveFileStatus(fileStatus);
}
return ret;
}
u32 ParseSaveFileStatus(const SaveFileStatus* fileStatus) {
...
if (fileStatus->checksum1 + fileStatus->checksum2 == 0x10000) {
ret = 2; // valid existing file
} else {
ret = 0; // bad file
}
...
During this preliminary "status check," the two checksums are compared. This is done by adding the two checksums together and determining if the sum is equal to 0x10000. If it is, the status check passes and the read function continues, where the checksums are later compared to the save data itself. If not, the save data is considered corrupted and is rendered unplayable.
On the surface, this works! Let's run through a scenario where the checksum value happens to equal 0xA.
checksum1 = 0xA
checksum2 = 0xFFF6 // two's complement negation of 0xA
0xA + 0xFFF6 = 0x10000
Wonderful! The sum of the checksums equal 0x10000, so the preliminary check passes! The checksum added to it's two's complement negation will almost always equal 0x10000 no matter the value!
Just for fun let's run through the same scenario, except this time let the checksum equal 0x0.
checksum1 = 0x0
checksum2 = 0x0 // two's complement negation of 0x0
0x0 + 0x0 = 0x0
Wonderful! The sum of the checksums equal 0x0, so the preliminary check... fails. Wait, that's not wonderful at all. In fact, it's catastrophic!
Since the preliminary check fails, the first copy of the save is considered corrupted. Worse yet, since the preliminary check failed due not to genuine corruption but instead due to the checksums values themselves, the second copy is also considered corrupted. This results in a complete and total loss of the save file.
That's where I got my "1 in 65,536 chance" figure from. Out of the 65,536 possible checksum values, one of them (zero) causes the error.
All this begs the question, "Why?"
Reading and writing two copies of a save at two separate addresses is fairly common, and is a pretty good idea as it astronomically reduces the chance of a save being permanently lost. As said before, that isn't the strange part. What IS strange is the two checksums and the "status check" before reading the save data.
Unfortunately, we'll never know the answer for sure unless we can track down and ask the guy who made the decision.
I do, however, have my own educated guess as to why the decision was made.
Reading an entire save file is expensive. It takes time, and while that time may be fairly insignificant it's not unreasonable to think that somebody would want to try and optimize their code by eliminating as many save data reads as possible.
Optimization. That's why there's two checksums per copy of the save file, and that's why there's a "status check" done before the save file is ever accessed. My evidence? The "SaveFileStatus" struct containing the two checksums. Reading this struct is MUCH cheaper than reading an entire save file. I believe the idea is to read the significantly cheaper "SaveFileStatus" and determine if the two checksums are equal. Since the "SaveFileStatus" and save data are stored in the same region, a mismatch in the checksums would indicate a very high likelihood of save corruption.
Instead of:
-> Reading through the entire save file
-> Running the calculations
-> Comparing the result to the checksum
-> Moving on to the next copy of the save if the calculation and checksum do not match
This approach simply:
-> Reads the "SaveFileStatus" struct
-> Compares the stored checksum values
-> Moves on to the next copy of the save if the checksums do not match
Personally, this seems like a lot of work to save, like, 5 seconds tops when loading a save. This also fails to answer another question, "Why store the second copy of checksum as the two's complement negation of the first? That is what caused the bug in the first place afterall."
To that I say... I really don't know. Maybe we should track the guy down and ask him.
That leads us to our last question, "How can we fix this?" Pretty easily, actually. This entire bug was caused by what amounts to a missed edge case, after all.
if (fileStatus->checksum1 + fileStatus->checksum2 == 0x10000)
My first thought was to just store the second copy of the checksum as is, instead of making it the two's complement negation of the first, but another function "VerifyChecksum" relies on the second copy being such.
u32 VerifyChecksum(SaveFileStatus* fileStatus, u16* data, u32 size) {
u32 temp;
u16 checksum;
checksum = CalculateChecksum((u16*)&fileStatus->status, 4);
checksum += CalculateChecksum(data, size);
if ((fileStatus->checksum1 != checksum) ||
(temp = fileStatus->checksum1 << 0x10, fileStatus->checksum2 != (-temp >> 0x10)) ||
(fileStatus->status != 'MCZ3')) {
return 0;
} else
return 1;
}
Interestingly, this function correctly checks the difference between the two checksum copies. So they did it right once, but not the second time?!
That also answers our question on how to fix the bug, I suppose. Although, temp variables and bit shifts are ugly, so I'll fix it like this:
if (fileStatus->checksum2 == (u16)(-fileStatus->checksum1))
That was easy. Such a devastating bug, caused by simply not accounting for an edge case...
...and what can only be assumed as some guy wanting to be different for the sake of being different. Seriously, if anybody has any ideas as to why the second copy is stored as the two's complement negation, please let me know.
Special thanks to Zelda Reverse Engineering Team for the decompilation of not only The Minish Cap, but many other Zelda games as well.
If you're interested in that kind of thing, check out their GitHub Page!