Code:
/*
* main.c
*
* Created on: Feb 29, 2012
* Author: JAC
*/
#include <gmp.h>
#include <pthread.h>
#include <stdio.h>
#include <time.h>
///////////////////////////////// DEFINITIONS //////////////////////////////////
#define SIDE_LENGTH 5
#define FORM_CATEGORIES 5
#define THREADS 12
#define TRANSFORMATIONS 16
/////////////////////////////////// STRUCTS ////////////////////////////////////
typedef struct {
clock_t tick;
mpz_t
i,
last,
total,
unique,
forms[FORM_CATEGORIES];
pthread_mutex_t lock;
} state;
///////////////////////////// FUNCTION PROTOTYPES //////////////////////////////
int cleanState(state *);
int getNextPosition(state *, mpz_t *);
int initState(state *, unsigned);
int processHash(
unsigned,
unsigned,
mpz_t *,
mpz_t *,
mpz_t *
);
int registerUnique(state *, int);
void *worker(void *);
////////////////////////// SYNCHRONIZATION INTERFACE ///////////////////////////
int cleanState(state *sync) {
int i;
mpz_clear(sync->i);
mpz_clear(sync->last);
mpz_clear(sync->total);
mpz_clear(sync->unique);
for (i = 0; i < FORM_CATEGORIES; i++) {
mpz_clear(sync->forms[i]);
}
pthread_mutex_destroy(&(sync->lock));
return 0;
}
int getNextPosition(state *sync, mpz_t *out) {
int to_return = 0;
pthread_mutex_lock(&(sync->lock));
if (mpz_cmp(sync->i, sync->last) <= 0) {
mpz_set(*out, sync->i);
mpz_add_ui(sync->i, sync->i, 1);
} else {
to_return = 1;
}
pthread_mutex_unlock(&(sync->lock));
return to_return;
}
int initState(state *sync, unsigned side_length) {
int i;
mpz_t ll, lr, ur;
unsigned size = side_length * side_length;
// Initialize the local variables.
mpz_init(ll);
mpz_init(lr);
mpz_init(ur);
// Initialize all the state variables.
sync->tick = clock();
mpz_init(sync->i);
mpz_init(sync->last);
mpz_init(sync->total);
mpz_init(sync->unique);
for (i = 0; i < FORM_CATEGORIES; i++) {
mpz_init(sync->forms[i]);
}
pthread_mutex_init(&(sync->lock), NULL);
// Calculate the total number of positions.
mpz_ui_pow_ui(sync->total, 3, size);
// Calculate the hash of the last unique position to optimize performance.
// The formula for the last unique position is as follows:
// last =
// total - 2 -
// (3 ** (size - 1))(length > 1) -
// (3 ** (size - length) + 3 ** (length - 1))(length > 2)
//
// This is the position with all its corners containing black stones and all
// other intersections contain white.
mpz_sub_ui(sync->last, sync->total, 2);
if (side_length > 1) {
mpz_ui_pow_ui(ll, 3, size - 1);
mpz_sub(sync->last, sync->last, ll);
}
if (side_length > 2) {
mpz_ui_pow_ui(lr, 3, size - side_length);
mpz_ui_pow_ui(ur, 3, side_length - 1);
mpz_sub(sync->last, sync->last, lr);
mpz_sub(sync->last, sync->last, ur);
}
// Clean up and return.
mpz_clear(ll);
mpz_clear(lr);
mpz_clear(ur);
return 0;
}
int registerUnique(state *sync, int forms) {
char buffer[BUFSIZ];
clock_t current;
int index;
pthread_mutex_lock(&(sync->lock));
mpz_add_ui(sync->unique, sync->unique, 1);
for (index = 0; forms > 1; index++, forms >>= 1);
mpz_add_ui(sync->forms[index], sync->forms[index], 1);
//*
current = clock();
if (current - sync->tick >= 500) {
sync->tick = current;
gmp_sprintf(
buffer,
"%Zd: %Zd (%u)",
sync->i,
sync->unique,
(unsigned)sync->tick
);
printf("%s\n", buffer);
}
//*/
pthread_mutex_unlock(&(sync->lock));
return 0;
}
///////////////////////////////// PROCESS HASH /////////////////////////////////
int processHash(
unsigned side_length,
unsigned board_size,
mpz_t *curr,
mpz_t *digit,
mpz_t *transformations
) {
unsigned long cell, form_count, i, j, coords[7];
// Initialize.
form_count = 1;
mpz_init_set(*curr, transformations[0]);
for (i = 1; i < TRANSFORMATIONS; i++) {
mpz_set_ui(transformations[i], 0);
}
// Transform the board at transformations[0] to its fifteen other positions.
for (i = 0; i < board_size; i++) {
short
col = i % side_length,
row = i / side_length;
// Calculate the value for the current intersection: 0 means empty, 1
// means black stone, and 2 means white stone. If the intersection is
// empty, skip to the next.
cell = mpz_fdiv_q_ui(*curr, *curr, 3);
if (!cell) {
continue;
}
// Determine the cell's coordinate in each of the transformations.
// 0: mirror horizontally
// 1: mirror vertically
// 2: mirror both
// 3: rotate left
// 4: rotate right
// 5: rotate left, mirror horizontally
// 6: rotate left, mirror vertically
coords[0] = row * side_length + (side_length - col - 1);
coords[1] = (side_length - row - 1) * side_length + col;
coords[2] = (side_length - row - 1) * side_length + (side_length - col - 1);
coords[3] = (side_length - col - 1) * side_length + row;
coords[4] = col * side_length + (side_length - row - 1);
coords[5] = (side_length - col - 1) * side_length + (side_length - row - 1);
coords[6] = col * side_length + row;
// Build the hash for each of the transformations using the determined
// cell value and coordinate.
for (j = 0; j < TRANSFORMATIONS - 1; j++) {
short place = j % 8;
mpz_ui_pow_ui(*digit, 3, place == 7 ? i : coords[place]);
if ((j > 6) ^ (cell == 2)) {
mpz_addmul_ui(transformations[j + 1], *digit, 2);
} else {
mpz_add(transformations[j + 1], transformations[j + 1], *digit);
}
}
}
// Determine the lowest hash value, the prototype, for the current board,
// and count the unique positions.
for (i = 1; i < TRANSFORMATIONS; i++) {
int is_hash;
if ((is_hash = mpz_cmp(transformations[i], transformations[0])) == 0) {
continue;
} else if (is_hash < 0) {
form_count = 0;
break;
}
for (
j = 0;
j < i && mpz_cmp(transformations[i], transformations[j]) != 0;
j++
); // Intentionally blank.
if (j == i) {
form_count++;
}
}
// Clean up and return.
return (int) form_count;
}
//////////////////////////////// WORKER THREAD /////////////////////////////////
void *worker(void *args) {
int i;
mpz_t curr, digit, transformations[TRANSFORMATIONS];
state *sync = (state *) ((unsigned *) args)[0];
unsigned
side_length = ((unsigned *) args)[1],
board_size = ((unsigned *) args)[2];
// Initialize.
mpz_init(curr);
mpz_init(digit);
for (i = 0; i < TRANSFORMATIONS; i++) {
mpz_init(transformations[i]);
}
// Continuously get position hashes from the synchronization state and
// evaluate them until there are none left.
while (!getNextPosition(sync, transformations)) {
if (
(i = processHash(
side_length,
board_size,
&curr,
&digit,
transformations
)) > 0
) {
registerUnique(sync, i);
}
}
// Clean up and return.
mpz_clear(curr);
mpz_clear(digit);
for (i = 0; i < TRANSFORMATIONS; i++) {
mpz_init(transformations[i]);
}
return NULL;
}
///////////////////////////////////// MAIN /////////////////////////////////////
int main() {
clock_t start;
int i;
pthread_t threads[THREADS];
state sync;
unsigned args[3] = {
(unsigned) &sync,
SIDE_LENGTH,
SIDE_LENGTH * SIDE_LENGTH
};
initState(&sync, SIDE_LENGTH);
start = clock();
for (i = 0; i < THREADS; i++) {
if (pthread_create(threads + i, NULL, worker, (void *) args) != 0) {
printf("-- THREAD COUNT: %d --\n", i);
break;
}
}
for (i = 0; i < THREADS; i++) {
pthread_join(threads[i], NULL);
}
gmp_printf(
"Size %u - %.15f seconds\nUnique: %Zd\n\tForm-1: %Zd\n\tForm-2: %Zd\n"
"\tForm-4: %Zd\n\tForm-8: %Zd\n\tForm-16: %Zd\nTotal: %Zd\n",
SIDE_LENGTH,
(clock() - start) / 1000.0,
sync.unique,
sync.forms[0],
sync.forms[1],
sync.forms[2],
sync.forms[3],
sync.forms[4],
sync.total
);
cleanState(&sync);
return 0;
}