pattern3.c

   1 #include <assert.h>
   2 #include <math.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5
   6 #include "board.h"
   7 #include "debug.h"
   8 #include "pattern3.h"
   9
  10
  11 static void
  12 pattern_record(struct pattern3s *p, int pi, char *str, hash3_t pat, int fixed_color)
  13 {
  14         hash_t h = hash3_to_hash(pat);
  15         while (p->hash[h & pattern3_hash_mask].pattern != pat
  16                && p->hash[h & pattern3_hash_mask].value != 0)
  17                 h++;
  18 #if 0
  19         if (h != hash3_to_hash(pat) && p->hash[h & pattern3_hash_mask].pattern != pat)
  20                 fprintf(stderr, "collision of %06x: %llx(%x)\n", pat, hash3_to_hash(pat)&pattern3_hash_mask, p->hash[hash3_to_hash(pat)&pattern3_hash_mask].pattern);
  21 #endif
  22         p->hash[h & pattern3_hash_mask].pattern = pat;
  23         p->hash[h & pattern3_hash_mask].value = (fixed_color ? fixed_color : 3) | (pi << 2);
  24         //fprintf(stderr, "[%s] %04x %d\n", str, pat, fixed_color);
  25 }
  26
  27 static int
  28 pat_vmirror(hash3_t pat)
  29 {
  30         /* V mirror pattern; reverse order of 3-2-3 color chunks and
  31          * 1-2-1 atari chunks */
  32         return ((pat & 0xfc00) >> 10) | (pat & 0x03c0) | ((pat & 0x003f) << 10)
  33                 | ((pat & 0x80000) >> 3) | (pat & 0x60000) | ((pat & 0x10000) << 3);
  34 }
  35
  36 static int
  37 pat_hmirror(hash3_t pat)
  38 {
  39         /* H mirror pattern; reverse order of 2-bit values within the chunks,
  40          * and the 2-bit middle atari chunk. */
  41 #define rev3(p) ((p >> 4) | (p & 0xc) | ((p & 0x3) << 4))
  42 #define rev2(p) ((p >> 2) | ((p & 0x3) << 2))
  43         return (rev3((pat & 0xfc00) >> 10) << 10)
  44                 | (rev2((pat & 0x03c0) >> 6) << 6)
  45                 | rev3((pat & 0x003f))
  46                 | ((pat & 0x20000) << 1)
  47                 | ((pat & 0x40000) >> 1)
  48                 | (pat & 0x90000);
  49 #undef rev3
  50 #undef rev2
  51 }
  52
  53 static int
  54 pat_90rot(hash3_t pat)
  55 {
  56         /* Rotate by 90 degrees:
  57          * 5 6 7  3     7 4 2     2
  58          * 3   4 1 2 -> 6   1 -> 3 0
  59          * 0 1 2  0     5 3 0     1  */
  60         /* I'm too lazy to optimize this :) */
  61
  62         int p2 = 0;
  63
  64         /* Stone info */
  65         int vals[8];
  66         for (int i = 0; i < 8; i++)
  67                 vals[i] = (pat >> (i * 2)) & 0x3;
  68         int vals2[8];
  69         vals2[0] = vals[5]; vals2[1] = vals[3]; vals2[2] = vals[0];
  70         vals2[3] = vals[6];                     vals2[4] = vals[1];
  71         vals2[5] = vals[7]; vals2[6] = vals[4]; vals2[7] = vals[2];
  72         for (int i = 0; i < 8; i++)
  73                 p2 |= vals2[i] << (i * 2);
  74
  75         /* Atari info */
  76         int avals[4];
  77         for (int i = 0; i < 4; i++)
  78                 avals[i] = (pat >> (16 + i)) & 0x1;
  79         int avals2[4];
  80         avals2[3] = avals[2];
  81         avals2[1] = avals[3]; avals2[2] = avals[0];
  82         avals2[0] = avals[1];
  83         for (int i = 0; i < 4; i++)
  84                 p2 |= avals2[i] << (16 + i);
  85
  86         return p2;
  87 }
  88
  89 void
  90 pattern3_transpose(hash3_t pat, hash3_t (*transp)[8])
  91 {
  92         int i = 0;
  93         (*transp)[i++] = pat;
  94         (*transp)[i++] = pat_vmirror(pat);
  95         (*transp)[i++] = pat_hmirror(pat);
  96         (*transp)[i++] = pat_vmirror(pat_hmirror(pat));
  97         (*transp)[i++] = pat_90rot(pat);
  98         (*transp)[i++] = pat_90rot(pat_vmirror(pat));
  99         (*transp)[i++] = pat_90rot(pat_hmirror(pat));
 100         (*transp)[i++] = pat_90rot(pat_vmirror(pat_hmirror(pat)));
 101 }
 102
 103 static void
 104 pattern_gen(struct pattern3s *p, int pi, hash3_t pat, char *src, int srclen, int fixed_color)
 105 {
 106         for (; srclen > 0; src++, srclen--) {
 107                 if (srclen == 5)
 108                         continue;
 109                 static const int ataribits[] = { -1, 0, -1, 1, 2, -1, 3, -1 };
 110                 int patofs = (srclen > 5 ? srclen - 1 : srclen) - 1;
 111                 switch (*src) {
 112                         /* Wildcards. */
 113                         case '?':
 114                                 *src = '.'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 115                                 *src = 'X'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 116                                 *src = 'O'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 117                                 *src = '#'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 118                                 *src = '?'; // for future recursions
 119                                 return;
 120                         case 'x':
 121                                 *src = '.'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 122                                 *src = 'O'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 123                                 *src = '#'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 124                                 *src = 'x'; // for future recursions
 125                                 return;
 126                         case 'o':
 127                                 *src = '.'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 128                                 *src = 'X'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 129                                 *src = '#'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 130                                 *src = 'o'; // for future recursions
 131                                 return;
 132
 133                         case 'X':
 134                                 *src = 'Y'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 135                                 if (ataribits[patofs] >= 0) {
 136                                         *src = '|'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 137                                 }
 138                                 *src = 'X'; // for future recursions
 139                                 return;
 140                         case 'O':
 141                                 *src = 'Q'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 142                                 if (ataribits[patofs] >= 0) {
 143                                         *src = '@'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 144                                 }
 145                                 *src = 'O'; // for future recursions
 146                                 return;
 147
 148                         case 'y':
 149                                 *src = '.'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 150                                 *src = '|'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 151                                 *src = 'O'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 152                                 *src = '#'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 153                                 *src = 'y'; // for future recursions
 154                                 return;
 155                         case 'q':
 156                                 *src = '.'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 157                                 *src = '@'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 158                                 *src = 'X'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 159                                 *src = '#'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 160                                 *src = 'q'; // for future recursions
 161                                 return;
 162
 163                         case '=':
 164                                 *src = '.'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 165                                 *src = 'Y'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 166                                 *src = 'O'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 167                                 *src = '#'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 168                                 *src = '='; // for future recursions
 169                                 return;
 170                         case '0':
 171                                 *src = '.'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 172                                 *src = 'Q'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 173                                 *src = 'X'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 174                                 *src = '#'; pattern_gen(p, pi, pat, src, srclen, fixed_color);
 175                                 *src = '0'; // for future recursions
 176                                 return;
 177
 178                         /* Atoms. */
 179                         case '.': /* 0 */ break;
 180                         case 'Y': pat |= S_BLACK << (patofs * 2); break;
 181                         case 'Q': pat |= S_WHITE << (patofs * 2); break;
 182                         case '|': assert(ataribits[patofs] >= 0);
 183                                   pat |= (S_BLACK << (patofs * 2)) | (1 << (16 + ataribits[patofs]));
 184                                   break;
 185                         case '@': assert(ataribits[patofs] >= 0);
 186                                   pat |= (S_WHITE << (patofs * 2)) | (1 << (16 + ataribits[patofs]));
 187                                   break;
 188                         case '#': pat |= S_OFFBOARD << (patofs * 2); break;
 189                 }
 190         }
 191
 192         /* Original pattern, all transpositions and rotations */
 193         hash3_t transp[8];
 194         pattern3_transpose(pat, &transp);
 195         for (int i = 0; i < 8; i++) {
 196                 /* Original color assignment */
 197                 pattern_record(p, pi, src - 9, transp[i], fixed_color);
 198                 /* Reverse color assignment */
 199                 if (fixed_color)
 200                         fixed_color = 2 - (fixed_color == 2);
 201                 pattern_record(p, pi, src - 9, pattern3_reverse(transp[i]), fixed_color);
 202         }
 203 }
 204
 205 static void
 206 patterns_gen(struct pattern3s *p, char src[][11], int src_n)
 207 {
 208         for (int i = 0; i < src_n; i++) {
 209                 //printf("<%s>\n", src[i]);
 210                 int fixed_color = 0;
 211                 switch (src[i][9]) {
 212                         case 'X': fixed_color = S_BLACK; break;
 213                         case 'O': fixed_color = S_WHITE; break;
 214                 }
 215                 //fprintf(stderr, "** %s **\n", src[i]);
 216                 pattern_gen(p, i, 0, src[i], 9, fixed_color);
 217         }
 218 }
 219
 220 static bool
 221 patterns_load(char src[][11], int src_n, char *filename)
 222 {
 223         FILE *f = fopen("moggy.patterns", "r");
 224         if (!f) return false;
 225
 226         int i;
 227         for (i = 0; i < src_n; i++) {
 228                 char line[32];
 229                 if (!fgets(line, sizeof(line), f))
 230                         goto error;
 231                 int l = strlen(line);
 232                 if (l != 10 + (line[l - 1] == '\n'))
 233                         goto error;
 234                 memcpy(src[i], line, 10);
 235         }
 236         fprintf(stderr, "moggy.patterns: %d patterns loaded\n", i);
 237         fclose(f);
 238         return true;
 239 error:
 240         fprintf(stderr, "Error loading moggy.patterns.\n");
 241         fclose(f);
 242         return false;
 243 }
 244
 245 void
 246 pattern3s_init(struct pattern3s *p, char src[][11], int src_n)
 247 {
 248         char nsrc[src_n][11];
 249
 250         if (!patterns_load(nsrc, src_n, "moggy.patterns")) {
 251                 /* Use default pattern set. */
 252                 for (int i = 0; i < src_n; i++)
 253                         strcpy(nsrc[i], src[i]);
 254         }
 255
 256         patterns_gen(p, nsrc, src_n);
 257 }
 258
 259
 260 static __attribute__((constructor)) void
 261 p3hashes_init(void)
 262 {
 263         /* tuned for 11482 collisions */
 264         /* XXX: tune better */
 265         hash_t h = 0x35373c;
 266         for (int i = 0; i < 8; i++) {
 267                 for (int a = 0; a < 2; a++) {
 268                         p3hashes[i][a][S_NONE] = (h = h * 16803-7);
 269                         p3hashes[i][a][S_BLACK] = (h = h * 16805-2);
 270                         p3hashes[i][a][S_WHITE] = (h = h * 16807-11);
 271                         p3hashes[i][a][S_OFFBOARD] = (h = h * 16809+7);
 272                 }
 273         }
 274 }