课程视频:https://www.bilibili.com/video/BV1iW411d7hd?share_source=copy_web

Lecture02:Bits,Bytes,and Integer

浮点数的二进制表示:100010.101=1*2^5+1*2^1+1*2^(-1)+1*2^(-3)

4个bit分为一组—>十六进制

x86-64上的数据类型:

char 1字节—8位
short 2字节—16位
int 4字节—32位
long 8字节—64位
float 4字节—32位
double 8字节—64位
long double 10/16字节(只使用10个字节，当在64位机器上使用时，额外6字节被浪费—保证了一切以16字节对齐)

64位机器、32位机器:地址是64位或32位(即pointer的大小)

位移操作(shift)

左移(left shift):将bit-vector向左移动,将溢出位舍弃,在右边填0

右移(right shift):将bit-vector向右移动,将多余位舍弃

signed的逻辑右移(logic shift):在左边填0

signed的算术右移(Arithmetic shift):在左边复制符号位(为什么没有算术左移?左移相当于执行了一次可能会溢出的乘法)

注意:移动<0的数或大于等于数据字节长度的行为,都是UB

二进制到unsigned,signed的转换(T表示two’s complement,即二进制补码形式):

$B2U(x)=\sum_{i=0}^{w-1}{x_{i}*2^{i} }$ $B2T(x)=-x_{w-1}*2^{w-1}+\sum_{i=0}^{w-2} {x_{i}*2^{i} }$

即最高位取负数,其他不变,若最高位为1,则一定是负数(最大为-1)

$UMin=0,UMax=2^{w}-1,TMin=-2^{w-1},TMax=2^{w-1}-1$

|TMin|=TMax+1

UMax=2*TMax+1

B2U,U2B(对同一个bit-vector,建立从signed到unsigned的映射)

注意:在C中,默认常量都是signed,如要使用unsigned需要添加后缀”U”,如0U,4294967259U

当signed,unsigned被混合运算时(如大小比较),signed总被转化成unsigned(bit-vector保持不变,仅仅是转换方式变化)

signed extension(如32位拓展到64位):signed在左边复制符号位(类似算术右移),即从符号位开始的一连串1,可等价于将这串1中,最低位作为符号位

Lecture03:Bits,Bytes,and Integers cont

Unsigned Addition :相加后无论”多出”的一位是什么,都舍弃掉,可理解为模运算,即 $UAdd_{w}(u,v)=(u+v)mod {2^{w} }$

Two’s complement Addition:等价于将两个数都转化为unsigned计算后再转化为signed(即按位相加)

正溢出(positive):两个较大正数加在一起使符号位变成1,即得到负数

负溢出(positive):两个较小负数加在一起使符号位变成0,即得到正数

.png)

Unsigned Multiplication:相乘后多余位舍弃,可理解为模运算,即 $UMult_{w}(u,v)=u*v mod{2^{w} }$

Signed Multiplication:当作unsigned相乘后舍弃多余位,剩下的首位作为符号位,如55=25—>11001—>1001—>-7,若相乘后的数字可以用目前位数表示,则结果正常(注意,这里相乘后的数字指的是*signed相乘结果,而不是转化成unsigned后的相乘结果)

注意,负数算术右移时,结果会向负无穷舍入,而不是零(即左侧,事实上这就是二分中通常用>>1的原因),如果想要向零舍入,需要添加一个偏移量(添加偏移量的操作,编译器会在使用除法时自动添加,然后在实施右移)

??C语言对signed的右移是算术还是逻辑右移没有明确规定,绝大多数情况下是算术右移

移位操作消耗1计算周期,而乘法操作消耗3个计算周期(通过各种硬件优化),除法操作消耗30个计算周期

signed取相反数(x—>-x):将所有位取反,再+1,故Tmin=-Tmin

数据是如何存储的:在64位机器中,地址有64位,可以将内存系统理解为一个巨大的char数组,每一个char占据一字节,64位地址能表示的下标从0~2^64,故最多存储2^64字节数据(实际上目前能使用的最大内存地址是47位,对应的内存大小大约是128TB),实际上,只是程序认为它可以使用这么大的空间,当程序运行时,系统会规定其能访问的内存区域,如果程序试图访问其他区域,将报错(即segementation fault)

一般情况下,数据类型的地址取其占有的bytes的最低位地址,如64位地址占据了0000~0007这8个byte,这该地址是0000,类比0008~0015是0008;而32位地址同理,0000~0004是0000,0005~0007是0005(地址表示一般情况下使用十六进制)

字长(Word Size):没有明确规定,当我们提及64位机器时,指的是其pointer/地址大小是64位(尽管只使用了47位)

使用GCC编译时,可以指定它是64位还是32位,会生成两种不同类似的object code,即硬件本身不一定定义字节大小,是硬件和编译器一起决定(64位的代码也可兼容32位机器)

