Vintage Computing – RPC-4000

Dissecting the Story of Mel

One of the things that piqued my interest in the RPC-4000 was the role it plays in the “Story of Mel”. A famous piece of hacker folklore describing the early days of programming – when “abstraction” and “modularity” were not a thing yet. To the contrary, programmers aimed to make full use of all intricacies of a machine to optimize their programs. Any side effect that let you squeeze out another instruction cycle or save a word in memory was fair game!

The story is set around 1960, after Royal Precision had adapted their trusty Blackjack tradeshow demo from the LGP-30 to the new RPC-4000. Ed Nather was asked to fix a small bug in the program after the original programmer, Mel, had left the company. Ed describes the close-to-the metal programming of the day, Mel’s skill and ambition to optimize his code, and how Ed had a hard time figuring out Mel’s coding tricks.

Ed recounted and posted his story on Usenet in 1983. I won’t retell it here – Ed does a much better job at that. Please treat yourself to the original story if you have not read it!

But is it true?

Mel was for real, and he was indeed the programmer of the RPC-4000 Blackjack version. We now know that his full name was Mel Kaye (Americanized from Melvin Kornitzky); he is included in a group picture in a 1956 Librascope company journal; and his name appears on the Blackjack program documentation and a few other programming artefacts from his Librascope days. There is a great fan website researching Mel’s background and CV.

There is no reason to doubt that Mel did employ intricate and creative optimization tricks, and that his colleague Ed struggled mightily to figure them out. But Ed also describes in specific technical detail how the particular hack – finding a way out of an apparently infinite loop – supposedly worked. And some of those details don’t align with the actual RPC-4000 instruction set, which is well-known from the preserved manuals. Which leads to the question how Mel could actually have implemented such a hack on the RPC-4000.

Here’s the catch

Ed Nather describes how Mel routinely used self-modifying code to let his programs loop through array elements: Increase the address field in the instruction and write the modified instruction back to program memory, shunning the newfangled “indexed addressing” alternative offered by the RPC-4000. And he explains how Mel “abused” that mechanism to let the address field overflow into the opcode field – creating an entirely new instruction, which provided the only way to exit the otherwise endless loop he had set up.

Ed also recounts how Mel’s use of the Index flag gave him the vital clue in his reverse-engineering: In any given instruction, that flag bit activates the use of indexed addressing in the RPC-4000. And since Mel was known to never use that mode, something funny must be going on with an instruction which had the bit set. Ed explains that Mel needed to set the Index bit to ‘1’ to allow his overflow trick to work – because “the bit lay between the address and the operation code in the instruction word”. And that, unfortunately, is not the case:

Instruction word structure of the RPC-4000

This figure from the RPC-4000 Features Manual shows that the Command (opcode) bits are located directly above the Operand Address bits. Incrementing the Operand Adress to create an overflow into the Command field works nicely. But it works totally independent of the Index bit, which sits innocently at the very end of the instruction word as the least significant bit.

So there was no reason for Mel to set that bit – and give Ed the “vital clue” he needed to figure out Mel’s trickery. The story does not check out in this respect.

High memory is precious!

Ed also writes that Mel “had located the data he was working on near the top of memory — the largest locations the instructions could address”. That seems vital for the hack to work, because incrementing the address eventually needs to produce an overflow into the opcode field.

But the “top of memory” addresses are special in the RPC-4000. The five highest track addresses (123 to 127) refer to tracks which can hold fewer data words, but allow faster access to those words. Track 127 in particular holds only 8 words of data and automatically repeats them 8 times per revolution. In a program optimized for speed those words are nearly as valuable as the CPU registers for holding often-used variables. There is no way Mel would have wasted all of them on an array!

RPC-4000 Recirculating Track with read/write heads.

I think we can “rescue” this part of the story. It seems very likely to me that Mel was using the same sector number but different tracks for each of his array elements. Hence, to move forward to the next element, he would increment the track address by adding to bit 11. This can still produce the overflow into the opcode field, and uses only one word in each of the precious fast-access tracks.

This explanation also seems plausible because it preserves optimum timing for the array access – assuming Mel had optimized the relative locations of instructions and data on the drum to minimize waits, as was his standard. The array elements would all reside in the same sector, i.e. would be accessible at the same optimized time relative to the prior instruction fetch.

Hence, while Ed’s description of Mel having used “the top of memory” is probably not accurate, it does not get in the way of a plausible hack based on an address overflow.

A tangent about self-modifying code

