17

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)

9
  • I touched up the assembly for you here because PUSH at address 2005 is a label, and so it belongs in the other column Nov 2, 2023 at 8:37
  • 4
    Routine 1 seems to rely on the fact that you can use a mnemonic as an immediate (the #NOP) - That's actually not a very common feature.
    – tofro
    Nov 2, 2023 at 8:39
  • 1
    @Lorraine wasn't, see the linked source material. But since the letter just shows off the routines itself, the author might have believed that constant to be obvious.
    – Raffzahn
    Nov 2, 2023 at 14:19
  • 5
    What's might be more interesting to today's readers than that little NOP trick is the reasoning for the original 8080 routine: "the program will infinitely loop, writing zero into the same memory location. The lights on your computer will indicate when the program has stopped;". A feature that can only be understood with a front panel computers in mind - less common nowadays :))
    – Raffzahn
    Nov 2, 2023 at 14:24
  • 2
    Oh my, a real-world imp, what fun!
    – noughtnaut
    Nov 2, 2023 at 18:06

3 Answers 3

12

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)

11
  • 6
    I'd say the usefulness seems obvious - at least in back then mindset of programmers believing they create the most sought after product in the universe and want to protect it against 'piracy'. By pointing monitor/break vectors to this routine an attempt to inspect the code will delete the code. [ I'll take that 'back then' back - people arestill the same, just the machines more complex :) ]
    – Raffzahn
    Nov 2, 2023 at 13:54
  • 1
    @Raffzahn If "destructive" is considered "useful" as in your example, then yes :)
    – tofro
    Nov 2, 2023 at 14:13
  • 2
    It's a use case - of course usefulness of that case is in the eye of the beholder :))
    – Raffzahn
    Nov 2, 2023 at 14:17
  • 2
    @raffzahn Well, if my goal would be to protect my code, I would rather overwrite memory with something that looks like reasonable code, but isn't, than with NOPs. But I'm a terrible character, I admit :)
    – tofro
    Nov 2, 2023 at 14:24
  • 2
    @BlackJack going by the letters written (see the links added to the question) it seems clear that it's more about being some code golf challenge than any real use case.
    – Raffzahn
    Nov 2, 2023 at 21:32
6

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.

4
  • 7
    I'm pretty sure once the BRA PUSH is partially overwritten, it will change into BRA 1, (thus jump into NOPs already created), run through alll these until $FFFF, PC would wrap around and run into the code yet again (Assuming "everywhere is RAM"). That will continue until everything is set to NOP - Admittedly, it is pretty unlikely we'll find an implementation that has 100% RAM.
    – tofro
    Nov 2, 2023 at 8:54
  • 2
    I also started to write an answer, but took too long to write it. Basically yes the routines write all the memory, except for the parts it doesn't because the routines stop working after being slowly overwritten so they can't erase the parts that are left because there are no longer opcodes left to overwrite anything. And one of the routines has a pretty bold assumption that undefined opcode 00h is executed as a NOP so there goes that too.
    – Justme
    Nov 2, 2023 at 10:22
  • 1
    @justme On a 6309, which is largely compatible with the 6800, for example, the opcode $00 will negate the accumulator. Not a NOP, but doesn't hurt execution. $9D and $DD are, however, not a good idea for known reasons (HCF). Actually, some of the routines work pretty reliable even overwriting their own code completely if you assume all RAM and use wrap-around in both SP and PC.
    – tofro
    Nov 2, 2023 at 12:38
  • 4
    I must take my words back. All the code snippets manage to fully end up with the memory contents set to constant 01h, 00h, or FFh values by writing all the memory, except routine 1 does not write address 2004h which is already 01h and routine 3 does not write addresses FFFBh and FFFCh which are already FFh. The assumption that 00H is NOP instead of random invalid opcode must be made, but it could do anything.
    – Justme
    Nov 2, 2023 at 20:00
2

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .