Skip to content

Bài 9: Mảng & Cấu Trúc¤

1. Nhắc lại kiểu dữ liệu cơ bản¤

Kiểu x86-64 32-bit
char 1 1
short 2 2
int 4 4
long 8 4
float 4 4
double 8 8
long double 10/16 —
pointer 8 4

Lưu ý quan trọng: Sự khác biệt lớn nhất giữa 32-bit và 64-bit là kiểu long và pointer — trên 64-bit chúng chiếm 8 bytes thay vì 4.

2. Mảng 1 chiều (1D Array)¤

2.1 Cấp phát mảng¤

Khai báo tổng quát:

C
T A[L];

Ý nghĩa: - T là kiểu dữ liệu phần tử - L là số lượng phần tử - Vùng nhớ được cấp phát liên tục với tổng kích thước = L * sizeof(T) bytes - Định danh A có thể dùng như con trỏ trỏ đến phần tử đầu tiên (A ≡ &A[0])

Ví dụ minh hoạ bộ nhớ:

Text Only
char string[12];   →  chiếm [x, x+12)
int  val[5];       →  chiếm [x, x+20), mỗi phần tử cách nhau 4 bytes
double a[3];       →  chiếm [x, x+24), mỗi phần tử cách nhau 8 bytes
char* p[3];        →  chiếm [x, x+24) trên x86-64 (pointer = 8 bytes)

2.2 Byte Ordering và mảng¤

Định nghĩa

  • Little Endian: byte trọng số thấp nhất nằm ở địa chỉ thấp nhất (x86/x86-64 dùng cách này)
  • Big Endian: byte trọng số thấp nhất nằm ở địa chỉ cao nhất

Byte ordering không ảnh hưởng đến thứ tự các phần tử trong mảng (phần tử index 0 vẫn luôn ở địa chỉ thấp hơn index 1), nhưng ảnh hưởng đến thứ tự các byte bên trong mỗi phần tử có kích thước > 1 byte.

Ví dụ với int array[4] = {1, 5, 3, 7} — giá trị 5 (0x00000005):

Text Only
Little Endian:  05 00 00 00  (byte thấp trước)
Big Endian:     00 00 00 05  (byte cao trước)

2.3 Truy xuất mảng¤

C
int val[5];  // Giả sử địa chỉ bắt đầu là x
// val = {1, 5, 2, 1, 3}
Biểu thức Kiểu Giá trị
val[4] int 3
val int * x
val + 1 int * x + 4
&val[2] int * x + 8
val[5] int undefined (ngoài mảng!)
*(val+1) int 5
val + i int * x + 4*i

Truy xuất ngoài biên

val[5] trên mảng 5 phần tử là undefined behavior — trình biên dịch không báo lỗi nhưng kết quả không dự đoán được. Đây là nguồn gốc của nhiều lỗ hổng bảo mật (buffer overflow).

2.4 Ví dụ bảng truy xuất (IA32)¤

Cho các khai báo sau trong hệ thống 32-bit:

C
char    A[12];
char   *B[8];
double  C[7];
double *D[5];
char  **E[5];
Mảng Địa chỉ phần tử i Địa chỉ bắt đầu Tổng kích thước Kích thước phần tử
A xA + i xA 12 bytes 1
B xB + 4i xB 32 bytes 4 (pointer 32-bit)
C xC + 8i xC 56 bytes 8
D xD + 4i xD 20 bytes 4
E xE + 4i xE 20 bytes 4

2.5 Ví dụ assembly: đọc phần tử mảng¤

C
typedef int zip_dig[5];

int get_digit(zip_dig z, int i) {
    return z[i];
}

Assembly sinh ra (IA32):

GAS
# %edx = z (địa chỉ đầu mảng)
# %eax = i (chỉ số)
movl (%edx, %eax, 4), %eax   # đọc ô nhớ tại địa chỉ z + 4*i

Giải thích: Cú pháp (%edx, %eax, 4) = Mem[%edx + %eax * 4]. Vì mỗi int = 4 bytes, phần tử thứ i nằm cách đầu mảng 4*i bytes.

2.6 Vòng lặp trên mảng¤

Dùng chỉ số (IA32)¤

C
void zincr(zip_dig z) {
    int i;
    for (i = 0; i < 5; i++)
        z[i]++;
}
GAS
# %edx = z
        movl  $0, %eax        # i = 0
        jmp   .L3             # goto kiểm tra điều kiện
