Chapter 10 - The stack. The main contents of the dissertation consist of three main parts: Stack data structure, interrupt I/O (again!), arithmetic using a stack. | Chapter 10 The Stack Stack data structure Interrupt I/O (again!) Arithmetic using a stack Stack Data Structure Abstract Data Structures are defined simply by the rules for inserting and extracting data The rule for a Stack is LIFO (Last In - First Out) Operations: Push (enter item at top of stack) Pop (remove item from top of stack) Error conditions: Underflow (trying to pop from empty stack) Overflow (trying to push onto full stack) We just have to keep track of the address of top of stack (TOS) 10 - A “physical” stack A coin holder as a stack 10 - A hardware stack Implemented in hardware (. registers) Previous data entries move up to accommodate each new data entry Note that the Top Of Stack is always in the same place. 10 - A software stack Implemented in memory The Top Of Stack moves as new data is entered Here R6 is the TOS register, a pointer to the Top Of Stack 10 - Push & Pop Push Decrement TOS pointer (our stack is moving down) then write data in R0 to new TOS Pop Read data at current TOS into R0 then increment TOS pointer PUSH ADD R6, R6, # -1 STR R0, R6, # 0 POP LDR R0, R6, # 0 ADD R6, R6, # 1 10 - Push & Pop (cont.) What if stack is already full or empty? Before pushing, we have to test for overflow Before popping, we have to test for underflow In both cases, we use R5 to report success or failure 10 - PUSH & POP in LC-3 POP ST R2, Sv2 ;save, needed by POP ST R1, Sv1 ;save, needed by POP LD R1, BASE ;BASE contains x-3FFF ADD R1, R1, # -1 ;R1 now has x-4000 ADD R2, R6, R1 ;Compare SP to x4000 BRz fail_exit ;Branch if stack is empty LDR R0, R6, # 0 ;The actual ‘pop’ ADD R6, R6, # 1 ;Adjust stack pointer BRnzp success_exit 10 - PUSH & POP in LC-3 (cont.) PUSH ST R2, Sv2 ;needed by PUSH ST R1, Sv1 ;needed by PUSH LD R1, MAX ;MAX has x-3FFB ADD R2, R6, R1 ;Compare SP to x4004 BRz fail_exit ;Branch is stack is full ADD R6, R6, # -1 ;Adjust Stack Pointer STR R0, R6, # 0 ;The actual ‘push’ 10 - PUSH & POP in LC-2 (cont.) . | Chapter 10 The Stack Stack data structure Interrupt I/O (again!) Arithmetic using a stack Stack Data Structure Abstract Data Structures are defined simply by the rules for inserting and extracting data The rule for a Stack is LIFO (Last In - First Out) Operations: Push (enter item at top of stack) Pop (remove item from top of stack) Error conditions: Underflow (trying to pop from empty stack) Overflow (trying to push onto full stack) We just have to keep track of the address of top of stack (TOS) 10 - A “physical” stack A coin holder as a stack 10 - A hardware stack Implemented in hardware (. registers) Previous data entries move up to accommodate each new data entry Note that the Top Of Stack is always in the same place. 10 - A software stack Implemented in memory The Top Of Stack moves as new data is entered Here R6 is the TOS register, a pointer to the Top Of Stack 10 - Push & Pop Push Decrement TOS pointer (our stack is moving down) then write data in R0 to new
