bsearch.c

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

    /* try a spiral pattern */    
    for ( distance = 2; distance <= searchRange; distance += 2 ) {
    tempRightMY = rightMY;
    if ( distance < tempRightMY ) {
        tempRightMY = distance;
    }
    tempRightMX = rightMX;
    if ( distance < tempRightMX ) {
        tempRightMX = distance;
    }

    /* do top, bottom */
    for ( my = -distance; my < tempRightMY;
          my += max(tempRightMY+distance-2, 2) ) {
        if ( my < leftMY ) {
        continue;
        }

        for ( mx = -distance; mx < tempRightMX; mx += 2 ) {
        if ( mx < leftMX ) {
            continue;
        }

        diff = LumAddMotionError(currentBlock, block, prev, by, bx,
                     my, mx, bestDiff);

        if ( diff < bestDiff ) {
            *motionY = my;
            *motionX = mx;
            bestDiff = diff;
        }
        }
    }

    /* do left, right */
    for ( mx = -distance; mx < tempRightMX; mx += max(tempRightMX+distance-2, 2) ) {
        if ( mx < leftMX ) {
        continue;
        }

        for ( my = -distance+2; my < tempRightMY-2; my += 2 ) {
        if ( my < leftMY ) {
            continue;
        }

        diff = LumAddMotionError(currentBlock, block, prev, by, bx,
                     my, mx, bestDiff);

        if ( diff < bestDiff ) {
            *motionY = my;
            *motionX = mx;
            bestDiff = diff;
            changed = TRUE;
        }
        }
    }
    }

    /* now look at neighboring half-pixels */
    my = *motionY;
    mx = *motionX;

    rightMY--;
    rightMX--;

    for ( yOffset = -1; yOffset <= 1; yOffset++ ) {
    for ( xOffset = -1; xOffset <= 1; xOffset++ ) {
        if ( (yOffset == 0) && (xOffset == 0) )
        continue;

        if ( VALID_MOTION(my+yOffset, mx+xOffset) &&
         ((diff = LumAddMotionError(currentBlock, block, prev, by, bx,
             my+yOffset, mx+xOffset, bestDiff)) < bestDiff) ) {
        *motionY = my+yOffset;
        *motionX = mx+xOffset;
        bestDiff = diff;
        changed = TRUE;
        }
    }
    }

    if ( ! changed ) {
    bestDiff++;
    }

    return bestDiff;
}


/*===========================================================================*
 *
 * FindBestMatchLogarithmic
 *
 *  tries to find matching motion vector
 *  see FindBestMatch for generic description
 *
 * DESCRIPTION:  uses a logarithmic search
 *
 *===========================================================================*/
static int32
FindBestMatchLogarithmic(block, currentBlock, prev, by, bx, motionY, motionX,
             bestSoFar, searchRange)
    LumBlock block;
    LumBlock currentBlock;
    MpegFrame *prev;
    int by;
    int bx;
    int *motionY;
    int *motionX;
    int32 bestSoFar;
    int searchRange;
{
    register int mx, my;
    int32 diff, bestDiff;
    int     stepSize;
    int     leftMY, leftMX;
    int     rightMY, rightMX;
    int     tempRightMY, tempRightMX;
    int     spacing;
    int     centerX, centerY;
    int     newCenterX, newCenterY;

    stepSize = (pixelFullSearch ? 2 : 1);

    COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);

    bestDiff = 0x7fffffff;

    /* grid spacing */
    if ( stepSize == 2 ) {  /* make sure spacing is even */
    spacing = (searchRange+1)/2;
    if ( (spacing % 2) != 0 ) {
        spacing++;
    }
    }
    else
    spacing = (searchRange+1)/2;
    centerX = 0;
    centerY = 0;

    while ( spacing >= stepSize ) {
    newCenterY = centerY;
    newCenterX = centerX;

    tempRightMY = rightMY;
    if ( centerY+spacing+1 < tempRightMY ) {
        tempRightMY = centerY+spacing+1;
    }
    tempRightMX = rightMX;
    if ( centerX+spacing+1 < tempRightMX ) {
        tempRightMX = centerX+spacing+1;
    }

    for ( my = centerY-spacing; my < tempRightMY; my += spacing ) {
        if ( my < leftMY ) {
        continue;
        }

        for ( mx = centerX-spacing; mx < tempRightMX; mx += spacing ) {
        if ( mx < leftMX ) {
            continue;
        }

        diff = LumAddMotionError(currentBlock, block, prev, by, bx,
                     my, mx, bestDiff);

        if ( diff < bestDiff ) {
            newCenterY = my;
            newCenterX = mx;

            bestDiff = diff;
        }
        }
    }

    centerY = newCenterY;
    centerX = newCenterX;

    if ( stepSize == 2 ) {  /* make sure spacing is even */
        if ( spacing == 2 ) {
        spacing = 0;
        }
        else
        {
        spacing = (spacing+1)/2;
        if ( (spacing % 2) != 0 ) {
            spacing++;
        }
        }
    }
    else
    {
        if ( spacing == 1 ) {
        spacing = 0;
        }
        else
        spacing = (spacing+1)/2;
    }
    }

    /* check old motion -- see if it's better */
    if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
     (*motionX >= leftMX) && (*motionX < rightMX) ) {
    diff = LumAddMotionError(currentBlock, block, prev, by, bx, *motionY, *motionX, bestDiff);
    } else {
    diff = 0x7fffffff;
    }

    if ( bestDiff < diff ) {
    *motionY = centerY;
    *motionX = centerX;
    }
    else
    bestDiff = diff;

    return bestDiff;
}


