ARM сборка быстрой сортировки и рекурсии - PullRequest
Новая
       39

ARM сборка быстрой сортировки и рекурсии

0 голосов
/ 03 декабря 2018

Я пытаюсь изменить код быстрой сортировки C на код сборки ARM.
Во-первых, я прошу прощения за мой длинный вопрос.
на всякий случай, я написал целые коды.
, но только часть, которая делаетПроблема в функции рекурсивной части.Я почти выполнил эту работу, за исключением части рекурсии funcion.
Я также попытался преобразовать C-коды в сборку ARM с помощью кросс-компилятора gcc, чтобы посмотреть, как работает компилятор.Но есть еще несколько вещей, которые я не могу понять хорошо.

Это код C. 

void quicksort_c(int array[8],int first,int last)
{
int i, j, pivot, temp;

if(first < last)
{
    pivot = first;
    i = first;
    j = last;

    while(i < j)
    {
        while(array[i] <= array[pivot] && i < last)
        {
            i++;
        }
        while(array[j] > array[pivot])
        {
            j--;
        }
        if(i < j)
        {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }


    temp = array[pivot];
    array[pivot] = array[j];
    array[j] = temp;
    quicksort_c(array, first, j-1);
    quicksort_c(array, j+1, last);
}
}

и это код сборки руки, который я написал с нуля. 

quicksort
    STMFD sp!, {r0-r8,lr}

quicksort_recursion
    CMP r1, r2 ;// if(first < last)
    BGE out_of_if

outer_if
    MOV r5, r1 ;// pivot = first
    MOV r3, r1 ;// i = first;
    MOV r4, r2 ;// j = last;

outer_while_loop
    CMP r3, r4 ;// while(i < j)
    BGE end_of_outer_while

outer_while

inner_while_1_loop
    ;//while(array[i] <= array[pivot] && i < last)
    LDR r7, [r0, r3, lsl #2] ;//r7 = array[i]
    LDR r8, [r0, r5, lsl #2] ;//r8 = array[pivot]

    CMP r7, r8 ;//array[i] <= array[pivot]
    BGT inner_while_2_loop

    CMP r3, r2 ;// i < last
    BGE inner_while_2_loop

inner_while_1
    ADD r3, #1 ;//i++
    B   inner_while_1_loop

inner_while_2_loop
    ;//whlie(array[j] > array[pivot])
    LDR r7, [r0, r4, lsl #2] ;// r7 = array[j]
    LDR r8, [r0, r5, lsl #2] ;//r8 = array[pivot]

    CMP r7, r8 ;// (array[j] > array[pivot])
    BLE inner_if_cmp

inner_while_2
    SUB r4, #1
    B   inner_while_2_loop

inner_if_cmp
    CMP r3, r4;// if(i < j)
    BGE outer_while_loop

inner_if
    LDR r7, [r0, r3, lsl #2] ;// r7 = array[i]
    MOV r6, r7 ;// temp = array[i]

    LDR r8, [r0, r4, lsl #2] ;// r8 = array[j]
    STR r8, [r0, r3, lsl #2] ;// array[i] = array[j]

    STR r6, [r0, r4, lsl #2] ;// array[j] = temp;

    B   outer_while_loop

end_of_outer_while
    LDR r7, [r0, r5, lsl #2] ;// r7 = array[pivot]
    MOV r6, r7 ;// temp = array[pivot]

    LDR r8, [r0, r4, lsl #2] ;// r8 = array[j]
    STR r8, [r0, r5, lsl #2] ;// array[pivot] = array[j]

    STR r6, [r0, r4, lsl #2] ;// array[j] = temp

    ;;//quicksort(array,first,j-1)
    STMFD sp!, {r0-r8,lr}
    SUBS    r2, r4, #1
    BL  quicksort_recursion
    ;//LDMFD sp!, {r0-r8,pc}


    ;//quicksort(array, j+1, last)
    STMFD sp!, {r0-r8,lr}
    ADDS    r1, r4, #1
    BL  quicksort_recursion
    ;//LDMFD sp!, {r0-r8,pc}

out_of_if

end_function
    LDMFD sp!, {r0-r8,pc}
    END

и вот как я использую регистр 

r0: array pointer
r1: first index
r2: last index

r3: i
r4: j
r5: pivot
r6: temp

r7: array[?] value
r8: array[?] value

Я подтвердил, что все части, кроме рекурсии моего кода, работают хорошо.

Сначала я делал рекурсию таким способом. 

;;//quicksort(array,first,j-1)
SUBS    r2, r4, #1
BL  quicksort

;//quicksort(array, j+1, last)
ADDS    r1, r4, #1
BL  quicksort

, но этот код толькорекурсия первой функции.

ex)
Массив до быстрой сортировки: 5 1 4 7 8 3 6
Массив после быстрой сортировки: 1 2 4 3 5 8 7 6

Я думаю, что этопотому что после вызова функции она не возвращается туда, где она разветвляется.поэтому я добавил push и pop до и после вызова функции следующим образом. 

;;//quicksort(array,first,j-1)
STMFD sp!, {r0-r8,lr}
SUBS    r2, r4, #1
BL  quicksort_recursion

;//quicksort(array, j+1, last)
STMFD sp!, {r0-r8,lr}
ADDS    r1, r4, #1
BL  quicksort_recursion

Но этот код попадает в бесконечный цикл.

согласно скомпилированному коду gcc, 

quicksort_linux
    cmp r1, r2
    blt L16
    bx  lr
L16
    push    {r4, r5, r6, r7, r8, r9, r10, lr}
    mov r10, r1
    add ip, r0, r1, lsl #2
    mov r5, r2
    mov r4, r1
L3
    lsls    r3, r4, #2
    add lr, r0, r3
    ldr r7, [r0, r4, lsl #2]
    ldr r6, [ip]
    cmp r2, r4
    ite le
    movle   r8, #0
    movgt   r8, #1
    cmp r7, r6
    it  gt
    movgt   r8, #0
    adds    r3, r3, #4
    add r3, r3, r0
    cmp r8, #0
    beq L9
L4
    adds    r4, r4, #1
    mov lr, r3
    ldr r7, [r3], #4
    cmp r2, r4
    ite le
    movle   r1, #0
    movgt   r1, #1
    cmp r7, r6
    it  gt
    movgt   r1, #0
    cmp r1, #0
    bne L4
L9
    lsls    r3, r5, #2
    add r9, r0, r3
    ldr r1, [r0, r5, lsl #2]
    cmp r1, r6
    ble L5
    subs    r3, r3, #4
    add r3, r3, r0
L6
    subs    r5, r5, #1
    mov r9, r3
    ldr r1, [r3], #-4
    cmp r1, r6
    bgt L6
L5
    cmp r4, r5
    bge L7
    str r1, [lr]
    str r7, [r9]
    b   L3
L7
    mov r7, r2
    mov r1, r10
    mov r4, r0
    ldr r3, [r0, r5, lsl #2]
    str r3, [r0, r10, lsl #2]
    str r6, [r0, r5, lsl #2]
    subs    r2, r5, #1
    bl  quicksort_linux
    mov r2, r7
    adds    r1, r5, #1
    mov r0, r4
    bl  quicksort_linux
    pop {r4, r5, r6, r7, r8, r9, r10, pc}

END

Кажется, что они не делают push или pop до или после ветвления, но это работает.

Итак, вопрос в
1. В чем проблема моего кода рекурсии функции?
2.Как я могу это исправить?
3.Как может скомпилированный код gcc работать без каких-либо push и pop до и после рекурсии функции?

...