一下子就到七月了，我六月的总结并没有写，因为六月比较忙…前半个月急着复习。后半个月忙着玩儿和打游戏。

上次说这个学期希望绩点高一点，我对这个学期的绩点还算比较满意吧，好歹花了很多时间精力在上面。然后是时长两周的小学期，感觉还是很不错的，前端的基础知识稍微巩固了一下，同时学习了很多新的东西，相较于刚开学的时候自己学前端，现在很多思路就很清晰。项目实践也比较容易上手。最有意思的是接触了一下XSS漏洞，发现网络安全也是很有意思的，并没有想象中的那么难，感觉是一个很好的上手点。

然后就是联系了一位老师做我的导师，他的方向是混沌密码学，他建议我尝试将混沌密码学用于图像编码，以此作为研究方向。让我去研究一些相关的知识和阅读其他的论文。但是感觉我的数学和英语基础还是比较薄弱，这样也是我需要加强的地方。

接下来的话，做下暑假的安排吧，我就先规划一下七月的，八月的之后再说：

• 首先是CSAPP的学习从现在开始的一周内，至少要学到第七章链接。
• 然后是接下来时间争取能学完第九章，在八月份之前。
• 平时累了的时候要着手开始学习算法，目前的打算是跟着OIwiki入门，争取每天写2~5题，学一个新的知识点
• 在时间有多的情况下，要开始学习Java，因为之后的很多知识都不可避免的要用到它
• 坚持每天都要背单词，先把四级背完
• 然后是这个月要把科目二结束，争取下个月可以把科目三过完

感觉暑假要做的事情很多，当然，可以做的事情也很多。要抓住这个机会，提升强化基本功能力，好迎接下个学期大量的专业课程和专业知识。加油呀相信自己。

我有时候也会在想自己为什么要学的这么辛苦，是因为喜欢吗，是为了更优秀一点吗。可能都有吧，关键是我想这么做，也许想学的时候也会学一学吧，想玩的时候也会好好玩一下吧。也许我的目标和规划做的到，也许做不到。但是没关系，我想这么做就行了。

文章原文：mov is Turing-complete ——by Stephen Dolan，Computer Laboratory, University of Cambridge

不使用特殊的寻址模式，代码自修改，和运行时生成代码。用mov实现图灵完备的模拟器

介绍

我们在学习下x86的指令集中我们时常会用到MOV指令。我们通常使用它的多种寻址模式：

• 用于内存数据的加载和存储
• 加载立即数到寄存器中

但是它并不具备比较和分支跳转的功能，所以我们一般认为MOV不是图灵完备的

但是实际上在x86的处理器中，我们可以通过mov来加载或者自修改代码来实现图灵完备性，但是这并不是我们想要的。

执行有限数量的mov指令将会在有限时间内结束。为了验证它的图灵完备性，所以我们需要无限循环。因此我们的图灵机将由一系列mov指令组成，执行完成后无条件跳转到第一条指令继续执行。

机器模型

我们将使用一个简单的抽象机器模型，我们介绍其组成：

• 一个由字组成的随机存储内存：每一个字可以存储一个内存地址或一个偏移值（偏移值只能是0或1，其中偏移值不被视作一个有效的内存地址）
• n个寄存器R₁ R₂ … R_n ：我们暂时假设我们会用到很多寄存器，不过我们之后会讨论怎么减少使用寄存器的数量
• Intel格式的mov指令：
  • 加载立即数：mov R_dest,c
  • 索引加载：mov R_dest,[R_src+R_offset]
  • 索引存储：mov [R_dest+R_offset],R_src
• 内存：内存被逻辑的划分为单元，这些单元都是成对的相邻的字。我们的加载存储操作本质可以视作是在这些单元中进行的。我们的指令从偶数的地址开始，我们使用两个寄存器，其中一个用来确定单元的地址R_src，另一个用来确定使用哪个字R_offset

使用这些组成，我们就可以模拟一个由mov进行的图灵机了

表示图灵机

我们使用一个元组来描述图灵机M:

1

M = (Q,q0,∑,σ0,δ)

• Q是一个有限状态集，其中指定一个起始状态q0∈Q
• ∑是有一个有限符号集，其中指定一个空白符号σ0∈∑
• δ是一个转换函数，图灵机根据当前的状态和读取到的符号决定：
  • 写入带上的新符号（Σ 中的一个符号）
  • 磁头移动的方向（左 L 或右 R）
  • 转换到的新状态（Q 中的一个状态）

图灵机有一个磁带，由无限多个位置组成，每个位置上有一个单独的符号。图灵机会持有一个当前的状态q0，和当前的位置（初始位置为磁带的最左边，磁带向右无限延申）。每个磁带的位置都被初始化为空白符号σ0。

图灵机会反复计算转换表δ，如果当前的状态和读取到的符号的情况在δ中并没有被定义，机器将会终止。如果是已有定义（σ，d，q），那么机器会将当前的状态设置为q，将σ写入当前的位置，同时根据d来决定纸带的跳转方向（如果d=L向左，如果d=R向右），然后机器继续运行。

我们可以在内存单元中表示我们的符号集。我们首先要将图灵机的符号集∑映射到每个单元中，符号集中的每个符号都对应一个内存的单元，这些单元的地址被描述为S₁，S₂，…，S_|∑|，其中|∑|是符号集的数量，即大小。每个单元S_i的内容是未指定的，他可能包含任何值。但是对于第一个内存单元S₁，它的值始终是空白符号σ0。

