From patchwork Fri Sep 17 02:08:04 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Rheinhardt X-Patchwork-Id: 30304 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a05:6602:2a4a:0:0:0:0 with SMTP id k10csp1785093iov; Thu, 16 Sep 2021 19:10:02 -0700 (PDT) X-Google-Smtp-Source: ABdhPJw++M3UshvJO9ShoP6vhuClAlK8fpm8xBcO3GOm1joFCS154DL40tBtImCWTXIeICauCEq6 X-Received: by 2002:a17:906:cc0e:: with SMTP id ml14mr9235438ejb.395.1631844601859; Thu, 16 Sep 2021 19:10:01 -0700 (PDT) Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org. [79.124.17.100]) by mx.google.com with ESMTP id e3si5833930ejs.199.2021.09.16.19.10.01; Thu, 16 Sep 2021 19:10:01 -0700 (PDT) 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=@outlook.com header.s=selector1 header.b=a4YrQ4Ss; arc=fail (body hash mismatch); 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=QUARANTINE dis=NONE) header.from=outlook.com Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id CEF5368B149; Fri, 17 Sep 2021 05:08:42 +0300 (EEST) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from EUR04-VI1-obe.outbound.protection.outlook.com (mail-oln040092075092.outbound.protection.outlook.com [40.92.75.92]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 8A85C68B0FD for ; Fri, 17 Sep 2021 05:08:38 +0300 (EEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=K4P83wKKkevaqsnX3KAjd2Axm7zhqPB738cK/Rnqrms4Xd3F+bsBX2LVi1Amd7zeg348ceqQMEbq29wuO6nOqJnWSxtrpXwRMPKjZkQxBlSFuHoTyXC2Njf6B8TzMOsLMFaRWq8IlqdrAO24TDAY4onQadCZMvB51ZC4mhQP0OJfLYZZ0cxUwzU4OOpGCNlcNtm2p+iTCoDu8IE5MIG/4t61OMLzwA/o/idnSmCM91GvZM9H/sD8n4TjqKKre7ExHCtCFeRRjT4POgUMPqROzsZQIaVwgLBDEMYJ+fOtgVeKCZNyqRP/m+uJuxK29+lTHf3HEnDX4MZN5agvQbXVSQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=R4BTs77sBOIlpQMGE5qgYN/KIQlgSKmLF5jICrmnTKM=; b=gc48TDiJD1olKs9U+Ip8aOmzAHiJuzolaL3cREO6LLb3VnvnzZRYh4P7EhAcj2k67HmKrwxxgdZkM49Lo23R+brcIfsyxRJGLGwfBNpbOLh2FYj7RiPUZdI/rdSmmdGq97yVFAbMordWzkoYxURJhfbQgbp0chw+tiqJaSapa+BE7kmFHjPqFYkvS965DYthlEahvRPFEzeNs2YbsHnl64svVGb5yC6jfpZIAfYgfLo9V4I3gBBy0AHnG5JqWdOeqXQHBEzpAnC8eHci1Z6afALsjLN657bRiZ+sSpWA+n3hUfy1AUekbyMjibi4OQBE3SnN2KtA9kizrYMQ1k8O3A== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=none; dmarc=none; dkim=none; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=outlook.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=R4BTs77sBOIlpQMGE5qgYN/KIQlgSKmLF5jICrmnTKM=; b=a4YrQ4SsM8ZIcNSrH9ZbE7pS+opN7hN42dO0TSqo77hLM+EcGzdya1b7os5P7gJNqLZ02C/Up0K4WjipshxfEIvLbGzKF9kv4temg/K9vAqWw9MLGait1ta0rN2nQT5Dw8bBQgrXcVdqBscDus8mjXohPds5LIxAohBnaigJnjym+TyFEwzY5TE8fZtteDnMcfrPIe340alXbFTPLg1ki3CFPUAMd6p6exuKhAslFZ5gEhiqdUtBoJjI2TAoVz51Va0LEH9rzdxB2cPaZvwqKkztYuOvFfwRDUpro+wktB5VLWaMFPwjuswZ5qbXvUBWCA09QQDE5/dvuFR0+5CvZg== Received: from AM7PR03MB6660.eurprd03.prod.outlook.com (2603:10a6:20b:1c1::22) by AM6PR03MB5297.eurprd03.prod.outlook.com (2603:10a6:20b:c5::22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4523.16; Fri, 17 Sep 2021 02:08:29 +0000 Received: from AM7PR03MB6660.eurprd03.prod.outlook.com ([fe80::787b:2156:ca99:fe00]) by AM7PR03MB6660.eurprd03.prod.outlook.com ([fe80::787b:2156:ca99:fe00%3]) with mapi id 15.20.4523.016; Fri, 17 Sep 2021 02:08:29 +0000 From: Andreas Rheinhardt To: ffmpeg-devel@ffmpeg.org Date: Fri, 17 Sep 2021 04:08:04 +0200 Message-ID: X-Mailer: git-send-email 2.30.2 In-Reply-To: References: X-TMN: [oo6Dvqw8ilGtdrpDKdlyjVBXrupLKWxr] X-ClientProxiedBy: AM8P191CA0018.EURP191.PROD.OUTLOOK.COM (2603:10a6:20b:21a::23) To AM7PR03MB6660.eurprd03.prod.outlook.com (2603:10a6:20b:1c1::22) X-Microsoft-Original-Message-ID: <20210917020808.275498-8-andreas.rheinhardt@outlook.com> MIME-Version: 1.0 X-MS-Exchange-MessageSentRepresentingType: 1 Received: from sblaptop.fritz.box (188.192.142.38) by AM8P191CA0018.EURP191.PROD.OUTLOOK.COM (2603:10a6:20b:21a::23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4523.14 via Frontend Transport; Fri, 17 Sep 2021 02:08:29 +0000 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 0e139f68-1da8-465a-2867-08d979800abf X-MS-Exchange-SLBlob-MailProps: S/btQ8cKWiQB5KKqMro6wr3957+0yV3UBKE9R8MG1zt+W+/DlJ/AlN2ytHo96fHvuorak4xRJU1BjrHL5pKVJV/df41mH+QM1jJBKZc8b15/Y0ORi7xFpUb307fBbHUCuoSrbAz3RAjEBCJ1jWRm+FhMNynPAiXOrzhfWY38MjUo0cgngi3xikxiB4/l8T+OEFsGfEBtpwFAHm/uaTaFlrPO9yyYWYp9DZ3VGWrrcm0foxZqALRKxRMfWwwvzN3wwh2RtSTfHNryY662nKBfaiqAstGdzGp6Wli8x0NaHFm4B8KtZeGdN6D6tefKADZPpYbm0KGn0+v3hgmERd9fyff1payVY21wB5QMTlDf4SOERoOVfSyKIcOd/VVc4QkgLBGs/4x7EbhlHvrMQbpoYJczIHhIt/K9o3eX8MaJgPj3BdwmikQs4fyh2Rw9r6VhLtlWwRZQUV5ZzmmjQgO6maXbPJx04Mpo6ds1uowftuBXYeO/jy3lG/TY1o89wY0P46u79l4xtCDqDnALSvKqj6ihZBU5T5/AZED1SgWumBPJ9q8IXE431G9RitBIeXB+N4cURAwXzcKY2GrucGtxIseosDadPi2cEwSTqlYfYUSUlfgoQbApwTyvlhVI/MlsAVtjvgwHeRvfu7R6JfbIxkot0zH6J7yxo1SLBx1Yo0tfNMehxgyN+zUZbst7BKv+ZLeeCkbsc7uMwwVbCWg/FcXmYuaxsY3717lwxzB/JtreRtxmJz3lA7rJu+owkcIybLxaZofJUKU= X-MS-TrafficTypeDiagnostic: AM6PR03MB5297: X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: h2+iVPNlOGP8s36MKVRkolf4q2yphVDBFvhkNR2y+wrDi+I4HFReKJ6UCtKNC6COztSnt8LzZu+iz3sF2FLKj2nJNBIgkB8vla3RBt8roRMKS6mjDrJ92tnOmraOWj9goiI7fi/pg75pI7yJjJGk0VKd88yuC7z92BWr7Of14bpop/8JYRaFlzzAJRqE6oZD5+Yusrp2PR6tJoMPgiORnMB9syGU8j1JfF1IPhhEK7WnMz1ca4jQyGqjQhq4HW7O/bHmTKgRjpnay6NBA9ZCe7ESTRkoVnZRxM3oDD8nr5RS+hcqolW9zguU6pjunHW5Vh25neTFVXv6QjwpGOVY1SFnmaGuM43U2sp8h7QX3kBZ7QTkjh9cpbvlAU0UivZYcUMgYswjMRsPDepYQCrbYEZ8SOHXVcKIUFRlwEfRlu/vcaF/WctGNcsAEgcqj+da X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: uzXg5rDtrqqfDg2SKo9HiLcALje9JB1dFoFERK729WZ4Gwz5UQajJ2ngOGtzNISwPtSCwEP35rtTtos5rToVNkg1mKi/PkBUSAMzxyzcA+jOs9eOq8DpnO13WQxDBehjuRfu4/7czkRW+DNMBztmZQ== X-OriginatorOrg: outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 0e139f68-1da8-465a-2867-08d979800abf X-MS-Exchange-CrossTenant-AuthSource: AM7PR03MB6660.eurprd03.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 17 Sep 2021 02:08:29.4821 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000 X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR03MB5297 Subject: [FFmpeg-devel] [PATCH 09/13] avcodec/elbg: Also allocate buffers for recursion only once 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: Andreas Rheinhardt Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" X-TUID: G+unoJmmAcGo This is possible because the number of elements needed in each recursion step decreases geometrically, so the geometric series provides an upper bound for the sum of number of elements of the needed buffers. Signed-off-by: Andreas Rheinhardt --- libavcodec/elbg.c | 38 ++++++++++++++++++++------------------ 1 file changed, 20 insertions(+), 18 deletions(-) diff --git a/libavcodec/elbg.c b/libavcodec/elbg.c index 4397bff1ef..2bacf5b773 100644 --- a/libavcodec/elbg.c +++ b/libavcodec/elbg.c @@ -53,6 +53,7 @@ typedef struct ELBGContext { int64_t *utility_inc; int *nearest_cb; int *points; + int *temp_points; int *size_part; AVLFG *rand_state; int *scratchbuf; @@ -67,6 +68,7 @@ typedef struct ELBGContext { unsigned cells_allocated; unsigned scratchbuf_allocated; unsigned cell_buffer_allocated; + unsigned temp_points_allocated; } ELBGContext; static inline int distance_limited(int *a, int *b, int dim, int limit) @@ -416,37 +418,29 @@ static void do_elbg(ELBGContext *elbg, int *points, int numpoints, * If numpoints <= 24 * num_cb this function fills codebook with random numbers. * If not, it calls do_elbg for a (smaller) random sample of the points in * points. - * @return < 0 in case of error, 0 otherwise */ -static int init_elbg(ELBGContext *elbg, int *points, int numpoints, - int max_steps) +static void init_elbg(ELBGContext *elbg, int *points, int *temp_points, + int numpoints, int max_steps) { int dim = elbg->dim; - int ret = 0; if (numpoints > 24LL * elbg->num_cb) { /* ELBG is very costly for a big number of points. So if we have a lot of them, get a good initial codebook to save on iterations */ - int *temp_points = av_malloc_array(dim, (numpoints/8)*sizeof(*temp_points)); - if (!temp_points) - return AVERROR(ENOMEM); for (int i = 0; i < numpoints / 8; i++) { int k = (i*BIG_PRIME) % numpoints; memcpy(temp_points + i*dim, points + k*dim, dim * sizeof(*temp_points)); } - ret = init_elbg(elbg, temp_points, numpoints / 8, 2 * max_steps); - if (ret < 0) { - av_freep(&temp_points); - return ret; - } + /* If anything is changed in the recursion parameters, + * the allocated size of temp_points will also need to be updated. */ + init_elbg(elbg, temp_points, temp_points + numpoints / 8 * dim, + numpoints / 8, 2 * max_steps); do_elbg(elbg, temp_points, numpoints / 8, 2 * max_steps); - av_free(temp_points); } else // If not, initialize the codebook with random positions for (int i = 0; i < elbg->num_cb; i++) memcpy(elbg->codebook + i * dim, points + ((i*BIG_PRIME)%numpoints)*dim, dim * sizeof(*elbg->codebook)); - return 0; } int avpriv_elbg_do(ELBGContext **elbgp, int *points, int dim, int numpoints, @@ -454,7 +448,6 @@ int avpriv_elbg_do(ELBGContext **elbgp, int *points, int dim, int numpoints, int *closest_cb, AVLFG *rand_state) { ELBGContext *const elbg = *elbgp ? *elbgp : av_mallocz(sizeof(*elbg)); - int ret; if (!elbg) return AVERROR(ENOMEM); @@ -487,10 +480,18 @@ int avpriv_elbg_do(ELBGContext **elbgp, int *points, int dim, int numpoints, ALLOCATE_IF_NECESSARY(size_part, num_cb, 1) ALLOCATE_IF_NECESSARY(cell_buffer, numpoints, 1) ALLOCATE_IF_NECESSARY(scratchbuf, dim, 5) + if (numpoints > 24LL * elbg->num_cb) { + /* The first step in the recursion in init_elbg() needs a buffer with + * (numpoints / 8) * dim elements; the next step needs numpoints / 8 / 8 + * * dim elements etc. The geometric series leads to an upper bound of + * numpoints / 8 * 8 / 7 * dim elements. */ + uint64_t prod = dim * (uint64_t)(numpoints / 7U); + if (prod > INT_MAX) + return AVERROR(ERANGE); + ALLOCATE_IF_NECESSARY(temp_points, prod, 1) + } - ret = init_elbg(elbg, points, numpoints, max_steps); - if (ret < 0) - return ret; + init_elbg(elbg, points, elbg->temp_points, numpoints, max_steps); do_elbg (elbg, points, numpoints, max_steps); return 0; } @@ -507,6 +508,7 @@ av_cold void avpriv_elbg_free(ELBGContext **elbgp) av_freep(&elbg->cells); av_freep(&elbg->utility_inc); av_freep(&elbg->scratchbuf); + av_freep(&elbg->temp_points); av_freep(elbgp); }