#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <stdint.h>
#include <string.h>
#include <unistd.h>

// -------------- config

#define MAX_AREA 10000 //Determine the initial max_area
#define NUM_INPUTS 4 //speaks for itself
#define MAX_GATES 3 // determine the max_amount of gates
#define NUM_THREADS 4 //Needs to be <= 9 or 18 or 27 for efficient splitting the work load

#define use_truth_table 1 //If 1 use the truth table below. If multiple outputs then paste the truth table after another from the [file].truth
#define target_truth_table "00000000"
//#define target_truth_table "11101000" //exampe here [Target A][Target B] pasted after another. 
//MAJ testing



//#define target_truth_table "1110100010010110"
//half adder
/*
The truth table matching this is that of a increase in value of the input variables
Let's say 3 input variables

I3 I2 I1   | O2 O1
A, B, Cin, | S Cout 
0, 0,   0, | 0 0
0, 0,   1, | 1 0
0, 1,   0, | 1 0
0, 1,   1, | 0 1
1, 0,   0, | 1 0
1, 0,   1, | 0 1
1, 1,   0, | 0 1
1, 1,   1, | 1 1

S =     10010110
Cout =  11101000
MUX =   11001010
target_truth_table = "S Cin" = "1110100010010110"
also means that output B
*/
//AND = &&, OR = ||, XOR = ^, NOT = !
int target_function(int inputs[]) {
    return inputs[0] ^ inputs[1];
}

// -------------- Auto-define

#define NUM_COMBINATION (1 << NUM_INPUTS)
#define NUM_OUTPUTS (sizeof(target_truth_table)-1)/NUM_COMBINATION

// -------------- structs

typedef struct {
    char* type;
    int area;
} GateType;

typedef struct {
    GateType* gate;
    int8_t in1;
    int8_t in2;
    int8_t in3;
    int8_t in4;
} Gate;

typedef struct {
    Gate gates[MAX_GATES];
    int8_t gate_count;
    int area;
} Circuit;

typedef struct {
    Circuit volatile best_circuit;
    GateType *gate_types;
    int num_inputs;
    int num_gates;
    int volatile best_area;
    int8_t  *truth_table;
    int8_t  *target_outputs;
    int worker_id;
    int num_circuit[2]; //first is the amount in million  and the second is the increment counter.
    pthread_mutex_t mutex;
} ThreadArgs;


// -------------- define used gates
GateType gate_types[] = {
    {"INV", 1160},
    {"MUX-XOR", 1288}
};

// -------------- start functions
void tee(FILE *f, char const *fmt, ...) { 
    va_list ap;
    va_start(ap, fmt);
    vprintf(fmt, ap);
    va_end(ap);
    va_start(ap, fmt);
    vfprintf(f, fmt, ap);
    va_end(ap);
}

void print_circuit(Circuit * circuit){
    FILE *fptr;

    fptr = fopen("./output/output_bruteforce.txt", "a");

    //for(int y=0; y<circuit->gate_count; y++){
    //    printf("%d: %s, in1: %d, in2: %d, in3: %d\n",y,circuit->gates[y].gate->type,circuit->gates[y].in1,circuit->gates[y].in2,circuit->gates[y].in3);
    //}

    tee(fptr,"---------- Circuit area: %d ----------\n",circuit->area);
    tee(fptr,"Input ");
    for(int i='a';(i-'a')<NUM_INPUTS;i++){tee(fptr,"%c, ",i);}
    tee(fptr,"\n");

    for(int y=0; y<circuit->gate_count; y++){
        int print_in1 = circuit->gates[y].in1 + '0';
        int print_in2 = circuit->gates[y].in2 + '0';
        int print_in3 = circuit->gates[y].in3 + '0';
        int print_in4 = circuit->gates[y].in4 + '0';
        if((print_in1-2-'0')<NUM_INPUTS && (print_in1-2-'0')>=0){
         print_in1 = circuit->gates[y].in1-2 + 'a';
        }
        if((print_in2-2-'0')<NUM_INPUTS && (print_in2-2-'0')>=0){
         print_in2 = circuit->gates[y].in2-2 + 'a';
        }
        if((print_in3-2-'0')<NUM_INPUTS && (print_in3-2-'0')>=0){
         print_in3 = circuit->gates[y].in3-2 + 'a';
        }
        if((print_in4-2-'0')<NUM_INPUTS && (print_in4-2-'0')>=0){
         print_in4 = circuit->gates[y].in4-2 + 'a';
        }
        
        tee(fptr,"%d: %s, in1: %c, in2: %c, in3: %c, in4: %c\n",y+NUM_INPUTS+2,circuit->gates[y].gate->type,print_in1,print_in2,print_in3,print_in4);
    }
    
    tee(fptr,"Output ");
    for(int i='x';(i-'x')<NUM_OUTPUTS;i++){tee(fptr,"%c:%lu, ",i,NUM_INPUTS+circuit->gate_count-NUM_OUTPUTS+(i-'x')+2);}
    tee(fptr,"\n");
    tee(fptr,"----------------------------------------\n");
    fclose(fptr);
}

