feat: initial commit of brainf interpreter

2 files changed, 306 insertions, 0 deletions

diff --git a/test_programs/hello_world.bf b/test_programs/hello_world.bf
new file mode 100644
index 0000000..1b8ceb3
--- /dev/null
+++ b/test_programs/hello_world.bf
@@ -0,0 +1,43 @@
+[ This program prints "Hello World!" and a newline to the screen, its
+  length is 106 active command characters. [It is not the shortest.]
+
+  This loop is an "initial comment loop", a simple way of adding a comment
+  to a BF program such that you don't have to worry about any command
+  characters. Any ".", ",", "+", "-", "<" and ">" characters are simply
+  ignored, the "[" and "]" characters just have to be balanced. This
+  loop and the commands it contains are ignored because the current cell
+  defaults to a value of 0; the 0 value causes this loop to be skipped.
+]
+++++++++               Set Cell #0 to 8
+[
+    >++++               Add 4 to Cell #1; this will always set Cell #1 to 4
+    [                   as the cell will be cleared by the loop
+        >++             Add 2 to Cell #2
+        >+++            Add 3 to Cell #3
+        >+++            Add 3 to Cell #4
+        >+              Add 1 to Cell #5
+        <<<<-           Decrement the loop counter in Cell #1
+    ]                   Loop until Cell #1 is zero; number of iterations is 4
+    >+                  Add 1 to Cell #2
+    >+                  Add 1 to Cell #3
+    >-                  Subtract 1 from Cell #4
+    >>+                 Add 1 to Cell #6
+    [<]                 Move back to the first zero cell you find; this will
+                        be Cell #1 which was cleared by the previous loop
+    <-                  Decrement the loop Counter in Cell #0
+]                       Loop until Cell #0 is zero; number of iterations is 8
+
+The result of this is:
+Cell no :   0   1   2   3   4   5   6
+Contents:   0   0  72 104  88  32   8
+Pointer :   ^
+
+>>.                     Cell #2 has value 72 which is 'H'
+>---.                   Subtract 3 from Cell #3 to get 101 which is 'e'
++++++++..+++.           Likewise for 'llo' from Cell #3
+>>.                     Cell #5 is 32 for the space
+<-.                     Subtract 1 from Cell #4 for 87 to give a 'W'
+<.                      Cell #3 was set to 'o' from the end of 'Hello'
++++.------.--------.    Cell #3 for 'rl' and 'd'
+>>+.                    Add 1 to Cell #5 gives us an exclamation point
+>++.                    And finally a newline from Cell #6
\ No newline at end of file
diff --git a/test_programs/hello_world_from_hell.bf b/test_programs/hello_world_from_hell.bf
new file mode 100644
index 0000000..64c3645
--- /dev/null
+++ b/test_programs/hello_world_from_hell.bf
@@ -0,0 +1,263 @@
+[
+    This routine is a demonstration of checking for the three cell sizes
+    that are normal for Brainfuck. The demo code also checks for bugs
+    that have been noted in various interpreters and compilers.
+
+    It should print one of three slight variations of "Hello world" followed
+    by an exclamation point then the maximum cell value (if it's less than a
+    few thousand) and a newline.
+
+    If the interpreter is broken in some way it can print a lot of other
+    different strings and frequently causes the interpreter to crash.
+
+    It does work correctly with 'bignum' cells.
+]
++>>
+
+	This code runs at pointer offset two and unknown bit width; don't
+	assume you have more that eight bits
+
+	======= DEMO CODE =======
+	First just print "Hello"
+
+	Notice that I reset the cells despite knowing that they are zero
+	this is a test for proper functioning of the ability to skip over
+	a loop that's never executed but isn't actually a comment loop
+
+	Secondly there's a NOP movement between the two 'l' characters
+
+	Also there's some commented out code afterwards
+
+	>[-]<[-]++++++++[->+++++++++<]>.----[--<+++>]<-.+++++++.><.+++.
+	[-][[-]>[-]+++++++++[<+++++>-]<+...--------------.>++++++++++[<+
+	++++>-]<.+++.-------.>+++++++++[<----->-]<.-.>++++++++[<+++++++>
+	-]<++.-----------.--.-----------.+++++++.----.++++++++++++++.>++
+	++++++++[<----->-]<..[-]++++++++++.[-]+++++++[.,]-]
+
+	===== END DEMO CODE =====
+<<-
+
+Calculate the value 256 and test if it's zero
+If the interpreter errors on overflow this is where it'll happen
+++++++++[>++++++++<-]>[<++++>-]
++<[>-<
+Multiply by 256 again to get 65536
+[>++++<-]>[<++++++++>-]<[>++++++++<-]
++>[>
+	Cells should be 32bits at this point
+
+	The pointer is at cell two and you can continue your code confident
+	that there are big cells
+
+	======= DEMO CODE =======
+	This code rechecks that the test cells are in fact nonzero
+	If the compiler notices the above is constant but doesn't
+	properly wrap the values this will generate an incorrect
+	string
+
+	An optimisation barrier; unbalanced loops aren't easy
+	>+[<]>-<
+
+	Print a message
+	++>[-]++++++[<+++++++>-]<.------------.[-]
+	<[>+<[-]]>
+	++++++++>[-]++++++++++[<+++++++++++>-]<.--------.+++.------.
+	--------.[-]
+
+	===== END DEMO CODE =====
+
+<[-]<[-]>] <[>>
+	Cells should be 16bits at this point
+
+	The pointer is at cell two and you can continue your code confident
+	that there are medium sized cells; you can use all the cells on the
+	tape but it is recommended that you leave the first two alone
+
+	If you need 32bit cells you'll have to use a BF doubler
+
+	======= DEMO CODE =======
+	Space
+	++>[-]+++++[<++++++>-]<.[-]
+
+	I'm rechecking that the cells are 16 bits
+	this condition should always be true
+
+	+>>++++[-<<[->++++<]>[-<+>]>]< + <[ >>
+
+	    Print a message
+	    >[-]++++++++++[<+++++++++++>-]<+++++++++.--------.
+	    +++.------.--------.[-]
+
+	<[-]<[-] ] >[> > Dead code here
+	    This should never be executed because it's in an 8bit zone hidden
+	    within a 16bit zone; a really good compiler should delete this
+	    If you see this message you have dead code walking
+
+	    Print a message
+	    [-]>[-]+++++++++[<++++++++++>-]<.
+	    >++++[<+++++>-]<+.--.-----------.+++++++.----.
+	    [-]
+
+	<<[-]]<
+	===== END DEMO CODE =====
+
+<<[-]] >[-]< ] >[>
+	Cells should be 8bits at this point
+
+	The pointer is at cell two but you only have 8 bits cells
+	and it's time to use the really big and slow BF quad encoding
+
+	======= DEMO CODE =======
+
+	A broken wrapping check
+	+++++[>++++<-]>[<+++++++++++++>-]<----[[-]>[-]+++++[<++++++>-]<++.
+	>+++++[<+++++++>-]<.>++++++[<+++++++>-]<+++++.>++++[<---->-]<-.++.
+	++++++++.------.-.[-]]
+
+	Space
+	++>[-]+++++[<++++++>-]<.[-]
+
+	An exponent checker for github user btzy
+	>++[>++<-]>[<<+>>[-<<[>++++<-]>[<++++>-]>]]<<[>++++[>---<++++]>++.
+	[<++>+]<.[>+<------]>.+++.[<--->++]<--.[-]<[-]]
+
+        Another dead code check
+        [-]>[-]>[-]<++[>++++++++<-]>[<++++++++>-]<[>++++++++<-]>[<++++++++>-
+        ]<[<++++++++>-]<[[-]>[-]+++++++++[<++++++++++>-]<.>++++[<+++++>-]<+.
+        --.-----------.+++++++.----.>>[-]<+++++[>++++++<-]>++.<<[-]]
+
+	Print a message
+	[-] <[>+<[-]]> +++++>[-]+++++++++[<+++++++++>-]<.
+	>++++[<++++++>-]<.+++.------.--------.
+	[-]
+	===== END DEMO CODE =====
+
+<[-]]<
+
++[[>]<-]    Check unbalanced loops are ok
+
+>>
+	======= DEMO CODE =======
+	Back out and print the last two characters
+
+	[<[[<[[<[[<[,]]]<]<]<]<][ Deep nesting non-comment comment loop ]]
+
+	Check that an offset of 128 will work
+	+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+	>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>-[+<-]
+
+	And back
+	+++[->++++++<]>[-<+++++++>]<[->>[>]+[<]<]>>[->]<<<<<<<<<<<<<<<<<<<<<
+	<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+	<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+
+	And inside a loop
+	--[>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+	>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>++<<<
+	<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+	<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+]+>----[++
+	++>----]-[+<-]
+
+	This is a simple multiply loop that looks like it goes off the
+	start of the tape
+	+[>]<- [-
+	    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+	    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+	    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+	    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+	    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+	    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+	    ++++
+	    >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+	    >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+	    >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+	    >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+	    >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+	    >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+	]
+
+	[ Check there are enough cells. This takes 18569597 steps. ]
+	[
+	    >++++++[<+++>-]<+[>+++++++++<-]>+[[->+>+<<]>>
+	    [-<<+>>]<[<[->>+<<]+>[->>+<<]+[>]<-]<-]<[-<]
+	]
+
+	This loop is a bug check for handling of nested loops; it goes
+	round the outer loop twice and the inner loop is skipped on the
+	first pass but run on the second
+
+	BTW: It's unlikely that an optimiser will notice how this works
+
+	>
+	    +[>[
+		Print the exclamation point
+		[-]+++>
+		[-]+++++ +#-
+		[<+++2+++>-]<
+		.
+
+	    <[-]>[-]]+<]
+	<
+
+	Clean up any debris
+	++++++++[[>]+[<]>-]>[>]<[[-]<]
+
+	This is a hard optimisation barrier
+	It contains several difficult to 'prove' constructions close together
+	and is likely to prevent almost all forms of optimisation
+	+[[>]<-[,]+[>]<-[]]
+
+	This part finds the actual value that the cell wraps at; even
+	if it's not one of the standard ones; but it gets bored after
+	a few thousand: any higher and we print nothing
+
+	This has a reasonably deep nested loop and a couple of loops
+	that have unbalanced pointer movements
+
+	Find maxint (if small)
+	[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<++++[->>++++>>++++>>++
+	++<<<<<<]++++++++++++++>>>>+>>++<<<<<<[->>[->+>[->+>[->+>+[>
+	>>+<<]>>[-<<+>]<-[<<<[-]<<[-]<<[-]<<[-]>>>[-]>>[-]>>[-]>->+]
+	<<<]>[-<+>]<<<]>[-<+>]<<<]>[-<+>]<<<]>+>[[-]<->]<[->>>>>>>[-
+	<<<<<<<<+>>>>>>>>]<<<<<<<]<
+
+	The number is only printed if we found the actual maxint
+	>+<[
+	    Space
+	    >[-]>[-]+++++[<++++++>-]<++.[-]<
+
+	    Print the number
+	    [[->>+<<]>>[-<++>[-<+>[-<+>[-<+>[-<+>[-<+>[-<+>[-<+>[-<+>[<[-]+>
+	    ->+<[<-]]]]]]]]]]>]<<[>++++++[<++++++++>-]<-.[-]<]]
+
+	]
+
+	Check if we should have had a value but didn't
+	>[
+	    >[-]>[-]++++[<++++++++>-]<[<++++++++>-]>+++[<++++++++>-]<+++++++
+	    [<-------->-]<------->+<[[-]>-<]>[>[-]<[-]++++[->++++++++<]>.+++
+	    +++[-<++>]<.[-->+++<]>++.<++++[>----<-]>.[-]<]<
+
+	    [-]>[-]++++++++[<++++++++>-]<[>++++<-]+>[<->[-]]<[>[-]<[-]++++[-
+	    >++++++++<]>.---[-<+++>]<.---.--------------.[-->+<]>--.[-]<]
+	]<
+
+	Clean up any debris
+	++++++++[[>]+[<]>-]>[>]<[[-]<]
+
+	One last thing: an exclamation point is not a valid BF instruction!
+
+	Print the newline
+	[-]++++++++++.[-]
+	[
+	    Oh, and now that I can use "!" the string you see should be one of:
+	    Hello World! 255
+	    Hello world! 65535
+	    Hello, world!
+
+	    And it should be followed by a newline.
+	]
+
+	===== END DEMO CODE =====
+
+<<  Finish at cell zero
\ No newline at end of file