Switched (unfortunatelly) to c++, added sensible makefile

1 files changed, 415 insertions, 0 deletions

diff --git a/src/cube.h b/src/cube.h
new file mode 100644
index 0000000..3ea20eb
--- /dev/null
+++ b/src/cube.h
@@ -0,0 +1,415 @@
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#ifndef _CUBE_H_
+#define _CUBE_H_
+
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <unistd.h>
+
+#include "khash.h"
+
+#define FACE32
+// #define FACE64
+
+#ifdef FACE32
+typedef uint32_t face_t;
+const uint32_t M012 = 0x00000fff;
+const uint32_t M234 = 0x000fff00;
+const uint32_t M456 = 0x0fff0000;
+const uint32_t M670 = 0xff00000f;
+#else
+typedef uint64_t face_t;
+#endif /* FACE32 */
+
+typedef enum {
+  UP = 0,
+  LEFT = 1,
+  FRONT = 2,
+  RIGHT = 3,
+  BACK = 4,
+  DOWN = 5
+} cube_side;
+
+typedef enum {
+  WHITE = 0,
+  ORANGE = 1,
+  GREEN = 2,
+  RED = 3,
+  BLUE = 4,
+  YELLOW = 5,
+  EMPTY_COLOR = 6
+} colors;
+
+typedef struct {
+  face_t faces[6];
+} cube_t;
+
+/******************************************************************************/
+/* Macros for generating rotation functions ***********************************/
+
+#define ROR(x, y) (face_t)((long)(x) >> (y) | (long)(x) << ((8*sizeof(face_t)) - (y)))
+static inline face_t ror(face_t x, face_t y) {
+  return ROR(x, y);
+}
+
+#define PASTE(to, from, M1, M2) {                                           \
+  to = ((to) & ~(M ## M1)) | ((from) & M ## M2);                           \
+}
+
+#define PASTE_ROR(to, from, M1, M2, len) {                                  \
+  (to) = ((to) & ~(M ## M1)) | ror((from) & M ## M2, len * sizeof(face_t)); \
+}
+
+#define PASTE_FACE(cube, to, from, M1, M2) { 		\
+  PASTE((cube).faces[to], (cube).faces[from], M1, M2);	\
+}
+
+#define PASTE_FACE_ROR(cube, to, from, M1, M2, len) {		\
+  PASTE_ROR((cube).faces[to], (cube).faces[from], M1, M2, len);	\
+}
+
+#define ABSTRACT_ROTATION_90(cube, face, len, f0, M0, f1, M1, f2, M2, f3, M3, C0, C1, C2, C3) { \
+  (cube).faces[face] = ror((cube).faces[face], len * sizeof(face_t));			\
+  face_t temporary_var = (cube).faces[f0];					\
+  PASTE_FACE_ROR(cube, f0, f1, M0, M1, C0);					\
+  PASTE_FACE_ROR(cube, f1, f2, M1, M2, C1);					\
+  PASTE_FACE_ROR(cube, f2, f3, M2, M3, C2);					\
+  PASTE_ROR((cube).faces[f3], temporary_var, M3, M0, C3);	\
+}
+
+#define ABSTRACT_ROTATION_180(cube, face, f0, M0, f1, M1, f2, M2, f3, M3, C01, C23) {	\
+  (cube).faces[face] = ror((cube).faces[face], 4 * sizeof(face_t));	\
+  face_t temporary_var = (cube).faces[f0];							\
+  PASTE_FACE_ROR(cube, f0, f1, M0, M1, C01);						\
+  PASTE_ROR((cube).faces[f1], temporary_var, M1, M0, C01);			\
+  temporary_var = (cube).faces[f2];									\
+  PASTE_FACE_ROR(cube, f2, f3, M2, M3, C23);						\
+  PASTE_ROR((cube).faces[f3], temporary_var, M3, M2, C23);			\
+}
+
+#define DEFINE_ROTATION_90(rotation, face, len, f0, M0, f1, M1, f2, M2, f3, M3, C0, C1, C2, C3)	\
+static void rotation_ ## rotation (cube_t *cube) {	\
+  ABSTRACT_ROTATION_90(*cube, face, len, f0, M0, f1, M1, f2, M2, f3, M3, C0, C1, C2, C3);	\
+}
+
+#define DEFINE_ROTATION_180(rotation, face, f0, M0, f1, M1, f2, M2, f3, M3, C01, C23)	\
+static void rotation_ ## rotation (cube_t *cube) {	\
+  ABSTRACT_ROTATION_180(*cube, face, f0, M0, f1, M1, f2, M2, f3, M3, C01, C23);	\
+}
+
+/* Clockwise rotations */
+DEFINE_ROTATION_90(r, RIGHT, 6, FRONT, 234, DOWN, 234, BACK, 670, UP, 234, 0, 4, 4, 0)
+DEFINE_ROTATION_90(l, LEFT, 6, FRONT, 670, UP, 670, BACK, 234, DOWN, 670, 0, 4, 4, 0)
+DEFINE_ROTATION_90(u, UP, 6, FRONT, 012, RIGHT, 012, BACK, 012, LEFT, 012, 0, 0, 0, 0)
+DEFINE_ROTATION_90(d, DOWN, 6, FRONT, 456, LEFT, 456, BACK, 456, RIGHT, 456, 0, 0, 0, 0)
+DEFINE_ROTATION_90(f, FRONT, 6, UP, 456, LEFT, 234, DOWN, 012, RIGHT, 670, 6, 6, 6, 6)
+DEFINE_ROTATION_90(b, BACK, 6, UP, 012, RIGHT, 234, DOWN, 456, LEFT, 670, 2, 2, 2, 2)
+
+/* Counter clockwise rotations */
+DEFINE_ROTATION_90(rp, RIGHT, 2, FRONT, 234, UP, 234, BACK, 670, DOWN, 234, 0, 4, 4, 0)
+DEFINE_ROTATION_90(lp, LEFT, 2, FRONT, 670, DOWN, 670, BACK, 234, UP, 670, 0, 4, 4, 0)
+DEFINE_ROTATION_90(up, UP, 2, FRONT, 012, LEFT, 012, BACK, 012, RIGHT, 012, 0, 0, 0, 0)
+DEFINE_ROTATION_90(dp, DOWN, 2, FRONT, 456, RIGHT, 456, BACK, 456, LEFT, 456, 0, 0, 0, 0)
+DEFINE_ROTATION_90(fp, FRONT, 2, UP, 456, RIGHT, 670, DOWN, 012, LEFT, 234, 2, 2, 2, 2)
+DEFINE_ROTATION_90(bp, BACK, 2, UP, 012, LEFT, 670, DOWN, 456, RIGHT, 234, 6, 6, 6, 6)
+
+/* Double clockwise */
+DEFINE_ROTATION_180(r2, RIGHT, FRONT, 234, BACK, 670, UP, 234, DOWN, 234, 4, 0)
+DEFINE_ROTATION_180(l2, LEFT, FRONT, 670, BACK, 234, UP, 670, DOWN, 670, 4, 0)
+DEFINE_ROTATION_180(u2, UP, FRONT, 012, BACK, 012, RIGHT, 012, LEFT, 012, 0, 0)
+DEFINE_ROTATION_180(d2, DOWN, FRONT, 456, BACK, 456, RIGHT, 456, LEFT, 456, 0, 0)
+DEFINE_ROTATION_180(f2, FRONT, UP, 456, DOWN, 012, RIGHT, 670, LEFT, 234, 4, 4)
+DEFINE_ROTATION_180(b2, BACK, UP, 012, DOWN, 456, RIGHT, 234, LEFT, 670, 4, 4)
+
+typedef enum {
+  ROT_R = 0,
+  ROT_L,
+  ROT_U,
+  ROT_D,
+  ROT_F,
+  ROT_B,
+  ROT_RP,
+  ROT_LP,
+  ROT_UP,
+  ROT_DP,
+  ROT_FP,
+  ROT_BP,
+  ROT_R2,
+  ROT_L2,
+  ROT_U2,
+  ROT_D2,
+  ROT_F2,
+  ROT_B2,
+  NULL_ROT
+} rotations;
+
+typedef void (*rot_f)(cube_t *);
+
+static const rot_f rot_func[] = {
+  rotation_r,
+  rotation_l,
+  rotation_u,
+  rotation_d,
+  rotation_f,
+  rotation_b,
+  rotation_rp,
+  rotation_lp,
+  rotation_up,
+  rotation_dp,
+  rotation_fp,
+  rotation_bp,
+  rotation_r2,
+  rotation_l2,
+  rotation_u2,
+  rotation_d2,
+  rotation_f2,
+  rotation_b2,
+};
+
+static void perform_rotations(cube_t *cube, rotations rots[]) {
+  while(*rots != NULL_ROT) {
+	rot_func[*rots](cube);	
+	rots++;
+  }
+}
+
+/******************************************************************************/
+/* Parsing rotations from input ***********************************************/
+
+#define PRIM_CHAR '\''
+
+static int str_to_rot(char *str, rotations *rot) {
+  ssize_t len = strlen(str);
+  int i;
+
+  if (len == 0 || len > 2) {
+	return -1;
+  }
+
+  const char rots_char[] = { 'R', 'L', 'U', 'D', 'F', 'B' };
+  for (i = 0; i < 6; i++) {
+	if (str[0] == rots_char[i]) {
+	  *rot = (rotations)i;
+	  if (len == 2) {
+		if (str[1] == PRIM_CHAR) {
+		  *(int*)rot += 6;
+		} else if (str[1] == '2') {
+		  *(int*)rot += 12;
+		}
+		else {
+		  return -1;
+		}
+	  }
+	  return 0;
+	}
+  }
+  return -1;
+}
+
+static rotations* parse_scramble(char **str) {
+  ssize_t sz = 0;
+  ssize_t i = 0;
+  char *rot_str = str[0];
+  while (rot_str) {
+	printf("token: %s\n", rot_str);
+	rot_str = str[++sz];
+  }
+
+  rotations *rots = (rotations *)calloc(sizeof(rotations), sz+1); 
+
+  for (i = 0; i < sz; i++) {
+	if (str_to_rot(str[i], &rots[i])) {
+	  free(rots);
+	  return NULL;
+	}
+  }
+
+  rots[sz] = NULL_ROT;
+
+  return rots;
+}
+
+static char **tokenize_rot_str(char *str) {
+  const char *delims = " \n\t";
+  ssize_t capacity = 20;
+  char **tokens = (char **)calloc(sizeof(char *), capacity);
+  int tok_cnt = 0;
+
+  char *tok = strtok(str, delims);
+  while (tok != NULL) {
+	tok_cnt++;
+	if (tok_cnt > capacity) {
+	  capacity *= 2;
+	  tokens = (char **)realloc(tokens, sizeof(char *) * capacity);
+	}
+	tokens[tok_cnt - 1] = tok;
+	tok = strtok(NULL, delims);
+  }
+
+  tokens = (char **)realloc(tokens, (sizeof(char *) * (1 + tok_cnt)));
+  tokens[tok_cnt] = NULL;
+
+  return tokens;
+}
+
+static rotations *rot_str_to_rotations(char *str_in) {
+  char *str = (char *)alloca(strlen(str_in) + 1);
+  memcpy(str, str_in, strlen(str_in) + 1);
+
+  char **tokens = tokenize_rot_str(str);
+  rotations *rots = parse_scramble(tokens); 
+  free(tokens);
+  return rots;
+}
+
+static int rotate_from_str(cube_t *cube, char *str) {
+  rotations *rot = rot_str_to_rotations(str);
+  if (!rot) {
+	return -1;
+  }
+  perform_rotations(cube, rot);
+  free(rot);
+  return 0;
+}
+
+static void init_cube(cube_t *cube) {
+  for (int face = 0; face < 6; face++) {
+	cube->faces[face] = 0;
+	for (int tile = 0; tile < 8; tile++) {
+	  cube->faces[face] |= (face << (tile * sizeof(face_t)));
+	}
+  }
+}
+
+/******************************************************************************/
+/* Printint cube state ********************************************************/
+
+static const char letters[] = { 'W', 'O', 'G', 'R', 'B', 'Y' };
+static const char *terminal_letters[] = {
+  "W",
+  "\e[35mO\e[0m",
+  "\e[32mG\e[0m",
+  "\e[31mR\e[0m",
+  "\e[34mB\e[0m",
+  "\e[33mY\e[0m",
+};
+
+static colors get_tile_color(face_t face, int tile) {
+  colors color = (colors)((face >> (tile * sizeof(face_t))) & 
+						  ((1<<sizeof(face_t)) - 1));
+  assert(color <= 5);
+  return color;
+}
+
+static void dump_face(face_t face, colors buf[3][3]) {
+  buf[0][0] = get_tile_color(face, 0); 
+  buf[0][1] = get_tile_color(face, 1); 
+  buf[0][2] = get_tile_color(face, 2); 
+  buf[1][0] = get_tile_color(face, 7); 
+  buf[1][2] = get_tile_color(face, 3); 
+  buf[2][0] = get_tile_color(face, 6); 
+  buf[2][1] = get_tile_color(face, 5); 
+  buf[2][2] = get_tile_color(face, 4); 
+  assert(buf[0][0] <= 5);
+}
+
+static void fill_face(cube_t *cube, cube_side face, colors buf[3][3]) {
+  dump_face(cube->faces[face], buf);
+  buf[1][1] = (colors)face;
+}
+
+static void dump_cube_grid(cube_t *cube) {
+  int i, j, row, col;
+  colors buf[3][4][3][3];	/* XD */
+
+  memset(buf, -1, 3*4*3*3*sizeof(colors));
+  fill_face(cube, UP, buf[0][1]);
+  fill_face(cube, LEFT, buf[1][0]);
+  fill_face(cube, FRONT, buf[1][1]);
+  fill_face(cube, RIGHT, buf[1][2]);
+  fill_face(cube, BACK, buf[1][3]);
+  fill_face(cube, DOWN, buf[2][1]);
+
+  for (i = 0; i < 3; i++) {
+	for (row = 0; row < 3; row++) {
+	  for (j = 0; j < 4; j++) {
+		for (col = 0; col < 3; col++) {
+		  colors color = buf[i][j][row][col];
+		  printf("%s", (color == -1 ? " " : terminal_letters[color])); 
+		} 
+	  }
+	  printf("\n");
+	}
+  }
+}
+
+/******************************************************************************/
+/* Hash map *******************************************************************/
+
+#ifdef FACE32
+#define P1 ((uint64_t)516077606561857057)
+#define P2 ((uint64_t)217685325020058187) 
+#define P3 ((uint64_t)843829397461693519)
+#define MOD_M 4200892139
+#define first_64(cube) (*(uint64_t*)((cube).faces))
+#define second_64(cube) (*(uint64_t*)((cube).faces+2))
+#define third_64(cube) (*(uint64_t*)((cube).faces+4))
+#define kh_cube_hash_func(cube) (khint32_t)((first_64(cube)*P1+second_64(cube)*P2+third_64(cube)*P3)%(uint64_t)MOD_M)
+#define kh_cube_hash_equal(cube1, cube2) (first_64(cube1) == first_64(cube2) && second_64(cube1) == second_64(cube2) && third_64(cube1) == third_64(cube2))
+
+
+#endif /* FACE32 */ 
+
+/******************************************************************************/
+/* Algorithm ******************************************************************/
+
+typedef uint32_t rot_cnt_t;
+#define build_rot_cnt(rot, cnt) (rot_cnt_t)(((uint32_t)rot << 16)|cnt)
+#define get_rot(rot_cnt) (((uint32_t)rot_cnt)>>16)
+#define get_cnt(rot_cnt) (uint32_t)(rot_cnt & 0xffff)
+
+KHASH_INIT(cube, cube_t, rot_cnt_t, 1, kh_cube_hash_func, kh_cube_hash_equal)
+
+khash_t(cube) *generate_pruning_table(int depth) {
+  khash_t(cube) *h = kh_init(cube); 
+
+}
+
+/******************************************************************************/
+/* Main ***********************************************************************/
+
+void test_scrambling() {
+  cube_t cube;
+  int i;
+  char *buf = NULL;
+  size_t sz;
+
+  while (getline(&buf, &sz, stdin) != -1) {
+	init_cube(&cube);
+	if (sz == 0) break;
+	printf("> %s\n", buf);
+	rotations *rots = rot_str_to_rotations(buf);
+	if (rots) {
+	  perform_rotations(&cube, rots);
+	  free(rots);
+	  dump_cube_grid(&cube);
+	} else {
+	  printf("Rots == null :o\n");
+	}
+  }
+
+  if (buf)
+	free(buf);
+}
+
+#endif /* _CUBE_H_ */
+
+#ifdef __cplusplus
+}
+#endif