Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 40 ยท Arrays, Strings and Structs

Arrays and Addressing Modes

Learn the x86-64 address form base + index*scale + displacement, how a[i] and 2D arrays compile, why scales stop at 8, and pointer walking versus indexing.

An array is just consecutive elements in memory, so reaching element i means computing an address: start of the array plus i times the element size. Doing that with separate imul and add instructions would be slow and bulky, so the x86 designers built the calculation into the memory operand itself. One instruction can say "load the 4 bytes at base plus 4 times index", and the address unit of the CPU does the arithmetic for free.

This lesson covers that general address form, how C array indexing turns into it, how two-dimensional arrays are laid out in row-major order, and the two classic loop styles: indexing and pointer walking. If you want to refresh what a memory operand is first, see Memory, Addresses and Endianness and MOV, LEA and Moving Data.

The effective address

A memory operand in x86-64 has up to four parts:

TEXT
[ base + index * scale + displacement ]
  • base: any 64-bit general-purpose register (often the array pointer);
  • index: another register, any except rsp (often the loop counter);
  • scale: 1, 2, 4 or 8, a constant written into the instruction;
  • displacement: a constant, signed 8-bit or 32-bit.

Every part is optional, but there must be at least one. The number the CPU computes is called the effective address. All of these are legal:

NASM
mov eax, DWORD PTR [rdi]              ; just a base
mov eax, DWORD PTR [rdi+16]           ; base + displacement
mov eax, DWORD PTR [rdi+rsi*4]        ; base + index * scale
mov eax, DWORD PTR [rdi+rsi*4+16]     ; all four parts
mov eax, DWORD PTR [rip+counter]      ; rip-relative (global variable)

(DWORD PTR is Intel-syntax wording for "4 bytes", GCC output uses QWORD PTR for 8, WORD PTR for 2, and BYTE PTR for 1.)

flowchart LR
  B["base register"] --> ADD["effective address"]
  I["index register"] --> M["times scale 1, 2, 4 or 8"]
  M --> ADD
  D["displacement constant"] --> ADD
  ADD --> MEM["memory access of 1, 2, 4 or 8 bytes"]

The address unit adds the parts together; a plain mov then reads or writes memory at that address.

The scale is limited to 1, 2, 4 and 8 because those are the sizes of the common integer and floating-point types: char, short, int/float, long/double/pointers. If your elements are 12 bytes, as in a struct of three ints, no single scale fits. The compiler then multiplies the index separately. A neat way is lea, which does address math without touching memory:

NASM
lea rax, [rcx+rcx*2]                  ; rax = 3 * i
mov edx, DWORD PTR [rsi+rax*4]        ; element at base + 12 * i

Here 3*i comes from rcx + rcx*2, and the load applies the remaining factor of 4. For larger sizes imul rax, rcx, 40 is also normal. The next lesson on strings uses scale 1, the byte-sized case.

How a[i] compiles

Take this C function:

C
int get(const int *a, long i) { return a[i]; }

Under the System V ABI the pointer a arrives in rdi and i in rsi. At -O2 GCC produces:

NASM
get:
    mov eax, DWORD PTR [rdi+rsi*4]    ; a + i * sizeof(int)
    ret

The whole index calculation is inside the load. The result goes to eax (not rax), because the function returns an int and a 32-bit write also clears the upper half, as the x86-64 registers lesson explained. If i were a 32-bit int, the compiler would first have to sign-extend it with movsxd rsi, esi, since the index register is a full 64 bits.

C's rule that a[i] is exactly *(a + i) makes this natural: pointer arithmetic in C already scales by the element size, which is precisely the scale field. If you want the C-level view, read Pointers and Arrays and Pointer Arithmetic.

Indexing versus pointer walking

There are two natural ways to loop over an array. Both appear in compiler output, often for the same C source.

Indexing keeps a base register fixed and a counter that increments; each access uses [base + counter*scale].

Pointer walking keeps a single pointer that moves forward by the element size each iteration, and stops when it reaches an end pointer computed once before the loop with lea. Typical optimized output for summing an int array looks like this (a shape GCC commonly uses at -O1, details vary):

NASM
sum:                                 ; long sum(const int *a, long n)
    test rsi, rsi
    jle  .Lempty
    lea  rdx, [rdi+rsi*4]            ; end pointer = a + n
    mov  eax, 0
.Lloop:
    movsxd rcx, DWORD PTR [rdi]      ; sign-extend each int to 64 bits
    add  rax, rcx
    add  rdi, 4                      ; advance one element
    cmp  rdi, rdx
    jne  .Lloop
    ret
.Lempty:
    mov  eax, 0
    ret

