问题描述:

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.

相关阅读:
Top