/*
 * 
 *   lightsout.c
 *
 *   Authors:	2008 Vincent Cruz	[cruz.vincent@gmail.com]
 *
 *   This software is placed in the public domain and can be used freely
 *   for any purpose. It comes without any kind of warranty, either
 *   expressed or implied, including, but not limited to the implied
 *   warranties of merchantability or fitness for a particular purpose.
 *   Use it at your own risk. the author is not responsible for any damage
 *   or consequences raised by use or inability to use this program.
 *
 *   "Lights Out!" game for GGI.
 *
 */

#include <ggi/gg.h>
#include <ggi/gii.h>
#include <ggi/gii-keyboard.h>
#include <ggi/ggi.h>

#include <string.h>

#define BOARD_SIZE 5
#define SQR_BOARD_SIZE 25
#define MATRIX_DIM 23

#define IS_ON(t) ((t) & 0x01)
#define IS_OFF(t) (!((t) & 0x01))
#define HAS_HINT(t) ((t) & 0x80)

#define WINING_ANIM_DURATION 500

/*
 * Timer
 */
struct Timer
{
	struct timeval previous, current;
	int millis;
};

/*
 * Initialize timer
 */
void initializeTimer(struct Timer* tv)
{
	tv->millis = 0;
	ggCurTime(&tv->previous);
}

/*
 * Determine time lapse
 */
void updateTimer(struct Timer* tv)
{
	ggCurTime(&tv->current);

	tv->millis = (tv->current.tv_sec  - tv->previous.tv_sec)  * 1000
	           + (tv->current.tv_usec - tv->previous.tv_usec) / 1000;

	tv->previous = tv->current;
}

/*
 * Board geometry
 */
struct BoardGeom
{
	ggi_coord min, max; /* Lower and upper screen coordinates of the board. */
	int tileSize;       /* Tile size. Tiles are squares. */
	int spaceBetween;   /* Space between tiles. Here it's tileSize / 4. */
	int delta;          /* tile size + space between tiles. */
};

/*
 * Compute board geometry 
 */ 
void computeBoardGeometry(int boardSize, int screenWidth, int screenHeight, struct BoardGeom* geom)
{
	int sx, sy, boardLength;
	
	sx = (4 * screenWidth)  / ((5 * boardSize) + 1);
	sy = (4 * screenHeight) / ((5 * boardSize) + 1);

	geom->tileSize = (sy < sx) ? sy : sx;

	geom->spaceBetween = geom->tileSize / 4;
	
	geom->delta = geom->tileSize + geom->spaceBetween;
	
	boardLength = (boardSize * geom->delta) - geom->spaceBetween;
	geom->min.x = (screenWidth  - boardLength) / 2;
	geom->min.y = (screenHeight - boardLength) / 2;;
	
	geom->max.x = geom->min.x + boardLength;
	geom->max.y = geom->min.y + boardLength;
}

/*
 * State ids...
 */ 
enum GAME_STATE
{
	IDLE = 0,
	DRAW_BOARD,
	RESET_BOARD,
	WON,
	QUIT
};

/*
 * Swiss knife
 */
struct
{
	ggi_visual_t vis;  /* Our visual */
	ggi_mode mode;     /* Used mode */
	ggi_coord pointer; /* Pointer position */

	ggi_pixel tileOn, tileOff; /* Tile colors */
	ggi_pixel background; /* Background color */
	ggi_pixel hintCol; /* Hint color */
	
	int currentColor; /* Color index used to cycle through palette */
	
	uint8_t board[SQR_BOARD_SIZE];
	
	struct BoardGeom geom;
	
	int state;   /* Game state */
	int hintsOn; /* Are hints on? */
	
	struct Timer time;
	int animDuration;
} g_app;

/*
 * Colors
 */
