/* * bool_and.c * * Created on: 11/02/2020 * Author: Pedro */ #ifndef __OPENCL_VERSION__ #include #include #include "bool_and.h" #include "../bitmaps.h" #include "../config.h" #include "../variables.h" #endif #include "../kernels/cl_aux_functions.h" #if CL_D_TYPE == CL_BITMAP #include "../kernels/cl_bitmaps.h" #elif CL_D_TYPE == CL_INTERVAL #include "../kernels/cl_intervals.h" #endif #include "../kernels/cl_constraints.h" #include "../kernels/cl_variables.h" #include "../kernels/cl_ttl.h" #ifndef __OPENCL_VERSION__ /* * Creates a new constraint of the type bool_and and return the constraint ID * (x & y) ↔ z * x_id - boolean variable * y_id - boolean variable * z_id - boolean variable whose assignment is the result of the binary AND between x and y variables */ unsigned int c_bool_and(unsigned int x_id, unsigned int y_id, unsigned int z_id) { if (VS[x_id].max > 1) { v_del_gt(&VS[x_id], 1); if (VS[x_id].n_vals == 0) { printf("\nConstraint BOOL_AND makes model inconsistent at creation. No solution found.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } if (VS[y_id].max > 1) { v_del_gt(&VS[y_id], 1); if (VS[y_id].n_vals == 0) { printf("\nConstraint BOOL_AND makes model inconsistent at creation. No solution found.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } if (VS[z_id].max > 1) { v_del_gt(&VS[z_id], 1); if (VS[z_id].n_vals == 0) { printf("\nConstraint BOOL_AND makes model inconsistent at creation. No solution found.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } // set to include in kernel compilation USE_CS[BOOL_AND] = 1; USE_NON_CS_REIFI[BOOL_AND] = 1; REV = 1; unsigned int c_vs[3]; c_vs[0] = x_id; c_vs[1] = y_id; c_vs[2] = z_id; // creates a new generic constraint unsigned int c_id = c_new(c_vs, 3, NULL, 0, -1); // pointers to this type of constraint functions CS[c_id].kind = BOOL_AND; CS[c_id].check_sol_f = &bool_and_check; CS[c_id].constant_val = 0; return c_id; } /* * Creates a new reified constraint of the bool_and type * (x & y) ↔ z * x_id - boolean variable * y_id - boolean variable * z_id - boolean variable whose assignment is the result of the binary AND between x and y variables * reif_v_id - ID of the reification variable */ unsigned int c_bool_and_reif(unsigned int x_id, unsigned int y_id, unsigned int z_id, int reif_v_id) { if (VS[x_id].max > 1) { v_del_gt(&VS[x_id], 1); if (VS[x_id].n_vals == 0) { printf("\nConstraint BOOL_AND_REIF makes model inconsistent at creation. No solution found.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } if (VS[y_id].max > 1) { v_del_gt(&VS[y_id], 1); if (VS[y_id].n_vals == 0) { printf("\nConstraint BOOL_AND_REIF makes model inconsistent at creation. No solution found.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } if (VS[z_id].max > 1) { v_del_gt(&VS[z_id], 1); if (VS[z_id].n_vals == 0) { printf("\nConstraint BOOL_AND_REIF makes model inconsistent at creation. No solution found.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } if (VS[reif_v_id].max > 1) { v_del_gt(&VS[reif_v_id], 1); if (VS[reif_v_id].n_vals == 0) { printf("\nConstraint BOOL_AND_REIF makes model inconsistent at creation. No solution found.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } // set to include in kernel compilation USE_CS[BOOL_AND] = 1; USE_CS_REIFI[BOOL_AND] = 1; REV = 1; unsigned int c_vs[3]; c_vs[0] = x_id; c_vs[1] = y_id; c_vs[2] = z_id; // creates a new generic constraint unsigned int c_id = c_new(c_vs, 3, NULL, 0, reif_v_id); // pointers to this type of constraint functions CS[c_id].kind = BOOL_AND; CS[c_id].check_sol_f = &bool_and_check; CS[c_id].constant_val = 0; return c_id; } /* * Return true if the bool_and constraint is respected or false if not * (x & y) ↔ z * c - constraint to check if is respected * explored - if the CSP was already explored, which mean that all the variables must already be singletons * */ bool bool_and_check(constr *c, bool explored) { var *x = c->c_vs[0]; var *y = c->c_vs[1]; var *z = c->c_vs[2]; unsigned int i; if (!explored) { for (i = 0; i < c->n_c_vs; i++) { if (c->c_vs[i]->n_vals > 1) { return false; } } } if (c->reified && VS[c->reif_v_id].n_vals > 1) { if (explored) { fprintf(stderr, "\nError: Reification variable of constraint BOOL_AND_REIF (%d) has 2 values.\n", c->c_id); return false; } } if (((!c->reified || (c->reified && VS[c->reif_v_id].min == 1)) && (((x->min == 0 || y->min == 0) && z->min == 1) || (x->min == 1 && y->min == 1 && z->min == 0))) || (c->reified && VS[c->reif_v_id].min == 0 && (((x->min == 0 || y->min == 0) && z->min != 1) || (x->min == 1 && y->min == 1 && z->min != 0)))) { if (explored) { if (c->reified) { fprintf(stderr, "\nError: Constraint BOOL_AND_REIF (%d) not respected:\n", c->c_id); fprintf(stderr, "Reif ID=%u -> minimum=%u, maximum=%u, number of values=%u\n\n", c->reif_v_id, b_get_min_val(&VS[c->reif_v_id].domain_b), b_get_max_val(&VS[c->reif_v_id].domain_b), b_cnt_vals(&VS[c->reif_v_id].domain_b)); } else { fprintf(stderr, "\nError: Constraint BOOL_AND (%d) not respected:\n", c->c_id); } for (i = 0; i < c->n_c_vs; i++) { fprintf(stderr, "Variable ID=%u -> minimum=%u, maximum=%u, number of values=%u\n\n", c->c_vs[i]->v_id, b_get_min_val(&c->c_vs[i]->domain_b), b_get_max_val(&c->c_vs[i]->domain_b), b_cnt_vals(&c->c_vs[i]->domain_b)); } } return false; } return true; } #endif #if CS_BOOL_AND == 1 /* * Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID bool_and constraint * (x & y) ↔ z * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order * vs_prop_ - all CSP variables with current step values * current_cs - constraint that should be propagated for the variable with prop_v_id ID * vs_id_to_prop_ - circular vector with the ids of the variables to propagate * prop_ok - will be set to 1 or 0 if the constraint is respected or not */ #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wunused-parameter" CUDA_FUNC void bool_and_prop(CL_INTS_MEM int *vs_per_c_idx, CL_MEMORY VARS_PROP *vs_prop_, CL_CS_MEM cl_constr *current_cs, CL_MEMORY unsigned short *vs_id_to_prop_, bool *prop_ok CS_IGNORE_FUNC TTL_CTR) { int x_id = vs_per_c_idx[0]; int y_id = vs_per_c_idx[1]; int z_id = vs_per_c_idx[2]; bool changed; if (V_N_VALS(vs_prop_[x_id]) == 1) { if (V_MIN(vs_prop_[x_id]) == 0) { cl_v_del_val_m(&changed, &vs_prop_[z_id], 1 TTL_CTR_V); if (changed) { // if the removal of the value resulted in an empty domain return 0 if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } else { if (V_N_VALS(vs_prop_[y_id]) == 1) { if (V_MIN(vs_prop_[y_id]) == 1) { cl_v_del_val_m(&changed, &vs_prop_[z_id], 0 TTL_CTR_V); if (changed) { // if the removal of the value resulted in an empty domain return 0 if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } else { cl_v_del_val_m(&changed, &vs_prop_[z_id], 1 TTL_CTR_V); if (changed) { // if the removal of the value resulted in an empty domain return 0 if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } // y has 2 values and x is 1 } else if (V_N_VALS(vs_prop_[z_id]) == 1) { if (V_MIN(vs_prop_[z_id]) == 1) { cl_v_bool_del_val_m(&vs_prop_[y_id], 0 TTL_CTR_V); v_add_to_prop(vs_id_to_prop_, vs_prop_, y_id); } else { cl_v_bool_del_val_m(&vs_prop_[y_id], 1 TTL_CTR_V); v_add_to_prop(vs_id_to_prop_, vs_prop_, y_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } } // x has 2 values and maybe y too } else if (V_N_VALS(vs_prop_[y_id]) == 1) { if (V_MIN(vs_prop_[y_id]) == 0) { cl_v_del_val_m(&changed, &vs_prop_[z_id], 1 TTL_CTR_V); if (changed) { // if the removal of the value resulted in an empty domain return 0 if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } else { if (V_N_VALS(vs_prop_[z_id]) == 1) { if (V_MIN(vs_prop_[z_id]) == 1) { cl_v_del_val_m(&changed, &vs_prop_[x_id], 0 TTL_CTR_V); if (changed) { // if the removal of the value resulted in an empty domain return 0 if (V_IS_EMPTY(vs_prop_[x_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } else { cl_v_del_val_m(&changed, &vs_prop_[x_id], 1 TTL_CTR_V); if (changed) { // if the removal of the value resulted in an empty domain return 0 if (V_IS_EMPTY(vs_prop_[x_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } } } } // x and y have two values if (V_N_VALS(vs_prop_[z_id]) == 1) { if (V_MIN(vs_prop_[z_id]) == 1) { cl_v_bool_del_val_m(&vs_prop_[x_id], 0 TTL_CTR_V); v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id); cl_v_bool_del_val_m(&vs_prop_[y_id], 0 TTL_CTR_V); v_add_to_prop(vs_id_to_prop_, vs_prop_, y_id); #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif } } } #pragma GCC diagnostic pop #if CS_R_BOOL_AND == 1 /* * Validate bool_and constraint to be normally propagated, when reified * (x & y) ↔ z * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order * vs_prop_ - all CSP variables with current step values * current_cs - constraint that should be propagated for the variable with prop_v_id ID * vs_id_to_prop_ - circular vector with the ids of the variables to propagate */ CUDA_FUNC void bool_and_reif( CL_INTS_MEM int *vs_per_c_idx, CL_MEMORY VARS_PROP *vs_prop_, CL_CS_MEM cl_constr *current_cs, CL_MEMORY unsigned short *vs_id_to_prop_ CS_IGNORE_FUNC TTL_CTR) { int x_id = vs_per_c_idx[0]; int y_id = vs_per_c_idx[1]; int z_id = vs_per_c_idx[2]; if (V_N_VALS(vs_prop_[z_id]) == 1 && V_MIN(vs_prop_[z_id]) == 1 && V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == 1 && V_N_VALS(vs_prop_[y_id]) == 1 && V_MIN(vs_prop_[y_id]) == 1) { cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 0 TTL_CTR_V); v_add_to_prop(vs_id_to_prop_, vs_prop_, convert_int (current_cs->reif_var_id)); #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif } else if (V_N_VALS(vs_prop_[z_id]) == 1 && V_MIN(vs_prop_[z_id]) == 1 && ((V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == 0) || (V_N_VALS(vs_prop_[y_id]) == 1 && V_MIN(vs_prop_[y_id]) == 0))) { cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 1 TTL_CTR_V); v_add_to_prop(vs_id_to_prop_, vs_prop_, convert_int (current_cs->reif_var_id)); #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif } else if (V_N_VALS(vs_prop_[z_id]) == 1 && V_MIN(vs_prop_[z_id]) == 0 && ((V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == 0) || (V_N_VALS(vs_prop_[y_id]) == 1 && V_MIN(vs_prop_[y_id]) == 0))) { cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 0 TTL_CTR_V); v_add_to_prop(vs_id_to_prop_, vs_prop_, convert_int (current_cs->reif_var_id)); #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif } else if (V_N_VALS(vs_prop_[z_id]) == 1 && V_MIN(vs_prop_[z_id]) == 0 && V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == 1 && V_N_VALS(vs_prop_[y_id]) == 1 && V_MIN(vs_prop_[y_id]) == 1) { cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 1 TTL_CTR_V); v_add_to_prop(vs_id_to_prop_, vs_prop_, convert_int (current_cs->reif_var_id)); #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif } } /* * Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID bool_and opposite constraint * (x & y) != z * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order * vs_prop_ - all CSP variables with current step values * current_cs - constraint that should be propagated for the variable with prop_v_id ID * vs_id_to_prop_ - circular vector with the ids of the variables to propagate * prop_ok - will be set to 1 or 0 if the constraint is respected or not */ #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wunused-parameter" CUDA_FUNC void bool_and_prop_opposite(CL_INTS_MEM int *vs_per_c_idx, CL_MEMORY VARS_PROP *vs_prop_, CL_CS_MEM cl_constr *current_cs, CL_MEMORY unsigned short *vs_id_to_prop_, bool *prop_ok CS_IGNORE_FUNC TTL_CTR) { int x_id = vs_per_c_idx[0]; int y_id = vs_per_c_idx[1]; int z_id = vs_per_c_idx[2]; bool changed; if (V_N_VALS(vs_prop_[x_id]) == 1) { if (V_MIN(vs_prop_[x_id]) == 0) { cl_v_del_val_m(&changed, &vs_prop_[z_id], 0 TTL_CTR_V); if (changed) { // if the removal of the value resulted in an empty domain return 0 if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } else { if (V_N_VALS(vs_prop_[y_id]) == 1) { if (V_MIN(vs_prop_[y_id]) == 1) { cl_v_del_val_m(&changed, &vs_prop_[z_id], 1 TTL_CTR_V); if (changed) { // if the removal of the value resulted in an empty domain return 0 if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } else { cl_v_del_val_m(&changed, &vs_prop_[z_id], 0 TTL_CTR_V); if (changed) { // if the removal of the value resulted in an empty domain return 0 if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } // y has 2 values and x is 1 } else if (V_N_VALS(vs_prop_[z_id]) == 1) { if (V_MIN(vs_prop_[z_id]) == 1) { cl_v_bool_del_val_m(&vs_prop_[y_id], 1 TTL_CTR_V); v_add_to_prop(vs_id_to_prop_, vs_prop_, y_id); } else { cl_v_bool_del_val_m(&vs_prop_[y_id], 0 TTL_CTR_V); v_add_to_prop(vs_id_to_prop_, vs_prop_, y_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } } // x has 2 values and maybe y too } else if (V_N_VALS(vs_prop_[y_id]) == 1) { if (V_MIN(vs_prop_[y_id]) == 0) { cl_v_del_val_m(&changed, &vs_prop_[z_id], 0 TTL_CTR_V); if (changed) { // if the removal of the value resulted in an empty domain return 0 if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } else { if (V_N_VALS(vs_prop_[x_id]) == 1) { if (V_MIN(vs_prop_[x_id]) == 1) { cl_v_del_val_m(&changed, &vs_prop_[z_id], 1 TTL_CTR_V); if (changed) { // if the removal of the value resulted in an empty domain return 0 if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } else { cl_v_del_val_m(&changed, &vs_prop_[z_id], 0 TTL_CTR_V); if (changed) { // if the removal of the value resulted in an empty domain return 0 if (V_IS_EMPTY(vs_prop_[z_id])) { *prop_ok = 0; return; } v_add_to_prop(vs_id_to_prop_, vs_prop_, z_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } // y has 2 values and x is 1 } else if (V_N_VALS(vs_prop_[z_id]) == 1) { if (V_MIN(vs_prop_[z_id]) == 1) { cl_v_bool_del_val_m(&vs_prop_[x_id], 1 TTL_CTR_V); v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id); } else { cl_v_bool_del_val_m(&vs_prop_[x_id], 0 TTL_CTR_V); v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id); } #if CL_CS_IGNORE cs_ignore[current_cs->c_id] = 1; #endif return; } } } } #pragma GCC diagnostic pop #endif /* * Decides the propagator to call for this constraint * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order * vs_prop_ - all CSP variables with current step values * current_cs - constraint that should be propagated for the variable with prop_v_id ID * vs_id_to_prop_ - circular vector with the ids of the variables to propagate * prop_ok - will be set to 1 or 0 if the constraint is respected or not */ CUDA_FUNC void bool_and_propagate(CL_INTS_MEM int *vs_per_c_idx, CL_MEMORY VARS_PROP *vs_prop_, CL_CS_MEM cl_constr *current_cs, CL_MEMORY unsigned short *vs_id_to_prop_, bool *prop_ok PROPAGATED_FUNC CS_IGNORE_FUNC TTL_CTR) { #if CS_R_BOOL_AND == 0 bool_and_prop(vs_per_c_idx, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V); #if CL_STATS == 1 *propagated = true; #endif #elif CS_R_BOOL_AND == 1 if (current_cs->reified == 1) { if (V_N_VALS(vs_prop_[current_cs->reif_var_id]) > 1) { bool_and_reif(vs_per_c_idx, vs_prop_, current_cs, vs_id_to_prop_ CS_IGNORE_CALL TTL_CTR_V); } else { if (V_MIN(vs_prop_[current_cs->reif_var_id]) == 1) { bool_and_prop(vs_per_c_idx, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V); } else { bool_and_prop_opposite(vs_per_c_idx, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V); } #if CL_STATS == 1 *propagated = true; #endif } } else { bool_and_prop(vs_per_c_idx, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V); #if CL_STATS == 1 *propagated = true; #endif } #endif } #endif