nissy-core

The "engine" of nissy, including the H48 optimal solver.
git clone https://git.tronto.net/nissy-core
Download | Log | Files | Refs | README | LICENSE

distribution.h (2792B)


      1 #define ENTRIES_PER_BYTE(k) (UINT64_C(8) / (uint64_t)(k))
      2 #define TABLE_SHIFT(i, k)   ((uint8_t)(k) * (uint8_t)((i) % ENTRIES_PER_BYTE(k)))
      3 #define TABLE_MASK(i, k)    ((UINT8_BIT(k) - UINT8_C(1)) << TABLE_SHIFT(i, k))
      4 
      5 typedef struct {
      6 	uint64_t min;
      7 	uint64_t max;
      8 	uint8_t bits;
      9 	uint64_t *distr;
     10 	const unsigned char *table;
     11 } getdistribution_data_t;
     12 
     13 STATIC void *getdistribution_runthread(void *);
     14 STATIC void getdistribution(const unsigned char *,
     15     uint64_t [static INFO_DISTRIBUTION_LEN], const tableinfo_t [static 1]);
     16 STATIC bool distribution_equal(const uint64_t [static INFO_DISTRIBUTION_LEN],
     17     const uint64_t [static INFO_DISTRIBUTION_LEN], uint8_t);
     18 
     19 STATIC void *
     20 getdistribution_runthread(void *arg)
     21 {
     22 	getdistribution_data_t *data = (getdistribution_data_t *)arg;
     23 	const unsigned char *table;
     24 	uint8_t j, k, m;
     25 	uint64_t i;
     26 
     27 	memset(data->distr, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
     28 
     29 	k = data->bits;
     30 	table = data->table;
     31 	m = TABLE_MASK(0, k);
     32 	for (i = data->min; i < data->max; i++)
     33 		for (j = 0; j < ENTRIES_PER_BYTE(k); j++)
     34 			data->distr[(table[i] & (m << (j*k))) >> (j*k)]++;
     35 
     36 	return NULL;
     37 }
     38 
     39 STATIC void
     40 getdistribution(
     41 	const unsigned char *table,
     42 	uint64_t distr[static INFO_DISTRIBUTION_LEN],
     43 	const tableinfo_t info[static 1]
     44 ) {
     45 	getdistribution_data_t targ[THREADS];
     46 	pthread_t thread[THREADS];
     47 	uint8_t pval, k;
     48 	uint64_t local_distr[THREADS][INFO_DISTRIBUTION_LEN];
     49 	uint64_t i, j, nbytes, sz, epb;
     50 
     51 	k = info->bits;
     52 	epb = ENTRIES_PER_BYTE(k);
     53 	nbytes = info->entries / epb;
     54 	sz = nbytes / THREADS;
     55 	for (i = 0; i < THREADS; i++) {
     56 		targ[i] = (getdistribution_data_t) {
     57 			.min = i * sz,
     58 			.max = i == THREADS - 1 ? nbytes : (i+1) * sz,
     59 			.bits = k,
     60 			.distr = local_distr[i],
     61 			.table = table,
     62 		};
     63 		pthread_create(&thread[i], NULL,
     64 		    getdistribution_runthread, &targ[i]);
     65 	}
     66 
     67 	for (i = 0; i < THREADS; i++)
     68 		pthread_join(thread[i], NULL);
     69 
     70 	memset(distr, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
     71 	for (i = 0; i < THREADS; i++)
     72 		for (j = 0; j < INFO_DISTRIBUTION_LEN; j++)
     73 			distr[j] += local_distr[i][j];
     74 
     75 	for (i = nbytes * epb; i < info->entries; i++) {
     76 		pval = (table[i/epb] & TABLE_MASK(i, k)) >> TABLE_SHIFT(i, k);
     77 		distr[pval]++;
     78 	}
     79 }
     80 
     81 STATIC bool
     82 distribution_equal(
     83 	const uint64_t expected[static INFO_DISTRIBUTION_LEN],
     84 	const uint64_t actual[static INFO_DISTRIBUTION_LEN],
     85 	uint8_t maxvalue
     86 )
     87 {
     88 	int wrong;
     89 	uint8_t i;
     90 
     91 	for (i = 0, wrong = 0; i <= MIN(maxvalue, 20); i++) {
     92 		if (expected[i] != actual[i]) {
     93 			wrong++;
     94 			LOG("[checkdata] Value for depth %" PRIu8
     95 			    ": expected %" PRIu64 ", found %" PRIu64 "\n",
     96 			    i, expected[i], actual[i]);
     97 		}
     98 		/*
     99 		else {
    100 			LOG("[checkdata] Value for depth %" PRIu8
    101 			    " is correct (%" PRIu64 ")\n", i, actual[i]);
    102 		}
    103 		*/
    104 	}
    105 
    106 	return wrong == 0;
    107 }