Abstract Data types or more colloquially data stuructures, are the complex items of information.
Subroutines
libraries the collections of some fragments available to user programmer
Such program fragments are called subroutines, or alternatively, procedures, or in C terminology, functions.
Call / Return Mechanism
We uses the call/return mechanism to direct the computer each time via the call instruction to the code A, and after the computer execute the code A, to the return instruction to the proper next instruction to be executed in the program.
caller the program that contains the call
callee the subroutine that contains the return
JSR / JSRR
for Jump to SubRoutine Opcode
Operand
Specification digit of addressing mode
- JSR PC-relative if its value is
1,
the second operand is obtained by sign-extending bitsto 16 bits.
- JSRR Base Register if its value is
0,
the second operands is the value in SR2 specified by bits.
must be
0.FUNTION
Condition Codes ✗
RET
Opcode
Operand
must be
000 111 000000FUNTION
Condition Codes ✗
Saving and Restoring Registers
If a value in a register will be needed after someting else is stored in that register, we must save it before something else happens and restore it before it can be subsequently used.
A register value is saved by storing it in memory, and is restored by loading it back into the register.
callee save the save/restore problem is handled by the callee.
caller save the save/restore problem is handled by the caller. e.g. R7
The Stack
Property / Stack Protocol
The last thing stored in the stack is the first thing to remove.
Simply put : Last In, First Out, or LIFO.
Implementaion
stack pointer, sp
It keeps track of the top of the stack. In LC-3, R6 is the stack pointer. Note the values inserted into the stack are stored in memory locations having decreasing addresses. We say the stack grows toward zero.
Push
push a value onto the stack. overflow we can’t push values where there is no space. R5 is used to indicatie success ( R5 = 0 ) or failure ( R5 = 1 ) information.
; push the value in R0 onto the stack.PUSH ST R1, PUSH_SAVE1LD R1, STACK_MAXNOT R1, R1ADD R1, R1, #1ADD R1, R1, R6BRz OVERFLOWADD R6, R6, #-1STR R0, R6, #0AND R5, R5, #0LD R1, PUSH_SAVE1RETOVERFLOW AND R5, R5, #0ADD R5, R5, #1LD R1, PUSH_SAVE1RETSTACK_MAX .FILL ADDR ; the topmost address of stackPUSH_SAVE1 .BLKW #1
Pop
pop a value from the stack. underflow we can’t pop values when the stack is empty. R5 is used to indicatie success ( R5 = 0 ) or failure ( R5 = 1 ) information.
; Lazy Pop, without delete the element; pop the value from the stack into R0.POP LD R0, STACK_BASENOT R0, R0ADD R0, R0, #1ADD R0, R0, R6BRz UNDERFLOWLDR R0, R6, #0ADD R6, R6, #1AND R5, R5, #0RETUNDERFLOW AND R5, R5, #0ADD R5, R5, #1RETSTACK_BASE .FILL ADDR ; the bottommost address of the stack
Recursion
Recursion is a mechanism for expressing a function in terms of itself.
Stack is used to implement the recursion. It stores the return linkage R7, the values used to solve the problem, and the other values concerning the save/restore problem.
Example : Factorial
; Suppose we have MUL instruction.FACT ADD R6, R6, #-1STR R1, R6, #0 ; Push caller's R1ADD R1, R0, #-1BRz BASE_CASE ; n = 1 is the base case.ADD R6, R6, #-1STR R7, R6, #0 ; Push return linkageADD R6, R6, #-1STR R0, R6, R0 ; Push nADD R0, R0, #-1JSR FACTLDR R1, R6, #0ADD R6, R6, #1 : Pop nMUL R0, R0, R1 ; R0 <- n * (n - 1)!LDR R7, R6, #0ADD R6, R6, #1 ; Pop return linkageBASE_CASE LDR R1, R6, #0ADD R6, R6, #1 ; Pop caller's R1RET
The Queue
Property
Implementation
FRONT pointer & REAR pointer
In LC-3, R3 is the FRONT pointer and R4 is the REAR pointer.
Remove from Front & Insert at Rear
Considering wrap around, underflow and overflow. R5 is used to indicatie success ( R5 = 0 ) or failure ( R5 = 1 ) information.
; don't consider queue initiation!INSERT ST R1, QUQUE_SAVE1AND R5, R5, #0LD R1, NEG_LASTADD R1, R1, R4BRnp INSERT_SKIP_1LD R4, FIRST ; Wrap around, R4 <- FIRSTBRnzp INSERT_SKIP_2INSERT_SKIP_1 ADD R4, R4, #1 ; No wrap around, R4 <- R4 + 1INSERT_SKIP_2 NOT R1, R4ADD R1, R1, #1 ; R1 = - REARADD R1, R1, R3 ; R1 <- FRONT - REARBRz OVERFLOWSTR R0, R4, #0 ; Do the insertBRnzp INSERT_DONEOVERFLOW LD R1, NEG_FIRSTADD R1, R1, R4BRnp INSERT_SKIP_3LD R4, LAST ; Wrap around, R4 <- LASTBRnzp INSERT_SKIP_4INSERT_SKIP_3 ADD R4, R4, #-1 ; No wrap around, R4 <- R4 - 1INSERT_SKIP_4 ADD R5, R5, #1INSERT_DONE LD R1, QUEUE_SAVE1RETREMOVE ST R1, QUQUE_SAVE1AND R5, R5, #0NOT R1, R4ADD R1, R1, #1 ; R1 = - REARADD R1, R1, R3 ; R1 = FRONT - REARBRz UNDERFLOWLD R1, NEG_LASTADD R1, R1, R3BRnp REMOVE_SKIP_1LD R3, FIRST ; Wrap around, R3 <- FIRSTBRnzp REMOVE_SKIP_2REMOVE_SKIP_1 ADD R3, R3, #1 ; No wrap around, R3 <- R3 + 1REMOVE_SKIP_2 LDR R0, R3, #0 ; Do the removeBRnzp REMOVE_DONEUNDERFLOW ADD R5, R5, #1REMOVE_DONE LD R1, QUEUE_SAVE1RETLAST .FILL ADDR1 ; the topmost memory spaceNEG_LAST .FILL -ADDR1FIRST .FILL ADDR2 ; the bottommost memory spaceNEG_FIRST .FILL -ADDR2QUEUE_SAVE1 .BLKW 1
How many elements can be stored in a Queue?
In order to differentiate the full queue and the empty queue, we only allow a queue to store only
elements if
elements has been allocated.<br />A queue is full when there areelements in the queue, i.e.FRONT - 1 == REAR.<br />A queue if full whenFRONT == REAR`.
:::
Character Strings
A one-dimensional array of ASCII codes, and at the end the null character
indicates the end of the character string.
若有收获，就点个赞吧
0 人点赞
