java2d/loops/ScaledBlit.c

/*
 * Copyright (c) 2001, 2013, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

#include <math.h>

#include "jni_util.h"
#include "GraphicsPrimitiveMgr.h"
#include "Region.h"

#include "sun_java2d_loops_ScaledBlit.h"

/*
 * The scaling loops used inside the helper functions are based on the
 * following pseudocode for stepping through the source image:
 *
 * shift - number of bits of sub-pixel precision in scaled values
 * srcxorig, srcyorig - scaled location of first pixel
 * srcxinc, srcyinc - scaled x and y increments
 * dstwidth, dstheight - number of pixels to process across and down
 *
 * 1. srcy = srcyorig;
 * 2. for (dstheight) {
 * 3.     srcx = srcxorig;
 * 4.     for (dstwidth) {
 * 5.         fetch and process pixel for (srcx >> shift, srcy >> shift)
 * 6.         srcx += srcxinc;
 * 7.     }
 * 8.     srcy += srcyinc;
 * 9. }
 *
 * Note that each execution of line 6 or 8 accumulates error of
 * +/- 1 into the scaled coordinate variables.  These lines are
 * each executed once per pixel across or once per pixel down
 * the region being iterated over, thus the error can accumulate
 * up to a magnitude of dstwidth in the horizontal direction and
 * dstheight in the vertical direction.
 *
 * If the error ever reaches a magnitude of (1 << shift) then we
 * will be off by at least 1 source pixel in our mapping.
 *
 * Note that we increment the source coordinates by the srcxinc
 * and srcyinc variables in each step.  Thus, if our error ever
 * accumulates to a magnitude equal to srcxinc or srcyinc then
 * we will be ahead or behind of "where we should be" by at least
 * one iteration.  Since each iteration is a destination pixel,
 * this means that our actual location will be off by at least
 * one destination pixel.
 *
 * This means that all of the values:
 *
 *     - (1 << shift)
 *     - srcxinc
 *     - srcyinc
 *
 * all represent a maximum bound on how much error we can accumulate
 * before we are off by a source or a destination pixel.  Thus,
 * we should make sure that we never process more than that many
 * pixels if we want to maintain single pixel accuracy.  Even
 * better would be to process many fewer pixels than those bounds
 * to ensure that our accumulated error is much smaller than a
 * pixel.
 */

/*
 * Find and return the largest tile size that is a power of 2 and
 * which is small enough to yield some reassuring degree of subpixel
 * accuracy.  The degree of subpixel accuracy that will be preserved
 * by the tile size it chooses will vary and the details on how
 * it makes this decision are detailed in the comments below.
 */
static jint
findpow2tilesize(jint shift, jint sxinc, jint syinc)
{
    /*
     * The initial value of shift is our first estimate for
     * the power of 2 for our tilesize since it ensures
     * less than 1 source pixel of error.
     *
     * Reducing it until (1 << shift) is not larger than the
     * smallest of our increments ensures we will have no more
     * than 1 destination pixel of error as well.
     */
    if (sxinc > syinc) {
        sxinc = syinc;
    }
    if (sxinc == 0) {
        /* Degenerate case will cause infinite loop in next loop... */
        return 1;
    }
    while ((1 << shift) > sxinc) {
        shift--;
    }
    /*
     * shift is now the largest it can be for less than 1 pixel
     * of error in either source or destination spaces.
     *
     * Now we will try for at least 8 bits of subpixel accuracy
     * with a tile size of at least 256x256 and reduce our subpixel
     * accuracy on a sliding scale down to a tilesize of 1x1 when
     * we have no bits of sub-pixel accuracy.
     */
    if (shift >= 16) {
        /* Subtracting 8 asks for 8 bits of subpixel accuracy. */
        shift -= 8;
    } else {
        /* Ask for half of the remaining bits to be subpixel accuracy. */
        /* Rounding is in favor of subpixel accuracy over tile size. */
        /* Worst case, shift == 0 and tilesize == (1 << 0) == 1 */
        shift /= 2;
    }
    return (1 << shift);
}

/*
 * For a given integer destination pixel coordinate "id", calculate the
 * integer destination coordinate of the start of the "ts" sized tile
 * in which it resides.
 * Tiles all start at even multiples of the tile size from the integer
 * destination origin "io".
 *
 * id == integer destination coordinate
 * io == integer destination operation origin
 * ts == tilesize (must be power of 2)
 */
