# 6502 FORTH, Part 3: 16 Bit Stack

** Published:**

In my previous post, I created my first Forth words: `next`

, `exit`

, and `dolist`

. I was about to continue on to creating some simple arithmetic words, but then I realized my program is missing the main data structure of Forth…the internal data stack. This is a 16-bit implementation, so I’ll need a 16-bit stack. This of course is not included in the default 65c02 system, so I had to write one myself.

## Stack Architecture

This implementation is largely based on Paul Dourish’s code, though I changed some of the implementations slightly.

All of the 6502’s registers are 8-bit except for its address bus. The memory map for the stack will look like the following:

```
$00FF <- Bottom of stack
$00FE
$00FD Stack will grow downward
.
. <- x register points to current top
.
$0082 <- Top possible address of stack
$0081
$0080 <- 2 bytes of extra space for storing temp values
```

The stack occupies the top half of the zero page, and grows downward towards `$0080`

. The final two bytes, `$0080-81`

, are reserved for temporary values (for reasons that will soon become clear). The `x`

register will hold the top of the stack, beginning at `$FF`

. We can increase the size of the stack by decrementing `x`

(`dex`

), and decrease the size of the stack by incrementing `x`

(`inx`

). We’ll have to implement the classic `push`

and `pop`

operations, but we’re also going to implement `dup`

(duplicate the top element), `add`

and `sub`

(add/subtract top elements, storing result as new top), and `swap`

(swap top two elements of stack).

The stack is initialized as follows:

`stackaccess`

will store our temporary values, and the `x`

register is initialized to `$FF`

for the top of the stack. `initstack`

will be called at the beginning of our program execution. Now we can get to creating the individual methods!

## Push/Pop/Duplicate

Push and pop are fairly straightforward, we just have to take care to preserve endianness for indirect addressing in other parts of our program. Our stack is growing downward, so we’ll start by pushing the LSB first, then the MSB (to ensure the least significant byte is stored at the smallest address). This value will be pulled from `stackaccess`

, our temp value. Let’s look at pushing the value `$ABCD`

:

```
0. Initial State
| $0080 | $0081 | x | (x) |
$CD $AB $90 ?
1. Push MSB to x
| $0080 | $0081 | x | (x) |
$CD $AB $90 $AB
2. Decrement x
| $0080 | $0081 | x | (x) | (x-1) |
$CD $AB $89 ? $AB
3. Push LSB to x
| $0080 | $0081 | x | (x) | (x-1) |
$CD $AB $89 $CD $AB
4. Decrement x
| $0080 | $0081 | x | (x) | (x-1) |
$CD $AB $88 ? $CD
Stack Layout:
$FF: some data
.
.
.
$90: $AB
$89: $CD
$88: <- x
```

Notice now how indirect indexing on `$89`

will correctly read out the address `$ABCD`

. The operation for `pop`

is just this in reverse–we’ll store the returned value in `stackaccess`

. Putting it into code:

Duplicate is very similar to `push`

, except we get the value from the top of the stack rather than from `stackaccess`

. The previous value is the two bytes above `x`

(`x+1,x+2`

), so we just copy and increment `x`

appropriately.

## Swap

Swap is a little trickier since we have to use a temporary variable. The basic flow of swap is the following:

```
Trying to swap top two values A,B
1. Copy A into stackaccess
2. Copy B onto A
3. Copy stackaccess onto B
```

Remember that our stack grows from top to bottom, and `x`

always points to the next *free* byte of memory. Thus, the value A from this example is stored at `x+1,x+2`

, and the value B is stored at `x+3,x+4`

.

## Add/Subtract

Now we just need two more instructions, and we’ll have a fully functioning Forth stack! These two commands are also very similar, and just implement simple 16-bit arithmetic. For addition, the flow looks like this:

```
x=$F0
# Adding $0405 + $0A10
$F4: $04
$F3: $05
$F2: $10
$F1: $0A
# Start with LSB, overwrite second value's LSB
# $05 + $10 = $15, no carry
$F4: $04
$F3: $15
$F2: $10
$F1: $0A
# Add MSB, overwrite second value's MSB
$ $0A + $10 = $1A, no carry
$F4: $1A
$F3: $15
$F2: $10
$F1: $0A
# increment x by two to 'pop' top value
x=$F2
```

The only trick to watch out for here is making sure the carry bit is set correctly–we have to be sure to clear the carry bit for addition, and set it for subtraction.

## Testing It Out

With this code written, we can get some test examples running just to test the stack functionality.

`pushtest1`

and `pushtest2`

push `$ABCD`

and `$0001`

to the stack (resp.), and `pushzero`

zeros out the value of `stackaccess`

(so we can verify we’ve actually popped a value and not just preserved the same value from `push16`

). These methods can be (un)commented as necessary, but the flow as written does the following:

```
0. initialize stack
1. push $ABCD to stack
2. push $0001 to stack
3. reset stackaccess to $0000
4. add the top two values
5. duplicate the top value
6. pop the top value
```

At the end of the program execution, the addresses `$0080-81`

and `$00FE-FF`

should be set to the value `$ABCE`

, since this corresponds to `$ABCD + $0001`

. Additionally, the `x`

register should be set to `$00FD`

, since we’ll have just popped the top value of the stack (leaving one entry on the stack). Since we’re storing everything little-endian, the smallest memory address should have the least significant bits, meaning that `$0080`

will have `$CE`

and `$0081`

will have `$AB`

. If we run this in `symon`

, we get the following:

This looks like what we want to see! Note that `$00FC-FD`

is also set to `$ABCE`

–this is correct, since when we pop values we don’t clear the previous memory (we just modify `x`

). The `x`

register correctly points to the next free value of stack memory at `$00FD`

, so we don’t have to worry about the persisting values. I also tested the other functions using this code, but I’m omitting screenshots for brevity.

## Next Steps

That’s all I need for a fully functioning stack! Now I have somewhere to put data, so I can write some words that store to and pull from the stack. Stay tuned for my next post, in which I plan to start testing the main FORTH code. I’m sure I’ll discover some bugs in these codes then, but that’ll be future me’s problem. As always, you can check my complete code repository on Github.