[FFmpeg-devel] [PATCH] avcodec/elbg: fix integer overflows

* [FFmpeg-devel] [PATCH] avcodec/elbg: fix integer overflows
@ 2023-05-12 21:46 Paul B Mahol
  2023-05-12 22:07 ` Leo Izen
                   ` (2 more replies)
  0 siblings, 3 replies; 6+ messages in thread
From: Paul B Mahol @ 2023-05-12 21:46 UTC (permalink / raw)
  To: FFmpeg development discussions and patches

[-- Attachment #1: Type: text/plain, Size: 10 bytes --]

Attached.

[-- Attachment #2: 0001-avcodec-elbg-fix-integer-overflows.patch --]
[-- Type: text/x-patch, Size: 5481 bytes --]

From f02425ca7207be131a0a9afe4b932fda084b7065 Mon Sep 17 00:00:00 2001
From: Paul B Mahol <onemda@gmail.com>
Date: Fri, 12 May 2023 23:37:59 +0200
Subject: [PATCH] avcodec/elbg: fix integer overflows

Signed-off-by: Paul B Mahol <onemda@gmail.com>
---
 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<dim; i++) {
-        dist += (a[i] - b[i])*(a[i] - b[i]);
-        if (dist > 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


[-- Attachment #3: Type: text/plain, Size: 251 bytes --]

_______________________________________________
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".

^ permalink raw reply	[flat|nested] 6+ messages in thread