接下来我们要在计算机内存中表示图灵机的状态和转换表。转换函数实际上就是根据当前给定的状态和当前读取的符号，来给出图灵机要进行的操作。我们可以理解为δ(σ,q) = (σ',d',q')。在内存中，每个状态q被表示为出转换的列表。每个做出转换被表示为一个包含四个元素的元组(σ,σ‘,d’,q’)，其中：

• σ表示当前状态下图灵机读取到的符号。在内存中，这个符号被表示为对应单元S_i的地址
• σ’表示图灵机在当前单元写入的新符号。在内存中，这个符号被表示为对应单元S_j的地址
• d’表示图灵机的读写头移动的方向。在内存中，这个状态被表示为一个数字，0L1R
• q’表示图灵机转换后的新状态。在内存中，对应出转换列表的地址

我们用一张图片来描述这个过程：

这个Q₀和Q₁则是转换的规则，我们可以根据它确定图灵机接下来的行为。

内存中的其他单元则用来表示我们图灵机中的磁带。我们假设磁带是无限长的（尽管现实中的内存地址是有限的），我们将单元按T₁,T₂,…来进行，命名使得T_n的中的字就是S₁的地址，T_n+1中的字是T_n+1的地址

通过这个方式，我们可以将T₁视作一个无限的表的起始，且无限的表中的每一个元素的初始值为S₁。在讨论图灵完备的过程中，我们通常只关心计算的过程，而忽略输入和输出。我们假设在程序开始前，输入是一串符号队列，从T₁到T_n。而输出则是在指令执行结束后，纸带上的值就是输出。

比较和条件语句

计算的基础之一就是分支，根据运行的值选择下一个要执行的操作，我们接下来尝试用mov来实现它。

我们可以用一下方式来比较A和B是否相等：

1
2
3

mov [R_i],0
mov [R_j],1
mov R_k,[R_i]

我们可以根据R_k的值判断R_i和R_j是否相等。如果R_i和R_j相等，那么相当于向同一个地址写入了两次值，如果不相等，[R_i]处的值就不会被修改。所以A=B->1 A!=B->0

我们也可以比较一个指定的值和N是否相等：

1
2
3
4
5

mov X,[R_i]
mov [N],0
mov [R_i],1
mov R_j,[N]
mov [R_i],X

原理同上，只不过这里我们用X保存了R_i地址上的数据

这个原理允许我们实现比较语句，结果要么是0要么是1。我们可以用这些结果去选择不同的值。如我们上面所说的在一个单元中我们可以根据index(即R_k)来计算使用哪个字。假如N是其中一个单元格的地址，我们就可以利用比较的结果来判断读取单元中的哪个字：

1
2
3

mov [N],R_i
mov [N+1],R_j
mov R_l,[N+R_k]

通过这些操作我们已经可以模拟一个图灵机了

模拟图灵机

• 我们使用T来存储当前的要测试的转换（存储了转换规则的地址）
• 使用S来存储当前读取的符号（用来查找规则）
• 使用L来代表当前位置左侧磁带部分的列表
• 使用R来代表当前位置右侧磁带部分的列表（LR可以用来模拟读写头移动的操作）

磁带由L+S+R组成

程序的开始，T会存储Q₀的地址，S存储T₁的地址，L存储N的地址（代表空列表，用于逆向存储左边磁带的部分。这样最近的位置总是左边的列表的第一个元素，这样向左处理无需移动整个列表），R存储T₂的地址（初始时为T，即磁带上除了第一个位置外所所有位置的列表）。L和R寄存器中的列表被视作栈，当图灵机向右移动时，当前的符号S被推入L队列中，R队列中的符号被弹出到S。同时由于我们会经常用到N，所以我们设置寄存器N始终保存地址N。

介绍完这些前置的条件，我们现在开始实现图灵机：

首先我们需要根据当前符号S和转换规则T来判断是否应该触发转换：

1
2
3
4
5
6

mov X,[T]		;获取转换规则
mov X,[X]		;获取触发符号
mov Y,[S]		;获取当前符号
mov [Y],0		;比较当前符号与触发符号
mov [X],1
mov M.[Y]

再此基础之上，我们构造功能来更新当前符号，当M=1(匹配)时触发

1
2
3
4
5
6
7
8

mov X,[T]		;获取转换规则（触发符号,新符号,...）
mov X,[X+1]		;跳过触发符号
mov X,[X]		;加载新符号	
mov Y,[S]		;记载旧符号
mov [N],Y		;选择新旧符号
mov [N+1],X
mov Z,[N+M]
mov [S],Z		;写入新符号

接着，我们加载纸带的移动方向：

1
2
3
4

mov D,[T]		;获取转换规则（触发符号,新符号,方向,...）
mov D,[D+1]		;跳过触发符号
mov D,[D+1]		;跳过新符号
mov D,[D]		;加载方向

然后根据D的值0左1右。将单元添加到磁带栈上的过程是，先将磁带栈的顶端写为[S+1]，然后修改磁带栈寄存器为S，下面这个是将S压入栈顶的过程：

1
2
3
4
5
6
7
8
9
10

mov [N],R		;获取[S+1]的值（[S+1]就是下一个要被读取的符号）
mov [N+1],L
mov X,[N+D]
mov [S+1],X
mov [N],L		;确定L的值
mov [N+1],S
mov L,[N+D]
mov [N],S		;确定R的值
mov [N+1],R
mov R,[N+D]

我们必须确认只有在转换规则匹配的时候才有移动。如果不匹配的话，我们需要翻转刚刚D的值，以复原移动

1
2
3
4
5
6

mov [N],1		;X~=D
mov [N+1],0
mov X,[N+D]
mov [N],X 		;选择X或者D
mov [N+1],D
mov D,[N+M]

接下我们将根据D的值将栈顶的值弹出至S:

1
2
3
4
5
6
7
8
9
10

mov [N],L		;获取S的值
mov [N+1],R
mov S,[N+D]
mov X,[S+1]		;获取L或R的栈顶元素
mov [N],X		;为L赋值
mov [N+1],R		;这里让L=R看起来很奇怪，实际上刚刚更新了当前的S_current = R_old，此时R栈顶尚未更新
mov L,[N+D]		
mov [N],R		;当左移时
mov [N+1],X
mov R,[N+D]

如果M是匹配的话就会正常移动，不匹配就会不动。然后接下来我们要更新图灵机的状态：

1
2
3
4
5
6
7
8
9

mov X,[T+1]		;加载下一个转换列表的地址
mov Y,[T]		;获取转换规则（触发符号,新符号,方向,下个状态的转换列表）
mov Y,[Y+1]		;跳过触发符号
mov Y,[Y+1]		;跳过新符号
mov Y,[Y+1]		;跳过方向
mov Y,[Y]		;获取下个状态的转换列表的地址
mov [N],X
mov [N+1],Y
mov T,[N+M]

不过有时候也会出现没有合适的转换规则的情况，这个时候我们需要做一个验证，检测是否到达了某个状态列表的末尾：

1
2
3
4
5

mov X,[T]
mov [N],0	;这里N代表空列表的地址，所以用T与N比较
mov [T],1
mov H,[N]
mov [T],X

如果H=0我们需要停止机器，我们通过从无效地址0中读取来实现这一点：

1
2
3
4

mov [N],0		;从0或N中选择
mov [N+1],N		
mov X,[N+H]
mov X,[X]		;加载0或N

如果程序地址没有终止程序，说明我们找到了下一个转换规则并将指针指向了T。同时我们将当前符号存放在S中。因此我们现在又一次的处于了一个合适的状态中，我们跳转到开始，再次重复上述的过程，这就是一个图灵机的完整的行为过程：

1

jump start

我们把之前的SEQ结构已经实现了，可是为了更好的符合流水线执行的特性，为我们需要对顺序的SEQ处理器做一点小的改动，我们需要将PC的计算拿到取指阶段。然后在不同的阶段之间留下流水线寄存器来保存状态。

Y86-64的流水线实现

SEQ+：重新安排计算阶段

我们要把更新PC的阶段放在取值阶段，在第一个时钟周期开始执行。这样可以保证每个周期都能做到去除指令，从而实现流水线运作的状态。我们把这种改动后的结构称为SEQ+

我们可以注意到，在SEQ中PC的计算是根据当前时钟周期中的信号值和数据机型计算的。而在SEQ+中PC的计算则是根据上一个时钟周期产生的信号计算得到的。我们可以在下面的整体架构中起初的看到这一点

要特别指出，在SEQ+中并没有设置硬件来保存当前的PC，而是根据前一条指令保存下来的状态信息动态的计算出PC

插入流水线寄存器

这是更新后的SEQ+架构，但是我们需要向其中插入流水线寄存器，以保存每个阶段的状态信息和数据

我们将流水线寄存器插入之后，可以得到PIPE-处理器，两者的硬件架构实际上差不多，但是信号的含义并不完全相同，我们接下来介绍一下其架构功能：

流水线寄存器的功能如下：

• F 保存程序计数器的预测值
• D 位于取指和译码阶段之间。它保存关于最新取出的指令的信息，即将由译码阶段进行处理
• E 位于译码和执行阶段之间。它保存关于最新译码的指令和从寄存器文件中读出的信息，接下来交给执行阶段处理
• M 位于执行和访存阶段之间。它保存最新执行的指令的结果，即将由访存阶段进行处理。它还保存关于用于处理条件转移的分支条件和分支目标的信息
• W 位于访存阶段和反馈路径之间，反馈路径将计算出来的值提供给寄存器文件写，当完成ret指令时，它还要向PC选择逻辑提供返回地址

在PIPE-处理器中我们流水线执行指令的效果是这样的：

对信号进行重新排列和标号

在之前的SEQ和SEQ+架构中，我们在每个时刻只处理一条指令，因此每个信号值在同一个时刻的都是唯一的值。在流水线化的设计中，不同的阶段使用和保存的是不同的信号值所以我们需要加以区分。并使用重新的命名机制。我们将流水线寄存器中的信号前面用大写的前缀标识，如D_atat E_stat M_stat W_stat。对于从一个阶段中计算出来的值，我们用小写开头来标识，不过特别注意实际状态Stat是由写回阶段计算出来的。

下面我们需要注意几个特别的地方：

1. 在译码阶段会产生dstM和dstE的值，他们指明valE和valM的目的寄存器。在SEQ+中我们可以直接将信号连到写端口地址输入。在PIPE-中，会在流水线中一直携带这样的信号穿过执行和访存阶段，直到写回才送到寄存器文件中。这样是为了确保写端口地址和数据输入最终是来自同一条指令。不然写回的数据是写回阶段的，但是给定的写端口却是取值阶段的。我们要避免这种情况
2. PIPE-中一个块在相同的表示形式的SEQ+中是没有的，那就是译码阶段中的SelectA块。这个块会从寄存器文件中的valA和流水线寄存器中D中的valP中的选出一个值作为流水线寄存器E的valA值。这个块用来减少携带给流水线寄存器E和M的状态数量。在所有的指令中，只有call在访存阶段中需要valP的值，只有跳转指令在执行阶段需要valP，而又恰好这些指令都不需要从寄存器文件中读出来的值。所以我们用这个块来合并这两个信号，将它作为valA携带穿过流水线，从而可以减少流水线寄存器的状态数量。
3. 不同阶段之间的流水线寄存器中包括一个状态码stat字段，开始时是在取指阶段计算出来的，但是在访存阶段可能因为错误访问导致修改状态。所以最好的办法就是让与每条指令关联的状态码和指令一起通过流水线，像图中一样。

预测下一个PC

在PIPE-设计中我们通过流水线化的设置使得每个时钟周期都发送一条新的指令，也就是说每个时钟周期都有一条新的指令进入执行阶段并最终完成。但是这要求我们取出一条指令之后能够立马确定下一条指令的文职。但是，当我们取出的是ret或者条件分支指令的时候，我们需要几个周期后才能确定返回的地址。

除了条件转移指令和ret以外，根据取指阶段中计算出来的信息，我们都能够确定下一条指令的地址。对于call和jmp而言，下一条指令的地址就是指令中的常数字valC，而对于其他指令来说就是valP。因此，我们对于这些指令都可以实现PC的预测。

而对于条件转移，我们既可以预测选择了分支，新PC为valC；也可以预测没有选择分支，新PC为valP。这种情况叫做分支预测，我们会在之后讨论这个问题。

对于ret指令的PC值的预测。通条件转移不同，此时可能的返回值是无限的，因为返回地址是位于栈顶的字，其可能是任意的。在设计中，我们不会试图对返回地址进行预测。只是简单的暂停处理新指令，直到ret指令完成写回，我们之后会讨论这个内容。

PIPE-的取指阶段，负责预测PC的下一个值，以及为取指选择实际的PC。其中标号为”Predict PC”的块会从PC增加器计算出的valP和取出指令中得到的valC中进行选择。然后将这个值放在流水线寄存器F中，作为程序计数器的预测值。

流水线冒险

将流水线技术引入一个带反馈的系统，当像相邻指令间存在相关时则会出现问题。这些相关有两种形式：

• 数据相关：下一条指令会用到这一条指令计算出的结果
• 控制相关：一条指令要确定下一条指令的未知。如执行跳转、调用或返回指令时。

这些相关可能会导致流水线产生错误，我们称之为冒险（分为数据冒险和控制冒险，我们先考虑数据冒险），这里我们可以了解一下不同程序状态可能产生的冒险的类型和状态：

• 程序寄存器：寄存器文件的读写是在不同的阶段进行的，导致不同指令之间可能出现不希望的相互作用
• 程序计数器：更新和读取程序计数器之间的冲突会导致控制冒险。当我们的取指阶段在取下一个指令之前，正确预测了程序计数器的新值时，就不会产生冒险。预测错误的分支和ret指令需要特殊处理。
• 内存：对数据内存的读和写都发生在访存阶段。在一条读内容的指令之前，我们需要将所有写内存的指令都完成，以免读写的状态不一样。同时我们要确保写入的内存空间不会影响指令代码，所以我们在此禁止，指令自我修改的情况。
• 条件寄存器：在执行阶段中，整数操作会写这些寄存器。条件传送指令会在执行阶段以及条件转移会在访存阶段读这些寄存器。在条件传送或条件转移到达执行阶段前，整数操作就已经完成了这个阶段。所以不会发生冒险
• 状态寄存器：指令经过流水线时，会影响程序状态。我们采用流水线中的每个指令都与一个状态码关联的机制，使得发生异常时，处理器可以有条理的停止。

我们用图片简单的演示一下冒险的发生：

上面展示了不同情况下可能发生冒险的情况及其原因。我们可以用以下几种方法来避免冒险：

用暂停来避免数据冒险

暂停时，处理器会停止流水线中一条或多条指令，直到冒险条件不再满足。让一条指令停顿在译码阶段，直到它的原操作书通过了写回阶段，这样我们的处理器就能避免数据冒险。例如：

当addq指令处于译码阶段时，流水线控制逻辑发现执行、访存或写回阶段中至少有一条指令会更新寄存器rdx或rax。处理器不会让addq指令带着错误的结果通过，于是会暂停这个指令，将其阻塞在译码阶段。直到得到正确的源操作数，然后沿着流水线继续执行。当然addq指令被阻塞在译码阶段时，halt指令也被阻塞在取指阶段，我们通过保持PC不变来实现这一点。

总之，暂停技术就是让一组指令阻塞在他们所处的阶段，而允许其他指令继续通过流水线。我们实现所用的方法是：每次要把一条指令阻塞在译码阶段，就像执行阶段插入一个气泡，气泡就像一个自动产生的nop指令——它不会改变任何程序状态。关于其详细机制，我们之后会讨论

在实际的指令中，像这样的数据冒险十分常见。如果我们频繁的使用暂停，会导致流水线的效率下降，严重降低了整体的吞吐量

用转发避免数据冒险

PIPE-的设计是在译码阶段从寄存器文件中读入原操作数。但是这些源操作数只有在写回阶段才能进行。与其等其暂停写入，不如直接将要写的值传到流水线寄存器E作为源操作数。这种将结果值直接从一个流水线阶段传到较早阶段的技术称为数据转发。例如：

不仅如此，为了充分利用数据转发技术，我们还可以将访存阶段对寄存器没有完成的写和执行阶段新计算出来的值转到译码阶段。

总结一下，我们可以将还没有写回的信号（W_valM，W_valE）转发到我们的E端口。也可以将刚从内存中读出的信号m_valM转发。也可以将尚未进行访存的信号M_valE进行转发。或者是将刚计算出来的e_valE进行转发。也就是说，我们有五个转发源（e_valE，m_valM，M_valE，W_valE，W_valM）和两个不同的转发目的（E_valA，E_valB）

我们在硬件层面上实现转发的功能，从而得到我们最终的PIPE处理器架构，使得我们不用暂停流水线就能处理大多形式的数据冒险。

这就要求处理器在译码阶段能够检测转发需求，所以我们看到来自五个转发源的值反馈到译码阶段中两个标号为”Sel+Fwd A”和”Fwd B”的块。标号为”Sel+Fwd A”的块是”SelectA”功能和转发逻辑功能的组合。它允许流水线寄存器E的valA位已增加的程序计数器valP，从寄存器文件A端口读出的值，或者某个转发过来的值。

加载/使用数据冒险

有一类数据冒险不能简单的使用转发来解决。这是因为内存读在流水线中发生的比较晚，我们以下图为例。可以看到，我们在周期7想要将数据转发时，程序还没有访问到指定内存的值

我们可以将暂停和转发结合起来，来避免加载/使用数据冒险。这个做法需要改变控制逻辑，但是我们可以使用现有的旁路路径。当流水线控制逻辑发现译码阶段的指令需要从内存中读取出来的结果是。它会将译码阶段中的指令暂停一个周期，导致执行阶段中插入一个气泡。从而实现避免数据冒险

这种用暂停来处理加载/使用冒险的方法称为加载互锁。加载互锁和转发技术结合起来足以处理所有可能的数据冒险类型，因为加载互锁出现的情况有限，流水线的吞吐效率几乎不会受到影响

避免控制冒险

当处理器无法根据取指阶段来确定下一条指令的地址时，就会出现控制冒险。不过控制冒险指挥发生在ret指令和跳转指令，我们将简单谈论其处理方式。

ret

ret控制冒险的处理比较简单，我们只需要在ret的译码、执行、访存阶段时，暂停流水线，在处理过程中插入三个气泡。当指令到达写回阶段，PC选择器就会选择返回地址作为指令的取指地址。从而避免控制冒险

分支错误预测

我们以一个汇编程序为例

1
2
3
4
5
6
7
8

0x000:	xorq %rax,%rax	
0x002:	jne target
0x00b:	irmovq $1,%rax
0x015:	halt
0x016:target:
0x016:	irmovq $2,%rdx
0x020:	irmovq $3,%rbx
0x02a:	halt

处理器处理的流程如下图

首先程序的预测分支逻辑会选择分支，于是在周期3中会把target指令进行取指。在周期4中，target进入译码，而target+1被取指，此时跳转指令会在执行阶段判断是否应该进行跳转。如果选择分支，则保持程序逻辑不变；如果不应该选择分支，我们则应该停止执行这两条命令（我们需要在下一个周期往译码和执行阶段插入气泡，并取消这两个错误的指令）。在周期5中，程序的条件码被改变，我们需要取消两条跳转预测指令，同时取指一条跳转指令后面的指令，从而避免了分支预测错误导致的控制冒险。

所以综上所述，通过暂停和往流水线中插入气泡的技术可以动态调整流水线的流程。我们对基本时钟寄存器设计的基本拓展可以实现暂停流水线，并向流水线控制逻辑一部分的流水线寄存器中插入气泡，从而实现避免控制冒险。

我们已经基本了解了Y86-64的指令集和汇编的用法，现在我们要尝试模拟处理器的硬件行为。这里描述一个称为SEQ的处理器，我们了解它的使用过程，并尝试构建它。

Y86-64的顺序实现

将处理组织成阶段

处理一条指令包括很多的操作和步骤，如果我们有序的将其进行划分。我们就可以得到一个顺序序列，所有的指令都可以按这个顺序进行处理，从而实现高效的流水线处理。我们可以将其划分为几个阶段：

• 取址：从内存读取指令字节，读取地址为当前PC的值。先取出指令指示符字节的两个四位部分：icode和ifunc，然后根据指令类型判断是否要取出寄存器指示符字节和8字节常数字。然后再按顺序计算当前指令的下一条指令的地址，将其作为下一次取指的PC。
• 译码：从寄存器文件中读入最多两个操作数，得到值valA和valB。读入的寄存器是rA和rB指明的寄存器。
• 执行：在执行阶段，ALU要么根据ifunc的值，计算内存引用的有效地址；要么增减栈指针。我们将得到的数据称为valE。同时执行阶段也可能会设置条件码，对于条件传送指令来说，这个阶段会检验条件码和传送条件(ifun)，如果条件成立，就更新目标寄存器。同样的，对于跳转指令，这个阶段决定是否应该选择分支。
• 访存：该阶段将数据写入内存，或从内存中读出数据。读出数据称为valM
• 写回：写回阶段最多将两个结果写到寄存器文件
• 更新PC：将PC设置为下一条指令的地址

处理器会不停的执行这些阶段，从而实现执行指令的功能。

而现在的难点在于我们怎么将每一个指令转换成这些阶段内，以实现处理器的按阶段执行，我们需要好好处理一下。

OPq rrmovq irmovq

这几个指令的共同点在于计算了一个值，并将值存放在寄存器中。而OPq则代表四个整数操作，因为它们只有OPq操作和ifunc值是不一样的，所以我们统一处理。这里的M_x[]的x指的是从内存中读取的字节数。

注意到并不是每个阶段都需要进行处理

rmmovp mrmovp

这两个指令都有访存阶段

pushq popq

这个过程的实现相对复杂，同时pushq和popq的实现过程，正是上一篇中push %rsp和pop %rsp行为的答案

jXX call ret

这三个指令都有控制转移的处理，有跳转，所以我们放到一起来进行讨论

这里需要注意JXX的执行阶段，我们通过条件码和跳转条件来确定是否选择分支，并将其设置为位信号Cnd

SEQ的硬件结构

我们将指令组织成了6个阶段来进行，现在每个阶段我们使用一个硬件单元来负责这些处理。这样子，在每个时钟周期，一个硬件都可以完成一次处理。现在我们根据这张图介绍一下硬件单元和各个处理阶段的关联：

• 取指：将PC作为指令内存的地址，读取指令的字节。使用PC增加器计算valP，即增加后的PC
• 译码：寄存器文件有两个读端口A和B,从这两个端口同时读寄存器值valA和valB
• 执行：执行阶段会根据指令的类型，将ALU用于不同的目的。同时计算条件码的新值。并根据跳转类型和条件码设置分支信号Cnd
• 访存：在访存时，数据内存读出或写入一个内存字。
• 写回：寄存器文件有两个写端口。端口E用来写ALU计算的值，端口M用来写从数据内存中得到的值
• PC更新：程序计数器的新值选择自：valP，下一条指令的地址；valC，调用指令或跳转指令指定的目标地址；valM，从内存读取的返回地址

我们可以这样笼统的表现我们的一个计算过程：

SEQ的时序

我们从软件层面上的习惯会使得我们认为，这几个阶段是从上到下按顺序执行的。但是SEQ作为一个硬件模型，它的操作运行并不一样。一个时钟变化会引发一个经过组合逻辑的流，从而执行整个指令。我们不妨分析一下这个行为。

SEQ的硬件实现主要由组合逻辑和两种存储器设备：时钟寄存器（程序计数器和条件码寄存器），随机访问存储器（寄存器文件，指令内存和数据内存）。组合逻辑则不需要任何时序和控制，只要输入变化了，值就通过逻辑电路传播。

我们由四个硬件单元需要对他们的时序进行明确的控制——程序计数器，条件码寄存器，数据内存和寄存器文件。这些单元通过一个时钟信号来控制，它触发将新值装载到寄存器，以及将值写到随机访问存储器。

我们可以看看这几个硬件单元的不同：

• 每个时钟周期，程序计数器都会装载新的指令地址。
• 只有在进行整数运算指令时，才会装载条件码寄存器。
• 只有在执行rmmovq pushq call时，才会写数据内存。
• 寄存器文件的两个写端口允许每个时钟周期更新两个程序寄存器，我们可以通过特殊ID 0xF来作为端口地址，表明端口不进行写操作

也就是说实际上，每个硬件的功能是同时进行的，且互不干扰的。我们用它来执行我们的程序，这就对我们的指令有着“从不回读”的要求。这意味着处理器从来不用为了完成一条指令的执行而去读由该指令更新的状态。

以pushq %rsp为例，如果是先将%rsp-8，在将更新后的%rsp作为写操作的地址。这就是错误的，为了执行内存操作，他需要先从寄存器中读更新过的栈指针，这是错误的。因为在硬件各个阶段同步执行下，没有一个指令可以即设置自己的状态又根据这个状态继续执行。

SEQ阶段的实现

取指阶段

取指阶段包括指令内存硬件单元。以PC作为第一个字节的地址，这个单元读取10个字节。

• 第一个字节为Split单元：
  • 高四位用来得到icode
  • 第四位用来得到ifunc
• 第二到十个字节为Align单元：
  • 第一个字节用来得到rA和rB根据高低四位得到
  • 后八个字节用来得到8字节常数valC

根据icode的值我们可以计算三个一位的信号：

• instr_valid：用来判断icode的是否是一个合法的指令
• need_registers：这个指令是否包括一个寄存器指示符字节
• need_valC：这个指令是否包括一个常数字

1
2
3
4
5
6
7
8
9
10
11

# need_registers 实现
if icode in [RRMOVQ,OPQ,PUSHQ,POPQ,IRMOVQ,RMMOVQ,MRMOVQ]:
	need_registers = 1
else:
    need_registers = 0
    
# need_valC 实现
if icode in [IRMOVQ,RMMOVQ,MRMOVQ,JXX,CALL]:
    need_valC = 1
else:
    need_valC = 0

我们根据信号来获取rA rB valC，如果need_registers==1，第二个字节分开装入rA和rB。对于valC，如果need_registers==0&&need_valC==1，第二到九个字节装入常数字valC；如果need_registers==1&&need_valC==1，则将第三到十个字节装入常数字valC

PC增加器应将单元则根据当前的PC以及两个信号need_valC和need_registers的值得到信号valP。对于PC值p，need_registers值r，以及need_valC值i，增加器产生的值为PC = p + 1 + r + 8*i

译码和写回阶段

之所以将译码和写回阶段放在一起，是因为它们都要对寄存器文件进行访问。

寄存器文件中有四个端口，其支持同时进行两个读（对端口A和B）和两个写（在端口E和M）。每个端口都有一个地址连接线（rArB）和一个数据连接线（icode）。地址连接线是寄存器ID，数据连接线则既可以做输出字也可以做读取字。两个读端口的地址输入为srcA和srcB，两个写端口的地址输入为dstE和dstM。如果某个地址端口上的值为0xF(RNONE)则代表不需要访问寄存器。

现在我们可以写出四个端口的输出情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# srcA
if icode in [RRMOVQ,RMMOVQ,OPQ,PUSHQ]:
    srcA = rA
else if icode in [POPQ,RET]:
    srcA = RSP
else:
    srcA = RNONE
# srcB
if icode in [OPQ,RMMOVQ,MRMOVQ]:
    srcB = rB
else if icode in [PUSHQ,POPQ,CALL,RET]:
    srcB = RSP
else:
    srcB = RNONE
# dstE
if icode in [OPQ,RRMOVQ,IRMOVQ]:
    dstE = rB
else if icode in [PUSHQ,POPQ,CALL,RET]:
    dstE = RSP
else:
    dstE = RNONE
# dstM
if icode in [MRMOVQ,POPQ]:
    dstM = rA
else:
    dstM = RNONE

这里我们要额外注意一个问题当我们执行popq %rsp的时候同时有向%rsp写入valE和valM，因此我们要对dstE和dstM端口设置一个优先级，以确保最后%rsp的值是弹出的值，而不是更新后的%rsp值。因此我们将M端口的优先级设置的高于E端口。

执行阶段

执行阶段的硬件主要使用ALU，这个单元根据alufun信号的设置，对输入aluA aluB进行ADD SUB AND OR运算。这些数据和控制信号是由三个控制块产生的，valE就是ALU的输出。

这里我们要明确，aluB是被计算的数，而aluB是用于计算的数。我们根据icode来选择性的设置aluA和aluB的值以完成计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# aluA
if icode in [RRMOVQ,OPQ]:
    aluA = valA
else if icode in [IRMOVQ,RMMOVQ,MRMOVQ]:
    aluA = valC
else if icode in [CALL,PUSHQ]:
    aluA = -8
else if icode in [POPQ,RET]:
    aluA = 8
# aluB
if icode in [RMMOVQ,MRMOVQ,OPQ,CALL,RET,PUSHQ,POPQ]：
	aluB = valB
else if icode in [IRMOVQ,RRMOVQ]:
    aluB = 0

同时我们要设置ALUfun，大多数时候ALU是做加法工作的，在执行OPQ指令时，对应ifun:

1
2
3
4
5

# alufun
if icode == OPQ:
    alufun = ifun
else:
    alufun = ADD

执行阶段还要设置条件码寄存器。每次运行时要设置（零，符号，溢出），不过我们只希望在执行OPQ指令时才设置CC：

1
2
3
4

if icode == OPQ:
    setCC = 1
else:
    setCC = 0

标号为Cond的硬件单元则会根据ifun和CC来设置信号Cnd，来确定是否要进行条件分支，或条件数据传送。它产生信号Cnd，用于设置条件传送的dstE，同时沿用在条件分支的下一个逻辑。对此我们可以设置指令CMOVXX的传送条件，即优化dstE的设置：

1
2
3
4
5
6
7
8
9

# dstE
if icode == RRMOVQ && Cnd:
    dstE = rB
else if icode in [OPQ,IRMOVQ]:
    dstE = rB
else if icode in [PUSHQ,POPQ,CALL,RET]:
    dstE = RSP
else:
    dstE = RNONE

访存阶段

该阶段的任务就是读写程序数据。两个控制块产生内存地址和内存输入数据的值。两外两个块产生表明读写操作的控制信号。当执行读操作时，数据内存产生值valM

我们根据指令的访存阶段的分析，可以简单的得到Mem_addr和Mem_data的设置：

1
2
3
4
5
6
7
8
9
10

# mem_addr
if icode in [RMMOVQ,PUSHQ,CALL,MRMOVQ]:
    mem_addr = valE
else if icode in [POPQ,RET]:
    mem_addr = valA
# mem_data
if icode in [RMMOVQ,PUSHQ]:
    mem_data = valA
else if icode == CALL:
    mem_data = valP

然后根据指令类型，判断数据内存读写的使用：

1
2
3
4
5
6
7
8
9
10

# mem_read
if icode in [MRMOVQ,POPQ,RET]
	mem_read = 1
else:
    mem_read = 0
# mem_write
if icode in [RMMOVQ,PUSHQ,CALL]:
	mem_write = 1
else:
    mem_write = 0

然后时是设置状态码，分别为SADR SINS SHLT SAOK

1
2
3
4
5
6
7
8
9

# Stat
if imem_error || dmem_error:
    Stat = ADR
else if !instr_valid:
    Stat = INS
else if icode == HALT:
    Stat = HLT
else:
    Stat = AOK

更新PC阶段

SEQ的最后一个阶段会产生PC的新值，我们需要根据指令的类型和是否要选择分支来设置PC，PC可能是valC，valM，valP。

1
2
3
4
5
6
7
8
9

# new_pc
if icode == CALL:
	new_pc = valC
else if icode == JXX && Cnd:
    new_pc = valC
else if icode == RET:
    new_pc = valM
else:
    new_pc = valP

到此为止，我们的SEQ的各个阶段的硬件模拟就完成了。之后我们会进一步优化SEQ的实现。

最近在看CSAPP的第四章，因为要记的东西比较多，所以整理一些东西帮助理解

Y86-64指令集体系结构

对于程序员可见的状态

Y86程序的每条指令都会对我们的处理器进行一些改变，我们把这个过程称之为状态的改变。这里我们需要能够知道对应的行为，使我们的状态发生了哪些变化。这些需要被观测的状态就是“对于程序员可见的状态”

程序计寄存器（RF）

Y86有15个程序寄存器，每个寄存器存储着一个64位的字，分别是：

1

%rax %rcx %rdx %rbx %rsp %rbp %rsi %rdi %r8~%r14

不同的程序寄存器做不同的用处，之后再细说

程序寄存器（PC）

程序寄存器用于存放当前正在执行的指令的地址，通过修改PC值，可以控制处理器执行指令

条件码（CC）

由三个1位的条件码组成：ZF SF OF，它们保存着最近的算数或逻辑指令造成影响的有关信息

程序状态（Stat）

它表明程序执行的总体状态，用于指示程序是在正常运行还是出现了某种异常状态

内存（DMEM）

内存实际上可以理解为一个很大的字节数组，保存着程序和数据。这里我们的Y86程序只考虑用虚拟地址来引用内存位置。我们只认为虚拟内存系统想Y86提供了一个单一的字节数组映像

Y86-64指令

这里的汇编代码格式采用ATT

指令细节：

• x86的movq在这里被拆分成了：rrmovq irmovq rmmovq mrmovq,显式的指明了指令的源和目的。其中对应立即数(i)，内存(m)，寄存器(r)。指令的第一个字母指定了源，第二个字母指定了目的
• OPq对应着四个整数指令：addq andq subq xorq，它们只对寄存器进行操作。这些操作会设置三个条件码ZF(零)，SF(符号)，OF(溢出)
• jXX对应着七个跳转指令：jmp(无条件跳转)，jle(小于等于跳转)，jl(小于跳转)，je(等于跳转)，jne(不等于跳转)，jge(大于等于跳转)，jg(大于跳转)。跳转指令会根据条件码进行分支判断跳转
• cmovXX对应了六个条件传送指令：cmovle(小于等于传送)，cmovl(小于传送)，cmove(等于传送)，cmovne(不等于传送)，cmovge(大于等于传送)，cmovg(大于传送)。条件传送只能用于满足条件时的传送，且源和目的只能是寄存器。
• call将返回地址入栈，然后跳转到目标地址。ret从这样的调用中返回
• pushq和popq实现入栈与出栈
• halt指令用于停止指令的执行，并将状态码设置成HLT状态

指令编码

现在讨论一下程序的指令编码，我们可以在上面的图看到大致的，每个指令的编码结构略有不同但还是由以下部分组成：

1

指令类型 | 源 | 目的

指令类型

指令类型通常在第一个字节给出，第一个字节分为高四位和第四位。其中：

• 高四位是代码(code)部分，用来决定操作类型
• 第四位是功能(function)部分，用决定操作所使用的功能。不过功能值只有在i相关指令共用一个操作的时候才有用

我们可以看到Y86带功能值的具体操作

源和目的

源和目的可能是寄存器或者内存地址，我们分开讨论：

• 寄存器：15个程序寄存器每个都有一个相对应的寄存器标识符(register ID)，这些程序寄存器存在CPU的一个寄存器文件中，这样我们可以把寄存器文件视作一个小的，以寄存器ID为地址的随机访问存储器。如果ID值为0xF意味着不访问任何寄存器。ID值如下：

• 内存地址：这里需要分情况讨论，可能存在三种用法：其一是将内存地址作为一个目的地址；其二是将内存地址作为rmmovq和mrmovq的地址指示符的偏移地址；其三是将其作为irmovq的立即数。内存地址在指令中是一个8字节的长数字，使用小端序编码。

现在我们可以把源和目的划分为三个部分：

1
2

|   寄存器字段   | 附加地址字段 |
|  rA   |  rB   |    Dest     |

寄存器字段占一个字节，附加地址字段占用八个字节

指令编码

通过将这几部分拼接组成就可以得到一条指令的编码，其中最重要的是每个字节编码一定要是唯一的解释。任意一个字节序列要么就是一个唯一的指令序列的编码，要么就不是一个合法的字节序列。

Y86-64异常

对于Y86，状态码包括以下情况，它描述程序执行的总体状态：

对于Y86，当遇到这些异常的时候我们就让处理器停止执行指令。不过更完整的设计中，处理器会调用一个异常处理程序，这个过程用来处理在遇到的某种类型的异常。

Y86-64程序

我们尝试将这个递归求和的程序翻译成Y86的汇编形式：

1
2
3
4
5

int rsun(int *start,int count){
    if(count <= 0)
        return 0;
    return *start + rsum(start+1,count-1);
}

Y86:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# int rsun(int *start,int count)
# start in %rdi  count in %rsi
rsum:
	xorq %rax %rax		# sum = 0
	andq %rsi %rsi		# set CC -> if %rsi != 0 , ZF = 0
	je return			# if count == 0 , return 0 -> if ZF == 1 , jmp
	pushq %rbx
	mrmovq (%rdi) %rbx
	irmovq $-1 %r10
	addq %r10 %rsi
	irmovq $8 %r10
	addq %r10 %rdi
	call rsum
	addq %rbx %rax
	popq %rbx
return:
	ret

Y86-64指令详情

大多数的Y86指令是容易理解且稳定的，不过我们需要注意两个特别的指令的组合。

pushq

pushq将栈指针rsp-8，并且将一个寄存器的值写入内存中。因此，当执行pushq %rsp时，指令的结果是不确定的，我们可能遇到两种情况：

• 压入%rsp的原始值
• 压入减去8的%rsp的值

实际上这里会压入%rsp的原始值，具体的原因，我们会在后面进行解释。

popq

同样的popq %rsp也是这么一个问题，可能会出现两种结果：

• %rsp置为先前压入的值
• %rsp置为+8后的%rsp的值

是将这里是将%rsp置为先前压入的值，也就是等价于mrmovq (%rsp) %rsp。具体的原因会在之后进行解释

我突然理解什么是解释器了，解释器的话全称应该理解为字节码解释器。本质上是对特定的数据赋予一定的规则下的意义，然后用同样的规则可以去解读同一个数据，这个实际上就是信息论。我们的解释器，机器码之类的也是这样，数据本没有意义，但是特定的规则赋予了其意义即信息。

这里我要讲到的QOI就是这么一种规则，图像的压缩规则。我们知道我们的原图像的每个像素的内容，这个就是数据就是我们的信息，每个像素需要3~4个字节来存储，这就导致在像素较多的情况下，我们所需的空间就很多。我们可以通过特定的方式对其进行再编码从而实现对信息的压缩，然后用同样的方式对其进行解码。

直接开始吧

QOI

QOI (The Quite OK Image Format) 是一种新的无损图像压缩方式, 它在保持压缩率与 PNG 相近的同时 (比 PNG 大 ~35%), 编码速度达到了 PNG 的 20~50 倍, 而解码速度也有 PNG 的 3~4 倍, 并且它极简的编码解码方式也是一个极大的亮点. 可以在 QOI 的主页 上找到更多信息.

在这个文档中可以看到QOI的具体规则QOI编码规则

图像格式

这里QOI只支持24位RGB和32位RGBA格式的图像，文件格式主要由三个部分组成：

1. 文件头

1
2

       0 1 2 3 | 4 5 6 7 | 8 9 10 11 |       12 | 13 
文件头	 "qoif"     width      height     channel  colorspace

这里的magic指的是魔法数字，我们的魔法数字是“qoif”用于解码的时候识别格式

channel指的是颜色通道，3为RGB，4为RGBA

colorspace则是颜色空间，0为sRGB非线性空间，1为Linear线性空间

这里我们文件头主要是用来说明图像的信息，并不会影响后面的内容

2. 编码数据

这里省略等下说

3. 结尾填充

1
2

         0 1 2 3 4 5 6 7 
填充字节  0 0 0 0 0 0 0 1

有7位0和一位1组成的填充字节，用于检测结束

图像编码

这里我们要介绍QOI的编码规则，一共分为六个压缩模块，我们分别介绍一下功能：

QOI_OP_RGB

1
2
3
4
5
6

┌─ QOI_OP_RGB ────────────┬─────────┬─────────┬─────────┐
│         Byte[0]         │ Byte[1] │ Byte[2] │ Byte[3] │
│  7  6  5  4  3  2  1  0 │ 7 .. 0  │ 7 .. 0  │ 7 .. 0  │
│─────────────────────────┼─────────┼─────────┼─────────│
│  1  1  1  1  1  1  1  0 │   red   │  green  │  blue   │
└─────────────────────────┴─────────┴─────────┴─────────┘

将当前的像素值写入文件内，不进行压缩编码，该模块的标识码是0xFE,RGB的压缩程度为133%

QOI_OP_RGBA

1
2
3
4
5
6

┌─ QOI_OP_RGBA ───────────┬─────────┬─────────┬─────────┬─────────┐
│         Byte[0]         │ Byte[1] │ Byte[2] │ Byte[3] │ Byte[4] │
│  7  6  5  4  3  2  1  0 │ 7 .. 0  │ 7 .. 0  │ 7 .. 0  │ 7 .. 0  │
│─────────────────────────┼─────────┼─────────┼─────────┼─────────│
│  1  1  1  1  1  1  1  1 │   red   │  green  │  blue   │  alpha  │
└─────────────────────────┴─────────┴─────────┴─────────┴─────────┘

同上，该模块的编码的标识码是0xFF,RGBA的压缩程度为125%

QOI_OP_INDEX

1
2
3
4
5
6

┌─ QOI_OP_INDEX ──────────┐
│         Byte[0]         │
│  7  6  5  4  3  2  1  0 │
│───────┼─────────────────│
│  0  0 │     index       │
└───────┴─────────────────┘

在进行编码时，我们会初始化一个缓存长度为64的数组running_array，将其中所有的元素初始化为RGBA(r=0,g=0,b=0,a=0)和RGB(r=0,g=0,b=0,a=255),每次我们对其进行hash转换index_position = (r*3+g*5+b*7+a*11),然后将对应的索引覆盖为当前的像素值，如果之后再次遇到相同的像素值时，我们我们可以直接使用index来表示这个像素值。

对于RGB信息，压缩程度为33%。对于RGBA信息，压缩程度为25%。这个模块的标识码是0b00

QOI_OP_DIFF

1
2
3
4
5
6

┌─ QOI_OP_DIFF ───────────┐
│         Byte[0]         │
│  7  6  5  4  3  2  1  0 │
│───────┼─────┼─────┼─────│
│  0  1 │  dr │  dg │  db │
└───────┴─────┴─────┴─────┘

如果当前像素值和上一个像素值差距较小（差值在-2~1即0~3）时，我们可以通过计算不同像素值的差值，来压缩存储，其中：

• dr = now_r - last_r
• dg = now_g - last_g
• db = now_b - last_b

这里的-2~1需要+2转换成0~3进行存储，在转换时需要要注意。同时只能用于A值不变的情况下

对与RGB信息，压缩程度为33%。对于RGBA信息，压缩程度为25%。这个模块的标识码是0b01

QOI_OP_LUMA

1
2
3
4
5
6

┌─ QOI_OP_LUMA ───────────┬─────────────────────────┐
│         Byte[0]         │         Byte[1]         │
│  7  6  5  4  3  2  1  0 │  7  6  5  4  3  2  1  0 │
│───────┼─────────────────┼─────────────┼───────────│
│  1  0 │   diff green    │   dr - dg   │  db - dg  │
└───────┴─────────────────┴─────────────┴───────────┘

在自然图像中相邻像素的颜色的变化往往在RGB通道上有相关性(当一个颜色上主要体现为深度变化时，其他通道上的颜色通常变化较小)，尤其是绿色通道通常能代表整体亮度的变化趋势。所以我们以绿色为基准，通过计算其他通道相对于绿色通道的差值来进行存储。

• diff_green = now_g - last_g (差值范围为-32~31->0~63)
• dr - dg = (now_r - last_r) - diff_green (差值范围为-8~7->0~15)
• db - dg = (now_b - last_b) - diff_blue (差值范围为-8~7->0~15)

对于RGB信息，压缩程度为67%。对于RGBA信息，压缩程度为50%。标识码为0b10

QOI_OP_RUN

1
2
3
4
5
6

┌─ QOI_OP_RUN ────────────┐
│         Byte[0]         │
│  7  6  5  4  3  2  1  0 │
│───────┼─────────────────│
│  1  1 │       run       │
└───────┴─────────────────┘

如果当前的像素值和上一个像素的像素值相同，我们就可以使用这个模块来计算。从当前像素开始有多少个像素值是相同的，将他的数量记作run，其范围为1~62->记作0~61。这里我们之所以不使用63和64是因为，在run=63的情况下这个字节会变成0xFE,在run=64的情况下这个字节会变成0xFF从而影响解码。

对于RGB信息，压缩程度为33%。对于RGBA信息，压缩程度为25%。标识码为0b11

编码选择

QOI编码的目的是尽可能的压缩数据的内容，也就是在实际编码的过程中，我们应该尽可能的使用压缩度高的编码方式：

1

QOI_OP_RUN <= QOI_OP_INDEX = QOI_OP_DIFF <= QOI_OP_LUMA <= QOI_OP_RGB(A)

尽管QOI_OP_INDEX与QOI_OP_DIFF的压缩度相等，但是考虑计算量的话，我们更多的使用QOI_OP_INDEX

图像解码

解码也就是编码的逆过程：

• 读取文件头判断是否为QOI图像格式——头标识为qoif
• 获取图像的高度，宽度，颜色通道和颜色空间
• 对数据块进行解码（逐字节的进行解析）
  • 判断标签确定模块
  • 根据模块选择解码方式

经过以上步骤，我们可以实现程序的无损压缩转换。同时我们也可以理解字节码解释器的意义。实际上是根据一种规则，来对特定的数据进行解释，从而实现各种功能

五月份恍恍惚惚就过去了，都不太记得发生了什么，本来说好的是中旬写一些反思的。但是当时应该是在打游戏，所以就这么拖到了现在。也不知道说点什么比较好，慢慢想一想吧。上个月说要学这个学那个，也没学成什么，C++也没学多少，不记得是卡在哪里了。学了一段时间蒋炎岩老师的课，但是学不太下去。

但是也发现了一些，经历了一些好玩的东西吧，零零散散学了很多东西，本来想更进一步深入的学习，但是不记得卡在了哪里。这么一想，感觉学了好多东西，但是又没沉下心来学什么东西。倒是遇到许多好玩的游戏，什么怪物猎人，艾尔登法环，还有星露谷物语，都挺好玩的。怎么玩都不累吧，我感觉还是很开心的，至少现在还能玩一玩游戏，以前都不太想玩。

可能最近有点散漫吧，不知道是颓废还是散漫。但是心理还算开心，所以就没啥感觉，有时候会有点焦虑，但是没啥感觉。这样的生活总感觉有什么东西越来越清晰吧，不知道是什么东西，但我很喜欢这种感觉，就是混混日子。但是我最近突然想找点事情做了，Emmmm可能是太无聊了，也可能是慢慢的有一些比较在乎的事情了。总之有想法是好事，就应该开始去做了，不过得先明确一下要做的事情。我就随便列一下好了：

1. 一个是绩点的事情吧，什么高数线代，最近越学越好玩。如果不把它们当成一个课程来完成的话，我觉得其实还是很有趣得。比如什么线代的应用，还有高数在计算机里的一些应用，我觉的数据建模什么的使用范围应该很广泛吧。既然想做，对自己就应该有一点要求，绩点的事情其实我也不太明白，什么平时分什么的，但我还是打算加把油，争取靠近年级的前十
2. 下一个是找导师做课题的事情吧，我打算试试联系一个老师，方向是密码学，据说挺难的，但是我感觉很有意思。其实机器学习也挺好的，什么人工智能，感觉很神奇。但是学校做的人太多了，遂放弃
3. 然后是看书的事情吧，我暑假想围绕两本书展开我的学习活动，一本是CSAPP，还有一本是数据结构的C++描述，如果时间有多的话，最好再把计算机网络看一下
4. 今天刚考完驾照，还是挺期待练车的，打算暑假赶快点搞完，感觉会很好玩

马上就要暑假了，我虽然最近散漫，但是我对自己的要求还是很高的。像暑假这么长而且完整的而且一个人的时间确实很难得，我打算沉下心来好好沉淀一段时间，整个大一基本上都是漫无目的的学习，等下个学期就要把好刚用在刀刃上了，得卷一点，准备一下考研保研之类的事情。

就先写这么多吧，差不多要准备学习一下了

上一部分中我们实现了对于程序的汇编级别的调试，但是这种调试，过程繁琐，难度大，且调试过程的可读性较差。我们需要拓展我们的调试器的性能，所以我们需要用到DWARF格式以实现源码级别的调试。

Dwarf和Elf

在此之前我们需要对这些知识有一定程度的掌握。ELF（可执行和链接格式）是Linux中最广泛使用的对象文件格式，其指定了一种存储二进制文件不同部分方式，如代码，数据，调试信息和字符串等。它还告诉加载器如何将二进制文件准备执行，这包括之处二进制文件不同部分应该放置再内存中的位置。不过这里我们并不着重讨论ELF的文件格式

DWARF是ELF常用的调试信息格式。它和ELF是同步开发的所以适配性比较好。这种格式对应了调试器源代码与二进制之间的关系。这些信息分布在不同的ELF段中，每个段有着不同的信息内容：

• .debug_abbrev：存储.debug_info节中的缩写表
• .debug_aranges：提供内存地址与编译单元之间的映射
• .debug_frame：存储调用栈信息
• .debug_info：存储DWARF调试信息的核心数据，包含调试信息条目(DIES)
• .debug_line：存储源代码行号信息
• .debug_loc：存储位置描述信息
• .debug_macinfo：存储宏定义信息
• .debug_pubnames：提供全局对象和函数的查找表
• .debug_pubtypes：提供全局类型的查找表
• .debug_ranges：存储地址范围信息
• .debug_str：存储字符串表
• .debug_types：存储类型描述信息

这里我们着重关注.debug_line和.debug_info的部分，让我们看看一个简单的程序的DWARF信息

1
2
3
4
5
6

int main(){
    long a = 3;
    long b = 2;
    long c = a + b;
    a = 4;
}

DWARF行表

想要查看程序的DWARF信息，我们需要在编译时加入一个-g选项，可以看到以下内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

.debug_line: line number info for a single cu
Source lines (from CU-DIE at .debug_info offset 0x0000000c):

            NS new statement, BB new basic block, ET end of text sequence
            PE prologue end, EB epilogue begin
            IS=val ISA number, DI=val discriminator value
<pc>        [lno,col] NS BB ET PE EB IS= DI= uri: "filepath"
0x00001129  [   1, 11] NS uri: "/home/ylin/Program/LearnDwarf/test.c"
0x00001131  [   2, 10] NS
0x00001139  [   3, 10] NS
0x00001141  [   4, 10] NS
0x00001150  [   5, 7] NS
0x0000115d  [   6, 1] NS
0x0000115f  [   6, 1] NS ET

这一行信息<pc> [lno,col] NS BB ET PE EB IS= DI= uri: "filepath"告诉了我们内容的格式与含义。其中NS表示该地址标记了新语句的开始，通常用于设置断点或者单步执行。PE标记了函数序言的结束，用于设置函数的入口断点。ET标记了翻译单元的结束。其他的信息在上方均有显示。

假如我们想在test.c的第四行设置一个断点，我们该怎么做？我们寻找与该文件对应的条目，然后寻找相关的行的条目，查找也与之对应的地址，并设置断点。这里我们对应的条目是：

1

0x00001139  [   3, 10] NS

所以我们需要在程序加载地址处偏移地址为0x00001139的地方，下断点，就可以实现在第四行下断点。

我们查看objdump的内容，也的确如此：

反向的操作也是如此。如果我们有一个内存位置——比如说，一个程序计数器的值，我们想知道他在源码中的位置，我们可以通过行表信息中最近的映射地址，并从那里获取行。

DWARF 调试信息

.debug_info是DWARF的核心。它提供了关于程序中存在的类型、函数、变量等信息。这个节中的基本单元是DWARF信息条目，通常称为DIES。一个DIE由一个标签组成，告诉你它所表示的源码级的实体类型，后面跟着有一系列使用与该实体的属性。下面是我们程序的.debug_info节：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

.debug_info

COMPILE_UNIT<header overall offset = 0x00000000>:
< 0><0x0000000c>  DW_TAG_compile_unit
                    DW_AT_producer              GNU C17 13.3.0 -mtune=generic -march=x86-64 -g -fasynchronous-unwind-tables -fstack-protector-strong -fstack-clash-protection -fcf-protection
                    DW_AT_language              DW_LANG_C11
                    DW_AT_name                  test.c
                    DW_AT_comp_dir              /home/ylin/Program/LearnDwarf
                    DW_AT_low_pc                0x00001129
                    DW_AT_high_pc               <offset-from-lowpc> 54 <highpc: 0x0000115f>
                    DW_AT_stmt_list             0x00000000

LOCAL_SYMBOLS:
< 1><0x0000002e>    DW_TAG_subprogram
                      DW_AT_external              yes(1)
                      DW_AT_name                  main
                      DW_AT_decl_file             0x00000001 /home/ylin/Program/LearnDwarf/test.c
                      DW_AT_decl_line             0x00000001
                      DW_AT_decl_column           0x00000005
                      DW_AT_type                  <0x00000072>
                      DW_AT_low_pc                0x00001129
                      DW_AT_high_pc               <offset-from-lowpc> 54 <highpc: 0x0000115f>
                      DW_AT_frame_base            len 0x0001: 0x9c:
                          DW_OP_call_frame_cfa
                      DW_AT_call_all_calls        yes(1)
                      DW_AT_sibling               <0x00000072>
< 2><0x00000050>      DW_TAG_variable
                        DW_AT_name                  a
                        DW_AT_decl_file             0x00000001
                        DW_AT_decl_line             0x00000002
                        DW_AT_decl_column           0x0000000a
                        DW_AT_type                  <0x00000079>
                        DW_AT_location              len 0x0002: 0x9158:
                            DW_OP_fbreg -40
< 2><0x0000005b>      DW_TAG_variable
                        DW_AT_name                  b
                        DW_AT_decl_file             0x00000001
                        DW_AT_decl_line             0x00000003
                        DW_AT_decl_column           0x0000000a
                        DW_AT_type                  <0x00000079>
                        DW_AT_location              len 0x0002: 0x9160:
                            DW_OP_fbreg -32
< 2><0x00000066>      DW_TAG_variable
                        DW_AT_name                  c
                        DW_AT_decl_file             0x00000001
                        DW_AT_decl_line             0x00000004
                        DW_AT_decl_column           0x0000000a
                        DW_AT_type                  <0x00000079>
                        DW_AT_location              len 0x0002: 0x9168:
                            DW_OP_fbreg -24
< 1><0x00000072>    DW_TAG_base_type
                      DW_AT_byte_size             0x00000004
                      DW_AT_encoding              DW_ATE_signed
                      DW_AT_name                  int
< 1><0x00000079>    DW_TAG_base_type
                      DW_AT_byte_size             0x00000008
                      DW_AT_encoding              DW_ATE_signed
                      DW_AT_name                  long int

第一个DIE代表一个编译单元（CU），下面是一些属性的含义：

• DW_AT_producer：生成的此可执行文件的编译器
• DW_AT_language：源语言
• DW_AT_name：此编译单元所代表的文件名
• DW_AT_comp_dir：编译目录
• DW_AT_low_pc：此CU的代码开始
• DW_AT_high_pc：此CU的代码结束

其他的DIES属性遵循差不多的方案，你可以推断出不同属性的含义。接下来我们使用DWARF的知识解决一些实际的问题

定位我们所在的函数

假设我们已有当前的程序计数器的值，我们想要弄清楚我们处在哪个函数之中，有一个算法是这样的：

1
2
3
4
5

for each compile unit:
	if the pc is between DW_AT_low_pc and DW_AT_high_pc:
        for each function in the compile uint:
            if the pc is between DW_AT_low_pc and DW_AT_high_pc:
                return function information

这个算法适用于各种用途，但在存在成员函数和内联的情况下，事情会变得比较困难。在内联的情况下，一但我们找到了包含我们PC的函数，我们需要递归遍历该DIE的子节点，看看是否有内联函数匹配。

在一个函数上设置断点

我们要找到的函数，你可以在DW_AT_low_pc给出的内存地址上设置断点。但是一般这样做，会导致断点被下在函数序言（一般是用于保存调用者的上下文和设置函数的局部变量空间）的开始处中断，但是我们实际想要的效果是在用户代码处中断。

解决这个问题的办法就是从DW_AT_low_pc开始，从行号表中逐条读取，直到找到标记为序言结束（PE）的条目，可以确定代码的起始位置 。不过有时候，有些编译器不会输出这些信息，所以另一种做法是在该函数的第二行条目给出的地址上设置断点。

比如我们想在示例程序中的main上设置断点。我们搜索名为main的函数，并得到这个DIE:

1
2
3
4
5
6
7
8
9
10
11
12

< 1><0x0000002e>    DW_TAG_subprogram
                      DW_AT_external              yes(1)
                      DW_AT_name                  main
                      DW_AT_decl_file             0x00000001 /home/ylin/Program/LearnDwarf/test.c
                      DW_AT_decl_line             0x00000001
                      DW_AT_decl_column           0x00000005
                      DW_AT_type                  <0x00000072>
                      DW_AT_low_pc                0x00001129
                      DW_AT_high_pc               <offset-from-lowpc> 54 <highpc: 0x0000115f>
                      DW_AT_frame_base            len 0x0001: 0x9c:
                          DW_OP_call_frame_cfa
                      DW_AT_call_all_calls        yes(1)

这告诉我们函数从0x00001129的偏移值开始，我们去行目表中查找，可以得到这个信息

1

0x00001129  [   1,11] NS uri: "/home/ylin/Program/LearnDwarf/test.c"

我们要跳过程序前文，所以读取下一个条目：

1

0x00001131  [   2,10] NS

这是我们要下断点的位置

我们该如何读取变量的内容

读取变量是一件很复杂的事情，它可能存在于不同的栈帧之中，被放置在寄存器中，或者在某个内存之中，也有可能被优化掉。不过我们还是可以通过一些简单的方法去找到它，我们可以查看变量a 的DW_AT_location属性：

1
2
3
4
5
6
7
8
9
10
11
12

< 2><0x00000050>      DW_TAG_variable
                        DW_AT_name                  a
                        DW_AT_decl_file             0x00000001
                        DW_AT_decl_line             0x00000002
                        DW_AT_decl_column           0x0000000a
                        DW_AT_type                  <0x00000079>
                        DW_AT_location              len 0x0002: 0x9158:
                            DW_OP_fbreg -40
< 1><0x00000079>    DW_TAG_base_type
                      DW_AT_byte_size             0x00000008
                      DW_AT_encoding              DW_ATE_signed
                      DW_AT_name                  long int

这表示我们的a被存储在栈基地址的-40偏移地址。为了计算出这个及地址在那里，我们查看该函数的DW_AT_frame_base属性：

1
2

DW_AT_frame_base            len 0x0001: 0x9c:
    DW_OP_call_frame_cfa

这意味着我们的栈基指针，是通过CFA计算得到的。

我们现在找到了这个变量，但是我们需要知道它的信息和类型，我们可以通过DW_AT_type找到，这告诉我们类型是一个8字节的有符号整数类型，因此我们可以将这个字节解释为int64_t并显示给用户。

我们对DWARF的初步理解就到此为止，接下来尝试使用它吧

上次把断点基本的设置搞完了，接下来需要进一步的对寄存器进行操作。我们将添加读取和写入寄存器和内存的功能，这样我们就可以操作程序寄存器(PC)，从而实现程序状态的观察和操作。

寄存器和内存

寄存器结构

我们需要建立x86_64架构寄存器的元数据，以便通过ptrace系统调用和DWARF调试信息于寄存器交互

首先我们需要明确我们需要用到的寄存器，我们主要使用一些比较常用的寄存器，忽略对于架构非必须的寄存器，我们先创建一个寄存器强类型枚举，用于确定我们要用到的寄存器

1
2
3
4
5
6
7
8
9
10
11
12

enum class reg {
	rax,rbx,rcx,rdx,
	rdi,rsi,rbp,rsp,
	r8,r9,r10,r11,
	r12,r13,r14,r15,
	rip,rflags,cs,
	orig_rax,fs_base,
	gs_rax,
	fs,gs,ss,ds,es
};

constexpr std::size_t n_registers = 27;	//constexpr用来优化编译

接下来我们来建立一下寄存器的描述结构，方便我们存储信息：

1
2
3
4
5

struct reg_descriptor {
	reg r;
	int dwarf_r;
	std::string name;
};

然后我们要设置一个全局寄存器描述符数组，其元素顺序需要和ptrace返回的寄存器结构的顺序一样，这样便于我们直接通过数组索引直接访问ptrace返回的结构字段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

const std::array<reg_descriptor,n_registers> g_register_descriptors{{
	{reg::r15,15,"r15"},
	{reg::r14,14,"r14"},
	{reg::r13,13,"r13"},
	{reg::r12,12,"r12"},
	{reg::rbp,6,"rbp"},
	{reg::rbx,3,"rbx"},
	{reg::r11,11,"r11"},
	{reg::r10,10,"r10"},
	{reg::r9,9,"r9"},
	{reg::r8,8,"r8"},
	{reg::rax,0,"rax"},
	{reg::rcx,2,"rcx"},
	{reg::rdx,1,"rdx"},
	{reg::rsi,4,"rsi"},
	{reg::rdi,5,"rdi"},
	{reg::orig_rax,-1,"orig_rax"},
	{reg::rip,-1,"rip"},
	{reg::cs,51,"cs"},
	{reg::rflags,49,"eflags"},
	{reg::rsp,7,"rsp"},
	{reg::ss,52,"ss"},
	{reg::fs_base,58,"fs_base"},
	{reg::gs_base,59,"gs_base"},
	{reg::ds,53,"ds"},
	{reg::es,50,"es"},
	{reg::fs,54,"fs"},
	{reg::gs,55,"gs"},
}};

中间的各种数字是对应的DWARF寄存器编号，你可以在这里找到他们psABI-x86_64.pdf

寄存器内容读取

现在我们可以尝试编写一些函数用来和寄存器交互。我们希望能够读取寄存器、向寄存器中写入数据、从DWARF寄存器编号中检索值，以及按名称查找寄存器。总之我们先实现一个函数用来读取get_register_value的值开始。

我们还是通过ptrace的PTRACE_GETREGS 实现对寄存器数据的访问。我们用一个user_regs_struct的类型来存储ptrace的返回值。

1
2
3
4
5
6
7
8
9
10
11

uint64_t get_register_value(pid_t pid,reg r) {
	user_regs_struct regs;
	ptrace(PTRACE_GETREGS,pid,nullptr,&regs);
	auto it = std::find_if(
			begin(g_register_descriptors),	//全局标识符的起点
			end(g_register_descriptors),	//全局标识符的终点
			[r](const reg_descriptor & rd){return rd.r==r;}//lambda表达式用来匹配条件
	);
    // 本质上是*(ptr + offset)
	return *(reinterpret_cast<uint64_t*>(&regs) + (it - begin(g_register_descriptors)));
}

这里我们之所以把传递的user_regs_struct结构按uint64_t的类型理解，因为这样是安全的，返回的user_regs_struct在内存上是连续分布的，我们可以将它按uint64_t的类型处理。

现在我们可以获取regs中的任意的指定寄存器的值了。

接着我们编写set_register_value的函数实现，和刚刚差不多的过程：

1
2
3
4
5
6
7
8
9
10
11

void set_register_value(pid_t pid,reg r,uint64_t value){
	user_regs_struct regs;
	ptrace(PTRACE_GETREGS,pid,nullptr,&regs);
	auto it = std::find_if(
			begin(g_register_descriptors),
			end(g_register_descriptors),
			[r](const reg_descriptor & rd){return rd.r==r;}
	);
	*(reinterpret_cast<uint64_t*>(&regs) + (it - begin(g_register_descriptors))) = value;
	ptrace(PTRACE_SETREGS,pid,nullptr,&regs);	//返回regs表
}

然后再拓展一下，刚刚是根据枚举变量进行查找，现在我们还可以根据DWARF值查找，或者根据寄存器名进行查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

uint64_t get_register_from_dwarf_register(pid_t pid,unsigned regnum){
	auto it = std::find_if(
			begin(g_register_descriptors),
			end(g_register_descriptors),
			[regnum](const reg_descriptor & rd){return rd.dwarf_r == regnum;}			
	);
	return get_register_value(pid,it->r);
}

std::string get_register_name(reg r){
	auto it = std::find_if(
			begin(g_register_descriptors),
			end(g_register_descriptors),
			[r](const reg_descriptor & rd){return rd.r == r;}
	);
	return it->name;
}

reg get_register_from_name(const std::string & name){
	auto it = std::find_if(
			begin(g_register_descriptors),
			end(g_register_descriptors),
			[name](const reg_descriptor & rd){return rd.name == name;}
	);
	return it->r;
}

这里中间有个辅助函数get_register_name可加可不加。

现在我们开始获取我们寄存器中的信息了！

操作寄存器

首先我们向调试器加入一个dump_register函数，用来获取我们的寄存器信息：

1
2
3
4
5
6
7
8

void debugger::dump_register(){
	for(const reg_descriptor& rd: g_register_descriptors){
        //输出格式 [reg_name] [0x0000000000000000]
		std::cout << rd.name << " 0x" << std::setfill('0') << 
         std::setw(16) << std::hex << 
         get_register_value(m_pid,rd.r) << std::endl;
	}
}

我们修改handle_command函数，将我们的读写寄存器的操作功能加入进去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void debugger::handle_command(const std::string& line){
	if(line.empty()){
		return;
	}
	auto args = split(line,' ');
	auto command = args[0];
	if(is_prefix(command,"continue")){
		...
	}else if(is_match(command,"exit")){
		...
	}else if(is_prefix(command,"register")){
		if (is_prefix(args[1],"dump")){
			dump_register();			
		}else if(is_prefix(args[1],"read")){
			std::cout << args[2] << " = " << get_register_value(m_pid,get_register_from_name(args[2])) << std::endl;	
		}else if(is_prefix(args[1],"write")){
			std::string val {args[3],2};
			set_register_value(m_pid,get_register_from_name(args[2]),std::stol(val,0,16));
			std::cout << "0x" << val << " -> " << args[2] << std::endl;
		}
	}else{
		...
	}
}

操作内存

不像寄存器那么复杂，我们直接使用ptrace系统调用就可以进行对程序内存的读写，在这里我们将函数封装起来：

1
2
3
4
5
6
7

uint64_t debugger::read_memory(uint64_t address){
	return ptrace(PTRACE_PEEKDATA,m_pid,address,nullptr);
}

void debugger::write_memory(uint64_t address,uint64_t value){
	ptrace(PTRACE_POKEDATA,m_pid,address,value);
}

这里我们使用ptrace一次只能传递64位的信息，如果你想要传递更多的信息可以通过系统调用process_vm_readv 、 process_vm_writev来实现这个功能，我们将内存操作添加到我们的handle_command函数中

1
2
3
4
5
6
7
8
9
10

}else if(is_prefix(command,"memory")){
	std::string addr {args[2],2};
	if(is_prefix(command,"read")){
		std::cout << args[2] << " (mem)" << " = " << std::hex << read_memory(std::stol(addr,0,16)) << " (mem)" << std::endl;
	}else if(is_prefix(command,"write")){
		std::string val {args[3],2};
		write_memory(std::stol(addr,0,16),std::stol(val,0,16));
		std::cout << args[3] << " -> " << args[2] << " (mem)" << std::endl;
	}
   }

