Sooo, nacht durchgemacht, hätte lieber lernen sollen.
Diese Version interpretiert den Brainfuck-Code nicht, sondern wandelt ihn in x86-Byte Code um, und ruft diesen dann auf. Eine Art JIT-Compiler also. Dadurch laufen die Brainfuck Programme unglaublich schnell.
Die Berechnung der Mandelbrotmenge (http://esoteric.sange.fi/brainfuck/u...t/mandelbrot.b) benötigt mit dem schnellen Interpeter (http://esoteric.sange.fi/brainfuck/utils/bf-tools/bf.c) beachtliche 40 Sekunden, mit meinem JIT-Compiler nur 5.8 Sekunden.
Funktioniert auf 32bit Linux + Windows.
Ob und wie das auf x64 läuft, weiß ich nicht.
Freu mich über Kommentare!
Edit:
Heute habe ich nochmal einiges umgeschrieben und etwas aufgeräumt. Der Speicher für das kompilierte Programm wächst nun dynamisch.
Außerdem habe ich eine einfache Art eingebaut, wie man bestimmte Codesegmente optimieren kann, z.B. wird das Pattern "[-]" gegen einen Befehl ausgetauscht, der die aktuelle Zelle sofort löscht. (Statt eine Schleife zu beginnen).
Außerdem wird beispielsweise [->*+<*] (* = ein- oder mehrmals das vorige Zeichen) gegen eine Addition ersätzt, falls die Anzahl der > und < gleich ist.
Im Anhang befindet sich das komplette Projekt inklusive Makefile + Executable für Windows + Linux. Hier mal ein paar Dateien herausgepickt.
bf.c
operations.c
Und hier noch die Funktionen, die ich benutze um den Bytecode zu schreiben und auszuführen.
asm_function.c
Diese Version interpretiert den Brainfuck-Code nicht, sondern wandelt ihn in x86-Byte Code um, und ruft diesen dann auf. Eine Art JIT-Compiler also. Dadurch laufen die Brainfuck Programme unglaublich schnell.
Die Berechnung der Mandelbrotmenge (http://esoteric.sange.fi/brainfuck/u...t/mandelbrot.b) benötigt mit dem schnellen Interpeter (http://esoteric.sange.fi/brainfuck/utils/bf-tools/bf.c) beachtliche 40 Sekunden, mit meinem JIT-Compiler nur 5.8 Sekunden.
Funktioniert auf 32bit Linux + Windows.
Ob und wie das auf x64 läuft, weiß ich nicht.
Freu mich über Kommentare!
Edit:
Heute habe ich nochmal einiges umgeschrieben und etwas aufgeräumt. Der Speicher für das kompilierte Programm wächst nun dynamisch.
Außerdem habe ich eine einfache Art eingebaut, wie man bestimmte Codesegmente optimieren kann, z.B. wird das Pattern "[-]" gegen einen Befehl ausgetauscht, der die aktuelle Zelle sofort löscht. (Statt eine Schleife zu beginnen).
Außerdem wird beispielsweise [->*+<*] (* = ein- oder mehrmals das vorige Zeichen) gegen eine Addition ersätzt, falls die Anzahl der > und < gleich ist.
Im Anhang befindet sich das komplette Projekt inklusive Makefile + Executable für Windows + Linux. Hier mal ein paar Dateien herausgepickt.
bf.c
C:
#include "bf.h"
#include "optimize.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
Der eigentliche Brainfuck jit-Compiler.
-0xC = Erste Zelle
-0x8 = Pointer
%eax = Wert der aktuellen Zelle
*/
static const unsigned char bf_code_start[] = {
// push %ebp
0x55,
// mov %esp,%ebp
0x89, 0xe5,
// sub $0x18,%esp
0x83, 0xec, 0x18,
// eax leer machen
0xb8, 0x00, 0x00, 0x00, 0x00, //mov %eax, 0x00
// pointer auf 0 setzten
0xc7, 0x45, -0x08, 0x00, 0x00, 0x00, 0x00 // movl $0x0,-0x8(%ebp)
};
static const unsigned char bf_code_end[] = {
// leave
0xc9,
// ret
0xc3,
0x90, 0x90, 0x90, 0x90, 0x90 //nops
};
bf_context* bf_create() {
bf_context *context = (bf_context*)malloc( sizeof( bf_context ) );
// 30kb für das BrianFuck Array und max 1mb für unser Programm
context->memory = (unsigned char*)malloc( 30000 );
context->loop_stack = stack_create();
context->func = asm_create();
memset( context->memory, 0, 30000 );
// den funktions anfang schreiben
asm_write_bytes( context->func, bf_code_start, sizeof( bf_code_start ) );
// memory pointer abspeichern
//movl $memory,-0xc(%ebp)
//0xc7, 0x45, -0x0c, $memory
const unsigned char code[] = { 0xc7, 0x45, -0x0c };
asm_write_bytes( context->func, code, sizeof( code ) );
asm_write_pointer( context->func, (void*)context->memory );
return context;
}
int bf_finish( bf_context *bf ) {
asm_write_bytes( bf->func, bf_code_end, sizeof( bf_code_end ) );
if( ! stack_empty( bf->loop_stack ) )
return -1;
return 0;
}
void bf_compile_string( bf_context *bf, const unsigned char *code, int length ) {
int sum = 0;
int index = 0;
int result = 0;
while( index < length ) {
result = bf_optimize( bf, code + index, length - index );
if( result > 0 ) {
index += result;
continue;
}
switch( code[index] ) {
case '+':
case '-':
sum = 0;
while( index < length ) {
if( code[index] == '+' ) sum++;
else
if( code[index] == '-' ) sum--;
else break;
index++;
}
if( sum > 0 ) {
bf_plus( bf, sum );
} else
if( sum < 0 ) {
bf_minus( bf, -sum );
}
break;
case '<':
case '>':
sum = 0;
while( index < length ) {
if( code[index] == '>' ) sum++;
else
if( code[index] == '<' ) sum--;
else break;
index++;
}
if( sum > 0 ) {
bf_right( bf, sum );
} else
if( sum < 0 ) {
bf_left( bf, -sum );
}
break;
case '.':
bf_putchar( bf );
index++;
break;
case ',':
bf_getchar( bf );
index++;
break;
case '[':
bf_loop_start( bf );
index++;
break;
case ']':
bf_loop_end( bf );
index++;
break;
// Kein Befehlszeichen
default:
index++;
}
}
}
int bf_run( bf_context *bf ) {
return bf->func->call();
}
operations.c
C:
#include "bf.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
static void bf_store_at_pointer( bf_context *bf );
static void bf_load_at_pointer( bf_context *bf );
void bf_plus( bf_context *bf, int amount ) {
// 0x04, amount, add $amount,%al
asm_write_byte( bf->func, 0x04 );
asm_write_byte( bf->func, amount % 255 );
}
void bf_minus( bf_context *bf, int amount ) {
// 0x2c, $amount, sub $amount,%al
asm_write_byte( bf->func, 0x2c );
asm_write_byte( bf->func, amount % 255 );
}
void bf_putchar( bf_context *bf ) {
const unsigned char code[] = {
// Speichere %eax nach %esp
// mov %eax,(%esp)
0x89, 0x04, 0x24
};
bf_store_at_pointer( bf );
asm_write_bytes( bf->func, code, sizeof( code ) );
asm_write_call( bf->func, (void*)putchar );
bf_load_at_pointer( bf );
}
int bf_getchar_handler() {
int result = getc( stdin );
if( result == -1 )
result = 0;
return (unsigned char)result;
}
void bf_getchar( bf_context *bf ) {
asm_write_call( bf->func, (void*)bf_getchar_handler );
}
void bf_right( bf_context *bf, int amount ) {
const unsigned char code[] = {
// Vergleiche Pointer mit 30000
// cmpl $0x752f,-0x8(%ebp)
0x81, 0x7d, -0x08, 0x2f, 0x75, 0x00, 0x00,
// Überspringe Subtraktion, falls p <= 30000
0x7e, 0x07,
// Subtrahiere 30000, falls p >= 30000
//subl $0x7530,-0x8(%ebp)
0x81, 0x6d, -0x08, 0x30, 0x75, 0x00, 0x00
};
bf_store_at_pointer( bf );
// Pointer um amount erhöhen
// addl $amount,-0x8(%ebp)
asm_write_byte( bf->func, 0x81 );
asm_write_byte( bf->func, 0x45 );
asm_write_byte( bf->func, -0x8 );
asm_write_int32( bf->func, amount % 30000 );
asm_write_bytes( bf->func, code, sizeof( code ) );
bf_load_at_pointer( bf );
}
void bf_left( bf_context *bf , int amount ) {
const unsigned char code[] = {
// Vergleiche den Pointer mit 0
// cmpl $0x0,-0x8(%ebp)
0x83, 0x7d, -0x08, 0x00,
// Überspringe Addition, falls >= 0
0x79, 0x07,
// Addiere 30000 auf den Pointer, falls wir < 0 sind
// addl $0x7530,-0xc(%ebp)
0x81, 0x45, -0x08, 0x30, 0x75, 0x00, 0x00,
};
bf_store_at_pointer( bf );
// Pointer um amount verkleinern
// subl $integer,-0x8(%ebp)
asm_write_byte( bf->func, 0x81 );
asm_write_byte( bf->func, 0x6d );
asm_write_byte( bf->func, -0x08 );
asm_write_int32( bf->func, amount % 30000 );
// In grenzen halten
asm_write_bytes( bf->func, code, sizeof( code ) );
bf_load_at_pointer( bf );
}
void bf_loop_start( bf_context *bf ) {
// Block überspringen (default 0, wird in bf_loop_end ergänzt)
// jmp $length
asm_write_byte( bf->func, 0xe9 );
asm_write_int32( bf->func, 0 );
stack_push( bf->loop_stack, (void*)bf->func->code_position );
}
void bf_loop_end( bf_context *bf ) {
int length;
const unsigned char code_compare[] = {
// Vergleiche %eax mit 0.
// cmp $0x00,%eax
0x3d, 0x00, 0x00, 0x00, 0x00
};
if( stack_empty( bf->loop_stack ) ) {
printf( "Klammern nicht ausbalanziert!\n" );
exit( 1 );
}
length = bf->func->code_position - (int)stack_pop( bf->loop_stack );
// Modifiziere den jmp Befehl
memcpy( bf->func->memory + bf->func->linker_size + bf->func->code_position - length - 4, &length, 4 );
// Vergleiche %eax mit 0
asm_write_bytes( bf->func, code_compare, sizeof( code_compare ) );
// Springe wenn %eax != 0 um -(length + sizeof( code_compare ) + 6 ) bytes
// jne -( $length + sizeof( code_compare ) + 6 )
asm_write_byte( bf->func, 0x0f );
asm_write_byte( bf->func, 0x85 );
asm_write_int32( bf->func, -1 * (length + sizeof( code_compare ) + 6) );
asm_write_byte( bf->func, 0x90 );
}
static void bf_load_at_pointer( bf_context *bf ) {
const unsigned char code[] = {
// Kopiere Memory Adresse nach %eax
// mov -0xc(%ebp),%eax
0x8b, 0x45, -0xc,
// addiere Pointer auf %eax vom Stack
// add -0x08(%ebp),%eax
0x03, 0x45, -0x08,
// lade den Wert der Adresse, die in %eax steht, nach %eax
// movsbl %al,%eax
0x0f, 0xb6, 0x00,
// movzbl %al,%eax
0x0f, 0xb6, 0xc0
};
asm_write_bytes( bf->func, code, sizeof( code ) );
}
static void bf_store_at_pointer( bf_context *bf ) {
// Speichere den Wert in %eax
const unsigned char code[] = {
// Verschiebe %eax nach %edx
// mov %eax,%edx
0x89, 0xc2,
// Kopiere Memory Adresse nach %eax
// mov -0xc(%ebp),%eax
0x8b, 0x45, -0xc,
// addiere Pointer auf %eax vom Stack
// add -0x08(%ebp),%eax
0x03, 0x45, -0x08,
// Speichere %dl nach der Adresse in %eax
// mov %dl,(%eax)
0x88, 0x10,
// Verschiebe %edx wieder nach %eax
// mov %edx,%eax
0x89, 0xd0
};
asm_write_bytes( bf->func, code, sizeof( code ) );
}
Und hier noch die Funktionen, die ich benutze um den Bytecode zu schreiben und auszuführen.
asm_function.c
C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "asm_function.h"
#define BUFFER_INCREASE 4096
/**
Kleine Hilfsfunktionen um den Assembler-Code dynamisch zu
speichern und auszuführen
*/
void asm_resize( asm_function *func, int linker, int code );
void asm_link( asm_function *func, void *pointer );
asm_function *asm_create() {
asm_function *func = (asm_function*)malloc( sizeof( asm_function ) );
func->memory = NULL;
func->code_position = 0;
func->code_size = 0;
func->linker_position = 0;
func->linker_size = 0;
asm_resize( func, 0, 4096 );
memset( func->memory, 0, func->linker_size + func->code_size );
return func;
}
void asm_destroy( asm_function *func ) {
if( func ) {
free( func->memory );
free( func );
}
}
void asm_resize( asm_function *func, int linker, int code ) {
int position;
int total_size = func->linker_size + func->code_size + linker + code;
unsigned char *new_memory = realloc( func->memory, total_size );
int offset = ((void*)new_memory + linker) - (void*)(func->memory);
func->memory = new_memory;
if( linker )
memmove( func->memory + linker, func->memory, func->linker_size + func->code_size );
func->linker_size += linker;
func->code_size += code;
func->call = (asm_call_t)(func->memory + func->linker_size);
// falls offset != 0 müssen wir auf alle
// Funktionsaufrufe (jmp-Befehle) im Linker
// offset addieren.
for( position = 5; position < func->linker_size - linker; position += 5 ) {
unsigned char *base = func->memory + func->linker_size - position;
if( *base != 0xe9 )
break;
*(int*)(base + 1) -= offset;
}
}
void asm_write_bytes( asm_function *func, const unsigned char *bytes, int n ) {
if( func->code_size < func->code_position + n )
asm_resize( func, 0, n );
memcpy( func->memory + func->linker_size + func->code_position, bytes, n );
func->code_position += n;
}
void asm_write_byte( asm_function *func, unsigned char byte ) {
if( func->code_size < func->code_position + 1 )
asm_resize( func, 0, BUFFER_INCREASE );
func->memory[ func->linker_size + func->code_position++ ] = byte;
}
void asm_write_int32( asm_function *func, int data ) {
asm_write_bytes( func, (const unsigned char*)&data, 4 );
}
void asm_write_pointer( asm_function *func, void *pointer ) {
if( sizeof( void* ) != 4 )
fprintf( stderr, "achtung: sizof( void* ) != 4, x64 architektur? ungetestet!\n" );
asm_write_bytes( func, (const unsigned char*)&pointer, 4 );
}
void asm_write_call( asm_function *func, void *pointer ) {
if( sizeof( void* ) != 4 )
fprintf( stderr, "achtung: sizof( void* ) != 4, x64 architektur? ungetestet!\n" );
asm_link( func, pointer );
}
void asm_link( asm_function *func, void *pointer ) {
int size = 5;
if( func->linker_position + size >= func->linker_size )
asm_resize( func, BUFFER_INCREASE, 0 );
unsigned char *base = func->memory +
func->linker_size -
func->linker_position - size;
int offset_this = (int)( base - (func->memory + func->linker_size + func->code_position + 5 ) );
int offset_func = (int)( pointer - (void*)(base + 5) );
// wir schreiben in den Linker-code jmp *offset zu pointer*
*base = 0xe9;
memcpy( base + 1, &offset_func, 4 );
func->linker_position += size;
// und schrieben in den normalen code: spring zu mir!
asm_write_byte( func, 0xe8 );
asm_write_int32( func, offset_this );
}
Anhänge
Zuletzt bearbeitet: