// Jonathan Frech, 18th, 19th, 20th, 31st of August, 2nd, 5th, 6th, 7th, 8th of September 2018
// A brainfuck interpreter written in C.

#define VERSION "Alpha 1.0"

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

enum condensed_instruction_type { NOP, MOV, ADD, JMP, PMJ, INP, OUT, DBG };
struct condensed_instruction {
    enum condensed_instruction_type instruction;
    int64_t property; // multiplicity, jump_target or DBG_index
};

FILE *source_file = NULL;
char *source_filename = NULL;

bool opt_help = false;
bool opt_output_condensed_code = false;
bool opt_no_color = false;
bool opt_no_debug = false;
bool opt_no_input = false;
bool opt_interactive = false;
bool opt_hexdump = false;

// condensed brainfuck code
int64_t code_size = 0xff;
struct condensed_instruction *code = NULL;

// parentheses stack to match loop parts
int64_t parentheses_stack_size = 0xff;
int64_t *parentheses_stack = NULL;

// brainfuck input
int64_t input_size = 0xff;
u_int8_t *input = NULL;

// brainfuck tape
int64_t tape_size = 0xff;
u_int8_t *tape = NULL;

// brainfuck output
int64_t output_size = 0xff;
u_int8_t *output = NULL;

void cleanup() {
    free(code), code = NULL;
    free(parentheses_stack), parentheses_stack = NULL;
    free(input), input = NULL;
    free(tape), tape = NULL;
    free(output), output = NULL;
    
    if (source_file != NULL)
        fclose(source_file);
}





#define ERROR(...)\
    return cleanup(), fprintf(stderr, "Error: " __VA_ARGS__), putchar('\n'), EXIT_FAILURE;\

// safe malloc wrapper
#define INITIALIZE_ARRAY(array, size) {\
    array = malloc(size * sizeof *array);\
    if (array == NULL)\
        ERROR("Memory allocation failed.")\
}

// safe calloc wrapper
#define INITIALIZE_CLEARED_ARRAY(array, size) {\
    array = calloc(size, sizeof *array);\
    if (array == NULL)\
        ERROR("Memory allocation failed.")\
}

// double an array's size
#define EXPAND_ARRAY(array, size) {\
    int64_t new_size = (size_t) (size*2);\
    if (new_size <= size)\
        ERROR("Size expansion failed.")\
    void *new_array = realloc(array, new_size * sizeof *array);\
    if (new_array == NULL)\
        ERROR("Memory reallocation failed.")\
    array = new_array;\
    size = new_size;\
}

// truncate an array to its minimum required size
#define TRUNCATE_ARRAY(array, size) {\
    if (size > 0) {\
        void *truncated_array = realloc(array, size * sizeof *array);\
        if (truncated_array == NULL)\
            ERROR("Memory reallocation failed whilst truncating.")\
        array = truncated_array;\
    }\
    else\
        free(array), array = NULL;\
}





void print_help() {
    printf(
        "\n"
        "A brainfuck interpreter written in C.\n"
        "Version %s, written by Jonathan Frech, 2018.\n"
        "Negative indices are supported, the tape does not wrap. All cells are 8 bits wide.\n"
        "Input exhaustion is interpreted as a never ending stream of NUL bytes.\n"
        "Both source file input embedding ('!') and debug break points ('#') are supported.\n"
        "\n"
        "    -h, --help             : Print this help screen.\n"
        "\n"
        "    -i, --interactive      : Interactive program execution. Ignores source code input\n"
        "                             and debug break points. Incompatible with '--hex'.\n"
        "    -x, --hexdump          : Display output as hexadecimal dump. Incompatible with '--interactive'.\n"
        "\n"
        "    --output-condensed-code: Output internal condensed code.\n"
        "\n"
        "    --no-color             : Do not use output in color.\n"
        "    --no-input             : Ignore source code input ('!').\n"
        "    --no-debug             : Ignore debug break points ('#').\n"
        "\n", VERSION
    );
}