OK !!!

退出断点（完善我们的continue_exection）

我们的程序在执行到断点之后，没办法执行下去了，这是因为我们原来在执行int 3之后，pc计数器向后移动了1个字节，我们之前无法重新设置它，所以程序会停止在那里，但是现在可以了。我们可以通过获取并修改pc的值，将保存的数据重新覆写，以实现程序的继续运行。我们在执行时可以检查我们的断点映射，看看我们是否处于断点。如果是，我们可以取消断点，并继续执行。

首先我们先添加几个辅助函数，将它们封装起来以提高清晰和简洁性：

1
2
3
4
5
6
7

uint64_t debugger::get_pc(){
	return get_register_value(m_pid,reg::rip);
}

void debugger::set_pc(uint64_t pc){
	set_register_value(m_pid,reg::rip,pc);
}

我们先设置一个操作来读取pc的值，便于后面的操作，这里我们设置一个操作用来实现断点后的执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void debugger::step_over_breakpoint(){
	auto possible_breakpoint_location = get_pc() - 1;				//pc执行断点后增加了一个字节
	if(m_breakpoint.count(possible_breakpoint_location)){
		auto &bp = m_breakpoint[possible_breakpoint_location];
		if(bp.is_enable()){
			auto previous_instruction_address = possible_breakpoint_location;
			set_pc(previous_instruction_address);
			bp.disable();
			ptrace(PTRACE_SINGLESTEP,m_pid,nullptr,nullptr);		//单步执行
			wait_for_signal();									 
			bp.enable();
		}
	}
}

