I guess it depends on your definition of trivial. Expanding strings comes up a lot in hacking for translations, so it's considered one of the basics. Older console games (NES and SNES; I imagine all of the 8 and 16-bit platforms would be similar) typically have a tables of pointers to strings that are in the same program bank as the table. If you have space in that bank, it's simple to expand. If you don't, you have to implement the things you mention, or rewrite the code that loads strings so it can load from multiple banks. That falls under decompiling, but with the excellent utilities and debugging emulators available it's actually not very hard, outside of games that handle things oddly. If the pointers aren't in a nice table, it's usually possible to find them with the string offset alone, without the need to decompile (but again the code more often than not will not account for the bank the string is in). JRPGs also often use fixed-length strings for things like inventory item names, so those require either simply changing the string length or completely rewriting the name loading subroutine(s), depending on how efficient you want to be, in addition to making sure the menus or whatever actually display the longer names, and that's definitely falling into non-trivial territory.
Is this actually that trivial for ROMs? I thought you had to stay within the allotted space for strings unless you wanted to get fancy (extra jump instructions, two characters in one byte, decompiling etc.) I know a lot of 8- and 16-bit games had sub-par English to Japanese translations in part because the translators has such limited space to work with.
Anyhow DeHackEd was just a system for replacing binary data, which meant you only had so much space to work with for any kind of edits.
Typically the reason translations suffered wasn't because it was difficult to expand the scripts, but because publishers were unwilling to use larger ROMs. The bigger the ROM, the more expensive to produce, so the translators were forced to cram their scripts into the same space that the original Japanese script used, often having to make significant cuts on top of implementing the techniques you mention. SNES fan translations almost always expand the ROM; it's less common with NES games because it's not nearly as easy, and because the maximum program size is decided by the MMC chip in the cartridge. (One of the Final Fantasy III translations actually increases the PRG size to 1MB, but the MMC3 board the game is on doesn't actually support anything higher than 512KB, so that translation won't work in accurate emualtors.)
If Quasar says it's non-trivial in Doom than it's non-trivial, though. He's the expert here, like I said I never looked into doom.exe, or any PC game for that matter. The only hacks I've done to PC games are things that were already documented, and that doesn't really count.
Edit: Blaming costs alone for the poor quality of most translations in that era is probably simplifying things a bit too much. There were definitely other issues, and I'm hardly an expert on that. I just know that it was very rare for the translated version of a game to use larger ROMs than the Japanese version, and costs are cited as the reason for that.
Last edited by Dragonsbrethren on Oct 3 2013 at 12:13