2362N/A * Copyright (c) 2001, 2005, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 2362N/A * published by the Free Software Foundation. Oracle designates this 0N/A * particular file as subject to the "Classpath" exception as provided 2362N/A * by Oracle in the LICENSE file that accompanied this code. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 0N/A * The scaling loops used inside the helper functions are based on the 0N/A * following pseudocode for stepping through the source image: 0N/A * shift - number of bits of sub-pixel precision in scaled values 0N/A * srcxorig, srcyorig - scaled location of first pixel 0N/A * srcxinc, srcyinc - scaled x and y increments 0N/A * dstwidth, dstheight - number of pixels to process across and down 0N/A * 1. srcy = srcyorig; 0N/A * 2. for (dstheight) { 0N/A * 3. srcx = srcxorig; 0N/A * 4. for (dstwidth) { 0N/A * 5. fetch and process pixel for (srcx >> shift, srcy >> shift) 0N/A * 6. srcx += srcxinc; 0N/A * 8. srcy += srcyinc; 0N/A * Note that each execution of line 6 or 8 accumulates error of 0N/A * +/- 1 into the scaled coordinate variables. These lines are 0N/A * each executed once per pixel across or once per pixel down 0N/A * the region being iterated over, thus the error can accumulate 0N/A * up to a magnitude of dstwidth in the horizontal direction and 0N/A * dstheight in the vertical direction. 0N/A * If the error ever reaches a magnitude of (1 << shift) then we 0N/A * will be off by at least 1 source pixel in our mapping. 0N/A * Note that we increment the source coordinates by the srcxinc 0N/A * and srcyinc variables in each step. Thus, if our error ever 0N/A * accumulates to a magnitude equal to srcxinc or srcyinc then 0N/A * we will be ahead or behind of "where we should be" by at least 0N/A * one iteration. Since each iteration is a destination pixel, 0N/A * this means that our actual location will be off by at least 0N/A * one destination pixel. 0N/A * This means that all of the values: 0N/A * all represent a maximum bound on how much error we can accumulate 0N/A * before we are off by a source or a destination pixel. Thus, 0N/A * we should make sure that we never process more than that many 0N/A * pixels if we want to maintain single pixel accuracy. Even 0N/A * better would be to process many fewer pixels than those bounds 0N/A * to ensure that our accumulated error is much smaller than a 0N/A * Find and return the largest tile size that is a power of 2 and 0N/A * which is small enough to yield some reassuring degree of subpixel 0N/A * accuracy. The degree of subpixel accuracy that will be preserved 0N/A * by the tile size it chooses will vary and the details on how 0N/A * it makes this decision are detailed in the comments below. 0N/A * The initial value of shift is our first estimate for 0N/A * the power of 2 for our tilesize since it ensures 0N/A * less than 1 source pixel of error. 0N/A * Reducing it until (1 << shift) is not larger than the 0N/A * smallest of our increments ensures we will have no more 0N/A * than 1 destination pixel of error as well. 0N/A /* Degenerate case will cause infinite loop in next loop... */ 0N/A * shift is now the largest it can be for less than 1 pixel 0N/A * of error in either source or destination spaces. 0N/A * Now we will try for at least 8 bits of subpixel accuracy 0N/A * with a tile size of at least 256x256 and reduce our subpixel 0N/A * accuracy on a sliding scale down to a tilesize of 1x1 when 0N/A * we have no bits of sub-pixel accuracy. 0N/A /* Subtracting 8 asks for 8 bits of subpixel accuracy. */ 0N/A /* Ask for half of the remaining bits to be subpixel accuracy. */ 0N/A /* Rounding is in favor of subpixel accuracy over tile size. */ 0N/A /* Worst case, shift == 0 and tilesize == (1 << 0) == 1 */ 0N/A * For a given integer destination pixel coordinate "id", calculate the 0N/A * integer destination coordinate of the start of the "ts" sized tile 0N/A * in which it resides. 0N/A * Tiles all start at even multiples of the tile size from the integer 0N/A * destination origin "io". 0N/A * id == integer destination coordinate 0N/A * io == integer destination operation origin 0N/A * ts == tilesize (must be power of 2) 0N/A * For a given integer destination pixel coordinate "id", calculate the 0N/A * sub-pixel accurate source coordinate from which its sample comes. 0N/A * The returned source coordinate is expressed in a shifted fractional 0N/A * arithmetic number system. 0N/A * id == integer destination coordinate 0N/A * fo == floating point destination operation origin, 0N/A * sf == source coordinate scale factor per destination pixel 0N/A * (multiplied by fractional arithmetic "shift") 0N/A * The caller is required to cast this value to the appropriate 0N/A * integer type for the needed precision. The rendering code which 0N/A * deals only with valid coordinates within the bounds of the source 0N/A * rectangle uses jint. The setup code, which occasionally deals 0N/A * with coordinates that run out of bounds, uses jlong. 0N/A * Note that the rounding in this calculation is at a fraction of a 0N/A * source pixel of (1.0 / (1<<shift)) since the scale factor includes 0N/A * the fractional shift. As a result, the type of rounding used is 0N/A * not very significant (floor, floor(x+.5), or ceil(x-.5)), but the 0N/A * ceil(x-.5) version is used for consistency with the way that pixel 0N/A * coordinates are rounded to assign the ".5" value to the lower 0N/A * Reverse map a srctarget coordinate into device space and refine the 0N/A * answer. More specifically, what we are looking for is the smallest 0N/A * destination coordinate that maps to a source coordinate that is 0N/A * greater than or equal to the given target source coordinate. 0N/A * Note that since the inner loops use math that maps a destination 0N/A * coordinate into source space and that, even though the equation 0N/A * we use below is the theoretical inverse of the dst->src mapping, 0N/A * we cannot rely on floating point math to guarantee that applying 0N/A * both of these equations in sequence will give us an exact mapping 0N/A * of src->dst->src. Thus, we must search back and forth to see if 0N/A * we really map back to the given source coordinate and that we are 0N/A * the smallest destination coordinate that does so. 0N/A * Note that, in practice, the answer from the initial guess tends to 0N/A * be the right answer most of the time and the loop ends up finding 0N/A * one iteration to be ">= srctarget" and the next to be "< srctarget" 0N/A * and thus finds the answer in 2 iterations. A small number of 0N/A * times, the initial guess is 1 too low and so we do one iteration 0N/A * at "< srctarget" and the next at ">= srctarget" and again find the 0N/A * answer in 2 iterations. All cases encountered during testing ended 0N/A * up falling into one of those 2 categories and so the loop was always 0N/A * executed exactly twice. 0N/A * Note also that the calculation of srcloc below may attempt to calculate 0N/A * the src location of the destination pixel which is "1 beyond" the 0N/A * end of the source image. Since our shift calculation code in the 0N/A * main function only guaranteed that "srcw << shift" did not overflow 0N/A * a 32-bit signed integer, we cannot guarantee that "(srcw+1) << shift" 0N/A * or, more generally, "(srcw << shift)+srcinc" does not overflow. 0N/A * As a result, we perform our calculations here with jlong values 0N/A * so that we aren't affected by this overflow. Since srcw (shifted) 0N/A * and srcinc are both 32-bit values, their sum cannot possibly overflow 0N/A * a jlong. In fact, we can step up to a couple of billion steps of 0N/A * size "srcinc" past the end of the image before we have to worry 0N/A * about overflow - in practice, though, the search never steps more 0N/A * than 1 past the end of the image so this buffer is more than enough. 0N/A /* Make a first estimate of dest coordinate from srctarget */ 0N/A /* Loop until we get at least one value < and one >= the target */ 0N/A * Find src coordinate from dest coordinate using the same 0N/A * math we will use below when iterating over tiles. 0N/A * If we were previously less than target, then the current 0N/A * dstloc is the smallest dst which maps >= the target. 0N/A * If we were previously greater than target, then this must 0N/A * be the first dstloc which maps to < the target. Since we 0N/A * want the smallest which maps >= the target, increment it 0N/A * first before returning. 0N/A * Class: sun_java2d_loops_ScaledBlit 0N/A * Determine the precision to use for the fixed point math 0N/A * for the coordinate scaling. 0N/A * - OR together srcw and srch to get the MSB between the two 0N/A * - Next shift it up until it goes negative 0N/A * - Count the shifts and that will be the most accurate 0N/A * precision available for the fixed point math 0N/A * - a source coordinate of 1.0 will be (1 << shift) 0N/A * - srcw & srch will be (srcw << shift) and (srch << shift) 0N/A * and will not overflow 0N/A * Note that if srcw or srch are so large that they are 0N/A * negative numbers before shifting, then: 0N/A * - tilesize will end up being 1x1 tiles 0N/A * - we will brute force calculate the source location 0N/A * of every destination pixel using the TILESTART and 0N/A * SRCLOC macros in this function and then call the 0N/A * scale helper function to copy one pixel at a time. 0N/A * - TILESTART involves mostly jdouble calculations so 0N/A * it should not have integer overflow problems. 0N/A * Now determine the scaled integer increments used to traverse 0N/A * the source image for each destination pixel. Our shift value 0N/A * has been calculated above so that any location within the 0N/A * destination image can be represented as a scaled integer 0N/A * without incurring integer overflow. 0N/A * But we also need to worry about overflow of the sxinc and syinc 0N/A * parameters. We already know that "srcw<<shift" and "srch<<shift" 0N/A * cannot overflow a jint, and the only time that sxinc and syinc 0N/A * can be larger than those two values is if ddy2-ddy1 or ddx2-ddx1 0N/A * are smaller than 1. Since this situation implies that the 0N/A * output area is no more than one pixel wide or tall, then we are 0N/A * stepping by distances that are at least the size of the image 0N/A * and only one destination pixel will ever be rendered - thus the 0N/A * amount by which we step is largely irrelevant since after 0N/A * drawing the first "in bounds" pixel, we will step completely 0N/A * out of the source image and render nothing more. As a result, 0N/A * we assign the appropriate "size of image" stepping parameter 0N/A * for any scale to smaller than one device pixel. 0N/A * Only refine lower bounds if lower source coordinate was clipped 0N/A * because the math will work out to be exactly idx1, idy1 if not. 0N/A * Always refine upper bounds since we want to make sure not to 0N/A * overstep the source bounds based on the tiled iteration math. 0N/A * For underflow cases, simply check if the SRCLOC for the single 0N/A * destination pixel maps inside the source bounds. If it does, 0N/A * we render that pixel row or column (and only that pixel row 0N/A * or column). If it does not, we render nothing. 0N/A /* Do everything in one tile */ 0N/A /* Break each clip span into tiles for better accuracy. */ 0N/A /* Clip span to Y range of current tile */ 0N/A /* Find scaled source coordinate of first pixel */ 0N/A /* Clip span to X range of current tile */ 0N/A /* Find scaled source coordinate of first pixel */