这篇文章是csapp第三章第8和第9节的阅读笔记。

接下来，从汇编代码的角度来看看C语言中数据结构的实现。

0x00 Array

先看看数组。

1.1 基本规则

对于具有N个类型T的元素的数组来说，C语言中是这么声明的：

T A[N];

令Xa为这个数组的起始地址，这样的声明有两个效果：

• 声明一个连续的内存，大小是L·N个字节，其中L是类型T的大小；
• 引入一个标识符A，可以用作这个数组的起始的地址，值就是Xa。

对于数组中的元素，可以通过起始地址Xa，以及范围是0到N-1的下标i来获取，这个元素的地址就是Xa+L·i。

还可以声明元素是指针的数组：

char* B[8];

这时T就是char*，L就是8，因为指针的大小是8 bytes。整个数组所占的连续内存大小是64 bytes。

1.2 指针的算术运算

C语言允许对指针的算术运算，包括加减。

不过每次加减的值都是L的倍数，如果p是类型T的指针，p的值是Xp，那么表达式p+i的值就是Xp+L·i。

下面是一些常见的指针算术运算，其中E的起始地址和下标i分别存在%rdx和%rcx中，计算的结果存在%eax（数据）或%rax（指针）中：

1.3 嵌套数组

数组中的元素还可以是一个数组，构成一个多维数组或嵌套数组。

比如：

int A[5][3];

可以表示成：

typedef int row3_t[3];
row3_t A[5];

构成一个5行3列的数组。

对于下面的二维数组来说（起始地址是Xd）：

T D[R][C];

元素D[i][j]的地址就是Xd+L(C·i+j)。

看一个例子：

#define:

long P[M][N];
long Q[N][M];

long sum_element(long i, long j) {
    return P[i][j] + Q[j][i];
}

编译之后的结果：

sum_element:
    leaq    0(, %rdi, 8), %rdx        ; Compute 8i
    subq    %rdi, %rdx                ; Compute 7i
    addq    %rsi, %rdx                ; Compute 7i + j
    leaq    (%rsi, %rsi, 4), %rax    ; Compute 5j
    addq    %rax, %rdi                ; Compute 5j + i
    movq    Q(, %rdi, 8), %rax        ; Retrieve M[Xq + 8 (5j + i)]
    addq    P(, %rdx, 8), %rax        ; Add M[Xp + 8 (7i + j)]
    ret

所以，M就是5，N就是7。

1.4 固定大小的数组

C编译器会对多维数组进行很多优化，可以使用-O1选项来指定。

比如下面的多维数据：

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

编译器可以通过对指针的解引用来访问数据元素。

/* Compute i,k of fixed matrix product */
int fix_prod_ele(fix_matrix A, fix_matrix B, long i, long k) {
    long j;
    int result = 0;
    for (j = 0; j < N; j++) {
        result += A[i][j] * B[j][k];p
    }
    return result;
}

编译后的代码：

fix_prod_ele:
    salq    $6, %rdx                ; Compute 64 * i
    addq    %rdx, %rdi                ; Compute Aptr = Xa + 64i = &A[i][0]
    leaq    (%rsi, %rcx, 4), %rcx    ; Compute Bptr = Xb + 4k = &B[0][k]
    leaq    1024(%rcx), %rsi        ; Compute Bend = Xb + 4k + 1024 = &B[N][k]
    movl    $0, %eax                ; Set result = 0
.L7:                                ; loop:
    movl    (%rdi), %eax            ; Read *Aptr
    imull    (%rcx), %eax            ; Multiply by *Bptr
    addl    %edx, %eax;                ; Add to result
    addq    $4, %rdi                ; Increment Aptr ++
    addq    $64, %rcx                ; Increment Bptr += N
    cmpq    %rsi, %rcx                ; Compare Bptr:Bend
    jne        .L7                        ; If !=, goto loop
    rep; ret                        ; Return

翻译成C代码：

