Stack Implementation

The Stack Implementation

Introduction

The inner-working of the stack depend on the program language used to implement the stack. The implementation will create the public functions used my a program to interact with the stack. It may also include other helper functions to make the implementation work. In addition, the implementation programmer will decide how to to store and access the data. Depending on the selected programming language, an array, linked-list, or some other data structure might be used

This page will explore an LC-3 Stack implementation

Public Function

Stack Data Declarations

In LC-3 there are only registers and memory to store data and manage the stack. This implementation will store all data and variables in memory

; -----------------------
; Stack Data Declarations
; -----------------------
    StackData   .BLKW #10   ; LIFO Data Storage
    StackEnd    .FILL xFFFF ; Negative Value
    StackPtr    .BLKW #1    ; Address of Current stack slot
    StackSize   .BLKW #1    ; Number of stack slots
    
    ; Register save area for all Stack operations
    StackSaveR4  .BLKW #1
    StackSaveR5  .BLKW #1
    StackSaveR6  .BLKW #1
    StackSaveR7  .BLKW #1

StackData is, in this implementation, a 10 memory slot storage. This is where the user program data will be stored

StackEnd is a location that defined the end of the Data section. The implementation will use this to check for the stack being full

StackPtr will contain the address within the StackData area that is the most recently pushed data element

StackSize will be set during implementation to represent how many slots the stack contains. In this can it will be set to 10

StackSaveR4 - StackSaveR7 as created for the various stack functions to share when saving and restoring registers

Initialize

It is likely some internal variables and states will need to be setup before a user program can start pushing and popping data. That will be done when the user program first starts using the stack. In a high-level programming language, this will be completed in the constructor, when the user creates a new stack

In LC-3, the user code will need to call the Init subroutine before using it

; Initializes the stack data block to zero (0) in each slot
; Sets StackPtr and StackSize for use by subroutines
;   Inputs:     none
;   Outputs:    No registers. StackPtr and StackSize are set
InitStack
    ST R4, StackSaveR4
    ST R5, StackSaveR5
    ST R6, StackSaveR6
    
    LEA R5, StackData   ; Top of the stack
    LEA R6, StackEnd    ; Bottom of stack

    ST R5, StackPtr     ; Calculate and store stack pointer
    ; Calculate and store stack size
    NOT R5, R5
    ADD R5, R5, #1
    ADD R6, R6, R5
    ST R6, StackSize
    
    AND R4, R4, #0      ;Value to init each slot to
    LD R5, StackPtr
    ClearLoop
        STR R4, R5, #0
        ADD R5, R5, #1  ; Move to next slot
        ADD R6, R6, #-1 ; Decrement loop counter
        BRp ClearLoop
    
    LD R4, StackSaveR4
    LD R5, StackSaveR5
    LD R6, StackSaveR6

RET

Addressed of StackData and StackEnd are loaded and used to calculate the stack size. The result is saved in StackSize at line 18

Line 13 sets the StackPrt to the first slot in the stack

Lines 22 - 26 loop through all slots in in the stack and set them to zero (0). This and resetting StackPtr are a good idea in case the user code wants to reset the stack after using it. Simply calling Init again will reset the stack for reuse

Push

When the user code calls *Push, the stack must do two (3) things. First checks that the stack is not already full. If there is room, it saves the pushed data in the next slot in the stack. Finally, it updated the StackPtr to the next slot so it is ready for another push call later

; Sets value in R0 to current stack slot. Advances StackPtr
;   Inputs: R0 contains value to place in Stack
;   Outputs: None
Push
    ST R5, StackSaveR5
    ST R6, StackSaveR6
    
    ;Check to see if Stack is full - ADDR[StackEnd] - StackPtr === 0
    LD R5, StackPtr     ; Address of current open stack slot
    LEA R6, StackEnd    ; Bottom of stack
    
    NOT R6, R6          ; Flip sign on R6 for 'subtraction'
    ADD R6, R6, #1
    
    ADD R6, R5, R6      ; StackPtr - ADDR[StackEnd]
    BRz PushExitEarly   ; Stack full, bail
    
    STR R0, R5, #0      ; Write value to Stack
    
    ; Advance StackPtr
    ADD R5, R5, #1
    ST R5, StackPtr
    
    PushExitEarly
    
    LD R5, StackSaveR5
    LD R6, StackSaveR6

RET

The current StackPrt is compared to the StackEnd if they are the same, that indicates that the stack is full

Basically, the StackPtr that was updated after the previous push was changed to the memory location pasted the last memory slot. This is not checked until the user code tried to push an 11th item onto the stack

Line 18 saved the user code's data (placed in R0 before calling Push) is copied into the currently open slot (StackPtr)

Lines 21-22 update the StackPrt to then next open slot and save it for next time

Pop

; Gets next value from Stack, Pulls StackPtr back 1 slot
;   Input: none
;   Output: R0 contains the value popped from the stack
Pop
  ST R5, StackSaveR5
  ST R7, StackSaveR7

  LD R5, StackPtr
  ADD R5, R5, #-1 ; Move pointer back to the last pushed slot
          
  LDR R0, R5, #0  ; Get value from last pushed slot

  ST R5, StackPtr ; write new StackPtr out for next time

  LD R5, StackSaveR5
  LD R7, StackSaveR7

RET

Lines 8-9 get the StackPtr and move it back one slot. Recall the StartPtr always refers to the then next open slot. To access the last pushed slot, it needs to be moved back 1 slot

Line 11 retrieves the data an the last updated slot. The value us stored in R0 according to the subroutine's header output note

Line 13 saves the updated StackPtr since it now points to the newly available slot

Was the value just popped actually deleted?

This implementation chose to not spend any extra instruction cycles clearing (zeroing out) stack memory slots after they are popped

As long as the StackPtr is updated correctly, it is unnecessary. Next time Push is called, the new value will over-write the stale data left behind from the previous Pop

This is typically ok for standard stack operations. However, stale data can be useful to hackers if it is some important data, like a password

If this stack had a requirement to be extra secure, zeroing out popped data would be needed in this implementation

Conclusion