git.sesse.net Git - ffmpeg/blob - libavfilter/vsrc_life.c

   1 /*
   2  * Copyright (c) Stefano Sabatini 2010
   3  *
   4  * This file is part of FFmpeg.
   5  *
   6  * FFmpeg is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * FFmpeg is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with FFmpeg; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20
  21 /**
  22  * @file
  23  * life video source, based on John Conways' Life Game
  24  */
  25
  26 /* #define DEBUG */
  27
  28 #include "libavutil/file.h"
  29 #include "libavutil/lfg.h"
  30 #include "libavutil/opt.h"
  31 #include "libavutil/parseutils.h"
  32 #include "libavutil/random_seed.h"
  33 #include "avfilter.h"
  34
  35 typedef struct {
  36     const AVClass *class;
  37     int w, h;
  38     char *filename;
  39     char *rule_str;
  40     uint8_t *file_buf;
  41     size_t file_bufsize;
  42     char *buf[2];
  43     uint8_t  buf_idx;
  44     uint16_t stay_rule;         ///< encode the behavior for filled cells
  45     uint16_t born_rule;         ///< encode the behavior for empty cells
  46     uint64_t pts;
  47     AVRational time_base;
  48     char *size;                 ///< video frame size
  49     char *rate;                 ///< video frame rate
  50     double   random_fill_ratio;
  51     uint32_t random_seed;
  52     int stitch;
  53     AVLFG lfg;
  54 } LifeContext;
  55
  56 #define OFFSET(x) offsetof(LifeContext, x)
  57
  58 static const AVOption life_options[] = {
  59     { "filename", "set source file",  OFFSET(filename), AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0 },
  60     { "f",        "set source file",  OFFSET(filename), AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0 },
  61     { "size",     "set video size",   OFFSET(size),     AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0 },
  62     { "s",        "set video size",   OFFSET(size),     AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0 },
  63     { "rate",     "set video rate",   OFFSET(rate),     AV_OPT_TYPE_STRING, {.str = "25"}, 0, 0 },
  64     { "r",        "set video rate",   OFFSET(rate),     AV_OPT_TYPE_STRING, {.str = "25"}, 0, 0 },
  65     { "rule",     "set rule",         OFFSET(rule_str), AV_OPT_TYPE_STRING, {.str = "B3/S23"}, CHAR_MIN, CHAR_MAX },
  66     { "random_fill_ratio", "set fill ratio for filling initial grid randomly", OFFSET(random_fill_ratio), AV_OPT_TYPE_DOUBLE, {.dbl=1/M_PHI}, 0, 1 },
  67     { "ratio",             "set fill ratio for filling initial grid randomly", OFFSET(random_fill_ratio), AV_OPT_TYPE_DOUBLE, {.dbl=1/M_PHI}, 0, 1 },
  68     { "random_seed", "set the seed for filling the initial grid randomly", OFFSET(random_seed), AV_OPT_TYPE_INT, {.dbl=-1}, -1, UINT32_MAX },
  69     { "seed",        "set the seed for filling the initial grid randomly", OFFSET(random_seed), AV_OPT_TYPE_INT, {.dbl=-1}, -1, UINT32_MAX },
  70     { "stitch",      "stitch boundaries", OFFSET(stitch), AV_OPT_TYPE_INT, {.dbl=1}, 0, 1 },
  71     { NULL },
  72 };
  73
  74 static const char *life_get_name(void *ctx)
  75 {
  76     return "life";
  77 }
  78
  79 static const AVClass life_class = {
  80     "LifeContext",
  81     life_get_name,
  82     life_options
  83 };
  84
  85 static int parse_rule(uint16_t *born_rule, uint16_t *stay_rule,
  86                       const char *rule_str, void *log_ctx)
  87 {
  88     char *tail;
  89     const char *p = rule_str;
  90     *born_rule = 0;
  91     *stay_rule = 0;
  92
  93     if (strchr("bBsS", *p)) {
  94         /* parse rule as a Born / Stay Alive code, see
  95          * http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life */
  96         do {
  97             uint16_t *rule = (*p == 'b' || *p == 'B') ? born_rule : stay_rule;
  98             p++;
  99             while (*p >= '0' && *p <= '8') {
 100                 *rule += 1<<(*p - '0');
 101                 p++;
 102             }
 103             if (*p != '/')
 104                 break;
 105             p++;
 106         } while (strchr("bBsS", *p));
 107
 108         if (*p)
 109             goto error;
 110     } else {
 111         /* parse rule as a number, expressed in the form STAY|(BORN<<9),
 112          * where STAY and BORN encode the corresponding 9-bits rule */
 113         long int rule = strtol(rule_str, &tail, 10);
 114         if (*tail)
 115             goto error;
 116         *born_rule  = ((1<<9)-1) & rule;
 117         *stay_rule = rule >> 9;
 118     }
 119
 120     return 0;
 121
 122 error:
 123     av_log(log_ctx, AV_LOG_ERROR, "Invalid rule code '%s' provided\n", rule_str);
 124     return AVERROR(EINVAL);
 125 }
 126
 127 #ifdef DEBUG
 128 static void show_life_grid(AVFilterContext *ctx)
 129 {
 130     LifeContext *life = ctx->priv;
 131     int i, j;
 132
 133     char *line = av_malloc(life->w + 1);
 134     if (!line)
 135         return;
 136     for (i = 0; i < life->h; i++) {
 137         for (j = 0; j < life->w; j++)
 138             line[j] = life->buf[life->buf_idx][i*life->w + j] ? '@' : ' ';
 139         line[j] = 0;
 140         av_log(ctx, AV_LOG_DEBUG, "%3d: %s\n", i, line);
 141     }
 142     av_free(line);
 143 }
 144 #endif
 145
 146 static int init_pattern_from_file(AVFilterContext *ctx)
 147 {
 148     LifeContext *life = ctx->priv;
 149     char *p;
 150     int ret, i, i0, j, h = 0, w, max_w = 0;
 151
 152     if ((ret = av_file_map(life->filename, &life->file_buf, &life->file_bufsize,
 153                            0, ctx)) < 0)
 154         return ret;
 155
 156     /* prescan file to get the number of lines and the maximum width */
 157     w = 0;
 158     for (i = 0; i < life->file_bufsize; i++) {
 159         if (life->file_buf[i] == '\n') {
 160             h++; max_w = FFMAX(w, max_w); w = 0;
 161         } else {
 162             w++;
 163         }
 164     }
 165     av_log(ctx, AV_LOG_DEBUG, "h:%d max_w:%d\n", h, max_w);
 166
 167     if (life->size) {
 168         if (max_w > life->w || h > life->h) {
 169             av_log(ctx, AV_LOG_ERROR,
 170                    "The specified size is %dx%d which cannot contain the provided file size of %dx%d\n",
 171                    life->w, life->h, max_w, h);
 172             return AVERROR(EINVAL);
 173         }
 174     } else {
 175         /* size was not specified, set it to size of the grid */
 176         life->w = max_w;
 177         life->h = h;
 178     }
 179
 180     if (!(life->buf[0] = av_mallocz(sizeof(char) * life->h * life->w)) ||
 181         !(life->buf[1] = av_mallocz(sizeof(char) * life->h * life->w))) {
 182         av_free(life->buf[0]);
 183         av_free(life->buf[1]);
 184         return AVERROR(ENOMEM);
 185     }
 186
 187     /* fill buf[0] */
 188     p = life->file_buf;
 189     for (i0 = 0, i = (life->h - h)/2; i0 < h; i0++, i++) {
 190         for (j = (life->w - max_w)/2;; j++) {
 191             av_log(ctx, AV_LOG_DEBUG, "%d:%d %c\n", i, j, *p == '\n' ? 'N' : *p);
 192             if (*p == '\n') {
 193                 p++; break;
 194             } else
 195                 life->buf[0][i*life->w + j] = !!isgraph(*(p++));
 196         }
 197     }
 198     life->buf_idx = 0;
 199
 200     return 0;
 201 }
 202
 203 static int init(AVFilterContext *ctx, const char *args, void *opaque)
 204 {
 205     LifeContext *life = ctx->priv;
 206     AVRational frame_rate;
 207     int ret;
 208
 209     life->class = &life_class;
 210     av_opt_set_defaults(life);
 211
 212     if ((ret = av_set_options_string(life, args, "=", ":")) < 0) {
 213         av_log(ctx, AV_LOG_ERROR, "Error parsing options string: '%s'\n", args);
 214         return ret;
 215     }
 216
 217     if ((ret = av_parse_video_rate(&frame_rate, life->rate)) < 0) {
 218         av_log(ctx, AV_LOG_ERROR, "Invalid frame rate: %s\n", life->rate);
 219         return AVERROR(EINVAL);
 220     }
 221
 222     if (!life->size && !life->filename)
 223         av_opt_set(life, "size", "320x240", 0);
 224
 225     if (life->size &&
 226         (ret = av_parse_video_size(&life->w, &life->h, life->size)) < 0) {
 227         av_log(ctx, AV_LOG_ERROR, "Invalid frame size: %s\n", life->size);
 228         return ret;
 229     }
 230
 231     if ((ret = parse_rule(&life->born_rule, &life->stay_rule, life->rule_str, ctx)) < 0)
 232         return ret;
 233
 234     life->time_base.num = frame_rate.den;
 235     life->time_base.den = frame_rate.num;
 236
 237     if (!life->filename) {
 238         /* fill the grid randomly */
 239         int i;
 240
 241         if (!(life->buf[0] = av_mallocz(sizeof(char) * life->h * life->w)) ||
 242             !(life->buf[1] = av_mallocz(sizeof(char) * life->h * life->w))) {
 243             av_free(life->buf[0]);
 244             av_free(life->buf[1]);
 245             return AVERROR(ENOMEM);
 246         }
 247         if (life->random_seed == -1)
 248             life->random_seed = av_get_random_seed();
 249
 250         av_lfg_init(&life->lfg, life->random_seed);
 251
 252         for (i = 0; i < life->w * life->h; i++) {
 253             double r = (double)av_lfg_get(&life->lfg) / UINT32_MAX;
 254             if (r <= life->random_fill_ratio)
 255                 life->buf[0][i] = 1;
 256         }
 257         life->buf_idx = 0;
 258     } else {
 259         if ((ret = init_pattern_from_file(ctx)) < 0)
 260             return ret;
 261     }
 262
 263     av_log(ctx, AV_LOG_INFO,
 264            "s:%dx%d r:%d/%d rule:%s stay_rule:%d born_rule:%d stitch:%d\n",
 265            life->w, life->h, frame_rate.num, frame_rate.den,
 266            life->rule_str, life->stay_rule, life->born_rule, life->stitch);
 267     return 0;
 268 }
 269
 270 static av_cold void uninit(AVFilterContext *ctx)
 271 {
 272     LifeContext *life = ctx->priv;
 273
 274     av_file_unmap(life->file_buf, life->file_bufsize);
 275     av_freep(&life->rule_str);
 276     av_freep(&life->buf[0]);
 277     av_freep(&life->buf[1]);
 278 }
 279
 280 static int config_props(AVFilterLink *outlink)
 281 {
 282     LifeContext *life = outlink->src->priv;
 283
 284     outlink->w = life->w;
 285     outlink->h = life->h;
 286     outlink->time_base = life->time_base;
 287
 288     return 0;
 289 }
 290
 291 static void evolve(AVFilterContext *ctx)
 292 {
 293     LifeContext *life = ctx->priv;
 294     int i, j, v;
 295     uint8_t *oldbuf = life->buf[ life->buf_idx];
 296     uint8_t *newbuf = life->buf[!life->buf_idx];
 297
 298     enum { NW, N, NE, W, E, SW, S, SE };
 299
 300     /* evolve the grid */
 301     for (i = 0; i < life->h; i++) {
 302         for (j = 0; j < life->w; j++) {
 303             int pos[8][2], n;
 304             if (life->stitch) {
 305                 pos[NW][0] = (i-1) < 0 ? life->h-1 : i-1; pos[NW][1] = (j-1) < 0 ? life->w-1 : j-1;
 306                 pos[N ][0] = (i-1) < 0 ? life->h-1 : i-1; pos[N ][1] =                         j  ;
 307                 pos[NE][0] = (i-1) < 0 ? life->h-1 : i-1; pos[NE][1] = (j+1) == life->w ?  0 : j+1;
 308                 pos[W ][0] =                         i  ; pos[W ][1] = (j-1) < 0 ? life->w-1 : j-1;
 309                 pos[E ][0] =                         i  ; pos[E ][1] = (j+1) == life->w ? 0  : j+1;
 310                 pos[SW][0] = (i+1) == life->h ?  0 : i+1; pos[SW][1] = (j-1) < 0 ? life->w-1 : j-1;
 311                 pos[S ][0] = (i+1) == life->h ?  0 : i+1; pos[S ][1] =                         j  ;
 312                 pos[SE][0] = (i+1) == life->h ?  0 : i+1; pos[SE][1] = (j+1) == life->w ?  0 : j+1;
 313             } else {
 314                 pos[NW][0] = (i-1) < 0 ? -1        : i-1; pos[NW][1] = (j-1) < 0 ? -1        : j-1;
 315                 pos[N ][0] = (i-1) < 0 ? -1        : i-1; pos[N ][1] =                         j  ;
 316                 pos[NE][0] = (i-1) < 0 ? -1        : i-1; pos[NE][1] = (j+1) == life->w ? -1 : j+1;
 317                 pos[W ][0] =                         i  ; pos[W ][1] = (j-1) < 0 ? -1        : j-1;
 318                 pos[E ][0] =                         i  ; pos[E ][1] = (j+1) == life->w ? -1 : j+1;
 319                 pos[SW][0] = (i+1) == life->h ? -1 : i+1; pos[SW][1] = (j-1) < 0 ? -1        : j-1;
 320                 pos[S ][0] = (i+1) == life->h ? -1 : i+1; pos[S ][1] =                         j  ;
 321                 pos[SE][0] = (i+1) == life->h ? -1 : i+1; pos[SE][1] = (j+1) == life->w ? -1 : j+1;
 322             }
 323
 324             /* compute the number of live neighbor cells */
 325             n = (pos[NW][0] == -1 || pos[NW][1] == -1 ? 0 : oldbuf[pos[NW][0]*life->w + pos[NW][1]]) +
 326                 (pos[N ][0] == -1 || pos[N ][1] == -1 ? 0 : oldbuf[pos[N ][0]*life->w + pos[N ][1]]) +
 327                 (pos[NE][0] == -1 || pos[NE][1] == -1 ? 0 : oldbuf[pos[NE][0]*life->w + pos[NE][1]]) +
 328                 (pos[W ][0] == -1 || pos[W ][1] == -1 ? 0 : oldbuf[pos[W ][0]*life->w + pos[W ][1]]) +
 329                 (pos[E ][0] == -1 || pos[E ][1] == -1 ? 0 : oldbuf[pos[E ][0]*life->w + pos[E ][1]]) +
 330                 (pos[SW][0] == -1 || pos[SW][1] == -1 ? 0 : oldbuf[pos[SW][0]*life->w + pos[SW][1]]) +
 331                 (pos[S ][0] == -1 || pos[S ][1] == -1 ? 0 : oldbuf[pos[S ][0]*life->w + pos[S ][1]]) +
 332                 (pos[SE][0] == -1 || pos[SE][1] == -1 ? 0 : oldbuf[pos[SE][0]*life->w + pos[SE][1]]);
 333             v = !!(1<<n & (oldbuf[i*life->w + j] ? life->stay_rule : life->born_rule));
 334             av_dlog(ctx, "i:%d j:%d live_neighbors:%d cell:%d -> cell:%d\n", i, j, n, oldbuf[i*life->w + j], v);
 335             newbuf[i*life->w+j] = v;
 336         }
 337     }
 338
 339     life->buf_idx = !life->buf_idx;
 340 }
 341
 342 static void fill_picture(AVFilterContext *ctx, AVFilterBufferRef *picref)
 343 {
 344     LifeContext *life = ctx->priv;
 345     uint8_t *buf = life->buf[life->buf_idx];
 346     int i, j, k;
 347
 348     /* fill the output picture with the old grid buffer */
 349     for (i = 0; i < life->h; i++) {
 350         uint8_t byte = 0;
 351         uint8_t *p = picref->data[0] + i * picref->linesize[0];
 352         for (k = 0, j = 0; j < life->w; j++) {
 353             byte |= buf[i*life->w+j]<<(7-k++);
 354             if (k==8 || j == life->w-1) {
 355                 k = 0;
 356                 *p++ = byte;
 357                 byte = 0;
 358             }
 359         }
 360     }
 361 }
 362
 363 static int request_frame(AVFilterLink *outlink)
 364 {
 365     LifeContext *life = outlink->src->priv;
 366     AVFilterBufferRef *picref = avfilter_get_video_buffer(outlink, AV_PERM_WRITE, life->w, life->h);
 367     picref->video->sample_aspect_ratio = (AVRational) {1, 1};
 368     picref->pts = life->pts++;
 369     picref->pos = -1;
 370
 371     fill_picture(outlink->src, picref);
 372     evolve(outlink->src);
 373 #ifdef DEBUG
 374     show_life_grid(outlink->src);
 375 #endif
 376
 377     avfilter_start_frame(outlink, avfilter_ref_buffer(picref, ~0));
 378     avfilter_draw_slice(outlink, 0, life->h, 1);
 379     avfilter_end_frame(outlink);
 380     avfilter_unref_buffer(picref);
 381
 382     return 0;
 383 }
 384
 385 static int query_formats(AVFilterContext *ctx)
 386 {
 387     static const enum PixelFormat pix_fmts[] = { PIX_FMT_MONOBLACK, PIX_FMT_NONE };
 388     avfilter_set_common_pixel_formats(ctx, avfilter_make_format_list(pix_fmts));
 389     return 0;
 390 }
 391
 392 AVFilter avfilter_vsrc_life = {
 393     .name        = "life",
 394     .description = NULL_IF_CONFIG_SMALL("Create life."),
 395     .priv_size = sizeof(LifeContext),
 396     .init      = init,
 397     .uninit    = uninit,
 398     .query_formats = query_formats,
 399
 400     .inputs    = (const AVFilterPad[]) {
 401         { .name = NULL}
 402     },
 403     .outputs   = (const AVFilterPad[]) {
 404         { .name            = "default",
 405           .type            = AVMEDIA_TYPE_VIDEO,
 406           .request_frame   = request_frame,
 407           .config_props    = config_props },
 408         { .name = NULL}
 409     },
 410 };