Problem G
A Linking Loader
---- The 2003 ACM Programming Contest World Finals ----

An object module is produced by a compiler as a result of processing a source program. A linking loader (or just a linker) is used to combine the multiple object modules used when a program contains several separately compiled modules. Two of its primary tasks are to relocate the code and data in each object module (since the compiler does not know where in memory a module will be placed), and to resolve symbolic references from one module to another. For example, a main program may reference a square root function called sqrt, and that function may be defined in a separate source module. The linker will then minimally have to assign addresses to the code and data in each module, and put the address of the sqrt function in the appropriate location(s) in the main module’s code.
 「ソースプログラムを処理した結果として、オブジェクトモジュールがコンパイラからつくり出される。別々にコンパイルされたモジュールを複数個含むプログラムの場合、これらのモジュールを結合するのにリンクローダ(リンカ)が使われる。リンカに基本的な役割が二つあり、ひとつ目は個々のモジュール内のコードとデータを再配置すること。(コンパイラがメモリのどこにモジュールが置かれるか知らないから。)二つ目はモジュール同士のシンボルの参照を解決すること。例えば、メインプログラムがsqrtという名前の平方根関数を参照としようとしていて、その関数が他のソースモジュールに定義されているとする。そこで、リンカは少なくとも、個々のモジュールのコードとデータにアドレスを割り当てないといけないし、sqrt関数のアドレスをメインモジュールコード内の適正箇所に書き込まないといけない。」

An object module contains (in order) zero or more external symbol definitions, zero or more external symbol references, zero or more bytes of code and data (that may include references to the values of external symbols), and an end of module marker. In this problem, an object module is represented as a sequence of text lines, each beginning with a single uppercase character that characterizes the remainder of the line. The format of each of these lines is as follows. Whitespace (one or more blanks and/or tab characters) will appear between the fields in these lines. Additional whitespace may follow the last field in each line.
 「オブジェクトモジュールは、順序として以下のものを含む、外部シンボル定義、外部シンボル参照、コードおよびデータ(外部シンボルの値を参照するかもしれない)、モジュールの終了記号。本問題では、オブジェクトモジュールはテキスト行として表現する。各行の先頭にアルファベット大文字の1字が入り、行の意味を決める。各行のフォーマットが以下の通り。ホワイトスペース(ひとつあるいはそれ以上のブランク文字かタブ文字)がフィールドの間に存在するかもしれない。また、各行の最後のフィールドの後ろにもホワイト文字があるかもしれない。」

  • A line of the form “D symbol offset” is an external symbol definition. It defines symbol as having the address offset bytes greater than the address where the first byte of code and data for the current object module is located by the linker. A symbol is a string of no more than eight upper case alphabetic characters. The offset is a hexadecimal number with no more than four digits (using only upper case alphabetic characters for the digits A through F). For example, in a module that is loaded starting at the address 10016, the line “D START 5C” indicates that the symbol START is defined as being associated with the address 15C16. The number of D lines in a test case is at most 100.
     「”D symbol offset"は外部シンボル定義の行。リンカによって配置された本モジュールのコードやデータに対し、そのスタートアドレスからのオフセット(バイト単位)アドレスを有するシンボルを定義する。シンボルは大文字8字以内の文字列。オフセットは4桁以内の16進数(A~Fには大文字しか使わない)。例えば、10016のアドレスからスタートするモジュールに対し、行”D START 5C”はアドレス15C16をもつものとしてシンボルSTARTを表す。D行の行数はテストケースでは最大100行まで。」

  • A line of the form “E symbol” is an external symbol reference, and indicates that the value of symbol (presumably defined in another object module) may be referenced as part of the code and data for the current module. For example, the line “E START” indicates that the value of the symbol START (that is, the address defined for it) may be used as part of the code and data for the module. Each of the “E” lines for each module is numbered sequentially, starting with 0, so they can be referenced in the “C” lines.
     「“E symbol”は外部シンボル参照の行。本モジュールのコードやデータの一部として参照されるシンボル(ほかのモジュールに定義されている)の値を示す。例えば、“E START”という行は、モジュールのコードとデータの一部としてシンボルSTARTの値(つまり、定義されたアドレス)が使われることを表す。各モジュールの各E行は、0からスタートする通し番号として番号づけられるので、 "C"行参照されることが可能。」

  • A line of the form “C n byte1 byte2 … byten” specifies the first or next n bytes of code and data for the current module. The value n is specified as a one or two digit hexadecimal number, and will be no larger than 10 hexadecimal. Each byte is either a one or two digit hexadecimal number, or a dollar sign. The first byte following a dollar sign (always on the same line) gives the 0-origin index of an external symbol reference for this module, and identifies the symbol which is to have its 16-bit value inserted at the current point in the linked program (that is, in the location indicated by the dollar sign and the following byte). The high-order byte is placed in the location indicated by the dollar sign. The values specified for the other bytes (those not following a dollar sign) are loaded into sequential memory locations, starting with the first (lowest) unused memory location. For example, the line “C 4 25 $ 0 37” would cause the values 2516 0116 5C16 and 3716 to be placed in the next four unused memory locations, assuming the first “E” line for the current module specified a symbol defined as having the address 15C16. If the 0-origin index of the external symbol reference is an undefined symbol, the 16-bit value inserted at the current point in the linked program is 000016.
     「 “C n byte1 byte2 … byten”は、本モジュールのコードとデータの最初またはそのつぎのnバイトを表す。値nは16進数の1桁ないし2桁、16進数10を超えることはない。個々のバイトも同様に1桁ないし2桁の16進数、あるいは、ドル記号($)のどちらだ。ドル記号の後に続く最初の1バイト(ドル記号とつねに同じ行にある)は本モジュールの外部シンボル参照のインデックス(0から)を示す。リンクが行われたとき、シンボルの16ビット値をここに、つまり、ドル記号とそれに続く1バイトの示す位置に、書き込まないといけない。上位バイトがドル記号の位置に書き込む。ドル記号の後に続く1バイト以外のものについて、その値がそのまま、未使用メモリの低いほうのスタート位置に転送される。例えば、“C 4 25 $ 0 37”の行は、次の4つの未使用メモリに、値2516 0116 5C16 3716を置くことを表す。ただし、本モジュールの最初のE行にアドレス15C16をもつシンボルを記述しているとする。0からスタートする外部シンボル参照のインデックスが未定義シンボルになってしまったときに、リンク時に書き込まれた16ビットの値は000016となる。」

  • A line of the form “Z” marks the end of an object module.
     「“Z”行はモジュールの終了マーク。」

