JrCube Source
Sun, 02/15/2009 - 02:41 — sle
/*************************************************************************/ /* 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 <errno.h> #include <getopt.h> #include <libgen.h> #include <stdarg.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/stat.h> #include <sys/types.h> #include <time.h> #include <unistd.h> /* TODO: Come up with a better system to detect what features are available. */ #ifdef __linux__ #define HAVE_MMAP 1 #endif #ifdef HAVE_MMAP #include <fcntl.h> #include <sys/mman.h> #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; }
