2 * Copyright (c) Stefano Sabatini 2010
4 * This file is part of FFmpeg.
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.
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.
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
23 * life video source, based on John Conways' Life Game
28 #include "libavutil/file.h"
29 #include "libavutil/intreadwrite.h"
30 #include "libavutil/lfg.h"
31 #include "libavutil/opt.h"
32 #include "libavutil/parseutils.h"
33 #include "libavutil/random_seed.h"
34 #include "libavutil/avstring.h"
49 * The two grid state buffers.
51 * A 0xFF (ALIVE_CELL) value means the cell is alive (or new born), while
52 * the decreasing values from 0xFE to 0 means the cell is dead; the range
53 * of values is used for the slow death effect, or mold (0xFE means dead,
54 * 0xFD means very dead, 0xFC means very very dead... and 0x00 means
55 * definitely dead/mold).
60 uint16_t stay_rule
; ///< encode the behavior for filled cells
61 uint16_t born_rule
; ///< encode the behavior for empty cells
63 AVRational frame_rate
;
64 double random_fill_ratio
;
68 uint8_t life_color
[4];
69 uint8_t death_color
[4];
70 uint8_t mold_color
[4];
72 void (*draw
)(AVFilterContext
*, AVFrame
*);
75 #define ALIVE_CELL 0xFF
76 #define OFFSET(x) offsetof(LifeContext, x)
77 #define FLAGS AV_OPT_FLAG_VIDEO_PARAM|AV_OPT_FLAG_FILTERING_PARAM
79 static const AVOption life_options
[] = {
80 { "filename", "set source file", OFFSET(filename
), AV_OPT_TYPE_STRING
, {.str
= NULL
}, 0, 0, FLAGS
},
81 { "f", "set source file", OFFSET(filename
), AV_OPT_TYPE_STRING
, {.str
= NULL
}, 0, 0, FLAGS
},
82 { "size", "set video size", OFFSET(w
), AV_OPT_TYPE_IMAGE_SIZE
, {.str
= NULL
}, 0, 0, FLAGS
},
83 { "s", "set video size", OFFSET(w
), AV_OPT_TYPE_IMAGE_SIZE
, {.str
= NULL
}, 0, 0, FLAGS
},
84 { "rate", "set video rate", OFFSET(frame_rate
), AV_OPT_TYPE_VIDEO_RATE
, {.str
= "25"}, 0, 0, FLAGS
},
85 { "r", "set video rate", OFFSET(frame_rate
), AV_OPT_TYPE_VIDEO_RATE
, {.str
= "25"}, 0, 0, FLAGS
},
86 { "rule", "set rule", OFFSET(rule_str
), AV_OPT_TYPE_STRING
, {.str
= "B3/S23"}, CHAR_MIN
, CHAR_MAX
, FLAGS
},
87 { "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
},
88 { "ratio", "set fill ratio for filling initial grid randomly", OFFSET(random_fill_ratio
), AV_OPT_TYPE_DOUBLE
, {.dbl
=1/M_PHI
}, 0, 1, FLAGS
},
89 { "random_seed", "set the seed for filling the initial grid randomly", OFFSET(random_seed
), AV_OPT_TYPE_INT
, {.i64
=-1}, -1, UINT32_MAX
, FLAGS
},
90 { "seed", "set the seed for filling the initial grid randomly", OFFSET(random_seed
), AV_OPT_TYPE_INT
, {.i64
=-1}, -1, UINT32_MAX
, FLAGS
},
91 { "stitch", "stitch boundaries", OFFSET(stitch
), AV_OPT_TYPE_INT
, {.i64
=1}, 0, 1, FLAGS
},
92 { "mold", "set mold speed for dead cells", OFFSET(mold
), AV_OPT_TYPE_INT
, {.i64
=0}, 0, 0xFF, FLAGS
},
93 { "life_color", "set life color", OFFSET( life_color
), AV_OPT_TYPE_COLOR
, {.str
="white"}, CHAR_MIN
, CHAR_MAX
, FLAGS
},
94 { "death_color", "set death color", OFFSET(death_color
), AV_OPT_TYPE_COLOR
, {.str
="black"}, CHAR_MIN
, CHAR_MAX
, FLAGS
},
95 { "mold_color", "set mold color", OFFSET( mold_color
), AV_OPT_TYPE_COLOR
, {.str
="black"}, CHAR_MIN
, CHAR_MAX
, FLAGS
},
99 AVFILTER_DEFINE_CLASS(life
);
101 static int parse_rule(uint16_t *born_rule
, uint16_t *stay_rule
,
102 const char *rule_str
, void *log_ctx
)
105 const char *p
= rule_str
;
109 if (strchr("bBsS", *p
)) {
110 /* parse rule as a Born / Stay Alive code, see
111 * http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life */
113 uint16_t *rule
= (*p
== 'b' || *p
== 'B') ? born_rule
: stay_rule
;
115 while (*p
>= '0' && *p
<= '8') {
116 *rule
+= 1<<(*p
- '0');
122 } while (strchr("bBsS", *p
));
127 /* parse rule as a number, expressed in the form STAY|(BORN<<9),
128 * where STAY and BORN encode the corresponding 9-bits rule */
129 long int rule
= strtol(rule_str
, &tail
, 10);
132 *born_rule
= ((1<<9)-1) & rule
;
133 *stay_rule
= rule
>> 9;
139 av_log(log_ctx
, AV_LOG_ERROR
, "Invalid rule code '%s' provided\n", rule_str
);
140 return AVERROR(EINVAL
);
144 static void show_life_grid(AVFilterContext
*ctx
)
146 LifeContext
*life
= ctx
->priv
;
149 char *line
= av_malloc(life
->w
+ 1);
152 for (i
= 0; i
< life
->h
; i
++) {
153 for (j
= 0; j
< life
->w
; j
++)
154 line
[j
] = life
->buf
[life
->buf_idx
][i
*life
->w
+ j
] == ALIVE_CELL
? '@' : ' ';
156 av_log(ctx
, AV_LOG_DEBUG
, "%3d: %s\n", i
, line
);
162 static int init_pattern_from_file(AVFilterContext
*ctx
)
164 LifeContext
*life
= ctx
->priv
;
166 int ret
, i
, i0
, j
, h
= 0, w
, max_w
= 0;
168 if ((ret
= av_file_map(life
->filename
, &life
->file_buf
, &life
->file_bufsize
,
171 av_freep(&life
->filename
);
173 /* prescan file to get the number of lines and the maximum width */
175 for (i
= 0; i
< life
->file_bufsize
; i
++) {
176 if (life
->file_buf
[i
] == '\n') {
177 h
++; max_w
= FFMAX(w
, max_w
); w
= 0;
182 av_log(ctx
, AV_LOG_DEBUG
, "h:%d max_w:%d\n", h
, max_w
);
185 if (max_w
> life
->w
|| h
> life
->h
) {
186 av_log(ctx
, AV_LOG_ERROR
,
187 "The specified size is %dx%d which cannot contain the provided file size of %dx%d\n",
188 life
->w
, life
->h
, max_w
, h
);
189 return AVERROR(EINVAL
);
192 /* size was not specified, set it to size of the grid */
197 if (!(life
->buf
[0] = av_calloc(life
->h
* life
->w
, sizeof(*life
->buf
[0]))) ||
198 !(life
->buf
[1] = av_calloc(life
->h
* life
->w
, sizeof(*life
->buf
[1])))) {
199 av_free(life
->buf
[0]);
200 av_free(life
->buf
[1]);
201 return AVERROR(ENOMEM
);
206 for (i0
= 0, i
= (life
->h
- h
)/2; i0
< h
; i0
++, i
++) {
207 for (j
= (life
->w
- max_w
)/2;; j
++) {
208 av_log(ctx
, AV_LOG_DEBUG
, "%d:%d %c\n", i
, j
, *p
== '\n' ? 'N' : *p
);
212 life
->buf
[0][i
*life
->w
+ j
] = av_isgraph(*(p
++)) ? ALIVE_CELL
: 0;
220 static av_cold
int init(AVFilterContext
*ctx
)
222 LifeContext
*life
= ctx
->priv
;
225 if (!life
->w
&& !life
->filename
)
226 av_opt_set(life
, "size", "320x240", 0);
228 if ((ret
= parse_rule(&life
->born_rule
, &life
->stay_rule
, life
->rule_str
, ctx
)) < 0)
231 if (!life
->mold
&& memcmp(life
->mold_color
, "\x00\x00\x00", 3))
232 av_log(ctx
, AV_LOG_WARNING
,
233 "Mold color is set while mold isn't, ignoring the color.\n");
235 if (!life
->filename
) {
236 /* fill the grid randomly */
239 if (!(life
->buf
[0] = av_calloc(life
->h
* life
->w
, sizeof(*life
->buf
[0]))) ||
240 !(life
->buf
[1] = av_calloc(life
->h
* life
->w
, sizeof(*life
->buf
[1])))) {
241 av_free(life
->buf
[0]);
242 av_free(life
->buf
[1]);
243 return AVERROR(ENOMEM
);
245 if (life
->random_seed
== -1)
246 life
->random_seed
= av_get_random_seed();
248 av_lfg_init(&life
->lfg
, life
->random_seed
);
250 for (i
= 0; i
< life
->w
* life
->h
; i
++) {
251 double r
= (double)av_lfg_get(&life
->lfg
) / UINT32_MAX
;
252 if (r
<= life
->random_fill_ratio
)
253 life
->buf
[0][i
] = ALIVE_CELL
;
257 if ((ret
= init_pattern_from_file(ctx
)) < 0)
261 av_log(ctx
, AV_LOG_VERBOSE
,
262 "s:%dx%d r:%d/%d rule:%s stay_rule:%d born_rule:%d stitch:%d seed:%u\n",
263 life
->w
, life
->h
, life
->frame_rate
.num
, life
->frame_rate
.den
,
264 life
->rule_str
, life
->stay_rule
, life
->born_rule
, life
->stitch
,
269 static av_cold
void uninit(AVFilterContext
*ctx
)
271 LifeContext
*life
= ctx
->priv
;
273 av_file_unmap(life
->file_buf
, life
->file_bufsize
);
274 av_freep(&life
->rule_str
);
275 av_freep(&life
->buf
[0]);
276 av_freep(&life
->buf
[1]);
279 static int config_props(AVFilterLink
*outlink
)
281 LifeContext
*life
= outlink
->src
->priv
;
283 outlink
->w
= life
->w
;
284 outlink
->h
= life
->h
;
285 outlink
->time_base
= av_inv_q(life
->frame_rate
);
290 static void evolve(AVFilterContext
*ctx
)
292 LifeContext
*life
= ctx
->priv
;
294 uint8_t *oldbuf
= life
->buf
[ life
->buf_idx
];
295 uint8_t *newbuf
= life
->buf
[!life
->buf_idx
];
297 enum { NW
, N
, NE
, W
, E
, SW
, S
, SE
};
299 /* evolve the grid */
300 for (i
= 0; i
< life
->h
; i
++) {
301 for (j
= 0; j
< life
->w
; j
++) {
302 int pos
[8][2], n
, alive
, cell
;
304 pos
[NW
][0] = (i
-1) < 0 ? life
->h
-1 : i
-1; pos
[NW
][1] = (j
-1) < 0 ? life
->w
-1 : j
-1;
305 pos
[N
][0] = (i
-1) < 0 ? life
->h
-1 : i
-1; pos
[N
][1] = j
;
306 pos
[NE
][0] = (i
-1) < 0 ? life
->h
-1 : i
-1; pos
[NE
][1] = (j
+1) == life
->w
? 0 : j
+1;
307 pos
[W
][0] = i
; pos
[W
][1] = (j
-1) < 0 ? life
->w
-1 : j
-1;
308 pos
[E
][0] = i
; pos
[E
][1] = (j
+1) == life
->w
? 0 : j
+1;
309 pos
[SW
][0] = (i
+1) == life
->h
? 0 : i
+1; pos
[SW
][1] = (j
-1) < 0 ? life
->w
-1 : j
-1;
310 pos
[S
][0] = (i
+1) == life
->h
? 0 : i
+1; pos
[S
][1] = j
;
311 pos
[SE
][0] = (i
+1) == life
->h
? 0 : i
+1; pos
[SE
][1] = (j
+1) == life
->w
? 0 : j
+1;
313 pos
[NW
][0] = (i
-1) < 0 ? -1 : i
-1; pos
[NW
][1] = (j
-1) < 0 ? -1 : j
-1;
314 pos
[N
][0] = (i
-1) < 0 ? -1 : i
-1; pos
[N
][1] = j
;
315 pos
[NE
][0] = (i
-1) < 0 ? -1 : i
-1; pos
[NE
][1] = (j
+1) == life
->w
? -1 : j
+1;
316 pos
[W
][0] = i
; pos
[W
][1] = (j
-1) < 0 ? -1 : j
-1;
317 pos
[E
][0] = i
; pos
[E
][1] = (j
+1) == life
->w
? -1 : j
+1;
318 pos
[SW
][0] = (i
+1) == life
->h
? -1 : i
+1; pos
[SW
][1] = (j
-1) < 0 ? -1 : j
-1;
319 pos
[S
][0] = (i
+1) == life
->h
? -1 : i
+1; pos
[S
][1] = j
;
320 pos
[SE
][0] = (i
+1) == life
->h
? -1 : i
+1; pos
[SE
][1] = (j
+1) == life
->w
? -1 : j
+1;
323 /* compute the number of live neighbor cells */
324 n
= (pos
[NW
][0] == -1 || pos
[NW
][1] == -1 ? 0 : oldbuf
[pos
[NW
][0]*life
->w
+ pos
[NW
][1]] == ALIVE_CELL
) +
325 (pos
[N
][0] == -1 || pos
[N
][1] == -1 ? 0 : oldbuf
[pos
[N
][0]*life
->w
+ pos
[N
][1]] == ALIVE_CELL
) +
326 (pos
[NE
][0] == -1 || pos
[NE
][1] == -1 ? 0 : oldbuf
[pos
[NE
][0]*life
->w
+ pos
[NE
][1]] == ALIVE_CELL
) +
327 (pos
[W
][0] == -1 || pos
[W
][1] == -1 ? 0 : oldbuf
[pos
[W
][0]*life
->w
+ pos
[W
][1]] == ALIVE_CELL
) +
328 (pos
[E
][0] == -1 || pos
[E
][1] == -1 ? 0 : oldbuf
[pos
[E
][0]*life
->w
+ pos
[E
][1]] == ALIVE_CELL
) +
329 (pos
[SW
][0] == -1 || pos
[SW
][1] == -1 ? 0 : oldbuf
[pos
[SW
][0]*life
->w
+ pos
[SW
][1]] == ALIVE_CELL
) +
330 (pos
[S
][0] == -1 || pos
[S
][1] == -1 ? 0 : oldbuf
[pos
[S
][0]*life
->w
+ pos
[S
][1]] == ALIVE_CELL
) +
331 (pos
[SE
][0] == -1 || pos
[SE
][1] == -1 ? 0 : oldbuf
[pos
[SE
][0]*life
->w
+ pos
[SE
][1]] == ALIVE_CELL
);
332 cell
= oldbuf
[i
*life
->w
+ j
];
333 alive
= 1<<n
& (cell
== ALIVE_CELL
? life
->stay_rule
: life
->born_rule
);
334 if (alive
) *newbuf
= ALIVE_CELL
; // new cell is alive
335 else if (cell
) *newbuf
= cell
- 1; // new cell is dead and in the process of mold
336 else *newbuf
= 0; // new cell is definitely dead
337 av_dlog(ctx
, "i:%d j:%d live_neighbors:%d cell:%d -> cell:%d\n", i
, j
, n
, cell
, *newbuf
);
342 life
->buf_idx
= !life
->buf_idx
;
345 static void fill_picture_monoblack(AVFilterContext
*ctx
, AVFrame
*picref
)
347 LifeContext
*life
= ctx
->priv
;
348 uint8_t *buf
= life
->buf
[life
->buf_idx
];
351 /* fill the output picture with the old grid buffer */
352 for (i
= 0; i
< life
->h
; i
++) {
354 uint8_t *p
= picref
->data
[0] + i
* picref
->linesize
[0];
355 for (k
= 0, j
= 0; j
< life
->w
; j
++) {
356 byte
|= (buf
[i
*life
->w
+j
] == ALIVE_CELL
)<<(7-k
++);
357 if (k
==8 || j
== life
->w
-1) {
366 // divide by 255 and round to nearest
367 // apply a fast variant: (X+127)/255 = ((X+127)*257+257)>>16 = ((X+128)*257)>>16
368 #define FAST_DIV255(x) ((((x) + 128) * 257) >> 16)
370 static void fill_picture_rgb(AVFilterContext
*ctx
, AVFrame
*picref
)
372 LifeContext
*life
= ctx
->priv
;
373 uint8_t *buf
= life
->buf
[life
->buf_idx
];
376 /* fill the output picture with the old grid buffer */
377 for (i
= 0; i
< life
->h
; i
++) {
378 uint8_t *p
= picref
->data
[0] + i
* picref
->linesize
[0];
379 for (j
= 0; j
< life
->w
; j
++) {
380 uint8_t v
= buf
[i
*life
->w
+ j
];
381 if (life
->mold
&& v
!= ALIVE_CELL
) {
382 const uint8_t *c1
= life
-> mold_color
;
383 const uint8_t *c2
= life
->death_color
;
384 int death_age
= FFMIN((0xff - v
) * life
->mold
, 0xff);
385 *p
++ = FAST_DIV255((c2
[0] << 8) + ((int)c1
[0] - (int)c2
[0]) * death_age
);
386 *p
++ = FAST_DIV255((c2
[1] << 8) + ((int)c1
[1] - (int)c2
[1]) * death_age
);
387 *p
++ = FAST_DIV255((c2
[2] << 8) + ((int)c1
[2] - (int)c2
[2]) * death_age
);
389 const uint8_t *c
= v
== ALIVE_CELL
? life
->life_color
: life
->death_color
;
390 AV_WB24(p
, c
[0]<<16 | c
[1]<<8 | c
[2]);
397 static int request_frame(AVFilterLink
*outlink
)
399 LifeContext
*life
= outlink
->src
->priv
;
400 AVFrame
*picref
= ff_get_video_buffer(outlink
, life
->w
, life
->h
);
402 return AVERROR(ENOMEM
);
403 picref
->sample_aspect_ratio
= (AVRational
) {1, 1};
404 picref
->pts
= life
->pts
++;
406 life
->draw(outlink
->src
, picref
);
407 evolve(outlink
->src
);
409 show_life_grid(outlink
->src
);
411 return ff_filter_frame(outlink
, picref
);
414 static int query_formats(AVFilterContext
*ctx
)
416 LifeContext
*life
= ctx
->priv
;
417 enum AVPixelFormat pix_fmts
[] = { AV_PIX_FMT_NONE
, AV_PIX_FMT_NONE
};
418 if (life
->mold
|| memcmp(life
-> life_color
, "\xff\xff\xff", 3)
419 || memcmp(life
->death_color
, "\x00\x00\x00", 3)) {
420 pix_fmts
[0] = AV_PIX_FMT_RGB24
;
421 life
->draw
= fill_picture_rgb
;
423 pix_fmts
[0] = AV_PIX_FMT_MONOBLACK
;
424 life
->draw
= fill_picture_monoblack
;
426 ff_set_common_formats(ctx
, ff_make_format_list(pix_fmts
));
430 static const AVFilterPad life_outputs
[] = {
433 .type
= AVMEDIA_TYPE_VIDEO
,
434 .request_frame
= request_frame
,
435 .config_props
= config_props
,
440 AVFilter ff_vsrc_life
= {
442 .description
= NULL_IF_CONFIG_SMALL("Create life."),
443 .priv_size
= sizeof(LifeContext
),
444 .priv_class
= &life_class
,
447 .query_formats
= query_formats
,
449 .outputs
= life_outputs
,