U.S. Pat. No. 7,765,539

DETAILED DESCRIPTION

FIGS. 2 and 6show an exemplary illustrative non-limiting implementations of trans-compilation systems and methods. In these exemplary illustrative non-limiting implementations, a software executable502(e.g., a “source file”) such as a video game file (“ROM”) in binary format executable on one platform is “trans-compiled” so it can run on a different platform. A trans-compiler tool504is used in the exemplary illustrative non-limiting example to decompile the binary executable to provide source code in a convenient higher level language such as C, C++, JAVA, etc. The (re)generated C source file506is then compiled and linked using libraries and headers and a standard conventional optimizing compiler/linker508to provide a new executable “target object” for the target platform.

The illustrative non-limiting implementation shown inFIGS. 2 and 6can be used to translate existing game objects to new target platforms. The tool504reads standard game ROM files and produces a standard “C” language file representation of the original game code. This C file is then compiled and linked using GCC with header, standard library and special abstraction layer files to create a new executable object for a target platform. Tool504extends traditional compiler technology to support object code translation, thus for example providing a system that can execute on very restricted target platforms without any loss in performance. Unlike at least some emulator contexts, exemplary illustrative tool504creates one new executable object for each original executable object.

The C compiler and linker508may compile and/or link the source code with hardware emulation/mapping library routines510designed or written for the particular target platform. Such library routines510may, for example, simulate, emulate and/or “stub” certain functions available on the original platform that are not available on the new target platform (e.g., graphics capabilities such as 3D effects, rotation, scaling, texture mapping, blending, or any of a variety of other graphics related functionality, audio functionality such as sound generation based on proprietary sound formats, etc.). The resulting trans-compiled object file512is stored in some type of storage medium (e.g., an SDRAM card, memory stick, internal RAM, Flash memory, etc.) to be efficiently run on the target platform to provide a satisfying and interesting game play experience.

FIG. 3shows a view of exemplary software components of library routines510. Such software components may include, for example:CPU libraries510a,memory management unit libraries510b,interrupt libraries510c,video library510d,sound library510e,I/O library510f, andother libraries510g.

In the exemplary illustrative non-limiting example shown, the CPU library510aprovides functionality needed to allow the target CPU (which may be different from the original CPU) to run the game software or other application. In some cases, the target platform may have the same CPU as the original platform. In such cases, the CPU library510amay not need to include detailed CPU cross-platform functionality. In other cases, where the CPU of the target platform is different than the CPU from the source platform, the CPU library510amay need to provide certain functionality to allow the decompiled source code once recompiled and linked to run on the target platform. CPU library510amay also contain a variety of different functions that the target platform uses to support the game application (e.g., original platform CPU runtime libraries that have been (re)written to optimize performance on the target platform).

The exemplary memory management unit library510bshown inFIG. 3includes functions used to manage the actual, virtual and/or emulated memory provided by the target platform. The original platform for which the game or other application was written may include a particular memory architecture that the game or other application expects, takes advantage of and/or is otherwise customized for. In some cases, such memory management functionality may need to be emulated or simulated on the target platform. In other cases, the memory management functionality may be stripped out from the (re)generated source code and replaced with new memory management functionality optimized specifically for the target platform while still meeting requirements of the game.

In the exemplary illustrative non-limiting implementation, interrupt library510cmay be used to provide interrupt capabilities and support (see also discussion below on software interrupt capabilities). The original platform in general is likely to contain some type of interrupt structure and functionality (e.g., interrupt vectors, interrupt handlers, interrupt registers and associated priority, etc.) that may need to be emulated or otherwise provided on the target platform. Additionally, the target platform in general may contain an interrupt capability that the trans-compilation process desirably takes advantage of to provide high efficiency operation. As is well know, such interrupt capabilities allow for efficient handling of input, output, timing and other events without the need for extensive polling and other associated functionality.

In the exemplary illustrative non-limiting implementation, video library510dis used to provide graphics support on the target platform. For example, video library510dmay support color graphics generation including 2D and 3D effects such as for example rotation, scaling, character-based or bit mapped graphics, hidden surface removal, foreground/background prioritization, texture mapping, shading, etc. Sound library510esimilarly provides sound generation functionality such as for example playback of .WAV, MIDI or other sound file formats, sound generation based on proprietary sound representation formats, etc. In the exemplary illustrative non-limiting implementation, video library510dand sound library510emay provide functionality specific to the target platform based upon the target platform's graphics and sound generation capabilities. Necessary functionality provided by the original platform that is not available on the target platform may be emulated, simulated or otherwise handled to provide acceptable video game and/or other application execution.

