How are Amiga Kickstart Relocation Files (.RTB) created?

Question

Examples of Amiga Kickstart files (ROMs) can be 256k (1.2/1.3) or 512k (3.0/3.1) binary files, located at $FC0000-$1000000 or $F80000-$1000000

Several programs are able to "soft-kick" Amigas, i.e. install another ROM than the original one, without changing the chips physically, either to upgrade to a newer ROM to run more recent programs, or on the contrary to boot older programs that aren't compatible with new ROMs.

Since the ROM is by definition not writable, those soft-kick programs have to load the replacement Kickstart somewhere else in memory.

Problem is: the ROM files isn't position-independent code. It contains a lot of hardcoded addresses between $F80000/$FC0000 and $1000000

That's where the relocation table files (aka .RTB) come into play. A table exists for almost every official ROM file (see here).

My question is: how exactly are created those relocation table files ?

I tried to re-create those myself and failed. Actually I was able to find most of the reloc offsets, but still miss some. For instance, this one is obvious, LAB_0186 must be relocated (it also could have been made originally PC-relative but that's another story:

LAB_0181:
    LEA LAB_0186,A0     ;0fc208c: 41f900fc20c0
    CLR.W   D1          ;0fc2092: 4241
    ...
    RTS             ;0fc20be: 4e75
LAB_0186:

now that one is more subtle:

MOVE.L  #$00fc1d28,312(A6)  ;0fc034a: 2d7c00fc1d280138

One recognizes an address inside the ROM, but it could be a value too. Introducing heuristics to try to find the hidden ones can find some, but also find fake ones.

And there are tables, that are difficult to figure out for the same reason (plus disassembling data confuses the disassembler which thinks that some data are instructions):

    DC.W    $00fc           ;0fc32c8
    DC.W    $25ae           ;0fc32ca   ; $FC25AE is probably an address
    DC.W    $00fc           ;0fc32cc
LAB_029C:
    MOVE.W  (A6),(A1)+      ;0fc32ce: 32d6  ; $FC32D6 too
    MOVE.W  D0,D7           ;0fc32d0: 3e00   ; now there's this stray word
    DC.W    $00fc           ;0fc32d2   
    MOVE.L  (A6)+,252(A2)       ;0fc32d4: 255e  ; and another probable address again... argh!!! 00fc
    MOVE.W  -(A0),(A1)+     ;0fc32d8: 32e0
    MOVE.W  D0,D6           ;0fc32da: 3c00
    DC.W    $00fc           ;0fc32dc

I doubt that those tables have been created by the actual Amiga developers who took time to assemble ROMs at different addresses to compute the relocation offsets (the simplest way to do that when you have the full source code) so someone did the hard job for all those Kickstarts

The author of skick probably created them himself and he confirms that it's non-trivial and is bragging about the fact that he's not going to disclose how it's done:

.RTB file consists of two parts. The first part contains all the relocation offsets ... It is created with a special program called RTG (relocation table generator) from specially pre-processed Kickstart image. How to get this image, it is my magic and I'll never tell anybody about it. One note only: generation of 39.046 .RTB took 1 1/2 hours. (Manual work, + about 10 mins my 7MHz '010 CPU time).

I'm impressed that the first part can be generated, on a 68010...

Second part contains BCPL relocation table and it is required for 1.3 ROM only. It was created manually, analysing dos.library, which is written in BCPL in 1.3.

That's more classical way to do it: fully reverse-engineer the program. I suppose it's easier because dos library is smaller, and doesn't change much between 1.x kickstarts. Not much mystery here.

.RTB file is not easy to create. I don't recommend anybody to try it without very good knowledge of assembly language and machine code (not the same). N.B. Auxiliary tools to do such work took 1 month to develop.

Yeah, I don't recommend it either...

