CSAPP-第四章

发表于 更新于

*4.45

在3.4.2节中，x86-64 pushq 指令被描述成要减少栈指针，然后将寄存器存储在栈指针的位置。因此，如果我们有一条指令形如对于某个寄存器 REG, pushq REG, 它等价千下面的代
码序列：

subq $8,%rsp  Decrement stack pointer
movq REG, (%rsp)  Store REG on stack

A. 借助于练习题 4.7中所做的分析，这段代码序列正确地描述了指令 pushq %rsp 的行为吗？请解释。

B. 你该如何改写这段代码序列，使得它能够像对 REG 是其他寄存器时一样，正确地描述 REG 是%rsp 的情况？

正常来说入栈是栈指针下移，把值放到栈上，但是pushq %rsp时，如果真的有这行代码，存的值是下移前还是后就产生了歧义。4.7告诉我们存的是没有减小的栈指针，所以题目所给的汇编代码是不正确的

修改的话：

movq REG, (%rsp-8)
subq $8,%rsp

*4.46

3.4.2节中， x86-64 popq 指令被描述为将来自栈顶的结果复制到目的寄存器，然后将栈指针减少。因此，如果我们有一条指令形如 popq REG, 它等价于下面的代码序列：

>movq (%rsp), REG    Read REG from stack
>addq $8,%rsp        Increment stack pointer

A. 借助于练习题 4.8 中所做的分析，这段代码序列正确地描述了指令 popq %rsp 的行为吗？请解释。

B. 你该如何改写这段代码序列，使得它能够像对 REG 是其他寄存器时一样，正确地描述 REG rsp 的情况？

和上一题同理

movq REG, (%rsp+8)
addq $8,%rsp

***4.47

你的作业是写一个执行冒泡排序的 Y86-64 程序。下面这个函数用数组引用实现冒泡排序，供你参考：

>1 /• Bubble sort: Array version•/ 
>2 void bubble_a(long* data, long count) { 
>3   long i, last; 
>4   for (last = count-1; last > 0; last--) { 
>5       for (i = O; i < last; i++) 
>6           if (data [i +1] < data [i]) { 
>7           /* Swap adjacent elements*/ 
>8               long t = data[i+1]; 
>9               data[i+1] = data[i]; 
>10              data[i] = t; 
>11          }
>12      }    
>13 }

A. 书写并测试一个版本，它用指针引用数组元素，而不是用数组索引。

B. 书写并测试一个由这个函数和测试代码组成的 Y86-64 程序。你会发现模仿编译你的代码产生的 x86-64 代码来做实现会很有帮助。虽然指针比较通常是用无符号算术运算来实现的，但是在这个练习中，你可以使用有符号算术运算。

用指针做一个替换

void bubble_a(long* data, long count){
  long i, last;
  long *p = data;
  for(last = count-1; last > 0; last--){
    for(i = 0; i < last; i++){
      long *a = data + i;
      long *b = data + i + 1;
      if(*a > *b){
        long t = *a;
        *a = *b;
        *b = t;
      }
    }
  }
}

得到的x86代码如下：

bubble_a:
.LFB23:
	.cfi_startproc
	endbr64
	leaq	-1(%rsi), %r8   ;last = count-1
	testq	%r8, %r8
	jle	.L1
	leaq	(%rdi,%r8,8), %rsi  ;rsi = rdi + 8 * r8
	jmp	.L3
.L4:
	addq	$8, %rax        ; 指向下一个元素
	cmpq	%rsi, %rax      ; 确认是否遍历完毕
	je	.L7                 ; 遍历完，进入L7，否则进入L5
.L5:
	movq	(%rax), %rdx
	movq	8(%rax), %rcx
	cmpq	%rcx, %rdx      ; 比较当前元素和下一个元素
	jle	.L4                 ; 跳到L4，下一次循环
	movq	%rcx, (%rax)    
	movq	%rdx, 8(%rax)   ; 交换
	jmp	.L4                 
.L7:
	subq	$8, %rsi        
	subq	$1, %r8
	je	.L1
.L3:
	movq	%rdi, %rax      ;把数组的起始地址放入 %rax
	jmp	.L5
.L1:
	ret
	.cfi_endproc

转译到Y86代码

回顾Y86指令，只有8字节数据。
有指明目标的4个movq：irmovq rrmovq mrmovq rmmovq，立即数(i)、寄存器 ® 或内存 (m).
四个只能操作寄存器的整数操作addq subq andq xorq
七个跳转指令jmp jle jl je jne jge jg
六个条件传送cmovle cmovl cmove cmovne cmovge cmovg
call ret
pushq popq
halt停止处理器

接下来对照x86汇编代码完成翻译：

bubble_a:
    irmovq  $1, %rax     ;rax = 1，立即数
    rrmovq  %rsi, %r8    ;r8 = count
    subq    %rbx, %r8    ; count - 1
    jle .L1              ;last小于0，进入.L1（返回）
    irmovq $8,  %rbx     ;rbx = 8
    rrmovq  %r8, %rcx    ;rcx = last
    andq    %rcx,%rcx    
    jle .L1              ;如果只有一个元素，也返回
    
    irmovq  $0, %rsi     ;rsi = 0
    
.L_mult:
    addq    %rbx, %rsi   ;rsi += 8
    subq    %rbx, %rcx   ;rcx -= 1  
    jg .L_mult           ;rcx 小于等于0时
    addq    %rdi, %rsi   ;rsi = data + last*8，完成寻址
    
.L3:
    rrmovq  %rdi, %rax   ;rax = data
    jmp .L5
.L5:
    mrmovq  (%rax), %rdx
    mrmovq  8(%rax), %rcx ;拿出两个待比较数字
    rrmovq  %rdx, %rbx  ;中继，不影响寄存器里的值
    subq    %rcx, %rbx  ;比较
    jle .L4
    rmmovq  %rcx, (%rax)
    rmmovq  %rdx, 8(%rax) ;交换
    
.L4:
    irmovq  $8, %rbx
    addq    %rbx, %rax  ;指向下一个元素
    rrmovq  %rsi, %rbx
    subq    %rax, %rbx  
    je .L7              ;内层循环结束，进入外层循环
    jmp .L5             ;继续内层循环
.L7:
    irmovq  $8, %rbx    ;rbx = 8
    subq    %rbx, %rsi  ;rsi -= 8
    irmovq  $1, %rbx    ;rbx = 1
    subq    %rbx, %r8   ;r8(last)-=1
    je .L1              ;last == 0,返回
    jmp .L3             ;否则回到L3
.L1:
    ret                 ;返回
# CSAPP# Y86