首先我们判断有没有断点，如果有，我们就退回到下断点之前，禁用它，并单步执行原始指令。然后，再把断点重新启用（我一开始也很疑惑为啥呀重新启用呢，这里我忽略了循环的情况）

这里有个wait_for_signal实际上这是我们对waitpid的封装：

1
2
3
4
5

void debugger::wait_for_signal(){	//等待子进程执行结束
	int wait_status;
	auto options = 0;
	waitpid(m_pid,&wait_status,options);
}

现在我们可以重写我们的continue_execution函数了：

1
2
3
4
5

void debugger::continue_execution(){
	step_over_breakpoint();
	ptrace(PTRACE_CONT,m_pid,nullptr,nullptr);
	wait_for_signal();
}

这样很好呀

测试

试了一下断点和查看寄存和内存的功能，能正常使用，不错：

昨天写了一些基本的架构，写到一半我突然有很多灵感，为什么一定要按照教程的内容去做呢。我应该有自己的想法，而且我现在也有能力去实现，有错误也可以慢慢调试。再加上AI的帮助，我可以以这个教程为蓝本，学习各种知识。

所以现在我要从头开始尝试这个过程，OK基本上自己重新实现了一遍，优化了一些功能和拓展了一些程序。接下来需要进一步学习怎么制作一个断点，这个还是要老老实实学原理了