void write_circuit_to_file(Circuit * circuit, int area, int worker_number, int file_number){
    FILE *fptr;

    char file_name[100];
    sprintf(file_name, "./output/output_%d_%d_%d_bruteforce.dot", area, worker_number, file_number);

    fptr = fopen(file_name, "w");

    //for(int y=0; y<circuit->gate_count; y++){
    //    printf("%d: %s, in1: %d, in2: %d, in3: %d\n",y,circuit->gates[y].gate->type,circuit->gates[y].in1,circuit->gates[y].in2,circuit->gates[y].in3);
    //}
    fprintf(fptr, "digraph Circuit {\n  rankdir=LR; // Makes the graph left-to-right\n  node [shape=ellipse]; // Default shape for nodes\n ranksep=2; // Increases vertical separation\n");


    for(int i='a';(i-'a')<NUM_INPUTS;i++){fprintf(fptr,"  %c [ shape=octagon, label=\"%c\", color=\"black\", fontcolor=\"black\"]; \n",i,i);}


    for(int y=0; y<circuit->gate_count; y++){
        int print_in1 = circuit->gates[y].in1 + '0';
        int print_in2 = circuit->gates[y].in2 + '0';
        int print_in3 = circuit->gates[y].in3 + '0';
        int print_in4 = circuit->gates[y].in4 + '0';
        if((print_in1-2-'0')<NUM_INPUTS && (print_in1-2-'0')>=0){
         print_in1 = circuit->gates[y].in1-2 + 'a';
        }
        if((print_in2-2-'0')<NUM_INPUTS && (print_in2-2-'0')>=0){
         print_in2 = circuit->gates[y].in2-2 + 'a';
        }
        if((print_in3-2-'0')<NUM_INPUTS && (print_in3-2-'0')>=0){
         print_in3 = circuit->gates[y].in3-2 + 'a';
        }
        if((print_in4-2-'0')<NUM_INPUTS && (print_in4-2-'0')>=0){
         print_in4 = circuit->gates[y].in4-2 + 'a';
        }

        int unit_number = y+NUM_INPUTS+2;
        fprintf(fptr,"  %d [ shape=record, label=\"{{<p1> ==|<p3> XOR 0|<p4> XOR 1|<p2> !=}| MUX-XOR %d |{<p4> Y}}\", color=\"darkred\", fontcolor=\"darkred\" ];\n",unit_number,unit_number);
        fprintf(fptr,"  %c:e -> %d:p1;\n  %c:e -> %d:p2;\n  %c:e -> %d:p3;\n %c:e -> %d:p4;\n",print_in1,unit_number,print_in2,unit_number,print_in3,unit_number,print_in4,unit_number);
    }
    
    for(int i='x';(i-'x')<NUM_OUTPUTS;i++){fprintf(fptr,"  %lu:e -> %c;\n",NUM_INPUTS+circuit->gate_count-NUM_OUTPUTS+(i-'x')+2,i);}
    

    fprintf(fptr,"}\n");
    fclose(fptr);
}

