CMU CSAPP Notes

Chapter 0. Intro

0.1 Ints are not Integers, Floats are not Reals

• $x^2\ge 0$$x^2\ge 0$：int（32-bit）may overflow；

• $a+(b+c)=(a+b)+c$$a+(b+c)=(a+b)+c$：floats may discard some "unsignificant" digits；

0.2 Learn Assembly but never write it

0.3 Memory Matters: Unbounded

​x
typedef struct {
    int a[2];
    double d;
} struct_t;

double func(int i) {
    struct_t t;
    t.d = 3.14;
    t.a[i] = 109390032;
    return t.d;
}
// func(0)/func(1) -> 3.14
// func(2)  -> 3.13...
// func(6)  -> segment fault

• C/C++ don't provide any memory protection（out of bounds/invalid pointer/abuse of malloc-free）: can lead to nasty bugs.

0.4 There's more to performance than asymtotic complexity

(有比渐进复杂度更能够优化性能的做法)

• 渐进复杂度中没有体现的“常数”也很重要；

• 应该在多方面优化性能：算法、数据结构表示、代码过程、循环等；

• Understand system to optimize performance;

xxxxxxxxxx
void copyij(int src[2048][2048], dst[2048][2048]) {
    int i,j;
    for (i = 0; i < 2048; ++i)
        for (j = 0; j < 2048; ++j)
            dst[i][j] = src[i][j];      // Row first.
}

void copyji(int src[2048][2048], dst[2048][2048]) {
    int i,j;
    for (j = 0; j < 2048; ++j)
        for (i = 0; i < 2048; ++i)
            dst[i][j] = src[i][j];      // Column first.
}

// In a particular machine it was about close to 20 times difference in performance! (4.3ms vs 81.8ms) 
// Memory hierachy: Cache memory

0.5 Computers do more than execute programs

• They need to get data in & out: I/O system;

• They communicate with each other over network;

Chapter 1. Bits, Bytes and Integers

1.1 Everythings is bits

本部分知识零碎，应该在数电 + 初级数据结构中接触。

• Each bit is 0 or 1;

• By encoding/interpreting sets of bits in various ways;

• Why bits? - Electronic Implemetation.

  • Easy to store with bistable elements.

  • Reliably transmitted on noisy and inaccurate wires.

• Base 2 Number Representation

• 1 Byte = 8 bits；

  • Binary: ${00000000}_2$$00000000_2$ to ${11111111}_2$$11111111_2$；

  • Decimal: $0_{10}$$0_{10}$ to ${255}_{10}$$255_{10}$；

  • Hexadecimal: ${00}_{16}$$00_{16}$ to $F{F}_{16}$$FF_{16}$；

    • 掌握快速 16 进制转 2 进制：$1010=A,1100=C,1111=F$$1010=A,\space1100=C,\space1111=F$，B/D/E 在其中；

• Data Representation in C language

  C Data Type	Typical 32-bit	Typical 64-bit	x86-64
  char	1	1	1
  short	2	2	2
  int	4	4	4
  long	4	8	8
  float	4	4	4
  double	8	8	8
  long double	N/A	N/A	10 / 16
  pointer	4	8	8

  • 注：单位 bytes，CSAPP 关注 x86-64 架构；

  • 注2：Intel x86-64 处理器的 long double 定为 10 bytes，但数据增量是 16 bytes，意味着会浪费 6 bytes 的存储空间；

  • 注3：pointer 值就是虚拟空间的地址，上面也正说明了 32 位和 64 位的名字的来源：这些虚拟内存的地址是 32 bits / 64 bits 长度的值；我们常说的 32 位机器、64 位机器就是指对应地址值的长度是 32/64 bits；

1.2 Boolean Algebra

• Developed by George boole in 19C, "True": 1, "False": 0;

• Operations: And(&) / Or(|) / Not(~) / Exclusive-or(Xor, ^);

  • Exercise: Operate on Bit Vectors;

• Example: Representing & Manipulating Sets

  • Representation: Width w bit vector can represent subsets of {0,...,w-1};

    xxxxxxxxxx
    & <=> Intersection
    | <=> Union
    ^ <=> Symmetric Difference
    ~ <=> Complement
    

• Shift Operations

  • left shift、right shift；

  • logic shift：Fill with “0”；

  • arithmetic shift：if (negetive) Fill with “1”，else Fill with “0”；

  • Undefined Behavior: shift amount < 0 or shift amount ≥ word size；

1.3 原码(true form)、反码(1's complement)、补码(2's complement)

• 补码速译：最高位权重变为负值；

• Unsigned range：$0\sim 2^w-1$$0\sim 2^w-1$；

  Two's complement range：$-2^{w-1}\sim 2^{w-1}-1$$-2^{w-1}\sim2^{w-1}-1$；

• 模 8 运算：保留补码后三位；

• Exercise 1: Mapping between signed & unsigned

  （将同一个数码看作不同的数，例如 11111111 可以表示 unsigned 的 255，也可以表示 signed -1，这两者相同的数码被称为 “相同的位模式（bit pattern）”）

  这对计算机很重要，因为它原本不知道是 signed 还是 unsigned；

• Exercise 2: Casting Surprises（模糊的常数给定，什么时候类型转换？怎么转换？）

  • 什么时候：C++ 书中说，在赋值、比较时进行隐式类型转换（implicit casting），还可以进行强制类型转换；

  • 怎么转换：

    1. 占用空间小的类型向大的类型转换：同时有 unsigned int 和 int，则向 unsigned int 转换（隐式类型转换）；

       ⚠ 隐式类型转换转换唯一需要注意的点：“原来是什么，后来还是什么”。例如，int 向 unsigned long、unsigned 向 long是否会 signed / zero extension，取决于原来的数是否有正负。

    2. Bit pattern（位模式）保持不变；

  • 编程的麻烦：

    xxxxxxxxxx
    // situation 1
    for (unsigned i = n - 1; i >= 0; --i)
        func(a[i]);
    // situation 2
    // 提示：sizeof 的返回值会被编译器认为是 size_t (unsigned long)
    for (int i = n - 1; i - sizeof(char) >= 0; --i)
        func(a[i]);
    

• Exercise 3: Sign Extension（在不改变值的情况下，将 w-bit 数变为 w+k-bit (k∈Z) 数）

  • Expanding Conclusion: Make k copies of MSB in signed, but fill "0" in unsigned.

    想想为什么。

  • Truncating Conclusion: mod $2^w$$2^w$ in unsigned, 很像 mod $2^w$$2^w$ 但不是 in signed (negative or positive);

1.4 Operations

• Unsigned Addition: $sum=UAd{d}_w(u,v)=u+v\mathrm{mod}{2}^w$$sum=UAdd_w(u,v)=u+v\mod2^w$（为什么成立？Truncating Conclusion）；

  • 一种溢出，这种溢出是模运算可以描述的；

  e.g., $(unsigned)13+5={1101}_2+{0101}_2\Rightarrow {0010}_2$$(unsigned)13+5=1101_2+0101_2\Rightarrow0010_2$ (Truncated)

• Two's complement Addition: $sum=TAd{d}_w(u,v)=UAd{d}_w(u,v)$$sum=TAdd_w(u,v)=UAdd_w(u,v)$（equal in bit pattern, Truncating Conclusion）;

  • 两种溢出：负溢出（$sum\le -2^{w-1}$$sum\le-2^{w-1}$ 时）和 正溢出（$sum\ge w^{w-1}$$sum\ge w^{w-1}$ 时）;

• Unsigned Multiplication: $multi=UMul{t}_w(u,v)=u\cdot v\mathrm{mod}{2}^w$$multi=UMult_w(u,v)=u\cdot v\mod2^w$（与加法同理）;

• Signed Multiplication Multiplication: $multi=TMult{i}_w(u,v)=UMult{i}_w(u,v)$$multi=TMulti_w(u,v)=UMulti_w(u,v)$（与加法同理）;

这意味着计算机的乘法、加法可以共用硬件；

• Shift & Power-of-2 Multiply / Divide: 原因可以看作改变权重；

  • Unsigned: no problem；

  • Signed: Use arithmetic shift. Add a bias（偏移量 1）to bit pattern and then right shift

    1. 为什么用 算数移位？因为 Expanding Conclusion；至于什么移位，C++ 标准没有明确说，但绝大多数机器都会算术移位；

    2. 为什么要偏移量？使结果向大数舍入；

• Negative（取相反数，当然只有 signed 做得到）：flip all the bits and then add 1（“~” 取反 + 1）

• 在介绍完移位运算后，回忆 1.3 中的 “编程麻烦”，能不能不用 unsigned，通通用 signed （全用补码表示）不就不会出现这些 casting suprises 了吗？确实，C++ 中尽量别用 unsigned，容易出问题；

  Java 就是这么做的。取消了 unsigned 的类型，并且禁止了某些隐式类型转换。但因为某些其他的需求，Java 不得不引入算数移位（>>> 和 <<<），就是 C++ 中处理 signed divide 的运算符;

  但 unsigned 也有用处：

  • 取模运算：利用 unsigned 加法溢出特性；

  • 使用 bits 来代表集合（1.2）；

1.5 Miscellaneous

• 2 的幂次数大小估算：因为 $2^{10}\approx {10}^3$$2^{10}\approx10^3$，这意味着每 3 位十进制数和 10 位二进制数相当，所以 $2^{20}\approx {10}^6$$2^{20}\approx10^6$；

• segmentation fault 的产生：64-bits pointer 让程序认为真的有 $2^{64}$$2^{64}$ bit 的内存空间，但实际上并不是。所以当程序访问到操作系统未给它分配的内存时，会抛出 segmentation fault；

