Reworking a decision tree to eliminate the dreaded GOTO

[metertech58761]

So I have some 6801 assembly code that I wanted to 'port' to C or similar modern language.

I finally realized the approach I need to take: Instead of translating the assembly language opcode by opcode, just write out in plain English what each section of code is supposed to do.
I can then use that English description as the basis for the code to be generated.

I've got a few sections redone, but I'm stuck on the next section which has a decision tree that I'm struggling with.

It should be possible to rewrite the GOTO-infested decision tree as a series of IF.. THEN.. ELSE.. but I'm not seeing it. Can anyone give me some suggestions?

The overall idea is that this code sends commands to a device being tested, monitors the relay contacts to ensure they are opening and closing, then reports the results.

Code: [Select]


; Test 72 - DCT related / strobe relays
Clear screen
Display text line 1: "Tst 72: Strobe rlys"

Load 2-way message template (msg2way)
msgTbl[6] = 0x60 // arm relays
Send message (msgCmd)
Delay: 125mS

Load 2-way message template (msg2way)
msgTbl[6] = 0x41 // open relays
Send message (msgCmd)
Delay: 125mS

rlyDTmp1 = rlyDStatus

Delay: 500mS

rlyATmp1 = rlyAStatus
rlyDTmp2 = rlyDStatus

Load 2-way message template (msg2way)
msgTbl[6] = 0x42 // close relays
Send message (msgCmd)
Delay: 125mS

rlyATmp2 = rlyAStatus

Delay: 500mS

\\ Evaluate Relay C (located in Relay A slot)

temp7 = 0

if (rlyAStatus == 0), goto test72_2

test72_1

Display text line 2: "Relay C: FAIL"

temp7 = (temp7 | 1)

goto test72_3

test72_2

if (rlyATmp2 == 0), goto test72_1

Display text line 2: "Relay C: PASS"

\\ Now evaluate Relay D

test72_3

if (rlyDTmp1 == 0), goto test72_4

if ((rlyATmp1 != 0) || (rlyDTmp2 != 0)), goto test72_4

Display text line 3: "Relay D: PASS"

goto test72_6

test72_4

Display text line 3: "Relay D: FAIL"

temp7 = (temp7 | 2)

\\ And the overall results?

test72_6

if (temp7 == 0), Display text line 4: "Test: PASS", test LED green
else display text line 4: "Test: FAIL", test LED red
Delay: 1 second
Get keypress: Repeat test or continue to next


[jpanhalt]

Doesn't "if, then, else" logic in Assembly often result in branch, goto, or call?  I don't do C, but I have read that when C is disassembleddecompiled, there are lots of goto's.  What's the problem with a goto/branch?  (Calls are a different story.)

Take this example in PIC Assembly:

Code: [Select]

btfss     PORTx,n
do something
do something else
The obvious problem is that "do something else" gets executed regardless of the btfss result (if false), unless there is a branch.  Now, if the "do something" is simple, like move a constant to the working register,  the branch can be avoided by something like this:

Code: [Select]

move something to WREG
btfss     PORTx,n
move something else to WREG
rest of code

John

[m k]

It should be possible to rewrite the GOTO-infested decision tree as a series of IF.. THEN.. ELSE.. but I'm not seeing it. Can anyone give me some suggestions?

if
then
else if
then

switch/case is another.
Don't forget to break out.

[audiotubes]

,

[audiotubes]

Right, there is no problem except that an academic who never delivered anything worthwhile in his life said they were bad.

That said, there are idiomatic ways to code in various languages. Not that C is an example of anything except how complete crap given away for free can take over the world, but in C goto is not idiomatic.

Everything has its time and place. For error handling, goto even in C is often the best way to deal with things. But, you can write bad code in any language and goto is not intrisincally bad.

[metertech58761]

audiotubes: I'm not saying that I'm completely against GOTO, but this little plate of spaghetti shows me why some people despise it.

My personal view is that GOTO is perfectly acceptable when used in moderation.

In this case, I intend to retain GOTO for moving between the main menu and test suites, and deciding whether specific tests are to be skipped according to certain variables.

But otherwise, when interpreting results or deciding which value to use, I would prefer to do so with some variation of IF.. THEN.. ELSE.

[pqass]

No GOTOs necessary; see C code below replacing stuff between "temp7=0 and test72_6 label:

