I am trying to convert a bubble sort program from assembly to Y86. I started with this C code and then converted it to assembly:
void bubbleSort2(long arr[], long len) {
long i; // inner loop index
long tmp; // temp for swapping
long *arr_curr; // pointer to element in arr
long *arr_next; // pointer to next element in arr
while (len > 1) {
arr_curr = arr; // begin at the start of arr
i = 0;
while (i < len-1) {
arr_next = arr_curr + 1; // set next pointer
if (*arr_curr > *arr_next) {
// Swap the two elements
// to bubble up the larger value
tmp = *arr_curr;
*arr_curr = *arr_next;
*arr_next = tmp;
}
i++;
arr_curr = arr_next; // move to the next element
}
len--;
}
}
So far I've come up with the following:
# Execution begins at address 0
.pos 0
irmovq stack, %rsp # Set up stack pointer
call main # Execute main program
halt # Terminate program
# Array
.align 8
arr:
.quad 0x64
.quad 0x34
.quad 0x40
.quad 0x25
.quad 0x12
.quad 0x22
.quad 0x11
.quad 0x90
.quad 0x55
.quad 0x42
main:
irmovq arr, %rdi
irmovq $10, %rsi
call bubble
ret
# start bubble
bubble:
irmovq $1, %rax
outer_loop:
rrmovq %rsi, %r8
subq %rax, %r8
irmovq $1, %r9
irmovq $0, %rcx
inner_loop:
rrmovq %rdi, %r10
addq %rcx, %r10
mrmovq (%r10), %r11
mrmovq 8(%r10), %r12
subq %r12, %r11
jle no_swap
subq %r11, %r12
je no_swap
jg swap
swap:
mrmovq (%r10), %r11
mrmovq 8(%r10), %r12
rmmovq %r11, 8(%r10)
rmmovq %r12, (%r10)
no_swap:
irmovq $8, %r13
addq %r13, %rcx
subq %rax, %r8
jg inner_loop
rrmovq %rdi, %r10
subq %rax, %r8
jg outer_loop
ret
# end bubble
# The stack starts here and grows to lower addresses
.pos 0x200
stack:
I keep getting this:
Changes to memory:
0x0018: 0x0000000000000064 0x0000000000000034
0x0020: 0x0000000000000034 0x0000000000000040
0x0028: 0x0000000000000040 0x0000000000000025
0x0030: 0x0000000000000025 0x0000000000000012
0x0038: 0x0000000000000012 0x0000000000000022
0x0040: 0x0000000000000022 0x0000000000000011
0x0048: 0x0000000000000011 0x0000000000000064
0x0050: 0x0000000000000090 0x0000000000000055
0x0058: 0x0000000000000055 0x0000000000000042
0x0060: 0x0000000000000042 0x0000000000000090
0x01f0: 0x0000000000000000 0x0000000000000085
0x01f8: 0x0000000000000000 0x0000000000000013
When I try with less than 5 elements, it's sorted but when i do 10, it's never sorted. Why does that happen? What is the problem with what I wrote, and how can it be corrected?
subq %r12, %r11 jle no_swap subq %r11, %r12 je no_swap jg swap
I get it that you are using a subtraction to replace a comparison, but what I don't get is the reason for that second subtraction.
Without the second subtraction, there would also be no reason to reload %r12 (using cmpq you wouldn't need to reload either!):
subq %r12, %r11
jle no_swap
swap:
mrmovq (%r10), %r11
rmmovq %r11, 8(%r10)
rmmovq %r12, (%r10)
no_swap:
subq %rax, %r8 jg inner_loop rrmovq %rdi, %r10 subq %rax, %r8 jg outer_loop
The inner loop ends on %r8 becoming 0. The subq %rax, %r8 that follows will leave %r8 at -1 and so jg outer_loop will stop there and then.
What could make sense is that you decrement the number of elements in the array (contained in %rsi):
subq %rax, %rsi # 10 -> 9 -> 8 ... 3 -> 2
cmpq %rax, %rsi
jne outer_loop