opt1.zig (3747B) - raw

      1 // opt1: use jump table
      2 
      3 const std = @import("std");
      4 const common = @import("common.zig");
      5 const Allocator = std.mem.Allocator;
      6 const ArrayList = std.ArrayList;
      7 const Program = common.Program;
      8 const JumpTable = ArrayList(usize);
      9 
     10 // comptime known build option, -Dtrace and -Ddebug-opts
     11 const build_options = @import("build_options");
     12 const TRACE = build_options.TRACE;
     13 
     14 pub fn main() anyerror!void {
     15     if (TRACE) {
     16         std.debug.print("Building with TRACE enabled\n", .{});
     17     }
     18 
     19     try common.runInterpreter(common.parseProgram, interpret);
     20 }
     21 
     22 test "og: interpret hello world" {
     23     try common.testHelloWorld(common.parseProgram, interpret);
     24 }
     25 
     26 fn interpret(program: Program, memory: []u8, rdr: anytype, wtr: anytype, alloc: Allocator) !void {
     27     var instruction_count = if (TRACE) std.AutoHashMap(u8, usize).init(alloc);
     28     if (TRACE) {
     29         defer instruction_count.deinit();
     30     }
     31 
     32     const jumptable = try computeJumptable(program, alloc);
     33     defer jumptable.deinit();
     34 
     35     const instructions = program.instructions;
     36     var pc: usize = 0;
     37     var dataptr: usize = 0;
     38 
     39     while (pc < instructions.len) {
     40         const instruction = instructions[pc];
     41 
     42         if (TRACE) {
     43             const entry = try instruction_count.getOrPut(instruction);
     44             if (entry.found_existing) {
     45                 entry.value_ptr.* += 1;
     46             } else {
     47                 entry.value_ptr.* = 1;
     48             }
     49         }
     50 
     51         switch (instruction) {
     52             '>' => dataptr += 1,
     53             '<' => dataptr -= 1,
     54             '+' => memory[dataptr] += 1,
     55             '-' => memory[dataptr] -= 1,
     56             ',' => memory[dataptr] = try rdr.readByte(),
     57             '.' => try wtr.writeByte(memory[dataptr]),
     58             // jumps to next matching ']' if curr_data == 0
     59             '[' => if (memory[dataptr] == 0) {
     60                 pc = jumptable.items[pc];
     61             },
     62             // jumps to previous matching ']' if curr data != 0
     63             ']' => if (memory[dataptr] != 0) {
     64                 pc = jumptable.items[pc];
     65             },
     66             else => {
     67                 return error.unreachableChar;
     68             },
     69         }
     70 
     71         pc += 1;
     72     }
     73 
     74     if (TRACE) {
     75         var kv = instruction_count.iterator();
     76         std.debug.print("\n# Instruction Count\n", .{});
     77         while (kv.next()) |entry| {
     78             std.debug.print("{c}: {d}\n", .{ entry.key_ptr.*, entry.value_ptr.* });
     79         }
     80     }
     81 }
     82 
     83 // jump from idx to jmp[idx]. Any non-jump is mapped jmp[idx] = 0
     84 fn computeJumptable(program: Program, alloc: Allocator) !JumpTable {
     85     var jumptable = try JumpTable.initCapacity(alloc, program.instructions.len);
     86     jumptable.appendNTimesAssumeCapacity(0, program.instructions.len);
     87 
     88     const instructions = program.instructions;
     89     var pc: usize = 0;
     90 
     91     // for each bracket, seek the matching bracket
     92     // and then write both into jumptable
     93     while (pc < instructions.len) {
     94         const instruction = instructions[pc];
     95 
     96         if (instruction == '[') {
     97             var bracket_nesting: usize = 1;
     98             var seek: usize = pc;
     99 
    100             while (bracket_nesting != 0 and seek < instructions.len - 1) {
    101                 seek += 1;
    102 
    103                 const seek_instruction = instructions[seek];
    104                 if (seek_instruction == ']') {
    105                     bracket_nesting -= 1;
    106                 } else if (seek_instruction == '[') {
    107                     bracket_nesting += 1;
    108                 }
    109             }
    110 
    111             if (bracket_nesting == 0) {
    112                 jumptable.items[pc] = seek;
    113                 jumptable.items[seek] = pc;
    114             } else {
    115                 std.debug.print("unmatched ']' at pc={}", .{pc});
    116             }
    117         }
    118         pc += 1;
    119     }
    120 
    121     return jumptable;
    122 }