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, 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;
  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, 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, pat, src, srclen, fixed_color);
 115                                 *src = 'X'; pattern_gen(p, pat, src, srclen, fixed_color);
 116                                 *src = 'O'; pattern_gen(p, pat, src, srclen, fixed_color);
 117                                 *src = '#'; pattern_gen(p, pat, src, srclen, fixed_color);
 118                                 *src = '?'; // for future recursions
 119                                 return;
 120                         case 'x':
 121                                 *src = '.'; pattern_gen(p, pat, src, srclen, fixed_color);
 122                                 *src = 'O'; pattern_gen(p, pat, src, srclen, fixed_color);
 123                                 *src = '#'; pattern_gen(p, pat, src, srclen, fixed_color);
 124                                 *src = 'x'; // for future recursions
 125                                 return;
 126                         case 'o':
 127                                 *src = '.'; pattern_gen(p, pat, src, srclen, fixed_color);
 128                                 *src = 'X'; pattern_gen(p, pat, src, srclen, fixed_color);
 129                                 *src = '#'; pattern_gen(p, pat, src, srclen, fixed_color);
 130                                 *src = 'o'; // for future recursions
 131                                 return;
 132
 133                         case 'X':
 134                                 *src = 'Y'; pattern_gen(p, pat, src, srclen, fixed_color);
 135                                 if (ataribits[patofs] >= 0)
 136                                         *src = '|'; pattern_gen(p, pat, src, srclen, fixed_color);
 137                                 *src = 'X'; // for future recursions
 138                                 return;
 139                         case 'O':
 140                                 *src = 'Q'; pattern_gen(p, pat, src, srclen, fixed_color);
 141                                 if (ataribits[patofs] >= 0)
 142                                         *src = '@'; pattern_gen(p, pat, src, srclen, fixed_color);
 143                                 *src = 'O'; // for future recursions
 144                                 return;
 145
 146                         case 'y':
 147                                 *src = '.'; pattern_gen(p, pat, src, srclen, fixed_color);
 148                                 *src = '|'; pattern_gen(p, pat, src, srclen, fixed_color);
 149                                 *src = 'O'; pattern_gen(p, pat, src, srclen, fixed_color);
 150                                 *src = '#'; pattern_gen(p, pat, src, srclen, fixed_color);
 151                                 *src = 'y'; // for future recursions
 152                                 return;
 153                         case 'q':
 154                                 *src = '.'; pattern_gen(p, pat, src, srclen, fixed_color);
 155                                 *src = '@'; pattern_gen(p, pat, src, srclen, fixed_color);
 156                                 *src = 'X'; pattern_gen(p, pat, src, srclen, fixed_color);
 157                                 *src = '#'; pattern_gen(p, pat, src, srclen, fixed_color);
 158                                 *src = 'q'; // for future recursions
 159                                 return;
 160
 161                         case '=':
 162                                 *src = '.'; pattern_gen(p, pat, src, srclen, fixed_color);
 163                                 *src = 'Y'; pattern_gen(p, pat, src, srclen, fixed_color);
 164                                 *src = 'O'; pattern_gen(p, pat, src, srclen, fixed_color);
 165                                 *src = '#'; pattern_gen(p, pat, src, srclen, fixed_color);
 166                                 *src = '='; // for future recursions
 167                                 return;
 168                         case '0':
 169                                 *src = '.'; pattern_gen(p, pat, src, srclen, fixed_color);
 170                                 *src = 'Q'; pattern_gen(p, pat, src, srclen, fixed_color);
 171                                 *src = 'X'; pattern_gen(p, pat, src, srclen, fixed_color);
 172                                 *src = '#'; pattern_gen(p, pat, src, srclen, fixed_color);
 173                                 *src = '0'; // for future recursions
 174                                 return;
 175
 176                         /* Atoms. */
 177                         case '.': /* 0 */ break;
 178                         case 'Y': pat |= S_BLACK << (patofs * 2); break;
 179                         case 'Q': pat |= S_WHITE << (patofs * 2); break;
 180                         case '|': assert(ataribits[patofs] >= 0);
 181                                   pat |= (S_BLACK << (patofs * 2)) | (1 << (16 + ataribits[patofs]));
 182                                   break;
 183                         case '@': assert(ataribits[patofs] >= 0);
 184                                   pat |= (S_WHITE << (patofs * 2)) | (1 << (16 + ataribits[patofs]));
 185                                   break;
 186                         case '#': pat |= S_OFFBOARD << (patofs * 2); break;
 187                 }
 188         }
 189
 190         /* Original pattern, all transpositions and rotations */
 191         hash3_t transp[8];
 192         pattern3_transpose(pat, &transp);
 193         for (int i = 0; i < 8; i++) {
 194                 /* Original color assignment */
 195                 pattern_record(p, src - 9, transp[i], fixed_color);
 196                 /* Reverse color assignment */
 197                 if (fixed_color)
 198                         fixed_color = 2 - (fixed_color == 2);
 199                 pattern_record(p, src - 9, pattern3_reverse(transp[i]), fixed_color);
 200         }
 201 }
 202
 203 static void
 204 patterns_gen(struct pattern3s *p, char src[][11], int src_n)
 205 {
 206         for (int i = 0; i < src_n; i++) {
 207                 //printf("<%s>\n", src[i]);
 208                 int fixed_color = 0;
 209                 switch (src[i][9]) {
 210                         case 'X': fixed_color = S_BLACK; break;
 211                         case 'O': fixed_color = S_WHITE; break;
 212                 }
 213                 //fprintf(stderr, "** %s **\n", src[i]);
 214                 pattern_gen(p, 0, src[i], 9, fixed_color);
 215         }
 216 }
 217
 218 static bool
 219 patterns_load(char src[][11], int src_n, char *filename)
 220 {
 221         FILE *f = fopen("moggy.patterns", "r");
 222         if (!f) return false;
 223
 224         int i;
 225         for (i = 0; i < src_n; i++) {
 226                 char line[32];
 227                 if (!fgets(line, sizeof(line), f))
 228                         goto error;
 229                 int l = strlen(line);
 230                 if (l != 10 + (line[l - 1] == '\n'))
 231                         goto error;
 232                 memcpy(src[i], line, 10);
 233         }
 234         fprintf(stderr, "moggy.patterns: %d patterns loaded\n", i);
 235         fclose(f);
 236         return true;
 237 error:
 238         fprintf(stderr, "Error loading moggy.patterns.\n");
 239         fclose(f);
 240         return false;
 241 }
 242
 243 void
 244 pattern3s_init(struct pattern3s *p, char src[][11], int src_n)
 245 {
 246         char nsrc[src_n][11];
 247
 248         if (!patterns_load(nsrc, src_n, "moggy.patterns")) {
 249                 /* Use default pattern set. */
 250                 for (int i = 0; i < src_n; i++)
 251                         strcpy(nsrc[i], src[i]);
 252         }
 253
 254         patterns_gen(p, nsrc, src_n);
 255 }
 256
 257
 258 static __attribute__((constructor)) void
 259 p3hashes_init(void)
 260 {
 261         /* tuned for 11482 collisions */
 262         /* XXX: tune better */
 263         hash_t h = 0x35373c;
 264         for (int i = 0; i < 8; i++) {
 265                 for (int a = 0; a < 2; a++) {
 266                         p3hashes[i][a][S_NONE] = (h = h * 16803-7);
 267                         p3hashes[i][a][S_BLACK] = (h = h * 16805-2);
 268                         p3hashes[i][a][S_WHITE] = (h = h * 16807-11);
 269                         p3hashes[i][a][S_OFFBOARD] = (h = h * 16809+7);
 270                 }
 271         }
 272 }