2 * Slide puzzle core game logic
3 * Copyright © 2022 Nick Bowler
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <https://www.gnu.org/licenses/>.
18 * The RNG implementation is adapted from xoshiro256** and splitmix64
19 * by David Blackman and Sebastiano Vigna, originally distributed under
20 * the Creative Commons Zero public domain dedication.
29 #define B64(x) ((x) & 0xffffffffffffffff)
31 /* Rotate val left by n bits. The behaviour is undefined if n is zero. */
32 static unsigned long long rot_left64(unsigned long long val, int n)
34 return B64( (val << n) | (val >> (64 - n)) );
37 static unsigned long long xoshiro256ss(unsigned long long *s)
39 unsigned long long tmp, ret;
41 ret = B64(rot_left64(B64(s[1]*5), 7) * 9);
42 tmp = B64(s[1] << 17);
49 s[3] = rot_left64(s[3], 45);
54 static unsigned long long splitmix64(unsigned long long *state)
58 z = B64(*state += 0x9e3779b97f4a7c15);
59 z = B64((z ^ (z >> 30)) * 0xbf58476d1ce4e5b9);
60 z = B64((z ^ (z >> 27)) * 0x94d049bb133111eb);
65 static unsigned long long rng_state[4];
67 static int rng_is_seeded(void)
69 return rng_state[0] || rng_state[1] || rng_state[2] || rng_state[3];
72 /* Calculate the least power of two greater than val, minus 1. */
73 static unsigned rng_mask(unsigned val)
80 if (UINT_MAX >= 65536)
86 /* Return a random integer uniformly on the closed interval [0, limit-1] */
87 static unsigned rng_uniform_int(unsigned max)
89 unsigned mask = rng_mask(max-1);
90 unsigned long long val;
93 val = ( xoshiro256ss(rng_state) >> 32 ) & mask;
99 static void shuffle(unsigned char *tiles, unsigned n)
103 for (i = 1; i < n; i++) {
106 j = rng_uniform_int(i+1);
113 void game_reseed(unsigned long long seed)
115 rng_state[0] = splitmix64(&seed);
116 rng_state[1] = splitmix64(&seed);
117 rng_state[2] = splitmix64(&seed);
118 rng_state[3] = splitmix64(&seed);
121 void game_reset(struct board *board)
123 unsigned char tiles[25];
126 if (!rng_is_seeded())
127 game_reseed(time(NULL));
129 for (i = 0; i < 24; i++) {
130 tiles[i] = (i%6) + 1;
134 memset(board->goal, 0, sizeof board->goal);
136 for (i = 0; i < 9; i++) {
137 uint_fast32_t position = board_position(i/3+1, i%3+1) >> 6;
139 if (tiles[i] & 1) board->goal[0] |= position;
140 if (tiles[i] & 2) board->goal[1] |= position;
141 if (tiles[i] & 4) board->goal[2] |= position;
144 tiles[24] = TILE_EMPTY;
147 memset(board->game, 0, sizeof board->game);
148 for (i = 0; i < 25; i++) {
149 unsigned x = i/5, y = i%5;
150 uint_fast32_t position;
152 position = board_position(x, y);
153 if (tiles[i] != TILE_EMPTY) {
154 if (tiles[i] & 1) board->game[0] |= position;
155 if (tiles[i] & 2) board->game[1] |= position;
156 if (tiles[i] & 4) board->game[2] |= position;
158 board->game[3] = ~position;
165 int game_do_move(struct board *board, int x, int y)
167 int bx = board->x, by = board->y;
168 uint_least32_t mask, val[4];
171 if ((bx != x) == (by != y))
175 mask = board_mask_v(x, by, y);
179 mask = board_mask_h(y, bx, x);
184 for (i = 0; i < 4; i++) {
185 board->game[i] ^= (val[i] = board->game[i] & mask);
186 board->game[i] |= val[i] << shl >> shr;
194 int game_check_goal(struct board *board)
198 for (i = 0; i < 3; i++)
199 ret &= ((board->game[i] & GOAL_MASK) >> 6) == board->goal[i];
203 void game_finish(struct board *board)
207 for (i = 0; i < 4; i++) {
208 board->game[i] &= GOAL_MASK;
212 * Setting both x and y hole location to a bogus value will effectively
213 * disable the game since there will be no valid moves.
215 board->x = board->y = -1;