Some may not approve of the use of a loop+break below but I find it cleaner [than haphazard GOTOs] and control flow is understood.

Code: [Select]

        // temp7 = 0

        do {
                if (rlyAStatus == 0 && rlyATmp2 != 0) {
                        // Display text line 2: "Relay C: PASS"
                        break;
                }
                // Display text line 2: "Relay C: FAIL"
                temp7 = (temp7 | 1);
        }  while (0);

        if ((rlyDTmp1 == 0) || ((rlyATmp1 != 0) || (rlyDTmp2 != 0))) {
                // Display text line 3: "Relay D: FAIL"

                temp7 = (temp7 | 2);
        } else {
                // Display text line 3: "Relay D: PASS"
        }

// test72_6


[golden_labels]

metertech58761: thre is no point in translating from assembly to any language. On average that isn’t bringing worthwhile improvement. Either rewrite it from scratch, a la clean-room development, or allocate the effort into improving the code elsewhere.

The cause behind no expected improvement arises from two factors. The original code is written using a mental model very different from that used by higher-level languages. Assembly is the most natural and readable way of expressing it. A direct C rewrite will look clumsy and weird. Higher-level programmers may find it deceitfully more readable, but not much more understandable. Assembly programmers are better with the original. No real gains for anybody.

The second issue is efficiency. Writing in assembly doesn’t imply higher performance. But writing exactly the same code in assembly and a higher-level language, the latter can rarely be better. I hope I don’t need to explain why.

So my advice would be: determine, if you actually gain anything by the rewrite. If you believe you do (e.g. portability to other platforms, no toolset dependency &c.), write down what are the observed effects of the code, let it sit away from your mind for a few weeks, come back and write it in C. Preferably without peeking at the original assembly. At least not until you find differences in behavior.

In either case: test, test, test. Even if you copy it to C, remember C uses a computational model dissimilar to your original assembly. Including some very unexpected behaviors and almost no way to precisely control timing/order.

[metertech58761]

m k: My goal in this case is to see if anyone else can see an easier way to phrase these specific evaluations such that I don't need to rely on so many GOTO statements.

[Nominal Animal]

I'd start by using Graphviz to visualize the code flow using a directed graph.  Each label is a node, and gotos, calls, and fallthroughs yield an edge (->).  For calls, I'd use a separate color, for example red: test72 -> somefunc [ color="#ff0000" ]; but you don't have any.  The resulting .dot file is (fixed)

Code: [Select]

digraph {
    node [ shape="ellipse" ];

    test72 -> test72_2;
    test72 -> test72_1;

    test72_1;
    test72_1 -> test72_3;
    test72_1 -> test72_2;

    test72_2;
    test72_2 -> test72_1;
    test72_2 -> test72_2_d;

    test72_2_d;
    test72_2_d -> test72_3;

    test72_3;
    test72_3 -> test72_4;
    test72_3 -> test72_3_d;

    test72_3_d;
    test72_3_d -> test72_6;

    test72_4;
    test72_4 -> test72_6;

    test72_6;
}If you have code both before and after a goto, I suggest adding a label (and thus a node) there; I did that for the display parts (_d suffix).

This is what dot -Tx11 above.dot (Linux) or dot -Tsvg above.dot > output.svg (SVG file you can view directly in your browser) generates (I removed the white background and converted it to GIF):


From this, it is much easier to decide on the if-then-else structure.   

In this case, in the body of the function test72, I'd have one while loop around test72_1, test72_2, and test72_2_d, followed by the code for test72_3, with an if-else case for test72_3_d and test73_4, followed by the code for test72_6.

It is extremely useful to consider the hardest parts first; here, how to make the while loop clean.  In this case, because they are just pass/fail checks, you can easily convert it into a single if-else case (with failure if rlyAStatus == 0 || rlyATmp == 0), eliminating the backwards-goto and thus the while loop.  This way, even the most intractable code can be slowly but surely unraveled, if you just have the time and the werewithal.

[jpanhalt]

I'd start by using Graphviz to visualize the code flow using a directed graph.

That's most interesting.

Does it actually analyze the code, or do you have to enter a flowchart?  I  often flowchart complicated stuff, but occasionally don't and quite rarely (bragging) get a stack overflow or underflow error.  Sometimes it's obvious and sometimes harder to find.  If it requires a flowchart, that won't help much.  If it can actually graph out calls and returns from raw code, that would help.

