Problem G
R2: Use Def

This is the $3$rd of $4$ steps in the SRE problem. The complete problem specification is on the NSA Cyber Challenge website.

Encoding

The input lines are binary data encoded as a string using the “hexlify” method (named for the way Python implements it in the binascii module). The binary $16$-bit unsigned integer represented in hexadecimal as 0xBEEF would simply be converted into an ASCII string “beef” (always use lower-case letters). The most significant bytes come first.

Input

The input is a binary MARIE program image represented as a series of hexadecimal strings. Each line will contain one string (a $16$-bit word) for each memory location. There will be less than or equal to $4\, 096$ lines.

Output

The demonstrated output format is sufficient to complete this problem. Each line of disassembly is printed as per problem R0. Subordinate to each line of disassembly are lines describing the inputs and outputs. Inputs are displayed as “ <– Storage=Definition”, and outputs as “ –> Storage=Definition”. See the sample output example below for spacing, number of dashes, etc. Register storage is displayed as the register’s name (e.g. AC). Memory storage is displayed as “ Cell[Address]”, where the address is the 3-hex-digit index of the memory cell. Constant definitions are displayed in hexadecimal (without padding). Symbolic definitions are displayed as “ <From Instruction>” with the defining instruction displayed exactly as in the disassembly, including its address. Finally, please include the Halt instruction.

Memory values should be output as 4 hexadecimal digits. Addresses (and immediate operands) should be output as 3 hexadecimal digits.

a000
5000
2009
5000
3009
300a
200a
6000
7000
0000
000a

000: Clear
  --> AC=0x0
001: Input
  --> AC=<FROM 001: Input>
002: Store 009
  <-- AC=<FROM 001: Input>
  --> Cell[009]=<FROM 001: Input>
003: Input
  --> AC=<FROM 003: Input>
004: Add 009
  <-- AC=<FROM 003: Input>
  <-- Cell[009]=<FROM 001: Input>
  --> AC=<FROM 004: Add 009>
005: Add 00a
  <-- AC=<FROM 004: Add 009>
  <-- Cell[00a]=0xa
  --> AC=<FROM 005: Add 00a>
006: Store 00a
  <-- AC=<FROM 005: Add 00a>
  --> Cell[00a]=<FROM 005: Add 00a>
007: Output
  <-- AC=<FROM 005: Add 00a>
008: Halt