void print_tape(int64_t tape_index, int64_t tape_shift) {
    printf("Tape: {...");
    for (int64_t j = tape_index-20; j <= tape_index+20; j++) {
            if (opt_no_color) {
                if (j == tape_index)
                    printf("[");
            }
            else {
                if (j % 2 == 0)
                    printf("\033[2m");
                if (j == tape_index)
                    printf("\033[7m");
            }
            
            if (0 <= j && j < tape_size)
                printf("%02X", tape[j]);
            else
                printf("00");
            
            if (opt_no_color) {
                if (j == tape_index)
                    printf("]");
            }
            else
                printf("\033[0m");
    }
    printf("...}\n");
}

void print_condensed_code() {
    printf("Condensed code: {");
    for (int64_t j = 0; j <= code_size; j++) {
        struct condensed_instruction ci = code[j];
        switch (ci.instruction) {
            case NOP: printf("NOP"                  ); break;
            case MOV: printf("MOV(%ld)", ci.property); break;
            case ADD: printf("ADD(%ld)", ci.property); break;
            case JMP: printf("JMP(%ld)", ci.property); break;
            case PMJ: printf("PMJ(%ld)", ci.property); break;
            case INP: printf("INP(%ld)", ci.property); break;
            case OUT: printf("OUT(%ld)", ci.property); break;
            case DBG: printf("DBG(%ld)", ci.property); break;
        }
        if (j != code_size)
            printf(", ");
    }
    printf("}\n");
}

void print_output() {
    if (!opt_hexdump) {
        for (int64_t j = 0; j < output_size; j++)
            putchar(output[j]);
        
        return;
    }
    
    for (int64_t line = 0; line < output_size/16+(output_size%16?1:0); line++) {
        printf("%08x: ", line*16);
        
        for (int64_t block = 0; block < 8; block++) {
            for (int64_t byte = 0; byte < 2; byte++) {
                int64_t j = line*16 + block*2 + byte;
                if (j < output_size)
                    printf("%02x", output[j]);
                else
                    printf("  ");
            }
            printf(" ");
        }
        
        printf(" ");
        
        for (int64_t block = 0; block < 8; block++) {
            for (int64_t byte = 0; byte < 2; byte++) {
                int64_t j = line*16 + block*2 + byte;
                if (j < output_size)
                    if (isprint(output[j]))
                        printf("%c", output[j]);
                    else
                        printf(".");
                else
                    printf(" ");
            }
        }
        
        printf("\n");
    }
}





int open_source_file() {
    if (source_filename == NULL)
        ERROR("No filename specified.")
    
    source_file = fopen(source_filename, "rb");
    if (source_file == NULL)
        ERROR("Could not open file \"%s\".", source_filename)
    
    return EXIT_SUCCESS;
}

