[QUIZ#3] OnlyFoo (C + x86-Assembler)

[OnlyFoo]

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

#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

#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

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

 

[OnlyFoo]

Muhar, nochmal drei mal schneller als vorher! Die Mandelbrot Menge wird nun in unter 2 Sekunden berechnet! Das alles duch viel besseren (und viel kürzeren) Assembler Code.

olli@desktop:~/work/quiz3$ time ./quiz3 mandelbrot.b > /dev/null

real    0m1.964s
user    0m1.952s
sys     0m0.004s

Und die Klausur hab ich bestanden, wo ich statt zu lernen lieber Programmiert hab