/*
* Copyright (C) 2007 Vitor Sessak <vitor1001@gmail.com>
*
- * This file is part of FFmpeg.
+ * This file is part of Libav.
*
- * FFmpeg is free software; you can redistribute it and/or
+ * Libav is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
- * FFmpeg is distributed in the hope that it will be useful,
+ * Libav is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
- * License along with FFmpeg; if not, write to the Free Software
+ * License along with Libav; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
/**
- * @file libavcodec/elbg.c
+ * @file
* Codebook Generator using the ELBG algorithm
*/
#include <string.h>
+#include "libavutil/common.h"
#include "libavutil/lfg.h"
#include "elbg.h"
#include "avcodec.h"
-#define DELTA_ERR_MAX 0.1 ///< Precision of the ELBG algorithm (as percentual error)
+#define DELTA_ERR_MAX 0.1 ///< Precision of the ELBG algorithm (as percentage error)
/**
* In the ELBG jargon, a cell is the set of points that are closest to a
/**
* ELBG internal data
*/
-typedef struct{
+typedef struct elbg_data {
int error;
int dim;
int numCB;
int *nearest_cb;
int *points;
AVLFG *rand_state;
+ int *scratchbuf;
} elbg_data;
static inline int distance_limited(int *a, int *b, int dim, int limit)
while (elbg->utility_inc[i] < r)
i++;
- assert(!elbg->cells[i]);
+ assert(elbg->cells[i]);
return i;
}
/**
* Implementation of the simple LBG algorithm for just two codebooks
*/
-static int simple_lbg(int dim,
+static int simple_lbg(elbg_data *elbg,
+ int dim,
int *centroid[3],
int newutility[3],
int *points,
{
int i, idx;
int numpoints[2] = {0,0};
- int newcentroid[2][dim];
+ int *newcentroid[2] = {
+ elbg->scratchbuf + 3*dim,
+ elbg->scratchbuf + 4*dim
+ };
cell *tempcell;
- memset(newcentroid, 0, sizeof(newcentroid));
+ memset(newcentroid[0], 0, 2 * dim * sizeof(*newcentroid[0]));
newutility[0] =
newutility[1] = 0;
int *newcentroid_p)
{
cell *tempcell;
- int min[elbg->dim];
- int max[elbg->dim];
+ int *min = newcentroid_i;
+ int *max = newcentroid_p;
int i;
for (i=0; i< elbg->dim; i++) {
}
for (i=0; i<elbg->dim; i++) {
- newcentroid_i[i] = min[i] + (max[i] - min[i])/3;
- newcentroid_p[i] = min[i] + (2*(max[i] - min[i]))/3;
+ int ni = min[i] + (max[i] - min[i])/3;
+ int np = min[i] + (2*(max[i] - min[i]))/3;
+ newcentroid_i[i] = ni;
+ newcentroid_p[i] = np;
}
}
/**
* Add the points in the low utility cell to its closest cell. Split the high
- * utility cell, putting the separed points in the (now empty) low utility
+ * utility cell, putting the separated points in the (now empty) low utility
* cell.
*
* @param elbg Internal elbg data
* and update elbg->error, elbg->utility and elbg->nearest_cb.
*
* @param elbg Internal elbg data
- * @param indexes {luc (low utility cell, huc (high utility cell), cluc (closest cell to low utility cell)}
+ * @param idx {luc (low utility cell, huc (high utility cell), cluc (closest cell to low utility cell)}
*/
static void try_shift_candidate(elbg_data *elbg, int idx[3])
{
int j, k, olderror=0, newerror, cont=0;
int newutility[3];
- int newcentroid[3][elbg->dim];
- int *newcentroid_ptrs[3];
+ int *newcentroid[3] = {
+ elbg->scratchbuf,
+ elbg->scratchbuf + elbg->dim,
+ elbg->scratchbuf + 2*elbg->dim
+ };
cell *tempcell;
- newcentroid_ptrs[0] = newcentroid[0];
- newcentroid_ptrs[1] = newcentroid[1];
- newcentroid_ptrs[2] = newcentroid[2];
-
for (j=0; j<3; j++)
olderror += elbg->utility[idx[j]];
newerror = newutility[2];
- newerror += simple_lbg(elbg->dim, newcentroid_ptrs, newutility, elbg->points,
+ newerror += simple_lbg(elbg, elbg->dim, newcentroid, newutility, elbg->points,
elbg->cells[idx[1]]);
if (olderror > newerror) {
- shift_codebook(elbg, idx, newcentroid_ptrs);
+ shift_codebook(elbg, idx, newcentroid);
elbg->error += newerror - olderror;
#define BIG_PRIME 433494437LL
-void ff_init_elbg(int *points, int dim, int numpoints, int *codebook,
- int numCB, int max_steps, int *closest_cb,
- AVLFG *rand_state)
+int ff_init_elbg(int *points, int dim, int numpoints, int *codebook,
+ int numCB, int max_steps, int *closest_cb,
+ AVLFG *rand_state)
{
- int i, k;
+ int i, k, ret = 0;
if (numpoints > 24*numCB) {
/* ELBG is very costly for a big number of points. So if we have a lot
of them, get a good initial codebook to save on iterations */
int *temp_points = av_malloc(dim*(numpoints/8)*sizeof(int));
+ if (!temp_points)
+ return AVERROR(ENOMEM);
for (i=0; i<numpoints/8; i++) {
k = (i*BIG_PRIME) % numpoints;
memcpy(temp_points + i*dim, points + k*dim, dim*sizeof(int));
}
- ff_init_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state);
- ff_do_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state);
-
+ ret = ff_init_elbg(temp_points, dim, numpoints / 8, codebook,
+ numCB, 2 * max_steps, closest_cb, rand_state);
+ if (ret < 0) {
+ av_freep(&temp_points);
+ return ret;
+ }
+ ret = ff_do_elbg(temp_points, dim, numpoints / 8, codebook,
+ numCB, 2 * max_steps, closest_cb, rand_state);
av_free(temp_points);
} else // If not, initialize the codebook with random positions
for (i=0; i < numCB; i++)
memcpy(codebook + i*dim, points + ((i*BIG_PRIME)%numpoints)*dim,
dim*sizeof(int));
-
+ return ret;
}
-void ff_do_elbg(int *points, int dim, int numpoints, int *codebook,
+int ff_do_elbg(int *points, int dim, int numpoints, int *codebook,
int numCB, int max_steps, int *closest_cb,
AVLFG *rand_state)
{
int dist;
elbg_data elbg_d;
elbg_data *elbg = &elbg_d;
- int i, j, k, last_error, steps=0;
+ int i, j, k, last_error, steps = 0, ret = 0;
int *dist_cb = av_malloc(numpoints*sizeof(int));
int *size_part = av_malloc(numCB*sizeof(int));
cell *list_buffer = av_malloc(numpoints*sizeof(cell));
elbg->nearest_cb = closest_cb;
elbg->points = points;
elbg->utility_inc = av_malloc(numCB*sizeof(int));
+ elbg->scratchbuf = av_malloc(5*dim*sizeof(int));
+
+ if (!dist_cb || !size_part || !list_buffer || !elbg->cells ||
+ !elbg->utility || !elbg->utility_inc || !elbg->scratchbuf) {
+ ret = AVERROR(ENOMEM);
+ goto out;
+ }
elbg->rand_state = rand_state;
} while(((last_error - elbg->error) > DELTA_ERR_MAX*elbg->error) &&
(steps < max_steps));
+out:
av_free(dist_cb);
av_free(size_part);
av_free(elbg->utility);
av_free(list_buffer);
av_free(elbg->cells);
av_free(elbg->utility_inc);
+ av_free(elbg->scratchbuf);
+ return ret;
}
projects / ffmpeg / blobdiff