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