메아리 저널

Brainfuck interpreter in 2 lines of C​

I did know about the twIP, a very small IP stack that can only respond to pings and also fit in a tweet, but recently I tried to execute the idea of making small and still usable things like that.

Well, I ended up with a slightly large program than a tweet, but it fits in two lines, i.e. 160 bytes. Let me introduce the world’s smallest Brainfuck interpreter1 in C: (Gist)

Test it yourself! For example:

$ cc bf.c -o bf
$ ./bf '++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.'
Hello World!

Details

Obviously it is so small that it is picky about environments:

  • Requires ASCII charset. (Nowadays…)
  • Requires a certain subset of POSIX-compatible operating system. More specifically, the OS should have syscall 3 and 4 for read and write respectively. (This subset includes 32-bit x86 Linux and FreeBSD.)
  • Requires sizeof(int) to be as wide as sizeof(int*) and sizeof(char*).
  • Requires a calling convention which orders arguments in the order in the memory, not in the reverse order.

So what does it implement? It implements a full Brainfuck interpreter with quite limited2 memory. It receives the correct Brainfuck program (without any non-instruction characters, including spaces) as an argument, and fully capable for input and output3. Memory is int-sized and it doesn’t modify the cell on EOF. The exit code doesn’t have the meaning.

The program itself is not that complex; the biggest decision I’ve made was how to handle loops, and I solved the problem by calling main itself recursively. In the other words, if the interpreter encounters [ it calls itself with the body as a new code. This is why it terminates at the first non-matching ]. Also it takes care of the case that the loop doesn’t run at all; in this case we still have to fast-forward to skip the loop, so main makes use of the first argument, a, to indicate this case. Having the overall design, deobfuscating the program would be simpler. (In fact I want to explain each byte, but the crazy network prohibits me from writing very long posts…)

Okay, it was quite fun for 24 free hours. Let me see if it can be shortened further and fit in a tweet… but for now that’s all folks. ;)


Addendum: The following is a much portable version of the interpreter. It only uses the standard C (with the only assumption being the size of int and pointers) but is slightly longer (170 bytes). Its behavior on EOF also differs.

s[999],*r=s,*d,c;main(a,b){char*v=1[d=b];for(;c=*v++%93;)for(b=c%7?a&&(c&17?c&1?
(*r-=c-44):(r+=c-61):c&2?putchar(*r):(*r=getchar()),0):v;b&&c|a**r;v=d)main(!c,&
b-1);d=v;}

  1. Not verified. Please note me if you found any smaller one. ;) 

  2. It has 99 cells in the original form, but you can modify s[99] to change the limit. 

  3. Output goes to stderr, not stdout. This was a compromise to shorten the program (by two bytes, by the way). 


노트들

  1. mostlymaths reblogged this from arachneng
  2. arachneng posted this
텀블러를 씁니다.