JIT Brainfuck

jit-bf.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DEBUG

#ifdef DEBUG
    unsigned char *mem;
    int mem_size;
#endif

typedef struct BiteCode {
    int opecode;
    int operand;
    struct BiteCode *back;
    struct BiteCode *next;
    struct BiteCode *loop_connection;
} BiteCode;

BiteCode *bc_append(BiteCode *bitecode, int opecode, int operand)
{
    if((bitecode->next = malloc(sizeof(BiteCode))) == NULL){
        return NULL;
    }
    bitecode->next->opecode = opecode;
    bitecode->next->operand = operand;
    bitecode->next->back = bitecode;
    bitecode->next->next = NULL;
    bitecode->next->loop_connection = NULL;
    return loop_connect(bitecode->next);
}

BiteCode *loop_connect(BiteCode *bitecode)
{
    BiteCode *top = bitecode;
    BiteCode *p = bitecode;
    int nest_flag = 0;
    
    if(now->opecode != ']'){
        return top;
    }
    
    while(p != NULL){
        if(p->operand == ']'){
            nest_flag++;
        }
        if(p->operand == '['){
            nest_flag--;
            if(nest_flag == 0){
                top->loop_connection = p;
                p->loop_connection = top;
                return top;
            }
        }
        p = p->back;
    }
    return top;
}

int bc_free(BiteCode *bitecode)
{
    if(bitecode == NULL){
        return 1;
    }
    bc_free(bitecode->next);
    free(bitecode);
    return 1;
}

int mem_need_size(BiteCode *bc)
{
    int counter = 1;
    int max = 1;
    while(bc != NULL){
        switch(bc->opecode){
        case '>':
            counter += bc->operand;
            break;
        case '<':
            if(counter > max) max = counter;
            counter -= bc->operand;
            break;
        }
        bc = bc->next;
    }
    if(counter > max) max = counter;
    return max;
}

unsigned char *compile(BiteCode *bc)
{
    // x86 Opecodes
    unsigned char MOV_DL = 0xB2;
    unsigned short int MOV_address_DL = 0x1588;
    unsigned short int MOV_DL_address = 0x158A;
    unsigned short int ADD_DL = 0xC280;
    unsigned short int SUB_DL = 0xEA80;
    unsigned char RET = 0xC3;
    
    // When memory was written, plant this flag
    int wrote_flag = 0;
    
    // Machine codes was written to area of memory
    unsigned char *buf = malloc(sizeof(char) * 50);
    int i = 0;
    int buf_size = 50;
    
    // When machine codes run, this area will be used
#ifndef DEBUG
    int mem_size;
    unsigned char *mem = calloc((mem_size = mem_need_size(bc)), sizeof(char));
#endif
    int p = 0;
    
    // Temporary variable
    unsigned char byte = 0;
    unsigned short int word = 0;
    unsigned int dword = 0;
    
#ifdef DEBUG
    mem = calloc((mem_size = mem_need_size(bc)), sizeof(char));
#endif
    
    while(bc != NULL){
        if(buf_size - i < 20){
            buf = realloc(buf, sizeof(char) * (buf_size += 50));
        }
        switch(bc->opecode){
            case '+':
                wrote_flag = 1;
                
                memcpy(buf + i, &ADD_DL, sizeof(short int));
                i += sizeof(short int);
                byte = (unsigned char)bc->operand;
                memcpy(buf + i, &byte, sizeof(char));
                i += sizeof(char);
                
                break;
            case '-':
                wrote_flag = 1;
                
                memcpy(buf + i, &SUB_DL, sizeof(short int));
                i += sizeof(short int);
                byte = (unsigned char)bc->operand;
                memcpy(buf + i, &byte, sizeof(char));
                i += sizeof(char);
                
                break;
            case '>':
                if(wrote_flag){
                    memcpy(buf + i, &MOV_address_DL, sizeof(short int));
                    i += sizeof(short int);
                    dword = (unsigned int)(mem + p);
                    memcpy(buf + i, &dword, sizeof(int));
                    i += sizeof(int);
                }
                
                p += bc->operand;
                
                memcpy(buf + i, &MOV_DL_address, sizeof(short int));
                i += sizeof(short int);
                dword = (unsigned int)(mem + p);
                memcpy(buf + i, &dword, sizeof(int));
                i += sizeof(int);
                
                wrote_flag = 0;
                break;
            case '<':
                if(wrote_flag){
                    memcpy(buf + i, &MOV_address_DL, sizeof(short int));
                    i += sizeof(short int);
                    dword = (unsigned int)(mem + p);
                    memcpy(buf + i, &dword, sizeof(int));
                    i += sizeof(int);
                }
                
                p -= bc->operand;
                
                memcpy(buf + i, &MOV_DL_address, sizeof(short int));
                i += sizeof(short int);
                dword = (unsigned int)(mem + p);
                memcpy(buf + i, &dword, sizeof(int));
                i += sizeof(int);
                
                wrote_flag = 0;
                break;
            case '.':
            case ',':
            case '[':
                /*** here machine code ***/
                /* cmp DL , 0 */
                /* jz [bc->loop_connection] */
            case ']':
                /*** here machine code ***/
                /* cmp DL , 0 */
                /* jnz [bc->loop_connection] */
            default: break;
        }
        bc = bc->next;
    }
    
    if(wrote_flag){
        memcpy(buf + i, &MOV_address_DL, sizeof(short int));
        i += sizeof(short int);
        dword = (unsigned int)(mem + p);
        memcpy(buf + i, &dword, sizeof(int));
        i += sizeof(int);
    }
    buf[i] = RET;
    return buf;
}

