lavfi: add cellauto source

6 files changed, 489 insertions, 1 deletions

diff --git a/Changelog b/Changelog
index 2a20c357c4..89d1893369 100644
--- a/Changelog
+++ b/Changelog
@@ -133,6 +133,7 @@ easier to use. The changes are:
 - CLJR encoder
 - new option: -report
 - Dxtory capture format decoder
+- cellauto source
 
 
 version 0.8:
diff --git a/doc/filters.texi b/doc/filters.texi
index 0b73fe49ad..09ef5985d7 100644
--- a/doc/filters.texi
+++ b/doc/filters.texi
@@ -2604,6 +2604,121 @@ this example corresponds to:
 buffer=320:240:6:1:24:1:1
 @end example
 
+@section cellauto
+
+Create a pattern generated by an elementary cellular automaton.
+
+The initial state of the cellular automaton can be defined through the
+@option{filename}, and @option{pattern} options. If such options are
+not specified an initial state is created randomly.
+
+At each new frame a new row in the video is filled with the result of
+the cellular automaton next generation. The behavior when the whole
+frame is filled is defined by the @option{scroll} option.
+
+This source accepts a list of options in the form of
+@var{key}=@var{value} pairs separated by ":". A description of the
+accepted options follows.
+
+@table @option
+@item filename, f
+Read the initial cellular automaton state, i.e. the starting row, from
+the specified file.
+In the file, each non-whitespace character is considered an alive
+cell, a newline will terminate the row, and further characters in the
+file will be ignored.
+
+@item pattern, p
+Read the initial cellular automaton state, i.e. the starting row, from
+the specified string.
+
+Each non-whitespace character in the string is considered an alive
+cell, a newline will terminate the row, and further characters in the
+string will be ignored.
+
+@item rate, r
+Set the video rate, that is the number of frames generated per second.
+Default is 25.
+
+@item random_fill_ratio, ratio
+Set the random fill ratio for the initial cellular automaton row. It
+is a floating point number value ranging from 0 to 1, defaults to
+1/PHI.
+
+This option is ignored when a file or a pattern is specified.
+
+@item random_seed, seed
+Set the seed for filling randomly the initial row, must be an integer
+included between 0 and UINT32_MAX. If not specified, or if explicitly
+set to -1, the filter will try to use a good random seed on a best
+effort basis.
+
+@item rule
+Set the cellular automaton rule, it is a number ranging from 0 to 255.
+Default value is 110.
+
+@item size, s
+Set the size of the output video.
+
+If @option{filename} or @option{pattern} is specified, the size is set
+by default to the width of the specified initial state row, and the
+height is set to @var{width} * PHI.
+
+If @option{size} is set, it must contain the width of the specified
+pattern string, and the specified pattern will be centered in the
+larger row.
+
+If a filename or a pattern string is not specified, the size value
+defaults to "320x518" (used for a randomly generated initial state).
+
+@item scroll
+If set to 1, scroll the output upward when all the rows in the output
+have been already filled. If set to 0, the new generated row will be
+written over the top row just after the bottom row is filled.
+Defaults to 1.
+
+@item start_full, full
+If set to 1, completely fill the output with generated rows before
+outputting the first frame.
+This is the default behavior, for disabling set the value to 0.
+
+@item stitch
+If set to 1, stitch the left and right row edges together.
+This is the default behavior, for disabling set the value to 0.
+@end table
+
+@subsection Examples
+
+@itemize
+@item
+Read the initial state from @file{pattern}, and specify an output of
+size 200x400.
+@example
+cellauto=f=pattern:s=200x400
+@end example
+
+@item
+Generate a random initial row with a width of 200 cells, with a fill
+ratio of 2/3:
+@example
+cellauto=ratio=2/3:s=200x200
+@end example
+
+@item
+Create a pattern generated by rule 18 starting by a single alive cell
+centered on an initial row with width 100:
+@example
+cellauto=p=@@:s=100x400:full=0:rule=18
+@end example
+
+@item
+Specify a more elaborated initial pattern:
+@example
+cellauto=p='@@@@ @@ @@@@':s=100x400:full=0:rule=18
+@end example
+
+@end itemize
+
 @section color
 
 Provide an uniformly colored input.
