PR #25876 opened by thardin
URL: https://code.ffmpeg.org/FFmpeg/FFmpeg/pulls/25876
Patch URL: https://code.ffmpeg.org/FFmpeg/FFmpeg/pulls/25876.patch

This patchset adds a k-d tree implementation and speeds up all users of 
libavcodec/elbg.c. The speedups are as follows:

* cinepakenc: +32%
* roqvideoenc: +29%
* msvideo1enc: +12%
* a64multienc: +23%
* vf_elbg: +218%

As measured by this script on an Intel i5-2520M @ 2.50GHz:

```bash
set -e

encoders=(cinepak roqvideo msvideo1 a64multi)
containers=(avi roq avi a64)
# Durations picked so that the amount of time per test is ~30 seconds
durations=(8.9 23.7 218.6 195.3)

CSV=timings.csv
rm -f $CSV

for commit in 0f89d936b39e1cb438a874ecfccffe253be6b63b 
e467c7179a4677ff5db6b0fc9485c8c4799a6a16
do
  git checkout $commit
  nice make -j3 ffmpeg
  for i in "${!encoders[@]}"
  do
    echo $commit ${encoders[i]}
    # 256x256 so that all encoders can use the same resolution
    T=$(/bin/time -f %U -o /dev/stdout ./ffmpeg -f lavfi -i 
testsrc=s=256x256:r=15:d=${durations[i]} -vcodec ${encoders[i]} -an -y 
/tmp/${encoders[i]}.${containers[i]})
    echo -n "$T," >> $CSV
  done
  T=$(/bin/time -f %U -o /dev/stdout ./ffmpeg -loglevel quiet -f lavfi -i 
testsrc=d=20.3,elbg -vcodec rawvideo -f null -)
  echo "$T" >> $CSV
done
```

Besides speeding up avcodec/elbg, avcodec/kdtree is also useful in cases where 
fast lookup in an existing codebook is desired. One example would be 
vf_paletteuse.


From 340c91b8a615a1d96dc7bf73592fbc7362c2ccef Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Tomas=20H=C3=A4rdin?= <[email protected]>
Date: Sun, 8 Nov 2026 20:16:44 +0100
Subject: [PATCH 1/8] avcodec/msvideo1enc: Compute average instead of using
 ELBG

Calling avpriv_elbg_do() is excessive for this simple operation
---
 libavcodec/msvideo1enc.c | 19 +++++++++++++++----
 1 file changed, 15 insertions(+), 4 deletions(-)

