Invalid pointer issue in insertion sort in ARM assembly

Question

I'm trying to translate a simple insertion sort algorithm to assembly, but something about this particular configuration is causing the program to get an invalid pointer error.

Here's the C version that I'm using:

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

This is a C struct that is being used:

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

Here is my assembly file:

.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



It seems to be

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


that causes a trip at some point.

Edit: I found out that r8's numbers during this instruction are somehow incorrect, since immediately using something like

mov r8, #4


before the store prevents the error (but of course makes the results incorrect).

Upon examining the contents of r0, it happens that the update is going off range because other members of the struct are being modified in the process. Array index 0 is at +16.

Invalid pointer issue in insertion sort in ARM assembly

3 Answers