FFmpeg: libavcodec/elbg.c Source File

FFmpeg

[フレーム]

libavcodec

elbg.c

Go to the documentation of this file.

1 /*

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 */

21 /**

22 * @file

23 * Codebook Generator using the ELBG algorithm

24 */

26 #include <string.h>

28 #include "libavutil/avassert.h"

29 #include "libavutil/common.h"

30 #include "libavutil/lfg.h"

31 #include "libavutil/mem.h"

32 #include "elbg.h"

34 #define DELTA_ERR_MAX 0.1 ///< Precision of the ELBG algorithm (as percentage error)

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;

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;

54 int *utility_inc;

55 int *nearest_cb;

56 int *points;

57 int *temp_points;

58 int *size_part;

59 AVLFG *rand_state;

60 int *scratchbuf;

61 cell *cell_buffer;

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(). */

66 unsigned utility_allocated;

67 unsigned utility_inc_allocated;

68 unsigned size_part_allocated;

69 unsigned cells_allocated;

70 unsigned scratchbuf_allocated;

71 unsigned cell_buffer_allocated;

72 unsigned temp_points_allocated;

73 } ELBGContext;

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];

81 distance *= distance;

82 if (dist >= limit - distance)

83 return limit;

84 dist += distance;

85 }

87 return dist;

88 }

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));

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

129 static int get_high_utility_cell(ELBGContext *elbg)

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

262 static void evaluate_utility_inc(ELBGContext *elbg)

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

516 av_cold void avpriv_elbg_free(ELBGContext **elbgp)

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

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

#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

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)