multi-byte word是如何在内存中排序的?

小端序(little endian):最低有效byte拥有最低位地址(x86,IOS,Windows,ARM processors running Android)

大端序(big endian):最低有效byte拥有最高位地址(PPC MAC,Internet)

如15213=3B6D(十六进制)

在小端序中:6D 3B 00 00

在大端序中:00 00 3B 6D

例外:无论是小端序还是大端序,char数组的存储顺序都是相同的,即都符合大端序,’/0’放在最高位

实际上,ARM的硬件配置为既能处理小端序也能处理大端序

Lecture04:Floating Point

小数/分数的二进制表示: $\sum_{k=-j}^{i}{b_{i}*2^{k} }$ (小数点左侧0~i,右侧-1~-j)

如果是分数—>依次减1/2,1/4,1/8判断该位是否为1

如果固定位数,将point左移,则能表示的最大值变小了,精度变大;将point右移,则精度变小,能表示的最大值变小了,故采用floating point,即浮点来表示小数

IEEE(电气电子工程师学会) floating point:

形式: $(-1)^{s}*M*2^{E}$

Sign bit 表示了该数是正是负;Significand/Mantissa表示一个介于[1.0,2.0)之间的值;而Exponent表示了该值要乘上2的多少次方

单精度浮点数(32位):s占一位,exp占8位,frac占23位;双精度浮点数(64位):s占一位,exp占11位,frac占52位;80位浮点数(Intel only):s占1位,exp占15位,frac占63位或64位(所以为什么不直接取64位呢?)

Normalized values:

exp域(阶码字段)决定了E,但不等于E,同时,exp域不能全为0或全为1.exp域视作一个unsigned number,exp域的值-bias(偏移量,值为 $2^{k-1}-1$ )后才是E.(example:exp占8位,则bias为127,exp域本身的范围是1~254,加上偏移量后是-126~127).

注意,为何不用exp域不使用signed number的标准—>便于浮点数之间比较

significand域(尾数域/frac)决定了M,但不等于M,其采用隐含编码法.即假设M=1.xxxxxx始终成立,可以省去一位来表示小数点前的1,所以尾数域全0时尾数最小为1,尾数域全1时尾数最大,极其接近2.0

Denormalized values:

来源:当我们想表示0or非常接近0的数时,尾数域隐含的1限制了我们

解决措施:当exp全为0时,其值不是0-bias,而是1-bias.同时,尾数域隐含的1变为0,即0.xxxxxx

example:

exp全为0,frac全为0,则此时值为0,但注意有(+0和-0的区别)
exp全为0,frac不全为0,则此时值很接近0(0.xxxxx的-126次方)

Special values:

当exp全为1时:

若frac全为0,则表示一个 ${\infty}$ ,如 $1.0/0.0=-1.0/-0.0={+\infty}$ , $1.0/-1.0={-\infty}$
frac不为0,表示Not-a-Number(NaN),表示无法确定的值,如sqrt(-1), ${\infty}-{\infty}$ , ${\infty}*0$

.png)

相关性质:比较浮点数的大小时,除了NaN,都可以将其视作unsigned number比较(即从高到低依次相比):正数总是比负数大;当exp不全为0时,exp域大的数总是比exp域小的数大(最高位是隐含的1);当exp全为0时,尾数域大的总是比尾数域小的数大

Floating Point Operations(addition,multiplication)

rounding(舍入):

towards zero(向零舍入)
round down(向负无穷舍入,即舍入后的值<=舍入前的值)
round up(向正无穷舍入,即舍入后的值>=舍入前的值)
default:nearest even(向最靠近的值舍入,偶数优先,如1.4-1,1.6-2,1.5-2,2.5-2,-1.5—2)

为什么采用IEEE采用nearest even作为默认舍入规则:当给定足够多数据时,这些数据有50%的概率增加或减少,故平均值保持不变(可能不够严谨,但至少能说明为什么该规则较优)

而应用到二进制数上:偶数即有效位的最低位是0,而中间值(即’0.5’)是10000….,其他都同理

Floating Point Multiplication:

符号位取异或,exp域相加,尾数域相乘

如果尾数域>=2,右移,增加exp

如果exp超出范围,overflow

对尾数域相乘结果进行舍入以对应尾数域精确度

Floating Point Addition:

首先对齐小数点(即exp域取二者中较大值),然后相加

若尾数域>=2,右移,增加exp

若尾数域<1,左移k位使其>=1,exp减少k

如果exp超出范围,overflow

对尾数域相加结果进行舍入以对应尾数域精确度

注意,浮点数的加法,乘法均不满足结合律,如(1e20+3.14)-1e20=0,(1e20-1e20)+3.14=3.14

(1e20*1e20)*1e-20=inf,1e20*(1e20*1e-20)=1e20

