Problem Solving

Translating Algorithms to LC-3

A step-by-step method for turning any algorithm into working LC-3 code.

The Translation Method

When you face a complex problem (like the palindrome checker), don't try to write assembly from scratch. Use this systematic method:

Step 1: Write pseudocode — Solve it in plain English or Python first. Step 2: Plan your registers — Decide what each register holds. Step 3: Translate line by line — Convert each pseudocode line using the patterns you know. Step 4: Handle the details — Add data labels, handle edge cases, set up memory.

Let's walk through this with the palindrome problem as a case study.

Step 1: Pseudocode

Before touching LC-3, write the solution in a way you understand:

``
left = start of string
right = end of string (last character before null)

while left < right:
if string[left] == space:
left = left + 1
continue
if string[right] == space:
right = right - 1
continue
if string[left] != string[right]:
result = -1 (not a palindrome)
stop
left = left + 1
right = right - 1

result = 1 (is a palindrome)
``

This is the same algorithm whether you implement it in Python or LC-3. The hard part is translating each line.

Step 2: Plan Your Registers

Before writing code, assign a job to each register. Write it as a comment at the top of your program.

; Register plan:
; R1 = left pointer (moves forward)
; R2 = right pointer (moves backward)
; R3 = character loaded from left
; R4 = character loaded from right
; R5 = temporary for comparisons
; R0 = used for storing results
Why plan registers? In high-level languages you name variables freely. In LC-3 you only have 8 registers. Planning prevents you from accidentally overwriting a value you still need.

Step 3: Translate Line by Line

Now take each pseudocode line and ask: "Which pattern do I need?"

Line: left = start of string We need to load the address x5000 into R1. Since x5000 is far from our program, use LD with a .FILL:
LD R1, STRING_ADDR     ; R1 = x5000 (left pointer)
; ...
STRING_ADDR .FILL x5000
Line: right = end of string We need to find the null terminator, then back up one. This is Pattern 6 (Find End of String):
ADD R2, R1, #0         ; R2 starts at beginning
FIND_END
LDR R5, R2, #0         ; load character at R2
BRz FOUND_END           ; null? done
ADD R2, R2, #1          ; keep looking
BR FIND_END
FOUND_END
ADD R2, R2, #-1         ; back up to last real character
Line: while left < right: This is the two-pointer loop condition. Compute R2 - R1 and check if positive (Pattern 5):
COMPARE_LOOP
NOT R5, R1
ADD R5, R5, #1
ADD R5, R2, R5          ; R5 = R2 - R1 (right - left)
BRnz IS_PALINDROME      ; if right <= left, pointers crossed → palindrome!
Line: if string[left] == space: left += 1; continue Load the character, check if it's a space (Pattern 7), and if so, advance and loop back:
LDR R3, R1, #0          ; R3 = character at left
LD R5, NEG_SPACE         ; R5 = -32
ADD R5, R3, R5           ; R5 = char - 32
BRnp NOT_SPACE_L         ; if not space, continue
ADD R1, R1, #1           ; skip the space
BR COMPARE_LOOP          ; re-check the loop condition
NOT_SPACE_L
Line: if string[left] != string[right]: result = -1 Compare the two characters (Pattern 3). Subtract one from the other — if not zero, they don't match:
; R3 already has left char, load right char
LDR R4, R2, #0          ; R4 = character at right

; Compare: R3 - R4
NOT R5, R4
ADD R5, R5, #1
ADD R5, R3, R5           ; R5 = left_char - right_char
BRnp NOT_PALINDROME      ; if not zero, characters don't match!
Lines: left += 1; right -= 1 Simple pointer movement:
ADD R1, R1, #1          ; left pointer moves right
ADD R2, R2, #-1         ; right pointer moves left
BR COMPARE_LOOP         ; back to the top

Step 4: Handle the Details

Add the result-storing code and data labels:

IS_PALINDROME
AND R0, R0, #0
ADD R0, R0, #1           ; R0 = 1
STI R0, RESULT_ADDR      ; store 1 at x6000
BR DONE

NOT_PALINDROME
AND R0, R0, #0
ADD R0, R0, #-1          ; R0 = -1 (xFFFF)
STI R0, RESULT_ADDR      ; store -1 at x6000

DONE HALT

STRING_ADDR .FILL x5000
RESULT_ADDR .FILL x6000
NEG_SPACE   .FILL #-32

The Complete Program

Putting it all together:

.ORIG x3000
; Register plan:
; R1 = left pointer       R2 = right pointer
; R3 = left character      R4 = right character
; R5 = temp for comparisons  R0 = result

; Setup: load string start address
LD R1, STRING_ADDR

; Find end of string
ADD R2, R1, #0
FIND_END
LDR R5, R2, #0
BRz FOUND_END
ADD R2, R2, #1
BR FIND_END
FOUND_END
ADD R2, R2, #-1

; Main comparison loop
COMPARE_LOOP
NOT R5, R1
ADD R5, R5, #1
ADD R5, R2, R5         ; R5 = right - left
BRnz IS_PALINDROME     ; pointers crossed → palindrome

; Skip spaces on left
LDR R3, R1, #0
LD R5, NEG_SPACE
ADD R5, R3, R5
BRnp NOT_SPACE_L
ADD R1, R1, #1
BR COMPARE_LOOP
NOT_SPACE_L

; Skip spaces on right
LDR R4, R2, #0
LD R5, NEG_SPACE
ADD R5, R4, R5
BRnp NOT_SPACE_R
ADD R2, R2, #-1
BR COMPARE_LOOP
NOT_SPACE_R

; Compare characters
NOT R5, R4
ADD R5, R5, #1
ADD R5, R3, R5         ; R5 = left_char - right_char
BRnp NOT_PALINDROME    ; mismatch!

; Advance both pointers
ADD R1, R1, #1
ADD R2, R2, #-1
BR COMPARE_LOOP

IS_PALINDROME
AND R0, R0, #0
ADD R0, R0, #1
STI R0, RESULT_ADDR
BR DONE

NOT_PALINDROME
AND R0, R0, #0
ADD R0, R0, #-1
STI R0, RESULT_ADDR

DONE HALT

STRING_ADDR .FILL x5000
RESULT_ADDR .FILL x6000
NEG_SPACE   .FILL #-32
.END

The Translation Checklist

Use this for any problem:

  • Can I solve this on paper? Write pseudocode first. If you can't solve it in English, you can't solve it in assembly.
  • What registers do I need? List each variable from your pseudocode and assign it a register. If you need more than 7 (R0–R6, with R7 reserved), you'll need to save some to memory.
  • What patterns does each line use? Comparison? String walking? Pointer arithmetic? Look at the patterns reference.
  • Where do my constants come from? Values outside -16 to 15 need .FILL + LD. Far addresses need .FILL + LDI/STI.
  • Did I preserve condition codes? Every ADD, AND, NOT, LD, LDR, LEA sets the CC. Make sure the CC reflects the right value before each BR.
    • Exercise

    Translate this pseudocode to LC-3: Read characters until the user types "!" (ASCII 33). Count how many characters were typed (not including the "!"). Print the count as a digit. Assume the count will be 0-9.

    main.asm
    1
    R0
    x00000
    R1
    x00000
    R2
    x00000
    R3
    x00000
    R4
    x00000
    R5
    x00000
    R6
    x00000
    R7
    x00000
    PCx3000
    CC
    NZP
    Quiz

    You're translating `if (a != b) goto FAIL`. R0 = a, R1 = b. Which LC-3 pattern should you use?

    ← Common Patterns & IdiomsRecursion →