int fix_prod_ele_opt(fix_matrix A, fix_matrix B, long i, long k) {
    int *Aptr = &A[i][0];            /* Points to elements in row i of A */
    int *Bptr = &B[0][k];            /* Points to elements in column k of B */
    int *Bend = &B[N][k];            /* Marks stopping point for Bptr */
    int result = 0;
    do {                            /* No need for initial test */
        result += *Aptr * *Bptr;    /* Add next product to sum */
        Aptr++;                        /* Move Aptr to next column */
        Bptr += N;                    /* Move Bptr to next row */
    } while (Bptr != Bend);            /* Test for stopping point */
    return result;
}

1.5 可变大小数组

C语言支持多位数组的大小在编译期间确定，比如：

int A[expr1][expr2];

不过需要使用者自己通过malloc或calloc等函数申请内存，然后安排多维数组的存储形式。

比如下面的函数：

int var_ele(long n, int A[n][n], long i, long j) {
    return A[i][j];
}

参数n需要在参数A前面。

编译后：

var_ele:
    imulq    %rdx, %rdi                ; Compute n * i
    leaq    (%rsi, %rdi, 4), %rax    ; Compute Xa + 4(n*i)
    movl    (%rax, %rcx, 4), %eax    ; Read from M[Xa+4(n*i)]
    ret

这里在计算n*i时使用了乘法，这是和固定大小的数组不一样的地方。

如果启用优化的话，如果程序中使用了多维数组，gcc可以避免通过乘法操作来获取元素，要么直接获取到指定元素的地址，要么通过一维数组的方式来获取指定元素，这两种方式都可以提高性能。

0x01 异质数据结构

C中还提供了两种结构：struct和union。

1.1 Struct

比如下面的结构体：

struct rec {
    int i;
    int j;
    int a[2];
    int *p;
};

布局如下：

  offset:      0     4     8         16         24
              |---|---|---|---|-------|
contents:    |i    |j    |a0    |a1    |p        |
            |---|---|---|---|-------|

为了访问struct中的元素，编译器直接通过对struct的指针加上待访问成员的offset即可。

比如r是rec*类型的变量且存在%rdi中，那么下面的语句就是将r->i赋值给r->j：

movl    (%rdi), %eax    ; Get r->i
movl    %eax, 4(%rdi)    ; Store in r->j

再看一个复杂的例子：

r->p = &r->a[r->i + r->j];

汇编代码（r存在%rdi中）：

movl    4(%rdi), %eax            ; Get r->j
addl    (%rdi), %eax            ; Add r->i
cltq                            ; Extend to 8 bytes
leaq    8(%rdi, %rax, 4), %rax    ; Compute &r->a[r->i + r-> j]
movq    %rax, 16(%rdi)            ; Store in r->p

也就是说，对结构体成员的访问都是在编译期间完成的，机器码完全不知道和结构体有关的信息。

1.2 Union

union和struct类似，但也有很大的不同。比如：

struct S3 {
    char c;
    int i[2];
    double v;
};

union U3 {
    char c;
    int i[2];
    double v;
};

虽然成员都一样，但是它们每个成员的offset却不同：

union在一些场景下有用，但大多数情况只会带来讨厌的bug。

关于union就这样吧，也不咋用。

1.3 Data Alignment

struct中的数据是需要对齐的，而不是紧密排列的。

比如：

struct S1 {
    int i;
    char c;
    int j;
};

实际的布局是这样的：

  offset:     0     45     8     12
              |---|---|---|
  contents:    |i    |c    |j    |
              |---|---|---|

c后面进行了填充，为了补齐4个字节。

即使c放在最后面，也需要进行对齐，这是为了方便数组访问（这个struct作为元素类型）。

为了高效地访问内存，会对struct的布局进行对齐，对齐的规则如下：

对于是K字节的基本类型对象来说，它的地址一定要是K的倍数。

其中K的取值如下：

给出一些对齐的例子：

A. struct P1 {short i; int c; int *j; short *d;};

B. struct P2 {int i[2]; char c[8]; short d[4]; long *j;};

C. struct P3 {long w[2]; int *c[2]};

D. struct P4 {char w[16]; char *c[2]};

E. struct P5 {struct P4 a[2]; struct P1 t};