bf

erhant · Jul 17, 2023 · 6a61318 · 6a61318
1 parent 208dbe5
commit 6a61318
Show file tree

Hide file tree

Showing 6 changed files with 248 additions and 16 deletions.
diff --git a/README.md b/README.md
@@ -29,18 +29,32 @@ We have the following operations defined in Brainfuck in terms of state changes
 | 45     | `-`   | `m'[p] <== m[p] - 1`              |
 | 46     | `.`   | `out   <== m[p]`                  |
 | 44     | `,`   | `m'[p] <== in`                    |
-| 91     | `[`   | if `m[p] != 0` then `i' <== j[i]` |
-| 93     | `]`   | if `m[p] != 0` then `i' <== j[i]` |
+|        | `[`   | if `m[p] != 0` then `i' <== j[i]` |
+|        | `]`   | if `m[p] != 0` then `i' <== j[i]` |
 
 Number refers to the value returned by `charCodeAt` (in JS) for that character, yielding the ASCII value. We will treat the corresponding field elements for instruction codes.
 
 If not specified otherwise, the following happens during the state transition:
 
 - `p' <== p` data pointer stays the same
-- `i' <== i` instruction pointer is incremented
+- `i' <== i + 1` instruction pointer is incremented
 - `m'[:] <== m[:]` memory blocks stay the same
 
