From patchwork Tue Dec 27 23:18:04 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?b?Q2zDqW1lbnQgQsWTc2No?= X-Patchwork-Id: 39785 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a05:6a20:bc95:b0:ad:ade2:bfd2 with SMTP id fx21csp3762145pzb; Tue, 27 Dec 2022 15:21:14 -0800 (PST) X-Google-Smtp-Source: AMrXdXv59DSJRmpt1cU7aZjpdKtfgsXsmrIR7bYQfKYIj83ZbNv8rkd++6dWYSSonvNC1y3Z9Mr0 X-Received: by 2002:a05:6402:a55:b0:475:9918:37ce with SMTP id bt21-20020a0564020a5500b00475991837cemr19961703edb.13.1672183274320; Tue, 27 Dec 2022 15:21:14 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1672183274; cv=none; d=google.com; s=arc-20160816; b=X+vX5Kz9ik09mkl8KpU9kzl4e1qMZeOjaBEPJFGWoB4rhN/NH62o/pIBE13uA1omla YJC5jrPwfQO8guuTQ/LQ2qfCJ51/FbmkcUei0BlvEuM0W+EAglxCnSFQmI3Ff7uPyUTJ KvQS8ZKuM5P+A4iC360kvu+PBqSKiiNHBxMrsvYNmcb+SswXzbsSrxFlCvIwBhL7xG4d 8K+ab1tSeplgtyuAWc5N0GBSo6wRKyRDOxpvo3Zg5PpSstMHYN5UJhDUzRy0R9RlakzZ WdJhw5dRUjQn+V90/y49LnasB5096WUvL7zwXTK2/ko/HdKzvqa+gNUsRImoyvAY0r6g LPFA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:content-transfer-encoding:cc:reply-to :list-subscribe:list-help:list-post:list-archive:list-unsubscribe :list-id:precedence:subject:mime-version:references:in-reply-to :message-id:date:to:from:dkim-signature:delivered-to; bh=8RJV+BPAU4hhGaiq+rOtVxirtviExoJq94QH/3JQET0=; b=nvujhSqph5ad3qHUiSBJdoYcUNFMhMGK00ilvX3zL5ZHbLkNMlH/o0A/a2EsemkLgl FVv9qElDKa53T/I1IGjMjhiP9NTSQ/9kC9gZ1RIm/AP3i7qVh8QO+YaNCi2+OlJrvpmy VMcvqU6CaZoN42fJbvezdXFzwPKEGccGidaVF8VCpbqzV2iZ9zHVDc6m6r/+El8n4AVY m9hvSVAiVV9I2w5r22kJNsEQaqVjWn0FwiPW38qV2WmAAEVAVY6kno+fdq57xt81a00z dAexYI/aYEX6/Fh0uVCflT5E0QwDaFUIzFjabWHtSw3s0S4l3Z2R5OI3NjAG39gR+ELZ mcqg== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@pkh.me header.s=selector1 header.b=qin8OV1n; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=pkh.me Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org. [79.124.17.100]) by mx.google.com with ESMTP id f8-20020a056402194800b004838856a8dasi7807644edz.568.2022.12.27.15.21.14; Tue, 27 Dec 2022 15:21:14 -0800 (PST) Received-SPF: pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) client-ip=79.124.17.100; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@pkh.me header.s=selector1 header.b=qin8OV1n; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=pkh.me Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 310A268BD4D; Wed, 28 Dec 2022 01:18:47 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org 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?b?Q2zDqW1lbnQgQsWTc2No?= 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?b?Q2zDqW1lbnQgQsWTc2No?= Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" X-TUID: WzZZKLWkANeL 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