• 字长究竟是多大：不确定。一般是由一种语言中指针表示的范围、存储器上最大存储块大小决定。例如 64 位机器就是擅长 64-bits 计算、指针大小 64-bits 的机器；因此一个程序的位数是由硬件和编译器共同决定的；

  所以 64 位机器可以运行 32 位程序（向后兼容）；

  考虑内存对齐，32-bits 下字长相当于 4 bytes，64-bits 下字长相当于 8 bytes；

• Byte Ordering

  • Big Endian（大端序）：现在常出现的地方就是 Internet，即当发送 32-bits 数据包时

    • Least significant byte has highest address（前面的 bits 排在地址靠前的位置，符合人类习惯）；

  • Little Endian（小端序）：目前支持主流操作系统的处理器都能用小端序

    • Least significant byte has lowest address（前面的 bits 排在地址靠后的位置）

  • Representing of integers

    • Example of 01234567：

      xxxxxxxxxx
      address: 0x100 0x101 0x102 0x103
      big    :  01    23    45    67
      little :  67    45    23    01
      

  • Representing of pointers

  • Representing of strings: Every machine is the same; (ended by '\0');

1.6 Puzzles

Initialization:

xxxxxxxxxx
int x = foo();
int y = bar();
unsigned ux = x;
unsigned uy = y;

• $x<0\Rightarrow (x\ast 2<0)$$x\lt0\Rightarrow(x*2\lt0)$ ?

  False, $x=TMin$$x=TMin$ (negative overflow) ?

• $ux\ge 0$$ux\ge0$ ?

  True;

• $x\mathrm{\&}7==7\Rightarrow (x<<30)<0$$x\space\And\space7==7\Rightarrow(x<<30)\lt0$ ?

  True, $(x<<30)==-2^{31}+2^{30}<0$$(x<<30)==-2^{31}+2^{30}\lt0$;

• $ux>-1$$ux\gt-1$ ?

  Always False, implicit casting：$(unsigned)(-1)=(\sum _{k=0}^{31}{2}^k{)}_{10}⟹\mathrm{\forall }x((unsigned)x\le (unsigned)(-1))$$(unsigned)(-1)=(\sum\limits_{k=0}^{31}2^k)_{10}\Longrightarrow\forall x((unsigned)x\le(unsigned)(-1))$;

• $x>y\Rightarrow -x<-y$$x\gt y\Rightarrow-x\lt-y$ ?

  False, $y==TMin\Rightarrow -y==TMin$$y==TMin\Rightarrow-y==TMin$.

  So: $\mathrm{\forall }x(y==TMin\to -x\ge -y)$$\forall x(y==TMin\rightarrow -x\ge-y)$

• $x\ast x\ge 0$$x*x\ge0$ ?

  False. Positive overflow.

• $x>0\mathrm{\&}\mathrm{\&}y>0\Rightarrow x+y>0$$x\gt0\space\And\And\space y\gt0\Rightarrow x+y\gt0$ ?

  False. Positive overflow.

• $x\ge 0\Rightarrow -x\le 0$$x\ge0\Rightarrow-x\le0$ ?

  True.

• $x\le 0\Rightarrow -x\ge 0$$x\le0\Rightarrow-x\ge0$ ?

  False, $x==TMin\Rightarrow -x==TMin$$x==TMin\Rightarrow-x==TMin$.

• $(x|-x)>>31==-1$$(x|-x)>>31==-1$ ?

  False. $x==0$$x==0$ ?

Chapter 2. Floating Point

2.1 Fractional Binary Numbers

• Limitations: Can only exactly represent numbers of the form $x/2^k$$x/2^k$; Other rational number have repeating bit representations.

• IEEE Floating Point

  • Numerical form: $(-1{)}^s\cdot M\cdot 2^E$$(-1)^s\cdot M\cdot2^E$;

    • Sign bit $s$$s$ determines whether number is positive or negative;

    • Significand（尾数，Mantissa） M normally a fractional value in $[1.0,2.0)$$[1.0,2.0)$;

    • Exponent E weights value by power of 2;

  • Single precision: 32-bits

    $s$$s$: 1-bit; $exp$$exp$: 8-bits; $frac$$frac$: 23-bits;（$s$$s$、$exp$$exp$、$frac$$frac$ 代表对应的数据域而已，下略）

  • Double precision: 64-bits

    $s$$s$: 1-bit; $exp$$exp$: 11-bits; $frac$$frac$: 52-bits;

  • Normalized values:

    • $exp$$exp$ 不全为 0，也不全为 1；

    • $exp$$exp$ coded as a biased value: $E=Exp-Bias$$E=Exp-Bias$;

      $Exp$$Exp$: unsigned value of exp field.

      $Bias=2^{k-1}-1$$Bias=2^{k-1}-1$, where $k$$k$ is number of exponent bits（当前 $exp$$exp$ 字段的 bit 长度，非常巧妙）

      为什么这么设定 Bias？

      Single precision's bias: 127（Exp: 1...254, E: -126...127）

      Double precision's bias: 1023（Exp: 1...2046, E: -1022...1023）

      考虑为什么 $E$$E$ 要这么表达？因为这么做比较起来非常方便（$Exp$$Exp$ 0000... 最小，1111...最大）；

    • Significand $M$$M$ coded with implied leading 1: $M=(1.xxxx...x{)}_2$$M = (1.xxxx...x)_2$

      $xxxx...x$$xxxx...x$: bits of $frac$$frac$ field（0000...0最小，此时 M = 1；1111...1最大，此时 $M=2-\epsilon$$M=2-\varepsilon$）

      由于前导 1，normalized value 只能表示绝对值 $[2^{1-Bias},(2-2^{-bitsOfFrac})\cdot 2^{2\cdot Bias})$$[2^{1-Bias},(2-2^{-bitsOfFrac})\cdot2^{2\cdot Bias})$ 范围的 floating point；

    • 理解：像科学计数法，$2^E$$2^E$ 相当于十进制中的 ${10}^E$$10^E$，用于移位，前面的 $M$$M$ 规定具体数值；

  • Denormalized values:

    • $exp$$exp$ 全为 0；

    • $exp$$exp$ coded as: $E=1-Bias$$E=1-Bias$;（可以理解为此时 $exp$$exp$ 字段全 0 本身没意义，它们的个数来表示 $Bias$$Bias$ 进而表示 $E$$E$）

    • Significand $M$$M$ coded with implied leading 0: $M=(0.xxx...x{)}_2$$M=(0.xxx...x)_2$;

      $xxx...x$$xxx...x$: bits of $frac$$frac$ field;

      注意，这里会发现可以表示 “+0” 和 “-0”；⚠ 在比较大小和判断的时候要当心！

      denormalized value 只能表示绝对值 $[0,2^{1-Bias})$$[0,2^{1-Bias})$ 范围的 floating point；

  • Special values:

    • $exp$$exp$ 全为 1；

    • 这种编码只有两种情况：

      1. $frac$$frac$ 域全为 0：代表 $\mathrm{\infty }$$\infty$;

      2. $frac$$frac$ 域不全为 0：代表 $NaN$$NaN$（not a number），例如 $\sqrt{-1}$$\sqrt{-1}$、$\mathrm{\infty }-\mathrm{\infty }$$\infty-\infty$、$\mathrm{\infty }\times 0$$\infty\times0$ 等；

  这样规定就会发现，浮点数恰好可以溢出到 $\pm \mathrm{\infty }$$\pm\infty$，而且错误数恰为 $NaN$$NaN$；

  Visualization：

  想要理解上面规定的原因还可以用少量的数位来模拟，你会发现之前的设定非常巧妙：

  （这里以 $s$$s$: 1-bit，$exp$$exp$: 4-bits，$frac$$frac$: 3-bits 为例）

  

• Special Properties of IEEE Encoding

  • FP（Floating Point）zero same as Integer zero（All bits = 0）；

  • Can almost（except NaN） use unsigned integer comparison；

    • Must first compare sign bits；

    • Must consider -0 = +0；

    • What should comparison with NaN yield？

    • Otherwise OK ($+\mathrm{\infty }$$+\infty$ 和 $-\mathrm{\infty }$$-\infty$ 都能与数比较)；

• Exercise: write float pointing in bit-level representation;

  xxxxxxxxxx
  float F = 15213.0;
  

  • ${15213}_{10}={11101101101101}_2={1.1101101101101}_2\times 2^{13}$$15213_{10}=11101101101101_2=1.1101101101101_2\times2^{13}$

  • $M={1.1101101101101}_2$$M=1.1101101101101_2$, $frac={11011011011010000000000}_2$$frac=11011011011010000000000_2$

  • $E=13$$E=13$, $Bias=127$$Bias=127$, $Exp=E+Bias={140}_{10}={10001100}_2$$Exp=E+Bias=140_{10}=10001100_2$;

  • $Normalizedvalue=01000110011011011011010000000000$$Normalized\space value=01000110011011011011010000000000$

2.2 The Operations for Floating Point

• Basic idea

  1. First compute exact result;

  2. Make it fit into desired precision

     • possibly overflow if exponent too large;

     • possibly round to fit into $frac$$frac$;

• Rounding for base 10 numbers

  • Towards zero（向 0 舍入）；

  • Round down（向下舍入）；

  • Round up（向上舍入）；

  • Nearest Even（default）

    即 四舍六入五成双，见概率统计；

    超过一半都是 “六” 的情况，少于一半都是 “四” 的情况，正好一半看最后保留位的奇偶；

• Rounding Binary number: Nearest Even 与 普通十进制数思路相同；

  举例：Round to nearest 1/4（2 bits right of binary point）：

  ${10.00011}_2\Rightarrow {10.00}_2$$10.00011_2\Rightarrow 10.00_2$，${10.00110}_2\Rightarrow {10.01}_2$$10.00110_2\Rightarrow10.01_2$，

  ${10.11100}_2\Rightarrow {11.00}_2$$10.11100_2\Rightarrow11.00_2$，${10.10100}_2\Rightarrow {10.10}_2$$10.10100_2\Rightarrow10.10_2$；

