bsearch.c

linux下将各类格式图片转换工具

/*===========================================================================*
 * bsearch.c                                     *
 *                                       *
 *  Procedures concerned with the B-frame motion search          *
 *                                       *
 * EXPORTED PROCEDURES:                              *
 *  SetBSearchAlg                                *
 *  BMotionSearch                                *
 *  BSearchName                              *
 *                                       *
 *===========================================================================*/

/*
 * Copyright (c) 1995 The Regents of the University of California.
 * All rights reserved.
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose, without fee, and without written agreement is
 * hereby granted, provided that the above copyright notice and the following
 * two paragraphs appear in all copies of this software.
 *
 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 */

/*  
 *  $Header: /n/picasso/project/mpeg/mpeg_dist/mpeg_encode/RCS/bsearch.c,v 1.10 1995/08/07 21:49:01 smoot Exp $
 *  $Log: bsearch.c,v $
 *  Revision 1.10  1995/08/07 21:49:01  smoot
 *  fixed bug in initial-B-frame searches
 *
 *  Revision 1.9  1995/06/26 21:36:07  smoot
 *  added new ordering constraints
 *  (B frames which are backward P's at the start of a sequence)
 *
 *  Revision 1.8  1995/03/27 19:17:43  smoot
 *  killed useless type error messge (int32 defiend as int)
 *
 * Revision 1.7  1995/01/19  23:07:20  eyhung
 * Changed copyrights
 *
 * Revision 1.6  1994/12/07  00:40:36  smoot
 * Added seperate P and B search ranges
 *
 * Revision 1.5  1994/03/15  00:27:11  keving
 * nothing
 *
 * Revision 1.4  1993/12/22  19:19:01  keving
 * nothing
 *
 * Revision 1.3  1993/07/22  22:23:43  keving
 * nothing
 *
 * Revision 1.2  1993/06/30  20:06:09  keving
 * nothing
 *
 * Revision 1.1  1993/06/03  21:08:08  keving
 * nothing
 *
 * Revision 1.1  1993/03/02  18:27:05  keving
 * nothing
 *
 */


/*==============*
 * HEADER FILES *
 *==============*/

#include "all.h"
#include "mtypes.h"
#include "frames.h"
#include "motion_search.h"
#include "fsize.h"


/*==================*
 * STATIC VARIABLES *
 *==================*/

static int  bsearchAlg;


/*===============================*
 * INTERNAL PROCEDURE prototypes *
 *===============================*/

static int32    FindBestMatch _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
              int by, int bx, int *motionY, int *motionX, int32 bestSoFar, int searchRange));
static int BMotionSearchSimple _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
            MpegFrame *next, int by, int bx, int *fmy, int *fmx,
            int *bmy, int *bmx, int oldMode));
static int BMotionSearchCross2 _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
            MpegFrame *next, int by, int bx, int *fmy, int *fmx,
            int *bmy, int *bmx, int oldMode));
static int BMotionSearchExhaust _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
            MpegFrame *next, int by, int bx, int *fmy, int *fmx,
            int *bmy, int *bmx, int oldMode));
static void BMotionSearchNoInterp _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
                  MpegFrame *next, int by, int bx,
                  int *fmy, int *fmx, int32 *forwardErr,
                  int *bmy, int *bmx, int32 *backErr,
                           boolean backNeeded));
static int32    FindBestMatchExhaust _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
              int by, int bx, int *motionY, int *motionX,
              int32 bestSoFar, int searchRange));
static int32    FindBestMatchTwoLevel _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
              int by, int bx, int *motionY, int *motionX,
              int32 bestSoFar, int searchRange));
static int32    FindBestMatchLogarithmic _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
              int by, int bx, int *motionY, int *motionX,
              int32 bestSoFar, int searchRange));
static int32    FindBestMatchSubSample _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
              int by, int bx, int *motionY, int *motionX,
              int32 bestSoFar, int searchRange));


/*=====================*
 * EXPORTED PROCEDURES *
 *=====================*/

/*===========================*
 * INITIALIZATION PROCEDURES *
 *===========================*/


