Arrays in memory, in one and two dimensions
prerequisite
An array is a list of values of one type stored side by side in memory, with no gaps between them. Each value is an element, and its position in the list is its index, counted from 0. Every element has the same size, so the address of any one of them follows from three numbers: where the array starts, which index you want, and how many bytes one element takes.
Finding element i
The address where an array starts is its base address. Element i sits i elements past the base, so the address of a[i] is base + i * size, where size is the width of one element in bytes. For an int array that starts at 0x1000, a[0] is at 0x1000, a[1] is at 0x1004, and a[5] is at 0x1000 + 5 * 4 = 0x1014.
AArch64 can do that multiply inside the load or store itself, which is called scaling the index. In ldr w2, [x19, w20, SXTW 2], x19 holds the base and w20 holds the index. SXTW means sign-extend word: the 32-bit index is widened to 64 bits, keeping its sign, so it can be added to a 64-bit address. The 2 then shifts the index left by 2 bits, which multiplies it by 4. The shift is the element size written as a power of two:
| element | bytes | shift | load one element |
|---|---|---|---|
| char | 1 | 0 | ldrb w2, [x19, w20, SXTW] |
| short | 2 | 1 | ldrsh w2, [x19, w20, SXTW 1] |
| int | 4 | 2 | ldr w2, [x19, w20, SXTW 2] |
| long or pointer | 8 | 3 | ldr x2, [x19, w20, SXTW 3] |
The shift can only be 0 or the one that matches the size of the load, so the table above is the whole list.
An array in the frame
A local array lives in the frame like any other local; it just takes more room. Eight ints take 8 * 4 = 32 bytes, so the frame size is alloc = -(16 + 32) & -16, which is -48: 16 bytes for the saved fp and lr, then 32 for the array. The array starts at fp + 16, right above the saved pair.
The scaled form needs the base address in a register. add sq_r, fp, sq_s works it out once. It keeps the sum fp + 16, which is the address itself; ldr would instead load the value stored at that address. After that line, every element is one load or store away.
fp + 44 sq[7] ...fp + 24 sq[2]fp + 20 sq[1]fp + 16 sq[0] <- sq_rfp + 8 saved lrfp + 0 saved fp <- fp and spThe program below fills the array with the squares of 0 to 7 in one loop and prints it in a second. It prints eight lines, from sq[0] = 0 to sq[7] = 49. Step through the fill loop and watch x9 take each square just before the str puts it in the array.
note
main keeps its base address and index in x19 and w20 because printf is allowed to change x0 to x18. Short programs like this one let main use x19 to x28 without saving them first. A subroutine you write yourself does not get that freedom: it must save any of x19 to x28 it uses and restore them before it returns.
pitfall
Nothing checks an index. Change b.lt to b.le in the fill loop and it writes a ninth element at fp + 48, which is past the end of this frame and inside the caller's. The program still prints the same eight lines, and the damage shows up later, if at all, far from the line that caused it. Check every loop bound against the array's length.
Two dimensions in one line of memory
Memory is one long row of bytes, so a table with rows and columns has to be laid out flat. Row-major order stores all of row 0, then all of row 1, and so on. In a table with COLS columns, element [row][col] is element number row * COLS + col counted from the start, so its address is base + (row * COLS + col) * size. C stores its 2D arrays this way, and so does every program on this site.
Column-major order is the other choice: it stores all of column 0 first, and the element number becomes col * ROWS + row. Fortran and some math libraries use it. Code that expects one order but is handed the other reads real values from the wrong places.
The same idea stretches to more dimensions. For a[D0][D1][D2], element [i][j][k] is number (i * D1 + j) * D2 + k: each index is multiplied by the sizes of all the dimensions to its right. The first size, D0, never appears in the formula. It only says how many rows there are.
An array in .bss
A table that several parts of a program share, or one too big for a frame, can live in the .bss section instead. .bss holds variables that start out as zero: the program file only records how many bytes to reserve, and those bytes are set to zero when the program starts. .skip ROWS * COLS * 4 reserves 4 * 5 * 4 = 80 bytes. .align 4 before it starts the table at an address that is a multiple of 16, because .align counts in powers of two and 2 to the 4th is 16. ldr grid_r, =grid then puts the table's address in a register, the same way ldr x0, =fmt does for a format string.
The program below fills a 4 by 5 table in .bss with row * 10 + col, so each value spells out its own position. The fill loops find each element by row and column: madd (multiply and add: madd w10, row_r, w9, col_r sets w10 = row_r * w9 + col_r) gives the element number, and the scaled store multiplies it by 4.
The print loop ignores rows and columns. It starts a pointer at the first byte and moves it 4 bytes after each value (ldr w1, [ptr_r], 4, the post-index form), and starts a new line whenever the count of values printed is a multiple of 5 (the remainder comes from sdiv and msub). The rows still come out in order, 0 to 3, because the table really is stored one whole row after another. The last line picks out one element with an offset the assembler works out from the formula, (2 * 5 + 3) * 4 = 52. The program prints:
0 1 2 3 4 10 11 12 13 14 20 21 22 23 24 30 31 32 33 34grid[2][3] = 23, at byte offset 52note
In the print loop, w9 and w10 only hold a value between one call and the next, because printf is allowed to change them. The pointer and the count must last across every call, so they live in ptr_r and k_r (x20 and w21).
pitfall
Common mistakes from this lesson, each with a broken program and its fix that you can run:
Check yourself
- An array of 10 longs starts at
0x2000. Where does element 7 start? - Which shift goes with
ldrshin the scaled form? - A row-major table of ints has 6 columns. What is the byte offset of element
[3][4]? - Change
ROWSto 3 in the grid program. Why does the last line stay the same?
answers
show answers
0x2000 + 7 * 8 = 0x2038.- 1, because a short is 2 bytes, and 2 is 2 to the power 1.
(3 * 6 + 4) * 4 = 88.- The offset of
[2][3]depends on the number of columns, not rows. Only three rows print now.
Practice
- Sum a global array, Min-max tournament, Bubble up the order and The multiplication table: programs that walk an array.
- Rotate by k: rotate a word array in place by any number of places.
- Tic-tac-toe judge: a 3 by 3 board stored row after row, one byte per cell.
- Basic quiz: arrays and structures, then core and challenge: element addresses and row-major order.
- Fill in the blank: arrays and structures (core) and Predict: arrays and structures (challenge): the scaled loads and the offsets they reach.