Переводчик Brainfuck написан на x86 Assembly

Question

Переводчик Brainfuck написан на x86 Assembly

Время истории: неделю назад я нашел вопрос об оптимизации кода сборки , то я вспомнил, как был потрясающий Brainfuck, и матч был сделан очень быстро. Я решил написать переводчика Brainfuck на Ассамблее!

Для этого я использовал ассемблер NASM с сборкой x86 и предназначен для работы на процессоре Intel и в ОС Windows. Я уверен, вы можете заставить его работать на других комбинациях, если вы действительно этого хотите. Я также использую компилятор Borland 5.5 C, который довольно старый, но Assembly Book использовал его, и я решил не отклоняться от него.

Вы можете скомпилировать код со следующим:

nasm -f obj bf-interpreter.asm
bcc32 bf-interpreter.obj

Я написал интерпретатор с производительностью в качестве основного фокуса, но я еще не много читал об оптимизации, поэтому я не удивлен, если окажется, что это ужасный код. Поскольку код связывается с C stdlib, я могу вызывать методы из C stdlib и по существу только EBX, EDI и ESI регистры считаются «безопасными», это означает, что они не будут перезаписаны вызовами C stdlib, моя реализация использует это соглашение много.

Эта версия интерпретатора BF читается из файла, который передается в качестве аргумента программе.

 extern _malloc, _calloc, _printf, _fdopen, _fprintf, _scanf, _getchar, _putchar, _fopen, _fseek, _ftell, _rewind, _fgetc, _fclose

%define STDERR                  2
%define SEEK_END                2
%define EOF                     -1    

%define BF_MEMORY_CELL_AMOUNT   30000

%define BF_PROGRAM_END          255

%define JUMP_PAST_CODE          91
%define JUMP_BACK_CODE          93

segment _DATA public align=4 class=DATA use32

format_int              db      "%d", 0

write_mode              db      "w", 0
read_mode               db      "r", 0

bfprogram_jump_table    times 43 dd run_program_loop_end, 
                        dd bfprogram_memory_inc, 
                        dd bfprogram_input, 
                        dd bfprogram_memory_dec,
                        dd bfprogram_output,
                        times 13 dd run_program_loop_end,
                        dd bfprogram_pointer_left,
                        dd run_program_loop_end,
                        dd bfprogram_pointer_right,
                        times 28 dd run_program_loop_end,
                        dd bfprogram_jump_past,
                        dd run_program_loop_end,
                        dd bfprogram_jump_back,
                        times 34 dd run_program_loop_end,
                        times 127 dd run_program_loop_end,      ; 128 (127 + next line) invalid ASCII characters
                        dd run_program_done                     ; if jump address is 255 (BF_PROGRAM_END), then we're done'

error_noargument        db      "Fatal: No argument was provided.", 0
error_notexist          db      "Fatal: The file does not exist.", 0
error_outofmemory       db      "Fatal: The Operating System does not have enough memory available.", 0

segment _BSS public align=4 class=BSS use32

file_name               resd 1

bf_program_size         resd 1
bf_program              resd 1    

bf_memory               resd 1

group DGROUP _BSS _DATA

segment _TEXT public align=1 class=CODE use32
        global  _main
_main:
    mov     ebp, esp                            ; save original stack pointer
;
; read command line arguments
;
    mov     eax, [ebp + 4]                      ; argc

    cmp     eax, 1
    je      error_exit_noargument

    mov     eax, [ebp + 8]                      ; *argv    
    mov     eax, [eax + 4]                      ; argv[1]

    mov     [file_name], eax
;
; open file
;
    push    read_mode
    push    eax
    call    _fopen
    add     esp, 8

    test    eax, eax
    jz      error_exit_notexist

    mov     edi, eax                            ; store file pointer
;
; get file size
;
    push    SEEK_END
    push    0
    push    edi
    call    _fseek
    add     esp, 12

    push    edi
    call    _ftell
    add     esp, 4

    inc     eax                                 ; reserve one extra byte for the BF_PROGRAM_END code
    mov     [bf_program_size], eax
;
; rewind file
;
    push    edi
    call    _rewind
    add     esp, 4