void evaluate_circuit(GateType* all_gates, Circuit* circuit, int8_t* inputs, int8_t* outputs) {
    int8_t intermediate_outputs[NUM_INPUTS + MAX_GATES+2];
    intermediate_outputs[0] = 0; //Make sure that intermediate_outputs[0] = 0 and [1] = 1 for constant signal attachments
    intermediate_outputs[1] = 1;
    memcpy(&intermediate_outputs[2], inputs, NUM_INPUTS * sizeof(int8_t)); //copy boolean value over this

    for (int i = 0; i < circuit->gate_count; i++) {
        int out1 = intermediate_outputs[circuit->gates[i].in1];
        int out2 = intermediate_outputs[circuit->gates[i].in2];
        int out3 = intermediate_outputs[circuit->gates[i].in3];
        int out4 = intermediate_outputs[circuit->gates[i].in4];
        int output = 0;

        if (circuit->gates[i].gate ==  &all_gates[0]) //INV
            output =  ~out1 & 1;
        else if (circuit->gates[i].gate ==  &all_gates[1]) //MUX-XOR
            output = (out4^out3) ? out2 : out1;

        intermediate_outputs[NUM_INPUTS + i + 2] = output;
    }

    for(int z=0; z<NUM_OUTPUTS;z++){
        outputs[z] = intermediate_outputs[NUM_INPUTS + 2 + circuit->gate_count-NUM_OUTPUTS+z];
    }
}

int detect_tautology(Circuit *current_circuit, int in1, int in2, int in3, int in4, int gate_selected, ThreadArgs *data){
    if ((in1 == in2 && gate_selected != 0) ||
        //(in1 == in3 || in2 == in3) ||
        (in3 == in4)){ 
        //(in1 == 0 && in2 == 1 && gate_selected != 0) ){ //|| //Skip gate if it has the same input both ports NOTE THAT IF i == 0 THEN WE SELECT INV.
        return 1;
    }
    

    for(int i=0; i<(current_circuit->gate_count-1);i++){
        if(current_circuit->gates[i].gate == &data->gate_types[gate_selected]){
            if(current_circuit->gates[i].in1 == in1 && current_circuit->gates[i].in2 == in2 && current_circuit->gates[i].in3 == in3){
                return 1; //DETECTED A COMPLETE equivalent circuit
            }
        }
    }

    int input_used[current_circuit->gate_count + data->num_inputs+2];
    memset(input_used, 0, sizeof(input_used));

    input_used[0] = 1; //make sure that the constant don't trigger a faulty tautology result.
    input_used[1] = 1;

    for(int i=0; i<current_circuit->gate_count; i++){
        input_used[current_circuit->gates[i].in1] = 1;
        input_used[current_circuit->gates[i].in2] = 1;
        input_used[current_circuit->gates[i].in3] = 1;
    }

    input_used[in1] = 1;
    input_used[in2] = 1;
    input_used[in3] = 1;
    input_used[in4] = 1;

    for(int i=0; i < (current_circuit->gate_count + data->num_inputs - NUM_OUTPUTS+2); i++){
        if(input_used[i]==0 && current_circuit->gate_count!=0){
            return 2; //missing an used output
        }
    }

    return 0;
}

