The Complete LC-3 Execution Lifecycle: From Assembly to Execution Traces A first-principles walkthrough of a Rust-based LC-3 VM — from two-pass assembler to execution cycles, and laying the theoretical groundwork for zkVM traces.

Clone the repository and experiment alongside this guide for a deeper understanding.

🔗 Repository: mahantybiplab/LC-3-Rust

A Virtual Machine, in this context, is a software simulation of physical hardware — every wire, register, and memory slot modelled as a data structure. Because it isn’t a physical chip, we call it “virtual.” From a practical perspective, it lets us safely run LC-3 programs in an isolated software environment.

Our LC-3 VM has exactly two components: memory and registers. Here is how they relate to each other and to the instructions that flow through them:

A compiled instruction — say, 0001 111 001 0 00 101 — gets loaded into memory at address x3000. When the CPU fetches it, the first 4 bits (0001) identify the opcode (ADD), which is matched against the instruction set. The matched operation then reads from and writes to the registers. That arrow from memory → opcodes → registers is the entire execution loop in one picture.

1. Memory — The Warehouse

A flat array of 65,536 slots (x0000 to xFFFF), each holding a 16-bit value. It stores everything side by side in the same address space: your program’s instructions, string data, and variables.

Not all of that space is yours to use, though. The LC-3 reserves specific regions for the operating system, interrupt handling, and device I/O:

The regions matter for our VM:

• x0000–x00FF — Trap Vector Table. Each address holds the starting address of a system call routine (PUTS, GETC, HALT, etc.).

• x0100–x01FF — Interrupt Vector Table. Addresses for hardware interrupt handlers.

• x0200–x2FFF — OS and Supervisor Stack. Reserved; your program must not touch this.

• x3000–xFDFF — User program space. This is where our loader writes the .obj file, and why .ORIG x3000 appears at the top of every LC-3 assembly program.

• xFE00–xFFFF — Device register addresses (memory-mapped I/O). xFE00 is KBSR (keyboard status) and xFE02 is KBDR (keyboard data). Reading these addresses triggers hardware interaction rather than returning ordinary memory values.

• Why it’s needed: The CPU needs a place to hold far more information than it can keep close to itself. The entire assembled .obj file is written here before a single instruction executes.
• The catch: The CPU cannot do arithmetic directly on values in memory. It must first copy them into registers, operate there, and write the result back to a register or to a memory address — depending on whether the instruction is an ADD (register result) or an ST/STI (store result back to memory).

2. Registers — The Workbench

The CPU’s ultra-fast, immediately accessible workspace. Physically, think of registers as a type of memory that’s much closer to the CPU than RAM. The LC-3 has 8 general-purpose registers (R0–R7), each holding one 16-bit value, plus two special-purpose registers:

• The Program Counter (pc): Holds the memory address of the next instruction to fetch. After every fetch, the CPU increments it by 1 automatically. Branch and jump instructions work by overwriting it — which is how loops and conditionals are possible in hardware.

• The Condition Flags (cond): Every time a value is written into a general-purpose register, the CPU records whether that value was Negative (N), Zero (Z), or Positive (P). Branch instructions inspect this flag to decide whether to jump or fall through. Only one flag is live at a time — writing to any register immediately overwrites the previous one.

• Why it’s needed: All arithmetic and logic in LC-3 happens exclusively between registers. ADD R4, R2, R3 adds whatever is currently in R2 and R3 — not raw values from memory.

• The constraint: With only 8 general-purpose registers, you are always juggling. Needing a 9th value means spilling something back to memory first.

In Rust, the entire physical reality of our LC-3 is two structs:

pub struct Registers {
    pub r0: u16,   // \
    pub r1: u16,   //  |
    pub r2: u16,   //  |
    pub r3: u16,   //  | general purpose (R0–R7)
    pub r4: u16,   //  |
    pub r5: u16,   //  |
    pub r6: u16,   //  |
    pub r7: u16,   // /
    pub pc: u16,   // program counter
    pub cond: u16, // condition flags: N / Z / P
}

pub struct VM {
    pub memory: [u16; 65536], // 64K × 16-bit slots = 64 × 1,024 × 16 bits = 65536 × 16 bits =  1,048,576 bits = 128 K
    pub registers: Registers,
}

