Does this 1978 code for a 6800 really clear ALL of memory?

Question

On page 43 of the October 1978 Dr. Dobb's Journal (reprinted in Volume 3 Page 425 Issue 10 Number 29) is a letter to the editor giving three 6800 routines to clear ALL of memory, stating...

  Routine 1 (8 bytes): fill memory with NOPs. Properly
assembled, this routine will execute anywhere in memory.
    
2000 8E 20 03       LDS  #STACK
2003 86 01    STACK LDAA #NOP
2005 36       PUSH  PSHA
2006 20 FD          BRA  PUSH

  Routine 2 (5 bytes): fill memory with zeroes. This routine
must reside at the addresses shown, and assumes that executing
an opcode of zero is identical to executing an NOP.
    
FFFB 8E FF FD      LDS #HERE-1
FFFE 8D FE    HERE BSR HERE

  Routine 3 (8 bytes): fill memory with ones (all bits on).
This routine must reside at the addresses shown.

FFF7 8E FF FA       LDS #THERE
FFFA CE FF FF THERE LDX #HERE+2
FFFD 8D FE    HERE  BSR HERE

  Assuming that every location in the address space acts
like RAM (ie, can be read, written, and executed), then all
three routines fill ALL of memory, obliterating themselves
in the process.

Can anyone confirm this code really works as advertised, given the stated constraints?

---

(The Letter itself is a comment to an 8080 memory clear routine in DDJ of September 1976 Page 32, left column, all the way down)

Answer 1