diff --git a/libavfilter/Makefile b/libavfilter/Makefile
index 7ee4d17101..4351d5e4e6 100644
--- a/libavfilter/Makefile
+++ b/libavfilter/Makefile
@@ -84,6 +84,7 @@ OBJS-$(CONFIG_VFLIP_FILTER)                  += vf_vflip.o
 OBJS-$(CONFIG_YADIF_FILTER)                  += vf_yadif.o
 
 OBJS-$(CONFIG_BUFFER_FILTER)                 += vsrc_buffer.o
+OBJS-$(CONFIG_CELLAUTO_FILTER)               += vsrc_cellauto.o
 OBJS-$(CONFIG_COLOR_FILTER)                  += vsrc_color.o
 OBJS-$(CONFIG_FREI0R_SRC_FILTER)             += vf_frei0r.o
 OBJS-$(CONFIG_LIFE_FILTER)                   += vsrc_life.o
diff --git a/libavfilter/allfilters.c b/libavfilter/allfilters.c
index 2fe92bdb28..fb50a3a0a9 100644
--- a/libavfilter/allfilters.c
+++ b/libavfilter/allfilters.c
@@ -95,6 +95,7 @@ void avfilter_register_all(void)
     REGISTER_FILTER (YADIF,       yadif,       vf);
 
     REGISTER_FILTER (BUFFER,      buffer,      vsrc);
+    REGISTER_FILTER (CELLAUTO,    cellauto,    vsrc);
     REGISTER_FILTER (COLOR,       color,       vsrc);
     REGISTER_FILTER (FREI0R,      frei0r_src,  vsrc);
     REGISTER_FILTER (LIFE,        life,        vsrc);
diff --git a/libavfilter/avfilter.h b/libavfilter/avfilter.h
index 1e295abc04..4aceebd7ac 100644
--- a/libavfilter/avfilter.h
+++ b/libavfilter/avfilter.h
@@ -29,7 +29,7 @@
 #include "libavutil/rational.h"
 
 #define LIBAVFILTER_VERSION_MAJOR  2
-#define LIBAVFILTER_VERSION_MINOR 52
+#define LIBAVFILTER_VERSION_MINOR 53
 #define LIBAVFILTER_VERSION_MICRO  0
 
 #define LIBAVFILTER_VERSION_INT AV_VERSION_INT(LIBAVFILTER_VERSION_MAJOR, \
