Module | TatungBytes

Why this matters

You have been using the stack since S3 without being told.

Every RET you have written found its way back somewhere. Every CALL in S7 and S11 remembered where it came from. None of that is magic, and none of it is free - it uses a region of memory that you also have to share, and which is smaller than you would guess.

This section is about what is actually happening, and what it costs.

What the stack is

A region of memory the processor uses as a scratch pad, with one rule: the last thing put on is the first thing taken off. Put three values on, take them off, and they come back in reverse order.

It has a register of its own - SP, the stack pointer - which holds the address of the top of the stack. And it grows downward: each new value goes at a lower address than the last, and SP decreases as the stack fills.

When your program starts, SP is FCED.

What CALL actually does

CALL sub does three things:

Work out the address of the instruction after the CALL - that is where it needs to come back to.
Put that address on the stack: subtract 1 from SP and store the high byte there, then subtract 1 again and store the low byte.
Jump to sub.

Note the order in step 2. SP moves first, then the byte is written. That is why the return address ends up sitting exactly at the address SP points to, and why nothing above SP is disturbed.

RET undoes it: read the low byte from (SP) and add 1 to SP, read the high byte and add 1 again, then jump to the address it just assembled.

You can watch this. This program reads the word at (SP) from inside a subroutine:

        ORG 256

        CALL sub
here:   LD BC,0
        RET

sub:    LD HL,0
        ADD HL,SP       ; HL = SP inside the subroutine
        LD E,(HL)
        INC HL
        LD D,(HL)       ; DE = the word sitting at (SP)
        RET

DE comes back as 0103. Assemble it with -l and you will find that 0103 is the address of here: - the instruction after the CALL. The return address is right there where SP points, waiting for RET to collect it.

ADD HL,SP is the trick for getting at SP, since you cannot read it directly: zero HL, add SP to it, and read it out of HL.

Nested calls

Because each return address goes on the stack in turn, a subroutine can call another, which can call another. Each RET takes off the most recent address, which is the right one.

That is the whole reason the stack exists, and it is why you must leave it as you found it. Anything you put on and forget to take off will be collected by the next RET and used as an address - and your program will jump to it.

PUSH and POP

You can use the stack yourself. PUSH puts a register pair on, POP takes one off:

        PUSH HL         ; save HL
        LD HL,0         ; use HL for something else
        POP HL          ; get the original back

It works with AF, BC, DE, HL, IX and IY. Not SP - that would make no sense, and the assembler rejects it.

A complete program:

        ORG 256

        LD HL,9         ; a value worth keeping
        PUSH HL         ; put it somewhere safe

        LD HL,0         ; scribble on HL

        POP HL          ; get it back

        LD A,L          ; the low byte - 9
        ADD A,48        ; make it the character '9'
        RST 8
        DEFB 158        ; ZOUTC

        RET

What you should see

>9

PUSH AF is worth knowing about: it saves A and the flags together, which is how you protect a comparison result across some other work.

Protecting registers in a subroutine

Here is what this is really for.

S8 showed that the keyboard scan destroys BC, DE and HL. That is a nuisance when you call it from a loop that was using them. The same problem applies to your subroutines: a routine that helpfully clobbers HL is a routine nobody can call safely.

The fix is for the subroutine to put back what it borrows:

        ORG 256

        LD HL,1234h     ; something the caller cares about
        CALL drawtile
        RET             ; HL is still 1234h here

; uses HL and DE, and gives them back
drawtile:
        PUSH HL         ; save what we are about to break
        PUSH DE

        LD HL,0         ; ... the actual work ...
        LD DE,0

        POP DE          ; give them back - reverse order
        POP HL
        RET

Pop in the reverse order you pushed. Last in, first out: HL then DE going on, DE then HL coming off. Get that backwards and the two values swap, which is a bug that runs perfectly and produces nonsense.