You may assume that no address requires more than four hexadecimal digits. Lines are always given in the order shown above. There are no syntax errors in the input.
 「16進数4桁以上のアドレスは必要としない。行の並びはつねに上に説明した順序であり、入力にシンタックスエラーはないものとする。」

Input
This problem has multiple input cases. The input for each case is one or more object modules, in sequence, that are to be linked, followed by a line beginning with a dollar sign. The first address at which code is to be loaded in each case is 10016.
 「本問題に複数の入力ケースを含む。個々のケースにおいて、順次に、リンクすべき1つあるいは複数のモジュールが与えられ、終わりに先頭ドル($)記号の行が入る。すべてのケースにおいて、コードのスタートアドレスは10016だ。

The last case will be followed by a line containing only a dollar sign.
 「最後のケースの後に、ドル記号だけを含む行が入る。」

Output
For each case, print the case number (starting with 1), the 16-bit checksum of the loaded bytes (as described below), and the load map showing the address of each externally defined or referenced symbol, in ascending order of symbol name. For undefined symbols, print the value as four question marks, but use zero as the symbol’s value when it is referenced in “C” lines. If a symbol is defined more than once, print “M” following the address shown in the load map, and use the value from the first definition encountered in any object module to satisfy external references. Format the output exactly as shown in the samples.
 「個々のケースに対し、1からスタートするケース番号(case number)、転送されるバイトの16ビットチェックサム(詳細は下に述べる)、個々の外部定義、外部参照シンボルのアドレスを示すロードマップを表示すること。シンボル名は昇順で並ぶこと。未定義シンボルについては、値として4つの「?」記号を表示することだが、 “C”行に参照されるシンボルの値としては0を使うこと。シンボルが1回以上定義された場合、ロードマップに示すアドレスの後に “M”を表示すること。その値は外部参照を満たす、最初のモジュールにある定義によるものとすること。サンプルデータのフォーマットに従うこと。」

The 16-bit checksum is computed by first setting it to zero. Then, for each byte assigned to a memory location by the loader, in increasing address order, circularly left shift the checksum by one bit, and add the byte from the memory location, discarding any carry out of the low-order 16 bits.
 「16ビットチェックサムは次のように計算する。初期値は0。アドレスの昇順でメモリに転送される各バイトに対し、チェックサムを1ビット左に循環シフトしてから、そのバイトと加算を行い、下位16ビットからのキャリアを切り捨てる。」

Sample Input
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
$
$

Output for the Sample Input
出力サンプルに正確に従えとの指示なので、右のグラフを
参考すること。

Case 1: checksum = 0078
 SYMBOL    ADDR
--------     ----
END         0105
MAIN        0100

Case 2: checksum = 548C
 SYMBOL     ADDR
--------      ----
ENTRY        0104
SUBX          0126 M
SUBY          ????

Comments are closed.

Post Navigation