#define TILESTART(id, io, ts)   ((io) + (((id)-(io)) & (~((ts)-1))))

/*
 * For a given integer destination pixel coordinate "id", calculate the
 * sub-pixel accurate source coordinate from which its sample comes.
 * The returned source coordinate is expressed in a shifted fractional
 * arithmetic number system.
 *
 * id == integer destination coordinate
 * fo == floating point destination operation origin,
 * sf == source coordinate scale factor per destination pixel
 *       (multiplied by fractional arithmetic "shift")
 *
 * The caller is required to cast this value to the appropriate
 * integer type for the needed precision.  The rendering code which
 * deals only with valid coordinates within the bounds of the source
 * rectangle uses jint.  The setup code, which occasionally deals
 * with coordinates that run out of bounds, uses jlong.
 *
 * Note that the rounding in this calculation is at a fraction of a
 * source pixel of (1.0 / (1<<shift)) since the scale factor includes
 * the fractional shift.  As a result, the type of rounding used is
 * not very significant (floor, floor(x+.5), or ceil(x-.5)), but the
 * ceil(x-.5) version is used for consistency with the way that pixel
 * coordinates are rounded to assign the ".5" value to the lower
 * integer.
 */
#define SRCLOC(id, fo, sf)   (ceil((((id) + 0.5) - (fo)) * (sf) - 0.5))

/*
 * Reverse map a srctarget coordinate into device space and refine the
 * answer.  More specifically, what we are looking for is the smallest
 * destination coordinate that maps to a source coordinate that is
 * greater than or equal to the given target source coordinate.
 *
 * Note that since the inner loops use math that maps a destination
 * coordinate into source space and that, even though the equation
 * we use below is the theoretical inverse of the dst->src mapping,
 * we cannot rely on floating point math to guarantee that applying
 * both of these equations in sequence will give us an exact mapping
 * of src->dst->src.  Thus, we must search back and forth to see if
 * we really map back to the given source coordinate and that we are
 * the smallest destination coordinate that does so.
 *
 * Note that, in practice, the answer from the initial guess tends to
 * be the right answer most of the time and the loop ends up finding
 * one iteration to be ">= srctarget" and the next to be "< srctarget"
 * and thus finds the answer in 2 iterations.  A small number of
 * times, the initial guess is 1 too low and so we do one iteration
 * at "< srctarget" and the next at ">= srctarget" and again find the
 * answer in 2 iterations.  All cases encountered during testing ended
 * up falling into one of those 2 categories and so the loop was always
 * executed exactly twice.
 *
 * Note also that the calculation of srcloc below may attempt to calculate
 * the src location of the destination pixel which is "1 beyond" the
 * end of the source image.  Since our shift calculation code in the
 * main function only guaranteed that "srcw << shift" did not overflow
 * a 32-bit signed integer, we cannot guarantee that "(srcw+1) << shift"
 * or, more generally, "(srcw << shift)+srcinc" does not overflow.
 * As a result, we perform our calculations here with jlong values
 * so that we aren't affected by this overflow.  Since srcw (shifted)
 * and srcinc are both 32-bit values, their sum cannot possibly overflow
 * a jlong.  In fact, we can step up to a couple of billion steps of
 * size "srcinc" past the end of the image before we have to worry
 * about overflow - in practice, though, the search never steps more
 * than 1 past the end of the image so this buffer is more than enough.
 */
