Unused ROM/RAM space and hacking

[STARWIN]

While I'm thinking mostly about NES/SNES, feel free to discuss other architectures as well if you want. This will be a swarm of questions, no need to answer everything.

1. What do you do when you need to add more code/data to the ROM? How will you ensure that the new locations you require are unused?

As I understand, some answers are:
-code/data logging while playing the game under the debug emulator
-checking existing structures for unused locations (ends of banks or ends of memory areas artificially reserved for a given purpose) for blocks of FF or 00

Logging answers the opposite question: What locations are used?

Structural analysis relies on coherent organization inside the ROM.

I assume the structure is the determining factor in the mind of the hacker, while the logging part only helps to reveal the structure and acts as a check.

Are there other methods?

Is it common for games to leave ROM unused?

Does anyone have experience of failing (causing side-effects) while using these methods?

2. What do you do when you need to add a new variable to RAM?

Are there RAM access loggers? Technically I can already use breakpoints while playing to eliminate location candidates. Again the answer we get is to the opposite question.

In case the emulator initializes the RAM space, finding location candidates may become very easy, if there is actual unused RAM. This would be similar to ROM structure analysis.

Is it common for games to leave RAM unused?

Does anyone have a more systematic approach?

Any experiences of difficulties?

3. Solving a ROM

Have there been tries to create programs that automatically solve the usage status of every byte in ROM/RAM?

So, instead of a human going through various codepaths and using a logger, the program would do it (as it has more time than we do).

Now, the amount of increasing possibilities obviously leads into combinatoric explosion. I think it might be fun to think of heuristics for this.

Depending on how well the methods for finding free space work, this kind of a solver may be completely unnecessary. Although I believe if there was a program that could solve a NES game, for example, it wouldn't be too much more to also include some codepath/causality information, e.g. mapping all the code that affects graphics memory given some causality distance. In general, automating the analysis of the game to some extent. And obviously full disassembly.

[Pikachumanson]

Well from what I've seen it's real common for Sega master system roms to have tons of space leftover in them. It makes it great for expanding text! Then, again the roms are usually 256k to begin with. Nes is kind of a mixed bag as the rom sized varied and the programming methods varied as so for some the space is real limited and for others you have oodles. I like to use Nflate to expand NeS roms. But I am going to learn how to do it manually just so I can get a better handle on NES and specific mapper architecture.

Sorry I couldn't answer all your questions. I'm just chiming in with what's been my experience.

[Pennywise]

It is not uncommon to find free space in NES/SNES ROMs. They are usually a bunch of consecutive FF's or 00's. If you wanna know how to access that space for your own purposes, well that's hardware specific stuff and requires a bit of ASM knowledge. Probably 99% of the time when you see apparently unused data, it is unused and you don't have to worry. You can also add space to a ROM by expanding it. The NES is more restrictive in what you can do, while the SNES is not.

As for unused RAM, if you look at RAM in a hex editor via emulator and see a RAM value like 00 or FF that isn't changing while you play, chances are it is not used by the game. To be sure you can set a write breakpoint to the address. All you really need to do is make an educated guess.

With NES, there are 3 main areas of RAM. $00-FF (Zero page), $600-7FF, $6000-7FFF (Cartridge RAM). Zero page should not be used due to its dynamic nature as RAM there is almost always in use. The end of RAM is always the safest bet. Dunno anything about SNES.

[Gideon Zhi]

It is not uncommon to find free space in NES/SNES ROMs. They are usually a bunch of consecutive FF's or 00's. If you wanna know how to access that space for your own purposes, well that's hardware specific stuff and requires a bit of ASM knowledge. Probably 99% of the time when you see apparently unused data, it is unused and you don't have to worry. You can also add space to a ROM by expanding it. The NES is more restrictive in what you can do, while the SNES is not.

As for unused RAM, if you look at RAM in a hex editor via emulator and see a RAM value like 00 or FF that isn't changing while you play, chances are it is not used by the game. To be sure you can set a write breakpoint to the address. All you really need to do is make an educated guess.

With NES, there are 3 main areas of RAM. $00-FF (Zero page), $600-7FF, $6000-7FFF (Cartridge RAM). Zero page should not be used due to its dynamic nature as RAM there is almost always in use. The end of RAM is always the safest bet. Dunno anything about SNES.

Pretty much this. The ends of banks, the ends of RAM. Anything that's all zeroes, all FFs, or that shows up as a sort of checkerboard pattern of noise in a tile editor can be considered safe to use the vast majority of the time. The only other tip I'd offer is that when you're hacking a game that has a gigantic Japanese font that you won't ever use, you can overwrite the unused characters with new code and data.

[FAST6191]

Coming off easy street.
On the GBA - everything is mapped to memory with no banks in any dumped commercial ROM (flash carts, some homebrew, lucky lucky man/tourist trap 32 in 1 pirate carts and the undumped version of the whole shrek film being an exception). It is mapped to 3 locations and as an added bonus most games do not use the upper 16 megs so you almost always (mother 3 is about the only exception for a finished ROM hack) have a free 16 megs.
On the DS - assuming your file format will hold it then just press rebuild ROM with the new ROM in it assuming you are not going to go over 512 megs (most games sit at around 64 to 128) and the ARM9 binary does not go over 4 megs (less anything for the overlays). I have pondered using the GBA section as extra memory for various things (who does not want another 32 megs of fast bus mapped memory) and certain hacks (as in actual get code to run on a locked system hacks) used it but I have not done anything like using it as memory yet.

Other systems- can get tricky if you have banks to deal with as things can get quite in depth depending upon how the banks work on your given game/system. Of course a lack of banks, or mappers depending upon how you want to view it, can be just as troublesome if you need more space as the mapper/bankless games are often packed to the limit.

