Translate pseudocode (bubble sort) into MIPS
A[0] holds the smallest value and
A[size -1] holds the largest value.
int t = 0;
for ( int i=0; i<size-1; i++ ) {
for ( int j=0; j<size-1-i; j++ ) {
if ( A[j] > A[j+1] ) {
t = A[j+1];
A[j+1] = A[j];
A[j] = t;
}
}
}
----------------------------------------------------------------------------------
PART 2
Translate pseudocode (binary search) into MIPS
The array A has already been sorted due to part 1. A[0]
holds the smallest value and A[size -1] holds the largest value, and v holds
the search value by user input
int left = 0;
int right = size - 1;
int middle = 0;
int element_index = -1;
while ( left <= right ) {
middle = left + (right - left) / 2;
if ( A[middle] == v) {
element_index = middle;
break;
}
if ( A[middle] < v )
left = middle + 1;
else
right = middle - 1;
}
if ( element_index < 0 )
printf( "%d not in sorted A\n", v );
else
printf( "Sorted A[%d] = %d\n", element_index, v );
______________________________________________________________________________
Translation of bubble sort psuedo code
size:
.zero 4
A:
.zero 4
t:
.zero 4
main:
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-4], 0
jmp .L2
.L6:
mov DWORD PTR [rbp-8], 0
jmp .L3
.L5:
mov eax, DWORD PTR [rbp-8]
cdqe
mov edx, DWORD PTR A[0+rax*4]
mov eax, DWORD PTR [rbp-8]
add eax, 1
cdqe
mov eax, DWORD PTR A[0+rax*4]
cmp edx, eax
jle .L4
mov eax, DWORD PTR [rbp-8]
add eax, 1
cdqe
mov eax, DWORD PTR A[0+rax*4]
mov DWORD PTR t[rip], eax
mov eax, DWORD PTR [rbp-8]
lea ecx, [rax+1]
mov eax, DWORD PTR [rbp-8]
cdqe
mov edx, DWORD PTR A[0+rax*4]
movsx rax, ecx
mov DWORD PTR A[0+rax*4], edx
mov edx, DWORD PTR t[rip]
mov eax, DWORD PTR [rbp-8]
cdqe
mov DWORD PTR A[0+rax*4], edx
.L4:
add DWORD PTR [rbp-8], 1
.L3:
mov eax, DWORD PTR size[rip]
sub eax, 1
sub eax, DWORD PTR [rbp-4]
cmp DWORD PTR [rbp-8], eax
jl .L5
add DWORD PTR [rbp-4], 1
.L2:
mov eax, DWORD PTR size[rip]
sub eax, 1
cmp DWORD PTR [rbp-4], eax
jl .L6
nop
nop
pop rbp
ret
2) Translation of binary search
binarySearch:
push
rbp
mov rbp, rsp
sub rsp, 48
mov QWORD PTR [rbp-24], rdi
mov DWORD PTR [rbp-28], esi
mov DWORD PTR [rbp-32], edx
mov DWORD PTR [rbp-36], ecx
mov eax, DWORD PTR [rbp-32]
cmp eax, DWORD PTR [rbp-28]
jl .L2
mov eax, DWORD PTR [rbp-32]
sub eax, DWORD PTR [rbp-28]
mov edx, eax
shr edx, 31
add eax, edx
sar eax
mov edx, eax
mov eax, DWORD PTR [rbp-28]
add eax, edx
mov DWORD PTR [rbp-4], eax
mov eax, DWORD PTR [rbp-4]
cdqe
lea rdx, [0+rax*4]
mov rax, QWORD PTR [rbp-24]
add rax, rdx
mov eax, DWORD PTR [rax]
cmp DWORD PTR [rbp-36], eax
jne .L3
mov eax, DWORD PTR [rbp-4]
jmp .L4
.L3:
mov eax, DWORD PTR [rbp-4]
cdqe
lea rdx, [0+rax*4]
mov rax, QWORD PTR [rbp-24]
add rax, rdx
mov eax, DWORD PTR [rax]
cmp DWORD PTR [rbp-36], eax
jge .L5
mov eax, DWORD PTR [rbp-4]
lea edi, [rax-1]
mov edx, DWORD PTR [rbp-36]
mov esi, DWORD PTR [rbp-28]
mov rax, QWORD PTR [rbp-24]
mov ecx, edx
mov edx, edi
mov rdi, rax
call
binarySearch
jmp .L4
.L5:
mov eax, DWORD PTR [rbp-4]
lea esi, [rax+1]
mov ecx, DWORD PTR [rbp-36]
mov edx, DWORD PTR [rbp-32]
mov rax, QWORD PTR [rbp-24]
mov rdi, rax
call
binarySearch
jmp .L4
.L2:
mov eax, -1
.L4:
leave
ret
.LC0:
.string "Element is not
present in array"
.LC1:
.string "Element is
present at index %d"
main:
push
rbp
mov rbp, rsp
sub rsp, 32
mov DWORD PTR [rbp-32], 2
mov DWORD PTR [rbp-28], 3
mov DWORD PTR [rbp-24], 4
mov DWORD PTR [rbp-20], 10
mov DWORD PTR [rbp-16], 40
mov DWORD PTR [rbp-4], 5
mov DWORD PTR [rbp-8], 10
mov eax, DWORD PTR [rbp-4]
lea esi, [rax-1]
mov edx, DWORD PTR [rbp-8]
lea rax, [rbp-32]
mov ecx, edx
mov edx, esi
mov esi, 0
mov rdi, rax
call
binarySearch
mov DWORD PTR [rbp-12], eax
cmp DWORD PTR [rbp-12], -1
jne .L7
mov edi, OFFSET FLAT:.LC0
mov eax, 0
call
printf
jmp .L8
.L7:
mov eax, DWORD PTR [rbp-12]
mov esi, eax
mov edi, OFFSET FLAT:.LC1
mov eax, 0
call
printf
.L8:
mov eax, 0
leave
ret
Get Answers For Free
Most questions answered within 1 hours.