• FP Multiplication: $multi=(-1{)}^s\cdot M\cdot 2^E=(-1{)}^{s_1}\cdot M_1\cdot 2^{E_1}\cdot (-1{)}^{s_2}\cdot M_2\cdot 2^{E_2}$$multi=(-1)^s\cdot M\cdot2^E=(-1)^{s_1}\cdot M_1\cdot 2^{E_1}\cdot(-1)^{s_2}\cdot M_2\cdot2^{E_2}$

  • Sign $s=s_1{}^{\wedge }{s}_2$$s=s_1\space^\wedge\space s_2$;

  • Significand $M=M_1\times M_2$$M=M_1\times M_2$;

  • Exponent $E=E_1+E_2$$E=E_1+E_2$;

  • Fixing

    1. If $M\ge 2$$M\ge2$，shift $M$$M$ right, increment $E$$E$; (That's why $M<2$$M\lt 2$)

    2. If $E$$E$ out of range ($Exp$$Exp$ out of range), overflow;

    3. Round $M$$M$ to fit $frac$$frac$ precision;

• FP Addition: $sum=(-1{)}^s\cdot M\cdot 2^E=(-1{)}^{s_1}\cdot M_1\cdot 2^{E_1}+(-1{)}^{s_2}\cdot M_2\cdot 2^{E_2}$$sum=(-1)^s\cdot M\cdot2^E=(-1)^{s_1}\cdot M_1\cdot2^{E_1}+(-1)^{s_2}\cdot M_2\cdot2^{E_2}$. (assume $E_1>E_2$$E_1\gt E_2$)

  • Sign $s$$s$, Significand $M$$M$: Result of signed align & add;

  • Exponent $E$$E$: the same as $E_1$$E_1$, which means $E_2$$E_2$ will be ignored if $E_1>>E_2$$E_1\gt\gt E_2$;

  • Fixing

    1. If $M\ge 2$$M\ge2$, shift $M$$M$ right, increment $E$$E$;

    2. If $M<1$$M\lt1$, shift $M$$M$ left $k$$k$ positions, decrement $E$$E$ by $k$$k$; (The difference between multiplication)

    3. If $E$$E$ out of range, overflow;

    4. Round $M$$M$ to fit $frac$$frac$ precision;

• Mathematical Properties of FP addition / multiplication:

  • 具备交换律 (commutative)，不具备结合性 (associative)：舍入的不准确性和溢出、大数和小数之和会丢失小数、大数和大数乘积会变为 $\mathrm{\infty }$$\infty$；

  • Every element has additive inverse (相反数) except for infinites & NaNs；

  • 几乎具备单调性 (Monotonicity): $a\ge b\Rightarrow a+x\ge b+c$$a\ge b\Rightarrow a+x\ge b+c$ except for infinites & NaNs;

  总而言之，在考试时，忘记这些问题不大，想要快速判断是否满足某个定律，只需找特殊：$\mathrm{\infty }$$\infty$、$NaN$$NaN$、overflow、0，这四者是大多数特例的来源；

2.3 Floating Point in C

• float（single precision），double（double precision）；

• Conversions / Casting:

  • int、double、float 间的转换会改变 bit representation；

    回忆 signed 和 unsigned 间的转换，不改变 bit pattern，只是改变某些位置的解释方式；

  • implicit casting 发生在占用小空间的类型（int）向占用大空间类型（double）转换，也可显式声明；

    • int -> double: 准确转换。因为 int 大小小于 53-bits；

    • int -> float: Will rounding according to rounding mode；

  • 显式类型转换 double/float -> int

    • Truncates (截断) fractional part;

    • Like rounding toward 0 (可以看作向 0 舍入);

    • Not defined when out of range / NaN: Generally sets to TMin;

2.4 Puzzles

initialization:

xxxxxxxxxx
int x = ...;
float f = ...;
double d = ...;
// Assume neither d nor f is NaN;

• $x==(int)(float)x$$x==(int)(float)x$ ?

  False; (int)x -> (float)x (rounded)

• $x==(int)(double)x$$x==(int)(double)x$ ?

  True;

• $f==(float)(double)f$$f==(float)(double)f$ ?

  True;

• $d==(double)(float)d$$d==(double)(float)d$ ?

  False; (double)d -> (float)d (rounded)

• $f==-(-f)$$f==-(-f)$ ?

  True. Even $f==\pm \mathrm{\infty }$$f==\pm\infty$ is true.

• $2/3==2/3.0$$2/3==2/3.0$ ?

  False; $(int)2/3=0$$(int)2/3=0$, $(double)2/3.0=0.666...67$$(double)2/3.0=0.666...67$;

• $d<0.0\Rightarrow (d\ast 2<0.0)$$d\lt0.0\Rightarrow(d*2\lt0.0)$ ?

  True; Even $d\ast 2==-\mathrm{\infty }$$d*2==-\infty$ is true.

• $d>f\Rightarrow -f>-d$$d\gt f\Rightarrow-f\gt-d$ ?

  False; $d==+\mathrm{\infty }$$d==+\infty$ or $f==-\mathrm{\infty }$$f==-\infty$ ?

• $d\ast d\ge 0.0$$d*d\ge0.0$ ?

  True. Even $d==\pm \mathrm{\infty }\Rightarrow d\ast d==+\mathrm{\infty }$$d==\pm\infty\Rightarrow d*d==+\infty$ is true.

• $(d+f)-d==f$$(d+f)-d==f$ ?

  False; $d>>f\Rightarrow (d+f)\approx d$$d>>f\Rightarrow(d+f)\approx d$;

C1 & C2 结束，请完成 Data Lab！

Chapter 3. Machine-Level Programming Ⅰ- Basics

和前面说的一样，本章不会教学一段段写汇编，只要求看懂 GCC 输出的汇编代码即完成任务；

本章涉及的机器语言运行在 Intel x86-64 机器上；

• 两种机器代码

  • 计算机实际运行的目标代码（一串字节编码处理器执行的指令，难以阅读）；

  • 汇编代码：过去用于直接对机器进行编程，现在是编译器输出的目标。

  以后说 “机器代码”，有时指第一种（目标代码），有时指第二种（文本格式的汇编代码），它们两者概念几乎相同，可替换。不过为了防止混淆以后对第二种会说 “汇编代码”。

3.1 History of Intel processors and architectures

• 什么是 Intel 的 x86-64？

  x86 是指 Intel 自己的 x86 processors，因为 Intel 这个系列的第一张处理器芯片的代号是 8086（产于 1978）。

  随着时间推移，这个系列的芯片不断添加特性、升级演进；Intel 自己跳过了 81 系列，推出过 8286、8386系列等，都是以 86 结尾，所以被称为 x86。

  后面的 64 表示这是 64-bits 的机器；

• 什么是 CISC 和 RISC？

  • Reduced Instruction Set Computer（RISC，精简指令集计算机）：一类装备改良的机器指令集的计算机，思想较新；

  • Complex Instruction Set Computer（CISC，复杂指令集计算机）：在 RISC 出现后，RISC 开发者把之前的使用旧指令集的计算机统称为 CISC，所以这个概念出现在本体之后，带有贬义；

  Intel 采用的是 CISC，CSAPP 中介绍的这方面的知识还是不全面，想要进一步了解 CISC 需要自己阅读 CISC 手册；

• Intel 芯片的进化

  • 8086: 1978, 5-10 MHz;

    First 16-bit Intel processor.

    1 MB Address space.

  • 386: 1985, 16-33 MHz

    First 32-bit Intel processor, referred to as IA32（Intel Architecture 32），占据了极大市场份额；现在不教它了，因为有更新的 x86-64;

    Added “flat addressing”，capable of running UNIX；

  • Pentium 4E（奔腾 4E）: 2004, 2800-3800 MHz

    First 64-bit Intel x86 processor, referred to as x86-64;

    收到了产品反馈：性能功耗问题，发热严重，不能无限制增加处理器时钟频率，开始着手多核处理器（一个芯片上放多个独立处理器）；

  • Core 2: 2006, 1060-3500 MHz

    First multi-core Intel processor;

  • Core i7: 2008, 1700-3900 MHz

    Four cores processor;（至今性能也不错）

• 什么是缓存？大致定义是 a temporary memory used to hold the most recently accessed data;

• 2015 年的 Intel 芯片架构

  

  • DDR 接口是连接到主存储器（DRAM，Dynamic Random Access Memory）的通道；

  • PCI 接口是与外围设备（peripheral devices）的连接通道；

  • SATA 接口是与不同类型硬盘的连接通道；

  • Ethernet 接口是网络接口；

  结论：集成到单个芯片上的不仅仅是处理器本身，还有很多逻辑单元所组合起的有机整体；

• Intel 的竞争对手：AMD（Advanced Micro Devices）

  • 总是跟在 Intel 后面发展，同级别的芯片稍微有点慢，但便宜的多；

• 什么是 ARM？

  • 除了 Intel 公司的 x86 类型的处理器，当前常用的、比较主流的另一类处理器是 ARM（Acron RISC Machine），CSAPP 不会深入涉及；

  • 创造这种处理器及其对应指令集（RISC）的原公司已经破产，但指令集写的很棒，能自定义，功耗比同水准的 x86 处理器更低。

  • 所以后继者建立了一个公司，但这个公司不销售处理器，只向众多公司销售 ARM 的设计许可权。因此，ARM 处理器是很多芯片厂商（尤其 Intel）生产的芯片的一部分，因为 ARM 的优势而被用在方方面面；

3.2 C, Assembly, Machine code

本节只是概述一下整个 C、汇编语言、机器语言的产生过程 和 宏观样貌。

具体对汇编代码的学习内容在下一节。

3.2.1 Definitions

• Architecture (also ISA: Instruction Set Architecture): The parts of a processor design that one needs to understand or write assembly/machine code.

  • 架构是处理器设计的一部分。开发硬件的人员在考虑设计机器和对应机器语言的时候，想到了将 “指令集架构” 这层抽象出来。例如针对某个寄存器，特定的指令集等，相当于驱动硬件的接口，将微架构和机器码隔离开。这样，硬件设计者只需要关心微架构，上层的设计者需要关注机器语言以及更抽象的语言就行。

  • 开发人员需要了解，以此来编写对应的汇编码、机器语言，以至对应平台的编译器；

  • examples:

    • Intel: x86, IA32, Itanium, x86-64;

    • ARM: (Name is itself) Used in almost all mobile phones.

• Microarchitecture: Implementation of the architecture.

  • 例如：缓存大小设计、内核频率设计。CSAPP 中也涉及的很少；

• Code Form

  • Machine Code: The byte-level programs that a processor executes;

  • Assembly Code: A text representation of machine code.

3.2.2 Assembly/Machine Code View

• Programmer-Visible State（在机器语言中需要开发者了解、操作的一些量，含有与真实硬件相关的细节）：

  • PC (Program Counter, 程序计数器)

    1. Get the address of next instruction;

    2. Called "RIP" (in x86-64);

  • Register file: Heavily used program data（汇编程序中绝大多数数据存放的位置）;

  • Condition Codes（状态代码，存放于状态寄存器）

    1. 存储绝大多数当前最近的算数/逻辑运算的状态信息；

    2. 数据用来判断状态分支；

  • Memory

    1. 由地址组织的 byte 数组，实际上是用一种不同方式（这个实现的方式以后的章节会详细介绍）实现的虚构对象，完成操作系统和硬件间的协作，因此称为虚拟内存（Virtual Memory），所以这使得虽然内存（硬件上实际的内存又称为物理内存，Physical Memory）在硬件上可能是零碎的，但汇编开发者看起来的却是一大块可以按地址成块使用的。每个程序都有自己独立的字节数组来访问数据。

    2. 存放代码、用户信息；

    3. 使用堆栈数据结构来支持步骤；

    这里解释一下经常提到的缓存（Cache），缓存是指一个动作，就是将最近访问的数据存储到高速缓存器（I/O 远快于普通寄存器和外存储器，但造价高，所以容量小）中。下一次访问相同数据时，会直接进入高速缓存器中，速度会更快。

    但是“缓存”这个动作对汇编开发者而言也是不可见（invisible）的，这是写在硬件中的动作（前面说的 microarchitecture），即使在汇编层面也没有专门的指令，无法操作。

• C 代码如何转变为 Object Code

  • 在 GNU Tutor 中曾经介绍过从源文件到目标文件的过程；

  • C 源文件（*.c, text） 编译器（compiler, C 一般用 gcc）编译为 ASM 源文件（*.s, text），再交给汇编器（assembler，一般用 gcc/as） 汇编为 目标文件（*.o, binary），最后交给链接器（linker，一般用 gcc/ld） 链接用到的第三方静态库，最终变为可执行文件；

  • 剩余还有一部分是动态链接库，要么自己写并且编译，放置在指定位置，要么用的是系统环境中的库，在程序运行时动态加载。

• 举例说明：下面以一个简单的 C 程序为例，演示其汇编代码及含义。

  xxxxxxxxxx
  // File: sum.c
  long plus(long x, long y) {
      return x + y;
  }
  
  void sumstore(long x, long y, long* dest) {
      long t = plus(x, y);
      *dest = t;
  }
  
  int main(int argc, char* argv[]) {
      long x = atoi(argv[1]);
      long y = atoi(argv[2]);
      long z;
      sumstore(x, y, &z);
      printf("%ld + %ld --> %ld\n", x, y, z);
      return 0;
  }
  

  现在运行 gcc -Og -S sum.c。

  • -Og 参数是较新的参数，与 -On（n=0，1，2，3） 优化不一样，为开发人员提供了易读的中间汇编码；另外，如果不加 -O 参数，就什么都不优化，那么代码同样难以阅读；

  • -S 参数意味着 gcc 套件将仅运行到产生汇编代码（*.s）就停止；

  找到代表 sumstore 函数的 asm 代码，以函数名 + 冒号开头：

  xxxxxxxxxx
  sumstore:
      pushq   %rbx
      .seh_pushreg    %rbx
      subq    $32, %rsp
      .seh_stackalloc 32
      .seh_endprologue
      movq    %r8, %rbx
      call    plus
      movl    %eax, (%rbx)
      addq    $32, %rsp
      popq    %rbx
      ret
      .seh_endproc
      .def    __main; .scl    2;  .type   32; .endef
      .section .rdata,"dr"
  

  这里注意开头含有 . 的操作实际不是原先代码的部分，它们与一些其他信息有关。例如为调试器提供行号的、为链接器提供信息表示全局函数的等等。一开始可以不用太过于在意这些，为了演示方便，这里直接删掉说明，如下：

  xxxxxxxxxx
  sumstore:
      pushq   %rbx    ; %rbx 表示访问名为 rbx 的寄存器，pushd 表示数据压入memory栈
      subq    $32, %rsp   
      movq    %r8, %rbx
      call    plus    ; 调用函数名为 plus 的函数
      movl    %eax, (%rbx)    ; 移动值
      addq    $32, %rsp
      popq    %rbx    ; 将栈中值弹出到 名为 rbx 的寄存器中
      ret             ; 当前函数结束，返回
  

3.2.3 Assembly Characteristics: Data Types

• "Integer" data of 1,2,4, or 8 bytes（不同的整型数据类型，不区分符号）

  • Data types / Address（untyped pointers）

• Floating point data of 4,8, or 10 bytes（浮点数处理方式不同，使用不同的寄存器组，之后详细提）

• 在汇编层面不存在聚合结构（aggregate types），例如数组、结构体，因为它们是在编译器层面人工设计的，本质上就是连续的一段内存，以后也会实现；

3.2.4 Assembly Characteristics: Operations

• Perform arithmetic function on register or memory data（算术运算在存储器上的数据）

• Transfer data between memory and register（在内存和寄存器间转移数据）

  • load data from memory to register

  • store register data into memory

• Transfer control（汇编代码流程控制）

  • Unconditional jumps to/from procedures

  • Conditional branches

3.2.5 Assembling & Disassembling Object Code: At first glance

先来看 C code 到 汇编语言/机器语言的过程。

当汇编代码被 assembler（汇编器）汇编为目标代码时，这时所能看到的就只有二进制序列了。接下来还以之前的 sum.c 中的 sumstore 函数为例：

xxxxxxxxxx
0x0400595:  # 表示本函数段从 0x0400595 处开始
    0x53    # 每一条指令长为 1/3/5 bytes，整段函数的长度为 14 bytes
    0x48
    0x89
    0xd3
    0xe8
    0xf2
    0xff
    0xff
    0xff
    0x48
    0x89
    0x03
    0x5b
    0xc3

这里每条指令只做一件事。以 sumstore 函数中的一个语句为例：

xxxxxxxxxx
*dest = t;  /* Store value t where designated by dest. */
            /* 这里加信号的含义是取 dest 所指向的地址 */

对应这条汇编代码：

xxxxxxxxxx
movq %rax, (%rbx)

对应这条目标代码：

xxxxxxxxxx
0x40059e:   48 89 03

这里 t 或某些 local variables 会存储于寄存器中（例如上面表示它在寄存器 %rax 中），而 dest 指针值自己也被存储于寄存器中（上面表示 dest 自身的值存于 %rbx 中）；

这里的 (%rbx) 表示 Memory[%rbx]，即 %rbx 值所代表的地址在 Memory 中的位置；

mov A, B 指令就是将值从 A 处移动到 B 处。上面的汇编语句连起来就是：将存放于 %rax 中的值移动到 %rbx 所代表 Memory 地址的位置上；

根据汇编器翻译，这条指令只用了 3 bytes 来编码：48 89 03；

再来看机器语言到汇编语言的反汇编过程（disassembling）。

反汇编的实现和汇编一样，后者是将文本版本（汇编代码）转换为字节码（机器代码）的形式表示，前者将字节码对应解释成易读的文本即可。

如果当前没有源文件，甚至没有汇编代码，那么可以由反汇编器（disassembler）来将目标代码（*.o）或者可执行程序（已链接库的目标代码）转换成汇编代码（*.s）：

xxxxxxxxxx
objdump -d sum > sum.d # 反编译之前的 sum 程序，-d 将可执行部分反汇编显示到 stdout

值得注意的是，在汇编代码的层次下，无法再向上还原到源文件（*.c），因为其中的函数/变量名、都在汇编过程丢失了，只剩下一些寄存器的名称和 Memory 地址。

上面使用 objdump 可以得到真正意义上的汇编代码（从机器代码转换而来），此外还有一种方法：使用 gdb。

如果使用 gdb 打开目标可执行文件，运行 disassemble <funcName> 就可以对可执行文件中对应的函数区域进行反汇编。但只显示这些指令的地址 + 翻译指令，不显示字节级的编码。

3.3 Assembly Basics

3.3.1 The names for integer registers

下面列举 x86-64 architecture 的 整数型寄存器（Integer Register）。

如图，这些寄存器共有 16 个，名字大致分为 2 类，一类是字母表示的（ax/bx/...），另一类是数字表示的（8/9/...）。

目前一个 x86-64 架构的 integer register 总大小有 64-bit。鉴于对以前 32-bit 机器和程序的向前兼容（backwards compatibility），汇编语言允许使用一个寄存器的不同部分，怎么用取决于指令。

对于字母类名称的寄存器（如上图左），如果使用前缀 %r（例如 %rax），那么这个整型寄存器将保存 64-bit 大小的整型数据（即使用全部空间）；如果使用前缀 %e（例如 %eax），那么这个整型寄存器将保存 32-bit 大小的整型数据（即从低位开始使用 32 bits，又称为 low-order 32-bit）。

对于数字类名称的寄存器（如上图右），前缀必须是 %r。如果不加后缀，表示保存 64-bit 大小的整型；如果使用后缀 d，那么将保存 32-bit 大小的整型。

在这些寄存器中，可以使用指令存取数据，而且这些是机器级编程，和具体机器的型号密切相关，每步即必须清楚指出从哪个寄存器到哪个寄存器。

在 x86-64 架构下，最常见的是 64-bit register 的使用，其次是 low-order 8-bit 的使用（用在条件控制中，这个会在下一章介绍）。因此，除非提及，下面默认的 register 全部是以 %r 为前缀的 16 个寄存器。

下面补充一些历史信息，帮助理解这些寄存器奇怪的（quirky）名字：

在早期 IA32 架构下 32-bit 处理器只用到了 8 个寄存器，它们的名字分别是：

%eax、%ecx、%edx、%ebx、%esi、%edi、%esp、%ebp（都是 %e 前缀,意味着存 32-bit 整型）

此位，这些寄存器还能引用 low-order 16-bits（它们是最开始出现的 16-bit 寄存器，没有 e/r 前缀，引用的名称为 %ax、%cx、%bx……），甚至是 low-order 8-bits 和 high-order 8-bits（分别是 %al 和 %ah 等，如下图）。这里不讲述这些旧版本机器的低位寄存器位置的操作指令，不过在下一章会提到操作 low-order 8-bits 的操作指令，因为会涉及汇编条件控制。

很早以前，各个寄存器的名字有特定含义，代表它们的目的。例如 a 代表 accumulate，c 代表 counter，d 代表 data，b 代表 base，si 代表 source index，di 代表 destination index，sp 代表 stack pointer，bp 代表 base pointer。

现在这些寄存器就是普通的存取数据的结构，名字也就没有特定的含义了——除了名字是 sp 的寄存器。它在目前的 x86-64 架构中也有一个非常具体的目的，就是上面说的，stack pointer，栈指针。

至于后面数字表示的寄存器，是后来从 IA32 架构升级到 64 位（x86-64）时，芯片可以在一个时钟周期处理 64-bit 的数据了，旧的寄存器设计不够用了，所以新添加上去的，因为没有特定用途，就以数字进行命名。

⚠ 说是没什么“特殊用途”，但还是有约定俗成的使用方法的！

例如，这些寄存器分为 “Callee-Saved Register” 和 “Caller-Saved Register”。

其中，Callee-Saved Register 是由被调用方保管使用的寄存器，数据内容只会在被调方的函数内有效、有意义。属于这类的寄存器有：%rbx、%r12-14、%rbp 和 %rsp，后两者是有特殊含义的，前面的寄存器是供被调方存储临时数据（Temporaries）；

Caller-Saved Register 是调用方保管使用的寄存器，它的作用大多数是沟通调用方和被调方的数据信息。例如 %rax 一般存放返回值，%rdi、%rsi、%rdx、%rcx、%r8、%r9 依此存放调用函数的第 1 ~ 第 6 参数；%r10、%r11 供存储调用方临时数据。

在下面的部分中，你会一遍遍加深对这个说法的印象的。上面的内容在第五章会进一步提及。

至于为什么要有 Callee-Saved 和 Caller-Saved Register，这也会在 5.4 中详细说明。

3.3.2 Move, Operands, and usage

接下来介绍整型寄存器在汇编代码中的使用。

Moving Data Command: movq <SrcR>, <DstR>

为什么命令名中有 "q" ？因为在 Intel 公司设定中，q 代表 quad，是 4 个字，而在 8086 系列中，1 个字被约定为 16 bits（2 bytes），所以 movq 指令操作的必须是 64 bits 的寄存器；

⚠ 另外请格外注意，Intel 和 Microsoft 使用的 x86-64 架构的汇编语言的这些参数和 Linux 使用的 x86-64 架构的参数顺序不一样！CSAPP 教授的指令语法按照 Linux 来，请不要弄错！不要在 Windows 环境下尝试这些指令！

Operands

• Immediate（数据直接量，例如常量整型）: 定义和 C 语言一样，但是需要加上前缀 $;

  例如：$0x400、$-523 等等；

• Register Name: 16 个中任意一个整型寄存器的名称。

  注意：保留作其他用途的寄存器也不应该被手动使用。前面说了，例如在 x86-64 架构中，%rsp 保留做特殊用途，因为栈中保存其他重要的状态信息，只能由机器内部进行修改。

• Memory: 8 consecutive bytes of memory at address given by registers.

• 汇编代码简单访问 Memory 的方法：

  • 法 1: Normal (%<registerName>)

    即保存在寄存器中的、8 bytes 连续的地址数据对应的 memory 位置。

    也就是说，当把寄存器名称放在括号里时，就是表示把寄存器中数据看作 memory 地址（无论是什么），并用这个地址来引用对应的内存位置。

    例如：(%rax) 就是代表取存放在 %rax 寄存器中的数据对应 memory 位置的引用；

    请牢牢记住，这种在括号内找地址的形式被称为 Simple Memory Addressing Modes（简单内存寻址模式），表示这个模式下，寄存器被看作指针，括号相当于取地址并找到 memory 对应的引用。

   

  • 法 2: Displacement <D>(%<registerName>)

    即保存在寄存器中的、8 bytes 连续的地址对应 memory 的某个位置，以这个位置为基准，向后偏移 D 个 bytes 所对应的内存位置的引用。

    例如：8(%rbp) 就是代表取存放在 %rbp 寄存器中的数据向后偏移 D 个 bytes 的位置对应 memory 的引用；

     

  • 法 3: Most General Form D(<Rbase>, <Rindex>, <Scale>)

    等价于 Memory[Reg[Rb] + S * Reg[Ri] + D]，指使用寄存器 Rb 中的数据为基，加上 S 倍率的寄存器 Ri 中的数据（因此 S 只取 1，2，4，8 这几个之一），最后总体偏移 D bytes；

    注意，Ri 不建议为寄存器 %rsp;

    法 3 就是原始意义上的数组自然引用的方式；

    可以思考为什么 S 只取 1、2、4、8 中的一个。原因很简单，这和它存在的意义有关。我们想在引用数组时，一定希望根据数据类型来缩放索引值，例如 int 需要缩放 4 倍（4 bytes），long 需要缩放 8 倍；小于这些数，则会导致数据错误，大于这些数据会导致空间浪费。

• Rules：以上有些 operand 的组合是不允许的。例如：

  • 直接量作为 destination，没有意义；

  • 为了方便硬件设计，不允许直接从一个内存位置复制到另一个内存位置，必须 2 步：从内存存入指定寄存器，再由指定寄存器存入另一块内存（内存到内存必须经过寄存器）；

• Examples：

  • 例如 movq $0x4,%rax 可能对应的就是 tmp = 0x4;

  • 例如 movq $-147,(%rax)可能对应 *p = -147;

  • 例如 movq %raw,%rdx 可能对应 tmp2 = tmp1;

  • 例如 movq $rax,(%rdx) 可能对应 *p = tmp;

  • 例如 movq (%rax),%rdx 可能对应 tmp = *p;

  • 例如假设下面这段程序可能的汇编代码：

    xxxxxxxxxx
    void swap(long *xp, long *yp) {
        long t0 = *xp;
        long t1 = *yp;
        *xp = t1;
        *yp = t0;
    }
    

    xxxxxxxxxx
    swap:
        movq    (%rdi), %rax
        movq    (%rsi), %rdx
        movq    %rdx, (%rdi)
        movq    %rax, (%rsi)
        ret                     ; 回到之前调用 swap 函数的位置，结束当前函数执行
    

    在上面这个函数体中，%rdi 是保存第一个参数的寄存器，%rsi 是第二个参数寄存器，最多用 6 个，这是在执行此函数前就设置好的。剩下寄存器的选择是由编译器自己决定的，每次编译都可能不太一样；

• Exercises: Address Computation Examples（根据信息填写下表）

  已知寄存器 %rdx 存放数据 0xf000，寄存器 %rcx 存放数据 0x0100。

  Expression	Address Computation	Address
  0x8(%rdx)
  (%rdx,%rcx)
  (%rdx,%rcx,4)
  0x80(,%rdx,2)

  第一行，就是普通 displacement，0xF000 + 0x8 = 0xF008;

  第二行，省略的 general displacement，0xF000 + 0x0100 = 0xF100;

  第三行，省略的 general displacement，0xF000 + 4 * 0x0100 = 0xF400;

  第四行，省略的 general displacement，0 + 2 * 0xF000 + 0x80 = 0x1E080;

3.3.3 Arithmetic & logical operations

Address Computation Instruction: leaq <Src>, <Dst>

指令含义：load effective address（加载有效地址）；

指令目标（很抽象，等会慢慢解释）：相当于 C 的 &（ampersand）符号来计算地址，基于想要计算的地址的一些内容（一般是指定内存引用）。同时也作为一种非常方便的算术运算方式。

指令的大致过程：通俗来说就是传入的内存引用 Src，leaq 会找到这个引用的地址值，并把这个地址传给 Dst，最后 Dst 的值是 Src 引用的地址，相当于 Dst 变成了指针，指向了 Src；

Dst 参数必须是寄存器名称，不能是直接量、内存引用；

Src 参数必须是内存引用，允许使用之前的 Simple Memory Addressing Mode，不能是直接量、寄存器名称；

下面举个例子：

xxxxxxxxxx
long m12(long x) { return x * 12; }

上面的函数对应的汇编代码可以是这样的：

xxxxxxxxxx
m21:
    leaq (%rdi,%rdi,2), %rax
    salq $2, $rax
    ret

首先解释 (%rdi,%rdi,2)，这是上面要求记住的 Simple Memory Addressing Mode，它代表，把 %rdi（即这里存放函数第一参数 x 的寄存器）中的内容看成地址，进行一个 general displacement：%rdi 的值 + 2 * %rdi 的值，这里巧妙地完成了找到 3 倍的 %rdi 的值，把它作为索引，其对应的 memory 地址引用（注：这个地址很可能不能被程序使用，这里只是借助它进行算术计算）；

然后 leaq 将第一参数（3 倍 %rdi 值索引所对应 memory 的引用位置）对应的地址赋给了 %rax 寄存器。到此为止，%rax 中成功获得了 %rdi 中的 3 倍值，中间的方法虽然用到了指针的概念，但本质不是指针操作，是算数操作（慢慢领悟吧）。

最后使用的 salq 指令很简单，就是底层的移位指令（在后面介绍），将 %rax 的二进制值向左移动 2 位，相当于 × 4，总的来说 %rax 的值就相当于原来 %rdi 的值 × 12，完成了 × 12 的操作。

有同学可能会问，为什么不全都给 leaq 来计算 × 12 呢？其实移位在效率上会更快一些。一般 C/C++ 程序在乘常数操作时，会被编译器优化，分解出 $2^k$$2^k$ 的因子，一部分用 leaq 计算，另一部分用 salq 移位。

Some Arithmetic Operations

• addq <Src>, <Dst>：相当于 Dst = Dst + Src

• subq <Src>, <Dst>：相当于 Dst = Dst - Src

• imulq <Src>, <Dst>：相当于 Dst = Dst * Src

• salq <Src>, <Dst>：相当于 Dst = Dst << Src

• sarq <Src>, <Dst>：相当于 Dst = Dst >> Src（算术右移，arithmetic right shift）

• shrq <Src>, <Dst>：相当于 Dst = Dst >> Src（逻辑右移，logical right shift）

• xorq <Src>, <Dst>：相当于 Dst = Dst ^ Src

• andq <Src>, <Dst>：相当于 Dst = Dst & Src

• orq <Src>, <Dst>：相当于 Dst = Dst | Src

切记，别搞错 operands 的顺序！Src 在前，Dst 在后；

• incq <Dst>：相当于 Dst = Dst + 1

• decq <Dst>：相当于 Dst = Dst - 1

• negq <Dst>：相当于 Dst = -Dst

• notq <Dst>：相当于 Dst = ~Dst（注意是按位否）

还有一部分针对 128 bits 的计算，先放在这，不急着背，慢慢消化即可：

• imulq <S>：默认 %rax 中存放另一个 operand，将 S * R[%rax] 的值存放到 R[%rdx]:R[%rax]（high-order 64-bits 由 %rdx 承担，low-order 64-bits 由 %rax 承担）中，针对 signed 数；

  在 64 位架构下，你会发现 R[%rdx]:R[%rax] 的拼接方法表示 128-bits 数是约定俗成的行为。

• mulq <S>：作用与 imulq <S> 相同，不过是对 unsigned 操作；

• idivq <S>：默认被除数（128-bits）存放在 R[%rdx]:R[%rax]，并与 S（64-bits）进行除法，除数存放在 %rax，余数存放在 %rdx。针对 signed 数；

• divq <S>：作用与 idivq <S> 相同，不过是对 unsigned 操作；

• cqto：少见的没有参数的指令。作用是把 64-bits（quad word，默认存放在 %rax）转为 128-bits（octal word，默认存放在 R[%rdx]:R[%rax]），signed extension；

更多指令请参阅 x86-64 指令手册。

下面是个 example：

xxxxxxxxxx
long arith(long x, long y, long z) {
    long t1 = x + y;
    long t2 = z + t1;
    long t3 = x + 4;
    long t4 = y * 48;
    long t5 = t3 + t4;
    long rval = t2 * t5;
    return rval;
}

对应的汇编代码：

xxxxxxxxxx
arith:
    leaq    (%rdi,%rsi), %rax
    addq    %rdx, %rax
    leaq    (%rsi,%rsi,2), %rdx
    salq    $4, %rdx
    leaq    4(%rdi,%rdx), %rcx
    imulq   %rcx, %rax
    ret

这里 %rdi 存放了函数第一参数 x，%rsi 存放了函数第二参数 y，%rdx 存放了函数第三参数 z；

第一步，可以理解为将 %rdi 和 %rsi 值看作地址，找到 %rdi 值 + %rsi 值 对应的 memory 引用，并利用 leaq 将引用代表的地址赋给 %rax，使得 %rax 获得了 %rdi 和 %rsi 值之和的值，之所以不用 addq，是因为 addq 会把结果加到 Dst 上，但这里显然不想修改任何寄存器中的值，只是想把值给到新的寄存器（此步对应 long t1 = x + y;，相当于这里 %rax 存的是 t1）；

第二步，把 %rdx 的值（x）加到 %rax 上，这时的 %rax 存的是 t2（t1 以后不会用了，所以编译器抛弃了，直接用 addq 操作 %rax，这么做可以提升效率，对应 long t2 = z + t1;）；

第三步、第四步，前面说了好几遍，这里说简单一点，就是把 %rdx （原先存 z 的寄存器，抛弃 z 也是因为之后不用 z 变量了，编译器进行了优化）赋以 3 倍的 %rsi 值，并且把 %rdx 的值乘以 $2^4=16$$2^4=16$，总的来说，%rdx 被赋以 48 倍的 %rsi（y）的值，对应 long t4 = y * 48;，这时 %rdx 存放的就是 t4 了；

第五步，简单说就是 %rcx 被赋以 %rdi 的值（x） + %rdx 的值（t4） + 4，可以看到，这里编译器想尽一切办法，把 long t3 = x + 4; 和 long t5 = t3 + t4; 这步合起来了，整整省下来了一个 t3 的操作，可谓优化到极致。所以，%rcx 存的是 t5；

最后一步，编译器实在想不到更好的优化方法，只能勉为其难地调用了唯一一次 imulq，把 %rcx 的值（t5）乘到 %rax 上，对应 long rval = t2 * t5;，函数结束，最后存放 rval 的寄存器是 %rax。

Chapter 4. Machine Level Programming Ⅱ - Control

4.1 Introduction to Condition Codes

4.1.1 Processor State of x86-64, partial

前面介绍过，x86-64 架构具有 16 个寄存器，其中 8 个沿用旧 x86 架构的名称，另外 8 个从 8 ~ 15 命名。可以总结一下，从这些寄存器 / flags 可以看出处理器当前的状态：

• Temporary data：除去 %rsp 的所有 15 个寄存器都是处理器运算时存储临时数据的位置；

• Location of runtime stack：%rsp;（在以后的章节会涉及运行时栈）

• Location of current code control point：%rip

  之前没有见过的寄存器，instruction point，和 %rsp 一样有特殊用途，可以将它看成程序计数器。

  它包含了当前正在执行指令的地址，也不能手动修改，一般是通过获取它的值来进行一些操作；

  它一般由 call 指令 和 ret 指令等修改；

• Status of recent tests: Condition Code

  • 一共 8 种， 现在只说四种，其他的用到再说：CF、ZF、SF、OF;

  • 它们都是 1-bit flag，不是被直接手动设置，而是根据其他指令操作后的结果进行设置（implicit setting）；

  • 是汇编条件操作的基础；

4.1.2 The meanings for Condition Codes

• Single bit register: 这种寄存器不是之前介绍的整型寄存器，它仅存储 1-bit 数据，专门用于存放 condition codes，它们的名称就是对应的 flag 的名称。先介绍其中 4 种的含义：

  • CF: Carry Flag (for unsigned, 将两个 unsigned 相加，MSB 的进位)；

  • SF: Sign Flag (for signed, 当 signed 运算结果的 MSB = 1，说明结果是负值，此位会被置 1);

  • ZF: Zero Flag (上一个计算结果为 0 时，此位会被置 1。依靠算术指令内部实现);

  • OF: Overflow Flag (signed 运算溢出的位。因此可以将 CF 理解为“unsigned 运算溢出的位”);

• 注意：之前说的 leaq 不会设置这些 flags；但之前介绍的算术运算指令会。

• 注意2：也有专门利用计算结果值来设置 flags 的指令：compare 和 test (explicit setting)

4.1.3 Condition Codes: Explicit Setting

Compare: cmpq <Src2, Src1>

• 作用：几乎和 subq 一样，但不修改结果值，因为它计算 Src1 - Src2 并且不会对 Src1/2 进行任何操作，但会由此设置上面 4 个介绍到的 condition codes；

• 内部如何设置 condition codes：主要依据 Src1 - Src2 减法操作。

  • CF set if carry out from MSB (used for unsigned comparisons);

  • ZF set if Src1 == Src2（即 Src1 - Src2 运算结果是否为 0）;

  • SF set if (Src1 - Src2) < 0（即 Src1 - Src2 运算结果的 sign 位是否为 1）;

  • OF set if (Src1 - Src2) in two's complement (signed) overflow（即 (Src1 < 0 && Src2 > 0 && (Src1 - Src2) > 0) || (Src1 > 0 && Src2 < 0 && (Src1 - Src2) < 0)，用的就是判断 signed 溢出的条件：两个同号 signed 相加为异号，说明正/负溢出）;

Test: testq <Src2, Src1>

• 作用：几乎和 andq 一样，但不修改结果值，只计算 Src1 & Src2，并由此设置 condition codes；

• 内部如何设置 condition codes：

  • ZF set when Src1 & Src2 == 0;

  • SF set when Src1 & Src2 < 0;

  • 因为按位且不会导致任何的进位，所以不设置 CF/OF;

• 和上面的 Compare 相比，Test 指令可以进行一个参数的判断，例如 testq %rax, %rax，也把一个参数写成 mask，例如 testq $0x22, %rax;

4.1.4 Condition Codes: Reading

前面说完如何设置，现在称述一下如何读取使用。这里一般不允许直接访问 flags 对应的寄存器，而是用一系列的 SetX instructions 来读取并操作。

SetX Instructions 的作用就是按照当前的 condition codes，来将指定的单个寄存器的单个 byte 设置为 1 或 0；

SetX Instructions 具体的类型如下：

SetX Instructions 都有唯一参数（语法 setX <Dst>），要求是单个寄存器的 low-order 8-bit 的引用名称，这是由这条指令的作用决定的。

看上面的表，就解释一个。以 setl 为例，因为大多数时候我们使用 cmpq 对 condition codes 进行设置，所以当 SF 为 1 时，很可能是 Src1 - Src2 < 0 的情况。但是需要排除 Src1 - Src2 正溢出的情况——正溢出也可能导致结果为负，因此是 SF ^ OF；

最后还有一个问题。setX 是为单个寄存器的单个 low-order 8-bit 设置 0/1，但之前在 3.3.1 中明确说过，我们在 x86-64 架构下一般都讨论 64-bit register 的使用，而那些访问寄存器的 low-order 32-bit（例如 %eax）、low-order 16-bit 的方法用的比较少（在 32 位架构下会多一点）。

而这里，为了条件控制，我们必须访问 64-bit register 的 low-order 8-bit 的位置，这些位置可以由以下名称给出：

• 字母类型命名的 register，不使用前缀 r，而使用后缀 l 就能代表对应的 low-order 8-bit 位置；例如：%rax 的 low-order 1-bit 位置是 %al、%rbx 是 %bl、%rcx 是 %cl、%rdx是 %dl、%rsi 是 %sil、%rdi 是 %dil、%rsp 是 %spl、%rbp 是 %bpl；

• 数字类型命名的 register，使用后缀 b 就代表对应的 low-order 8-bit 位置；例如 %r8b、%r15b 等；

这样操作 64-bit integer register 的 low-order 8-bit，不会影响到其他位的信息；

下面是 example：

xxxxxxxxxx
int gt(long x, long y) { return x > y; }

其对应的汇编代码为：

xxxxxxxxxx
gt:
    cmpq    %rsi, %rdi
    setg    %al
    movzbl  %al, %eax
    ret

已知 %rdi 存放了函数的第一参数 x 的值，%rsi 存放了函数第二参数 y 的值，函数返回的结果就放在 %rax 中。下面逐步分析：

第一步使用了 cmpq 将 %rdi 值 - %rsi 值（即 x - y）计算，并为 4 个 condition codes 进行修改；

第二步，setg 对 %al 操作，这是 %rax 的 low-order 8-bit 的位置，表明如果 ~(SF ^ OF) & ~ZF 成立，即 x > y 成立，那么为 %rax 的 low-order 8-bit 位置置为 1，否则置为 0；显然，这里的 %rax 还需要把前面 7 bytes 全部置为 0，才能成为我要返回的值（(int)0/1），我们应该怎么做呢？

第三步用到了新的指令 movzbl（move with zero extension byte to long）

语法：movzbl <Src>, <Dst>;

作用：把一个 Src 数据引用大小的 0 数据 扩展到 Dst 中（会改变 Dst，但不会改变 Src）;

那么好，问题又来了，为什么我们明明要把 %rax 剩下的所有 7 bytes 全部置 0，但是汇编中写的却是对 %eax（之前提到的，register 的 low-order 32-bit 位置）置 0，剩下的 high-order 32-bit 不管了吗？

⚠ 实际上，这是 x86-64 架构内部令人迷惑的特性。当一个 64-bit register 从 low-order 只被修改 32-bit 数据时，会自动将剩下的 high-order 32-bit 全部置 0。（但是如果只是修改 low-order 16-bit、low-order 8-bit 时，却不会为前面的部分置 0）

到此为止，%rax 中的数据应该长这样：0x000000000000000?（最后一位取决于 setg 到底 set 了什么），这就是我们需要返回的 x > y 表达式的值，所以函数结束。

4.2 Conditional Branches

前一节的例子描述了如何依靠 condition codes 来修改某个寄存器的 low-order 8-bit 的值，这是实现条件分支的基础。

这一节将利用 condition code 来组织条件分支，本质上也是 reading condition codes；

4.2.1 JX Instructions 【Old】

• 语法：jX <LABEL>，这里的 <LABEL> 是汇编程序中的一个段落标签，在具体例子中会展示。

  还有一种语法，会在 4.4 中介绍。

• 作用：有条件（根据 condition codes）/ 无条件跳转到指定部分的汇编代码继续执行；

• 具体类型（和 SetX Instructions 使用名称类似）：

  jX	Condition	Description
  jmp	1	Unconditional
  je	ZF	Equal/Zero
  jne	~ZF	Not Equal/Not Zero
  js	SF	Negative
  jns	~SF	Nonegative
  jg	~(SF^OF)&~ZF	Greater (signed)
  jge	~(SF^OF)	Greater or Equal (signed)
  jl	(SF^OF)	Less (signed)
  jle	(SF^OF) | ZF	Less or Equal (signed)
  ja	~CF & ~ZF	Above (unsigned)
  jb	CF	Below (unsigned)

• Example：

  xxxxxxxxxx
  long absdiff(long x, long y) {
      long result;
      if (x > y) result = x - y;
      else result = y - x;
      return result;
  }
  

  对应的汇编代码如下：

  xxxxxxxxxx
  absdiff:
      cmpq    %rsi, %rdi
      jle     .L4
      movq    %rdi, %rax
      subq    %rsi, %rax
      ret
  .L4:
      movq    %rsi, %rax
      subq    %rdi, %rax
      ret
  

  已知 %rdi 保存的是函数第一参数 x，%rsi 保存的是函数第二参数 y，%rax 保存函数返回值。

  再次说一下，汇编函数返回前只需要把返回值放在特定的寄存器中就行，只要调用方清除你放在哪就行。比如这里放在 %rax，那么函数结束后，调用方会去 %rax 访问结果。

  第一步 cmpq 根据 %rdi 值 - %rsi 值 来设置 condition codes；

  第二步的 jle 对应的条件是 (SF ^ OF) | ZF，结合上一步也就是 x ≤ y 时，跳至 .L4 标签标记的位置继续执行。

  这里 .L4 是一个标签，. 开头表示它是内部的操作或标签，只会出现在汇编代码中，不会出现在目标代码（机器代码）中，所以不会被当作独立的函数。

  有同学会说，不是说汇编代码就是机器代码的文本表示吗？为啥还有差别？

  其实是这样的，汇编代码相对于机器代码，在转换为易读的文本同时，会把一些指令地址设置成内部标签。在汇编转机器代码时，会再计算代入回去。不然你读 jle 0x0F0E2310 肯定没有 jle .L4 好读。

  后两步的含义已经比较简单了，不再赘述。

  上面的内容类似 C/C++ 中的 goto 语句，不建议在 C/C++ 中使用；

4.2.2 General Conditional Expression Translation & Conditional Moves

本小节介绍了 “条件移动” 这种编译器优化的方式，告诉我们在有些情况下，编译器将条件控制一味地翻译成 JX Instructions 不见得是最好的；同时也指明了不应该使用 “条件移动” 优化的情形。

上面介绍的 JX Instructions 真的适合编译器使用吗？效率是最高的吗？如果仔细看上一节标题会发现有一个 “【Old】” 的标志，这说明现在不经常用到它了。如果效率不佳，那么有哪些方法可以考虑呢？为什么呢？

如果编译器将 C++ 代码翻译为上面的 JX Instructions，那么这种翻译被称为 General Conditional Expression Translation，这也是最自然的方法：如果满足某个条件就跳转到哪里执行，否则如何如何。

还有一种方法被称为 条件移动（Conditional Moves），是将 C/C++ 代码中的条件分支（if-else）的 “then” 分支和 “else” 分支全部执行，最后按照条件再决定将谁移动到结果寄存器中。

伪代码如下：

xxxxxxxxxx
result  = the value of Then_Expr
eval    = the value of Else_Expr
cond    = !(the value of Test)
if (cond) result = eval

return result

有人说，这把 then 子句和 else 子句都运行了，平均的时间复杂度上不是会比之前的 General Condition Expression 更浪费时间吗？其实不然，这里的知识和后面章节的 “流水线” 有关。

因为现代处理器采用 “流水线（pipeline）” 的运行方式，在到达一行代码时会关联甚至运行下面几行的代码。现代处理器大概可以同时处理 20 行左右的指令深度（主要取决于事先读入的指令条数）。当运行到含有分支的部分时，处理器会采取 “分支预测技术”，根据上下文猜测会运行到哪个分支，并将猜测的分支事先读入流水线。

如果猜对，那么执行非常迅速，直接读取流水线上的信息，并离开这个分支；但是如果猜错，那么将停止执行当前流水线上的代码，并重新读入另一段分支。这是个耗时操作，较差情况下会花费 40 个时钟周期（40 步普通指令执行时间）。

因此，在某些情况下，使用 Conditional Moves 的条件判断方法可能会比 General Conditional Expression 更高效。

正因如此，大多数编译器在某些情况下都选择 Conditional Moves，而不是上面的 JX 指令（代表 General Condition Expression），所以你几乎看不到 4.2.1 中的汇编代码。如果实在想看到，那么在用 gcc 编译时，给定参数 -fno-if-conversion，这样不允许编译器使用条件移动。

所以在 4.2.1 中大多数情况下的汇编代码应该长这样：

xxxxxxxxxx
absdiff:
    movq    %rdi, %rax
    subq    %rsi, %rax
    movq    %rsi, %rdx
    subq    %rdi, %rdx
    cmpq    %rsi, %rdi
    cmovle  %rdx, %rax
    ret

再稍微解释一下，第一步是将 %rdi 的值（即函数第一参数 x）赋给 %rax；

从第二步开始就是条件移动的方法了：第二步先把 %rax 的值（x）减去 %rsi（y），相当于先做了 then 分支的内容；

第三步是将 %rsi 的值（y）移动到 %rdx 中，并再第四步把 %rdx 的值减去 %rdi（x），相当于完成了 else 分支的内容；

到目前为止，%rax 中存放 x - y 的值，%rdx 中存放 y - x 的值；

第五步才是按照 x、y 的值来设置 condition codes；

最后一步是一个新指令：cmovle;

• 语法：cmovle <Src>, <Dst>；

• 作用：条件移动，按照当前 condition codes 的状态进行移动。其中 cmov 就是 conditional moves，le 就是之前的 X 情况（小于等于情况），所以猜测还有 cmovl、cmovge、cmovg……

但是，上面说 Conditional Moves 更快是在“某些情况下”，那么什么是 “另外的情况”？

现在介绍在什么时候，汇编的翻译不应该用 Conditional Moves：

Situation 1: Expensive Computations

xxxxxxxxxx
val = Test(x) ? Hard1(x) : Hard2(x);

这种 then 子句和 else 子句都非常难以计算的时候，不应该用条件移动。因为重新读入流水线的时间很可能会少于把两个子句都计算一遍的时间；

Situation 2: Risky Computations

xxxxxxxxxx
val = p ? *p : 0;

上面的判断语句必须先判断再进行执行，否则会出现程序错误，尤其是在指针的判断上；

Situation 3: Computations with side effects

xxxxxxxxxx
val = x > 0 ? x*=7 : x+=3;

上面的 then 和 else 子句一旦执行，会破坏程序的原义，造成意想不到的后果。

4.3 Loops

4.3.1 Do-While Loop

对于一个计算 x 代表的二进制代码中的 1 的个数的函数：

xxxxxxxxxx
long pcount_do(unsigned long x) {
    long result = 0;
    do {
        result += x & 0x1;
        x >>= 1;
    } while (x);
    return result;
}

它的汇编代码非常简单，就可以用 General Conditional Expression 的方法，结合 JX Instructions 实现：

xxxxxxxxxx
pcount_do:
    movl    $0, %eax
.L2:
    movq    %rdi, %rdx
    andl    $1, %edx
    addq    %rdx, %rax
    shrq    %rdi
    jne     .L2
    rep; ret

对应的伪代码：

xxxxxxxxxx
    preparations
loop:
    Body
    if (Test)
        goto loop

这里注意一下，movl 和 andl 都不算新的指令——之前说过 q 的含义代表操作数的位数，quad 指 4 字（4 × 16 bits），l 就指 2 字，2 × 16 bits；

4.3.2 General While Loop Translation #1 - "Jump to Middle" Translation

从 do-while 到 while 只需要更改一下测试条件的顺序就行。例如上一节的代码改成 while 循环：

xxxxxxxxxx
long pcount_do(unsigned long x) {
    long result = 0;
    while (x) {
        result += x & 0x1;
        x >>= 1;
    };
    return result;
}

那么对应的汇编伪代码可以是（一般在编译器优化等级 -Og 时出现）：

xxxxxxxxxx
    goto test;      // 先测试
loop:
    Body
test:
    if (Test)
        goto loop;  // 通过再进循环体
done:
    // ...

4.3.3 General While Loop Translation #2 - "Do-while" Conversion

如果把编译器的优化等级调至 -O1，那么编译器在处理 while 循环时不会采用上面的 ”Jump to Middle“ 的翻译策略，而是采用 转换为 do-while 循环 的策略，这样会更加高效。

这相当于把 C/C++ 代码中：

xxxxxxxxxx
while (Test) {
    Body
}

换成了：

xxxxxxxxxx
if (!Test)
    goto done;
do {
    Body
} while (Test);
done:
    // ...

具体的汇编伪代码会变成：

xxxxxxxxxx
    if (!Test)      // 仅进入前判断一下，接下来就变成 do-while
        goto done;
loop:
    Body
    if (Test)
        goto loop;
done:
    // ...

从这个优化上可以看出，其实 do-while 循环会比 while 循环更高效，但现在的编译器比较智能，只要优化等级不低，这个方面会帮你优化掉的。

4.3.4 For Loop

for loop 的汇编实现没那么简单，我们可能需要向 while 或 do-while 上看齐。比如对如下 for 循环：

xxxxxxxxxx
for (Init; Test; Update) {
    Body
}

编译器可以转换成 while 循环，如果使用了 -O1 优化，会优化到 do-while：

xxxxxxxxxx
Init;
while (Test) {
    Body
    Update;
}

// -------------

Init;
if (!Test) {    // do-while 前的测试块（Initial Test）
    goto done;
}
do {
    Body
    Update;
} while (Test);
done:
    // ...

很多时候，-O1 下的编译器甚至可以识别 Init 块 和 do-while 前的测试块的关联，并且合理舍弃前置的测试块。

4.4 Switch Statements

将 C/C++ 的 switch 语句翻译为汇编是相当有难度的。首先应该弄清楚 switch 语句在 C/C++ 中的一系列特性：

• Match integer values；

• Fall through cases：当 case 中不存在 break 时，会一直向下运行；

• Merge cases：当一个 case 中没有任何内容时，相当于并入下一个 case（上一点的特例）；

• Default case：对于没有匹配的 cases，会进入最后的 default case（如果有的话）；

当然，现代的编译器对于 switch 语句的翻译绝不是一系列的 if-else 语句的翻译，而是利用了一个数据结构：跳表（Jump Table Structure）；

如下图，switch-case 语句就像一串代码块，每个 case 就是一个块。编译时，switch-case 块会整体一起编译（如下图 Jump Targets），转为汇编指令后，每个块的汇编指令所对应的地址会被存储在一个跳表中（如下图 Jump Table）。这样在根据条件调用相应代码块时，只需要 goto 跳表中的对应地址（ray indexing）就能完成任务，无需一个个比对条件。

那么，汇编代码是如何在跳表中找到合适的地址的呢？举个例子：

xxxxxxxxxx
long switch_eg(long x, long y, long z) {
    long w = 1;
    switch (x) {
    case 1:
        w = y * z;
        break;
    case 2:
        w = y / z;
        /* Fall Through */
    case 3:
        w += z;
        break;
    case 5:
    case 6:
        w -= z;
        break;
    default:
        w = 2;
    }
    return w;
}

上面的例子对应的汇编代码可以是（一部分代码）：

xxxxxxxxxx
switch_eg:
    movq    %rdx, %rcx
    cmpq    $6, %rdi
    ja      .L8
    jmp     *.L4(,%rdi,8)

逐步解释：

第一步将 %rdx（第三参数 z）赋值到 %rcx 寄存器中；

第二步就将 %rdi（第一参数 x）与常数 6 进行做差比较（为什么是 6？因为在源码中 6 是最大的 case），以此修改 condition codes；

第三步 ja 表示只要 %rdi（x）的值（看作 unsigned）在 6 之上，那么就跳至 .L8（看来是 default 片段），否则第四步会无条件跳至某个位置；

这里编译器处理的非常巧妙：使用 ja（unsigned above）而不是 jg（signed greater），这样同时把 x > 6 和 x < 0 的情况都算入 ja 的条件中，进一步提高了效率；

这里还需要解释一下，之前没有提到的 JX Instructions 的使用语法。除了 jX <LABEL> 直接跳转至对应标签（direct jump），另一种方法是间接跳转（indirect jump）：jX <effectiveAddress>；

参数是有效地址，可以是寄存器名称，也可以是右值，例如这个例子中 jmp *.L4(,%rdi,8)，后面的部分 .L4(,%rdi,8) 应该很熟悉了：因为标签会被汇编器翻译为代码段的地址，所以它就是 .L4地址 + 8 * x（%rdi 的值是 x），并把这个值看作 memory 的地址。前面的 * 星号就是直接取地址上内容的意思（和 C/C++ 的相同），可以理解为 leaq 相反的过程；这个 memory 地址中的值就是跳表中的一个代码段的地址，所以取出来的也是地址；

第四步跳转的位置如何，我们需要看看剩下来的汇编代码（跳表部分）：

xxxxxxxxxx
            ; read only data
.section    .rodata ; 这行和下一行是为了构造跳表的基本结构
    .align  8       ; 伪对齐指令，指明下面的变量必须从下一个能被 8 整除的地址开始
.L4:                ; 代码块按照 x 的值的顺序进行排列
    .quad   .L8     ; x = 0 的情况
    .quad   .L3     ; x = 1
    .quad   .L5     ; x = 2
    .quad   .L9     ; x = 3
    .quad   .L8     ; x = 4
    .quad   .L7     ; x = 5
    .quad   .L7     ; x = 6

如上所示，跳表的结构是由汇编代码指定的，如何填这个表是汇编器的工作，不是编译器的工作；

在编译器生成的汇编代码中，.quad 只是个声明，标记表示这里是一个 4 字（4 × 16 bits）的数据，以后汇编器需要填上后面指定标签指令段的地址；

我们可以发现，x < 0 和 x > 6 的情况在之前的代码中被 ja 处理，跳至 .L8（default 代码段），剩余在 switch 中整数缺省的情况（x = 4 和 x = 0）也会自动转至 .L8;

主干看完了，继续看之前提到的各个代码段的汇编代码：

xxxxxxxxxx
.L3:                    ; 对应 x = 1 的情况的代码段
    movq    %rsi, %rax
    imulq   %rdx, %rax
    ret