diff --git a/libavfilter/vsrc_cellauto.c b/libavfilter/vsrc_cellauto.c
new file mode 100644
index 0000000000..fc235a1896
--- /dev/null
+++ b/libavfilter/vsrc_cellauto.c
@@ -0,0 +1,370 @@
+/*
+ * Copyright (c) Stefano Sabatini 2011
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/**
+ * @file
+ * cellular automaton video source, based on Stephen Wolfram "experimentus crucis"
+ */
+
+/* #define DEBUG */
+
+#include "libavutil/file.h"
+#include "libavutil/lfg.h"
+#include "libavutil/opt.h"
+#include "libavutil/parseutils.h"
+#include "libavutil/random_seed.h"
+#include "avfilter.h"
+
+typedef struct {
+    const AVClass *class;
+    int w, h;
+    char *filename;
+    char *rule_str;
+    uint8_t *file_buf;
+    size_t file_bufsize;
+    uint8_t *buf;
+    int buf_prev_row_idx, buf_row_idx;
+    uint8_t rule;
+    uint64_t pts;
+    AVRational time_base;
+    char *size;                 ///< video frame size
+    char *rate;                 ///< video frame rate
+    double   random_fill_ratio;
+    uint32_t random_seed;
+    int stitch, scroll, start_full;
+    int64_t generation;         ///< the generation number, starting from 0
+    AVLFG lfg;
+    char *pattern;
+} CellAutoContext;
+
+#define OFFSET(x) offsetof(CellAutoContext, x)
+
+static const AVOption cellauto_options[] = {
+    { "filename", "read initial pattern from file", OFFSET(filename), AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0 },
+    { "f",        "read initial pattern from file", OFFSET(filename), AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0 },
+    { "pattern",  "set initial pattern", OFFSET(pattern), AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0 },
+    { "p",        "set initial pattern", OFFSET(pattern), AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0 },
+    { "rate",     "set video rate", OFFSET(rate), AV_OPT_TYPE_STRING, {.str = "25"}, 0, 0 },
+    { "r",        "set video rate", OFFSET(rate), AV_OPT_TYPE_STRING, {.str = "25"}, 0, 0 },
+    { "size",     "set video size", OFFSET(size), AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0 },
+    { "s",        "set video size", OFFSET(size), AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0 },
+    { "rule",     "set rule",       OFFSET(rule), AV_OPT_TYPE_INT,    {.dbl = 110},  0, 255 },
+    { "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 },
+    { "ratio",             "set fill ratio for filling initial grid randomly", OFFSET(random_fill_ratio), AV_OPT_TYPE_DOUBLE, {.dbl = 1/M_PHI}, 0, 1 },
+    { "random_seed", "set the seed for filling the initial grid randomly", OFFSET(random_seed), AV_OPT_TYPE_INT, {.dbl = -1}, -1, UINT32_MAX },
+    { "seed",        "set the seed for filling the initial grid randomly", OFFSET(random_seed), AV_OPT_TYPE_INT, {.dbl = -1}, -1, UINT32_MAX },
+    { "scroll",      "scroll pattern downward", OFFSET(scroll), AV_OPT_TYPE_INT, {.dbl = 1}, 0, 1 },
+    { "start_full",  "start filling the whole video", OFFSET(start_full), AV_OPT_TYPE_INT, {.dbl = 0}, 0, 1 },
+    { "full",        "start filling the whole video", OFFSET(start_full), AV_OPT_TYPE_INT, {.dbl = 1}, 0, 1 },
+    { "stitch",      "stitch boundaries", OFFSET(stitch), AV_OPT_TYPE_INT,    {.dbl = 1},   0, 1 },
+    { NULL },
+};
+
+static const char *cellauto_get_name(void *ctx)
+{
+    return "cellauto";
+}
+
+static const AVClass cellauto_class = {
+    "CellAutoContext",
+    cellauto_get_name,
+    cellauto_options
+};
+
+#ifdef DEBUG
+static void show_cellauto_row(AVFilterContext *ctx)
+{
+    CellAutoContext *cellauto = ctx->priv;
+    int i;
+    uint8_t *row = cellauto->buf + cellauto->w * cellauto->buf_row_idx;
+    char *line = av_malloc(cellauto->w + 1);
+    if (!line)
+        return;
+
+    for (i = 0; i < cellauto->w; i++)
+        line[i] = row[i] ? '@' : ' ';
+    line[i] = 0;
+    av_log(ctx, AV_LOG_DEBUG, "generation:%"PRId64" row:%s|\n", cellauto->generation, line);
+    av_free(line);
+}
+#endif
+
+static int init_pattern_from_string(AVFilterContext *ctx)
+{
+    CellAutoContext *cellauto = ctx->priv;
+    char *p;
+    int i, w = 0;
+
+    w = strlen(cellauto->pattern);
+    av_log(ctx, AV_LOG_DEBUG, "w:%d\n", w);
+
+    if (cellauto->size) {
+        if (w > cellauto->w) {
+            av_log(ctx, AV_LOG_ERROR,
+                   "The specified width is %d which cannot contain the provided string width of %d\n",
+                   cellauto->w, w);
+            return AVERROR(EINVAL);
+        }
+    } else {
+        /* width was not specified, set it to width of the provided row */
+        cellauto->w = w;
+        cellauto->h = (double)cellauto->w * M_PHI;
+    }
+
+    cellauto->buf = av_mallocz(sizeof(uint8_t) * cellauto->w * cellauto->h);
+    if (!cellauto->buf)
+        return AVERROR(ENOMEM);
+
+    /* fill buf */
+    p = cellauto->pattern;
+    for (i = (cellauto->w - w)/2;; i++) {
+        av_log(ctx, AV_LOG_DEBUG, "%d %c\n", i, *p == '\n' ? 'N' : *p);
+        if (*p == '\n' || !*p)
+            break;
+        else
+            cellauto->buf[i] = !!isgraph(*(p++));
+    }
+
+    return 0;
+}
+
+static int init_pattern_from_file(AVFilterContext *ctx)
+{
+    CellAutoContext *cellauto = ctx->priv;
+    int ret;
+
+    ret = av_file_map(cellauto->filename,
+                      &cellauto->file_buf, &cellauto->file_bufsize, 0, ctx);
+    if (ret < 0)
+        return ret;
+
+    /* create a string based on the read file */
+    cellauto->pattern = av_malloc(cellauto->file_bufsize + 1);
+    if (!cellauto->pattern)
+        return AVERROR(ENOMEM);
+    memcpy(cellauto->pattern, cellauto->file_buf, cellauto->file_bufsize);
+    cellauto->pattern[cellauto->file_bufsize] = 0;
+
+    return init_pattern_from_string(ctx);
+}
+
+static int init(AVFilterContext *ctx, const char *args, void *opaque)
+{
+    CellAutoContext *cellauto = ctx->priv;
+    AVRational frame_rate;
+    int ret;
+
+    cellauto->class = &cellauto_class;
+    av_opt_set_defaults(cellauto);
+
+    if ((ret = av_set_options_string(cellauto, args, "=", ":")) < 0) {
+        av_log(ctx, AV_LOG_ERROR, "Error parsing options string: '%s'\n", args);
+        return ret;
+    }
+
+    if ((ret = av_parse_video_rate(&frame_rate, cellauto->rate)) < 0) {
+        av_log(ctx, AV_LOG_ERROR, "Invalid frame rate: %s\n", cellauto->rate);
+        return AVERROR(EINVAL);
+    }
+
+    if (!cellauto->size && !cellauto->filename && !cellauto->pattern)
+        av_opt_set(cellauto, "size", "320x518", 0);
+
+    if (cellauto->size &&
+        (ret = av_parse_video_size(&cellauto->w, &cellauto->h, cellauto->size)) < 0) {
+        av_log(ctx, AV_LOG_ERROR, "Invalid frame size: %s\n", cellauto->size);
+        return ret;
+    }
+
+    cellauto->time_base.num = frame_rate.den;
+    cellauto->time_base.den = frame_rate.num;
+
+    if (cellauto->filename && cellauto->pattern) {
+        av_log(ctx, AV_LOG_ERROR, "Only one of the filename or pattern options can be used\n");
+        return AVERROR(EINVAL);
+    }
+
+    if (cellauto->filename) {
+        if ((ret = init_pattern_from_file(ctx)) < 0)
+            return ret;
+    } else if (cellauto->pattern) {
+        if ((ret = init_pattern_from_string(ctx)) < 0)
+            return ret;
+    } else {
+        /* fill the first row randomly */
+        int i;
+
+        cellauto->buf = av_mallocz(sizeof(uint8_t) * cellauto->w * cellauto->h);
+        if (!cellauto->buf)
+            return AVERROR(ENOMEM);
+        if (cellauto->random_seed == -1)
+            cellauto->random_seed = av_get_random_seed();
+
+        av_lfg_init(&cellauto->lfg, cellauto->random_seed);
+
+        for (i = 0; i < cellauto->w; i++) {
+            double r = (double)av_lfg_get(&cellauto->lfg) / UINT32_MAX;
+            if (r <= cellauto->random_fill_ratio)
+                cellauto->buf[i] = 1;
+        }
+    }
+
+    av_log(ctx, AV_LOG_INFO,
+           "s:%dx%d r:%d/%d rule:%d stitch:%d scroll:%d full:%d seed:%u\n",
+           cellauto->w, cellauto->h, frame_rate.num, frame_rate.den,
+           cellauto->rule, cellauto->stitch, cellauto->scroll, cellauto->start_full,
+           cellauto->random_seed);
+    return 0;
+}
+
+static av_cold void uninit(AVFilterContext *ctx)
+{
+    CellAutoContext *cellauto = ctx->priv;
+
+    av_file_unmap(cellauto->file_buf, cellauto->file_bufsize);
+    av_freep(&cellauto->buf);
+    av_freep(&cellauto->pattern);
+}
+
+static int config_props(AVFilterLink *outlink)
+{
+    CellAutoContext *cellauto = outlink->src->priv;
+
+    outlink->w = cellauto->w;
+    outlink->h = cellauto->h;
+    outlink->time_base = cellauto->time_base;
+
+    return 0;
+}
+
+static void evolve(AVFilterContext *ctx)
+{
+    CellAutoContext *cellauto = ctx->priv;
+    int i, v, pos[3];
+    uint8_t *row, *prev_row = cellauto->buf + cellauto->buf_row_idx * cellauto->w;
+    enum { NW, N, NE };
+
+    cellauto->buf_prev_row_idx = cellauto->buf_row_idx;
+    cellauto->buf_row_idx      = cellauto->buf_row_idx == cellauto->h-1 ? 0 : cellauto->buf_row_idx+1;
+    row = cellauto->buf + cellauto->w * cellauto->buf_row_idx;
+
+    for (i = 0; i < cellauto->w; i++) {
+        if (cellauto->stitch) {
+            pos[NW] = i-1 < 0 ? cellauto->w-1 : i-1;
+            pos[N]  = i;
+            pos[NE] = i+1 == cellauto->w ? 0  : i+1;
+            v = prev_row[pos[NW]]<<2 | prev_row[pos[N]]<<1 | prev_row[pos[NE]];
+        } else {
+            v = 0;
+            v|= i-1 >= 0          ? prev_row[i-1]<<2 : 0;
+            v|=                     prev_row[i  ]<<1    ;
+            v|= i+1 < cellauto->w ? prev_row[i+1]    : 0;
+        }
+        row[i] = !!(cellauto->rule & (1<<v));
+        av_dlog(ctx, "i:%d context:%c%c%c -> cell:%d\n", i,
+                v&4?'@':' ', v&2?'@':' ', v&1?'@':' ', row[i]);
+    }
+
+    cellauto->generation++;
+}
+
+static void fill_picture(AVFilterContext *ctx, AVFilterBufferRef *picref)
+{
+    CellAutoContext *cellauto = ctx->priv;
+    int i, j, k, row_idx = 0;
+    uint8_t *p0 = picref->data[0];
+
+    if (cellauto->scroll && cellauto->generation >= cellauto->h)
+        /* show on top the oldest row */
+        row_idx = (cellauto->buf_row_idx + 1) % cellauto->h;
+
+    /* fill the output picture with the whole buffer */
+    for (i = 0; i < cellauto->h; i++) {
+        uint8_t byte = 0;
+        uint8_t *row = cellauto->buf + row_idx*cellauto->w;
+        uint8_t *p = p0;
+        for (k = 0, j = 0; j < cellauto->w; j++) {
+            byte |= row[j]<<(7-k++);
+            if (k==8 || j == cellauto->w-1) {
+                k = 0;
+                *p++ = byte;
+                byte = 0;
+            }
+        }
+        row_idx = (row_idx + 1) % cellauto->h;
+        p0 += picref->linesize[0];
+    }
+}
+
+static int request_frame(AVFilterLink *outlink)
+{
+    CellAutoContext *cellauto = outlink->src->priv;
+    AVFilterBufferRef *picref =
+        avfilter_get_video_buffer(outlink, AV_PERM_WRITE, cellauto->w, cellauto->h);
+    picref->video->sample_aspect_ratio = (AVRational) {1, 1};
+    if (cellauto->generation == 0 && cellauto->start_full) {
+        int i;
+        for (i = 0; i < cellauto->h-1; i++)
+            evolve(outlink->src);
+    }
+    fill_picture(outlink->src, picref);
+    evolve(outlink->src);
+
+    picref->pts = cellauto->pts++;
+    picref->pos = -1;
+
+#ifdef DEBUG
+    show_cellauto_row(outlink->src);
+#endif
+
+    avfilter_start_frame(outlink, avfilter_ref_buffer(picref, ~0));
+    avfilter_draw_slice(outlink, 0, cellauto->h, 1);
+    avfilter_end_frame(outlink);
+    avfilter_unref_buffer(picref);
+
+    return 0;
+}
+
+static int query_formats(AVFilterContext *ctx)
+{
+    static const enum PixelFormat pix_fmts[] = { PIX_FMT_MONOBLACK, PIX_FMT_NONE };
+    avfilter_set_common_pixel_formats(ctx, avfilter_make_format_list(pix_fmts));
+    return 0;
+}
+
+AVFilter avfilter_vsrc_cellauto = {
+    .name        = "cellauto",
+    .description = NULL_IF_CONFIG_SMALL("Create pattern generated by an elementary cellular automaton."),
+    .priv_size = sizeof(CellAutoContext),
+    .init      = init,
+    .uninit    = uninit,
+    .query_formats = query_formats,
+
+    .inputs    = (const AVFilterPad[]) {
+        { .name = NULL}
+    },
+    .outputs   = (const AVFilterPad[]) {
+        { .name            = "default",
+          .type            = AVMEDIA_TYPE_VIDEO,
+          .request_frame   = request_frame,
+          .config_props    = config_props },
+        { .name = NULL}
+    },
+};