Final Fantasy 2&3 save engine

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Final Fantasy 2&3 save engine

Post by Bregalad »

I've been curious about how games with battery holds its saved data, becasue the bytes that are here can be valid as well than invalid.
I've traced some code into FF1, FF2 and FF3. FF1 has only one save slot, and it does just check two variables, if the first one is $55 and the segond one $aa the save is considered as "valid" (I think this is a good vay to handle it, because data in a new RAM chip is often $ff and $00, so $aa and $55 are logically the two value that have the smallest chanes to be there randomly in a ram chip when you power it up).
FF2 and FF3 seems to do it a bit more tricky way. I noted in FF2 that $6000-$62ff handles the current data, $6300-$65ff the first slot, $6600-$68ff the segond slot, $6900-$6bff the third one and eventually $6c00-$6eff the fourth one. The programm does add all the value of a whole slot together, then add 1, and the data seems to be valid only if the result of all this is zero. Seems very crazy isn't it ? Then, if this control has been successfull, another value (like $5a) is checked into the slot.
FF3 does this, but in the other order, so it fist check the value of $5a into the slot, then it does that crazy "mega-addition".
Why would this "mega-addition" be needed ? Does anyone have comment/suggetions about it ? I'll be in need to handle that someday for my Ecological Evolution project.
Useless, lumbering half-wits don't scare us.
User avatar
Quietust
Posts: 1920
Joined: Sun Sep 19, 2004 10:59 pm
Contact:

Post by Quietust »

The "mega-addition" you describe sounds like a simple checksum, an extremely common practice used to verify data integrity. My assumption is that when FF2 saves a game, it performs a checksum of all but 1 byte and then uses that data to fill in the last byte so the overall sum is zero (thereby not requiring an explicit checksum value for each savegame).
Quietust, QMT Productions
P.S. If you don't get this note, let me know and I'll write you another.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples »

The custom stamps in Mario Paint (for Super NES) use a 16-bit hash made of an 8-bit sum and an 8-bit xor.
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Post by Bregalad »

Well, it takes more sense from this viewpoint, but still, I can't see why this big addition is needed. Just check for one security byte (or two) is okay, I think. Well, just when you're copiying data from the current slot to the save slot, corrupted data could appear in the save slot if the programm is reseted just at this time. In that case, I'll just modify the security byte in order to make the data invalid, copy all the stuff and turn the security back to his good value. I can't see why this simpler and faster method wouldn't work fine.
An even better method would to have index in the SRAM that can cutomisely change all position of every slots (including the current one). So, when you save your game, you just have to change an index byte to tell that the slot n point to the current data, and after that we can copy all data from the old current data slot to the slot n were the overwritten saving data was, and eventually change the current data index. That way, the actual "saving" has no transfer in it, the transfer is done after the saving, so this would avoid corrupter data in save slots.
Useless, lumbering half-wits don't scare us.
Guest

Post by Guest »

When a battery weakens, it is possible for some data to become corrupt. The checksum is useful for verifying that the saved data has not been garbled. There are some games out there that can behave really strangely when the battery is low - these games typically don't do a checksum validation and thus will permit loading a corrupted saved game.
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Post by Bregalad »

Yeah, I see. Effectively, weak battery can be a scaring problem. Trough, I tested my Zelda card's battery and it's still ~3,17 V, even 15 years after the time it was build (exept if anyone who owned the card prior to me would have changed the battery).

Also, when running in emulation, this could do some protection against evil players that want to cheat, and search for the number of your level, HP, etc... in the save file trough an hex editor. If they change this, their save will be... deleted ! Hahaha, well done. I'll definitely use this method (or a similar one) for all games with saves I'll write in the future.

Another way to handle the above problem would be to EOR all the value with a constant, so all data will be "corrupted", but it could be rescued trough the same EOR opperation.

I just noted that when you turn on the power of a RAM chip, the most often it has only $ff or $00 in it. In both cases, the result of a mega-adittion will be zero, so in both case the save will be valid... So both methods together have to be used.
Useless, lumbering half-wits don't scare us.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples »

Bregalad wrote:Also, when running in emulation, this could do some protection against evil players that want to cheat, and search for the number of your level, HP, etc... in the save file trough an hex editor. If they change this, their save will be... deleted ! Hahaha, well done. I'll definitely use this method (or a similar one) for all games with saves I'll write in the future.
And then the cheaters will just ips your game to skip verifying the checksum if the player, say, holds player 2 B button. Then at next save, it'll write a correct checksum.

Even slicker is to only use 11 out of every 15 bytes of the save file, using the rest for error correction using a parallel Hamming code.
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

An even better method would to have index in the SRAM that can cutomisely change all position of every slots (including the current one). So, when you save your game, you just have to change an index byte to tell that the slot n point to the current data, and after that we can copy all data from the old current data slot to the slot n were the overwritten saving data was, and eventually change the current data index. That way, the actual "saving" has no transfer in it, the transfer is done after the saving, so this would avoid corrupter data in save slots.

Apple's Mac OS file system has a "swap file contents" function for exactly this purpose. When saving a file, they recommend saving to a temporary file, then swapping its data with the original file, so that there is no way to lose the file if the system crashes in the middle of saving.

Another use of this technique is in flash memory, where there is limited rewrite life. By moving the data each time and updating an index, rewriting is minimized and spread over all the cells.

This is of course standard fare when doing atomic changes to data shared by multiple threads of execution.
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Post by Bregalad »

