Skip to main content

Section 15.1 Arrays

An array in C/C++ consists of one or more elements, all of the same data type, arranged contiguously in memory. An example is the C-style text strings we have been using in the past few chapters. So far, we have been accessing the elements sequentially, one immediately after the other. This array processing only requires the address of the beginning of the array.

To access a single element in an array we need to specify two address-related items:

  • The beginning of the array.

  • The number of the element to access.

For example, given the declaration in C:

int array[50];

you can store an integer, say \(123\text{,}\) in the \(i-th\) element with the statement

array[i] = 123;

In this example the beginning of the array is specified by using the name, and the number of the element is specified by the [...] syntax. The program in Listing 15.1.1 shows how to access each element in an array directly, both storing a value and reading it.

/* printArray1.c
 * Stores index number in each element of array
 * and prints the array.
 * 2017-09-29: Bob Plantz
 */
#include <stdio.h>

int main(void)
{
  int intArray[10];
  register int index;
   
  for (index = 0; index < 10; index++)
    intArray[index] = index;
    
  for (index = 0; index < 10; index++)
    printf("%i\n", intArray[index]);
  return 0;
}
Listing 15.1.1. Filling an array and printing it. (C)

Listing 15.1.2 shows a way to access array elements in assembly language.

        .arch armv6
        .file   "printArray1.c"
        .section  .rodata
        .align  2
.LC0:
        .ascii  "%i\012\000"
        .text
        .align  2
        .global main
        .syntax unified
        .arm
        .fpu vfp
        .type   main, %function
main:
        @ args = 0, pretend = 0, frame = 40
        @ frame_needed = 1, uses_anonymous_args = 0
        push    {r4, fp, lr}
        add     fp, sp, #8
        sub     sp, sp, #44
        mov     r4, #0          @@ index = 0;
        b       .L2
.L3:
        lsl     r3, r4, #2      @@ 4 * index
        sub     r2, fp, #12     @@ address of end of array
        add     r3, r2, r3      @@ index-th element beyond end
        str     r4, [r3, #-40]  @@ minus length of array
        add     r4, r4, #1      @@ index++
.L2:
        cmp     r4, #9          @@ check for end
        ble     .L3
        mov     r4, #0
        b       .L4
.L5:
        lsl     r3, r4, #2
        sub     r2, fp, #12
        add     r3, r2, r3
        ldr     r3, [r3, #-40]
        mov     r1, r3
        ldr     r0, .L7
        bl      printf
        add     r4, r4, #1
.L4:
        cmp     r4, #9
        ble     .L5
        mov     r3, #0
        mov     r0, r3
        sub     sp, fp, #8
        @ sp needed
        pop     {r4, fp, pc}
.L8:
        .align  2
.L7:
        .word   .LC0
        .ident  "GCC: (Raspbian 6.3.0-18+rpi1) 6.3.0 20170516"
Listing 15.1.2. Filling an array and printing it. (gcc asm)

In the code sequence:

mov     r3, r4, asl #2  @@ 4 * index
sub     r2, fp, #12     @@ address of end of array
add     r3, r2, r3      @@ index-th element beyond end
str     r4, [r3, #-40]  @@ minus length of array

the number of bytes from the beginning of the array to specified element is computed by multiplying the index number by four. Next, the address of the end of the array is computed. The byte offset of the specified element is added to the address of the end of the array, which leaves r3 pointing to an address beyond the end of the array. Storing the value (index number in this program) uses a negative offset equal to the total length (in bytes) of the array. So the net result is that the value is stored in the proper location in the array.

I do not know why the compiler writer decided to use this algorithm to access an array. I have used a more direct approach in Listing 15.1.3

@ printArray2.s
@ Stores index number in each element of array
@ and prints the array.
@ 2017-09-29: Bob Plantz

@ Define my Raspberry Pi
        .cpu    cortex-a53
        .fpu    neon-fp-armv8
        .syntax unified         @ modern syntax

@ Constants for assembler
        .equ    nElements,10    @ number of elements in array
        .equ    intArray,-52    @ array beginning
        .equ    decString,-68   @ for decimal text string
        .equ    locals,56       @ space for local vars

@ The program
        .text
        .align  2
        .global main
        .type   main, %function
main:
        sub     sp, sp, 16      @ space for saving regs
        str     r4, [sp, 0]     @ save r4
        str     r5, [sp, 4]     @      r5
        str     fp, [sp, 8]     @      fp
        str     lr, [sp, 12]    @      lr
        add     fp, sp, 12      @ set our frame pointer
        sub     sp, sp, locals  @ for the array
        
        add     r4, fp, intArray  @ address of array beginning
        mov     r5, 0           @ index = 0;
fillLoop:
        cmp     r5, nElements   @ all filled?
        bge     allFull         @ yes
        lsl     r0, r5, 2       @ no, offset is 4 * index
        str     r5, [r4, r0]    @ at index-th element
        add     r5, r5, 1       @ index++;
        b       fillLoop
allFull:
        add     r4, fp, intArray  @ address of array beginning
        mov     r5, 0           @ index = 0;
printLoop:
        cmp     r5, nElements   @ all filled?
        bge     allDone         @ yes
        lsl     r0, r5, 2       @ no, offset is 4 * index
        ldr     r1, [r4, r0]    @ get index-th element
        add     r0, fp, decString  @ to store decimal string
        bl      uIntToDec       @ convert it
        add     r0, fp, decString  @ get decimal string
        bl      writeStr        @ write it
        bl      newLine
        add     r5, r5, 1       @ index++;
        b       printLoop
allDone:
        mov     r0, 0           @ return 0;
        add     sp, sp, locals  @ deallocate local var
        ldr     r4, [sp, 0]     @ restore r4
        ldr     r5, [sp, 4]     @      r5
        ldr     fp, [sp, 8]     @         fp
        ldr     lr, [sp, 12]    @         lr
        add     sp, sp, 16      @ restore sp
        bx      lr              @ return
Listing 15.1.3. Filling an array and printing it. (prog asm)

In my algorithm I use r4 as the base register to hold the address of the beginning of the array and r5 to maintain the array element number (index):

add     r4, fp, intArray  @ address of array beginning
mov     r5, 0           @ index = 0;

It is then a simple matter to access any element of the array by computing the byte offset from the beginning of the array, storing this value in a register, and using the register addressing mode (Section 11.1):

lsl     r0, r5, 2       @ no, offset is 4 * index
str     r5, [r4, r0]    @ at index-th element