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, <, &eq, >);
+
+ /**
+ * 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, <, &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]