bf/
bf.rs

+1
+2
+3
+4
+5
+6
+7
+8
+9
+10
+11
+12
+13
+14
+15
+16
+17
+18
+19
+20
+21
+22
+23
+24
+25
+26
+27
+28
+29
+30
+31
+32
+33
+34
+35
+36
+37
+38
+39
+40
+41
+42
+43
+44
+45
+46
+47
+48
+49
+50
+51
+52
+53
+54
+55
+56
+57
+58
+59
+60
+61
+62
+63
+64
+65
+66
+67
+68
+69
+70
+71
+72
+73
+74
+75
+76
+77
+78
+79
+80
+81
+82
+83
+84
+85
+86
+87
+88
+89
+90
+91
+92
+93
+94
+95
+96
+97
+98
+99
+100
+101
+102
+103
+104
+105
+106
+107
+108
+109
+110
+111
+112
+113
+114
+115
+116
+117
+118
+119
+120
+121
+122
+123
+124
+125
+126
+127
+128
+129
+130
+131
+132
+133
+134
+135
+136
+137
+138
+139
+140
+141
+142
+143
+144
+145
+146
+147
+148
+149
+150
+151
+152
+153
+154
+155
+156
+157
+158
+159
+160
+161
+162
+163
+164
+165
+166
+167
+168
+169
+170
+171
+172
+173
+174
+175
+176
+177
+178
+179
+180
+181
+182
+183
+184
+185
+186
+187
+188
+189
+190
+191
+192
+193
+194
+195
+196
+197
+198
+199
+200
+201
+202
+203
+204
+205
+206
+207
+208
+209
+210
+211
+212
+213
+214
+215
+216
+217
+218
+219
+220
+221
+222
+223
+224
+225
+226
+227
+228
+229
+230
+231
+232
+233
+234
+235
+236
+237
+238
+239
+240
+241
+242
+243
+244
+245
+246
+247
+248
+249
+250
+251
+252
+253
+254
+255
+256
+257
+258
+259
+260
+261
+262
+263
+264
+265
+266
+267
+268
+269
+270
+271
+272
+273
+274
+275
+276
+277
+278
+279
+280
+281
+282
+283
+284
+285
+286
+287
+288
+289
+290
+291
+292

