/*
 * Slide puzzle core game logic
 * Copyright © 2022 Nick Bowler
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 *
 * The RNG implementation is adapted from xoshiro256** and splitmix64
 * by David Blackman and Sebastiano Vigna, originally distributed under
 * the Creative Commons Zero public domain dedication.
 */

#include <config.h>
#include <limits.h>
#include <string.h>
#include <time.h>
#include "game.h"

#define B64(x) ((x) & 0xffffffffffffffff)

/* Rotate val left by n bits.  The behaviour is undefined if n is zero. */
static unsigned long long rot_left64(unsigned long long val, int n)
{
	return B64( (val << n) | (val >> (64 - n)) );
}

static unsigned long long xoshiro256ss(unsigned long long *s)
{
	unsigned long long tmp, ret;

	ret = B64(rot_left64(B64(s[1]*5), 7) * 9);
	tmp = B64(s[1] << 17);

	s[2] ^= s[0];
	s[3] ^= s[1];
	s[1] ^= s[2];
	s[0] ^= s[3];
	s[2] ^= tmp;
	s[3] = rot_left64(s[3], 45);

	return ret;
}

static unsigned long long splitmix64(unsigned long long *state)
{
	unsigned long long z;

	z = B64(*state += 0x9e3779b97f4a7c15);
	z = B64((z ^ (z >> 30)) * 0xbf58476d1ce4e5b9);
	z = B64((z ^ (z >> 27)) * 0x94d049bb133111eb);

	return z ^ (z >> 31);
}

static unsigned long long rng_state[4];

static int rng_is_seeded(void)
{
	return rng_state[0] || rng_state[1] || rng_state[2] || rng_state[3];
}

/* Calculate the least power of two greater than val, minus 1. */
static unsigned rng_mask(unsigned val)
{
	val |= val >> 1;
	val |= val >> 2;
	val |= val >> 4;
	val |= val >> 8;

	if (UINT_MAX >= 65536)
		val |= val >> 16;

	return val;
}

/* Return a random integer uniformly on the closed interval [0, limit-1] */
static unsigned rng_uniform_int(unsigned max)
{
	unsigned mask = rng_mask(max-1);
	unsigned long long val;

	do {
		val = ( xoshiro256ss(rng_state) >> 32 ) & mask;
	} while (val >= max);

	return val;
}

static void shuffle(unsigned char *tiles, unsigned n)
{
	unsigned i, j;

	for (i = 1; i < n; i++) {
		unsigned char tmp;

		j = rng_uniform_int(i+1);
		tmp = tiles[i];
		tiles[i] = tiles[j];
		tiles[j] = tmp;
	}
}

void game_reseed(unsigned long long seed)
{
	rng_state[0] = splitmix64(&seed);
	rng_state[1] = splitmix64(&seed);
	rng_state[2] = splitmix64(&seed);
	rng_state[3] = splitmix64(&seed);
}

void game_reset(struct board *board)
{
	unsigned char tiles[25];
	unsigned i;

	if (!rng_is_seeded())
		game_reseed(time(NULL));

	for (i = 0; i < 24; i++) {
		tiles[i] = (i%6) + 1;
	}

	shuffle(tiles, 24);
	memset(board->goal, 0, sizeof board->goal);

	for (i = 0; i < 9; i++) {
		uint_fast32_t position = board_position(i/3+1, i%3+1) >> 6;

		if (tiles[i] & 1) board->goal[0] |= position;
		if (tiles[i] & 2) board->goal[1] |= position;
		if (tiles[i] & 4) board->goal[2] |= position;
	}

	tiles[24] = TILE_EMPTY;
	shuffle(tiles, 25);

	memset(board->game, 0, sizeof board->game);
	for (i = 0; i < 25; i++) {
		unsigned x = i/5, y = i%5;
		uint_fast32_t position;

		position = board_position(x, y);
		if (tiles[i] != TILE_EMPTY) {
			if (tiles[i] & 1) board->game[0] |= position;
			if (tiles[i] & 2) board->game[1] |= position;
			if (tiles[i] & 4) board->game[2] |= position;
		} else {
			board->game[3] = ~position;
			board->x = x;
			board->y = y;
		}
	}
}

int game_do_move(struct board *board, int x, int y)
{
	int bx = board->x, by = board->y;
	uint_least32_t mask, val[4];
	int i, shl, shr;

	if ((bx != x) == (by != y))
		return -1;

	if (bx == x) {
		mask = board_mask_v(x, by, y);
		shr = 5*(by < y);
		shl = 5*(by > y);
	} else {
		mask = board_mask_h(y, bx, x);
		shr = bx < x;
		shl = bx > x;
	}

	for (i = 0; i < 4; i++) {
		board->game[i] ^= (val[i] = board->game[i] & mask);
		board->game[i] |= val[i] << shl >> shr;
	}

	board->x = x;
	board->y = y;
	return 0;
}

int game_check_goal(struct board *board)
{
	int i, ret = 1;

	for (i = 0; i < 3; i++)
		ret &= ((board->game[i] & GOAL_MASK) >> 6) == board->goal[i];
	return ret;
}

void game_finish(struct board *board)
{
	int i;

	for (i = 0; i < 4; i++) {
		board->game[i] &= GOAL_MASK;
	}

	/*
	 * Setting both x and y hole location to a bogus value will effectively
	 * disable the game since there will be no valid moves.
	 */
	board->x = board->y = -1;
}