justinmeiners/lc3-vm

Write your own virtual machine for the LC-3 computer!

LC-3 VM

READ TUTORIAL HERE

This is a tutorial and source code for creating a VM of the LC3 computer.

Editing

The documentation and source are generated from the .lit file using srcweave. If you don't want to go through the trouble of setting it up, your contributions are welcome. Just make your edits the .lit file, and we can regenerate it for you.

License

This applies to the article and figures:

CC BY-NC-SA 4.0

This applies to all code:

MIT License

Copyright (c) 2022 Justin Meiners

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

lc3-vm's Issues

Typo?

Hi there! Thank you for your great work!
BTW, I've noticed a little typo. If it is, can I submit PR?

it can understand a machine language which you can you can use to program it.
https://github.com/justinmeiners/lc3-vm/blob/master/index.lit#L41

bug in PUTSP trap implementation?

in

lc3-vm/docs/index.html

Lines 929 to 944 in e854c34

	<pre class="prettyprint"><code class="">{
	/* one char per byte (two bytes per word)
	here we need to swap back to
	big endian format */
	uint16_t* c = memory + reg[R_R0];
	while (*c)
	{
	char char1 = (*c) &amp; 0xFF;
	putc(char1, stdout);
	char char2 = (*c) &gt;&gt; 8;
	if (char2) putc(char2, stdout);
	++c;
	}
	fflush(stdout);
	}
	</code></pre>

it seems that the trap only stops printing when it encounters a 0x0000. however, the specification says that:

A character string consisting of an odd
number of characters to be written will have x00 in bits [15:8] of the memory
location containing the last character to be written.

in my interpretation, it sounds like the trap should stop when it has encountered a 0x0000, or it should print the first byte, and if the second byte is 0x00, it should stop, otherwise it should print it too. but this does not align with your implementation. i wonder whether it is a bug or my interpretation is wrong?

Typo: it seems the `break` keyword in JSR(R) implementation is redundant

lc3-vm/index.lit

Lines 540 to 557 in e86236f

	### Jump Register
	--- JSR
	{
	uint16_t long_flag = (instr >> 11) & 1;
	reg[R_R7] = reg[R_PC];
	if (long_flag)
	{
	uint16_t long_pc_offset = sign_extend(instr & 0x7FF, 11);
	reg[R_PC] += long_pc_offset; /* JSR */
	}
	else
	{
	uint16_t r1 = (instr >> 6) & 0x7;
	reg[R_PC] = reg[r1]; /* JSRR */
	}
	break;
	}
	---

Tests for testing correct implementation?

Hi!
First, thanks for the guide, I enjoyed it 😃 I am wondering if there are test-images or something that extensively test if things are implemented correctly? The code I came up with does not match your example code exactly and I'd like to see if would make a difference in a hypothetical "compliance test suite".

Need help regarding bitwise AND

Hello, I need help in this part of the ADD instruction code:

uint16_t r0 = (instr >> 9) & 0x7;

This is my first time using bitwise operations. The tricky part for me is why exactly is & 0x7 used? I understand the intention behind it (getting the register index), but it does not seem intuitive to me and clearly I am missing something. From where does the 0x7 come from? I did the operation by hand and sure enough it does work, but how would I figure this out myself? Excuse me, but I am at loss, everything else before this went smoothly.

Thank you.

Is Gonna Work?

Missing fflush?

Hi,
shouldn't there be fflush(stdout) in this block?

case TRAP_IN:
                        /* TRAP IN */
                        {
                            printf("Enter a character: ");
                            char c = getchar();
                            putc(c, stdout);
                            reg[R_R0] = (uint16_t)c;
                        }

                        break;

Changes to the LEA and TRAP instructions in the Third Edition

Changes have been made to the LEA and TRAP instructions in the third edition of Introduction to Computing Systems, that you don't seem to have taken into account:

Major Changes in the Third Edition
The LC-3
A hallmark of our book continues to be the LC-3 ISA, which is small enough to be described in a few pages and hopefully mastered in a very short time, yet rich enough to convey the essence of what an ISA provides. It is the LC “3” because it took us three tries to get it right. Four tries, actually, but the two changes in the LC-3 ISA since the second edition (i.e., changes to the LEA instruction and to the TRAP instruction) are so minor that we decided not to call the slightly modified ISA the LC-4. The LEA instruction no longer sets condition codes. It used to set condition codes on the mistaken belief that since LEA stands for Load Effective Address, it should set condition codes like LD, LDI, and LDR do. We recognize now that this reason was silly. LD, LDI, and LDR load a register from memory, and so the condition codes provide useful information – whether the value loaded is negative, zero, or positive. LEA loads an address into a register, and for that, the condition codes do not really provide any value. Legacy code written before this change should still run correctly. The TRAP instruction no longer stores the linkage back to the calling pro- gram in R7. Instead, the PC and PSR are pushed onto the system stack and popped by the RTI instruction (renamed Return from Trap or Interrupt) as the last instruc- tion in a trap routine. Trap routines now execute in privileged memory (x0000 to x2FFF). This change allows trap routines to be re-entrant. It does not affect old code provided the starting address of the trap service routines, obtained from the Trap Vector Table, is in privileged memory and the terminating instruction of each trap service routine is changed from RET to RTI. As before, Appendix A specifies the LC-3 completely.

Going Branchless

I'm not on a development computer at the moment, but some thoughts.