#define NUM_COLORS 7
static ggi_color g_colors[NUM_COLORS]  = 
{
	{ 0x0000, 0x0000, 0x0000, 0x0000 }, /* black */
	{ 0xffff, 0xffff, 0xffff, 0x0000 }, /* white */
	{ 0xffff, 0x0000, 0x0000, 0x0000 }, /* red */
	{ 0x0000, 0x0000, 0xffff, 0x0000 }, /* blue */
	{ 0x0000, 0xffff, 0x0000, 0x0000 }, /* green */
	{ 0xffff, 0xffff, 0x0000, 0x0000 }, /* cyan */
	{ 0x0000, 0xffff, 0xffff, 0x0000 }  /* yellow */
};
static ggi_pixel g_lookup[7];

/*
 * Hint matrix
 */
uint8_t g_hintMatrix[MATRIX_DIM][MATRIX_DIM] =
{
	{ 0,1,1,1,0,0,0,1,0,1,0,0,0,1,1,0,0,0,0,1,0,0,0 },
	{ 1,1,0,1,1,0,1,0,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0 },
	{ 1,0,1,1,1,1,0,1,1,0,0,0,1,1,0,1,1,1,1,1,0,1,0 },
	{ 1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1 },
	{ 0,1,1,0,1,1,0,0,0,0,1,0,1,0,1,0,0,1,0,1,1,1,0 },
	{ 0,0,1,0,1,0,1,1,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0 },
	{ 0,1,0,1,0,1,1,0,1,1,0,0,0,1,0,1,1,1,0,0,0,1,0 },
	{ 1,0,1,0,0,1,0,1,1,0,0,0,0,0,1,1,0,1,0,1,1,0,1 },
	{ 0,0,1,0,0,0,1,1,1,0,1,0,0,1,1,1,0,0,1,0,0,1,1 },
	{ 1,0,0,0,0,1,1,0,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1 },
	{ 0,0,0,0,1,0,0,0,1,1,0,0,1,0,1,1,1,1,1,0,0,1,0 },
	{ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1 },
	{ 0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,0,1,0,0,1,1,0 },
	{ 1,1,1,0,0,0,1,0,1,0,0,0,1,1,1,0,0,0,1,0,0,0,0 },
	{ 1,1,0,0,1,0,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,0,0 },
	{ 0,0,1,0,0,0,1,1,1,0,1,0,0,0,1,1,0,1,0,1,1,0,1 },
	{ 0,0,1,1,0,0,1,0,0,1,1,1,0,0,1,0,1,1,1,0,0,0,1 },
	{ 0,0,1,0,1,0,1,1,0,1,1,0,1,0,0,1,1,0,1,1,1,0,0 },
	{ 0,1,1,0,0,1,0,0,1,0,1,0,0,1,1,0,1,1,1,0,0,0,1 },
	{ 1,0,1,0,1,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,0,1 },
	{ 0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,1,0,1,1,1,0 },
	{ 0,0,1,1,1,0,1,0,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1 },
	{ 0,0,0,1,0,0,0,1,1,1,0,1,0,0,0,1,1,0,1,1,0,1,0 }
};

/*
 * Basis vectors
 */ 
uint8_t g_basis[2][SQR_BOARD_SIZE] = 
{
 	{1,0,1,0,1,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,0,1,0,1},
  	{1,1,0,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,1,0,1,1}
};

/*
 * Fill board with random pattern and clear hint.
 */
void randomizeBoard()
{
	int i;
	for(i=0; i<SQR_BOARD_SIZE; ++i)
	{
		if(rand() > (RAND_MAX / 2))
		{
			g_app.board[i] = 0x01;
		}
		else
		{
			g_app.board[i] = 0x00;
		}
	}
}

/*
 * a = (a ^ b) & 1;
 */
inline void sum(uint8_t* a, uint8_t* b, int size)
{
	int i;
	for(i=0; i<size; ++i)
	{
		a[i] ^= b[i];
	}
}

/*
 * Compute weight
 */
inline int weight(uint8_t *a, int size)
{
	int i, w;
	for(i=0, w=0; i<size; ++i)
	{
		w += a[i];
	}
	
	return w;
}

/*
 * Check if the board is sovable
 */
int isSolvable()
{
	int i;
	uint8_t dot;

	dot = 0;
	for(i=0; i<SQR_BOARD_SIZE; ++i)
	{
		dot ^= (g_basis[0][i] & g_app.board[i]);
	}
	
	if(dot) return 0;
	
	dot = 0;
	for(i=0; i<SQR_BOARD_SIZE; ++i)
	{
		dot ^= (g_basis[1][i] & g_app.board[i]);
	}
	
	if(dot) return 0;
	return 1;
}