/*===========================================================================*
 *
 * SetBSearchAlg
 *
 *  set the B-search algorithm
 *
 * RETURNS: nothing
 *
 * SIDE EFFECTS:    bsearchAlg modified
 *
 *===========================================================================*/
void
SetBSearchAlg(const char * const alg)
{
    if ( strcmp(alg, "SIMPLE") == 0 ) {
    bsearchAlg = BSEARCH_SIMPLE;
    } else if ( strcmp(alg, "CROSS2") == 0 ) {
    bsearchAlg = BSEARCH_CROSS2;
    } else if ( strcmp(alg, "EXHAUSTIVE") == 0 ) {
    bsearchAlg = BSEARCH_EXHAUSTIVE;
    } else {
    fprintf(stderr, "ERROR:  Illegal bsearch alg:  %s\n", alg);
    exit(1);
    }
}


/*===========================================================================*
 *
 * BSearchName
 *
 *  return the text of the B-search algorithm
 *
 * RETURNS: a pointer to the string
 *
 * SIDE EFFECTS:    none
 *
 *===========================================================================*/
const char *
BSearchName(void)
{
    const char *retval;

    switch(bsearchAlg) {
    case BSEARCH_SIMPLE:
        retval = "SIMPLE";break;
    case BSEARCH_CROSS2:
        retval = "CROSS2";break;
    case BSEARCH_EXHAUSTIVE:
        retval = "EXHAUSTIVE";break;
    default:
        fprintf(stderr, "ERROR:  Illegal BSEARCH ALG:  %d\n", psearchAlg);
        exit(1);
        break;
    }
    return retval;
}


/*===========================================================================*
 *
 * BMotionSearch
 *
 *  search for the best B-frame motion vectors
 *
 * RETURNS: MOTION_FORWARD      forward motion should be used
 *      MOTION_BACKWARD     backward motion should be used
 *      MOTION_INTERPOLATE  both should be used and interpolated
 *
 * OUTPUTS: *fmx, *fmy  =   TWICE the forward motion vector
 *      *bmx, *bmy  =   TWICE the backward motion vector
 *
 * SIDE EFFECTS:    none
 *
 * PRECONDITIONS:   The relevant block in 'current' is valid (it has not
 *          been dct'd).  Thus, the data in 'current' can be
 *          accesed through y_blocks, cr_blocks, and cb_blocks.
 *          This is not the case for the blocks in 'prev' and
 *          'next.'  Therefore, references into 'prev' and 'next'
 *          should be done
 *          through the struct items ref_y, ref_cr, ref_cb
 *
 * POSTCONDITIONS:  current, prev, next should be unchanged.
 *          Some computation could be saved by requiring
 *          the dct'd difference to be put into current's block
 *          elements here, depending on the search technique.
 *          However, it was decided that it mucks up the code
 *          organization a little, and the saving in computation
 *          would be relatively little (if any).
 *
 * NOTES:   the search procedure MAY return (0,0) motion vectors
 *
 *===========================================================================*/
int
BMotionSearch(currentBlock, prev, next, by, bx, fmy, fmx, bmy, bmx, oldMode)
    LumBlock currentBlock;
    MpegFrame *prev;
    MpegFrame *next;
    int by;
    int bx;
    int *fmy;
    int *fmx;
    int *bmy;
    int *bmx;
    int oldMode;
{
    int retval;

  /* If we are an initial B frame, no possibility of forward motion */
  if (prev == (MpegFrame *) NULL) {
    PMotionSearch(currentBlock, next, by, bx, bmy, bmx);
    return MOTION_BACKWARD;
  }
  
  /* otherwise simply call the appropriate algorithm, based on user preference */
  
    switch(bsearchAlg) {
    case BSEARCH_SIMPLE:
        retval = BMotionSearchSimple(currentBlock, prev, next, by, bx, fmy,
                                     fmx, bmy, bmx, oldMode);
        break;
    case BSEARCH_CROSS2:
        retval = BMotionSearchCross2(currentBlock, prev, next, by, bx, fmy,
                                     fmx, bmy, bmx, oldMode);
        break;
    case BSEARCH_EXHAUSTIVE:
        retval = BMotionSearchExhaust(currentBlock, prev, next, by, bx, fmy,
                       fmx, bmy, bmx, oldMode);
        break;
    default:
        fprintf(stderr, "Illegal B-frame motion search algorithm:  %d\n",
            bsearchAlg);
        exit(1);
    }
    return retval;
}


