The Stack

Due to being accepted into a Master of Science in Computer Science program I will be shifting to posting updates every other week. This will be alternating between my Blazing Games Development blog and  this blog so I will start posting this blog on Saturday. The next post will be May 12th. I have a lot of material already in the queue and am going to be blocking out time for working on this so hopefully this blog will continue to run smoothly while I am at university.

The stack is a powerful yet simple to implement data storage structure. They work like a stack of books. You push a book onto the stack which causes it to grow and pull a book off the top of the stack. This means that the last thing put onto the stack is the first thing that is retrieved from the stack. This is very handy for calling functions as you can push data onto the stack before calling the function then retrieve it back when you return. As the last items pushed are the first to be pulled, this allows for the function called to call other functions without any worry. It even allows for recursion but with only 256 bytes of stack the level of recursion is very limited.

The stack is one of the easier algorithms to implement. The 6502 implements the stack as a reverse array with the stack starting at the top of the page it is assigned to and working down. Normally the stack is on page 1, but the 2600 has it set up on page 0.

The push operations on a stack, which is used by PHA and PHP as well as the JSR method. This is handled by putting the value as a byte onto to the address pointed to by the currently assigned stack page with the stack pointer added to it. The stack pointer then is reduced by one, wrapping if it becomes less than zero.

    fun pushByteOnStack(num:Int) {

        val stackAddress = stackPage * 256 + state.sp

        state.sp = (state.sp - 1) and 255

        mem.write(stackAddress, num)

    }

 Pull operations work the opposite as pull and simply increase the stack pointer then returns the value located at that location in memory. Stack pulls can adjust flags so if the adjustFlags option is set it will call the setNumberFlags function to set the zero and negative flags appropriately.

    fun pullByteFromStack(adjustFlags:Boolean = false):Int {

        state.sp = (state.sp +1) and 255

        val num = mem.read(stackPage * 256 + state.sp)

        if (adjustFlags)

            setNumberFlags(num)

        return num

    }

The stack pointer index is set using TXS which transfers the value in the x register into the stack pointer register. TSX puts the pointer into the X register. This allows you to adjust the x register and peek into values stored in the stack.

Pushing and pulling bytes is done using the PHA and PLA commands. The flags can be stored onto the stack using PHP with PLP retrieving the flags from the stack.

TSX – Transfer Stack pointer to X Register

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Implied	186	$BA	1	2

Flags affected: NZ

Usage: Moves the current stack pointer to the X register, which can be used to investigate the stack to find information passed on the stack.

Test Code:

; TSX and TXS

     LDX #128

     TXS

     LDX #0

     TSX

     BRK

; X, SP = 128

Implementation:

state.x = setNumberFlags(state.sp)

TXS – Transfer X register to Stack pointer

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Implied	154	$9A	1	2

Flags affected: None

Usage: Copies value of X Register into the Stack pointer. Used for setting up the stack or reserving space on the stack.

Test Code:

; TSX and TXS

     LDX #128

     TXS

     LDX #0

     TSX

     BRK

; X, SP = 128

Implementation:

state.sp = state.x

PHA – PusH Accumulator onto stack

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Implied	72	$48	1	3

Flags affected: None

Usage: Pushes contents of accumulator onto stack. Use to preserve what was in the accumulator such as when you are entering a function or handling and interrupt.

Test Code:

; Stack Pushing test

     LDX #255

     TXS

     LDA #11

     SED

     LDY #0     ; set zero flag so flag register should now be 42

     PHP

     PHA

; sp = 253, M1FE=11 M1FF=42

Implementation:

writeByteToStack(state.acc)

PHP – PusH Processor status on Stack

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Implied	8	$08	1	3

Flags affected: None

Usage: Stores the state of the flags on the stack.

Test Code:

; Stack Pushing test

     LDX #255

     TXS

     LDA #11

     SED

     LDY #0     ; set zero flag so flag register should now be 42

     PHP

     PHA

; sp = 253, M1FE=11 M1FF=42

Implementation:

writeByteToStack(state.flags)

PLA – PuLl Accumulator from stack

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Implied	104	$68	1	4

Flags affected: NZ

Usage: Recovers bytes pushed to the stack.

Test Code:

; Stack popping test

     PLA

     PLP

     BRK

.ORG $1FE

.BYTE 11 42

; sp = 253, M1FE=11 M1FF=42

Implementation:

state.acc = pullByteFromStack(true)

PLP  – PuLl Processor status from stack

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Implied	40	$28	1	4

Flags affected: CDINVZ

Usage: Restores the state of the flags that were pushed onto the stack with PHP.

Test Code:

; Stack popping test

     PLA

     PLP

     BRK

.ORG $1FE

.BYTE 11 42

; sp = 253, M1FE=11 M1FF=42

Implementation:

state.flags = pullByteFromStack()