Page MenuHomePhorge
Files F386674

bruteforce.c
No OneTemporary
Actions

Size
10 KB
Referenced Files
None
Subscribers
None

bruteforce.c
View Options

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <stdint.h>
#include <string.h>
// -------------- config
#define MAX_AREA 100000000
#define NUM_THREADS 1 //Needs to be <= 9 or 18 or 27 for efficient splitting the work load
#define NUM_INPUTS 2
#define MAX_GATES 5
#define USE_CIRCUIT_FOR_THRUTH_TABLE 0 //0: use target_function, 1: use Circuits
//0:
int target_function(int inputs[]) {
return inputs[0] ^ inputs[1];
}
//1:
// -------------- structs
typedef struct {
char* type;
int area;
} GateType;
typedef struct {
GateType* gate;
int in1;
int in2;
} Gate;
typedef struct {
Gate gates[MAX_GATES];
int gate_count;
int area;
} Circuit;
typedef struct {
Circuit best_circuit;
GateType *gate_types;
int num_inputs;
int num_gates;
int best_area;
int *truth_table;
int *target_outputs;
int worker_id;
} ThreadArgs;
Circuit test_circuit= {
{
},
,
}
// -------------- define used gates
GateType gate_types[] = {
{"INV", 1160},
{"AND", 3472},
{"NAND", 2832},
{"OR", 3472},
{"NOR", 2832},
{"XOR", 4632},
{"XNOR", 4632},
{"ANDNOT", 3472},
{"ORNOT", 3472}
};
// -------------- start functions
int evaluate_circuit(GateType* all_gates, Circuit* circuit, int* inputs) {
int intermediate_outputs[NUM_INPUTS + MAX_GATES];
memcpy(intermediate_outputs, inputs, NUM_INPUTS * sizeof(int));
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 output = 0;
if (circuit->gates[i].gate == &all_gates[0]) //INV
output = ~out1 & 1;
else if (circuit->gates[i].gate == &all_gates[1]) //AND
output = out1 & out2;
else if (circuit->gates[i].gate == &all_gates[2]) //NAND
output = ~(out1 & out2) & 1;
else if (circuit->gates[i].gate == &all_gates[3]) //OR
output = out1 | out2;
else if (circuit->gates[i].gate == &all_gates[4]) //NOR
output = ~(out1 | out2) & 1;
else if (circuit->gates[i].gate == &all_gates[5]) //XOR
output = out1 ^ out2;
else if (circuit->gates[i].gate == &all_gates[6]) //XNOR
output = ~(out1 ^ out2) & 1;
else if (circuit->gates[i].gate == &all_gates[7]) //ANDNOT
output = out1 & (~out2 & 1);
else if (circuit->gates[i].gate == &all_gates[8]) //ORNOT
output = out1 | (~out2 & 1);
intermediate_outputs[NUM_INPUTS + i] = output;
}
return intermediate_outputs[NUM_INPUTS + circuit->gate_count - 1];
}
int detect_tautology(Circuit *current_circuit, int in1, int in2, int gate_selected, ThreadArgs *data){
if ((in1 == in2 && gate_selected != 0) || //NOTE THAT IF i == 0 THEN WE SELECT INV
(in1 != in2 && gate_selected == 0) ||
(in1 > in2 && gate_selected != 7 && gate_selected != 8)) { //NOTE THAT i == 7 IS ANDNOT and i ==8 is ORNOT
return 1;
}
int input_used[current_circuit->gate_count + data->num_inputs];
memset(input_used, 0, sizeof(input_used));
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[in1] = 1;
input_used[in2] = 1;
for(int i=0; i<(current_circuit->gate_count + data->num_inputs -1);i++){
if(input_used[i]==0 && current_circuit->gate_count!=0){
return 2;
}
}
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 = 9;
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++) {
// ----------------- Going for multi processor approach
if(depth == 0){//at first level has to seperate into threads
if(NUM_THREADS<=9){
if((i<(data->worker_id*division)) | (i>=((data->worker_id+1)*division))){
//printf("Thread %d, skipping %s\n",data->worker_id,data->gate_types[i].type);
continue;
}
} else {
if( i != (data->worker_id/multi_core_division)){
//printf("Thread %d, skipping %s\n",data->worker_id,data->gate_types[i].type);
continue;
}
}
} else if (depth == 1 && NUM_THREADS>9) {
if((i<(data->worker_id%multi_core_division)*(9/multi_core_division)) | (i>=((data->worker_id+1)%multi_core_division)*(9/multi_core_division))){
//printf("at depth 1 Thread %d, skipping %s\n",data->worker_id,data->gate_types[i].type);
continue;
}
}
for (int in1 = 0; in1 < depth + data->num_inputs; in1++) {
for (int in2 = 0; in2 < depth + data->num_inputs; in2++) {
// Skip invalid gate configurations as in Python code
// 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->gate_count = depth + 1;
//if(current_circuit->gates[0].gate==&data->gate_types[5]){ // && current_circuit->gates[1].gate==&data->gate_types[5] && current_circuit->gates[2].gate==&data->gate_types[6]){
// printf("test\n");
//}
int tautology = detect_tautology(current_circuit,in1,in2,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;
for (int y=0; y < (1 << data->num_inputs); y++){ //CHECK IF IT IS VALID
if(evaluate_circuit(data->gate_types, current_circuit, &data->truth_table[y*data->num_inputs])!=data->target_outputs[y]){ //Check if it satisfies the equation
valid = 0;
}
}
}
//valid circuit add area
current_circuit->area += gate_types[i].area; // Example area increment (modify as needed)
if(valid == 1 && current_circuit->area<data->best_area){
//Found a valid solution!
memcpy(&data->best_circuit, current_circuit, sizeof(Circuit)); //write to best circuit
printf("Found proper solution\n");
for(int y=0; y<current_circuit->gate_count; y++){
printf("%d: %s, in1: %d, in2: %d\n",y,current_circuit->gates[y].gate->type,current_circuit->gates[y].in1,current_circuit->gates[y].in2);
}
data->best_area = current_circuit->area;
}
// 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)
}
}
}
}
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;
int best_area = data->best_area;
Circuit current_circuit;
current_circuit.area = 0;
current_circuit.gate_count = 0;
printf("In thread %d with best Area %d\nGoing in recusive loop to check all circuits\n",data->worker_id, data->best_area);
generate_circuits_recursive(&current_circuit, 0, data);
return NULL; // Return the best found circuit and area as needed
}
void brute_force_boolean(Circuit* best_circuit, int truth_table[], int 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;
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;
pthread_create(&threads[i], NULL, search_space_worker, (void *)&thread_args[i]);
}
for (int i = 0; i < NUM_THREADS; i++) {
pthread_join(threads[i], NULL);
// Collect best circuits and area from each thread
}
for (int i = 0; i< NUM_THREADS; i++) {
if(thread_args[i].best_area<best_area){
best_area = thread_args[i].best_area;
memcpy(best_circuit, &thread_args[i].best_circuit, sizeof(Circuit));
}
}
// Output the best circuit
}
void fill_target_outputs(int truth_table[], int target_outputs[], int num_inputs) {
int num_combinations = 1 << num_inputs;
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
int target_outputs[1 << NUM_INPUTS]; // 1<<NUM_INPUTS is equivalent to 2^NUM_INPUTS
int truth_table[(1 << NUM_INPUTS)*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);
Circuit best_circuit;
brute_force_boolean(&best_circuit, truth_table, target_outputs, NUM_INPUTS, MAX_GATES, MAX_AREA);
printf("Found best solution with area: %d\n",best_circuit.area);
for(int y=0; y<best_circuit.gate_count; y++){
printf("%d: %s, in1: %d, in2: %d\n",y,best_circuit.gates[y].gate->type,best_circuit.gates[y].in1,best_circuit.gates[y].in2);
}
// Print best circuit details
return 0;
}

File Metadata

Mime Type
text/x-c
Expires
Fri, Jul 4, 3:38 AM (12 h, 58 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
157446
Default Alt Text
bruteforce.c (10 KB)

Event Timeline