断点

怎么生成一个断点

程序中的断点，在我们调试代码时，使程序停止到指定位置。但是这是什么原理呢？首先程序的断点分为两种：一种是软件断点，还有一种是硬件断点。这里我们使用的是软件断点，接下来我们研究，断点是怎么生成的？

这里我们使用x86的内置的中断操作int 3，这个操作会向程序发出信号。在现代操作系统中，当处理器执行到int 3时，会触发一个SIGTRAP信号，通知我们的调试程序。当然，如果我们想要实现一个断点，我们就需要在指定位置修改内存，将内存覆盖为int 3，然后运行，触发中断，等执行完这个断点之后，我们再将原来的内存覆写回来。

下面这张图很好的展现了这个过程，我们按照这个原理来实现断点的生成:

但是，这里我们怎么利用系统发出的SIGTRAP信号，来通知我们的调试进程，断点的发生呢。我们可以使用waitpid来实现，设置断点，程序执行，调用waitpid等待SIGTRAP的信号发生。然后可以将断点信息传给用户。

实现程序断点

首先我们设置一个断点的类，方便我们的设置和使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class breakpoint{
	public:
		breakpoint (pid_t pid, std::intptr_t addr) : m_pid(pid),m_addr(addr),m_enable(false),m_saved_data(0) {}
		//启用禁用
		void enable();
		void disable();
		//检查启用
		auto is_enable() const->bool {return m_enable;}
		//获取地址
		auto get_address() const->std::intptr_t {return m_addr;} 

	private:
		pid_t m_pid;
		std::intptr_t m_addr;
		bool m_enable;
		uint8_t m_saved_data;	//用来存储被覆盖的函数
};

