1/*
2 * Copyright (c) Stefano Sabatini 2011
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 * cellular automaton video source, based on Stephen Wolfram "experimentus crucis"
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 "libavutil/avstring.h"
34#include "avfilter.h"
35#include "internal.h"
36#include "formats.h"
37#include "video.h"
38
39typedef struct {
40    const AVClass *class;
41    int w, h;
42    char *filename;
43    char *rule_str;
44    uint8_t *file_buf;
45    size_t file_bufsize;
46    uint8_t *buf;
47    int buf_prev_row_idx, buf_row_idx;
48    uint8_t rule;
49    uint64_t pts;
50    AVRational frame_rate;
51    double   random_fill_ratio;
52    uint32_t random_seed;
53    int stitch, scroll, start_full;
54    int64_t generation;         ///< the generation number, starting from 0
55    AVLFG lfg;
56    char *pattern;
57} CellAutoContext;
58
59#define OFFSET(x) offsetof(CellAutoContext, x)
60#define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM
61
62static const AVOption cellauto_options[] = {
63    { "filename", "read initial pattern from file", OFFSET(filename), AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0, FLAGS },
64    { "f",        "read initial pattern from file", OFFSET(filename), AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0, FLAGS },
65    { "pattern",  "set initial pattern", OFFSET(pattern), AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0, FLAGS },
66    { "p",        "set initial pattern", OFFSET(pattern), AV_OPT_TYPE_STRING, {.str = NULL}, 0, 0, FLAGS },
67    { "rate",     "set video rate", OFFSET(frame_rate), AV_OPT_TYPE_VIDEO_RATE, {.str = "25"}, 0, 0, FLAGS },
68    { "r",        "set video rate", OFFSET(frame_rate), AV_OPT_TYPE_VIDEO_RATE, {.str = "25"}, 0, 0, FLAGS },
69    { "size",     "set video size", OFFSET(w),    AV_OPT_TYPE_IMAGE_SIZE, {.str = NULL}, 0, 0, FLAGS },
70    { "s",        "set video size", OFFSET(w),    AV_OPT_TYPE_IMAGE_SIZE, {.str = NULL}, 0, 0, FLAGS },
71    { "rule",     "set rule",       OFFSET(rule), AV_OPT_TYPE_INT,    {.i64 = 110},  0, 255, FLAGS },
72    { "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, FLAGS },
73    { "ratio",             "set fill ratio for filling initial grid randomly", OFFSET(random_fill_ratio), AV_OPT_TYPE_DOUBLE, {.dbl = 1/M_PHI}, 0, 1, FLAGS },
74    { "random_seed", "set the seed for filling the initial grid randomly", OFFSET(random_seed), AV_OPT_TYPE_INT, {.i64 = -1}, -1, UINT32_MAX, FLAGS },
75    { "seed",        "set the seed for filling the initial grid randomly", OFFSET(random_seed), AV_OPT_TYPE_INT, {.i64 = -1}, -1, UINT32_MAX, FLAGS },
76    { "scroll",      "scroll pattern downward", OFFSET(scroll), AV_OPT_TYPE_INT, {.i64 = 1}, 0, 1, FLAGS },
77    { "start_full",  "start filling the whole video", OFFSET(start_full), AV_OPT_TYPE_INT, {.i64 = 0}, 0, 1, FLAGS },
78    { "full",        "start filling the whole video", OFFSET(start_full), AV_OPT_TYPE_INT, {.i64 = 1}, 0, 1, FLAGS },
79    { "stitch",      "stitch boundaries", OFFSET(stitch), AV_OPT_TYPE_INT,    {.i64 = 1},   0, 1, FLAGS },
80    { NULL }
81};
82
83AVFILTER_DEFINE_CLASS(cellauto);
84
85#ifdef DEBUG
86static void show_cellauto_row(AVFilterContext *ctx)
87{
88    CellAutoContext *cellauto = ctx->priv;
89    int i;
90    uint8_t *row = cellauto->buf + cellauto->w * cellauto->buf_row_idx;
91    char *line = av_malloc(cellauto->w + 1);
92    if (!line)
93        return;
94
95    for (i = 0; i < cellauto->w; i++)
96        line[i] = row[i] ? '@' : ' ';
97    line[i] = 0;
98    av_log(ctx, AV_LOG_DEBUG, "generation:%"PRId64" row:%s|\n", cellauto->generation, line);
99    av_free(line);
100}
101#endif
102
103static int init_pattern_from_string(AVFilterContext *ctx)
104{
105    CellAutoContext *cellauto = ctx->priv;
106    char *p;
107    int i, w = 0;
108
109    w = strlen(cellauto->pattern);
110    av_log(ctx, AV_LOG_DEBUG, "w:%d\n", w);
111
112    if (cellauto->w) {
113        if (w > cellauto->w) {
114            av_log(ctx, AV_LOG_ERROR,
115                   "The specified width is %d which cannot contain the provided string width of %d\n",
116                   cellauto->w, w);
117            return AVERROR(EINVAL);
118        }
119    } else {
120        /* width was not specified, set it to width of the provided row */
121        cellauto->w = w;
122        cellauto->h = (double)cellauto->w * M_PHI;
123    }
124
125    cellauto->buf = av_mallocz_array(sizeof(uint8_t) * cellauto->w, cellauto->h);
126    if (!cellauto->buf)
127        return AVERROR(ENOMEM);
128
129    /* fill buf */
130    p = cellauto->pattern;
131    for (i = (cellauto->w - w)/2;; i++) {
132        av_log(ctx, AV_LOG_DEBUG, "%d %c\n", i, *p == '\n' ? 'N' : *p);
133        if (*p == '\n' || !*p)
134            break;
135        else
136            cellauto->buf[i] = !!av_isgraph(*(p++));
137    }
138
139    return 0;
140}
141
142static int init_pattern_from_file(AVFilterContext *ctx)
143{
144    CellAutoContext *cellauto = ctx->priv;
145    int ret;
146
147    ret = av_file_map(cellauto->filename,
148                      &cellauto->file_buf, &cellauto->file_bufsize, 0, ctx);
149    if (ret < 0)
150        return ret;
151
152    /* create a string based on the read file */
153    cellauto->pattern = av_malloc(cellauto->file_bufsize + 1);
154    if (!cellauto->pattern)
155        return AVERROR(ENOMEM);
156    memcpy(cellauto->pattern, cellauto->file_buf, cellauto->file_bufsize);
157    cellauto->pattern[cellauto->file_bufsize] = 0;
158
159    return init_pattern_from_string(ctx);
160}
161
162static av_cold int init(AVFilterContext *ctx)
163{
164    CellAutoContext *cellauto = ctx->priv;
165    int ret;
166
167    if (!cellauto->w && !cellauto->filename && !cellauto->pattern)
168        av_opt_set(cellauto, "size", "320x518", 0);
169
170    if (cellauto->filename && cellauto->pattern) {
171        av_log(ctx, AV_LOG_ERROR, "Only one of the filename or pattern options can be used\n");
172        return AVERROR(EINVAL);
173    }
174
175    if (cellauto->filename) {
176        if ((ret = init_pattern_from_file(ctx)) < 0)
177            return ret;
178    } else if (cellauto->pattern) {
179        if ((ret = init_pattern_from_string(ctx)) < 0)
180            return ret;
181    } else {
182        /* fill the first row randomly */
183        int i;
184
185        cellauto->buf = av_mallocz_array(sizeof(uint8_t) * cellauto->w, cellauto->h);
186        if (!cellauto->buf)
187            return AVERROR(ENOMEM);
188        if (cellauto->random_seed == -1)
189            cellauto->random_seed = av_get_random_seed();
190
191        av_lfg_init(&cellauto->lfg, cellauto->random_seed);
192
193        for (i = 0; i < cellauto->w; i++) {
194            double r = (double)av_lfg_get(&cellauto->lfg) / UINT32_MAX;
195            if (r <= cellauto->random_fill_ratio)
196                cellauto->buf[i] = 1;
197        }
198    }
199
200    av_log(ctx, AV_LOG_VERBOSE,
201           "s:%dx%d r:%d/%d rule:%d stitch:%d scroll:%d full:%d seed:%u\n",
202           cellauto->w, cellauto->h, cellauto->frame_rate.num, cellauto->frame_rate.den,
203           cellauto->rule, cellauto->stitch, cellauto->scroll, cellauto->start_full,
204           cellauto->random_seed);
205    return 0;
206}
207
208static av_cold void uninit(AVFilterContext *ctx)
209{
210    CellAutoContext *cellauto = ctx->priv;
211
212    av_file_unmap(cellauto->file_buf, cellauto->file_bufsize);
213    av_freep(&cellauto->buf);
214    av_freep(&cellauto->pattern);
215}
216
217static int config_props(AVFilterLink *outlink)
218{
219    CellAutoContext *cellauto = outlink->src->priv;
220
221    outlink->w = cellauto->w;
222    outlink->h = cellauto->h;
223    outlink->time_base = av_inv_q(cellauto->frame_rate);
224
225    return 0;
226}
227
228static void evolve(AVFilterContext *ctx)
229{
230    CellAutoContext *cellauto = ctx->priv;
231    int i, v, pos[3];
232    uint8_t *row, *prev_row = cellauto->buf + cellauto->buf_row_idx * cellauto->w;
233    enum { NW, N, NE };
234
235    cellauto->buf_prev_row_idx = cellauto->buf_row_idx;
236    cellauto->buf_row_idx      = cellauto->buf_row_idx == cellauto->h-1 ? 0 : cellauto->buf_row_idx+1;
237    row = cellauto->buf + cellauto->w * cellauto->buf_row_idx;
238
239    for (i = 0; i < cellauto->w; i++) {
240        if (cellauto->stitch) {
241            pos[NW] = i-1 < 0 ? cellauto->w-1 : i-1;
242            pos[N]  = i;
243            pos[NE] = i+1 == cellauto->w ? 0  : i+1;
244            v = prev_row[pos[NW]]<<2 | prev_row[pos[N]]<<1 | prev_row[pos[NE]];
245        } else {
246            v = 0;
247            v|= i-1 >= 0          ? prev_row[i-1]<<2 : 0;
248            v|=                     prev_row[i  ]<<1    ;
249            v|= i+1 < cellauto->w ? prev_row[i+1]    : 0;
250        }
251        row[i] = !!(cellauto->rule & (1<<v));
252        av_dlog(ctx, "i:%d context:%c%c%c -> cell:%d\n", i,
253                v&4?'@':' ', v&2?'@':' ', v&1?'@':' ', row[i]);
254    }
255
256    cellauto->generation++;
257}
258
259static void fill_picture(AVFilterContext *ctx, AVFrame *picref)
260{
261    CellAutoContext *cellauto = ctx->priv;
262    int i, j, k, row_idx = 0;
263    uint8_t *p0 = picref->data[0];
264
265    if (cellauto->scroll && cellauto->generation >= cellauto->h)
266        /* show on top the oldest row */
267        row_idx = (cellauto->buf_row_idx + 1) % cellauto->h;
268
269    /* fill the output picture with the whole buffer */
270    for (i = 0; i < cellauto->h; i++) {
271        uint8_t byte = 0;
272        uint8_t *row = cellauto->buf + row_idx*cellauto->w;
273        uint8_t *p = p0;
274        for (k = 0, j = 0; j < cellauto->w; j++) {
275            byte |= row[j]<<(7-k++);
276            if (k==8 || j == cellauto->w-1) {
277                k = 0;
278                *p++ = byte;
279                byte = 0;
280            }
281        }
282        row_idx = (row_idx + 1) % cellauto->h;
283        p0 += picref->linesize[0];
284    }
285}
286
287static int request_frame(AVFilterLink *outlink)
288{
289    CellAutoContext *cellauto = outlink->src->priv;
290    AVFrame *picref = ff_get_video_buffer(outlink, cellauto->w, cellauto->h);
291    if (!picref)
292        return AVERROR(ENOMEM);
293    picref->sample_aspect_ratio = (AVRational) {1, 1};
294    if (cellauto->generation == 0 && cellauto->start_full) {
295        int i;
296        for (i = 0; i < cellauto->h-1; i++)
297            evolve(outlink->src);
298    }
299    fill_picture(outlink->src, picref);
300    evolve(outlink->src);
301
302    picref->pts = cellauto->pts++;
303
304#ifdef DEBUG
305    show_cellauto_row(outlink->src);
306#endif
307    return ff_filter_frame(outlink, picref);
308}
309
310static int query_formats(AVFilterContext *ctx)
311{
312    static const enum AVPixelFormat pix_fmts[] = { AV_PIX_FMT_MONOBLACK, AV_PIX_FMT_NONE };
313    ff_set_common_formats(ctx, ff_make_format_list(pix_fmts));
314    return 0;
315}
316
317static const AVFilterPad cellauto_outputs[] = {
318    {
319        .name          = "default",
320        .type          = AVMEDIA_TYPE_VIDEO,
321        .request_frame = request_frame,
322        .config_props  = config_props,
323    },
324    { NULL }
325};
326
327AVFilter ff_vsrc_cellauto = {
328    .name          = "cellauto",
329    .description   = NULL_IF_CONFIG_SMALL("Create pattern generated by an elementary cellular automaton."),
330    .priv_size     = sizeof(CellAutoContext),
331    .priv_class    = &cellauto_class,
332    .init          = init,
333    .uninit        = uninit,
334    .query_formats = query_formats,
335    .inputs        = NULL,
336    .outputs       = cellauto_outputs,
337};
338