3 * Copyright (c) 2002-2004 Michael Niedermayer
5 * This file is part of Libav.
7 * Libav is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
12 * Libav is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with Libav; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 * Motion estimation template.
27 //Let us hope gcc will remove the unused vars ...(gcc 3.2.2 seems to do it ...)
29 uint32_t av_unused * const score_map= c->score_map;\
30 const int av_unused xmin= c->xmin;\
31 const int av_unused ymin= c->ymin;\
32 const int av_unused xmax= c->xmax;\
33 const int av_unused ymax= c->ymax;\
34 uint8_t *mv_penalty= c->current_mv_penalty;\
35 const int pred_x= c->pred_x;\
36 const int pred_y= c->pred_y;\
38 #define CHECK_HALF_MV(dx, dy, x, y)\
40 const int hx= 2*(x)+(dx);\
41 const int hy= 2*(y)+(dy);\
42 d= cmp_hpel(s, x, y, dx, dy, size, h, ref_index, src_index, cmp_sub, chroma_cmp_sub, flags);\
43 d += (mv_penalty[hx - pred_x] + mv_penalty[hy - pred_y])*penalty_factor;\
44 COPY3_IF_LT(dmin, d, bx, hx, by, hy)\
47 static int hpel_motion_search(MpegEncContext * s,
48 int *mx_ptr, int *my_ptr, int dmin,
49 int src_index, int ref_index,
52 MotionEstContext * const c= &s->me;
53 const int mx = *mx_ptr;
54 const int my = *my_ptr;
55 const int penalty_factor= c->sub_penalty_factor;
56 me_cmp_func cmp_sub, chroma_cmp_sub;
60 int flags= c->sub_flags;
64 cmp_sub= s->dsp.me_sub_cmp[size];
65 chroma_cmp_sub= s->dsp.me_sub_cmp[size+1];
67 if(c->skip){ //FIXME move out of hpel?
73 if(c->avctx->me_cmp != c->avctx->me_sub_cmp){
74 dmin= cmp(s, mx, my, 0, 0, size, h, ref_index, src_index, cmp_sub, chroma_cmp_sub, flags);
75 if(mx || my || size>0)
76 dmin += (mv_penalty[2*mx - pred_x] + mv_penalty[2*my - pred_y])*penalty_factor;
79 if (mx > xmin && mx < xmax &&
80 my > ymin && my < ymax) {
82 const int index= (my<<ME_MAP_SHIFT) + mx;
83 const int t= score_map[(index-(1<<ME_MAP_SHIFT))&(ME_MAP_SIZE-1)]
84 + (mv_penalty[bx - pred_x] + mv_penalty[by-2 - pred_y])*c->penalty_factor;
85 const int l= score_map[(index- 1 )&(ME_MAP_SIZE-1)]
86 + (mv_penalty[bx-2 - pred_x] + mv_penalty[by - pred_y])*c->penalty_factor;
87 const int r= score_map[(index+ 1 )&(ME_MAP_SIZE-1)]
88 + (mv_penalty[bx+2 - pred_x] + mv_penalty[by - pred_y])*c->penalty_factor;
89 const int b= score_map[(index+(1<<ME_MAP_SHIFT))&(ME_MAP_SIZE-1)]
90 + (mv_penalty[bx - pred_x] + mv_penalty[by+2 - pred_y])*c->penalty_factor;
93 unsigned map_generation= c->map_generation;
95 uint32_t *map= c->map;
97 key= ((my-1)<<ME_MAP_MV_BITS) + (mx) + map_generation;
98 assert(map[(index-(1<<ME_MAP_SHIFT))&(ME_MAP_SIZE-1)] == key);
99 key= ((my+1)<<ME_MAP_MV_BITS) + (mx) + map_generation;
100 assert(map[(index+(1<<ME_MAP_SHIFT))&(ME_MAP_SIZE-1)] == key);
101 key= ((my)<<ME_MAP_MV_BITS) + (mx+1) + map_generation;
102 assert(map[(index+1)&(ME_MAP_SIZE-1)] == key);
103 key= ((my)<<ME_MAP_MV_BITS) + (mx-1) + map_generation;
104 assert(map[(index-1)&(ME_MAP_SIZE-1)] == key);
106 CHECK_HALF_MV(0, 1, mx ,my-1)
108 CHECK_HALF_MV(1, 1, mx-1, my-1)
110 CHECK_HALF_MV(1, 1, mx , my-1)
112 CHECK_HALF_MV(1, 1, mx-1, my )
114 CHECK_HALF_MV(1, 0, mx-1, my )
116 CHECK_HALF_MV(1, 1, mx , my-1)
118 CHECK_HALF_MV(1, 1, mx-1, my-1)
120 CHECK_HALF_MV(1, 1, mx , my )
122 CHECK_HALF_MV(1, 0, mx , my )
127 CHECK_HALF_MV(1, 1, mx-1, my-1)
129 CHECK_HALF_MV(1, 1, mx , my )
131 CHECK_HALF_MV(1, 0, mx-1, my)
132 CHECK_HALF_MV(1, 1, mx-1, my)
135 CHECK_HALF_MV(1, 1, mx , my-1)
137 CHECK_HALF_MV(1, 1, mx-1, my)
139 CHECK_HALF_MV(1, 0, mx , my)
140 CHECK_HALF_MV(1, 1, mx , my)
142 CHECK_HALF_MV(0, 1, mx , my)
144 assert(bx >= xmin*2 && bx <= xmax*2 && by >= ymin*2 && by <= ymax*2);
153 static int no_sub_motion_search(MpegEncContext * s,
154 int *mx_ptr, int *my_ptr, int dmin,
155 int src_index, int ref_index,
163 inline int ff_get_mb_score(MpegEncContext * s, int mx, int my, int src_index,
164 int ref_index, int size, int h, int add_rate)
166 // const int check_luma= s->dsp.me_sub_cmp != s->dsp.mb_cmp;
167 MotionEstContext * const c= &s->me;
168 const int penalty_factor= c->mb_penalty_factor;
169 const int flags= c->mb_flags;
170 const int qpel= flags & FLAG_QPEL;
171 const int mask= 1+2*qpel;
172 me_cmp_func cmp_sub, chroma_cmp_sub;
179 cmp_sub= s->dsp.mb_cmp[size];
180 chroma_cmp_sub= s->dsp.mb_cmp[size+1];
183 // assert(c->avctx->me_sub_cmp != c->avctx->mb_cmp);
185 d= cmp(s, mx>>(qpel+1), my>>(qpel+1), mx&mask, my&mask, size, h, ref_index, src_index, cmp_sub, chroma_cmp_sub, flags);
186 //FIXME check cbp before adding penalty for (0,0) vector
187 if(add_rate && (mx || my || size>0))
188 d += (mv_penalty[mx - pred_x] + mv_penalty[my - pred_y])*penalty_factor;
193 #define CHECK_QUARTER_MV(dx, dy, x, y)\
195 const int hx= 4*(x)+(dx);\
196 const int hy= 4*(y)+(dy);\
197 d= cmp_qpel(s, x, y, dx, dy, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);\
198 d += (mv_penalty[hx - pred_x] + mv_penalty[hy - pred_y])*penalty_factor;\
199 COPY3_IF_LT(dmin, d, bx, hx, by, hy)\
202 static int qpel_motion_search(MpegEncContext * s,
203 int *mx_ptr, int *my_ptr, int dmin,
204 int src_index, int ref_index,
207 MotionEstContext * const c= &s->me;
208 const int mx = *mx_ptr;
209 const int my = *my_ptr;
210 const int penalty_factor= c->sub_penalty_factor;
211 const unsigned map_generation = c->map_generation;
212 const int subpel_quality= c->avctx->me_subpel_quality;
213 uint32_t *map= c->map;
214 me_cmp_func cmpf, chroma_cmpf;
215 me_cmp_func cmp_sub, chroma_cmp_sub;
218 int flags= c->sub_flags;
220 cmpf= s->dsp.me_cmp[size];
221 chroma_cmpf= s->dsp.me_cmp[size+1]; //factorize FIXME
224 cmp_sub= s->dsp.me_sub_cmp[size];
225 chroma_cmp_sub= s->dsp.me_sub_cmp[size+1];
227 if(c->skip){ //FIXME somehow move up (benchmark)
233 if(c->avctx->me_cmp != c->avctx->me_sub_cmp){
234 dmin= cmp(s, mx, my, 0, 0, size, h, ref_index, src_index, cmp_sub, chroma_cmp_sub, flags);
235 if(mx || my || size>0)
236 dmin += (mv_penalty[4*mx - pred_x] + mv_penalty[4*my - pred_y])*penalty_factor;
239 if (mx > xmin && mx < xmax &&
240 my > ymin && my < ymax) {
241 int bx=4*mx, by=4*my;
244 const int index= (my<<ME_MAP_SHIFT) + mx;
245 const int t= score_map[(index-(1<<ME_MAP_SHIFT) )&(ME_MAP_SIZE-1)];
246 const int l= score_map[(index- 1 )&(ME_MAP_SIZE-1)];
247 const int r= score_map[(index+ 1 )&(ME_MAP_SIZE-1)];
248 const int b= score_map[(index+(1<<ME_MAP_SHIFT) )&(ME_MAP_SIZE-1)];
249 const int c= score_map[(index )&(ME_MAP_SIZE-1)];
253 memset(best, 64, sizeof(int)*8);
254 if(s->me.dia_size>=2){
255 const int tl= score_map[(index-(1<<ME_MAP_SHIFT)-1)&(ME_MAP_SIZE-1)];
256 const int bl= score_map[(index+(1<<ME_MAP_SHIFT)-1)&(ME_MAP_SIZE-1)];
257 const int tr= score_map[(index-(1<<ME_MAP_SHIFT)+1)&(ME_MAP_SIZE-1)];
258 const int br= score_map[(index+(1<<ME_MAP_SHIFT)+1)&(ME_MAP_SIZE-1)];
260 for(ny= -3; ny <= 3; ny++){
261 for(nx= -3; nx <= 3; nx++){
262 //FIXME this could overflow (unlikely though)
263 const int64_t t2= nx*nx*(tr + tl - 2*t) + 4*nx*(tr-tl) + 32*t;
264 const int64_t c2= nx*nx*( r + l - 2*c) + 4*nx*( r- l) + 32*c;
265 const int64_t b2= nx*nx*(br + bl - 2*b) + 4*nx*(br-bl) + 32*b;
266 int score= (ny*ny*(b2 + t2 - 2*c2) + 4*ny*(b2 - t2) + 32*c2 + 512)>>10;
269 if((nx&3)==0 && (ny&3)==0) continue;
271 score += (mv_penalty[4*mx + nx - pred_x] + mv_penalty[4*my + ny - pred_y])*penalty_factor;
273 // if(nx&1) score-=1024*c->penalty_factor;
274 // if(ny&1) score-=1024*c->penalty_factor;
278 memmove(&best[i+1], &best[i], sizeof(int)*(7-i));
279 memmove(&best_pos[i+1][0], &best_pos[i][0], sizeof(int)*2*(7-i));
281 best_pos[i][0]= nx + 4*mx;
282 best_pos[i][1]= ny + 4*my;
290 //FIXME this could overflow (unlikely though)
291 const int cx = 4*(r - l);
292 const int cx2= r + l - 2*c;
293 const int cy = 4*(b - t);
294 const int cy2= b + t - 2*c;
297 if(map[(index-(1<<ME_MAP_SHIFT)-1)&(ME_MAP_SIZE-1)] == (my<<ME_MAP_MV_BITS) + mx + map_generation && 0){ //FIXME
298 tl= score_map[(index-(1<<ME_MAP_SHIFT)-1)&(ME_MAP_SIZE-1)];
300 tl= cmp(s, mx-1, my-1, 0, 0, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);//FIXME wrong if chroma me is different
303 cxy= 2*tl + (cx + cy)/4 - (cx2 + cy2) - 2*c;
305 assert(16*cx2 + 4*cx + 32*c == 32*r);
306 assert(16*cx2 - 4*cx + 32*c == 32*l);
307 assert(16*cy2 + 4*cy + 32*c == 32*b);
308 assert(16*cy2 - 4*cy + 32*c == 32*t);
309 assert(16*cxy + 16*cy2 + 16*cx2 - 4*cy - 4*cx + 32*c == 32*tl);
311 for(ny= -3; ny <= 3; ny++){
312 for(nx= -3; nx <= 3; nx++){
313 //FIXME this could overflow (unlikely though)
314 int score= ny*nx*cxy + nx*nx*cx2 + ny*ny*cy2 + nx*cx + ny*cy + 32*c; //FIXME factor
317 if((nx&3)==0 && (ny&3)==0) continue;
319 score += 32*(mv_penalty[4*mx + nx - pred_x] + mv_penalty[4*my + ny - pred_y])*penalty_factor;
320 // if(nx&1) score-=32*c->penalty_factor;
321 // if(ny&1) score-=32*c->penalty_factor;
325 memmove(&best[i+1], &best[i], sizeof(int)*(7-i));
326 memmove(&best_pos[i+1][0], &best_pos[i][0], sizeof(int)*2*(7-i));
328 best_pos[i][0]= nx + 4*mx;
329 best_pos[i][1]= ny + 4*my;
336 for(i=0; i<subpel_quality; i++){
339 CHECK_QUARTER_MV(nx&3, ny&3, nx>>2, ny>>2)
342 assert(bx >= xmin*4 && bx <= xmax*4 && by >= ymin*4 && by <= ymax*4);
355 #define CHECK_MV(x,y)\
357 const unsigned key = ((y)<<ME_MAP_MV_BITS) + (x) + map_generation;\
358 const int index= (((y)<<ME_MAP_SHIFT) + (x))&(ME_MAP_SIZE-1);\
359 assert((x) >= xmin);\
360 assert((x) <= xmax);\
361 assert((y) >= ymin);\
362 assert((y) <= ymax);\
363 /*printf("check_mv %d %d\n", x, y);*/\
364 if(map[index]!=key){\
365 d= cmp(s, x, y, 0, 0, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);\
367 score_map[index]= d;\
368 d += (mv_penalty[((x)<<shift)-pred_x] + mv_penalty[((y)<<shift)-pred_y])*penalty_factor;\
369 /*printf("score:%d\n", d);*/\
370 COPY3_IF_LT(dmin, d, best[0], x, best[1], y)\
374 #define CHECK_CLIPPED_MV(ax,ay)\
378 const int Lx2= FFMAX(xmin, FFMIN(Lx, xmax));\
379 const int Ly2= FFMAX(ymin, FFMIN(Ly, ymax));\
383 #define CHECK_MV_DIR(x,y,new_dir)\
385 const unsigned key = ((y)<<ME_MAP_MV_BITS) + (x) + map_generation;\
386 const int index= (((y)<<ME_MAP_SHIFT) + (x))&(ME_MAP_SIZE-1);\
387 /*printf("check_mv_dir %d %d %d\n", x, y, new_dir);*/\
388 if(map[index]!=key){\
389 d= cmp(s, x, y, 0, 0, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);\
391 score_map[index]= d;\
392 d += (mv_penalty[((x)<<shift)-pred_x] + mv_penalty[((y)<<shift)-pred_y])*penalty_factor;\
393 /*printf("score:%d\n", d);*/\
403 #define check(x,y,S,v)\
404 if( (x)<(xmin<<(S)) ) printf("%d %d %d %d %d xmin" #v, xmin, (x), (y), s->mb_x, s->mb_y);\
405 if( (x)>(xmax<<(S)) ) printf("%d %d %d %d %d xmax" #v, xmax, (x), (y), s->mb_x, s->mb_y);\
406 if( (y)<(ymin<<(S)) ) printf("%d %d %d %d %d ymin" #v, ymin, (x), (y), s->mb_x, s->mb_y);\
407 if( (y)>(ymax<<(S)) ) printf("%d %d %d %d %d ymax" #v, ymax, (x), (y), s->mb_x, s->mb_y);\
409 #define LOAD_COMMON2\
410 uint32_t *map= c->map;\
411 const int qpel= flags&FLAG_QPEL;\
412 const int shift= 1+qpel;\
414 static av_always_inline int small_diamond_search(MpegEncContext * s, int *best, int dmin,
415 int src_index, int ref_index, int const penalty_factor,
416 int size, int h, int flags)
418 MotionEstContext * const c= &s->me;
419 me_cmp_func cmpf, chroma_cmpf;
423 unsigned map_generation = c->map_generation;
425 cmpf= s->dsp.me_cmp[size];
426 chroma_cmpf= s->dsp.me_cmp[size+1];
428 { /* ensure that the best point is in the MAP as h/qpel refinement needs it */
429 const unsigned key = (best[1]<<ME_MAP_MV_BITS) + best[0] + map_generation;
430 const int index= ((best[1]<<ME_MAP_SHIFT) + best[0])&(ME_MAP_SIZE-1);
431 if(map[index]!=key){ //this will be executed only very rarey
432 score_map[index]= cmp(s, best[0], best[1], 0, 0, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);
439 const int dir= next_dir;
440 const int x= best[0];
441 const int y= best[1];
445 if(dir!=2 && x>xmin) CHECK_MV_DIR(x-1, y , 0)
446 if(dir!=3 && y>ymin) CHECK_MV_DIR(x , y-1, 1)
447 if(dir!=0 && x<xmax) CHECK_MV_DIR(x+1, y , 2)
448 if(dir!=1 && y<ymax) CHECK_MV_DIR(x , y+1, 3)
456 static int funny_diamond_search(MpegEncContext * s, int *best, int dmin,
457 int src_index, int ref_index, int const penalty_factor,
458 int size, int h, int flags)
460 MotionEstContext * const c= &s->me;
461 me_cmp_func cmpf, chroma_cmpf;
465 unsigned map_generation = c->map_generation;
467 cmpf= s->dsp.me_cmp[size];
468 chroma_cmpf= s->dsp.me_cmp[size+1];
470 for(dia_size=1; dia_size<=4; dia_size++){
472 const int x= best[0];
473 const int y= best[1];
475 if(dia_size&(dia_size-1)) continue;
477 if( x + dia_size > xmax
478 || x - dia_size < xmin
479 || y + dia_size > ymax
480 || y - dia_size < ymin)
483 for(dir= 0; dir<dia_size; dir+=2){
486 CHECK_MV(x + dir , y + dia_size - dir);
487 CHECK_MV(x + dia_size - dir, y - dir );
488 CHECK_MV(x - dir , y - dia_size + dir);
489 CHECK_MV(x - dia_size + dir, y + dir );
492 if(x!=best[0] || y!=best[1])
498 static int hex_search(MpegEncContext * s, int *best, int dmin,
499 int src_index, int ref_index, int const penalty_factor,
500 int size, int h, int flags, int dia_size)
502 MotionEstContext * const c= &s->me;
503 me_cmp_func cmpf, chroma_cmpf;
506 unsigned map_generation = c->map_generation;
508 const int dec= dia_size & (dia_size-1);
510 cmpf= s->dsp.me_cmp[size];
511 chroma_cmpf= s->dsp.me_cmp[size+1];
513 for(;dia_size; dia_size= dec ? dia_size-1 : dia_size>>1){
518 CHECK_CLIPPED_MV(x -dia_size , y);
519 CHECK_CLIPPED_MV(x+ dia_size , y);
520 CHECK_CLIPPED_MV(x+( dia_size>>1), y+dia_size);
521 CHECK_CLIPPED_MV(x+( dia_size>>1), y-dia_size);
523 CHECK_CLIPPED_MV(x+(-dia_size>>1), y+dia_size);
524 CHECK_CLIPPED_MV(x+(-dia_size>>1), y-dia_size);
526 }while(best[0] != x || best[1] != y);
532 static int l2s_dia_search(MpegEncContext * s, int *best, int dmin,
533 int src_index, int ref_index, int const penalty_factor,
534 int size, int h, int flags)
536 MotionEstContext * const c= &s->me;
537 me_cmp_func cmpf, chroma_cmpf;
540 unsigned map_generation = c->map_generation;
542 int dia_size= c->dia_size&0xFF;
543 const int dec= dia_size & (dia_size-1);
544 static const int hex[8][2]={{-2, 0}, {-1,-1}, { 0,-2}, { 1,-1},
545 { 2, 0}, { 1, 1}, { 0, 2}, {-1, 1}};
547 cmpf= s->dsp.me_cmp[size];
548 chroma_cmpf= s->dsp.me_cmp[size+1];
550 for(; dia_size; dia_size= dec ? dia_size-1 : dia_size>>1){
555 CHECK_CLIPPED_MV(x+hex[i][0]*dia_size, y+hex[i][1]*dia_size);
557 }while(best[0] != x || best[1] != y);
562 CHECK_CLIPPED_MV(x+1, y);
563 CHECK_CLIPPED_MV(x, y+1);
564 CHECK_CLIPPED_MV(x-1, y);
565 CHECK_CLIPPED_MV(x, y-1);
570 static int umh_search(MpegEncContext * s, int *best, int dmin,
571 int src_index, int ref_index, int const penalty_factor,
572 int size, int h, int flags)
574 MotionEstContext * const c= &s->me;
575 me_cmp_func cmpf, chroma_cmpf;
578 unsigned map_generation = c->map_generation;
579 int x,y,x2,y2, i, j, d;
580 const int dia_size= c->dia_size&0xFE;
581 static const int hex[16][2]={{-4,-2}, {-4,-1}, {-4, 0}, {-4, 1}, {-4, 2},
582 { 4,-2}, { 4,-1}, { 4, 0}, { 4, 1}, { 4, 2},
583 {-2, 3}, { 0, 4}, { 2, 3},
584 {-2,-3}, { 0,-4}, { 2,-3},};
586 cmpf= s->dsp.me_cmp[size];
587 chroma_cmpf= s->dsp.me_cmp[size+1];
591 for(x2=FFMAX(x-dia_size+1, xmin); x2<=FFMIN(x+dia_size-1,xmax); x2+=2){
594 for(y2=FFMAX(y-dia_size/2+1, ymin); y2<=FFMIN(y+dia_size/2-1,ymax); y2+=2){
600 for(y2=FFMAX(y-2, ymin); y2<=FFMIN(y+2,ymax); y2++){
601 for(x2=FFMAX(x-2, xmin); x2<=FFMIN(x+2,xmax); x2++){
606 //FIXME prevent the CLIP stuff
608 for(j=1; j<=dia_size/4; j++){
610 CHECK_CLIPPED_MV(x+hex[i][0]*j, y+hex[i][1]*j);
614 return hex_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags, 2);
617 static int full_search(MpegEncContext * s, int *best, int dmin,
618 int src_index, int ref_index, int const penalty_factor,
619 int size, int h, int flags)
621 MotionEstContext * const c= &s->me;
622 me_cmp_func cmpf, chroma_cmpf;
625 unsigned map_generation = c->map_generation;
627 const int dia_size= c->dia_size&0xFF;
629 cmpf= s->dsp.me_cmp[size];
630 chroma_cmpf= s->dsp.me_cmp[size+1];
632 for(y=FFMAX(-dia_size, ymin); y<=FFMIN(dia_size,ymax); y++){
633 for(x=FFMAX(-dia_size, xmin); x<=FFMIN(dia_size,xmax); x++){
641 CHECK_CLIPPED_MV(x , y);
642 CHECK_CLIPPED_MV(x+1, y);
643 CHECK_CLIPPED_MV(x, y+1);
644 CHECK_CLIPPED_MV(x-1, y);
645 CHECK_CLIPPED_MV(x, y-1);
652 #define SAB_CHECK_MV(ax,ay)\
654 const unsigned key = ((ay)<<ME_MAP_MV_BITS) + (ax) + map_generation;\
655 const int index= (((ay)<<ME_MAP_SHIFT) + (ax))&(ME_MAP_SIZE-1);\
656 /*printf("sab check %d %d\n", ax, ay);*/\
657 if(map[index]!=key){\
658 d= cmp(s, ax, ay, 0, 0, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);\
660 score_map[index]= d;\
661 d += (mv_penalty[((ax)<<shift)-pred_x] + mv_penalty[((ay)<<shift)-pred_y])*penalty_factor;\
662 /*printf("score: %d\n", d);*/\
663 if(d < minima[minima_count-1].height){\
666 while(d >= minima[j].height) j++;\
668 memmove(&minima [j+1], &minima [j], (minima_count - j - 1)*sizeof(Minima));\
670 minima[j].checked= 0;\
671 minima[j].height= d;\
681 #define MAX_SAB_SIZE ME_MAP_SIZE
682 static int sab_diamond_search(MpegEncContext * s, int *best, int dmin,
683 int src_index, int ref_index, int const penalty_factor,
684 int size, int h, int flags)
686 MotionEstContext * const c= &s->me;
687 me_cmp_func cmpf, chroma_cmpf;
688 Minima minima[MAX_SAB_SIZE];
689 const int minima_count= FFABS(c->dia_size);
693 unsigned map_generation = c->map_generation;
695 cmpf= s->dsp.me_cmp[size];
696 chroma_cmpf= s->dsp.me_cmp[size+1];
698 /*Note j<MAX_SAB_SIZE is needed if MAX_SAB_SIZE < ME_MAP_SIZE as j can
699 become larger due to MVs overflowing their ME_MAP_MV_BITS bits space in map
701 for(j=i=0; i<ME_MAP_SIZE && j<MAX_SAB_SIZE; i++){
702 uint32_t key= map[i];
704 key += (1<<(ME_MAP_MV_BITS-1)) + (1<<(2*ME_MAP_MV_BITS-1));
706 if((key&((-1)<<(2*ME_MAP_MV_BITS))) != map_generation) continue;
708 minima[j].height= score_map[i];
709 minima[j].x= key & ((1<<ME_MAP_MV_BITS)-1); key>>=ME_MAP_MV_BITS;
710 minima[j].y= key & ((1<<ME_MAP_MV_BITS)-1);
711 minima[j].x-= (1<<(ME_MAP_MV_BITS-1));
712 minima[j].y-= (1<<(ME_MAP_MV_BITS-1));
714 // all entries in map should be in range except if the mv overflows their ME_MAP_MV_BITS bits space
715 if( minima[j].x > xmax || minima[j].x < xmin
716 || minima[j].y > ymax || minima[j].y < ymin)
720 if(minima[j].x || minima[j].y)
721 minima[j].height+= (mv_penalty[((minima[j].x)<<shift)-pred_x] + mv_penalty[((minima[j].y)<<shift)-pred_y])*penalty_factor;
726 qsort(minima, j, sizeof(Minima), minima_cmp);
728 for(; j<minima_count; j++){
729 minima[j].height=256*256*256*64;
731 minima[j].x= minima[j].y=0;
734 for(i=0; i<minima_count; i++){
735 const int x= minima[i].x;
736 const int y= minima[i].y;
739 if(minima[i].checked) continue;
741 if( x >= xmax || x <= xmin
742 || y >= ymax || y <= ymin)
747 SAB_CHECK_MV(x , y-1)
748 SAB_CHECK_MV(x , y+1)
750 minima[i].checked= 1;
753 best[0]= minima[0].x;
754 best[1]= minima[0].y;
755 dmin= minima[0].height;
757 if( best[0] < xmax && best[0] > xmin
758 && best[1] < ymax && best[1] > ymin){
760 //ensure that the refernece samples for hpel refinement are in the map
761 CHECK_MV(best[0]-1, best[1])
762 CHECK_MV(best[0]+1, best[1])
763 CHECK_MV(best[0], best[1]-1)
764 CHECK_MV(best[0], best[1]+1)
769 static int var_diamond_search(MpegEncContext * s, int *best, int dmin,
770 int src_index, int ref_index, int const penalty_factor,
771 int size, int h, int flags)
773 MotionEstContext * const c= &s->me;
774 me_cmp_func cmpf, chroma_cmpf;
778 unsigned map_generation = c->map_generation;
780 cmpf= s->dsp.me_cmp[size];
781 chroma_cmpf= s->dsp.me_cmp[size+1];
783 for(dia_size=1; dia_size<=c->dia_size; dia_size++){
785 const int x= best[0];
786 const int y= best[1];
788 start= FFMAX(0, y + dia_size - ymax);
789 end = FFMIN(dia_size, xmax - x + 1);
790 for(dir= start; dir<end; dir++){
793 //check(x + dir,y + dia_size - dir,0, a0)
794 CHECK_MV(x + dir , y + dia_size - dir);
797 start= FFMAX(0, x + dia_size - xmax);
798 end = FFMIN(dia_size, y - ymin + 1);
799 for(dir= start; dir<end; dir++){
802 //check(x + dia_size - dir, y - dir,0, a1)
803 CHECK_MV(x + dia_size - dir, y - dir );
806 start= FFMAX(0, -y + dia_size + ymin );
807 end = FFMIN(dia_size, x - xmin + 1);
808 for(dir= start; dir<end; dir++){
811 //check(x - dir,y - dia_size + dir,0, a2)
812 CHECK_MV(x - dir , y - dia_size + dir);
815 start= FFMAX(0, -x + dia_size + xmin );
816 end = FFMIN(dia_size, ymax - y + 1);
817 for(dir= start; dir<end; dir++){
820 //check(x - dia_size + dir, y + dir,0, a3)
821 CHECK_MV(x - dia_size + dir, y + dir );
824 if(x!=best[0] || y!=best[1])
830 static av_always_inline int diamond_search(MpegEncContext * s, int *best, int dmin,
831 int src_index, int ref_index, int const penalty_factor,
832 int size, int h, int flags){
833 MotionEstContext * const c= &s->me;
835 return funny_diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
836 else if(c->dia_size<-1)
837 return sab_diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
838 else if(c->dia_size<2)
839 return small_diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
840 else if(c->dia_size>1024)
841 return full_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
842 else if(c->dia_size>768)
843 return umh_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
844 else if(c->dia_size>512)
845 return hex_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags, c->dia_size&0xFF);
846 else if(c->dia_size>256)
847 return l2s_dia_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
849 return var_diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
853 @param P a list of candidate mvs to check before starting the
854 iterative search. If one of the candidates is close to the optimal mv, then
855 it takes fewer iterations. And it increases the chance that we find the
858 static av_always_inline int epzs_motion_search_internal(MpegEncContext * s, int *mx_ptr, int *my_ptr,
859 int P[10][2], int src_index, int ref_index, int16_t (*last_mv)[2],
860 int ref_mv_scale, int flags, int size, int h)
862 MotionEstContext * const c= &s->me;
863 int best[2]={0, 0}; /**< x and y coordinates of the best motion vector.
864 i.e. the difference between the position of the
865 block currently being encoded and the position of
866 the block chosen to predict it from. */
867 int d; ///< the score (cmp + penalty) of any given mv
868 int dmin; /**< the best value of d, i.e. the score
869 corresponding to the mv stored in best[]. */
870 unsigned map_generation;
872 const int ref_mv_stride= s->mb_stride; //pass as arg FIXME
873 const int ref_mv_xy= s->mb_x + s->mb_y*ref_mv_stride; //add to last_mv beforepassing FIXME
874 me_cmp_func cmpf, chroma_cmpf;
880 penalty_factor= c->pre_penalty_factor;
881 cmpf= s->dsp.me_pre_cmp[size];
882 chroma_cmpf= s->dsp.me_pre_cmp[size+1];
884 penalty_factor= c->penalty_factor;
885 cmpf= s->dsp.me_cmp[size];
886 chroma_cmpf= s->dsp.me_cmp[size+1];
889 map_generation= update_map_generation(c);
892 dmin= cmp(s, 0, 0, 0, 0, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);
893 map[0]= map_generation;
896 //FIXME precalc first term below?
897 if((s->pict_type == AV_PICTURE_TYPE_B && !(c->flags & FLAG_DIRECT)) || s->flags&CODEC_FLAG_MV0)
898 dmin += (mv_penalty[pred_x] + mv_penalty[pred_y])*penalty_factor;
901 if (s->first_slice_line) {
902 CHECK_MV(P_LEFT[0]>>shift, P_LEFT[1]>>shift)
903 CHECK_CLIPPED_MV((last_mv[ref_mv_xy][0]*ref_mv_scale + (1<<15))>>16,
904 (last_mv[ref_mv_xy][1]*ref_mv_scale + (1<<15))>>16)
906 if(dmin<((h*h*s->avctx->mv0_threshold)>>8)
907 && ( P_LEFT[0] |P_LEFT[1]
909 |P_TOPRIGHT[0]|P_TOPRIGHT[1])==0){
915 CHECK_MV( P_MEDIAN[0] >>shift , P_MEDIAN[1] >>shift)
916 CHECK_CLIPPED_MV((P_MEDIAN[0]>>shift) , (P_MEDIAN[1]>>shift)-1)
917 CHECK_CLIPPED_MV((P_MEDIAN[0]>>shift) , (P_MEDIAN[1]>>shift)+1)
918 CHECK_CLIPPED_MV((P_MEDIAN[0]>>shift)-1, (P_MEDIAN[1]>>shift) )
919 CHECK_CLIPPED_MV((P_MEDIAN[0]>>shift)+1, (P_MEDIAN[1]>>shift) )
920 CHECK_CLIPPED_MV((last_mv[ref_mv_xy][0]*ref_mv_scale + (1<<15))>>16,
921 (last_mv[ref_mv_xy][1]*ref_mv_scale + (1<<15))>>16)
922 CHECK_MV(P_LEFT[0] >>shift, P_LEFT[1] >>shift)
923 CHECK_MV(P_TOP[0] >>shift, P_TOP[1] >>shift)
924 CHECK_MV(P_TOPRIGHT[0]>>shift, P_TOPRIGHT[1]>>shift)
928 CHECK_CLIPPED_MV((last_mv[ref_mv_xy-1][0]*ref_mv_scale + (1<<15))>>16,
929 (last_mv[ref_mv_xy-1][1]*ref_mv_scale + (1<<15))>>16)
930 if(!s->first_slice_line)
931 CHECK_CLIPPED_MV((last_mv[ref_mv_xy-ref_mv_stride][0]*ref_mv_scale + (1<<15))>>16,
932 (last_mv[ref_mv_xy-ref_mv_stride][1]*ref_mv_scale + (1<<15))>>16)
934 CHECK_CLIPPED_MV((last_mv[ref_mv_xy+1][0]*ref_mv_scale + (1<<15))>>16,
935 (last_mv[ref_mv_xy+1][1]*ref_mv_scale + (1<<15))>>16)
936 if(s->mb_y+1<s->end_mb_y) //FIXME replace at least with last_slice_line
937 CHECK_CLIPPED_MV((last_mv[ref_mv_xy+ref_mv_stride][0]*ref_mv_scale + (1<<15))>>16,
938 (last_mv[ref_mv_xy+ref_mv_stride][1]*ref_mv_scale + (1<<15))>>16)
942 if(c->avctx->last_predictor_count){
943 const int count= c->avctx->last_predictor_count;
944 const int xstart= FFMAX(0, s->mb_x - count);
945 const int ystart= FFMAX(0, s->mb_y - count);
946 const int xend= FFMIN(s->mb_width , s->mb_x + count + 1);
947 const int yend= FFMIN(s->mb_height, s->mb_y + count + 1);
950 for(mb_y=ystart; mb_y<yend; mb_y++){
952 for(mb_x=xstart; mb_x<xend; mb_x++){
953 const int xy= mb_x + 1 + (mb_y + 1)*ref_mv_stride;
954 int mx= (last_mv[xy][0]*ref_mv_scale + (1<<15))>>16;
955 int my= (last_mv[xy][1]*ref_mv_scale + (1<<15))>>16;
957 if(mx>xmax || mx<xmin || my>ymax || my<ymin) continue;
963 //check(best[0],best[1],0, b0)
964 dmin= diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
966 //check(best[0],best[1],0, b1)
970 // printf("%d %d %d \n", best[0], best[1], dmin);
974 //this function is dedicated to the braindamaged gcc
975 inline int ff_epzs_motion_search(MpegEncContext * s, int *mx_ptr, int *my_ptr,
976 int P[10][2], int src_index, int ref_index, int16_t (*last_mv)[2],
977 int ref_mv_scale, int size, int h)
979 MotionEstContext * const c= &s->me;
980 //FIXME convert other functions in the same way if faster
981 if(c->flags==0 && h==16 && size==0){
982 return epzs_motion_search_internal(s, mx_ptr, my_ptr, P, src_index, ref_index, last_mv, ref_mv_scale, 0, 0, 16);
984 // return epzs_motion_search_internal(s, mx_ptr, my_ptr, P, src_index, ref_index, last_mv, ref_mv_scale, FLAG_QPEL);
986 return epzs_motion_search_internal(s, mx_ptr, my_ptr, P, src_index, ref_index, last_mv, ref_mv_scale, c->flags, size, h);
990 static int epzs_motion_search4(MpegEncContext * s,
991 int *mx_ptr, int *my_ptr, int P[10][2],
992 int src_index, int ref_index, int16_t (*last_mv)[2],
995 MotionEstContext * const c= &s->me;
998 unsigned map_generation;
999 const int penalty_factor= c->penalty_factor;
1002 const int ref_mv_stride= s->mb_stride;
1003 const int ref_mv_xy= s->mb_x + s->mb_y *ref_mv_stride;
1004 me_cmp_func cmpf, chroma_cmpf;
1006 int flags= c->flags;
1009 cmpf= s->dsp.me_cmp[size];
1010 chroma_cmpf= s->dsp.me_cmp[size+1];
1012 map_generation= update_map_generation(c);
1015 //printf("%d %d %d %d //",xmin, ymin, xmax, ymax);
1017 if (s->first_slice_line) {
1018 CHECK_MV(P_LEFT[0]>>shift, P_LEFT[1]>>shift)
1019 CHECK_CLIPPED_MV((last_mv[ref_mv_xy][0]*ref_mv_scale + (1<<15))>>16,
1020 (last_mv[ref_mv_xy][1]*ref_mv_scale + (1<<15))>>16)
1021 CHECK_MV(P_MV1[0]>>shift, P_MV1[1]>>shift)
1023 CHECK_MV(P_MV1[0]>>shift, P_MV1[1]>>shift)
1024 //FIXME try some early stop
1025 CHECK_MV(P_MEDIAN[0]>>shift, P_MEDIAN[1]>>shift)
1026 CHECK_MV(P_LEFT[0]>>shift, P_LEFT[1]>>shift)
1027 CHECK_MV(P_TOP[0]>>shift, P_TOP[1]>>shift)
1028 CHECK_MV(P_TOPRIGHT[0]>>shift, P_TOPRIGHT[1]>>shift)
1029 CHECK_CLIPPED_MV((last_mv[ref_mv_xy][0]*ref_mv_scale + (1<<15))>>16,
1030 (last_mv[ref_mv_xy][1]*ref_mv_scale + (1<<15))>>16)
1033 CHECK_CLIPPED_MV((last_mv[ref_mv_xy+1][0]*ref_mv_scale + (1<<15))>>16,
1034 (last_mv[ref_mv_xy+1][1]*ref_mv_scale + (1<<15))>>16)
1035 if(s->mb_y+1<s->end_mb_y) //FIXME replace at least with last_slice_line
1036 CHECK_CLIPPED_MV((last_mv[ref_mv_xy+ref_mv_stride][0]*ref_mv_scale + (1<<15))>>16,
1037 (last_mv[ref_mv_xy+ref_mv_stride][1]*ref_mv_scale + (1<<15))>>16)
1040 dmin= diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
1045 // printf("%d %d %d \n", best[0], best[1], dmin);
1049 //try to merge with above FIXME (needs PSNR test)
1050 static int epzs_motion_search2(MpegEncContext * s,
1051 int *mx_ptr, int *my_ptr, int P[10][2],
1052 int src_index, int ref_index, int16_t (*last_mv)[2],
1055 MotionEstContext * const c= &s->me;
1058 unsigned map_generation;
1059 const int penalty_factor= c->penalty_factor;
1060 const int size=0; //FIXME pass as arg
1062 const int ref_mv_stride= s->mb_stride;
1063 const int ref_mv_xy= s->mb_x + s->mb_y *ref_mv_stride;
1064 me_cmp_func cmpf, chroma_cmpf;
1066 int flags= c->flags;
1069 cmpf= s->dsp.me_cmp[size];
1070 chroma_cmpf= s->dsp.me_cmp[size+1];
1072 map_generation= update_map_generation(c);
1075 //printf("%d %d %d %d //",xmin, ymin, xmax, ymax);
1077 if (s->first_slice_line) {
1078 CHECK_MV(P_LEFT[0]>>shift, P_LEFT[1]>>shift)
1079 CHECK_CLIPPED_MV((last_mv[ref_mv_xy][0]*ref_mv_scale + (1<<15))>>16,
1080 (last_mv[ref_mv_xy][1]*ref_mv_scale + (1<<15))>>16)
1081 CHECK_MV(P_MV1[0]>>shift, P_MV1[1]>>shift)
1083 CHECK_MV(P_MV1[0]>>shift, P_MV1[1]>>shift)
1084 //FIXME try some early stop
1085 CHECK_MV(P_MEDIAN[0]>>shift, P_MEDIAN[1]>>shift)
1086 CHECK_MV(P_LEFT[0]>>shift, P_LEFT[1]>>shift)
1087 CHECK_MV(P_TOP[0]>>shift, P_TOP[1]>>shift)
1088 CHECK_MV(P_TOPRIGHT[0]>>shift, P_TOPRIGHT[1]>>shift)
1089 CHECK_CLIPPED_MV((last_mv[ref_mv_xy][0]*ref_mv_scale + (1<<15))>>16,
1090 (last_mv[ref_mv_xy][1]*ref_mv_scale + (1<<15))>>16)
1093 CHECK_CLIPPED_MV((last_mv[ref_mv_xy+1][0]*ref_mv_scale + (1<<15))>>16,
1094 (last_mv[ref_mv_xy+1][1]*ref_mv_scale + (1<<15))>>16)
1095 if(s->mb_y+1<s->end_mb_y) //FIXME replace at least with last_slice_line
1096 CHECK_CLIPPED_MV((last_mv[ref_mv_xy+ref_mv_stride][0]*ref_mv_scale + (1<<15))>>16,
1097 (last_mv[ref_mv_xy+ref_mv_stride][1]*ref_mv_scale + (1<<15))>>16)
1100 dmin= diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
1105 // printf("%d %d %d \n", best[0], best[1], dmin);