feat: Impelemnt VM

5 files changed, 299 insertions, 6 deletions

diff --git a/vm/src/main.rs b/vm/src/main.rs
index 7b0216d..bf3655c 100644
--- a/vm/src/main.rs
+++ b/vm/src/main.rs
@@ -7,7 +7,45 @@ mod vmm;
 use vmm::VirtualMachineMonitor;
 
 fn main() {
-    let vm = VirtualMachine::create();
+    /* This is a simple program: calculate 331 + 95 in address 5
+     *
+     * > ADD 331, 95
+     * > JMP 0
+     *
+     * > subleq 331, 0
+     * > subleq 0, 95
+     * > subleq 0, 0
+     * > subleq 0, 0, 0
+     *
+     * > subleq 3, 0
+     * > subleq 0, 4
+     * > subleq 0, 0
+     * > subleq 0, 0, 0
+     */
+    let vm = VirtualMachine::create_with_memory(&vec![
+        /*  0 */ 0,
+        /*  1 */ -1_i64 as u64,
+        /*  2 */ 5,
+        /*  3 */ 331,
+        /*  4 */ 95,
+
+
+        /*  5 */ 3,
+        /*  6 */ 0,
+        /*  7 */ 8,
+
+        /*  8 */ 0,
+        /*  9 */ 4,
+        /* 10 */ 11,
+
+        /* 11 */ 0,
+        /* 12 */ 0,
+        /* 13 */ 14,
+
+        /* 14 */ 0,
+        /* 15 */ 0,
+        /* 16 */ 0,
+    ]);
 
     let _vm_handle = {
         let vm = Arc::clone(&vm);
diff --git a/vm/src/vm/memory.rs b/vm/src/vm/memory.rs
new file mode 100644
index 0000000..e341827
--- /dev/null
+++ b/vm/src/vm/memory.rs
@@ -0,0 +1,149 @@
+use std::{
+    collections::HashMap,
+    ops::Index,
+};
+
+pub(crate) type Word = u64;
+
+// Size of each memory block in words
+// Since words are 64bit, each word corresponds to 4 bytes
+const PAGE_SIZE: usize = 1024;
+
+#[derive(Debug, Default)]
+pub(crate) struct Memory {
+    /// Since we can have a huge number of addresses, we divide the address space
+    /// into pages, and we only create a page when a value is **stored** in it.
+    /// If someone tries to get a value from a nonexistant page, we'll always
+    /// return 0, since default values in pages will be 0.
+    sparse_pages: HashMap<usize, Page>,
+}
+
+impl Memory {
+    pub(crate) fn parse_address(word: Word) -> Vec<usize> {
+        static MASK: usize = 0b111111111111111111111;
+        let value = word as usize;
+
+        // 21bit addressing
+        // One word contains three addresses
+        if value.leading_ones() > 0 {
+            vec![
+                (value & (MASK << 42)) >> 42,
+                (value & (MASK << 21)) >> 21,
+                value & MASK,
+            ]
+        }
+        // 63bit addressing
+        // One word contains one address
+        else {
+            vec![value]
+        }
+    }
+
+    fn new() -> Memory {
+        Memory {
+            sparse_pages: HashMap::from([(0, Default::default())]),
+        }
+    }
+
+    pub(crate) fn new_from(mem: &Vec<Word>) -> Memory {
+        let mut memobj = Memory::new();
+        for (i, chunk) in mem.chunks(PAGE_SIZE).enumerate() {
+            memobj.sparse_pages.insert(i, Page::new(chunk));
+        }
+        memobj
+    }
+
+    pub(crate) fn get_mut(&mut self, ind: usize) -> &mut Word {
+        let page_ind = ind / PAGE_SIZE;
+        // Since we may write data to the page, create it
+        if ! self.sparse_pages.contains_key(&page_ind) {
+            self.sparse_pages.insert(page_ind, Default::default());
+        }
+        self.sparse_pages
+            .get_mut(&page_ind)
+            .unwrap()
+            .get_mut(ind % PAGE_SIZE)
+    }
+}
+
+impl Index<usize> for Memory {
+    type Output = Word;
+
+    fn index(&self, ind: usize) -> &Self::Output {
+        let page_ind = ind / PAGE_SIZE;
+        // Since we're only reading data, if the page isn't allocated, obviously
+        // the values inside it are zeroes
+        if ! self.sparse_pages.contains_key(&page_ind) {
+            &0
+        }
+        else {
+            &self.sparse_pages[&page_ind][ind % PAGE_SIZE]
+        }
+    }
+}
+
+#[derive(Debug)]
+struct Page {
+    container: [Word; PAGE_SIZE],
+}
+
+impl Page {
+    fn new(data: &[Word]) -> Page {
+        let mut page = Page::default();
+        for (i, value) in data.iter().enumerate() {
+            page.container[i] = *value;
+        }
+        page
+    }
+
+    fn get_mut(&mut self, ind: usize) -> &mut Word {
+        &mut self.container[ind]
+    }
+}
+
+impl Default for Page {
+    fn default() -> Self {
+        Page {
+            container: [0; PAGE_SIZE],
+        }
+    }
+}
+
+impl Index<usize> for Page {
+    type Output = Word;
+
+    fn index(&self, ind: usize) -> &Self::Output {
+        &self.container[ind]
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn new_memory_has_first_page() {
+        let mem = Memory::new();
+        assert!(mem.sparse_pages.contains_key(&0));
+    }
+
+    #[test]
+    fn parse_63bit_address_correct() {
+                    /*      #|-- Address                                                 --| */
+        let value: Word = 0b0111100010000010000000000001111100010101001000000000000100001001;
+        let out = Memory::parse_address(value);
+        assert!(out.len() == 1);
+        assert_eq!(out[0], value as usize);
+    }
+
+    #[test]
+    fn parse_21bit_addresses_correct() {
+                    /*      #|-- Address       --||-- Address       --||-- Address       --| */
+        let value: Word = 0b1111100010000010000000000001111100010101001000000000000100001001;
+        let out = Memory::parse_address(value);
+        assert!(out.len() == 3);
+        assert_eq!(out[0], 0b111100010000010000000, "First address is incorrect");
+        assert_eq!(out[1], 0b000001111100010101001, "Second address is incorrect");
+        assert_eq!(out[2], 0b000000000000100001001, "Third address is incorrect");
+    }
+}
diff --git a/vm/src/vm/mod.rs b/vm/src/vm/mod.rs
index 23e443d..bf83391 100644
--- a/vm/src/vm/mod.rs
+++ b/vm/src/vm/mod.rs
@@ -1,17 +1,23 @@
+mod primitive;
+mod memory;
+
 use std::{
     sync::{ Arc, Mutex },
     thread,
     time
 };
 
-mod primitive;
 use primitive::PrimitiveVirtualMachine;
+use memory::Word;
 
 pub(crate) type VirtualMachine = Arc<Mutex<PrimitiveVirtualMachine>>;
 
 pub(crate) trait VirtualMachineInterface {
     fn create() -> VirtualMachine;
+    fn create_with_memory(mem: &Vec<Word>) -> VirtualMachine;
+
     fn start(&self);
+    fn get_word(&self, index: usize) -> Word;
 }
 
 impl VirtualMachineInterface for VirtualMachine {
@@ -19,6 +25,10 @@ impl VirtualMachineInterface for VirtualMachine {
         Arc::new(Mutex::new(PrimitiveVirtualMachine::new()))
     }
 
+    fn create_with_memory(mem: &Vec<Word>) -> VirtualMachine {
+        Arc::new(Mutex::new(PrimitiveVirtualMachine::new_with_memory(mem)))
+    }
+
     fn start(&self) {
         let tick_gap = {
             let vm = (*self).lock().unwrap();
@@ -28,9 +38,17 @@ impl VirtualMachineInterface for VirtualMachine {
         loop {
             {
                 let mut vm = (*self).lock().unwrap();
-                vm.x += 1;
+                vm.step();
+                if vm.is_halted() {
+                    break;
+                }
             }
             thread::sleep(time::Duration::from_millis(tick_gap));
         }
     }
+
+    fn get_word(&self, index: usize) -> Word {
+        let vm = (*self).lock().unwrap();
+        vm.get_word(index)
+    }
 }
diff --git a/vm/src/vm/primitive.rs b/vm/src/vm/primitive.rs
index 42427ca..c748a1b 100644
--- a/vm/src/vm/primitive.rs
+++ b/vm/src/vm/primitive.rs
@@ -1,13 +1,98 @@
+use crate::vm::memory::{ Memory, Word };
+
+// Special addrs
+mod spa {
+    pub(crate) const PROGRAM_COUNTER: usize = 2;
+}
+
+#[derive(Debug, PartialEq, Eq)]
+pub(crate) enum VirtualMachineStatus {
+    Halt,
+    Continue,
+}
+
+#[derive(Debug, Default)]
 pub struct PrimitiveVirtualMachine {
     pub(crate) tick_gap: u64,
-    pub(crate) x: u32,
+    pub(crate) mem: Memory,
+    halted: bool,
 }
 
 impl PrimitiveVirtualMachine {
     pub fn new() -> PrimitiveVirtualMachine {
         PrimitiveVirtualMachine {
             tick_gap: 100,
-            x: 0,
+            halted: false,
+            ..Default::default()
+        }
+    }
+
+    pub fn new_with_memory(mem: &Vec<Word>) -> PrimitiveVirtualMachine {
+        PrimitiveVirtualMachine {
+            tick_gap: 100,
+            halted: false,
+            mem: Memory::new_from(mem),
+        }
+    }
+
+    pub fn step(&mut self) -> VirtualMachineStatus {
+        let mut addrs = Memory::parse_address(*self.current_word());
+        if addrs.len() == 1 {
+            self.increment_pc();
+            addrs.extend(
+                Memory::parse_address(*self.current_word())
+            );
+
+            self.increment_pc();
+            addrs.extend(
+                Memory::parse_address(*self.current_word())
+            );
+        }
+
+        let a = self.mem[addrs[0]];
+        let b = self.mem.get_mut(addrs[1]);
+        let c = addrs[2] as u64;
+
+        // SUBLEQ
+        *b = b.overflowing_sub(a).0;
+        if *b == 0 || b.leading_ones() > 0 {
+            *self.pc_mut() = c;
         }
+        else {
+            self.increment_pc();
+        }
+
+
+        if *self.pc() == 0 {
+            self.halted = true;
+            VirtualMachineStatus::Halt
+        }
+        else {
+            VirtualMachineStatus::Continue
+        }
+    }
+
+    pub fn is_halted(&self) -> bool {
+        self.halted
+    }
+
+    pub fn get_word(&self, index: usize) -> Word {
+        self.mem[index]
+    }
+
+    fn current_word(&self) -> &Word {
+        &self.mem[*self.pc() as usize]
+    }
+
+    fn increment_pc(&mut self) {
+        *self.pc_mut() += 1;
+    }
+
+    fn pc(&self) -> &Word {
+        &self.mem[spa::PROGRAM_COUNTER]
+    }
+
+    fn pc_mut(&mut self) -> &mut Word {
+        self.mem.get_mut(spa::PROGRAM_COUNTER)
     }
 }
diff --git a/vm/src/vmm/mod.rs b/vm/src/vmm/mod.rs
index 0e7cfbc..f2f148c 100644
--- a/vm/src/vmm/mod.rs
+++ b/vm/src/vmm/mod.rs
@@ -20,7 +20,10 @@ impl VirtualMachineMonitor {
         loop {
             {
                 let vm = (*vm).lock().unwrap();
-                println!("{}", vm.x);
+                if vm.is_halted() {
+                    print!("HALTED: ");
+                }
+                println!("{}", vm.get_word(4));
             }
             thread::sleep(time::Duration::from_millis(self.refresh_rate));
         }