/*
 * bitmaps.c
 *
 *  Created on: 23/08/2014

 *      Author: pedro

 */

#include "bitmaps.h"

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

#include "CL/cl_platform.h"
#include "config.h"

#if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__)
#include <intrin.h>
#if H_BITS == 32
#define __builtin_popcount __popcnt
#else
#define __builtin_popcountl __popcnt64
#endif
#endif

/*
 * Check if current bitmap size on host is enough and update D_MAX and D_MIN if needed
 * d_min - minimum value on the domain
 * d_max - maximum value on the domain
 */

void b_check_and_update_bounds(unsigned int d_min, unsigned int d_max) {
	if (H_BITS < d_max + 1) {
		fprintf(stderr, "\n PHACT was compiled to work with domains that range from 0 to %d. You are trying to set a value of %u.\n"
				" For that, please compile solver with \"make all CFLAGS=\"-D BITS=%u\"\" to allow the usage of domains with values up to %u elements.\n",
				H_BITS - 1, d_max, d_max + 1, d_max + 1);
		exit(-1);
	}

	if (d_min < D_MIN) {
		D_MIN = d_min;

	}
	if (d_max > D_MAX) {
		D_MAX = d_max;
	}
}

/*
 * create a new domain with one value
 * d_new - new domain to create
 * val - value to place on the domain
 */
void b_new_val(bitmap* d, unsigned int val) {

	b_check_and_update_bounds(val, val);

	b_clear(d);

#if H_N_WORDS == 1

	*d = (H_ONE << (val));
#else
	(*d)[val >> H_DIV] = H_ONE << val;
#endif
}

/*
 * Create a new domain with all value between min and max set
 * d - new domain to create
 * min - minimum domain value
 * max - maximum domain value
 * */
void b_new_range(bitmap* d, unsigned int min, unsigned int max) {
	if (max < min) {
		fprintf(stderr, "\nPHACT is trying to create a value with the maximum value lesser than the minimum value.\n");
		exit(-1);

	}

	b_check_and_update_bounds(min, max);

	b_clear(d);

#if H_N_WORDS == 1
	*d = (H_ALL_ONES << min) & (H_ALL_ONES >> (H_WORD - max - 1));
#else
	unsigned int f = min >> H_DIV;
	unsigned int l = max >> H_DIV;

	if (f == l) {
		(*d)[f] = (H_ALL_ONES << min) & (H_ALL_ONES >> (H_WORD - max - 1));
	} else {
		(*d)[f] = (H_ALL_ONES << min);
		while (++f < l) {
			(*d)[f] = H_ALL_ONES;
		}
		(*d)[l] = H_ALL_ONES >> (H_WORD - (max & (H_WORD - 1)) - 1);
	}
#endif
}

/*
 * Create a new domain with the received values.
 * d - new domain to create
 * d_vals - vector with all the values allowed for the new variable
 * n_vals - number of domain values in values vector
 * */
void b_new_vals(bitmap* d, unsigned int* d_vals, unsigned int n_vals) {
	unsigned int min = d_vals[0];
	unsigned int max = min;
	unsigned int i;

	// get values range to check bounds
	for (i = 1; i < n_vals; i++) {
		if (d_vals[i] < min) {
			min = d_vals[i];
		}

		if (d_vals[i] > max) {

			max = d_vals[i];
		}
	}

	b_check_and_update_bounds(min, max);
	b_clear(d);

	for (i = 0; i < n_vals; i++) {
#if H_N_WORDS == 1
		(*d) |= H_ONE << d_vals[i];
#else
		(*d)[d_vals[i] >> H_DIV] |= (H_ONE << (d_vals[i] & (H_WORD - 1)));
#endif
	}
}

void b_set_val(bitmap* d, unsigned int val) {
#if H_N_WORDS == 1
	*d = (H_ONE << (val));
#else
	(*d)[val >> H_DIV] = H_ONE << val;
#endif
}

/*
 * Set domain to zeros

 * d - domain to set to zeros

 */
void b_clear(bitmap* d) {
#if H_N_WORDS == 1
	(*d) = 0;
#else
	memset(d, 0, H_BITS >> 3);
#endif
}

/*
 * Return true if domain is empty, and false if not

 * d - domain to check if empty

 */
