* blk: top left pel of (16*h) block * h: height of block * lx: distance (in bytes) of vertically adjacent pels in ref,blk * org: top left pel of source reference picture * ref: top left pel of reconstructed reference picture * i0,j0: center of search window * sx,sy: half widths of search window * xmax,ymax: right/bottom limits of search area * iminp,jminp: pointers to where the result is stored *              result is given as half pel offset from ref(0,0) *              i.e. NOT relative to (i0,j0) */static int fullsearch(org,ref,blk,lx,i0,j0,sx,sy,h,xmax,ymax,iminp,jminp)unsigned char *org,*ref,*blk;int lx,i0,j0,sx,sy,h,xmax,ymax;int *iminp,*jminp;{  int i,j,imin,jmin,ilow,ihigh,jlow,jhigh;  int d,dmin;  int k,l,sxy;  ilow = i0 - sx;  ihigh = i0 + sx;  if (ilow<0)    ilow = 0;  if (ihigh>xmax-16)    ihigh = xmax-16;  jlow = j0 - sy;  jhigh = j0 + sy;  if (jlow<0)    jlow = 0;  if (jhigh>ymax-h)    jhigh = ymax-h;  /* full pel search, spiraling outwards */  imin = i0;  jmin = j0;  dmin = dist1(org+imin+lx*jmin,blk,lx,0,0,h,65536);  sxy = (sx>sy) ? sx : sy;  for (l=1; l<=sxy; l++)  {    i = i0 - l;    j = j0 - l;    for (k=0; k<8*l; k++)    {      if (i>=ilow && i<=ihigh && j>=jlow && j<=jhigh)      {        d = dist1(org+i+lx*j,blk,lx,0,0,h,dmin);        if (d<dmin)        {          dmin = d;          imin = i;          jmin = j;        }      }      if      (k<2*l) i++;      else if (k<4*l) j++;      else if (k<6*l) i--;      else            j--;    }  }  /* half pel */  dmin = 65536;  imin <<= 1;  jmin <<= 1;  ilow = imin - (imin>0);  ihigh = imin + (imin<((xmax-16)<<1));  jlow = jmin - (jmin>0);  jhigh = jmin + (jmin<((ymax-h)<<1));  for (j=jlow; j<=jhigh; j++)    for (i=ilow; i<=ihigh; i++)    {      d = dist1(ref+(i>>1)+lx*(j>>1),blk,lx,i&1,j&1,h,dmin);      if (d<dmin)      {        dmin = d;        imin = i;        jmin = j;      }    }  *iminp = imin;  *jminp = jmin;  return dmin;}/* * total absolute difference between two (16*h) blocks * including optional half pel interpolation of blk1 (hx,hy) * blk1,blk2: addresses of top left pels of both blocks * lx:        distance (in bytes) of vertically adjacent pels * hx,hy:     flags for horizontal and/or vertical interpolation * h:         height of block (usually 8 or 16) * distlim:   bail out if sum exceeds this value */static int dist1(blk1,blk2,lx,hx,hy,h,distlim)unsigned char *blk1,*blk2;int lx,hx,hy,h;int distlim;{  unsigned char *p1,*p1a,*p2;  int i,j;  int s,v;  s = 0;  p1 = blk1;  p2 = blk2;  if (!hx && !hy)    for (j=0; j<h; j++)    {      if ((v = p1[0]  - p2[0])<0)  v = -v; s+= v;      if ((v = p1[1]  - p2[1])<0)  v = -v; s+= v;      if ((v = p1[2]  - p2[2])<0)  v = -v; s+= v;      if ((v = p1[3]  - p2[3])<0)  v = -v; s+= v;      if ((v = p1[4]  - p2[4])<0)  v = -v; s+= v;      if ((v = p1[5]  - p2[5])<0)  v = -v; s+= v;      if ((v = p1[6]  - p2[6])<0)  v = -v; s+= v;      if ((v = p1[7]  - p2[7])<0)  v = -v; s+= v;      if ((v = p1[8]  - p2[8])<0)  v = -v; s+= v;      if ((v = p1[9]  - p2[9])<0)  v = -v; s+= v;      if ((v = p1[10] - p2[10])<0) v = -v; s+= v;      if ((v = p1[11] - p2[11])<0) v = -v; s+= v;      if ((v = p1[12] - p2[12])<0) v = -v; s+= v;      if ((v = p1[13] - p2[13])<0) v = -v; s+= v;      if ((v = p1[14] - p2[14])<0) v = -v; s+= v;      if ((v = p1[15] - p2[15])<0) v = -v; s+= v;      if (s >= distlim)        break;      p1+= lx;      p2+= lx;    }  else if (hx && !hy)    for (j=0; j<h; j++)    {      for (i=0; i<16; i++)      {        v = ((unsigned int)(p1[i]+p1[i+1]+1)>>1) - p2[i];        if (v>=0)          s+= v;        else          s-= v;      }      p1+= lx;      p2+= lx;    }  else if (!hx && hy)  {    p1a = p1 + lx;    for (j=0; j<h; j++)    {      for (i=0; i<16; i++)      {        v = ((unsigned int)(p1[i]+p1a[i]+1)>>1) - p2[i];        if (v>=0)          s+= v;        else          s-= v;      }      p1 = p1a;      p1a+= lx;      p2+= lx;    }  }  else /* if (hx && hy) */  {    p1a = p1 + lx;    for (j=0; j<h; j++)    {      for (i=0; i<16; i++)      {        v = ((unsigned int)(p1[i]+p1[i+1]+p1a[i]+p1a[i+1]+2)>>2) - p2[i];        if (v>=0)          s+= v;        else          s-= v;      }      p1 = p1a;      p1a+= lx;      p2+= lx;    }  }  return s;}/* * total squared difference between two (16*h) blocks * including optional half pel interpolation of blk1 (hx,hy) * blk1,blk2: addresses of top left pels of both blocks * lx:        distance (in bytes) of vertically adjacent pels * hx,hy:     flags for horizontal and/or vertical interpolation * h:         height of block (usually 8 or 16) */static int dist2(blk1,blk2,lx,hx,hy,h)unsigned char *blk1,*blk2;int lx,hx,hy,h;{  unsigned char *p1,*p1a,*p2;  int i,j;  int s,v;  s = 0;  p1 = blk1;  p2 = blk2;  if (!hx && !hy)    for (j=0; j<h; j++)    {      for (i=0; i<16; i++)      {        v = p1[i] - p2[i];        s+= v*v;      }      p1+= lx;      p2+= lx;    }  else if (hx && !hy)    for (j=0; j<h; j++)    {      for (i=0; i<16; i++)      {        v = ((unsigned int)(p1[i]+p1[i+1]+1)>>1) - p2[i];        s+= v*v;      }      p1+= lx;      p2+= lx;    }  else if (!hx && hy)  {    p1a = p1 + lx;    for (j=0; j<h; j++)    {      for (i=0; i<16; i++)      {        v = ((unsigned int)(p1[i]+p1a[i]+1)>>1) - p2[i];        s+= v*v;      }      p1 = p1a;      p1a+= lx;      p2+= lx;    }  }  else /* if (hx && hy) */  {    p1a = p1 + lx;    for (j=0; j<h; j++)    {      for (i=0; i<16; i++)      {        v = ((unsigned int)(p1[i]+p1[i+1]+p1a[i]+p1a[i+1]+2)>>2) - p2[i];        s+= v*v;      }      p1 = p1a;      p1a+= lx;      p2+= lx;    }  }  return s;}/* * absolute difference error between a (16*h) block and a bidirectional * prediction * * p2: address of top left pel of block * pf,hxf,hyf: address and half pel flags of forward ref. block * pb,hxb,hyb: address and half pel flags of backward ref. block * h: height of block * lx: distance (in bytes) of vertically adjacent pels in p2,pf,pb */static int bdist1(pf,pb,p2,lx,hxf,hyf,hxb,hyb,h)unsigned char *pf,*pb,*p2;int lx,hxf,hyf,hxb,hyb,h;{  unsigned char *pfa,*pfb,*pfc,*pba,*pbb,*pbc;  int i,j;  int s,v;  pfa = pf + hxf;  pfb = pf + lx*hyf;  pfc = pfb + hxf;  pba = pb + hxb;  pbb = pb + lx*hyb;  pbc = pbb + hxb;  s = 0;  for (j=0; j<h; j++)  {    for (i=0; i<16; i++)    {      v = ((((unsigned int)(*pf++ + *pfa++ + *pfb++ + *pfc++ + 2)>>2) +            ((unsigned int)(*pb++ + *pba++ + *pbb++ + *pbc++ + 2)>>2) + 1)>>1)           - *p2++;      if (v>=0)        s+= v;      else        s-= v;    }    p2+= lx-16;    pf+= lx-16;    pfa+= lx-16;    pfb+= lx-16;    pfc+= lx-16;    pb+= lx-16;    pba+= lx-16;    pbb+= lx-16;    pbc+= lx-16;  }  return s;}/* * squared error between a (16*h) block and a bidirectional * prediction * * p2: address of top left pel of block * pf,hxf,hyf: address and half pel flags of forward ref. block * pb,hxb,hyb: address and half pel flags of backward ref. block * h: height of block * lx: distance (in bytes) of vertically adjacent pels in p2,pf,pb */static int bdist2(pf,pb,p2,lx,hxf,hyf,hxb,hyb,h)unsigned char *pf,*pb,*p2;int lx,hxf,hyf,hxb,hyb,h;{  unsigned char *pfa,*pfb,*pfc,*pba,*pbb,*pbc;  int i,j;  int s,v;  pfa = pf + hxf;  pfb = pf + lx*hyf;  pfc = pfb + hxf;  pba = pb + hxb;  pbb = pb + lx*hyb;  pbc = pbb + hxb;  s = 0;  for (j=0; j<h; j++)  {    for (i=0; i<16; i++)    {      v = ((((unsigned int)(*pf++ + *pfa++ + *pfb++ + *pfc++ + 2)>>2) +            ((unsigned int)(*pb++ + *pba++ + *pbb++ + *pbc++ + 2)>>2) + 1)>>1)          - *p2++;      s+=v*v;    }    p2+= lx-16;    pf+= lx-16;    pfa+= lx-16;    pfb+= lx-16;    pfc+= lx-16;    pb+= lx-16;    pba+= lx-16;    pbb+= lx-16;    pbc+= lx-16;  }  return s;}/* * variance of a (16*16) block, multiplied by 256 * p:  address of top left pel of block * lx: distance (in bytes) of vertically adjacent pels */static int variance(p,lx)unsigned char *p;int lx;{  int i,j;  unsigned int v,s,s2;  s = s2 = 0;  for (j=0; j<16; j++)  {    for (i=0; i<16; i++)    {      v = *p++;      s+= v;      s2+= v*v;    }    p+= lx-16;  }  return s2 - (s*s)/256;}