assembly Y86冒泡排序程序未正确排序

euoag5mw  于 2023-04-30  发布在  其他
关注(0)|答案(1)|浏览(135)

我正在尝试将一个冒泡排序程序从汇编转换为Y86。我从这段C代码开始,然后将其转换为汇编:

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--;
    }
}

到目前为止,我已经提出了以下内容:

# 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:

我一直收到这个:

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

当我尝试少于5个元素时,它是排序的,但当我尝试10个元素时,它永远不会排序。为什么会这样呢?我写的东西有什么问题,如何纠正?

vxbzzdmp

vxbzzdmp1#

subq %r12, %r11
jle no_swap
subq %r11, %r12
je no_swap
jg swap

我知道你用减法来代替比较,但我不明白的是第二次减法的原因。
如果没有第二次减法,也没有理由重新加载%r12(使用cmpq,您也不需要重新加载!):

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

内循环在%r8变为0时结束。接下来的subq %rax, %r8将使%r8处于**-1**,因此jg outer_loop将停止在那里。
有意义的是,你递减数组中的元素数量(包含在%rsi中):

subq %rax, %rsi    # 10 -> 9 -> 8 ... 3 -> 2
cmpq %rax, %rsi
jne  outer_loop

相关问题