How To Initialize A Lc 3 Register To 100
Virtual Machines (VMs) are a magical affair: a computer being emulated inside a physical computer. Since this emulated computer isn't physical, we phone call information technology "virtual". Such a unproblematic description for something so powerful.
From a practical perspective, VMs permit users to safely run programs in an isolated environs: the emulated car.
Why build a Virtual Machine from scratch
So, why build i when there are already and so many dandy VMs out there? Simply put: To ameliorate understand how computers work. Personally, whenever I need to empathise something complex enough that reading past itself won't requite me a deep agreement, I must build it. That which I cannot build, I cannot deeply empathize.
I've constitute that learning how to build a elementary VM is a keen and seemingly underrated way to learn the bones philosophy behind assembly and assemblers.
Also, Justin Meiners and Ryan Pendleton already put out a great piece on building an LC-3 VM. I'm writing this document as a complement to this work. I go into a picayune more details and some of the underlying ideas I found tricky to understand. And as an alternative to writing an LC-three in C, I'm doing it in Rust.
You can notice the final source code here.
How to read this document
This guide is relatively long. VMs aren't uncomplicated, and at that place is a lot of knowledge near information technology that, as I went through it, I constitute to be sort of "hidden," or "heavy causeless to exist known," and that fabricated understanding much harder for me.
For example, I studied bitwise operations (such as shifts) a long fourth dimension ago, I know the concept, but I have never had the gamble to use it directly. And considering of that, many tricks used in systems-level programming went direct over my caput – these are "tribal" knowledge that people assume to be trivial, and therefore it is barely touched in these other documents.
I wanted to follow a different arroyo, a first-principles approach. I try to go over the most fundamental principles and tricks used to build a VM, with little prerequisite knowledge in systems programming other than entry-level Rust noesis.
I've learned a lot along the mode – systems programming is super fun. That said, let's become to it.
The VM abstraction
The virtual machine will take 2 main components: registers and retentiveness. It's much simpler than it sounds.
Retentivity is where we volition store a program's binary representation; information technology's a bounded array of bytes. Yup, that's all in that location is to information technology, a good onetime array that will comprise instructions and the indices are the addresses.
When loading an LC-3 programme into memory, we do information technology at the address/index 0x3000 (12288 in decimal), the program section of the VM'south memory. Everything before this index is reserved for other things we'll talk virtually afterward. Here's the memory layout for the LC-3 retention:
Registers will store data that our opcode (Performance Code) will operate on. Physically, think of registers similar a type of retentivity that's much closer to the CPU than, say, the RAM.
Here we have 7 of these general-purpose registers. On height of that, we take 2 special purpose registers that I'll talk nigh below.
Controlling the plan flow with the Program Counter (PC) Register
The program counter (PC) stores the accost of the next instruction in memory to be executed. In other words, it will point to an index/accost in our array that represents the memory of the VM.
Manipulating this PC register is how nosotros "walk" through each didactics and perform loops, conditional branching, and jumps; simply changing the index/accost will affect the execution of the next instruction. For instance, in a loop instruction, we change the PC to go back a few "steps" until we meet a specific status.
Just how practice nosotros check for these logical conditions? Enters our next special purpose register.
Checking for logical conditions with the Condition Flags (Cond) Register
And talking about conditions brings united states of america to the next special register: The condition flags annals that tells us about the last ciphering. This annals checks for conditions to perform command flow tasks (loops, ifs, etc.). It'southward a straightforward one, and information technology might not immediately make sense how we employ it, merely all it does is store the signal (negative, zero, or positive) status of the last performance that happened within the machine. Nosotros'll go over it in more detail afterward!
Structuring the projection
This is how I'm structuring the project:
LC_3 git:(principal) ✗ tree src src ├── hardware │ ├── education │ │ └── mod.rs // Teaching-related code │ ├── modernistic.rs // Gum-code for all the virtual hardware │ ├── register │ │ └── modern.rs // Register-related lawmaking │ └── vm │ └── modern.rs // Loftier-level VM-related code (uses the registers/didactics) └── main.rs This is dead elementary to represent in Rust; In src/hardware/register/modern.rs nosotros accept the abstraction for our registers:
pub struct Registers { pub r0: u16, pub r1: u16, pub r2: u16, pub r3: u16, pub r4: u16, pub r5: u16, pub r6: u16, pub r7: u16, pub pc: u16, pub cond: u16, } impl Registers { pub fn new() -> Registers { Registers { r0: 0, // full general purpose annals r1: 0, // general purpose annals r2: 0, // full general purpose annals r3: 0, // full general purpose register r4: 0, // full general purpose annals r5: 0, // general purpose register r6: 0, // general purpose register r7: 0, // full general purpose register pc: PC_START, // program counter cond: 0, // status flag } } pub fn update(& mut self, alphabetize: u16, value: u16) { match alphabetize { 0 => self.r0 = value, 1 => cocky.r1 = value, 2 => self.r2 = value, three => self.r3 = value, four => self.r4 = value, 5 => cocky.r5 = value, 6 => self.r6 = value, 7 => self.r7 = value, 8 => cocky.pc = value, 9 => self.cond = value, _ => panic!("Index out of bound"), } } pub fn go(&self, index: u16) -> u16 { match index { 0 => self.r0, 1 => self.r1, two => self.r2, 3 => self.r3, 4 => self.r4, five => self.r5, 6 => self.r6, vii => cocky.r7, 8 => cocky.pc, 9 => self.cond, _ => panic!("Index out of jump. "), } } } Notice how we're initializing the PC as: pc: PC_START,, where PC_START is 0x3000. That's considering, as we've seen in the specs, this is where the space in the VM's memory reserved for the user's program starts.
Also, find that we're explicitly using u16 (unsigned 16 bits) instead of the usual u8. We'll talk about this soon plenty!
So, for our condition flag register, its goal is to shop the information about the latest ciphering, which nosotros will then utilize to test logical conditions. Information technology's a simple Enum, but it contains some tricks:
enum ConditionFlag { POS = ane << 0, // Positive ZRO = 1 << one, // Zero NEG = 1 << 2, // Negative } The << operator is a left scrap shift operator. It'due south simpler than it looks: n << one thousand ways nosotros're moving (or shifting) the bits in the binary representation of the number n by k. for instance, 1 in binary representation is 0000000000000001.
1 << two means nosotros're shifting the bits twice to the left so that the 1 at the end of 0000000000000001 will effectively move to the left, twice. It ends upwards being 0000000000000100, which in decimal representation is 4. Thus, one << ii == four. And then why are we storing 1, 2, four here? Glad y'all asked. In binary, with 3 bits but:
-
1 == 001 -
2 == 010 -
4 == 100
And then nosotros're playing with the possible conditional flags settings! Because the status education will exist nzp (neg, null, pos) and only i can exist set at a fourth dimension, information technology volition either exist 001 (positive set nz1) 010 (zero set up, n1p) 100 (negative set, 1zp). And these three binary values are i, 2, and 4 in decimal base of operations. How cool is that?!
Now we've gotta add i more method to our Registers implementation: one to update the condition annals based on the last operation on a given (full general purpose) register:
pub fn update_r_cond_register(& mut cocky, r: u16) { if self.get(r) == 0 { // Note that `9` is the register number 9, // which is the cond register self.update(9, ConditionFlag::ZRO as u16); } else if (self.get(r) >> xv) != 0 { // a 1 in the left-almost bit indicates negative cocky.update(9, ConditionFlag::NEG as u16); } else { self.update(nine, ConditionFlag::POS as u16); } } What does the LC-iii compiled binary look like?
Now that nosotros have the skeleton of our VM'due south abstraction somewhat fix, let's take a step back and see how an LC-3 compiled binary looks like.
Under examples/ we take an already compiled hello_world plan for the LC-iii. Permit's try reading it and seeing what it looks like:
let data = fs::read(args[ane].clone()).wait("Unable to read file"); println!("information: {:?}\northward", information); Output:
data: [48, 0, 224, 2, 240, 34, 240, 37, 0, 72, 0, 101, 0, 108, 0, 108, 0, 111, 0, 32, 0, 87, 0, 111, 0, 114, 0, 108, 0, 100, 0, 33, 0, 0] Equally expected: gibberish.
Okay, so, quickly taking a expect at the fs::read docs we come across that its signature is: pub fn read<P: AsRef<Path>>(path: P) -> io::Upshot<Vec<u8>> meaning, it returns a vector of eight bits.
However, LC-three operates with xvi bits per instruction!
We take to alter how nosotros're reading the file to read information technology expecting 16 $.25 instead of 8.
Let's run across how the man-readable hello world programme in LC-3 assembly looks like:
.ORIG x3000 ; this is the address in retentivity where the program will be loaded LEA R0, HELLO_STR ; load the address of the HELLO_STR cord into R0 PUTs ; output the cord pointed to past R0 to the panel HALT ; halt the program HELLO_STR .STRINGZ "Hello Globe!" ; store this string here in the program .Cease ; mark the end of the file The offset line (.ORIG x3000) ways that the first sixteen bits read from the compiled binary tell the VM the position in memory where the program starts.
Dorsum to reading and loading the compiled binary, just now expecting u16 instead of u8:
// Note the `read_u16`, forcing information technology to read equally u16 and non u8. let base_address = f.read_u16::<BigEndian>().look("error"); allow mut accost = base_address as usize; loop { match f.read_u16::<BigEndian>() { Ok(didactics) => { println!("address: {:?} teaching: {:?}\due north", address, teaching); accost += 1; } Err(eastward) => { if e.kind() == std::io::ErrorKind::UnexpectedEof { println!("OK") } else { println!("failed: {}", e); } pause; } } } Endianness
Note that when we're reading the 16 bits chunks, we tell Rust we want it as BigEndian: f.read_u16::<BigEndian>().
Without diving too deep into information technology, endianness is the order or direction in which the "motorcar" reads binary data. You can either read from left to correct or right to left. The order is specific only to byte ordering and not bit ordering.
For instance, if we take just i byte, 0000 0010 (2 in decimal), it will be the aforementioned in big-endian or petty-endian. However, the ordering is afflicted one time we accept more than 1 byte.
Big-endian ways we're storing the "big cease" first, then the residue. Little-endian means storing the "little end" offset. This big/fiddling end thing means the nigh meaning byte, the byte in a binary value that holds the biggest position.
In 00000010 (2), the left-most cipher is the most significant one; changing it to ane would cause the virtually meaning modify to the number, information technology would turn information technology into 10000010, which is 130 in decimal.
Changing the correct-most zero would crusade the smallest change to the number: 00000011 is three.
Let'south consider a large 2 bytes number: 65,535, in binary: 1111 1111.
Since hither nosotros have two bytes, one is the about significant, the other is the least significant:
And now we reach the crux of this Big Endian vs. Little Endian understanding: Big Endian will beginning store the Most Pregnant Byte (MSB). Little Endian will store the Least Significant Byte (LSB) first.
Unlike machines, languages, implementations will use unlike endianness; such is life. LC-iii uses Big Endianness. That'south why we're using f.read_u16::<BigEndian>().
Now permit's go dorsum to the code higher up.
Running the code above passing the hi world binary file:
address: 12288 teaching: 57346 accost: 12289 instruction: 61474 accost: 12290 instruction: 61477 address: 12291 instruction: 72 address: 12292 instruction: 101 address: 12293 teaching: 108 address: 12294 instruction: 108 address: 12295 instruction: 111 address: 12296 teaching: 32 address: 12297 education: 87 address: 12298 teaching: 111 address: 12299 instruction: 114 address: 12300 instruction: 108 address: 12301 educational activity: 100 address: 12302 instruction: 33 address: 12303 instruction: 0 Note that it's showing 12288 as the base of operations accost, 12288 in hex is 0x3000, exactly how it's in the original specs for the LC-3; how cool is that?!
Nosotros accept to load the instruction 57346 in memory at the alphabetize 12288, 61474 at 12289, and then on.
Do you want to see something even cooler? In the hello world associates, the first pedagogy is
LEA R0, HELLO_STR ; load the address of the HELLO_STR cord into R0 PUTs LEA (we'll see what that is later) is the name of the instruction/opcode, let'due south meet the binary representation of that instruction in the spec:
Note that the OpCode is 1110.
Let's see the output of our println! over again:
address: 12288 education: 57346 So, load at 12288 (0x3000 in hex) the instruction 57346, this instruction in binary: 1110000000000010. Hey! The opcode is right there: 1110 000000000010.
The rest of the binary is the necessary information to perform the LEA operation, but yous run across that the OpCode is at that place. How cool is that?!
Now we have to load all these instructions coming from a plan into the VM retention:
pub struct VM { pub retention: [u16; MEMORY_SIZE], pub registers: Registers, } impl VM { pub fn new() -> VM { VM { memory: [0; MEMORY_SIZE], registers: Registers::new(), } } pub fn write_memory(& mut self, address: usize, value: u16) { self.memory[address] = value; } } Note that nosotros're using a constant MEMORY_SIZE that nosotros're defining beneath. This abiding is the maximum amount of retentiveness we're giving to our VM. We'll exist defining it as 65535, which is the max value for 16 bits.
And then our principal.rs looks like this
let base_address = f.read_u16::<BigEndian>().await("fault"); // Hither nosotros're loading the program in retentivity let mut address = base_address as usize; loop { match f.read_u16::<BigEndian>() { Ok(instruction) => { vm.write_memory(address, pedagogy); accost += i; } Err(e) => { if eastward.kind() == std::io::ErrorKind::UnexpectedEof { println!("OK") } else { println!("failed: {}", e); } break; } } } In plain English language: nosotros start at the base of operations address 0x3000, load the offset educational activity at this position, increment the address, load the next teaching, and and so on.
Executing the program
Once we accept a program loaded into the VM's memory, running it is a matter of walking through the memory positions using the value stored in the Program Counter (PC) register.
use vm::VM; pub const MEMORY_SIZE: usize = std::u16::MAX equally usize; pub fn execute_program(vm: & mut VM) { while vm.registers.pc < MEMORY_SIZE equally u16 { // Read instruction allow education = vm.read_memory(vm.registers.pc); // Increase program counter vm.registers.pc += 1; // Extract op_code and execute operation instruction::execute_instruction(instruction, vm) } } This leads to two important functions: read_memory and execute_instruction.
Reading the memory is pretty straightforward, at least at this stage:
pub fn read_memory(& mut cocky, address: u16) -> u16 { self.retentivity[address as usize] } Executing the education is about:
- Detecting which instruction a given
u16value is, i.east., what's the OpCode? - Matching it against all possible OpCodes
- Running the matching OpCode and extracting the operands from the whole education.
The first two parts are pretty simple:
pub fn execute_instruction(instr: u16, vm: & mut VM) { // Excerpt OpCode from the instruction permit op_code = get_op_code(&instr); // Match OpCode and execute instruction lucifer op_code { Some(OpCode::ADD) => add(instr, vm), Some(OpCode::AND) => and(instr, vm), Some(OpCode::NOT) => not(instr, vm), Some(OpCode::BR) => br(instr, vm), Some(OpCode::JMP) => jmp(instr, vm), Some(OpCode::JSR) => jsr(instr, vm), Some(OpCode::LD) => ld(instr, vm), Some(OpCode::LDI) => ldi(instr, vm), Some(OpCode::LDR) => ldr(instr, vm), Some(OpCode::LEA) => lea(instr, vm), Some(OpCode::ST) => st(instr, vm), Some(OpCode::STI) => sti(instr, vm), Some(OpCode::STR) => str(instr, vm), Some(OpCode::TRAP) => trap(instr, vm), _ => {} } } Notation that each OpCode is incredibly well specified in the original spec docs. Our goal is to implement ane by i!
Extracting and handling our first instruction
Okay, how do we know which instruction is a u16 piece of data?
Let'due south consider the first assembly didactics in our hello world plan: LEA, information technology has, equally expected, 16 bits: 
And we want to take an education, grab the starting time four bits (the OpCode) and ostend it'due south an LEA OpCode: 1110. Given the first education, if we print its decimal and binary representation, we get:
println!("instruction: {:?}\north", teaching); println!("educational activity in binary: {:#b}\n", educational activity); Output:
instruction: 57346 instruction in binary: 0b1110000000000010 Okay, then the OpCode is correct in that location: 1110, how do we excerpt it from the whole instruction?
A common technique is to use bit shifting (>> or <<) to turn 1110000000000010 into 0000000000001110, which is the OpCode representation with the total leading zeroes!
That ways we tin right-shift the original number 12 times past using >>. Proceed, count, and y'all will run across that moving each element in that binary representation from its original position (1110000000000010) to the right, 12 times, will atomic number 82 to 0000000000001110.
So if we do this:
println!("pedagogy: {:?}\due north", didactics); println!("didactics in binary: {:#b}\n", education); println!("instruction >> 12: {:?}\n", pedagogy >> 12); println!("educational activity >> 12: {:#b}\n", didactics >> 12); Nosotros get:
instruction: 57346 instruction in binary: 0b1110000000000010 instruction >> 12: 14 didactics >> 12: 0b1110 Now, hither are all the OpCodes from the specs: 
We now have to match the extracted 4 first $.25 of an education against the list of all OpCodes:
pub enum OpCode { BR = 0, // branch Add together, // add LD, // load JSR, // jump register AND, // bitwise and LDR, // load register STR, // store register RTI, // unused NOT, // bitwise not LDI, // load indirect STI, // store indirect JMP, // jump RES, // reserved (unused) LEA, // load constructive address TRAP, // execute trap } pub fn get_op_code(instruction: & u16) -> Pick<OpCode> { friction match instruction >> 12 { 0 => Some(OpCode::BR), 1 => Some(OpCode::ADD), 2 => Some(OpCode::LD), 3 => Some(OpCode::ST), four => Some(OpCode::JSR), 5 => Some(OpCode::AND), vi => Some(OpCode::LDR), vii => Some(OpCode::STR), eight => Some(OpCode::RTI), 9 => Some(OpCode::Non), x => Some(OpCode::LDI), 11 => Some(OpCode::STI), 12 => Some(OpCode::JMP), xiii => Some(OpCode::RES), 14 => Some(OpCode::LEA), 15 => Some(OpCode::TRAP), _ => None, } } Detect that we're matching it against the decimal representation of the instruction that'south coming as u16.
Now our execute_instruction makes a lot more sense:
pub fn execute_instruction(instr: u16, vm: & mut VM) { // Extract OpCode from the educational activity allow op_code = get_op_code(&instr); // Lucifer OpCode and execute education match op_code { Some(OpCode::ADD) => add(instr, vm), Some(OpCode::AND) => and(instr, vm), Some(OpCode::Non) => not(instr, vm), Some(OpCode::BR) => br(instr, vm), Some(OpCode::JMP) => jmp(instr, vm), Some(OpCode::JSR) => jsr(instr, vm), Some(OpCode::LD) => ld(instr, vm), Some(OpCode::LDI) => ldi(instr, vm), Some(OpCode::LDR) => ldr(instr, vm), Some(OpCode::LEA) => lea(instr, vm), Some(OpCode::ST) => st(instr, vm), Some(OpCode::STI) => sti(instr, vm), Some(OpCode::STR) => str(instr, vm), Some(OpCode::TRAP) => trap(instr, vm), _ => {} } } And if we impress the op_code for each didactics coming from the hello world plan, we go:
op_code: Some(LEA) op_code: Some(TRAP) op_code: Some(TRAP) Now let's keep the implementation and implement only the necessary to run the hello globe program: Some(OpCode::LEA) => lea(instr, vm),
LEA stands for Load Constructive Address. Equally we've seen earlier, the first 4 $.25 are the OpCode identification (1110) 
The other two are the Direct Annals (DR) and the Programme Counter (PC) offset.
The commencement instruction is doing the following:
And then, finer, nosotros're loading an address into a register. In this case, nosotros're loading the cord HELLO_STR into the register R0 by loading the address where the HELLO_STR lives.
From the original specs:
An address is computed by sign-extending bits [8:0] to sixteen bits and calculation this value to the incremented PC. This accost is loaded into DR. The condition codes are set, based on whether the value loaded is negative, nothing, or positive.
And then the footnote:
The LEA education does non read memory to obtain the information to load into DR. The address itself is loaded into DR.
So, for the LEA instruction, hither's what the lawmaking needs to practice.
Outset, get the DR portion of the instruction:
permit dr = (education >> ix) & 0x7; This is a play a joke on to get the destination register portion of the instruction.
Let's intermission this downward. The educational activity that nosotros've received at LEA R0, HELLO_STR is 0b1110_000_000000010.
From left to right: 1110 is the OpCode, 000 is the Directly Register (DR), and 000000010 is the PCOffset9.
Then when we shift information technology to the right 9 times, we get:
original instruction: 0b1110_000_000000010 didactics >> 9: 0b0000000001110_000 So nosotros've shifted enough that the last three bits are the directly register in the instruction: 000. The bits shifted "out" of the value sorta "disappear" from the value; in other words, they don't rotate back to the beginning of the value.
Now that we have our "target" $.25 aligned at the end of the value, nosotros apply a mask & 0x7 (0b0000000000000111). This mask is a bitwise AND against the instruction that nosotros shifted.
And the effect is:
educational activity >> 9 & 0x7: 0b0000000000000000 So it'southward the annals 0, as expected.
Simply why practice we mask? There are commonly three reasons to apply bitwise masking:
- Bitwise AND to extract a subset of the bits in the value
- Bitwise OR to set a subset of the bits in the value
- Bitwise XOR to toggle a subset of the $.25 in the value
In the AND example, for instance:
Mask: 0000 1111 Value: 0101 0101 ------------------- Result: 0000 0101 The goal of this mask is, from left to right, to clear the first iv bits and continue the final four bits of the value. So the result volition be 0b00000101.
And so in our LEA R0, HELLO_STR case, (pedagogy >> 9) & 0x7 is trying to say: shift it and so that the concluding three bits are the direct register we're looking for, but since the upshot of that instruction >> ix isn't the final straight annals (merely the concluding 3 bits), mask information technology with 0b0000000000000111 and so that nosotros clear everything upwards to the last iii bits, which is what we want. The resulting sixteen bits value volition be exactly the straight annals! How cool is that?! I detect the intricate simplicity behind this technique beautiful.
Sign extension
At present back to the LEA spec:
An address is computed by sign-extending $.25 [8:0] to 16 bits and calculation this value to the incremented PC.
Permit's meet how this sign-extending thing works. Simply put, considering we're operating on 16 $.25, whenever a value has less than 16 bits, we have to extend it to be 16 bits.
The accost nosotros're loading with LEA, bits 8 to 0 (left to correct), clearly isn't 16 $.25 – so we accept to sign-extend it!
For positive numbers, it's like shooting fish in a barrel: add zeroes before the value. This doesn't piece of work for negative numbers, though. Borrowing an example from Justin:
For case, -i in 5 bits is
1 1111. If we simply extended it with 0'due south, this is0000 0000 0001 1111, which is equal to 31
So instead of only filling in zeroes, we must also fill in ones for negative numbers. And so this is how it looks:
// ... let pc_offset = sign_extend(instruction & 0x1ff, 9); // ... fn sign_extend(mut ten: u16, bit_count: u8) -> u16 { if (x >> (bit_count - 1)) & ane != 0 { x |= 0xFFFF << bit_count; } x } More than bitwise tricks! Let's break this down.
We start off with
sign_extend(instruction & 0x1ff, 9); 0x1ff is 111111111, nine consecutive ones. Another mask! Past instruction & 0x1ff, we mean to go on merely the last ix bits of the instruction, which happens to be the PCOffset9, the address we're loading into a register, and the value that we take to sign-extend.
And so hither we're just extracting the PCOffset9 portion from the didactics. We didn't demand to shift things around because PCOffset9 is already correct-aligned.
Now, because it's a 9-bit value, we want to extend it to exist 16. Enters sign_extend function. Let's break it downward. Yous can check the formal definition for sign extension here: https://en.wikipedia.org/wiki/Sign_extension.
The short version is, if information technology's a signed positive number, padding with zeroes will work. Adding zeroes won't preserve the value if information technology's a signed negative number, only padding with ones will.
The sign_extend is doing that. Information technology takes a bit_count which is the number of bits in the original value; in the case of the LEA command, we're dealing with a ix-bit value that nosotros desire to convert into 16-flake. That'south why we phone call it similar this: let pc_offset = sign_extend(education & 0x1ff, ix);
The if clause if (ten >> (bit_count - 1)) & one != 0 is testing the sign of the value. We're moving ten to the right up until the sign bit (bit_count - i) and applying a single bitmask & one to grab information technology. And then bank check if it's different than zippo; if it is, it's signed as one (negative), significant we accept to pad with ones instead of zeroes. Otherwise, it'southward zero, and nosotros render as is, every bit information technology already is padded with zeroes.
And the part where we pad with ones is:
ten |= 0xFFFF << bit_count; This role is catchy if you're new to bitwise operations. 0xFFFF << bit_count is happening, and so its result is |="d against x. |= means bitwise OR, merely with an assignment step, so x volition be OR'd against the result of 0xFFFF << bit_count and the consequence of that OR will exist assigned to x, replacing the original value.
0xFFFF is 1111111111111111 (sixteen bits). We shift it left bit_count times, i.east., the number of bits in the original value x (in this instance,9). Meaning that, for the original value, we're going to "exit it lonely" and only set up 1's to the balance, all the way to 16 $.25 total. This way, nosotros're going to have 1111111_<original ten value>, and we're done! Super clever trick.
Finer, the LEA command in our hello globe example is loading the address of the beginning of the string onto the register 0.
The concluding part is updating the cond annals based on the value stored in the register that we last operated on, in this example, R0. Which looks similar
vm.registers.update_r_cond_register(dr); // ... pub fn update_r_cond_register(& mut self, r: u16) { if self.get(r) == 0 { self.update(9, ConditionFlag::ZRO equally u16); } else if (self.become(r) >> xv) != 0 { // a one in the left-well-nigh bit indicates negative self.update(ix, ConditionFlag::NEG as u16); } else { self.update(9, ConditionFlag::POS as u16); } } enum ConditionFlag { POS = one << 0, // Positive ZRO = 1 << one, // Zero NEG = i << ii, // Negative } Then, in our how-do-you-do world example, we run a TRAP OpCode. Trap is an OpCode for interacting with IO devices, such as halting, output/input of data, etc. In other words, it's where nosotros go to do a very known thing chosen organisation calls!
The trap spec is unique in comparison to the other OpCodes: 
1111 is the OpCode identifier, but then we have this thing chosen a trap vector, which is 8 bits long. The trap vector holds the identifier to which system call it wants to execute. The spec is super clear about how it works:
trapallows interacting with I/O devices. First R7 is loaded with the incremented PC. (This enables a render to the education physically following the TRAP instruction in the original program afterward the service routine has completed execution.) Then the PC is loaded with the starting accost of the system call specified past trap vector8. The starting address is contained in the retention location whose accost is obtained by zero-extending trap vector8 to 16 bits.
And then below:
Memory locations x0000 through x00FF, 256 in all, are available to contain starting addresses for organization calls specified by their corresponding trap vectors. This region of memory is called the Trap Vector Tabular array.
And beneath that we have the list of all "trap service routines": 
So our trap implementation will expect like something like this
pub fn trap(instruction: u16, vm: & mut VM) { println!("trap instruction: {:#018b}\due north", instruction); match instruction & 0xFF { 0x20 => { // Get character } 0x21 => { // Write out character } 0x22 => { // Puts } 0x23 => { // In, Print a prompt on the screen and read a unmarried character from the keyboard. The character is echoed onto the panel monitor, and its ASCII lawmaking is copied into R0.The high 8 bits of R0 are cleared. } 0x24 => { // Putsp } 0x25 => { // Halt } _ => { procedure::exit(1); } } } And just similar the "college level" OpCodes (LEA, ADD, etc.), we accept to implement one by i.
In our hi world instance, the first trap used is PUTS, to print a string. The didactics binary representation is: 1111000000100010. Then, 00100010 (the last 8 $.25) is the trap vector identifier. 00100010 is 0x22 in hex, which maps to PUTS!
Notice that nosotros do a match instruction & 0xFF { to observe 0x22. Simply like before, we do the & 0xFF (chosen a mask) to capture but the 0xFF worth of $.25 from the pedagogy, 0xFF is 11111111, eight $.25, which is the length of the trap vector we want to capture.
Hither's how the PUTS implementation looks like
x22 => { // Puts permit mut alphabetize = vm.registers.r0; permit mut c = vm.read_memory(index); while c != 0x0000 { print!("{}", (c as u8) as char); index += 1; c = vm.read_memory(alphabetize); } io::stdout().flush().expect("failed to flush"); } We're press char by char, and the address of the beginning of the string lives in the register 0. And so nosotros're walking through it.
Let's visualize this better. If nosotros print teaching:accost pairs at the beginning, when we're loading the howdy globe plan into the VM'southward retention, nosotros see this:
address: 12288 pedagogy: 57346 address: 12289 didactics: 61474 address: 12290 instruction: 61477 address: 12291 instruction: 72 address: 12292 instruction: 101 accost: 12293 education: 108 accost: 12294 teaching: 108 address: 12295 instruction: 111 address: 12296 educational activity: 32 address: 12297 teaching: 87 address: 12298 instruction: 111 address: 12299 instruction: 114 address: 12300 instruction: 108 address: 12301 instruction: 100 address: 12302 instruction: 33 address: 12303 instruction: 0 Notice how at the beginning of the accost 12291 the instructions become slightly different. This is where the characters of the "hello world" string beginning being loaded at. Fun particular: these "instructions" outset to look like utf8 encoding!
Let's further confirm that 12291 is the beginning of the string:
let mut index = vm.registers.r0; println!("index: {:?}\north", alphabetize); Alright! Once we sympathize that, the reading loop becomes trivial:
while c != 0x0000 { print!("{}", (c as u8) as char); alphabetize += 1; c = vm.read_memory(index); } We're only walking through each address until nosotros see a 0x0000. And the print! over there is printing it to the stdout, that's how we run into Hullo, world! coming from the register 0!
And so, the side by side trap instruction we see is HALT, 1111000000100101. Which is the simplest one to implement:
0x25 => { println!("HALT detected"); io::stdout().affluent().expect("Failed to affluent"); procedure::get out(1); } And that'south information technology for the hello world case:
Finished dev [unoptimized + debuginfo] target(southward) in 0.19s Running `target/debug/LC-3 examples/howdy-globe.obj` OK Howdy World!HALT detected Nosotros just managed to run a binary file for the LC-three computer in our VM!
At present, our side by side goal is to implement the rest of the OpCodes, add some more keyboard input control, so we'll be good to run more complex programs. It might sound complicated, but it isn't. Now that we understand the logic and flow behind this VM, its bitwise operation tricks, how we use registers, etc., information technology'south now a matter of reading the spec for each OpCode and implementing its logic, which is unremarkably very straightforward.
Implementing the ADD OpCode
Here's the Add spec:
We take two operation modes for Add, and we can pick which i we're gonna employ by setting the chip [v] of the teaching. Hither's how it's officially described:
If bit [5] is 0, the second source operand is obtained from SR2. If bit [five] is 1, the 2nd source operand is obtained past sign-extending the imm5 field to 16 $.25. In both cases, the second source operand is added to the contents of SR1 and the result stored in DR. The condition codes are prepare, based on whether the result is negative, zip, or positive
In other words, ADD will be adding ii numbers; the showtime comes from a register, the second will come either from a register (SR2) or by direct passing an immediate value to the instruction, like:
Add R2, R3, R4 ; R2←R3+R4, R2 receives the sum of what's in R3 and R4 ADD R2, R3, #vii ; R2←R3+vii, R2 receives the sum of what's in R3 and the num 7 In the firsthand case, it needs to be in 16 $.25 because it's a full value, so we sign-extend information technology. The merchandise-off is that the education only has room for a small number, up to ii^5=32.
Here's how the lawmaking looks like
pub fn add together(educational activity: u16, vm: & mut VM) { allow dr = (educational activity >> 9) & 0x7; // Outset operand let sr1 = (instruction >> 6) & 0x7; // Check if we're in firsthand mode or register mode. let imm_flag = (instruction >> 5) & 0x1; if imm_flag == 1 { let imm5 = sign_extend(instruction & 0x1F, 5); //val is declared as u32 to foreclose from overflow. let val: u32 = imm5 every bit u32 + vm.registers.go(sr1) as u32; //val is declared as u16, so that type arithmatic boot in and number is rounded to get fit into u16. vm.registers.update(dr, val as u16); } else { /* kickoff operand (SR2) */ let sr2 = educational activity & 0x7; permit val: u32 = vm.registers.go(sr1) every bit u32 + vm.registers.get(sr2) as u32; vm.registers.update(dr, val as u16); } vm.registers.update_r_cond_register(dr); } Let'south suspension it down.
let dr = (pedagogy >> 9) & 0x7; This gets the destination address using bitwise operation tricks.
instruction >> 9 will shift the binary from the pedagogy it 9 times to the right. That means the final scrap will be the stop of the DR portion of the didactics. And the bitwise-and (&) 0x7 will catch only the length of 111 out of the instruction, i.e., the concluding iii $.25, which is precisely the length of the DR.
allow sr1 = (teaching >> six) & 0x7; Aforementioned thing as before, merely now we're moving only 6 times because the SR1 annals is later on the directly register (DR).
let imm_flag = (instruction >> 5) & 0x1; Again, aforementioned affair, just the ane bit at position v that represents the operation way.
Then we go on with the operation way logic:
if imm_flag == 1 { permit imm5 = sign_extend(instruction & 0x1F, 5); // This is declared as u32 to prevent from overflow. let val: u32 = imm5 every bit u32 + vm.registers.get(sr1) as u32; // Set the outcome of the sum to the target register vm.registers.update(dr, val as u16); } else { // If not firsthand manner, we need to extract the second register. let sr2 = instruction & 0x7; // Go along equally usual permit val: u32 = vm.registers.become(sr1) every bit u32 + vm.registers.get(sr2) every bit u32; // Prepare the result of the sum to the target register vm.registers.update(dr, val as u16); } If it'south the immediate mode, grab the immediate value by extending it to be 16 bits. Then add together and update the target annals (R0).
If not firsthand style, grab the other annals passed in the instruction and proceed as usual.
And that's information technology! And so nosotros take to update the condition register:
vm.registers.update_r_cond_register(dr); We pass dr here because this is the register containing the issue of the final operation. Remember that the cond register'due south thought is to set up positive/negative/zero based on the upshot of the last operation, which in this case live in dr.
Implementing the LDI OpCode
In uncomplicated terms, the LDI operation is loading the accost of a slice of information onto a register. All the same, it's a bit trickier than that considering it adds another layer of indirection (that'due south why it'south chosen load indirect).
It starts by adding the PC to a PCOffset9 in the pedagogy. This sum is an address to a memory location, and that accost contains some other value which is the accost of the value to load. It sounds tricky, simply the code probably makes it articulate. It looks like this:
pub fn ldi(pedagogy: u16, vm: & mut VM) { // Get the directly register encoded in the instruction (meet `add` fn for more in-depth details) let dr = (instruction >> 9) & 0x7; // Go the PC kickoff and sign extend it to be sixteen bits allow pc_offset = sign_extend(education & 0x1ff, 9); permit first_read = vm.read_memory(vm.registers.pc + pc_offset); let resulting_address = vm.read_memory(first_read); vm.registers.update(dr, resulting_address); vm.registers.update_r_cond_register(dr); } Implementing the AND OpCode
Adept old logical and, only applied to binary values. This one is similar to ADD; it has 2 operation modes: immediate and register. Since you probably already got the hang of it, hither'south the code without much explanation:
pub fn and(didactics: u16, vm: & mut VM) { // Get the direct register encoded in the instruction (run into `add` fn for more in-depth details) permit dr = (instruction >> 9) & 0x7; // As seen in `add` fn, aforementioned tricks. allow sr1 = (instruction >> half dozen) & 0x7; let imm_flag = (educational activity >> 5) & 0x1; if imm_flag == 1 { permit imm5 = sign_extend(pedagogy & 0x1F, 5); // Perform the bitwise and (`&`) and store its value in the DR. vm.registers.update(dr, vm.registers.get(sr1) & imm5); } else { allow sr2 = pedagogy & 0x7; // Perform the bitwise and (`&`) and store its value in the DR. vm.registers .update(dr, vm.registers.go(sr1) & vm.registers.get(sr2)); } vm.registers.update_r_cond_register(dr); } Nothing new here, same sometime tricks, just instead of +ing stuff, we're just bitwise-and'ing information technology.
Implementing the Non OpCode
Another dead elementary OpCode, elementary binary negation. Won't diameter you with the details:
pub fn not(instruction: u16, vm: & mut VM) { let dr = (didactics >> 9) & 0x7; let sr1 = (didactics >> 6) & 0x7; vm.registers.update(dr, !vm.registers.get(sr1)); vm.registers.update_r_cond_register(dr); } Implementing the BR OpCode
Finally, we're using the condition register! Nosotros use a branch (BR) operation to control the flow of a program. At that place are many ways to use it: 
Permit's look at the didactics encoding: 
This ane has some tricks that are worth digging into.
We have 3 bits set here: n for negative, z for zero, and p for positive. If whatsoever of these conditions are true, we'll move the flow of the programme to wherever Characterization is, which is a position stored in the PC register.
In a more concrete case, if the BR pedagogy has 101 for nzp, we're maxim that if the last teaching resulted in a negative number of a positive number, but not nothing, then we trigger the branching, by moving the PC to Characterization.
This brings the states to how we implement the condition flags in our VM:
enum ConditionFlag { POS = 1 << 0, // Positive ZRO = ane << 1, // Zero NEG = ane << 2, // Negative } Simple enough, only why these values set for POS, ZRO, and NEG?
i in binary representation is 0000000000000001, 1 << ii means nosotros're shifting the $.25 twice to the left, and so that one at the end volition finer move to left twice. It ends upward being 0000000000000100, which in decimal representation is iv. Thus, ane << 2 == iv.
So why are nosotros storing 1, 2, four here? Glad you lot asked. In binary, with iii bits only: ane == 001 two == 010 four == 100
And then we're playing with the possible provisional flags settings! Because the condition pedagogy volition be nzp (neg, zero, pos) and merely one can be set at a time, it will either be:
-
001(positive setnz1) -
010(zero set,n1p) -
100(negative set,1zp)
And these three binary values are ane, two, and 4 in decimal!
At present, our branching performance looks like this:
pub fn br(didactics: u16, vm: & mut VM) { // Grab the PCOffset of the didactics and sign extend it // You lot can read more than sign extension inside the `sign_extend` fn. let pc_offset = sign_extend((instruction) & 0x1ff, 9); // Shift ix and catch three bits (& 0x7 is doing that) // You lot tin can read more about this fob inside `lea` fn. allow cond_flag = (didactics >> 9) & 0x7; if cond_flag & vm.registers.cond != 0 { allow val: u32 = vm.registers.pc as u32 + pc_offset as u32; vm.registers.pc = val as u16; } // If the branch isn't taken (no condition met), PC isn't inverse // and PC will just point to the adjacent sequential instruction. } And we do the testing in that location as: f cond_flag & vm.registers.cond != 0 {
We're taking the 001, or 010, or 100 stored in the status annals and &ing it to the 001, or 010, or 100 coming from the instruction; note that the one coming from the instruction can exist 110, 111 or any combination.
For example, if the concluding operation turned positive, we have 001 in the status annals. If the status to trigger the branching is 011 (either positive or zero), and so 001 & 011 volition be 001, which means the branching is enabled, significant nosotros will change the PC past adding the PCOffset to it and moving on. The next instruction executed will be decided by this new PCOffset; this is ordinarily used for while/for loops and if-statements.
Implementing the JMP OpCode
JMP is another flow command performance, like BR, but without conditions. So we're mutating the PC annals no matter what.
The plan unconditionally jumps to the location specified by the content of the base annals in the instruction. Bits [8:vi] identify the base register.
RET is listed as a divide education in the specification since it is a different keyword in assembly. However, it is a particular case of JMP. RET happens whenever R1 is 7.
This is how the encoding looks similar: 
In our implementation, RET and JMP are going to be handled by the same JMP role, as they're basically the same, just dissimilar assembly keywords, and RET is ever when the register is 111 (register 7) instead of an capricious register BaseR..
pub fn jmp(teaching: u16, vm: & mut VM) { // base_reg will either be an arbitrary register or the // register 7 (`111`) which in this // case it would be the `RET` operation. let base_reg = (didactics >> 6) & 0x7; vm.registers.pc = vm.registers.become(base_reg); } Implementing the JSR OpCode
Also known as JumptoSubRoutine. The spec itself for this one is incredibly clear:
Start, the incremented PC is saved in R7. This is the linkage back to the calling routine. Then the PC is loaded with the address of the first instruction of the subroutine, causing an unconditional jump to that address. The address of the subroutine is obtained from the base of operations register (if bit [11] is 0), or the address is computed by sign-extending bits [10:0] and adding this value to the incremented PC (if bit [11] is 1).
The code, then, is pretty straightforward:
pub fn jsr(educational activity: u16, vm: & mut VM) { // Take hold of the base of operations register let base_reg = (instruction >> 6) & 0x7; // 0x7ff == 11111111111 (eleven ones, exactly the length of PCOffset11) // Catch it and extend it to 16 bits. let long_pc_offset = sign_extend(instruction & 0x7ff, 11); // Take hold of the flag chip at [xi] and test it let long_flag = (pedagogy >> 11) & ane; // Salvage the incremented PC in R7 vm.registers.r7 = vm.registers.pc; if long_flag != 0 { // JSR case, the address to jump is computed from PCOffset11 permit val: u32 = vm.registers.pc equally u32 + long_pc_offset as u32; vm.registers.pc = val every bit u16; } else { // JSRR case, address to spring to lives in the base register vm.registers.pc = vm.registers.become(base_reg); } } Implementing the LD OpCode
The standard load performance. Incredibly elementary one! 
We're loading onto a register DR the value stored in a place in retentivity computed using the PCOffset9.
pub fn ld(instruction: u16, vm: & mut VM) { // Get the direct annals encoded in the education (see `add together` fn for more in-depth details) let dr = (instruction >> 9) & 0x7; // Grab the PCOffset and sign extend information technology let pc_offset = sign_extend(instruction & 0x1ff, 9); permit mem: u32 = pc_offset as u32 + vm.registers.pc as u32; // Read the value from the identify where the memory above was computed permit value = vm.read_memory(mem as u16); // Salvage that value to the direct register and update the condition register vm.registers.update(dr, value); vm.registers.update_r_cond_register(dr); } Implementing the LDR OpCode
It stands for Load Base+Offset; it's a specialized version of the LD operation. The only deviation is that instead of only using a base register, nosotros add the base register to an Offset6 (sign-extended to 16 $.25) before loading.
pub fn ldr(instruction: u16, vm: & mut VM) { // Become the direct annals encoded in the instruction (see `add together` fn for more in-depth details) let dr = (didactics >> ix) & 0x7; // Grab the base register let base_reg = (instruction >> vi) & 0x7; // Take hold of the offset6 and sign extend it allow first = sign_extend(instruction & 0x3F, 6); // Compute the memory location to be loaded let val: u32 = vm.registers.get(base_reg) equally u32 + offset equally u32; // Read the value at that memory location let mem_value = vm.read_memory(val as u16).clone(); // Update the annals with the loaded value and update the condition register vm.registers.update(dr, mem_value); vm.registers.update_r_cond_register(dr); } Implementing the ST OpCode
Some other simple functioning: Store. Information technology will store the contents in the register SR in the retentivity location computed by the current PC and the PCOffset9. Every bit usual, the offset will be sign-extended to 16-bit.
The lawmaking for it is equally like shooting fish in a barrel equally the clarification:
pub fn st(educational activity: u16, vm: & mut VM) { // Get the directly register encoded in the didactics (see `add` fn for more in-depth details) let sr = (educational activity >> nine) & 0x7; // Grab the PC beginning and sign extend information technology let pc_offset = sign_extend(pedagogy & 0x1ff, 9); // Add together the current PC to the PC starting time // We're doing these conversions to avoid overflow allow val: u32 = vm.registers.pc as u32 + pc_offset as u32; allow val: u16 = val every bit u16; // Shop the value in the register being passed in the instruction at // the accost computed above vm.write_memory(val as usize, vm.registers.get(sr)); } Implementing the STI OpCode
Store indirect, just like Shop, but with a layer of indirection. The encoding is very similar, though: 
This role of the official spec covers it well IMO:
What is in memory at this address is the address of the location to which the data in SR is stored
It kind of sounds like pointers, right?!
The lawmaking is pretty much the aforementioned equally ST (Store) with one extra pace:
pub fn sti(didactics: u16, vm: & mut VM) { // Get the direct register encoded in the teaching (come across `add` fn for more than in-depth details) let sr = (education >> 9) & 0x7; // Take hold of the PC offset and sign extend it allow pc_offset = sign_extend(didactics & 0x1ff, ix); // Add the current PC to the PC offset // We're doing these conversions to avoid overflow let val: u32 = vm.registers.pc equally u32 + pc_offset every bit u32; let val: u16 = val equally u16; // This is the difference between STI and ST let address = vm.read_memory(val) every bit usize; vm.write_memory(address, vm.registers.get(sr)); } Implementing the STR OpCode
Store base+start. Similar to Load Base+Offset, but shop instead of load. The instruction has a base register and offset, and we add together them together to get the place where we desire to shop the values in the register SR. 
The code is also fairly simple:
pub fn str(educational activity: u16, vm: & mut VM) { // Get the register encoded in the instruction (see `add` fn for more in-depth details) let dr = (educational activity >> 9) & 0x7; // Take hold of the base register allow base_reg = (didactics >> 6) & 0x7; // Grab the outset and sign extend it let beginning = sign_extend(instruction & 0x3F, 6); // Get the value in the base_register and sum it to the offset encoded in the instruction // Note that we're doing some conversions here to prevent overflow. allow val: u32 = vm.registers.become(base_reg) equally u32 + beginning as u32; allow val: u16 = val every bit u16; vm.write_memory(val as usize, vm.registers.go(dr)); } And that's it! We've implemented all the operations from the spec, and we can now run more circuitous programs.
However, we will need to add more IO command stuff to our VM, like handling keyboard input and such. Let's practice that!
Memory-mapped registers
Information technology's mutual to create special registers to collaborate with peripherals, similar a keyboard and mouse. These registers are only accessed by reading and writing from a reserved retentiveness location.
In LC-3, we accept two of those special memory-mapped registers:
pub enum MemoryMappedReg { // Keyboard status: The KBSR indicates whether a key has been pressed Kbsr = 0xFE00, // Keyboard data: The KBDR identifies which fundamental was pressed Kbdr = 0xFE02, } Ane for keyboard status (i.e., is central pressed?) and another for keyboard data (i.due east., which key pressed?). Why non but use getc to get this data? I like Justin Meiners'south explanation about it:
Although you lot tin request keyboard input using
GETC, this blocks execution until input is received.KBSRandKBDRallows you to poll the state of the device and keep execution, so the program can stay responsive while waiting for input.
Okay, then when do we read/write from/to these registers? Simple enough, whenever we're reading the VM's retention, we will perform this check. That means we'll be extending our read_memory role from the beginning, which was:
pub fn read_memory(& mut self, address: u16) -> u16 { self.memory[address as usize] } And it will become this:
pub fn read_memory(& mut self, address: u16) -> u16 { if address == MemoryMappedReg::Kbsr equally u16 { cocky.handle_keyboard(); } self.memory[address every bit usize] } fn handle_keyboard(& mut cocky) { let mut buffer = [0; one]; std::io::stdin().read_exact(& mut buffer).unwrap(); if buffer[0] != 0 { self.write_memory(MemoryMappedReg::Kbsr equally usize, i << xv); self.write_memory(MemoryMappedReg::Kbdr equally usize, buffer[0] as u16); } else { self.write_memory(MemoryMappedReg::Kbsr as usize, 0) } } So, if the address we're reading is the address of the keyboard status annals, nosotros'll enter this "keyboard handling mode," where we'll write the status and the keyboard data to these special registers.
With that done, nosotros can at present even run a game called Rogue in our LC-iii VM: 
The compiled object for the Rogue program is inside examples/ in this projection'due south repository. To run information technology: cargo run -- examples/rogue.obj.
Where to go from hither
We accept a working Virtual Auto for the LC-iii computer, that'southward awesome. We're able to run whatsoever compiled plan that's supposed to run on LC-3 on our VM—This is super powerful!
Nonetheless, nosotros have one trouble: nosotros depend on compiled programs to do stuff with our VM. It would be nice to write LC-3 assembly in plaintext and compile it to the LC-3 architecture. This is something I'd like to work on at some bespeak every bit a continuation of this projection—that and a disassembler, i.e., from the compiled .obj files to plaintext associates.
I might piece of work on that if I have the fourth dimension and do some other write-up that would be a follow-upward to this one.
Source: https://www.rodrigoaraujo.me/posts/lets-build-an-lc-3-virtual-machine/
Posted by: kreidersonters.blogspot.com
0 Response to "How To Initialize A Lc 3 Register To 100"
Post a Comment