Assuming the address space of the CPU is 100% writeable (i.e. no ROM somewhere), these routines seem in fact to clear all of the memory (including the routines themselves) to either zero or the opcode of NOP (01) by using the stack. They are, however, a bit of an academic nature - once the memory is completely filled, the CPU will be executing NOPs (or #0s) from the freshly cleared memory, without any possibility to escape.

All the routines seem to be relying on the fact that the stack pointer is expected to wrap around to $FFFF when it is at 0 and something is pushed. By exploiting this wrap-around, they clear the memory "behind" the routines and the routines themselves.

The tricky part of all routines is when the wrapped-around stack starts to "nibble" at code at the end of the routines: In routine 1, at some point the code at $2006 will change to

   BRA 1

which will jump into the series of NOPs already created, run through roughly 64k of NOPs (with the PC wrapping around) and do that several times until the PSH A is executed for the last time, replacing it with a NOP.

You might wonder why in routine 3, the X register is loaded with $FFFF: That is because on the last loop, the BSR HERE will overwrite itself with $FFFF, which is the instruction "STX $FFFF" - and fill the last bytes in memory from the X register.

None of the routines is, however, particularly useful. Once the RAM is set to the desired value, we've arrived in a dead end. Considering that contemporary computers often had a switch panel with single-step and HALT functionality, you could assume a bit more usefulness (you could stop the CPU looping through 64k of NOPS manually and enter new code - but that would assume some sort of banking mechanism to bank in some ROM for support)

Answer 2

The simple way to "confirm" those would be to find a 6800 emulator with debugger, load those snippets and execute them.

But just looking at them, I can explain how they should work, so I'd assume they should do what they said they would do (unless I am overlooking something). All of them use the 16-bit stack pointer S.

2000 8E 20 03         LDS  #STACK
2003 86 01      STACK LDAA #NOP
2005 36         PUSH  PSHA
2006 20 FD            BRA  PUSH

Point S to STACK, then load the opcode for NOP into A, then keep pushing it (wrapping around the 64K) until it overwrites the BRA, at which point execution will continue at 2009 (which doesn't help, because it has been overwritten). This will actually not clean the complete memory, but leave the loop of the code snippet intact (which is acceptable).

FFFB 8E FF FD        LDS #HERE-1
FFFE 8D FE      HERE BSR HERE

Do a subroutine call to HERE (which loops), pushing the return address, which happens to be 0000 for the code at this location. Finally it will overwrite the BSR with 00 00, execute those as NOPs, and continue to address 0000 (which again doesn't help, as it has been overwritten).

FFF7 8E FF FA         LDS #THERE
FFFA CE FF FF   THERE LDX #HERE+2
FFFD 8D FE      HERE  BSR HERE

Same idea, but the return address is FFFF, and the LDX acts as a nop already having FF FF as the operand.

Answer 3

The code works as advertised, let's examine each piece of code in (what some may call excruciating) detail, covering the "phases" in which it runs :-)

---

For the first code segment (at any base address):

base+0 8E 20 03       LDS  #STACK
base+3 86 01    STACK LDAA #NOP
base+5 36       PUSH  PSHA
base+6 20 FD          BRA  PUSH

The phases are:

• Executing the code from base+0 up to but not including base+5 (the PSHA). This code sets up the stack pointer and accumulator to perform the work in a loop, and no memory has yet been changed.

• The loop starts, and this loop only needs addresses base+5, through base+7 inclusive to be preserved. It places NOP into all memory locations from base+3 down to 0000 (base+4 already had a NOP).

• The stack pointer wraps to ffff and we continue writing NOP bytes down to base+8. At this point, all of memory is NOP except for the PSHA and BRA PUSH instructions.

• Now it gets a little tricky. The next PSHA replaces the offset of the BRA instruction with NOP which turns it into a BRA 1 instruction. When it executes that instruction, it no longer goes to the PUSH label but instead jumps a forward a little into the memory that contains all NOP instructions.

• It will continue executing each instruction, wrapping from ffff to 0000 and then executing the NOPs before base+5.

• Executing the PSHA at base+5 will then replace the first byte (opcode) of the BRA instruction with NOP and it will then start executing the NOPs again (the entire BRA PUSH is now two NOP instructions).

• It will once again go through all of the NOP memory, wrapping at ffff, until it once again reaches the PSHA. That instruction is the final nail in the coffin as all memory is now filled with NOP instructions. It will happily execute those instructions (wrapping and wrapping) until the heat death of the universe, assuming the CPU and power supply last that long.

---

The next one relies heavily on the code location because the return address is important:

FFFB 8E FF FD      LDS #HERE-1
FFFE 8D FE    HERE BSR HERE

In sequence:

• Execution of the first instruction sets the stack pointer to fffd. Note that the stack pointer in the 6800 is the first free location.

• The first BSR will push the return address on the stack then jump back to fffe. This return address is the address immediately past the BSR instruction, which is location 0000. This is written to memory locations fffc/fffd.

• The second execution of that BSR will do exactly the same thing but the 0000 return address is written to fffa/fffb (note that the first of each of these pairs is even).

• This continues up until the point that 0000/0001 is overwritten by the 0000 return address and the stack pointer becomes ffff.

• The next BSR execution will push 0000 to memory locations fffe/ffff, effectively filling the last bit of memory with zeros, and overwriting the BSR HERE instruction in the process.

• Then, as in the first example (assuming as the question states that the invalid 00 opcode is identical to NOP), it will run forever.

---

The final example is a variation on the second:

FFF7 8E FF FA       LDS #THERE
FFFA CE FF FF THERE LDX #HERE+2
FFFD 8D FE    HERE  BSR HERE

The sequence of events in this example are as follows:

• It has to first load fffa into the stack and ffff into the X register.
• The first BSR pushes the return address ffff into memory locations fff9/fffa and adjusts the stack pointer down two to fff8. Like the previous example, fffb/fffc are both already ff.
• This continues to the point where all memory from 0001 to fffc is set to ff, and the stack pointer is 0000.
• The next BSR instruction sets memory locations ffff/0000 (because of wrapping) both to ff and sets the stack pointer to fffd.
• The BSR then executes one last time, pushing ffff to memory locations fffd/fffe, overwriting the BSR instruction. All of memory is now set to ff and the program counter is fffd (the BSR was actioned).

As in both other cases, the code will run then forever, wrapping at the ffff/0000 boundary. Because memory is filled with ff bytes, the instructions executed are:

xxxx FF FF FF      STX $FFFF

This is the extended addressing mode STX which will get the two byte address at address ffff/0000 (which is, of course, ffff). It will then store the X register (which is also ffff) into that address. Hence no memory is changed by this instruction.