FFmpeg
elbg.c
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2007 Vitor Sessak <vitor1001@gmail.com>
3  *
4  * This file is part of FFmpeg.
5  *
6  * FFmpeg is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * FFmpeg is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with FFmpeg; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19  */
20 
21 /**
22  * @file
23  * Codebook Generator using the ELBG algorithm
24  */
25 
26 #include <string.h>
27 
28 #include "libavutil/avassert.h"
29 #include "libavutil/common.h"
30 #include "libavutil/lfg.h"
31 #include "elbg.h"
32 
33 #define DELTA_ERR_MAX 0.1 ///< Precision of the ELBG algorithm (as percentage error)
34 
35 /**
36  * In the ELBG jargon, a cell is the set of points that are closest to a
37  * codebook entry. Not to be confused with a RoQ Video cell. */
38 typedef struct cell_s {
39  int index;
40  struct cell_s *next;
41 } cell;
42 
43 /**
44  * ELBG internal data
45  */
46 typedef struct ELBGContext {
47  int error;
48  int dim;
49  int num_cb;
50  int *codebook;
51  cell **cells;
52  int *utility;
54  int *nearest_cb;
55  int *points;
57  int *size_part;
59  int *scratchbuf;
60  cell *cell_buffer;
61 
62  /* Sizes for the buffers above. Pointers without such a field
63  * are not allocated by us and only valid for the duration
64  * of a single call to avpriv_elbg_do(). */
68  unsigned cells_allocated;
72 } ELBGContext;
73 
74 static inline int distance_limited(int *a, int *b, int dim, int limit)
75 {
76  int i, dist=0;
77  for (i=0; i<dim; i++) {
78  int64_t distance = a[i] - b[i];
79 
80  distance *= distance;
81  if (dist >= limit - distance)
82  return limit;
83  dist += distance;
84  }
85 
86  return dist;
87 }
88 
89 static inline void vect_division(int *res, int *vect, int div, int dim)
90 {
91  int i;
92  if (div > 1)
93  for (i=0; i<dim; i++)
94  res[i] = ROUNDED_DIV(vect[i],div);
95  else if (res != vect)
96  memcpy(res, vect, dim*sizeof(int));
97 
98 }
99 
100 static int eval_error_cell(ELBGContext *elbg, int *centroid, cell *cells)
101 {
102  int error=0;
103  for (; cells; cells=cells->next) {
104  int distance = distance_limited(centroid, elbg->points + cells->index*elbg->dim, elbg->dim, INT_MAX);
105  if (error >= INT_MAX - distance)
106  return INT_MAX;
107  error += distance;
108  }
109 
110  return error;
111 }
112 
113 static int get_closest_codebook(ELBGContext *elbg, int index)
114 {
115  int pick = 0;
116  for (int i = 0, diff_min = INT_MAX; i < elbg->num_cb; i++)
117  if (i != index) {
118  int diff;
119  diff = distance_limited(elbg->codebook + i*elbg->dim, elbg->codebook + index*elbg->dim, elbg->dim, diff_min);
120  if (diff < diff_min) {
121  pick = i;
122  diff_min = diff;
123  }
124  }
125  return pick;
126 }
127 
129 {
130  int i=0;
131  /* Using linear search, do binary if it ever turns to be speed critical */
132  uint64_t r;
133 
134  if (elbg->utility_inc[elbg->num_cb - 1] < INT_MAX) {
135  r = av_lfg_get(elbg->rand_state) % (unsigned int)elbg->utility_inc[elbg->num_cb - 1] + 1;
136  } else {
137  r = av_lfg_get(elbg->rand_state);
138  r = (av_lfg_get(elbg->rand_state) + (r<<32)) % elbg->utility_inc[elbg->num_cb - 1] + 1;
139  }
140 
141  while (elbg->utility_inc[i] < r) {
142  i++;
143  }
144 
145  av_assert2(elbg->cells[i]);
146 
147  return i;
148 }
149 
150 /**
151  * Implementation of the simple LBG algorithm for just two codebooks
152  */
153 static int simple_lbg(ELBGContext *elbg,
154  int dim,
155  int *centroid[3],
156  int newutility[3],
157  int *points,
158  cell *cells)
159 {
160  int i, idx;
161  int numpoints[2] = {0,0};
162  int *newcentroid[2] = {
163  elbg->scratchbuf + 3*dim,
164  elbg->scratchbuf + 4*dim
165  };
166  cell *tempcell;
167 
168  memset(newcentroid[0], 0, 2 * dim * sizeof(*newcentroid[0]));
169 
170  newutility[0] =
171  newutility[1] = 0;
172 
173  for (tempcell = cells; tempcell; tempcell=tempcell->next) {
174  idx = distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX)>=
175  distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX);
176  numpoints[idx]++;
177  for (i=0; i<dim; i++)
178  newcentroid[idx][i] += points[tempcell->index*dim + i];
179  }
180 
181  vect_division(centroid[0], newcentroid[0], numpoints[0], dim);
182  vect_division(centroid[1], newcentroid[1], numpoints[1], dim);
183 
184  for (tempcell = cells; tempcell; tempcell=tempcell->next) {
185  int dist[2] = {distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX),
186  distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX)};
187  int idx = dist[0] > dist[1];
188  if (newutility[idx] >= INT_MAX - dist[idx])
189  newutility[idx] = INT_MAX;
190  else
191  newutility[idx] += dist[idx];
192  }
193 
194  return (newutility[0] >= INT_MAX - newutility[1]) ? INT_MAX : newutility[0] + newutility[1];
195 }
196 
197 static void get_new_centroids(ELBGContext *elbg, int huc, int *newcentroid_i,
198  int *newcentroid_p)
199 {
200  cell *tempcell;
201  int *min = newcentroid_i;
202  int *max = newcentroid_p;
203  int i;
204 
205  for (i=0; i< elbg->dim; i++) {
206  min[i]=INT_MAX;
207  max[i]=0;
208  }
209 
210  for (tempcell = elbg->cells[huc]; tempcell; tempcell = tempcell->next)
211  for(i=0; i<elbg->dim; i++) {
212  min[i]=FFMIN(min[i], elbg->points[tempcell->index*elbg->dim + i]);
213  max[i]=FFMAX(max[i], elbg->points[tempcell->index*elbg->dim + i]);
214  }
215 
216  for (i=0; i<elbg->dim; i++) {
217  int ni = min[i] + (max[i] - min[i])/3;
218  int np = min[i] + (2*(max[i] - min[i]))/3;
219  newcentroid_i[i] = ni;
220  newcentroid_p[i] = np;
221  }
222 }
223 
224 /**
225  * Add the points in the low utility cell to its closest cell. Split the high
226  * utility cell, putting the separated points in the (now empty) low utility
227  * cell.
228  *
229  * @param elbg Internal elbg data
230  * @param indexes {luc, huc, cluc}
231  * @param newcentroid A vector with the position of the new centroids
232  */
233 static void shift_codebook(ELBGContext *elbg, int *indexes,
234  int *newcentroid[3])
235 {
236  cell *tempdata;
237  cell **pp = &elbg->cells[indexes[2]];
238 
239  while(*pp)
240  pp= &(*pp)->next;
241 
242  *pp = elbg->cells[indexes[0]];
243 
244  elbg->cells[indexes[0]] = NULL;
245  tempdata = elbg->cells[indexes[1]];
246  elbg->cells[indexes[1]] = NULL;
247 
248  while(tempdata) {
249  cell *tempcell2 = tempdata->next;
250  int idx = distance_limited(elbg->points + tempdata->index*elbg->dim,
251  newcentroid[0], elbg->dim, INT_MAX) >
252  distance_limited(elbg->points + tempdata->index*elbg->dim,
253  newcentroid[1], elbg->dim, INT_MAX);
254 
255  tempdata->next = elbg->cells[indexes[idx]];
256  elbg->cells[indexes[idx]] = tempdata;
257  tempdata = tempcell2;
258  }
259 }
260 
262 {
263  int64_t inc=0;
264 
265  for (int i = 0; i < elbg->num_cb; i++) {
266  if (elbg->num_cb * (int64_t)elbg->utility[i] > elbg->error)
267  inc += elbg->utility[i];
268  elbg->utility_inc[i] = FFMIN(inc, INT_MAX);
269  }
270 }
271 
272 
273 static void update_utility_and_n_cb(ELBGContext *elbg, int idx, int newutility)
274 {
275  cell *tempcell;
276 
277  elbg->utility[idx] = newutility;
278  for (tempcell=elbg->cells[idx]; tempcell; tempcell=tempcell->next)
279  elbg->nearest_cb[tempcell->index] = idx;
280 }
281 
282 /**
283  * Evaluate if a shift lower the error. If it does, call shift_codebooks
284  * and update elbg->error, elbg->utility and elbg->nearest_cb.
285  *
286  * @param elbg Internal elbg data
287  * @param idx {luc (low utility cell, huc (high utility cell), cluc (closest cell to low utility cell)}
288  */
289 static void try_shift_candidate(ELBGContext *elbg, int idx[3])
290 {
291  int j, k, cont=0, tmp;
292  int64_t olderror=0, newerror;
293  int newutility[3];
294  int *newcentroid[3] = {
295  elbg->scratchbuf,
296  elbg->scratchbuf + elbg->dim,
297  elbg->scratchbuf + 2*elbg->dim
298  };
299  cell *tempcell;
300 
301  for (j=0; j<3; j++)
302  olderror += elbg->utility[idx[j]];
303 
304  memset(newcentroid[2], 0, elbg->dim*sizeof(int));
305 
306  for (k=0; k<2; k++)
307  for (tempcell=elbg->cells[idx[2*k]]; tempcell; tempcell=tempcell->next) {
308  cont++;
309  for (j=0; j<elbg->dim; j++)
310  newcentroid[2][j] += elbg->points[tempcell->index*elbg->dim + j];
311  }
312 
313  vect_division(newcentroid[2], newcentroid[2], cont, elbg->dim);
314 
315  get_new_centroids(elbg, idx[1], newcentroid[0], newcentroid[1]);
316 
317  newutility[2] = eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[0]]);
318  tmp = eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[2]]);
319  newutility[2] = (tmp >= INT_MAX - newutility[2]) ? INT_MAX : newutility[2] + tmp;
320 
321  newerror = newutility[2];
322 
323  tmp = simple_lbg(elbg, elbg->dim, newcentroid, newutility, elbg->points,
324  elbg->cells[idx[1]]);
325  if (tmp >= INT_MAX - newerror)
326  newerror = INT_MAX;
327  else
328  newerror += tmp;
329 
330  if (olderror > newerror) {
331  shift_codebook(elbg, idx, newcentroid);
332 
333  elbg->error += newerror - olderror;
334 
335  for (j=0; j<3; j++)
336  update_utility_and_n_cb(elbg, idx[j], newutility[j]);
337 
338  evaluate_utility_inc(elbg);
339  }
340  }
341 
342 /**
343  * Implementation of the ELBG block
344  */
345 static void do_shiftings(ELBGContext *elbg)
346 {
347  int idx[3];
348 
349  evaluate_utility_inc(elbg);
350 
351  for (idx[0]=0; idx[0] < elbg->num_cb; idx[0]++)
352  if (elbg->num_cb * (int64_t)elbg->utility[idx[0]] < elbg->error) {
353  if (elbg->utility_inc[elbg->num_cb - 1] == 0)
354  return;
355 
356  idx[1] = get_high_utility_cell(elbg);
357  idx[2] = get_closest_codebook(elbg, idx[0]);
358 
359  if (idx[1] != idx[0] && idx[1] != idx[2])
360  try_shift_candidate(elbg, idx);
361  }
362 }
363 
364 static void do_elbg(ELBGContext *av_restrict elbg, int *points, int numpoints,
365  int max_steps)
366 {
367  int *const size_part = elbg->size_part;
368  int i, j, steps = 0;
369  int best_idx = 0;
370  int last_error;
371 
372  elbg->error = INT_MAX;
373  elbg->points = points;
374 
375  do {
376  cell *free_cells = elbg->cell_buffer;
377  last_error = elbg->error;
378  steps++;
379  memset(elbg->utility, 0, elbg->num_cb * sizeof(*elbg->utility));
380  memset(elbg->cells, 0, elbg->num_cb * sizeof(*elbg->cells));
381 
382  elbg->error = 0;
383 
384  /* This loop evaluate the actual Voronoi partition. It is the most
385  costly part of the algorithm. */
386  for (i=0; i < numpoints; i++) {
387  int best_dist = distance_limited(elbg->points + i * elbg->dim,
388  elbg->codebook + best_idx * elbg->dim,
389  elbg->dim, INT_MAX);
390  for (int k = 0; k < elbg->num_cb; k++) {
391  int dist = distance_limited(elbg->points + i * elbg->dim,
392  elbg->codebook + k * elbg->dim,
393  elbg->dim, best_dist);
394  if (dist < best_dist) {
395  best_dist = dist;
396  best_idx = k;
397  }
398  }
399  elbg->nearest_cb[i] = best_idx;
400  elbg->error = (elbg->error >= INT_MAX - best_dist) ? INT_MAX : elbg->error + best_dist;
401  elbg->utility[elbg->nearest_cb[i]] = (elbg->utility[elbg->nearest_cb[i]] >= INT_MAX - best_dist) ?
402  INT_MAX : elbg->utility[elbg->nearest_cb[i]] + best_dist;
403  free_cells->index = i;
404  free_cells->next = elbg->cells[elbg->nearest_cb[i]];
405  elbg->cells[elbg->nearest_cb[i]] = free_cells;
406  free_cells++;
407  }
408 
409  do_shiftings(elbg);
410 
411  memset(size_part, 0, elbg->num_cb * sizeof(*size_part));
412 
413  memset(elbg->codebook, 0, elbg->num_cb * elbg->dim * sizeof(*elbg->codebook));
414 
415  for (i=0; i < numpoints; i++) {
416  size_part[elbg->nearest_cb[i]]++;
417  for (j=0; j < elbg->dim; j++)
418  elbg->codebook[elbg->nearest_cb[i]*elbg->dim + j] +=
419  elbg->points[i*elbg->dim + j];
420  }
421 
422  for (int i = 0; i < elbg->num_cb; i++)
423  vect_division(elbg->codebook + i*elbg->dim,
424  elbg->codebook + i*elbg->dim, size_part[i], elbg->dim);
425 
426  } while(((last_error - elbg->error) > DELTA_ERR_MAX*elbg->error) &&
427  (steps < max_steps));
428 }
429 
430 #define BIG_PRIME 433494437LL
431 
432 /**
433  * Initialize the codebook vector for the elbg algorithm.
434  * If numpoints <= 24 * num_cb this function fills codebook with random numbers.
435  * If not, it calls do_elbg for a (smaller) random sample of the points in
436  * points.
437  */
438 static void init_elbg(ELBGContext *av_restrict elbg, int *points, int *temp_points,
439  int numpoints, int max_steps)
440 {
441  int dim = elbg->dim;
442 
443  if (numpoints > 24LL * elbg->num_cb) {
444  /* ELBG is very costly for a big number of points. So if we have a lot
445  of them, get a good initial codebook to save on iterations */
446  for (int i = 0; i < numpoints / 8; i++) {
447  int k = (i*BIG_PRIME) % numpoints;
448  memcpy(temp_points + i*dim, points + k*dim, dim * sizeof(*temp_points));
449  }
450 
451  /* If anything is changed in the recursion parameters,
452  * the allocated size of temp_points will also need to be updated. */
453  init_elbg(elbg, temp_points, temp_points + numpoints / 8 * dim,
454  numpoints / 8, 2 * max_steps);
455  do_elbg(elbg, temp_points, numpoints / 8, 2 * max_steps);
456  } else // If not, initialize the codebook with random positions
457  for (int i = 0; i < elbg->num_cb; i++)
458  memcpy(elbg->codebook + i * dim, points + ((i*BIG_PRIME)%numpoints)*dim,
459  dim * sizeof(*elbg->codebook));
460 }
461 
462 int avpriv_elbg_do(ELBGContext **elbgp, int *points, int dim, int numpoints,
463  int *codebook, int num_cb, int max_steps,
464  int *closest_cb, AVLFG *rand_state, uintptr_t flags)
465 {
466  ELBGContext *const av_restrict elbg = *elbgp ? *elbgp : av_mallocz(sizeof(*elbg));
467 
468  if (!elbg)
469  return AVERROR(ENOMEM);
470  *elbgp = elbg;
471 
472  elbg->nearest_cb = closest_cb;
473  elbg->rand_state = rand_state;
474  elbg->codebook = codebook;
475  elbg->num_cb = num_cb;
476  elbg->dim = dim;
477 
478 #define ALLOCATE_IF_NECESSARY(field, new_elements, multiplicator) \
479  if (elbg->field ## _allocated < new_elements) { \
480  av_freep(&elbg->field); \
481  elbg->field = av_malloc_array(new_elements, \
482  multiplicator * sizeof(*elbg->field)); \
483  if (!elbg->field) { \
484  elbg->field ## _allocated = 0; \
485  return AVERROR(ENOMEM); \
486  } \
487  elbg->field ## _allocated = new_elements; \
488  }
489  /* Allocating the buffers for do_elbg() here once relies
490  * on their size being always the same even when do_elbg()
491  * is called from init_elbg(). It also relies on do_elbg()
492  * never calling itself recursively. */
493  ALLOCATE_IF_NECESSARY(cells, num_cb, 1)
494  ALLOCATE_IF_NECESSARY(utility, num_cb, 1)
495  ALLOCATE_IF_NECESSARY(utility_inc, num_cb, 1)
496  ALLOCATE_IF_NECESSARY(size_part, num_cb, 1)
497  ALLOCATE_IF_NECESSARY(cell_buffer, numpoints, 1)
498  ALLOCATE_IF_NECESSARY(scratchbuf, dim, 5)
499  if (numpoints > 24LL * elbg->num_cb) {
500  /* The first step in the recursion in init_elbg() needs a buffer with
501  * (numpoints / 8) * dim elements; the next step needs numpoints / 8 / 8
502  * * dim elements etc. The geometric series leads to an upper bound of
503  * numpoints / 8 * 8 / 7 * dim elements. */
504  uint64_t prod = dim * (uint64_t)(numpoints / 7U);
505  if (prod > INT_MAX)
506  return AVERROR(ERANGE);
507  ALLOCATE_IF_NECESSARY(temp_points, prod, 1)
508  }
509 
510  init_elbg(elbg, points, elbg->temp_points, numpoints, max_steps);
511  do_elbg (elbg, points, numpoints, max_steps);
512  return 0;
513 }
514 
516 {
517  ELBGContext *elbg = *elbgp;
518  if (!elbg)
519  return;
520 
521  av_freep(&elbg->size_part);
522  av_freep(&elbg->utility);
523  av_freep(&elbg->cell_buffer);
524  av_freep(&elbg->cells);
525  av_freep(&elbg->utility_inc);
526  av_freep(&elbg->scratchbuf);
527  av_freep(&elbg->temp_points);
528 
529  av_freep(elbgp);
530 }
error
static void error(const char *err)
Definition: target_bsf_fuzzer.c:31
vect_division
static void vect_division(int *res, int *vect, int div, int dim)
Definition: elbg.c:89
do_shiftings
static void do_shiftings(ELBGContext *elbg)
Implementation of the ELBG block.
Definition: elbg.c:345
r
const char * r
Definition: vf_curves.c:126
AVERROR
Filter the word “frame” indicates either a video frame or a group of audio as stored in an AVFrame structure Format for each input and each output the list of supported formats For video that means pixel format For audio that means channel sample they are references to shared objects When the negotiation mechanism computes the intersection of the formats supported at each end of a all references to both lists are replaced with a reference to the intersection And when a single format is eventually chosen for a link amongst the remaining all references to the list are updated That means that if a filter requires that its input and output have the same format amongst a supported all it has to do is use a reference to the same list of formats query_formats can leave some formats unset and return AVERROR(EAGAIN) to cause the negotiation mechanism toagain later. That can be used by filters with complex requirements to use the format negotiated on one link to set the formats supported on another. Frame references ownership and permissions
eval_error_cell
static int eval_error_cell(ELBGContext *elbg, int *centroid, cell *cells)
Definition: elbg.c:100
ELBGContext::error
int error
Definition: elbg.c:47
BIG_PRIME
#define BIG_PRIME
Definition: elbg.c:430
cell_s
In the ELBG jargon, a cell is the set of points that are closest to a codebook entry.
Definition: elbg.c:38
ELBGContext::nearest_cb
int * nearest_cb
Definition: elbg.c:54
ELBGContext::temp_points
int * temp_points
Definition: elbg.c:56
tmp
static uint8_t tmp[11]
Definition: aes_ctr.c:28
b
#define b
Definition: input.c:41
ELBGContext::codebook
int * codebook
Definition: elbg.c:50
ALLOCATE_IF_NECESSARY
#define ALLOCATE_IF_NECESSARY(field, new_elements, multiplicator)
max
#define max(a, b)
Definition: cuda_runtime.h:33
FFMAX
#define FFMAX(a, b)
Definition: macros.h:47
ELBGContext::rand_state
AVLFG * rand_state
Definition: elbg.c:58
ELBGContext::utility_inc_allocated
unsigned utility_inc_allocated
Definition: elbg.c:66
update_utility_and_n_cb
static void update_utility_and_n_cb(ELBGContext *elbg, int idx, int newutility)
Definition: elbg.c:273
shift_codebook
static void shift_codebook(ELBGContext *elbg, int *indexes, int *newcentroid[3])
Add the points in the low utility cell to its closest cell.
Definition: elbg.c:233
ELBGContext::utility_inc
int * utility_inc
Definition: elbg.c:53
evaluate_utility_inc
static void evaluate_utility_inc(ELBGContext *elbg)
Definition: elbg.c:261
ELBGContext::cell_buffer_allocated
unsigned cell_buffer_allocated
Definition: elbg.c:70
ELBGContext::temp_points_allocated
unsigned temp_points_allocated
Definition: elbg.c:71
avpriv_elbg_do
int avpriv_elbg_do(ELBGContext **elbgp, int *points, int dim, int numpoints, int *codebook, int num_cb, int max_steps, int *closest_cb, AVLFG *rand_state, uintptr_t flags)
Implementation of the Enhanced LBG Algorithm Based on the paper "Neural Networks 14:1219-1237" that c...
Definition: elbg.c:462
avassert.h
ELBGContext::num_cb
int num_cb
Definition: elbg.c:49
av_cold
#define av_cold
Definition: attributes.h:90
ELBGContext::size_part
int * size_part
Definition: elbg.c:57
av_lfg_get
static unsigned int av_lfg_get(AVLFG *c)
Get the next random unsigned 32-bit number using an ALFG.
Definition: lfg.h:53
lfg.h
do_elbg
static void do_elbg(ELBGContext *av_restrict elbg, int *points, int numpoints, int max_steps)
Definition: elbg.c:364
distance_limited
static int distance_limited(int *a, int *b, int dim, int limit)
Definition: elbg.c:74
DELTA_ERR_MAX
#define DELTA_ERR_MAX
Precision of the ELBG algorithm (as percentage error)
Definition: elbg.c:33
elbg.h
NULL
#define NULL
Definition: coverity.c:32
ROUNDED_DIV
#define ROUNDED_DIV(a, b)
Definition: common.h:49
get_new_centroids
static void get_new_centroids(ELBGContext *elbg, int huc, int *newcentroid_i, int *newcentroid_p)
Definition: elbg.c:197
index
int index
Definition: gxfenc.c:89
ELBGContext::cells
cell ** cells
Definition: elbg.c:51
ELBGContext::points
int * points
Definition: elbg.c:55
cell_s::index
int index
Definition: elbg.c:39
cell_s::next
struct cell_s * next
Definition: elbg.c:40
ELBGContext::scratchbuf
int * scratchbuf
Definition: elbg.c:59
AVLFG
Context structure for the Lagged Fibonacci PRNG.
Definition: lfg.h:33
simple_lbg
static int simple_lbg(ELBGContext *elbg, int dim, int *centroid[3], int newutility[3], int *points, cell *cells)
Implementation of the simple LBG algorithm for just two codebooks.
Definition: elbg.c:153
get_closest_codebook
static int get_closest_codebook(ELBGContext *elbg, int index)
Definition: elbg.c:113
avpriv_elbg_free
av_cold void avpriv_elbg_free(ELBGContext **elbgp)
Free an ELBGContext and reset the pointer to it.
Definition: elbg.c:515
diff
static av_always_inline int diff(const struct color_info *a, const struct color_info *b, const int trans_thresh)
Definition: vf_paletteuse.c:164
get_high_utility_cell
static int get_high_utility_cell(ELBGContext *elbg)
Definition: elbg.c:128
a
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
Definition: undefined.txt:41
ELBGContext::dim
int dim
Definition: elbg.c:48
ELBGContext::scratchbuf_allocated
unsigned scratchbuf_allocated
Definition: elbg.c:69
av_assert2
#define av_assert2(cond)
assert() equivalent, that does lie in speed critical code.
Definition: avassert.h:67
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:245
ELBGContext
ELBG internal data.
Definition: elbg.c:46
common.h
try_shift_candidate
static void try_shift_candidate(ELBGContext *elbg, int idx[3])
Evaluate if a shift lower the error.
Definition: elbg.c:289
FFMIN
#define FFMIN(a, b)
Definition: macros.h:49
av_mallocz
void * av_mallocz(size_t size)
Allocate a memory block with alignment suitable for all memory accesses (including vectors if availab...
Definition: mem.c:254
ELBGContext::size_part_allocated
unsigned size_part_allocated
Definition: elbg.c:67
limit
static double limit(double x)
Definition: vf_pseudocolor.c:142
dim
int dim
Definition: vorbis_enc_data.h:425
U
#define U(x)
Definition: vpx_arith.h:37
ELBGContext::cells_allocated
unsigned cells_allocated
Definition: elbg.c:68
steps
static const int16_t steps[16]
Definition: misc4.c:30
ELBGContext::utility_allocated
unsigned utility_allocated
Definition: elbg.c:65
init_elbg
static void init_elbg(ELBGContext *av_restrict elbg, int *points, int *temp_points, int numpoints, int max_steps)
Initialize the codebook vector for the elbg algorithm.
Definition: elbg.c:438
ELBGContext::utility
int * utility
Definition: elbg.c:52
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:34
distance
static float distance(float x, float y, int band)
Definition: nellymoserenc.c:230
flags
#define flags(name, subs,...)
Definition: cbs_av1.c:474
int
int
Definition: ffmpeg_filter.c:422
codebook
static const unsigned codebook[256][2]
Definition: cfhdenc.c:42
ELBGContext::cell_buffer
cell * cell_buffer
Definition: elbg.c:60
min
float min
Definition: vorbis_enc_data.h:429