/*
 * Compute hint vector
 */
void hint()
{
	int i, j;
	uint8_t hint[SQR_BOARD_SIZE];
	uint8_t next[SQR_BOARD_SIZE];
	uint8_t best[SQR_BOARD_SIZE];
	
	memset(hint, 0, SQR_BOARD_SIZE);
	
	for(i=0; i<MATRIX_DIM; ++i)
	{
		for(j=0; j<MATRIX_DIM; ++j)
		{
			hint[i] ^= g_app.board[j] & g_hintMatrix[i][j];
		}
	}

	memcpy(best, hint, SQR_BOARD_SIZE);
	memcpy(next, hint, SQR_BOARD_SIZE);
	sum(next, g_basis[0], SQR_BOARD_SIZE);
	if(weight(next, SQR_BOARD_SIZE) < weight(best, SQR_BOARD_SIZE))
	{
		memcpy(best, next, SQR_BOARD_SIZE);
	}
	
	memcpy(next, hint, SQR_BOARD_SIZE);
	sum(next, g_basis[1], SQR_BOARD_SIZE);
	if(weight(next, SQR_BOARD_SIZE) < weight(best, SQR_BOARD_SIZE))
	{
		memcpy(best, next, SQR_BOARD_SIZE);
	}
	
	memcpy(next, hint, SQR_BOARD_SIZE);
	sum(next, g_basis[0], SQR_BOARD_SIZE);
	sum(next, g_basis[1], SQR_BOARD_SIZE);
	if(weight(next, SQR_BOARD_SIZE) < weight(best, SQR_BOARD_SIZE))
	{
		memcpy(best, next, SQR_BOARD_SIZE);
	}

	for(i=0; i<SQR_BOARD_SIZE; ++i)
	{
		g_app.board[i] = (g_app.board[i] & 0x7f) | (best[i] << 7);
	}
}

/*
 * Remove hint flag
 */
void removeHint()
{
	int i;
	for(i=0; i<SQR_BOARD_SIZE; ++i)
	{
		g_app.board[i] &= 0x7f;
	}
}

/* Fill screen with background color */
void clearScreen()
{
	ggiSetGCForeground(g_app.vis, g_app.background);
	ggiFillscreen(g_app.vis);
}

/* Draw a tile */
void drawTile(int i, int j)
{
	int x, y;
	uint8_t tile;
	
	x = g_app.geom.min.x + (i * g_app.geom.delta);
	y = g_app.geom.min.y + (j * g_app.geom.delta);
	
	tile = g_app.board[i + (j * BOARD_SIZE)];
	
	ggiSetGCForeground(g_app.vis, IS_ON(tile) ? g_app.tileOn : g_app.tileOff);
	ggiDrawBox(g_app.vis, x, y, g_app.geom.tileSize, g_app.geom.tileSize);
	
	if(HAS_HINT(tile))
	{
		ggiSetGCForeground(g_app.vis, g_app.hintCol);
		ggiDrawBox(g_app.vis, x, y, g_app.geom.tileSize/4, g_app.geom.tileSize/4);
	}
}

/* Draw the whole board */
void drawBoard()
{
	int i, j, x, y;
	uint8_t *tile;
	
	y = g_app.geom.min.y;
	for(j=0, tile=g_app.board; j<BOARD_SIZE; ++j, y+=g_app.geom.delta)
	{
		x = g_app.geom.min.x;
		for(i=0; i<BOARD_SIZE; ++i, ++tile, x+=g_app.geom.delta)
		{
			// draw square
			ggiSetGCForeground(g_app.vis, IS_ON(*tile) ? g_app.tileOn : g_app.tileOff);
			ggiDrawBox(g_app.vis, x, y, g_app.geom.tileSize, g_app.geom.tileSize);

			if(HAS_HINT(*tile))
			{
				ggiSetGCForeground(g_app.vis, g_app.hintCol);
				ggiDrawBox(g_app.vis, x, y, g_app.geom.tileSize/4, g_app.geom.tileSize/4);
			}
			
		}
	}
}

