3 * Copyright (c) 2002-2004 Michael Niedermayer
5 * This file is part of FFmpeg.
7 * FFmpeg 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 * FFmpeg 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 FFmpeg; 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;
94 unsigned map_generation= c->map_generation;
95 key= ((my-1)<<ME_MAP_MV_BITS) + (mx) + map_generation;
96 av_assert2(c->map[(index-(1<<ME_MAP_SHIFT))&(ME_MAP_SIZE-1)] == key);
97 key= ((my+1)<<ME_MAP_MV_BITS) + (mx) + map_generation;
98 av_assert2(c->map[(index+(1<<ME_MAP_SHIFT))&(ME_MAP_SIZE-1)] == key);
99 key= ((my)<<ME_MAP_MV_BITS) + (mx+1) + map_generation;
100 av_assert2(c->map[(index+1)&(ME_MAP_SIZE-1)] == key);
101 key= ((my)<<ME_MAP_MV_BITS) + (mx-1) + map_generation;
102 av_assert2(c->map[(index-1)&(ME_MAP_SIZE-1)] == key);
105 CHECK_HALF_MV(0, 1, mx ,my-1)
107 CHECK_HALF_MV(1, 1, mx-1, my-1)
109 CHECK_HALF_MV(1, 1, mx , my-1)
111 CHECK_HALF_MV(1, 1, mx-1, my )
113 CHECK_HALF_MV(1, 0, mx-1, my )
115 CHECK_HALF_MV(1, 1, mx , my-1)
117 CHECK_HALF_MV(1, 1, mx-1, my-1)
119 CHECK_HALF_MV(1, 1, mx , my )
121 CHECK_HALF_MV(1, 0, mx , my )
126 CHECK_HALF_MV(1, 1, mx-1, my-1)
128 CHECK_HALF_MV(1, 1, mx , my )
130 CHECK_HALF_MV(1, 0, mx-1, my)
131 CHECK_HALF_MV(1, 1, mx-1, my)
134 CHECK_HALF_MV(1, 1, mx , my-1)
136 CHECK_HALF_MV(1, 1, mx-1, my)
138 CHECK_HALF_MV(1, 0, mx , my)
139 CHECK_HALF_MV(1, 1, mx , my)
141 CHECK_HALF_MV(0, 1, mx , my)
143 av_assert2(bx >= xmin*2 && bx <= xmax*2 && by >= ymin*2 && by <= ymax*2);
152 static int no_sub_motion_search(MpegEncContext * s,
153 int *mx_ptr, int *my_ptr, int dmin,
154 int src_index, int ref_index,
162 av_extern_inline int ff_get_mb_score(MpegEncContext * s, int mx, int my, int src_index,
163 int ref_index, int size, int h, int add_rate)
165 // const int check_luma= s->dsp.me_sub_cmp != s->dsp.mb_cmp;
166 MotionEstContext * const c= &s->me;
167 const int penalty_factor= c->mb_penalty_factor;
168 const int flags= c->mb_flags;
169 const int qpel= flags & FLAG_QPEL;
170 const int mask= 1+2*qpel;
171 me_cmp_func cmp_sub, chroma_cmp_sub;
178 cmp_sub= s->dsp.mb_cmp[size];
179 chroma_cmp_sub= s->dsp.mb_cmp[size+1];
181 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);
182 //FIXME check cbp before adding penalty for (0,0) vector
183 if(add_rate && (mx || my || size>0))
184 d += (mv_penalty[mx - pred_x] + mv_penalty[my - pred_y])*penalty_factor;
189 #define CHECK_QUARTER_MV(dx, dy, x, y)\
191 const int hx= 4*(x)+(dx);\
192 const int hy= 4*(y)+(dy);\
193 d= cmp_qpel(s, x, y, dx, dy, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);\
194 d += (mv_penalty[hx - pred_x] + mv_penalty[hy - pred_y])*penalty_factor;\
195 COPY3_IF_LT(dmin, d, bx, hx, by, hy)\
198 static int qpel_motion_search(MpegEncContext * s,
199 int *mx_ptr, int *my_ptr, int dmin,
200 int src_index, int ref_index,
203 MotionEstContext * const c= &s->me;
204 const int mx = *mx_ptr;
205 const int my = *my_ptr;
206 const int penalty_factor= c->sub_penalty_factor;
207 const unsigned map_generation = c->map_generation;
208 const int subpel_quality= c->avctx->me_subpel_quality;
209 uint32_t *map= c->map;
210 me_cmp_func cmpf, chroma_cmpf;
211 me_cmp_func cmp_sub, chroma_cmp_sub;
214 int flags= c->sub_flags;
216 cmpf= s->dsp.me_cmp[size];
217 chroma_cmpf= s->dsp.me_cmp[size+1]; //factorize FIXME
220 cmp_sub= s->dsp.me_sub_cmp[size];
221 chroma_cmp_sub= s->dsp.me_sub_cmp[size+1];
223 if(c->skip){ //FIXME somehow move up (benchmark)
229 if(c->avctx->me_cmp != c->avctx->me_sub_cmp){
230 dmin= cmp(s, mx, my, 0, 0, size, h, ref_index, src_index, cmp_sub, chroma_cmp_sub, flags);
231 if(mx || my || size>0)
232 dmin += (mv_penalty[4*mx - pred_x] + mv_penalty[4*my - pred_y])*penalty_factor;
235 if (mx > xmin && mx < xmax &&
236 my > ymin && my < ymax) {
237 int bx=4*mx, by=4*my;
240 const int index= (my<<ME_MAP_SHIFT) + mx;
241 const int t= score_map[(index-(1<<ME_MAP_SHIFT) )&(ME_MAP_SIZE-1)];
242 const int l= score_map[(index- 1 )&(ME_MAP_SIZE-1)];
243 const int r= score_map[(index+ 1 )&(ME_MAP_SIZE-1)];
244 const int b= score_map[(index+(1<<ME_MAP_SHIFT) )&(ME_MAP_SIZE-1)];
245 const int c= score_map[(index )&(ME_MAP_SIZE-1)];
249 memset(best, 64, sizeof(int)*8);
250 if(s->me.dia_size>=2){
251 const int tl= score_map[(index-(1<<ME_MAP_SHIFT)-1)&(ME_MAP_SIZE-1)];
252 const int bl= score_map[(index+(1<<ME_MAP_SHIFT)-1)&(ME_MAP_SIZE-1)];
253 const int tr= score_map[(index-(1<<ME_MAP_SHIFT)+1)&(ME_MAP_SIZE-1)];
254 const int br= score_map[(index+(1<<ME_MAP_SHIFT)+1)&(ME_MAP_SIZE-1)];
256 for(ny= -3; ny <= 3; ny++){
257 for(nx= -3; nx <= 3; nx++){
258 //FIXME this could overflow (unlikely though)
259 const int64_t t2= nx*nx*(tr + tl - 2*t) + 4*nx*(tr-tl) + 32*t;
260 const int64_t c2= nx*nx*( r + l - 2*c) + 4*nx*( r- l) + 32*c;
261 const int64_t b2= nx*nx*(br + bl - 2*b) + 4*nx*(br-bl) + 32*b;
262 int score= (ny*ny*(b2 + t2 - 2*c2) + 4*ny*(b2 - t2) + 32*c2 + 512)>>10;
265 if((nx&3)==0 && (ny&3)==0) continue;
267 score += (mv_penalty[4*mx + nx - pred_x] + mv_penalty[4*my + ny - pred_y])*penalty_factor;
269 // if(nx&1) score-=1024*c->penalty_factor;
270 // if(ny&1) score-=1024*c->penalty_factor;
274 memmove(&best[i+1], &best[i], sizeof(int)*(7-i));
275 memmove(&best_pos[i+1][0], &best_pos[i][0], sizeof(int)*2*(7-i));
277 best_pos[i][0]= nx + 4*mx;
278 best_pos[i][1]= ny + 4*my;
286 //FIXME this could overflow (unlikely though)
287 const int cx = 4*(r - l);
288 const int cx2= r + l - 2*c;
289 const int cy = 4*(b - t);
290 const int cy2= b + t - 2*c;
293 if(map[(index-(1<<ME_MAP_SHIFT)-1)&(ME_MAP_SIZE-1)] == (my<<ME_MAP_MV_BITS) + mx + map_generation && 0){ //FIXME
294 tl= score_map[(index-(1<<ME_MAP_SHIFT)-1)&(ME_MAP_SIZE-1)];
296 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
299 cxy= 2*tl + (cx + cy)/4 - (cx2 + cy2) - 2*c;
301 av_assert2(16*cx2 + 4*cx + 32*c == 32*r);
302 av_assert2(16*cx2 - 4*cx + 32*c == 32*l);
303 av_assert2(16*cy2 + 4*cy + 32*c == 32*b);
304 av_assert2(16*cy2 - 4*cy + 32*c == 32*t);
305 av_assert2(16*cxy + 16*cy2 + 16*cx2 - 4*cy - 4*cx + 32*c == 32*tl);
307 for(ny= -3; ny <= 3; ny++){
308 for(nx= -3; nx <= 3; nx++){
309 //FIXME this could overflow (unlikely though)
310 int score= ny*nx*cxy + nx*nx*cx2 + ny*ny*cy2 + nx*cx + ny*cy + 32*c; //FIXME factor
313 if((nx&3)==0 && (ny&3)==0) continue;
315 score += 32*(mv_penalty[4*mx + nx - pred_x] + mv_penalty[4*my + ny - pred_y])*penalty_factor;
316 // if(nx&1) score-=32*c->penalty_factor;
317 // if(ny&1) score-=32*c->penalty_factor;
321 memmove(&best[i+1], &best[i], sizeof(int)*(7-i));
322 memmove(&best_pos[i+1][0], &best_pos[i][0], sizeof(int)*2*(7-i));
324 best_pos[i][0]= nx + 4*mx;
325 best_pos[i][1]= ny + 4*my;
332 for(i=0; i<subpel_quality; i++){
335 CHECK_QUARTER_MV(nx&3, ny&3, nx>>2, ny>>2)
338 av_assert2(bx >= xmin*4 && bx <= xmax*4 && by >= ymin*4 && by <= ymax*4);
351 #define CHECK_MV(x,y)\
353 const unsigned key = ((y)<<ME_MAP_MV_BITS) + (x) + map_generation;\
354 const int index= (((y)<<ME_MAP_SHIFT) + (x))&(ME_MAP_SIZE-1);\
355 av_assert2((x) >= xmin);\
356 av_assert2((x) <= xmax);\
357 av_assert2((y) >= ymin);\
358 av_assert2((y) <= ymax);\
359 /*printf("check_mv %d %d\n", x, y);*/\
360 if(map[index]!=key){\
361 d= cmp(s, x, y, 0, 0, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);\
363 score_map[index]= d;\
364 d += (mv_penalty[((x)<<shift)-pred_x] + mv_penalty[((y)<<shift)-pred_y])*penalty_factor;\
365 /*printf("score:%d\n", d);*/\
366 COPY3_IF_LT(dmin, d, best[0], x, best[1], y)\
370 #define CHECK_CLIPPED_MV(ax,ay)\
374 const int Lx2= FFMAX(xmin, FFMIN(Lx, xmax));\
375 const int Ly2= FFMAX(ymin, FFMIN(Ly, ymax));\
379 #define CHECK_MV_DIR(x,y,new_dir)\
381 const unsigned key = ((y)<<ME_MAP_MV_BITS) + (x) + map_generation;\
382 const int index= (((y)<<ME_MAP_SHIFT) + (x))&(ME_MAP_SIZE-1);\
383 /*printf("check_mv_dir %d %d %d\n", x, y, new_dir);*/\
384 if(map[index]!=key){\
385 d= cmp(s, x, y, 0, 0, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);\
387 score_map[index]= d;\
388 d += (mv_penalty[((x)<<shift)-pred_x] + mv_penalty[((y)<<shift)-pred_y])*penalty_factor;\
389 /*printf("score:%d\n", d);*/\
399 #define check(x,y,S,v)\
400 if( (x)<(xmin<<(S)) ) printf("%d %d %d %d %d xmin" #v, xmin, (x), (y), s->mb_x, s->mb_y);\
401 if( (x)>(xmax<<(S)) ) printf("%d %d %d %d %d xmax" #v, xmax, (x), (y), s->mb_x, s->mb_y);\
402 if( (y)<(ymin<<(S)) ) printf("%d %d %d %d %d ymin" #v, ymin, (x), (y), s->mb_x, s->mb_y);\
403 if( (y)>(ymax<<(S)) ) printf("%d %d %d %d %d ymax" #v, ymax, (x), (y), s->mb_x, s->mb_y);\
405 #define LOAD_COMMON2\
406 uint32_t *map= c->map;\
407 const int qpel= flags&FLAG_QPEL;\
408 const int shift= 1+qpel;\
410 static av_always_inline int small_diamond_search(MpegEncContext * s, int *best, int dmin,
411 int src_index, int ref_index, int const penalty_factor,
412 int size, int h, int flags)
414 MotionEstContext * const c= &s->me;
415 me_cmp_func cmpf, chroma_cmpf;
419 unsigned map_generation = c->map_generation;
421 cmpf= s->dsp.me_cmp[size];
422 chroma_cmpf= s->dsp.me_cmp[size+1];
424 { /* ensure that the best point is in the MAP as h/qpel refinement needs it */
425 const unsigned key = (best[1]<<ME_MAP_MV_BITS) + best[0] + map_generation;
426 const int index= ((best[1]<<ME_MAP_SHIFT) + best[0])&(ME_MAP_SIZE-1);
427 if(map[index]!=key){ //this will be executed only very rarey
428 score_map[index]= cmp(s, best[0], best[1], 0, 0, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);
435 const int dir= next_dir;
436 const int x= best[0];
437 const int y= best[1];
441 if(dir!=2 && x>xmin) CHECK_MV_DIR(x-1, y , 0)
442 if(dir!=3 && y>ymin) CHECK_MV_DIR(x , y-1, 1)
443 if(dir!=0 && x<xmax) CHECK_MV_DIR(x+1, y , 2)
444 if(dir!=1 && y<ymax) CHECK_MV_DIR(x , y+1, 3)
452 static int funny_diamond_search(MpegEncContext * s, int *best, int dmin,
453 int src_index, int ref_index, int const penalty_factor,
454 int size, int h, int flags)
456 MotionEstContext * const c= &s->me;
457 me_cmp_func cmpf, chroma_cmpf;
461 unsigned map_generation = c->map_generation;
463 cmpf= s->dsp.me_cmp[size];
464 chroma_cmpf= s->dsp.me_cmp[size+1];
466 for(dia_size=1; dia_size<=4; dia_size++){
468 const int x= best[0];
469 const int y= best[1];
471 if(dia_size&(dia_size-1)) continue;
473 if( x + dia_size > xmax
474 || x - dia_size < xmin
475 || y + dia_size > ymax
476 || y - dia_size < ymin)
479 for(dir= 0; dir<dia_size; dir+=2){
482 CHECK_MV(x + dir , y + dia_size - dir);
483 CHECK_MV(x + dia_size - dir, y - dir );
484 CHECK_MV(x - dir , y - dia_size + dir);
485 CHECK_MV(x - dia_size + dir, y + dir );
488 if(x!=best[0] || y!=best[1])
494 static int hex_search(MpegEncContext * s, int *best, int dmin,
495 int src_index, int ref_index, int const penalty_factor,
496 int size, int h, int flags, int dia_size)
498 MotionEstContext * const c= &s->me;
499 me_cmp_func cmpf, chroma_cmpf;
502 unsigned map_generation = c->map_generation;
504 const int dec= dia_size & (dia_size-1);
506 cmpf= s->dsp.me_cmp[size];
507 chroma_cmpf= s->dsp.me_cmp[size+1];
509 for(;dia_size; dia_size= dec ? dia_size-1 : dia_size>>1){
514 CHECK_CLIPPED_MV(x -dia_size , y);
515 CHECK_CLIPPED_MV(x+ dia_size , y);
516 CHECK_CLIPPED_MV(x+( dia_size>>1), y+dia_size);
517 CHECK_CLIPPED_MV(x+( dia_size>>1), y-dia_size);
519 CHECK_CLIPPED_MV(x+(-dia_size>>1), y+dia_size);
520 CHECK_CLIPPED_MV(x+(-dia_size>>1), y-dia_size);
522 }while(best[0] != x || best[1] != y);
528 static int l2s_dia_search(MpegEncContext * s, int *best, int dmin,
529 int src_index, int ref_index, int const penalty_factor,
530 int size, int h, int flags)
532 MotionEstContext * const c= &s->me;
533 me_cmp_func cmpf, chroma_cmpf;
536 unsigned map_generation = c->map_generation;
538 int dia_size= c->dia_size&0xFF;
539 const int dec= dia_size & (dia_size-1);
540 static const int hex[8][2]={{-2, 0}, {-1,-1}, { 0,-2}, { 1,-1},
541 { 2, 0}, { 1, 1}, { 0, 2}, {-1, 1}};
543 cmpf= s->dsp.me_cmp[size];
544 chroma_cmpf= s->dsp.me_cmp[size+1];
546 for(; dia_size; dia_size= dec ? dia_size-1 : dia_size>>1){
551 CHECK_CLIPPED_MV(x+hex[i][0]*dia_size, y+hex[i][1]*dia_size);
553 }while(best[0] != x || best[1] != y);
558 CHECK_CLIPPED_MV(x+1, y);
559 CHECK_CLIPPED_MV(x, y+1);
560 CHECK_CLIPPED_MV(x-1, y);
561 CHECK_CLIPPED_MV(x, y-1);
566 static int umh_search(MpegEncContext * s, int *best, int dmin,
567 int src_index, int ref_index, int const penalty_factor,
568 int size, int h, int flags)
570 MotionEstContext * const c= &s->me;
571 me_cmp_func cmpf, chroma_cmpf;
574 unsigned map_generation = c->map_generation;
575 int x,y,x2,y2, i, j, d;
576 const int dia_size= c->dia_size&0xFE;
577 static const int hex[16][2]={{-4,-2}, {-4,-1}, {-4, 0}, {-4, 1}, {-4, 2},
578 { 4,-2}, { 4,-1}, { 4, 0}, { 4, 1}, { 4, 2},
579 {-2, 3}, { 0, 4}, { 2, 3},
580 {-2,-3}, { 0,-4}, { 2,-3},};
582 cmpf= s->dsp.me_cmp[size];
583 chroma_cmpf= s->dsp.me_cmp[size+1];
587 for(x2=FFMAX(x-dia_size+1, xmin); x2<=FFMIN(x+dia_size-1,xmax); x2+=2){
590 for(y2=FFMAX(y-dia_size/2+1, ymin); y2<=FFMIN(y+dia_size/2-1,ymax); y2+=2){
596 for(y2=FFMAX(y-2, ymin); y2<=FFMIN(y+2,ymax); y2++){
597 for(x2=FFMAX(x-2, xmin); x2<=FFMIN(x+2,xmax); x2++){
602 //FIXME prevent the CLIP stuff
604 for(j=1; j<=dia_size/4; j++){
606 CHECK_CLIPPED_MV(x+hex[i][0]*j, y+hex[i][1]*j);
610 return hex_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags, 2);
613 static int full_search(MpegEncContext * s, int *best, int dmin,
614 int src_index, int ref_index, int const penalty_factor,
615 int size, int h, int flags)
617 MotionEstContext * const c= &s->me;
618 me_cmp_func cmpf, chroma_cmpf;
621 unsigned map_generation = c->map_generation;
623 const int dia_size= c->dia_size&0xFF;
625 cmpf= s->dsp.me_cmp[size];
626 chroma_cmpf= s->dsp.me_cmp[size+1];
628 for(y=FFMAX(-dia_size, ymin); y<=FFMIN(dia_size,ymax); y++){
629 for(x=FFMAX(-dia_size, xmin); x<=FFMIN(dia_size,xmax); x++){
637 CHECK_CLIPPED_MV(x , y);
638 CHECK_CLIPPED_MV(x+1, y);
639 CHECK_CLIPPED_MV(x, y+1);
640 CHECK_CLIPPED_MV(x-1, y);
641 CHECK_CLIPPED_MV(x, y-1);
648 #define SAB_CHECK_MV(ax,ay)\
650 const unsigned key = ((ay)<<ME_MAP_MV_BITS) + (ax) + map_generation;\
651 const int index= (((ay)<<ME_MAP_SHIFT) + (ax))&(ME_MAP_SIZE-1);\
652 /*printf("sab check %d %d\n", ax, ay);*/\
653 if(map[index]!=key){\
654 d= cmp(s, ax, ay, 0, 0, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);\
656 score_map[index]= d;\
657 d += (mv_penalty[((ax)<<shift)-pred_x] + mv_penalty[((ay)<<shift)-pred_y])*penalty_factor;\
658 /*printf("score: %d\n", d);*/\
659 if(d < minima[minima_count-1].height){\
662 while(d >= minima[j].height) j++;\
664 memmove(&minima [j+1], &minima [j], (minima_count - j - 1)*sizeof(Minima));\
666 minima[j].checked= 0;\
667 minima[j].height= d;\
677 #define MAX_SAB_SIZE ME_MAP_SIZE
678 static int sab_diamond_search(MpegEncContext * s, int *best, int dmin,
679 int src_index, int ref_index, int const penalty_factor,
680 int size, int h, int flags)
682 MotionEstContext * const c= &s->me;
683 me_cmp_func cmpf, chroma_cmpf;
684 Minima minima[MAX_SAB_SIZE];
685 const int minima_count= FFABS(c->dia_size);
689 unsigned map_generation = c->map_generation;
691 cmpf= s->dsp.me_cmp[size];
692 chroma_cmpf= s->dsp.me_cmp[size+1];
694 /*Note j<MAX_SAB_SIZE is needed if MAX_SAB_SIZE < ME_MAP_SIZE as j can
695 become larger due to MVs overflowing their ME_MAP_MV_BITS bits space in map
697 for(j=i=0; i<ME_MAP_SIZE && j<MAX_SAB_SIZE; i++){
698 uint32_t key= map[i];
700 key += (1<<(ME_MAP_MV_BITS-1)) + (1<<(2*ME_MAP_MV_BITS-1));
702 if((key&((-1)<<(2*ME_MAP_MV_BITS))) != map_generation) continue;
704 minima[j].height= score_map[i];
705 minima[j].x= key & ((1<<ME_MAP_MV_BITS)-1); key>>=ME_MAP_MV_BITS;
706 minima[j].y= key & ((1<<ME_MAP_MV_BITS)-1);
707 minima[j].x-= (1<<(ME_MAP_MV_BITS-1));
708 minima[j].y-= (1<<(ME_MAP_MV_BITS-1));
710 // all entries in map should be in range except if the mv overflows their ME_MAP_MV_BITS bits space
711 if( minima[j].x > xmax || minima[j].x < xmin
712 || minima[j].y > ymax || minima[j].y < ymin)
716 if(minima[j].x || minima[j].y)
717 minima[j].height+= (mv_penalty[((minima[j].x)<<shift)-pred_x] + mv_penalty[((minima[j].y)<<shift)-pred_y])*penalty_factor;
722 qsort(minima, j, sizeof(Minima), minima_cmp);
724 for(; j<minima_count; j++){
725 minima[j].height=256*256*256*64;
727 minima[j].x= minima[j].y=0;
730 for(i=0; i<minima_count; i++){
731 const int x= minima[i].x;
732 const int y= minima[i].y;
735 if(minima[i].checked) continue;
737 if( x >= xmax || x <= xmin
738 || y >= ymax || y <= ymin)
743 SAB_CHECK_MV(x , y-1)
744 SAB_CHECK_MV(x , y+1)
746 minima[i].checked= 1;
749 best[0]= minima[0].x;
750 best[1]= minima[0].y;
751 dmin= minima[0].height;
753 if( best[0] < xmax && best[0] > xmin
754 && best[1] < ymax && best[1] > ymin){
756 //ensure that the refernece samples for hpel refinement are in the map
757 CHECK_MV(best[0]-1, best[1])
758 CHECK_MV(best[0]+1, best[1])
759 CHECK_MV(best[0], best[1]-1)
760 CHECK_MV(best[0], best[1]+1)
765 static int var_diamond_search(MpegEncContext * s, int *best, int dmin,
766 int src_index, int ref_index, int const penalty_factor,
767 int size, int h, int flags)
769 MotionEstContext * const c= &s->me;
770 me_cmp_func cmpf, chroma_cmpf;
774 unsigned map_generation = c->map_generation;
776 cmpf= s->dsp.me_cmp[size];
777 chroma_cmpf= s->dsp.me_cmp[size+1];
779 for(dia_size=1; dia_size<=c->dia_size; dia_size++){
781 const int x= best[0];
782 const int y= best[1];
784 start= FFMAX(0, y + dia_size - ymax);
785 end = FFMIN(dia_size, xmax - x + 1);
786 for(dir= start; dir<end; dir++){
789 //check(x + dir,y + dia_size - dir,0, a0)
790 CHECK_MV(x + dir , y + dia_size - dir);
793 start= FFMAX(0, x + dia_size - xmax);
794 end = FFMIN(dia_size, y - ymin + 1);
795 for(dir= start; dir<end; dir++){
798 //check(x + dia_size - dir, y - dir,0, a1)
799 CHECK_MV(x + dia_size - dir, y - dir );
802 start= FFMAX(0, -y + dia_size + ymin );
803 end = FFMIN(dia_size, x - xmin + 1);
804 for(dir= start; dir<end; dir++){
807 //check(x - dir,y - dia_size + dir,0, a2)
808 CHECK_MV(x - dir , y - dia_size + dir);
811 start= FFMAX(0, -x + dia_size + xmin );
812 end = FFMIN(dia_size, ymax - y + 1);
813 for(dir= start; dir<end; dir++){
816 //check(x - dia_size + dir, y + dir,0, a3)
817 CHECK_MV(x - dia_size + dir, y + dir );
820 if(x!=best[0] || y!=best[1])
826 static av_always_inline int diamond_search(MpegEncContext * s, int *best, int dmin,
827 int src_index, int ref_index, int const penalty_factor,
828 int size, int h, int flags){
829 MotionEstContext * const c= &s->me;
831 return funny_diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
832 else if(c->dia_size<-1)
833 return sab_diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
834 else if(c->dia_size<2)
835 return small_diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
836 else if(c->dia_size>1024)
837 return full_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
838 else if(c->dia_size>768)
839 return umh_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
840 else if(c->dia_size>512)
841 return hex_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags, c->dia_size&0xFF);
842 else if(c->dia_size>256)
843 return l2s_dia_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
845 return var_diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
849 @param P a list of candidate mvs to check before starting the
850 iterative search. If one of the candidates is close to the optimal mv, then
851 it takes fewer iterations. And it increases the chance that we find the
854 static av_always_inline int epzs_motion_search_internal(MpegEncContext * s, int *mx_ptr, int *my_ptr,
855 int P[10][2], int src_index, int ref_index, int16_t (*last_mv)[2],
856 int ref_mv_scale, int flags, int size, int h)
858 MotionEstContext * const c= &s->me;
859 int best[2]={0, 0}; /**< x and y coordinates of the best motion vector.
860 i.e. the difference between the position of the
861 block currently being encoded and the position of
862 the block chosen to predict it from. */
863 int d; ///< the score (cmp + penalty) of any given mv
864 int dmin; /**< the best value of d, i.e. the score
865 corresponding to the mv stored in best[]. */
866 unsigned map_generation;
868 const int ref_mv_stride= s->mb_stride; //pass as arg FIXME
869 const int ref_mv_xy= s->mb_x + s->mb_y*ref_mv_stride; //add to last_mv beforepassing FIXME
870 me_cmp_func cmpf, chroma_cmpf;
876 penalty_factor= c->pre_penalty_factor;
877 cmpf= s->dsp.me_pre_cmp[size];
878 chroma_cmpf= s->dsp.me_pre_cmp[size+1];
880 penalty_factor= c->penalty_factor;
881 cmpf= s->dsp.me_cmp[size];
882 chroma_cmpf= s->dsp.me_cmp[size+1];
885 map_generation= update_map_generation(c);
888 dmin= cmp(s, 0, 0, 0, 0, size, h, ref_index, src_index, cmpf, chroma_cmpf, flags);
889 map[0]= map_generation;
892 //FIXME precalc first term below?
893 if((s->pict_type == AV_PICTURE_TYPE_B && !(c->flags & FLAG_DIRECT)) || s->flags&CODEC_FLAG_MV0)
894 dmin += (mv_penalty[pred_x] + mv_penalty[pred_y])*penalty_factor;
897 if (s->first_slice_line) {
898 CHECK_MV(P_LEFT[0]>>shift, P_LEFT[1]>>shift)
899 CHECK_CLIPPED_MV((last_mv[ref_mv_xy][0]*ref_mv_scale + (1<<15))>>16,
900 (last_mv[ref_mv_xy][1]*ref_mv_scale + (1<<15))>>16)
902 if(dmin<((h*h*s->avctx->mv0_threshold)>>8)
903 && ( P_LEFT[0] |P_LEFT[1]
905 |P_TOPRIGHT[0]|P_TOPRIGHT[1])==0){
911 CHECK_MV( P_MEDIAN[0] >>shift , P_MEDIAN[1] >>shift)
912 CHECK_CLIPPED_MV((P_MEDIAN[0]>>shift) , (P_MEDIAN[1]>>shift)-1)
913 CHECK_CLIPPED_MV((P_MEDIAN[0]>>shift) , (P_MEDIAN[1]>>shift)+1)
914 CHECK_CLIPPED_MV((P_MEDIAN[0]>>shift)-1, (P_MEDIAN[1]>>shift) )
915 CHECK_CLIPPED_MV((P_MEDIAN[0]>>shift)+1, (P_MEDIAN[1]>>shift) )
916 CHECK_CLIPPED_MV((last_mv[ref_mv_xy][0]*ref_mv_scale + (1<<15))>>16,
917 (last_mv[ref_mv_xy][1]*ref_mv_scale + (1<<15))>>16)
918 CHECK_MV(P_LEFT[0] >>shift, P_LEFT[1] >>shift)
919 CHECK_MV(P_TOP[0] >>shift, P_TOP[1] >>shift)
920 CHECK_MV(P_TOPRIGHT[0]>>shift, P_TOPRIGHT[1]>>shift)
924 CHECK_CLIPPED_MV((last_mv[ref_mv_xy-1][0]*ref_mv_scale + (1<<15))>>16,
925 (last_mv[ref_mv_xy-1][1]*ref_mv_scale + (1<<15))>>16)
926 if(!s->first_slice_line)
927 CHECK_CLIPPED_MV((last_mv[ref_mv_xy-ref_mv_stride][0]*ref_mv_scale + (1<<15))>>16,
928 (last_mv[ref_mv_xy-ref_mv_stride][1]*ref_mv_scale + (1<<15))>>16)
930 CHECK_CLIPPED_MV((last_mv[ref_mv_xy+1][0]*ref_mv_scale + (1<<15))>>16,
931 (last_mv[ref_mv_xy+1][1]*ref_mv_scale + (1<<15))>>16)
932 if(s->mb_y+1<s->end_mb_y) //FIXME replace at least with last_slice_line
933 CHECK_CLIPPED_MV((last_mv[ref_mv_xy+ref_mv_stride][0]*ref_mv_scale + (1<<15))>>16,
934 (last_mv[ref_mv_xy+ref_mv_stride][1]*ref_mv_scale + (1<<15))>>16)
938 if(c->avctx->last_predictor_count){
939 const int count= c->avctx->last_predictor_count;
940 const int xstart= FFMAX(0, s->mb_x - count);
941 const int ystart= FFMAX(0, s->mb_y - count);
942 const int xend= FFMIN(s->mb_width , s->mb_x + count + 1);
943 const int yend= FFMIN(s->mb_height, s->mb_y + count + 1);
946 for(mb_y=ystart; mb_y<yend; mb_y++){
948 for(mb_x=xstart; mb_x<xend; mb_x++){
949 const int xy= mb_x + 1 + (mb_y + 1)*ref_mv_stride;
950 int mx= (last_mv[xy][0]*ref_mv_scale + (1<<15))>>16;
951 int my= (last_mv[xy][1]*ref_mv_scale + (1<<15))>>16;
953 if(mx>xmax || mx<xmin || my>ymax || my<ymin) continue;
959 //check(best[0],best[1],0, b0)
960 dmin= diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
962 //check(best[0],best[1],0, b1)
966 // printf("%d %d %d \n", best[0], best[1], dmin);
970 //this function is dedicated to the braindamaged gcc
971 av_extern_inline int ff_epzs_motion_search(MpegEncContext * s, int *mx_ptr, int *my_ptr,
972 int P[10][2], int src_index, int ref_index, int16_t (*last_mv)[2],
973 int ref_mv_scale, int size, int h)
975 MotionEstContext * const c= &s->me;
976 //FIXME convert other functions in the same way if faster
977 if(c->flags==0 && h==16 && size==0){
978 return epzs_motion_search_internal(s, mx_ptr, my_ptr, P, src_index, ref_index, last_mv, ref_mv_scale, 0, 0, 16);
980 // return epzs_motion_search_internal(s, mx_ptr, my_ptr, P, src_index, ref_index, last_mv, ref_mv_scale, FLAG_QPEL);
982 return epzs_motion_search_internal(s, mx_ptr, my_ptr, P, src_index, ref_index, last_mv, ref_mv_scale, c->flags, size, h);
986 static int epzs_motion_search4(MpegEncContext * s,
987 int *mx_ptr, int *my_ptr, int P[10][2],
988 int src_index, int ref_index, int16_t (*last_mv)[2],
991 MotionEstContext * const c= &s->me;
994 unsigned map_generation;
995 const int penalty_factor= c->penalty_factor;
998 const int ref_mv_stride= s->mb_stride;
999 const int ref_mv_xy= s->mb_x + s->mb_y *ref_mv_stride;
1000 me_cmp_func cmpf, chroma_cmpf;
1002 int flags= c->flags;
1005 cmpf= s->dsp.me_cmp[size];
1006 chroma_cmpf= s->dsp.me_cmp[size+1];
1008 map_generation= update_map_generation(c);
1011 //printf("%d %d %d %d //",xmin, ymin, xmax, ymax);
1013 if (s->first_slice_line) {
1014 CHECK_MV(P_LEFT[0]>>shift, P_LEFT[1]>>shift)
1015 CHECK_CLIPPED_MV((last_mv[ref_mv_xy][0]*ref_mv_scale + (1<<15))>>16,
1016 (last_mv[ref_mv_xy][1]*ref_mv_scale + (1<<15))>>16)
1017 CHECK_MV(P_MV1[0]>>shift, P_MV1[1]>>shift)
1019 CHECK_MV(P_MV1[0]>>shift, P_MV1[1]>>shift)
1020 //FIXME try some early stop
1021 CHECK_MV(P_MEDIAN[0]>>shift, P_MEDIAN[1]>>shift)
1022 CHECK_MV(P_LEFT[0]>>shift, P_LEFT[1]>>shift)
1023 CHECK_MV(P_TOP[0]>>shift, P_TOP[1]>>shift)
1024 CHECK_MV(P_TOPRIGHT[0]>>shift, P_TOPRIGHT[1]>>shift)
1025 CHECK_CLIPPED_MV((last_mv[ref_mv_xy][0]*ref_mv_scale + (1<<15))>>16,
1026 (last_mv[ref_mv_xy][1]*ref_mv_scale + (1<<15))>>16)
1029 CHECK_CLIPPED_MV((last_mv[ref_mv_xy+1][0]*ref_mv_scale + (1<<15))>>16,
1030 (last_mv[ref_mv_xy+1][1]*ref_mv_scale + (1<<15))>>16)
1031 if(s->mb_y+1<s->end_mb_y) //FIXME replace at least with last_slice_line
1032 CHECK_CLIPPED_MV((last_mv[ref_mv_xy+ref_mv_stride][0]*ref_mv_scale + (1<<15))>>16,
1033 (last_mv[ref_mv_xy+ref_mv_stride][1]*ref_mv_scale + (1<<15))>>16)
1036 dmin= diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
1041 // printf("%d %d %d \n", best[0], best[1], dmin);
1045 //try to merge with above FIXME (needs PSNR test)
1046 static int epzs_motion_search2(MpegEncContext * s,
1047 int *mx_ptr, int *my_ptr, int P[10][2],
1048 int src_index, int ref_index, int16_t (*last_mv)[2],
1051 MotionEstContext * const c= &s->me;
1054 unsigned map_generation;
1055 const int penalty_factor= c->penalty_factor;
1056 const int size=0; //FIXME pass as arg
1058 const int ref_mv_stride= s->mb_stride;
1059 const int ref_mv_xy= s->mb_x + s->mb_y *ref_mv_stride;
1060 me_cmp_func cmpf, chroma_cmpf;
1062 int flags= c->flags;
1065 cmpf= s->dsp.me_cmp[size];
1066 chroma_cmpf= s->dsp.me_cmp[size+1];
1068 map_generation= update_map_generation(c);
1071 //printf("%d %d %d %d //",xmin, ymin, xmax, ymax);
1073 if (s->first_slice_line) {
1074 CHECK_MV(P_LEFT[0]>>shift, P_LEFT[1]>>shift)
1075 CHECK_CLIPPED_MV((last_mv[ref_mv_xy][0]*ref_mv_scale + (1<<15))>>16,
1076 (last_mv[ref_mv_xy][1]*ref_mv_scale + (1<<15))>>16)
1077 CHECK_MV(P_MV1[0]>>shift, P_MV1[1]>>shift)
1079 CHECK_MV(P_MV1[0]>>shift, P_MV1[1]>>shift)
1080 //FIXME try some early stop
1081 CHECK_MV(P_MEDIAN[0]>>shift, P_MEDIAN[1]>>shift)
1082 CHECK_MV(P_LEFT[0]>>shift, P_LEFT[1]>>shift)
1083 CHECK_MV(P_TOP[0]>>shift, P_TOP[1]>>shift)
1084 CHECK_MV(P_TOPRIGHT[0]>>shift, P_TOPRIGHT[1]>>shift)
1085 CHECK_CLIPPED_MV((last_mv[ref_mv_xy][0]*ref_mv_scale + (1<<15))>>16,
1086 (last_mv[ref_mv_xy][1]*ref_mv_scale + (1<<15))>>16)
1089 CHECK_CLIPPED_MV((last_mv[ref_mv_xy+1][0]*ref_mv_scale + (1<<15))>>16,
1090 (last_mv[ref_mv_xy+1][1]*ref_mv_scale + (1<<15))>>16)
1091 if(s->mb_y+1<s->end_mb_y) //FIXME replace at least with last_slice_line
1092 CHECK_CLIPPED_MV((last_mv[ref_mv_xy+ref_mv_stride][0]*ref_mv_scale + (1<<15))>>16,
1093 (last_mv[ref_mv_xy+ref_mv_stride][1]*ref_mv_scale + (1<<15))>>16)
1096 dmin= diamond_search(s, best, dmin, src_index, ref_index, penalty_factor, size, h, flags);
1101 // printf("%d %d %d \n", best[0], best[1], dmin);