Every mechanism in the sections that follow — the loader(the code in main.rs that reads the .obj file and writes each 16-bit word into vm.memory starting at x3000), the fetch-decode-execute loop, the ASCII conversion, the branch logic — is ultimately just reads and writes to these two structs.

.ORIG x3000

; =====================================
; 1. GET THE FIRST INPUT
; =====================================
LEA R0, PROMPT1       ; Load address of PROMPT1 string into R0
PUTS                  ; Print the string (TRAP x22)
GETC                  ; Wait for keypress → result in R0 (TRAP x20)
OUT                   ; Echo the typed char (TRAP x21)
LD  R1, ASCII_NEG     ; R1 ← -48 (0xFFD0 in two's complement)
ADD R2, R0, R1        ; R2 = R0 − 48  (ASCII digit → integer)
LD  R0, NEWLINE       ; Load '\n' character
OUT                   ; Print newline

; =====================================
; 2. GET THE SECOND INPUT
; =====================================
LEA R0, PROMPT2
PUTS
GETC
OUT
ADD R3, R0, R1        ; R3 = R0 − 48  (ASCII digit → integer)
LD  R0, NEWLINE
OUT

; =====================================
; 3. DO THE MATH (SHOWING BOTH ADD MODES)
; =====================================
ADD R4, R2, R3        ; MODE 1 — REGISTER:  R4 = R2 + R3
ADD R4, R4, #2        ; MODE 2 — IMMEDIATE: R4 = R4 + 2 (baked into bits!)

; =====================================
; 4. PRINT THE RESULT
; =====================================
LEA R0, RESULT_STR
PUTS
LD  R1, ASCII_POS     ; R1 ← +48 (0x0030)
ADD R0, R4, R1        ; R0 = R4 + 48  (integer → ASCII char)
OUT
LD  R0, NEWLINE
OUT
HALT                  ; TRAP x25

; =====================================
; DATA SEGMENT
; =====================================
PROMPT1     .STRINGZ "Enter 1st digit: "
PROMPT2     .STRINGZ "Enter 2nd digit: "
RESULT_STR  .STRINGZ "Sum plus 2 is: "
NEWLINE     .FILL x000A    ; ASCII '\n'
ASCII_NEG   .FILL xFFD0    ; −48 in two's complement
ASCII_POS   .FILL x0030    ; +48
.END

Here is the column-by-column logic for the jumps in our Data Segment. Remember: in Hex, you carry over only after hitting 15 (F).

1. Adding 18 Words (x12) Used to find the address after PROMPT1 and PROMPT2.

  x3019   (Start)
+ x0012   (18 words = 18 = 16+2 = (1×16^1)+(2×16^0) = x0012) 
───────
  x302B

• Right column: 9 + 2 = 11. In Hex, 11 is B.
• Second column: 1 + 1 = 2.

2. Adding 16 Words (x10) Used to find the address after RESULT_STR.

  x303D   (Start)
+ x0010   (16 words = 16 + 0 = (1×16^1) + (0×16^0) = x0010)
───────
  x304D

• Right column: D + 0 = D.
• Second column: 3 + 1 = 4.

3. Sequential Fills (+1) Used for single-word directives like .FILL.

x304D + 1 = x304E   (ASCII_NEG)
x304E + 1 = x304F   (ASCII_POS)
x304F + 1 = x3050   (End of Program)

1. Hex to Binary

• Each hexadecimal digit = 4 binary bits.

• Convert each hex digit individually.

2. Hex to Decimal

• Use powers of 16 from right to left:
  16³, 16², 16¹, 16⁰

Example: Convert x300A

Hex: x300A

Step 1: Hex → Binary

Convert each digit to 4-bit binary:

Binary result: 0011 0000 0000 1010

Step 2: Hex → Decimal Calculate:
3×16³ + 0×16² + 0×16¹ + 10×16⁰

• 3 × 4096 = 12288
• 0 × 256 = 0
• 0 × 16 = 0
• 10 × 1 = 10

Decimal result: 12298

Use this mapping for fast conversion:
0=0000, 1=0001, …, 9=1001, A=1010, B=1011, C=1100, D=1101, E=1110, F=1111

First — why does MSB = 1 mean negative?

In a normal unsigned 16-bit number, every bit position carries a positive weight: $2^{15},\ 2^{14},\ 2^{13},\ \ldots,\ 2^1,\ 2^0$ So 1111 1111 1111 1111 = $65535$. No negatives possible.

Two’s complement fixes this with one architectural decision: make the MSB’s weight negative. $\mathbf{-2^{15}},\ 2^{14},\ 2^{13},\ \ldots,\ 2^1,\ 2^0$ That’s it. Every bit except the MSB keeps its positive weight. The MSB alone contributes $-32768$. So any bit pattern with MSB = 1 starts at $-32768$ and adds the remaining bits back up — which is always a negative result.

Now, working out xFFD0 step by step

Step 1 — Hex to Binary Convert each hex digit to 4 bits:

Full 16-bit string: 1111 1111 1101 0000

Step 2 — Check the Sign Bit The MSB is 1. As established above, this means the number is negative and its MSB alone is already contributing $-2^{15} = -32768$. We now need to find the exact magnitude using the Flip and Add 1 shortcut — which is faster than computing the full weighted sum.

Step 3 — Flip All the Bits (NOT) Invert every bit — 1 becomes 0, 0 becomes 1:

Before:  1111 1111 1101 0000
After:   0000 0000 0010 1111

Step 4 — Add 1

0000 0000 0010 1111
+                   1
= 0000 0000 0011 0000

The trailing 1111 + 1 ripple-carries left, turning all four bits to 0 and setting the next bit up.

Step 5 — Binary to Decimal Only two bits are set in 0000 0000 0011 0000: $2^5 + 2^4 = 32 + 16 = 48$

Result The magnitude is 48. The original MSB was 1 (negative), so: $\texttt{xFFD0} = -48$

The program converts a digit to ASCII by adding 0x0030 (+48) to the raw integer result. This works perfectly as long as the sum is a single digit (0–9):

But ASCII digits only occupy the range 0x0030–0x0039. The moment the sum hits 10 or above, you spill out of that range entirely:

For the inputs 7 + 1 + 2 = 10 in this program, the output is ':' instead of '10' — because the program has no logic to handle multi-digit results. Producing '10' would require splitting the integer into its tens digit (1) and units digit (0) and converting each separately, which involves division — an operation LC-3 has no native instruction for.

This is a deliberate simplification for teaching purposes. The program correctly demonstrates the ASCII ↔ integer conversion mechanic; it just assumes inputs small enough that their sum stays within 0–9.

 Address     Memory Contents        Segment
          .───────────────────. 
          |    (Empty / OS)   | 
          |───────────────────| 
 x3000    |  0xE018 (LEA)     |  ◄── PC Start
 x3001    |  0xF022 (PUTS)    |   ▲
   ...    |       ...         |   │  INSTRUCTIONS
 x3017    |  0xF021 (OUT)     |   │  (25 words)
 x3018    |  0xF025 (HALT)    |   ▼
          |───────────────────|  ─── BOUNDARY
 x3019    |  'E' (0x0045)     |   ▲
 x301A    |  'n' (0x006E)     |   │
   ...    |       ...         |   │  DATA / STRINGS
 x304D    |  0x000A ('\n')    |   │  (55 words)
 x304E    |  0xFFD0 (-48)     |   │
 x304F    |  0x0030 (+48)     |   ▼
          |───────────────────| 
          |    (Available)    |
          '───────────────────'

Bitwise shifts move an entire sequence of bits left or right by a specified number of spaces. Think of it like a conveyor belt: bits are pushed in one direction, causing bits on one edge to fall off into the void, while empty spaces on the other edge are filled with new bits.

1. Left Shift (<<): The Multiplier Shifting left pushes all bits to the left. The bits on the far left fall off and disappear, while new 0s are fed into the right side.

Mathematically, shifting left by $n$ spaces is the same as multiplying by $2^n$.

Example: 3 << 2 (Shift the number $3$ left by $2$ spaces)

• Original: 0000 0011 ($3$)
• Shift 1: 0000 0110 ($6$)
• Shift 2: 0000 1100 ($12$)

2. Right Shift (>>): The Divider Shifting right pushes all bits to the right. The bits on the far right (the smallest values) fall off and are permanently lost. For unsigned integers, new 0s are fed into the left side.

Mathematically, shifting right by $n$ spaces is the same as integer division by $2^n$ (meaning remainders are dropped).

Example: 24 >> 3 (Shift the number $24$ right by $3$ spaces)

• Original: 0001 1000 ($24$)
• Shift 1: 0000 1100 ($12$)
• Shift 2: 0000 0110 ($6$)
• Shift 3: 0000 0011 ($3$)

🛠️ Why we use them in the VM?

In computer architecture, you rarely use shifts for math; you use them to align data.

In your LC-3 VM, a 16-bit instruction contains multiple “fields” packed tightly together. To read the Destination Register (DR) sitting in bits [11:9], you have to move it to the end of the line before you can isolate it:

1. Shift it: instruction >> 9 pushes the 16-bit word right by 9 spaces. The DR bits slide all the way down into the [2:0] slots.
2. Mask it: Now that the DR bits are at the end, you use & 0x7 to chop off all the higher bits, leaving you with just the exact Register ID!

To understand how a VM bridges the gap between small instruction components and 16-bit math, we have to look at two specific mechanisms: Sign Extension and the Condition (COND) Flags.

1. Sign Extension (sign_extend)

The Problem: The LC-3 processor only knows how to do math on full 16-bit numbers. However, instructions often contain smaller numbers. For example, an ADD instruction in Immediate Mode only has 5 bits for the number. A LD offset only has 9 bits. How do we add a 5-bit number to a 16-bit register?

The Wrong Way (Zero Padding): Imagine we want to add $-2$. In 5-bit Two’s Complement, $-2$ is 11110. If we just fill the remaining 11 bits with zeros so the ALU can process it, we get 0000 0000 0001 1110. In 16-bit math, that is $+30$. We completely destroyed the value!

The Right Way (Sign Extension): To keep the mathematical value identical while making the binary wider, we must look at the Most Significant Bit (MSB) of the small number (the sign bit) and copy it to fill all the new empty space.

• If MSB is 0 (Positive): Pad with 0s.
• If MSB is 1 (Negative): Pad with 1s.

Example of Sign-Extending our 5-bit $-2$: 11110 $\rightarrow$ copy the leading 1 $\rightarrow$ 1111 1111 1111 1110 (which is properly $-2$ in 16-bit math).

sign_extend is called on every PCoffset9 and imm5 before arithmetic:

fn sign_extend(mut x: u16, bit_count: u8) -> u16 {
   if (x >> (bit_count - 1)) & 1 != 0 {
       x |= 0xFFFF << bit_count;
   }
   x
}

For a backward-jumping PCoffset9 like 0b1_1111_1100 (= −4 in 9-bit space):

Test sign bit: (0b1_1111_1100 >> 8) & 1 = 1  → negative!

0xFFFF << 9   = 1111 1110 0000 0000
x (9-bit)     = 0000 0001 1111 1100

x |= result:
  0000 0001 1111 1100
| 1111 1110 0000 0000
= 1111 1111 1111 1100  = 0xFFFC = −4 in i16  ✓

Without this, a backward branch offset of −4 would be misread as +508, sending the PC into garbage memory.

2. Condition Flags (COND)

The Problem: A CPU has no memory of the past; it just blindly executes the instruction currently in the PC. So, how do you write an if statement or a while loop? The CPU needs a way to evaluate a value and make a routing decision.

The Solution: The Condition Flags act as a tiny, automatic “sticky note” that the CPU updates every time it writes data into a register. The LC-3 has three flags: N (Negative), Z (Zero), and P (Positive).

How it works:

1. The Trigger: Any instruction that writes to a register (ADD, AND, NOT, LD, LDI, LDR, LEA) triggers the flag update.
2. The Evaluation: The CPU looks at the raw 16-bit binary just before it goes into the register.
   • If the MSB is 1, it sets the N flag.
   • If all 16 bits are 0, it sets the Z flag.
   • Otherwise, it sets the P flag.
3. The Consumer: Branch instructions (BR) do absolutely no math. They simply look at the “sticky note.” If you write BRz (Branch if Zero), the CPU checks the Z flag. If it’s set, the PC jumps; if not, the PC just moves to the next line.