+If an unknown token is received, it is ignored and default behavior state transitions occur.
+
+### Looping
+
+To make looping more snark-friendly, we will replace the `[` and `]` with their respective target position in the code. For example:
+
+```bf
+  0 1 2 3 4 5 6 7 8 # position
+> + + [ + - - ] + . # input
+> + + 6 + - - 2 + . # converted
+```
+
 ## Honorable Mentions
 
 - [Typefuck](https://github.com/susisu/typefuck) is a Brainfuck interpreter using the type-system of Typescript alone.
 - [How Brainfuck Works](https://gist.github.com/roachhd/dce54bec8ba55fb17d3a) is a great Gist about Brainfuck.
+- [Brainfuck in STARK](https://neptune.cash/learn/brainfuck-tutorial/) is a quite nice example of another zkBrainfuck.
+- [Brainfuck in Golang](https://github.com/kgabis/brainfuck-go/blob/master/bf.go) is another implementation of Brainfuck in go.
diff --git a/circuits/brainfuck.circom b/circuits/brainfuck.circom
@@ -0,0 +1,21 @@
+pragma circom 2.1.0;
+
+include "./vm.circom"
+
+// MEM: memory size
+// LEN: code size
+// CLK: number of clock-cycles
+template Brainfuck(MEM, LEN, CLK) {
+  signal input code[LEN];
+
+  component vm = VM(MEM);
+
+  // reset pointers & memory
+  vm.i <== 0;
+  vm.p <== 0;
+
+  // reset memory
+  for (var i = 0; i < M; i++) {
+    vm.m[i] <== 0;
+  }
+}
diff --git a/circuits/utils.circom b/circuits/utils.circom
@@ -0,0 +1,67 @@
+pragma circom 2.1.0;
+
+// Checks if two numbers are equal.
+//
+// Inputs:
+// - `in`: two numbers
+//
+// Outputs:
+// - `out`: 1 if `in[0] == in[1]`, 0 otherwise
+template IsEqual() {
+  signal input in[2];
+  signal output {bool} out;
+
+  out <== IsZero()(in[1] - in[0]);
+}
+
+// Checks if a number is zero.
+//
+// Inputs:
+// - `in`: a number
+//
+// Outputs:
+// - `out`: 1 if `in == 0`, 0 otherwise
+template IsZero() {
+  signal input in;
+  signal output {bool} out;
+
+  signal inv <-- in != 0 ? (1 / in) : 0;
+
+  out <== (-in * inv) + 1;
+  in * out === 0;
+}
+
+// If-else branching.
+//
+// Inputs:
+// - `cond`: a boolean condition
+// - `ifTrue`: signal to be returned if condition is true
+// - `ifFalse`: signal to be returned if condition is false
+//
+// Outputs:
+// - `out`: equals `cond ? ifTrue : ifFalse`
+template IfElse() {
+  signal input {bool} cond;
+  signal input ifTrue;
+  signal input ifFalse;
+  signal output out;
+
+  out <== cond * (ifTrue - ifFalse) + ifFalse;
+}
+
+// Swaps in[0] ~ in[1] if `cond` is true.
+//
+// Inputs:
+// - `cond`: a boolean condition
+// - `in`: two numbers
+//
+// Outputs:
+// - `out`: two numbers either swapped or not
+template Swap() {
+  signal input {bool} cond;
+  signal input in[2];
+  signal output out[2];
+
+  out[0] <== cond * (in[1] - in[0]) + in[0];
+  out[1] <== cond * (in[0] - in[1]) + in[1];
+}
diff --git a/circuits/vm.circom b/circuits/vm.circom
@@ -1,23 +1,17 @@
-pragma circom 2.0.0;
+pragma circom 2.1.0;
 
-template Brainfuck(SIZE) {
-  component vm = VM(SIZE);
-  vm.i <== 0;
-  vm.p <== 0;
-  for (var i = 0; i < SIZE; i++) {
-    vm.m[i] <== 0;
-  }
-}
-
-template VM(SIZE) {
+template VM(MEM) {
   // previous state
   signal input i;
   signal input p;
-  signal input m[SIZE];
+  signal input m[MEM];
 
   // next state
   signal output _i;
   signal output _p;
-  signal output _m[SIZE];
+  signal output _m[MEM];
+
+  // todo...
+
 
 }
diff --git a/vm/go.mod b/vm/go.mod
@@ -0,0 +1,3 @@
+module vm
+
+go 1.20
diff --git a/vm/main.go b/vm/main.go
@@ -0,0 +1,133 @@
+package main
+
+import (
+	"errors"
+	"fmt"
+	"log"
+)
+
+const MEM_SIZE = 126
+const MAX_CLOCKS = 1 << 16
+
+type MEM_TYPE = uint32
+type OP_TYPE = uint32
+
+const (
+	OP_INC_PTR = OP_TYPE(62)
+	OP_DEC_PTR = OP_TYPE(60)
+	OP_INC_MEM = OP_TYPE(43)
+	OP_DEC_MEM = OP_TYPE(45)
+	OP_INPUT   = OP_TYPE(44)
+	OP_OUTPUT  = OP_TYPE(46)
+)
+
+// Compiles the brainfuck program.
+func compile(instructions string) ([]OP_TYPE, error) {
+	code := make([]OP_TYPE, len(instructions))
+	for i, c := range instructions {
+		switch c {
+		case '>':
+			code[i] = OP_INC_PTR
+		case '<':
+			code[i] = OP_DEC_PTR
+		case '+':
+			code[i] = OP_INC_MEM
+		case '-':
+			code[i] = OP_DEC_MEM
+		case '.':
+			code[i] = OP_INPUT
+		case ',':
+			code[i] = OP_OUTPUT
+		case '[':
+			j := i + 1 // j will point to the matching ]
+			for ctr := 1; j < len(instructions); j++ {
+				if instructions[j] == ']' {
+					ctr--
+					if ctr == 0 {
+						break
+					}
+				} else if instructions[j] == '[' {
+					ctr++
+				}
+			}
+
+			if j < len(instructions) {
+				code[i], code[j] = uint32(j)+1, uint32(i)
+			} else {
+				return nil, errors.New("missing ]")
+			}
+		case ']':
+			if instructions[code[i]] != '[' {
+				return nil, errors.New("missing [")
+			}
+		default:
+			// ignore all else
+		}
+	}
+
+	return code, nil
+}
+
+func run(code []OP_TYPE) error {
+	clk := 0                          // clock
+	i := 0                            // instruction pointer
+	p := 0                            // memory pointer
+	mem := make([]MEM_TYPE, MEM_SIZE) // memory
+
+	for ; clk < MAX_CLOCKS && i < len(code); clk++ {
+		// execute code
+		c := code[i]
+		switch c {
+		case OP_INC_PTR:
+			if p == MEM_SIZE-1 {
+				return errors.New("memory pointer overflow")
+			}
+			p++
+			i++
+		case OP_DEC_PTR:
+			if p == 0 {
+				return errors.New("memory pointer underflow")
+			}
+			p--
+			i++
+
+		case OP_INC_MEM:
+			mem[p]++
+			i++
+		case OP_DEC_MEM:
+			mem[p]--
+			i++
+		default:
+			// TODO
+			if mem[p] == 0 {
+
+			} else {
+
+			}
+
+		}
+
+		if i >= len(code) {
+			return errors.New("instruction pointer overflow")
+		}
+
+	}
+
+	if clk == MAX_CLOCKS {
+		return errors.New("maximum clock cycles reached")
+	}
+}
+
+func main() {
+	instructions := "++[-[]++]"
+
+	// compile code
+	feltcode, err := compile(instructions)
+	if err != nil {
+		log.Fatal(err)
+	}
+	fmt.Println(feltcode)
+
+	// execute
+
+}