From patchwork Fri May 12 21:46:34 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paul B Mahol X-Patchwork-Id: 41600 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a05:6a20:ba91:b0:105:feb:71f2 with SMTP id fb17csp2130pzb; Fri, 12 May 2023 14:47:20 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6XZgzifF8kDgdKXxaoRRGPfEY8MpE462+WXPtgbkMvjTRTgtiuli7opFaw5UbeoAk5Ponr X-Received: by 2002:aa7:c7da:0:b0:50b:c693:70af with SMTP id o26-20020aa7c7da000000b0050bc69370afmr18801094eds.2.1683928040103; Fri, 12 May 2023 14:47:20 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1683928040; cv=none; d=google.com; s=arc-20160816; b=L1HrO3Als5kx6jhn182IPtBnERvzMw08j4fPK0Jb0A8LTAkIDwl94dKIa3Xn3wPrk6 AZkFk8V6GeC14gY5dB92kc2lKXEYDYdK06IFUkvzuYp/zK/whHOv/TnN7OViRr9B09fa bSfbHKEhQXjTq+0c4OkGyDHPBD1ZLC/Y8fY3jEho6yGhEYNC8mmP2Ge8tlGXfe2VJgVm lZ7zuv5c6qF//NeTvtKRz26xxtgc3fW9InzAhH35sZMhQbP1YFLBDUef56A2rIdIiu/N yPtDJqqcZCgYX3GbnHRaoZ6waTCrkFysYmwO7JF47dRZX3mrwD3wbBIs817wy0GOoAwP zvoQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:subject:to :message-id:date:from:mime-version:dkim-signature:delivered-to; bh=Ohrp+nSb4hnzESDWO+2maYr/U7oi7X6vFWbXXxZXcl4=; b=q0iR5ETxKACRYokLpbCnnJEWNw6+CVHM/hlBrjCJMJxPaKi2sAAp0Z5kBfTCU9EA3Z RqqEm/6OBbQwU3PwZwPrSVPpJ1ZDjw/3S01aXNn1ivYbdoAMynbfZQAocvDnuhd366T9 Fmetw060en9lHEkn4E21/lKh9xe7mc+v50uywzPxka42ZCpKbFjwe7TiPHHkjF3pC+S2 Lp+zjOhkwa8FANxdWYB/21QVDcUyLU8yzgPsxyIB86O3LUEtDr8FibJTmVtKPsapQVP/ k9H4uCIbOAQ9BVX8CWseHK2Slj0TxjIrRy1OBbyBS8Rh1g4+7k1pFgWqgXEbBgnsAvK6 WDkg== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@gmail.com header.s=20221208 header.b=IOPTG11d; 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=gmail.com Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org. [79.124.17.100]) by mx.google.com with ESMTP id u2-20020aa7d0c2000000b005068437bfb4si6661318edo.333.2023.05.12.14.47.19; Fri, 12 May 2023 14:47:20 -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=@gmail.com header.s=20221208 header.b=IOPTG11d; 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=gmail.com Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 68D0E68C099; Sat, 13 May 2023 00:47:15 +0300 (EEST) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-vs1-f41.google.com (mail-vs1-f41.google.com [209.85.217.41]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 50F8C68BECE for ; Sat, 13 May 2023 00:47:08 +0300 (EEST) Received: by mail-vs1-f41.google.com with SMTP id ada2fe7eead31-434839b4544so3055818137.1 for ; Fri, 12 May 2023 14:47:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1683928026; x=1686520026; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=4CKYMqBIYa+CvJ7klnjIbt6KjuyfXuJCX0MLLWEmo8c=; b=IOPTG11d60l1dH/fUXNDAYL2xqkTndf5jJU2HQsYvBAXvEjWpOHz+ty/5//EnbtmV/ oxb6KMN60pzInb0FaXt/6NWPNBlTjpkpNJO5NHRe9MKWmsaeyrhAXSkv6/z6wnePX8rI YwwRBguGO9/VnTRndZgWZO51f/9g7CBnhCF1RfOP+n++7wPK111+GYWViMCrEMXARz/O +zbSHAgSTItre6E0DXlRPcncqEMb00Z1QGDI+c4T8gKvC6lum7ynAAMegn/A8zeuvEfF 3pjvPA5ve0s07UlpJyS6VzORjkqjliWNcF3S8PDS5eJX6ac+S73Zew6EH6CPu5+J46RL mbcA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1683928026; x=1686520026; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=4CKYMqBIYa+CvJ7klnjIbt6KjuyfXuJCX0MLLWEmo8c=; b=P3pB53TE0otpDJ1VPmq/ap3DG20AcyiKxoblnyyCbLFhvoQwLsFRAjOxzqhm/h235H /Mw7F30RiKuC0YpK14fZGc459nlAZcSji6MLCDelh3g2leZ4voNecBIK8HOcvJdPAJoX CIx4CZ04wYO/G8RlrTGxlQDAfwemNNVMTYSSW+B9w3QF4zLok7mtxZfH0elWr4bM6OZR 3wkrXFu9t+ELuIaWhEI+nKcCkH3cVEY/scPCDkmL7xB5VozvUepXLY3wTMtrcxNa6xXY gDIdwYWCucrtK2qgQBKYc8dWD8dLLpwqTbj+mDZHa0zygB4SULSLeVE2ETGKBqUVuT3z CXUA== X-Gm-Message-State: AC+VfDzTG8IApzKG6rz4QV94PR6DtJZxcOmPgjJuKxm1aPBh/VNQ9ynz gKO3BrIoazE/q8L+axPY1UIppRWYts5vM5J3tX2e0js5 X-Received: by 2002:a67:eb53:0:b0:434:6958:cdbf with SMTP id x19-20020a67eb53000000b004346958cdbfmr10126511vso.18.1683928026099; Fri, 12 May 2023 14:47:06 -0700 (PDT) MIME-Version: 1.0 From: Paul B Mahol Date: Fri, 12 May 2023 23:46:34 +0200 Message-ID: To: FFmpeg development discussions and patches X-Content-Filtered-By: Mailman/MimeDel 2.1.29 Subject: [FFmpeg-devel] [PATCH] avcodec/elbg: fix integer overflows 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 Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" X-TUID: MftSp4DuJXLq Attached. From f02425ca7207be131a0a9afe4b932fda084b7065 Mon Sep 17 00:00:00 2001 From: Paul B Mahol Date: Fri, 12 May 2023 23:37:59 +0200 Subject: [PATCH] avcodec/elbg: fix integer overflows Signed-off-by: Paul B Mahol --- libavcodec/elbg.c | 51 ++++++++++++++++++++++++++++++----------------- 1 file changed, 33 insertions(+), 18 deletions(-) diff --git a/libavcodec/elbg.c b/libavcodec/elbg.c index d97a7bc3f9..50197e21bc 100644 --- a/libavcodec/elbg.c +++ b/libavcodec/elbg.c @@ -44,13 +44,13 @@ typedef struct cell_s { * ELBG internal data */ typedef struct ELBGContext { - int64_t error; + int error; int dim; int num_cb; int *codebook; cell **cells; - int64_t *utility; - int64_t *utility_inc; + int *utility; + int *utility_inc; int *nearest_cb; int *points; int *temp_points; @@ -75,9 +75,12 @@ static inline int distance_limited(int *a, int *b, int dim, int limit) { int i, dist=0; for (i=0; i limit) + int64_t distance = FFABS(a[i] - b[i]); + + distance *= distance; + if (dist >= limit - distance) return INT_MAX; + dist += distance; } return dist; @@ -97,8 +100,12 @@ static inline void vect_division(int *res, int *vect, int div, int dim) static int eval_error_cell(ELBGContext *elbg, int *centroid, cell *cells) { int error=0; - for (; cells; cells=cells->next) - error += distance_limited(centroid, elbg->points + cells->index*elbg->dim, elbg->dim, INT_MAX); + for (; cells; cells=cells->next) { + int distance = distance_limited(centroid, elbg->points + cells->index*elbg->dim, elbg->dim, INT_MAX); + if (error >= INT_MAX - distance) + return INT_MAX; + error += distance; + } return error; } @@ -178,10 +185,13 @@ static int simple_lbg(ELBGContext *elbg, int dist[2] = {distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX), distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX)}; int idx = dist[0] > dist[1]; - newutility[idx] += dist[idx]; + if (newutility[idx] >= INT_MAX - dist[idx]) + newutility[idx] = INT_MAX; + else + newutility[idx] += dist[idx]; } - return newutility[0] + newutility[1]; + return (newutility[0] >= INT_MAX - newutility[1]) ? INT_MAX : newutility[0] + newutility[1]; } static void get_new_centroids(ELBGContext *elbg, int huc, int *newcentroid_i, @@ -253,9 +263,9 @@ static void evaluate_utility_inc(ELBGContext *elbg) int64_t inc=0; for (int i = 0; i < elbg->num_cb; i++) { - if (elbg->num_cb * elbg->utility[i] > elbg->error) + if (elbg->num_cb * (int64_t)elbg->utility[i] > elbg->error) inc += elbg->utility[i]; - elbg->utility_inc[i] = inc; + elbg->utility_inc[i] = FFMIN(inc, INT_MAX); } } @@ -278,7 +288,7 @@ static void update_utility_and_n_cb(ELBGContext *elbg, int idx, int newutility) */ static void try_shift_candidate(ELBGContext *elbg, int idx[3]) { - int j, k, cont=0; + int j, k, cont=0, tmp; int64_t olderror=0, newerror; int newutility[3]; int *newcentroid[3] = { @@ -305,12 +315,17 @@ static void try_shift_candidate(ELBGContext *elbg, int idx[3]) get_new_centroids(elbg, idx[1], newcentroid[0], newcentroid[1]); newutility[2] = eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[0]]); - newutility[2] += eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[2]]); + tmp = eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[2]]); + newutility[2] = (tmp >= INT_MAX - newutility[2]) ? INT_MAX : newutility[2] + tmp; newerror = newutility[2]; - newerror += simple_lbg(elbg, elbg->dim, newcentroid, newutility, elbg->points, + tmp = simple_lbg(elbg, elbg->dim, newcentroid, newutility, elbg->points, elbg->cells[idx[1]]); + if (tmp >= INT_MAX - newerror) + newerror = INT_MAX; + else + newerror += tmp; if (olderror > newerror) { shift_codebook(elbg, idx, newcentroid); @@ -334,7 +349,7 @@ static void do_shiftings(ELBGContext *elbg) evaluate_utility_inc(elbg); for (idx[0]=0; idx[0] < elbg->num_cb; idx[0]++) - if (elbg->num_cb * elbg->utility[idx[0]] < elbg->error) { + if (elbg->num_cb * (int64_t)elbg->utility[idx[0]] < elbg->error) { if (elbg->utility_inc[elbg->num_cb - 1] == 0) return; @@ -352,9 +367,9 @@ static void do_elbg(ELBGContext *av_restrict elbg, int *points, int numpoints, int *const size_part = elbg->size_part; int i, j, steps = 0; int best_idx = 0; - int64_t last_error; + int last_error; - elbg->error = INT64_MAX; + elbg->error = INT_MAX; elbg->points = points; do { @@ -382,7 +397,7 @@ static void do_elbg(ELBGContext *av_restrict elbg, int *points, int numpoints, } } elbg->nearest_cb[i] = best_idx; - elbg->error += best_dist; + elbg->error = elbg->error >= INT_MAX - best_dist ? INT_MAX : elbg->error + best_dist; elbg->utility[elbg->nearest_cb[i]] += best_dist; free_cells->index = i; free_cells->next = elbg->cells[elbg->nearest_cb[i]]; -- 2.39.1