search

rdebath / Brainfuck

Brainfuck torture test. Brainfuck interpreters and compilers to C, V. VIM syntax file for brainf*ck. Fast JIT Assembly, JIT C running, Perl, Python, php, Ruby, lua, go, awk, neko, PS1, bash, ook, trollscript etc etc
GNU General Public License v2.0
201 stars 22 forks source link

My compiler chokes on the first five lines of Cellsize.b, but passes the bitwidth.b program #4

Closed btzy closed 7 years ago

btzy commented 7 years ago

I made an online compiler which passes bitwidth.b, but gives an incorrect output for Cellsize.b. Here is the bugged version of my compiler.

It is due to incorrectly optimizing the exponentiation in the first 5 lines of Cellsize.b. bitwidth.b has no exponentiation at all, maybe you would like to add some exponentiation to your torture test?

rdebath commented 7 years ago

Looks like this is a suitable (not too expensive) variant to add.

>++[>++<-]>[<<+>>[-<<[>++++<-]>[<++++>-]>]]<<[>++++[>---<++++]>++.[<++>+]<.[>+<------]>.+++.[<--->++]<--.[-]<[-]]

A different insert so it makes sense if someone manages to trigger both of them :smiling_imp:

btzy commented 7 years ago

That's an interesting way of printing Evil you've got there; it took me a while to understand how you were exploiting integer overflow/underflow :O

[Update] Oops sorry, I didn't realize you added the check to the 8-bit section of your bitwidth.b code.

But it seems to only work on 8 bits. 16^4 ≡ 0 is only true on 8 and 16 bits, but not 32.

And the overflow/underflow exploit probably needs to be edited for 16 bits. The online compiler here (the only online compiler supporting 16 bits that I could find) returns some Chinese characters when I input +[>++++[>---<++++]>++.[<++>+]<.[>+<------]>.+++.[<--->++]<--.[-]<[-]] (simulating a failure in the 16^4 test).

rdebath commented 7 years ago

I nearly used this one ...

-[[+>]+[+++<]>-]>>>>>---.<<<--.>+.+++.>>>>--------.[>]<[[-]<]<<

But it turned out slightly longer once I started clearing the cells.

I have considered adding this test to the 16bit part, but the instruction count for Cellsize.b is a bit high (the 32bit and up are basically unrunnable without good optimisation) and I do want the bitwidth.b to run on almost any interpreter.

So it comes down to how likely the bug is for 16bit; I don't think there will be enough Interpreters to test. 

$ bf2c -i -T'unsigned  short'  testing/Cellsize.b
This interpreter has 16bit cells.

Commands executed: 817423
$ bf2c -i -Tunsigned testing/Cellsize.b
This interpreter has 32bit cells.

Commands executed: 52971276231
$ bf2c -c -i -T'unsigned long' testing/Cellsize.b | ...
This interpreter has 64bit cells.

Commands executed: 227509843575751147520
$ bf2c -c -i -T__uint128_t testing/Cellsize.b | ...
This interpreter has 128bit cells.

Commands executed: 113427455640312814857969558651062452224
$

NB: The last two may still have overflowed on the instruction counts!

btzy commented 7 years ago

Nice, I see (:

The one that you nearly used is also interesting because of the unbalanced shifting of the pointer.