The I/O library510fin the exemplary illustrative non-limiting implementation handles input and output functionality on the target platform. Typically, the user input devices available on the original platform are not identical to those present on the target platform, so I/O library510fprovides input control remapping (which may be user customizable in some instances) to take differences into account. The I/O library510fmay allow the trans-compiled video game or other application to communicate with a variety of other devices including for example memory cards, wireless adapters, infrared communication, head-to-head “game link” wired communication between devices, etc.

Other libraries510gmay be included to provide any additional functionality desired on the target platform.

FIG. 6provides an additional, more detailed exemplary view of the exemplary tool's software components and architecture (in this diagram, “NATSU” may refer to tool504). In the example shown, main or principal components include:

a tool chain for generating the transcompiler;

the transcompiler504itself;

abstraction layer libraries;

standard C libraries and headers; and

GCC built for the target tool environment.

In one exemplary illustrative implementation, the components used to generate the tool504include a compiler (“GCC”) built for the target tool environment (e.g., x86), the New Jersey Machine Code Toolkit; the Syntax description OCHA file in SLED format; the NJMCT generated parser C code file; and an open-source or other “decompiler” tool for controlled translation of object code into a C representation of that object code.

In the exemplary implementation shown, the tool504uses the original object ROM file (e.g., as previously prepared for distribution and execution on original native target platforms). The tool504generates various files including a decompiled C or other high level source file representing the original object code; a symbol file; and error/log file; and various header files.

The exemplary GCC compiler takes as its input the C or other decompiled high level source file generated by tool504representing the original object code. It may also use the tool-generated symbol file, the too-generated header files, and other convention input files such as UMAI Peripheral Abstraction Layer libraries, standard C libraries and standard C headers for the target CPU/OS of the target platform.

As shown inFIG. 4, the different software modules shown inFIG. 2may interact with one another in complex ways. For example, the CPU and/or MMU libraries510a,510bmay each or both interact with the sound functionality provided by sound library510e, the video functionality provided by video library510d, and the user input or other (e.g., wired or wireless “game link” networking) functionality provided by I/O library510f.

FIG. 5shows an example non-limiting storage medium600compatible with the target platform. The storage medium stores trans-compiled game code610and linked run-time libraries612native to the target platform.

Exemplary Compilation and Linking Process

In more detail,FIGS. 8 and 9show that an exemplary compilation process performed by compiler/linker508may use many of the same strategies as modern compilers. Such exemplary techniques include for example lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization, code generation, etc. The compilation/linking process may for example use a symbol table manager and an error handler as shown inFIG. 8.FIG. 9shows an exemplary compiler statement translation through these various phases of compilation and linking.

Exemplary Decompilation Process

One exemplary illustrative trans-compiler tool504implementation is based on a conventional open-source tool such as “Boomerang” for the controlled translation of object code into a C representation of that object code. Such a tool can work by the iterative abstraction of machine code to an internal abstract register transfer language and then into a C code representation of the original object code. The final C code is intended to be Turning Equivalent to the original C source code that the programmer originally created the original object code from. See for example http://boomerang.sourceforge.net/ (website incorporated herein by reference) for additional information

Note that source code output of transcompiler tool504is generally not identical to the original source code written by the software developer. For example, any comments the original programmer wrote will not be present in the decompiled output of tool504. In addition, a very large number of different variations of a hypothetical source code may all upon compilation produce the same object code. This is why the transcompiler tool504output is considered to be a Turning Equivalent (but not necessarily identical to) the original source code. We have found that there are advantages to conducting this process without using the actual original source code. Often, the original source code is no longer available or may not be available to the developers of the transcompiled code. In addition, there may be some advantage to working from decompiled source code as opposed to original source code even if the original source code is available.

Tables 1-3 below show exemplary comparisons between original source codes and decompiled source codes using tool504. These examples show that the resulting source codes are fairly readable and compile with no fatal errors and run correctly. For example, Table I illustrates features such as conversion of stack locations to local variables; detection, declaration use and initialization of arrays, correct handling of C strings through rough use of the string as a parameter to a library function, and replacement of a pretested “while” loop with a post-tested “do while” loop that are functionally equivalent.