void generate_circuits_recursive(Circuit *current_circuit, int depth, ThreadArgs *data) {
    if (depth == data->num_gates){
        // Reached end of amount of gates. 
        return;
    }

    GateType* gate_types = data->gate_types;

    // Loop through gate types and inputs to build possible circuits
    //int num_gate_types = 1;
    //int division = (num_gate_types + NUM_THREADS-1)/NUM_THREADS;
    //int multi_core_division=NUM_THREADS/num_gate_types;
    //0 - 2, 3 - 5, 6 - 8
    //for (int i = 0; i < num_gate_types; i++) {
    int i = 1; //Only select the multiplexer

    if((current_circuit->area+data->gate_types[i].area)>data->best_area){
        //printf("worker %d: area %d on gate type %d and depth %d larger then best area %d continueing\n",data->worker_id,current_circuit->area,i,depth,data->best_area);
        return;
    }

    for (int in4 = 0; in4 < depth + data->num_inputs + 2; in4++){
        for (int in3 = 0; in3 < depth + data->num_inputs + 2; in3++){

            //Going for multithread approach
            if(in3 != data->worker_id+2 && depth == 0){
                continue;
            }

            for (int in2 = 0; in2 < depth + data->num_inputs + 2; in2++) {
                for (int in1 = 0; in1 < depth + data->num_inputs + 2; in1++){
                    data->num_circuit[0] += 1;



                    // Add the new gate to the circuit
                    current_circuit->gates[depth].gate = &gate_types[i]; //set pointer to the type of gate
                    current_circuit->gates[depth].in1 = in1;
                    current_circuit->gates[depth].in2 = in2;
                    current_circuit->gates[depth].in3 = in3;
                    current_circuit->gates[depth].in4 = in4;
                    current_circuit->gate_count = depth + 1;

                    //if(current_circuit->gates[0].in1 == 0 && current_circuit->gates[0].in2 == 1 && current_circuit->gates[0].in3 == 3 && current_circuit->gates[1].in1 == 2 && current_circuit->gates[1].in2 == 3 && current_circuit->gates[1].in3 == 4 && current_circuit->gates[2].in1 == 4 && current_circuit->gates[2].in2 == 5 && current_circuit->gates[2].in3 == 6){// && current_circuit->gates[2].gate==&data->gate_types[6]){
                    //if(current_circuit->gates[0].in1 == 2 && current_circuit->gates[0].in2 == 3 && current_circuit->gates[0].in3 == 4){
                    //    printf("test\n");
                    //}

                    int tautology = detect_tautology(current_circuit,in1,in2,in3,in4,i,data); //0: nothing found, 1: direct tautology, 2:unconnected device may still be connected.
                    if(tautology==1){
                        continue; //Found already unnecessary combo and should skip it
                    }


                    int valid = 0;

                    if(tautology!=2){ //There is an unconnected gate if this holds true
                        valid = 1;
                        int8_t output[NUM_OUTPUTS];
                        for (int y=0; y < (1 << data->num_inputs); y++){ //CHECK IF IT IS VALID
                            evaluate_circuit(data->gate_types, current_circuit, &data->truth_table[y*data->num_inputs], output);
                            for(int z=0; z<NUM_OUTPUTS;z++){
                                if(output[z]!=data->target_outputs[y+NUM_COMBINATION*z]){
                                    valid = 0;
                                }
                            }
                        }
                    }
                    //valid circuit add area
                    current_circuit->area += gate_types[i].area;  // Example area increment (modify as needed)
                    
                    if(data->num_circuit[0]%1000000000 == 0){
                        data->num_circuit[1] += 1;
                        data->num_circuit[0] = 0;
                        printf("%d:At circuit number %d M current best_area %d and tested area %d\n",data->worker_id,data->num_circuit[1],data->best_area,current_circuit->area);
                    }

                    pthread_mutex_lock(&data->mutex); //get mutex
                    if(valid == 1 && current_circuit->area<data->best_area){
                        //Found a valid solution!
                        memcpy((void *)&data->best_circuit, current_circuit, sizeof(Circuit)); //write to best circuit
                        printf("%d: Found proper solution\n",data->worker_id);
                        print_circuit(current_circuit);
                        write_circuit_to_file(current_circuit,current_circuit->area,data->worker_id,data->num_circuit[0]*100 + data->num_circuit[1]);
                        data->best_area = current_circuit->area;
                    }
                    pthread_mutex_unlock(&data->mutex);
                    // Recurse to add more gates
                    
                    generate_circuits_recursive(current_circuit, depth + 1, data);
                    current_circuit->area -= gate_types[i].area;  // Example area increment (modify as needed)
                    //printf("worker %d: returning with depth %d and area %d\n",data->worker_id,depth,current_circuit->area);
                }
            }
        }
    }
}

void* search_space_worker(void* args) {
    // Define and initialize worker-specific parameters and loop through circuits
    // You will need to pass parameters in `args` and cast them in this function
    ThreadArgs *data;
    data = (ThreadArgs *) args;

    Circuit current_circuit;
    current_circuit.area = 0;
    current_circuit.gate_count = 0;

    printf("%d: best Area %d, Going in recusive loop to check all circuits\n",data->worker_id, data->best_area);
    generate_circuits_recursive(&current_circuit, 0, data);

    //finished set worker_id to 1000 to indicate to the management thread that we finished
    pthread_mutex_lock(&data->mutex);
    data->worker_id = 1000;
    pthread_mutex_unlock(&data->mutex);

    return NULL;  // Return the best found circuit and area as needed
}