bool b_is_empty(bitmap* d) {
#if H_N_WORDS == 1
	return ((*d) == 0);
#else
	unsigned int i;
	for (i = 0; i <= D_MAX >> H_DIV; i++) {
		if ((*d)[i] != 0) {
			return false;
		}
	}

	return true;

#endif
}

/*
 * Return true if the the domain cantins the values or false if not
 * d - domain to check if it containes the values
 * val - value to check if contained
 */
bool b_contains_val(bitmap* d, unsigned int val) {
#if H_N_WORDS == 1
	return (*d) & (H_ONE << val);
#else
	return (*d)[val >> H_DIV] & (H_ONE << val);
#endif
}

/*
 * Return true if domains are equal, and false if different

 * d1 - domain 1 to check if equal to d2

 * d2 - domain 2 to check if equal to d1
 */
bool bs_eq(bitmap* d1, bitmap* d2) {
#if H_N_WORDS == 1
	return (*d1 == *d2);
#else
	unsigned int i;
	for (i = 0; i <= D_MAX >> H_DIV; i++) {
		if ((*d1)[i] != (*d2)[i]) {
			return false;
		}
	}

	return true;

#endif
}

/*
 * Return the nth value of the domain
 * d - domain to get nth value
 * nth - nth value to get from domain (from 1 to max value)
 */
unsigned int b_get_nth_val(bitmap* d, unsigned int nth) {
	unsigned int vals_cnt = 0;
	unsigned int i;

#if H_N_WORDS == 1
	for (i = 0; vals_cnt <= nth; i++) {
		if ((*d) & (H_ONE << i)){
			vals_cnt++;
		}
		if (vals_cnt == nth) {

			return i;

		}
	}
#else
	unsigned int word_idx;
	for (word_idx = 0; word_idx <= D_MAX >> H_DIV; word_idx++) {
		for (i = 0; i < H_WORD; i++) {
			if ((*d)[word_idx] & (H_ONE << i)) {
				vals_cnt++;
			}
			if (vals_cnt == nth) {
				return i + (word_idx << H_DIV);
			}
		}
	}
#endif
	return 0;
}

/*
 * Copy d_src values to d_dest
 * d_dest - where to copy the values
 * d_src - domain to copy
 */
void b_copy(bitmap* d_dest, bitmap* d_src) {
#if H_N_WORDS == 1
	*d_dest = *d_src;
#else
	memcpy(*d_dest, *d_src, H_N_WORDS * sizeof(H_WORD_TYPE));
#endif
}


/*

 * Return the number of values (bits set) on the received domain

 * d - domain with values to count
 * */
unsigned int b_cnt_vals(bitmap* d) {
#if H_N_WORDS == 1
#if H_WORD == 32
	return __builtin_popcount(*d);
#else

	return __builtin_popcountl(*d);
#endif
#else
	int cnt = 0;

	unsigned int i;

	for (i = 0; i <= D_MAX >> H_DIV; i++) {
#if H_WORD == 32
		cnt += __builtin_popcount((*d)[i]);
#else
		cnt += __builtin_popcountl((*d)[i]);
#endif
	}
	return (unsigned int)cnt;
#endif
}

/*
 * Return the minimum domain value
 * d - domain to look for the minimum value
 * */
int b_get_min_val(bitmap* d) {

#if H_N_WORDS == 1

#if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__)
	H_WORD_TYPE r = 0;
#if H_WORD == 32
	_BitScanForward(&r, *d);
#else
	_BitScanForward64(&r, *d);

#endif

	return (int)r;
#else
#if H_WORD == 32
	return __builtin_ctz(*d);
#else
	return __builtin_ctzl(*d);
#endif
#endif

#else

	unsigned int i;
#if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__)
	bitmap r = {0};
	for (i = 0; i <= D_MAX >> H_DIV; i ++) {
		if ((*d)[i] > 0) {
#if H_WORD == 32
			_BitScanForward(&r[0], (*d)[i]);
#else
			_BitScanForward64(&r[0], (*d)[i]);
#endif
			return (int)r[0] + (i << H_DIV);
		}
	}
#else
	for (i = 0; i <= D_MAX >> H_DIV; i++) {
		if ((*d)[i] > 0) {
#if H_WORD == 32
			return __builtin_ctz((*d)[i]) + ((int)i << H_DIV);
#else
			return __builtin_ctzl((*d)[i]) + ((int)i << H_DIV);
#endif
		}
	}
#endif
	return -1;

#endif
}

