FFmpeg coverage

Line	Branch	Exec	Source
1			/*
2			* Copyright (c) 2016 ReneBrals
3			* Copyright (c) 2021 Paul B Mahol
4			*
5			* This file is part of FFmpeg.
6			*
7			* Permission is hereby granted, free of charge, to any person obtaining a copy
8			* of this software and associated documentation files (the "Software"), to deal
9			* in the Software without restriction, including without limitation the rights
10			* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11			* copies of the Software, and to permit persons to whom the Software is
12			* furnished to do so, subject to the following conditions:
13			*
14			* The above copyright notice and this permission notice shall be included in all
15			* copies or substantial portions of the Software.
16			*
17			* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18			* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19			* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20			* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21			* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22			* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23			* SOFTWARE.
24			*/
25
26			#include "libavutil/avassert.h"
27			#include "libavutil/imgutils.h"
28			#include "libavutil/intreadwrite.h"
29			#include "libavutil/mem.h"
30			#include "libavutil/opt.h"
31			#include "libavutil/pixdesc.h"
32			#include "avfilter.h"
33			#include "filters.h"
34			#include "framesync.h"
35			#include "video.h"
36
37			enum MorphModes {
38			ERODE,
39			DILATE,
40			OPEN,
41			CLOSE,
42			GRADIENT,
43			TOPHAT,
44			BLACKHAT,
45			NB_MODES
46			};
47
48			typedef struct IPlane {
49			uint8_t **img;
50			int w, h;
51			int range;
52			int depth;
53			int type_size;
54
55			void (*max_out_place)(uint8_t *c, const uint8_t *a, const uint8_t *b, int x);
56			void (*min_out_place)(uint8_t *c, const uint8_t *a, const uint8_t *b, int x);
57			void (*diff_rin_place)(uint8_t *a, const uint8_t *b, int x);
58			void (*max_in_place)(uint8_t *a, const uint8_t *b, int x);
59			void (*min_in_place)(uint8_t *a, const uint8_t *b, int x);
60			void (*diff_in_place)(uint8_t *a, const uint8_t *b, int x);
61			} IPlane;
62
63			typedef struct LUT {
64			/* arr is shifted from base_arr by FFMAX(min_r, 0).
65			* arr != NULL means "lut completely allocated" */
66			uint8_t ***arr;
67			uint8_t ***base_arr;
68			int min_r;
69			int max_r;
70			int I;
71			int X;
72			int pre_pad_x;
73			int type_size;
74			} LUT;
75
76			typedef struct chord {
77			int x;
78			int y;
79			int l;
80			int i;
81			} chord;
82
83			typedef struct chord_set {
84			chord *C;
85			int size;
86			int cap;
87
88			int *R;
89			int Lnum;
90
91			int minX;
92			int maxX;
93			int minY;
94			int maxY;
95			unsigned nb_elements;
96			} chord_set;
97
98			#define MAX_THREADS 64
99
100			typedef struct MorphoContext {
101			const AVClass *class;
102			FFFrameSync fs;
103
104			chord_set SE[4];
105			IPlane SEimg[4];
106			IPlane g[4], f[4], h[4];
107			LUT Ty[MAX_THREADS][2][4];
108
109			int mode;
110			int planes;
111			int structures;
112
113			int planewidth[4];
114			int planeheight[4];
115			int splanewidth[4];
116			int splaneheight[4];
117			int depth;
118			int type_size;
119			int nb_planes;
120
121			int got_structure[4];
122
123			AVFrame *temp;
124
125			int64_t *plane_f, *plane_g;
126			} MorphoContext;
127
128			#define OFFSET(x) offsetof(MorphoContext, x)
129			#define FLAGS AV_OPT_FLAG_VIDEO_PARAM | AV_OPT_FLAG_FILTERING_PARAM | AV_OPT_FLAG_RUNTIME_PARAM
130
131			static const AVOption morpho_options[] = {
132			{ "mode", "set morphological transform", OFFSET(mode), AV_OPT_TYPE_INT, {.i64=0}, 0, NB_MODES-1, FLAGS, .unit = "mode" },
133			{ "erode", NULL, 0, AV_OPT_TYPE_CONST, {.i64=ERODE}, 0, 0, FLAGS, .unit = "mode" },
134			{ "dilate", NULL, 0, AV_OPT_TYPE_CONST, {.i64=DILATE}, 0, 0, FLAGS, .unit = "mode" },
135			{ "open", NULL, 0, AV_OPT_TYPE_CONST, {.i64=OPEN}, 0, 0, FLAGS, .unit = "mode" },
136			{ "close", NULL, 0, AV_OPT_TYPE_CONST, {.i64=CLOSE}, 0, 0, FLAGS, .unit = "mode" },
137			{ "gradient",NULL, 0, AV_OPT_TYPE_CONST, {.i64=GRADIENT},0, 0, FLAGS, .unit = "mode" },
138			{ "tophat",NULL, 0, AV_OPT_TYPE_CONST, {.i64=TOPHAT}, 0, 0, FLAGS, .unit = "mode" },
139			{ "blackhat",NULL, 0, AV_OPT_TYPE_CONST, {.i64=BLACKHAT},0, 0, FLAGS, .unit = "mode" },
140			{ "planes", "set planes to filter", OFFSET(planes), AV_OPT_TYPE_INT, {.i64=7}, 0, 15, FLAGS },
141			{ "structure", "when to process structures", OFFSET(structures), AV_OPT_TYPE_INT, {.i64=1}, 0, 1, FLAGS, .unit = "str" },
142			{ "first", "process only first structure, ignore rest", 0, AV_OPT_TYPE_CONST, {.i64=0}, 0, 0, FLAGS, .unit = "str" },
143			{ "all", "process all structure", 0, AV_OPT_TYPE_CONST, {.i64=1}, 0, 0, FLAGS, .unit = "str" },
144			{ NULL }
145			};
146
147		✗	FRAMESYNC_DEFINE_CLASS(morpho, MorphoContext, fs);
148
149			static const enum AVPixelFormat pix_fmts[] = {
150			AV_PIX_FMT_YUVA444P, AV_PIX_FMT_YUV444P, AV_PIX_FMT_YUV440P,
151			AV_PIX_FMT_YUVJ444P, AV_PIX_FMT_YUVJ440P,
152			AV_PIX_FMT_YUVA422P, AV_PIX_FMT_YUV422P, AV_PIX_FMT_YUVA420P, AV_PIX_FMT_YUV420P,
153			AV_PIX_FMT_YUVJ422P, AV_PIX_FMT_YUVJ420P,
154			AV_PIX_FMT_YUVJ411P, AV_PIX_FMT_YUV411P, AV_PIX_FMT_YUV410P,
155			AV_PIX_FMT_GBRP, AV_PIX_FMT_GBRAP, AV_PIX_FMT_GRAY8, AV_PIX_FMT_GRAY9,
156			AV_PIX_FMT_YUV420P9, AV_PIX_FMT_YUV422P9, AV_PIX_FMT_YUV444P9, AV_PIX_FMT_GBRP9,
157			AV_PIX_FMT_YUVA420P9, AV_PIX_FMT_YUVA422P9, AV_PIX_FMT_YUVA444P9,
158			AV_PIX_FMT_YUV420P10, AV_PIX_FMT_YUV422P10, AV_PIX_FMT_YUV444P10,
159			AV_PIX_FMT_YUV420P12, AV_PIX_FMT_YUV422P12, AV_PIX_FMT_YUV444P12, AV_PIX_FMT_YUV440P12,
160			AV_PIX_FMT_YUV420P14, AV_PIX_FMT_YUV422P14, AV_PIX_FMT_YUV444P14,
161			AV_PIX_FMT_YUV420P16, AV_PIX_FMT_YUV422P16, AV_PIX_FMT_YUV444P16,
162			AV_PIX_FMT_YUVA420P10, AV_PIX_FMT_YUVA422P10, AV_PIX_FMT_YUVA444P10,
163			AV_PIX_FMT_YUVA422P12, AV_PIX_FMT_YUVA444P12,
164			AV_PIX_FMT_YUVA420P16, AV_PIX_FMT_YUVA422P16, AV_PIX_FMT_YUVA444P16,
165			AV_PIX_FMT_GBRP10, AV_PIX_FMT_GBRP12, AV_PIX_FMT_GBRP14, AV_PIX_FMT_GBRP16,
166			AV_PIX_FMT_GBRAP10, AV_PIX_FMT_GBRAP12, AV_PIX_FMT_GBRAP16,
167			AV_PIX_FMT_GRAY10, AV_PIX_FMT_GRAY12, AV_PIX_FMT_GRAY14, AV_PIX_FMT_GRAY16,
168			AV_PIX_FMT_NONE
169			};
170
171		✗	static void min_fun(uint8_t *c, const uint8_t *a, const uint8_t *b, int x)
172			{
173		✗	for (int i = 0; i < x; i++)
174		✗	c[i] = FFMIN(b[i], a[i]);
175		✗	}
176
177		✗	static void mininplace_fun(uint8_t *a, const uint8_t *b, int x)
178			{
179		✗	for (int i = 0; i < x; i++)
180		✗	a[i] = FFMIN(a[i], b[i]);
181		✗	}
182
183		✗	static void max_fun(uint8_t *c, const uint8_t *a, const uint8_t *b, int x)
184			{
185		✗	for (int i = 0; i < x; i++)
186		✗	c[i] = FFMAX(a[i], b[i]);
187		✗	}
188
189		✗	static void maxinplace_fun(uint8_t *a, const uint8_t *b, int x)
190			{
191		✗	for (int i = 0; i < x; i++)
192		✗	a[i] = FFMAX(a[i], b[i]);
193		✗	}
194
195		✗	static void diff_fun(uint8_t *a, const uint8_t *b, int x)
196			{
197		✗	for (int i = 0; i < x; i++)
198		✗	a[i] = FFMAX(b[i] - a[i], 0);
199		✗	}
200
201		✗	static void diffinplace_fun(uint8_t *a, const uint8_t *b, int x)
202			{
203		✗	for (int i = 0; i < x; i++)
204		✗	a[i] = FFMAX(a[i] - b[i], 0);
205		✗	}
206
207		✗	static void min16_fun(uint8_t *cc, const uint8_t *aa, const uint8_t *bb, int x)
208			{
209		✗	const uint16_t *a = (const uint16_t *)aa;
210		✗	const uint16_t *b = (const uint16_t *)bb;
211		✗	uint16_t *c = (uint16_t *)cc;
212
213		✗	for (int i = 0; i < x; i++)
214		✗	c[i] = FFMIN(b[i], a[i]);
215		✗	}
216
217		✗	static void mininplace16_fun(uint8_t *aa, const uint8_t *bb, int x)
218			{
219		✗	uint16_t *a = (uint16_t *)aa;
220		✗	const uint16_t *b = (const uint16_t *)bb;
221
222		✗	for (int i = 0; i < x; i++)
223		✗	a[i] = FFMIN(a[i], b[i]);
224		✗	}
225
226		✗	static void diff16_fun(uint8_t *aa, const uint8_t *bb, int x)
227			{
228		✗	const uint16_t *b = (const uint16_t *)bb;
229		✗	uint16_t *a = (uint16_t *)aa;
230
231		✗	for (int i = 0; i < x; i++)
232		✗	a[i] = FFMAX(b[i] - a[i], 0);
233		✗	}
234
235		✗	static void diffinplace16_fun(uint8_t *aa, const uint8_t *bb, int x)
236			{
237		✗	uint16_t *a = (uint16_t *)aa;
238		✗	const uint16_t *b = (const uint16_t *)bb;
239
240		✗	for (int i = 0; i < x; i++)
241		✗	a[i] = FFMAX(a[i] - b[i], 0);
242		✗	}
243
244		✗	static void max16_fun(uint8_t *cc, const uint8_t *aa, const uint8_t *bb, int x)
245			{
246		✗	const uint16_t *a = (const uint16_t *)aa;
247		✗	const uint16_t *b = (const uint16_t *)bb;
248		✗	uint16_t *c = (uint16_t *)cc;
249
250		✗	for (int i = 0; i < x; i++)
251		✗	c[i] = FFMAX(a[i], b[i]);
252		✗	}
253
254		✗	static void maxinplace16_fun(uint8_t *aa, const uint8_t *bb, int x)
255			{
256		✗	uint16_t *a = (uint16_t *)aa;
257		✗	const uint16_t *b = (const uint16_t *)bb;
258
259		✗	for (int i = 0; i < x; i++)
260		✗	a[i] = FFMAX(a[i], b[i]);
261		✗	}
262
263		✗	static int alloc_lut(LUT *Ty, chord_set *SE, int type_size, int mode)
264			{
265		✗	const int min = FFMAX(Ty->min_r, 0);
266		✗	const int max = min + (Ty->max_r - Ty->min_r);
267		✗	int pre_pad_x = 0;
268
269		✗	if (SE->minX < 0)
270		✗	pre_pad_x = 0 - SE->minX;
271		✗	Ty->pre_pad_x = pre_pad_x;
272		✗	Ty->type_size = type_size;
273
274		✗	Ty->base_arr = av_calloc(max + 1, sizeof(*Ty->base_arr));
275		✗	if (!Ty->base_arr)
276		✗	return AVERROR(ENOMEM);
277		✗	for (int r = min; r <= max; r++) {
278		✗	uint8_t **arr = Ty->base_arr[r] = av_calloc(Ty->I, sizeof(uint8_t *));
279		✗	if (!Ty->base_arr[r])
280		✗	return AVERROR(ENOMEM);
281		✗	for (int i = 0; i < Ty->I; i++) {
282		✗	arr[i] = av_calloc(Ty->X + pre_pad_x, type_size);
283		✗	if (!arr[i])
284		✗	return AVERROR(ENOMEM);
285		✗	if (mode == ERODE)
286		✗	memset(arr[i], UINT8_MAX, pre_pad_x * type_size);
287			/* Shifting the X index such that negative indices correspond to
288			* the pre-padding.
289			*/
290		✗	arr[i] = &(arr[i][pre_pad_x * type_size]);
291			}
292			}
293
294		✗	Ty->arr = &(Ty->base_arr[min - Ty->min_r]);
295
296		✗	return 0;
297			}
298
299		✗	static void free_lut(LUT *table)
300			{
301		✗	const int min = FFMAX(table->min_r, 0);
302		✗	const int max = min + (table->max_r - table->min_r);
303
304		✗	if (!table->base_arr)
305		✗	return;
306
307		✗	for (int r = min; r <= max; r++) {
308		✗	if (!table->base_arr[r])
309		✗	break;
310		✗	for (int i = 0; i < table->I; i++) {
311		✗	if (!table->base_arr[r][i])
312		✗	break;
313			// The X index was also shifted, for padding purposes.
314		✗	av_free(table->base_arr[r][i] - table->pre_pad_x * table->type_size);
315			}
316		✗	av_freep(&table->base_arr[r]);
317			}
318		✗	av_freep(&table->base_arr);
319		✗	table->arr = NULL;
320			}
321
322		✗	static int alloc_lut_if_necessary(LUT *Ty, IPlane *f, chord_set *SE,
323			int num, enum MorphModes mode)
324			{
325		✗	if (!Ty->arr || Ty->I != SE->Lnum ||
326		✗	Ty->X != f->w ||
327		✗	SE->minX < 0 && -SE->minX > Ty->pre_pad_x ||
328		✗	Ty->min_r != SE->minY ||
329		✗	Ty->max_r != SE->maxY + num - 1) {
330			int ret;
331
332		✗	free_lut(Ty);
333
334		✗	Ty->I = SE->Lnum;
335		✗	Ty->X = f->w;
336		✗	Ty->min_r = SE->minY;
337		✗	Ty->max_r = SE->maxY + num - 1;
338		✗	ret = alloc_lut(Ty, SE, f->type_size, mode);
339		✗	if (ret < 0)
340		✗	return ret;
341			}
342		✗	return 0;
343			}
344
345		✗	static void circular_swap(LUT *Ty)
346			{
347			/*
348			* Swap the pointers to r-indices in a circle. This is useful because
349			* Ty(r,i,x) = Ty-1(r+1,i,x) for r < ymax.
350			*/
351		✗	if (Ty->max_r - Ty->min_r > 0) {
352		✗	uint8_t **Ty0 = Ty->arr[Ty->min_r];
353
354		✗	for (int r = Ty->min_r; r < Ty->max_r; r++)
355		✗	Ty->arr[r] = Ty->arr[r + 1];
356
357		✗	Ty->arr[Ty->max_r] = Ty0;
358			}
359		✗	}
360
361		✗	static void compute_min_row(IPlane *f, LUT *Ty, chord_set *SE, int r, int y)
362			{
363		✗	if (y + r >= 0 && y + r < f->h) {
364		✗	memcpy(Ty->arr[r][0], f->img[y + r], Ty->X * Ty->type_size);
365			} else {
366		✗	memset(Ty->arr[r][0], UINT8_MAX, Ty->X * Ty->type_size);
367			}
368
369		✗	for (int i = 1; i < SE->Lnum; i++) {
370		✗	int d = SE->R[i] - SE->R[i - 1];
371
372		✗	f->min_out_place(Ty->arr[r][i] - Ty->pre_pad_x * f->type_size,
373		✗	Ty->arr[r][i - 1] - Ty->pre_pad_x * f->type_size,
374		✗	Ty->arr[r][i - 1] + (d - Ty->pre_pad_x) * f->type_size,
375		✗	Ty->X + Ty->pre_pad_x - d);
376		✗	memcpy(Ty->arr[r][i] + (Ty->X - d) * f->type_size,
377		✗	Ty->arr[r][i - 1] + (Ty->X - d) * f->type_size,
378		✗	d * f->type_size);
379			}
380		✗	}
381
382		✗	static void update_min_lut(IPlane *f, LUT *Ty, chord_set *SE, int y, int tid, int num)
383			{
384		✗	for (int i = 0; i < num; i++)
385		✗	circular_swap(Ty);
386
387		✗	compute_min_row(f, Ty, SE, Ty->max_r - tid, y);
388		✗	}
389
390		✗	static int compute_min_lut(LUT *Ty, IPlane *f, chord_set *SE, int y, int num)
391			{
392		✗	int ret = alloc_lut_if_necessary(Ty, f, SE, num, ERODE);
393		✗	if (ret < 0)
394		✗	return ret;
395
396		✗	for (int r = Ty->min_r; r <= Ty->max_r; r++)
397		✗	compute_min_row(f, Ty, SE, r, y);
398
399		✗	return 0;
400			}
401
402		✗	static void compute_max_row(IPlane *f, LUT *Ty, chord_set *SE, int r, int y)
403			{
404		✗	if (y + r >= 0 && y + r < f->h) {
405		✗	memcpy(Ty->arr[r][0], f->img[y + r], Ty->X * Ty->type_size);
406			} else {
407		✗	memset(Ty->arr[r][0], 0, Ty->X * Ty->type_size);
408			}
409
410		✗	for (int i = 1; i < SE->Lnum; i++) {
411		✗	int d = SE->R[i] - SE->R[i - 1];
412
413		✗	f->max_out_place(Ty->arr[r][i] - Ty->pre_pad_x * f->type_size,
414		✗	Ty->arr[r][i - 1] - Ty->pre_pad_x * f->type_size,
415		✗	Ty->arr[r][i - 1] + (d - Ty->pre_pad_x) * f->type_size,
416		✗	Ty->X + Ty->pre_pad_x - d);
417		✗	memcpy(Ty->arr[r][i] + (Ty->X - d) * f->type_size,
418		✗	Ty->arr[r][i - 1] + (Ty->X - d) * f->type_size,
419		✗	d * f->type_size);
420			}
421		✗	}
422
423		✗	static void update_max_lut(IPlane *f, LUT *Ty, chord_set *SE, int y, int tid, int num)
424			{
425		✗	for (int i = 0; i < num; i++)
426		✗	circular_swap(Ty);
427
428		✗	compute_max_row(f, Ty, SE, Ty->max_r - tid, y);
429		✗	}
430
431		✗	static int compute_max_lut(LUT *Ty, IPlane *f, chord_set *SE, int y, int num)
432			{
433		✗	int ret = alloc_lut_if_necessary(Ty, f, SE, num, DILATE);
434		✗	if (ret < 0)
435		✗	return ret;
436
437		✗	for (int r = Ty->min_r; r <= Ty->max_r; r++)
438		✗	compute_max_row(f, Ty, SE, r, y);
439
440		✗	return 0;
441			}
442
443		✗	static void line_dilate(IPlane *g, LUT *Ty, chord_set *SE, int y, int tid)
444			{
445		✗	memset(g->img[y], 0, g->w * g->type_size);
446
447		✗	for (int c = 0; c < SE->size; c++) {
448		✗	g->max_in_place(g->img[y],
449		✗	Ty->arr[SE->C[c].y + tid][SE->C[c].i] + SE->C[c].x * Ty->type_size,
450		✗	av_clip(g->w - SE->C[c].x, 0, g->w));
451			}
452		✗	}
453
454		✗	static void line_erode(IPlane *g, LUT *Ty, chord_set *SE, int y, int tid)
455			{
456		✗	memset(g->img[y], UINT8_MAX, g->w * g->type_size);
457
458		✗	for (int c = 0; c < SE->size; c++) {
459		✗	g->min_in_place(g->img[y],
460		✗	Ty->arr[SE->C[c].y + tid][SE->C[c].i] + SE->C[c].x * Ty->type_size,
461		✗	av_clip(g->w - SE->C[c].x, 0, g->w));
462			}
463		✗	}
464
465		✗	static int dilate(IPlane *g, IPlane *f, chord_set *SE, LUT *Ty, int y0, int y1)
466			{
467		✗	int ret = compute_max_lut(Ty, f, SE, y0, 1);
468		✗	if (ret < 0)
469		✗	return ret;
470
471		✗	line_dilate(g, Ty, SE, y0, 0);
472		✗	for (int y = y0 + 1; y < y1; y++) {
473		✗	update_max_lut(f, Ty, SE, y, 0, 1);
474		✗	line_dilate(g, Ty, SE, y, 0);
475			}
476
477		✗	return 0;
478			}
479
480		✗	static int erode(IPlane *g, IPlane *f, chord_set *SE, LUT *Ty, int y0, int y1)
481			{
482		✗	int ret = compute_min_lut(Ty, f, SE, y0, 1);
483		✗	if (ret < 0)
484		✗	return ret;
485
486		✗	line_erode(g, Ty, SE, y0, 0);
487		✗	for (int y = y0 + 1; y < y1; y++) {
488		✗	update_min_lut(f, Ty, SE, y, 0, 1);
489		✗	line_erode(g, Ty, SE, y, 0);
490			}
491
492		✗	return 0;
493			}
494
495		✗	static void difference(IPlane *g, IPlane *f, int y0, int y1)
496			{
497		✗	for (int y = y0; y < y1; y++)
498		✗	f->diff_in_place(g->img[y], f->img[y], f->w);
499		✗	}
500
501		✗	static void difference2(IPlane *g, IPlane *f, int y0, int y1)
502			{
503		✗	for (int y = y0; y < y1; y++)
504		✗	f->diff_rin_place(g->img[y], f->img[y], f->w);
505		✗	}
506
507		✗	static int insert_chord_set(chord_set *chords, chord c)
508			{
509			// Checking if chord fits in dynamic array, resize if not.
510		✗	if (chords->size == chords->cap) {
511		✗	chords->C = av_realloc_f(chords->C, chords->cap * 2, sizeof(chord));
512		✗	if (!chords->C)
513		✗	return AVERROR(ENOMEM);
514		✗	chords->cap *= 2;
515			}
516
517			// Add the chord to the dynamic array.
518		✗	chords->C[chords->size].x = c.x;
519		✗	chords->C[chords->size].y = c.y;
520		✗	chords->C[chords->size++].l = c.l;
521
522			// Update minimum/maximum x/y offsets of the chord set.
523		✗	chords->minX = FFMIN(chords->minX, c.x);
524		✗	chords->maxX = FFMAX(chords->maxX, c.x);
525
526		✗	chords->minY = FFMIN(chords->minY, c.y);
527		✗	chords->maxY = FFMAX(chords->maxY, c.y);
528
529		✗	return 0;
530			}
531
532		✗	static void free_chord_set(chord_set *SE)
533			{
534		✗	av_freep(&SE->C);
535		✗	SE->size = 0;
536		✗	SE->cap = 0;
537
538		✗	av_freep(&SE->R);
539		✗	SE->Lnum = 0;
540		✗	}
541
542		✗	static int init_chordset(chord_set *chords)
543			{
544		✗	chords->nb_elements = 0;
545		✗	chords->size = 0;
546		✗	chords->C = av_calloc(1, sizeof(chord));
547		✗	if (!chords->C)
548		✗	return AVERROR(ENOMEM);
549
550		✗	chords->cap = 1;
551		✗	chords->minX = INT16_MAX;
552		✗	chords->maxX = INT16_MIN;
553		✗	chords->minY = INT16_MAX;
554		✗	chords->maxY = INT16_MIN;
555
556		✗	return 0;
557			}
558
559		✗	static int comp_chord_length(const void *p, const void *q)
560			{
561			chord a, b;
562		✗	a = *((chord *)p);
563		✗	b = *((chord *)q);
564
565		✗	return (a.l > b.l) - (a.l < b.l);
566			}
567
568		✗	static int comp_chord(const void *p, const void *q)
569			{
570			chord a, b;
571		✗	a = *((chord *)p);
572		✗	b = *((chord *)q);
573
574		✗	return (a.y > b.y) - (a.y < b.y);
575			}
576
577		✗	static int build_chord_set(IPlane *SE, chord_set *chords)
578			{
579		✗	const int mid = 1 << (SE->depth - 1);
580			int chord_length_index;
581			int chord_start, val, ret;
582			int centerX, centerY;
583		✗	int r_cap = 1;
584			chord c;
585
586		✗	ret = init_chordset(chords);
587		✗	if (ret < 0)
588		✗	return ret;
589			/*
590			* In erosion/dilation, the center of the IPlane has S.E. offset (0,0).
591			* Otherwise, the resulting IPlane would be shifted to the top-left.
592			*/
593		✗	centerX = (SE->w - 1) / 2;
594		✗	centerY = (SE->h - 1) / 2;
595
596			/*
597			* Computing the set of chords C.
598			*/
599		✗	for (int y = 0; y < SE->h; y++) {
600			int x;
601
602		✗	chord_start = -1;
603		✗	for (x = 0; x < SE->w; x++) {
604		✗	if (SE->type_size == 1) {
605		✗	chords->nb_elements += (SE->img[y][x] >= mid);
606			//A chord is a run of non-zero pixels.
607		✗	if (SE->img[y][x] >= mid && chord_start == -1) {
608			// Chord starts.
609		✗	chord_start = x;
610		✗	} else if (SE->img[y][x] < mid && chord_start != -1) {
611			// Chord ends before end of line.
612		✗	c.x = chord_start - centerX;
613		✗	c.y = y - centerY;
614		✗	c.l = x - chord_start;
615		✗	ret = insert_chord_set(chords, c);
616		✗	if (ret < 0)
617		✗	return AVERROR(ENOMEM);
618		✗	chord_start = -1;
619			}
620			} else {
621		✗	chords->nb_elements += (AV_RN16(&SE->img[y][x * 2]) >= mid);
622			//A chord is a run of non-zero pixels.
623		✗	if (AV_RN16(&SE->img[y][x * 2]) >= mid && chord_start == -1) {
624			// Chord starts.
625		✗	chord_start = x;
626		✗	} else if (AV_RN16(&SE->img[y][x * 2]) < mid && chord_start != -1) {
627			// Chord ends before end of line.
628		✗	c.x = chord_start - centerX;
629		✗	c.y = y - centerY;
630		✗	c.l = x - chord_start;
631		✗	ret = insert_chord_set(chords, c);
632		✗	if (ret < 0)
633		✗	return AVERROR(ENOMEM);
634		✗	chord_start = -1;
635			}
636			}
637			}
638		✗	if (chord_start != -1) {
639			// Chord ends at end of line.
640		✗	c.x = chord_start - centerX;
641		✗	c.y = y - centerY;
642		✗	c.l = x - chord_start;
643		✗	ret = insert_chord_set(chords, c);
644		✗	if (ret < 0)
645		✗	return AVERROR(ENOMEM);
646			}
647			}
648
649			/*
650			* Computing the array of chord lengths R(i).
651			* This is needed because the lookup table will contain a row for each
652			* length index i.
653			*/
654		✗	qsort(chords->C, chords->size, sizeof(chord), comp_chord_length);
655		✗	chords->R = av_calloc(1, sizeof(*chords->R));
656		✗	if (!chords->R)
657		✗	return AVERROR(ENOMEM);
658		✗	chords->Lnum = 0;
659		✗	val = 0;
660		✗	r_cap = 1;
661
662		✗	if (chords->size > 0) {
663		✗	val = 1;
664		✗	if (chords->Lnum >= r_cap) {
665		✗	chords->R = av_realloc_f(chords->R, r_cap * 2, sizeof(*chords->R));
666		✗	if (!chords->R)
667		✗	return AVERROR(ENOMEM);
668		✗	r_cap *= 2;
669			}
670		✗	chords->R[chords->Lnum++] = 1;
671		✗	val = 1;
672			}
673
674		✗	for (int i = 0; i < chords->size; i++) {
675		✗	if (val != chords->C[i].l) {
676		✗	while (2 * val < chords->C[i].l && val != 0) {
677		✗	if (chords->Lnum >= r_cap) {
678		✗	chords->R = av_realloc_f(chords->R, r_cap * 2, sizeof(*chords->R));
679		✗	if (!chords->R)
680		✗	return AVERROR(ENOMEM);
681		✗	r_cap *= 2;
682			}
683
684		✗	chords->R[chords->Lnum++] = 2 * val;
685		✗	val *= 2;
686			}
687		✗	val = chords->C[i].l;
688
689		✗	if (chords->Lnum >= r_cap) {
690		✗	chords->R = av_realloc_f(chords->R, r_cap * 2, sizeof(*chords->R));
691		✗	if (!chords->R)
692		✗	return AVERROR(ENOMEM);
693		✗	r_cap *= 2;
694			}
695		✗	chords->R[chords->Lnum++] = val;
696			}
697			}
698
699			/*
700			* Setting the length indices of chords.
701			* These are needed so that the algorithm can, for each chord,
702			* access the lookup table at the correct length in constant time.
703			*/
704		✗	chord_length_index = 0;
705		✗	for (int i = 0; i < chords->size; i++) {
706		✗	while (chords->R[chord_length_index] < chords->C[i].l)
707		✗	chord_length_index++;
708		✗	chords->C[i].i = chord_length_index;
709			}
710
711			/*
712			* Chords are sorted on Y. This way, when a row of the lookup table or IPlane
713			* is cached, the next chord offset has a better chance of being on the
714			* same cache line.
715			*/
716		✗	qsort(chords->C, chords->size, sizeof(chord), comp_chord);
717
718		✗	return 0;
719			}
720
721		✗	static void free_iplane(IPlane *imp)
722			{
723		✗	av_freep(&imp->img);
724		✗	}
725
726		✗	static int read_iplane(IPlane *imp, const uint8_t *dst, int dst_linesize,
727			int w, int h, int R, int type_size, int depth)
728			{
729		✗	if (!imp->img)
730		✗	imp->img = av_calloc(h, sizeof(*imp->img));
731		✗	if (!imp->img)
732		✗	return AVERROR(ENOMEM);
733
734		✗	imp->w = w;
735		✗	imp->h = h;
736		✗	imp->range = R;
737		✗	imp->depth = depth;
738		✗	imp->type_size = type_size;
739		✗	imp->max_out_place = type_size == 1 ? max_fun : max16_fun;
740		✗	imp->min_out_place = type_size == 1 ? min_fun : min16_fun;
741		✗	imp->diff_rin_place = type_size == 1 ? diff_fun : diff16_fun;
742		✗	imp->max_in_place = type_size == 1 ? maxinplace_fun : maxinplace16_fun;
743		✗	imp->min_in_place = type_size == 1 ? mininplace_fun : mininplace16_fun;
744		✗	imp->diff_in_place = type_size == 1 ? diffinplace_fun : diffinplace16_fun;
745
746		✗	for (int y = 0; y < h; y++)
747		✗	imp->img[y] = (uint8_t *)dst + y * dst_linesize;
748
749		✗	return 0;
750			}
751
752		✗	static int config_input(AVFilterLink *inlink)
753			{
754		✗	const AVPixFmtDescriptor *desc = av_pix_fmt_desc_get(inlink->format);
755		✗	MorphoContext *s = inlink->dst->priv;
756
757		✗	s->depth = desc->comp[0].depth;
758		✗	s->type_size = (s->depth + 7) / 8;
759		✗	s->nb_planes = desc->nb_components;
760		✗	s->planewidth[1] = s->planewidth[2] = AV_CEIL_RSHIFT(inlink->w, desc->log2_chroma_w);
761		✗	s->planewidth[0] = s->planewidth[3] = inlink->w;
762		✗	s->planeheight[1] = s->planeheight[2] = AV_CEIL_RSHIFT(inlink->h, desc->log2_chroma_h);
763		✗	s->planeheight[0] = s->planeheight[3] = inlink->h;
764
765		✗	return 0;
766			}
767
768		✗	static int config_input_structure(AVFilterLink *inlink)
769			{
770		✗	const AVPixFmtDescriptor *desc = av_pix_fmt_desc_get(inlink->format);
771		✗	AVFilterContext *ctx = inlink->dst;
772		✗	MorphoContext *s = inlink->dst->priv;
773
774		✗	av_assert0(ctx->inputs[0]->format == ctx->inputs[1]->format);
775
776		✗	s->splanewidth[1] = s->splanewidth[2] = AV_CEIL_RSHIFT(inlink->w, desc->log2_chroma_w);
777		✗	s->splanewidth[0] = s->splanewidth[3] = inlink->w;
778		✗	s->splaneheight[1] = s->splaneheight[2] = AV_CEIL_RSHIFT(inlink->h, desc->log2_chroma_h);
779		✗	s->splaneheight[0] = s->splaneheight[3] = inlink->h;
780
781		✗	return 0;
782			}
783
784		✗	static int activate(AVFilterContext *ctx)
785			{
786		✗	MorphoContext *s = ctx->priv;
787		✗	return ff_framesync_activate(&s->fs);
788			}
789
790			typedef struct ThreadData {
791			AVFrame *in, *out;
792			} ThreadData;
793
794		✗	static int morpho_slice(AVFilterContext *ctx, void *arg, int jobnr, int nb_jobs)
795			{
796		✗	MorphoContext *s = ctx->priv;
797		✗	ThreadData *td = arg;
798		✗	AVFrame *out = td->out;
799		✗	AVFrame *in = td->in;
800			int ret;
801
802		✗	for (int p = 0; p < s->nb_planes; p++) {
803		✗	const int width = s->planewidth[p];
804		✗	const int height = s->planeheight[p];
805		✗	const int y0 = (height * jobnr ) / nb_jobs;
806		✗	const int y1 = (height * (jobnr+1)) / nb_jobs;
807		✗	const int depth = s->depth;
808
809		✗	if (ctx->is_disabled || !(s->planes & (1 << p))) {
810		✗	copy:
811		✗	av_image_copy_plane(out->data[p] + y0 * out->linesize[p],
812			out->linesize[p],
813		✗	in->data[p] + y0 * in->linesize[p],
814			in->linesize[p],
815		✗	width * ((depth + 7) / 8),
816			y1 - y0);
817		✗	continue;
818			}
819
820		✗	if (s->SE[p].minX == INT16_MAX ||
821		✗	s->SE[p].minY == INT16_MAX ||
822		✗	s->SE[p].maxX == INT16_MIN ||
823		✗	s->SE[p].maxY == INT16_MIN)
824		✗	goto copy;
825
826		✗	switch (s->mode) {
827		✗	case ERODE:
828		✗	ret = erode(&s->g[p], &s->f[p], &s->SE[p], &s->Ty[jobnr][0][p], y0, y1);
829		✗	break;
830		✗	case DILATE:
831			case GRADIENT:
832		✗	ret = dilate(&s->g[p], &s->f[p], &s->SE[p], &s->Ty[jobnr][0][p], y0, y1);
833		✗	break;
834		✗	case OPEN:
835			case TOPHAT:
836		✗	ret = erode(&s->h[p], &s->f[p], &s->SE[p], &s->Ty[jobnr][0][p], y0, y1);
837		✗	break;
838		✗	case CLOSE:
839			case BLACKHAT:
840		✗	ret = dilate(&s->h[p], &s->f[p], &s->SE[p], &s->Ty[jobnr][0][p], y0, y1);
841		✗	break;
842		✗	default:
843		✗	av_assert0(0);
844			}
845
846		✗	if (ret < 0)
847		✗	return ret;
848			}
849
850		✗	return 0;
851			}
852
853		✗	static int morpho_sliceX(AVFilterContext *ctx, void *arg, int jobnr, int nb_jobs)
854			{
855		✗	MorphoContext *s = ctx->priv;
856			int ret;
857
858		✗	for (int p = 0; p < s->nb_planes; p++) {
859		✗	const int height = s->planeheight[p];
860		✗	const int y0 = (height * jobnr ) / nb_jobs;
861		✗	const int y1 = (height * (jobnr+1)) / nb_jobs;
862
863		✗	if (ctx->is_disabled || !(s->planes & (1 << p))) {
864		✗	copy:
865		✗	continue;
866			}
867
868		✗	if (s->SE[p].minX == INT16_MAX ||
869		✗	s->SE[p].minY == INT16_MAX ||
870		✗	s->SE[p].maxX == INT16_MIN ||
871		✗	s->SE[p].maxY == INT16_MIN)
872		✗	goto copy;
873
874		✗	switch (s->mode) {
875		✗	case OPEN:
876		✗	ret = dilate(&s->g[p], &s->h[p], &s->SE[p], &s->Ty[jobnr][1][p], y0, y1);
877		✗	break;
878		✗	case CLOSE:
879		✗	ret = erode(&s->g[p], &s->h[p], &s->SE[p], &s->Ty[jobnr][1][p], y0, y1);
880		✗	break;
881		✗	case GRADIENT:
882		✗	ret = erode(&s->h[p], &s->f[p], &s->SE[p], &s->Ty[jobnr][1][p], y0, y1);
883		✗	if (ret < 0)
884		✗	break;
885		✗	difference(&s->g[p], &s->h[p], y0, y1);
886		✗	break;
887		✗	case TOPHAT:
888		✗	ret = dilate(&s->g[p], &s->h[p], &s->SE[p], &s->Ty[jobnr][1][p], y0, y1);
889		✗	if (ret < 0)
890		✗	break;
891		✗	difference2(&s->g[p], &s->f[p], y0, y1);
892		✗	break;
893		✗	case BLACKHAT:
894		✗	ret = erode(&s->g[p], &s->h[p], &s->SE[p], &s->Ty[jobnr][1][p], y0, y1);
895		✗	if (ret < 0)
896		✗	break;
897		✗	difference(&s->g[p], &s->f[p], y0, y1);
898		✗	break;
899		✗	default:
900		✗	av_assert0(0);
901			}
902
903		✗	if (ret < 0)
904		✗	return ret;
905			}
906
907		✗	return 0;
908			}
909
910		✗	static int do_morpho(FFFrameSync *fs)
911			{
912		✗	AVFilterContext *ctx = fs->parent;
913		✗	AVFilterLink *outlink = ctx->outputs[0];
914		✗	MorphoContext *s = ctx->priv;
915		✗	AVFrame *in = NULL, *structurepic = NULL;
916			ThreadData td;
917			AVFrame *out;
918			int ret;
919
920		✗	ret = ff_framesync_dualinput_get(fs, &in, &structurepic);
921		✗	if (ret < 0)
922		✗	return ret;
923		✗	if (!structurepic)
924		✗	return ff_filter_frame(outlink, in);
925
926		✗	out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
927		✗	if (!out) {
928		✗	av_frame_free(&in);
929		✗	return AVERROR(ENOMEM);
930			}
931		✗	av_frame_copy_props(out, in);
932
933		✗	for (int p = 0; p < s->nb_planes; p++) {
934		✗	const uint8_t *ssrc = structurepic->data[p];
935		✗	const int ssrc_linesize = structurepic->linesize[p];
936		✗	const int swidth = s->splanewidth[p];
937		✗	const int sheight = s->splaneheight[p];
938		✗	const uint8_t *src = in->data[p];
939		✗	int src_linesize = in->linesize[p];
940		✗	uint8_t *dst = out->data[p];
941		✗	int dst_linesize = out->linesize[p];
942		✗	const int width = s->planewidth[p];
943		✗	const int height = s->planeheight[p];
944		✗	const int depth = s->depth;
945		✗	int type_size = s->type_size;
946
947		✗	if (!s->got_structure[p] || s->structures) {
948		✗	free_chord_set(&s->SE[p]);
949
950		✗	ret = read_iplane(&s->SEimg[p], ssrc, ssrc_linesize, swidth, sheight, 1, type_size, depth);
951		✗	if (ret < 0)
952		✗	goto fail;
953		✗	ret = build_chord_set(&s->SEimg[p], &s->SE[p]);
954		✗	if (ret < 0)
955		✗	goto fail;
956		✗	s->got_structure[p] = 1;
957			}
958
959		✗	ret = read_iplane(&s->f[p], src, src_linesize, width, height, 1, type_size, depth);
960		✗	if (ret < 0)
961		✗	goto fail;
962
963		✗	ret = read_iplane(&s->g[p], dst, dst_linesize, s->f[p].w, s->f[p].h, s->f[p].range, type_size, depth);
964		✗	if (ret < 0)
965		✗	goto fail;
966
967		✗	switch (s->mode) {
968		✗	case OPEN:
969			case CLOSE:
970			case GRADIENT:
971			case TOPHAT:
972			case BLACKHAT:
973		✗	ret = read_iplane(&s->h[p], s->temp->data[p], s->temp->linesize[p], width, height, 1, type_size, depth);
974		✗	break;
975			}
976
977		✗	if (ret < 0)
978		✗	goto fail;
979			}
980
981		✗	td.in = in; td.out = out;
982		✗	ret = ff_filter_execute(ctx, morpho_slice, &td, NULL,
983		✗	FFMIN3(s->planeheight[1], s->planeheight[2],
984			FFMIN(MAX_THREADS, ff_filter_get_nb_threads(ctx))));
985		✗	if (ret == 0 && (s->mode != ERODE && s->mode != DILATE)) {
986		✗	ff_filter_execute(ctx, morpho_sliceX, NULL, NULL,
987		✗	FFMIN3(s->planeheight[1], s->planeheight[2],
988			FFMIN(MAX_THREADS, ff_filter_get_nb_threads(ctx))));
989			}
990
991		✗	av_frame_free(&in);
992		✗	out->pts = av_rescale_q(s->fs.pts, s->fs.time_base, outlink->time_base);
993		✗	return ff_filter_frame(outlink, out);
994		✗	fail:
995		✗	av_frame_free(&out);
996		✗	av_frame_free(&in);
997		✗	return ret;
998			}
999
1000		✗	static int config_output(AVFilterLink *outlink)
1001			{
1002		✗	AVFilterContext *ctx = outlink->src;
1003		✗	MorphoContext *s = ctx->priv;
1004		✗	AVFilterLink *mainlink = ctx->inputs[0];
1005		✗	FilterLink *il = ff_filter_link(mainlink);
1006		✗	FilterLink *ol = ff_filter_link(outlink);
1007			int ret;
1008
1009		✗	s->fs.on_event = do_morpho;
1010		✗	ret = ff_framesync_init_dualinput(&s->fs, ctx);
1011		✗	if (ret < 0)
1012		✗	return ret;
1013		✗	outlink->w = mainlink->w;
1014		✗	outlink->h = mainlink->h;
1015		✗	outlink->time_base = mainlink->time_base;
1016		✗	outlink->sample_aspect_ratio = mainlink->sample_aspect_ratio;
1017		✗	ol->frame_rate = il->frame_rate;
1018
1019		✗	if ((ret = ff_framesync_configure(&s->fs)) < 0)
1020		✗	return ret;
1021		✗	outlink->time_base = s->fs.time_base;
1022
1023		✗	s->temp = ff_get_video_buffer(outlink, outlink->w, outlink->h);
1024		✗	if (!s->temp)
1025		✗	return AVERROR(ENOMEM);
1026
1027		✗	s->plane_f = av_calloc(outlink->w * outlink->h, sizeof(*s->plane_f));
1028		✗	s->plane_g = av_calloc(outlink->w * outlink->h, sizeof(*s->plane_g));
1029		✗	if (!s->plane_f || !s->plane_g)
1030		✗	return AVERROR(ENOMEM);
1031
1032		✗	return 0;
1033			}
1034
1035		✗	static av_cold void uninit(AVFilterContext *ctx)
1036			{
1037		✗	MorphoContext *s = ctx->priv;
1038
1039		✗	for (int p = 0; p < 4; p++) {
1040		✗	free_iplane(&s->SEimg[p]);
1041		✗	free_iplane(&s->f[p]);
1042		✗	free_iplane(&s->g[p]);
1043		✗	free_iplane(&s->h[p]);
1044		✗	free_chord_set(&s->SE[p]);
1045		✗	for (int n = 0; n < MAX_THREADS; n++) {
1046		✗	free_lut(&s->Ty[n][0][p]);
1047		✗	free_lut(&s->Ty[n][1][p]);
1048			}
1049			}
1050
1051		✗	ff_framesync_uninit(&s->fs);
1052
1053		✗	av_frame_free(&s->temp);
1054		✗	av_freep(&s->plane_f);
1055		✗	av_freep(&s->plane_g);
1056		✗	}
1057
1058			static const AVFilterPad morpho_inputs[] = {
1059			{
1060			.name = "default",
1061			.type = AVMEDIA_TYPE_VIDEO,
1062			.config_props = config_input,
1063			},
1064			{
1065			.name = "structure",
1066			.type = AVMEDIA_TYPE_VIDEO,
1067			.config_props = config_input_structure,
1068			},
1069			};
1070
1071			static const AVFilterPad morpho_outputs[] = {
1072			{
1073			.name = "default",
1074			.type = AVMEDIA_TYPE_VIDEO,
1075			.config_props = config_output,
1076			},
1077			};
1078
1079			const AVFilter ff_vf_morpho = {
1080			.name = "morpho",
1081			.description = NULL_IF_CONFIG_SMALL("Apply Morphological filter."),
1082			.preinit = morpho_framesync_preinit,
1083			.priv_size = sizeof(MorphoContext),
1084			.priv_class = &morpho_class,
1085			.activate = activate,
1086			.uninit = uninit,
1087			FILTER_INPUTS(morpho_inputs),
1088			FILTER_OUTPUTS(morpho_outputs),
1089			FILTER_PIXFMTS_ARRAY(pix_fmts),
1090			.flags = AVFILTER_FLAG_SUPPORT_TIMELINE_INTERNAL |
1091			AVFILTER_FLAG_SLICE_THREADS,
1092			.process_command = ff_filter_process_command,
1093			};
1094