Pointer walking saves one register and one instruction (no separate counter), but modern compilers choose whichever is faster for the target, and at -O3 they usually vectorize the whole thing, as we will see in Floating Point and SIMD.

The first demo uses a small toy CPU, a JavaScript interpreter with byte-addressable memory and Intel-style operands including the full [base + index*scale + disp] form. Its cmp simply remembers both numbers and the jumps compare them, which is a simplification of the real flags (see Flags). Registers hold plain JavaScript numbers. The program sums eight 4-byte integers at address 0x40, once by indexing and once by pointer walking, then doubles every element in place and reports where the last one lives.

JS Sum an array: indexing versus pointer walking

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Both sums print 31 (3+1+4+1+5+9+2+6). The lea rdx, [rsi+28] line computes 0x40 + 28 = 0x5c without reading memory, which is the "address arithmetic" use of lea; the following mov then reads the doubled value 12 from that address.

Two-dimensional arrays

C stores int m[3][4] as one flat block of 12 ints, row-major: row 0 first (all four columns), then row 1, then row 2. The address of m[r][c] is

TEXT
address = base + (r * columns + c) * element_size

This is why C requires every dimension except the first in a parameter type: int m[][4]. The compiler needs the column count to know how far to jump per row. A function reading one element:

C
int at(int m[][4], long r, long c) { return m[r][c]; }

compiles at -O2 to something like this (m in rdi, r in rsi, c in rdx):

NASM
at:
    lea eax, [rdx+rsi*4]               ; r * 4 + c    (4 = number of columns)
    cdqe                               ; sign-extend eax into rax
    mov eax, DWORD PTR [rdi+rax*4]     ; load the element
    ret

Compilers vary here (some skip the cdqe and use a 64-bit lea), but the structure is always the same: one multiply-add for the flattened index, then a scaled load. The demo below computes the same addresses by hand and shows why the loop order matters for caches: moving along a row steps by 4 bytes, but moving down a column steps by a whole row (16 bytes here, and thousands in real matrices).

JS Row-major addresses and strides

Press Run (or Ctrl + Enter) to see the console output here.

No output.

For m[2][3] the flat index is 11 and the byte offset 44, so the address is 0x102c. Indexing a 3-D array adds one more multiply: (i * planes + j) * cols + k.

When you read compiler output and see an odd constant in lea or imul just before a scaled load, ask "what is the row length?" That constant is usually the number of columns, or the size of a struct (see Structs, Padding and Alignment).

Addressing mode odds and ends

  • No memory-to-memory operations. An instruction may have at most one memory operand, so copying an element needs a register in between.
  • rsp cannot be an index, though it can be a base ([rsp+8] is how locals appear in code without a frame pointer; see Stack Frames).
  • Displacements add up with base and index, so [rbx+rcx*8+16] reaches the third field of the rcx-th 8-byte record, which is also how a field inside an array element is reached.
  • lea is not a load. It computes the effective address and stores that number in a register, which makes it a cheap way to compute a + b*4 + 7, which has nothing to do with memory.
  • Bounds are your problem. The CPU happily computes [rdi + 1000000*4]; nothing checks the array length. Reading or writing past the end is how many security bugs start, as discussed in Security: Buffer Overflows and Defenses.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which instruction loads the 4-byte int a[i], with a in rdi and i in rsi?

    The scale applies to the index register, so the address is base + index * 4. The scale cannot be applied to the base, and omitting the scale would step one byte per element.
  2. 2. Which scale values can an x86-64 memory operand use?

    The encoding has two bits for the scale, giving 1, 2, 4 or 8. Other element sizes need an extra lea or imul to compute the offset.
  3. 3. In an int m[3][4] array stored row-major, what is the byte offset of m[2][1] from the start?

    Offset = (row * columns + column) * element size, with 4 columns and 4-byte ints. That is (2*4+1)*4 = 36.
  4. 4. What does lea rdx, [rsi+28] do?

    lea means load effective address: it performs only the address arithmetic and writes the result into the register. No memory is read or written.

Summary

  • A memory operand has the form [base + index*scale + displacement]; the CPU computes the effective address for free inside one instruction.
  • Scale is 1, 2, 4 or 8, matching the common element sizes; other sizes use lea or imul first.
  • a[i] in C becomes a scaled load such as mov eax, [rdi+rsi*4].
  • Multi-dimensional C arrays are row-major: address = base + (r * columns + c) * size.
  • Loops either index with a counter or walk a pointer to an end pointer; compilers pick the faster shape.
  • lea does address arithmetic without touching memory, and nothing in hardware checks array bounds.

Next: Strings and Byte Processing, where the element size is one byte and the loop ends at a zero.