Yeah, the file system idea I have seems rather good for a NES game, in case of if the power could go down during a save (not because the player has turned off the power button, but, for example, there could be your fuse that become over for any reason or your house can be stopped to be alimented at all in case of storm, or something).
It would be pretty difficult to handle this correctly. For example, the player choose to start a new game. There is two methods to handle this. We can check if the slot 0 is used for any save file, if it is, check for slot 1, etc.... then, the first "free" slot is assigned to the current data, and the game can start. When saving, the game should change the saved file to the used slot, but what becomes the current slot ? If it doesn't change, the game will be "permanently" saved, and it'll be saved even if the player don't want it to. This could be interessting for games that have a "supend" commend like Just Breed and Fire Emblem. So, when saving, we have to interchange those two files. Well, first change current slot index, then copy from the saved file to it or the opposite ? Using this method is something tough.
Even slicker is to only use 11 out of every 15 bytes of the save file, using the rest for error correction using a parallel Hamming code.

I really don't see what you do mean by this. Anyway, if the cheater really want to cheat, it's impossible to avoid them to cheat. But, it's possible to render their task harder. Change the code isn't for everyone, but change the data trough a hex editor is.
Also, found a method to avoid savestates to work would be pretty interessting, but I really can't see how it would be possible to handle that.
Useless, lumbering half-wits don't scare us.
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

In a game with 3 save slots, have 4 actual slots in SRAM and a table of 3 indicies for the visible save slots. When saving, find the one unused actual slot, save there, then change the index in the table. The key is to use an atomic operation when changing data, which either succeeds or fails without changing data. In this case, the visible data doesn't change until the index is updated at the end.

One problem with this is that the table of indicies is open to corruption. You could have the actual slots marked as valid/invalid to allow "recovery" of slots if the index becomes corrupt, much like a filesystem does when the directory doesn't get updated properly.
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Post by Bregalad »

Thanks, that sound like a good algorithm
blargg wrote:The key is to use an atomic operation when changing data, which either succeeds or fails without changing data. In this case, the visible data doesn't change until the index is updated at the end.
I didn't get this part actually. You mean that the data from the slot that have been saved should be transfered to the new unused slot, that was the old save data, to be able to continue the game witout affect saved games, right ?
One problem with this is that the table of indicies is open to corruption. You could have the actual slots marked as valid/invalid to allow "recovery" of slots if the index becomes corrupt, much like a filesystem does when the directory doesn't get updated properly.
A simple way to handle this would be to dupplicate each byto of index. So it would take 6 bytes, and if they're not similar, the non-similar ones can be considered as dumb and the save become non-valid. Well, still complicated. An easy way to make a save non valid is to volontary break its checksum, but the best of the best is to reserv a byte for this, if possible check for an $5a or something with as much bit set than clear in it.
Useless, lumbering half-wits don't scare us.
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

OK, you start out with an index with values 1, 2, 3 and internal save slots 1, 2, and 3 used, and 4 is unused. Player saves game to slot 3. Internally you save game to slot 4, then change the index to 1, 2, 4. Now internal slots 1, 2, and 4 are used, and 3 is unused.

The key is that if power is removed before the index is updated, it is as if the save was never done. After the single byte in the index is changed from 3 to 4, the save is complete. This is the atomic part (atomic meaning indivisible, not exactly the definition the physicists follow anymore!).
User avatar
Quietust
Posts: 1920
Joined: Sun Sep 19, 2004 10:59 pm
Contact:

Post by Quietust »

To make it a bit 'nicer', you could then copy slot 4 into slot 3 and subsequently set the index back to 1,2,3. If the power was interrupted during the 4->3 copy, the program could simply restart later when it noticed the index was not set to 1,2,3.
Quietust, QMT Productions
P.S. If you don't get this note, let me know and I'll write you another.
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Post by Bregalad »

Yeah, I got the atomic part, lol.
Quietust : Your idea isn't bad, but at this point index become useless, only one byte (or two to avoid corruption) become used, then, if zero the index are 1, 2, 3, else if 1 it's 4, 2, 3, if 2 it's 1, 4, 3 and eventually if 3 it's 1, 2, 4.
So, when saving : The index byte mentionned above take the number of the slot saved, then slot 4 is copied to slot x, then the index byte returns to it's standard value (0).
When loading : Check for the index byte (or the two index bytes, if they matches do like if there were only one, else.... all saves are deleted ?), if it's zero load data from slots 1, 2, 3, else, the slot were the number match with the index byte(s) is loaded from slot 4 instead.
Pretty good at all, but I don't know if all this stuff would be needed. Actually, a single transfer from one block to another block like that (let's consider the worst case, where only lda [$xx],Y are used) :
Let's consider the game uses four software slots, where 3 are for saves and one for current data, and all these slots with a size of 1kb (that's exactly the FF3's case) :

Code: Select all

loop:
lda [CurrentSlot],Y   ;5 cylces
sta [SavedSlot],Y    ;11 cycles
iny                      ;13 cylces
bne loop            ;16*255 = 3315 cycles + 1 (not branch the last time)
inc CurrentSlot ;3321 cycles
inc SavedSlot   ;3326 cylces
dex                ;3328 cycles
bpl loop          ;3331 cycles in total*4 (size = 1kb) = 13 324 cycles
So, let's round down the processor speed to 1,5 MHz (it's actually 1,7.....), this would make 13 324*(1/1 500 000) = 8,88 ms, (and it'll actually be less time). I would consider that if the power goes off during this very short amount of time, the player is REALLY not lucky. This system is surely needed on GBA games or something, but I dobt it would be required on a NES game. However, it can be used to be really safe.
Useless, lumbering half-wits don't scare us.
Post Reply