/*===========================================================================*
 *
 * BMotionSearchSimple
 *
 *  does a simple search for B-frame motion vectors
 *  see BMotionSearch for generic description
 *
 * DESCRIPTION:
 *  1)  find best backward and forward vectors
 *  2)  compute interpolated error using those two vectors
 *  3)  return the best of the three choices
 *
 *===========================================================================*/
static int
BMotionSearchSimple(currentBlock, prev, next, by, bx, fmy, fmx, bmy, bmx,
            oldMode)
    LumBlock currentBlock;
    MpegFrame *prev;
    MpegFrame *next;
    int by;
    int bx;
    int *fmy;
    int *fmx;
    int *bmy;
    int *bmx;
    int oldMode;
{
    int32   forwardErr, backErr, interpErr;
    LumBlock    interpBlock;
    int32   bestSoFar;

                    /* STEP 1 */
    BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx,
              &forwardErr, bmy, bmx, &backErr, TRUE);
              
                    /* STEP 2 */

    ComputeBMotionLumBlock(prev, next, by, bx, MOTION_INTERPOLATE,
               *fmy, *fmx, *bmy, *bmx, interpBlock);
    bestSoFar = min(backErr, forwardErr);
    interpErr = LumBlockMAD(currentBlock, interpBlock, bestSoFar);

                /* STEP 3 */

    if ( interpErr <= forwardErr ) {
    if ( interpErr <= backErr ) {
        return MOTION_INTERPOLATE;
    }
    else
        return MOTION_BACKWARD;
    } else if ( forwardErr <= backErr ) {
    return MOTION_FORWARD;
    } else {
    return MOTION_BACKWARD;
    }
}


/*===========================================================================*
 *
 * BMotionSearchCross2
 *
 *  does a cross-2 search for B-frame motion vectors
 *  see BMotionSearch for generic description
 *
 * DESCRIPTION:
 *  1)  find best backward and forward vectors
 *  2)  find best matching interpolating vectors
 *  3)  return the best of the 4 choices
 *
 *===========================================================================*/
static int
BMotionSearchCross2(currentBlock, prev, next, by, bx, fmy, fmx, bmy, bmx,
            oldMode)
    LumBlock currentBlock;
    MpegFrame *prev;
    MpegFrame *next;
    int by;
    int bx;
    int *fmy;
    int *fmx;
    int *bmy;
    int *bmx;
    int oldMode;
{
    LumBlock    forwardBlock, backBlock;
    int32   forwardErr, backErr, interpErr;
    int     newfmy, newfmx, newbmy, newbmx;
    int32   interpErr2;
    int32   bestErr;

                /* STEP 1 */

    BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx,
              &forwardErr, bmy, bmx, &backErr, TRUE);

    bestErr = min(forwardErr, backErr);

                /* STEP 2 */
    ComputeBMotionLumBlock(prev, next, by, bx, MOTION_FORWARD,
               *fmy, *fmx, 0, 0, forwardBlock);
    ComputeBMotionLumBlock(prev, next, by, bx, MOTION_BACKWARD,
               0, 0, *bmy, *bmx, backBlock);

    /* try a cross-search; total of 4 local searches */    
    newbmy = *bmy;  newbmx = *bmx;
    newfmy = *fmy;  newfmx = *fmx;

    interpErr = FindBestMatch(forwardBlock, currentBlock, next, by, bx,
                  &newbmy, &newbmx, bestErr, searchRangeB);
    bestErr = min(bestErr, interpErr);
    interpErr2 = FindBestMatch(backBlock, currentBlock, prev, by, bx,
                   &newfmy, &newfmx, bestErr, searchRangeB);