commit afc096e93c59690b90ddb4dc6b3bdeb6f4e7e31f
Author: david cochran <about.trout@gmail.com>
Date: Sun, 8 Jan 2023 21:38:54 +0000
initial commit
Diffstat:
| A | README.md | | | 3 | +++ |
| A | gbfy.go | | | 128 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | gbfy_test.go | | | 80 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | go.mod | | | 5 | +++++ |
| A | go.sum | | | 2 | ++ |
5 files changed, 218 insertions(+), 0 deletions(-)
diff --git a/README.md b/README.md
@@ -0,0 +1,3 @@
+# `gbfy`
+
+A [Brainfuck](https://en.wikipedia.org/wiki/Brainfuck) interpreter in Golang.
diff --git a/gbfy.go b/gbfy.go
@@ -0,0 +1,128 @@
+package gbfy
+
+import (
+ "bytes"
+ "errors"
+ "fmt"
+)
+
+// Brainfuck is the interpreter state.
+type Brainfuck struct {
+ cells [3e4]byte // cells/tape
+ cmds []byte // program being executed
+ d, i int // data and instruction pointers
+ in, out *bytes.Buffer // input and output buffers
+}
+
+// New constructs a new Brainfuck interpreter with the given
+// program and input buffer.
+func New(program string, input []byte) *Brainfuck {
+ return &Brainfuck{
+ cmds: []byte(program),
+ in: bytes.NewBuffer(input),
+ out: new(bytes.Buffer),
+ }
+}
+
+// Run the program loaded into the interpreter.
+func (bf *Brainfuck) Run() ([]byte, error) {
+ for bf.i < len(bf.cmds) {
+ if err := bf.eval(bf.cmds[bf.i]); err != nil {
+ return nil, fmt.Errorf("Run failed with error: %v", err)
+ }
+ bf.i++
+ }
+ return bf.out.Bytes(), nil
+}
+
+// eval evaluates a single Brainfuck command.
+func (bf *Brainfuck) eval(cmd byte) error {
+ switch cmd {
+ case '>':
+ // Increment data pointer.
+ bf.d++
+ if bf.d >= len(bf.cells) {
+ bf.d -= len(bf.cells)
+ }
+ case '<':
+ // Decrement data pointer.
+ bf.d--
+ if bf.d < 0 {
+ bf.d += len(bf.cells)
+ }
+ case '+':
+ // Increment value at current cell.
+ bf.cells[bf.d]++
+ case '-':
+ // Decrement value at current cell.
+ bf.cells[bf.d]--
+ case '.':
+ // Write current cell's value to output buffer.
+ bf.out.WriteByte(bf.cells[bf.d])
+ case ',':
+ // Read value from input and store in current cell.
+ if b, err := bf.in.ReadByte(); err != nil {
+ return errors.New("Program expects more input!")
+ } else {
+ bf.cells[bf.d] = b
+ }
+ case '[':
+ // Loop start. Continue through loop body if current cell
+ // is non-zero, otehrwise jump to matching ].
+ if bf.cells[bf.d] == 0 {
+ idx, err := findMatchingClose(bf.cmds, bf.i)
+ if err != nil {
+ return fmt.Errorf("Invalid program! %v", err)
+ }
+ bf.i = idx
+ }
+ case ']':
+ // Loop end. Jump to matching [ if current cell is non-zero.
+ if bf.cells[bf.d] != 0 {
+ idx, err := findMatchingOpen(bf.cmds, bf.i)
+ if err != nil {
+ return fmt.Errorf("Invalid program! %v", err)
+ }
+ bf.i = idx
+ }
+ default:
+ // TODO: Consider stripping non-brainfuck characters in pre-processing.
+ // Technically they are valid in BF programs and should be treated as comments.
+ return fmt.Errorf("Invalid program! Unknown command %q", cmd)
+ }
+ return nil
+}
+
+func findMatchingClose(cmds []byte, i int) (int, error) {
+ var opens int
+ for i < len(cmds) {
+ switch cmds[i] {
+ case '[':
+ opens++
+ case ']':
+ if opens == 0 {
+ return i, nil
+ }
+ opens--
+ }
+ i++
+ }
+ return 0, fmt.Errorf("Missing matching ] for [ at %d", i)
+}
+
+func findMatchingOpen(cmds []byte, i int) (int, error) {
+ var closes int
+ for i >= 0 {
+ switch cmds[i] {
+ case '[':
+ if closes == 0 {
+ return i, nil
+ }
+ closes--
+ case ']':
+ closes++
+ }
+ i--
+ }
+ return 0, fmt.Errorf("Missing matching [ for ] at %d", i)
+}
diff --git a/gbfy_test.go b/gbfy_test.go
@@ -0,0 +1,80 @@
+package gbfy
+
+import (
+ "fmt"
+ "testing"
+
+ "github.com/google/go-cmp/cmp"
+)
+
+func TestEval(t *testing.T) {
+ tests := []struct {
+ // Command to evaluate.
+ cmd byte
+ // Expected value of Data pointer.
+ d int
+ // Expected values of *specific* cells; mapping between cell
+ // index and value expected there. Since the cell region is
+ // large (3e4) and sparse (0 by default) only specific cells
+ // are checked.
+ cells map[int]byte
+ // Expected output data.
+ out []byte
+ }{
+ // Check < and > move data pointer around circular cell region.
+ {'<', 29999, nil, nil},
+ {'>', 0, nil, nil},
+ // Check that + and - modify cell values.
+ {'+', 0, map[int]byte{0: 1}, nil},
+ {'-', 0, map[int]byte{0: 0}, nil},
+ // Check that , and . read input and write output bytes.
+ // NB: output is inspected at the very end since the interpreter
+ // uses bytes.Buffer.
+ {',', 0, map[int]byte{0: 4}, nil},
+ {'>', 1, map[int]byte{0: 4}, nil},
+ {',', 1, map[int]byte{0: 4, 1: 8}, nil},
+ {',', 1, map[int]byte{0: 4, 1: 15}, nil},
+ {'>', 2, map[int]byte{0: 4, 1: 15}, nil},
+ {',', 2, map[int]byte{0: 4, 1: 15, 2: 16}, nil},
+ {'.', 2, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16}},
+ {'<', 1, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16}},
+ {'.', 1, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15}},
+ {'<', 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15}},
+ {'.', 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
+ // Hmm, we can't really test [ and ] with eval ...
+ }
+
+ bf := New("", []byte{4, 8, 15, 16, 23, 41})
+ if err := checkInterpreter(bf, 0, 0, nil, nil); err != nil {
+ t.Fatalf("[0] Unexpected interpreter state: %v", err)
+ }
+
+ for i, test := range tests {
+ if err := bf.eval(test.cmd); err != nil {
+ t.Fatalf("[%d] Eval(%q) failed with error: %v", i, test.cmd, err)
+ }
+ // Note since we called `eval` ourselves rather than `Run`, the instruction
+ // pointer is not being used, i.e. is always zero. It's tested separately below.
+ if err := checkInterpreter(bf, 0, test.d, test.cells, test.out); err != nil {
+ t.Errorf("[%d] Unexpected interpreter state: %v", i, err)
+ }
+ }
+}
+
+func checkInterpreter(bf *Brainfuck, i, d int, cells map[int]byte, out []byte) error {
+ if bf.i != i {
+ return fmt.Errorf("instruction pointer; got %d, want %d", bf.i, i)
+ }
+ if bf.d != d {
+ return fmt.Errorf("data pointer; got %d, want %d", bf.d, d)
+ }
+ for idx, got := range bf.cells {
+ if want := cells[idx]; got != want {
+ return fmt.Errorf("cell value at index %d; got %b, want %b", idx, got, want)
+ }
+ }
+ if diff := cmp.Diff(out, bf.out.Bytes()); diff != "" {
+ return fmt.Errorf("output diff (-want +got): %s", diff)
+ }
+ return nil
+}
diff --git a/go.mod b/go.mod
@@ -0,0 +1,5 @@
+module github.com/abtrout/gbfy
+
+go 1.19
+
+require github.com/google/go-cmp v0.5.9
diff --git a/go.sum b/go.sum
@@ -0,0 +1,2 @@
+github.com/google/go-cmp v0.5.9 h1:O2Tfq5qg4qc4AmwVlvv0oLiVAGB7enBSJ2x2DqQFi38=
+github.com/google/go-cmp v0.5.9/go.mod h1:17dUlkBOakJ0+DkrSSNjCkIjxS6bF9zb3elmeNGIjoY=