/*
 * Return the maximum domain value
 * d - domain to look for the maximum value
 * */
int b_get_max_val(bitmap *d) {
#if H_N_WORDS == 1

#if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__)
	H_WORD_TYPE r = 0;
#if H_WORD == 32
	_BitScanReverse(&r, *d);
#else
	_BitScanReverse64(&r, *d);
#endif
	return (int)r;
#else
#if H_WORD == 32
	return H_WORD - __builtin_clz(*d) - 1;
#else
	return H_WORD - __builtin_clzl(*d) - 1;
#endif
#endif

#else
	int i;
#if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__)
	bitmap r = {0};
	for (i = D_MAX >> H_DIV; i >= 0; i--) {
		if ((*d)[i] > 0) {
#if H_WORD == 32
			_BitScanReverse(&r[0], (*d)[i]);
#else
			_BitScanReverse64(&r[0], (*d)[i]);
#endif
			return (int)r[0] + (i << H_DIV);
		}
	}
#else
	for (i = (int)D_MAX >> H_DIV; i >= 0; i--) {
		if ((*d)[i] > 0) {
#if H_WORD == 32
			return H_WORD - __builtin_clz((*d)[i]) - 1 + (i << H_DIV);
#else
			return H_WORD - __builtin_clzl((*d)[i]) - 1 + (i << H_DIV);
#endif
		}
	}

#endif

	return -1;

#endif
}

/*
 * Do operation d1 = d1 & d2
 * Return true if domain changed and false if not
 * d1 - domain to save operation
 * d2 - domain to do AND with
 */
bool b_intersect_b(bitmap* d1, bitmap* d2) {
#if H_N_WORDS == 1
	H_WORD_TYPE d_prev = (*d1);

	(*d1) &= (*d2);

	return ((*d1) != d_prev);
#else
	bool changed = false;

	H_WORD_TYPE d_prev;

	unsigned int i;
	for (i = 0; i <= D_MAX >> H_DIV; i++) {
		d_prev = (*d1)[i];

		(*d1)[i] &= (*d2)[i];
		changed |= (*d1)[i] != d_prev;
	}
	return changed;
#endif
}

/*
 * Do operation d1 = d1 | d2
 * Return true if domain changed and false if not
 * d1 - domain to save operation
 * d2 - domain to do or with
 */
bool b_union_b(bitmap* d1, bitmap* d2) {
#if H_N_WORDS == 1
	H_WORD_TYPE d_prev = (*d1);

	(*d1) |= (*d2);

	return ((*d1) != d_prev);
#else
	bool changed = false;

	H_WORD_TYPE d_prev;

	unsigned int i;
	for (i = 0; i <= D_MAX >> H_DIV; i++) {
		d_prev = (*d1)[i];

		(*d1)[i] |= (*d2)[i];
		changed |= (*d1)[i] != d_prev;
	}
	return changed;
#endif
}

/*
 * Remove the minimum value in d domain from the d_to_chg domain
 * Return true if domain changed and false if not
 * d_to_chg - domain to remove value from
 * d - domain with the minimum value to remove from d_to_chg
 */
bool b_del_singl_val(bitmap* d_to_chg, bitmap* d) {
#if H_N_WORDS == 1
	H_WORD_TYPE d_prev = (*d_to_chg);

	(*d_to_chg) &= ~(*d);

	return ((*d_to_chg) != d_prev);

#else

	unsigned int bit_numb = (unsigned int)b_get_min_val(d);

	unsigned int bitmap_idx = bit_numb >> H_DIV;
	H_WORD_TYPE d_prev = (*d_to_chg)[bitmap_idx];

	(*d_to_chg)[bitmap_idx] &= ~(H_ONE << (bit_numb - (bitmap_idx << H_DIV)));

	return ((*d_to_chg)[bitmap_idx] != d_prev);
#endif
}

/*
 * Remove from the domain all the values lesser than val
 * d_to_chg - domain to remove values from
 * val - minimum value to keep at domain
 */