Sign Extend is called a lot, We could turn this into a branch free routine. (removes 41 instructions on compiler explorer output -O3).

uint16_t sign_extend(const uint16_t x, const int bit_count)
{
    uint16_t mask = -((x >> (bit_count - 1)) & 1);
    return x | (mask << bit_count);
}

We could also change the update_flags to be branchless (Saving another 40 instructions). Unfortunitely it would require changing the enum numbering which would break existing programs.

enum
{
    FL_ZRO = 0, /* Z */
    FL_POS = 1, /* P */
    FL_NEG = 3, /* N */
};
void update_flags(const uint16_t r)
{
    reg[R_COND] = ((reg[r] >> 14) & 2) | (reg[r] != 0);
}

Kind regards,
Mike Brown

Question about using uint16

Hi experts,

I'm reading the tutorial and wondering why you use unsigned 16-bit integer for PC offset?
For example, in the example code below, what happens if oc_offset should be a negative (thus 1 extended) number? I think the sign gets extended but still oc_offset is intepreted as a positive nunmber as it's an uint16_t. Where is my misunderstanding? Thanks!

{
    uint16_t pc_offset = sign_extend(instr & 0x1FF, 9);
    uint16_t cond_flag = (instr >> 9) & 0x7;
    if (cond_flag & reg[R_COND])
    {
        reg[R_PC] += pc_offset;
    }
}

Condition flags aren't updated when reading keyboard characters

While trying to reproduce the issue for #43, I ran into another issue related to the traps. It turns out the traps aren't updating condition flags, which can result in some odd behavior.

I think this is best illustrated using the following program:

.orig x3000

read_character:
    in

loop:
    brnzp loop

print_message:
    lea r0, msg
    puts
    halt

msg: .STRINGZ "hello world"

.end

Given that brnzp is essentially an unconditional jmp, this program should read a single character and then hang in the loop. You can confirm this is the case with the official lc3sim program, as well as my implementation that uses the lc3os.obj file. However, the article's implementation results in some pretty interesting behavior:

$ ./lc3 input.obj
Enter a character: fhello worldHALT

Notice how even though it should be stuck in the loop, it actually continues to print_message and executes the rest of the program? (And if the halt isn't included, the program actually restarts and goes back to read_character, which I assume is due to the PC register overflowing. I haven't checked to see how the real lc3sim handles this though.)

Shouldn't sign_extend() return a int16_t instead of a uint16_t?

According to the spec:

PCoffset9 A 9-bit value; bits [8:0] of an instruction; used with the PC+offset addressing mode.
Bits [8:0] are taken as a 9-bit signed 2’s complement integer, sign-extended to 16
bits and then added to the incremented PC to form an address. Range −256..255.

In the LDI implementation example the memory read will always be positively offsetted compared to the PC because the return value of sign_extend is an unsigned type:

{
    /* destination register (DR) */
    uint16_t r0 = (instr >> 9) & 0x7;
    /* PCoffset 9*/
    uint16_t pc_offset = sign_extend(instr & 0x1FF, 9);
    /* add pc_offset to the current PC, look at that memory location to get the final address */
    reg[r0] = mem_read(mem_read(reg[R_PC] + pc_offset));
    update_flags(r0);
}

ins<15> instantiation - Use of uninitalised variable.

May I just say that the use of this template pattern to "build" common behaviour between instructions is beautiful. Its nice to know I can still learn new things.

Again, while looking at branches - I have discovered a bug. As op is known at compile time, we can also compute opbit, again allowing us to completely remove the branches. Optimisations can and should already do this for us. However, if we utilise constexpr we get better error reporting.

    constexpr uint16_t opbit = (1 << op);
    if constexpr (0x4EEE & opbit) { r0 = (instr >> 9) & 0x7; }
    ... etc ...

The error is.

(363): note: see reference to function template instantiation 'void ins<15>(const uint16_t)' being compiled
(272) : warning C4700: uninitialized local variable 'r1' used

Relating to absolute jumps? Which suggests to me the bit pattern for 15 has an issue?

The C and C++ files are missing

These links from the tutorial are missing:

• https://justinmeiners.github.io/lc3-vm/lc3.c
• https://justinmeiners.github.io/lc3-vm/lc3-alt.cpp

Wow thank you so much!

Wow this tutorial is really amazing & helpful!

I wanna learn some basic virtualization technology principles and found your tutorial!

It's really great!

Just wanna open the issue to say thank you! 👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍

Some error in section LDI?

Hi, good job on your guide of VM implementation!

Maybe there's an error in section LDI?

// the value of far_data is an address
// of course far_data itself (the location in memory containing the address) has an address
char* far_data = "apple";

// In memory it may be layed out like this:

// Address Label      Value
// 0x123:  far_data = 0x456
// ...
// 0x456:  string   = 'a'

// if PC was at 0x100
// LDI R0 0x023
// would load 'a' into R0

Shouldn't the last 2 lines be:

// LDI R0 0x123
// would load 'a' into R0

?

TRAP instruction should modify R7

According to the LC3 spec, the TRAP instruction should save the incremented PC to R7 and then jump to the trap implementation using the trap vector table.

Since we're implementing traps directly in the VM instead of relying on a assembly-based implementations, we don't need to jump to the implementation. However, the fact that R7 changes is technically part of the spec and is an observable side-effect, so we should still make that change. Without it, it's easy to write programs that work on our VM but not the official VM due to forgetting to save R7.