NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/sys/amiga/programmer/7418

Text File | 1996-08-05 | 6.1 KB | 132 lines

Newsgroups: comp.sys.amiga.programmer
Path: news.ifm.liu.se!liuida!news
From: [e-mail] (Mans Engman)
Subject: Re: 680X0 -> PPC translator?
X-Nntp-Posting-Host: astmatix.ida.liu.se
Message-ID: <[e-mail]>
Sender: [e-mail]
Organization: CIS Dept, Linkoping University, Sweden
X-Newsreader: THOR 2.22 (Amiga;TCP/IP) *UNREGISTERED*
References: <[e-mail]> <[e-mail]><[e-mail]><[e-mail]><[e-mail]><[e-mail]><[e-mail]><[e-mail]>
    <[e-mail]> <[e-mail]>
    <[e-mail]> <[e-mail]>
Date: Tue, 16 Apr 1996 08:19:24 GMT

>> What do you mean? You think someone will come up with algorithms to solve
>> problems *beyond* what a Turing machine can?

> excuse my poor knowledge of the english language, but i don't know what the
> hell turing
>machines are, so i can't reply to that.

Basically, there was a guy called Turing who introduced that concept. It's a
theoretical machine that is based on very simple axioms, yet it is the most
powerful formalism known. Apart from the limited memory of "real" computers,
every program can be transformed to a Turing machine and vice versa. They
are equivalent and are able to solve the same problems. So one may use this
abstract machine instead of having to prove things for different kinds of
programming languages and computers. And it follows that undecidable problems
are for real, that is, it has been proven that *no* possible algorithm can
exist which can solve all cases of these problems. If you wonder how the heck
one could prove these things I can recommend doing some reading about
computability/complexity theory.

>> This isn't an "irrelevant analogy", it's a simple example (among *many*
>> undecidable problems) used to construct a program for which you can't
>> analyse the program flow statically.

>'among many', PRECISLEY my point, your point still doesn't make it clear why
>static code translation isn't possible, don't generalise on questionable
>theories and be mucho more concrete, PLEASE!!!!

Precisley my point also. I showed how to make a program that will be able to
"fool" a translator, and you can't deal with the problem without assuming
things, as you've shown. Unless someone shows how to really solve the problem
this is a proof that static translation isn't possible for all cases. The
logic is perfectly clear, right?
(Besides, I wouldn't call those theories "questionable")

>No,no,no that's not what you said, you refered to making a pc-relative jump
>using some calculated value returned by some mathemtic function which is
>simply not possible cus then you'd have to call the function from distances
>of integer multiples of  your defined interval (say 42) otherwise you can't
>call the function from any other place that way and that's simply not
>practical to use in any program, AH AH no sirry. and even if you use this
>method there's no problem detecting the function which calculates this offset
>and figure which intervals are being used in the calculation. after all the
>interval is fixed and the interface of fata exchange between the caller and
>the callee is known to the analysing program, so it could discern the pattern
>and actually jump in integer multiples of that interval to either of the 2
>directions (up,down) and find the called functions that way.

No no no, you're assuming things again. The only restriction we have is
that the address jumped to is an even address. What is "practical" to
use is subjective and not relevant.

>>
>> Even if you use an array, you'd have exactly the same problem trying to
>> know which elements of the array are used as code pointers, and which of
>> them are something completely different. Like pointers to data which looks
>> like code, but isn't used as such (see below).

> not if the pointed code
> bytes make some sense ie use defined data addresses, make valid calls,
> has an RTS at the end, no, it's just too ordered for it to be just random
> chaos, now would it.

It makes sense so it *might* be code, right.

>> It's perhaps not practical to have this very-advanced-function(tm) to
>> calculate jump-addresses, but it's legal and possible.

>your 'highly' advanced feature will just have to wait for version 2.0 of the
>translator, i guess, initial target is for 'less-advanced' programs if you
>wish to call it that way which consist of ALL existing programs.

Who's generalizing now, eh? :)

So, when the v2.0 translator is out, I'd upgrade my program to v1.01 by adding
two instructions, and the translator won't work until v3.0.

>> $7070
>> $c1c1
>> $4e75
>> ...
>> moveq   #112,d0
>> muls    d1,d0
>> rts

>yes, true, but you can defer the translation until you ,ake sure someone's
>calling
>this piece of code, which can be done by further analysing the rest of the
>program. and besides, if a sequence of words makes some sense ie makes valid
>references to other memory areas and it's a long section then it's probably
>code, even you would have to agree that this is highly unlikely that it's
>some other data.

Yes, it's probably unlikely, possibly, for most cases, except those my wicked
mind will come up with. But I'd like to discuss theory and provable
algorithms, not statistics and heuristics.

>> The best thing you can do about this is to have the both the original data
>> and the translated part, in the final translated program.
>> Then, you could determine, at *run-time*, how it is used.

>NO!! no way, all the required information is in the binary itself, no need
>for any run-time analysis, you just need to know how to correctly distill
>this information into a useful one which i have described how in previous
>articles. give me problems i can't solve and then i'll raise my white flag
>otherwise, it's on with the crusade and the pirate skull flag is still held
>up high. hehehe

;)

Why don't you begin by trying to find an algorithm for solving my toy
example, Hilberts 10th problem. If you succeed you'll rule the world
(and have my deepest respect, believe it or not).

>Avi Lev.

/Mans (.sig being recompiled)