Note where drawtile sits - after the main program's RET. Put a subroutine where execution can wander into it and it runs twice, which S7 covered.

A subroutine that protects the registers it uses can be called from anywhere without the caller having to know or care what it does inside. That is worth the four extra bytes almost every time.

How much stack you have

Not much. This is the part worth taking seriously.

SP starts at FCED, and below it is memory the machine is using for its own purposes. Push far enough and you overwrite it.

100 bytes of stack works fine.
176 bytes resets the machine. Not a crash you can recover from - the Einstein restarts as though you had switched it off.

So your working budget is somewhere under 176 bytes, and there is no warning as you approach it. In practice that is plenty: each CALL costs 2 bytes, each PUSH costs 2, and even deeply nested code rarely goes past a couple of dozen levels.

What it will not survive is a leak. A subroutine that pushes and forgets to pop costs two bytes every time it is called. Called once a frame, fifty times a second, that is 100 bytes a second - and a reset within two seconds.

Every PUSH needs its POP, on every path out of the routine. That last part matters: a routine with a conditional RET in the middle needs the pops before that return too, not just before the one at the bottom.

Change one thing

In the register-protecting program, swap POP DE and POP HL. Check HL in the register line. What is in it, and where did it come from?
Delete POP HL entirely and run it. PC in the register line will tell you where RET sent the program. Compare it with what you pushed.
Change the push-and-print program to PUSH AF and POP AF around the LD HL,0. Does it still print 9? Why is that a different thing to protect?
Put PUSH HL inside a loop that runs twenty times, with no matching POP. Count the bytes and predict whether it survives before you run it.
In the (SP) program, add a second CALL inside sub to another subroutine and read (SP) at the deepest level. Which return address do you get, and where is the other one?

Exercises

12.1 - Watch it move. Write a program that records SP at the start, calls a subroutine that records SP again, and returns. Report both. Then add a PUSH inside the subroutine and see what changes.

12.2 - A safe subroutine. Write a routine that uses HL, DE and AF and gives all three back untouched. Prove it by loading known values before the call and reading them off the register line after.

12.3 - Wrong order on purpose. Take 12.2 and pop two of the pairs in the wrong order. Predict both values before you run it.

12.4 - Find the wall. The stack survives 100 bytes and resets at 176. Narrow it down. Start with 128 and bisect, and keep a note of each result - you are mapping something nobody wrote down.

12.5 - Protect a call you did not write. S8's keyboard scan destroys BC, DE and HL. Write a wrapper subroutine around it that returns the key in A and leaves everything else exactly as it found it. Then use it in a counted loop that keeps its counter in C - which is impossible without the wrapper.

When it goes wrong

What you see	What it means
The machine resets	Very likely a stack leak - a `PUSH` without a `POP`, probably inside a loop. Count the pushes on every path through your routine.
`PC` in the register line is an address nowhere in your program	`RET` collected something off the stack that was not a return address.
Two values have swapped	Popped in the same order you pushed instead of the reverse.
A subroutine works alone but breaks its caller	It clobbers a register the caller was using. Push what you borrow.
The routine runs twice	Execution fell into it from above. Move it below the main `RET`.

Summary

The stack is memory the processor uses last-in-first-out, tracked by SP, and it grows downward from FCED.
CALL moves SP down two and stores the return address there, so the address sits at (SP). RET reads it back and moves SP up two.
PUSH and POP work with AF, BC, DE, HL, IX and IY. Pop in the reverse order you pushed.
A subroutine that protects the registers it uses can be called from anywhere. That is worth a few bytes almost always.
You have well under 176 bytes. 100 works, 176 resets the machine. Every PUSH needs its POP on every path out, or a loop will exhaust it in seconds.

S13. Arrays and lookup tables. A string was bytes in a row. So is a list of numbers - and once you can index into one, you can replace whole chains of decisions with a table of answers, which is how most of a game's data works.

← Previous Next →

The stack