[Nominal Animal]

Does [Graphviz] actually analyze the code, or do you have to enter a flowchart?

It is just a visualizer, not a code analyser, so you have to write the .dot file yourself, or use a code analyzer that can generate it for you.

From symbolic assembly or disassembly, you can write a script that reads the mnemonics, generates missing target labels if any, and then the DOT language graph, as long as no computed jumps are used (those with a target address in a register).  Some code analysers do support DOT output, and most have a simple text/csv-based output that is easy to turn to DOT.  (awk is a very powerful tool for this.)

If you have an existing codebase with separate function symbols at the node level, and use ELF format object files, you can parse the possible call graph from the objdump output on many architectures (those where the relocation record uses the target symbol, not the target section with an offset).  If each function is put in its own section (via e.g. -ffunction-sections using GCC or clang), then the call graph can be done on all architectures using ELF object files.  I can show an example of this, although one of my not-yet-done projects is writing that in Python 3 (using just struct.Struct, no other dependencies); it already works (tested on AVR, ARM, x86, a86-64; need to test on a big-endian arch too), but the code is just too ugly to live in public.

In this case, because DOT supports comments (/* C-style */, // C/C++ style till the end of the line, and # at the start of the line), I would suggest writing the pseudocode (as shown in the thread start post) as a .dot file from the get go.  There are also many ways how nodes and edges and entire graphs can be modified, for example many different node shapes exist; so one could use those as well to indicate code section types.  Even HTML table node labels are possible.

[SiliconWizard]

So I have some 6801 assembly code that I wanted to 'port' to C or similar modern language.

I finally realized the approach I need to take: Instead of translating the assembly language opcode by opcode, just write out in plain English what each section of code is supposed to do.

Yes, that's a good start. But to make it better, I think you should not stop at translating the assembly code literally, but rather determine the FSM(s) that are implemented, using graphs if needed (as some have suggested), and then re-implement that in whatever language you're going to use. Don't start the implementation too soon, and don't do it as a translation.

The assembly "goto's" can be expressed as transitiions from one state to another.

[metertech58761]

Problem is, the original device uses a niche M6800 variant that is otherwise unavailable except from brokers at a "not worth it" price.

My first choice (and frankly my preference as I cut my teeth on 65xx assembly) was to clean up the sloppy assembly code and adjust it to work with the HC11/F1, but even those are drying up, and many of the support ICs on the digital side are at minimum well past NRND and aren't getting any cheaper (MC6840, i8279, etc.).

Given the popularity and ready availability of modules like RPi and 4x20 LCD modules, it would almost seem silly not to take advantage of that. Certainly a 4x20 LCD could be more user-friendly than eight 7-segment displays and eight LEDs?

So, yes, that is my goal - writing a plain English explanation of the assembly code, but that's not happening overnight, as the source alone is ~80K, at least a third of which is comments added as I had one 'Aha' moment after another, and I had a couple more while writing the summary of different sections.

[m k]

Goto is everywhere, it's just how far from the surface.
A route to dog.bark.awg.amp probably includes multiple unconditional jumps.
Goto can be even partially free with some newer hardware.

if (test)
{
}

Opening bracket is a conditional jump to closing bracket.

Optional part that maintains the original test result is

else
{
}

For literal values, characters included, there is also

switch (result_as_value)
{
case 1:
// do
break;
case 2:
case 4:
case 5:
// do
break;
case 3:
// do
break;
default:
}

There break is unconditional jump to closing bracket.

Nesting is nothing special.

if (test1)
{
if (test2)
{
if (test3)
{
do3();
}
do2();
}
do1();
}

But layout becomes important, at least for the future.

One other real benefit using C is that it generally has no whitespaces nor linefeeds.
So one string of characters can still be the same thing.

if (test1) { if (test2) { if (test3) { do3(); } do2(); } do1(); }

Latter layout can sometimes be much more informative.

There is also a block comment.

if (test1) { if (test2) { if (test3) { do3(); } do2(); /* always after test3 */ } do1(); }

Assembler code is easily very vertical, there editor can help, like collapsing stuff and adding colors.
Maybe there is also something that can use wide screen more productively, like adding newspaper style columns.

Would different endianness and language "orientation" be a major thing?