TABLE 1test/pentium/summary:Original source codeDecompiled source code#include int a[10] = {1, 2, 3, 4, 5, 6, 7, 8,int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 109, 10};};char* global1 = “Sum is %d\n”;int main( ) {int main(int argc, char** argv, char**int sum = 0;envp)int i;{int local1; // m[r28{0} − 8] // sumint local2; // m[r28{0} − 12] // ilocal1 = 0;for (i=0; i < 10; i++) {local2 = 0;sum += a[i];while (local2 <= 9) {local1 += a[local2]; // sum += a[i]local2++; // i++}L3:printf(“Sum is %d\n”, sum);}return 0;printf(“Sum is %d\n”, local1);}return 0;}

TABLE 2test/pentium/fibo-O4:Original source codeDecompiled source code#include char* global0 = “Input number: ”;char global1[0];char* global2 = “fibonacci(%d) =%d\n”;int main (void)int main(int argc, char** argv, char** envp){ int number, value;{int local10; // r24 // valueint local7; // m[r28{0} − 8] // Local7int local8; // r24{39}int local9; // r28printf (“Input number: ”);printf(“Input number: ”);scanf (“%d”, &number);scanf(“%d”, local9 − 8); // Error: should bevalue = fib(number);&local7// The compiler inlined the call to fibif (local7 1){return (fib(x − 1) +int local6; // r24{18}fib(x − 2));int local7; // r24 // Return value (was eax)else return (x);if (param1 <= 1) {}local7 = param1; // ret = x} else {local6 = fib(param1 − 1); // temp1 = fib(x−1)local7 = fib(param1 − 2); // temp2 = fib(x−2)local7 = local7 + local6; // ret =temp1+temp2}return local7:}

