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  int64_t error;
48  int dim;
49  int num_cb;
50  int *codebook;
51  cell **cells;
52  int64_t *utility;
53  int64_t *utility_inc;
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  dist += (a[i] - b[i])*(a[i] - b[i]);
79  if (dist > limit)
80  return INT_MAX;
81  }
82 
83  return dist;
84 }
85 
86 static inline void vect_division(int *res, int *vect, int div, int dim)
87 {
88  int i;
89  if (div > 1)
90  for (i=0; i<dim; i++)
91  res[i] = ROUNDED_DIV(vect[i],div);
92  else if (res != vect)
93  memcpy(res, vect, dim*sizeof(int));
94 
95 }
96 
97 static int eval_error_cell(ELBGContext *elbg, int *centroid, cell *cells)
98 {
99  int error=0;
100  for (; cells; cells=cells->next)
101  error += distance_limited(centroid, elbg->points + cells->index*elbg->dim, elbg->dim, INT_MAX);
102 
103  return error;
104 }
105 
106 static int get_closest_codebook(ELBGContext *elbg, int index)
107 {
108  int pick = 0;
109  for (int i = 0, diff_min = INT_MAX; i < elbg->num_cb; i++)
110  if (i != index) {
111  int diff;
112  diff = distance_limited(elbg->codebook + i*elbg->dim, elbg->codebook + index*elbg->dim, elbg->dim, diff_min);
113  if (diff < diff_min) {
114  pick = i;
115  diff_min = diff;
116  }
117  }
118  return pick;
119 }
120 
122 {
123  int i=0;
124  /* Using linear search, do binary if it ever turns to be speed critical */
125  uint64_t r;
126 
127  if (elbg->utility_inc[elbg->num_cb - 1] < INT_MAX) {
128  r = av_lfg_get(elbg->rand_state) % (unsigned int)elbg->utility_inc[elbg->num_cb - 1] + 1;
129  } else {
130  r = av_lfg_get(elbg->rand_state);
131  r = (av_lfg_get(elbg->rand_state) + (r<<32)) % elbg->utility_inc[elbg->num_cb - 1] + 1;
132  }
133 
134  while (elbg->utility_inc[i] < r) {
135  i++;
136  }
137 
138  av_assert2(elbg->cells[i]);
139 
140  return i;
141 }
142 
143 /**
144  * Implementation of the simple LBG algorithm for just two codebooks
145  */
146 static int simple_lbg(ELBGContext *elbg,
147  int dim,
148  int *centroid[3],
149  int newutility[3],
150  int *points,
151  cell *cells)
152 {
153  int i, idx;
154  int numpoints[2] = {0,0};
155  int *newcentroid[2] = {
156  elbg->scratchbuf + 3*dim,
157  elbg->scratchbuf + 4*dim
158  };
159  cell *tempcell;
160 
161  memset(newcentroid[0], 0, 2 * dim * sizeof(*newcentroid[0]));
162 
163  newutility[0] =
164  newutility[1] = 0;
165 
166  for (tempcell = cells; tempcell; tempcell=tempcell->next) {
167  idx = distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX)>=
168  distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX);
169  numpoints[idx]++;
170  for (i=0; i<dim; i++)
171  newcentroid[idx][i] += points[tempcell->index*dim + i];
172  }
173 
174  vect_division(centroid[0], newcentroid[0], numpoints[0], dim);
175  vect_division(centroid[1], newcentroid[1], numpoints[1], dim);
176 
177  for (tempcell = cells; tempcell; tempcell=tempcell->next) {
178  int dist[2] = {distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX),
179  distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX)};
180  int idx = dist[0] > dist[1];
181  newutility[idx] += dist[idx];
182  }
183 
184  return newutility[0] + newutility[1];
185 }
186 
187 static void get_new_centroids(ELBGContext *elbg, int huc, int *newcentroid_i,
188  int *newcentroid_p)
189 {
190  cell *tempcell;
191  int *min = newcentroid_i;
192  int *max = newcentroid_p;
193  int i;
194 
195  for (i=0; i< elbg->dim; i++) {
196  min[i]=INT_MAX;
197  max[i]=0;
198  }
199 
200  for (tempcell = elbg->cells[huc]; tempcell; tempcell = tempcell->next)
201  for(i=0; i<elbg->dim; i++) {
202  min[i]=FFMIN(min[i], elbg->points[tempcell->index*elbg->dim + i]);
203  max[i]=FFMAX(max[i], elbg->points[tempcell->index*elbg->dim + i]);
204  }
205 
206  for (i=0; i<elbg->dim; i++) {
207  int ni = min[i] + (max[i] - min[i])/3;
208  int np = min[i] + (2*(max[i] - min[i]))/3;
209  newcentroid_i[i] = ni;
210  newcentroid_p[i] = np;
211  }
212 }
213 
214 /**
215  * Add the points in the low utility cell to its closest cell. Split the high
216  * utility cell, putting the separated points in the (now empty) low utility
217  * cell.
218  *
219  * @param elbg Internal elbg data
220  * @param indexes {luc, huc, cluc}
221  * @param newcentroid A vector with the position of the new centroids
222  */
223 static void shift_codebook(ELBGContext *elbg, int *indexes,
224  int *newcentroid[3])
225 {
226  cell *tempdata;
227  cell **pp = &elbg->cells[indexes[2]];
228 
229  while(*pp)
230  pp= &(*pp)->next;
231 
232  *pp = elbg->cells[indexes[0]];
233 
234  elbg->cells[indexes[0]] = NULL;
235  tempdata = elbg->cells[indexes[1]];
236  elbg->cells[indexes[1]] = NULL;
237 
238  while(tempdata) {
239  cell *tempcell2 = tempdata->next;
240  int idx = distance_limited(elbg->points + tempdata->index*elbg->dim,
241  newcentroid[0], elbg->dim, INT_MAX) >
242  distance_limited(elbg->points + tempdata->index*elbg->dim,
243  newcentroid[1], elbg->dim, INT_MAX);
244 
245  tempdata->next = elbg->cells[indexes[idx]];
246  elbg->cells[indexes[idx]] = tempdata;
247  tempdata = tempcell2;
248  }
249 }
250 
252 {
253  int64_t inc=0;
254 
255  for (int i = 0; i < elbg->num_cb; i++) {
256  if (elbg->num_cb * elbg->utility[i] > elbg->error)
257  inc += elbg->utility[i];
258  elbg->utility_inc[i] = inc;
259  }
260 }
261 
262 
263 static void update_utility_and_n_cb(ELBGContext *elbg, int idx, int newutility)
264 {
265  cell *tempcell;
266 
267  elbg->utility[idx] = newutility;
268  for (tempcell=elbg->cells[idx]; tempcell; tempcell=tempcell->next)
269  elbg->nearest_cb[tempcell->index] = idx;
270 }
271 
272 /**
273  * Evaluate if a shift lower the error. If it does, call shift_codebooks
274  * and update elbg->error, elbg->utility and elbg->nearest_cb.
275  *
276  * @param elbg Internal elbg data
277  * @param idx {luc (low utility cell, huc (high utility cell), cluc (closest cell to low utility cell)}
278  */
279 static void try_shift_candidate(ELBGContext *elbg, int idx[3])
280 {
281  int j, k, cont=0;
282  int64_t olderror=0, newerror;
283  int newutility[3];
284  int *newcentroid[3] = {
285  elbg->scratchbuf,
286  elbg->scratchbuf + elbg->dim,
287  elbg->scratchbuf + 2*elbg->dim
288  };
289  cell *tempcell;
290 
291  for (j=0; j<3; j++)
292  olderror += elbg->utility[idx[j]];
293 
294  memset(newcentroid[2], 0, elbg->dim*sizeof(int));
295 
296  for (k=0; k<2; k++)
297  for (tempcell=elbg->cells[idx[2*k]]; tempcell; tempcell=tempcell->next) {
298  cont++;
299  for (j=0; j<elbg->dim; j++)
300  newcentroid[2][j] += elbg->points[tempcell->index*elbg->dim + j];
301  }
302 
303  vect_division(newcentroid[2], newcentroid[2], cont, elbg->dim);
304 
305  get_new_centroids(elbg, idx[1], newcentroid[0], newcentroid[1]);
306 
307  newutility[2] = eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[0]]);
308  newutility[2] += eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[2]]);
309 
310  newerror = newutility[2];
311 
312  newerror += simple_lbg(elbg, elbg->dim, newcentroid, newutility, elbg->points,
313  elbg->cells[idx[1]]);
314 
315  if (olderror > newerror) {
316  shift_codebook(elbg, idx, newcentroid);
317 
318  elbg->error += newerror - olderror;
319 
320  for (j=0; j<3; j++)
321  update_utility_and_n_cb(elbg, idx[j], newutility[j]);
322 
323  evaluate_utility_inc(elbg);
324  }
325  }
326 
327 /**
328  * Implementation of the ELBG block
329  */
330 static void do_shiftings(ELBGContext *elbg)
331 {
332  int idx[3];
333 
334  evaluate_utility_inc(elbg);
335 
336  for (idx[0]=0; idx[0] < elbg->num_cb; idx[0]++)
337  if (elbg->num_cb * elbg->utility[idx[0]] < elbg->error) {
338  if (elbg->utility_inc[elbg->num_cb - 1] == 0)
339  return;
340 
341  idx[1] = get_high_utility_cell(elbg);
342  idx[2] = get_closest_codebook(elbg, idx[0]);
343 
344  if (idx[1] != idx[0] && idx[1] != idx[2])
345  try_shift_candidate(elbg, idx);
346  }
347 }
348 
349 static void do_elbg(ELBGContext *av_restrict elbg, int *points, int numpoints,
350  int max_steps)
351 {
352  int *const size_part = elbg->size_part;
353  int i, j, steps = 0;
354  int best_idx = 0;
355  int64_t last_error;
356 
357  elbg->error = INT64_MAX;
358  elbg->points = points;
359 
360  do {
361  cell *free_cells = elbg->cell_buffer;
362  last_error = elbg->error;
363  steps++;
364  memset(elbg->utility, 0, elbg->num_cb * sizeof(*elbg->utility));
365  memset(elbg->cells, 0, elbg->num_cb * sizeof(*elbg->cells));
366 
367  elbg->error = 0;
368 
369  /* This loop evaluate the actual Voronoi partition. It is the most
370  costly part of the algorithm. */
371  for (i=0; i < numpoints; i++) {
372  int best_dist = distance_limited(elbg->points + i * elbg->dim,
373  elbg->codebook + best_idx * elbg->dim,
374  elbg->dim, INT_MAX);
375  for (int k = 0; k < elbg->num_cb; k++) {
376  int dist = distance_limited(elbg->points + i * elbg->dim,
377  elbg->codebook + k * elbg->dim,
378  elbg->dim, best_dist);
379  if (dist < best_dist) {
380  best_dist = dist;
381  best_idx = k;
382  }
383  }
384  elbg->nearest_cb[i] = best_idx;
385  elbg->error += best_dist;
386  elbg->utility[elbg->nearest_cb[i]] += best_dist;
387  free_cells->index = i;
388  free_cells->next = elbg->cells[elbg->nearest_cb[i]];
389  elbg->cells[elbg->nearest_cb[i]] = free_cells;
390  free_cells++;
391  }
392 
393  do_shiftings(elbg);
394 
395  memset(size_part, 0, elbg->num_cb * sizeof(*size_part));
396 
397  memset(elbg->codebook, 0, elbg->num_cb * elbg->dim * sizeof(*elbg->codebook));
398 
399  for (i=0; i < numpoints; i++) {
400  size_part[elbg->nearest_cb[i]]++;
401  for (j=0; j < elbg->dim; j++)
402  elbg->codebook[elbg->nearest_cb[i]*elbg->dim + j] +=
403  elbg->points[i*elbg->dim + j];
404  }
405 
406  for (int i = 0; i < elbg->num_cb; i++)
407  vect_division(elbg->codebook + i*elbg->dim,
408  elbg->codebook + i*elbg->dim, size_part[i], elbg->dim);
409 
410  } while(((last_error - elbg->error) > DELTA_ERR_MAX*elbg->error) &&
411  (steps < max_steps));
412 }
413 
414 #define BIG_PRIME 433494437LL
415 
416 /**
417  * Initialize the codebook vector for the elbg algorithm.
418  * If numpoints <= 24 * num_cb this function fills codebook with random numbers.
419  * If not, it calls do_elbg for a (smaller) random sample of the points in
420  * points.
421  */
422 static void init_elbg(ELBGContext *av_restrict elbg, int *points, int *temp_points,
423  int numpoints, int max_steps)
424 {
425  int dim = elbg->dim;
426 
427  if (numpoints > 24LL * elbg->num_cb) {
428  /* ELBG is very costly for a big number of points. So if we have a lot
429  of them, get a good initial codebook to save on iterations */
430  for (int i = 0; i < numpoints / 8; i++) {
431  int k = (i*BIG_PRIME) % numpoints;
432  memcpy(temp_points + i*dim, points + k*dim, dim * sizeof(*temp_points));
433  }
434 
435  /* If anything is changed in the recursion parameters,
436  * the allocated size of temp_points will also need to be updated. */
437  init_elbg(elbg, temp_points, temp_points + numpoints / 8 * dim,
438  numpoints / 8, 2 * max_steps);
439  do_elbg(elbg, temp_points, numpoints / 8, 2 * max_steps);
440  } else // If not, initialize the codebook with random positions
441  for (int i = 0; i < elbg->num_cb; i++)
442  memcpy(elbg->codebook + i * dim, points + ((i*BIG_PRIME)%numpoints)*dim,
443  dim * sizeof(*elbg->codebook));
444 }
445 
446 int avpriv_elbg_do(ELBGContext **elbgp, int *points, int dim, int numpoints,
447  int *codebook, int num_cb, int max_steps,
448  int *closest_cb, AVLFG *rand_state, uintptr_t flags)
449 {
450  ELBGContext *const av_restrict elbg = *elbgp ? *elbgp : av_mallocz(sizeof(*elbg));
451 
452  if (!elbg)
453  return AVERROR(ENOMEM);
454  *elbgp = elbg;
455 
456  elbg->nearest_cb = closest_cb;
457  elbg->rand_state = rand_state;
458  elbg->codebook = codebook;
459  elbg->num_cb = num_cb;
460  elbg->dim = dim;
461 
462 #define ALLOCATE_IF_NECESSARY(field, new_elements, multiplicator) \
463  if (elbg->field ## _allocated < new_elements) { \
464  av_freep(&elbg->field); \
465  elbg->field = av_malloc_array(new_elements, \
466  multiplicator * sizeof(*elbg->field)); \
467  if (!elbg->field) { \
468  elbg->field ## _allocated = 0; \
469  return AVERROR(ENOMEM); \
470  } \
471  elbg->field ## _allocated = new_elements; \
472  }
473  /* Allocating the buffers for do_elbg() here once relies
474  * on their size being always the same even when do_elbg()
475  * is called from init_elbg(). It also relies on do_elbg()
476  * never calling itself recursively. */
477  ALLOCATE_IF_NECESSARY(cells, num_cb, 1)
478  ALLOCATE_IF_NECESSARY(utility, num_cb, 1)
479  ALLOCATE_IF_NECESSARY(utility_inc, num_cb, 1)
480  ALLOCATE_IF_NECESSARY(size_part, num_cb, 1)
481  ALLOCATE_IF_NECESSARY(cell_buffer, numpoints, 1)
482  ALLOCATE_IF_NECESSARY(scratchbuf, dim, 5)
483  if (numpoints > 24LL * elbg->num_cb) {
484  /* The first step in the recursion in init_elbg() needs a buffer with
485  * (numpoints / 8) * dim elements; the next step needs numpoints / 8 / 8
486  * * dim elements etc. The geometric series leads to an upper bound of
487  * numpoints / 8 * 8 / 7 * dim elements. */
488  uint64_t prod = dim * (uint64_t)(numpoints / 7U);
489  if (prod > INT_MAX)
490  return AVERROR(ERANGE);
491  ALLOCATE_IF_NECESSARY(temp_points, prod, 1)
492  }
493 
494  init_elbg(elbg, points, elbg->temp_points, numpoints, max_steps);
495  do_elbg (elbg, points, numpoints, max_steps);
496  return 0;
497 }
498 
500 {
501  ELBGContext *elbg = *elbgp;
502  if (!elbg)
503  return;
504 
505  av_freep(&elbg->size_part);
506  av_freep(&elbg->utility);
507  av_freep(&elbg->cell_buffer);
508  av_freep(&elbg->cells);
509  av_freep(&elbg->utility_inc);
510  av_freep(&elbg->scratchbuf);
511  av_freep(&elbg->temp_points);
512 
513  av_freep(elbgp);
514 }
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:86
do_shiftings
static void do_shiftings(ELBGContext *elbg)
Implementation of the ELBG block.
Definition: elbg.c:330
r
const char * r
Definition: vf_curves.c:116
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:97
BIG_PRIME
#define BIG_PRIME
Definition: elbg.c:414
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
ELBGContext::error
int64_t error
Definition: elbg.c:47
index
fg index
Definition: ffmpeg_filter.c:168
b
#define b
Definition: input.c:40
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:263
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:223
U
#define U(x)
Definition: vp56_arith.h:37
evaluate_utility_inc
static void evaluate_utility_inc(ELBGContext *elbg)
Definition: elbg.c:251
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:446
avassert.h
ELBGContext::num_cb
int num_cb
Definition: elbg.c:49
ELBGContext::utility_inc
int64_t * utility_inc
Definition: elbg.c:53
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:349
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:187
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:146
get_closest_codebook
static int get_closest_codebook(ELBGContext *elbg, int index)
Definition: elbg.c:106
avpriv_elbg_free
av_cold void avpriv_elbg_free(ELBGContext **elbgp)
Free an ELBGContext and reset the pointer to it.
Definition: elbg.c:499
get_high_utility_cell
static int get_high_utility_cell(ELBGContext *elbg)
Definition: elbg.c:121
ELBGContext::utility
int64_t * utility
Definition: elbg.c:52
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:64
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:271
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:279
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:263
ELBGContext::size_part_allocated
unsigned size_part_allocated
Definition: elbg.c:67
limit
static double limit(double x)
Definition: vf_pseudocolor.c:128
dim
int dim
Definition: vorbis_enc_data.h:425
ELBGContext::cells_allocated
unsigned cells_allocated
Definition: elbg.c:68
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:422
diff
static av_always_inline int diff(const uint32_t a, const uint32_t b)
Definition: vf_palettegen.c:139
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:35
flags
#define flags(name, subs,...)
Definition: cbs_av1.c:561
int
int
Definition: ffmpeg_filter.c:156
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