无法在 ARM 中对数组进行排序。它已排序，但有数字丢失和重复

Question

我正在尝试在 ARM 中实现 BubbleSort。

这是main.c：

#include <stdio.h>
#define SIZE 9

int sort(int*,int);

int main(){
        int array[SIZE] = {5,6,2,5,8,4,1,75,4};
        printf("Array before sort:\n");
        for(int i=0;i<SIZE;++i)
                printf("%d ",array[i]);
        sort(array,SIZE);
        printf("\nArray after sort:\n");
        for (int i=0;i<SIZE;++i)
                printf("%d ",array[i]);
        printf("\n");

        return 0;
}

这里是sort.s：

.global sort
.type sort%function

array   .req r0
offset_end .req r1
offset_1 .req r2
offset_2 .req r3
min_1   .req r4
min_2   .req r5

sort:
        mov ip,#4
        mul offset_end,r1,ip    // calculate final offset (in r1 there was the size)
        mov offset_1,#0    // initialize first offset to the first position
        mov offset_2,#4    // initialize second offset to the second position
loop1:
        cmp offset_1,offset_end
        beq end    // if I reached the end, it goes to end
        ldr min_1,[array,offset_1]    // get the corresponding int
        push {ip,lr}    // save lr
        mov offset_2,offset_1    // put the offset_1 in the second offset (that will be used in the loop2)
        add offset_2,offset_2,#4    // move second offset to next element
        bl loop2    // enter in the second loop
        pop {ip,lr}
        add offset_1,offset_1,#4
        b loop1
loop2:
        cmp offset_2,offset_end
        bxge lr     // if the second offset reached the end, it returns
        ldr min_2,[array,offset_2]    // get the value
        cmp min_1,min_2
        push {ip,lr}    // save lr
        blge swap    // if min_1 is greater than min_2, it swaps
        pop {ip,lr}
        add offset_2,offset_2,#4     // go to next value
        b loop2     // repeat the loop2
swap:
        str min_2,[array,offset_1]    // put the new min in the offset of the first loop
        str min_1,[array,offset_2]    // put the old min in the offset of the second loop
        bx lr     //returns
end:
        bx lr     // exit the program

输出：

$ arm-linux-gnueabihf-gcc main.c sort.s 
$ ./a.out 
Array before sort:
5 6 2 5 8 4 1 75 4 
Array after sort:
4 5 6 6 6 8 8 8 75

可以看到，数组已经排序了，但是有缺号和重号。我怎样才能找到错误？

Answer 1

错误是在swap之后，min_1和min_2不再对应于offset_1和offset_2处的数组条目但是你假设至少 min_1 是。要解决此问题，请将 swap 函数中的 min_1 更新为索引 offset_1 处的值，即 min_2:

的先前值

swap:
        str min_2,[array,offset_1]    // put the new min in the offset of the first loop
        str min_1,[array,offset_2]    // put the old min in the offset of the second loop
        mov min_1, min_2              // update min_1 to new minimum
        bx lr     //returns

您应该修复的另一件事是您的代码不保留寄存器 r4 和 r5，尽管 ABI 要求这样做。要解决此问题，请在函数开始时将这些寄存器压入堆栈，然后在结束时将它们弹出。

无法在 ARM 中对数组进行排序。它已排序，但有数字丢失和重复

Can't sort an array in ARM. It's sorted, but there are numbers missing and duplicated

sorting

assembly

arm

bubble-sort