6
\$\begingroup\$

About

I'm trying to implement a simple virtual machine. Now it supports only three operations:

  • ADD(reg0, reg1, reg2) -> reg0 = reg1 + reg2
  • LOAD(reg, value) -> reg = value
  • EXIT -> finish process

It has 8 registers and no memory (for now).

Source code

main.rs:

use std::process;

mod opcodes;
mod utils;

const REGISTERS_COUNT: usize = 8;

#[derive(Copy, Clone)]
struct Program<'a> {
    code: &'a Vec<u8>,
    pos: usize
}

impl<'a> Program<'a> {
    pub fn new(code: &'a Vec<u8>) -> Program<'a> {
        Program { code: code, pos: 0 }
    }

    pub fn fetch(&mut self) -> u8 {
        self.pos += 1;
        if self.pos > self.code.len() {
            process::exit(0);
        }
        return self.code[self.pos - 1];
    }
}

fn eval(mut program: Program, mut registers: [u64; REGISTERS_COUNT]) {
    loop {
        let operator = program.fetch();
        let operands = (
            program.fetch(),

            vec![
                program.fetch(), program.fetch(),
                program.fetch(), program.fetch(),
                program.fetch(), program.fetch(),
                program.fetch(), program.fetch()
            ]
        );

        match operator {
            opcodes::EXIT => {
                process::exit(0);
            }
            opcodes::LOAD => {
                registers[operands.0 as usize] = utils::concat_bytes(&operands.1);
            }
            opcodes::ADD => {
                registers[operands.0 as usize] = registers[utils::concat_bytes(&operands.1[..4]) as usize]
                    + registers[utils::concat_bytes(&operands.1[4..]) as usize];
            }
            _ => {
                println!("error: invalid instruction code");
                process::exit(1);
            }
        }

        println!("{:?}", registers);
    }
}

fn main() {
    let registers: [u64; REGISTERS_COUNT] = [0; REGISTERS_COUNT];
    let code = vec![
        opcodes::LOAD,
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x64,
        opcodes::LOAD,
            0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xC8,
        opcodes::ADD,
            0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
        opcodes::EXIT,
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
    ];
    let program = Program::new(&code);

    eval(program, registers);
}

utils.rs:

pub fn concat_bytes(bytes: &[u8]) -> u64 {
    let mut result = bytes[0] as u64;
    for i in 1..bytes.len() {
        result = (result << 8) | (bytes[i] as u64)
    }
    return result;
}

opcodes.rs:

pub const EXIT: u8 = 0x00;
pub const LOAD: u8 = 0x01;
pub const ADD:  u8 = 0x02;

Output

[100, 0, 0, 0, 0, 0, 0, 0]
[100, 200, 0, 0, 0, 0, 0, 0]
[100, 200, 300, 0, 0, 0, 0, 0]

Disadvantages:

  • No memory
  • Only integers
  • All operators require the same number of arguments (even if they don't need any, like EXIT)

Anything else?

\$\endgroup\$
1

1 Answer 1

5
\$\begingroup\$
  1. Document your instruction format! Looks to be opcode, destination, 8 bytes of input. You need to describe the endianness of the data though. Comments are an OK first step, but data structures with self-describing names are probably even better.

  2. You could avoid entire classes of errors by splitting the program and data memory. This is "Harvard" vs "von Neumann" architecture.

  3. Remove unneeded type specification, such as when defining registers in main.

  4. Can use Default::default to get a reasonable initial state, such as a vector of zeroes. Prevents having to re-type the length again.

  5. Don't use explicit return statements at the end of functions.

  6. What is the expected behavior if you concat a slice with more than 8 bytes? I made this limit to the first 8 bytes.

  7. Become intimately familiar with the methods on Iterator and try to leverage the functional tools it provides, like fold.

  8. Avoid slice indexing whenever possible. It's slightly slower as it performs bounds checks.

  9. concat is a bit odd of a name. I feel that pack is more typical for this operation.

  10. Your opcode is crying out to be an enum. This also happens to be a great place to hang behavior, such as converting it to/from an integer.

  11. It's a little strange that eval accepts the program and registers by value. Maybe you want to create a Machine that owns them, or accept them by mutable reference?

  12. It's strange that Program contains a pointer to where the data is. Typically, the program should be immutable and you'd have a Program Counter (PC) that tracks where you are in the program.

  13. Printing the registers each iteration is a form of logging. If you need such a thing, inject it using a generic. In this case, I just accepted a generic function type, but you could also create your own trait if you wanted more granular places to log.

  14. You should basically never use a &Vec<T>; use &[T] instead.

  15. You should basically never use process:exit inside of any function but main; use proper error handling like Option or Result. I usually start with expect on these types which will panic the program, then thread the errors through once the general structure is in place.

  16. Use slice::get instead of checking the length manually.

  17. Creating a fetch_many method allows better naming, flexibility, and a more efficient implementation.

  18. Create more types! For example, create a RegisterFile and Arguments to offload some of the decision making and implementation details. These types provide naming (which is self-documentation), extra seams for types and assertions, as well as places to put "helper" methods (e.g. pack_bytes). They might show places where you might be misusing sizes (e.g. indexing the register file beyond 8-bit makes no sense).


use std::ops::{Index, IndexMut};
use std::cmp;
use std::error::Error;

enum Opcode {
    Exit = 0x00,
    Load = 0x01,
    Add  = 0x02,
}

impl Opcode {
    fn from_u8(byte: u8) -> Result<Opcode, Box<Error + Send + Sync>> {
        use Opcode::*;

        let opc = match byte {
            x if x == Exit as u8 => Exit,
            x if x == Load as u8 => Load,
            x if x == Add as u8 => Add,
            _ => return Err(From::from("invalid instruction code")),
        };

        Ok(opc)
    }
}

#[derive(Debug)]
struct RegisterFile {
    registers: [u64; 8],
}

// TODO: Consider catching and reporting access to registers outside
// of the register file. The indexing implementation panics the
// program.

impl Index<u8> for RegisterFile {
    type Output = u64;

    fn index(&self, idx: u8) -> &u64 {
        &self.registers[idx as usize]
    }
}

impl IndexMut<u8> for RegisterFile {
    fn index_mut(&mut self, idx: u8) -> &mut u64 {
        &mut self.registers[idx as usize]
    }
}

impl Default for RegisterFile {
    fn default() -> RegisterFile {
        RegisterFile { registers: Default::default() }
    }
}

#[derive(Copy, Clone)]
struct Program<'a> {
    code: &'a [u8],
    pos: usize
}

impl<'a> Program<'a> {
    pub fn new(code: &'a [u8]) -> Program<'a> {
        Program { code: code, pos: 0 }
    }

    fn fetch(&mut self) -> Result<u8, Box<Error + Send + Sync>> {
        let v = try!(self.code.get(self.pos).ok_or("No more code to read"));
        self.pos += 1;
        Ok(*v)
    }

    fn fetch_many(&mut self, n: usize) -> Result<Vec<u8>, Box<Error + Send + Sync>> {
        if self.code.len() < self.pos + n {
            return Err(From::from("No more code to read"));
        }
        let v = &self.code[self.pos..(self.pos + n)];
        self.pos += n;
        Ok(v.to_owned())
    }
}

struct Arguments {
    values: Vec<u8>,
}

impl Arguments {
    // TODO: Did I pick `high` and `low` right?
    pub fn high_u32_8(&self) -> u8 {
        self.values[3]
    }

    pub fn low_u32_8(&self) -> u8 {
        self.values[7]
    }

    pub fn u64(&self) -> u64 {
        Arguments::pack_bytes(&self.values)
    }

    fn pack_bytes(bytes: &[u8]) -> u64 {
        let len = cmp::min(bytes.len(), 8);
        bytes[..len].iter().fold(0, |acc, &byte| acc << 8 | (byte as u64))
    }
}

fn eval<F>(mut program: Program, mut registers: RegisterFile, each_iteration: F) -> Result<(), Box<Error + Send + Sync>>
    where F: Fn(&RegisterFile),
{
    loop {
        let operator = try!(program.fetch());
        let operator = try!(Opcode::from_u8(operator));
        let destination = try!(program.fetch());
        let arguments = try!(program.fetch_many(8));
        let arguments = Arguments { values: arguments };

        match operator {
            Opcode::Exit => return Ok(()),
            Opcode::Load => {
                registers[destination] = arguments.u64();
            }
            Opcode::Add => {
                registers[destination] = registers[arguments.high_u32_8()]
                    + registers[arguments.low_u32_8()];
            }
        }

        each_iteration(&registers);
    }
}

fn main() {
    let registers = Default::default();
    let code = vec![
        Opcode::Load as u8,
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x64,
        Opcode::Load as u8,
            0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xC8,
        Opcode::Add as u8,
            0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
        Opcode::Exit as u8,
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
    ];
    let program = Program::new(&code);

    if let Err(e) = eval(program, registers, |registers| println!("{:?}", registers)) {
        println!("Evaluation failed: {}", e);
        // TODO: Could add process::exit with an error code here
    }
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ "You could avoid entire classes of errors by splitting the program and data memory." → The best interpreted VMs use large register files with instructions that directly address the stack. They then effectively get a fresh register file every call. You still need a separate heap, but normally that's accessed through an allocator rather than explicit access. \$\endgroup\$
    – Veedrac
    May 16, 2016 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.