home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 9 / CD_ASCQ_09_1193.iso / news / 4441 / mpegcode / src / bsearch.c < prev    next >
C/C++ Source or Header  |  1993-09-27  |  29KB  |  1,093 lines
  1. /*===========================================================================*
  2.  * bsearch.c                                     *
  3.  *                                         *
  4.  *    Procedures concerned with the B-frame motion search             *
  5.  *                                         *
  6.  * EXPORTED PROCEDURES:                                 *
  7.  *    SetBSearchAlg                                 *
  8.  *    BMotionSearch                                 *
  9.  *    BSearchName                                 *
  10.  *                                         *
  11.  *===========================================================================*/
  12.  
  13. /*
  14.  * Copyright (c) 1993 The Regents of the University of California.
  15.  * All rights reserved.
  16.  *
  17.  * Permission to use, copy, modify, and distribute this software and its
  18.  * documentation for any purpose, without fee, and without written agreement is
  19.  * hereby granted, provided that the above copyright notice and the following
  20.  * two paragraphs appear in all copies of this software.
  21.  *
  22.  * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
  23.  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
  24.  * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
  25.  * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26.  *
  27.  * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
  28.  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
  29.  * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
  30.  * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
  31.  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  32.  */
  33.  
  34. /*  
  35.  *  $Header: /n/picasso/users/keving/encode/src/RCS/bsearch.c,v 1.3 1993/07/22 22:23:43 keving Exp keving $
  36.  *  $Log: bsearch.c,v $
  37.  * Revision 1.3  1993/07/22  22:23:43  keving
  38.  * nothing
  39.  *
  40.  * Revision 1.2  1993/06/30  20:06:09  keving
  41.  * nothing
  42.  *
  43.  * Revision 1.1  1993/06/03  21:08:08  keving
  44.  * nothing
  45.  *
  46.  * Revision 1.1  1993/03/02  18:27:05  keving
  47.  * nothing
  48.  *
  49.  */
  50.  
  51.  
  52. /*==============*
  53.  * HEADER FILES *
  54.  *==============*/
  55.  
  56. #include "all.h"
  57. #include "mtypes.h"
  58. #include "frames.h"
  59. #include "search.h"
  60. #include "fsize.h"
  61.  
  62.  
  63. /*==================*
  64.  * STATIC VARIABLES *
  65.  *==================*/
  66.  
  67. static int    bsearchAlg;
  68.  
  69.  
  70. /*===============================*
  71.  * INTERNAL PROCEDURE prototypes *
  72.  *===============================*/
  73.  
  74. static int32    FindBestMatch _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
  75.               int by, int bx, int *motionY, int *motionX, int32 bestSoFar));
  76. static int BMotionSearchSimple _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
  77.             MpegFrame *next, int by, int bx, int *fmy, int *fmx,
  78.             int *bmy, int *bmx, int oldMode));
  79. static int BMotionSearchCross2 _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
  80.             MpegFrame *next, int by, int bx, int *fmy, int *fmx,
  81.             int *bmy, int *bmx, int oldMode));
  82. static int BMotionSearchExhaust _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
  83.             MpegFrame *next, int by, int bx, int *fmy, int *fmx,
  84.             int *bmy, int *bmx, int oldMode));
  85. static void BMotionSearchNoInterp _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
  86.                   MpegFrame *next, int by, int bx,
  87.                   int *fmy, int *fmx, int *forwardErr,
  88.                   int *bmy, int *bmx, int *backErr,
  89.                            boolean backNeeded));
  90. static int32    FindBestMatchExhaust _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
  91.               int by, int bx, int *motionY, int *motionX,
  92.               int32 bestSoFar));
  93. static int32    FindBestMatchTwoLevel _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
  94.               int by, int bx, int *motionY, int *motionX,
  95.               int32 bestSoFar));
  96. static int32    FindBestMatchLogarithmic _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
  97.               int by, int bx, int *motionY, int *motionX,
  98.               int32 bestSoFar));
  99. static int32    FindBestMatchSubSample _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
  100.               int by, int bx, int *motionY, int *motionX,
  101.               int32 bestSoFar));
  102.  
  103.  
  104. /*=====================*
  105.  * EXPORTED PROCEDURES *
  106.  *=====================*/
  107.  
  108. /*===========================*
  109.  * INITIALIZATION PROCEDURES *
  110.  *===========================*/
  111.  
  112.  
  113. /*===========================================================================*
  114.  *
  115.  * SetBSearchAlg
  116.  *
  117.  *    set the B-search algorithm
  118.  *
  119.  * RETURNS:    nothing
  120.  *
  121.  * SIDE EFFECTS:    bsearchAlg modified
  122.  *
  123.  *===========================================================================*/
  124. void
  125. SetBSearchAlg(alg)
  126.     char *alg;
  127. {
  128.     if ( strcmp(alg, "SIMPLE") == 0 ) {
  129.     bsearchAlg = BSEARCH_SIMPLE;
  130.     } else if ( strcmp(alg, "CROSS2") == 0 ) {
  131.     bsearchAlg = BSEARCH_CROSS2;
  132.     } else if ( strcmp(alg, "EXHAUSTIVE") == 0 ) {
  133.     bsearchAlg = BSEARCH_EXHAUSTIVE;
  134.     } else {
  135.     fprintf(stderr, "ERROR:  Illegal bsearch alg:  %s\n", alg);
  136.     exit(1);
  137.     }
  138. }
  139.  
  140.  
  141. /*===========================================================================*
  142.  *
  143.  * BSearchName
  144.  *
  145.  *    return the text of the B-search algorithm
  146.  *
  147.  * RETURNS:    a pointer to the string
  148.  *
  149.  * SIDE EFFECTS:    none
  150.  *
  151.  *===========================================================================*/
  152. char *
  153. BSearchName()
  154. {
  155.     switch(bsearchAlg) {
  156.     case BSEARCH_SIMPLE:
  157.         return "SIMPLE";
  158.     case BSEARCH_CROSS2:
  159.         return "CROSS2";
  160.     case BSEARCH_EXHAUSTIVE:
  161.         return "EXHAUSTIVE";
  162.     default:
  163.         exit(1);
  164.         break;
  165.     }
  166. }
  167.  
  168.  
  169. /*===========================================================================*
  170.  *
  171.  * BMotionSearch
  172.  *
  173.  *    search for the best B-frame motion vectors
  174.  *
  175.  * RETURNS:    MOTION_FORWARD        forward motion should be used
  176.  *        MOTION_BACKWARD     backward motion should be used
  177.  *        MOTION_INTERPOLATE  both should be used and interpolated
  178.  *
  179.  * OUTPUTS:    *fmx, *fmy  =    TWICE the forward motion vector
  180.  *        *bmx, *bmy  =    TWICE the backward motion vector
  181.  *
  182.  * SIDE EFFECTS:    none
  183.  *
  184.  * PRECONDITIONS:    The relevant block in 'current' is valid (it has not
  185.  *            been dct'd).  Thus, the data in 'current' can be
  186.  *            accesed through y_blocks, cr_blocks, and cb_blocks.
  187.  *            This is not the case for the blocks in 'prev' and
  188.  *            'next.'  Therefore, references into 'prev' and 'next'
  189.  *            should be done
  190.  *            through the struct items ref_y, ref_cr, ref_cb
  191.  *
  192.  * POSTCONDITIONS:    current, prev, next should be unchanged.
  193.  *            Some computation could be saved by requiring
  194.  *            the dct'd difference to be put into current's block
  195.  *            elements here, depending on the search technique.
  196.  *            However, it was decided that it mucks up the code
  197.  *            organization a little, and the saving in computation
  198.  *            would be relatively little (if any).
  199.  *
  200.  * NOTES:    the search procedure MAY return (0,0) motion vectors
  201.  *
  202.  *===========================================================================*/
  203. int
  204. BMotionSearch(currentBlock, prev, next, by, bx, fmy, fmx, bmy, bmx, oldMode)
  205.     LumBlock currentBlock;
  206.     MpegFrame *prev;
  207.     MpegFrame *next;
  208.     int by;
  209.     int bx;
  210.     int *fmy;
  211.     int *fmx;
  212.     int *bmy;
  213.     int *bmx;
  214.     int oldMode;
  215. {
  216.     /* simply call the appropriate algorithm, based on user preference */
  217.  
  218.     switch(bsearchAlg) {
  219.     case BSEARCH_SIMPLE:
  220.         return BMotionSearchSimple(currentBlock, prev, next, by, bx, fmy,
  221.                        fmx, bmy, bmx, oldMode);
  222.         break;
  223.     case BSEARCH_CROSS2:
  224.         return BMotionSearchCross2(currentBlock, prev, next, by, bx, fmy,
  225.                        fmx, bmy, bmx, oldMode);
  226.         break;
  227.     case BSEARCH_EXHAUSTIVE:
  228.         return BMotionSearchExhaust(currentBlock, prev, next, by, bx, fmy,
  229.                        fmx, bmy, bmx, oldMode);
  230.         break;
  231.     default:
  232.         fprintf(stderr, "Illegal B-frame motion search algorithm:  %d\n",
  233.             bsearchAlg);
  234.         exit(1);
  235.     }
  236. }
  237.  
  238.  
  239. /*===========================================================================*
  240.  *
  241.  * BMotionSearchSimple
  242.  *
  243.  *    does a simple search for B-frame motion vectors
  244.  *    see BMotionSearch for generic description
  245.  *
  246.  * DESCRIPTION:
  247.  *    1)  find best backward and forward vectors
  248.  *    2)  compute interpolated error using those two vectors
  249.  *    3)  return the best of the three choices
  250.  *
  251.  *===========================================================================*/
  252. static int
  253. BMotionSearchSimple(currentBlock, prev, next, by, bx, fmy, fmx, bmy, bmx,
  254.             oldMode)
  255.     LumBlock currentBlock;
  256.     MpegFrame *prev;
  257.     MpegFrame *next;
  258.     int by;
  259.     int bx;
  260.     int *fmy;
  261.     int *fmx;
  262.     int *bmy;
  263.     int *bmx;
  264.     int oldMode;
  265. {
  266.     int32    forwardErr, backErr, interpErr;
  267.     LumBlock    interpBlock;
  268.     int32    bestSoFar;
  269.  
  270.                     /* STEP 1 */
  271.     BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx,
  272.               &forwardErr, bmy, bmx, &backErr, TRUE);
  273.               
  274.                     /* STEP 2 */
  275.  
  276.     ComputeBMotionLumBlock(prev, next, by, bx, MOTION_INTERPOLATE,
  277.                *fmy, *fmx, *bmy, *bmx, interpBlock);
  278.     bestSoFar = min(backErr, forwardErr);
  279.     interpErr = LumBlockMAD(currentBlock, interpBlock, bestSoFar);
  280.  
  281.                 /* STEP 3 */
  282.  
  283.     if ( interpErr <= forwardErr ) {
  284.     if ( interpErr <= backErr ) {
  285.         return MOTION_INTERPOLATE;
  286.     }
  287.     else
  288.         return MOTION_BACKWARD;
  289.     } else if ( forwardErr <= backErr ) {
  290.     return MOTION_FORWARD;
  291.     } else {
  292.     return MOTION_BACKWARD;
  293.     }
  294. }
  295.  
  296.  
  297. /*===========================================================================*
  298.  *
  299.  * BMotionSearchCross2
  300.  *
  301.  *    does a cross-2 search for B-frame motion vectors
  302.  *    see BMotionSearch for generic description
  303.  *
  304.  * DESCRIPTION:
  305.  *    1)  find best backward and forward vectors
  306.  *    2)  find best matching interpolating vectors
  307.  *    3)  return the best of the 4 choices
  308.  *
  309.  *===========================================================================*/
  310. static int
  311. BMotionSearchCross2(currentBlock, prev, next, by, bx, fmy, fmx, bmy, bmx,
  312.             oldMode)
  313.     LumBlock currentBlock;
  314.     MpegFrame *prev;
  315.     MpegFrame *next;
  316.     int by;
  317.     int bx;
  318.     int *fmy;
  319.     int *fmx;
  320.     int *bmy;
  321.     int *bmx;
  322.     int oldMode;
  323. {
  324.     LumBlock    forwardBlock, backBlock;
  325.     int32    forwardErr, backErr, interpErr;
  326.     int        newfmy, newfmx, newbmy, newbmx;
  327.     int32    interpErr2;
  328.     int32    bestErr;
  329.  
  330.                 /* STEP 1 */
  331.  
  332.     BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx,
  333.               &forwardErr, bmy, bmx, &backErr, TRUE);
  334.  
  335.     bestErr = min(forwardErr, backErr);
  336.  
  337.                 /* STEP 2 */
  338.     ComputeBMotionLumBlock(prev, next, by, bx, MOTION_FORWARD,
  339.                *fmy, *fmx, 0, 0, forwardBlock);
  340.     ComputeBMotionLumBlock(prev, next, by, bx, MOTION_BACKWARD,
  341.                0, 0, *bmy, *bmx, backBlock);
  342.  
  343.     /* try a cross-search; total of 4 local searches */    
  344.     newbmy = *bmy;    newbmx = *bmx;
  345.     newfmy = *fmy;    newfmx = *fmx;
  346.  
  347.     interpErr = FindBestMatch(forwardBlock, currentBlock, next, by, bx,
  348.                   &newbmy, &newbmx, bestErr);
  349.     bestErr = min(bestErr, interpErr);
  350.     interpErr2 = FindBestMatch(backBlock, currentBlock, prev, by, bx,
  351.                    &newfmy, &newfmx, bestErr);
  352.  
  353.                 /* STEP 3 */
  354.  
  355.     if ( interpErr <= interpErr2 ) {
  356.     newfmy = *fmy;
  357.     newfmx = *fmx;
  358.     }
  359.     else
  360.     {
  361.     newbmy = *bmy;
  362.     newbmx = *bmx;
  363.     interpErr = interpErr2;
  364.     }
  365.  
  366.     if ( interpErr <= forwardErr ) {
  367.     if ( interpErr <= backErr ) {
  368.         *fmy = newfmy;
  369.         *fmx = newfmx;
  370.         *bmy = newbmy;
  371.         *bmx = newbmx;
  372.  
  373.         return MOTION_INTERPOLATE;
  374.     }
  375.     else
  376.         return MOTION_BACKWARD;
  377.     } else if ( forwardErr <= backErr ) {
  378.     return MOTION_FORWARD;
  379.     } else {
  380.     return MOTION_BACKWARD;
  381.     }
  382. }
  383.  
  384.  
  385. /*===========================================================================*
  386.  *
  387.  * BMotionSearchExhaust
  388.  *
  389.  *    does an exhaustive search for B-frame motion vectors
  390.  *    see BMotionSearch for generic description
  391.  *
  392.  * DESCRIPTION:
  393.  *    1)  find best backward and forward vectors
  394.  *    2)  use exhaustive search to find best interpolating vectors
  395.  *    3)  return the best of the 3 choices
  396.  *
  397.  *===========================================================================*/
  398. static int
  399. BMotionSearchExhaust(currentBlock, prev, next, by, bx, fmy, fmx, bmy, bmx,
  400.             oldMode)
  401.     LumBlock currentBlock;
  402.     MpegFrame *prev;
  403.     MpegFrame *next;
  404.     int by;
  405.     int bx;
  406.     int *fmy;
  407.     int *fmx;
  408.     int *bmy;
  409.     int *bmx;
  410.     int oldMode;
  411. {
  412.     register int mx, my;
  413.     int32 diff, bestDiff;
  414.     int        stepSize;
  415.     LumBlock    forwardBlock;
  416.     int32    forwardErr, backErr;
  417.     int        newbmy, newbmx;
  418.     int        leftMY, leftMX;
  419.     int        rightMY, rightMX;
  420.     boolean result;
  421.  
  422.                 /* STEP 1 */
  423.  
  424.     BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx,
  425.               &forwardErr, bmy, bmx, &backErr, FALSE);
  426.  
  427.     if ( forwardErr <= backErr ) {
  428.         bestDiff = forwardErr;
  429.     result = MOTION_FORWARD;
  430.     }
  431.     else
  432.     {
  433.         bestDiff = backErr;
  434.     result = MOTION_BACKWARD;
  435.     }
  436.  
  437.                 /* STEP 2 */
  438.  
  439.     stepSize = (pixelFullSearch ? 2 : 1);
  440.  
  441.     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
  442.  
  443.     if ( searchRange < rightMY ) {
  444.     rightMY = searchRange;
  445.     }
  446.     if ( searchRange < rightMX ) {
  447.     rightMX = searchRange;
  448.     }
  449.  
  450.     for ( my = -searchRange; my < rightMY; my += stepSize ) {
  451.     if ( my < leftMY ) {
  452.         continue;
  453.     }
  454.  
  455.     for ( mx = -searchRange; mx < rightMX; mx += stepSize ) {
  456.         if ( mx < leftMX ) {
  457.         continue;
  458.         }
  459.  
  460.         ComputeBMotionLumBlock(prev, next, by, bx, MOTION_FORWARD,
  461.                my, mx, 0, 0, forwardBlock);
  462.  
  463.         newbmy = my;    newbmx = mx;
  464.  
  465.         diff = FindBestMatch(forwardBlock, currentBlock, next, by, bx,
  466.                  &newbmy, &newbmx, bestDiff);
  467.  
  468.         if ( diff < bestDiff ) {
  469.         *fmy = my;
  470.         *fmx = mx;
  471.         *bmy = newbmy;
  472.         *bmx = newbmx;
  473.         bestDiff = diff;
  474.         result = MOTION_INTERPOLATE;
  475.         }
  476.     }
  477.     }
  478.  
  479.     return result;
  480. }
  481.  
  482.  
  483. /*===========================================================================*
  484.  *
  485.  * FindBestMatch
  486.  *
  487.  *    given a motion-compensated block in one direction, tries to find
  488.  *    the best motion vector in the opposite direction to match it
  489.  *
  490.  * RETURNS:    the best vector (*motionY, *motionX), and the corresponding
  491.  *        error is returned if it is better than bestSoFar.  If not,
  492.  *        then a number greater than bestSoFar is returned and
  493.  *        (*motionY, *motionX) has no meaning.
  494.  *
  495.  * SIDE EFFECTS:  none
  496.  *
  497.  *===========================================================================*/
  498. static int32
  499. FindBestMatch(block, currentBlock, prev, by, bx, motionY, motionX, bestSoFar)
  500.     LumBlock block;
  501.     LumBlock currentBlock;
  502.     MpegFrame *prev;
  503.     int by;
  504.     int bx;
  505.     int *motionY;
  506.     int *motionX;
  507.     int32 bestSoFar;
  508. {
  509.     int32    result;
  510.  
  511.     switch(psearchAlg) {
  512.     case PSEARCH_SUBSAMPLE:
  513.         result = FindBestMatchSubSample(block, currentBlock, prev, by, bx,
  514.                         motionY, motionX, bestSoFar);
  515.         break;
  516.     case PSEARCH_EXHAUSTIVE:
  517.         result = FindBestMatchExhaust(block, currentBlock, prev, by, bx,
  518.                       motionY, motionX, bestSoFar);
  519.         break;
  520.     case PSEARCH_LOGARITHMIC:
  521.         result = FindBestMatchLogarithmic(block, currentBlock, prev, by, bx,
  522.                           motionY, motionX, bestSoFar);
  523.         break;
  524.     case PSEARCH_TWOLEVEL:
  525.         result = FindBestMatchTwoLevel(block, currentBlock, prev, by, bx,
  526.                        motionY, motionX, bestSoFar);
  527.         break;
  528.     default:
  529.         fprintf(stderr, "ERROR:  Illegal P-search alg %d\n", psearchAlg);
  530.         exit(1);
  531.     }
  532.  
  533.     return result;
  534. }
  535.  
  536.  
  537. /*===========================================================================*
  538.  *
  539.  * FindBestMatchExhaust
  540.  *
  541.  *    tries to find matching motion vector
  542.  *    see FindBestMatch for generic description
  543.  *
  544.  * DESCRIPTION:  uses an exhaustive search
  545.  *
  546.  *===========================================================================*/
  547. static int32
  548. FindBestMatchExhaust(block, currentBlock, prev, by, bx, motionY, motionX,
  549.              bestSoFar)
  550.     LumBlock block;
  551.     LumBlock currentBlock;
  552.     MpegFrame *prev;
  553.     int by;
  554.     int bx;
  555.     int *motionY;
  556.     int *motionX;
  557.     int32 bestSoFar;
  558. {
  559.     register int mx, my;
  560.     int32 diff, bestDiff;
  561.     int        stepSize;
  562.     int        leftMY, leftMX;
  563.     int        rightMY, rightMX;
  564.     int        distance;
  565.     int        tempRightMY, tempRightMX;
  566.     boolean changed = FALSE;
  567.  
  568.     stepSize = (pixelFullSearch ? 2 : 1);
  569.  
  570.     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
  571.  
  572.     /* try old motion vector first */
  573.     if ( VALID_MOTION(*motionY, *motionX) ) {
  574.     bestDiff = LumAddMotionError(currentBlock, block, prev, by, bx,
  575.                      *motionY, *motionX, bestSoFar);
  576.  
  577.     if ( bestSoFar < bestDiff ) {
  578.         bestDiff = bestSoFar;
  579.     }
  580.     }
  581.     else
  582.     {
  583.     *motionY = 0;
  584.     *motionX = 0;
  585.  
  586.     bestDiff = bestSoFar;
  587.     }
  588.  
  589. /* maybe should try spiral pattern centered around  prev motion vector? */
  590.  
  591.  
  592.     /* try a spiral pattern */    
  593.     for ( distance = stepSize; distance <= searchRange; distance += stepSize ) {
  594.     tempRightMY = rightMY;
  595.     if ( distance < tempRightMY ) {
  596.         tempRightMY = distance;
  597.     }
  598.     tempRightMX = rightMX;
  599.     if ( distance < tempRightMX ) {
  600.         tempRightMX = distance;
  601.     }
  602.  
  603.     /* do top, bottom */
  604.     for ( my = -distance; my < tempRightMY;
  605.           my += max(tempRightMY+distance-stepSize, stepSize) ) {
  606.         if ( my < leftMY ) {
  607.         continue;
  608.         }
  609.  
  610.         for ( mx = -distance; mx < tempRightMX; mx += stepSize ) {
  611.         if ( mx < leftMX ) {
  612.             continue;
  613.         }
  614.  
  615.         diff = LumAddMotionError(currentBlock, block, prev, by, bx,
  616.                      my, mx, bestDiff);
  617.  
  618.         if ( diff < bestDiff ) {
  619.             *motionY = my;
  620.             *motionX = mx;
  621.             bestDiff = diff;
  622.         }
  623.         }
  624.     }
  625.  
  626.     /* do left, right */
  627.     for ( mx = -distance; mx < tempRightMX; mx += max(tempRightMX+distance-stepSize, stepSize) ) {
  628.         if ( mx < leftMX ) {
  629.         continue;
  630.         }
  631.  
  632.         for ( my = -distance+stepSize; my < tempRightMY-stepSize; my += stepSize ) {
  633.         if ( my < leftMY ) {
  634.             continue;
  635.         }
  636.  
  637.         diff = LumAddMotionError(currentBlock, block, prev, by, bx,
  638.                      my, mx, bestDiff);
  639.  
  640.         if ( diff < bestDiff ) {
  641.             *motionY = my;
  642.             *motionX = mx;
  643.             bestDiff = diff;
  644.             changed = TRUE;
  645.         }
  646.         }
  647.     }
  648.     }
  649.  
  650.     if ( ! changed ) {
  651.     bestDiff++;
  652.     }
  653.  
  654.     return bestDiff;
  655. }
  656.  
  657.  
  658. /*===========================================================================*
  659.  *
  660.  * FindBestMatchTwoLevel
  661.  *
  662.  *    tries to find matching motion vector
  663.  *    see FindBestMatch for generic description
  664.  *
  665.  * DESCRIPTION:  uses an exhaustive full-pixel search, then looks at
  666.  *         neighboring half-pixels
  667.  *
  668.  *===========================================================================*/
  669. static int32
  670. FindBestMatchTwoLevel(block, currentBlock, prev, by, bx, motionY, motionX,
  671.               bestSoFar)
  672.     LumBlock block;
  673.     LumBlock currentBlock;
  674.     MpegFrame *prev;
  675.     int by;
  676.     int bx;
  677.     int *motionY;
  678.     int *motionX;
  679.     int32 bestSoFar;
  680. {
  681.     register int mx, my;
  682.     int32 diff, bestDiff;
  683.     int        leftMY, leftMX;
  684.     int        rightMY, rightMX;
  685.     int        distance;
  686.     int        tempRightMY, tempRightMX;
  687.     boolean changed = FALSE;
  688.     int        yOffset, xOffset;
  689.  
  690.     /* exhaustive full-pixel search first */
  691.  
  692.     COMPUTE_MOTION_BOUNDARY(by,bx,2,leftMY,leftMX,rightMY,rightMX);
  693.  
  694.     rightMY--;
  695.     rightMX--;
  696.  
  697.     /* try old motion vector first */
  698.     if ( VALID_MOTION(*motionY, *motionX) ) {
  699.     bestDiff = LumAddMotionError(currentBlock, block, prev, by, bx,
  700.                      *motionY, *motionX, bestSoFar);
  701.  
  702.     if ( bestSoFar < bestDiff ) {
  703.         bestDiff = bestSoFar;
  704.     }
  705.     }
  706.     else
  707.     {
  708.     *motionY = 0;
  709.     *motionX = 0;
  710.  
  711.     bestDiff = bestSoFar;
  712.     }
  713.  
  714.     rightMY++;
  715.     rightMX++;
  716.  
  717. /* maybe should try spiral pattern centered around  prev motion vector? */
  718.  
  719.  
  720.     /* try a spiral pattern */    
  721.     for ( distance = 2; distance <= searchRange; distance += 2 ) {
  722.     tempRightMY = rightMY;
  723.     if ( distance < tempRightMY ) {
  724.         tempRightMY = distance;
  725.     }
  726.     tempRightMX = rightMX;
  727.     if ( distance < tempRightMX ) {
  728.         tempRightMX = distance;
  729.     }
  730.  
  731.     /* do top, bottom */
  732.     for ( my = -distance; my < tempRightMY;
  733.           my += max(tempRightMY+distance-2, 2) ) {
  734.         if ( my < leftMY ) {
  735.         continue;
  736.         }
  737.  
  738.         for ( mx = -distance; mx < tempRightMX; mx += 2 ) {
  739.         if ( mx < leftMX ) {
  740.             continue;
  741.         }
  742.  
  743.         diff = LumAddMotionError(currentBlock, block, prev, by, bx,
  744.                      my, mx, bestDiff);
  745.  
  746.         if ( diff < bestDiff ) {
  747.             *motionY = my;
  748.             *motionX = mx;
  749.             bestDiff = diff;
  750.         }
  751.         }
  752.     }
  753.  
  754.     /* do left, right */
  755.     for ( mx = -distance; mx < tempRightMX; mx += max(tempRightMX+distance-2, 2) ) {
  756.         if ( mx < leftMX ) {
  757.         continue;
  758.         }
  759.  
  760.         for ( my = -distance+2; my < tempRightMY-2; my += 2 ) {
  761.         if ( my < leftMY ) {
  762.             continue;
  763.         }
  764.  
  765.         diff = LumAddMotionError(currentBlock, block, prev, by, bx,
  766.                      my, mx, bestDiff);
  767.  
  768.         if ( diff < bestDiff ) {
  769.             *motionY = my;
  770.             *motionX = mx;
  771.             bestDiff = diff;
  772.             changed = TRUE;
  773.         }
  774.         }
  775.     }
  776.     }
  777.  
  778.     /* now look at neighboring half-pixels */
  779.     my = *motionY;
  780.     mx = *motionX;
  781.  
  782.     rightMY--;
  783.     rightMX--;
  784.  
  785.     for ( yOffset = -1; yOffset <= 1; yOffset++ ) {
  786.     for ( xOffset = -1; xOffset <= 1; xOffset++ ) {
  787.         if ( (yOffset == 0) && (xOffset == 0) )
  788.         continue;
  789.  
  790.         if ( VALID_MOTION(my+yOffset, mx+xOffset) &&
  791.          ((diff = LumAddMotionError(currentBlock, block, prev, by, bx,
  792.              my+yOffset, mx+xOffset, bestDiff)) < bestDiff) ) {
  793.         *motionY = my+yOffset;
  794.         *motionX = mx+xOffset;
  795.         bestDiff = diff;
  796.         changed = TRUE;
  797.         }
  798.     }
  799.     }
  800.  
  801.     if ( ! changed ) {
  802.     bestDiff++;
  803.     }
  804.  
  805.     return bestDiff;
  806. }
  807.  
  808.  
  809. /*===========================================================================*
  810.  *
  811.  * FindBestMatchLogarithmic
  812.  *
  813.  *    tries to find matching motion vector
  814.  *    see FindBestMatch for generic description
  815.  *
  816.  * DESCRIPTION:  uses a logarithmic search
  817.  *
  818.  *===========================================================================*/
  819. static int32
  820. FindBestMatchLogarithmic(block, currentBlock, prev, by, bx, motionY, motionX,
  821.              bestSoFar)
  822.     LumBlock block;
  823.     LumBlock currentBlock;
  824.     MpegFrame *prev;
  825.     int by;
  826.     int bx;
  827.     int *motionY;
  828.     int *motionX;
  829.     int32 bestSoFar;
  830. {
  831.     register int mx, my;
  832.     int32 diff, bestDiff;
  833.     int        stepSize;
  834.     int        leftMY, leftMX;
  835.     int        rightMY, rightMX;
  836.     int        tempRightMY, tempRightMX;
  837.     int        spacing;
  838.     int        centerX, centerY;
  839.     int        newCenterX, newCenterY;
  840.  
  841.     stepSize = (pixelFullSearch ? 2 : 1);
  842.  
  843.     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
  844.  
  845.     bestDiff = 0x7fffffff;
  846.  
  847.     /* grid spacing */
  848.     if ( stepSize == 2 ) {    /* make sure spacing is even */
  849.     spacing = (searchRange+1)/2;
  850.     if ( (spacing % 2) != 0 ) {
  851.         spacing++;
  852.     }
  853.     }
  854.     else
  855.     spacing = (searchRange+1)/2;
  856.     centerX = 0;
  857.     centerY = 0;
  858.  
  859.     while ( spacing >= stepSize ) {
  860.     newCenterY = centerY;
  861.     newCenterX = centerX;
  862.  
  863.     tempRightMY = rightMY;
  864.     if ( centerY+spacing+1 < tempRightMY ) {
  865.         tempRightMY = centerY+spacing+1;
  866.     }
  867.     tempRightMX = rightMX;
  868.     if ( centerX+spacing+1 < tempRightMX ) {
  869.         tempRightMX = centerX+spacing+1;
  870.     }
  871.  
  872.     for ( my = centerY-spacing; my < tempRightMY; my += spacing ) {
  873.         if ( my < leftMY ) {
  874.         continue;
  875.         }
  876.  
  877.         for ( mx = centerX-spacing; mx < tempRightMX; mx += spacing ) {
  878.         if ( mx < leftMX ) {
  879.             continue;
  880.         }
  881.  
  882.         diff = LumAddMotionError(currentBlock, block, prev, by, bx,
  883.                      my, mx, bestDiff);
  884.  
  885.         if ( diff < bestDiff ) {
  886.             newCenterY = my;
  887.             newCenterX = mx;
  888.  
  889.             bestDiff = diff;
  890.         }
  891.         }
  892.     }
  893.  
  894.     centerY = newCenterY;
  895.     centerX = newCenterX;
  896.  
  897.     if ( stepSize == 2 ) {    /* make sure spacing is even */
  898.         if ( spacing == 2 ) {
  899.         spacing = 0;
  900.         }
  901.         else
  902.         {
  903.         spacing = (spacing+1)/2;
  904.         if ( (spacing % 2) != 0 ) {
  905.             spacing++;
  906.         }
  907.         }
  908.     }
  909.     else
  910.     {
  911.         if ( spacing == 1 ) {
  912.         spacing = 0;
  913.         }
  914.         else
  915.         spacing = (spacing+1)/2;
  916.     }
  917.     }
  918.  
  919.     /* check old motion -- see if it's better */
  920.     if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
  921.      (*motionX >= leftMX) && (*motionX < rightMX) ) {
  922.     diff = LumAddMotionError(currentBlock, block, prev, by, bx, *motionY, *motionX, bestDiff);
  923.     } else {
  924.     diff = 0x7fffffff;
  925.     }
  926.  
  927.     if ( bestDiff < diff ) {
  928.     *motionY = centerY;
  929.     *motionX = centerX;
  930.     }
  931.     else
  932.     bestDiff = diff;
  933.  
  934.     return bestDiff;
  935. }
  936.  
  937.  
  938. /*===========================================================================*
  939.  *
  940.  * FindBestMatchSubSample
  941.  *
  942.  *    tries to find matching motion vector
  943.  *    see FindBestMatch for generic description
  944.  *
  945.  * DESCRIPTION:  should use subsampling method, but too lazy to write all
  946.  *         the code for it (so instead just calls FindBestMatchExhaust)
  947.  *
  948.  *===========================================================================*/
  949. static int32
  950. FindBestMatchSubSample(block, currentBlock, prev, by, bx, motionY, motionX,
  951.              bestSoFar)
  952.     LumBlock block;
  953.     LumBlock currentBlock;
  954.     MpegFrame *prev;
  955.     int by;
  956.     int bx;
  957.     int *motionY;
  958.     int *motionX;
  959.     int32 bestSoFar;
  960. {
  961.     /* too lazy to write the code for this... */
  962.  
  963.     return FindBestMatchExhaust(block, currentBlock, prev,
  964.                 by, bx, motionY, motionX, bestSoFar);
  965. }
  966.  
  967.  
  968. /*===========================================================================*
  969.  *
  970.  * BMotionSearchNoInterp
  971.  *
  972.  *    finds the best backward and forward motion vectors
  973.  *    if backNeeded == FALSE, then won't find best backward vector if it
  974.  *    is worse than the best forward vector
  975.  *
  976.  * RETURNS:    (*fmy,*fmx) and associated error *forwardErr
  977.  *        (*bmy,*bmx) and associated error *backErr
  978.  *
  979.  * SIDE EFFECTS:    none
  980.  *
  981.  *===========================================================================*/
  982. static void
  983. BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx, forwardErr,
  984.               bmy, bmx, backErr, backNeeded)
  985.     LumBlock currentBlock;
  986.     MpegFrame *prev;
  987.     MpegFrame *next;
  988.     int by;
  989.     int bx;
  990.     int *fmy;
  991.     int *fmx;
  992.     int *forwardErr;
  993.     int *bmy;
  994.     int *bmx;
  995.     int *backErr;
  996.     boolean backNeeded;
  997. {
  998.     /* CALL SEARCH PROCEDURE */
  999.     switch(psearchAlg) {
  1000.     case PSEARCH_SUBSAMPLE:
  1001.         *forwardErr = PSubSampleSearch(currentBlock, prev, by, bx,
  1002.                       fmy, fmx);
  1003.         *backErr = PSubSampleSearch(currentBlock, next, by, bx, bmy, bmx);
  1004.         break;
  1005.     case PSEARCH_EXHAUSTIVE:
  1006.         *forwardErr = PLocalSearch(currentBlock, prev, by, bx, fmy, fmx, 0x7fffffff);
  1007.         if ( backNeeded ) {
  1008.         *backErr = PLocalSearch(currentBlock, next, by, bx, bmy, bmx, 0x7fffffff);
  1009.         } else {
  1010.         *backErr = PLocalSearch(currentBlock, next, by, bx, bmy, bmx, *forwardErr);
  1011.         }
  1012.         break;
  1013.     case PSEARCH_LOGARITHMIC:
  1014.         *forwardErr = PLogarithmicSearch(currentBlock, prev, by, bx, fmy, fmx);
  1015.         *backErr = PLogarithmicSearch(currentBlock, next, by, bx, bmy, bmx);
  1016.         break;
  1017.     case PSEARCH_TWOLEVEL:
  1018.         *forwardErr = PTwoLevelSearch(currentBlock, prev, by, bx, fmy, fmx, 0x7fffffff);
  1019.         if ( backNeeded ) {
  1020.         *backErr = PTwoLevelSearch(currentBlock, next, by, bx, bmy, bmx, 0x7fffffff);
  1021.         } else {
  1022.         *backErr = PTwoLevelSearch(currentBlock, next, by, bx, bmy, bmx, *forwardErr);
  1023.         }
  1024.         break;
  1025.     default:
  1026.         fprintf(stderr, "ERROR:  Illegal PSEARCH ALG:  %d\n", psearchAlg);
  1027.         exit(1);    
  1028.         break;
  1029.     }
  1030. }
  1031.  
  1032.  
  1033.  
  1034. /*===========================================================================*
  1035.  *                                         *
  1036.  * UNUSED PROCEDURES                                 *
  1037.  *                                         *
  1038.  *    The following procedures are all unused by the encoder             *
  1039.  *                                         *
  1040.  *    They are listed here for your convenience.  You might want to use    *
  1041.  *    them if you experiment with different search techniques             *
  1042.  *                                         *
  1043.  *===========================================================================*/
  1044.  
  1045. #ifdef UNUSED_PROCEDURES
  1046.  
  1047. /*===========================================================================*
  1048.  *
  1049.  * ValidBMotion
  1050.  *
  1051.  *    decides if the given B-frame motion is valid
  1052.  *
  1053.  * RETURNS:    TRUE if the motion is valid, FALSE otherwise
  1054.  *
  1055.  * SIDE EFFECTS:    none
  1056.  *
  1057.  *===========================================================================*/
  1058. boolean
  1059. ValidBMotion(by, bx, mode, fmy, fmx, bmy, bmx)
  1060.     int by;
  1061.     int bx;
  1062.     int mode;
  1063.     int fmy;
  1064.     int fmx;
  1065.     int bmy;
  1066.     int bmx;
  1067. {
  1068.     if ( mode != MOTION_BACKWARD ) {
  1069.     /* check forward motion for bounds */
  1070.     if ( (by*DCTSIZE+(fmy-1)/2 < 0) || ((by+2)*DCTSIZE+(fmy+1)/2-1 >= Fsize_y) ) {
  1071.         return FALSE;
  1072.     }
  1073.     if ( (bx*DCTSIZE+(fmx-1)/2 < 0) || ((bx+2)*DCTSIZE+(fmx+1)/2-1 >= Fsize_x) ) {
  1074.         return FALSE;
  1075.     }
  1076.     }
  1077.  
  1078.     if ( mode != MOTION_FORWARD ) {
  1079.     /* check backward motion for bounds */
  1080.     if ( (by*DCTSIZE+(bmy-1)/2 < 0) || ((by+2)*DCTSIZE+(bmy+1)/2-1 >= Fsize_y) ) {
  1081.         return FALSE;
  1082.     }
  1083.     if ( (bx*DCTSIZE+(bmx-1)/2 < 0) || ((bx+2)*DCTSIZE+(bmx+1)/2-1 >= Fsize_x) ) {
  1084.         return FALSE;
  1085.     }
  1086.     }
  1087.  
  1088.     return TRUE;
  1089. }
  1090.  
  1091.  
  1092. #endif UNUSED_PROCEDURES
  1093.