src/game.c

   1 /*
   2  * Slide puzzle core game logic
   3  * Copyright © 2022 Nick Bowler
   4  *
   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.
   9  *
  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.
  14  *
  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/>.
  17  *
  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.
  21  */
  22
  23 #include <config.h>
  24 #include <limits.h>
  25 #include <string.h>
  26 #include <time.h>
  27 #include "game.h"
  28
  29 #define B64(x) ((x) & 0xffffffffffffffff)
  30
  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)
  33 {
  34         return B64( (val << n) | (val >> (64 - n)) );
  35 }
  36
  37 static unsigned long long xoshiro256ss(unsigned long long *s)
  38 {
  39         unsigned long long tmp, ret;
  40
  41         ret = B64(rot_left64(B64(s[1]*5), 7) * 9);
  42         tmp = B64(s[1] << 17);
  43
  44         s[2] ^= s[0];
  45         s[3] ^= s[1];
  46         s[1] ^= s[2];
  47         s[0] ^= s[3];
  48         s[2] ^= tmp;
  49         s[3] = rot_left64(s[3], 45);
  50
  51         return ret;
  52 }
  53
  54 static unsigned long long splitmix64(unsigned long long *state)
  55 {
  56         unsigned long long z;
  57
  58         z = B64(*state += 0x9e3779b97f4a7c15);
  59         z = B64((z ^ (z >> 30)) * 0xbf58476d1ce4e5b9);
  60         z = B64((z ^ (z >> 27)) * 0x94d049bb133111eb);
  61
  62         return z ^ (z >> 31);
  63 }
  64
  65 static unsigned long long rng_state[4];
  66
  67 static int rng_is_seeded(void)
  68 {
  69         return rng_state[0] || rng_state[1] || rng_state[2] || rng_state[3];
  70 }
  71
  72 /* Calculate the least power of two greater than val, minus 1. */
  73 static unsigned rng_mask(unsigned val)
  74 {
  75         val |= val >> 1;
  76         val |= val >> 2;
  77         val |= val >> 4;
  78         val |= val >> 8;
  79
  80         if (UINT_MAX >= 65536)
  81                 val |= val >> 16;
  82
  83         return val;
  84 }
  85
  86 /* Return a random integer uniformly on the closed interval [0, limit-1] */
  87 static unsigned rng_uniform_int(unsigned max)
  88 {
  89         unsigned mask = rng_mask(max-1);
  90         unsigned long long val;
  91
  92         do {
  93                 val = ( xoshiro256ss(rng_state) >> 32 ) & mask;
  94         } while (val >= max);
  95
  96         return val;
  97 }
  98
  99 static void shuffle(unsigned char *tiles, unsigned n)
 100 {
 101         unsigned i, j;
 102
 103         for (i = 1; i < n; i++) {
 104                 unsigned char tmp;
 105
 106                 j = rng_uniform_int(i+1);
 107                 tmp = tiles[i];
 108                 tiles[i] = tiles[j];
 109                 tiles[j] = tmp;
 110         }
 111 }
 112
 113 void game_reseed(unsigned long long seed)
 114 {
 115         rng_state[0] = splitmix64(&seed);
 116         rng_state[1] = splitmix64(&seed);
 117         rng_state[2] = splitmix64(&seed);
 118         rng_state[3] = splitmix64(&seed);
 119 }
 120
 121 void game_reset(struct board *board)
 122 {
 123         unsigned char tiles[25];
 124         unsigned i;
 125
 126         if (!rng_is_seeded())
 127                 game_reseed(time(NULL));
 128
 129         for (i = 0; i < 24; i++) {
 130                 tiles[i] = (i%6) + 1;
 131         }
 132
 133         shuffle(tiles, 24);
 134         memset(board->goal, 0, sizeof board->goal);
 135
 136         for (i = 0; i < 9; i++) {
 137                 uint_fast32_t position = board_position(i/3+1, i%3+1) >> 6;
 138
 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;
 142         }
 143
 144         tiles[24] = TILE_EMPTY;
 145         shuffle(tiles, 25);
 146
 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;
 151
 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;
 157                 } else {
 158                         board->game[3] = ~position;
 159                         board->x = x;
 160                         board->y = y;
 161                 }
 162         }
 163 }
 164
 165 int game_do_move(struct board *board, int x, int y)
 166 {
 167         int bx = board->x, by = board->y;
 168         uint_least32_t mask, val[4];
 169         int i, shl, shr;
 170
 171         if ((bx != x) == (by != y))
 172                 return -1;
 173
 174         if (bx == x) {
 175                 mask = board_mask_v(x, by, y);
 176                 shr = 5*(by < y);
 177                 shl = 5*(by > y);
 178         } else {
 179                 mask = board_mask_h(y, bx, x);
 180                 shr = bx < x;
 181                 shl = bx > x;
 182         }
 183
 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;
 187         }
 188
 189         board->x = x;
 190         board->y = y;
 191         return 0;
 192 }
 193
 194 int game_check_goal(struct board *board)
 195 {
 196         int i, ret = 1;
 197
 198         for (i = 0; i < 3; i++)
 199                 ret &= ((board->game[i] & GOAL_MASK) >> 6) == board->goal[i];
 200         return ret;
 201 }
 202
 203 void game_finish(struct board *board)
 204 {
 205         int i;
 206
 207         for (i = 0; i < 4; i++) {
 208                 board->game[i] &= GOAL_MASK;
 209         }
 210
 211         /*
 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.
 214          */
 215         board->x = board->y = -1;
 216 }