bool b_del_lt(bitmap* d, unsigned int val) {
#if H_N_WORDS == 1
	H_WORD_TYPE d_prev = (*d);

	(*d) &= (H_ALL_ONES << val);

	return ((*d) != d_prev);
#else
	H_WORD_TYPE w;

	unsigned int limit = val >> H_DIV;

	bool changed = false;
	unsigned int word_idx;

	for (word_idx = 0; word_idx < limit; word_idx++) {
		if ((*d)[word_idx] != 0) {
			(*d)[word_idx] = 0;
			changed = true;
		}
	}
	w = (*d)[word_idx] & (H_ALL_ONES << (val % H_WORD));

	if (!changed && w == (*d)[word_idx]) {
		return false;
	}
	(*d)[word_idx] = w;

	return true;
#endif
}

/*
 * Remove from the domain all the values lower or equal to val
 * d_to_chg - domain to remove values from
 * val - bottom value to remove from domain
 */
bool b_del_le(bitmap* d, unsigned int val) {
	return b_del_lt(d, ++val);
}

/*
 * Remove from the domain all the values lower than val

 * d - domain to remove values from

 * val - maximum value to keep at domain
 */

bool b_del_gt(bitmap* d, unsigned int val) {

#if H_N_WORDS == 1
	H_WORD_TYPE d_prev = (*d);
	(*d) &= (H_ALL_ONES >> (H_WORD - 1 - val));

	return ((*d) != d_prev);
#else
	H_WORD_TYPE w;
	bool changed = false;

	unsigned int word_idx = val >> H_DIV;

	int i;

	w = (*d)[word_idx] & ((H_ALL_ONES >> (H_WORD -1 - (val % H_WORD))));

	for (i = (int)word_idx + 1; i < H_N_WORDS; i++) {
		if ((*d)[i] != 0) {
			(*d)[i] = 0;
			changed = true;
		}
	}

	if (!changed && w == (*d)[word_idx]) {

		return false;

	}

	(*d)[word_idx] = w;

	return true;
#endif
}

/*
 * Remove from the domain all the values lower than val
 * d_to_chg - domain to remove values from
 * val - top value to remove from the domain
 */
bool b_del_ge(bitmap* d, unsigned int val) {
	return b_del_gt(d, --val);
}

/*
 * remove value from d_to_chg domain

 * Return true if domain changed and false if not

 * d - domain to remove value from
 * val - value to remove from d_to_chg

 */

bool b_del_val(bitmap* d, unsigned int val) {
#if H_N_WORDS == 1
	H_WORD_TYPE d_prev = (*d);

	(*d) &= ~(H_ONE << val);

	return ((*d) != d_prev);
#else
	unsigned int word_idx = val >> H_DIV;

	H_WORD_TYPE d_prev = ((*d)[word_idx]);

	(*d)[word_idx] &= ~(H_ONE << val);

	return ((*d)[word_idx] != d_prev);
#endif
}

/*
 * Clear all values from domain d, except val if present
 * Return true if domain changed and false if not
 * d - domain to clear all values except val
 * val - value to keep on domain if present
 */
bool b_del_all_except_val(bitmap* d, unsigned int val) {
#if H_N_WORDS == 1
	H_WORD_TYPE d_prev = (*d);

	*d &= (H_ONE << val);

	return ((*d) != d_prev);
#else
	unsigned int word_idx = val >> H_DIV;

	H_WORD_TYPE d_prev = (*d)[word_idx];

	bool changed = false;
	unsigned int i;

	for (i = 0; i < word_idx; i++) {
		if ((*d)[i] != 0) {
			(*d)[i] = 0;
			changed = true;
		}
	}
	(*d)[word_idx] = d_prev & (H_ONE << val);

	for (i = word_idx + 1; i <= (D_MAX >> H_DIV); i++) {
		if ((*d)[i] != 0) {
			(*d)[i] = 0;
			changed = true;
		}
	}
	return (changed || (*d)[word_idx] != d_prev);
#endif
}

/*
 * print the bitmap (bitmap/s) of the received bitmap
 * d - domain (bitmap) to print
 */
void b_print_domain(bitmap* d) {
#if H_N_WORDS == 1
#if H_WORD == 32
	printf("%u", *d);
#else
	printf("%lu", *d);
#endif
#else
	unsigned int i;

#if H_WORD == 32

	printf("%u", (*d)[0]);
	for (i = 1; i <= D_MAX >> H_DIV; i++) {
		printf(",%u", (*d)[i]);
	}
#else
	printf("%lu", (*d)[0]);
	for (i = 1; i <= D_MAX >> H_DIV; i++) {
		printf(",%lu", (*d)[i]);
	}
#endif
#endif
}