int parse() {
    if (code_size < 1 || parentheses_stack_size < 1 || input_size < 1)
        ERROR("Initial array size too small.")
    
    int64_t code_index = 0;
    INITIALIZE_ARRAY(code, code_size);
    
    int64_t parentheses_stack_index = 0;
    INITIALIZE_ARRAY(parentheses_stack, parentheses_stack_size);
    
    int64_t input_index = 0;
    INITIALIZE_ARRAY(input, input_size);
    
    // prime code array with a NOP
    code[code_index] = (struct condensed_instruction) { .instruction = NOP };
    
    // switch between brainfuck source and its input by using an exclamation point ('!')
    bool reading_input = false;
    
    // debug statement's index
    int64_t debug_index = 0;
    
    
    
    for (int16_t chr = EOF; (chr = fgetc(source_file)) != EOF; ) {
        #define CONDENSE_INSTRUCTION(INSTR, property_delta) {\
            if (code[code_index].instruction == INSTR)\
                code[code_index].property += property_delta;\
            else\
                code[++code_index] = (struct condensed_instruction) { .instruction = INSTR, .property = property_delta};\
        }
        
        if (reading_input)
            input[input_index++] = chr;
        
        else if (chr == '+') CONDENSE_INSTRUCTION(ADD,  1)
        else if (chr == '-') CONDENSE_INSTRUCTION(ADD, -1)
        else if (chr == '>') CONDENSE_INSTRUCTION(MOV,  1)
        else if (chr == '<') CONDENSE_INSTRUCTION(MOV, -1)
        else if (chr == '.') CONDENSE_INSTRUCTION(OUT,  1)
        else if (chr == ',') CONDENSE_INSTRUCTION(INP,  1)
        else if (chr == '[') {
            code[++code_index] = (struct condensed_instruction) { .instruction = JMP };
            parentheses_stack[parentheses_stack_index++] = code_index;
        }
        else if (chr == ']') {
            if (parentheses_stack_index <= 0)
                ERROR("Unmatched loop end.")
            int64_t parentheses_match = parentheses_stack[--parentheses_stack_index];
            code[
                code[parentheses_match].property = ++code_index
            ] = (struct condensed_instruction) { .instruction = PMJ, .property = parentheses_match };
        }
        
        else if (chr == '#' && !opt_interactive && !opt_no_debug)
            code[++code_index] = (struct condensed_instruction) { .instruction = DBG, .property = debug_index++ };
        else if (chr == '!' && !opt_interactive && !opt_no_input)
            reading_input = true;
        
        #undef CONDENSE_INSTRUCTION
        
        // assure array sizes
        if (code_index >= code_size-1)
            EXPAND_ARRAY(code, code_size)
        if (parentheses_stack_index >= parentheses_stack_size)
            EXPAND_ARRAY(parentheses_stack, parentheses_stack_size)
        if (input_index >= input_size)
            EXPAND_ARRAY(input, input_size)
    }
    
    
    
    // all parentheses should be matched
    if (parentheses_stack_index != 0)
        ERROR("Unmatched loop start.")
    else
        free(parentheses_stack), parentheses_stack = NULL;
       
    // truncate arrays to appropriate size
    code_size = code_index+1;
    TRUNCATE_ARRAY(code, code_size);
    input_size = input_index;
    if (input_size > 0 && input[input_size-1] == '\n')
        input_size--;
    TRUNCATE_ARRAY(input, input_size);
    
    if (opt_output_condensed_code)
        print_condensed_code();
   
    return EXIT_SUCCESS;
}

int parse_arguments(int argc, char *argv[]) {
    bool expecting_flags = true;
    
    for (int64_t v = 0; ++v < argc; ) {
        char *arg = argv[v];
        
        // flag
        if (expecting_flags && arg[0] == '-') {
            // multi-character flag
            if (arg[1] == '-')
                if (strcmp(arg, "--") == 0)
                    expecting_flags = false;
                else if (strcmp(arg, "--help") == 0)
                    return opt_help = true, EXIT_SUCCESS;
                else if (strcmp(arg, "--interactive") == 0)
                    opt_interactive = true;
                else if (strcmp(arg, "--hexdump") == 0)
                    opt_hexdump = true;
                else if (strcmp(arg, "--output-condensed-code") == 0)
                    opt_output_condensed_code = true;
                else if (strcmp(arg, "--no-color") == 0)
                    opt_no_color = true;
                else if (strcmp(arg, "--no-input") == 0)
                    opt_no_input = true;
                else if (strcmp(arg, "--no-debug") == 0)
                    opt_no_debug = true;
                else
                    ERROR("Unrecognized option \"%s\".", arg)
            
            // single character flag
            else if (arg[1])
                for (int64_t j = 1; arg[j]; j++) {
                    char f = arg[j];
                    
                    if (f == 'h')
                        return opt_help = true, EXIT_SUCCESS;
                    else if (f == 'i')
                        opt_interactive = true;
                    else if (f == 'x')
                        opt_hexdump = true;
                    else
                        ERROR("Unrecognized option \"-%c\".", f)


                }
            
            else
                ERROR("Unrecognized option \"-\" (a single dash).")
        }
        
        // non-flag options: source filename
        else
            if (source_filename == NULL)
                source_filename = arg;
            else
                ERROR("Unrecognized option \"%s\".", arg)
    }
    
    if (opt_interactive && opt_hexdump)
        ERROR("Conflicting flags '--interactive' and '--hex'.")
    
    return EXIT_SUCCESS;
}





int interpret() {
    // assure minimum array size
    if (tape_size < 1 || output_size < 1)
        ERROR("Initial array size too small.")
    
    // assure the existence of vital arrays
    if (!code)
        ERROR("Vital arrays not present.")
    
    // initialize brainfuck input index
    int64_t input_index = 0;
    
    // initialize tape array
    // note: tape_index can be temporarily negative
    int64_t tape_index = tape_size/2;
    int64_t tape_shift = 0;
    INITIALIZE_CLEARED_ARRAY(tape, tape_size)
    
    // initialize output array
    int64_t output_index = 0;
    if (!opt_interactive)
        INITIALIZE_ARRAY(output, output_size)
    
    // execute condensed instructions
    for (int64_t code_index = 0; code_index < code_size; code_index++) {
        struct condensed_instruction ci = code[code_index];
        
        if (ci.instruction == ADD)
            tape[tape_index] += (u_int8_t) ci.property;
        else if (ci.instruction == MOV)
            tape_index += ci.property;
        else if (ci.instruction == JMP && !tape[tape_index])
            code_index = ci.property;
        else if (ci.instruction == PMJ && tape[tape_index])
            code_index = ci.property;
        else if (ci.instruction == OUT)
            for (int _ = 0; _ < ci.property; _++) {
                if (opt_interactive)
                    putchar(tape[tape_index]);
                else {
                    output[output_index++] = tape[tape_index];
                    
                    if (output_index >= output_size)
                        EXPAND_ARRAY(output, output_size)
                }
            }
        else if (ci.instruction == INP)
            if (opt_interactive)
                for (int64_t _ = 0; _ < ci.property; _++) {
                    int16_t c = getchar();
                    tape[tape_index] = (c != EOF ? (u_int8_t) c : 0);
                }
            else {
                // skip unnecessary input instructions (since the tape index will not change)
                input_index += ci.property-1;
                
                if (input_index >= input_size)
                    tape[tape_index] = 0;
                else
                    tape[tape_index] = input[input_index++];
            }
        else if (ci.instruction == DBG) {
            printf("(Break point #%ld) ", ci.property);
            print_tape(tape_index, tape_shift);
        }
        
        // attempt expand tape array to the left or right as long as necessary
        while (tape_index < 0 || tape_index >= tape_size) {
            int64_t old_tape_size = tape_size;
            EXPAND_ARRAY(tape, tape_size)
            
            // expand on the left; shift old array segment to new array segment's right, flush with zeros
            if (tape_index < 0) {
                memmove(tape+old_tape_size, tape, old_tape_size * sizeof *tape);
                memset(tape, 0, old_tape_size * sizeof *tape);
                tape_index += old_tape_size;
                tape_shift -= old_tape_size;
            }
            
            // expand on the right; flush new array segment with zeros
            else if (tape_index >= old_tape_size)
                memset(tape+old_tape_size, 0, old_tape_size * sizeof *tape);
        }
    }
    
    free(code), code = NULL;
    free(input), input = NULL;
    free(tape), tape = NULL;
    
    output_size = output_index;
    TRUNCATE_ARRAY(output, output_size)
    
    print_output();
        free(output), output = NULL;
    
    return EXIT_SUCCESS;
}





int main(int argc, char *argv[]) {
    if (parse_arguments(argc, argv) != EXIT_SUCCESS)
        return EXIT_FAILURE;
    if (opt_help)
        return print_help(), EXIT_SUCCESS;
    
    if (open_source_file() != EXIT_SUCCESS)
        return EXIT_FAILURE;
    
    if (parse() != EXIT_SUCCESS)
        return EXIT_FAILURE;
    
    if (interpret() != EXIT_SUCCESS)
        return EXIT_FAILURE;
    
    // exit cleanly
    return cleanup(), EXIT_SUCCESS;
}