* Three macro definitions defined in this program:
 * 1. EARLY_TERMINATION: early termination algrithm, refer to JVT-D016.doc
 * 2. SEARCH_ONE_PIXEL: search one pixel in search range
 * 3. SEARCH_ONE_PIXEL1(value_iAbort): search one pixel in search range,
 *                                 but give a parameter to show if mincost refeshed
 * \author
 *   Main contributors: (see contributors.h for copyright, address and affiliation details)
 *   - Zhibo Chen         <chenzhibo@tsinghua.org.cn>
 *   - JianFeng Xu        <fenax@video.mdc.tsinghua.edu.cn>  
 * \date   :
 *   2003.8
 ************************************************************************
 */
int                                     //  ==> minimum motion cost after search
FastIntegerPelBlockMotionSearch  (pel_t**   orig_pic,     // <--  not used
                  int       ref,          // <--  reference frame (0... or -1 (backward))
                  int       list,
                  int       pic_pix_x,    // <--  absolute x-coordinate of regarded AxB block
                  int       pic_pix_y,    // <--  absolute y-coordinate of regarded AxB block
                  int       blocktype,    // <--  block type (1-16x16 ... 7-4x4)
                  int       pred_mv_x,    // <--  motion vector predictor (x) in sub-pel units
                  int       pred_mv_y,    // <--  motion vector predictor (y) in sub-pel units
                  int*      mv_x,         //  --> motion vector (x) - in pel units
                  int*      mv_y,         //  --> motion vector (y) - in pel units
                  int       search_range, // <--  1-d search range in pel units                         
                  int       min_mcost,    // <--  minimum motion cost (cost for center or huge value)
                  double    lambda)       // <--  lagrangian parameter for determining motion cost
{
  static int Diamond_x[4] = {-1, 0, 1, 0};
  static int Diamond_y[4] = {0, 1, 0, -1};
  static int Hexagon_x[6] = {2, 1, -1, -2, -1, 1};
  static int Hexagon_y[6] = {0, -2, -2, 0,  2, 2};
  static int Big_Hexagon_x[16] = {0,-2, -4,-4,-4, -4, -4, -2,  0,  2,  4,  4, 4, 4, 4, 2};
  static int Big_Hexagon_y[16] = {4, 3, 2,  1, 0, -1, -2, -3, -4, -3, -2, -1, 0, 1, 2, 3};

  int   pos, cand_x, cand_y,  mcost;
  pel_t *(*get_ref_line)(int, pel_t*, int, int, int, int);
  int   list_offset   = ((img->MbaffFrameFlag)&&(img->mb_data[img->current_mb_nr].mb_field))? img->current_mb_nr%2 ? 4 : 2 : 0;
  pel_t*  ref_pic       = listX[list+list_offset][ref]->imgY_11;//img->type==B_IMG? Refbuf11 [ref+((mref==mref_fld)) +1] : Refbuf11[ref];
  int   lambda_factor = LAMBDA_FACTOR (lambda);                   // factor for determining lagragian motion cost
  int   mvshift       = 2;                  // motion vector shift for getting sub-pel units
  int   blocksize_y   = input->blc_size[blocktype][1];            // vertical block size
  int   blocksize_x   = input->blc_size[blocktype][0];            // horizontal block size
  int   blocksize_x4  = blocksize_x >> 2;                         // horizontal block size in 4-pel units
  int   pred_x        = (pic_pix_x << mvshift) + pred_mv_x;       // predicted position x (in sub-pel units)
  int   pred_y        = (pic_pix_y << mvshift) + pred_mv_y;       // predicted position y (in sub-pel units)
  int   center_x      = pic_pix_x + *mv_x;                        // center position x (in pel units)
  int   center_y      = pic_pix_y + *mv_y;                        // center position y (in pel units)
  int   best_x = 0, best_y = 0;
  int   search_step,iYMinNow, iXMinNow;
  int   i,m, iSADLayer; 
  int   iAbort;
  int   N_Bframe = input->successive_Bframe;
  float betaSec,betaThird;
  int height=((img->MbaffFrameFlag)&&(img->mb_data[img->current_mb_nr].mb_field))?img->height/2:img->height;
   

  //===== set function for getting reference picture lines =====
  if ((center_x > search_range) && (center_x < img->width -1-search_range-blocksize_x) &&
    (center_y > search_range) && (center_y < height-1-search_range-blocksize_y)   )
  {
    get_ref_line = FastLineX;
  }
  else
  {
    get_ref_line = UMVLineX;
  }
  
  //////allocate memory for search state//////////////////////////
  memset(McostState[0],0,(2*search_range+1)*(2*search_range+1)*4);
  
   ///////Threshold defined for early termination///////////////////  
  if(ref>0) 
  {
    if(pred_SAD_ref!=0)
    {
      betaSec = Bsize[blocktype]/(pred_SAD_ref*pred_SAD_ref)-AlphaSec[blocktype];
      betaThird = Bsize[blocktype]/(pred_SAD_ref*pred_SAD_ref)-AlphaThird[blocktype];
    }
    else
    {
      betaSec = 0;
      betaThird = 0;
    }
  }
  else 
  {
    if(blocktype==1)
    {
      if(pred_SAD_space !=0)
      {
        betaSec = Bsize[blocktype]/(pred_SAD_space*pred_SAD_space)-AlphaSec[blocktype];
        betaThird = Bsize[blocktype]/(pred_SAD_space*pred_SAD_space)-AlphaThird[blocktype];
      }
      else
      {
        betaSec = 0;
        betaThird = 0;
      }
    }
    else
    {
      if(pred_SAD_uplayer !=0)
      {
        betaSec = Bsize[blocktype]/(pred_SAD_uplayer*pred_SAD_uplayer)-AlphaSec[blocktype];
        betaThird = Bsize[blocktype]/(pred_SAD_uplayer*pred_SAD_uplayer)-AlphaThird[blocktype];
      }
      else
      {
        betaSec = 0;
        betaThird = 0;
      }
    }
  }
  /*****************************/

  //check the center median predictor
  cand_x = center_x ;
  cand_y = center_y ;
  mcost = MV_COST (lambda_factor, mvshift, cand_x, cand_y, pred_x, pred_y);
  mcost = PartCalMad(ref_pic, orig_pic, get_ref_line,blocksize_y,blocksize_x,blocksize_x4,mcost,min_mcost,cand_x,cand_y);
  McostState[search_range][search_range] = mcost;
  if (mcost < min_mcost)
  {
    min_mcost = mcost;
    best_x = cand_x;
    best_y = cand_y;
  }

  iXMinNow = best_x;
  iYMinNow = best_y;
  for (m = 0; m < 4; m++)
  {   
    cand_x = iXMinNow + Diamond_x[m];
    cand_y = iYMinNow + Diamond_y[m];   
    SEARCH_ONE_PIXEL
  } 

  if(center_x != pic_pix_x || center_y != pic_pix_y)
  {
    cand_x = pic_pix_x ;
    cand_y = pic_pix_y ;
    SEARCH_ONE_PIXEL

    iXMinNow = best_x;
    iYMinNow = best_y;
    for (m = 0; m < 4; m++)
    {   
      cand_x = iXMinNow + Diamond_x[m];
      cand_y = iYMinNow + Diamond_y[m];   
      SEARCH_ONE_PIXEL
    } 
  }
  
    if(blocktype>1)
  {
    cand_x = pic_pix_x + (pred_MV_uplayer[0]/4);
    cand_y = pic_pix_y + (pred_MV_uplayer[1]/4);
    SEARCH_ONE_PIXEL
    if ((min_mcost-pred_SAD_uplayer)<pred_SAD_uplayer*betaThird)
      goto third_step;
    else if((min_mcost-pred_SAD_uplayer)<pred_SAD_uplayer*betaSec)
      goto sec_step;
  } 

  //coordinate position prediction
  if ((img->number > 1 + ref && ref!=-1) || (list == 1 && (Bframe_ctr%N_Bframe) > 1))  //for debug
  {
    cand_x = pic_pix_x + pred_MV_time[0]/4;
    cand_y = pic_pix_y + pred_MV_time[1]/4;
    SEARCH_ONE_PIXEL
  }

  //prediciton using mV of last ref moiton vector
  if (input->PicInterlace == FIELD_CODING)
  {
    if ((list==0 && ref > 0) || (img->type == B_SLICE && list == 0 && (ref==0 ||ref==2 ) )) 
      //Notes: for interlace case, ref==1 should be added
    {
      cand_x = pic_pix_x + pred_MV_ref[0]/4;
      cand_y = pic_pix_y + pred_MV_ref[1]/4;
      SEARCH_ONE_PIXEL
    }
  }
  else
  {
    if ((list==0 && ref > 0) || (img->type == B_SLICE && list == 0 && ref==0 )) 
      //Notes: for interlace case, ref==1 should be added
    {
      cand_x = pic_pix_x + pred_MV_ref[0]/4;
      cand_y = pic_pix_y + pred_MV_ref[1]/4;
      SEARCH_ONE_PIXEL
    }
  }
  //small local search
  iXMinNow = best_x;
  iYMinNow = best_y;
  for (m = 0; m < 4; m++)
  {   
    cand_x = iXMinNow + Diamond_x[m];
    cand_y = iYMinNow + Diamond_y[m];   
    SEARCH_ONE_PIXEL
  } 

  //early termination algrithm, refer to JVT-D016
    EARLY_TERMINATION
  
  if(blocktype>6)
    goto sec_step;
  else
    goto first_step;
  
first_step: //Unsymmetrical-cross search 
  iXMinNow = best_x;
  iYMinNow = best_y;
  
  for(i=1;i<=search_range/2;i++)
  {
    search_step = 2*i - 1;
    cand_x = iXMinNow + search_step;
    cand_y = iYMinNow ;
    SEARCH_ONE_PIXEL    
    cand_x = iXMinNow - search_step;
    cand_y = iYMinNow ;
    SEARCH_ONE_PIXEL
  }
  
  for(i=1;i<=search_range/4;i++)
  {
    search_step = 2*i - 1;
    cand_x = iXMinNow ;
    cand_y = iYMinNow + search_step;
    SEARCH_ONE_PIXEL
    cand_x = iXMinNow ;
    cand_y = iYMinNow - search_step;
    SEARCH_ONE_PIXEL
  }
  //early termination algrithm, refer to JVT-D016
    EARLY_TERMINATION
  
  iXMinNow = best_x;
  iYMinNow = best_y;
    // Uneven Multi-Hexagon-grid Search 
  for(pos=1;pos<25;pos++)
  {
    cand_x = iXMinNow + spiral_search_x[pos];
    cand_y = iYMinNow + spiral_search_y[pos];
    SEARCH_ONE_PIXEL
  }
  //early termination algrithm, refer to JVT-D016
    EARLY_TERMINATION
  
  for(i=1;i<=search_range/4; i++)
  {
    iAbort = 0;   
    for (m = 0; m < 16; m++)
    {
      cand_x = iXMinNow + Big_Hexagon_x[m]*i;
      cand_y = iYMinNow + Big_Hexagon_y[m]*i; 
      SEARCH_ONE_PIXEL1(1)
    }
    if (iAbort)
    { 
      //early termination algrithm, refer to JVT-D016
      EARLY_TERMINATION
    }
  }
sec_step:  //Extended Hexagon-based Search
      iXMinNow = best_x;
      iYMinNow = best_y;
      for(i=0;i<search_range;i++) 
      {
        iAbort = 1;   
        for (m = 0; m < 6; m++)
        {   
          cand_x = iXMinNow + Hexagon_x[m];
          cand_y = iYMinNow + Hexagon_y[m];   
          SEARCH_ONE_PIXEL1(0)
        } 
        if(iAbort)
          break;
        iXMinNow = best_x;
        iYMinNow = best_y;
      }
third_step: // the third step with a small search pattern
      iXMinNow = best_x;
      iYMinNow = best_y;
      for(i=0;i<search_range;i++) 
      {
        iSADLayer = 65536;
        iAbort = 1;   
        for (m = 0; m < 4; m++)
        {   
          cand_x = iXMinNow + Diamond_x[m];
          cand_y = iYMinNow + Diamond_y[m];   
          SEARCH_ONE_PIXEL1(0)
        } 
        if(iAbort)
          break;