UVA1024 A Linking Loader

目标模块（object module）是编译器处理源码后的产物。链接加载器（linking loader），也称链接器（linker），用来把分别编译好的目标模块合并到一起。它的主要任务有两个：对代码和数据进行重定位（因为编译器并不知道这些模块将被放在内存中的哪个位置），以及解析模块之间的符号引用。比如，主程序可能会引用一个称为 sqrt 的平方根函数，而此函数可能定义在其他模块中，因此链接器必须给每个模块的数据和代码分配内存地址，然后把 sqrt 函数的地址写到主函数代码中的合适位置（可能会有多个）。 一个目标模块按顺序包含 0 个或多个外部符号定义（external symbol definition），0 个或多个外部符号引用（external symbol reference），0 个或多个字节的代码和数据（它们可能会包含对外部符号的引用），最后是模块结束标志。在本题中，一个目标模块用一个文本序列来描述，其中每一行的第一个字符为一个大写字母，表示该行的类型。在一行中，相邻数据项之间由一个或多个空白字符隔开，最后一个数据项后可能会有多余的空白字符。一共有4种可能的行。 - 格式为 `D symbol offset` 的行是一个外部符号定义，表示 `symbol` 的地址是当前模块的首地址加 `offset` 。这里的 `symbol` 由不超过 8 个大写字母组成，而 `offset` 是一个不超过 4 位的十六进制整数（只用大小字母表示）。比如，在一个首地址为 $\mathtt{100_{(16)}}$ 的模块中，`D START 5C` 会让 START 的地址为 $\mathtt{15C_{(16)}}$ 。此类型的行在单组数据中至多出现 100 次。 - 格式为 `E symbol` 的行是一个外部符号引用，表示本模块可能会引用 `symbol` 这个符号（而这个符号很可能在其他模块中定义）。比如，行 `E START` 表示本模块可以使用 `START` 这个符号。在每个模块中，所有的 “E” 操作行按照出现顺序从 0 开始编号。这个编号将被 C 行使用。 - 格式为 `C n byte1 byte2 ... byten` 的行是需要填充到内存中的 n 个字节（模块代码或数据），其中 n 是一或两位十六进制整数，且不超过 $10_{(16)}$ 。每个byte 要么是一个一或两位的十六进制整数，要么是一个美元符号 \$ 。美元符号的下一个字节（保证在同一行中）代表一个外部符号引用，该字节的数值等于 “E” 行的下标。如果这个外部符号有定义，把它的地址拷贝到 \$ 和它的下一个字节中，其中地址的高字节拷贝到 \$ 所对应的字节中。如果符号无定义，用$\mathtt{0000_{(16)}}$ 覆盖那两个字节。比如，若第一个 E 行（下标为 0）中的符号有定义，地址为 $\mathtt{15C_{(16)}}$，则行 `C 4 25 $ 0 37` 的作用是把 $\mathtt{25_{(16)},01_{(16)},5C_{(16)},37_{(16)}}$ 这 4 个地址放到内存中 。 - 单独一行 `Z` 表示模块结束。 在本题中：假定 4 位十六进制地址总是足够的，各行一定按照 D，E，C，Z 的顺序出现，并且不会包含格式错误。每个模块中的 C 行应按出现顺序填充到内存中（D 和 E 行只是模块描述，并不对应于实际的内存数据），不同模块按照输入顺序依次填充到内存中。填充时应按照地址从低到高的顺序进行，第一个模块的首地址总是 $\mathtt{100_{(16)}}$ 。

输入包含多组数据，每组数据包含一个或多个模块定义，最后一行是 \$ （作为单组数据的结束标志）。输入结束标志也是一行 \$。

对于每组数据，首先是测试数据编号和模块校验码（计算方法见后），然后是所有定义或引用的外部符号列表，按照符号名排序。对于没有定义的符号，在表里用 4 个问号表示，但在 C 行引用的时候作为 0 处理。如果一个符号定义多次，在地址后打印一个大写字母M，并且以第一次出现的定义为准。 校验码计算方式如下：首先设为 0 ，然后按照地址从低到高顺序依次处理各个字节，每次先把校验码循环左移一位，加上当前内存值，然后忽略进位保留低 16 位。 相邻两组数据的输出之间应有一个空行。 ### 输入输出样例 **输入 #1** ``` D MAIN 0 D END 5 C 03 01 02 03 C 03 04 05 06 Z $ D ENTRY 4 E SUBX E SUBY C 10 1 2 3 4 5 $ 0 6 7 8 9 A B C D E C 8 10 20 30 40 50 60 70 80 C 8 90 A0 B0 C0 D0 E0 $ 1 C 5 $ 0 FF EE DD Z D SUBX 01 C 06 A B C D E F Z D SUBX 05 C 06 51 52 53 54 55 56 Z $ $ ``` **输出 #1** ``` Case 1: checksum = 0078 SYMBOL ADDR -------- ---- END 0105 MAIN 0100 Case 2: checksum = 548C SYMBOL ADDR -------- ---- ENTRY 0104 SUBX 0126 M SUBY ???? ```