/*COPYRIGHT, LICENSE AND WARRANTY INFORMATIONThis software module has been originally developed by Nokia Corporation. Provided that a person, entity or a company willing to use the Software (hereinafter Licensee) comply with all the terms and conditions of this Statement and subject to the limitations set forth in this Statement Nokia grants to such Licensee a non-exclusive, sub-licensable, worldwide, limited license under copyrights owned by Nokia to use the Software for the sole purpose of creating, manufacturing, selling, marketing, or  distributing (including the right to make modifications to the Software) a fully compliant decoder implementation (hereinafter "Decoder") of ITU-T Recommendation H.264 / ISO/IEC International Standard 14496-10 and an encoder implementation producing output that is decodable with the Decoder.Nokia retains the ownership of copyrights to the Software. There is no patent nor other intellectual property right of Nokia licensed under this Statement (except the copyright license above). Licensee hereby assumes sole responsibility to secure any other intellectual property rights needed, if any. For example, if patent licenses  are required, it is their responsibility to acquire the license before utilizing the Software.The license by Nokia is subject to that the Licensee grants to Nokia the non-exclusive, worldwide, royalty-free, perpetual and irrevocable covenant that the Licensee(s) shall not bring a suit before any court or administrative agency or otherwise assert a claim for infringement under the Licensee intellectual property rights that, but for a license, would be infringed by the Software against     (a)  Nokia or Nokia's Affiliate; or     (b)  other recipient of a license and covenant not to sue with respect         to the Software from Nokia; or    (c)  contractor, customer or distributor of a party listed above in a         or b,  which suit or claim is related to the Software or use thereof.The Licensee(s) further agrees to grant a reciprocal license to Nokia (as granted by Nokia to the Licensee(s) on the modifications made by Licensee(s) to the Software. THE SOFTWARE IS PROVIDED "AS IS" AND THE ORIGINAL DEVELOPER DISCLAIMS ANY AND ALL WARRANTIES WHETHER EXPRESS, IMPLIED OR STATUTORY, INCLUDING BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. THOSE INTENDING TO USE THE SOFTWARE ARE EXPRESSLY ADVISED THAT ITS USE MAY INFRINGE EXISTING PATENTS AND BE SUBJECT TO ROYALTY PAYMENTS TO PATENT OWNERS. ANYONE USING THE SOFTWARE ON THE BASIS OF THIS LICENSE AGREES TO OBTAIN THE NECESSARY PERMISSIONS FROM ANY AND ALL APPLICABLE PATENT OWNERS FOR SUCH USE.IN NO EVENT SHALL THE ORIGINAL DEVELOPER BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.This copyright, license and warranty information notice must be retained in all copies and derivative works of the Software or substantial portions thereof.*/#include <limits.h>#include <string.h>#include "globals.h"#include "debug.h"#include "vlcutility.h"#include "transform.h"#include "motcomp.h"#include "meutility.h"#include "macroblock.h"#include "stream.h"#define CENTER_PRED_MV              0#define CENTER_LARGER_BLOCK_MV      1#define SAD_NOT_AVAILABLE     0#define SAD_AVAILABLE         1#define MAX_SUB_MB_RECT_SIZE  576/* * * mesMultiStepSearch: * * Parameters: *      blk                 Buffer pointers and parameters related to the block *      pMeProf             Parameters for controlling ME *      bestVec             Best vector so far, will be updated at return *      bestSad             Minimum SAD so far, will be updated at return *      neighborSads        SAD of neighboring positions * * Function: *      Perform integer motion vector. Support sparse search. N-step search *      is the special case.  * * Returns: *      Return values are in bestVec and bestSad. * */static int mesMultiStepSearch(mbPart_s    *mbPart,                               meProfile_s *pMeProf,                               motVec_s    *bestVec,                              int         *bestSad,                              int         *neighborSads){  int startX, stopX, startY, stopY;  int subsamplingStep, offset, returnStat;  LC3_s *plc3= & (pMeProf->lc3);  subsamplingStep = pMeProf->subsampling;  // sparse search based on the step size, subsamplingStep must be 2's power  // subsamplingStep was in quater pixel precision, we shift by 1/2 step  offset = (subsamplingStep >> 3) * 4;  startX = pMeProf->p0[0];  startY = pMeProf->p0[1];  stopX  = pMeProf->p1[0];  stopY  = pMeProf->p1[1];  startX += offset;  stopX  -= offset;  startY += offset;  stopY  -= offset;   if ( (plc3->low_complex_prof3) && (plc3->spec_search_pos)    ) {    //   : do_16x8 must be 1 for 16x16 mode, and might become 0 when    // handling 16x8 or 8x16 mode    if (plc3->do_16x8)      matchBlockLong_MultiStep(mbPart, startX, stopX, startY, stopY, subsamplingStep, bestVec, bestSad);  }  else    matchBlockLong(mbPart, startX, stopX, startY, stopY, subsamplingStep, bestVec, bestSad, plc3->low_complex_prof3);  // refinement step-wise search to get the finer step size  returnStat = SAD_NOT_AVAILABLE;  if (mbPart->profile == PROF_CODING_SPEED)  {    // we do one step refinement and record the SADs at neighboring positions    if (subsamplingStep > 4)    {      neighborSads[0] = *bestSad;      // neighborSads[0] has been used above      if (matchBlockLocal4(mbPart, 4, bestVec, bestSad, neighborSads + 1))        // the best location has changed        returnStat = SAD_AVAILABLE;    }  }  else  {    while (subsamplingStep > 4)    {      // perform refinement search      subsamplingStep >>= 1;          // should always be 4 now      matchBlockDiamond(mbPart, subsamplingStep, bestVec, bestSad, 0);    }    returnStat = SAD_NOT_AVAILABLE;  }  return returnStat;}/* * * mesGradientSearch: * * Parameters: *      blk                 Buffer pointers and parameters related to the block *      pMeProf             Parameters for controlling ME *      bestVec             Best vector so far, will be updated at return *      bestSad             Minimum SAD so far, will be updated at return * * Function: *      Perform gradient search for integer motion vector. This is used as *      the refinement search stage if the best motion vector is located *      at the boundary of the search window. * * Returns: *      Return values are in bestVec and bestSad. * */void mesGradientSearch(mbPart_s    *mbPart,                        meProfile_s *pMeProf,                        motVec_s    *bestVec,                       int         *bestSad){  int i, loopCount;  int p0[2], p1[2];  p0[0] = pMeProf->p0[0];  p1[0] = pMeProf->p1[0];  p0[1] = pMeProf->p0[1];  p1[1] = pMeProf->p1[1];  loopCount = 0;  while ((bestVec->x == p0[0]) || (bestVec->x == p1[0]) ||    (bestVec->y == p0[1]) || (bestVec->y == p1[1]))  {    int searchDir[2], vec[2], tmp;    motVec_s prevBestVec;    vec[0] = bestVec->x;    vec[1] = bestVec->y;    for (i = 0; i < 2; i ++)    {      searchDir[i] = 0;      if (vec[i] == p1[i])      // upper boundary        searchDir[i] = 1;      else if (vec[i] == p0[i])    // lower boundary        searchDir[i] = -1;    }    if ((searchDir[0] != 0) && (searchDir[1] != 0))    {      // this is the corner      p0[0] = bestVec->x - searchDir[0] * 4;      p1[0] = bestVec->x + searchDir[0] * 12;      p0[1] = bestVec->y - searchDir[1] * 4;      p1[1] = bestVec->y + searchDir[1] * 12;    }    else    {      // this is at least 1 pixel away from the corner      if (searchDir[0] != 0)      {        p0[0] = bestVec->x + searchDir[0] * 4;        p1[0] = bestVec->x + searchDir[0] * 20;        p0[1] = bestVec->y - 8;          p1[1] = bestVec->y + 8;       }      else      {        p0[0] = bestVec->x - 8;          p1[0] = bestVec->x + 8;          p0[1] = bestVec->y + searchDir[1] * 4;        p1[1] = bestVec->y + searchDir[1] * 20;      }    }    for (i = 0; i < 2; i ++)    {      if (p0[i] > p1[i])      {        tmp   = p0[i];        p0[i] = p1[i];         p1[i] = tmp;      }      if (p0[i] < pMeProf->vecLmt0[i])        p0[i] = pMeProf->vecLmt0[i];      if (p1[i] >  pMeProf->vecLmt1[i])        p1[i] = pMeProf->vecLmt1[i];    }    prevBestVec = *bestVec;    matchBlockLong(mbPart, p0[0], p1[0], p0[1], p1[1], 4, bestVec, bestSad, pMeProf->lc3.low_complex_prof3);    // bestVec could be a new value    loopCount ++;    if (((prevBestVec.x == bestVec->x) && (prevBestVec.y == bestVec->y)) ||      (loopCount == 3))      break;  }}static int mySad2(mbPart_s *mbPart, int vecX, int vecY){  int currSad;  int lambda;  /* Take into account number fo bits spent for motion vector */  lambda = mbPart->lambdaCoarse;  currSad = lambda * (mbPart->vlcMvBitsX[vecX] + mbPart->vlcMvBitsY[vecY]);  if (mbPart->mode == MOT_16x16)  {    if ((vecY | vecX) == 0)      currSad -= lambda * ZERO_VEC_SAD;  }  /* Accumulate sad until no pels left or sad is worse than best so far */  currSad = findSAD2(mbPart->orig, mbPart->ref, mbPart->refWidth,     mbPart->width, mbPart->height, vecX, vecY, currSad, INT_MAX);  return currSad;}#define NO_HALF_PRED        -128#define NOT_REAL_SAD        -4096// estimate the half pixel location from 5 SADsstatic int mesPredictHalfPixel(mbPart_s *mbPart,                                int *neighborSads,                               int *halfPixelSads,                               motVec_s *bestVec,                               int *bestSad,                               int *direction){  int i, idx, centerSad, x, y;  int range[2], whoIsLarger[2], larger[2], center[2];//  int confidence[2], max[2];  // estimate at x direction  for (i = 0; i < 9; i ++)    halfPixelSads[i] = NOT_REAL_SAD;  halfPixelSads[4] = *bestSad;  center[0] = bestVec->x;  center[1] = bestVec->y;  centerSad = *bestSad;  // characterize the data and perform 1-D estimation  for (i = 0; i < 2; i ++)  {    direction[i] = NO_HALF_PRED;    if (neighborSads[1 + i] >= neighborSads[3 + i])    {      larger[i] = neighborSads[1 + i];      whoIsLarger[i] = 1;    }    else    {      larger[i] = neighborSads[3 + i];      whoIsLarger[i] = -1;    }    // neighborSads[0] is at center    range[i] = larger[i] - neighborSads[0];    if (i == 0)    // x direction    {      x = whoIsLarger[0];      y = 0;      idx = 3 + 1 + x;      x *= 2;    }    else          // y direction    {      x = 0;      y = whoIsLarger[1];      idx = (1 + y) * 3 + 1;      y *= 2;    }    halfPixelSads[idx] = mySad2(mbPart, center[0] + x, center[1] + y);    direction[i] = 0;    if (halfPixelSads[idx] < *bestSad)    {      *bestSad = halfPixelSads[idx];      bestVec->x = (int16) (center[0] + x);      bestVec->y = (int16) (center[1] + y);      direction[i] = whoIsLarger[i];    }  }  // let's find out how confident we are  if ((direction[1] != NO_HALF_PRED) && (direction[1] != NO_HALF_PRED))  {    if ((direction[0] != 0) && (direction[1] != 0))    {      // predict a diagonal half-pixel point, very un-reliable      int candidate;      int x0, y0;      // diagonal search,       x0 = direction[0];      y0 = direction[1];      idx = (1 + y0) * 3 + 1 + x0;      x0 *= 2;      y0 *= 2;      halfPixelSads[idx] = mySad2(mbPart, center[0] + x0, center[1] + y0);      candidate = 0;      if (halfPixelSads[idx] < *bestSad)      {        *bestSad = halfPixelSads[idx];        bestVec->x = (int16) (center[0] + x0);        bestVec->y = (int16) (center[1] + y0);        candidate = 1;      }    }  }  return (direction[0] != NO_HALF_PRED) && (direction[1] != NO_HALF_PRED);}