The two methods seem to be
Fixed window and last three quarters shifting to whatever.
Complete page swap or alignment change. Whether this is backed by having the binary or a fragment in memory goes game by game and others can choose to do things like copy the game to all banks/discs (Final Fantasy 7 being a fairly notable example here).

How banks are swapped (register in standard bus, register on cart, soft memory lookup should you construct an appropriate address) is what you will have to figure into your routines if you play this game. Switching latency I imagine would be one of the more annoying issues though adding a function to a game that hooks at random intervals and having to do a selected bank check I imagine to be just as fun.

How to tell if it is free.
Runs of 00 and FF (or occasionally alternating 00 and FF), especially at the end of a ROM or at the end of a section, are a good bet. I already mentioned the niceness of the GBA and DS but for some banked games you might have an unused bank for the mapper/cart type or have a remarkably similar mapper you can convert to (the GB/GBC being quite good for this on some occasions).
You can try using tracing, pointers and other such methods and they are well worth it but in practice it can be hard to account for all the edge cases (especially for games with minigames, post game content and other "rare use" sections). Same applies to the RAM though you can do things like DEADBEEF padding (floodfill the RAM with DEADBEEF and any DEADBEEF left at the point you care about, assuming the game did not otherwise initialise the memory, is hopefully good to go) and you may run into pointers (as in the cheat maker's nemesis and favourite of those giving tests on C programming) on later consoles more often which is fun.
The DS usually piles endless junk into the binary (error messages in every language or something) which ends up in RAM so I am happy enough there (though I will still tend to avoid repointing if I can). You can also optimise games or do things like remove compression if it bounces something into work ram on the way to VRAM. Truth be told most of my work is not new variables as much as altering existing ones or subverting functions to give them more scope which is more trouble finding space in the binary (which, as covered, is usually not the hardest) in which case I need temporary variables at best and can often cover it with registers or the stack.

Failing. I was once trying to help out with a DS phoenix wright game and I missed that the VRAM was filled up by the increased sprite size (it was a multi layer affair and so quite easy to do), cue head scratching as I tried to pin down what went despite the file "decoding" properly. Sprite and VRAM stuff is quite common in other areas where before it might have used repeated tiles and you only had say two kanji before with a blank tile in the middle.
In my "breaking formats" phase I saw things that, were I doing an actual hack, I would have run foul of a few apparent limits which were far lower than the pointers they could use would theoretically allow (full 32 bits but not going much past 24). That said I have come the other way and used formats with 32 bit pointers to trick jump commands and whatever else to read way later than was originally intended. I once played around with a game that was almost all scripting engine down to commands themselves carrying their length as well as assets they could load but later ran up against internal memory limits. I believe one of the fire emblem DS hacks ran into this as well but was rather odd (something about the characters per line being increased but running out of memory somewhere else if memory serves).
More commonly it is just the same as when you corrupt or screw up inserting a game and you crashes, corruption, oddities and more depending upon what you have done and how good the games are (and defensive coding is hardly a single player/local multiplayer* game developer speciality, especially upon old consoles and handhelds).

*I say local but the multiplayer lot are not on my shortlist of potential hires should I be developing something that has to be seriously fault tolerant (medical and industrial stuff for instance). That said I would probably struggle to convince myself to hire any game programmer that did not cut their teeth on anything playstation or older.

Common for such blank sections. RAM can vary though I am not surprised either way. With consoles traditionally not be OS laden, multitasking systems with mountains of dedicated VRAM it is certainly not a sure thing though like it might be on a PC.
In a ROM... given we dump ROMs to the power of 2 sizes (give or take banks) then yes. Given we often fish extraneous data from ROMs then yes again. Moreover given we tend to alter games rather than expand them you can reclaim space.

3. My first thought is to say halting problem and leave it at that. I have seen things scan known ROMs to determine what goes (Atrius' GBA golden sun stuff being the most notable though some of the pokemon lot do OK too), compression searching is a thing, you can do things like log BIOS and ROM calls and on the DS and other filesystem using systems header parsing and other mild heuristics can happen.
Even without the halting problem most of ROM hacking is concerned with divining the weird and wonderful that programmers ended up using for formats so that is troubled again.

I am waffling so I am out for the time being.

[Drakon]

Yes it's very common for game roms to have unused space.  This's because maskroms only come in certain sizes so often the games don't need to use all the space.  Unfortunately with bankswitching systems you're not always able to find much free space in bank zero making it a pain to add even a bankswitch to your added code.  It's easy to find free space in later banks, but to get to them you need to program in a bankswitch.

Sometimes you need to be careful too, I usually look for blocks of 00s or ffs at the end of a bank.  Finding an empty block in the middle of a bank usually means the space is actually data, which in many cases is true.

[Bregalad]

The most vicious thing you could possibly encounter is that you have a bunch of unused zeroes, or ffs, but that the first one (or the first few ones) are actually used.

Other than that you can be sure that a long strings of zeroes, ffs are used as a "fill in" to complete ROM banks.

[FAST6191]

To go on from Bregalad's post I did actually see that on a few GBA games where they were trimmed but the very last 00 was used as an end of file or something like that (GBA games have no size value in the header or anywhere really unlike some other consoles). Most of ROM hacking is less concerned with this as you will probably want to align something anyway and will tend not to operate on a trimmed ROM.
Similarly though I never bothered to investigate it some of the "safe trimming" methods on the DS leave space in addition to the header mandated size lest either download play or wifi be troubled.

Laziness (why mess around when you can just add to the end) has yet to see me fall foul of it but as Drakon said runs of 00 can also be data, especially graphics where 00 (or 0000) is not uncommon for transparency or 00 can run for several dozen bytes as padding of some form.