How are multidimensional arrays laid out in memory?

C stores 2D arrays in row-major order — one whole row laid out contiguously, then the next — so arr[i][j] lives at base + (i*N_cols + j)*sizeof(elem).

* Row-major: row 0 is laid out fully, then row 1, then row 2 — so arr[i][j] sits at base + (i·cols + j)·size. *

Declaration:

// 3 rows, 4 columns
int arr[3][4];
// Type: "array of 3 arrays of 4 ints"

Memory layout (row-major):

arr[0][0] arr[0][1] arr[0][2] arr[0][3] arr[1][0] arr[1][1] ...
|---------- row 0 -----------|---------- row 1 ---------|

Size calculation:

• One element: sizeof(int) = 4 bytes
• One row: 4 * sizeof(int) = 16 bytes
• Entire array: 3 * 4 * sizeof(int) = 48 bytes

Address calculation for arr[i][j]:

address = base + (i * N_cols + j) * sizeof(element)
// Or equivalently:
address = base + i * sizeof(row) + j * sizeof(element)

Example: For int arr[3][4] at address 1000:

arr[2][1] = 1000 + (2 * 4 + 1) * 4 = 1000 + 36 = 1036

Key insight for reverse engineering:

• To find arr[i][j], compiler only needs N_cols, not N_rows
• The formula i * N_cols + j appears in assembly
• Look for multiply-add patterns: lea (%rdi,%rsi,4), %rax

Contrast with pointer-to-pointer:

// Pointer to pointer - NOT a 2D array!
int **p;
// True 2D array - contiguous memory
int arr[3][4];

Go deeper:

• Row- and column-major order — Wikipedia — the two array layouts and their cache implications.