As a side note, one of the shortcuts Ed attributes to Mel’s self-modifying code does not check out either. He mentions that, after incrementing and storing the modified instruction, Mel would “execute the modified instruction right from the register”. That’s not a facility available to RPC-4000 programs: The user can execute an instruction from the accumulator interactively from the front panel, as a way of bootstrapping the machine. But under program control there is no instruction to achieve the same effect.

While this is not a required feature for the hack described in the story, it is another indication that Ed’s memory of the technical details was a bit blurry – very understandable given that more than 20 years had passed.

Side note to the side note: “Read – modify – write back – read to execute” was a rather unfavorable sequence of actions on the RPC-4000. Three of those four operations require access to the same memory location on the drum, hence the total sequence takes more than two full drum revolutions. To make effective use of the computer, you would either have to interleave these operations with other code. Or you could place that critical self-modified instruction in one of the eight precious memory words on the RPC-4000’s “Recirculating Track” 127, where it would appear eight times per drum revolution for much faster access.

Or, if you could afford to reserve an accumulator for the duration of the loop: You could keep and increment the operand address in the accumulator and use a dedicated “Store Address” command to patch just the address field of an instruction in memory. That saved one memory access of the read – modify – write cycle, but you still needed another access to fetch and execute the instruction. The existence of a dedicated address patching command shows how commonly self-modifying code was used!

What others think

Several enthusiasts have looked into the technical details of the Story of Mel. But I am not convinced by any published analysis so far. In chronological order:

James Seibel does a nice job of catching modern readers up on magnetic drum vs. core memory, self-modifying code, index register functionality etc. But he does not look at the actual RPC-4000 instruction set and structure, and hence does not note the technical inconsistencies in the story.
David Nugent points out the ill-placed Index flag and the fact that one could nevertheless modify the opcode as a side effect. But I find his suggestion of the TBC instruction as Mel’s hidden Jump instruction less than convincing – the precursor of that instruction (i.e. TBC opcode minus 1) is already a conditional jump!

Also, David’s explanation for the need to set the Index bit, Ed’s vital clue, does not add up: To loop through array elements, one would never add to the least significant bit of the instruction. That would mess up the next instruction address, and require thousands of adds to actually change the operand address by one. Rather, one adds direclty to the operand address field, bit 17 and above. The Index flag in bit 31 does not have any effect on that operation and does not need to be set.
YeGoblynQueenne unfortunately misinterprets the bit order in the RPC-4000, and as a result suggests some explanations which are unnecessarily far from Ed’s account:

(a) The code did not run on an RPC-4000 at all but on an LGP-30, real or emulated. That does not make technical sense since the LGP-30 had no indexed addressing mode at all – so the “vital clue” key ingredient of the story would be missing.

(b) The hack was about the Branch Control flag rather than the Index flag. But Branch Control is not a bit field in each instruction, but rather a state flip-flop in the computer. Also, contrary to the Index mode, use of Branch Control is unavoidable in any nontrivial program, so Mel will certainly have used it routinely. For either reason, Ed would have had nothing to spot in the instructions as his clue.
David Frenkiel nicely explains the technical aspects of Ed Nather’s account. Alas, David’s discussion is again based on a misunderstanding of the bit order in the RPC-4000. He assumes the opcode field to reside in the least significant bits, which would render the whole overflow-induced opcode modification impossible. But as we saw above, that is not the case – the opcode resides in the most significant bits and the operand address can nicely overflow into it.

How did Mel really do it?

Key ingredients of the hack

There are several technical details of Mel’s hack which I assume Ed Nather remembered and recounted correctly, because they are so central to the story:

Mel liked to use self-modifying code. Incrementing the operand address field of an instruction to loop through an array seems a very likely scenario. As we saw in the “tangent” section above, this coding pattern was not uncommon – the RPC-4000 even offered a dedicated instruction to patch operand addresses in memory.
An overflow from the operand address into the opcode field is most likely also part of the hack. The opcode is indeed affected by an overflow of the operand address in the RPC-4000. And changing it into an entirely different operation can provide a baffling “way out” of an apparently infinite loop – which is what the story is about.
The Index flag must be set to make the hack work. Ed describes so vividly how finding the Index bit in use, contrary to Mel’s normal practice, was the vital clue which tipped him off – so I assume that setting this flag was indeed part of Mel’s hack.

So, assuming the above is right – what are the potential hacks Mel could have implemented on the RPC-4000?

Create a TBC instruction

TBC stands for Transfer on Branch Control, opcode 10111₂. It’s a conditional jump which is taken when the machine’s internal Branch Control flip-flop was set by a preceding operation – by an overflow, a comparison or by checking external switches. The bit field that serves as the operand address for most instructions becomes the Target Address, i.e. the address where program execution continues if the branch is taken.