int run(unsigned char *buf)
{
    int i;
    int j;
    void (*code)(void) = buf;
    for(i = 0;i < 30;i++){
        printf("%x ", buf[i]);
    }
    printf("\n");
    code();
    printf("run:end\n");
#ifdef DEBUG
    printf("mem_size : %d\n", mem_size);
    for(j = 0;j < mem_size;j++){
        printf("%x ", mem[j]);
    }
#endif
}

int main(int argc, char *argv[])
{
    char *filename = argv[1];
    FILE *fp = NULL;
    
    char c;
    char opecode;
    int counter = 0;
    int loop_id = 0;
    
    char *buf;
    
#ifdef DEBUG
    BiteCode *p = NULL;
#endif
    
    BiteCode *start;
    BiteCode *next;
    BiteCode *bitecode = malloc(sizeof(BiteCode));
    bitecode->opecode = 0;
    bitecode->operand = 0;
    bitecode->next = NULL;
    start = bitecode;
    
    if(argc < 2){
        printf("error:argv\n");
        return 0;
    }
    if((fp = fopen(filename, "r")) == NULL){
        printf("error:can't open file:%s\n", filename);
        return 0;
    }
    
    while((c = fgetc(fp)) != EOF){
        CONTINUE:
        switch(c){
            case '+':
            case '-':
            case '>':
            case '<':
                opecode = c;
                counter = 1;
                while((c = fgetc(fp)) != EOF){
                    if(c != opecode){
                        bitecode = bc_append(bitecode, opecode, counter);
                        goto CONTINUE;
                    }
                    counter++;
                }
                break;
            case '.':
            case ',':
                bitecode = bc_append(bitecode, c, 0);
                break;
            case '[':
                loop_id++;
                bitecode = bc_append(bitecode, c, loop_id);
                break;
            case ']':
                loop_id--;
                bitecode = bc_append(bitecode, c, loop_id);
                break;
        }
    }
    
    fclose(fp);
#ifdef DEBUG
    p = start;
    while(p != NULL){
        printf("[%c, %x] ", p->opecode, p->operand);
        p = p->next;
    }
#endif
    run(buf = compile(start->next));
    free(buf);
    bc_free(bitecode);
    return 0;
}