在”自然”条件中,值通常是连续的,即不会相差太大,浮点数的该性质通常不会产生影响.但是在非自然条件中,如金融行业中的计算,需要注意该性质对结果的影响.

C语言中的浮点数

当浮点数和int之间发生类型转化时,不能保持bit-vector不变而只改变翻译方式

double/float—>int:

截去小数(效果如同向0舍入)
当浮点数的值超出范围或者为NaN时,没有定义,通常情况下会设置为TMin

int—>double:

如果int的位数小于等于53(double的尾数域长度),值将不会改变

int—>float:

同理double,若尾数域长度小于int位数,将会发生舍入

Lecture05:Machine-Level Programing I:Basics

一般说machine program有两种含义,一是计算机实际运行的object code(是一系列代表着实际操作的字节);二是汇编代码(编译器的目标便是将代码转化成汇编代码).二者是一一对应的.

x86机器有两种汇编语言,一种是Intel和Microsoft使用的,一种是Linux使用的(本课程使用).二者参数顺序不同.

本课程采用的是英特尔64位processors(处理器)的指令集

英特尔processors的历史:

x86是对英特尔processer的一个口头称呼,因为芯片名字都含有86

x86的特性总是不断进化\重叠,其指令集或许不是最清晰易懂的,却是最uesful的

80年代的RISC(reduced instructions set computer,即精简指令集计算机)和CISC(complex instructions set computer,复杂指令计算机.实际上,CISC是RISC派给以前的处理器起的名,带有贬义色彩,乐)大战

英特尔采用CISC架构

8086:1978年推出,是第一个16位Intel processor,有1MB的内存空间,其一个变种是IBS和DOS的基础

386:1985年推出,也被称作IA32,因为其是第一个32位Intel processor.添加了”flat addressing”,能运行Unix或Lunix

Pentium 4E:2004年推出,也被称作x86-64,因为其是第一个64位Intel processor(其也可运行32位代码,避免了software从32位到64位的长久迭代)(到这一代为止,Intel processor的性能都在逐步提升,但面对着功耗过高的问题,引出了多核processor(可以理解为在一个芯片上塞多个处理器))

Core 2:2006年推出,是第一个multi-core(多核)Intel Processor

Core i7:2008年推出,其拥有4个core

Processors有Desktop Model(一般功率更高)和Server Model(Cores一般更多)两种

.png)

DDR:processor链接到主存储器的方式,即DRAM/动态RAM

PCI是与外部设备的连接

SATA是与不同类型盘的连接

Ethernet(以太网接口)连接到一个网路

这些逻辑单元和处理器一起组成了芯片

Advanced Micro Decvices:AMD(Intel的对手,和Intel之间吵过专利,结果是AMD被允许生产x86处理器)

AMD提出了64位英特尔扩展程序

2001年,Intel投入大量资金,试图从IA32转变到IA64,在市场上没有成功

而AMD将寄存器变大,只是将东西从32位变成64位,并获得了成功,于是Intel跟随其脚部继续推出x86

ARM(Acorn RISC Machine),一家公司推出的自家芯片,然后公司华丽丽的破产了,但是其指令集非常高效且简单,可以设置在芯片上,且可定制

所以ARM现在是一家位于英国剑桥的公司,向其他公司出售使用其设计的许可权利(其比x86机器功耗更低)

如前言所说,编译器的目标是将你的code转化成电脑操作的指令,但有些指令更简单,却需要更多硬件,有些指令很繁琐,但不需要什么硬件条件,而如何最好的实现指令集,是硬件研究者的工作

.png)

pc:Program counter,存储下一条指令的地址,在x86-64中被称作”RIP”

condition code:存储操作的状态信息,在branching(“分支”)中使用

Memory:可以视作一个巨大的字节数组,实际上是操作系统和硬件协调产生的一种”虚拟内存”,每个软件都有自己独立的字节数组,而在物理意义上,所有软件都共享这些字节数组(cache指的是多次访问同一位置的内存总是更快,但注意,在指令层面,你无法直接操作cache)

将C 转变成object code:

.png)

第一步是将C代码变成汇编代码(gcc -Og -S,-Og是对编译器进行什么优化的规范,O是指Optimize,如果不加,将不会进行任何优化,;-S意思是Stop,只做第一部分,即将C代码变成汇编代码)

第二步是通过汇编程序(Assembler)运行它,将文本形式的代码转化成字节形式

第三步是通过链接器(Linker),将不同的文件融合在一起

(你的各个代码文件和库代码)

实际上,当真正开始运行这个程序上时,有些库是在首次启动时动态导入

1.将C转化成Assembly(汇编代码)

.png)

pushq:将某个数据压入栈中

movq:将某个数据移动位置

call:调用某个procedure(操作序列)

ret:从一个特定的函数返回

汇编代码中的数据类型:

.png)

