汇编程序第一遍和第二遍教程

Question

是否有很好的教程来解释汇编程序的第一遍和第二遍及其算法？我搜索了很多关于它们的信息，但没有得到满意的结果。如果有教程，请链接。

Answer 1

不知道有什么教程，真的没什么。

one:
  inc r0
  cmp r0,0
  jnz one
  call fun
  add r0,7
  jmp more_fun
fun:
  mov r1,r0
  ret
more_fun:

汇编器/软件就像人类一样从上到下读取源文件，从文件中的字节 0 到末尾。对于每次传递要完成的内容没有硬性规定，并且不一定是“文件”传递，而是“数据”传递。

第一遍：当你阅读每一行时，你会解析它。您正在构建某种数据结构，其中包含按文件顺序排列的指令。当您遇到这样的标签时：，您会跟踪前面的指令，或者也许您在指令之间有一个标记，但您选择执行它。当你遇到一条使用标签的指令时，你有两个选择，你现在可以去找那个标签，如果它是一个向后看的标签，那么你应该已经看到它了，就像 jnz one 指令一样。 如果您到目前为止一直在跟踪指令的数量和大小（如果字长可变），那么如果它是相对指令，您现在可以选择编码该指令，如果指令集使用绝对指令，您可能只需要留下一个占位符。

现在call fun和jump more_fun指令提出了一个问题，当你到达这些指令时，你此时无法解析它们，你不知道这些标签是该文件的本地还是在另一个文件中，因此你无法对该指令进行编码第一遍，你必须保存以供以后使用，这就是第二遍的原因。

第二遍可能是跨数据结构的遍，而不是实际在文件上的遍，这在很大程度上是特定于实现的。例如，您可能有一个一维结构数组，所有内容都在其中。您可以选择对该数据进行多次传递，例如，通过数组启动一个索引来查找未解析的标签。当您找到未解析的标签时，请通过数组发送第二个索引以查找标签定义。如果您没有找到它，那么，特定于应用程序，您的汇编器是否创建稍后链接的对象，或者是否创建二进制文件，是否必须将这个汇编程序中的所有内容解析为二进制步骤？如果是对象，那么您假设这是外部的，除非特定于应用程序，否则您的汇编器需要将外部标签定义为外部。因此，丢失标签是否是一个错误取决于应用程序。如果不是错误，则针对特定应用程序，您应该对最长/最远类型的分支进行编码，留下地址或距离详细信息供链接器填写。

对于您找到的标签，您现在已经大致了解了距离。现在，根据汇编器的指令集和/或功能，您需要对数据进行多次传递。您需要开始对指令进行编码，假设您至少有一种相对距离调用或分支指令，您必须在第一个编码过程中决定是否希望（我假设）是一个更短/更小的指令相对距离分支或假设较大的一个。在指令中得到一次或几次编码传递之前，您无法真正确定较小的是否会到达。

top:
  ...
  jmp down
  ...
  jnz top
  ...
down:

当您向下编码 jmp 时，您可以乐观地选择将其编码为较小的（如果字长可变，则为字节/字数）相对分支，从而确定距离。当您到达 jnz top 时，可以说它恰好是距离 top 足够近的字节，可以使用相对分支进行编码。在第二遍中，尽管您必须返回并完成向下跳转，但您发现它无法到达，您需要更多字节/字将其编码为长分支。现在 jnz 顶部也必须成为远分支（导致向下再次移动）。你必须不断地传递指令，计算它们的远/短距离，直到你不做任何改变地通过。小心不要陷入无限循环，在一次循环中，您可以缩短一条指令，但这会导致另一条指令延长，而在下一次循环中，延长一条指令会导致另一条指令延长，但第二条指令会缩短，这样就会永远重复。

我们可以回到顶部，在您的第一遍中，您可能会构建多个数据结构，也许当您构建一个已找到标签的列表和一个缺失标签的列表时。第二遍时，您将查看丢失的列表，看看它们是否在找到的内容中，然后以这种方式解决它们。或者也许在第一遍中，有些人可能会认为这是单遍汇编程序，当您找到标签时，在继续浏览文件之前，您会回头看看是否有人在寻找该标签（或者该标签是否已定义）声明错误）我将其称为多遍汇编器，因为它仍然多次传递数据。

现在让情况变得更糟。以 ARM 指令集和任何其他固定长度指令集为例。您的相关分支通常编码在一条指令中，因此是固定长度的指令集。远分支通常涉及从该地址找到的数据加载 pc，这意味着您确实需要指令的两项，然后在该指令的相对范围内的某个位置包含包含分支绝对地址的数据字。您可以选择强制用户创建这些，但使用 ARM 汇编器为例，他们可以并且将会为您执行此操作，最简单的示例是：

ldr r0,=0x12345678
...
b somewhere

该语法意味着使用值 0x12345678 加载 r0，该值不适合 arm 指令。汇编器使用该语法所做的事情是，它尝试在该指令可到达的代码中找到一个可以放置数据值的死点，然后将该指令编码为来自 pc 相对地址的加载。例如，在无条件分支之后是隐藏数据的好地方。有时您必须使用 .pool 等指令来鼓励或提醒汇编器放置此数据的好地方。r0 不是程序计数器 r15，您可以在那里使用 r15 将其连接到上面的分支讨论。

看看我为这个项目创建的汇编器http://github.com/dwelch67/lsasim，一个固定长度的指令集，但我强制用户分配单词并从中加载，我不允许快捷方式arm汇编器倾向于允许。

我希望这有助于解释事情。最重要的是，您无法通过一次线性传递数据来解析标签，您必须返回并将这些点连接到前向引用的标签。我认为无论如何你都必须做很多遍来解析所有的长/短编码（除非指令集/语法强制用户显式指定绝对分支与相对分支，并且有些执行 rjmp 与 jmp 或 rjmp 与 ljmp、rcall与呼叫等）。对“文件”进行一次传递肯定不是问题。如果您允许包含类型指令，某些工具将创建一个临时文件，其中它会在创建一个不包含包含内容的单个文件时提取所有包含内容，然后该工具对此进行一次传递（这就是 gcc 管理包含的方式，例如，有时保存中间文件并查看生成了哪些文件）（如果您报告带有警告/错误的行号，那么您必须管理临时文件行与原始文件名和行。）。

Answer 2

David Solomon 的书Assemblers and Loaders是一个很好的起点。这是一本较旧的书，但信息仍然相关。

您可以下载该书的 PDF版本。