Anyone has information on the RTG program or how it could work ? (the author didn't even have access to memory protection to execute and find ill-relocated locations...)

Answer 1

The job is non-trivial, but I don't think it would be hard for someone 'experienced in the art'. 256k or even 512k is not a lot of code, and the ROMs are highly structured with a well-defined interface. I suspect it would be easier than cracking some of the more sophisticated copy-protection schemes used in Amiga games.

In some respects ROM code is easier to analyze than code compiled for RAM. No relocation quirks to worry about. No self-modifying code. Any PC-relative reference must be to code or static data (no variables mixed in with instructions!) etc. Most of the code was generated by C compilers which didn't optimize to the extent that modern compilers do, so it is clean and easy to follow.

One recognizes an address inside the ROM, but it could be a value too. Introducing heuristics to try to find the hidden ones can find some, but also find fake ones.

Any 32 bit number starting with $00fC is far more likely to be an address inside the ROM than a 'value'. Examining the code that uses the 'value' should tell you if it is an address or not.

And there are tables, that are difficult to figure out for the same reason (plus disassembling data confuses the disassembler which thinks that some data are instructions):

Tables are generally accessed with 'boiler plate' code that is easily recognizable. Tables of 16 bit words (commonly used for switch/case statements) don't need to be relocated.

A good disassembler should be able to correctly disassemble the code 99% of the time. Reviewing it and fixing misidentified sections might take a few hours. If the job is done properly it should reassemble to identical code, but this test probably isn't necessary. All you have to do is find those absolute references to memory locations in the ROM, and the rest is trivial.

Anyone has information on the RTG program or how it could work ?

I don't have any information on it, but I imagine it is just as the author described - a 'simple algorithm' that compresses the relocation offsets. You could probably figure it out by analyzing the program that extracts them.

(the author didn't even have access to memory protection to execute and find ill-relocated locations...)

No memory protection - the horror!

I doubt that those tables have been created by the actual Amiga developers who took time to assemble ROMs at different addresses to compute the relocation offsets (the simplest way to do that when you have the full source code)

They didn't do it, their compiler/linker did. Having the 'full' source code would actually be a very hard way to do it - perhaps even impossible. You would have to duplicate the exact development system that they used back then, including the same compiler versions, same make files etc. Disassembling the ROM to produce asm source which reassembles to identical code would be much easier.

Answer 2

I finally had to bite the bullet and do the exercise to create a .RTB of a ROM file which didn't have one: the old A1000 1.1 ROM (v31.34)

Bruce Abott answer is spot on on most parts, but devil is in the details.

As an introduction, I started thinking that I could do it when I successfully could relocate Red Zone, a Psygnosis 3D game running in chip memory (and now also others like Prince of Persia, Hunter, and others). In the case of Red Zone, it was every harder as the addresses were included between $8000 and $52000 so filtering between $FCxxxx and $FFxxxx was not an option.

The advantage with that game is that testing the full game (and activating all the code) was much easier than exploring every single part of the ROM.

I applied pretty much the same recipes in the case of the game and the old kickstart any way: IRA, python scripts, vasm assembler/linker, and some hours to spare.

As opposed to the author of SKick, I have nothing to hide and I'll describe my method.

• disassembly of the code using IRA (disassembler) with addresses/offsets in comments (-a option)
• a python script that reworks IRA labels so they match the addresses instead of being numbered LAB_0000, LAB_0001 ... That allow to convert addresses into labels when needed
• timesaver: a python script that converts longword 0 instruction (ORI.B #0,D0, clearly a zero longword, happens a lot in programs) into 2 0 words (so 2 offsets). In the future, when another scripts wants to insert a label, it finds the offset instead of having to split the line manually)
• assemble the code in 2 different ways: issue the original binary output, and issue an executable format. The original binary output mode is used to compare to the original ROM at each build. Stop and fix as soon as there's a difference. That's how you spot mistakes immediately. That way, you're sure not to degrade/insert bugs the original code base.
• An annoying part is finding instructions like move.l #address,Ax (or sub.l or cmp.l or pea...). As opposed to lea, the disassembler doesn't generate a label, it can't be sure if this is a data or an address. Another python script of mine does the job (better check the results manually, as sometimes games load an offset in an address register. Don't change those into a label or this will break!)
• now try to look for move.l (Ax,Dy),Az instructions, that may indicate that a jump table is used. The jump table is converted with a python script.
• There are also "hybrid" tables (aka structures) that contain data and pointers. Those are the trickiest. For the ROM case, just filtering longwords between 0xFC0000 and 0x100000 did the trick. At start you have fake code, and you end up (using another python script) with a nice dc.w or/and dc.l reloc_label list.
• When converting a zone to dc.w or dc.l, intermediate labels are / should be dropped. Another script (see below) should take care of re-inserting them if needed by parsing the unsatisfied symbols errors when assembling. But if the unsatisfied symbol appears in a branch instruction line it means that this is a fake branch instruction (happens a lot with lowercase ASCII unfortunately) and needs to be converted to ASCII data instead._
• The python script may generate labels that don't exist (yet) in the code base. Assembling & linking now yield unsatisfied symbols. A python script (add_undefined_labels.py) wraps the link, parses the output, and inserts the missing labels (remember: they contain the offset in the code) at the proper location. Sometimes it fails because the offset is in the middle of a data/fake instruction, in that case, converting the zone to dc.w or splitting the line is required. Repeat...
• If the executable can be created, then read the reloc hunk to get all reloc offsets. Much safer than generating everything by hand.
• BCPL (kick 1.x only) offsets are much trickier in theory, but in fact, just look for the in the upper part of the ROM (from 0xFF0000) for addresses divided by 4 that match the ROM address range (see below for a sample script)
• After that, a lot of addresses were probably overlooked. So I'm scanning the whole binary data for possible ROM addresses.

using such a python script (extract, see below for full scripts)

for offset in range(0,len(data)-4,2):
    value = struct.unpack_from(">I",data,offset)[0]
    if (0xFC0000 <= value < 0xFFFFF0) and (value & 0xFF):
        possible_reloc_values[value].append(offset)
    else:
        value *= 4
        if (0xFF0000 < value < 0xFFFFF0):
            possible_reloc_values_bcpl[value].append(offset)

This locates all APTR (normal) and BPTR (BCPL) potential relocs. Luckily, BTPR/BCPL relocs are all valid, whereas some normal relocs are obviously false alarms, but fortunately, we can remove the relocs that we know are valid since we have them.

There's the process of analysing the remaining relocs (less than 200 IIRC) by hand. I didn't create helper tools for that, but seeking the offsets of those relocs and checking asm code manually gives the solution instantly. The most annoying ones are the ones like 0xFFxxxxxx because they're often fake alarms (full-bit masks). Log all fake relocs in a table.

A link to the now complete reloc project is here: https://github.com/jotd666/kick1.1_A1000

Once it's done, relocate the ROM and boot it. I'm using whdload so if I've forgotten a reloc, the code will try to access the original 0xFC0000 to 0xFFFFFF zone (in the case of the ROM) and the MMU will catch the rare omissions (this is the final test, where you have to try to activate all the code to make sure that no part still contain relocs, but if the manual inspection of the remaining addresses was done properly, it's not needed (well you could have missed some move.l #address instructions). It was absolutely needed in the case of Red Zone because trying to guess all offsets would be too long: the addresses are not characteristic enough: no 0xFC, 0xFD, 0xFE characteristing most significant byte there.

Writing the .RTB format wasn't too difficult, except for the "checksum" part. It's a longword but I don't know which CRC algoritm was used... Anyway, for my case (whdload) it was not useful. And I can't imagine someone softkicking in version 1.1 for serious purposes.

So it took certainly more than 1.5 hours to do that, but not more than 4 or 5 hours, and the tools (part of them were reused) took a few hours to write to. I'm not sure I want to do it again for other kickstarts.

Answer 3

The simple answer is don’t build your relocation tables by disassembling the code, use the relocation tables already built in tools like Remus and Capitoline.

The more complex answer and the process I use to create the tables is by breaking down the Kickstart ROM into individual modules using the ROMHEADER and LIBHEADER structures, the program kickinfo does this, however, the exact boundaries aren’t clearly labelled (ROMSKIP is unreliable for this purpose). Once you know the boundaries of the individual libraries, you can be more confident that relative addresses you find in that range that reference an address in the range is valid, i.e. libraries don’t make absolute address references outside their boundaries (not entirely true), to call another library use use that libraries call table. Once you have a list of candidate RELOC addresses you can then perform two checks, verify with disassembly, and if you’re really lucky you’ll have another ROM with the same library in a different address, repeating the process should yield identical RELOCS, if not, only the ones in common are valid. If you byte for byte compare the same library in two different Kickstarts the only differences will be absolute addresses.

To read a Kickstart and pull out the libraries, you mainly only need to understand how each library is stored, this means reading the ROMTAG structure; ROMTAG Structure but be warned, RT_ENDSKIP is the minimum end, it could end after this, also the library might start before the ROMTAG.

Doobrey's Remus tool allows you to extract individual libraries from Kickstarts (that it knows about), you can also use my tool Capitoline (this may not be it's permanent home, but you will always find the most up to date info and link to the code on Facebook.

Once you have the extracted libraries, you can read these files as they are in Amiga HUNK format, the hunks you'll be most interested in are HUNK_RELOC* and HUNK_DREL* these allow the libraries to be placed anywhere in memory (although building a Kickstart is like loading a library, the absolute addresses are decided when you build it, which is why the relocs are "lost" when you build a Kickstart)

After you have all the RELOC data for the libraries in the Kickstart, the only things remaining are the things in the ROMHEADER, this exists at the start of the ROM (EXECBASE) and in the middle of the ROM (aka KickitySplit) or the start of an expansion ROM, all three are the same thing and make sure that the hardware knows where to start (ROMBASE).

The final note is to watch out for things that aren't in library RELOC data, things it doesn't expect to move, the most important one is the library scan table in exec.library, this is a list of addresses that exec scans for libraries, so it's absolutely crucial, for example, the KS 3.1 scantable looks lke this;

0x00F800000100000000F0000000F80000FFFFFFFF

which breaks down as scan F80000-100000 then F00000-F80000 (expansion roms), note the CD32 exec also has E00000, which is why it can use an extended Kickstart), so you need to treat that first F80000 as a reloc location too (obviously a disassembler will treat this as data)

Final note, Capitoline is mainly a Kickstart editing tool to assemble your own ROMs, but it’s got a bunch of extra utilities built in like a module extractor, disassembler, splitter, merger, patcher, byteswapper etc. it has a Windows GUI, but the CLI (Windows/Mac/Linux) has all commands available, it’s also got an RTB builder built in, but as with all these things it’s not something I’ve spent too much time on and it doesn’t create RTBs exactly the same as the skick ones - in some cases only the trailers are different. Unlike skick and Remus, Capitoline uses INI files for it's reloc data, these aren't as efficient, but they are human readable if you want to compare your relocs with mine.

---

Now about .RTB checksums:

The checksum (first four bytes of the RTB) is a (trivial) Commodore Amiga proprietary one, basically just summing every 4 byte word in the ROM additionally incrementing by 1 each time it overflows, the SUM of the ROM must add up to 0xFFFFFFFF therefore, any shortfall is set at position 20 bytes from the end of the ROM.

In other words, to make a valid RTB, just copy the 4 bytes at an offset of -20 from the end of the target kickstart.

Of course the other two issues are the different RTB trailers (i.e. it's not always 0x0000000000000000, and I haven't worked out why), and, the biggest issue, that you'll almost certainly need to create a .PAT file for the ROM to function correctly if relocated.

The tool I've written can create perfect RTB files for any kickstart it knows of, unfortunately, without the .PAT they are unlikely to actually boot with skick.