JrCube Source
/*************************************************************************/
/* JrCube 0.9.5 */
/* by */
/* Steven L. Elliott */
/* */
/* This program will form a complete database of all possible */
/* permutations of the 2x2x2 Rubik's cube, known as Rubik's Jr, and then */
/* uses that database to solve a provided cube in a minimum number of */
/* twists. The 3.6 MiB database is generated using the '-g' option. */
/* */
/* Indent : indent -gnu -nut -i4 -bli0 -npcs -nbad jrcube.c */
/*************************************************************************/
#define _GNU_SOURCE /* Needed for asprintf() */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
/* TODO: Come up with a better system to detect what features are available. */
#ifdef __linux__
#define HAVE_MMAP 1
#endif
#ifdef HAVE_MMAP
#include
#include
#endif
/* Types */
/* For each of the eight locations that make up the larger cube the number of
* the smaller cube that is there and it's rotation.
*/
typedef struct
{
int piece; /* Piece number 0-7 */
int rot; /* 0-not rotated 1-to the left 2-to the right */
} mini_cube_t;
/* Item in the sides table. See that table for details. */
typedef struct
{
int poss[4];
int rots[4];
} side_t;
/* Item in the orienting_turns table. See that table for details. */
typedef struct
{
int turns[4];
} orienting_turns_t;
/* The state of a particular cube as well as previous and next pointers. */
typedef struct cube_s
{
struct cube_s *prev;
struct cube_s *next;
mini_cube_t pos[8];
int index;
} cube_t;
/* An item in a linked list of items to be freed. */
typedef struct freeitem_s
{
struct freeitem_s *next;
void *ptr;
int is_mmap;
size_t size;
} freeitem_t;
/* Enumerations */
/* Log level argument passed in. */
typedef enum level_e
{
level_debug,
level_message,
level_warning,
level_fatal
} level_t;
/* Constants */
#define LOG_LEVEL level_message
#define NOOP 0
#define GENERATE 1
#define SOLVE 2
#define TEST 4
#define DB_SIZE 3674160
#define MAX_CF_NAMES 200
#define MAX_TWISTS 0x7f
#define LOWER ('a' - 'A') /* Add this in ASCII to convert to lower case. */
#ifndef JC_LIB_DIR
#define JC_LIB_DIR "/usr/local/lib/jrcube"
#endif
/* Globals */
/* Linked list to be freed later. */
static freeitem_t *freeitem;
/* Calculated at runtime based on other values. This is used to calculate the
* index for a cube.
*/
static int digit_value[13];
/* Global tables */
/* When translating to and from an index the cube can be thought of as a
* mixed base number. Each entry indicates the base of that digit. The
* first row is for the rotations and the second row is for pieces.
* The angle of the last corner is deduced.
*/
static const int digit_base[13] = { 3, 3, 3, 3, 3, 3, 1, 2, 3, 4, 5, 6, 7 };
/* Each side of the cube consists of four smaller cubes. When a twist is
* applied to a side the four smaller cubes that make up that side are
* rearranged in a way that can be described as an item being removed from
* a sequence and pushed onto the other end of the sequence:
* ABCD -> DABC
* What the following table does is for each twist that can be done to a side
* the index in the sequence (ABCD in the example above) is mapped onto the
* position in the cube.
*/
static const side_t sides[] = {
{{4, 0, 2, 6}, {2, 1, 2, 1}}, /* x+ */
{{1, 5, 7, 3}, {2, 1, 2, 1}}, /* X+ */
{{1, 0, 4, 5}, {0, 0, 0, 0}}, /* y+ */
{{2, 3, 7, 6}, {0, 0, 0, 0}}, /* Y+ */
{{0, 1, 3, 2}, {2, 1, 2, 1}}, /* z+ */
{{5, 4, 6, 7}, {2, 1, 2, 1}} /* Z+ */
};
/* A series of indexes into sides that indicates the turns required to
* orient piece zero to positions zero. Terminated by -1.
*/
/* *INDENT-OFF* */
static const orienting_turns_t orienting_turns[] = {
{{-1, -1, -1, -1}}, /* piece 0 at 0 */
{{ 3, -1, -1, -1}}, /* piece 0 at 1 */
{{ 5, -1, -1, -1}}, /* piece 0 at 2 */
{{ 5, 5, -1, -1}}, /* piece 0 at 3 */
{{ 1, -1, -1, -1}}, /* piece 0 at 4 */
{{ 3, 3, -1, -1}}, /* piece 0 at 5 */
{{ 1, 1, -1, -1}}, /* piece 0 at 6 */
{{ 1, 1, 3, -1}} /* piece 0 at 7 */
};
/* *INDENT-ON* */
/* Utility functions */
/* Add memory to a list of items that are to be freed later. */
static void
freeitem_add(void *ptr, int is_mmap, size_t size)
{
freeitem_t *fi = malloc(sizeof(*fi));
if (!fi)
{
/* If memory has been exhausted then just leak this item. */
return;
}
fi->next = freeitem;
fi->ptr = ptr;
fi->is_mmap = is_mmap;
fi->size = size;
freeitem = fi;
}
/* Iterate through the freeitem linked list of items and either free or unmap
* them.
*/
static void
freeitem_free()
{
freeitem_t *fi;
freeitem_t *fi_next;
for (fi = freeitem; fi; fi = fi_next)
{
if (fi->is_mmap)
{
#ifdef HAVE_MMAP
/* Don't bother with error handling since we are shutting down. */
munmap(fi->ptr, fi->size);
#endif
}
else
{
free(fi->ptr);
}
fi_next = fi->next;
free(fi);
}
}
/* Error handling functions */
/* Logs a message to stderr. If the level is high enough then the errno
* may be decoded. For fatal errors this program is aborted.
*/
static void
log_msg(level_t level, const char *fmt, ...)
{
va_list ap;
if (level < LOG_LEVEL)
{
return;
}
va_start(ap, fmt);
vfprintf(stderr, fmt, ap);
if ((level >= level_warning) && errno)
{
fprintf(stderr, "errno=%d - %s\n", errno, strerror(errno));
}
if (level >= level_fatal)
{
fprintf(stderr, "FATAL ERROR. Exiting.\n");
exit(1);
}
va_end(ap);
}
/* Conversion functions */
/* Convert a list of unique items ("perms") to a mixed based number ("digits")
* that is equal to the unique items' index if the list of all possible
* unique items were put in reverse order. For example consider the various
* permutations of 'A', 'B' and 'C' if they were arranged in reverse order and
* what their "digits" would be:
*
* Perms Digits Index
* CBA 000 0
* CAB 010 1
* BCA 100 2
* BAC 110 3
* ACB 200 4
* ABC 210 5
*
* In the above the index is determined as a function of the digits where
* each digit has some weighted value. The first (most significant) digit is
* worth 2, the second is worth 1 and the last zero. So, BAC, for example,
* is worth 2 * 1 + 1 * 1 + 0 * 1 = 3
*
* Each digit is equal to the number of less significant items that follow the
* item that corresponds to the digit that are greater in value. For example
* For BAC the digit that corresponds to the 'B' is 1 because there is one
* less significant item that follows that is greater in value (the 'C'
* but not the 'A').
*
* The above definition, particularly the part about it being in reverse order,
* was chosen so that the solved position is at index zero. The solved position
* involves placing the lowest numbered pieces in the least significant
* locations
*/
static void
digits_from_perms(int *digits, int *perms, int num)
{
int digit_val;
int item_index;
int item_scan;
memset(digits, 0, num * sizeof(int));
for (item_index = num - 1; item_index >= 0; item_index--)
{
digit_val = 0;
for (item_scan = item_index - 1; item_scan >= 0; item_scan--)
{
if (perms[item_scan] > perms[item_index])
{
digit_val++;
}
}
digits[item_index] = digit_val;
}
}
/* This does the reverse of digits_from_perms(). See that functions comments
* for details.
*/
static void
perms_from_digits(int *perms, int *digits, int num)
{
int item_index;
int perm_buff;
int perm_sort;
for (item_index = 0; item_index < num; item_index++)
{
perms[item_index] = num - item_index;
}
for (item_index = num - 1; item_index >= 0; item_index--)
{
/* Place the number indicated by the mixed case number first. */
perm_buff = perms[item_index];
perms[item_index] = perms[digits[item_index]];
perms[digits[item_index]] = perm_buff;
if (digits[item_index] < (item_index - 1))
{
/* Make sure that the remaining perms are in descending order. */
for (perm_sort = digits[item_index]; perm_sort < (item_index - 1);
perm_sort++)
{
perms[perm_sort] = perms[perm_sort + 1];
}
perms[item_index - 1] = perm_buff;
}
}
}
/* Converts a numeric rotation to something descriptive. */
static char
rot_to_char(int rot)
{
switch (rot)
{
case 0:
return '-';
case 1:
return 'L';
case 2:
return 'R';
default:
return '?'; /* This should not happen. */
}
}
/* Converts a descriptive rotation to something numeric. */
static int
char_to_rot(char rot)
{
switch (rot)
{
case '-':
return 0;
case 'L':
return 1;
case 'R':
return 2;
default:
return 999; /* This should not happen. */
}
}
/* Converts a numeric position to something descriptive. The 8 small cubes
* are numbered 0 through 7. They are enumerated by looping through the cubes
* X, Y and Z axis with the X axis in the inner most loop.
* */
static char *
pos_to_str(int pos, char *str)
{
int x_front = 1 & pos;
int y_front = 2 & pos;
int z_front = 4 & pos;
sprintf(str, "%c%c%c", 'X' + (x_front ? 0 : LOWER),
'Y' + (y_front ? 0 : LOWER), 'Z' + (z_front ? 0 : LOWER));
return str;
}
/* Convert a numeric piece to something descriptive (the colors that appears
* on that piece / small cube).
*/
static char *
piece_to_str(int piece, char *str)
{
int x_front = 1 & piece;
int y_front = 2 & piece;
int z_front = 4 & piece;
sprintf(str, "%c%c%c", (x_front ? 'R' : 'O'), (y_front ? 'B' : 'G'),
(z_front ? 'W' : 'Y'));
return str;
}
/* Output functions */
/* Output the state of the cube. Each small cube / piece is displayed as
* well as the rotation. Note that the numeric columns demonstrate the format
* of input files.
*/
static void
cube_print(cube_t * cube)
{
char piece_str[4];
char pos_str[4];
int pos_index;
printf("Pos #\tPos\tPiece #\tPiece\tRotation\n");
for (pos_index = 0; pos_index <= 7; pos_index++)
{
printf("%d\t%s\t%d\t%s\t%c\n", pos_index,
pos_to_str(pos_index, pos_str), cube->pos[pos_index].piece,
piece_to_str(cube->pos[pos_index].piece, piece_str),
rot_to_char(cube->pos[pos_index].rot));
}
}
static void
print_twist(int front, char axis, int sign)
{
printf("%c%c ", axis + (front ? 0 : ('a' - 'A')), (sign > 0) ? '+' : '-');
}
/* Cube functions */
/* Make sure that the rotations of the pieces are such that the cube is
* solvable. Rotating one of the eight pieces without making any other changes
* results in a cube that can not be solved.
*/
static int
cube_rot_check(cube_t * cube)
{
int pos_index;
int rot_total = 0;
for (pos_index = 0; pos_index <= 7; pos_index++)
{
rot_total += cube->pos[pos_index].rot;
}
return rot_total % 3;
}
/* A lower level version of cube_twist(). It applies a twist by taking a
* mapping for the sides and rotations (which small cube gets mapped to which
* position, etc.). See cube_twist() for details.
*/
static void
cube_rot_circulate(cube_t * cube, const int rots[], const int poss[], int num,
int sign)
{
int item_index;
mini_cube_t mc_buf;
for (item_index = 0; item_index < num; item_index++)
{
cube->pos[poss[item_index]].rot = (cube->pos[poss[item_index]].rot
+ rots[item_index]) % 3;
}
if (sign == 1)
{
mc_buf = cube->pos[poss[0]];
for (item_index = 0; item_index < (num - 1); item_index++)
{
cube->pos[poss[item_index]] = cube->pos[poss[item_index + 1]];
}
cube->pos[poss[num - 1]] = mc_buf;
}
else
{
mc_buf = cube->pos[poss[num - 1]];
for (item_index = num - 1; item_index > 0; item_index--)
{
cube->pos[poss[item_index]] = cube->pos[poss[item_index - 1]];
}
cube->pos[poss[0]] = mc_buf;
}
}
/* Reduce the size required for the database by taking advantage of symmetry.
* Before attempting to find the index for a given cube it is first oriented
* into a standard position such that the zero cube (piece 0) is in
* position 0. Also, the cube is rotated so that the zero cube has no rotation.
* This results in the zero cube always being it it's solved location and
* rotation, so it can be ignored for the index calculation.
*/
static void
cube_orient(cube_t * cube)
{
int pos_zero; /* Position of the zero cube. */
int side;
int turn;
int xside; /* The opposing parallel side. */
/* Find the location of the zero cube. */
for (pos_zero = 0; (pos_zero <= 7) && cube->pos[pos_zero].piece;
pos_zero++);
/* Rotate the entire cube so that the zero cube ends up in the zero
* position.
*/
for (turn = 0; (side = orienting_turns[pos_zero].turns[turn])
!= -1; turn++)
{
/* Turn the cube along the specified side. */
cube_rot_circulate(cube, sides[side].rots, sides[side].poss, 4, 1);
/* Determine the opposite side and sign (ex., X+ becomes x-) and
* perform that turn. The result is the entire cube is turned.
*/
xside = 1 ^ side;
cube_rot_circulate(cube, sides[xside].rots, sides[xside].poss, 4, -1);
}
/* Rotate the entire cube along the diagonal axis that passes through
* position 0 and position 7 so that the zero cube no longer has any
* rotation. It turns out that rotating the entire cube along this
* diagonal axis circulates smaller cubes around paths that are three cubes
* long.
*/
switch ((3 - cube->pos[0].rot) % 3)
{
case 1:
/* Zero cube at position 0 is rotated to the right. */
cube->pos[0].rot = (cube->pos[0].rot + 1) % 3;
{
const int rots[] = { 2, 2, 2 };
const int poss[] = { 4, 1, 2 };
cube_rot_circulate(cube, rots, poss, 3, 1);
}
{
const int rots[] = { 1, 1, 1 };
const int poss[] = { 5, 3, 6 };
cube_rot_circulate(cube, rots, poss, 3, 1);
}
cube->pos[7].rot = (cube->pos[7].rot + 2) % 3;
break;
case 2:
/* Zero cube at position 0 is rotated to the left. */
cube->pos[0].rot = (cube->pos[0].rot + 2) % 3;
{
const int rots[] = { 1, 1, 1 };
const int poss[] = { 2, 1, 4 };
cube_rot_circulate(cube, rots, poss, 3, 1);
}
{
const int rots[] = { 2, 2, 2 };
const int poss[] = { 6, 3, 5 };
cube_rot_circulate(cube, rots, poss, 3, 1);
}
cube->pos[7].rot = (cube->pos[7].rot + 1) % 3;
break;
}
}
/* Get and index for a cube by first converting the positions and the rotations
* to a mixed base number. See digits_from_perms() for details.
*/
static void
cube_set_index(cube_t * cube)
{
cube_t cube_loc = *cube;
int digit;
int digits[13];
int pieces[7];
int pos_index;
cube_orient(&cube_loc);
for (pos_index = 1; pos_index <= 7; pos_index++)
{
pieces[pos_index - 1] = cube_loc.pos[pos_index].piece;
if (pos_index != 7)
{
digits[pos_index - 1] = cube_loc.pos[pos_index].rot;
}
}
digits_from_perms(digits + 6, pieces, 7);
cube->index = 0;
for (digit = 12; digit >= 0; digit--)
{
cube->index += digit_value[digit] * digits[digit];
}
}
/* A constructor that returns a new cube based on a specified cube. */
cube_t *
cube_new_cube(cube_t * cube)
{
cube_t *cube_new;
if (!(cube_new = malloc(sizeof(*cube_new))))
{
log_msg(level_fatal, "Unable to allocate %d bytes for a cube_new\n",
DB_SIZE);
}
*cube_new = *cube;
/* Assume the caller will keep a reference to the cube_new returned. */
return cube_new;
}
/* A constructor that creates a new cube by loading it from a file. The cube
* file has three columns:
* Position Number Piece Number Rotation
* Errors reading the specified file causes this program to abort.
*/
static cube_t *
cube_new_fname(char *cf_name)
{
FILE *cf_fp;
char rot[2]; /* Character and null terminator. */
cube_t *cube;
int piece;
int pos;
int total_rot;
if (!(cf_fp = fopen(cf_name, "r")))
{
log_msg(level_fatal, "Could not open cube file for read: %s\n",
cf_name);
}
printf("Loading %s:\n\n", cf_name);
cube = calloc(1, sizeof(*cube));
while (3 == fscanf(cf_fp, "%d%d%1s\n", &pos, &piece, rot))
{
if ((pos < 0) || (pos > 7))
{
log_msg(level_fatal,
"Position with value %d is outside the allowed "
"[0, 7] range.\n", pos, pos);
}
if ((piece < 0) || (piece > 7))
{
log_msg(level_fatal, "Piece with value %d is outside the allowed "
"[0, 7] range.\n", piece, piece);
}
cube->pos[pos].piece = piece;
cube->pos[pos].rot = char_to_rot(*rot);
if (cube->pos[pos].rot == 999)
{
log_msg(level_fatal, "Invalid rotation of '%s' specified. Only "
"'L', '-' and 'R' are allowed.\n", rot);
}
}
fclose(cf_fp);
cube_print(cube);
if ((total_rot = cube_rot_check(cube)))
{
log_msg(level_fatal, "The pieces have an additional rotation of %d "
"(the sum of the rotations mod 3 is not zero). Can not "
"solve.\n", total_rot);
}
cube_set_index(cube);
return cube;
}
/* A constructor that creates a new cube from a specified index. */
static cube_t *
cube_new_index(int index)
{
cube_t *cube;
int digit;
int digits[13];
int pieces[7];
int pos_index;
int remaining = index;
cube = calloc(1, sizeof(*cube));
memset(cube, 0, sizeof(cube));
for (digit = 12; digit >= 0; digit--)
{
digits[digit] = remaining / digit_value[digit];
remaining -= digits[digit] * digit_value[digit];
}
perms_from_digits(pieces, digits + 6, 7);
for (pos_index = 1; pos_index <= 7; pos_index++)
{
cube->pos[pos_index].piece = pieces[pos_index - 1];
if (pos_index != 7)
{
cube->pos[pos_index].rot = digits[pos_index - 1];
}
else
{
/* The rotation of the last cube can be deduced. */
cube->pos[pos_index].rot = (3 - cube_rot_check(cube)) % 3;
}
}
cube->index = index;
return cube;
}
/* Shallow free of the specified cube. */
static void
cube_free(cube_t * cube)
{
if (cube)
{
free(cube);
}
}
/* Deep free of the specified cube. The term "history" is used since the
* linked list is traversed backwards to free the older cubes.
*/
static void
cube_free_history(cube_t * cube)
{
cube_t *cube_prev;
while (cube)
{
cube_prev = cube->prev;
cube_free(cube);
cube = cube_prev;
}
}
/* Perform a given twist by causing the pieces to switch places. The rotations
* are updated for pieces that cross the X-Z plane.
*/
static cube_t *
cube_twist(cube_t * cube, int front, char axis, int sign)
{
cube_t *next_cube;
int side;
next_cube = cube_new_cube(cube);
next_cube->prev = cube;
cube->next = next_cube;
side = 2 * (axis - 'X') + front;
cube_rot_circulate(next_cube, sides[side].rots, sides[side].poss, 4,
sign);
cube_set_index(next_cube);
return next_cube;
}
/* Undoes a twist by reverting to the saved cube and index.
*/
static cube_t *
cube_untwist(cube_t * cube, int do_free)
{
cube_t *prev_cube;
/* This assumes that when a twist is undone it is not redone again later. */
prev_cube = cube->prev;
if (do_free)
{
cube_free(cube);
}
prev_cube->next = NULL;
return prev_cube;
}
/* Try each possible twist and find the twist / twist that works best (that
* gets the cube closer to being solved).
*/
cube_t *
cube_best_twist(cube_t * cube, char *db, int mode, int *num_good_twists)
{
char axis;
char axis_best;
cube_t *cube_best = NULL;
int num_twists;
int score;
int score_best;
int sign;
int sign_best;
if (num_good_twists)
{
*num_good_twists = 0;
}
if ((cube->index < 0) || (cube->index >= DB_SIZE))
{
log_msg(level_fatal, "Invalid position. index=%d\n", cube->index);
}
num_twists = db[cube->index];
log_msg(level_debug, "num_twists=%d\n", num_twists);
if (SOLVE & mode)
{
if (!num_twists)
{
/* The cube is already solved. */
return NULL;
}
/* Start with the current score so that only twists that get closer to
* solved are considered.
*/
score_best = num_twists << 16;
}
for (axis = 'X'; axis <= 'Z'; axis++)
{
for (sign = -1; sign <= 1; sign += 2)
{
cube = cube_twist(cube, 1, axis, sign);
if (GENERATE & mode)
{
if (db[cube->index] > (num_twists + 1))
{
db[cube->index] = num_twists + 1;
if (num_good_twists)
{
(*num_good_twists)++;
}
}
}
if (SOLVE & mode)
{
#ifdef RND_SOLUTIONS
/* Pick a twist at random that gets it closer to solved . */
score = (db[cube->index] << 16) + (rand() % 0x10000);
#else
/* Construct the score so that following is considered in
* order of importance:
* 1) Twists that reduce the number of twists from solved.
* 2) Twists that are in a positive direction.
* 3) First 'X", then 'Y' and finally 'Z'.
*/
score = (db[cube->index] << 16) + ((1 - sign) << 8) + axis;
#endif
log_msg(level_debug, "score=%06x axis=%c sign=%2d\n", score,
axis, sign);
if (score < score_best)
{
score_best = score;
log_msg(level_debug, "score_best=%06x\n", score_best);
if (cube_best)
{
cube_free(cube_best);
}
cube_best = cube;
axis_best = axis;
sign_best = sign;
if (num_good_twists)
{
(*num_good_twists)++;
}
}
}
cube = cube_untwist(cube, cube != cube_best);
}
}
if ((SOLVE & mode) && cube_best)
{
print_twist(1, axis_best, sign_best);
}
return cube_best;
}
/* Solve the cube by starting with init_cube and seeing which twists, according
* to the database, brings the cube closer to being solved.
*/
static cube_t *
cube_solve(cube_t * cube, char *db)
{
cube_t *cube_last = NULL;
while ((cube = cube_best_twist(cube, db, SOLVE, NULL)))
{
cube_last = cube; /* The last non-null cube found. */
}
if (!cube_last)
{
/* Due to previous input checking the following should never happen. */
log_msg(level_fatal, " Unable to find any twist that improves the "
"specified cube.\n");
}
if (cube_last->index)
{
log_msg(level_warning,
" Index %d instead of 0. Solution not valid.\n",
cube_last->index);
}
putchar('\n');
return cube_last;
}
/* Database functions */
/* For a given index set the number of twists from solved. Although currently
* the database is just an array this allows for some abstraction.
*/
static int
dbase_set_twists(char *db, int num_twists)
{
cube_t *cube;
int index;
int num_changes;
int num_total = 0;
for (index = 0; index < DB_SIZE; index++)
{
if (db[index] == num_twists)
{
cube = cube_new_index(index);
cube_best_twist(cube, db, GENERATE, &num_changes);
cube_free(cube);
num_total += num_changes;
}
}
printf("%d positions found %d twists from solved.\n", num_total,
num_twists + 1);
return num_total;
}
/* A constructor that creates a new database by allocating an array, marking the
* solved position as zero twists from being solved and then working backwards
* (one positions one twist from solved are marked as one twist from solved,
* etc.).
*/
static char *
dbase_new_fname_gen(char *fname, int *do_mmap)
{
#ifdef HAVE_MMAP
int db_fd;
#else
FILE *db_fp;
#endif
char *db;
int num_twists;
struct stat db_stat;
/* Delete the db, if it exists. */
if (stat(fname, &db_stat) != -1)
{
if (remove(fname) == -1)
{
log_msg(level_fatal, "Unable to remove existing database at %s\n",
fname);
}
}
#ifdef HAVE_MMAP
*do_mmap = 1;
/* Although 0666 is used for the following the umask will limit the
* permissions on the resulting file.
*/
if ((db_fd = open(fname, O_CREAT | O_RDWR, 0666)) == -1)
{
log_msg(level_fatal, "Unable to open the database at %s\n", fname);
}
/* Make sure a sparse file exists by seeking forward and writing a single
* zero at the end.
*/
lseek(db_fd, DB_SIZE - 1, SEEK_SET);
write(db_fd, "", 1);
if ((db =
mmap(NULL, DB_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, db_fd,
0)) == MAP_FAILED)
{
log_msg(level_fatal, "Unable to mmap the database at %s\n", fname);
}
close(db_fd);
#else
*do_mmap = 0;
if (!(db = malloc(DB_SIZE)))
{
log_msg(level_fatal, "Unable to allocate %d bytes for db\n", DB_SIZE);
}
#endif
memset(db, MAX_TWISTS, DB_SIZE);
db[0] = 0; /* Mark the first position as solved. */
for (num_twists = 0; num_twists < MAX_TWISTS; num_twists++)
{
if (!dbase_set_twists(db, num_twists))
{
/* No changes to the database were made. */
break;
}
}
#ifndef HAVE_MMAP
if (!(db_fp = fopen(fname, "wb")))
{
log_msg(level_fatal, "Could not open database for write: %s\n",
fname);
}
fwrite(db, DB_SIZE, 1, db_fp);
fclose(db_fp);
#endif
return db;
}
/* A constructor that creates a new database by loading it from a specified file.
*/
static char *
dbase_new_fname_load(const char *fname, int *do_mmap)
{
#ifdef HAVE_MMAP
int db_fd;
#else
FILE *db_fp;
#endif
char *db;
struct stat db_stat;
if (stat(fname, &db_stat) == -1)
{
log_msg(level_fatal, "Unable to stat the database at %s\n", fname);
}
if (db_stat.st_size != DB_SIZE)
{
log_msg(level_fatal, "Database at %s is %d bytes instead of %d\n",
fname, db_stat.st_size, DB_SIZE);
}
#ifdef HAVE_MMAP
*do_mmap = 1;
if ((db_fd = open(fname, O_RDONLY)) == -1)
{
log_msg(level_fatal, "Unable to open the database at %s\n", fname);
}
if ((db = mmap(NULL, DB_SIZE, PROT_READ, MAP_PRIVATE, db_fd, 0)) ==
MAP_FAILED)
{
log_msg(level_fatal, "Unable to mmap the database at %s\n", fname);
}
close(db_fd);
#else
*do_mmap = 0;
if (!(db = malloc(DB_SIZE)))
{
log_msg(level_fatal, "Unable to allocate %d bytes to load the "
"db\n", DB_SIZE);
}
if (!(db_fp = fopen(fname, "rb")))
{
log_msg(level_fatal, "Could not open database for read: %s\n", fname);
}
/* TODO: Add other validation. Maybe the database should have a magic
* header. Maybe it should be stat'd to make sure it is the right size.
*/
if (fread(db, DB_SIZE, 1, db_fp) < 1)
{
fclose(db_fp);
log_msg(level_fatal, "Short read for the db: %s\n", fname);
}
fclose(db_fp);
#endif
return db;
}
/* Misc functions */
/* Do whatever has to be done for shutdown. */
static void
deinit()
{
freeitem_free();
}
/* Initialize global arrays that are redundant to other data (arrays where it
* would be inefficient for them to have their own initializers).
*/
static void
init()
{
int digit;
int digit_val = 1;
for (digit = 0; digit <= 12; digit++)
{
digit_value[digit] = digit_val;
digit_val *= digit_base[digit];
}
atexit(deinit);
}
/* Test the code by applying various twists and then the corresponding
* anti-twist. After each anti-twist the cube should return to it's original
* solved state with an index of 0 where dbase[0] = 0 (the solved cube,
* stored at index 0, is 0 twists from being solved).
*/
static void
test(const char *db)
{
cube_t *cube;
printf("The database is %sloaded.\n\n", db ? "" : "NOT ");
cube = cube_new_index(0);
cube = cube_twist(cube, 1, 'X', 1);
printf("X+ index=%d from_solved=%d\n", cube->index,
db ? db[cube->index] : 0);
cube_print(cube);
cube = cube_twist(cube, 1, 'X', -1);
printf("\nX- index=%d from_solved=%d\n", cube->index,
db ? db[cube->index] : 0);
cube_print(cube);
cube = cube_twist(cube, 0, 'Y', 1);
printf("\nY+ index=%d from_solved=%d\n", cube->index,
db ? db[cube->index] : 0);
cube_print(cube);
cube = cube_twist(cube, 0, 'Y', -1);
printf("\nY- index=%d from_solved=%d\n", cube->index,
db ? db[cube->index] : 0);
cube_print(cube);
cube = cube_twist(cube, 0, 'Z', 1);
printf("\nZ+ index=%d from_solved=%d\n", cube->index,
db ? db[cube->index] : 0);
cube_print(cube);
cube = cube_twist(cube, 0, 'Z', -1);
printf("\nZ- index=%d from_solved=%d\n", cube->index,
db ? db[cube->index] : 0);
cube_print(cube);
cube_free_history(cube);
}
/* Simple usage statement. */
static void
usage(const char *name)
{
fprintf(stderr, "Usage: %s -g dbase\n", name);
fprintf(stderr, "Usage: %s [-l dbase] [-n solutions] -s cube file "
"[-s cube file ...]\n", name);
fprintf(stderr, "Usage: %s -t\n", name);
exit(1);
}
/* Main entry point. This parses command line options and calls everything
* else.
*/
int
main(int argc, char *argv[], char *envp[])
{
char *cf_name[MAX_CF_NAMES];
char *db;
char *dbase_fname = NULL;
char opt_char;
char opt_err = 0;
cube_t *cube_init;
cube_t *cube_solved;
int cube_file_index;
int cube_files = 0;
int do_mmap;
int mode = NOOP;
int sol_count;
int solutions = 1;
int solve_args = 0;
init();
while (EOF != (opt_char = getopt(argc, argv, "g:l:n:s:t")))
{
switch (opt_char)
{
case 'g':
mode |= GENERATE;
dbase_fname = strdup(optarg);
break;
case 'l':
mode |= SOLVE;
solve_args++;
dbase_fname = strdup(optarg);
break;
case 'n':
mode |= SOLVE;
solve_args++;
solutions = atoi(optarg);
break;
case 's':
mode |= SOLVE;
solve_args++;
if (cube_files == 200)
{
log_msg(level_fatal, "Too many cube files specified.");
break;
}
cf_name[cube_files++] = optarg;
break;
case 't':
mode |= TEST;
break;
default:
opt_err = 1;
}
}
if (!dbase_fname)
{
asprintf(&dbase_fname, "%s/%s.db", JC_LIB_DIR, basename(argv[0]));
}
if (!dbase_fname)
{
log_msg(level_fatal,
"Unable to allocate memory for the database name.");
}
freeitem_add(dbase_fname, 0, 0);
if (!mode || (mode > TEST) || opt_err ||
((mode == GENERATE) && (argc != 3)) ||
((mode == SOLVE) && !cube_files) ||
((mode == SOLVE) && (argc != (1 + 2 * solve_args))))
{
usage(basename(argv[0]));
}
if (GENERATE & mode)
{
db = dbase_new_fname_gen(dbase_fname, &do_mmap);
}
else
{
db = dbase_new_fname_load(dbase_fname, &do_mmap);
}
freeitem_add(db, do_mmap, DB_SIZE);
if (TEST & mode)
{
test(db);
}
else if (SOLVE & mode)
{
for (cube_file_index = 0; cube_file_index < cube_files;
cube_file_index++)
{
cube_init = cube_new_fname(cf_name[cube_file_index]);
printf("\nSolutions:\n");
for (sol_count = 1; sol_count <= solutions; sol_count++)
{
printf(" #%d: ", sol_count);
cube_solved = cube_solve(cube_init, db);
if (cube_solved)
{
cube_free_history(cube_solved);
}
}
if (cube_file_index != (cube_files - 1))
{
/* Newline if not the last cube. */
putchar('\n');
}
}
}
return 0;
}