;
; read Brainfuck program from file
;            
    push    dword [bf_program_size]
    call    _malloc
    add     esp, 4

    test    eax, eax
    jz      error_exit_outofmemory

    mov     [bf_program], eax    
    mov     esi, eax

store_program_loop:
    push    edi
    call    _fgetc
    add     esp, 4

    cmp     eax, EOF                            ; stop reading when end of file reached
    jz      short store_program_done

    mov     [esi], al

    inc     esi
    jmp     short store_program_loop

store_program_done:
    mov     [esi], byte BF_PROGRAM_END          ; store program end special code
;
; close file
;
    push    edi
    call    _fclose
    add     esp, 4
;
; zero-initialize BF memory cells
;
    push    dword 1
    push    BF_MEMORY_CELL_AMOUNT
    call    _calloc
    add     esp, 8

    test    eax, eax
    jz      error_exit_outofmemory

    mov     [bf_memory], eax
;
; run the BF program
;
    mov     esi, eax                            ; current memory address
    mov     edi, [bf_program]                   ; current program address    

run_program_loop:        
    movzx   eax, byte [edi]

    jmp     [bfprogram_jump_table + 4*eax]      ; addresses are dword, ASCII is translated to byte offsets

run_program_loop_end:
    inc     edi

    jmp     short run_program_loop

run_program_done:
    jmp     normal_exit

bfprogram_pointer_right:
    inc     esi

    jmp     run_program_loop_end

bfprogram_pointer_left:
    dec     esi

    jmp     run_program_loop_end

bfprogram_memory_inc:
    mov     al, [esi]
    inc     al
    mov     [esi], al

    jmp     run_program_loop_end

bfprogram_memory_dec:
    mov     al, [esi]
    dec     al
    mov     [esi], al

    jmp     run_program_loop_end

bfprogram_output:
    mov     al, [esi]

    push    eax                                 ; safe to do because eax is 000000xxh before the prior mov
    call    _putchar
    add     esp, 4

    jmp     run_program_loop_end

bfprogram_input:
    call    _getchar

    mov     [esi], al

    jmp     run_program_loop_end

bfprogram_jump_past:
    mov     al, [esi]

    test    al, al                              ; check if memory cell is zero
    jnz     run_program_loop_end                ; if not zero, move to next instruction
;
; find matching ]
;
    mov     ebx, 1                              ; when counter reaches zero the ] is found where we need to jump past

bfprogram_jump_past_loop:
    inc     edi
    mov     al, [edi]

    cmp     al, JUMP_PAST_CODE
    jz      short bfprogram_jump_past_loop_found_jump_past

    cmp     al, JUMP_BACK_CODE
    jz      short bfprogram_jump_past_loop_found_jump_back

    jmp     short bfprogram_jump_past_loop

bfprogram_jump_past_loop_found_jump_past:
    inc     ebx

    jmp     short bfprogram_jump_past_loop

bfprogram_jump_past_loop_found_jump_back:
    dec     ebx

    test    ebx, ebx
    jz      run_program_loop_end                ; jumped over matching ]

    jmp     short bfprogram_jump_past_loop

bfprogram_jump_back:
    mov     al, [esi]

    test    al, al                              ; check if memory cell is zero
    jz      run_program_loop_end                ; if zero, move to next instruction
