Editing Binary translation

{{short description|Form of binary recompilation}}
{{Use mdy dates|date=March 2014|cs1-dates=y}}
In [[computing]], '''binary translation''' is a form of [[binary recompilation]] where sequences of [[instruction (computer science)|instruction]]s are translated from a source [[instruction set]] (ISA) to the target instruction set with respect to the [[operating system]] for which the binary was compiled for. In some cases such as [[instruction set simulator|instruction set simulation]], the target instruction set may be the same as the source instruction set, providing testing and debugging features such as instruction trace, conditional breakpoints and [[Hot spot (computer science)|hot spot]] detection.

The two main types are static and dynamic binary translation.  Translation can be done in hardware (for example, by circuits in a [[CPU]]) or in software (e.g. run-time engines, static recompiler, emulators, all are typically slow).

== Motivation ==
Binary translation is motivated by a lack of a binary for a target platform, the lack of source code to compile for the target platform, or otherwise difficulty in compiling the source for the target platform.

Statically recompiled binaries run potentially faster than their respective emulated binaries, as the emulation overhead is removed.  This is similar to the difference in performance between interpreted and compiled programs in general.

== Static binary translation ==
A translator using static binary translation aims to convert all of the code of an [[Executable|executable file]] into code that runs on the target architecture and platform without having to run the code first, as is done in dynamic binary translation. This is very difficult to do correctly, since not all the code can be discovered by the translator. For example, some parts of the executable may be reachable only through [[indirect branch]]es, whose value is known only at run-time.