.L4:                          # loop:
        addl  $1, (%edx,%eax,4)  # z[i]++  (dùng i tính địa chỉ)
        addl  $1, %eax        # i++
.L3:
        cmpl  $5, %eax        # so sánh i với 5
        jne   .L4             # nếu i != 5, quay lại loop
Câu hỏi: Nếu đổi thành short zip_dig[6], code thay đổi như thế nào?

Có 2 điểm thay đổi:

  • Dòng so sánh: cmpl $5, %eax → cmpl $6, %eax (vì giờ có 6 phần tử)
  • Dòng tăng giá trị: addl $1, (%edx,%eax,4) → addw $1, (%edx,%eax,2) vì:
    • addw thay cho addl (thao tác trên word 2 bytes thay vì dword 4 bytes)
    • Scale factor 4 → 2 (mỗi short chỉ 2 bytes, nên bước nhảy là 2*i)

Dùng con trỏ (IA32)¤

C
void zincr_v(zip_dig z) {
    void *vz = z;
    int dt = 0;
    do {
        (*((int *)(vz + dt)))++;
        dt += 4;
    } while (dt != 4 * 5);
}
GAS
# %edx = z = vz
        movl  $0, %eax          # dt = 0
.L8:
        addl  $1, (%edx,%eax)   # tăng giá trị tại vz+dt
        addl  $4, %eax          # dt += 4
        cmpl  $20, %eax         # so sánh dt với 20 (= 4*5)
        jne   .L8

Khác biệt so với dùng chỉ số: thay vì dùng i để tính 4*i, ta trực tiếp cộng dồn khoảng cách (offset) dt, rồi dùng (%edx, %eax) = Mem[vz + dt].

Câu hỏi: Nếu đổi thành short zip_dig[6]?
  • Dòng so sánh: cmpl $20, %eax → cmpl $12, %eax (vì 2*6 = 12)
  • Dòng tăng offset: addl $4, %eax → addl $2, %eax (bước nhảy = sizeof(short) = 2)
  • Dòng thao tác: addl $1, (%edx,%eax) → addw $1, (%edx,%eax) (thao tác 2 bytes)

Phiên bản x86-64¤

C
void zincr(zip_dig z) {
    size_t i;
    for (i = 0; i < 5; i++)
        z[i]++;
}
GAS
# %rdi = z
        movl  $0, %eax
        jmp   .L3
.L4:
        addl  $1, (%rdi,%rax,4)  # z[i]++
        addq  $1, %rax           # i++ (dùng addq vì i là size_t = 64-bit)
.L3:
        cmpq  $4, %rax           # so sánh với 4 (điều kiện i <= 4 tức i < 5)
        jbe   .L4                # jump if below or equal
        rep; ret

Lệnh jbe (jump if below or equal) dùng cho so sánh unsigned — phù hợp với kiểu size_t không dấu. Đây là điểm khác biệt quan trọng so với jl (signed less than).

2.7 Câu hỏi ôn tập: Mảng 1 chiều¤

Bài tập: Tìm T và N trong hệ 32-bit, biết T A[N] có tổng kích thước 20 bytes

Giải:

Ta có: sizeof(T) * N = 20

Với sizeof(T) ∈ {1, 2, 4, 8} và N là số nguyên dương:

sizeof(T) N Kết luận
1 20 ✅ char A[20]
2 10 ✅ short A[10]
4 5 ✅ int A[5], float A[5], char* A[5] (pointer 32-bit = 4)
8 2.5 ❌ N không nguyên

Đáp án: Ba trường hợp thỏa mãn.

3. Mảng 2 chiều (Nested Array)¤

3.1 Định nghĩa và bố cục bộ nhớ¤

C
T A[R][C];   // R hàng, C cột, mỗi phần tử T chiếm K bytes
  • Tổng kích thước: R * C * K bytes
  • Bố cục: Row-Major Order — các phần tử của cùng một hàng nằm liên tiếp nhau trong bộ nhớ
Text Only
Trong bộ nhớ (int A[3][4]):
A[0][0] A[0][1] A[0][2] A[0][3] | A[1][0] A[1][1] ... | A[2][0] ...
^--- hàng 0 liên tục ---^         ^--- hàng 1 ---^

3.2 Công thức tính địa chỉ¤

Text Only
Địa chỉ A[i][j] = &A + i*(C*K) + j*K
                = &A + (i*C + j)*K

