[FFmpeg-devel] [PATCH] Add a codebook generator
Michael Niedermayer
michaelni
Sat Jun 2 18:21:32 CEST 2007
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>
More information about the ffmpeg-devel
mailing list