One such static binary translator uses universal [[superoptimization|superoptimizer]] [[peephole optimization|peephole]] technology (developed by [[Sorav Bansal]] and Alex Aiken from [[Stanford University]]) to perform efficient translation between possibly many source and target pairs, with considerably low development costs and high performance of the target binary. In experiments of PowerPC-to-x86 translations, some binaries even outperformed native versions, but on average they ran at two-thirds of native speed.<ref>{{cite conference |last1=Bansal |first1=Sorav |last2=Aiken |first2=Alex |title=Binary Translation Using Peephole Superoptimizers |book-title=Proceedings of the 8th USENIX conference on Operating systems design and implementation |date=December 2008 |pages=177–192 |url=https://www.usenix.org/legacy/events/osdi08/tech/full_papers/bansal/bansal.pdf}}</ref>

=== Examples for static binary translations ===
In 1960s [[Honeywell]] provided a program called the [[Liberator (Honeywell)|Liberator]] for their [[Honeywell 200]] series of computers; it could translate programs for the [[IBM 1400 series]] of computers into programs for the Honeywell 200 series.<ref>{{cite book |url=http://bitsavers.org/pdf/honeywell/series200/charlie_gibbs/012_Series_200_Summary_Description.pdf |title=Honeywell Series 200 Summary Description |date=February 1966 |publisher=[[Honeywell]] |page=11 |quote=For example, the instruction repertoire of Series 200 processors is similar enough to those of several other processing systcms, viz., the IBM 1400 series, to allow automated, one-time translation of programs written for these competitive systems to a form suitable for execution on higher-performance Series 200 systems.}}</ref>

In 1995 Norman Ramsey at [[Bell Communications Research]] and Mary F. Fernandez at Department of Computer Science, [[Princeton University]] developed ''The New Jersey Machine-Code Toolkit'' that had the basic tools for static assembly translation.<ref>{{cite conference |book-title=Proceeding TCON'95 Proceedings of the USENIX 1995 Technical Conference Proceedings |url=https://www.usenix.org/legacy/publications/library/proceedings/neworl/full_papers/ramsey |author-last1=Ramsey |author-first1=Norman |author-last2=Fernandez |author-first2=Mary F. |date=1995 |pages=24 |title=The New Jersey Machine-Code Toolkit |publisher=USENIX Association Berkeley, CA, USA}}</ref>

In 2004 Scott Elliott and Phillip R. Hutchinson at [[Nintendo]] developed a tool to generate "C" code from [[Game Boy]] binary that could then be compiled for a new platform and linked against a hardware library for use in airline entertainment systems.<ref>{{cite patent|country=US|number=7765539|title=System and method for trans-compiling video games|issue-date=2010|inventor1-last=Elliott|inventor2-last=Hutchinson|inventor1-first=Scott|inventor2-first=Phillip|url=http://www.google.com/patents/US7765539}}</ref>

In 2014, an [[ARM architecture]] version of the 1998 [[video game]] ''[[StarCraft (video game)|StarCraft]]'' was generated by static recompilation and additional [[reverse engineering]] of the original [[x86]] version.<ref>{{cite web |author-last=Steinlechner |author-first=Peter |date=March 10, 2014 |title=Starcraft für ARM-Handheld kompiliert |url=http://www.golem.de/news/open-pandora-starcraft-fuer-arm-handheld-kompiliert-1403-105031.html |access-date=March 25, 2014 |publisher=golem.de |language=de}}</ref><ref>{{cite web |author=notaz |date=March 4, 2014 |title=StarCraft |url=http://repo.openpandora.org/?page=detail&app=package.starcraft |access-date=March 26, 2014 |publisher=repo.openpandora.org}}</ref>
The [[Pandora (console)|Pandora]] handheld community was capable of developing the required tools<ref>{{cite web |author=notaz |date=2014-03-01 |title=ia32rtools/ |url=https://github.com/notaz/ia32rtools |access-date=2015-01-09 |publisher=[[GitHub]]}}</ref> on their own and achieving such translations successfully several times.<ref>{{cite web |author=notaz |date=March 4, 2014 |title=Starcraft |url=http://boards.openpandora.org/topic/15820-starcraft/ |access-date=March 29, 2014 |publisher=openpandora.org |quote=''The "no source, no port" rule is not completely true, you can get something similar (but not the same) as a port through static recompilation. Similar stuff was done several times by M-HT for some DOS games. The game was also converted for Android with somewhat similar approach.''}}</ref><ref>{{cite web |author=M-HT |title=Warcraft: Orcs & Humans |url=http://repo.openpandora.org/?page=detail&app=warcraft_sr |publisher=repo.openpandora.org}}</ref>

Another example is the [[Nintendo Entertainment System|NES]]-to-[[x86]] statically recompiled version of the videogame ''[[Super Mario Bros.]]'' which was generated under usage of [[LLVM]] in 2013.<ref>{{cite web |author-last=Kelley |author-first=Andrew |date=2013-07-07 |title=Statically Recompiling NES Games into Native Executables with LLVM and Go |url=http://andrewkelley.me/post/jamulator.html |access-date=2013-08-08 |quote=This article presents original research regarding the possibility of statically disassembling and recompiling Nintendo Entertainment System games into native executables.}}</ref>

For instance, a successful x86-to-[[x64]] static recompilation was generated for the [[Procedural generation|procedural terrain generator]] of the video game ''[[Cube World]]'' in 2014.<ref>{{cite web |author-last=Kærlev |author-first=Mathias |date=2014-04-14 |title=Practical and Portable X86 Recompilation |url=http://mp2.dk/blog/blog/2014/04/14/practical-and-portable-binary-recompilation/ |access-date=2014-08-08 |quote=but then the idea of somehow using the original x86 machine code presented itself. However, for our open server, we need to support x86-64 as well, and in that case, we absolutely need emulation or recompilation. […] Static recompilation to assembler seemed like a much better option, but to keep it portable, we would need to write backends for x86, x86-64, and possibly ARM/PowerPC.}}</ref>

== Dynamic binary translation ==
Dynamic binary translation (DBT) looks at a short sequence of code—typically on the order of a single [[basic block]]—then translates it and caches the resulting sequence. Code is only translated as it is discovered and when possible, and branch instructions are made to point to already translated and saved code ([[memoization]]).

Dynamic binary translation differs from simple emulation (eliminating the emulator's main read-decode-execute loop—a major performance bottleneck), paying for this by large overhead during translation time. This overhead is hopefully amortized as translated code sequences are executed multiple times.

More advanced dynamic translators employ [[dynamic recompilation]] where the translated code is instrumented to find out what portions are executed a large number of times, and these portions are [[compiler optimization|optimized]] aggressively. This technique is reminiscent of a [[JIT compiler]], and in fact such compilers (e.g. [[Sun Microsystems|Sun]]'s [[HotSpot (Java)|HotSpot]] technology) can be viewed as dynamic translators from a virtual instruction set (the [[bytecode]]) to a real one.

=== Examples for dynamic binary translations in software ===
* [[Apple Computer]] implemented a dynamic translating [[emulator]] for [[Motorola 68000 series|M68K]] code in their [[PowerPC]] line of [[Apple Macintosh|Macintoshes]],<ref name="Wharton_1994"/> which achieved a very high level of reliability, performance and compatibility (see [[Mac 68K emulator]]). This allowed Apple to bring the machines to market with only a partially native [[operating system]], and end users could adopt the new, faster architecture without risking their investment in software. Partly because the emulator was so successful, many parts of the operating system remained emulated. A full transition to a PowerPC native [[operating system]] (OS) was not made until the release of [[Mac OS X]] (10.0) in 2001. (The Mac OS X "[[Classic (Mac OS X)|Classic]]" runtime environment continued to offer this emulation capability on PowerPC Macs until [[Mac OS X 10.5]].)
* [[Mac OS X 10.4|Mac OS X 10.4.4]] for Intel-based Macs introduced the [[Rosetta (software)|Rosetta]] dynamic translation layer to ease Apple's transition from PPC-based hardware to x86. Developed for Apple by [[Transitive Corporation]], the Rosetta software is an implementation of Transitive's [[QuickTransit]] solution.
* QuickTransit during its product lifespan also provided [[SPARC]]→[[x86]], x86→[[PowerPC]] and [[MIPS architecture|MIPS]]→[[Itanium 2]] translation support.
* [[Digital Equipment Corporation|DEC]] achieved similar success with its translation tools to help users migrate from the [[Complex instruction set computer|CISC]] [[VAX]] architecture to the [[DEC Alpha|Alpha]] [[RISC]] architecture.{{citation needed|date=July 2011}}
* [[Hewlett-Packard|HP]] ARIES (Automatic Re-translation and Integrated Environment Simulation) is a software<ref>{{cite book |url=https://books.google.com/books?id=1hQ7ngEACAAJ |publisher=Prentice Hall PTR |date=2003 |title=Itanium Rising: Breaking Through Moore's Second Law of Computing Power |author-first1=Jim |author-last1=Carlson |author-first2=Jerry |author-last2=Huck |access-date=2015-01-09 |isbn=978-0-13046415-6}}</ref> dynamic binary translation system that combines fast code interpretation with two phase dynamic translation to transparently and accurately execute [[HP 9000]] [[HP-UX]] applications on [[HP-UX]] 11i for [[HPE Integrity Servers]].<ref>{{cite web |url=http://h21007.www2.hp.com/portal/site/dspp/menuitem.863c3e4cbcdc3f3515b49c108973a801/?ciid=0208713ba4f02110713ba4f02110275d6e10RCRD |title=HP ARIES Dynamic Binary Translator |publisher=[[Hewlett-Packard|HP]] |access-date=2015-01-09 |archive-url=https://web.archive.org/web/20150110072830/http://h21007.www2.hp.com/portal/site/dspp/menuitem.863c3e4cbcdc3f3515b49c108973a801/?ciid=0208713ba4f02110713ba4f02110275d6e10RCRD |archive-date=2015-01-10 |url-status=dead}}</ref> The ARIES fast interpreter emulates a complete set of non-privileged [[PA-RISC]] instructions with no user intervention. During interpretation, it monitors the application's execution pattern and translates only the frequently executed code into native [[Itanium]] code at runtime. ARIES implements two phase dynamic translation, a technique in which translated code in first phase collects runtime profile information which is used during second phase translation to further optimize the translated code. ARIES stores the dynamically translated code in memory buffer called code cache. Further references to translated basic blocks execute directly in the code cache and do not require additional interpretation or translation. The targets of translated code blocks are back-patched to ensure execution takes place in code cache most of the time. At the end of the emulation, ARIES discards all the translated code without modifying the original application. The ARIES emulation engine also implements Environment Emulation which emulates an [[HP 9000]] [[HP-UX]] application's system calls, signal delivery, exception management, threads management, emulation of [[Hewlett-Packard|HP]] [[GDB]] for debugging, and core file creation for the application.
* DEC created the [[FX!32]] binary translator for converting [[x86]] applications to Alpha applications.<ref name="Wharton_1994"/>
* [[Sun Microsystems]]' [[Wabi (software)|Wabi]] software included dynamic translation from x86 to SPARC instructions.
* In January 2000, [[Transmeta]] Corporation announced a novel processor design named [[Transmeta Crusoe|Crusoe]].<ref>{{cite web |url=http://archive.arstechnica.com/cpu/1q00/crusoe/m-crusoe-1.html |title=Transmeta Crusoe Explored |author-first1=Jon |author-last1=Stokes |publisher=[[Ars Technica]] |access-date=2015-01-09}}</ref><ref>{{cite web |url=http://www.geek.com/procspec/features/transmeta/crusoe.htm |title=Transmeta's Crusoe Microprocessor |author-first=Rob |author-last=Hughes |date=January 20, 2000 |publisher=[[geek.com]] |archive-url=https://web.archive.org/web/20070927184520/http://www.geek.com/procspec/features/transmeta/crusoe.htm |archive-date=September 27, 2007 |url-status=dead}}</ref> From the [[FAQ]]<ref>{{cite web |url=http://www.transmeta.com/crusoe/faq.html |title=Transmeta Crusoe Processor Frequently Asked Questions FAQ |publisher=[[Transmeta]] |date=2007 |archive-url=https://web.archive.org/web/20070110213448/http://www.transmeta.com/crusoe/faq.html |archive-date=2007-01-10 |url-status=dead}}</ref> on their web site, {{quote|''The smart microprocessor consists of a hardware [[VLIW]] core as its engine and a software layer called Code Morphing software. The Code Morphing software acts as a shell […] morphing or translating [[x86]] instructions to native Crusoe instructions. In addition, the Code Morphing software contains a dynamic compiler and code optimizer […] The result is increased performance at the least amount of power. […] [This] allows Transmeta to evolve the VLIW hardware and Code Morphing software separately without affecting the huge base of software applications.''}}
* [[Intel]] Corporation developed and implemented an [[IA-32 Execution Layer]] - a dynamic binary translator designed to support IA-32 applications on [[Itanium]]-based systems, which was included in [[Microsoft]] [[Windows Server]] for [[Itanium]] architecture, as well as in several flavors of [[Linux]], including [[Red Hat]] and [[SUSE Linux|Suse]].  It allowed IA-32 applications to run faster than they would using the native IA-32 mode on Itanium processors.
* [[Dolphin (emulator)|Dolphin]] (an emulator for the [[GameCube]]/[[Wii]]) performs JIT recompilation of PowerPC code to x86 and AArch64.
* [[Microsoft Virtual PC]] supports binary translation for 32-bit guest operating systems.
* [[VMware Workstation]] 12 or earlier are known to support binary translation for 32-bit guest operating systems.

=== Examples for dynamic binary translations in hardware ===
* [[Nvidia]] [[Tegra]] K1 Denver translates [[ARM architecture|ARM]] instructions over a slow hardware decoder to its native microcode instructions and uses a software binary translator for hot code.{{citation needed|date=February 2015}}

== See also ==
* [[Binary optimization]]
* [[Binary recompilation]]
* [[Dynamic recompilation]]
* [[Just-in-time compilation]]
* [[Instruction set simulator]]
* [[Emulator]]
* [[Virtual machine]]
* [[Comparison of platform virtualization software]]
* [[Shadow memory]]

== References ==
{{Reflist|refs=
<ref name="Wharton_1994">{{Cite journal |title=Gary Kildall, industry pioneer, dead at 52: created first microcomputer languages, disk operating systems |journal=[[Microprocessor Report]] |publisher=[[MicroDesign Resources Inc.]] (MDR) |author-first=John Harrison |author-last=Wharton |author-link=John Harrison Wharton |volume=8 |number=10 |date=1994-08-01 |url=http://tech-insider.org/personal-computers/research/1994/0801.html |access-date=2016-11-18 |url-status=live |archive-url=https://web.archive.org/web/20161118222925/http://tech-insider.org/personal-computers/research/1994/0801.html |archive-date=2016-11-18 |quote=[…] Ironically, many of the techniques [[Gary Arlen Kildall|Gary]] pioneered are being rediscovered now, ten years later. [[Apple Computer|Apple]] and [[Digital Equipment Corporation|DEC]] are touting [[binary recompilation]] as a "new" technology for porting existing software to the [[PowerPC]] or [[DEC Alpha|Alpha]] architecture. Actually, [[Digital Research|DRI]] introduced an [[8080]]-to-[[8086]] binary recompiler in the early 1980s. […]}}</ref>
}}

== Further reading ==
{{Refbegin}}
* {{Cite web |url=http://moodle.technion.ac.il/pluginfile.php/373059/mod_resource/content/3/IntroductionToBinaryTranslation-ver2.pdf |title=Introduction to Binary Translation |author-first=Gadi |author-last=Haber |publisher=[[Intel]] |date=2010 |access-date=March 30, 2014 |archive-url=https://web.archive.org/web/20160309094116/https://moodle.technion.ac.il/pluginfile.php/373059/mod_resource/content/3/IntroductionToBinaryTranslation-ver2.pdf |archive-date=March 9, 2016 |url-status=dead }}
* {{Cite web |url=http://www.cse.iitd.ernet.in/~sbansal/pubs/osdi08_html/index.html |title=Binary Translation Using Peephole Superoptimizers |publisher=Indian Institute of Technology Delhi |work=Department of Computer Science and Engineering |date=December 2008 |access-date=2014-03-30 |author-first1=Sorav |author-last1=Bansal |author-first2=Alex |author-last2=Aiken }}
* {{Cite conference |url=http://dl.acm.org/citation.cfm?id=956550 |title=IA-32 Execution Layer: a two-phase dynamic translator designed to support IA-32 applications on Itanium-based systems |author-first1=Leonid |author-last1=Baraz |author-first2=Tevi |author-last2=Devor |author-first3=Orna |author-last3=Etzion |author-first4=Shalom |author-last4=Goldenberg |author-first5=Alex |author-last5=Skaletsky |author-first6=Yun |author-last6=Wang |author-first7=Yigal |author-last7=Zemach |book-title=Proceedings of the 36th Annual IEEE/ACM International Symposium on Microarchitecture |series=MICRO 36 |date=2003 |isbn=978-0-7695-2043-8 |pages=191– |publisher=[[IEEE Computer Society]] |location=Washington, DC, USA }}
* {{Cite web |url=http://www.gtoal.com/sbt/ |title=An Emulator Writer's HOWTO for Static Binary Translation |author-first=Graham |author-last=Toal }}
* {{Cite journal |url=http://www.computer.org/csdl/mags/mi/1998/02/m2056-abs.html |title=FX!32: A Profile-Directed Binary Translator |journal=IEEE Micro |issn=0272-1732 |volume=18 |issue=2 |pages=56–64 |author-last1=Chernoff |author-first1=Anton |author-first2=Mark |author-last2=Herdeg |author-first3=Ray |author-last3=Hookway |author-first4=Chris |author-last4=Reeve |author-first5=Norman |author-last5=Rubin |author-first6=Tony |author-last6=Tye |author-first7=S. Bharadwaj |author-last7=Yadavalli |author-first8=John |author-last8=Yates |date=1998 |doi=10.1109/40.671403 |url-access=subscription }}
* {{Cite conference |url=https://books.google.com/books?id=U4IKBwAAQBAJ&pg=PA117 |title=ISAMAP: Instruction Mapping Driven by Dynamic Translation |author-first1=Maxwell |author-last1=Souza |author-first2=Daniel |author-last2=Nicácio |author-first3=Guido |author-last3=Araújo |conference=Computer Architecture - ISCA 2010 International Workshops |location=Saint-Malo, France |date=2010-06-23 |orig-year=2010-06-19 |pages=117– |isbn=9783642243226 }}
* {{Cite web |url=https://core.ac.uk/download/pdf/4417669.pdf |title=Dynamic Binary Translation from x86-32 code to x86-64 code for Virtualization |author-first=Yu-hsin |author-last=Chen |date=2009-06-20 |orig-year=2009-06-18 |publisher=[[Massachusetts Institute of Technology]] }}
{{Refend}}

[[Category:Emulation software]]
[[Category:Interpreters (computing)]]
[[Category:Virtualization]]