You may work in teams of 1 to 4 on this assignment. EXACTLY ONE MEMBER OF YOUR TEAM SHOULD SUBMIT THE ASSIGNMENT IN CANVAS! THE TAs WILL ASSESS A PENALTY IF MORE THAN ONE MEMBER OF YOUR GROUP SUBMITS THE ASSIGNMENT, AS THIS CREATES A SIGNIFICANT OVERHEAD FOR THEM WHILE GRADING. Your submission should be headed by a comment giving the names and NetIDs of each member of your team.
You will be writing a program in LEGv8 assembly. Contrary to the claims in the textbook, there is not an emulator that comes with the book; in its place, I wrote one. Our emulator is Linux only. I’ve placed a statically-linked copy on Pyrite in /home/sheaffer/legv8emul . I’ve also attached a copy here: legv8emul. Being statically linked, it should work on any Linux system (or, I suppose, in the Windows Linux Subsystem; if somebody knows how to use this, maybe you could post a short tutorial?). Since your U drive is mapped to Pyrite, simply running your programs on Pyrite and editing them on your favorite platform will probably be simplest for most of you. Information about how to access Pyrite and about VM access is at the bottom of this document, reproduced from my COM S 327 syllabus.
You will be implementing insertion sort in LEGv8 assembly. In a high(er) level language, implementing the entirety of insertion sort in a single function should be straightforward for students with your level of experience, but in assembly, it gets complicated fairly quickly. To ameliorate some of the complication, we’ll break the implementation into a number of procedures, none of which require nested loops. Descriptions of these procedures, some with pseudocode, follow.
In the problem description below, all values are 8 bytes each. Procedures to be solved on LEGv8 assembly:
• Shift right: This procedure takes three parameters, the address of an array of ints, the index of the final element in the array, and a position in the array. It overwrites the final element, shifting intermediate elements to the right, leaving a whole at the position.
ShiftRight(addr, pos, final):
for i from final – 1 to pos:
addr[i + 1] = addr[i]
• Find sorted position: This procedure takes three parameters, the address of an array of sorted ints, a value, and the index of the last element in the array. It searches the array for the sorted position of the value and returns that index.
FindSortedPos(addr, val, final):
for i from 0 to final
if addr[i] >= val
break
return i
• Insert sorted position: This procedure takes two parameters, the address of a sorted array of ints, the final element not in sorted position, and the index of the last element of the array. It moves the final element into its sorted position, shifting elements to the right as necessary such that the entire element is in sorted order and no data is lost.
InsertSortedPos(addr, final):
v = addr[j]
p = FindSortedPos(addr, v, final)
ShiftRight(addr, p, final)
addr(p) = v
• Insertion sort: This procedure takes two parameters, the address of an array of ints and the number of elements in the array. It sorts the array using the insertion sort algorithm.
InsertionSort(addr, length):
for i from 1 to length:
InsertSortedPos(addr, i)
• Fill: Fill(addr, length) will create an array at address addr of length elements containing length unique integers in reverse sorted order
• Main: Your main procedure takes no parameters, and doesn’t strictly need to be named (its the start of your program, by default). It calls Fill to create a reverse sorted array and then calls InsertionSort to sort it.
How to get started:
• Get an environment running that you are comfortable in.
• Write all of the above procedures in C, or some similar language. If you do it in, e.g., Java, keep it C like (use only primitives and arrays). Make sure your code works. You’ll use it to help you reason about your assembly. In a sense, you’ll compile it by hand. Please note that, while I believe it is correct, I have not tested the given pseudocode! It is absolutely possible that it contains off-by-one or other such subtle errors! Make your higher-level language implementation work!
• Write Fill first. It will configure your memory in a way that makes it easy to check that other procedures work.
• You have complete, unmanaged access to memory. Memory starts at address 0 and goes (by default, but adjustable via a command line switch) through byte 4095, inclusive (default 4 kB). To allocate storage, you simply use it. e.g., to access a 10 element array at address 100, I simply put 100 into a register and then use that register to index your array.
Gotchas:
Be very careful about the 8s (8 byte integers!) you’re going to need all over the place. It’s easy to forget them, and then things simply don’t work!
What to turn in:
A single file, assignment1.legv8asm, containing your program. Don’t forget the comment at the top with team members names and NetIDs.
Using legv8emul:
Running the emulator with no parameters will give usage instructions. Code may have comments. Comments start with // and continue to the end of the line (actually, I never check for the second slash, so technically they start with /).