From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by master.gitmailbox.com (Postfix) with ESMTP id 32EBC44E3D for ; Tue, 27 Dec 2022 23:21:12 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id F17E968BD4C; Wed, 28 Dec 2022 01:18:46 +0200 (EET) Received: from ssq0.pkh.me (laubervilliers-656-1-228-164.w92-154.abo.wanadoo.fr [92.154.28.164]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id F1C2968BCD2 for ; Wed, 28 Dec 2022 01:18:34 +0200 (EET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pkh.me; s=selector1; t=1672183099; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=MP8qLHNnIPfx+eYMMHi45KrmAqo6FfJYPQitNhEjlY4=; b=qin8OV1n7Wwi98u8ZXAv0LBP9ONaD2mGMyyqvtGL57+unKJ8e4qAbhTH3AaAVxnAxdVH8i 64wibGV1kVR28vx42ZH28z46WLxoipWK3wm7PC2bh3lvkKBvBACFHhOtCE+FbpUWcjCcz5 FFdAn84MXZ1XCpYj9DSarbvmgMywLns= Received: from localhost (ssq0.pkh.me [local]) by ssq0.pkh.me (OpenSMTPD) with ESMTPA id 5ddc06c0; Tue, 27 Dec 2022 23:18:19 +0000 (UTC) From: =?UTF-8?q?Cl=C3=A9ment=20B=C5=93sch?= To: ffmpeg-devel@ffmpeg.org Date: Wed, 28 Dec 2022 00:18:04 +0100 Message-Id: <20221227231814.2520181-23-u@pkh.me> X-Mailer: git-send-email 2.38.1 In-Reply-To: <20221227231814.2520181-1-u@pkh.me> References: <20221105152617.1809282-1-u@pkh.me> <20221227231814.2520181-1-u@pkh.me> MIME-Version: 1.0 Subject: [FFmpeg-devel] [PATCH v2 22/32] avfilter/palettegen: make refs order deterministic X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Cc: =?UTF-8?q?Cl=C3=A9ment=20B=C5=93sch?= Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Archived-At: List-Archive: List-Post: Currently, in case of equality on the first color channel, the order of the ref colors is defined by the hashing function. This commit makes the sorting deterministic and improve the hierarchical ordering. --- libavfilter/vf_palettegen.c | 61 ++++++++++++++++++++++-------- tests/ref/fate/filter-palettegen-1 | 2 +- tests/ref/fate/filter-palettegen-2 | 2 +- 3 files changed, 47 insertions(+), 18 deletions(-) diff --git a/libavfilter/vf_palettegen.c b/libavfilter/vf_palettegen.c index ba81739d27..784e81b875 100644 --- a/libavfilter/vf_palettegen.c +++ b/libavfilter/vf_palettegen.c @@ -113,19 +113,51 @@ static int query_formats(AVFilterContext *ctx) typedef int (*cmp_func)(const void *, const void *); -#define DECLARE_CMP_FUNC(name, pos) \ -static int cmp_##name(const void *pa, const void *pb) \ -{ \ - const struct color_ref * const *a = pa; \ - const struct color_ref * const *b = pb; \ - return FFDIFFSIGN((*a)->lab.name, (*b)->lab.name); \ +#define DECLARE_CMP_FUNC(k0, k1, k2) \ +static int cmp_##k0##k1##k2(const void *pa, const void *pb) \ +{ \ + const struct color_ref * const *a = pa; \ + const struct color_ref * const *b = pb; \ + const int c0 = FFDIFFSIGN((*a)->lab.k0, (*b)->lab.k0); \ + const int c1 = FFDIFFSIGN((*a)->lab.k1, (*b)->lab.k1); \ + const int c2 = FFDIFFSIGN((*a)->lab.k2, (*b)->lab.k2); \ + return c0 ? c0 : c1 ? c1 : c2; \ } -DECLARE_CMP_FUNC(L, 0) -DECLARE_CMP_FUNC(a, 1) -DECLARE_CMP_FUNC(b, 2) +DECLARE_CMP_FUNC(L, a, b) +DECLARE_CMP_FUNC(L, b, a) +DECLARE_CMP_FUNC(a, L, b) +DECLARE_CMP_FUNC(a, b, L) +DECLARE_CMP_FUNC(b, L, a) +DECLARE_CMP_FUNC(b, a, L) + +enum { ID_XYZ, ID_XZY, ID_ZXY, ID_YXZ, ID_ZYX, ID_YZX }; +static const char * const sortstr[] = { "Lab", "Lba", "bLa", "aLb", "baL", "abL" }; + +static const cmp_func cmp_funcs[] = { + [ID_XYZ] = cmp_Lab, + [ID_XZY] = cmp_Lba, + [ID_ZXY] = cmp_bLa, + [ID_YXZ] = cmp_aLb, + [ID_ZYX] = cmp_baL, + [ID_YZX] = cmp_abL, +}; -static const cmp_func cmp_funcs[] = {cmp_L, cmp_a, cmp_b}; +/* + * Return an identifier for the order of x, y, z (from higher to lower), + * preferring x over y and y over z in case of equality. + */ +static int sort3id(int64_t x, int64_t y, int64_t z) +{ + if (x >= y) { + if (y >= z) return ID_XYZ; + if (x >= z) return ID_XZY; + return ID_ZXY; + } + if (x >= z) return ID_YXZ; + if (y >= z) return ID_YZX; + return ID_ZYX; +} /** * Simple color comparison for sorting the final palette @@ -167,10 +199,7 @@ static void compute_box_stats(PaletteGenContext *s, struct range_box *box) } /* Define the best axis candidate for cutting the box */ - box->major_axis = 0; - if (er2[2] >= er2[0] && er2[2] >= er2[1]) box->major_axis = 2; - if (er2[1] >= er2[0] && er2[1] >= er2[2]) box->major_axis = 1; - if (er2[0] >= er2[1] && er2[0] >= er2[2]) box->major_axis = 0; + box->major_axis = sort3id(er2[0], er2[1], er2[2]); /* The box that has the axis with the biggest error amongst all boxes will but cut down */ box->cut_score = FFMAX3(er2[0], er2[1], er2[2]); @@ -316,9 +345,9 @@ static AVFrame *get_palette_frame(AVFilterContext *ctx) int i; int64_t median, weight; - ff_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64" sort by %c (already sorted:%c) ", + ff_dlog(ctx, "box #%02X [%6d..%-6d] (%6d) w:%-6"PRIu64" sort by %s (already sorted:%c) ", box_id, box->start, box->start + box->len - 1, box->len, box->weight, - "Lab"[box->major_axis], box->sorted_by == box->major_axis ? 'y':'n'); + sortstr[box->major_axis], box->sorted_by == box->major_axis ? 'y':'n'); /* sort the range by its major axis if it's not already sorted */ if (box->sorted_by != box->major_axis) { diff --git a/tests/ref/fate/filter-palettegen-1 b/tests/ref/fate/filter-palettegen-1 index bae6b7064b..1e5c9ee002 100644 --- a/tests/ref/fate/filter-palettegen-1 +++ b/tests/ref/fate/filter-palettegen-1 @@ -3,4 +3,4 @@ #codec_id 0: rawvideo #dimensions 0: 16x16 #sar 0: 1/1 -0, 0, 0, 1, 1024, 0xbb5cde01 +0, 0, 0, 1, 1024, 0xa285dd77 diff --git a/tests/ref/fate/filter-palettegen-2 b/tests/ref/fate/filter-palettegen-2 index 7217de3a92..c1fc64e13d 100644 --- a/tests/ref/fate/filter-palettegen-2 +++ b/tests/ref/fate/filter-palettegen-2 @@ -3,4 +3,4 @@ #codec_id 0: rawvideo #dimensions 0: 16x16 #sar 0: 1/1 -0, 0, 0, 1, 1024, 0xfbf66e70 +0, 0, 0, 1, 1024, 0xf2286e18 -- 2.39.0 _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org https://ffmpeg.org/mailman/listinfo/ffmpeg-devel To unsubscribe, visit link above, or email ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".