[Solved] CS224 Lab #3 Relatively Big MIPS Assembly Language Programming Machine Instruction Generation, Recursion, Linked Lists

Purpose: Practicing machine code generation. More experience with MIPS assembly language programming using recursion and linked lists. Gaining experience in MIPS program analysis by adding more to the utilities of an existing program.

Summary

Part 1 (30 points): Code generation for symbolic and pseudo machine instructions. Learning the principles of recursive programming and the implementation of dynamic link list data structure by program analysis in MIPS assembly language.

Part 2 (70 points): More experience with linked lists and recursive programming.Study and try to finish the lab part at home before coming to the lab. Make sure that you show the lab work to your TA before uploading in the lab.

Part 1. Preliminary Work / Preliminary Design Report (30 points)

You have to provide a neat presentation prepared by Word or a word processor with similar output quality. At the top of the paper on left provide the following information and staple all papers. In this part provide the program listings with proper identification. Please make sure that this info is there for proper grading of your work, otherwise some points will be taken off.

CS224

For the linked list parts only upload the utilities that you have implemented do not upload the parts provided to you.

1. 1. Generating machine instructions (12 points):Give the object code in hexadecimal for the instructions 1 to 6. The beginning positions of text and data are provide below after the code segment.

again: add $t0, $t0, $t1

add $t0, $t0, $t1

add $t0, $t0, $t1

add $t0, $t0, $t1

beq $t0, $t1, next # inst. no. 1

bne $t0, $t1, again # inst. no. 2

add $t0, $t0, $t1

add $t0, $t0, $t1

next: j again # inst. no. 3

la $t0, array # inst. no. 4

lw $t1, array # inst. no. 5

bge $t1, $t2, next # inst. no. 6

.data

.space 7

.align 2 # align: an assembler directive, see the Mars help menu or try and learn.

array: .word 10, 20, 30

Assume that the label again is located at the memory location 00 40 01 80₁₆.

Assume that the data segment starts at the memory location 10 01 00 80₁₆.

For the pseudo instructions first provide the symbolic machine instructions to be generated.

2. 2. recursiveMultiplication (8 points): Write a recursive MIPS subprogram that performs multiplication of two positive numbers by successive additions. Error check is optional. For recursiveMultiplication and recursivesummation provide a simple user interface to test them under the same main program..

3. 3. recursiveSummation (10 points): Write a recursive MIPS subprograms that finds the summation of numbers from 1 to N. Error check is optional.

4. 4. DeleteAll_x (10 points): Study the linked list program provided and the linked list explanation provided below in Part 2.Delete all elements from the linked list with value x: the pointer to the linked list is passed in $a0, and the integer value of the element to be deleted is given in $a1. Return value in $v0= 0 if successful (was able to delete), -1 if not. In either case, the return value in $v1 contains the pointer to the head of the linked list. Are you able to return the deleted nodes back to the heap? If not include a comment in the program to explain why. Modify the given linked list program to include this option.

Part 2. Lab Work: Creating Linked List Utility Routines (60 points)

Linked lists are important dynamic data structures, useful to a variety of algorithms because of their ability to grow and shrink. Utilities libraries for linked lists are therefore useful, so that common functions can be available to users, pre-written, tested and ready to go. In this lab, you will write the utility functions defined below for linked lists, in MIPS assembly language. Your utilities will be combined with other utility programs such as create_list and display_list, and called by a main program. [Any code other than the you are asked to write in this lab will be provided (see the Unilica folder)you dont need to write it.]

In memory, the linked lists your utilities will work with are implemented as follows: each element consists of 2 parts: pointerToNext, and value. Each part is a 32-bit MIPS word in memory. The two parts are located in successive word addresses, with the pointerToNext being first. For example, if the byte address of the pointerToNext is 100, then the byte address of the value will be 104. Remember, MIPS memory is byte addressable.

In the last element of the linked list, the pointerToNext has value 0, in other words it is the null pointer. This means that there is not any next element. Do not forget that the last element still has a value.

Write the following linked list utility routines. Follow MIPS programming conventions in terms of using the stack and registers. Ignore the other methods not implemented. Modify the menu to include the following possibilities.

1. Insert_end (10 points):Insert an element to the linked list at end: the pointer to the linked list is passed in $a0, and the integer value of the new element to be inserted is given in $a1. This utility will request space in memory by syscall, use it to create a new element, and then insert the new element into the linked list at the end. Upon return, the value in $v0 =0 if successful, -1 if not. In either case, the pointer to the head of the linked list should be the same as it was before the call.
2. Delete_n (10 points):Delete an element from the linked list at position n: the pointer to the linked list is passed in $a0, and the position of the element to be deleted is given in $a1. The first element is in position 1, the second element in position 2, etc. Return value in $v0 =0 if successful, -1 if not. In either case, the return value in $v1 contains the pointer to the head of the linked list.
3. Invert_List (20 points): Invert a linked list. This means that if the list contains -> 10 -> 20 -> 30 after the call it becomes -> 30 -> 20 -> 10. No restriction in implementation: it can be recursive or non recursive. It must return the new list head in $v0.
4. Display_Reverse_Order_Recursively (20 points): Display the elements of the linked list in reverse order. This means that if the list contains -> 10 -> 20 -> 30 it displays the list in the reverse order 30, 20, 10. This must be a recursive subprogram: it must call itself with jal.