/*
 * Copy the bitmap number "bitmap_n" in "dev_bs" array, with CL_BITS size to the single host_b with size H_BITS
 * host_b - where to copy the bitmaps to
 * dev_bs - array with all the bitmaps to copy one from
 * bitmap_n - number of the bitmap to copy inside the dev_bs array of bitmaps
 */
void b_copy_dev_to_host(bitmap* host_b, void** dev_bs, unsigned int bitmap_n) {

	if (CL_N_WORDS_ == 1) {
		if (CL_WORD_ == 32) {
			unsigned int* dev_domains = (unsigned int*)dev_bs;
#if H_N_WORDS == 1	// host bitmaps are one unsigned int or cl_ulong and device bitmaps are one unsigned int
			*host_b = (H_WORD_TYPE)dev_domains[bitmap_n];
#else	// host bitmaps are an array of unsigned int or cl_ulong and device bitmaps are one unsigned int
			(*host_b)[0] = (H_WORD_TYPE)dev_domains[bitmap_n];

#endif

		} else {
			cl_ulong* dev_domains = (cl_ulong*)dev_bs;
#if H_N_WORDS == 1	// host bitmaps are one cl_ulong and device bitmaps are one cl_ulong

			*host_b = dev_domains[bitmap_n];

#else
			if (H_WORD == 32) {	// host bitmaps are an array of unsigned int and device bitmaps are one cl_ulong
				(*host_b)[1] = (H_WORD_TYPE)(dev_domains[bitmap_n] >> 32);

				(*host_b)[0] = (H_WORD_TYPE)(dev_domains[bitmap_n]);

			} else {	// host bitmaps are an array of cl_ulong and device bitmaps are one cl_ulong
				(*host_b)[0] = dev_domains[bitmap_n];

			}

#endif
		}
	} else {
		if (CL_WORD_ == 32) {

#if H_N_WORDS == 1 && H_WORD == 64	// host bitmaps are one cl_ulong and device bitmaps are two unsigned int
			unsigned int* dev_domains = (unsigned int*)dev_bs;

			*host_b = ((cl_ulong)dev_domains[bitmap_n * 2 + 1] << 32) | ((cl_ulong)dev_domains[bitmap_n * 2]);
#elif H_N_WORDS > 1 && H_WORD == 32	// host and device bitmaps are an array of unsigned int
			unsigned int* dev_domains = (unsigned int*)dev_bs;
			unsigned int j;
			for (j = 0; j < CL_N_WORDS_; j++) {
				(*host_b)[j] = dev_domains[bitmap_n * CL_N_WORDS_ + j];
			}
#elif H_N_WORDS > 1 && H_WORD == 64	// host bitmaps are an array of cl_ulong and device bitmaps are an array of unsigned int
			unsigned int* dev_domains = (unsigned int*)dev_bs;
			unsigned int j;
			for (j = 0; j < CL_N_WORDS_ / 2; j++) {
				(*host_b)[j] = ((cl_ulong)dev_domains[bitmap_n * CL_N_WORDS_ + j + 1] << 32) | ((cl_ulong)dev_domains[bitmap_n * CL_N_WORDS_ + j]);
			}
			// if device bitmaps are an odd array of unsigned int add the last one
			if (CL_N_WORDS_ % 2 != 0) {
				(*host_b)[j] |= ((cl_ulong)dev_domains[bitmap_n * CL_N_WORDS_ + j]);
			}

#endif

		} else {
#if H_N_WORDS > 1

			unsigned int j;

			cl_ulong* dev_domains = (cl_ulong*)dev_bs;
#if H_WORD == 32	// host bitmaps are an array of unsigned int and device bitmaps are an array of cl_ulong
			for (j = 0; j < CL_N_WORDS_; j++) {

				(*host_b)[j * 2 + 1] = (H_WORD_TYPE)(dev_domains[bitmap_n * CL_N_WORDS_ + j] >> 32);

				(*host_b)[j * 2] = (H_WORD_TYPE)(dev_domains[bitmap_n * CL_N_WORDS_ + j]);
			}
#else	// host and device bitmaps are an array of cl_ulong
			for (j = 0; j < CL_N_WORDS_; j++) {
				(*host_b)[j] = dev_domains[bitmap_n * CL_N_WORDS_ + j];

			}

#endif
#endif
		}
	}
}