c - ARM程序集插入排序中的无效指针问题

Question

我正在尝试将一个简单的插入排序算法转换为程序集，但有关此特定配置的某些内容导致程序出现无效指针错误。

这是我使用的 C 版本:

int n, array[100], c, d, t;
for (c = 1; c < n - 1; c++) {
    d = c;
    while (d > 0 && array[d] < array[d - 1]) {
        t = array[d];
        array[d] = array[d - 1];
        array[d - 1] = t;
        d--;
    }
}

这是一个正在使用的 C 结构:

typedef struct { 
    int *list;
    int size;
    int maxSize;
} list; 

这是我的汇编文件:

.syntax unified

.text

.align 8
.global insert_ARM
.func insert_ARM, insert_ARM
.type insert_ARM, %function

insert_ARM:
    push {r4-r11, ip, lr}

@ setup
    ldr r4, [r0, #4]
    sub r4, r4, 1    @ r4 = n-1
    mov r5, #1       @ c=1
    mov r6, #16      @ d=0, which starts at #16
    mov r7, #0       @ t=0

for:

   @ d = c ; needs these lines to do the assembly equivalent, which is * 4.
    mov r6, r5      @ d = c
    LSL r6, #2      @ uses logical shift left: multiplies r6 by 4 to get the correct index
    add r6, r6, 16  @ add 16 because that's where the array starts

while:

    @ condition 1: d > 0
    cmp r6, #0      @ if d <= 0, get out of there
    ble forLoopStatements

    @ condition 2: array[d] < array[d-1]
    @ first, I need to define array[d] and array[d-1]
    @ r8 = array[d] and r9 = array[d-1]
    sub r10, r6, #4 @ r10 = d-1
    ldr r9, [r0, r10]   @ r9 = array[d-1]
    ldr r8, [r0, r6]    @ r8 = array[d]
    cmp r9, r8      @ comparing array[d-1] with array[d]
    bge forLoopStatements   @ if array[d] >= array[d-1], get out of there

    @ while effects
    @ note that r8 should still be array[d] here.
    str r9, [r0, r6]    @ array[d] = array[d-1]
    str r8, [r0, r10]   @ array[d-1] = t @ BUG HERE.

    sub r6, r6, #4  @ d--; // does -4 for ARM
    bal while       @ repeat loop


forLoopStatements:
    @ (c<n-1; c++)
    add r5, r5, #1  @ c++
    cmp r5, r4      @ compares c with n-1
    blt for     @ if c < n-1, loop again


end:
    mov r0, r10

    pop {r4-r11, ip, lr}

    BX lr
.endfunc

.end

好像是

str r8, [r0, r10]   @ array[d-1] = t

这会在某个时候导致旅行。

编辑:我发现在这条指令中 r8 的数字不知何故不正确，因为立即使用类似的东西

mov r8, #4

在商店防止错误之前(但当然会使结果不正确)。

检查 r0 的内容时，碰巧更新超出了范围，因为该结构的其他成员正在该过程中被修改。数组索引 0 位于 +16。

Answer 1

您在汇编的翻译中发现了问题。但是请注意以下问题:

• 外循环应该一直运行到 c < n而不是 c < n - 1 .按照编码，数组的最后一个元素永远不会移动。

• 使用 2 个嵌套的 for 会更具可读性循环:

  int n, array[100], c, d, t;
  for (c = 1; c < n; c++) {
      for (d = c; d > 0 && array[d] < array[d - 1]; d--) {
          t = array[d];
          array[d] = array[d - 1];
          array[d - 1] = t;
      }
  }