/*===========================================================================*
 *
 * FindBestMatchSubSample
 *
 *  tries to find matching motion vector
 *  see FindBestMatch for generic description
 *
 * DESCRIPTION:  should use subsampling method, but too lazy to write all
 *       the code for it (so instead just calls FindBestMatchExhaust)
 *
 *===========================================================================*/
static int32
FindBestMatchSubSample(block, currentBlock, prev, by, bx, motionY, motionX,
             bestSoFar, searchRange)
    LumBlock block;
    LumBlock currentBlock;
    MpegFrame *prev;
    int by;
    int bx;
    int *motionY;
    int *motionX;
    int32 bestSoFar;
    int searchRange;
{
    /* too lazy to write the code for this... */

    return FindBestMatchExhaust(block, currentBlock, prev,
                by, bx, motionY, motionX, bestSoFar, searchRange);
}


/*===========================================================================*
 *
 * BMotionSearchNoInterp
 *
 *  finds the best backward and forward motion vectors
 *  if backNeeded == FALSE, then won't find best backward vector if it
 *  is worse than the best forward vector
 *
 * RETURNS: (*fmy,*fmx) and associated error *forwardErr
 *      (*bmy,*bmx) and associated error *backErr
 *
 * SIDE EFFECTS:    none
 *
 *===========================================================================*/
static void
BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx, forwardErr,
              bmy, bmx, backErr, backNeeded)
    LumBlock currentBlock;
    MpegFrame *prev;
    MpegFrame *next;
    int by;
    int bx;
    int *fmy;
    int *fmx;
    int32 *forwardErr;
    int *bmy;
    int *bmx;
    int32 *backErr;
    boolean backNeeded;
{
    /* CALL SEARCH PROCEDURE */
    switch(psearchAlg) {
    case PSEARCH_SUBSAMPLE:
        *forwardErr = PSubSampleSearch(currentBlock, prev, by, bx, 
                       fmy, fmx, searchRangeB);
        *backErr = PSubSampleSearch(currentBlock, next, by, bx, 
                    bmy, bmx, searchRangeB);
        break;
    case PSEARCH_EXHAUSTIVE:
        *forwardErr = PLocalSearch(currentBlock, prev, by, bx, fmy, fmx, 
                       0x7fffffff, searchRangeB);
        if ( backNeeded ) {
        *backErr = PLocalSearch(currentBlock, next, by, bx, bmy, bmx, 
                    0x7fffffff, searchRangeB);
        } else {
        *backErr = PLocalSearch(currentBlock, next, by, bx, bmy, bmx, 
                    *forwardErr, searchRangeB);
        }
        break;
    case PSEARCH_LOGARITHMIC:
        *forwardErr = PLogarithmicSearch(currentBlock, prev, by, bx, 
                         fmy, fmx, searchRangeB);
        *backErr = PLogarithmicSearch(currentBlock, next, by, bx, 
                      bmy, bmx, searchRangeB);
        break;
    case PSEARCH_TWOLEVEL:
        *forwardErr = PTwoLevelSearch(currentBlock, prev, by, bx, fmy, fmx, 
                      0x7fffffff, searchRangeB);
        if ( backNeeded ) {
        *backErr = PTwoLevelSearch(currentBlock, next, by, bx, bmy, bmx, 
                       0x7fffffff, searchRangeB);
        } else {
        *backErr = PTwoLevelSearch(currentBlock, next, by, bx, bmy, bmx, 
                       *forwardErr, searchRangeB);
        }
        break;
    default:
        fprintf(stderr, "ERROR:  Illegal PSEARCH ALG:  %d\n", psearchAlg);
        exit(1);    
        break;
    }
}



/*===========================================================================*
 *                                       *
 * UNUSED PROCEDURES                                 *
 *                                       *
 *  The following procedures are all unused by the encoder           *
 *                                       *
 *  They are listed here for your convenience.  You might want to use    *
 *  them if you experiment with different search techniques          *
 *                                       *
 *===========================================================================*/

#ifdef UNUSED_PROCEDURES

/*===========================================================================*
 *
 * ValidBMotion
 *
 *  decides if the given B-frame motion is valid
 *
 * RETURNS: TRUE if the motion is valid, FALSE otherwise
 *
 * SIDE EFFECTS:    none
 *
 *===========================================================================*/
boolean
ValidBMotion(by, bx, mode, fmy, fmx, bmy, bmx)
    int by;
    int bx;
    int mode;
    int fmy;
    int fmx;
    int bmy;
    int bmx;
{
    if ( mode != MOTION_BACKWARD ) {
    /* check forward motion for bounds */
    if ( (by*DCTSIZE+(fmy-1)/2 < 0) || ((by+2)*DCTSIZE+(fmy+1)/2-1 >= Fsize_y) ) {
        return FALSE;
    }
    if ( (bx*DCTSIZE+(fmx-1)/2 < 0) || ((bx+2)*DCTSIZE+(fmx+1)/2-1 >= Fsize_x) ) {
        return FALSE;
    }
    }

    if ( mode != MOTION_FORWARD ) {
    /* check backward motion for bounds */
    if ( (by*DCTSIZE+(bmy-1)/2 < 0) || ((by+2)*DCTSIZE+(bmy+1)/2-1 >= Fsize_y) ) {
        return FALSE;
    }
    if ( (bx*DCTSIZE+(bmx-1)/2 < 0) || ((bx+2)*DCTSIZE+(bmx+1)/2-1 >= Fsize_x) ) {
        return FALSE;
    }
    }

    return TRUE;
}


#endif /* UNUSED_PROCEDURES */