Neliac Decompiler
Program-Transformation.Org: The Program Transformation Wiki
Tom Moran wrote:
- A working decompiler for NELIAC, an Algol 58 derivative language not too unlike C, is described (including source listing) in Appendix D in "Machine-Independent Computer Programming" by Maurice H. Halstead, copyright 1962 and undoubtedly long out of print. It cites a Navy Electronics Laboratory Technical Memorandum #427 by Joel Donnelly which might conceivably still be available.
- Halstead saw a decompiler as useful for 1) understanding/modifying a program to which you no longer had source code, and 2) porting such a program to a new machine by decompiling it and then recompiling for the new machine.
The following is from the book:
Maurice H. Halstead, "Machine-Independent Computer Programming" Spartan Books, Washington DC 1962.Note how programs are displayed in octal, not even indisassembled form.
Decompiling with D-Neliac
For several years it has been apparent that those computer programs written in machine-dependent languages represented large investments in time which were lost whenever a change in computers was required. Even though a change to a machine-independent language was made, all programs written before the change still require complete rewriting if they are to remain in use. If, however, such programs could be computer-converted to the Neliac language, then they would be in a form adaptable to recompilation upon any other computer having a Neliac compiler. Furthermore, if the translator were to be capable of accepting the machine-language programs of a given computer as input, then it would not matter whether the program had originally been written in machine language, in an assembly system, or any possible problem-oriented compiler system. While it would be premature to infer that this objective can be met with complete satisfaction, the Donnelly D-Neliac system [15] as as produced by J. K. Donnelly and Herman Englander has already established that such an approach is highly feasible, and preliminary versions now exist for both the Remington Rand Univac M-460 Countess computer and for the Control Data Corporation 1604 computer. A recent version of the former is given in complete detail in Appendix D. To understand the workings of a decompiler, consider the following case, in which Example 69 shows the source material, a machine-language version of a program which has been written, tested, and rendered operational on the M-460 Countess. [15] J. K. Donnelly, "A Decompiler for the Countess Computer," Navy Electronics Laboratory Technical Memorandum 427 , Sept., 1960.EXAMPLE 69. Address ff jkb yyyyy Address ff jkb yyyyy 10100 00 000 00000 10142 07 000 00036 10101 00 000 00000 10143 03 000 00036 10102 00 000 00000 10144 23 030 10106 10103 00 000 00000 10145 14 030 10107 10104 00 000 00000 10146 61 010 10131 10105 00 000 00000 10147 10 030 10103 10106 00 000 00000 10150 26 030 10100 10107 00 000 00000 10151 22 030 10106 10110 00 000 00000 10152 14 030 10107 10111 00 000 00000 10153 10 030 10100 10112 00 000 00000 10154 27 630 10103 10113 00 000 00000 I0155 65 000 10113 10114 10 030 10103 10156 11 030 10100 10115 35 030 10100 10157 10 030 10106 10116 61 010 10113 10160 27 000 00001 10117 00 000 00000 10161 04 430 10103 10120 10 000 00005 10162 61 000 10165 10121 26 030 10100 10163 65 000 10117 10122 27 730 10106 10164 61 000 10166 10123 61 000 10126 10165 65 000 10131 10124 65 000 10113 10166 61 000 10167 10125 61 000 10130 10167 12 100 00000 10126 10 030 10103 10170 10 000 00170 10127 34 030 10100 10171 40 031 10103 10130 61 010 10117 10172 07 000 00073 10131 00 000 00000 10173 41 031 10100 10132 10 030 10106 10174 07 000 00072 10133 26 030 10103 10175 14 031 10107 10134 07 000 00036 10176 71 100 00003 10135 03 000 00036 10177 61 000 10170 10136 23 030 10106 10200 10 030 10103 10137 26 030 10107 10201 14 030 10106 10140 22 030 10100 10202 61 400 10000 10141 26 030 10103The program of Example 69 was then accepted by the Decompiler of Appendix D, which found all of the absolute addresses used as nouns or verbs, and assigned arbitrary names to them. The program logic itself was then decoded into the equivalent Neliac statements, as shown in Example 70.
EXAMPLE 71.
SUB A 0 10117
ENT A 0 10166
ENT B 0 10167
SUB B 0 10113
ENT C 0 10130
ENT D 0 10126
ENT E 0 10165
SUB C 0 10131
START 0 10147
AA 3 10103
AB 3 10100
AC 3 10106
AD 3 10107
where an initial zero denotes a verb and a 3 indicates a noun.
It may be noted that in a case of this kind there is no inherent
meaning in the names assigned to nouns or verbs, except perhaps
to the first and last of the verbs. If the original documentation has
been adequate, so that the comments accompanying the original
program has been sufficiently informative to allow a person to provide
meaningful names for given addresses, the decompiler will
accept and use them.
As can be seen from a study of Appendix D, in the event that
a machine-language combination is encountered for which no
decompilation instructions have been written it can still convert them
to the Neliac machine-language form, and then continue. Strangely
enough, working with decompilers has emphasized one of the
limitations in the bit-handling capabilities of the Neliac language. This
limitation consists of the inability to specify any but contiguous
bits in a part word, a feature sometimes used in masking for logical
operations.
In addition to its primary mission of translating non-Neliac
programs into the Neliac language, D-Neliac has also proved useful
in another way. This secondary use has been in the area of error
detection. Since a program will appear in different words, and
with several of the details handled differently if it is decompiled
after having been compiled, the paraphrased version is sometimes
helpful in the detection of errors in logic. A classic example is a
case in which an occasionally used regression-analysis program was
found to fault in certain circumstances. Since the program had
originally been coded in machine language by a mathematician no
longer available, the fault was so subtle that it had not been found,
even after considerable searching. Upon decompilation, however,
it was immediately apparent that a misuse of an index occasion-
ally occurred.
A final pair of examples will show the decompilation of one of
the utility routines long in use on the Countess for loading flexo-
writer coded punched tape. This particular routine calls upon
other subroutines outside the area being decompiled, so that while
the decompiler named them, it obviously could record only their
locations, and not their contents. The numerical values for the
Flexowriter codes in Table III correspond with results in this case,
too, of course. The first example shows the raw program as fed
to the D-Neliac program, the second shows the Neliac program
which it produced, while the third shows the Name List which it
also furnished.
EXAMPLE 72. Ad.dress ff jkb yyyyy Ad.dress ff jkb yyyyy 00522 00 000 00000 00565 12 130 00130 00523 65 000 00352 00566 10 030 00132 00524 65 000 00211 00567 14 031 00000 00525 16 030 00130 00570 61 000 00526 00526 16 030 00131 00571 65 000 00346 00527 16 030 00132 00572 12 500 00007 00530 12 300 00000 00573 10 030 00130 00531 10 030 00130 00574 27 515 00133 00532 27 500 00051 00575 61 000 00541 00533 61 000 00571 00576 72 500 00573 00534 10 030 00130 00577 11 530 00130 00535 27 500 00045 00600 61 000 00571 00536 61 000 00571 00601 10 030 00130 00537 65 000 00346 0060? 27 500 00004 00540 61 000 00526 00603 61 000 00571 00541 10 003 00000 00604 10 030 00130 00542 27 700 00005 00605 27 500 00057 00543 61 000 00553 00606 61 000 00571 00544 10 030 00131 00607 10 030 00130 00545 05 000 00003 00610 27 500 00047 00546 14 030 00467 00611 61 000 00571 00547 10 005 00000 00612 10 030 00130 00550 26 030 00467 00613 27 500 00077 00551 14 030 00131 00614 61 000 00571 00552 61 000 00561 00615 10 030 00130 00553 10 030 00132 00616 27 400 00042 00554 05 000 00003 00617 61 000 00526 00555 14 030 00467 00620 65 000 00346 00556 10 005 00000 00621 10 030 00130 00557 26 030 00467 00622 27 400 00042 00560 14 030 00132 00623 61 000 00526 00561 12 303 00001 00624 65 000 00265 00562 10 003 00000 00625 65 000 00363 00563 27 400 00017 00626 61 010 00522 00564 61 000 00571 00627 00 000 00000
EXAMPLE 74. SUB A 0 352 SUB B 0 211 SUB C 0 346 ENT A 0 526 ENT B 0 571 SUB D 0 265 SUB E 0 363 ENT C 0 522 ENT D 0 541 ENT E 0 561 ENT F 0 553 START 0 522 AA 3 130 AB 3 131 AC 3 132 AD 3 467 AE 3 133Click here for the Univac M460 instruction set. CategoryDecompilation