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()

Storing and Transferring Between Registers

To my surprise, storing registers was a lot easier to implement then loading. Partially this was due to the simple fact that I was able to take advantage of the existing findAbsoluteAddress function, but the larger reason is that none of the storing commands have to worry about setting flags and the clock cycles for these commands are consistent.

The three commands for storing registers to memory are STA, STX, and STY. They simply take the value that was in the respective register and stores it in the indicated address which is determined by the address mode used.

The registers are fast since they are on the CPU. Older processors ran at similar speeds to their memory so the cost of memory access was significantly less back then. Today accessing memory that was not in the cash incurs cost of hundreds of cycles. Back then the cost of accessing memory was only a few cycles. Still, there is a slight time advantage of transferring data between memory in all but immediate mode and the register transfer instructions are all a single byte saving memory over the two byte immediate instructions.

Unlike storing from registers to memory, flags are affected by transferring between registers. As there are several instructions that need to determine if the number transferred is zero or negative and set the Z and N flags appropriately, a simple function handles this. For convenience, I have the function return the value being tested to allow it to be chained.

    fun setNumberFlags(num:Int):Int {

        adjustFlag (ZERO_FLAG, num == 0)

        adjustFlag (NEGATIVE_FLAG, (num and 128) > 0)

        return num

    }

There are commands for copying the contents of the accumulator to the x and the y registers (TAX and TAY) as well as from the x register or the y register to the accumulator (TXA, TYA). There is no instruction for transferring between the x and y registers.

Two remaining transfer instructions exist, which are tied to manipulating the stack. We will cover those as well as explain the concept behind the stack next time.

STA – STore Accumulator

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Zero Page	133	$85	2	3
Zero Page,X	149	$95	2	4
Absolute	128	$80	3	4
Absolute,X	144	$90	3	5
Absolute,Y	153	$99	3	5
(Indirect,X)	129	$81	2	6
(Indirect),Y	145	$91	2	6

Flags affected: None

Usage: Stores the contents of the accumulator to memory

Test Code:

; STA tests (all seven modes)

     LDA #123

     LDX #$10

     LDY #5

     STA $AB    ; zero page

     STA $AB,X

     STA $250

     STA $250,X

     STA $250,Y

     STA ($50,X)

     STA ($60),Y

.ORG $60

.WORD $600

;MAB, MBB, M250, M260, M255, M600, M605 = 123

Implementation:

// zero page

mem.write(mem.read(state.ip+1), state.acc)

// zero page,X

mem.write(mem.read(state.ip+1) + state.x, state.acc)

//absolute

m.mem.write(findAbsoluteAddress(m.state.ip), m.state.acc)

//absolute,X

m.mem.write(findAbsoluteAddress(m.state.ip)+m.state.x, m.state.acc)

//absolute,Y

m.mem.write(findAbsoluteAddress(m.state.ip)+m.state.y, m.state.acc)

// (indirect, X)

mem.write(findAbsoluteAddress(((mem.read(state.ip+1)+state.x) and 255)-1), state.acc)

// (indirect),Y

mem.write(findAbsoluteAddress(mem.read(state.ip+1) -1) + state.y, state.acc)

       

STX – STore X register

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Zero Page	134	$86	2	3
Zero Page,Y	150	$96	2	4
Absolute	142	$8E	3	4

Flags affected: None

Usage: Stores contents of X register to memory

Test Code:

     LDX #22

     LDY #5

     STX $50    ;  Zero Page

     STX $50,Y  ;  Zero Page,Y

     STX $250   ;  Absolute

     BRK

;M50, M55, M250 = 22

Implementation:

// zero page

mem.write(mem.read(state.ip+1), state.x)

// zero page,Y

mem.write(mem.read(state.ip+1) + state.y, state.x)

//absolute

mem.write(findAbsoluteAddress(state.ip), state.x)

STY  – STore Y Register

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Zero Page	132	$84	2	3
Zero Page,X	148	$94	2	4
Absolute	140	$8C	3	4

Flags affected: None

Usage: Stores the contents of the Y Register to memory

Test Code:

     LDX #5

     LDY #33

     STY $50    ;  Zero Page

     STY $50,X  ;  Zero Page,X

     STY $250   ;  Absolute

     BRK

;M50, M55, M250 = 33

Implementation:

// zero page

mem.write(mem.read(state.ip+1), state.y)

// zero page,X

mem.write(mem.read(state.ip+1) + state.x, state.y)

//absolute

mem.write(findAbsoluteAddress(state.ip), state.y)

TAX – Transfer Accumulator to X register

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Implied	170	$AA	1	2

Flags affected: NZ

Usage: Moves value in accumulator to X. Fast and small often used as part of restoring processor state.

Test Code:

; TYA TAX test

     LDY #24

     TYA

     TAX

     BRK

; Acc, X=24, N=0, Z=0

Implementation:

state.x = setNumberFlags(state.acc)

TAY – Transfer Accumulator to Y

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Implied	168	$A8	1	2

Flags affected: NZ

Usage: Moves value in accumulator to Y. Fast and small often used as part of restoring processor state.

Test Code:

; TXA TAY test

     LDX #179

     TXA

     TAY

     BRK

; Acc, Y=79, N=1, Z=0

Implementation:

state.y = setNumberFlags(state.acc)

Place implementation code here

TXA – Transfer X register to Accumulator

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Implied	138	$8A	1	2

Flags affected: NZ

Usage: Moves value in X to the accumulator. Fast and small often used as part of saving processor state.

Test Code:

; TXA TAY test

     LDX #179

     TXA

     TAY

     BRK

; Acc, Y=79, N=1, Z=0

Implementation:

state.acc = setNumberFlags(state.x)

TYA – Transfer Y register to Accumulator

Address Mode	Decimal OPCode	Hexadecimal OpCode	Size	Cycles
Implied	152	$98	1	2

Flags affected: NZ

Usage: Moves value in Y to accumulator. Fast and small often used as part of saving processor state.

Test Code:

; TYA TAX test

     LDY #24

     TYA

     TAX

     BRK

; Acc, X=24, N=0, Z=0

Implementation:

state.acc = setNumberFlags(state.y)