Integer类型:存储整数(不区分signed,unsigned,C中的pointer等数据类型也以该形式存储)

Floating point类型:以不同的方式处理,使用不同的寄存器组

Code:定义了一系列操作的字节序列

结构体等数据类型,都不存在于机器代码中,都由编译器来定义

2.将汇编代码变成object code

.png)

一些指令可能只有1byte,但也有些指令有15bytes(不同指令所代表byte长度不一定)

变量的所有名称,在汇编代码,机器代码级别完全丢失(变成了寄存器和内存中的某个位置)

.png)

disassembler/反汇编(顾名思义,将object code逆推成汇编代码)

.png)

gdb:强大的debugger,可以在存在source code的情况下进行调试,不存在source code时,也可进行调试,其也具有反汇编功能(disassemble xxxx)

x/14xb sumstore—显示从sumstore地址开始的14个十六进制byte

更多的汇编基础知识:

.png)

注意:如果你使用%r版本,使用的是64位register;如果你使用%e版本,使用的是32位register(实际上,%e版本只是使用了%r版本的低32位,同理,8位,16位都可取到)

rsp是特殊的寄存器,被称为栈指针(stack point)

左半部分寄存器(除rsp)的命名来自其原始用途,现在这些名字只是历史遗留问题,在大多数情况下,他们都可用于保存数据

.png)

注意,从IA32到64位处理器,寄存器数量增加了一倍

movq operation:

.png)

注意,不能将内存中的数据直接移动到内存中的另一个地方,需要两次操作(Mem-Reg,Reg-Mem)

.png)

(%xxx)表示对该寄存器所存储的地址解引用

D(%xxx),D是一个数字,表示对该寄存器所存储的地址加一个偏移量后解引用

.png)

swap函数示例

对地址解引用的更多操作:

.png)

leaq(load effective address):地址操作

有些乘法操作可以转化成leaq,如*12—>*3再*4

.png)

Lecture06:Machine-Level Programing II:Control

Condition codes:

.png)%rip:指令指针(instruction pointer,在IA32中中叫%eip),包含正在执行指令的地址,无法通过正常方式操作(可通过技巧获取它的值)

condition codes一共有8个,图中只展示了4个,都只有1bit

.png)

CF:在二进制加法时,表示是否进位(翻译为溢出更恰当?)

ZF:当计算结果为0时被置位

SF:计算结果最高位为1时(signed)被置位

OF:当signed计算溢出时被置位(包括加,乘?)

注意,lea不会操作这4个condition code

专门操作condition code的指令:

.png)

获取condition code的手段:

.png)

setX根据condition code的状态,将目标寄存器的低位,置1或置0,以此来知道最近的指令做了什么

sete,setne表示上次指令的结果是相等或为零

sets,setns表示上次指令的结果的正负性(没有考虑溢出)

setg,setge表示上次指令的结果是大于(大于或等于),这里用了~(SF^OF)表示大于或等于,即考虑了正溢出和负溢出,保证了比大小不会因为溢出出错

setl,setle同理

setb表示上次指令结果是否溢出(unsigned)

.png)

%xxl表示寄存器的最后一位(l—low)

setX示例:

.png)

PS:x86-64的小特性:当你操作32位寄存器时,会将寄存器的其余32位置为0.

而byte(如short)操作不动其他位(更低位也如此)

Conditional branches:

if和else

传统的实现方法:jump instruction

unconditional jump(无条件跳跃)

conditonal jump(有条件跳跃)

.png)

示例:

.png)

.XXX:label,在object code中并不存在(代表了指令的地址?)

优化:Conditional Moves(类似于先将if的结果和else的结果都算出来,根据条件值判断使用哪个)

先猜测条件结果(大部分情况下都能猜对),并直接开始计算

.png)

可以类比工厂的工作流水线,可以同一时间处理多条指令,而不是卡在条件指令,使之更有效率

示例:

.png)

注意,conditional move仅在分支计算都很简单的时候能提高效率,在某些情况下甚至有风险(如解引用NULL指针),有时计算结果影响条件判断

.png)

loops:

.png)

dowhile循环的实现

-Og级别的while:

.png)

-O1级别的:

.png)

for循环

.png)

类似while循环

.png)

采用O1优化时,会删除初始化之后的一个test(因为一定对)

switch:

.png)

switch会生成一个类似于数组的jump table,以快速定位提高效率

.png)

注意,从0到x的最大值均有其标签(如果出现负数,会添加一个bias使下标从0开始)

若是x的范围过大且相对稀疏(如x为0和1000000,会使用二分优化成if else)

.png)

break代码块:

.png)

注意,switch后即为return w,故将ret写在代码块内

.png)

只有case3中的指令需要w初始化,故将w初始化放在case3中.

case2fall-through到case3中,故在初始化后添加merge标签供case2跳转