1. 数组
2. 结构
3. 联合
4. 数据对齐

数组

1. 分配N个T类型大小的连续空间
2. 指向这个连续空间的第一个T类型大小的指针叫做A, A中的地址就是这个数组的第一个元素. 按照索引往后查找的时候, 只需要用地址加上偏移量乘以T的大小, 就是索引为偏移量的元素位置.

练习题 3.36

练习题 3.37

1. 由于i表示行号, 所以先定位到i行的起始地址, 可以用xd加上i乘以一行的长度, 一行的长度是C * L, 则第i行的起始地址是 xd + i * C * L
2. 之后需要根据j来定位具体元素, 所以再从起始地址加上j*L即可.
3. 最终的地址就是 xd + i * C * L + j * L = xd + L * (i * C + j)

练习 3.38 根据汇编倒推P和Q两个二维数组的列和行

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

i in %rdi, j in %rsi

sum_element:
    leaq   0(,%rdi, 8),  %rdx       %rdx = 8i
    subq   %rdi, %rdx               这个是计算 %rdx - i = 7i
    addq   %rsi, %rdx               这个是计算 %rdx = 7i+j
    leaq   (%rsi, %rsi, 4), %rax    %rax = 5j
    addq   %rax, %rdi               %rdi = i + 5j
    movq   Q(, %rdi, 8), %rax       取地址是 (5j+i)*8 + Q, 可见对于Q来讲, 每行元素的数量为5, 所以M = 5
    movq   P(, %rdx, 8), %rax       取地址是 (7i+j)*8 + P, 可见对于P来讲, 每行元素是7, 所以N = 7

结构

练习题 3.41 根据结构的声明回答问题

struct prob {
    int *p;
    struct {
        int x;
        int y;
    } s;
    struct prob *next;
};

1. A 下列字段的偏移量是多少:
   1. p: 由于指针p是这个结构的第一个元素, 偏移量就是0
   2. s.x: 可以看到, s.x是紧接在p之后的结构内的第一个元素, 所以偏移量是8
   3. s.y: 知道了s.x的偏移量是8, x的长度是4, 所以s.y是偏移量是12
   4. next: y的偏移量是12, y的长度是4, 所以next的偏移量是16
2. 结构所需的总字节数是 8+4+4+8 = 24字节
3. 根据汇编代码填写C代码:

               void sp_init(struct prob *sp)
               sp in %rdi
               sp_init:
                   movl 12(%rdi), %eax     取偏移量为12的4字节值到%eax中, 偏移量12的值是y
                   movl %eax, 8(%rdi)      将y写入到偏移量为8开始的四字节中, 所以前两句是 sp->s.x = sp->s.y
                   leaq 8(%rdi), %rax      %rax中的值是 sp->s.x 的地址
                   movq %rax, (%rdi)       这其实是 sp->p = &(sp->s.x)
                   movq %rdi, 16(%rdi)     这其实是把sp->next = sp
   

   补完之后的代码是:

               void sp_init(struct prob *sp){
                   sp->s.x = sp->s.y;
                   sp->p = &(sp->s.x);
                   sp->next = sp;
               }
   

练习题 3.42 根据汇编代码写出C语言

struct ELE {
    long v;
    struct ELE *p;
}

long fun(struct ELE *ptr)
prt in %rdi

fun:
    movl   $0, %eax         %rax清零, 可能是为返回值做准备
    jmp    .L2              无条件跳转.L2, 可能是循环开始
  .L3:
    addq   (%rdi), %rax     将 v 加到 %rax上
    movq   8(%rdi), %rdi    将ptr->next更新到 %rdi中
  .L2:
    testq  %rdi, %rdi       无条件跳转到的标号, 进去看是测试 %rdi
    jne    .L3              如果不是0, 则跳转L3, 至此可以知道这是一个while(ptr!=0)的循环, 循环体是 L3
    rep; ret                如果测试失败, 返回此时的%rax中的0.

long fun(struct ELE *ptr){
    long result = 0;
    while(ptr!=NULL){
        result += ptr->v;
        ptr= ptr->p;
    }
    return result;
}

联合

练习题 3.43 将操作写成汇编代码

typedef union {
    struct {
        long u;
        short v;
        char w;
    } t1;
    struct {
        int a[2];
        char *p;
    } t2;
} u_type;

void get(u_type *up, type *dest){
    *dest = expr;
}

1. up->t1.u, 这个是取struct1的开始元素, 很显然类型是long, 指针肯定就是up, 取8个字节即可, 汇编指令是

           movq  (%rdi), %rax
           movq  %rax , (%rsi)
   

