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.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"
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
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