/* Check if a tile was pressed and get pressed tile coordinates*/
int getBoardCoord(int* bx, int* by)
{
	int x, y, tx, ty;

	if(((g_app.pointer.y < g_app.geom.min.y) ||
	    (g_app.pointer.y > g_app.geom.max.y)) ||
	   ((g_app.pointer.x < g_app.geom.min.x) ||
	    (g_app.pointer.x > g_app.geom.max.x)))
	{
		return 0;
	}
		
	// compute board coordinate
	x = g_app.pointer.x - g_app.geom.min.x;
	y = g_app.pointer.y - g_app.geom.min.y;
		
	*bx = x / g_app.geom.delta;
	*by = y / g_app.geom.delta;
		
	tx = (*bx) * g_app.geom.delta;
	ty = (*by) * g_app.geom.delta;

	// check if it lies on tile							
	if((x > (tx + g_app.geom.tileSize)) ||
	   (y > (ty + g_app.geom.tileSize)))
	{
		return 0;
	}
	
	return 1;
}

// Update board
int updateBoard(int bx, int by)
{
	int pos = bx + (by * BOARD_SIZE);

	// Update tiles
	g_app.board[pos] ^= 1;
	
	if(bx > 0)
		g_app.board[pos-1] ^= 1;
		
	if(bx < (BOARD_SIZE-1))
		g_app.board[pos+1] ^= 1;
	
	if(by > 0)
		g_app.board[pos-BOARD_SIZE] ^= 1;
	
	if(by < (BOARD_SIZE-1))
		g_app.board[pos+BOARD_SIZE] ^= 1;
		
	// Check if all tiles are off
	pos = SQR_BOARD_SIZE;
	while(pos > 0)
	{
		--pos;
		if(IS_ON(g_app.board[pos]))
			return 0;
	}
	
	return 1;
}

/*
 * Key press handler
 */
void onKeyPress(int keySym)
{
	switch (keySym)
	{
		case GIIUC_Escape:
			g_app.state = QUIT;
		break;
		
		case ' ':
			if(g_app.state == IDLE)
			{
				/* toggle hints */
				if(g_app.hintsOn)
				{
					removeHint();
				}
				else
				{
					hint();
				}
				g_app.hintsOn ^= 1;
				g_app.state = DRAW_BOARD;
			}
		break;
	}
}

/*
 * Mouse button handler
 */
void onPtrButtonPress(int button)
{
	int bx, by;
	
	if(button != GII_PBUTTON_FIRST)
	{
		return;
	}
	
	/* This is skipped if we are displaying the "wining animation" */
	if(g_app.state == IDLE)
	{
		/* If the mouse pointer is on a tile, update board and
		 * check if we have won. */
		if(getBoardCoord(&bx, &by))
		{
			if(updateBoard(bx, by))
			{
				g_app.state = WON;
			}
			else
			{
				g_app.state = DRAW_BOARD;
			}
		}
	}
}

/* 
 * Ninja state machine :| 
 */
void processState()
{
	/* a. We won. Display the board for 500 milliseconds 
	 *    before going to next board. */
	if(g_app.state == WON)
	{
		if(g_app.animDuration == 0)
		{
			removeHint();
			drawBoard();
		}
		
		/* Display the wonderful wining animation */
		if(g_app.animDuration < WINING_ANIM_DURATION)
		{		
			g_app.animDuration += g_app.time.millis;
		}
		else
		{
			/* Enought partying. Move to next board! */
			g_app.state = RESET_BOARD;
		}
	}
	/* b. Reset board = Start a new board. */
	if(g_app.state == RESET_BOARD)
	{
		clearScreen();
		/*
		 * The board are randomly generated. But we have
		 * to make sure that they are solvable.
		 */
		do
		{
			randomizeBoard();
		}while(!isSolvable());

		/* Cycle color for tiles */
		++g_app.currentColor;
		if(g_app.currentColor >= NUM_COLORS)
		{
			g_app.currentColor = 2;
		}
		g_app.tileOff = g_lookup[g_app.currentColor];
			
		/* No hints */
		g_app.hintsOn = 0;
		/* Reset wining "animation" timer */
		g_app.animDuration = 0;

		clearScreen();
		
		/* We are now ready. */
		g_app.state = DRAW_BOARD;
	}
		
	/* The board needs to be drawn. */
	if(g_app.state == DRAW_BOARD)
	{
		drawBoard();
		g_app.state = IDLE;
	}
}