diff --git a/libavcodec/msvideo1enc.c b/libavcodec/msvideo1enc.c
index b1cae720814..cb95be0923f 100644
--- a/libavcodec/msvideo1enc.c
+++ b/libavcodec/msvideo1enc.c
@@ -65,6 +65,17 @@ enum MSV1Mode{
 
 static const int remap[16] = { 0, 1, 4, 5, 2, 3, 6, 7, 8, 9, 12, 13, 10, 11, 
14, 15 };
 
+static void compute_average(Msvideo1EncContext *c) {
+    for (int color = 0; color < 3; color++) {
+        int tot = 0;
+        for (int x = 0; x < 16; x++) {
+            tot += c->block[x*3 + color];
+        }
+        // replicate elbg.c's use of ROUNDED_DIV()
+        c->avg[color] = (tot + 8) / 16;
+    }
+}
+
 static int encode_frame(AVCodecContext *avctx, AVPacket *pkt,
                                const AVFrame *pict, int *got_packet)
 {
@@ -121,10 +132,10 @@ static int encode_frame(AVCodecContext *avctx, AVPacket 
*pkt,
             }
             // try to find optimal value to fill whole 4x4 block
             score = 0;
-            ret = avpriv_elbg_do(&c->elbg, c->block, 3, 16, c->avg,
-                                 1, 1, c->output, &c->rnd, 0);
-            if (ret < 0)
-                return ret;
+
+            // This is way faster than calling avpriv_elbg_do() just to get 
the average color
+            compute_average(c);
+
             if(c->avg[0] == 1) // red component = 1 will be written as skip 
code
                 c->avg[0] = 0;
             for(j = 0; j < 4; j++){
-- 
2.54.0


From 6f3fbf494bbb74f421ff1d192a9e8e6ec2aa0ca8 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Tomas=20H=C3=A4rdin?= <[email protected]>
Date: Sun, 8 Nov 2026 21:56:12 +0100
Subject: [PATCH 2/8] avfilter/vf_elbg: Don't uselessly quantize opaque alpha
 when use_alpha == 0

---
 libavfilter/vf_elbg.c | 19 +++++++++++--------
 1 file changed, 11 insertions(+), 8 deletions(-)

diff --git a/libavfilter/vf_elbg.c b/libavfilter/vf_elbg.c
index 040dc763d0a..9a7fc3a8a16 100644
--- a/libavfilter/vf_elbg.c
+++ b/libavfilter/vf_elbg.c
@@ -166,14 +166,17 @@ static int filter_frame(AVFilterLink *inlink, AVFrame 
*frame)
             elbg->codeword[k++] = p[b_idx];
             elbg->codeword[k++] = p[g_idx];
             elbg->codeword[k++] = p[r_idx];
-            elbg->codeword[k++] = elbg->use_alpha ? p[a_idx] : 0xff;
+            if (elbg->use_alpha) {
+                elbg->codeword[k++] = p[a_idx];
+            }
             p += elbg->pix_desc->nb_components;
         }
         p0 += frame->linesize[0];
     }
 
     /* compute the codebook */
-    ret = avpriv_elbg_do(&elbg->ctx, elbg->codeword, NB_COMPONENTS,
+    int dim = elbg->use_alpha ? NB_COMPONENTS : 3;
+    ret = avpriv_elbg_do(&elbg->ctx, elbg->codeword, dim,
                          elbg->codeword_length, elbg->codebook,
                          elbg->codebook_length, elbg->max_steps_nb,
                          elbg->codeword_closest_codebook_idxs, &elbg->lfg, 0);
@@ -197,11 +200,11 @@ static int filter_frame(AVFilterLink *inlink, AVFrame 
*frame)
         p0 = (uint8_t *)out->data[0];
 
         for (i = 0; i < elbg->codebook_length; i++) {
-            const unsigned al =  elbg->use_alpha ? elbg->codebook[i*4+3] : 
0xff;
-            pal[i] =  al                    << 24  |
-                     (elbg->codebook[i*4+2] << 16) |
-                     (elbg->codebook[i*4+1] <<  8) |
-                      elbg->codebook[i*4  ];
+            const unsigned al =  elbg->use_alpha ? elbg->codebook[i*dim+3] : 
0xff;
+            pal[i] =  al                      << 24  |
+                     (elbg->codebook[i*dim+2] << 16) |
+                     (elbg->codebook[i*dim+1] <<  8) |
+                      elbg->codebook[i*dim  ];
         }
 
         k = 0;
@@ -223,7 +226,7 @@ static int filter_frame(AVFilterLink *inlink, AVFrame 
*frame)
     for (i = 0; i < inlink->h; i++) {
         p = p0;
         for (j = 0; j < inlink->w; j++) {
-            int cb_idx = NB_COMPONENTS * 
elbg->codeword_closest_codebook_idxs[k++];
+            int cb_idx = dim * elbg->codeword_closest_codebook_idxs[k++];
             p[b_idx] = elbg->codebook[cb_idx];
             p[g_idx] = elbg->codebook[cb_idx+1];
             p[r_idx] = elbg->codebook[cb_idx+2];
-- 
2.54.0


From 6d057b8147a400332f9dbfd8612410b7cf767c07 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Tomas=20H=C3=A4rdin?= <[email protected]>
Date: Mon, 2 Nov 2026 11:05:41 +0100
Subject: [PATCH 3/8] avcodec/elbg: Constify points

---
 libavcodec/elbg.c | 14 +++++++-------
 libavcodec/elbg.h |  2 +-
 2 files changed, 8 insertions(+), 8 deletions(-)

diff --git a/libavcodec/elbg.c b/libavcodec/elbg.c
index 34d03d416e7..c99879040af 100644
--- a/libavcodec/elbg.c
+++ b/libavcodec/elbg.c
@@ -53,7 +53,7 @@ typedef struct ELBGContext {
     int *utility;
     int *utility_inc;
     int *nearest_cb;
-    int *points;
+    const int *points;
     int *temp_points;
     int *size_part;
     AVLFG *rand_state;
@@ -72,7 +72,7 @@ typedef struct ELBGContext {
     unsigned temp_points_allocated;
 } ELBGContext;
 
-static inline int distance_limited(int *a, int *b, int dim, int limit)
+static inline int distance_limited(const int *a, const int *b, int dim, int 
limit)
 {
     int i, dist=0;
     for (i=0; i<dim; i++) {
@@ -87,7 +87,7 @@ static inline int distance_limited(int *a, int *b, int dim, 
int limit)
     return dist;
 }
 
-static inline void vect_division(int *res, int *vect, int div, int dim)
+static inline void vect_division(int *res, const int *vect, int div, int dim)
 {
     int i;
     if (div > 1)
@@ -155,7 +155,7 @@ static int simple_lbg(ELBGContext *elbg,
                       int dim,
                       int *centroid[3],
                       int newutility[3],
-                      int *points,
+                      const int *points,
                       cell *cells)
 {
     int i, idx;
@@ -362,7 +362,7 @@ static void do_shiftings(ELBGContext *elbg)
         }
 }
 
-static void do_elbg(ELBGContext *restrict elbg, int *points, int numpoints,
+static void do_elbg(ELBGContext *restrict elbg, const int *points, int 
numpoints,
                     int max_steps)
 {
     int *const size_part = elbg->size_part;
@@ -436,7 +436,7 @@ static void do_elbg(ELBGContext *restrict elbg, int 
*points, int numpoints,
  * If not, it calls do_elbg for a (smaller) random sample of the points in
  * points.
  */
-static void init_elbg(ELBGContext *restrict elbg, int *points, int 
*temp_points,
+static void init_elbg(ELBGContext *restrict elbg, const int *points, int 
*temp_points,
                       int numpoints, int max_steps)
 {
     int dim = elbg->dim;
@@ -460,7 +460,7 @@ static void init_elbg(ELBGContext *restrict elbg, int 
*points, int *temp_points,
                    dim * sizeof(*elbg->codebook));
 }
 
-int avpriv_elbg_do(ELBGContext **elbgp, int *points, int dim, int numpoints,
+int avpriv_elbg_do(ELBGContext **elbgp, const int *points, int dim, int 
numpoints,
                    int *codebook, int num_cb, int max_steps,
                    int *closest_cb, AVLFG *rand_state, uintptr_t flags)
 {
diff --git a/libavcodec/elbg.h b/libavcodec/elbg.h
index 34d96846b15..e1ddb50e616 100644
--- a/libavcodec/elbg.h
+++ b/libavcodec/elbg.h
@@ -45,7 +45,7 @@ struct ELBGContext;
  * @param flags Currently unused; must be set to 0.
  * @return < 0 in case of error, 0 otherwise
  */
-int avpriv_elbg_do(struct ELBGContext **ctx, int *points, int dim,
+int avpriv_elbg_do(struct ELBGContext **ctx, const int *points, int dim,
                    int numpoints, int *codebook, int num_cb, int num_steps,
                    int *closest_cb, AVLFG *rand_state, uintptr_t flags);
 
-- 
2.54.0


From daa1bfbe728b57eb8d0bdb8d4ec388ebbfdd77eb Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Tomas=20H=C3=A4rdin?= <[email protected]>
Date: Fri, 6 Nov 2026 15:42:06 +0100
Subject: [PATCH 4/8] avcodec/elbg: Restrict value range to [0,255]

Restricting the range to what is actually used limits
the range for squared distances between points.
Current users have value ranges as follows:

    a64multienc     [0,255]
    cinepakenc      [0,255]
    msvideo1enc     [0,31]
    roqvideoenc     [0,255]
    vf_elbg         [0,255]
---
 libavcodec/elbg.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/libavcodec/elbg.h b/libavcodec/elbg.h
index e1ddb50e616..59b22af8129 100644
--- a/libavcodec/elbg.h
+++ b/libavcodec/elbg.h
@@ -34,7 +34,7 @@ struct ELBGContext;
  * @param ctx  A pointer to a pointer to an already allocated ELBGContext
  *             or a pointer to NULL. In the latter case, this function
  *             will allocate an ELBGContext and put a pointer to it in `*ctx`.
- * @param points Input points.
+ * @param points Input points. Must be in the range [0,255].
  * @param dim Dimension of the points.
  * @param numpoints Num of points in **points.
  * @param codebook Pointer to the output codebook. Must be allocated.
-- 
2.54.0


From ff7c3ce2455f14d9ee5200916eb971d06d3cb8f9 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Tomas=20H=C3=A4rdin?= <[email protected]>
Date: Fri, 6 Nov 2026 16:46:04 +0100
Subject: [PATCH 5/8] avcodec/kdtree: Add k-d tree implementation

This makes use of a number of tricks:

* codebook points are deduplicated
* a fast approximate median algorithm is used
* the "gap" between tree branches is maximized (gap between sets along 
splitting axis)
* loops are removed where possible
* queries are terminated when distance == 0
---
 libavcodec/kdtree.c | 470 ++++++++++++++++++++++++++++++++++++++++++++
 libavcodec/kdtree.h |  98 +++++++++
 2 files changed, 568 insertions(+)
 create mode 100644 libavcodec/kdtree.c
 create mode 100644 libavcodec/kdtree.h

diff --git a/libavcodec/kdtree.c b/libavcodec/kdtree.c
new file mode 100644
index 00000000000..c50a3b58ead
--- /dev/null
+++ b/libavcodec/kdtree.c
@@ -0,0 +1,470 @@
+/*
+ * Copyright (C) 2026 Tomas Härdin <[email protected]>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/**
+ * @file
+ * K-d tree implementation intended for speeding up VQ codebook lookups
+ */
+
+#include <stdlib.h>
+
+#include "libavutil/avassert.h"
+#include "libavutil/common.h"
+#include "libavutil/mem.h"
+#include "kdtree.h"
+
+#define SORT2(a, b) do { if (a > b) FFSWAP(int, a, b); } while (0)
+
+static int kdtree_median5(int a, int b, int c, int d, int e) {
+    // https://arxiv.org/pdf/1405.5754.pdf page 10
+    SORT2(a, b);
+    SORT2(c, d);
+    SORT2(a, c);
+    SORT2(b, d);
+    SORT2(b, c);
+    SORT2(d, e);
+    SORT2(b, d);
+    //SORT2(a, b);  // not necessary
+    SORT2(c, d);
+    return c;
+}
+
+/**
+ * Computes approximate median by computing median-of-medians
+ */
+static int kdtree_median(KDTree *kdtree, int D, int start, int end) {
+    int n = end - start, m = n / 5;
+    int a, b, c, d, e;
+
+    a = kdtree->dedup_codebook[kdtree->partmap[start]].point[D];
+    if (n >= 2) b = kdtree->dedup_codebook[kdtree->partmap[start + 
1]].point[D];
+    if (n >= 3) c = kdtree->dedup_codebook[kdtree->partmap[start + 
2]].point[D];
+    if (n >= 4) d = kdtree->dedup_codebook[kdtree->partmap[start + 
3]].point[D];
+    if (n >= 5) e = kdtree->dedup_codebook[kdtree->partmap[start + 
4]].point[D];
+
+    switch (n) {
+    case 1:
+        return a;
+    case 2:
+        // Round up because we split on < and >=
+        return (a + b + 1)/2;
+    case 3:
+        SORT2(a, b);
+        SORT2(b, c);
+        SORT2(a, b);
+        return b;
+    case 4:
+        SORT2(a, c);
+        SORT2(b, d);
+        SORT2(a, b);
+        SORT2(c, d);
+        // Final SORT2(b, c) is not necessary
+        return (b + c + 1) / 2;
+    case 5:
+        return kdtree_median5(a, b, c, d, e);
+    default:
+        // This could maybe use better range rounding,
+        // for example when n=9, but it works
+        a = kdtree_median(kdtree, D, start,       start + m);
+        b = kdtree_median(kdtree, D, start +   m, start + 2*m);
+        c = kdtree_median(kdtree, D, start + 2*m, start + 3*m);
+        d = kdtree_median(kdtree, D, start + 3*m, start + 4*m);
+        e = kdtree_median(kdtree, D, start + 4*m, end);
+        return kdtree_median5(a, b, c, d, e);
+    }
+}
+
+/**
+ * Counts number of points less than, equal to and greater than the given 
median value
+ */
+static void kdtree_count(KDTree *kdtree, int D, int start, int end, int m, int 
*lt, int *eq, int *gt) {
+    *lt = 0;
+    *eq = 0;
+    *gt = 0;
+
+    for (int x = start; x < end; x++) {
+        int v = kdtree->dedup_codebook[kdtree->partmap[x]].point[D];
+
+        if (v < m) {
+            (*lt)++;
+        } else if (v == m) {
+            (*eq)++;
+        } else {
+            (*gt)++;
+        }
+    }
+}
+
+/**
+ * Returns largest value < m and smallest value >= m
+ */
+static void kdtree_compute_gap(KDTree *kdtree, int D, int start, int end, int 
m, int *lo_max, int *hi_min) {
+    *lo_max = INT_MIN;
+    *hi_min = INT_MAX;
+
+    for (int x = start; x < end; x++) {
+        int v = kdtree->dedup_codebook[kdtree->partmap[x]].point[D];
+
+        if (v < m && v > *lo_max) {
+            *lo_max = v;
+        } else if (v >= m && v < *hi_min) {
+            *hi_min = v;
+        }
+    }
+}
+
+/**
+ * Partitions [start,end) and updates partmap
+ */
+static void kdtree_do_partition(KDTree *kdtree, int D, int start, int end, int 
m, int lo_cnt) {
+    int hi_x = lo_cnt;
+
+    for (int x = 0; x < lo_cnt; x++) {
+        // Partition the range by swapping elements that are out of place
+        int lo_v = kdtree->dedup_codebook[kdtree->partmap[start + x]].point[D];
+
+        if (lo_v >= m) {
+            // Find a replacement. This is guaranteed to work
+            for (;; hi_x++) {
+                av_assert2(hi_x < end - start);
+
+                int hi_v = kdtree->dedup_codebook[kdtree->partmap[start + 
hi_x]].point[D];
+
+                if (hi_v < m) {
+                    FFSWAP(int, kdtree->partmap[start + x], 
kdtree->partmap[start + hi_x]);
+                    // After the swap both x and hi_x are correct
+                    hi_x++;
+                    break;
+                }
+            }
+        }
+    }
+}
+
+/**
+ * Comparator for qsort() and deduplication
+ */
+static int kdtree_compare(const void *a, const void *b) {
+    const KDDedupEntry *da = a;
+    const KDDedupEntry *db = b;
+
+    return memcmp(da->point, db->point, da->dim*sizeof(da->point[0]));
+}
+
+/**
+ * Finds a plane that will split the codebook points into two non-empty sets.
+ * Also tries to maximize the gap between the two sets of points.
+ */
+static void kdtree_get_splitting_plane(KDTree *kdtree, int start, int end, int 
*best_D, int *best_m, int *best_lt, int *best_lo_max, int *best_hi_min) {
+    int best_gap = INT_MIN;
+
+    for (int D = 0; D < kdtree->dim; D++) {
+        // Compute an approximate median, then adjust it if necessary
+        int m = kdtree_median(kdtree, D, start, end);
+
+        int lt, eq, gt;
+        kdtree_count(kdtree, D, start, end, m, &lt, &eq, &gt);
+
+        /**
+         * m is either equal to some value, or sits between two values.
+         * Therefore the possibilities/actions for zeroes in lt, eq and gt are:
+         *
+         * lt   eq  gt  Comment
+         * 0    0   0   Not possible
+         * 0    0   +   Not possible
+         * 0    +   0   All points lie on the median line in this dimension. 
We must try another dimension.
+         *               We are guaranteed to find a suitable dimension due to 
point uniqueness
+         * 0    +   +   Incrementing m will separate eq and gt. We can then 
proceed
+         * +    0   0   Not possible
+         * +    0   +   Proceed
+         * +    +   0   Proceed
+         * +    +   +   Check if we can balance both branches by incrementing 
m. Then proceed
+         */
+        av_assert2(lt + eq + gt > 0);
+        av_assert2(eq + gt > 0);
+
+        if (lt == 0) {
+            av_assert2(eq > 0);
+
+            if (gt > 0) {
+                // Increasing m is enough to split the points
+                m++;
+                // Ensure that we have correct less-than count for 
kdtree_do_partition()
+                lt = eq;
+            } else {
+                // All points == m
+                // Try another dimension
+                // We are guaranteed to find one becaues of point uniqueness
+                continue;
+            }
+        } else {
+            // We have points on both sides of the split
+            // Check if we can improve lo/hi balance by incrementing m
+            if (FFABS(lt + eq - gt) < FFABS(lt - eq - gt)) {
+                m++;
+                lt += eq;
+            }
+        }
+
+        // This is more upfront work compared to just
+        // picking whichever dimension works first,
+        // but a larger gap speeds up avpriv_kdtree_query()
+        int lo_max, hi_min;
+        kdtree_compute_gap(kdtree, D, start, end, m, &lo_max, &hi_min);
+
+        if (hi_min - lo_max > best_gap) {
+            best_gap = hi_min - lo_max;
+            *best_D = D;
+            *best_m = m;
+            *best_lt = lt;
+            *best_lo_max = lo_max;
+            *best_hi_min = hi_min;
+        }
+    }
+}
+
+static int kdtree_partition(KDTree *kdtree, int node, int start, int end) {
+    if (end - start <= KDTREE_LEAF_SIZE) {
+        // Copy point data so as to not require indirection in 
avpriv_kdtree_query()
+        kdtree->nodes[node].D = -1;
+#if KDTREE_LEAF_SIZE > 1
+        kdtree->nodes[node].u.leaf.num_points = end - start;
+#endif
+
+#if KDTREE_LEAF_SIZE == 1
+        int x = 0;
+#else
+        for (int x = 0; x < end - start; x++)
+#endif
+        {
+            KDDedupEntry *dedup = 
&kdtree->dedup_codebook[kdtree->partmap[start + x]];
+            kdtree->nodes[node].u.leaf.indices[x] = dedup->index;
+
+            memcpy(
+                kdtree->nodes[node].u.leaf.points[x],
+                dedup->point,
+                kdtree->dim * sizeof(dedup->point[0])
+            );
+        }
+
+        return 1;
+    } else {
+        int m, D, lt, lo_max, hi_min;
+
+        kdtree_get_splitting_plane(kdtree, start, end, &D, &m, &lt, &lo_max, 
&hi_min);
+        kdtree_do_partition(kdtree, D, start, end, m, lt);
+
+        int lo_cnt = kdtree_partition(kdtree, node + 1,          start,        
start + lt);
+        int hi_cnt = kdtree_partition(kdtree, node + 1 + lo_cnt, start + lt,   
end);
+
+        kdtree->nodes[node].D = D;
+        kdtree->nodes[node].u.plane.lo_max = lo_max;
+        kdtree->nodes[node].u.plane.hi_min = hi_min;
+        kdtree->nodes[node].u.plane.lo_cnt = lo_cnt;
+
+        return 1 + lo_cnt + hi_cnt;
+    }
+}
+
+int avpriv_kdtree_create(KDTree *kdtree, const int *codebook, int num_cb, int 
dim) {
+    if (num_cb > KDTREE_MAX_CB || dim > KDTREE_MAX_CB) {
+        return AVERROR(EINVAL);
+    }
+
+    kdtree->dim = dim;
+
+    // Sort codebook and remove duplicates
+    for (int x = 0; x < num_cb; x++) {
+        kdtree->dedup_codebook[x].index = x;
+        kdtree->dedup_codebook[x].dim = dim;
+        memcpy(kdtree->dedup_codebook[x].point, codebook + x*dim, 
dim*sizeof(*codebook));
+    }
+
+    // We could maybe gain some performance by writing a custom sort that
+    // removes duplicates as it runs across them. Keep it simple for now
+    qsort(kdtree->dedup_codebook, num_cb, sizeof(kdtree->dedup_codebook[0]), 
kdtree_compare);
+
+    int unique = 1;
+    for (int x = 1; x < num_cb; x++) {
+        if (kdtree_compare(&kdtree->dedup_codebook[unique-1], 
&kdtree->dedup_codebook[x])) {
+            memmove(&kdtree->dedup_codebook[unique], 
&kdtree->dedup_codebook[x], sizeof(kdtree->dedup_codebook[0]));
+            unique++;
+        }
+    }
+
+    for (int x = 0; x < unique; x++) {
+        kdtree->partmap[x] = x;
+    }
+
+    // All codebook points are now unique, which makes some of the following 
logic simpler
+    (void)kdtree_partition(kdtree, 0, 0, unique);
+
+    return 0;
+}
+
+#define KDTREE_SQUARE_DIST_TEMPLATE(dim) \
+static int kdtree_square_dist_ ## dim(const int *a, const int *b) { \
+    int ret = 0; \
+    for (int x = 0; x < dim; x++) { \
+        int diff = a[x] - b[x]; \
+        ret += diff*diff; \
+    } \
+    return ret; \
+}
+
+/**
+ * Dimensionality of users:
+ *
+ *  a64multienc.c   32
+ *  cinepakenc.c    4, 6
+ *  roqvideoenc.c   6, 24
+ *  vf_elbg.c       3, 4
+ */
+KDTREE_SQUARE_DIST_TEMPLATE(3)
+KDTREE_SQUARE_DIST_TEMPLATE(4)
+KDTREE_SQUARE_DIST_TEMPLATE(6)
+KDTREE_SQUARE_DIST_TEMPLATE(24)
+KDTREE_SQUARE_DIST_TEMPLATE(32)
+
+static int kdtree_square_dist(const int *a, const int *b, int dim) {
+    // ret <= KDTREE_MAX_DIM * 255 * 255 = 2080800
+    int ret = 0;
+
+    // There's no benefit to implementing a limit like distance_limited() in 
elbg.c here
+    for (int x = 0; x < dim; x++) {
+        int diff = a[x] - b[x];
+        ret += diff*diff;
+    }
+
+    return ret;
+}
+
+static void kdtree_query(const KDTree *kdtree, const int *point, int 
*bestdist, int *bestidx, int n) {
+    const KDNode *node = &kdtree->nodes[n];
+
+    if (node->D < 0) {
+        // Leaf
+#if KDTREE_LEAF_SIZE == 1
+        int x = 0;
+#else
+        for (int x = 0; x < node->u.leaf.num_points; x++)
+#endif
+        {
+            int dist;
+
+            // Pick an optimized distance routine based on dimension
+            if (kdtree->dim == 3) {
+                dist = kdtree_square_dist_3(point, node->u.leaf.points[x]);
+            } else if (kdtree->dim == 4) {
+                dist = kdtree_square_dist_4(point, node->u.leaf.points[x]);
+            } else if (kdtree->dim == 6) {
+                dist = kdtree_square_dist_6(point, node->u.leaf.points[x]);
+            } else if (kdtree->dim == 24) {
+                dist = kdtree_square_dist_24(point, node->u.leaf.points[x]);
+            } else if (kdtree->dim == 32) {
+                dist = kdtree_square_dist_32(point, node->u.leaf.points[x]);
+            } else {
+                // Fall back to generic implementation
+                dist = kdtree_square_dist(point, node->u.leaf.points[x], 
kdtree->dim);
+            }
+
+            if (dist < *bestdist) {
+                *bestidx = node->u.leaf.indices[x];
+                *bestdist = dist;
+            }
+        }
+    } else {
+        int v = point[node->D];
+        int side;
+
+        if (v <= node->u.plane.lo_max) {
+            side = 0;
+        } else if (v >= node->u.plane.hi_min) {
+            side = 1;
+        } else {
+            // Descend into whichever branch is closest,
+            // unless there's no point in going further
+            int lodist = v - node->u.plane.lo_max;
+            int hidist = node->u.plane.hi_min - v;
+
+            if ((*bestdist) <= lodist * lodist &&
+                (*bestdist) <= hidist * hidist) {
+                // The sphere around us doesn't extend past the gap
+                // No need to search further
+                return;
+            }
+
+            // Tie break towards lower side for cache coherence reasons (<= 
instead of <)
+            if (lodist <= hidist) {
+                side = 0;
+            } else {
+                side = 1;
+            }
+        }
+
+        if (side == 0) {
+            kdtree_query(kdtree, point, bestdist, bestidx, n + 1);
+
+            if (*bestdist == 0) {
+                return;
+            }
+
+            // Whether to descend into the upper side depends on
+            // the distance to the upper splitting plane.
+            // This is why hi_min is computed rather than
+            // only relying on the median.
+            // We could do better by clipping against the planes
+            // from upper levels in the call stack.
+            // In some cases we may get a lower-dimensional thing
+            // like a line or even a point to test against,
+            // instead of only the splitting plane.
+            // For now do the simplest thing.
+            int dv = point[node->D] - node->u.plane.hi_min;
+
+            if (dv*dv < *bestdist) {
+                kdtree_query(kdtree, point, bestdist, bestidx, n + 1 + 
node->u.plane.lo_cnt);
+            }
+        } else {
+            kdtree_query(kdtree, point, bestdist, bestidx, n + 1 + 
node->u.plane.lo_cnt);
+
+            if (*bestdist == 0) {
+                return;
+            }
+
+            int dv = point[node->D] - node->u.plane.lo_max;
+
+            if (dv*dv < *bestdist) {
+                kdtree_query(kdtree, point, bestdist, bestidx, n + 1);
+            }
+        }
+    }
+}
+
+void avpriv_kdtree_query(const KDTree *kdtree, const int *points, int 
numpoints, int *indices, int *best_dists) {
+    for (int x = 0; x < numpoints; x++) {
+        int bestdist = INT_MAX; // We are guaranteed to find a point better 
than this
+
+        kdtree_query(kdtree, points + x * kdtree->dim, &bestdist, indices + x, 
0);
+
+        if (best_dists) {
+            best_dists[x] = bestdist;
+        }
+    }
+}
diff --git a/libavcodec/kdtree.h b/libavcodec/kdtree.h
new file mode 100644
index 00000000000..4f1cb67a3f5
--- /dev/null
+++ b/libavcodec/kdtree.h
@@ -0,0 +1,98 @@
+/*
+ * Copyright (C) 2026 Tomas Härdin <[email protected]>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef AVCODEC_KDTREE_H
+#define AVCODEC_KDTREE_H
+
+#include <limits.h>
+
+/**
+ * Max dimension and codebook size of current ELBG users:
+ *
+ *                  dim num_cb  Comment
+ *  a64multienc.c   32  256
+ *  cinepakenc.c    6   256
+ *  msvideo1enc.c   3   2       Does not use k-d tree due to small codebook 
size
+ *  roqvideoenc.c   24  256
+ *  vf_elbg.c       4   INT_MAX
+ */
+#define KDTREE_MAX_DIM      32  ///< Maximum number of dimensions
+#define KDTREE_MAX_CB       256 ///< Maximum number of codebook entries. 
Should be a power of two for performance reasons
+#define KDTREE_LEAF_SIZE    1   ///< Don't bother splitting nodes of this size 
or smaller. Verified fastest with valgrind and time
+#define KDTREE_POINT_MAX    255 ///< Maximum value of a point. Coordinates 
must span [0,KDTREE_POINT_MAX]
+
+#if KDTREE_MAX_DIM * KDTREE_POINT_MAX * KDTREE_POINT_MAX > INT_MAX - 1
+#error KDTREE_MAX_DIM too large
+#endif
+
+typedef struct {
+    int D;              ///< Split dimension. <0 if leaf
+    union {
+        struct {
+            int lo_max; ///< Highest value on "low" side of plane
+            int hi_min; ///< Lowest value on "high" side of plane
+            int lo_cnt; ///< Number of nodes on "low" side of plane
+        } plane;
+        struct {
+            // num_points is not necessary when KDTREE_LEAF_SIZE == 1 but it 
seems to improve cache coherence
+            int num_points;                                 ///< 1 .. 
KDTREE_LEAF_SIZE
+            int points[KDTREE_LEAF_SIZE][KDTREE_MAX_DIM];   ///< Codebook 
vector points
+            int indices[KDTREE_LEAF_SIZE];                  ///< Original 
codebook indices
+        } leaf;
+    } u;
+} KDNode;
+
+typedef struct {
+    int index;                  ///< Index into input codebook
+    int dim;                    ///< Copy of dimensions. Needed due to lack of 
qsort_r()
+    int point[KDTREE_MAX_DIM];
+} KDDedupEntry;
+
+typedef struct KDTree {
+    int dim;
+    // TODO: Try to smush together dedup_codebook by having each entry be 
precisely (2 + dim)*sizeof(int) bytes
+    KDDedupEntry dedup_codebook[KDTREE_MAX_CB];
+    int partmap[KDTREE_MAX_CB]; ///< Maps partition indices to dedup_codebook 
indices
+    // Sized for worst-case scenario
+    KDNode nodes[2*KDTREE_MAX_CB-1];
+} KDTree;
+
+/**
+ * Creates a k-d tree from the given codebook.
+ * @param kdtree Pointer to already allocated KDTree.
+ * @param codebook Input codebook points. Must be in the range [0,255].
+ * @param num_cb Number of codebook points. Must be <= KDTREE_MAX_CB.
+ * @param dim Dimension of the codebook points. Must be <= KDTREE_MAX_DIM.
+ * @return < 0 in case of error, 0 otherwise
+ */
+int avpriv_kdtree_create(KDTree *kdtree, const int *codebook, int num_cb, int 
dim);
+
+/**
+ * Queries the closest points in the codebook given to avpriv_kdtree_create()
+ * to the given array of points.
+ * @param kdtree Pointer to KDTree created by avpriv_kdtree_create().
+ * @param points Points to quantize.
+ * @param numpoints Number of points.
+ * @param indices Indices of closest codebook entry for each input point.
+ * @param best_dists If non-NULL, store squared distances for each point here.
+ */
+void avpriv_kdtree_query(const KDTree *kdtree, const int *points, int 
numpoints, int *indices, int *best_dists);
+
+#endif /* AVCODEC_KDTREE_H */
-- 
2.54.0


From 023f0cbcfc5fd3eb153eca3de56dd9c5e82093e2 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Tomas=20H=C3=A4rdin?= <[email protected]>
Date: Sun, 8 Nov 2026 23:13:32 +0100
Subject: [PATCH 6/8] avfilter/vf_elbg: Limit -codebook_length to k-d tree
 limit

---
 libavfilter/vf_elbg.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/libavfilter/vf_elbg.c b/libavfilter/vf_elbg.c
index 9a7fc3a8a16..79e297c62e9 100644
--- a/libavfilter/vf_elbg.c
+++ b/libavfilter/vf_elbg.c
@@ -24,6 +24,7 @@
  */
 
 #include "libavcodec/elbg.h"
+#include "libavcodec/kdtree.h"
 #include "libavutil/mem.h"
 #include "libavutil/opt.h"
 #include "libavutil/pixdesc.h"
@@ -56,8 +57,8 @@ typedef struct ELBGFilterContext {
 #define FLAGS AV_OPT_FLAG_VIDEO_PARAM|AV_OPT_FLAG_FILTERING_PARAM
 
 static const AVOption elbg_options[] = {
-    { "codebook_length", "set codebook length", OFFSET(codebook_length), 
AV_OPT_TYPE_INT, { .i64 = 256 }, 1, INT_MAX, FLAGS },
-    { "l",               "set codebook length", OFFSET(codebook_length), 
AV_OPT_TYPE_INT, { .i64 = 256 }, 1, INT_MAX, FLAGS },
+    { "codebook_length", "set codebook length", OFFSET(codebook_length), 
AV_OPT_TYPE_INT, { .i64 = 256 }, 1, KDTREE_MAX_CB, FLAGS },
+    { "l",               "set codebook length", OFFSET(codebook_length), 
AV_OPT_TYPE_INT, { .i64 = 256 }, 1, KDTREE_MAX_CB, FLAGS },
     { "nb_steps", "set max number of steps used to compute the mapping", 
OFFSET(max_steps_nb), AV_OPT_TYPE_INT, { .i64 = 1 }, 1, INT_MAX, FLAGS },
     { "n",        "set max number of steps used to compute the mapping", 
OFFSET(max_steps_nb), AV_OPT_TYPE_INT, { .i64 = 1 }, 1, INT_MAX, FLAGS },
     { "seed", "set the random seed", OFFSET(lfg_seed), AV_OPT_TYPE_INT64, 
{.i64 = -1}, -1, UINT32_MAX, FLAGS },
-- 
2.54.0


From 5b43d599e37b9f663343aa8d3544840a13a04e94 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Tomas=20H=C3=A4rdin?= <[email protected]>
Date: Sun, 8 Nov 2026 20:12:33 +0100
Subject: [PATCH 7/8] avcodec/elbg: Make use of k-d tree

---
 libavcodec/Makefile                   | 12 +++---
 libavcodec/elbg.c                     | 53 ++++++++++++++++++++++-----
 tests/ref/fate/idroq-video-encode     |  2 +-
 tests/ref/seek/vsynth_lena-roqvideo   |  2 +-
 tests/ref/vsynth/vsynth1-cinepak      |  8 ++--
 tests/ref/vsynth/vsynth1-roqvideo     |  8 ++--
 tests/ref/vsynth/vsynth2-cinepak      |  8 ++--
 tests/ref/vsynth/vsynth2-roqvideo     |  8 ++--
 tests/ref/vsynth/vsynth_lena-cinepak  |  8 ++--
 tests/ref/vsynth/vsynth_lena-roqvideo |  8 ++--
 10 files changed, 76 insertions(+), 41 deletions(-)

diff --git a/libavcodec/Makefile b/libavcodec/Makefile
index 4bffc081184..d68ba18348a 100644
--- a/libavcodec/Makefile
+++ b/libavcodec/Makefile
@@ -191,8 +191,8 @@ OBJS-$(CONFIG_WMV2DSP)                 += wmv2dsp.o
 
 # decoders/encoders
 OBJS-$(CONFIG_ZERO12V_DECODER)         += 012v.o
-OBJS-$(CONFIG_A64MULTI_ENCODER)        += a64multienc.o elbg.o
-OBJS-$(CONFIG_A64MULTI5_ENCODER)       += a64multienc.o elbg.o
+OBJS-$(CONFIG_A64MULTI_ENCODER)        += a64multienc.o elbg.o kdtree.o
+OBJS-$(CONFIG_A64MULTI5_ENCODER)       += a64multienc.o elbg.o kdtree.o
 OBJS-$(CONFIG_AAC_DECODER)             += aactab.o \
                                           aacsbr.o aacps_common.o 
aacps_float.o \
                                           kbdwin.o \
@@ -315,7 +315,7 @@ OBJS-$(CONFIG_CDXL_DECODER)            += cdxl.o
 OBJS-$(CONFIG_CFHD_DECODER)            += cfhd.o cfhddata.o cfhddsp.o
 OBJS-$(CONFIG_CFHD_ENCODER)            += cfhdenc.o cfhddata.o cfhdencdsp.o
 OBJS-$(CONFIG_CINEPAK_DECODER)         += cinepak.o
-OBJS-$(CONFIG_CINEPAK_ENCODER)         += cinepakenc.o elbg.o
+OBJS-$(CONFIG_CINEPAK_ENCODER)         += cinepakenc.o elbg.o kdtree.o
 OBJS-$(CONFIG_CLEARVIDEO_DECODER)      += clearvideo.o
 OBJS-$(CONFIG_CLJR_DECODER)            += cljrdec.o
 OBJS-$(CONFIG_CLJR_ENCODER)            += cljrenc.o
@@ -602,7 +602,7 @@ OBJS-$(CONFIG_MSRLE_DECODER)           += msrle.o msrledec.o
 OBJS-$(CONFIG_MSS1_DECODER)            += mss1.o mss12.o
 OBJS-$(CONFIG_MSS2_DECODER)            += mss2.o mss12.o mss2dsp.o wmv2data.o
 OBJS-$(CONFIG_MSVIDEO1_DECODER)        += msvideo1.o
-OBJS-$(CONFIG_MSVIDEO1_ENCODER)        += msvideo1enc.o elbg.o
+OBJS-$(CONFIG_MSVIDEO1_ENCODER)        += msvideo1enc.o elbg.o kdtree.o
 OBJS-$(CONFIG_MSZH_DECODER)            += lcldec.o
 OBJS-$(CONFIG_MTS2_DECODER)            += mss4.o
 OBJS-$(CONFIG_MV30_DECODER)            += mv30.o
@@ -684,7 +684,7 @@ OBJS-$(CONFIG_REALTEXT_DECODER)        += realtextdec.o 
ass.o
 OBJS-$(CONFIG_RKA_DECODER)             += rka.o
 OBJS-$(CONFIG_RL2_DECODER)             += rl2.o
 OBJS-$(CONFIG_ROQ_DECODER)             += roqvideodec.o roqvideo.o
-OBJS-$(CONFIG_ROQ_ENCODER)             += roqvideoenc.o roqvideo.o elbg.o
+OBJS-$(CONFIG_ROQ_ENCODER)             += roqvideoenc.o roqvideo.o elbg.o 
kdtree.o
 OBJS-$(CONFIG_ROQ_DPCM_DECODER)        += dpcm.o
 OBJS-$(CONFIG_ROQ_DPCM_ENCODER)        += roqaudioenc.o
 OBJS-$(CONFIG_RPZA_DECODER)            += rpza.o
@@ -1161,7 +1161,7 @@ STLIBOBJS-$(CONFIG_RTP_MUXER)          += golomb.o 
jpegtables.o \
 STLIBOBJS-$(CONFIG_SPDIF_MUXER)        += dca_sample_rate_tab.o
 
 # libavfilter dependencies
-OBJS-$(CONFIG_ELBG_FILTER)             += elbg.o
+OBJS-$(CONFIG_ELBG_FILTER)             += elbg.o kdtree.o
 
 # external codec libraries
 OBJS-$(CONFIG_AAC_AT_DECODER)             += audiotoolboxdec.o
diff --git a/libavcodec/elbg.c b/libavcodec/elbg.c
index c99879040af..8a9051ff345 100644
--- a/libavcodec/elbg.c
+++ b/libavcodec/elbg.c
@@ -30,6 +30,7 @@
 #include "libavutil/lfg.h"
 #include "libavutil/mem.h"
 #include "elbg.h"
+#include "kdtree.h"
 
 #define DELTA_ERR_MAX 0.1  ///< Precision of the ELBG algorithm (as percentage 
error)
 
@@ -59,6 +60,8 @@ typedef struct ELBGContext {
     AVLFG *rand_state;
     int *scratchbuf;
     cell *cell_buffer;
+    int *best_dists;
+    KDTree kdtree;
 
     /* Sizes for the buffers above. Pointers without such a field
      * are not allocated by us and only valid for the duration
@@ -70,6 +73,7 @@ typedef struct ELBGContext {
     unsigned scratchbuf_allocated;
     unsigned cell_buffer_allocated;
     unsigned temp_points_allocated;
+    unsigned best_dists_allocated;
 } ELBGContext;
 
 static inline int distance_limited(const int *a, const int *b, int dim, int 
limit)
@@ -362,7 +366,7 @@ static void do_shiftings(ELBGContext *elbg)
         }
 }
 
-static void do_elbg(ELBGContext *restrict elbg, const int *points, int 
numpoints,
+static int do_elbg(ELBGContext *restrict elbg, const int *points, int 
numpoints,
                     int max_steps)
 {
     int *const size_part = elbg->size_part;
@@ -382,10 +386,28 @@ static void do_elbg(ELBGContext *restrict elbg, const int 
*points, int numpoints
 
         elbg->error = 0;
 
+        // Using a k-d tree is only worthwhile if the codebooks are large 
enough
+        // This limit is based on msvideo1enc.c not benefiting from k-d,
+        // and having a maximum codebook size of 2
+        int use_kdtree = elbg->num_cb > 2;
+
+        if (use_kdtree) {
+            int ret = avpriv_kdtree_create(&elbg->kdtree, elbg->codebook, 
elbg->num_cb, elbg->dim);
+            if (ret < 0) {
+                return ret;
+            }
+            avpriv_kdtree_query(&elbg->kdtree, elbg->points, numpoints, 
elbg->nearest_cb, elbg->best_dists);
+        }
+
         /* This loop evaluate the actual Voronoi partition. It is the most
            costly part of the algorithm. */
         for (i=0; i < numpoints; i++) {
-            int best_dist = distance_limited(elbg->points   + i * elbg->dim,
+            int best_dist;
+
+            if (use_kdtree) {
+                best_dist = elbg->best_dists[i];
+            } else {
+            best_dist = distance_limited(elbg->points   + i * elbg->dim,
                                              elbg->codebook + best_idx * 
elbg->dim,
                                              elbg->dim, INT_MAX);
             for (int k = 0; k < elbg->num_cb; k++) {
@@ -398,6 +420,8 @@ static void do_elbg(ELBGContext *restrict elbg, const int 
*points, int numpoints
                 }
             }
             elbg->nearest_cb[i] = best_idx;
+            }
+
             elbg->error += best_dist;
             elbg->utility[elbg->nearest_cb[i]] = 
(elbg->utility[elbg->nearest_cb[i]] >= INT_MAX - best_dist) ?
                                                   INT_MAX : 
elbg->utility[elbg->nearest_cb[i]] + best_dist;
@@ -426,6 +450,8 @@ static void do_elbg(ELBGContext *restrict elbg, const int 
*points, int numpoints
 
     } while(((last_error - elbg->error) > DELTA_ERR_MAX*elbg->error) &&
             (steps < max_steps));
+
+    return 0;
 }
 
 #define BIG_PRIME 433494437LL
@@ -436,7 +462,7 @@ static void do_elbg(ELBGContext *restrict elbg, const int 
*points, int numpoints
  * If not, it calls do_elbg for a (smaller) random sample of the points in
  * points.
  */
-static void init_elbg(ELBGContext *restrict elbg, const int *points, int 
*temp_points,
+static int init_elbg(ELBGContext *restrict elbg, const int *points, int 
*temp_points,
                       int numpoints, int max_steps)
 {
     int dim = elbg->dim;
@@ -451,13 +477,18 @@ static void init_elbg(ELBGContext *restrict elbg, const 
int *points, int *temp_p
 
         /* 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,
+        int ret = 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);
-    } else  // If not, initialize the codebook with random positions
+        if (ret < 0) {
+            return ret;
+        }
+        return do_elbg(elbg, temp_points, numpoints / 8, 2 * max_steps);
+    } 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, const int *points, int dim, int 
numpoints,
@@ -497,6 +528,7 @@ int avpriv_elbg_do(ELBGContext **elbgp, const int *points, 
int dim, int numpoint
     ALLOCATE_IF_NECESSARY(size_part,   num_cb,    1)
     ALLOCATE_IF_NECESSARY(cell_buffer, numpoints, 1)
     ALLOCATE_IF_NECESSARY(scratchbuf,  dim,       5)
+    ALLOCATE_IF_NECESSARY(best_dists,  numpoints, 1)
     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
@@ -508,9 +540,11 @@ int avpriv_elbg_do(ELBGContext **elbgp, const int *points, 
int dim, int numpoint
         ALLOCATE_IF_NECESSARY(temp_points, prod, 1)
     }
 
-    init_elbg(elbg, points, elbg->temp_points, numpoints, max_steps);
-    do_elbg (elbg, points, numpoints, max_steps);
-    return 0;
+    int ret = init_elbg(elbg, points, elbg->temp_points, numpoints, max_steps);
+    if (ret < 0) {
+        return ret;
+    }
+    return do_elbg (elbg, points, numpoints, max_steps);
 }
 
 av_cold void avpriv_elbg_free(ELBGContext **elbgp)
@@ -526,6 +560,7 @@ av_cold void avpriv_elbg_free(ELBGContext **elbgp)
     av_freep(&elbg->utility_inc);
     av_freep(&elbg->scratchbuf);
     av_freep(&elbg->temp_points);
+    av_freep(&elbg->best_dists);
 
     av_freep(elbgp);
 }
diff --git a/tests/ref/fate/idroq-video-encode 
b/tests/ref/fate/idroq-video-encode
index e983ffb1e6b..f709a3f5fc6 100644
--- a/tests/ref/fate/idroq-video-encode
+++ b/tests/ref/fate/idroq-video-encode
@@ -1 +1 @@
-e1cadf95578031643e70e4772d917ba8
+795c8e459c127ffc8a1480d8ac4d6eda
diff --git a/tests/ref/seek/vsynth_lena-roqvideo 
b/tests/ref/seek/vsynth_lena-roqvideo
index e1c5bcb4c41..477b47f2d01 100644
--- a/tests/ref/seek/vsynth_lena-roqvideo
+++ b/tests/ref/seek/vsynth_lena-roqvideo
@@ -1,4 +1,4 @@
-ret: 0         st: 0 flags:0 dts: 0.000000 pts: 0.000000 pos:     24 size: 
26876
+ret: 0         st: 0 flags:0 dts: 0.000000 pts: 0.000000 pos:     24 size: 
26512
 ret:-1         st:-1 flags:0  ts:-1.000000
 ret:-1         st:-1 flags:1  ts: 1.894167
 ret:-1         st: 0 flags:0  ts: 0.800000
diff --git a/tests/ref/vsynth/vsynth1-cinepak b/tests/ref/vsynth/vsynth1-cinepak
index 7cb33220e74..89a5d3502b2 100644
--- a/tests/ref/vsynth/vsynth1-cinepak
+++ b/tests/ref/vsynth/vsynth1-cinepak
@@ -1,4 +1,4 @@
-6b9b4d2b32854fd8b0f84ee4d76b1fed *tests/data/fate/vsynth1-cinepak.avi
-408910 tests/data/fate/vsynth1-cinepak.avi
-4acdcc3e664d12facbcefc389079cfa6 *tests/data/fate/vsynth1-cinepak.out.rawvideo
-stddev:   61.38 PSNR: 12.37 MAXDIFF:  223 bytes:  7603200/   921600
+55d510206493d6b611d2a751d0fbecb2 *tests/data/fate/vsynth1-cinepak.avi
+409386 tests/data/fate/vsynth1-cinepak.avi
+d5b27caf24a764a89ec928d32356cda9 *tests/data/fate/vsynth1-cinepak.out.rawvideo
+stddev:   61.39 PSNR: 12.37 MAXDIFF:  227 bytes:  7603200/   921600
diff --git a/tests/ref/vsynth/vsynth1-roqvideo 
b/tests/ref/vsynth/vsynth1-roqvideo
index 35c346d8fe2..bc479d2908c 100644
--- a/tests/ref/vsynth/vsynth1-roqvideo
+++ b/tests/ref/vsynth/vsynth1-roqvideo
@@ -1,4 +1,4 @@
-bfdf6d1a43c048b7e51f6680faf48a99 *tests/data/fate/vsynth1-roqvideo.roq
-102061 tests/data/fate/vsynth1-roqvideo.roq
-05af26df27889215c950cb471f534a16 *tests/data/fate/vsynth1-roqvideo.out.rawvideo
-stddev:    7.75 PSNR: 30.34 MAXDIFF:   99 bytes:  7603200/   760320
+bb81c10b2079969d4f684364c83d4fae *tests/data/fate/vsynth1-roqvideo.roq
+101873 tests/data/fate/vsynth1-roqvideo.roq
+acab412f594c29826f32f05e8adbeb8e *tests/data/fate/vsynth1-roqvideo.out.rawvideo
+stddev:    7.75 PSNR: 30.34 MAXDIFF:   88 bytes:  7603200/   760320
diff --git a/tests/ref/vsynth/vsynth2-cinepak b/tests/ref/vsynth/vsynth2-cinepak
index 72b87941160..c45dcc48e4d 100644
--- a/tests/ref/vsynth/vsynth2-cinepak
+++ b/tests/ref/vsynth/vsynth2-cinepak
@@ -1,4 +1,4 @@
-675d6a4370c315dc53c219a9271be4c6 *tests/data/fate/vsynth2-cinepak.avi
-400720 tests/data/fate/vsynth2-cinepak.avi
-cbf6900b882b484bc531f9b4799c226e *tests/data/fate/vsynth2-cinepak.out.rawvideo
-stddev:   80.96 PSNR:  9.96 MAXDIFF:  229 bytes:  7603200/   921600
+e014d46ad1a144adadb5bedbad89969b *tests/data/fate/vsynth2-cinepak.avi
+400928 tests/data/fate/vsynth2-cinepak.avi
+707b3e095675fc50236fd5c865382bef *tests/data/fate/vsynth2-cinepak.out.rawvideo
+stddev:   80.96 PSNR:  9.96 MAXDIFF:  227 bytes:  7603200/   921600
diff --git a/tests/ref/vsynth/vsynth2-roqvideo 
b/tests/ref/vsynth/vsynth2-roqvideo
index b914f66a108..d842e440f9a 100644
--- a/tests/ref/vsynth/vsynth2-roqvideo
+++ b/tests/ref/vsynth/vsynth2-roqvideo
@@ -1,4 +1,4 @@
-7eb634e57b13114e40e0b52f16e014b0 *tests/data/fate/vsynth2-roqvideo.roq
-91783 tests/data/fate/vsynth2-roqvideo.roq
-5c04ce7828401cfcdeb5c11011dbdcbd *tests/data/fate/vsynth2-roqvideo.out.rawvideo
-stddev:    4.87 PSNR: 34.38 MAXDIFF:   80 bytes:  7603200/   760320
+56befe82316588309bedab52106f0e3a *tests/data/fate/vsynth2-roqvideo.roq
+93178 tests/data/fate/vsynth2-roqvideo.roq
+f288f00480d25f82308e806494918610 *tests/data/fate/vsynth2-roqvideo.out.rawvideo
+stddev:    4.88 PSNR: 34.35 MAXDIFF:   72 bytes:  7603200/   760320
diff --git a/tests/ref/vsynth/vsynth_lena-cinepak 
b/tests/ref/vsynth/vsynth_lena-cinepak
index c9cb2cfaba7..5db8d1a0102 100644
--- a/tests/ref/vsynth/vsynth_lena-cinepak
+++ b/tests/ref/vsynth/vsynth_lena-cinepak
@@ -1,4 +1,4 @@
-a79f907fecb95c8a5b5de670ccda215b *tests/data/fate/vsynth_lena-cinepak.avi
-407952 tests/data/fate/vsynth_lena-cinepak.avi
-2664cdff5f14508e891477b498cc840e 
*tests/data/fate/vsynth_lena-cinepak.out.rawvideo
-stddev:   58.10 PSNR: 12.85 MAXDIFF:  185 bytes:  7603200/   921600
+3a7ab4a197e16d46a8c6835de46ff7f4 *tests/data/fate/vsynth_lena-cinepak.avi
+408206 tests/data/fate/vsynth_lena-cinepak.avi
+c063612cdabae9572d59ab7bfc5b4240 
*tests/data/fate/vsynth_lena-cinepak.out.rawvideo
+stddev:   58.10 PSNR: 12.85 MAXDIFF:  186 bytes:  7603200/   921600
diff --git a/tests/ref/vsynth/vsynth_lena-roqvideo 
b/tests/ref/vsynth/vsynth_lena-roqvideo
index 80a3b112b64..2d8c580bcfc 100644
--- a/tests/ref/vsynth/vsynth_lena-roqvideo
+++ b/tests/ref/vsynth/vsynth_lena-roqvideo
@@ -1,4 +1,4 @@
-5e7736b7054c7f3c0a46cd8dc5ecefa0 *tests/data/fate/vsynth_lena-roqvideo.roq
-94506 tests/data/fate/vsynth_lena-roqvideo.roq
-818ecfaf625324c7a24bdb716a760e20 
*tests/data/fate/vsynth_lena-roqvideo.out.rawvideo
-stddev:    3.81 PSNR: 36.51 MAXDIFF:   57 bytes:  7603200/   760320
+84f9f89447d7fe7f4a20745706ccab51 *tests/data/fate/vsynth_lena-roqvideo.roq
+94075 tests/data/fate/vsynth_lena-roqvideo.roq
+86df7c59ccb0ebadb5f5c5fbffe93c50 
*tests/data/fate/vsynth_lena-roqvideo.out.rawvideo
+stddev:    3.81 PSNR: 36.50 MAXDIFF:   55 bytes:  7603200/   760320
-- 
2.54.0


From e467c7179a4677ff5db6b0fc9485c8c4799a6a16 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Tomas=20H=C3=A4rdin?= <[email protected]>
Date: Sun, 8 Nov 2026 20:18:44 +0100
Subject: [PATCH 8/8] avcodec/elbg: Indent

---
 libavcodec/elbg.c | 24 ++++++++++++------------
 1 file changed, 12 insertions(+), 12 deletions(-)

diff --git a/libavcodec/elbg.c b/libavcodec/elbg.c
index 8a9051ff345..3130b56d9ad 100644
--- a/libavcodec/elbg.c
+++ b/libavcodec/elbg.c
@@ -407,19 +407,19 @@ static int do_elbg(ELBGContext *restrict elbg, const int 
*points, int numpoints,
             if (use_kdtree) {
                 best_dist = elbg->best_dists[i];
             } else {
-            best_dist = distance_limited(elbg->points   + i * elbg->dim,
-                                             elbg->codebook + best_idx * 
elbg->dim,
-                                             elbg->dim, INT_MAX);
-            for (int k = 0; k < elbg->num_cb; k++) {
-                int dist = distance_limited(elbg->points   + i * elbg->dim,
-                                            elbg->codebook + k * elbg->dim,
-                                            elbg->dim, best_dist);
-                if (dist < best_dist) {
-                    best_dist = dist;
-                    best_idx = k;
+                best_dist = distance_limited(elbg->points   + i * elbg->dim,
+                                                elbg->codebook + best_idx * 
elbg->dim,
+                                                elbg->dim, INT_MAX);
+                for (int k = 0; k < elbg->num_cb; k++) {
+                    int dist = distance_limited(elbg->points   + i * elbg->dim,
+                                                elbg->codebook + k * elbg->dim,
+                                                elbg->dim, best_dist);
+                    if (dist < best_dist) {
+                        best_dist = dist;
+                        best_idx = k;
+                    }
                 }
-            }
-            elbg->nearest_cb[i] = best_idx;
+                elbg->nearest_cb[i] = best_idx;
             }
 
             elbg->error += best_dist;
-- 
2.54.0

_______________________________________________
ffmpeg-devel mailing list -- [email protected]
To unsubscribe send an email to [email protected]

Reply via email to