;
; find matching [
;
    mov     ebx, 1                              ; when counter reaches zero the [ is found where we need to jump back to

bfprogram_jump_back_loop:
    dec     edi
    mov     al, [edi]

    cmp     al, JUMP_BACK_CODE
    jz      short bfprogram_jump_back_loop_found_jump_back

    cmp     al, JUMP_PAST_CODE
    jz      short bfprogram_jump_back_loop_found_jump_past

    jmp     short bfprogram_jump_back_loop

bfprogram_jump_back_loop_found_jump_back:
    inc     ebx

    jmp     short bfprogram_jump_back_loop

bfprogram_jump_back_loop_found_jump_past:
    dec     ebx

    test    ebx, ebx
    jz      run_program_loop_end                ; jumped back to matching [

    jmp     short bfprogram_jump_back_loop

error_exit_noargument:
    push    write_mode
    push    2
    call    _fdopen
    add     esp, 8

    push    error_noargument
    push    eax
    call    _fprintf
    add     esp, 8
    mov     eax, -1

    jmp     short exit

error_exit_notexist:
    push    write_mode
    push    2
    call    _fdopen
    add     esp, 8

    push    error_notexist
    push    eax
    call    _fprintf
    add     esp, 8
    mov     eax, -2

    jmp     short exit

error_exit_outofmemory:
    push    write_mode
    push    2
    call    _fdopen
    add     esp, 8

    push    error_outofmemory
    push    eax
    call    _fprintf
    add     esp, 8
    mov     eax, -3

    jmp     short exit

normal_exit:
    mov     eax, 0

exit:
    ret

Полный исходный репозиторий доступен на GitHub .
В качестве бонуса я нашел генератор Мандельброта, написанный в онлайн-режиме Brainfuck .
Вы можете увидеть как в действии в следующее видео YouTube, которое я записал .

assembly interpreter brainfuck

оригинал

65 голосов | спросил skiwi 14 12016vEurope/Moscow11bEurope/MoscowMon, 14 Nov 2016 23:55:02 +0300 2016, 23:55:02

2 ответа

2

Команды перехода медленны и должны быть сведены к минимуму. Одна команда перехода в цикле интерпретатора может быть удалена следующим образом:

    dec      edi       ; on first pass, compensate for inc edi
run_program_loop:      ; jump here after executing an opcode
run_program_loop_end:  ; old label for reference
    inc     edi
    movzx   eax, byte [edi]

    jmp     [bfprogram_jump_table + 4*eax]      ; addresses are dword, ASCII is translated to byte offsets

ответил CWallach 16 32016vEurope/Moscow11bEurope/MoscowWed, 16 Nov 2016 03:06:47 +0300 2016, 03:06:47

score 37 · Accepted Answer

Комментарий ; *argv должен быть ; argv, так как вы еще не разыменовываете указатель.
После команды cmp вы должны предпочесть je over jz, так как это лучше для читателя.

О, старые времена, когда вам нужно было сказать ассемблеру jmp short, потому что он не мог понять это самостоятельно. :)
В run the BF program, я бы изменил esi и edi, чтобы s регистрирует точки в s нашем коде, а регистр d указывает на атаку d . Но это просто для удовольствия.
В bfprogram_memory_inc вы можете просто сказать inc byte [esi]. Команда inc имеет кодировку r/m8, которая позволяет напрямую увеличивать значение в памяти, не требуя косвенности.
Оптимизация safe to do приятна.
Так как вы все равно полагаетесь на кодировку ASCII, вы должны определить JUMP_PAST_CODE как '[' вместо 91, если это возможно. Не каждый читатель знает наизусть коды ASCII.
Поддерживает ли NASM локальные метки? Это сделало бы имена меток в bfprogram_jump_past_loop немного короче и тем самым более легким для чтения.
Вместо вызова _fdopen, является stderr символом видимого линкера, чтобы вы могли получить к нему доступ напрямую?
Поскольку ваши сообщения об ошибках не содержат процентных символов, вы должны вызвать fputs вместо fprintf.
Сообщения об ошибках должны содержать конечную новую строку.

(Или они отсутствуют, потому что Windows все равно добавляет эту новую строку? Если это так, то это нормально, так как нет необходимости писать строго соответствующий код ANSI C, когда вы нацеливаете определенную платформу.)
bfprogram_jump_table очень большой. Вероятно, вы можете уменьшить его, закодировав цель перехода по отношению к известному местоположению, которое должно принимать только один байт за запись. times 43 db 0, db bfprogram_memory_inc - run_program_loop_end, ....
format_int, кажется, не используется.
STDERR следует называть STDERR_FILENO (хотя это имя происходит от POSIX, а не от Windows, оно все еще широко известно).
Так как 0xFF является действительной инструкцией в программе Brainfuck, использование ее в качестве маркера EOF не является хорошей идеей. При загрузке кода из файла вы можете заменить каждый символ выше 93 или ниже 43 на 44. Это изменение также позволит вам сделать таблицу перехода меньше.

В целом, это хорошая небольшая программа, и код делает очевидную вещь. Мне приятно читать.

Переводчик Brainfuck написан на x86 Assembly

2 ответа

Похожие вопросы

Популярные теги