27 сентября 2010 в 15:58

Интерпретатор Brainfuck размером 160 байт

Прочитав про IP-стэк twIP, который помещается в размер твита и отвечает на пинги, корейский программист Канг Сеонгхун (Kang Seonghoon) решил создать нечто такое же миниатюрное и при этом работоспособное. И он создал самый маленький интерпретатор Brainfuck на C размером всего 160 байт.

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

Интерпретатор способен выполнять любые программы на Brainfuck.

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


Конечно, из-за стремления втиснуться в 160 байт пришлось многие вещи переложить на окружение. Более портативная и независимая от окружения версия интерпретатора занимает 170 байт.

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;}

Если добавить нормальную табуляцию, то код будет выглядеть так:

  // с пробелами

  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;
  }
Анатолий Ализар @alizar
карма
751,5
рейтинг 18,2
Пользователь
Похожие публикации
Самое читаемое Разработка

Комментарии (32)

  • +1
    1 твит == 140 байт…
    • +1
      А twIP 1.1 — 139 байт.
    • +8
      1 твит == 140 символов. Так как юникод, то 1 символ не равен 1 байту.
      • 0
        Весь ASCII, емнип, всунули в однобайтовую зону. Ну а твиттер считает любые символы, а не байты, если на то пошло.
  • +30
    Молодец.
    Вот бы кто jre в 140 байт обкорнал…
    мечты…
    • +2
      не 140 конечно, но ОЧЕНЬ мало
      www.harbaum.org/till/nanovm/index.shtml
      джава машина для контроллера atmega8, даже работает :)
  • +1
    Код с табуляцией соответствует 170-байтной программе, а не 160-байтной.
  • +1
    Codegoooooooolf :)
    Я еще вот такую задачку гольфил на с :)
  • 0
    На www.muppetlabs.com/~breadbox/bf/ есть 166-байтный компилятор брейнфака.
    • 0
      Президент одобряет.
  • 0
    [al@localhost ~]$ cat bf.c
    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;}
    [al@localhost ~]$ cc bf.c -o bf
    bf.c:1: предупреждение: data definition has no type or storage class
    bf.c: В функции ‘main’:
    bf.c:1: предупреждение: в присваивании целое преобразуется в указатель без приведения типа
    bf.c:1: предупреждение: при инициализации целое преобразуется в указатель без приведения типа
    bf.c:1: предупреждение: несоответствие типов указатель/целое в условном выражении
    bf.c:1: предупреждение: несоответствие типов указатель/целое в условном выражении
    bf.c:1: предупреждение: несоответствие типов указатель/целое в условном выражении
    bf.c:1: предупреждение: в присваивании указатель преобразуется в целое без приведения типа
    bf.c:1: предупреждение: несовместимый тип указателя в присваивании
    bf.c:1: предупреждение: несовместимый тип указателя в присваивании
    [al@localhost ~]$ ./bf '++++++++++[>+++++++>++++++++++>+++>+.'
    Ошибка сегментирования
    • 0
      zubchick~ % cc test.c -o bf 17:59
      test.c:1: warning: data definition has no type or storage class
      test.c: In function ‘main’:
      test.c:1: warning: assignment makes pointer from integer without a cast
      test.c:1: warning: initialization makes pointer from integer without a cast
      test.c:1: warning: pointer/integer type mismatch in conditional expression
      test.c:1: warning: pointer/integer type mismatch in conditional expression
      test.c:1: warning: pointer/integer type mismatch in conditional expression
      test.c:1: warning: assignment makes integer from pointer without a cast
      test.c:1: warning: assignment from incompatible pointer type
      test.c:1: warning: assignment from incompatible pointer type
      zubchick~ % ./bf '++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.'
      Hello World!
    • +1
      Видимо это не для x64…
  • +2
    что означает число 93?
    • +22
      То есть назначение остальных чисел вам понятно?
    • +5
      почти то же, что и 42.

      Это десятичное представление команд BF в ASCII. 93 это ]
  • +2
    Прошу прощения за оффтоп, что значит реализация ip-стека, как его вообще можно реализовать, это ведь просто иерархия протоколов, логическая. Не удивляйтесь глупому вопросу — гуглил, не помогло… Не могли бы вы объснить что тут к чему?
    • –4
      Из контекста статьи получается, что IP = Instruction Pointer, соответственно IP-стек = стек вызова.
      • –2
        то есть если я правильно вас понимаю то IP в данном случае аналог EIP в асме? и его каким то образом можно изменять?
      • +2
        а какже
        >> и отвечает на пинги
    • 0
      Ну код-то посмотрите там 3 строчки. Конечно никакого стека там нет. Читает пакет из stdin, если ICMP — меняет адреса местами, ставит тип эхо и пишет в stdout.
    • 0
      Прошу прощения за оффтоп, что значит реализация ip-стека, как его вообще можно реализовать, это ведь просто иерархия протоколов, логическая.
      Это вы автора топика спрашиваете?
      Нашли кого спросить.
      По моим наблюдениям, alizar не является IT-специалистом и, к сожалению, часто постит то, что сам даже не до конца понимает. Увы.

      Если вы посмотрите в оригинал статьи, на которую он сослался, то вам станет понятно, что программа twIP (с кодом на C в 139 символов):
      — вешается на обработку входящих/исходящих потоков сетевого интерфейса;
      — может только отвечать на ping (получать пакеты ICMP echo request и отдавать в ответ пакеты ICMP echo reply);
      — не использует сокеты и оперирует голыми пакетами, извлекаемыми из потока;
      — написана just for fun;
      — в предложенном варианте работает только под FreeBSD, а для работы в Linux нужно делать некоторые добавления в код, которые делают код уже длиннее 140 символов.
  • +1
    Если не путаю, то самый маленький вирус был 47 байт, и 32 байта который портил файл (заражаемый корд затирался).
    • –2
      Самый маленький вирус вот (вешает 9х намертво):

      cli
      jmp $

      (это 2 байта в .com)
      • +9
        Вирус — это самовоспроизводящийся код, а не любая пакость.
      • –1
        while(fork()) fork()
        вешает намертво любой юникс
        • +3
          Только в том случае, если не включен лимит на кол-во процессов для пользователя. На машинах «для студентов» обычно включают.
  • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    160 или 170 байт — это исходный код, а не сам интерпретатор!
    Скомпилированный файл у меня получился 9053 байта — есть, над чем работать. Например, переписать на ассемблере под ДОС :)
    • +2
      Зачем DOS, лучше под спектрум =)
      (вечерком попробую)
    • 0
      *Компилятор* bf, написанный на ассемблере. В откомпилированном виде занимает 170 байт.
      www.muppetlabs.com/~breadbox/software/tiny/bf.asm.txt

      ~/tmp$ nasm -f bin -o bf bf.asm
      ~/tmp$ chmod +x bf
      ~/tmp$ ./bf < hello.b > hello
      ~/tmp$ chmod +x hello
      ~/tmp$ ./hello
      Hello World!
      • 0
        уже упомянут выше

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.