Code translation
Lee Hart
> I have to say, to simulate a Z80 on an 6502 would be a real
> challange, and if it has been done, I wouldn't be surprised
> it is extremely slow. 6502 is really limited in registers
> and instructions compared to the Z80.
This got me to thinking about an old problem again.
When you automatically translate machine code from one CPU to another,
the results are quite poor. Each instruction in the source code becomes
multiple instructions of object code. The resulting program runs much
slower, and takes much more memory.
It's not that one CPU is "inferior" to the other; it doesn't matter much
which way you go. A 6502 emulating a Z80 might run 10 times slower and
need twice the memory. But a Z80 emulating a 6502 also runs 10 times
slower and takes twices the memory.
However, suppose the source program was in some high-level language,
like C. Compile it for a Z80. Compile it for a 6502. Now the two
machine-code programs are nearly the same size, and run at nearly the
same speed. That's because the Z80 and 6502 are roughly equal performers
(assuming same memory size and same bus cycle rates).
Of course we can bury the problem with vast overkill of memory and clock
speeds; a 4 MHz 64k Z80 system can be emulated by a 400 MHz 64 megabyte
Pentium PC.
But shouldn't there be a more elegant, efficient solution? What Dr.
Dobbs used to call "running light without overbyte"? It seems that what
is needed is a decompiler; a program that disassembles a
machine-language program for one CPU into some higher-level language,
and then a recompiler that efficiently recompiles it for a *different*
CPU.
One simple test to see whether this is possible is to ask ourselves, "Is
it possible for a human to do this job?" I think the answer is "yes". On
numerous occasions, I have read assembler code for one CPU to understand
what it does, and then written equivalent code for another CPU that does
the same thing. But there is *not* a 1:1 correspondence between the two;
I may have to move things that were in registers into RAM, or reverse
the byte order, or replaces sequences of instructions with a single
instruction. It requires intelligence, but is an orderly process.
But I have never a decompiler-recompiler program to do this on an
automated basis. Has it been done? Has anyone even tried to do it?
--
If you would not be forgotten
When your body's dead and rotten
Then write of great deeds worth the reading
Or do the great deeds worth repeating
-- Ben Franklin, Poor Richard's Almanac
--
Lee A. Hart, 814 8th Ave N, Sartell MN 56377, leeahart_at_earthlink.net
Jack Peacock
news:42DA0C...@earthlink.net...
> But shouldn't there be a more elegant, efficient solution? What Dr.
> Dobbs used to call "running light without overbyte"? It seems that what
> is needed is a decompiler; a program that disassembles a
> machine-language program for one CPU into some higher-level language,
> and then a recompiler that efficiently recompiles it for a *different*
> CPU.
>
Alpha was a viable CPU chip Microsoft offerred a version of Windows NT
operating system, in native 64-bit Alpha code (but only 32-bit address
support). Alphas were the high end of NT servers, easily outrunning x86
contemporaries.
The problem was, Microsoft only had NT and a few server applications ported
to the Alpha. No Office, no Visual Studio in native Alpha mode, and that
was a killer in getting the Alpha accepted on the desktop. So DEC looked at
how to get x86 apps to run (with some reasonable performance) on the Alpha.
Their solution was a product known as FX32. It combined the concepts of an
instruction set interpreter and the idea of recompiling the binary of x86
into executable Alpha binary. The interpreter profiled the code as it
executed, identifying section where recompiling would be of greatest
benefit. FX32 then compiled the x86 binary section into an equivalent Alpha
object. The concept worked pretty well, with the net effect that the x86
app would speed up the more it was used. There was a penalty in terms of
memory and file size, but worth the benefit of being able to use x86 Windows
apps.
Sadly the Alpha met its demise a few years back, so FX32 is no more. Some
of the concepts do survive in VMS though. When VMS was ported from VAX to
Alpha, and now to Itanium, routines in assembler are ported to new
architectures by treating the assembly code as a high level language that is
compiled into the target processor binaries: VAX MACRO-32 compiles into
Alpha 64-bit code, Alpha compiles into Itanium.
Jack Peacock
jmk
bizarre) behaviors that virtually no one relies on, but have to be
correctly emulated if you want to be CERTAIN that the old code runs on
the new processor. I've done a number of replacement processor designs
for the military, where we took a processor and did the microcode to
make it look like some old TTL-based machine. It's the 80-20 rule (or
maybe the 90-10 rule)... most of the stuff is easy to emulate. Then
you hit something as simple as MDR (Move Double Register) - basically
copies Ri,Ri+1 to Rn,Rn+1. But what if Ri and Rn overlap, and in which
order. What if they are the same? You have to produce the same
GARBAGE that the origional chip did. And that, typically, is what
really starts to slow down the emulation.
Guy Macon
jmk wrote:
I might add that we CP/M users are lucky that virtually no one
relies on these quirks. On machines that had a lot of pirating
and anti-pirating such as the C64 or Apple II, many applications
(especially games) make use of any quirk they can find in order
to make disassembly/cracking harder.
Randy McLaughlin
news:11dnrtu...@corp.supernews.com...
Not true many programs use strange quirks for a variety of reasons.
Common methods include jumping into the middle of multibyte instructions to
either confuse disassembly as in the Electric Pencil and movcpm or just to
conserve bytes.
Self modifying code is extremely common, using undocumented instructions,
etc.
Any decent assembly language programmer builds a repertoire of tricky code.
I recently gave an example of byte swapping using only three instructions
that was an prime example of both poor programming and tricky code:
To swap bytes at 1000h & 1001h in three instructions (8080 code):
lhld 1000h
shld 0FFFh
shld 1001h
This code should never be found in a real program since it is slower and
takes more bytes than necessary as well as clobbering the two adjacent bytes
but it is common to jump into the second byte of an MVI or LXI instruction.
I often use jumps/calls into MVI/LXI (z80 LD) instructions to use alternate
the functions of routines, I also use rotate instructions to move a bit into
the carry flag to make a one byte comparison instruction.
Randy
www.s100-manuals.com
Scott Moore
> But shouldn't there be a more elegant, efficient solution? What Dr.
> Dobbs used to call "running light without overbyte"? It seems that what
> is needed is a decompiler; a program that disassembles a
> machine-language program for one CPU into some higher-level language,
> and then a recompiler that efficiently recompiles it for a *different*
> CPU.
No, the problem you are solving is not having the source code in your
possession. The problem of moving from one machine to another was solved
long ago (called a "compiler").
The reasons for lack of source are:
1. You don't own the program.
2. You lost the source.
Ni ether problem warrants great expenditures of programmer effort, certainly
not the vast resources that have been wasted on this "problem" in the name
of "binary translation".
>
> But I have never a decompiler-recompiler program to do this on an
> automated basis. Has it been done? Has anyone even tried to do it?
Decompilers are a fundamental tautology. The have worked, but only on
code from very poor compilers that tend to have the same simple sequences
in code repeated over and over. They fail on better compiled code.
So the tautology is that decompilers work best on code that is least
worth decompiling/moving to a different processor.
s_dub...@yahoo.com
Lee Hart wrote:
> from the "was there ever a CPM for..." thread:
> > I have to say, to simulate a Z80 on an 6502 would be a real
> > challange, and if it has been done, I wouldn't be surprised
> > it is extremely slow. 6502 is really limited in registers
> > and instructions compared to the Z80.
>
> This got me to thinking about an old problem again.
>
> When you automatically translate machine code from one CPU to another,
> the results are quite poor. Each instruction in the source code becomes
> multiple instructions of object code. The resulting program runs much
> slower, and takes much more memory.
>
> It's not that one CPU is "inferior" to the other; it doesn't matter much
> which way you go. A 6502 emulating a Z80 might run 10 times slower and
> need twice the memory. But a Z80 emulating a 6502 also runs 10 times
> slower and takes twices the memory.
>
> However, suppose the source program was in some high-level language,
> like C. Compile it for a Z80. Compile it for a 6502. Now the two
> machine-code programs are nearly the same size, and run at nearly the
> same speed. That's because the Z80 and 6502 are roughly equal performers
> (assuming same memory size and same bus cycle rates).
>
Seems to me the implementations of a HLL resolve down to abstract data
types, such as lists, stacks, fifo buffers [a form of list], trees; and
their operators. Those basic data abstractions can be implemented on
most cpu's to varying degrees of success. Hence, the HLL's are
portable.
> Of course we can bury the problem with vast overkill of memory and clock
> speeds; a 4 MHz 64k Z80 system can be emulated by a 400 MHz 64 megabyte
> Pentium PC.
>
> But shouldn't there be a more elegant, efficient solution? What Dr.
> Dobbs used to call "running light without overbyte"? It seems that what
> is needed is a decompiler; a program that disassembles a
> machine-language program for one CPU into some higher-level language,
> and then a recompiler that efficiently recompiles it for a *different*
> CPU.
>
Such as a reverse P-Code Decompiler? That would take a program an
decompile it into P-Code or some such, so you could recompile it for
another processor with a P-Code compiler. The abstract data types
should transfer. So the modern equivalent would be to decompile into a
Java Virtual Machine. Only, you are talking about: source cpu micro
code -> JVM -> target cpu micro code. So you need a decompile to Java,
and a JVM on the target cpu.
Fred J. Scipione
>> I have to say, to simulate a Z80 on an 6502 would be a real
>> challange, and if it has been done, I wouldn't be surprised
>> it is extremely slow. 6502 is really limited in registers
>> and instructions compared to the Z80.
>
> This got me to thinking about an old problem again.
> One simple test to see whether this is possible is to ask ourselves,
> "Is
> it possible for a human to do this job?" I think the answer is "yes".
> On
> numerous occasions, I have read assembler code for one CPU to
> understand
> what it does, and then written equivalent code for another CPU that
> does
> the same thing. But there is *not* a 1:1 correspondence between the
> two;
> I may have to move things that were in registers into RAM, or reverse
> the byte order, or replaces sequences of instructions with a single
> instruction. It requires intelligence, but is an orderly process.
>
> But I have never a decompiler-recompiler program to do this on an
> automated basis. Has it been done? Has anyone even tried to do it?
By serendipitous synchronicity, there is a recent thread on this very
topic over in comp.compilers. My summary of the wisdom espoused there
is that the amount of knowledge that would have to encoded into a
program for reasonable results is too great for anyone to have made the
effort by now, or in the near future. The problem is the amount of
detail needed for global consideration of the register and memory use
conversion, and for optimizing away un-needed flag manipulations.
Re-generating object code to semi-meaningful assembly code is hard
enough. To get any success in re-constructing source code requires
big hints, like knowing which compiler and libraries were used, and
having the de-bugger symbol information as well.
Try Googeling for 'de-compiler' to find some web literature on the
current state for the subject. It's been done, but only for some
very limited and specialized cases. At the present time, emulation
of the source machine is what's most practical, with just-in-time
compilation of emulator snippets yielding the best speeds.
Lee Hart
> the problem you are solving is not having the source code in your
> possession. The problem of moving from one machine to another was
> solved long ago (called a "compiler").
My understanding is that an "assembler" has pretty close to a 1 to 1
correspondence between assembly-language instructions and machine
language. So it is a code -- you can translate back and forth between
them 1 to 1, like english to morse code and vice versa.
But, I agree that assembly language often has comments that can help a
lot in understanding exactly why the program is doing what it does. For
instance, they can tell you the NAME of a memory location, so you
understand what's going on. These comments are lost when you disassemble
a machine-language program.
> Neither problem warrants great expenditures of programmer effort,
> certainly not the vast resources that have been wasted on this
> "problem" in the name of "binary translation".
Even if you have the assembly language source code for a program, I'm
not aware of any good translators to convert it for another CPU.
Programs like XLT86 were very crude, and needed a lot of tweaking.
Programs that translate 8080 mnemonics to Z80 mnemonics don't do any
actual code changing (such has fixing flag errors); they just do a blind
stupid substitution of LD H,L for MOV H,L etc.
There are a great many times when people need to run an old program on a
new computer. The only way I know of this being done successfully is
with an emulator; but you pay an enormous speed and memory penalty.
Luckily, speed and memory have advanced fast enough to make this "easy"
approach work. But it's going to get harder and harder in the future!
> Decompilers are a fundamental tautology.
I don't understand. "Tautology" is pointless repetition, like a
mandatory requirement.
> The have worked, but only on code from very poor compilers that
> tend to have the same simple sequences in code repeated over and
> over. They fail on better compiled code.
I can see that a poor decompiler would be like a poor data compression
algorithm -- it only works well on highly repetitive data.
However, we have very good data compression programs that work even on
highly nonrepetitive data. They can find deeply coded patterns, and take
advantage of them.
So, shouldn't it likewise be possible to look at long strings of machine
code instructions and say, "Aha! It's doing a 16-bit multiply on a CPU
that didn't have a multiply instructions. I can translate that into a
multiply statement in the high-level language."
I know that when I am analyzing a snippet of machine-level code, if I
look too closely, at just a few instructions at a time, all I see is
mindless register manipulations and memory moves. But as I widen my
scope, to cover dozens of instructions, the pattern becomes clear and I
can figure out what the code is doing.
--
The two most common elements in the universe are hydrogen and stupidity.
-- Harlan Ellison
Lee Hart
> Such as a reverse P-Code Decompiler? That would take a program an
> decompile it into P-Code or some such, so you could recompile it
> for another processor with a P-Code compiler.
> The abstract data types should transfer. So the modern equivalent
> would be to decompile into a Java Virtual Machine. Only, you are
> So you need a decompile to Java, and a JVM on the target cpu.
Yes; that's the idea.
--
The two most common elements in the universe are hydrogen and stupidity.
-- Harlan Ellison
bud
'Lo Lee:
Group: comp.os.cpm Date: Tue, Jul 19, 2005, 4:26am (CDT+5) From:
leea...@earthlink.net (Lee Hart)
script:
> The only way I know of this being done >successfully is with an
emulator; but you
>pay an enormous speed and memory
>penalty.
Seems to me that an emulator (a good one) is the perfect translator.
I don't understand why an 'emulator engine' couldn't be modified to
"'re-write' code to another platform", rather than just sending it to a
CPU.
Then again, IANAC (I Am Not A Coder).
:-))
salaam,
dowcom
P.S.: This is 'a thread after my on heart'. (No pun on Hart.)
To e-mail me, add the character zero to "dowcom". i.e.:
dowcom(zero)(at)webtv(dot)net.
--
http://community.webtv.net/dowcom/DOWCOMSAMSTRADGUIDE
MSWindows is television,… Linux is radar.
Guy Macon
bud wrote:
>Seems to me that an emulator (a good one) is the perfect translator.
>
>I don't understand why an 'emulator engine' couldn't be modified to
>"'re-write' code to another platform", rather than just sending it to a
>CPU.
>
>Then again, IANAC (I Am Not A Coder).
You might be enough of a coder to do the following - it's pretty simple.
Pick two CPUs; a 6502 and a Z80, for example.
[1] Write a very simple 6502 program that increments a memory
location and then loops. Very easy to do.
[2] Write a very simple Z80 program that increments a memory
location and then loops. Very easy to do.
[3] Write a very simple 6502 emulator in Z80 assembly language
that only has to emulate the increment/loop instructions in
program [1]. A bit harder, but still pretty easy to do.
[4] Write a very simple 6502 translator that translates [1]
into [2]. So easy to do that you can do it with a pen and
paper using a lookup table.
Now try to get [3] to create [2] out of [1]. Hard to do.
glen herrmannsfeldt
(snip)
> I might add that we CP/M users are lucky that virtually no one
> relies on these quirks. On machines that had a lot of pirating
> and anti-pirating such as the C64 or Apple II, many applications
> (especially games) make use of any quirk they can find in order
> to make disassembly/cracking harder.
In the Apple II case it was also the size constraint. The address
space for the built in ROMs was pretty small, after allocating to
the slot ROMs. I remember a story about someone selling cloned
Apple II's, including copies of the ROM, claiming that the only
possible ROM code was the Apple code so it should be legal to
copy it. There are a lot of tricks to make the code smaller,
such as branching to the second byte of an immediate instruction
where the instruction itself is not used, but only to ignore the
branched to instruction.
-- glen