这里主要是用于跟踪存储断点的状态，断点设置的主要实现还是在enable和diable中，我们来尝试实现他们:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void breakpoint::enable(){
	auto data = ptrace(PTRACE_PEEKDATA,m_pid,m_addr,nullptr);	 //返回的data是64位
	m_saved_data = static_cast<uint8_t> (data & 0xff);			//8位是用来存储64位信息的最低位数据
	uint64_t int3 = 0xcc;									  //64位的int3方便对齐
	uint64_t data_with_int3 = ((data & ~0xff) | int3);
	ptrace(PTRACE_POKEDATA,m_pid,m_addr,data_with_int3);

	m_enable = true;
}

void breakpoint::disable(){
	auto data = ptrace(PTRACE_PEEKDATA,m_pid,m_addr,nullptr);
	auto restore_data = ((data & ~0xff) | m_saved_data);
	ptrace(PTRACE_POKEDATA,m_pid,m_addr,restore_data);

	m_enable = false;
}

这里我们用到的原理是使用PTRACE_PEEKDATA的请求到ptrace，给定指定的进程和内存地址，会返回该地址前的一个64位的数据。我们先将要被覆盖的地址保存下来，然后将int3的数据0xcc覆写上去，然后使用PTRACE_POKEDATA请求，将内容覆写会程序的内存中，从而实现了断点的设置。取消断点则反之，将数据恢复后再写会去。这个过程中一定要注意内存地址的对齐，不要覆盖错了位置。