David Nugent has previously proposed TBC as the likely “hidden jump” instruction used by Mel. It resonates with some of the aspects we expect to find in the hack, but I see a major stumbling block:

Setting the Index bit would not be strictly required to make this work, but it may be desirable to modify the Target Address by adding the Index register value. If the address were 0000 after the overflow of the operand address, that would send program control back to the cold start address of the Blackjack program (according to the preserved documentation). Adding the Index Register value to the Target Address would provide a convenient way to direct the branch elsewhere.

However, if the operand address got incremented by adding to its track part as suggested above, the sector part could easily be non-zero anyway – no need to add an Index offset. So we have only a weak motivation for one of the key elements in Ed’s account.
More critically, the “precursor” instruction for TBC, i.e. the opcode 10110₂ that must be present before the overflow, would be TMI – Transfer on Minus, another conditional branch instruction! Not only does this conflict with Ed’s statement that “the loop had no test in it”, but it also does not make much technical sense:

Just as with TBC, the TMI instruction interprets the operand address field as the Target Address for the conditional jump. Self-modifying code which keeps incrementing that Target Address would send the program to a different destination in every iteration through the loop. While such an address modification could be used for jump vector tables, it seems very exotic to do this in a loop over a full range of target addresses, and it certainly does not loop through a series of array elements. Also, Ed clearly states that the loop was accessing data located at the top end of the memory address range.

So I don’t think this conversion of a TMI into a TBC instruction is the specific opcode modification that Mel used.

Create a TMI instruction

As just mentioned, TMI is the other conditional branch available in the RPC-4000: Transfer on Minus, opcode 10110₂. Again, this could be created from its “precursor” instruction via an overflow of the operand address into the opcode field.

The same considerations regarding the Index bit apply as for the TBC scenario. So that part of Ed’s story can be explained, although not in a compelling way.
To create TMI via an overflow, one must start with CMG, Compare Memory Greater, opcode 10101₂. That’s not another branch, but it is still a bit “meh”: What purpose would a comparison serve if it is not followed by a conditional branch? The RPC-4000 did not have a Carry facility which could have made use of the comparison result in some other way. So it’s hard to see how Mel would have used the CMG for a useful purpose.

This is my favorite theory. The SNS instruction, Sense (opcode 00000₂), checks the status of a set of switches on the front panel (and/or of the active I/O devices) and sets the Branch Control flag accordingly. The track part of the operand address field is interpreted as a mask that defines which inputs are to be checked.

With the SNS hypothesis there is a compelling reason to set the Index flag: If you don’t, the mask field that defines which switches are evaluated will always be zero. (Remember the track address just overflowed.) The SNS instruction becomes a HaLT instruction in that case, and program execution stops. So the Index flag must be set to make this hack work – giving us a key ingredient of Ed’s story.
The precursor instruction before the address overflow is SBL in this case, Subtract from Lower accumulator, opcode 11111₂. Among the scenarios I have discussed, this is the only precursor which does something useful on its own before the overflow happens – another point in favor of this hypothesis.
Caveat: The SNS instruction will only set the Branch Control flag if one of its test conditions is actually met. The Blackjack program documentation describes how Sense Switch 1 controls the shuffling and cutting of the deck, so this may be a plausible SNS input. Or SNS could test for readiness of a known-to-be absent I/O device, which would always set the Branch Control. In either case we need to make an additional assumption to let the SNS test set the end-of-loop condition.
Caveat #2: The newly created SNS instruction is not a conditional branch in itself; it will jump to the same next instruction address as the SBL did before. So one does need a “regular” TBC branch in the code which follows the SNS (or the SBL preceding it). But when Ed states that “the loop had no test in it”, that may well refer to the lack of a test which sets the Branch Control flag, rather than the lack of a conditional branch instruction.
Actually the SBL instruction that would have been in place before the address overflow could set the Branch Control flag as well, upon producing an overflow (underflow). This makes for a particularly vexing potential code pattern: A subtraction which can, by program design, never underflow to set the Branch Control flag – but is nevertheless followed by a conditional TBC branch. I imagine Ed staring at that piece of code…

Conclusions

So, do we know the true details of Mel’s hack now? Not really…

Among the three scenarios I came up with, I would rule out the TBC variant and consider the creation of a SNS instruction the best fit, for the reasons discussed above. But there is no hard-and-fast argument that it’s the only plausible implementation. And of course there might be other variants which I have not even thought of!

I am currently revisiting my RPC-4000 replica project and plan to get in touch with a couple of collectors. Maybe there is still a chance that the original RPC-4000 Blackjack program will resurface and give us a definite answer…