src/game.c

   1 /*
   2  * The RNG implementation is adapted from xoshiro256** and splitmix64
   3  * by David Blackman and Sebastiano Vigna, originally distributed under
   4  * the Creative Commons Zero public domain dedication.
   5  */
   6 #include <config.h>
   7 #include <limits.h>
   8 #include <string.h>
   9 #include <time.h>
  10 #include "game.h"
  11
  12 #define B64(x) ((x) & 0xffffffffffffffff)
  13
  14 /* Rotate val left by n bits.  The behaviour is undefined if n is zero. */
  15 static unsigned long long rot_left64(unsigned long long val, int n)
  16 {
  17         return B64( (val << n) | (val >> (64 - n)) );
  18 }
  19
  20 static unsigned long long xoshiro256ss(unsigned long long *s)
  21 {
  22         unsigned long long tmp, ret;
  23
  24         ret = B64(rot_left64(B64(s[1]*5), 7) * 9);
  25         tmp = B64(s[1] << 17);
  26
  27         s[2] ^= s[0];
  28         s[3] ^= s[1];
  29         s[1] ^= s[2];
  30         s[0] ^= s[3];
  31         s[2] ^= tmp;
  32         s[3] = rot_left64(s[3], 45);
  33
  34         return ret;
  35 }
  36
  37 static unsigned long long splitmix64(unsigned long long *state)
  38 {
  39         unsigned long long z;
  40
  41         z = B64(*state += 0x9e3779b97f4a7c15);
  42         z = B64((z ^ (z >> 30)) * 0xbf58476d1ce4e5b9);
  43         z = B64((z ^ (z >> 27)) * 0x94d049bb133111eb);
  44
  45         return z ^ (z >> 31);
  46 }
  47
  48 static unsigned long long rng_state[4];
  49
  50 static int rng_is_seeded(void)
  51 {
  52         return rng_state[0] || rng_state[1] || rng_state[2] || rng_state[3];
  53 }
  54
  55 /* Calculate the least power of two greater than val, minus 1. */
  56 static unsigned rng_mask(unsigned val)
  57 {
  58         val |= val >> 1;
  59         val |= val >> 2;
  60         val |= val >> 4;
  61         val |= val >> 8;
  62
  63         if (UINT_MAX >= 65536)
  64                 val |= val >> 16;
  65
  66         return val;
  67 }
  68
  69 /* Return a random integer uniformly on the closed interval [0, limit-1] */
  70 static unsigned rng_uniform_int(unsigned max)
  71 {
  72         unsigned mask = rng_mask(max-1);
  73         unsigned long long val;
  74
  75         do {
  76                 val = ( xoshiro256ss(rng_state) >> 32 ) & mask;
  77         } while (val >= max);
  78
  79         return val;
  80 }
  81
  82 static void shuffle(unsigned char *tiles, unsigned n)
  83 {
  84         unsigned i, j;
  85
  86         for (i = 1; i < n; i++) {
  87                 unsigned char tmp;
  88
  89                 j = rng_uniform_int(i+1);
  90                 tmp = tiles[i];
  91                 tiles[i] = tiles[j];
  92                 tiles[j] = tmp;
  93         }
  94 }
  95
  96 void game_reseed(unsigned long long seed)
  97 {
  98         rng_state[0] = splitmix64(&seed);
  99         rng_state[1] = splitmix64(&seed);
 100         rng_state[2] = splitmix64(&seed);
 101         rng_state[3] = splitmix64(&seed);
 102 }
 103
 104 void game_reset(struct board *board)
 105 {
 106         unsigned char tiles[25];
 107         unsigned i;
 108
 109         if (!rng_is_seeded())
 110                 game_reseed(time(NULL));
 111
 112         for (i = 0; i < 24; i++) {
 113                 tiles[i] = (i%6) + 1;
 114         }
 115
 116         shuffle(tiles, 24);
 117         memset(board->goal, 0, sizeof board->goal);
 118
 119         for (i = 0; i < 9; i++) {
 120                 uint_fast32_t position = board_position(i/3+1, i%3+1);
 121
 122                 if (tiles[i] & 1)
 123                         board->goal[0] |= position >> 6;
 124                 if (tiles[i] & 2)
 125                         board->goal[1] |= position >> 6;
 126                 if (tiles[i] & 4)
 127                         board->goal[2] |= position >> 6;
 128         }
 129
 130         tiles[24] = TILE_EMPTY;
 131         shuffle(tiles, 25);
 132         memset(board->game, 0, sizeof board->game);
 133
 134         for (i = 0; i < 25; i++) {
 135                 unsigned x = i/5, y = i%5;
 136                 uint_fast32_t position;
 137
 138                 position = board_position(x, y);
 139                 if (tiles[i] == TILE_EMPTY) {
 140                         board->game[0] = 0x1ffffff ^ position;
 141                         board->x = x;
 142                         board->y = y;
 143                 } else {
 144                         if (tiles[i] & 1)
 145                                 board->game[1] |= position;
 146                         if (tiles[i] & 2)
 147                                 board->game[2] |= position;
 148                         if (tiles[i] & 4)
 149                                 board->game[3] |= position;
 150                 }
 151         }
 152 }
 153
 154 int game_do_move(struct board *board, int x, int y)
 155 {
 156         int bx = board->x, by = board->y;
 157         uint_least32_t mask, val[4];
 158         int i, shl, shr;
 159
 160         if ((bx != x) == (by != y))
 161                 return -1;
 162
 163         if (bx == x) {
 164                 mask = board_mask_v(x, by, y);
 165                 shr = 5*(by < y);
 166                 shl = 5*(by > y);
 167         } else {
 168                 mask = board_mask_h(y, bx, x);
 169                 shr = bx < x;
 170                 shl = bx > x;
 171         }
 172
 173         for (i = 0; i < 4; i++) {
 174                 board->game[i] ^= (val[i] = board->game[i] & mask);
 175                 board->game[i] |= val[i] << shl >> shr;
 176         }
 177
 178         board->x = x;
 179         board->y = y;
 180         return 0;
 181 }