Home > Enterprise >  Finding the smallest element in array in arm assembly
Finding the smallest element in array in arm assembly

Time:12-20

I have this program that i have to write in arm assembly to find the smallest element in an array. Normally this is a pretty easy thing to do in every programming language, but i just can't get my head around what i'm doing wrong in arm assembly. I'm a beginner in arm but i know my way around c. So I wrote the algorithm on how to find the smallest number in an array in c like this.

int minarray = arr[0];
    for (int i =0; i < len; i  ){
        if (arr[i] < minarray){
            minarray = arr[i];
        }

It's easy and nothing special really. Now i tried taking over the algorithm in arm almost the same. There are two things that have already been programmed from the beginning. The address of the first element is stored in register r0. The length of the array is stored in register r1. In the end, the smallest element must be stored back in register r0. Here is what i did:

.global min
min:


LDR r4, [r0] 



loop1:
      LDR     r8, [r0]   
     
      CMP     r8, r4     
      MOVLE   r8, r4 
      ADD     r0, r0, #4      
      SUBS    r1, r1, #1 
      BPL     loop1        
      MOV     r0, r4    

      

MOV pc, lr  

This is almost the same algorithm as the one in c. First i load the first element into a new register r4. Now the first element is the smallest. Then once again, i load the first element in r8. I compare those two, if r8 <= r4, then copy the content of r8 to r4. After that (because i'm working with numbers of 32 bits) i add 4bytes to r0 to get on to the next element of the array. After that i subtract 1 from the array length to loop through the array until its below 0 to stop the program. The feedback i'm getting from my testing function that was given to us to check if our program works says that it works partly. It says that it works for short arrays and arrays of length 0 but not for long arrays. I'm honestly lost. I think i'm making a really dumb mistake but i just cannot find it and i've been stuck at this easy problem for 3 days now but everything i have tried did not work or as i said, only worked "partly". I would really appreciate if someone could help me out. This is the feedback that i get:

  • ✗ min works with other numbers
  • ✗ min works with a long array
  • ✓ min works with a short array
  • ✓ min tolerates size = 0

(x is for "it does not work", ✓ is for "it works")

So you see what i'm saying? i just do not understand how to implement the fact that its supposed to work with a longer array.

CodePudding user response:

I'm not very good at ARM assembly by to my understanding R4 is expected to keep the value of minimum. R8 is used to keep the most recently fetched value from the input array.

The minimum is updated with this instruction:

MOVLE   r8, r4

But it actually updated R8, not R4.

Try:

MOVLE   r4, r8

EDIT

Other issue is using incorrect branch instruction:

SUBS    r1, r1, #1 
BPL     loop1

works like:

r1 = r1 - 1
if (r1 >= 0) goto loop1;

For R1 equal to 1 the loop is exectured twice.

r1 = 1
... do stuff
r1 = r1 - 1 // r1 is 0 now
if (r1 >= 0) goto loop1;     // 0>=0 TRUE!
... do stuff, overflow the input by indexing at `[r0   4]`
r1 = r1 - 1 // r1 is -1
if (r1 >= 0) goto loop1;     // -1 >= 0   FALSE
// exit function

To fix it use branching only when input is non-zero.

BNE loop1

CodePudding user response:

  1. Coding in C use the correct types
  2. You do not have to iterate from the index 0 only 1
int foo(const int *arr, size_t len)
{
    int minarray = arr[0];
    for (size_t i = 1; i < len; i  )
    {
        if (arr[i] < minarray)
        {
            minarray = arr[i];
        }
    }
    return minarray;
}

And it generates this code:

foo:
        mov     r3, r0
        subs    r1, r1, #1
        ldr     r0, [r3], #4
        beq     .L1
.L3:
        ldr     r2, [r3], #4
        cmp     r0, r2
        it      ge
        movge   r0, r2
        subs    r1, r1, #1
        bne     .L3
.L1:
        bx      lr
  • Related