[FFmpeg-devel] [PATCH] Add a codebook generator

[Michael Niedermayer]

Hi

On Sat, Jun 02, 2007 at 05:54:43PM +0200, Vitor wrote:
> Hi
> 
> Michael Niedermayer wrote:
> [...]
> >>+    int *points;
> >>+    AVRandomState *rand_state;
> >>+} elbg_data;
> >>+
> >>+static inline int distance_limited(int *a, int *b, int dim, int limit)
> >>+{
> >>+    int i, dist=0;
> >>+    for (i=0; i<dim; i++) {
> >>+        dist += (a[i] - b[i])*(a[i] - b[i]);
> >>+        if (dist > limit)
> >>+            return INT_MAX;
> >>+    }
> >>+
> >>+    return dist;
> >>+}
> >>    
> >
> >if a and b where 16bit/short then it would be trivial to calculate the
> >above with mmx
> >its possible with int too but it would need 2x as many reads and would
> >need to convert from 32 to 16bit ...
> >
> >
> >  
> 
> Actually, I can't do any ASM. Anyway, if it where to optimize something 
> in assembler, wouldn't it be better to separate the whole loop (the 
> following) of the closest codebook search in a single function?
> 
>            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;
>                }

yes

[...]
> >>+
> >>+void ff_init_elbg(int *points, int dim, int numpoints, int *codebook,
> >>+                  int numCB, int max_steps, int *closest_cb,
> >>+                  AVRandomState *rand_state)
> >>+{
> >>+    int *temp_points;
> >>+    int i, k;
> >>+
> >>+    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    
> >>*/
> >>+        temp_points = av_malloc(dim*(numpoints/8)*sizeof(int));
> >>+        for (i=0; i<numpoints/8; i++) {
> >>+            k = (i*97) % numpoints;
> >>    
> >
> >97 is not guranteed to be relative prim to numpoints
> >if for example numpoints is x*97 this will not behave well ...
> >simply choosing a larger prime should fix that
> >for example 433494437LL would be an option (picked from 
> >http://en.wikipedia.org/wiki/List_of_prime_numbers)
> >  
> 
> I was a bit uneasy with the possibility of overflowing (is there any 
> chances of getting a repeated point if numpoints is not a power of two 
> and i*BIGPRIM overflows)?

you missed the LL at the end of the prime, that makes it a long long which
should be at least 64bit, you could also write i*(int64_t)prime if you
prefer


[...]
> +    if (olderror > newerror) {
> +
> +        shift_codebook(elbg, idx, newcentroid);
> +
> +        elbg->error += newerror - olderror;
> +
> +        for (j=0; j<3; j++)
> +            update_utility_and_n_cb(elbg, idx[j], newutility[j]);
> +
> +        evaluate_utility_inc(elbg);
> +
> +    }

are the 2 empty lines within the {} intended?


[...]

> +void ff_init_elbg(int *points, int dim, int numpoints, int *codebook,
> +                  int numCB, int max_steps, int *closest_cb,
> +                  AVRandomState *rand_state)
> +{
> +    int *temp_points;
> +    int i, k;
> +
> +    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       */
> +        temp_points = av_malloc(dim*(numpoints/8)*sizeof(int));

nitpick: int *temp_points = ...
is slightly simpler


[...]
> +        for (k=0; k < numpoints; k++)
> +            dist_cb[k] = INT_MAX;

cant that be moved into the for loop below?


> +
> +        memset(elbg->utility, 0, numCB*sizeof(int));
> +        memset(elbg->cells, 0, numCB*sizeof(cell *));
> +
> +        elbg->error = 0;
> +
> +        /* This loop evaluate the actual Voronoi partition. It is the most
> +           costly part of the algorithm. */
> +        for (i=0; i < numpoints; i++) {

[...]

> +        for (i=0; i < elbg->numCB; i++)
> +            memset(elbg->codebook + i*elbg->dim, 0, dim*sizeof(int));

memset(elbg->codebook, 0, elbg->numCB*dim*sizeof(int))


[...]

> +          vect_division(elbg->codebook + i*elbg->dim,
> +                        elbg->codebook + i*elbg->dim, size_part[i], elbg->dim);

indention is 2 spaces here while its 4 spaces everywhere else


except these iam fine with the patch, ive been nitpicking enough on it ...

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Concerning the gods, I have no means of knowing whether they exist or not
or of what sort they may be, because of the obscurity of the subject, and
the brevity of human life -- Protagoras
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070602/54bfe60f/attachment.pgp>