Moving LC-3 P.C. more than 256 Hex addresses down? [Binary]

[Enharmonics]

Homework Statement

I'm writing a program in binary on the LC-3. The program counts the occurrences of a specific character in a file. Relevant excerpts from the assignment instructions:

1) Download the source code for Figure 5.17 from the textbook webpage as code1.bin.

• Code x3000 as the program’s load-address in the initial line of the program.
• Code x3100 for the starting address of the file in the empty line (location x3012)

[...]

3) [50 points] Start the LC3 simulator:

· Load verse.obj and code1.obj into memory (at x3100 and x3000 respectively)

· Set a breakpoint at the Halt instruction and run the program to count the number of ‘i’ characters. The count should be 8.

· Set breakpoints at the Halt and Increment R2 instructions. Run the program again and complete the table to show R2 and R3 (in hex) at each breakpoint.

[...]

This part was easy enough. No problems. Here's the part that's tripping me up:

4) [25 points] Extend code1.bin to build a list in memory of the addresses where the ‘i’ matches occur. Start the list at x3500. Save your modified program as code2.bin.

I'll explain what's confusing me in the "attempt at a solution" section.

Homework Equations

N/A.

The Attempt at a Solution

First and foremost, my code (in Binary):

0011 0000 0000 0000 ;Codes x3000 as Load-address of program
0101 010 010 1 00000 ;R2 <- 0
0010 011 000010000 ;R3 <- M[x3012]
1111 0000 0010 0011 ;TRAP x23 (Loads INPUT into R0)
0110 001 011 000000 ;R1 <- M[R3]
;LOOP BEGINS HERE
0001 100 001 1 11100 ;R4 <- R1 - EOT
0000 010 000001000 ;If above = 0, exit loop
1001 001 001 111111 ;R1 <- NOT R1
0001 001 001 1 00001 ;R1 <- R1 + 1
0001 001 001 0 00 000 ;R1 <- R1 + R0
0000 101 000000001 ;If above != 0, do NOT increment counter
0001 010 010 1 00001 ;R2 <- R2 + 1 (increment counter)
0001 011 011 1 00001 ;R3 <- R3 + 1 (increments pointer to next char in file)
0110 001 011 000000 ;R1 <- M[R3] (loads next char into R1)
0000 111 111110110 ;BRnzp x3004 (unconditionally RETURN to loop start)
;LOOP ENDS HERE
0010 000 000000100 ;R0 <- M[x3013]
0001 000 000 0 00 010 ;R0 <- R0 + R2
1111 0000 0010 0001 ;TRAP x21
1111 0000 0010 0101 ;TRAP x25
0011 0001 0000 0000 ;Codes x3100 for the starting address of the file
0000 000 000110000

What I'm confused about is the "starting the list at x3500" bit. I don't know how I'm actually supposed to "get" to that memory address. My textbook (Patt & Patel's Intro. to Computing Systems, 2e) doesn't really cover how to do that.

For instance, my first-instinct solution to the problem involved using Load Indirect (LDI), but that seems to be impossible, since it can only take a 9-bit offset to the value of the Program Counter.

The problem there is I want to code the instructions that write to the list right under the R2 <- R2 + 1 instruction (the one that increments the counter). That instruction is at memory address x300A (since the program starts at x3000), so my LDI instruction would be at x300B, and accounting for the incremented Program Counter, in order to get to address x3500, I'd have to move

x3500 + (NOT x300C + 1) = 0011 0101 0000 0000 + (1100 1111 1111 0100) = 0000 0100 1000 1101 = x048D

Thus it's impossible, since the most bits that could fit into PCOffset9 in LDI is 0 1000 1101, which would be x008D, not x048D.

Or, more simply put, it's impossible because 9 bits can represent at most up to the number 256, and x3500 is more than 256 spaces away from x300C.

