index 712c927..2707599 100644 (file)
*/

/**
- * @file libavcodec/elbg.c
+ * @file
* Codebook Generator using the ELBG algorithm
*/

#include <string.h>

-#include "libavutil/random.h"
+#include "libavutil/avassert.h"
+#include "libavutil/common.h"
+#include "libavutil/lfg.h"
#include "elbg.h"
#include "avcodec.h"

@@ -52,7 +54,8 @@ typedef struct{
int *utility_inc;
int *nearest_cb;
int *points;
-    AVRandomState *rand_state;
+    AVLFG *rand_state;
+    int *scratchbuf;
} elbg_data;

static inline int distance_limited(int *a, int *b, int dim, int limit)
@@ -105,11 +108,11 @@ static int get_high_utility_cell(elbg_data *elbg)
{
int i=0;
/* Using linear search, do binary if it ever turns to be speed critical */
-    int r = av_random(elbg->rand_state)%(elbg->utility_inc[elbg->numCB-1]-1) + 1;
+    int r = av_lfg_get(elbg->rand_state)%elbg->utility_inc[elbg->numCB-1] + 1;
while (elbg->utility_inc[i] < r)
i++;

-    assert(!elbg->cells[i]);
+    av_assert2(elbg->cells[i]);

return i;
}
@@ -117,7 +120,8 @@ static int get_high_utility_cell(elbg_data *elbg)
/**
* 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,
@@ -125,10 +129,13 @@ static int simple_lbg(int dim,
{
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;
@@ -158,8 +165,8 @@ static void get_new_centroids(elbg_data *elbg, int huc, int *newcentroid_i,
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++) {
@@ -174,14 +181,16 @@ static void get_new_centroids(elbg_data *elbg, int huc, int *newcentroid_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 separate points in the (now empty) low utility
* cell.
*
* @param elbg         Internal elbg data
@@ -242,20 +251,19 @@ static void update_utility_and_n_cb(elbg_data *elbg, int idx, int newutility)
* 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]];

@@ -277,11 +285,11 @@ static void try_shift_candidate(elbg_data *elbg, int idx[3])

-    newerror += simple_lbg(elbg->dim, newcentroid_ptrs, newutility, elbg->points,
+    newerror += simple_lbg(elbg, elbg->dim, newcentroid, newutility, elbg->points,
elbg->cells[idx[1]]);

-        shift_codebook(elbg, idx, newcentroid_ptrs);
+        shift_codebook(elbg, idx, newcentroid);

@@ -318,7 +326,7 @@ static void do_shiftings(elbg_data *elbg)

void ff_init_elbg(int *points, int dim, int numpoints, int *codebook,
int numCB, int max_steps, int *closest_cb,
-                  AVRandomState *rand_state)
+                  AVLFG *rand_state)
{
int i, k;

@@ -345,7 +353,7 @@ void ff_init_elbg(int *points, int dim, int numpoints, int *codebook,

void ff_do_elbg(int *points, int dim, int numpoints, int *codebook,
int numCB, int max_steps, int *closest_cb,
-                AVRandomState *rand_state)
+                AVLFG *rand_state)
{
int dist;
elbg_data elbg_d;
@@ -355,6 +363,7 @@ void ff_do_elbg(int *points, int dim, int numpoints, int *codebook,
int *size_part = av_malloc(numCB*sizeof(int));
cell *list_buffer = av_malloc(numpoints*sizeof(cell));
cell *free_cells;
+    int best_dist, best_idx = 0;

elbg->error = INT_MAX;
elbg->dim = dim;
@@ -365,6 +374,7 @@ void ff_do_elbg(int *points, int dim, int numpoints, int *codebook,
elbg->nearest_cb = closest_cb;
elbg->points = points;
elbg->utility_inc = av_malloc(numCB*sizeof(int));
+    elbg->scratchbuf = av_malloc(5*dim*sizeof(int));

elbg->rand_state = rand_state;

@@ -380,14 +390,16 @@ void ff_do_elbg(int *points, int dim, int numpoints, int *codebook,
/* This loop evaluate the actual Voronoi partition. It is the most
costly part of the algorithm. */
for (i=0; i < numpoints; i++) {
-            dist_cb[i] = INT_MAX;
+            best_dist = distance_limited(elbg->points + i*elbg->dim, elbg->codebook + best_idx*elbg->dim, dim, INT_MAX);
for (k=0; k < elbg->numCB; k++) {
-                dist = distance_limited(elbg->points + i*elbg->dim, elbg->codebook + k*elbg->dim, dim, dist_cb[i]);
-                if (dist < dist_cb[i]) {
-                    dist_cb[i] = dist;
-                    elbg->nearest_cb[i] = k;
+                dist = distance_limited(elbg->points + i*elbg->dim, elbg->codebook + k*elbg->dim, dim, best_dist);
+                if (dist < best_dist) {
+                    best_dist = dist;
+                    best_idx = k;
}
}
+            elbg->nearest_cb[i] = best_idx;
+            dist_cb[i] = best_dist;
elbg->error += dist_cb[i];
elbg->utility[elbg->nearest_cb[i]] += dist_cb[i];
free_cells->index = i;
@@ -422,4 +434,5 @@ void ff_do_elbg(int *points, int dim, int numpoints, int *codebook,
av_free(list_buffer);
av_free(elbg->cells);
av_free(elbg->utility_inc);
+    av_free(elbg->scratchbuf);
}