The obvious solution was to attempt to recreate the missing functions from the existing binary copy of CGMX. BCPL, like most compiled high level languages, tends to produce code that is fairly easy to recognise, for example the code for each routine in memory is prefixed with an ASCII copy of its name, all calls between BCPL routines are made using a support routine, %BSAVE, return from a BCPL function is made using a support routine %BRETURN, most calls between BCPL routines are made using addresses stored in the global vector, and so on.
The first task was to identify the different regions in the binary copy, notably the global vector. Since most calls pass via the global vector the easiest way would be to identify calls, which would have the form:
LDX 3 xxx [ load X3 from global vector
CALL 1 %BSAVE
yyyy [ size of current stack frame
Using the George 3 PRINT command it was possible to find that the binary CGMX contains 826 occurences of "CALL 1 16736", so it seemed probable that %BSAVE was at 16736, and examination showed that the code at 16736 started:
16736 !0EV +4458870 #21004566 ANDX 2 2422 16737 4802 +1081346 #04100002 NGN 0 2 16738 1+02 +372738 #01330002 TXU 0 2(3) 16739 ST5Q -3194511 #63640561 BCC 16753Which corresponds to the source of %BSAVE:
#CUE %BSAVE
# RTAP AND FNAP COMPILE TO :-
# CALL 1 SAVE
# N [SAVE SPACE RELATIVE TO P
# WITH X3=ADDRESS OF ROUTINE OR FUNCTION
# AND X4=RESULT IF ANY
ANDX 2 '#17777777'
NGN 0 2
BXE 0 2(3),TRCE
Assuming that 16736 was %BSAVE and the fact that compiled BCPL routines start with a prefined sequence including their name in ASCII it was possible to locate the global vector. The WRITEF function was discovered to be at address 13623:
13623 3S£] +996669 #03632475 BRN 13629 13624 000- +29 #00000035 LDX 0 29 13625 ____ -1 #77777777 177 7 4095(3) 13626 1E-" +415570 #01453522 ORS 0 1874(1) 13627 "%!5 +4805701 #22252105 DVR 2 1093(1) 13628 !@00 +4587520 #21400000 ANDS 2 0 13629 D20/ -7331809 #44020037 LDN 4 31(2)The sequence #01453522, #22252105, #21400000 decodes to the BCPL string "WRITEF". Searching low memory the address 13623 was found in location 1810, and that location was used in call sequences like:
2526 (0," +6293266 #30003422 LDX 3 1810
2527 ;D5@ +3031392 #13440540 CALL 1 16736
2528 00"' +1175 #00002227 LDX 0 1175
It seems probable that location 1810 is global vector entry 76, which implies that the global vector starts at 1735 (global vector entries start at 1). Examination of other calls confirms this hypothesis.
Armed with this knowledge it was possible to write a disassembler to convert the binary format of CGMX to a sequence of PLAN routines. For simplicity the disassembler was written in Perl (using a handy time machine found lying in the garage).
The disassembly was accomplished in a stepwise fashion, firstly the output from the George PRINT had to be slightly massaged -- it eliminates duplicate values from the output to make it more compact, the script expand.pl reinstated the omitted values.
Then the code was converted to PLAN format using the script disassemble.pl which performed the job of allocating labels for the addresses used in the code.
In order to produce more readable output disassemble.pl requires a list of names of elements in the global vector. In a first pass a script, extract-globals.pl was used to extract the global declarations from the CGMX source. This was complicated by the fact that some global vector elements had multiple names, in some cases it was obvious that one of them was wrong, for example CGMX uses element 100 for DATAP rather than the entrypoint PROGRAM, in some cases it was just that two slightly different names were used by different routines, WRITEO versus WRITEOCT. Another problem was that some global vector entries were clearly used by the compiled code but weren't mentioned in the source. The list of global entries was augmented by extracting missing routine names from the output of disassemble.pl, which was then re-run using the new list.
Running disassemble.pl on the original binary and the newly compiled version it was possible to see that the missing routines were:
APPENDN B.A.SET BRANCHAHEAD EMPTY FREECELL LIST NEWCELL PRINTSTACK REPORTSTATE -- never used and possibly incorrect. STRING SUMMARIZESTATE TRACENAMES WRITECUES WRITEOPexamination of the extracted routines showed some special cases, the code for WRITEOP included what was clearly a SWITCH command:
CALL 1 L1305 [ 12594 3027251 12595
L1305 ADX 1 4 [ 12595 2113540
LDX 4 3(1) [ 12596 -8384509
EXIT 4 0 [ 12597 -7438336
LDX 0 230(3) [ 12598 12518
LDX 0 232(3) [ 12599 12520
LDX 0 188(3) [ 12600 12476
LDX 0 188(3) [ 12601 12476
A script, fix-switch.pl was written to turn this into a usable form:
L1166 ADX 1 4 [ 12595 2113540
LDX 4 3(1) [ 12596 -8384509
EXIT 4 0 [ 12597 -7438336
/C2518
/C2520
/L1165
/L1165
...
Finally the extracted routines were massaged by a script, fix-plan.pl which, using the list of global vector entries, generated the necessary PLAN code to initialise the global vector with the adresses of the missing routines, producing the final replacement PLAN code.
When CGMX was recompiled with the replacement code it successfully generated code for the compiler.
The next project was to re-write the missing routines in BCPL. This is fairly easy to do as the code generated by CGMX is quite close to the OCODE generated by the compiler, which in turn maps rather clearly onto the original BCPL.
For example taking the PLAN version of the routine EMPTY:
First we have the standard BCPL routine start, a branch to the start of the routine, followed by the length of the stack frame (only for debugging, and not generated by all versions of CGMX), then a flag word containig the illegal instruction "-1" and the name of the routine encoded as BCPL ascii string: the name of the routine encoded
L0216 BRN L1116 [ 12039 995084 12044
LDX 0 3 [ 12040 3
-1 [ 12041 -1
345421 [ "EMPTY"
5264473
This translates into BCPL as:
LET EMPTY (label) BEThe start of the routine loads the argument of the routine to X4, and if it is zero returns to the caller:
L1116 LDX 4 2(2) [ load first argument, stack location 2(2)
BNZ 4 L1117 [ branch around return if not zero
BRN %BRETURN [ return from routine
Or, in BCPL:
IF addr EQ 0 RETURNotherwise we jump down.
L1117 BRN L1118 [ branch downPlaying with various example BCPL programs shows that the compiler outputs the body of loops before the end test, starting the loop with a jump to the end. For example a loop like:
WHILE A GE 23 DO $( SOMETHING() $)Will be compiled as:
BRN END LOOP ... SOMETHING END ... test A GE 23 BPZ LOOPThe advantage of doing this is that execution of the loop takes one less instruction, at the expense of one more instruction the first time around the loop. If we assume loops are usually executed more than once this is a clear win.
Examining the code at label L1118 we find:
L1118 LDX 4 2(2) [ load 1st argument
BNZ 4 L1121 [ loop if not zero
So what we have here is, in BCPL:
WHILE label NE 0 DO $(Then the body of the loop starts:
L1121 LDX 1 2(2) [ get 1st argument to index reg
LDX 4 0(1) [ load what 1st arg pointed at
STO 4 3(2) [ save in local stack frame
Which is the initialisation of a new local variable at stack location 3(2):
LET p = label!0Now we have what looks like a TEST (i.e. an if/then/else):
LDX 4 '4194304' [ get constant to X4
ANDX 4 3(2) [ and with local variable
BNZ 4 L1119 [ branch to "else"
Or, in BCPL:
TEST (p & #20000000) EQ 0 THENThe "then" branch is a call to the global routine SCF5 (global vector entry 249):
LDN 4 59 [ pass 1st argument, 59
STO 4 6(2) [
LDX 4 3(2) [ pass 2nd argument, local
STO 4 7(2) [ variable 3(2)
LDX 3 G249 [
CALL 1 %BSAVE [
4 [ 4 words in local stack frame
BRN L1120 [ Branch around "else"
which corresponds to the BCPL:
SCF5 (59, p)Then we get the else (OR in BCPL terminology) branch of the TEST:
L1119 LDN 4 4095 [ compute p & #7777
ANDX 4 3(2) [ in X4
LDN 5 52 [
STO 5 6(2) [ 1st arg is 52
STO 4 7(2) [ 2nd arg is p & #7777
LDX 3 G249 [ call SCF5
CALL 1 %BSAVE [
4 [
Which is BCPL:
OR SCF5 (52, p & #7777)The code continues with some more calls to SCF5:
L1120 STOZ 6(2) [ 1st arg is zero
LDX 4 '32767' [ 2nd is 32767
STO 4 7(2) [
LDX 3 G249 [ call SCF5
CALL 1 %BSAVE [
4 [
...
Then we have the use of a new local variable, stack location 4(2) so we must be in a new block:
LDX 4 2(2) [ load local 2(2)
STO 4 4(2) [ save as new local 4(2)
LDX 1 4(2) [ load local variable
LDX 4 1(1) [ load 2nd word it points at
STO 4 2(2) [ and save
Or, in BCPL:
$( LET q = label label := q!1Note the use of the routine argument as if it were a local variable. Now we call FREECELL with "q" as its argument:
LDX 4 4(2) [ pass local 4(2)
STO 4 7(2) [
LDX 3 G245 [ to routine FREECELL
CALL 1 %BSAVE [
5 [ stack frame size now 5
Note how the local stack frame is now 5 words as we have a new local variable. This is:
FREECELL (q)Now we reach the end of the loop. (Or, from the BCPL point of view the head of the loop):
L1118 LDX 4 2(2) [ get local
BNZ 4 L1121 [ loop back if nonzero
Followed by a last call to SCF5 and the RETURN:
LDN 4 59 [
STO 4 5(2) [
LDX 4 G111 [ Global STVQ
STO 4 6(2) [
LDX 3 G249 [ call SCF5
CALL 1 %BSAVE [
3 [ Stack frame now 3 words
BRN %BRETURN [ return
Note how the stack frame on the call to SCF5 is only 3 words, this implies we have left
the block where "p" was declared (the body of the loop) and the inner block where "q"
was declared. In BCPL:
$) $) SCF5 (59, STVQ) $)When the re-created code was compiled it turned out to be word-for-word identical with the PLAN code extracted from the original CGMX binary.
The same process has been used to recreate all of the missing BCPL routines:
appendn.bcpl b.a.set.bcpl branchahead.bcpl empty.bcpl list.bcpl newcell.bcpl -- functions NEWCELL and FREECELL printstack.bcpl string.bcpl summarizestate.bcpl tracenames.bcpl writecues.bcpl writeop.bcpl
The recreated functions have now been added to the code generator and it has been successfully rebuilt from source.