I've thought of a "workaround" involving the Load Effective Address (LEA) instruction: I could use one LEA instructions to move from x300C to x3250 by setting the 9-bit offset to 244 (which is within the representable range of 9 bits). Since LEA stores the a memory ADDRESS in a register, I could then use ANOTHER LEA on that same register to move from x3251 (again, accounting for incremented Program Counter) to x3500, which would be 249 spaces (again, within representable range for 9 bits).

I haven't actually tried this yet, primarily because it just feels... cumbersome? Inconvenient? I'm not sure what word to use. I just can't shake the feeling that there has to be an easier way to do this. Some kind of way to immediately "jump" the Program Counter to x3499 so I can just use ONE LEA to store x3500 in a register, or even to directly store a value into x3500 from x300C, but as I said, my textbook doesn't mention anything about this.

The reason I feel like there has to be a simpler way is that part 1) of the instructions directs us to "code x3000 as the program's load-address", and the way we do that is by literally writing x3000 in binary as the first line of the program (as you can see in my code).

That struck me as interesting because it's literally just writing a memory address in binary form as a line of code - no opcode is involved, no register, nothing. Thing is, I don't know if this can only be done as the FIRST LINE of a program (i.e. only as a "load-address" that serves as a marker for the beginning of the program).

Is it possible to simply write 0011 0101 0000 0000 (i.e. x3500) as a line of code ANYWHERE in the program, and the Program Counter will "jump" to that memory address? I'm too afraid to try this without knowing for sure. It's my first time coding in binary, and it's pretty intimidating relative to higher-level languages (no console to hold your hand in an LC-3 simulator).

Any help here would be appreciated. Apologies if this is outside the scope of "programming languages" (if that's what this even is) the forum is intended to offer help for.

 

[lewando]

...it's impossible because 9 bits can represent at most up to the number 256

Are you sure? 1 1111 1111₂ = 511₁₀.

 

[Enharmonics]

Are you sure? 1 1111 1111₂ = 511₁₀.

You're absolutely right, but since the LC-3 sign-extends its 9-bit PC-offset values to 16 bits, using (for example) 1 1111 1111 as the offset would actually yield

b1111 1111 1111 1111 = xFFFF

Rather than b0000 0001 1111 1111 = x01FF = d511.

That's why I couldn't use

b0000 01000 1000 1101 = x048D

as the offset in an LDI or a single LEA instruction, since the most I could use is 9 of its bits: 0 1000 1101, which would be sign-extended to 16 bits as

0000 0000 1000 1101 = x008D.

So it seems if I want a positive number, the 9th bit has to be left as 0, thus I have to abide by the limits of decimal representation of a set of n 2's complement bits - that is, the range from

-2^n-1 . . . (2^n-1 - 1)

Or in the case of 9 bits, -256 to 255.

 

[lewando]

Yes, that is a fail on my part. Sorry. . Glad I wasn't super snarky. Have you explored the STR instruction?

 

[lewando]

That struck me as interesting because it's literally just writing a memory address in binary form as a line of code - no opcode is involved, no register, nothing. Thing is, I don't know if this can only be done as the FIRST LINE of a program (i.e. only as a "load-address" that serves as a marker for the beginning of the program).

You can do this in an area outside your code area but close enough to your code area so that is is within reach of your offset. Usually right after the end of your code area.

You can even embed it within your code, just make sure you don't execute it (jump over it).

 

[Tom.G]

since the LC-3 sign-extends its 9-bit PC-offset values to 16 bits

Are you sure? The documentation I found indicates something different. See the LEA instruction and the definition of pgoffset9.

EDIT: Is it possible to simply write 0011 0101 0000 0000 (i.e. x3500) as a line of code ANYWHERE in the program, and the Program Counter will "jump" to that memory address?
No. The program Loader (later on in your studies) reads the first 16 bits of data as the memory address in which to store the program.

(Preview to later studies: [short definition]
The Loader is a program or part of an operating system whose job is to read a program from external storage and save it in memory for execution. Since most programs have some absolute addresses in them, they have to be at a known/predefined address to execute properly.)