问题描述:

I"m trying to do an insert sort in arm assembly but I have no idea how to do a while loop with 2 conditions? I got this psuedocode for the algorithm here from wikipedia but I am having trouble translating the while loop to ARM instructions because there are 2 condtions.

`for i = 1 to length(A)`

x = A[i]

j = i - 1

while j >= 0 and A[j] > x

A[j+1] = A[j]

j = j - 1

end while

A[j+1] = x

end for

Here is my attempt at translating the code to ARM assembly instructions, the array is holding 20 integers:

`MOV R7, #0 ;intialize index`

ForLoop:

CMP R7, #20 ;check if end of array

BEQ EndFor ;exit for loop if done

LDR R1, =array ;Load array address

MOV R2, R7, LSL #2 ;multiply array index r7 by 4 to get array offset

ADD R2, R1, R2 ;Set R2 to element address

LDR R1, [R2] ;R1 = A[R7]

MOV R8, R1 ;R8 = R1

SUB R9, R7, #1 ;R9 = R7 - 1

LDR R1, =array ;Load array address

MOV R2, R9, LSL #2 ;multiply array index r9 by 4 to get array offset

ADD R2, R1, R2 ;Set R2 to element address

LDR R3, [R2] ;r3 = A[r9]

WhileLoop:

CMP R9, #0 ;while >= 0

BEQ Endwhile

CMP R3, R8 ;while R3> R8

BEQ Endwhile

LDR R1, =array ;Load array address

MOV R2, R9, LSL #2 ;multiply array index r9 by 4 to get array offset

ADD R2, R1, R2 ;Set R2 to element address

LDR R3, [R2] ;r3 = A[r9]

ADD R9, R9, #1 ;R9 = R9 + 1

LDR R1, =array ;Load array address

MOV R2, R9, LSL #2 ;multiply array index by 4 to get array offset

ADD R2, R1, R2 ;Set R2 to element address

STR R3, [R2] ;A[R9] = R3

SUB R9, R9, #1 ;R9 = R9 - 1

B WhileLoop

Endwhile:

ADD R9, R9, #1 ;R9 = R9 + 1

LDR R1, =array ;Load array address

MOV R2, R9, LSL #2 ;multiply array index by 4 to get array offset

ADD R2, R1, R2 ;Set R2 to element address

STR R8, [R2] ;A[R9] = R8

ADD R7, R7, #1 ;increment index

B ForLoop

EndFor:

When I run the program, my code runs in an infinite loop in while loop. Any help will greatly appreciated.

```
while j >= 0 and A[j] > x
A[j+1] = A[j]
j = j -1
```

would be

```
while 1
if (j<0) break;
if (a[j] <= x) break;
A[j+1] = A[j]
j = j -1
```

your code is checking for j==0 and A[j]==0 instead

also INSIDE your loop, you're increasing R9 to read A[j+1], but not restoring it

instead of manually calculating the "+1" you could do an offset'ed `LDR R3, [R2, #4]`

which would do the "+1" for you

You question says you have difficulty with this line; `while j >= 0 and A[j] > x`

. The way a compiler implement **OR** and **AND** is as follows,

```
AND_CASE:
tst cond1
bxx end_loop ; false 1st condition
tst cond2
bxx end_loop ; false 2nd condition
; true code
b AND_CASE
end_loop:
OR_CASE:
tst cond1
bxx true ; short circuit (doesn't do 2nd statement)
tst cond2
bxx end_loop ; false 2nd condition
true:
; true code
b OR_CASE
end_loop:
```

For your case you check the index and then use it.

```
AND_CASE:
tst reg_j ; testing index 'j'
bmi end_loop ; false
; r0 represents some free scratch register...
ldr r0, [reg_a, reg_j, LSL #2] ; get the memory
cmp r0,reg_x ; compare vs key
blt end_loop ; false
; true code
b AND_CASE
end_loop:
```

Verify that the condition are appropriate for your signed-ness. The important point is that the compiler with test one condition at a time and then do a branch depending on whether it is **OR** or **AND**; the conditions are just inverted for the branch. Assembler programmers must usually do the same thing as a compiler. Every thing is the same for `if`

, `for`

, etc statements and their conditions.

You have the basic structure correct, but I think that you need to move the `ldr`

to the 'test block' and not include it else where; ie the 2nd condition test. As well, you need to get your signs and conditions correct. I would prefer not to give this information as it is wrote memorization and a good exercise for learning.