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

[Vitor]

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

[...]
>> +
>> +static inline void vect_division(int *res, int *vect, int div, int dim)
>> +{
>> +    int i;
>> +    if (div > 1)
>> +        for (i=0; i<dim; i++)
>> +            res[i] = vect[i]/div;
>>     
>
> this should be rounded to nearest like:
>
> if vect[i] is guranteed to be positive
> (vect[i] + div/2)/div;
> else 
> ROUNDED_DIV(vect[i], div)
>   

I used ROUNDED_DIV, because I don't think just this is worth making the 
whole code specific to positive integers.

[...]

>> +
>> +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)?

And I agree with the rest.

-Vitor

-------------- next part --------------
A non-text attachment was scrubbed...
Name: elbg5.diff
Type: text/x-patch
Size: 15891 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070602/769634b0/attachment.bin>