5475 - A Linking Loader

　　一个对象模块是编译器处理源程序的过程中产生的。一个链接载入程序（或者称为链接程序）能够用来整合许多对象模块。当一个程序包含了许多单独的编译模块的时候，我们就需要用到它。它有两个最主要的功能：一是重新分配每个对象模块的代码和数据（因为编译器不知道一个模块将会被放置在哪一个内存里），二是解决两个模块之间的符号引用。比如一个主程序可能会引用平方根函数sqrt，它可能被定义在一个单独的代码模块中。链接程序需要最低限度地给每个模块中的代码和数据分配地址，然后将sqrt函数的地址放置在主模块代码中合适的位置。
　　一个对象模块有序地包含0个或多个外部符号定义、0个或多个外部符号引用、0个或多个字节的代码和数据（可能包含对外部符号值的引用）以及一个模块结尾标志。在这个问题中，一个对象模块表示为一个文本行序列，每行以一个大写字母开头，描述了剩余文本的含义。它们的格式如下所示。每行文本间存在空白分隔符（一些空格或制表符），每行的末尾也可能存在多余的空白分隔符。

　　· D symbol offset
　　“D”语句是一个外部符号定义。它定义了symbol的地址为当前模块的代码和数据的第一个字节地址向后偏移offset字节。symbol是一个长度小于等于8的大写字母字符串。offset是一个至多4位的十六进制数（使用大写字母A-F）。比如，在一个模块中，被分配的地址从(100)16开始，“D START 5C”表示符号START将会被分配地址(15C)16。在一组测试数据中，这样的定义至多为100个。
　　· E symbol
　　“E”语句是一个外部符号引用。它表明symbol的值可能会在当前模块的代码或数据中被调用（可能被定义在另一个对象模块中，并且可能会在当前模块之后）。比如，“E START”表示符号STATR的值（被分配的地址）可能在当前模块的代码和数据中被使用。每一个模块中，“E”语句从0开始连续编号，使它们能够在“C”语句中被引用。
　　· C n byte1 byte2 ... byten
　　“C”语句指定了当前模块的代码和数据的第一个或后n个字节的地址。数值n是一个一位或两位的十六进制数，并且不超过十六进制的10。每一个byte是一个一位或两位的十六进制数，或者是一个“”符号。一个“”符号后方跟随一个字节（中间不存在换行），表示引用当前模块中一个从0开始编号的外部符号。编译器将这个符号的值（即它的地址）插入当前链接程序所指的位置（即“”符号所代表的地址以及后一个地址），十六进制数的高位放在“”所指示的位置。其余的字节（不跟随在一个“”后方）将会被放入连续的内存地址中，起始位置为第一个未使用的内存地址。比如语句“C 4 25 0 37”将会把四个十六进制值(25)16 (01)16 (5C)16 (37)16 放入接下来四个未使用的内存地址，假设当前模块的“E”语句已经引用了一个已经被定义地址为(15C)16的符号。如果这个被引用的符号从未被定义，那么将其地址视为(0000)16。
　　· Z
　　一行一个字母“Z”代表了当前模块的结束。

　　你可以假设不存在超过四位十六进制数的地址。每行的格式都按照以上所述并且不存在语法错误。

　　输入数据存在多组测试数据。每组数据至少包含一个需要被按顺序链接的模块，以仅包含一个“$”的一行结束。每组数据的起始地址为(100)16。
　　最后一组数据之后是仅包含一个“$”的一行。

　　对于每一组数据，输出它的编号（从1开始），一个对于被载入字节的十六位校验和（将在之后描述）以及一个载入表。载入表按字典序升序给出每个被定义或引用的符号以及他们的地址。对于未定义的符号，地址处输出“????”，但在“C”语句中引用时应视为(0000)16。对于重复定义的符号，在地址后输出“M”，并且使用第一次定义的值。具体格式参考样例输入输出。相邻两组测试数据之间用一个空行分开，但最后一组测试数据后请不要存在多余空行。
　　十六位校验和的计算方法如下：首先将其值设为0，然后以升序遍历所有地址，每次循环左移一位，然后加上该内存地址所存储的值，并无视溢出。


　　循环左移的定义为，将十六位校验和的二进制的最高位移至最低位。比如FF00循环左移一位之后得到FE01。
　　为了方便理解，此处对样例中第一个测试数据的校验和做出解释，此时内存中存储的6个值分别为01, 02, 03, 04, 05, 06（均为十六进制）。校验和初始为0，
　　00 × 2 + 01 = 01;
　　01 × 2 + 02 = 04;
　　04 × 2 + 03 = 0B;
　　0B × 2 + 04 = 1A;
　　1A × 2 + 05 = 39;
　　39 × 2 + 06 = 78.

蓝桥杯