rom_patching.html 13.5 KB

Raw Blame History Permalink

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <title>Patching N64 ROMs for the BB Player</title>

  <meta http-equiv="content-type"
 content="text/html; charset=ISO-8859-1">
</head>
  <body>

<h2>Patching N64 ROMs for the BB Player</h2>
 November 2002<br>
  <br>
 This document is a collection of notes describing the issues and possible
solutions for patching existing N64 ROMs to work on the BB Player. &nbsp;Many
of these issues are related to the details of system compatibility as discussed
in the <a href="../hwimpact.html">porting issues</a> document. <br>
<br>
The main idea is that most differences in software compatibility are encapsulated
by the libultra library. &nbsp;The main areas of incompatibility from an
application software perspective are state saving, the manipulating the controller
and the rumble pack, and processor clock speed differences. &nbsp;Other incompatabilities
such as the use of flash memory as cartridge memory should be transparent
to game application once the hardware has been configured and the game application
launched. <br>
<br>
The idea behind trying to reuse existing ROMs is that it may be difficult
to gain access to source or even object files for all games, therefore it
is in our interest to try to use a modified version of the ROM image. &nbsp;If
the incompatibilities are encapuslated by libultra, then all that should
be required is to build a small library with replacement versions of the
libultra routines, insert that into some available space in the ROM image
such that it is loaded with the rest of the game and then patch references
from the game to the libultra routines to point to this new patch library.
&nbsp; &nbsp;This is probably a slight over-simplification of the problem.
&nbsp;We'll describe issues in more detail below:<br>
<br>
<h3>References from Patch libultra to ROM libultra</h3>
The small patch library itself may need to 'know' addresses of other routines
or shared data structures (e.g., to manipulate interrupts, etc), so there
is a step where these addresses are determined and inserted into the patch
library.<br>
<h3>Locating Call Sites in the ROM</h3>
To change the references to the original libultra to the new patch library,
every reference in the ROM for each function must be determined and replaced.
&nbsp;The best way to do this is to find the memory address of each function
entry to be patched and search for the references in the remainder of the
ROM code. &nbsp; &nbsp;Ideally, the game symbol table would give us this
information, but it is unlikely that we will have access to it. &nbsp;This
necessitates some reverse engineering of the ROM image to determine the addresses
of the function entries.<br>
<br>
One way to do this is by search the binary ROM image for an instruction sequence
pattern corresponding to each function. &nbsp;The patterns are determined
by extracting them from an <b>identical</b> libultra.a. &nbsp;This means
that we will need to know which release of libultra.a the game was linked
against and which development tools were used to produce the final image
so that we have the correct patterns. &nbsp;The search itself shouldn't be
very difficult since the instructions are fixed size and are 4-byte aligned.
&nbsp;The only special requirement is that bits holding addresses or displacements
need to be masked since the addresses/displacements will depend on the layout
of code in the ROM image. &nbsp; &nbsp;As an example here is the first part
of osEepromRead:<br>
<br>
&nbsp;&nbsp; &nbsp; &nbsp; <tt>0:&nbsp;&nbsp; 27bdffb0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
addiu&nbsp;&nbsp; $sp,$sp,-80<br>
&nbsp;&nbsp; 4:&nbsp;&nbsp; afb20038&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
sw&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $s2,56($sp)<br>
&nbsp;&nbsp; 8:&nbsp;&nbsp; 00c09021&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
move&nbsp;&nbsp;&nbsp; $s2,$a2<br>
&nbsp;&nbsp; c:&nbsp;&nbsp; afb10034&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
sw&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $s1,52($sp)<br>
&nbsp; 10:&nbsp;&nbsp; 3c110000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
lui&nbsp;&nbsp;&nbsp;&nbsp; $s1,0x0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
10: R_MIPS_HI16 __osEepPifRam<br>
&nbsp; 14:&nbsp;&nbsp; 26310000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
addiu&nbsp;&nbsp; $s1,$s1,0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
14: R_MIPS_LO16 __osEepPifRam<br>
&nbsp; 18:&nbsp;&nbsp; afb3003c&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
sw&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $s3,60($sp)<br>
&nbsp; 1c:&nbsp;&nbsp; 00809821&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
move&nbsp;&nbsp;&nbsp; $s3,$a0<br>
&nbsp; 20:&nbsp;&nbsp; afb40040&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
sw&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $s4,64($sp)<br>
&nbsp; 24:&nbsp;&nbsp; 30b400ff&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
andi&nbsp;&nbsp;&nbsp; $s4,$a1,0xff<br>
&nbsp; 28:&nbsp;&nbsp; afbf0048&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
sw&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $ra,72($sp)<br>
&nbsp; 2c:&nbsp;&nbsp; afbc0044&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
sw&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $gp,68($sp)<br>
&nbsp; 30:&nbsp;&nbsp; afb00030&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
sw&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $s0,48($sp)<br>
&nbsp; 34:&nbsp;&nbsp; 3c190000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
lui&nbsp;&nbsp;&nbsp;&nbsp; $t9,0x0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
34: R_MIPS_HI16 __osSiGetAccess<br>
&nbsp; 38:&nbsp;&nbsp; 27390000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
addiu&nbsp;&nbsp; $t9,$t9,0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
38: R_MIPS_LO16 __osSiGetAccess<br>
&nbsp; 3c:&nbsp;&nbsp; 0320f809&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
jalr&nbsp;&nbsp;&nbsp; $t9<br>
&nbsp; 40:&nbsp;&nbsp; 00000000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
nop<br>
&nbsp; 44:&nbsp;&nbsp; 02602021&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
move&nbsp;&nbsp;&nbsp; $a0,$s3<br>
&nbsp; 48:&nbsp;&nbsp; 27a50018&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
addiu&nbsp;&nbsp; $a1,$sp,24<br>
&nbsp; 4c:&nbsp;&nbsp; 3c190000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
lui&nbsp;&nbsp;&nbsp;&nbsp; $t9,0x0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
4c: R_MIPS_HI16 __osEepStatus<br>
&nbsp; 50:&nbsp;&nbsp; 27390000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
addiu&nbsp;&nbsp; $t9,$t9,0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
50: R_MIPS_LO16 __osEepStatus<br>
&nbsp; 54:&nbsp;&nbsp; 0320f809&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
jalr&nbsp;&nbsp;&nbsp; $t9<br>
&nbsp; 58:&nbsp;&nbsp; 00000000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
nop<br>
&nbsp; 5c:&nbsp;&nbsp; 97a30018&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
lhu&nbsp;&nbsp;&nbsp;&nbsp; $v1,24($sp)<br>
&nbsp; 60:&nbsp;&nbsp; 00408021&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
move&nbsp;&nbsp;&nbsp; $s0,$v0<br>
&nbsp; 64:&nbsp;&nbsp; 1600005e&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
bnez&nbsp;&nbsp;&nbsp; $s0,1e0 &lt;osEepromRead+0x1e0&gt;<br>
&nbsp; 68:&nbsp;&nbsp; 3063c000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
andi&nbsp;&nbsp;&nbsp; $v1,$v1,0xc000<br>
&nbsp; 6c:&nbsp;&nbsp; 34028000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
li&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $v0,0x8000<br>
&nbsp; 70:&nbsp;&nbsp; 10620005&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
beq&nbsp;&nbsp;&nbsp;&nbsp; $v1,$v0,88 &lt;osEepromRead+0x88&gt;<br>
&nbsp; 74:&nbsp;&nbsp; 3402c000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
li&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $v0,0xc000<br>
&nbsp; 78:&nbsp;&nbsp; 10620008&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
beq&nbsp;&nbsp;&nbsp;&nbsp; $v1,$v0,9c &lt;osEepromRead+0x9c&gt;<br>
&nbsp; 7c:&nbsp;&nbsp; 24020001&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
li&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $v0,1<br>
&nbsp; 80:&nbsp;&nbsp; 08000029&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
j&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a4 &lt;osEepromRead+0xa4&gt;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
80: R_MIPS_26&nbsp;&nbsp; .text<br>
&nbsp; 84:&nbsp;&nbsp; 24100008&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
li&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $s0,8<br>
&nbsp; 88:&nbsp;&nbsp; 2e820040&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
sltiu&nbsp;&nbsp; $v0,$s4,64<br>
&nbsp; 8c:&nbsp;&nbsp; 50400005&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
beqzl&nbsp;&nbsp; $v0,a4 &lt;osEepromRead+0xa4&gt;<br>
&nbsp; 90:&nbsp;&nbsp; 2410ffff&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
li&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $s0,-1<br>
&nbsp; 94:&nbsp;&nbsp; 08000029&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
j&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a4 &lt;osEepromRead+0xa4&gt;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
94: R_MIPS_26&nbsp;&nbsp; .text<br>
&nbsp; 98:&nbsp;&nbsp; 00000000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
nop<br>
&nbsp; 9c:&nbsp;&nbsp; 3c010000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
lui&nbsp;&nbsp;&nbsp;&nbsp; $at,0x0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
9c: R_MIPS_HI16 __osEepromRead16K<br>
&nbsp; a0:&nbsp;&nbsp; ac220000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
sw&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $v0,0($at)</tt><br>
<br>
The binary encodings of the instruction are in the second column. &nbsp;Any
instruction which has associated relocation information (e.g., R_MIPS_xxxx),
needs to have an appropriate mask to avoid comparing the relocated information.<br>
<br>
So to do the pattern matching the relevant version of libultra needs to be
converted to a set of patterns. &nbsp; Once the patterns have been produced,
the addresses of the function entries are located (typically the address
of the first word in the pattern), then all jumps to each address need to
be located. &nbsp;The jumps will likely use either the jump absolute or jump
register instructions, so these need to be located and then analyzed to determine
if they are to a target address. &nbsp;The jal instructions should be simple
enough since the address is encoded in the instruction, the jalr instructions
are more complicated since the contents of the register needs to be determined
before the match can be done. &nbsp;Depending on the compiler used, the jump
idiom might be easy to analyze, e.g., for the version of gcc we are using
it looks like:<br>
<br>
<tt>lui&nbsp;&nbsp;&nbsp; &nbsp;$t9,addr_hi<br>
addiu&nbsp;&nbsp; $t9,$t9,addr_lo<br>
jalr&nbsp;&nbsp;&nbsp; $t9</tt><br>
<br>
For the most part we will assume that we are only looking for subroutine
jumps and that the application does not store pointers to functions in libultra.<br>
<h3>Placing The Patch Library</h3>
The patch library needs to be loaded into a predefined ram location.&nbsp;
&nbsp;However, we need to understand some basics concerning how memory is
used by the game in order to locate some free memory. &nbsp;In addition,
the game has to be modified to load the patch library code into memory. &nbsp;If
necesary, we could have the BB Browser app perform this step as part of game
loading. &nbsp;The real issue is locating a good place in memory to put the
code without knowing any details of the memory map.<br>
<h3>Multiple Code Segments and Compression</h3>
Many games use multiple code segments. &nbsp;Often the bootsegment contains
all of the libultra code used by the other segments, however; all of the
segments need to be modified to use the patch library. &nbsp;This requires
identifying all of the code segments in the ROM image and patching them.
&nbsp;The brute force way to do this is to search all of ROM for patterns
that look like MIPS instruction sequences. &nbsp;Another approach is to try
to snoop transfers from cartridge space and try to build a segment map, and
then look at individual segments. &nbsp; One additional complication is that
segments other than the boot segment are likely to be compressed with an
abitrary compression scheme and are only decompressed when they are loaded
to memory. &nbsp;This makes the task extremely complicated unless we have
a priori knowledge of the compression scheme. &nbsp;Again, trying to determine
the segment boundaries in advance by snooping cartridge accesses may help,
however once a compressed segment has been located it still may be difficult
to determine the compression scheme. &nbsp;So far we are aware of two schemes
from two different games. &nbsp;One tool that may help with this task is
instrumenting one of the existing N64 PC emulators to help dump information
about the game while it is executing.<br>
<h3>Summary of Issues</h3>
<ul>
  <li>Obtaining correct version of libultra_rom.a for a given game - shouldn't
be very difficult - need OS2.0D to OS2.0L releases</li>
  <li>Identifying all code segments in decompressed form for patching - could
be arbitrarily difficult</li>
  <li>Find free space in memory map for patch code - for 4M games, easy;
for anything else need extra knowledge or snoop ram addresses</li>
  <li>Hook to load patch code into ram - can make part of game launch if
necessary.<br>
  </li>
</ul>
<br>
<br>

</body>
</html>