/*
 * Display game controls (on stdout for the moment)
 */
void displayInstructions()
{
	printf("GGI Lights Out!\n"
	       "[space] Toggle hints to solve board.\n"
	       "[ESC]   Quit.\n");
}

/*
 * Main entry
 */
int main(int argc, char** argv)
{
   	int i;
	
	/* Clear board */
	memset(g_app.board, 1, SQR_BOARD_SIZE * sizeof(uint8_t));

	/* Initialize visual */
	ggiParseMode("", &g_app.mode);

	g_app.vis = ggNewStem(libgii, libggi, NULL);
	if (g_app.vis == NULL) {
	      ggPanic("Couldn't create stem!\n");
	}
	
	if (ggiOpen(g_app.vis, NULL) != GGI_OK)
	{
      		ggPanic("Couldn't open default visual!\n");
	}

	ggiSetFlags(g_app.vis, GGIFLAG_ASYNC);

	/* Set video mode */
	ggiCheckGraphMode(g_app.vis, 320, 240, GGI_AUTO, GGI_AUTO, GGI_AUTO, &g_app.mode);
	ggiSetMode(g_app.vis, &g_app.mode);

	/* Display controls */
	displayInstructions();
	
	/* Clean up screen */
	clearScreen();

	/* Reset mouse pointer */
	g_app.pointer.x = g_app.pointer.y = 0;

	/* Map colors */
	g_app.currentColor = 1;
	for(i=0; i<NUM_COLORS; ++i)
	{
		g_lookup[i] = ggiMapColor(g_app.vis, g_colors+i);
	}
	g_app.tileOn     = g_lookup[1];
	g_app.background = g_lookup[0];
	g_app.tileOff    = g_lookup[NUM_COLORS-1];
	g_app.hintCol    = g_lookup[0];
	
	/* Adjust tile size and placement according to current screen resolution */
	computeBoardGeometry(BOARD_SIZE, g_app.mode.visible.x, g_app.mode.visible.y, &g_app.geom);

	/* Reset board at startup */
	g_app.state = RESET_BOARD;
	
	/* Initiaze timer */
	initializeTimer(&g_app.time);
	
 	/* Main even loop */  	
  	do
  	{
          	/* Input timeout */
                struct timeval tv = { 0, 100 };

		/* Update timer */
		updateTimer(&g_app.time);

		/* Process current state */
		processState();
		
		/* Wait for keys or mouse event. */
                if (giiEventPoll(g_app.vis, emKey|emPointer, &tv))
                {
			gii_event ev;
			int nEvents;
			
			nEvents = giiEventsQueued(g_app.vis, emKey|emPointer);
			for(;nEvents;--nEvents)
			{
				giiEventRead(g_app.vis, &ev, emKey|emPointer);
				switch(ev.any.type)
				{
					case evKeyPress:
						onKeyPress (ev.key.sym);
					break;
					
					case evPtrButtonPress:
						onPtrButtonPress(ev.pbutton.button);
					break;
					
					/* Update mouse position */
					case evPtrAbsolute:
						g_app.pointer.x = ev.pmove.x;
						g_app.pointer.y = ev.pmove.y;
					break;

					case evPtrRelative:
						g_app.pointer.x += ev.pmove.x;
						g_app.pointer.y += ev.pmove.y;
					break;
				}
			}
		}                
                ggiFlush(g_app.vis);
        } while(g_app.state != QUIT);

	/* Close visual */
	if (ggiClose(g_app.vis) != GGI_OK)
	{
      		ggPanic("Couldn't close default visual!\n");
	}

	ggDelStem(g_app.vis);

	return 0;
}