00001 /*===========================================================================*
00002  * bsearch.c                                                                 *
00003  *                                                                           *
00004  *      Procedures concerned with the B-frame motion search                  *
00005  *                                                                           *
00006  * EXPORTED PROCEDURES:                                                      *
00007  *      SetBSearchAlg                                                        *
00008  *      BMotionSearch                                                        *
00009  *      BSearchName                                                          *
00010  *                                                                           *
00011  *===========================================================================*/
00012 
00013 /*
00014  * Copyright (c) 1995 The Regents of the University of California.
00015  * All rights reserved.
00016  *
00017  * Permission to use, copy, modify, and distribute this software and its
00018  * documentation for any purpose, without fee, and without written agreement is
00019  * hereby granted, provided that the above copyright notice and the following
00020  * two paragraphs appear in all copies of this software.
00021  *
00022  * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
00023  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
00024  * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
00025  * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00026  *
00027  * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
00028  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
00029  * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
00030  * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
00031  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
00032  */
00033 
00034 /*  
00035  *  $Header: /misc/elrond0/share/cvs/AFNI/src/mpeg_encodedir/bsearch.c,v 1.4 2004/04/02 15:12:40 rwcox Exp $
00036  *  $Log: bsearch.c,v $
00037  *  Revision 1.4  2004/04/02 15:12:40  rwcox
00038  *  Cput
00039  *
00040  *  Revision 1.3  2003/12/23 13:50:08  rwcox
00041  *  Cput
00042  *
00043  *  Revision 1.2  2003/12/03 14:46:14  rwcox
00044  *  Cput
00045  *
00046  *  Revision 1.1  2001/12/17 16:11:53  rwcox
00047  *  Cadd
00048  *
00049  *  Revision 1.10  1995/08/07 21:49:01  smoot
00050  *  fixed bug in initial-B-frame searches
00051  *
00052  *  Revision 1.9  1995/06/26 21:36:07  smoot
00053  *  added new ordering constraints
00054  *  (B frames which are backward P's at the start of a sequence)
00055  *
00056  *  Revision 1.8  1995/03/27 19:17:43  smoot
00057  *  killed useless type error messge (int32 defiend as int)
00058  *
00059  * Revision 1.7  1995/01/19  23:07:20  eyhung
00060  * Changed copyrights
00061  *
00062  * Revision 1.6  1994/12/07  00:40:36  smoot
00063  * Added seperate P and B search ranges
00064  *
00065  * Revision 1.5  1994/03/15  00:27:11  keving
00066  * nothing
00067  *
00068  * Revision 1.4  1993/12/22  19:19:01  keving
00069  * nothing
00070  *
00071  * Revision 1.3  1993/07/22  22:23:43  keving
00072  * nothing
00073  *
00074  * Revision 1.2  1993/06/30  20:06:09  keving
00075  * nothing
00076  *
00077  * Revision 1.1  1993/06/03  21:08:08  keving
00078  * nothing
00079  *
00080  * Revision 1.1  1993/03/02  18:27:05  keving
00081  * nothing
00082  *
00083  */
00084 
00085 
00086 /*==============*
00087  * HEADER FILES *
00088  *==============*/
00089 
00090 #include "all.h"
00091 #include "mtypes.h"
00092 #include "frames.h"
00093 #include "search.h"
00094 #include "fsize.h"
00095 
00096 
00097 /*==================*
00098  * STATIC VARIABLES *
00099  *==================*/
00100 
00101 static int      bsearchAlg;
00102 
00103 
00104 /*===============================*
00105  * INTERNAL PROCEDURE prototypes *
00106  *===============================*/
00107 
00108 static int32    FindBestMatch _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
00109                       int by, int bx, int *motionY, int *motionX, int32 bestSoFar, int searchRange));
00110 static int BMotionSearchSimple _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
00111                         MpegFrame *next, int by, int bx, int *fmy, int *fmx,
00112                         int *bmy, int *bmx, int oldMode));
00113 static int BMotionSearchCross2 _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
00114                         MpegFrame *next, int by, int bx, int *fmy, int *fmx,
00115                         int *bmy, int *bmx, int oldMode));
00116 static int BMotionSearchExhaust _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
00117                         MpegFrame *next, int by, int bx, int *fmy, int *fmx,
00118                         int *bmy, int *bmx, int oldMode));
00119 static void BMotionSearchNoInterp _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
00120                                   MpegFrame *next, int by, int bx,
00121                                   int *fmy, int *fmx, int32 *forwardErr,
00122                                   int *bmy, int *bmx, int32 *backErr,
00123                                                boolean backNeeded));
00124 static int32    FindBestMatchExhaust _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
00125                       int by, int bx, int *motionY, int *motionX,
00126                       int32 bestSoFar, int searchRange));
00127 static int32    FindBestMatchTwoLevel _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
00128                       int by, int bx, int *motionY, int *motionX,
00129                       int32 bestSoFar, int searchRange));
00130 static int32    FindBestMatchLogarithmic _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
00131                       int by, int bx, int *motionY, int *motionX,
00132                       int32 bestSoFar, int searchRange));
00133 static int32    FindBestMatchSubSample _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
00134                       int by, int bx, int *motionY, int *motionX,
00135                       int32 bestSoFar, int searchRange));
00136 
00137 
00138 /*=====================*
00139  * EXPORTED PROCEDURES *
00140  *=====================*/
00141 
00142 /*===========================*
00143  * INITIALIZATION PROCEDURES *
00144  *===========================*/
00145 
00146 
00147 /*===========================================================================*
00148  *
00149  * SetBSearchAlg
00150  *
00151  *      set the B-search algorithm
00152  *
00153  * RETURNS:     nothing
00154  *
00155  * SIDE EFFECTS:    bsearchAlg modified
00156  *
00157  *===========================================================================*/
00158 void
00159 SetBSearchAlg(alg)
00160     char *alg;
00161 {
00162     if ( strcmp(alg, "SIMPLE") == 0 ) {
00163         bsearchAlg = BSEARCH_SIMPLE;
00164     } else if ( strcmp(alg, "CROSS2") == 0 ) {
00165         bsearchAlg = BSEARCH_CROSS2;
00166     } else if ( strcmp(alg, "EXHAUSTIVE") == 0 ) {
00167         bsearchAlg = BSEARCH_EXHAUSTIVE;
00168     } else {
00169         fprintf(stderr, "ERROR:  Illegal bsearch alg:  %s\n", alg);
00170         exit(1);
00171     }
00172 }
00173 
00174 
00175 /*===========================================================================*
00176  *
00177  * BSearchName
00178  *
00179  *      return the text of the B-search algorithm
00180  *
00181  * RETURNS:     a pointer to the string
00182  *
00183  * SIDE EFFECTS:    none
00184  *
00185  *===========================================================================*/
00186 char *
00187 BSearchName()
00188 {
00189     switch(bsearchAlg) {
00190         case BSEARCH_SIMPLE:
00191             return "SIMPLE";
00192         case BSEARCH_CROSS2:
00193             return "CROSS2";
00194         case BSEARCH_EXHAUSTIVE:
00195             return "EXHAUSTIVE";
00196         default:
00197             exit(1);
00198             break;
00199     }
00200 }
00201 
00202 
00203 /*===========================================================================*
00204  *
00205  * BMotionSearch
00206  *
00207  *      search for the best B-frame motion vectors
00208  *
00209  * RETURNS:     MOTION_FORWARD      forward motion should be used
00210  *              MOTION_BACKWARD     backward motion should be used
00211  *              MOTION_INTERPOLATE  both should be used and interpolated
00212  *
00213  * OUTPUTS:     *fmx, *fmy  =   TWICE the forward motion vector
00214  *              *bmx, *bmy  =   TWICE the backward motion vector
00215  *
00216  * SIDE EFFECTS:    none
00217  *
00218  * PRECONDITIONS:       The relevant block in 'current' is valid (it has not
00219  *                      been dct'd).  Thus, the data in 'current' can be
00220  *                      accesed through y_blocks, cr_blocks, and cb_blocks.
00221  *                      This is not the case for the blocks in 'prev' and
00222  *                      'next.'  Therefore, references into 'prev' and 'next'
00223  *                      should be done
00224  *                      through the struct items ref_y, ref_cr, ref_cb
00225  *
00226  * POSTCONDITIONS:      current, prev, next should be unchanged.
00227  *                      Some computation could be saved by requiring
00228  *                      the dct'd difference to be put into current's block
00229  *                      elements here, depending on the search technique.
00230  *                      However, it was decided that it mucks up the code
00231  *                      organization a little, and the saving in computation
00232  *                      would be relatively little (if any).
00233  *
00234  * NOTES:       the search procedure MAY return (0,0) motion vectors
00235  *
00236  *===========================================================================*/
00237 int
00238 BMotionSearch(currentBlock, prev, next, by, bx, fmy, fmx, bmy, bmx, oldMode)
00239     LumBlock currentBlock;
00240     MpegFrame *prev;
00241     MpegFrame *next;
00242     int by;
00243     int bx;
00244     int *fmy;
00245     int *fmx;
00246     int *bmy;
00247     int *bmx;
00248     int oldMode;
00249 {
00250   /* If we are an initial B frame, no possibility of forward motion */
00251   if (prev == (MpegFrame *) NULL) {
00252     PMotionSearch(currentBlock, next, by, bx, bmy, bmx);
00253     return MOTION_BACKWARD;
00254   }
00255   
00256   /* otherwise simply call the appropriate algorithm, based on user preference */
00257   
00258     switch(bsearchAlg) {
00259         case BSEARCH_SIMPLE:
00260             return BMotionSearchSimple(currentBlock, prev, next, by, bx, fmy,
00261                                        fmx, bmy, bmx, oldMode);
00262             break;
00263         case BSEARCH_CROSS2:
00264             return BMotionSearchCross2(currentBlock, prev, next, by, bx, fmy,
00265                                        fmx, bmy, bmx, oldMode);
00266             break;
00267         case BSEARCH_EXHAUSTIVE:
00268             return BMotionSearchExhaust(currentBlock, prev, next, by, bx, fmy,
00269                                        fmx, bmy, bmx, oldMode);
00270             break;
00271         default:
00272             fprintf(stderr, "Illegal B-frame motion search algorithm:  %d\n",
00273                     bsearchAlg);
00274             exit(1);
00275     }
00276 }
00277 
00278 
00279 /*===========================================================================*
00280  *
00281  * BMotionSearchSimple
00282  *
00283  *      does a simple search for B-frame motion vectors
00284  *      see BMotionSearch for generic description
00285  *
00286  * DESCRIPTION:
00287  *      1)  find best backward and forward vectors
00288  *      2)  compute interpolated error using those two vectors
00289  *      3)  return the best of the three choices
00290  *
00291  *===========================================================================*/
00292 static int
00293 BMotionSearchSimple(currentBlock, prev, next, by, bx, fmy, fmx, bmy, bmx,
00294                     oldMode)
00295     LumBlock currentBlock;
00296     MpegFrame *prev;
00297     MpegFrame *next;
00298     int by;
00299     int bx;
00300     int *fmy;
00301     int *fmx;
00302     int *bmy;
00303     int *bmx;
00304     int oldMode;
00305 {
00306     int32       forwardErr, backErr, interpErr;
00307     LumBlock    interpBlock;
00308     int32       bestSoFar;
00309 
00310                             /* STEP 1 */
00311     BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx,
00312                           &forwardErr, bmy, bmx, &backErr, TRUE);
00313                           
00314                             /* STEP 2 */
00315 
00316     ComputeBMotionLumBlock(prev, next, by, bx, MOTION_INTERPOLATE,
00317                            *fmy, *fmx, *bmy, *bmx, interpBlock);
00318     bestSoFar = min(backErr, forwardErr);
00319     interpErr = LumBlockMAD(currentBlock, interpBlock, bestSoFar);
00320 
00321                             /* STEP 3 */
00322 
00323     if ( interpErr <= forwardErr ) {
00324         if ( interpErr <= backErr ) {
00325             return MOTION_INTERPOLATE;
00326         }
00327         else
00328             return MOTION_BACKWARD;
00329     } else if ( forwardErr <= backErr ) {
00330         return MOTION_FORWARD;
00331     } else {
00332         return MOTION_BACKWARD;
00333     }
00334 }
00335 
00336 
00337 /*===========================================================================*
00338  *
00339  * BMotionSearchCross2
00340  *
00341  *      does a cross-2 search for B-frame motion vectors
00342  *      see BMotionSearch for generic description
00343  *
00344  * DESCRIPTION:
00345  *      1)  find best backward and forward vectors
00346  *      2)  find best matching interpolating vectors
00347  *      3)  return the best of the 4 choices
00348  *
00349  *===========================================================================*/
00350 static int
00351 BMotionSearchCross2(currentBlock, prev, next, by, bx, fmy, fmx, bmy, bmx,
00352                     oldMode)
00353     LumBlock currentBlock;
00354     MpegFrame *prev;
00355     MpegFrame *next;
00356     int by;
00357     int bx;
00358     int *fmy;
00359     int *fmx;
00360     int *bmy;
00361     int *bmx;
00362     int oldMode;
00363 {
00364     LumBlock    forwardBlock, backBlock;
00365     int32       forwardErr, backErr, interpErr;
00366     int         newfmy, newfmx, newbmy, newbmx;
00367     int32       interpErr2;
00368     int32       bestErr;
00369 
00370                             /* STEP 1 */
00371 
00372     BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx,
00373                           &forwardErr, bmy, bmx, &backErr, TRUE);
00374 
00375     bestErr = min(forwardErr, backErr);
00376 
00377                             /* STEP 2 */
00378     ComputeBMotionLumBlock(prev, next, by, bx, MOTION_FORWARD,
00379                            *fmy, *fmx, 0, 0, forwardBlock);
00380     ComputeBMotionLumBlock(prev, next, by, bx, MOTION_BACKWARD,
00381                            0, 0, *bmy, *bmx, backBlock);
00382 
00383     /* try a cross-search; total of 4 local searches */    
00384     newbmy = *bmy;      newbmx = *bmx;
00385     newfmy = *fmy;      newfmx = *fmx;
00386 
00387     interpErr = FindBestMatch(forwardBlock, currentBlock, next, by, bx,
00388                               &newbmy, &newbmx, bestErr, searchRangeB);
00389     bestErr = min(bestErr, interpErr);
00390     interpErr2 = FindBestMatch(backBlock, currentBlock, prev, by, bx,
00391                                &newfmy, &newfmx, bestErr, searchRangeB);
00392 
00393                             /* STEP 3 */
00394 
00395     if ( interpErr <= interpErr2 ) {
00396         newfmy = *fmy;
00397         newfmx = *fmx;
00398     }
00399     else
00400     {
00401         newbmy = *bmy;
00402         newbmx = *bmx;
00403         interpErr = interpErr2;
00404     }
00405 
00406     if ( interpErr <= forwardErr ) {
00407         if ( interpErr <= backErr ) {
00408             *fmy = newfmy;
00409             *fmx = newfmx;
00410             *bmy = newbmy;
00411             *bmx = newbmx;
00412 
00413             return MOTION_INTERPOLATE;
00414         }
00415         else
00416             return MOTION_BACKWARD;
00417     } else if ( forwardErr <= backErr ) {
00418         return MOTION_FORWARD;
00419     } else {
00420         return MOTION_BACKWARD;
00421     }
00422 }
00423 
00424 
00425 /*===========================================================================*
00426  *
00427  * BMotionSearchExhaust
00428  *
00429  *      does an exhaustive search for B-frame motion vectors
00430  *      see BMotionSearch for generic description
00431  *
00432  * DESCRIPTION:
00433  *      1)  find best backward and forward vectors
00434  *      2)  use exhaustive search to find best interpolating vectors
00435  *      3)  return the best of the 3 choices
00436  *
00437  *===========================================================================*/
00438 static int
00439 BMotionSearchExhaust(currentBlock, prev, next, by, bx, fmy, fmx, bmy, bmx,
00440                     oldMode)
00441     LumBlock currentBlock;
00442     MpegFrame *prev;
00443     MpegFrame *next;
00444     int by;
00445     int bx;
00446     int *fmy;
00447     int *fmx;
00448     int *bmy;
00449     int *bmx;
00450     int oldMode;
00451 {
00452     register int mx, my;
00453     int32 diff, bestDiff;
00454     int     stepSize;
00455     LumBlock    forwardBlock;
00456     int32       forwardErr, backErr;
00457     int         newbmy, newbmx;
00458     int     leftMY, leftMX;
00459     int     rightMY, rightMX;
00460     boolean result;
00461 
00462                             /* STEP 1 */
00463 
00464     BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx,
00465                           &forwardErr, bmy, bmx, &backErr, FALSE);
00466 
00467     if ( forwardErr <= backErr ) {
00468         bestDiff = forwardErr;
00469         result = MOTION_FORWARD;
00470     }
00471     else
00472     {
00473         bestDiff = backErr;
00474         result = MOTION_BACKWARD;
00475     }
00476 
00477                             /* STEP 2 */
00478 
00479     stepSize = (pixelFullSearch ? 2 : 1);
00480 
00481     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
00482 
00483     if ( searchRangeB < rightMY ) {
00484         rightMY = searchRangeB;
00485     }
00486     if ( searchRangeB < rightMX ) {
00487         rightMX = searchRangeB;
00488     }
00489 
00490     for ( my = -searchRangeB; my < rightMY; my += stepSize ) {
00491         if ( my < leftMY ) {
00492             continue;
00493         }
00494 
00495         for ( mx = -searchRangeB; mx < rightMX; mx += stepSize ) {
00496             if ( mx < leftMX ) {
00497                 continue;
00498             }
00499 
00500             ComputeBMotionLumBlock(prev, next, by, bx, MOTION_FORWARD,
00501                            my, mx, 0, 0, forwardBlock);
00502 
00503             newbmy = my;        newbmx = mx;
00504 
00505             diff = FindBestMatch(forwardBlock, currentBlock, next, by, bx,
00506                                  &newbmy, &newbmx, bestDiff, searchRangeB);
00507 
00508             if ( diff < bestDiff ) {
00509                 *fmy = my;
00510                 *fmx = mx;
00511                 *bmy = newbmy;
00512                 *bmx = newbmx;
00513                 bestDiff = diff;
00514                 result = MOTION_INTERPOLATE;
00515             }
00516         }
00517     }
00518 
00519     return result;
00520 }
00521 
00522 
00523 /*===========================================================================*
00524  *
00525  * FindBestMatch
00526  *
00527  *      given a motion-compensated block in one direction, tries to find
00528  *      the best motion vector in the opposite direction to match it
00529  *
00530  * RETURNS:     the best vector (*motionY, *motionX), and the corresponding
00531  *              error is returned if it is better than bestSoFar.  If not,
00532  *              then a number greater than bestSoFar is returned and
00533  *              (*motionY, *motionX) has no meaning.
00534  *
00535  * SIDE EFFECTS:  none
00536  *
00537  *===========================================================================*/
00538 static int32
00539 FindBestMatch(block, currentBlock, prev, by, bx, motionY, motionX, bestSoFar, searchRange)
00540     LumBlock block;
00541     LumBlock currentBlock;
00542     MpegFrame *prev;
00543     int by;
00544     int bx;
00545     int *motionY;
00546     int *motionX;
00547     int32 bestSoFar;
00548     int searchRange;
00549 {
00550     int32       result;
00551 
00552     switch(psearchAlg) {
00553         case PSEARCH_SUBSAMPLE:
00554             result = FindBestMatchSubSample(block, currentBlock, prev, by, bx,
00555                                             motionY, motionX, bestSoFar, searchRange);
00556             break;
00557         case PSEARCH_EXHAUSTIVE:
00558             result = FindBestMatchExhaust(block, currentBlock, prev, by, bx,
00559                                           motionY, motionX, bestSoFar, searchRange);
00560             break;
00561         case PSEARCH_LOGARITHMIC:
00562             result = FindBestMatchLogarithmic(block, currentBlock, prev, by, bx,
00563                                               motionY, motionX, bestSoFar, searchRange);
00564             break;
00565         case PSEARCH_TWOLEVEL:
00566             result = FindBestMatchTwoLevel(block, currentBlock, prev, by, bx,
00567                                            motionY, motionX, bestSoFar, searchRange);
00568             break;
00569         default:
00570             fprintf(stderr, "ERROR:  Illegal P-search alg %d\n", psearchAlg);
00571             exit(1);
00572     }
00573 
00574     return result;
00575 }
00576 
00577 
00578 /*===========================================================================*
00579  *
00580  * FindBestMatchExhaust
00581  *
00582  *      tries to find matching motion vector
00583  *      see FindBestMatch for generic description
00584  *
00585  * DESCRIPTION:  uses an exhaustive search
00586  *
00587  *===========================================================================*/
00588 static int32
00589 FindBestMatchExhaust(block, currentBlock, prev, by, bx, motionY, motionX,
00590                      bestSoFar, searchRange)
00591     LumBlock block;
00592     LumBlock currentBlock;
00593     MpegFrame *prev;
00594     int by;
00595     int bx;
00596     int *motionY;
00597     int *motionX;
00598     int32 bestSoFar;
00599     int searchRange;
00600 {
00601     register int mx, my;
00602     int32 diff, bestDiff;
00603     int     stepSize;
00604     int     leftMY, leftMX;
00605     int     rightMY, rightMX;
00606     int     distance;
00607     int     tempRightMY, tempRightMX;
00608     boolean changed = FALSE;
00609 
00610     stepSize = (pixelFullSearch ? 2 : 1);
00611 
00612     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
00613 
00614     /* try old motion vector first */
00615     if ( VALID_MOTION(*motionY, *motionX) ) {
00616         bestDiff = LumAddMotionError(currentBlock, block, prev, by, bx,
00617                                      *motionY, *motionX, bestSoFar);
00618 
00619         if ( bestSoFar < bestDiff ) {
00620             bestDiff = bestSoFar;
00621         }
00622     }
00623     else
00624     {
00625         *motionY = 0;
00626         *motionX = 0;
00627 
00628         bestDiff = bestSoFar;
00629     }
00630 
00631 /* maybe should try spiral pattern centered around  prev motion vector? */
00632 
00633 
00634     /* try a spiral pattern */    
00635     for ( distance = stepSize; distance <= searchRange; distance += stepSize ) {
00636         tempRightMY = rightMY;
00637         if ( distance < tempRightMY ) {
00638             tempRightMY = distance;
00639         }
00640         tempRightMX = rightMX;
00641         if ( distance < tempRightMX ) {
00642             tempRightMX = distance;
00643         }
00644 
00645         /* do top, bottom */
00646         for ( my = -distance; my < tempRightMY;
00647               my += max(tempRightMY+distance-stepSize, stepSize) ) {
00648             if ( my < leftMY ) {
00649                 continue;
00650             }
00651 
00652             for ( mx = -distance; mx < tempRightMX; mx += stepSize ) {
00653                 if ( mx < leftMX ) {
00654                     continue;
00655                 }
00656 
00657                 diff = LumAddMotionError(currentBlock, block, prev, by, bx,
00658                                      my, mx, bestDiff);
00659 
00660                 if ( diff < bestDiff ) {
00661                     *motionY = my;
00662                     *motionX = mx;
00663                     bestDiff = diff;
00664                 }
00665             }
00666         }
00667 
00668         /* do left, right */
00669         for ( mx = -distance; mx < tempRightMX; mx += max(tempRightMX+distance-stepSize, stepSize) ) {
00670             if ( mx < leftMX ) {
00671                 continue;
00672             }
00673 
00674             for ( my = -distance+stepSize; my < tempRightMY-stepSize; my += stepSize ) {
00675                 if ( my < leftMY ) {
00676                     continue;
00677                 }
00678 
00679                 diff = LumAddMotionError(currentBlock, block, prev, by, bx,
00680                                      my, mx, bestDiff);
00681 
00682                 if ( diff < bestDiff ) {
00683                     *motionY = my;
00684                     *motionX = mx;
00685                     bestDiff = diff;
00686                     changed = TRUE;
00687                 }
00688             }
00689         }
00690     }
00691 
00692     if ( ! changed ) {
00693         bestDiff++;
00694     }
00695 
00696     return bestDiff;
00697 }
00698 
00699 
00700 /*===========================================================================*
00701  *
00702  * FindBestMatchTwoLevel
00703  *
00704  *      tries to find matching motion vector
00705  *      see FindBestMatch for generic description
00706  *
00707  * DESCRIPTION:  uses an exhaustive full-pixel search, then looks at
00708  *               neighboring half-pixels
00709  *
00710  *===========================================================================*/
00711 static int32
00712 FindBestMatchTwoLevel(block, currentBlock, prev, by, bx, motionY, motionX,
00713                       bestSoFar, searchRange)
00714     LumBlock block;
00715     LumBlock currentBlock;
00716     MpegFrame *prev;
00717     int by;
00718     int bx;
00719     int *motionY;
00720     int *motionX;
00721     int32 bestSoFar;
00722     int searchRange;
00723 {
00724     register int mx, my;
00725     int32 diff, bestDiff;
00726     int     leftMY, leftMX;
00727     int     rightMY, rightMX;
00728     int     distance;
00729     int     tempRightMY, tempRightMX;
00730     boolean changed = FALSE;
00731     int     yOffset, xOffset;
00732 
00733     /* exhaustive full-pixel search first */
00734 
00735     COMPUTE_MOTION_BOUNDARY(by,bx,2,leftMY,leftMX,rightMY,rightMX);
00736 
00737     rightMY--;
00738     rightMX--;
00739 
00740     /* convert vector into full-pixel vector */
00741     if ( *motionY > 0 ) {
00742         if ( ((*motionY) % 2) == 1 ) {
00743             (*motionY)--;
00744         }
00745     } else if ( ((-(*motionY)) % 2) == 1 ) {
00746         (*motionY)++;
00747     }
00748 
00749     if ( *motionX > 0 ) {
00750         if ( ((*motionX) % 2) == 1 ) {
00751             (*motionX)--;
00752         }
00753     } else if ( ((-(*motionX)) % 2) == 1 ) {
00754         (*motionX)++;
00755     }
00756 
00757     /* try old motion vector first */
00758     if ( VALID_MOTION(*motionY, *motionX) ) {
00759         bestDiff = LumAddMotionError(currentBlock, block, prev, by, bx,
00760                                      *motionY, *motionX, bestSoFar);
00761 
00762         if ( bestSoFar < bestDiff ) {
00763             bestDiff = bestSoFar;
00764         }
00765     }
00766     else
00767     {
00768         *motionY = 0;
00769         *motionX = 0;
00770 
00771         bestDiff = bestSoFar;
00772     }
00773 
00774     rightMY++;
00775     rightMX++;
00776 
00777 /* maybe should try spiral pattern centered around  prev motion vector? */
00778 
00779 
00780     /* try a spiral pattern */    
00781     for ( distance = 2; distance <= searchRange; distance += 2 ) {
00782         tempRightMY = rightMY;
00783         if ( distance < tempRightMY ) {
00784             tempRightMY = distance;
00785         }
00786         tempRightMX = rightMX;
00787         if ( distance < tempRightMX ) {
00788             tempRightMX = distance;
00789         }
00790 
00791         /* do top, bottom */
00792         for ( my = -distance; my < tempRightMY;
00793               my += max(tempRightMY+distance-2, 2) ) {
00794             if ( my < leftMY ) {
00795                 continue;
00796             }
00797 
00798             for ( mx = -distance; mx < tempRightMX; mx += 2 ) {
00799                 if ( mx < leftMX ) {
00800                     continue;
00801                 }
00802 
00803                 diff = LumAddMotionError(currentBlock, block, prev, by, bx,
00804                                      my, mx, bestDiff);
00805 
00806                 if ( diff < bestDiff ) {
00807                     *motionY = my;
00808                     *motionX = mx;
00809                     bestDiff = diff;
00810                 }
00811             }
00812         }
00813 
00814         /* do left, right */
00815         for ( mx = -distance; mx < tempRightMX; mx += max(tempRightMX+distance-2, 2) ) {
00816             if ( mx < leftMX ) {
00817                 continue;
00818             }
00819 
00820             for ( my = -distance+2; my < tempRightMY-2; my += 2 ) {
00821                 if ( my < leftMY ) {
00822                     continue;
00823                 }
00824 
00825                 diff = LumAddMotionError(currentBlock, block, prev, by, bx,
00826                                      my, mx, bestDiff);
00827 
00828                 if ( diff < bestDiff ) {
00829                     *motionY = my;
00830                     *motionX = mx;
00831                     bestDiff = diff;
00832                     changed = TRUE;
00833                 }
00834             }
00835         }
00836     }
00837 
00838     /* now look at neighboring half-pixels */
00839     my = *motionY;
00840     mx = *motionX;
00841 
00842     rightMY--;
00843     rightMX--;
00844 
00845     for ( yOffset = -1; yOffset <= 1; yOffset++ ) {
00846         for ( xOffset = -1; xOffset <= 1; xOffset++ ) {
00847             if ( (yOffset == 0) && (xOffset == 0) )
00848                 continue;
00849 
00850             if ( VALID_MOTION(my+yOffset, mx+xOffset) &&
00851                  ((diff = LumAddMotionError(currentBlock, block, prev, by, bx,
00852                          my+yOffset, mx+xOffset, bestDiff)) < bestDiff) ) {
00853                 *motionY = my+yOffset;
00854                 *motionX = mx+xOffset;
00855                 bestDiff = diff;
00856                 changed = TRUE;
00857             }
00858         }
00859     }
00860 
00861     if ( ! changed ) {
00862         bestDiff++;
00863     }
00864 
00865     return bestDiff;
00866 }
00867 
00868 
00869 /*===========================================================================*
00870  *
00871  * FindBestMatchLogarithmic
00872  *
00873  *      tries to find matching motion vector
00874  *      see FindBestMatch for generic description
00875  *
00876  * DESCRIPTION:  uses a logarithmic search
00877  *
00878  *===========================================================================*/
00879 static int32
00880 FindBestMatchLogarithmic(block, currentBlock, prev, by, bx, motionY, motionX,
00881                      bestSoFar, searchRange)
00882     LumBlock block;
00883     LumBlock currentBlock;
00884     MpegFrame *prev;
00885     int by;
00886     int bx;
00887     int *motionY;
00888     int *motionX;
00889     int32 bestSoFar;
00890     int searchRange;
00891 {
00892     register int mx, my;
00893     int32 diff, bestDiff;
00894     int     stepSize;
00895     int     leftMY, leftMX;
00896     int     rightMY, rightMX;
00897     int     tempRightMY, tempRightMX;
00898     int     spacing;
00899     int     centerX, centerY;
00900     int     newCenterX, newCenterY;
00901 
00902     stepSize = (pixelFullSearch ? 2 : 1);
00903 
00904     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
00905 
00906     bestDiff = 0x7fffffff;
00907 
00908     /* grid spacing */
00909     if ( stepSize == 2 ) {      /* make sure spacing is even */
00910         spacing = (searchRange+1)/2;
00911         if ( (spacing % 2) != 0 ) {
00912             spacing++;
00913         }
00914     }
00915     else
00916         spacing = (searchRange+1)/2;
00917     centerX = 0;
00918     centerY = 0;
00919 
00920     while ( spacing >= stepSize ) {
00921         newCenterY = centerY;
00922         newCenterX = centerX;
00923 
00924         tempRightMY = rightMY;
00925         if ( centerY+spacing+1 < tempRightMY ) {
00926             tempRightMY = centerY+spacing+1;
00927         }
00928         tempRightMX = rightMX;
00929         if ( centerX+spacing+1 < tempRightMX ) {
00930             tempRightMX = centerX+spacing+1;
00931         }
00932 
00933         for ( my = centerY-spacing; my < tempRightMY; my += spacing ) {
00934             if ( my < leftMY ) {
00935                 continue;
00936             }
00937 
00938             for ( mx = centerX-spacing; mx < tempRightMX; mx += spacing ) {
00939                 if ( mx < leftMX ) {
00940                     continue;
00941                 }
00942 
00943                 diff = LumAddMotionError(currentBlock, block, prev, by, bx,
00944                                      my, mx, bestDiff);
00945 
00946                 if ( diff < bestDiff ) {
00947                     newCenterY = my;
00948                     newCenterX = mx;
00949 
00950                     bestDiff = diff;
00951                 }
00952             }
00953         }
00954 
00955         centerY = newCenterY;
00956         centerX = newCenterX;
00957 
00958         if ( stepSize == 2 ) {  /* make sure spacing is even */
00959             if ( spacing == 2 ) {
00960                 spacing = 0;
00961             }
00962             else
00963             {
00964                 spacing = (spacing+1)/2;
00965                 if ( (spacing % 2) != 0 ) {
00966                     spacing++;
00967                 }
00968             }
00969         }
00970         else
00971         {
00972             if ( spacing == 1 ) {
00973                 spacing = 0;
00974             }
00975             else
00976                 spacing = (spacing+1)/2;
00977         }
00978     }
00979 
00980     /* check old motion -- see if it's better */
00981     if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
00982          (*motionX >= leftMX) && (*motionX < rightMX) ) {
00983         diff = LumAddMotionError(currentBlock, block, prev, by, bx, *motionY, *motionX, bestDiff);
00984     } else {
00985         diff = 0x7fffffff;
00986     }
00987 
00988     if ( bestDiff < diff ) {
00989         *motionY = centerY;
00990         *motionX = centerX;
00991     }
00992     else
00993         bestDiff = diff;
00994 
00995     return bestDiff;
00996 }
00997 
00998 
00999 /*===========================================================================*
01000  *
01001  * FindBestMatchSubSample
01002  *
01003  *      tries to find matching motion vector
01004  *      see FindBestMatch for generic description
01005  *
01006  * DESCRIPTION:  should use subsampling method, but too lazy to write all
01007  *               the code for it (so instead just calls FindBestMatchExhaust)
01008  *
01009  *===========================================================================*/
01010 static int32
01011 FindBestMatchSubSample(block, currentBlock, prev, by, bx, motionY, motionX,
01012                      bestSoFar, searchRange)
01013     LumBlock block;
01014     LumBlock currentBlock;
01015     MpegFrame *prev;
01016     int by;
01017     int bx;
01018     int *motionY;
01019     int *motionX;
01020     int32 bestSoFar;
01021     int searchRange;
01022 {
01023     /* too lazy to write the code for this... */
01024 
01025     return FindBestMatchExhaust(block, currentBlock, prev,
01026                                 by, bx, motionY, motionX, bestSoFar, searchRange);
01027 }
01028 
01029 
01030 /*===========================================================================*
01031  *
01032  * BMotionSearchNoInterp
01033  *
01034  *      finds the best backward and forward motion vectors
01035  *      if backNeeded == FALSE, then won't find best backward vector if it
01036  *      is worse than the best forward vector
01037  *
01038  * RETURNS:     (*fmy,*fmx) and associated error *forwardErr
01039  *              (*bmy,*bmx) and associated error *backErr
01040  *
01041  * SIDE EFFECTS:    none
01042  *
01043  *===========================================================================*/
01044 static void
01045 BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx, forwardErr,
01046                       bmy, bmx, backErr, backNeeded)
01047     LumBlock currentBlock;
01048     MpegFrame *prev;
01049     MpegFrame *next;
01050     int by;
01051     int bx;
01052     int *fmy;
01053     int *fmx;
01054     int32 *forwardErr;
01055     int *bmy;
01056     int *bmx;
01057     int32 *backErr;
01058     boolean backNeeded;
01059 {
01060     /* CALL SEARCH PROCEDURE */
01061     switch(psearchAlg) {
01062         case PSEARCH_SUBSAMPLE:
01063             *forwardErr = PSubSampleSearch(currentBlock, prev, by, bx, 
01064                                            fmy, fmx, searchRangeB);
01065             *backErr = PSubSampleSearch(currentBlock, next, by, bx, 
01066                                         bmy, bmx, searchRangeB);
01067             break;
01068         case PSEARCH_EXHAUSTIVE:
01069             *forwardErr = PLocalSearch(currentBlock, prev, by, bx, fmy, fmx, 
01070                                        0x7fffffff, searchRangeB);
01071             if ( backNeeded ) {
01072                 *backErr = PLocalSearch(currentBlock, next, by, bx, bmy, bmx, 
01073                                         0x7fffffff, searchRangeB);
01074             } else {
01075                 *backErr = PLocalSearch(currentBlock, next, by, bx, bmy, bmx, 
01076                                         *forwardErr, searchRangeB);
01077             }
01078             break;
01079         case PSEARCH_LOGARITHMIC:
01080             *forwardErr = PLogarithmicSearch(currentBlock, prev, by, bx, 
01081                                              fmy, fmx, searchRangeB);
01082             *backErr = PLogarithmicSearch(currentBlock, next, by, bx, 
01083                                           bmy, bmx, searchRangeB);
01084             break;
01085         case PSEARCH_TWOLEVEL:
01086             *forwardErr = PTwoLevelSearch(currentBlock, prev, by, bx, fmy, fmx, 
01087                                           0x7fffffff, searchRangeB);
01088             if ( backNeeded ) {
01089                 *backErr = PTwoLevelSearch(currentBlock, next, by, bx, bmy, bmx, 
01090                                            0x7fffffff, searchRangeB);
01091             } else {
01092                 *backErr = PTwoLevelSearch(currentBlock, next, by, bx, bmy, bmx, 
01093                                            *forwardErr, searchRangeB);
01094             }
01095             break;
01096         default:
01097             fprintf(stderr, "ERROR:  Illegal PSEARCH ALG:  %d\n", psearchAlg);
01098             exit(1);    
01099             break;
01100     }
01101 }
01102 
01103 
01104 
01105 /*===========================================================================*
01106  *                                                                           *
01107  * UNUSED PROCEDURES                                                         *
01108  *                                                                           *
01109  *      The following procedures are all unused by the encoder               *
01110  *                                                                           *
01111  *      They are listed here for your convenience.  You might want to use    *
01112  *      them if you experiment with different search techniques              *
01113  *                                                                           *
01114  *===========================================================================*/
01115 
01116 #ifdef UNUSED_PROCEDURES
01117 
01118 /*===========================================================================*
01119  *
01120  * ValidBMotion
01121  *
01122  *      decides if the given B-frame motion is valid
01123  *
01124  * RETURNS:     TRUE if the motion is valid, FALSE otherwise
01125  *
01126  * SIDE EFFECTS:    none
01127  *
01128  *===========================================================================*/
01129 boolean
01130 ValidBMotion(by, bx, mode, fmy, fmx, bmy, bmx)
01131     int by;
01132     int bx;
01133     int mode;
01134     int fmy;
01135     int fmx;
01136     int bmy;
01137     int bmx;
01138 {
01139     if ( mode != MOTION_BACKWARD ) {
01140         /* check forward motion for bounds */
01141         if ( (by*DCTSIZE+(fmy-1)/2 < 0) || ((by+2)*DCTSIZE+(fmy+1)/2-1 >= Fsize_y) ) {
01142             return FALSE;
01143         }
01144         if ( (bx*DCTSIZE+(fmx-1)/2 < 0) || ((bx+2)*DCTSIZE+(fmx+1)/2-1 >= Fsize_x) ) {
01145             return FALSE;
01146         }
01147     }
01148 
01149     if ( mode != MOTION_FORWARD ) {
01150         /* check backward motion for bounds */
01151         if ( (by*DCTSIZE+(bmy-1)/2 < 0) || ((by+2)*DCTSIZE+(bmy+1)/2-1 >= Fsize_y) ) {
01152             return FALSE;
01153         }
01154         if ( (bx*DCTSIZE+(bmx-1)/2 < 0) || ((bx+2)*DCTSIZE+(bmx+1)/2-1 >= Fsize_x) ) {
01155             return FALSE;
01156         }
01157     }
01158 
01159     return TRUE;
01160 }
01161 
01162 
01163 #endif /* UNUSED_PROCEDURES */