Develop MIPS assembly code for a merge sort algorithm given above. < Requirement
ID: 3629995 • Letter: D
Question
Develop MIPS assembly code for a merge sort algorithm given above.
< Requirements >
1. Array should be used for initial data set (word size).
2. Print the final result using the syscall on the console window.
3. A sorting result should be correct.
4. Your code must be relevant with the original source code. Try to translate the given C code to assembly code. Different algorithm is not allowed.
5. Show your register mapping plan using a table. (e.g. low -> $s0)
6. Comment for your code and explain how to implement the algorithm.
< Initial Data Set >
8, 14, 5, 1, 20, 7, 2, 30, 3, 9, 21, 6, 29, 11, 17, 4, 24, 28
- End of Question -
cf.
I have to run this assembly code using SPIM simulator.
The simulator should show me the correct result, otherwise I'll not be able to get any grade point.
Please implement the complete MIPS code to run.
If your solution doesn't work, I cannot give you any Karma Point.
I hope there is somebody who can help me.
Thank you so much. :)
Comment added:
Thanks to anonymous who commented. I have no option but only 8 hours with 350 Karma Points.
The deadline of this question is the midnight of Oct. 10th.
I'll re-post this question when it expired.
Plz don't concern about the left time, solve this problem.
Explanation / Answer
print prompt
read unsigned 32-bit integer from console (into $s0)
allocate space on stack
loop for each space:
call random number generator
store resulting number in space
print unsorted array heading
loop for each space:
print number
call merge_sort
print sorted array heading
loop for each space:
print number
exit
.data
.align 2
.jumptable: .word main, randloop, randoverflow, randnext, printloop1, printloop2, halt, merge_sort, mergeloop, mergesecond, finishfirst, finishsecond, copy, mergereturn
strings
SizePrompt: .asciiz "Enter size of array: "
UnsortedHeader: .asciiz " Unsorted array: "
SortedHeader: .asciiz " Sorted array: "
Spacer: .asciiz " "
MergeSortDebug1: .asciiz " merge_sort num_entries="
MergeSortDebug2: .asciiz " array_pointer="
.text
main:
Register allocations
s0 size of array (in entries)
s1 size of array (in bytes)
s2 pointer to head of array
s3 pointer to tail of array
s4 pointer into array
print prompt
li $v0, 4 operation = 4 (print string)
la $a0, SizePrompt param = address of string
syscall call O/S
s0 <-- 32bit signed integer from console
li $v0, 5 operation = 5 (read unsigned int from console)
syscall call O/S
move $s0, $v0 store result
s1 = size of array (in bytes)
sll $s1, $s0, 2 s1 = s0 << 2
tail of array
move $s3, $sp
allocate space on stack
subu $sp, $sp, $s1
start of array
move $s2, $sp
initialize PRND
li $t0, 33614 A$t0 <-- seed
li $v0, 2147483646 previous result doesn't exist S'$v0 <-- 2147483646
pointer into array (at start of array)
move $s4, $s2
loop for each space, generating a random number:
randloop:
multu $v0, $t0 HI,LO = A$t0
mflo $t1 Q$t1 = bits 00..31 of A
srl $t1, $t1, 1
mfhi $t2 P$t2 = bits 32..63 of A
addu $v0, $t1, $t2 result$v0 = P + Q
bltz $v0, randoverflow handle overflow ( rare )
sw $v0, 0($s4) store result in stack entry
j randnext
randoverflow:
sll $v0, $v0, 1 zero bit 31 of result$v0
srl $v0, $v0, 1
addiu $v0, $v0, 1 increment result$v0
sw $v0, 0($s4) store result in stack entry
randnext:
move to the next entry
addiu $s4, $s4, 4 move to next entry
end of array hasn't been reached, so loop
bne $s3, $s4, randloop
print unsorted array heading
li $v0, 4 operation = 4 (print string)
la $a0, UnsortedHeader param = address of string
syscall call O/S
s4 = pointer into array (at start of array)
move $s4, $s2
loop for each space:
printloop1:
load the number from the array
lw $a0, 0($s4)
print the number
li $v0, 1 operation = 1 (print signed 32bit integer)
syscall call O/S
move to the next entry
addiu $s4, $s4, 4 move to next entry
print spacer
li $v0, 4 operation = 4 (print string)
la $a0, Spacer param = address of string
syscall call O/S
end of array hasn't been reached, so loop
bne $s3, $s4, printloop1
call merge_sort
addiu $sp, $sp, -8 allocate space for 2 parameters
move $a0, $s0 a0 = size of array (in 4-byte entries)
move $a1, $s2 a1 = pointer to head of array
jal merge_sort call the function
addiu $sp, $sp, 8 deallocate space on the stack
print sorted array heading
li $v0, 4 operation = 4 (print string)
la $a0, SortedHeader param = address of string
syscall call O/S
s4 = pointer into array (at start of array)
move $s4, $s2
loop for each space:
printloop2:
load the number from the array
lw $a0, 0($s4)
print the number
li $v0, 1 operation = 1 (print signed 32bit integer)
syscall call O/S
move to the next entry
addiu $s4, $s4, 4 move to next entry
print spacer
li $v0, 4 operation = 4 (print string)
la $a0, Spacer param = address of string
syscall call O/S
end of array hasn't been reached, so loop
bne $s3, $s4, printloop2
halt:
li $v0, 10 operation = 10 (halt)
syscall call O/S
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.