static jint
refine(jint intorigin, jdouble dblorigin, jint tilesize,
       jdouble scale, jint srctarget, jint srcinc)
{
    /* Make a first estimate of dest coordinate from srctarget */
    jint dstloc = (jint) ceil(dblorigin + srctarget / scale - 0.5);
    /* Loop until we get at least one value < and one >= the target */
    jboolean wasneg = JNI_FALSE;
    jboolean waspos = JNI_FALSE;
    jlong lsrcinc = srcinc;
    jlong lsrctarget = srctarget;

    while (JNI_TRUE) {
        /*
         * Find src coordinate from dest coordinate using the same
         * math we will use below when iterating over tiles.
         */
        jint tilestart = TILESTART(dstloc, intorigin, tilesize);
        jlong lsrcloc = (jlong) SRCLOC(tilestart, dblorigin, scale);
        if (dstloc > tilestart) {
            lsrcloc += lsrcinc * ((jlong) dstloc - tilestart);
        }
        if (lsrcloc >= lsrctarget) {
            /*
             * If we were previously less than target, then the current
             * dstloc is the smallest dst which maps >= the target.
             */
            if (wasneg) break;
            dstloc--;
            waspos = JNI_TRUE;
        } else {
            /*
             * If we were previously greater than target, then this must
             * be the first dstloc which maps to < the target.  Since we
             * want the smallest which maps >= the target, increment it
             * first before returning.
             */
            dstloc++;
            if (waspos) break;
            wasneg = JNI_TRUE;
        }
    }
    return dstloc;
}

/*
 * Class:     sun_java2d_loops_ScaledBlit
 * Method:    Scale
 * Signature: (Lsun/java2d/SurfaceData;Lsun/java2d/SurfaceData;Ljava/awt/Composite;Lsun/java2d/pipe/Region;IIIIDDDD)V
 */
