-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On Tue, 17 May 2005, Thomas Boutell wrote:
> (We can't always or even usually tell them in advance that they
> have too much code -- halting problem. But we can drop hints.
In the halting problem, you want to know if the code will go FOREVER.
This we cannot do.
In our problem here, however, you want to know if it is possible to
EXCEED A CERTAIN AMOUNT OF TIME. This we can do.
Treat the code as a graph, where each instruction is a node in the graph,
and the edges show possible flows of control. Each edge has a cost:
number of cycles consumed while executing the node we're leaving.
Note this is indeed the cost of the edge, as a branch may consume a
different number of cycles depending on which way it goes.
Now given the start node (the first instruction) and an end node (a return
instruction), you want to find the path through the graph with the lowest
cost. (This is a classic NP problem; it is solvable, although it becomes
computationally more expensive exponentially with the size of the graph.)
Once you have this lowest cost possible, you can compare it to a known
value (say the amount of cycles available in the overscan area) and
issue an error if it is too large.
That's only part of the problem though; i.e. an error will NOT be issued
if the SHORTEST path is short enough, but some other path might be too long
(or indeed infinite). These I agree we cannot catch.
- --
adam@xxxxxxxxxxxxxxxx http://cuddlepuddle.org/~adam
KG6GZR http://cuddlepuddle.org/~adam/resume.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)
iD8DBQFCi7DzyvXf5Z0z5zERAkCkAJoDLL5KroYyw+NFv2QLE+4ow7DV5wCgzEn+
k4QqP9fSFcLL6OAfbCtxSdE=
=TLPN
-----END PGP SIGNATURE-----
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://stella.biglist.com