void brute_force_boolean(Circuit* best_circuit, int8_t truth_table[], int8_t target_outputs[], int num_inputs, int max_gates, int max_area) {
    pthread_t threads[NUM_THREADS];
    ThreadArgs thread_args[NUM_THREADS];  // Define `ThreadArgs` to pass data to threads
    int best_area = max_area;
    int total_circuits = 0;



    for (int i = 0; i < NUM_THREADS; i++) {
        thread_args[i].gate_types = gate_types;
        thread_args[i].num_inputs = num_inputs;
        thread_args[i].num_gates = max_gates;
        thread_args[i].best_area = best_area;
        thread_args[i].truth_table = truth_table;
        thread_args[i].target_outputs = target_outputs;
        thread_args[i].worker_id = i;
        thread_args[i].num_circuit[0] = 0;
        thread_args[i].num_circuit[1] = 0;
        pthread_mutex_init(&thread_args[i].mutex, NULL);
        pthread_create(&threads[i], NULL, search_space_worker, (void *)&thread_args[i]);
    }

    clock_t begin = clock();
    int number_of_running_threads = NUM_THREADS;
    while(number_of_running_threads>0){
        number_of_running_threads = NUM_THREADS;
        for (int i = 0; i < NUM_THREADS; i++) {
            pthread_mutex_lock(&thread_args[i].mutex); //get lock on the data

            //Check if it found a better circuit then known before.
            if(thread_args[i].best_area<best_area){
                best_area = thread_args[i].best_area;
                printf("Found best circuit at size %d, on worker: %d\n",best_area,i);
                memcpy(best_circuit, (void *)&thread_args[i].best_circuit, sizeof(Circuit));
            }

            //found a better circuit by another thread. Update data variable so that it does not searche longer where not necessary
            if(thread_args[i].best_area>best_area){
                printf("setting the best_area size %d, on worker: %d\n",best_area,i);
                thread_args[i].best_area = best_area;
            }

            //lastly check if the thread_closed
            if(thread_args[i].worker_id==1000){
                number_of_running_threads -= 1;
            }
            pthread_mutex_unlock(&thread_args[i].mutex);
            // Collect best circuits and area from each thread
        }

        clock_t toc = clock();
        printf("%f: running number of threads: %d\n",(double)(toc - begin) / (CLOCKS_PER_SEC*number_of_running_threads),number_of_running_threads);
        sleep(5);
    }
    printf("no threads running anymore\n");
    // Output the best circuit

    //count total amount of circuits
    for(int i=0;i<NUM_THREADS;i++){
        total_circuits += thread_args[i].num_circuit[1];
    }

    printf("Total amount of circuits searched is %d M\n",total_circuits);
}

void fill_target_outputs(int8_t truth_table[], int8_t target_outputs[], int num_inputs) {
    int num_combinations = NUM_COMBINATION;
    for (int i = 0; i < num_combinations; i++) {
        int inputs[num_inputs];
        for (int j = 0; j < num_inputs; j++) {
            inputs[j] = (i >> j) & 1;  // Extract each bit of i as an input
            truth_table[i*num_inputs+j] = (i >> j) & 1;;
        }
        target_outputs[i] = target_function(inputs);
    }
}



int main() {
    // Define target function output
    int8_t target_outputs[NUM_COMBINATION*NUM_OUTPUTS]; // 1<<NUM_INPUTS is equivalent to 2^NUM_INPUTS
    int8_t truth_table[NUM_COMBINATION*NUM_INPUTS]; // create a truth_table the size of target_output with an entry for every input.
    fill_target_outputs(truth_table, target_outputs, NUM_INPUTS);

    if(use_truth_table){
        for(int i=0; i<(NUM_COMBINATION*NUM_OUTPUTS); i++){
            target_outputs[i] = target_truth_table[(NUM_COMBINATION*NUM_OUTPUTS-1)-i]-'0'; //load in the truth table but then flipped
        }
    }

    Circuit best_circuit;
    brute_force_boolean(&best_circuit, truth_table, target_outputs, NUM_INPUTS, MAX_GATES, MAX_AREA);

    printf("Found best solution\n");
    print_circuit(&best_circuit);
    write_circuit_to_file(&best_circuit,best_circuit.area,0,0);
    // Print best circuit details
    return 0;
}