Basic 1D Implementation
A 1-dimensional array can be easily implemented as a region of memory with items at consecutive addresses. This way, an item can be identified by the array’s base address and an offset determined by the index
array DEFB ...
MOV R1, #2
ADR R2, array
LDRB R3, [R2, R1]Bounds Checking
For a given array access, the index may not be known at compile-time. For this reason, it is unknown whether it is a valid index for the size of the array. To prevent hard-to-trace errors resulting from out-of-bounds array access, the index can be checked at runtime:
CMP R1, #N ; N is the length of the arary. This *must* be known.
BGE Error
CMP R1, #0
BLT Error ; Negative indices are not allowed either.
LDR R3, [R2, R1, LSL #2]This overhead can be costly in performance. If an index is known at compile time, or is known to be within the bounds, then this step can be skipped.
Arrays of Complex Objects
It is not sufficient to be limited to arrays with elements of a fixed size. To allow arrays of complex objects, such as strings, each element of the array contains the address of the start of the data.
Multi-Dimensional Arrays
There are several ways to implement multi-dimensional arrays.
Contiguous Storage
Given a 2D array A of size (M, N), the offset from the base address to access element A[x][y] is x + (M * y).
This is an example of the “column-major” format, however other implementations may use a different order of rows and columns.
Nested Arrays
An alternative method is to create a Basic 1D Implementation array, where each element is a pointer to the next-level array. This method requires more memory accesses, as to access an element in an n-dimensional array, n memory operations are required.