Суть языка Brainfuck в том, что мы всегда бегаем по ячейкам ленты, уменьшая или увеличивая значения в них. В циклах мы можем пробегать из одного конца в другой, что-то подсчитывая, зачастую используя много вложенных циклов. Не трудно догадаться, что интерпретация этого языка относительно медленна. Конечно, на современных компьютерах этого практически не заметно, но… Предлагаю небольшой тест: берите написанный вами интерпретатор, и запускайте вот этот не хитрый код:
Дождались конца выполнения? Согласитесь, что это было не так быстро, как могло показаться сразу. Что ж, давайте посмотрим, как сделать интерпретатор, который будет выполнять данный код не больше чем за несколько секунд.
В основе лежит идея JIT-компиляции. Википедиа говорит нам, что JIT-компиляция это технология увеличения производительности программных систем, использующих байт-код, путём компиляции байт-кода в машинный код непосредственно во время работы программы. Немного подумав, я решил, что будет гораздо целесообразнее сразу построить весь необходимый массив машинного кода, а не подменять его во время работы. Я так думаю, что суть от этого меняется не сильно. Но, давайте по порядку.
Итак, как всем уже известно, синтаксис языка Brainfuck состоит всего из 8 операторов. В наличии имеется набор ячеек памяти и указатель на текущую ячейку. Фактически, нам необходимо в результате выполнения программы конвертировать код на Brainfuck в ассемблерные команды (их машинные коды) x86 процессора. Для этого неплохо иметь какое-то представление о языке ассемблера, а так же о правилах генерации машинных кодов (опкодов). Каждую команду на Brainfuck мы будем заменять на одну или несколько команд процессора x86.
Прежде всего необходимо создать массив ячеек памяти и получить на него указатель. Это можно сделать с помощью функции динамического выделения памяти. Так, в языке программирования Pascal (а дальнейший код примеров будет на нем), это можно сделать так:
Далее, необходимо продумать стратегию обработки команд Brainfuck’a. Я использовал следующую:
Условимся, что в регистре ESI будет храниться указатель на массив ячеек.
Тогда, остальные команды будут:
Что касается команд ‘.’ и ‘,’, то тут понадобятся процедура вывода символа и функция вода символа. Их можно реализовать так:
Затем, можно условиться, что регистр EDX при старте выполнимого кода содержит адрес процедуры печати символа
а регистр EBX – адрес функции ввода символа:
Тогда, обрабатывать ‘.’ Можно следующим образом:
А команду “,” так:
Для простоты заведем статичный массив ExBuf, куда и будем складывать все наши опкоды, а затем передадим управление на начало массива. Переменная ptr будет указателем последнего занесенного опкода.
Первыми тремя командами в нашем блоке кода будут, как мы условились, установка регистра ESI на указатель ячеек, регистра EDX на указатель процедуры WriteChar и регистра EBX на указатель функции ReadChar. Сделать это можно так:
Все, первичная инициализация проведена. Теперь нужно написать процедуру обработки кодов Brainfuck. Для первых команд она может быть такой:
На вход процедуры поочередно передаем коды на языке Brainfuck, которые преобразуются в машинные кода и постепенно заносятся в массив ExBuf.
Несколько сложнее обстоит дело с командами циклов ‘[‘ и ‘]’. Как все мы помним, у процессоров x86 есть несколько режимов адресации, и соответственно, несколько команд ближних (near) или коротких (short) переходов. Так, если общая длинна опкодов между командой перехода и меткой не превышает 127 байт, можно использовать короткие (short) переходы. Если больше, то уже понадобятся команды ближних переходов (near). Я реализовал это следующим образом: при встрече команды ‘[‘ я генерирую команду je near xxx и запоминаю в дополнительном массиве текущую позицию буфера команд. После, когда в коде встретиться команда ‘]’, я вычисляю разницу между началом цикла и концом (длину байт), и если она меньше 127 байт, я возвращаюсь на запомненную позицию, затираю прежний je near xxx на je short xxx и перебрасываю остаток кода на четыре байта вперед. С учетом этого остается дополнить вышеописанную процедуру JITCode:
Вот практически и все, это уже готовая рабочая реализация. Остается совсем не много – записать последней командой ret (возврат из процедуры). Ее опкод – 0xC3:
И передать управление на сформированный буфер машинных команд:
Но давайте посмотрим, что можно сделать еще с оптимизацией нашей программы. Идея, которая буквально лежит на поверхности: в коде Brainfuck часто встречаются повторяющиеся однотипные команды, например +++++++++++ или <<<<. Что значит увеличить текущую ячейку на 11 или переместить указатель ячеек на 4 влево. Можно ввести дополнительные символы, которые будут обозначать следующее:
<<<<< = заменяется на p# (prev) сдвиг указателя влево сразу на # значений
>>>>> = заменяется на n# (next) сдвиг указателя вправо сразу на # значений
+++++ = заменяется на i# (inc) увеличение текущей ячейки сразу на #
— = заменяется на d# (dec) уменьшение текущей ячейки сразу на #
[-],[+] = заменяется на z (zero) установка значения ячейки в 0
Такую предобработку можно провести в начале интерпретатора. Порой, это дает существенное уменьшение исходного кода на Brainfuck, и как следствие, уменьшение x86 кода. После данной обработки остается дополнить нашу процедуру JITCode:
Скачать исходный код и скомпилированную Win32 версию можно тут: rghost.ru/4249797
У программы есть ключи:
-c — создать на диске файл OUT.BC, содержащий в себе промежуточный байт-код, после предпроцессора.
-b — создать на диске файл BF.BIN, содержащий в себе сгенерированный массив машинных кодов. Если его открыть в HIEW, то можно увидеть обычные ассемблерные команды.
Всем удачи.
>+>+>+>+>++<[>[<+++>-
>>>>>
>+>+>+>+>++<[>[<+++>-
>>>>>
>+>+>+>+>++<[>[<+++>-
>>>>>
>+>+>+>+>++<[>[<+++>-
>>>>>
+++[->+++++<]>[-]<
<<<<<
]<<]>[-]
<<<<<
]<<]>[-]
<<<<<
]<<]>[-]
<<<<<
]<<]>.Дождались конца выполнения? Согласитесь, что это было не так быстро, как могло показаться сразу. Что ж, давайте посмотрим, как сделать интерпретатор, который будет выполнять данный код не больше чем за несколько секунд.
В основе лежит идея JIT-компиляции. Википедиа говорит нам, что JIT-компиляция это технология увеличения производительности программных систем, использующих байт-код, путём компиляции байт-кода в машинный код непосредственно во время работы программы. Немного подумав, я решил, что будет гораздо целесообразнее сразу построить весь необходимый массив машинного кода, а не подменять его во время работы. Я так думаю, что суть от этого меняется не сильно. Но, давайте по порядку.
Итак, как всем уже известно, синтаксис языка Brainfuck состоит всего из 8 операторов. В наличии имеется набор ячеек памяти и указатель на текущую ячейку. Фактически, нам необходимо в результате выполнения программы конвертировать код на Brainfuck в ассемблерные команды (их машинные коды) x86 процессора. Для этого неплохо иметь какое-то представление о языке ассемблера, а так же о правилах генерации машинных кодов (опкодов). Каждую команду на Brainfuck мы будем заменять на одну или несколько команд процессора x86.
Прежде всего необходимо создать массив ячеек памяти и получить на него указатель. Это можно сделать с помощью функции динамического выделения памяти. Так, в языке программирования Pascal (а дальнейший код примеров будет на нем), это можно сделать так:
Var
Stack : Pointer;
Begin
GetMem(Stack,30000); //число ячеек в стандартном brainfuck - 30000
End;
Далее, необходимо продумать стратегию обработки команд Brainfuck’a. Я использовал следующую:
Условимся, что в регистре ESI будет храниться указатель на массив ячеек.
mov esi, Stack
Тогда, остальные команды будут:
| Brainfuck | Assembler | Opcode |
| + | inc byte [esi] | FE 06 |
| - | dec byte [esi] | FE 0E |
| > | inc esi | 46 |
| < | dec esi | 4E |
| [ | cmp byte [esi], 0 | 80 3E 00 |
| je "]+1" | 0F 84 xx xx xx xx или 74 xx | |
| ] | jmp "[" | E9 xx xx xx xx или EB xx |
Что касается команд ‘.’ и ‘,’, то тут понадобятся процедура вывода символа и функция вода символа. Их можно реализовать так:
procedure WriteChar(S: Char);
begin
Write(S);
end;
function ReadChar: Char;
var
c : char;
begin
Read(c );
ReadChar := c;
end;
Затем, можно условиться, что регистр EDX при старте выполнимого кода содержит адрес процедуры печати символа
mov edx, offset WriteCharа регистр EBX – адрес функции ввода символа:
mov ebx, offset ReadCharТогда, обрабатывать ‘.’ Можно следующим образом:
mov al,[esi] 8A 06 ;в регистр AL значение текущей ячейки
cbw 66 98 ;расширить до двойного слова EAX
push eax 50 ;занести в стек параметр процедуры (символ)
call edx FF D2 ;вызвать процедуру WriteCharА команду “,” так:
call ebx FF D3;вызвать процедуру ReadChar
mov [esi],al 88 06; поместить в текущую ячейку код символа
Для простоты заведем статичный массив ExBuf, куда и будем складывать все наши опкоды, а затем передадим управление на начало массива. Переменная ptr будет указателем последнего занесенного опкода.
Var
ExBuf : Array [1..65535] of Byte;
Ptr : Word;
Tmp : LongInt;Первыми тремя командами в нашем блоке кода будут, как мы условились, установка регистра ESI на указатель ячеек, регистра EDX на указатель процедуры WriteChar и регистра EBX на указатель функции ReadChar. Сделать это можно так:
ptr := 1;
ExBuf[ptr] := $BE; inc(ptr); // mov esi,Stack
asm
mov edx,Stack
mov Tmp,edx
end;
Move(Tmp,ExBuf[ptr],4); inc(ptr,4);
ExBuf[ptr] := $BA; inc(ptr); // mov edx,offset WriteChar
asm
mov edx, offset WriteChar
mov Tmp, edx
end;
Move(Tmp,ExBuf[ptr],4); inc(ptr,4);
ExBuf[ptr] := $BB; inc(ptr); // mov ebx,offset ReadChar
asm
mov edx, offset ReadChar
mov Tmp, edx
end;
Move(Tmp,ExBuf[ptr],4); inc(ptr,4);Все, первичная инициализация проведена. Теперь нужно написать процедуру обработки кодов Brainfuck. Для первых команд она может быть такой:
Procedure JITCode(S: Char);
Begin
Case S of
'+': Begin
ExBuf[ptr] := $FE; //inc byte ptr [esi]
ExBuf[ptr+1] := $06;
Inc(ptr,2);
End;
'-': Begin
ExBuf[ptr] := $FE; //dec byte ptr [esi]
ExBuf[ptr+1] := $0E;
Inc(ptr,2);
End;
'>': Begin
ExBuf[ptr] := $46; //inc esi
Inc(ptr);
End;
'<': Begin
ExBuf[ptr] := $4E; //dec esi
Inc(ptr);
End;
'.': Begin
ExBuf[ptr] := $8A; //mov al,[esi]
ExBuf[ptr+1] := $06;
Inc(ptr,2);
ExBuf[ptr] := $66; //cbw
ExBuf[ptr+1] := $98;
Inc(ptr,2);
ExBuf[ptr] := $50; //push eax
Inc(ptr);
ExBuf[ptr] := $FF; //call edx
ExBuf[ptr+1] := $D2;
Inc(ptr,2);
End;
',': Begin
ExBuf[ptr] := $FF; //call ReadChar
ExBuf[ptr+1] := $D3;
Inc(ptr,2);
ExBuf[ptr] := $88; //mov [esi],al
ExBuf[ptr+1] := $06;
Inc(ptr,2);
End;
End;На вход процедуры поочередно передаем коды на языке Brainfuck, которые преобразуются в машинные кода и постепенно заносятся в массив ExBuf.
Несколько сложнее обстоит дело с командами циклов ‘[‘ и ‘]’. Как все мы помним, у процессоров x86 есть несколько режимов адресации, и соответственно, несколько команд ближних (near) или коротких (short) переходов. Так, если общая длинна опкодов между командой перехода и меткой не превышает 127 байт, можно использовать короткие (short) переходы. Если больше, то уже понадобятся команды ближних переходов (near). Я реализовал это следующим образом: при встрече команды ‘[‘ я генерирую команду je near xxx и запоминаю в дополнительном массиве текущую позицию буфера команд. После, когда в коде встретиться команда ‘]’, я вычисляю разницу между началом цикла и концом (длину байт), и если она меньше 127 байт, я возвращаюсь на запомненную позицию, затираю прежний je near xxx на je short xxx и перебрасываю остаток кода на четыре байта вперед. С учетом этого остается дополнить вышеописанную процедуру JITCode:
'[': Begin
ExBuf[ptr] := $80; //cmp byte ptr [esi],0
ExBuf[ptr+1] := $3E;
ExBuf[ptr+2] := $00;
Inc(ptr,3);
ExBuf[ptr] := $0F; //je near xxx
ExBuf[ptr+1] := $84;
Inc(ptr,2);
bstack[bcnt] := ptr;
inc(bcnt);
Inc(ptr,4);
End;
']': Begin
Tmp := ptr - bstack[bcnt-1];
If Tmp > 122 then
begin
ExBuf[ptr] := $E9; //jmp
Inc(ptr);
Inc(Tmp);
Move(Tmp,ExBuf[bstack[bcnt-1]],4);
Tmp := -Tmp-9;
Move(Tmp,ExBuf[ptr],4);
Inc(ptr,4);
Dec(bcnt);
end
else
begin
ExBuf[ptr] := $EB; //jmp short
Inc(ptr);
ExBuf[bstack[bcnt-1]-2] := $74; // je short xxx
Dec(Tmp,2);
Move(Tmp,ExBuf[bstack[bcnt-1]-1],1);
Tmp := -Tmp-5;
Move(Tmp,ExBuf[ptr],1);
Inc(ptr);
Move(ExBuf[bstack[bcnt-1]+4],ExBuf[bstack[bcnt-1]],ptr-bstack[bcnt-1]-4);
Dec(ptr,4);
Dec(bcnt);
end;
End;Вот практически и все, это уже готовая рабочая реализация. Остается совсем не много – записать последней командой ret (возврат из процедуры). Ее опкод – 0xC3:
ExBuf[ptr] := $C3; //retnИ передать управление на сформированный буфер машинных команд:
asm
mov edx,offset ExBuf
call edx
end;Но давайте посмотрим, что можно сделать еще с оптимизацией нашей программы. Идея, которая буквально лежит на поверхности: в коде Brainfuck часто встречаются повторяющиеся однотипные команды, например +++++++++++ или <<<<. Что значит увеличить текущую ячейку на 11 или переместить указатель ячеек на 4 влево. Можно ввести дополнительные символы, которые будут обозначать следующее:
<<<<< = заменяется на p# (prev) сдвиг указателя влево сразу на # значений
>>>>> = заменяется на n# (next) сдвиг указателя вправо сразу на # значений
+++++ = заменяется на i# (inc) увеличение текущей ячейки сразу на #
— = заменяется на d# (dec) уменьшение текущей ячейки сразу на #
[-],[+] = заменяется на z (zero) установка значения ячейки в 0
Такую предобработку можно провести в начале интерпретатора. Порой, это дает существенное уменьшение исходного кода на Brainfuck, и как следствие, уменьшение x86 кода. После данной обработки остается дополнить нашу процедуру JITCode:
'i': Begin
ExBuf[ptr] := $80; //add byte ptr [esi],xx
ExBuf[ptr+1] := $06;
ExBuf[ptr+2] := Ord(Buf[i+1]);
Inc(i);
Inc(ptr,3);
End;
'd': Begin
ExBuf[ptr] := $80; //sub byte ptr [esi],xx
ExBuf[ptr+1] := $2E;
ExBuf[ptr+2] := Ord(Buf[i+1]);
Inc(i);
Inc(ptr,3);
End;
'n': Begin
ExBuf[ptr] := $83; //add esi,xx
ExBuf[ptr+1] := $C6;
ExBuf[ptr+2] := Ord(Buf[i+1]);
Inc(i);
Inc(ptr,3);
End;
'p': Begin
ExBuf[ptr] := $83; //sub esi,xx
ExBuf[ptr+1] := $EE;
ExBuf[ptr+2] := Ord(Buf[i+1]);
Inc(i);
Inc(ptr,3);
End;
'z': Begin
ExBuf[ptr] := $C6; //mov byte ptr [esi],0
ExBuf[ptr+1] := $06;
ExBuf[ptr+2] := $00;
Inc(ptr,3);
End;Скачать исходный код и скомпилированную Win32 версию можно тут: rghost.ru/4249797
У программы есть ключи:
-c — создать на диске файл OUT.BC, содержащий в себе промежуточный байт-код, после предпроцессора.
-b — создать на диске файл BF.BIN, содержащий в себе сгенерированный массив машинных кодов. Если его открыть в HIEW, то можно увидеть обычные ассемблерные команды.
Всем удачи.