//! Brainfuck VM.
+//!
+//! This example implements a simple
+//! [brainfuck](https://en.wikipedia.org/wiki/Brainfuck) interpreter
+//! [`BrainfuckInterp`] and a jit compiler [`BrainfuckJit`].
+//!
+//! Brainfuck is an esoteric programming languge existing of 8 commands.
+//! - `>` increment data pointer.
+//! - `<` decrement data pointer.
+//! - `+` increment data at current data pointer.
+//! - `-` decrement data at current data pointer.
+//! - `.` output data at current data pointer.
+//! - `,` read input and store at current data pointer.
+//! - `[` jump behind matching ']' if data at data pointer is zero.
+//! - `]` jump behind matching '[' if data at data pointer is non-zero.
+
+use std::collections::HashMap;
+use std::io::Write;
+
+use juicebox_asm::insn::*;
+use juicebox_asm::Runtime;
+use juicebox_asm::{Asm, Imm64, Imm8, Label, MemOp, MemOp8, Reg64, Reg8};
+
+struct BrainfuckInterp {
+    pc: usize,
+    imem: Vec<char>,
+    dptr: usize,
+    dmem: [u8; 256],
+    branches: HashMap<usize, usize>,
+}
+
+impl BrainfuckInterp {
+    fn new(prog: &str) -> Result<Self, String> {
+        // Do a first pass over the bf program to filter whitespace and detect invalid tokens.
+        // Additionally validate all conditional branches, and compute their branch target.
+        let (imem, branches) = {
+            // Instruction memory holding the final bf program.
+            let mut imem = Vec::new();
+            // Helper to track index of open brackets.
+            let mut lhs_brackets = Vec::new();
+            // Mapping from branch instruction to branch target.
+            let mut branches = HashMap::new();
+
+            for (idx, token) in prog.chars().filter(|c| !c.is_whitespace()).enumerate() {
+                match token {
+                    '<' | '>' | '+' | '-' | '.' | ',' => { /* ignore valid bf tokens */ }
+                    '[' => lhs_brackets.push(idx),
+                    ']' => {
+                        if let Some(lhs) = lhs_brackets.pop() {
+                            branches.insert(lhs, idx);
+                            branches.insert(idx, lhs);
+                        } else {
+                            return Err(format!("encountered un-balanced brackets, found ']' at index {idx} without matching '['"));
+                        }
+                    }
+                    _ => return Err(format!("invalid bf token '{token}'")),
+                }
+                imem.push(token)
+            }
+
+            if !lhs_brackets.is_empty() {
+                return Err(String::from(
+                    "encountered un-balanced brackets, left-over '[' after parsing bf program",
+                ));
+            }
+
+            (imem, branches)
+        };
+
+        Ok(BrainfuckInterp {
+            pc: 0,
+            imem,
+            dptr: 0,
+            dmem: [0; 256],
+            branches,
+        })
+    }
+}
+
+fn run_interp(prog: &str) {
+    let mut vm = BrainfuckInterp::new(prog).unwrap();
+
+    loop {
+        let insn = match vm.imem.get(vm.pc) {
+            Some(insn) => insn,
+            None => break, // End of bf program.
+        };
+
+        let putchar = |val: u8| {
+            std::io::stdout()
+                .write(&[val])
+                .expect("Failed to write to stdout!");
+        };
+
+        match insn {
+            '>' => {
+                vm.dptr += 1;
+                assert!(vm.dptr < vm.dmem.len());
+            }
+            '<' => {
+                assert!(vm.dptr > 0);
+                vm.dptr -= 1;
+            }
+            '+' => {
+                vm.dmem[vm.dptr] += 1;
+            }
+            '-' => {
+                vm.dmem[vm.dptr] -= 1;
+            }
+            '.' => {
+                putchar(vm.dmem[vm.dptr]);
+            }
+            ',' => {
+                unimplemented!("getchar");
+            }
+            '[' => {
+                if vm.dmem[vm.dptr] == 0 {
+                    vm.pc = *vm.branches.get(&vm.pc).unwrap();
+                }
+            }
+            ']' => {
+                if vm.dmem[vm.dptr] != 0 {
+                    vm.pc = *vm.branches.get(&vm.pc).unwrap();
+                }
+            }
+            _ => unreachable!(),
+        }
+
+        vm.pc += 1;
+    }
+}
+
+// -- BRAINFUCK JIT --------------------------------------------------------------
+
+#[cfg(not(any(target_arch = "x86_64", target_os = "linux")))]
+compile_error!("Only supported on x86_64 with SystemV abi");
+
+struct BrainfuckJit {
+    imem: Vec<char>,
+    dmem: [u8; 256],
+}
+
+impl BrainfuckJit {
+    fn new(prog: &str) -> Result<Self, String> {
+        // Do a first pass over the bf program to filter whitespace and detect invalid tokens.
+        let imem = prog
+            .chars()
+            .filter(|c| !c.is_whitespace())
+            .map(|c| match c {
+                '<' | '>' | '+' | '-' | '.' | ',' | '[' | ']' => Ok(c),
+                _ => Err(format!("invalid bf token '{c}'")),
+            })
+            .collect::<Result<Vec<char>, String>>()?;
+
+        Ok(BrainfuckJit {
+            imem,
+            dmem: [0; 256],
+        })
+    }
+}
+
+extern "C" fn putchar(c: u8) {
+    std::io::stdout()
+        .write(&[c])
+        .expect("Failed to write to stdout!");
+}
+
+fn run_jit(prog: &str) {
+    let mut vm = BrainfuckJit::new(prog).unwrap();
+
+    // Use callee saved registers to hold vm state, such that we don't
+    // need to save any state before calling out to putchar.
+    let dmem_base = Reg64::rbx;
+    let dmem_idx = Reg64::r12;
+
+    let mut asm = Asm::new();
+    // Move data memory pointer (argument on jit entry) into correct
+    // register.
+    asm.mov(dmem_base, Reg64::rdi);
+    // Clear data memory index.
+    asm.xor(dmem_idx, dmem_idx);
+
+    // A stack of label pairs, used to link up forward and backward
+    // jumps for a given '[]' pair.
+    let mut label_stack = Vec::new();
+
+    // Generate code for each instruction in the bf program.
+    for insn in vm.imem {
+        match insn {
+            '>' => {
+                // TODO: generate runtime bounds check.
+                asm.inc(dmem_idx);
+            }
+            '<' => {
+                // TODO: generate runtime bounds check.
+                asm.dec(dmem_idx);
+            }
+            '+' => {
+                asm.inc(MemOp8::from(MemOp::IndirectBaseIndex(dmem_base, dmem_idx)));
+            }
+            '-' => {
+                asm.dec(MemOp8::from(MemOp::IndirectBaseIndex(dmem_base, dmem_idx)));
+            }
+            '.' => {
+                // Load data memory from active cell into di register,
+                // which is the first argument register according to
+                // the SystemV abi, then call into putchar. Since we
+                // stored all out vm state in callee saved registers
+                // we don't need to save any registers before the
+                // call.
+                asm.mov(Reg8::dil, MemOp::IndirectBaseIndex(dmem_base, dmem_idx));
+                asm.mov(Reg64::rax, Imm64::from(putchar as usize));
+                asm.call(Reg64::rax);
+            }
+            ',' => {
+                unimplemented!("getchar");
+            }
+            '[' => {
+                // Create new label pair.
+                label_stack.push((Label::new(), Label::new()));
+                // UNWRAP: We just pushed a new entry on the stack.
+                let label_pair = label_stack.last_mut().unwrap();
+
+                // Goto label_pair.0 if data memory at active cell is 0.
+                //   if vm.dmem[vm.dptr] == 0 goto label_pair.0
+                asm.cmp(
+                    MemOp::IndirectBaseIndex(dmem_base, dmem_idx),
+                    Imm8::from(0u8),
+                );
+                asm.jz(&mut label_pair.0);
+
+                // Bind label_pair.1 after the jump instruction, which
+                // will be the branch target for the matching ']'.
+                asm.bind(&mut label_pair.1);
+            }
+            ']' => {
+                let mut label_pair = label_stack
+                    .pop()
+                    .expect("encountered un-balanced brackets, found ']' without matching '['");
+
+                // Goto label_pair.1 if data memory at active cell is
+                // not 0.
+                //   if vm.dmem[vm.dptr] != 0 goto label_pair.1
+                asm.cmp(
+                    MemOp::IndirectBaseIndex(dmem_base, dmem_idx),
+                    Imm8::from(0u8),
+                );
+                asm.jnz(&mut label_pair.1);
+
+                // Bind label_pair.0 after the jump instruction, which
+                // is the branch target for the matching '['.
+                asm.bind(&mut label_pair.0);
+            }
+            _ => unreachable!(),
+        }
+    }
+
+    // Return from bf program.
+    asm.ret();
+
+    if !label_stack.is_empty() {
+        panic!("encountered un-balanced brackets, left-over '[' after jitting bf program")
+    }
+
+    // Execute jitted bf program.
+    let mut rt = Runtime::new();
+    let bf_entry = unsafe { rt.add_code::<extern "C" fn(*mut u8)>(asm.into_code()) };
+    bf_entry(&mut vm.dmem as *mut u8);
+}
+
+fn main() {
+    // https://en.wikipedia.org/wiki/Brainfuck#Adding_two_values
+    //let inp = "++>+++++ [<+>-] ++++++++[<++++++>-]<.";
+    //println!("add-print-7 (wikipedia.org) - interp");
+    //run_interp(inp);
+    //println!("add-print-7 (wikipedia.org) - jit");
+    //run_jit(inp);
+
+    // https://en.wikipedia.org/wiki/Brainfuck#Hello_World!
+    let inp = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.";
+    println!("hello-world (wikipedia.org) - interp");
+    run_interp(inp);
+    println!("hello-world (wikipedia.org) - jit");
+    run_jit(inp);
+
+    // https://programmingwiki.de/Brainfuck
+    let inp = ">+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.";
+    println!("hello-world (programmingwiki.de) - interp");
+    run_interp(inp);
+    println!("hello-world (programmingwiki.de) - jit");
+    run_jit(inp);
+}
+

bf/bf.rs

bf/
bf.rs