Ví dụ với int pgh[6][5] (tức zip_dig pgh[6]):

C
#define PCOUNT 6
zip_dig pgh[PCOUNT] = {
    {1, 5, 2, 0, 6},
    {1, 5, 2, 1, 3},
    ...
};

Địa chỉ pgh[i][j] = pgh + 20*i + 4*j (vì C=5, K=4, nên C*K=20)

Lấy giá trị phần tử 1 ở hàng 2 cột 3 của pgh?
  • Cú pháp C: pgh[2][3]
  • Địa chỉ: pgh + 2*20 + 3*4 = pgh + 40 + 12 = pgh + 52
  • Nếu pgh bắt đầu tại địa chỉ 76: địa chỉ phần tử = 76 + 52 = 128 ✓

3.3 Truy xuất một hàng¤

Vì A[i] là một mảng con gồm C phần tử kiểu T:

Text Only
Địa chỉ bắt đầu A[i] = &A + i*(C*K)

Khi truyền A[i] vào hàm, ta truyền địa chỉ đầu hàng đó — đây là con trỏ tới phần tử A[i][0].

3.4 Assembly: truy xuất phần tử mảng 2 chiều (IA32)¤

C
int get_pgh_digit(int index, int dig) {
    return pgh[index][dig];
}
GAS
movl  8(%ebp), %eax           # eax = index
leal  (%eax,%eax,4), %eax     # eax = 5*index  (index + 4*index)
addl  12(%ebp), %eax          # eax = 5*index + dig
movl  pgh(,%eax,4), %eax      # đọc pgh + 4*(5*index + dig)

Giải thích từng bước: 1. Load index vào %eax 2. leal (%eax,%eax,4) = eax + 4*eax = 5*index (tính số phần tử tính từ đầu đến hàng index) 3. Cộng thêm dig → 5*index + dig (chỉ số tuyến tính trong mảng 1D) 4. Scale với 4 (sizeof int) và cộng địa chỉ pgh

4. Mảng Nhiều Cấp (Multi-Level Array)¤

4.1 Khái niệm¤

C
int *univ[3] = {mit, cmu, ucb};

Đây không phải mảng 2 chiều thực sự. Cấu trúc:

Text Only
univ[0] → địa chỉ của mit → [0, 2, 1, 3, 9]
univ[1] → địa chỉ của cmu → [1, 5, 2, 1, 3]
univ[2] → địa chỉ của ucb → [9, 4, 7, 2, 0]
  • univ là mảng 3 phần tử, mỗi phần tử là con trỏ (4 hoặc 8 bytes)
  • Mỗi con trỏ trỏ đến một mảng int nằm ở vùng nhớ riêng biệt — không liên tục nhau

4.2 So sánh Nested Array vs Multi-Level Array¤

Cú pháp C A[i][j] giống nhau, nhưng cách tính địa chỉ hoàn toàn khác:

Text Only
Nested Array:     Mem[pgh + 20*index + 4*digit]    → 1 lần đọc bộ nhớ
Multi-Level:      Mem[Mem[univ + 4*index] + 4*digit] → 2 lần đọc bộ nhớ

Assembly cho multi-level (IA32):

GAS
# int get_univ_digit(int index, int digit)
movl  8(%ebp), %eax           # eax = index
movl  univ(,%eax,4), %edx     # edx = univ[index]  ← lần đọc 1: lấy con trỏ
movl  12(%ebp), %eax          # eax = digit
movl  (%edx,%eax,4), %eax     # eax = *(univ[index] + 4*digit)  ← lần đọc 2

Hiệu năng

Multi-level array cần 2 lần truy cập bộ nhớ (2 memory dereferences) so với 1 lần của nested array. Điều này ảnh hưởng đến hiệu năng do cache miss.

5. Ma Trận N×N¤

5.1 Ba cách hiện thực¤

Cách 1: Số chiều cố định (biết tại compile time)¤

C
#define N 16
typedef int fix_matrix[N][N];

int fix_ele(fix_matrix a, size_t i, size_t j) {
    return a[i][j];
}

Địa chỉ a[i][j] = &a + i*(N*4) + j*4 = &a + 64*i + 4*j

