Recursive Insertion Sortieren in Assembly

Question

Ich versuche Insertion sort in Assembly ARMV-8A zu implementieren. Insbesondere habe ich versucht, den folgenden Code in C zu übersetzen:

void insertionSortRecursive(int arr[], int n) 
{ 
    
    if (n <= 1) 
        return; 
  
    insertionSortRecursive(arr, n-1); 
    int last = arr[n-1]; 
    int j = n-2; 
  
    while (j >= 0 && arr[j] > last) 
    { 
        arr[j+1] = arr[j]; 
        j--; 
    } 
    arr[j+1] = last; 
} 
  

ich es zu übersetzen versucht haben, wie es ist, aber meine Implementierung wird in Endlosschleife in Funktion loop_insertion als Debugger zeigt:

.data 
my_Table:  .space 16 
size:   .word 4 
FileOpenMode: .string "r" 
FileName:  .string "test1.txt" 
fscanf_str:  .string "%d" 
printf_str:  .string "%d " 
out_message_str: .string "%d " 


.text 
.global main 

main: 

     stp  x29,x30,[sp,-32]! 
     add  x29,sp,0 

     adr  x1,FileOpenMode 
     adr  x0,FileName 
     bl  fopen 

     mov  x20,x0 

     adr  x0,my_Table 
     mov  x22,x0   //x22 adr of table 
     mov  x21,4 
     mov  x23,0 
//**************** READ FROM FILE ****************** 
loop: 
     add  x2,x29,28 
     adr  x1,fscanf_str 

     mov  x0,x20 
     bl  fscanf 

     ldr  w1,[x29,28] 
     mov  x0,x22 
     str  w1,[x0,x23] 
     add  x23,x23,4 

     add  w21,w21,-1 
     cbnz w21,loop 
//******************************************** 

     mov  x0,x22 //adr of table 
     mov  x1,4 
     bl  insertion_sort 

//**************** PRINT TO SCREEN FROM TABLE ***************** 
     mov  x21,0 
     mov  x23,4 

loop_print: 
     adr  x0, out_message_str 
     ldr  w1,[x22,x21] 
     bl  printf 
     add  x21,x21,4 
     sub  x23,x23,1 
     cbnz x23,loop_print 

//*********************************************************** 

     ldp  x29, x30, [sp], 32 
     ret 

insertion_sort: 
     stp  x29,x30,[sp,-64]! 
     add  x29,sp,0 

     str  x19,[x29,32] //str the save register 
     str  x0,[x29,16]  //str the address of table 
     str  w1,[x29,24]  //str the n 

     mov  x19,4 

     cmp  w1,1 
     b.le exit_ins 

     sub  w1,w1,1 

     bl  insertion_sort 

     ldr  w9,[x29,24]  //load the n for the suitable function 
     sub  w9,w9,1   //n-1 
     mul  w9,w9,w19 
     ldr  x10,[x29,16] //adr table 
     ldr  w11,[x10,x9] //last 
     udiv w9,w9,w19 
     sub  w12,w9,1  //j=n-2 

loop_insertion: 
     ldr  w12,[x29,24] 
     cmp  w12,0 
     b.lt label1 
     mul  w12,w12,w19 
     ldr  w13,[x10,x12] // w13=arr[j] 
     cmp  w13,w11 
     b.le label1 
     add  w12,w12,w19 
     str  w13,[x10,x12] //arr[j+1]=w13 
     udiv w12,w12,w19 
     sub  w12,w12,1 
     str  w12,[x29,24] 
     b  loop_insertion 

label1: 
     add  w12,w12,1 
     mul  w12,w12,w19 
     str  w11,[x10,x12] 

exit_ins: 
     ldr  x19,[x29,32] //ldr the value of x19 back to the x19 
     ldp  x29, x30, [sp], 64 
     ret 

I hat einige Änderungen vorgenommen, wie das Laden und Speichern des Wertes von n-2 innerhalb der Funktion insert_loop, aber das ändert nichts.

Answer 1

Sie müssen Ihren Code besser kommentieren, besonders wenn Sie möchten, dass andere helfen.

Ich rate, dass statt j in w12 Sie Berechnungen mit ihm machen und dann versuchen, den ursprünglichen Wert zurück, aber scheitern. Da Sie add w12,w12,w19 getan haben, um arr[j+1] zu erhalten, wird der Wert w12 nach udiv w12,w12,w19j+1 sein und wenn Sie eins davon subtrahieren, enden Sie wieder mit j, daher die Endlosschleife. Sie haben Tonnen von Registern, verwenden Sie einfach eine andere für die j+1.

Sie sollten dies in Ihrem Debugger sehen können.