JNIEXPORT void JNICALL
Java_sun_java2d_loops_ScaledBlit_Scale
    (JNIEnv *env, jobject self,
     jobject srcData, jobject dstData,
     jobject comp, jobject clip,
     jint sx1, jint sy1, jint sx2, jint sy2,
     jdouble ddx1, jdouble ddy1, jdouble ddx2, jdouble ddy2)
{
    SurfaceDataOps *srcOps;
    SurfaceDataOps *dstOps;
    SurfaceDataRasInfo srcInfo;
    SurfaceDataRasInfo dstInfo;
    NativePrimitive *pPrim;
    CompositeInfo compInfo;
    jint sxinc, syinc, shift;
    jint tilesize;
    jint idx1, idy1;
    jdouble scalex, scaley;
    RegionData clipInfo;
    jint dstFlags;
    jboolean xunderflow, yunderflow;

    pPrim = GetNativePrim(env, self);
    if (pPrim == NULL) {
        return;
    }
    if (pPrim->pCompType->getCompInfo != NULL) {
        (*pPrim->pCompType->getCompInfo)(env, &compInfo, comp);
    }
    if (Region_GetInfo(env, clip, &clipInfo)) {
        return;
    }

    srcOps = SurfaceData_GetOps(env, srcData);
    if (srcOps == 0) {
        return;
    }
    dstOps = SurfaceData_GetOps(env, dstData);
    if (dstOps == 0) {
        return;
    }

    /*
     * Determine the precision to use for the fixed point math
     * for the coordinate scaling.
     * - OR together srcw and srch to get the MSB between the two
     * - Next shift it up until it goes negative
     * - Count the shifts and that will be the most accurate
     *   precision available for the fixed point math
     * - a source coordinate of 1.0 will be (1 << shift)
     * - srcw & srch will be (srcw << shift) and (srch << shift)
     *   and will not overflow
     * Note that if srcw or srch are so large that they are
     * negative numbers before shifting, then:
     * - shift will be 0
     * - tilesize will end up being 1x1 tiles
     * - we will brute force calculate the source location
     *   of every destination pixel using the TILESTART and
     *   SRCLOC macros in this function and then call the
     *   scale helper function to copy one pixel at a time.
     * - TILESTART involves mostly jdouble calculations so
     *   it should not have integer overflow problems.
     */
    sxinc = (sx2 - sx1) | (sy2 - sy1);
    shift = 0;
    if (sxinc > 0) {
        while ((sxinc <<= 1) > 0) {
            shift++;
        }
    }
    /*
     * Now determine the scaled integer increments used to traverse
     * the source image for each destination pixel.  Our shift value
     * has been calculated above so that any location within the
     * destination image can be represented as a scaled integer
     * without incurring integer overflow.
     *
     * But we also need to worry about overflow of the sxinc and syinc
     * parameters.  We already know that "srcw<<shift" and "srch<<shift"
     * cannot overflow a jint, and the only time that sxinc and syinc
     * can be larger than those two values is if ddy2-ddy1 or ddx2-ddx1
     * are smaller than 1.  Since this situation implies that the
     * output area is no more than one pixel wide or tall, then we are
     * stepping by distances that are at least the size of the image
     * and only one destination pixel will ever be rendered - thus the
     * amount by which we step is largely irrelevant since after
     * drawing the first "in bounds" pixel, we will step completely
     * out of the source image and render nothing more.  As a result,
     * we assign the appropriate "size of image" stepping parameter
     * for any scale to smaller than one device pixel.
     */
    yunderflow = (ddy2 - ddy1) < 1.0;
    scaley = (((jdouble) (sy2 - sy1)) / (ddy2 - ddy1)) * (1 << shift);
    syinc = (yunderflow ? ((sy2 - sy1) << shift) : (jint) scaley);
    xunderflow = (ddx2 - ddx1) < 1.0;
    scalex = (((jdouble) (sx2 - sx1)) / (ddx2 - ddx1)) * (1 << shift);
    sxinc = (xunderflow ? ((sx2 - sx1) << shift) : (jint) scalex);
    tilesize = findpow2tilesize(shift, sxinc, syinc);


    srcInfo.bounds.x1 = sx1;
    srcInfo.bounds.y1 = sy1;
    srcInfo.bounds.x2 = sx2;
    srcInfo.bounds.y2 = sy2;
    if (srcOps->Lock(env, srcOps, &srcInfo, pPrim->srcflags) != SD_SUCCESS) {
        return;
    }
    if (srcInfo.bounds.x2 <= srcInfo.bounds.x1 ||
        srcInfo.bounds.y2 <= srcInfo.bounds.y1)
    {
        SurfaceData_InvokeUnlock(env, srcOps, &srcInfo);
        return;
    }

    /*
     * Only refine lower bounds if lower source coordinate was clipped
     * because the math will work out to be exactly idx1, idy1 if not.
     * Always refine upper bounds since we want to make sure not to
     * overstep the source bounds based on the tiled iteration math.
     *
     * For underflow cases, simply check if the SRCLOC for the single
     * destination pixel maps inside the source bounds.  If it does,
     * we render that pixel row or column (and only that pixel row
     * or column).  If it does not, we render nothing.
     */
    idx1 = (jint) ceil(ddx1 - 0.5);
    idy1 = (jint) ceil(ddy1 - 0.5);
    if (xunderflow) {
        jdouble x = sx1 + (SRCLOC(idx1, ddx1, scalex) / (1 << shift));
        dstInfo.bounds.x1 = dstInfo.bounds.x2 = idx1;
        if (x >= srcInfo.bounds.x1 && x < srcInfo.bounds.x2) {
            dstInfo.bounds.x2++;
        }
    } else {
        dstInfo.bounds.x1 = ((srcInfo.bounds.x1 <= sx1)
                             ? idx1
                             : refine(idx1, ddx1, tilesize, scalex,
                                      (srcInfo.bounds.x1-sx1) << shift, sxinc));
        dstInfo.bounds.x2 = refine(idx1, ddx1, tilesize, scalex,
                                   (srcInfo.bounds.x2-sx1) << shift, sxinc);
    }
    if (yunderflow) {
        jdouble y = sy1 + (SRCLOC(idy1, ddy1, scaley) / (1 << shift));
        dstInfo.bounds.y1 = dstInfo.bounds.y2 = idy1;
        if (y >= srcInfo.bounds.y1 && y < srcInfo.bounds.y2) {
            dstInfo.bounds.y2++;
        }
    } else {
        dstInfo.bounds.y1 = ((srcInfo.bounds.y1 <= sy1)
                             ? idy1
                             : refine(idy1, ddy1, tilesize, scaley,
                                      (srcInfo.bounds.y1-sy1) << shift, syinc));
        dstInfo.bounds.y2 = refine(idy1, ddy1, tilesize, scaley,
                                   (srcInfo.bounds.y2-sy1) << shift, syinc);
    }

    SurfaceData_IntersectBounds(&dstInfo.bounds, &clipInfo.bounds);
    dstFlags = pPrim->dstflags;
    if (!Region_IsRectangular(&clipInfo)) {
        dstFlags |= SD_LOCK_PARTIAL_WRITE;
    }
    if (dstOps->Lock(env, dstOps, &dstInfo, dstFlags) != SD_SUCCESS) {
        SurfaceData_InvokeUnlock(env, srcOps, &srcInfo);
        return;
    }

    if (dstInfo.bounds.x2 > dstInfo.bounds.x1 &&
        dstInfo.bounds.y2 > dstInfo.bounds.y1)
    {
        srcOps->GetRasInfo(env, srcOps, &srcInfo);
        dstOps->GetRasInfo(env, dstOps, &dstInfo);
        if (srcInfo.rasBase && dstInfo.rasBase) {
            SurfaceDataBounds span;
            void *pSrc = PtrCoord(srcInfo.rasBase,
                                  sx1, srcInfo.pixelStride,
                                  sy1, srcInfo.scanStride);

            Region_IntersectBounds(&clipInfo, &dstInfo.bounds);
            Region_StartIteration(env, &clipInfo);
            if (tilesize >= (ddx2 - ddx1) &&
                tilesize >= (ddy2 - ddy1))
            {
                /* Do everything in one tile */
                jint sxloc = (jint) SRCLOC(idx1, ddx1, scalex);
                jint syloc = (jint) SRCLOC(idy1, ddy1, scaley);
                while (Region_NextIteration(&clipInfo, &span)) {
                    jint tsxloc = sxloc;
                    jint tsyloc = syloc;
                    void *pDst;

                    if (span.y1 > idy1) {
                        tsyloc += syinc * (span.y1 - idy1);
                    }
                    if (span.x1 > idx1) {
                        tsxloc += sxinc * (span.x1 - idx1);
                    }

                    pDst = PtrCoord(dstInfo.rasBase,
                                    span.x1, dstInfo.pixelStride,
                                    span.y1, dstInfo.scanStride);
                    (*pPrim->funcs.scaledblit)(pSrc, pDst,
                                               span.x2-span.x1, span.y2-span.y1,
                                               tsxloc, tsyloc,
                                               sxinc, syinc, shift,
                                               &srcInfo, &dstInfo,
                                               pPrim, &compInfo);
                }
            } else {
                /* Break each clip span into tiles for better accuracy. */
                while (Region_NextIteration(&clipInfo, &span)) {
                    jint tilex, tiley;
                    jint sxloc, syloc;
                    jint x1, y1, x2, y2;
                    void *pDst;

                    for (tiley = TILESTART(span.y1, idy1, tilesize);
                         tiley < span.y2;
                         tiley += tilesize)
                    {
                        /* Clip span to Y range of current tile */
                        y1 = tiley;
                        y2 = tiley + tilesize;
                        if (y1 < span.y1) y1 = span.y1;
                        if (y2 > span.y2) y2 = span.y2;

                        /* Find scaled source coordinate of first pixel */
                        syloc = (jint) SRCLOC(tiley, ddy1, scaley);
                        if (y1 > tiley) {
                            syloc += syinc * (y1 - tiley);
                        }

                        for (tilex = TILESTART(span.x1, idx1, tilesize);
                             tilex < span.x2;
                             tilex += tilesize)
                        {
                            /* Clip span to X range of current tile */
                            x1 = tilex;
                            x2 = tilex + tilesize;
                            if (x1 < span.x1) x1 = span.x1;
                            if (x2 > span.x2) x2 = span.x2;

                            /* Find scaled source coordinate of first pixel */
                            sxloc = (jint) SRCLOC(tilex, ddx1, scalex);
                            if (x1 > tilex) {
                                sxloc += sxinc * (x1 - tilex);
                            }

                            pDst = PtrCoord(dstInfo.rasBase,
                                            x1, dstInfo.pixelStride,
                                            y1, dstInfo.scanStride);
                            (*pPrim->funcs.scaledblit)(pSrc, pDst, x2-x1, y2-y1,
                                                       sxloc, syloc,
                                                       sxinc, syinc, shift,
                                                       &srcInfo, &dstInfo,
                                                       pPrim, &compInfo);
                        }
                    }
                }
            }
            Region_EndIteration(env, &clipInfo);
        }
        SurfaceData_InvokeRelease(env, dstOps, &dstInfo);
        SurfaceData_InvokeRelease(env, srcOps, &srcInfo);
    }
    SurfaceData_InvokeUnlock(env, dstOps, &dstInfo);
    SurfaceData_InvokeUnlock(env, srcOps, &srcInfo);
}