TABLE 3test/pentium/fromssa2 (as of 24/Sep/04):Original source codeDecompiled source codevoid main( ) {int main(int argc, char** argv, char** envp){int a, x;int local8; // r27 // aa = 0;local8 = 0;do {do {a = a+1;local8++;x = a;%pc = %pc − 209; // x not assigned; error withprintf(“%d ”, a);%pc} while (a < 10);printf(“%d ”, local8);printf(“a is %d, x is} while (local8 <= 9); // Minor change%d\n”,a, x);printf(“a is %d, x is %d\n”, 10, 10); // Notereturn 0;10,10}return 0;}

Exemplary Tool “Front End”

The exemplary illustrative implementation uses a “front end” consisting of a series of modules that transform the source input into a high-level representation. The front end may comprise the following modules illustrated inFIG. 10:

binary file decoder

instruction decoder

semantic mapper

original RTM to HRTL translator

The exemplary illustrative implementation may not require a true lexical analyzer. Due to the highly regular nature of machine code, there may not be a need for a complex lexical analysis. Of course, one could be provided if desired. In the exemplary illustrative implementation, however, the lexical analyzer is replaced with a binary file decoder to read in the original source object code (seeFIG. 10).

Exemplary Trans-Compiler Tool Back End

The exemplary illustrative implementation transcompiler tool504provides target support for the C programming language. Other implementations could use other target source code support such as for example Javascript, Pascal, Visual Basic, Assembler or any desired source code format. The exemplary illustrative code generation C compiler and linker508may be very similar to traditional conventional compiler back ends. In one exemplary illustrative implementation, the HRTL is reduced to C code and the generated C code is provided to a GCC compiler/linker along with headers and libraries such as for example hardware libraries to create a final executable program. Retargeting the original object code to execute on a different target platform may use a Hardware Abstraction Layer. The interface between the Hardware Abstraction Layer and the application may be for example the registers and interrupts used by the original program on the original platform. The back-end of the Hardware Abstraction Layer may back-end interface to the target hardware. In one exemplary implementation the Hardware Abstraction Layer may be âεestubbed outâε to the original hardware so as to allow the original platform to be the new target. This can provide speed and performance optimization (i.e., in some instances the transcompiled version runs more efficiently than the original version).

Exemplary Software Interrupts

Software Interrupt instructions (SWIs) are used by the ARM and Thumb processors to emulate complex instruction sequences (i.e.: integer division, square root calculation, etc). The processor then changes mode to execute a series of instructions from ROM (Read-Only Memory). The instructions use a separate set of registers, so the original state of the processor remains undisturbed during this time. The instruction includes a 24-bit field in ARM mode and a 8-bit field in Thumb mode to distinguish the individual ROM sequences.

The GameBoy Advance (GBA) extended the capacity of the SWI instruction by adding several operations that are specific to the GBA. These operations include a decompression algorithm (LZ77), a Huffman decompression algorithm, several sequencing operations (Interrupt Wait), and graphics processing algorithms (BgAffineSet and ObjAffineSet). In our efforts to create a system that behaves in the same manner, we have translated these algorithms to C and compiled them as a separate library.

A Unified Machine Abstraction Interface library including sound, graphics, buttons, non-volatile memory, interrupts etc. may be used to provide the Hardware Abstraction Layer. Each Hardware Abstraction Layer should be customized to the particular target platform being used (i.e., there will be different Hardware Abstraction Layer libraries for different platforms).

Where original C source libraries are available, they may be included as standard C files. Otherwise, they will be generated from the original object files. ROM libraries may be translated in the normal manner and then linked as needed. The standard C headers for the target platform may be used by the compiler and linker to tie the application to the target platform. Standard C libraries may be linked as needed.

Traditional emulators may also be created using the libraries and techniques described above. Such emulators can be used for example to detect and identify hard to understand data objects such as those loaded at run time into the WRAM space. An Interrupt Replacement Unit may be used to replace C code in the recovered source to improve target hardware performance to avoid spin-locks for example. It is also possible to optimize performance by detecting wait times and recode waits into native calls, thereby avoiding spinlock waiting conditions. For example, one may want to recode virtual blanking wait tests into native function calls that do all the hardware events that happen up until the vertical blanking stage and then start the vertical blanking stage where the program resumes execution. It is also possible to take advantage of source platform detection of only a small subset of available software interrupt function calls to extend the software interrupt call set to include a wide array of hardware related stalls and code them into native calls. A common example would be a program waiting for a given horizontal blanking cycle to occur, which we can recode into different software interrupt calls depending on which registers are available. Since the tool generates a single C source code file in the exemplary illustrative implementation and it is typical for developers to use many C source code files, a higher level of optimization may be possible using the compiler techniques described herein due to the fact that the optimizing compiler will optimize over the entire (larger, common) source code file. Developers could achieve this same result by combining their source files into a single common file before final compilation. As compiler technology advances the recovered source can be recompiled with more advanced compilers.

Exemplary SWI Instructions and GBA Emulation

In our exemplary illustrative implementation, the GBA system should act in the same manner as the existing GameBoy Advance platform. To do this, we created a library for the existing set of software interrupt (SWI) instructions used in the GBA games. This library was written in C, so that it would be portable to other target platforms. The entry points to this new library in the exemplary illustrative implementation are compiled using SWI values that were not used in the original GBA ROM design.

Prior to the year 2000, a flaw was discovered in the ROM implementation of the GameBoy Advance sound routines. These functions were bypassed by adding the MusicPlayer 2000 music library to the GBA Sofware Development Kit (SDK).

While improving performance, we discovered that the MusicPlayer 2000 library was used repeatedly, generating several hundred ARM/Thumb instructions for every function call. We then analyzed the code in the MusicPlayer 2000 library, and replaced the entry points to the library functions with SWI instructions, calling target-independent C library functions. We then scanned each of the GBA games that we are deploying with our system, replacing the MusicPlayer 2000 libraries with SWI instructions.

We have continued to refine and extend this replacement process, substituting many complex series of instructions with a single SWI instruction, and creating a C library that executes the same operation. We have automated the process of identifying existing library entry points in our GBA games, and insert our SWI instructions prior to the deployment of the game.

Software development houses often use the same “engine” or the same set of libraries and algorithms between multiple games. We are exploiting this tendency by replacing these sections of common code with calls to our C libraries.

Since the number of sections of code will quickly exceed the number of available SWI instructions, we have modified our implementation. We now use an SWI instruction with the same value for any SWI in a particular game, and the OCHA system figures out which C library function to execute based on the current value of the program counter. This allows us to arbitrarily extend the list of known ARM/Thumb instructions that can be replaced by portable C library calls.

While the technology herein has been described in connection with exemplary illustrative non-limiting embodiments, the invention is not to be limited by the disclosure. For example, while Nintendo GAME BOY®, GAME BOY COLOR® and GAME BOY ADVANCE® platforms are used herein as examples, the technology herein could be used advantageously with any sort of computing, game or other platform. The invention is intended to be defined by the claims and to cover all corresponding and equivalent arrangements whether or not specifically disclosed herein.