2. up->t1.v, 这个是取t1.v, 前边有一个long元素, 很显然偏移量是8 , 类型是short ,所以可以写:

            movl $0 %eax
            movw 8(%rdi), %ax
            movw %ax, (%rsi)
   

3. &up->t1.w, 这个是取t1.w的地址, 这里不考虑对齐, 偏移量应该是8+2 =10, 显然结果也是一个指针, 所以可以写成, 类型是char*, 也就是一个指针

           movl $0, %eax          寄存器清0
           leaq 10(%rdi), %rax
           movl %rax , (%rsi)
   

4. up->t2.a, 这个也是取首地址, 但是类型是一个指针, 而不是数组首个元素

           movq %rdi, (%rsi)    直接把指针赋给*dest
   

5. up->t2.a[up->t1.u], 这个实际上是先取到t2.a的地址, 然后用指针加上t1.u的值, 取其中的值, 再把值复制给指针指向的地方,最后用指针从a数组中取数, 类型是int

           movq (%rdi), %rax   把t1.u的值装入%eax
           movl (%rdi, %rax,4), %eax     把t1.u的值乘以4,加上首地址的值, 得到实际的地址值, 在取值放入%eax中
           movl %eax, (%rsi)   把%eax的值赋值给%rsi间接引用.
   

6. *up->t2.p, 这个实际上是先取到t2.p这个指针, 然后使用间接引用, 再赋给dest. t2.p的偏移应该是8. 而类型是char

               movl $0, %eax
               movq 8(%rdi), %rax   把偏移量+8的地址放入%rax
               movb (%rax), %al     取到char*指向的字节值, 放入%ax寄存器
               movb %al , (%rsi)
   

数据对齐

练习 3.44 确定每个字段的偏移量, 结构总大小 和 X86-64下的对齐要求

1. struct P1 {int i; char c; int j; char d;}, 大小分别为4,1,4,1 但要保证int j也要对齐4位, 因此实际分配的字节是4,4,4,4, 结构大小是16个字节.
2. struct P2 {int i; char c; char d; long j;}, 大小分别是4,1,1,8, 注意8要对齐到8的倍数, 所以 可能的分配是 4,2,2,8, 这样下一个结构依然可以对齐. 两个char可以挨着,之后有两字节的空白.
3. struct P3 {short w[3]; char c[3]}, 第一个元素是3个2字节的长度, 之后是3个1字节的长度, 注意 2的要对齐到2字节, 很显然在6个分配之后, 还有3个字节,一共9字节, 所以末尾要有一个空白字节, 结构实际长度为10字节, 这样就可以保证short以2对齐.
4. struct P4 {short w[5]; char *c[3]}, 先是10个字节长, 然后是24个字节长的指针数组. 由于指针要8字节对齐, 之前的10字节后边要加上6个字节的空白才行, 则总长度是40字节.
5. struct P5 {struct P3 a[2]; struct P2 t}, P3的单个长度是10, P3 a[2]长20, 而P2的长度是16, 最长对齐到8, 所以有4字节的空白, 则总长度是 20+4+16 = 40 , 这样总长度和其中的索引都是对齐到8的倍数.

练习 3.45 优化组合

struct {
    char *a;    8
    short b;    2
    double c;   8
    char d;     1
    float e;    4
    char f;     1
    long g;     8
    int h;      4
} rec

1. a的偏移量为0, 没什么问题
2. b的偏移量是8, 跟在a后边,没有什么问题, 对齐到2了也对齐到8了
3. c的偏移量就不能直接是10了, 否则xd+10不是8的倍数, 所以 b后边要跟6个字节的空白, 偏移量为 xd+16,就可以是8的倍数了
4. d的偏移量跟在c之后,应该是xd+24
5. e的偏移量很显然,也不能是xd+25, 否则不是4的倍数, 因此要补到 xd+28, 即d后边有3个空白
6. f又是一个char , 偏移量是xd+32
7. 到了g, 不能是xd+33, 必须补到8的倍数, 所以有7个字节的空白. 偏移量是 xd + 40
8. 最后的h 偏移量是 xd+48, 也没有问题, 是4的倍数.

struct {
    char d;     1
    char f;     1
    short b;    2
    float e;    4
    int h;      4
    char *a;    8
    double c;   8
    long g;     8
}

1. d的偏移量是xd+0
2. f的偏移量是xd+1,和1字节对齐,问题不大
3. b的偏移量是xd+2,和2字节对齐
4. e的偏移量是xd+4,和4字节对齐
5. int的偏移量是xd+8, 也和4字节对齐
6. a的偏移量如果不补空白,就是12, 不行,要补4字节空白, 为xd+16
7. c就是xd+24, 没问题
8. g是xd+32