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.
12 #define B64(x) ((x) & 0xffffffffffffffff)
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)
17 return B64( (val << n) | (val >> (64 - n)) );
20 static unsigned long long xoshiro256ss(unsigned long long *s)
22 unsigned long long tmp, ret;
24 ret = B64(rot_left64(B64(s[1]*5), 7) * 9);
25 tmp = B64(s[1] << 17);
32 s[3] = rot_left64(s[3], 45);
37 static unsigned long long splitmix64(unsigned long long *state)
41 z = B64(*state += 0x9e3779b97f4a7c15);
42 z = B64((z ^ (z >> 30)) * 0xbf58476d1ce4e5b9);
43 z = B64((z ^ (z >> 27)) * 0x94d049bb133111eb);
48 static unsigned long long rng_state[4];
50 static int rng_is_seeded(void)
52 return rng_state[0] || rng_state[1] || rng_state[2] || rng_state[3];
55 /* Calculate the least power of two greater than val, minus 1. */
56 static unsigned rng_mask(unsigned val)
63 if (UINT_MAX >= 65536)
69 /* Return a random integer uniformly on the closed interval [0, limit-1] */
70 static unsigned rng_uniform_int(unsigned max)
72 unsigned mask = rng_mask(max-1);
73 unsigned long long val;
76 val = ( xoshiro256ss(rng_state) >> 32 ) & mask;
82 static void shuffle(unsigned char *tiles, unsigned n)
86 for (i = 1; i < n; i++) {
89 j = rng_uniform_int(i+1);
96 void game_reseed(unsigned long long seed)
98 rng_state[0] = splitmix64(&seed);
99 rng_state[1] = splitmix64(&seed);
100 rng_state[2] = splitmix64(&seed);
101 rng_state[3] = splitmix64(&seed);
104 void game_reset(struct board *board)
106 unsigned char tiles[25];
109 if (!rng_is_seeded())
110 game_reseed(time(NULL));
112 for (i = 0; i < 24; i++) {
113 tiles[i] = (i%6) + 1;
117 memset(board->goal, 0, sizeof board->goal);
119 for (i = 0; i < 9; i++) {
120 uint_fast32_t position = board_position(i/3+1, i%3+1);
123 board->goal[0] |= position >> 6;
125 board->goal[1] |= position >> 6;
127 board->goal[2] |= position >> 6;
130 tiles[24] = TILE_EMPTY;
132 memset(board->game, 0, sizeof board->game);
134 for (i = 0; i < 25; i++) {
135 unsigned x = i/5, y = i%5;
136 uint_fast32_t position;
138 position = board_position(x, y);
139 if (tiles[i] == TILE_EMPTY) {
140 board->game[0] = 0x1ffffff ^ position;
145 board->game[1] |= position;
147 board->game[2] |= position;
149 board->game[3] |= position;
154 int game_do_move(struct board *board, int x, int y)
156 int bx = board->x, by = board->y;
157 uint_least32_t mask, val[4];
160 if ((bx != x) == (by != y))
164 mask = board_mask_v(x, by, y);
168 mask = board_mask_h(y, bx, x);
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;