Assembly Subroutines and Recursion

The goal of this project is to implement the LC-3 calling convention using assembly recursion. This will involve the use of the stack to save the return address (RA) and the old frame pointer (OFP). In each section, I'll act as a compiler, converting the provided pseudocode into assembly code that follows the LC-3 calling convention.

Subroutines:

1. Right Bit Shift The idea is to rotate' bits around and mask until we get the result we want. Definerotating' as shifting a binary number B left 1 bit and then setting the new least significant bit of B to the old most significant bit of B before the shift. So, for example, if we rotate a 4-bit binary number abcd, where a; b; c; d are bits, then we get bcda. Notice that if we perform this 16 times for a 16-bit number, we loop around and get the original number back again. And if we `rotate' only 15 times for a 16 bit number, then we've bitshifted the number right 1 bit, with the most significant bit being the old least significant bit.

2. Fast Exponentiation We will implement the following O(log k) algorithm which calculates n^k where k >=0:

pow(n; k) = ( pow(n; k=2)2 k is even n pow(n; bk=2c)2 k is odd

pow(n; 0) = 1

1. Recursive Bubble Sort Essentially, the idea is to iterate over an array n times, each time pushing the largest element to its correct position. Most implementations of Bubble Sort are done iteratively, where you have two nested loops, but that's just boring. Instead, we are going to do it recursively! In each recursive call, I will iterate over the array and push the largest element to the very end. Once I do that, I will recursively call the bubble sort method where I will decrease the size by one. Also, I will have to keep track of the number of swaps that I make and return the grand total.

Built With

• assembly