src/bedbugs.c

   1 /*
   2  * Output bits of a rule file for Golly for a Conway-like cellular
   3  * automaton displayed with smoothing reminiscent of the Mullard
   4  * SAA5050 Teletext character generation (aka BBC "MODE 7").
   5  *
   6  * The resulting automaton flips the world between two states:
   7  * one where everything is one of two states, and one where an
   8  * expanded set of 32 states is used (16 'off', 16 'on') according
   9  * to what diagonals are required for the smoothing. Each of the
  10  * expanded states has an associated icon.
  11  *
  12  * In the first step we go from two states to 32 implementing the
  13  * smoothing algorithm as a transition function on a 3x3 neighbourhood.
  14  * In the second step we go from 32 back to 2 with a Conway-derived
  15  * transition function, again on a 3x3 neighbourhood (this step is not
  16  * in this source file).
  17  * (FIXME: this would be more slick, although probably even less
  18  * efficient, implemented in one go with a 5x5 neighbourhood, which
  19  * Golly does support.)
  20  *
  21  * The smoothing algorithm and graphics are derived from 'Bedstead' by
  22  * Ben Harris: http://bjh21.me.uk/bedstead/
  23  * The idea of applying this smoothing to Conway's Life can be blamed
  24  * on Simon Tatham.
  25  */
  26
  27 /*
  28  * This file is part of Bedbugs.
  29  * Copyright (C) 2014 Jacob Nevins.
  30  * Portions copyright (C) 2009 Ben Harris (see below).
  31  *
  32  * This program is free software; you can redistribute it and/or modify
  33  * it under the terms of the GNU General Public License as published by
  34  * the Free Software Foundation; either version 2 of the License, or
  35  * (at your option) any later version.
  36  *
  37  * This program is distributed in the hope that it will be useful,
  38  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  39  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  40  * GNU General Public License for more details.
  41  *
  42  * You should have received a copy of the GNU General Public License along
  43  * with this program; if not, write to the Free Software Foundation, Inc.,
  44  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  45  *
  46  * Website: http://www.chiark.greenend.org.uk/ucgi/~jacobn/git/bedbugs-git/
  47  *
  48  *
  49  * This source file, bedbugs.c, is based on
  50  * http://bjh21.me.uk/bedstead/  bedstead.c  bzr r137
  51  * from which the following bits of the copyright notice and documentation
  52  * remain relevant:
  53  *
  54  * [...] the file is covered by the following:
  55  *
  56  * Copyright (c) 2009 Ben Harris.
  57  *
  58  * Permission is hereby granted, free of charge, to any person
  59  * obtaining a copy of this software and associated documentation files
  60  * (the "Software"), to deal in the Software without restriction,
  61  * including without limitation the rights to use, copy, modify, merge,
  62  * publish, distribute, sublicense, and/or sell copies of the Software,
  63  * and to permit persons to whom the Software is furnished to do so,
  64  * subject to the following conditions:
  65  *
  66  * The above copyright notice and this permission notice shall be
  67  * included in all copies or substantial portions of the Software.
  68  *
  69  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  70  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  71  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  72  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  73  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  74  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  75  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  76  * SOFTWARE.
  77  */
  78 /*
  79  * This [was once] a program to construct an outline font from a bitmap.
  80  * It's based on the character-rounding algorithm of the Mullard SAA5050
  81  * series of Teletext character generators, and thus works best on
  82  * character shapes in the same style of those of the SAA5050.  This
  83  * file includes all of the glyphs from the SAA5050, SAA5051, SAA5052,
  84  * SAA5053, SAA5054, SAA5055, SAA5056, and SAA5057.  The output is a
  85  * Spline Font Database file suitable for feeding to Fontforge.
  86  *
  87  * The character-smoothing algorithm of the SAA5050 and friends is
  88  * a fairly simple means of expanding a 5x9 pixel character to 10x18
  89  * pixels for use on an interlaced display.  All it does is to detect
  90  * 2x2 clumps of pixels containing a diagonal line and add a couple of
  91  * subpixels to it, like this:
  92  *
  93  * . #  -> . . # # -> . . # # or # . -> # # . . -> # # . .
  94  * # .     . . # #    . # # #    . #    # # . .    # # # .
  95  *         # # . .    # # # .           . . # #    . # # #
  96  *         # # . .    # # . .           . . # #    . . # #
  97  *
  98  * This is applied to every occurrence of these patterns, even when
  99  * they overlap, and the result is that thin diagonal lines are
 100  * smoothed out while other features mostly remain the same.
 101  *
 102  * One way of extending this towards continuity would be to repeatedly
 103  * double the resolution and add more pixels to diagonals each time,
 104  * but this ends up with the diagonals being much too heavy.  Instead,
 105  * in places where the SAA5050 would add pixels, this program adds a
 106  * largeish triangle to each unfilled pixel, and removes a small
 107  * triangle from each filled one, something like this:
 108  *
 109  * . #  -> . . # # -> . . / # or # . -> # # . . -> # \ . .
 110  * # .     . . # #    . / # /    . #    # # . .    \ # \ .
 111  *         # # . .    / # / .           . . # #    . \ # \
 112  *         # # . .    # / . .           . . # #    . . \ #
 113  *
 114  * The position of the lines is such that on a long diagonal line, the
 115  * amount of filled space is the same as in the rounded bitmap.  There
 116  * are a few additional complications, in that the trimming of filled
 117  * pixels can leave odd gaps where a diagonal stem joins another one,
 118  * so the code detects this and doesn't trim in these cases:
 119  *
 120  * . # # -> . . # # # # -> . . / # # # -> . . / # # #
 121  * # . .    . . # # # #    . / # / # #    . / # # # #
 122  *          # # . . . .    / # / . . .    / # / . . .
 123  *          # # . . . .    # / . . . .    # / . . . .
 124  *
 125  * [...]
 126  */
 127
 128 #include <assert.h>
 129 #include <errno.h>
 130 #include <stdbool.h>
 131 #include <stdio.h>
 132 #include <stdlib.h>
 133 #include <string.h>
 134
 135 static bool *
 136 blank(int size)
 137 {
 138     return calloc(size*size, sizeof(bool));
 139 }
 140
 141 static void output(bool *r, int size) {
 142     int x, y;
 143     for (y=0; y<size; y++) {
 144         putchar('\"');
 145         for (x=0; x<size; x++) {
 146             putchar(r[x+y*size] ? 'A' : '.');
 147         }
 148         putchar('\"');
 149         putchar('\n');
 150     }
 151 }
 152
 153 static bool *
 154 triangle(bool *r, int size, int startpos, bool top, bool left)
 155 {
 156     int x, y;
 157     for (y = 0; y < startpos; y++) {
 158         for (x = 0; x < startpos-y; x++) {
 159             int rx, ry;
 160             if (top) {
 161                 ry = y;
 162             } else {
 163                 ry = size-1 - y;
 164             }
 165             if (left) {
 166                 rx = x;
 167             } else {
 168                 rx = size-1 - x;
 169             }
 170             r[rx+ry*size]=true;
 171         }
 172     }
 173     return r;
 174 }
 175
 176 static void
 177 triangles(bool *r, int size, int startpos, int bl, int br, int tr, int tl)
 178 {
 179     if (!bl) {
 180         triangle(r, size, startpos, false, true);
 181     }
 182     if (!br) {
 183         triangle(r, size, startpos, false, false);
 184     }
 185     if (!tr) {
 186         triangle(r, size, startpos, true, false);
 187     }
 188     if (!tl) {
 189         triangle(r, size, startpos, true, true);
 190     }
 191 }
 192
 193 static void
 194 whitepixel(bool *r, int size, int bl, int br, int tr, int tl)
 195 {
 196     /* wrt blackpixel(): -1 for adjacency, -1 for gridlines
 197      * (which Golly has no apparent way to suppress :/ ) */
 198     const int startpos = size-size/4-2;
 199     triangles(r, size, startpos, bl, br, tr, tl);
 200 }
 201
 202 static void
 203 blackpixel(bool *r, int size, int bl, int br, int tr, int tl)
 204 {
 205     const int startpos = size/4;
 206     int i;
 207     triangles(r, size, startpos, bl, br, tr, tl);
 208     for (i=0; i<size*size; i++) {
 209         r[i] = !r[i];
 210     }
 211 }
 212
 213 void bedstead (void)
 214 {
 215         /* Output smoothing rules as a Golly rule table mapping from
 216          * (0,1) to an expanded set of states that we can hang icons
 217          * from. (The smoothing algorithm requires a 3x3 neighbourhood,
 218          * which is fortuitous.) */
 219
 220         /* Index into small bitmap */
 221 #define GETPIX(x,y) (!!(iter & 1u<<((y)*3+(x))))
 222 #define L GETPIX(x-1, y)
 223 #define R GETPIX(x+1, y)
 224 #define U GETPIX(x, y-1)
 225 #define D GETPIX(x, y+1)
 226 #define UL GETPIX(x-1, y-1)
 227 #define UR GETPIX(x+1, y-1)
 228 #define DL GETPIX(x-1, y+1)
 229 #define DR GETPIX(x+1, y+1)
 230
 231         /* Iterate over all neighbourhoods (9 cells) */
 232         int iter;
 233         for (iter = 0; iter < 1u<<9; iter++) {
 234                         int state, x = 1, y = 1;
 235                         /* The core of the Bedstead smoothing algorithm
 236                          * from Ben Harris. */
 237                         if (GETPIX(x, y)) {
 238                                 bool tl, tr, bl, br;
 239
 240                                 /* Assume filled in */
 241                                 tl = tr = bl = br = true;
 242                                 /* Check for diagonals */
 243                                 if ((UL && !U && !L) || (DR && !D && !R))
 244                                         tr = bl = false;
 245                                 if ((UR && !U && !R) || (DL && !D && !L))
 246                                         tl = br = false;
 247                                 /* Avoid odd gaps */
 248                                 if (L || UL || U) tl = true;
 249                                 if (R || UR || U) tr = true;
 250                                 if (L || DL || D) bl = true;
 251                                 if (R || DR || D) br = true;
 252                                 /* On states are 18..33 */
 253                                 state = 2 + 16 + (bl | br<<1 | tr<<2 | tl<<3);
 254                         } else {
 255                                 bool tl, tr, bl, br;
 256
 257                                 /* Assume clear */
 258                                 tl = tr = bl = br = false;
 259                                 /* white pixel -- just diagonals */
 260                                 if (L && U && !UL) tl = true;
 261                                 if (R && U && !UR) tr = true;
 262                                 if (L && D && !DL) bl = true;
 263                                 if (R && D && !DR) br = true;
 264                                 /* Off states are 2..17 */
 265                                 state = 2 + (bl | br<<1 | tr<<2 | tl<<3);
 266                         }
 267                         if (iter == 0) {
 268                                 /* Special case: we don't want to try to
 269                                  * flip all of infinite empty space between
 270                                  * 0 and 2 every step (this has odd effects
 271                                  * on Golly) */
 272                                 assert(state == 2);
 273                                 state = 0;
 274                         }
 275                         /* Output rule in Golly rule format
 276                          * (FIXME completely unoptimised) */
 277                         printf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n",
 278                                GETPIX(x,y),U,UR,R,DR,D,DL,L,UL,state);
 279         }
 280 }
 281
 282 void icons(void)
 283 {
 284         /* Bedbugs icons. In each size supported by Golly,
 285          * draw one icon per state, in the XPM format Golly wants.
 286          * This does not actually depend on bedstead() at all.
 287          * (FIXME: but it could. Some of the states we generate icons
 288          * and rules for are not actually reachable. We could spot
 289          * unused states above and avoid generating icons or rules for
 290          * them.)
 291          * (FIXME: we could also output pre-Golly-2.5 format icons) */
 292         {
 293             const int sizes[] = {7, 15, 31};
 294             int size_index;
 295             for (size_index = 0;
 296                  size_index < sizeof(sizes)/sizeof(sizes[0]);
 297                  size_index++) {
 298                 int size = sizes[size_index], state;
 299                 printf("XPM\n/* width height num_colors chars_per_pixel */\n");
 300                 printf("\"%d %d 2 1\"\n", size, size*33);
 301                 printf("/* colors */\n\". c #000000\"\n\"A c #FFFFFF\"\n");
 302                 /* icons never used for state 0 */
 303                 for (state = 1; state < 34; state++) {
 304                     bool *r = blank(size);
 305                     if (state == 0) {
 306                         ; /* Conway 'off': nothing */
 307                     } else if (state == 1) {
 308                         /* Conway 'on': everything */
 309                         memset(r, 1, size*size*sizeof(*r));
 310                     } else if (state < 16+2) {
 311                         /* Bedstead 'off' */
 312                         int bits = ~(state-2);
 313                         whitepixel(r, size, bits&1, bits&2, bits&4, bits&8);
 314                     } else {
 315                         /* Bedstead 'on' */
 316                         int bits = state-16-2;
 317                         blackpixel(r, size, bits&1, bits&2, bits&4, bits&8);
 318                     }
 319                     printf("/* icon for state %d */\n", state);
 320                     output(r, size);
 321                     free(r);
 322                 }
 323             }
 324         }
 325 }
 326
 327 int main(int argc, char *argv[])
 328 {
 329     while (!feof(stdin)) {
 330         char l[100]; /* bleah */
 331         if (!fgets(l, sizeof(l), stdin)) {
 332             break;
 333         }
 334         if (strlen(l) == sizeof(l)-1) {
 335             fprintf(stderr, "Long input line; possible truncation; I suck\n");
 336             exit(1);
 337         }
 338         if (strlen(l) >= 2 && l[0] == '@' && l[1] == '@') {
 339             size_t n = strcspn(l+2, "\n");
 340             if (strncmp(l+2, "BEDSTEAD", n) == 0) {
 341                 bedstead();
 342             } else if (strncmp(l+2, "ICONS", n) == 0) {
 343                 icons();
 344             } else {
 345                 /* Bodily insert named file on stdout. */
 346                 FILE *f;
 347                 l[n+2]='\0';
 348                 if (!(f = fopen(l+2, "r"))) {
 349                     fprintf(stderr, "Couldn't open '%s': %s\n", l+2,
 350                             strerror(errno));
 351                     exit(1);
 352                 } else {
 353                     do {
 354                         char buf[2048]; /* also bleah */
 355                         size_t n = fread(buf, 1, sizeof(buf), f);
 356                         fwrite(buf, 1, n, stdout);
 357                     } while (!feof(f) && !ferror(f));
 358                     if (ferror(f)) {
 359                         fprintf(stderr, "Error reading '%s': %s\n", l+2,
 360                                 strerror(errno));
 361                         exit(1);
 362                     }
 363                     fclose(f);
 364                 }
 365             }
 366         } else {
 367             printf("%s", l);
 368         }
 369     }
 370     return 0;
 371 }