添加到调试器中

我们已经简单的实现了断点的方法和属性，接下来我们将其添加到调试器中，来实现我们对程序的控制，我们需要做到以下几点：

• 在debugger类中添加存储断点信息的数据结构
• 创建一个方法函数用来设置断点set_breakpoint_at_address
• 修改我们的handle_cammand函数，使其支持断点操作

1
2
3
4
5
6
7
8
9
10

class debugger{
	public:
   		...
		//设置断点
		void set_breakpoint_at_address(std::intptr_t addr);

  	private:
		...
		std::unordered_map<std::intptr_t,breakpoint> m_breakpoint;
};

首先添加新的属性和函数到程序调试器中，我们使用哈希表unoredered_map，以地址作为键，以断点作为值进行存储。

然后我们创建一个函数用来设置我们的断点set_breakpoint_at_adress:

1
2
3
4
5
6

void debugger::set_breakpoint_at_address(std::intptr_t addr){
	std::cout << "设置断点到 " << std::hex << addr << "处"<< std::endl;
	breakpoint bp {m_pid,addr};
	bp.enable();
	m_breakpoint[addr] = bp;	//存储断点信息
}

然后我们修改我们的命令行处理函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void debugger::handle_command(const std::string& line){
	if(line.empty()){
		return;
	}
	auto args = split(line,' ');
	auto command = args[0];
	if(is_prefix(command,"continue")){
		...
	}else if(is_match(command,"exit")){
		...
	}else if(is_prefix(command,"breakpoint")){
		std::string addr {args[1],2};						//去除16进制数据前的0x
		set_breakpoint_at_address(std::stol(addr,0,16));	  //从数据的开头开始按十六进制转换成intptr_t可读的长整数
	}else{
		...
	}
}

至此为止，我们的断点就设置完成啦

test test test

让我们试试能不能正常的使用，虽然我们现在只能设置断点，还不能正常的执行它，也不能取消它，我们可以看一看它的表现：

现在我们希望将断点下在程序的call pmem处，由于地址的空间随机化，我们在objdump 中只能看到指令的偏移地址，但是我们可以通过进程的内存映射找到程序的加载入口，我们可以计算出0x558b09f02000+0x16bb就是我们要下断点的位置。

看一看效果：

非常成功！

不过由于我们还没有编写能够终止断点的函数，所以程序到这里就直接停下来了，我们之后再来完善