NCL 402: Indexed Data

In the previous lesson, we used PUSH and POP to temporarily store values on the value stack.

PUSH 10
PUSH 20
PUSH 30

POP r0
POP r1
POP r2

We learned that the stack is last in, first out: the most recently pushed value is the first one popped.

For that to work, the processor needs to keep track of where the next value belongs.

NCL lets us see — and change — that position ourselves.

The Stack Pointer

The special integer register sp is the stack pointer.

It starts at 0 and points to the next available position on the value stack.

As values are pushed, sp moves forward. As values are popped, it moves backward.

Our example from the previous lesson looks like this:

Instruction	Value stack	sp
Start	empty	0
PUSH 10	10	1
PUSH 20	10, 20	2
PUSH 30	10, 20, 30	3
POP r0	10, 20	2
POP r1	10	1
POP r2	empty	0

Notice that sp does not point directly at the value on top of the stack.

It points to the position where the next value would go.

When the stack contains three values, sp is 3. Those values occupy positions 0, 1, and 2, leaving position 3 available for the next one.

The value stack contains 128 positions, numbered 0 through 127. Because sp points to the next available position, its valid range is 0 through 128.

When sp is 128, all 128 positions are in use.

The Stack Value

NCL provides another special register named sv.

sv represents the value immediately before sp:

stack[sp - 1]

In other words, sv is the value currently on top of the stack.

sp	sv refers to
1	stack[0]
2	stack[1]
3	stack[2]
...	...
128	stack[127]

A useful way to remember the two registers is:

sp says where. sv says what is there.

Both registers are readable and writable.

For example:

MOVE r0 sp

copies the current stack pointer into r0.

And:

MOVE r0 sv

copies the value on top of the stack into r0 without removing it.

Because sv is writable, we can also change that value directly:

MOVE sv 42

This replaces the value on top of the stack with 42.

When sp is 0, the stack is empty and there is no value for sv to represent. Reading or writing sv in this state causes a fatal STACK_ERROR.

Building PUSH

Now that we can access sp and sv directly, we can construct the behavior of PUSH ourselves.

Suppose we want to push #value.

First, move the stack pointer forward:

INC sp

The new position immediately before sp is now the top of the stack.

Then write the value there:

MOVE sv #value

Together:

INC sp
MOVE sv #value

This produces the same stack change as:

PUSH #value

PUSH gives this useful operation a direct instruction.

Building POP

We can construct POP in the same way.

First, read the current top value:

MOVE #value sv

Then move the stack pointer backward:

DEC sp

Together:

MOVE #value sv
DEC sp

This produces the same stack change as:

POP #value

The order matters.

When pushing, we move sp before writing sv, so sv refers to the newly added position.

When popping, we read sv before moving sp, while it still refers to the value being removed.

Normally, there is no reason to replace PUSH and POP with these longer versions. The direct instructions are shorter and make their purpose immediately clear.

But now we can see the machinery they operate.

More importantly, we are not limited to moving sp one position at a time.

Selecting a Stack Position

Because sp is writable, we can choose which stack position sv refers to.

For example:

MOVE sp 65
MOVE sv 42

When sp is 65, sv refers to:

stack[64]

We have written 42 directly into stack position 64.

We can read it again the same way:

MOVE sp 65
MOVE r0 sv

Now r0 contains 42.

This gives us something PUSH and POP cannot do directly: we can choose a particular position in the value stack without adding or removing all the values before it.

Borrowing sp

There is a problem with the previous example.

We changed sp.

If the program was already using PUSH and POP, those instructions now see 65 as the current stack pointer.

Usually, we only want to borrow sp long enough to access a particular position.

We can save its current value first:

MOVE r31 sp

Then use it:

MOVE sp 65
MOVE r0 sv

And restore it when we're finished:

MOVE sp r31

Together:

MOVE r31 sp

MOVE sp 65
MOVE r0 sv

MOVE sp r31

The stack pointer ends with the same value it had before, but we were able to read position 64 while we borrowed it.

This gives us an important habit:

When borrowing sp for direct stack access, save it first and restore it when you're finished.

Indexed Data

Selecting a fixed position is useful, but the position does not need to be fixed.

Suppose we store several related values beginning at stack position 64.

Because sv accesses the position immediately before sp, the first value is selected by sp = 65.

Index	sp	Selected position
0	65	stack[64]
1	66	stack[65]
2	67	stack[66]
3	68	stack[67]
...	...	...
63	128	stack[127]

If an index is stored in a register, we can calculate the required value of sp:

#base 65
#index r0
#value r1

MOVE r31 sp

ADD sp #base #index
MOVE #value sv

MOVE sp r31

If #index is 0, sp becomes 65 and we read stack[64].

If #index is 1, sp becomes 66 and we read stack[65].

If #index is 2, we read stack[66].

The index can come from a calculation, user input, a loop, or anywhere else.

The program can therefore choose which value it wants while it is running.

This is indexed data.

Writing Indexed Data

The same calculation can select a position to write.

#base 65
#index r0
#value r1

MOVE r31 sp

ADD sp #base #index
MOVE sv #value

MOVE sp r31

Only the direction of the final MOVE changed.

To read:

MOVE #value sv

To write:

MOVE sv #value

The index determines which position is selected in either case.

A Small Collection

Let's store four values in positions 64 through 67.

#base 65
#index r0
#value r1

MOVE r31 sp

MOVE sp 65
MOVE sv 12
INC sp
MOVE sv 27
INC sp
MOVE sv 8
INC sp
MOVE sv 31

MOVE sp r31

The stack now contains:

Index	Stack position	Value
0	64	12
1	65	27
2	66	8
3	67	31

We can choose one of those values using an index:

MOVE #index 2

MOVE r31 sp
ADD sp #base #index
MOVE #value sv
MOVE sp r31

D.TXT #value
D.BLT

The display shows:

8

Change #index to 0, 1, or 3, and the same instructions select a different value.

The data stays in the same place.

Only the index changes.

Try it

The following code stores four values beginning at stack position 64:

#base 65
#index r0
#value r1

MOVE r31 sp

MOVE sp 65
MOVE sv 12
INC sp
MOVE sv 27
INC sp
MOVE sv 8
INC sp
MOVE sv 31

MOVE sp r31

Write a loop that displays all four values in order:

12 27 8 31

Use #index to select each value rather than writing four separate reads.

Remember to save sp before borrowing it and restore it when you're finished.

---

The value stack isn't the only stack we've already been using.

In the next lesson, NCL 403: The Call Stack, we'll return to CALL and RET and look at how the processor remembers where a subroutine should return.