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
longvà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:
T A[L];Ý nghĩa:
Tlà kiểu dữ liệu phần tửLlà 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
Acó thể dùng như con trỏ trỏ đến phần tử đầu tiên (A ≡ &A[0])
Ví dụ minh hoạ bộ nhớ:
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
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):
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
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 |
2.4 Ví dụ bảng truy xuất (IA32)
Cho các khai báo sau trong hệ thống 32-bit:
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
typedef int zip_dig[5];
int get_digit(zip_dig z, int i) {
return z[i];
}Assembly sinh ra (IA32):
# %edx = z (địa chỉ đầu mảng)
# %eax = i (chỉ số)
movl (%edx, %eax, 4), %eax # đọc ô nhớ tại địa chỉ z + 4*iGiả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)
void zincr(zip_dig z) {
int i;
for (i = 0; i < 5; i++)
z[i]++;
}# %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 loopCâ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ì:addwthay choaddl(thao tác trên word 2 bytes thay vì dword 4 bytes)- Scale factor
4→2(mỗishortchỉ 2 bytes, nên bước nhảy là2*i)
Dùng con trỏ (IA32)
void zincr_v(zip_dig z) {
void *vz = z;
int dt = 0;
do {
(*((int *)(vz + dt)))++;
dt += 4;
} while (dt != 4 * 5);
}# %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 .L8Khá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
void zincr(zip_dig z) {
size_t i;
for (i = 0; i < 5; i++)
z[i]++;
}# %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; retLệnh
jbe(jump if below or equal) dùng cho so sánh unsigned — phù hợp với kiểusize_tkhông dấu. Đây là điểm khác biệt quan trọng so vớijl(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ớ
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 * Kbytes - 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ớ
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ỉ
Địa chỉ A[i][j] = &A + i*(C*K) + j*K
= &A + (i*C + j)*KVí dụ với int pgh[6][5] (tức zip_dig pgh[6]):
#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
pghbắ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:
Đị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)
int get_pgh_digit(int index, int dig) {
return pgh[index][dig];
}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:
- Load
indexvào%eax leal (%eax,%eax,4)=eax + 4*eax=5*index(tính số phần tử tính từ đầu đến hàngindex)- Cộng thêm
dig→5*index + dig(chỉ số tuyến tính trong mảng 1D) - 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
int *univ[3] = {mit, cmu, ucb};Đây không phải mảng 2 chiều thực sự. Cấu trúc:
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]univlà 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
intnằ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:
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):
# 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 25. 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)
#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
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)
#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)
int var_ele(size_t n, int a[n][n], size_t i, size_t j) {
return a[i][j];
}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]`
# %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]`
int sum_element(int i, int j) {
return mat1[i][j] + mat2[j][i];
}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 = 5Phân tích:
mat1[i][j]: chỉ số =7*i + j→mat1[M][7]→ N = 7mat2[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)
0x101C - 0x1000 = 0x1C = 28 bytes
28 = 2*sizeof(T)*(N + 1)
sizeof(T)*(N+1) = 14Xé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]