GAS
movl  12(%ebp), %edx   # edx = i
sall  $6, %edx         # edx = i*64  (shift left 6 = nhân 2^6 = 64)
movl  16(%ebp), %eax   # eax = j
sall  $2, %eax         # eax = j*4
addl  8(%ebp), %eax    # eax = &a + j*4
movl  (%eax,%edx), %eax # đọc *(a + j*4 + i*64)

Cách 2: Số chiều biến đổi, đánh chỉ số tường minh (cách truyền thống)¤

C
#define IDX(n, i, j) ((i)*(n) + (j))

int vec_ele(size_t n, int *a, size_t i, size_t j) {
    return a[IDX(n, i, j)];
}

Mảng 2D được "giả lập" trên mảng 1D, lập trình viên tự tính chỉ số. Hữu ích khi n chỉ biết lúc runtime.

Cách 3: Số chiều biến đổi, đánh chỉ số ngầm (VLA — Variable Length Array, C99)¤

C
int var_ele(size_t n, int a[n][n], size_t i, size_t j) {
    return a[i][j];
}
GAS
movl  8(%ebp), %eax    # eax = n
sall  $2, %eax         # eax = n*4
movl  %eax, %edx
imull 16(%ebp), %edx   # edx = i*n*4
movl  20(%ebp), %eax   # eax = j
sall  $2, %eax         # eax = j*4
addl  12(%ebp), %eax   # eax = &a + j*4
movl  (%eax,%edx), %eax # đọc *(a + j*4 + i*n*4)

Khác biệt với fix_matrix: phải dùng lệnh imull (nhân nguyên) vì n không biết trước → không thể dùng shift cố định.

6. Bài Tập Tổng Hợp¤

Bài tập 1¤

Xác định M và N của int array[M][N]
GAS
# %ecx = i, %edx = j
movl  $array, %eax
sall  $2, %edx              # edx = 4*j
leal  (%edx, %eax), %eax   # eax = array + 4*j
movl  (%eax, %ecx, 16), %eax  # eax = *(array + 4*j + 16*i)

Từ công thức địa chỉ: array + i*(N*4) + j*4

So sánh với code: array + 16*i + 4*j

→ N*4 = 16 → N = 4

Đáp án: B — N = 4 (M không xác định được từ đoạn code này vì ta không thấy giới hạn vòng lặp)

Bài tập 2¤

Tìm M, N của mat1[M][N] và mat2[N][M]
C
int sum_element(int i, int j) {
    return mat1[i][j] + mat2[j][i];
}
GAS
movl  8(%ebp),  %ecx    # ecx = i
movl  12(%ebp), %edx    # edx = j
leal  0(,%ecx,8), %eax  # eax = 8*i
subl  %ecx, %eax        # eax = 8*i - i = 7*i
addl  %edx, %eax        # eax = 7*i + j   → chỉ số tuyến tính mat1[i][j]
movl  mat1(,%eax,4), %eax  # mat1 + 4*(7*i + j) → N = 7

leal  (%edx,%edx,4), %edx  # edx = 5*j
addl  %ecx, %edx           # edx = 5*j + i  → chỉ số tuyến tính mat2[j][i]
addl  mat2(,%edx,4), %eax  # mat2 + 4*(5*j + i) → M = 5

Phân tích: - mat1[i][j]: chỉ số = 7*i + j → mat1[M][7] → N = 7 - mat2[j][i]: chỉ số = 5*j + i → mat2[7][5] → M = 5

Đáp án: M = 5, N = 7

Bài tập 3¤

Tìm T và N của T A[N][N] trong hệ 32-bit

Cho: &A = 0x1000, &A[2][2] = 0x101C

Giải:

Công thức: &A[2][2] = &A + 2*sizeof(T)*N + 2*sizeof(T)

Text Only
0x101C - 0x1000 = 0x1C = 28 bytes
28 = 2*sizeof(T)*(N + 1)
sizeof(T)*(N+1) = 14

Xét các trường hợp:

sizeof(T) N+1 N Kết luận
1 14 13 ✅ char A[13][13]
2 7 6 ✅ short A[6][6]
4 3.5 — ❌ không nguyên
8 1.75 — ❌ không nguyên

Đáp án: char A[13][13] hoặc short A[6][6]

Tóm tắt công thức cần nhớ

Loại Địa chỉ phần tử
Mảng 1D T A[L] &A + i*sizeof(T)
Mảng 2D T A[R][C] &A + (i*C + j)*sizeof(T)
Multi-level T *A[R] *(A + i*4) + j*sizeof(T) ← 2 lần dereference