Review Chap 8

Subroutines

It is almost always the case that collections of fragments to invoke the program are available to user programmers to free them from writing their own. These collections are referred to as libraries.

In a library, a specified fragment can be invoked multiple times within the same program without having to specify its details. Such program fragments are called subroutines, or in C we call it functions.

• The Call/Return Mechanism

It allows us to execute this one three-instruction sequence multiple times by requiring us to include it as a subroutine in our program only once.

The programmer uses the call/return mechanism to direct the computer each time via the call instruction to the code A, and after the computer has executed the code A, to the return instruction to the proper next instruction to be executed in the program.

Two instructions will be needed: JSR(R) calls the subroutinue; and RET(JMP R7) to go back to the main program.

• The JSR(R) instruction detailed

  The instruction uses one of two addressing modes for computing the starting address of the subroutine, PC-relative addressing or Base Register addressing. The LC-3 assembly language provides two different mnemonic names for the opcode, JSR and JSRR, depending on which addressing mode is used.

  The JSR (R) instruction does two things. Like all control instructions, it loads the PC, overwriting the incremented PC that was loaded during the FETCH phase of the JSR (R) instruction. In this case, the starting address of the subroutine is computed and loaded into the PC.

  The second thing the JSR (R) instruction does is save the return address in R7. The return address is the incremented PC, which is the address of the instruction following the JSR (R) instruction in the calling program.

• Saving and Restoring Registers

If a value in a register will be needed after something else is stored in that register, we must save it before something else happens and restore it before we can subsequently use it. We save a register value by storing it in memory; we restore it by loading it back into the register.

The save/restore problem can be handled either by the calling program before the JSR occurs or by the subroutine.

In summary, we use the term "caller-save" if the calling program handles the save/restore problem, and we use the term "callee-save" if the called program handles the problem. The appropriate one to handle the problem is the one that knows which registers will be destroyed by subsequent actions.

The Stack

The stack is an abstract data type whose defining notion is that the last thing you stored in the stack is the first thing you remove from it. Simply, Last In, First Out, LIFO.

In a stack implemented in hardware, as each value is added or removed, all the other values already on the stack move.

• Implementation in Memory

In the LC-3, R6 is the stack pointer.

These show the implementation in memory. Different from hardware,

Figure 8.9a shows an initially empty stack. Since there are no values on the stack, the stack pointer contains the address x4000, which is the address of the memory location just after the memory locations reserved for the stack. This setup makes sense because as we will see through the code for pushing and popping values, the stack grows towards zero.

Figure 8.9b illustrates the stack after pushing the value 18. Notice that the stack pointer now contains the address x3FFF, which becomes the new top of the stack.

In Figure 8.9c, we can see the stack after pushing the values 31, 5, and 12 in that order. It is important to note that the values inserted into the stack are stored in memory locations with decreasing addresses, as the stack grows towards zero.

Lastly, Figure 8.9d demonstrates the stack after popping the top two elements off the stack. The values 5 and 12, which were popped, are still present in memory locations x3FFD and x3FFC, respectively. However, these values cannot be accessed from memory as long as every access to memory is controlled by the stack mechanism.

Unlike the coin holder and computer hardware stack implementations discussed in the previous section, when values are pushed and popped to and from a stack implemented in sequential memory locations, the data already stored on the stack does not physically move.

• Underflow and Overflow
• Underflow: Underflow happens when an attempt is made to pop a value from an empty stack. In other words, the stack is already empty, but a pop operation is requested. This results in an error condition because there are no values to retrieve from the stack. It is important to check for underflow conditions before performing a pop operation to avoid data loss or program malfunction.
• Overflow: Overflow occurs when an attempt is made to push a value onto a stack that is already full. In LC-3, the stack is implemented within a defined region of memory with a fixed size. When the stack becomes full and additional values need to be pushed onto it, an overflow condition arises. This can lead to data corruption or unpredictable behavior in the program. It is crucial to monitor the stack usage and prevent overflow situations by appropriately managing the stack size or implementing error handling mechanisms.

Both underflow and overflow conditions can be detected by monitoring the stack pointer and checking its position relative to the stack boundaries. Handling these scenarios effectively is essential to ensure the proper functioning and integrity of programs using the LC-3 stack.

Here are a complete picture, from which you can detect the way to avoid underflow and overflow.

Recursion, a Powerful Technique When Used Appopriately

Recursion is a mechanism for expressing a function in terms of itself.

Good Example：a maze

The Queue

Unlike the stack, it is FIFO(first in first out). This means we need to keep track of two ends of the storage structure: a FRONT pointer for servicing and a REAR pointer for entering. Here are an example.

The basic operations: Remove from front, Insert at rear.

Wrap-Around: It works by having our removal and insertion algorithms test the contents of FRONT and REAR for the value x8005. If we wish to insert, and REAR contains x8005, we know we have reached the end of our available storage and we must see if x8000 is available. If we wish to remove, we must see if FRONT contains the address x8005. If it does, the front of the queue is in x8000.

• NOTE: We cannot let the empty queue and the full queue look the same, What should we do?

Our answer is to allow the queue to store only n-1 elements if space for n elements has been allocated. That means, if inserting a nth element into the queue would cause FRONT to equal REAR, we do not allow that insertion. We declare the queue full when there are n-1 elements in the queue.

If the queue is empty, FRONT=REAR.

Test of UNDERFLOW: just test if R3=R4. If so, it means it is already empty.

Test of OVERFLOW: similarly, just add 1 to the REAR, if R3=R4, it means it is already full.

Character Strings(Omit)