1 /* Copyright (C) 2001-2019 Artifex Software, Inc. 2 All Rights Reserved. 3 4 This software is provided AS-IS with no warranty, either express or 5 implied. 6 7 This software is distributed under license and may not be copied, 8 modified or distributed except as expressly authorized under the terms 9 of the license contained in the file LICENSE in this distribution. 10 11 Refer to licensing information at http://www.artifex.com or contact 12 Artifex Software, Inc., 1305 Grant Avenue - Suite 200, Novato, 13 CA 94945, U.S.A., +1(415)492-9861, for further information. 14 */ 15 16 17 /* Fixed-point arithmetic for Ghostscript */ 18 19 #ifndef gxfixed_INCLUDED 20 # define gxfixed_INCLUDED 21 22 #include "std.h" 23 24 /* 25 * Coordinates are generally represented internally by fixed-point 26 * quantities: integers lose accuracy in crucial places, 27 * and floating point arithmetic is slow. 28 */ 29 #if ARCH_SIZEOF_INT == 4 30 typedef int fixed; 31 typedef uint ufixed; /* only used in a very few places */ 32 # define ARCH_SIZEOF_FIXED ARCH_SIZEOF_INT 33 # define max_fixed max_int 34 # define min_fixed min_int 35 #else 36 # if ARCH_SIZEOF_LONG == 4 37 typedef long fixed; 38 typedef ulong ufixed; /* only used in a very few places */ 39 # define ARCH_SIZEOF_FIXED ARCH_SIZEOF_LONG 40 # define max_fixed max_long 41 # define min_fixed min_long 42 # endif 43 #endif 44 45 #define fixed_0 0L 46 #define fixed_epsilon 1L 47 /* 48 * 8 bits of fraction provides both the necessary accuracy and 49 * a sufficiently large range of coordinates. 50 */ 51 #define _fixed_shift 8 52 #define fixed_fraction_bits _fixed_shift 53 #define fixed_int_bits (sizeof(fixed) * 8 - _fixed_shift) 54 #define fixed_scale (1<<_fixed_shift) 55 #define _fixed_rshift(x) arith_rshift(x,_fixed_shift) 56 #define _fixed_round_v (fixed_scale>>1) 57 #define _fixed_fraction_v (fixed_scale-1) 58 /* 59 * We use a center-of-pixel filling rule; Adobe specifies that coordinates 60 * designate half-open regions. Because of this, we need special rounding 61 * to go from a coordinate to the pixel it falls in. We use the term 62 * "pixel rounding" for this kind of rounding. 63 */ 64 #define _fixed_pixround_v (_fixed_round_v - fixed_epsilon) 65 66 /* 67 * Most operations can be done directly on fixed-point quantities: 68 * addition, subtraction, shifting, multiplication or division by 69 * (integer) constants; assignment, assignment with zero; 70 * comparison, comparison against zero. 71 * Multiplication and division by floats is OK if the result is 72 * explicitly cast back to fixed. 73 * Conversion to and from int and float types must be done explicitly. 74 * Note that if we are casting a fixed to a float in a context where 75 * only ratios and not actual values are involved, we don't need to take 76 * the scale factor into account: we can simply cast to float directly. 77 */ 78 #define int2fixed(i) ((fixed)(i)<<_fixed_shift) 79 /* Define some useful constants. */ 80 /* Avoid casts, so strict ANSI compilers will accept them in #ifs. */ 81 #define fixed_1 (fixed_epsilon << _fixed_shift) 82 #define fixed_half (fixed_1 >> 1) 83 /* 84 * On 16-bit systems, we can convert fixed variables to ints more efficiently 85 * than general fixed quantities. For this reason, we define two separate 86 * sets of conversion macros. 87 */ 88 #define fixed2int(x) ((int)_fixed_rshift(x)) 89 #define fixed2int_rounded(x) ((int)_fixed_rshift((x)+_fixed_round_v)) 90 #define fixed2int_ceiling(x) ((int)_fixed_rshift((x)+_fixed_fraction_v)) 91 #define fixed_pre_pixround(x) ((x)+_fixed_pixround_v) 92 #define fixed2int_pixround(x) fixed2int(fixed_pre_pixround(x)) 93 #define fixed2int_pixround_perfect(x) ((x) < 0 && ((x) & (fixed_1 - fixed_epsilon)) == fixed_half \ 94 ? (int)_fixed_rshift(x) + 1 : fixed2int_pixround(x)) 95 #define fixed_is_int(x) !((x)&_fixed_fraction_v) 96 #if ARCH_INTS_ARE_SHORT & !ARCH_IS_BIG_ENDIAN 97 /* Do some of the shifting and extraction ourselves. */ 98 # define _fixed_hi(x) *((const uint *)&(x)+1) 99 # define _fixed_lo(x) *((const uint *)&(x)) 100 # define fixed2int_var(x)\ 101 ((int)((_fixed_hi(x) << (16-_fixed_shift)) +\ 102 (_fixed_lo(x) >> _fixed_shift))) 103 # define fixed2int_var_rounded(x)\ 104 ((int)((_fixed_hi(x) << (16-_fixed_shift)) +\ 105 (((_fixed_lo(x) >> (_fixed_shift-1))+1)>>1))) 106 # define fixed2int_var_ceiling(x)\ 107 (fixed2int_var(x) -\ 108 arith_rshift((int)-(_fixed_lo(x) & _fixed_fraction_v), _fixed_shift)) 109 #else 110 /* Use reasonable definitions. */ 111 # define fixed2int_var(x) fixed2int(x) 112 # define fixed2int_var_rounded(x) fixed2int_rounded(x) 113 # define fixed2int_var_ceiling(x) fixed2int_ceiling(x) 114 #endif 115 #define fixed2int_var_pixround(x) fixed2int_pixround(x) 116 #define fixed2long(x) ((long)_fixed_rshift(x)) 117 #define fixed2long_rounded(x) ((long)_fixed_rshift((x)+_fixed_round_v)) 118 #define fixed2long_ceiling(x) ((long)_fixed_rshift((x)+_fixed_fraction_v)) 119 #define fixed2long_pixround(x) ((long)_fixed_rshift((x)+_fixed_pixround_v)) 120 #define float2fixed(f) ((fixed)((f)*(float)fixed_scale)) 121 #define float2fixed_rounded(f) ((fixed)floor((f)*(float)fixed_scale + 0.5)) 122 123 /* Note that fixed2float actually produces a double result. */ 124 #define fixed2float(x) ((x)*(1.0/fixed_scale)) 125 126 /* Rounding and truncation on fixeds */ 127 #define fixed_floor(x) ((x)&(-1L<<_fixed_shift)) 128 #define fixed_rounded(x) (((x)+_fixed_round_v)&(-1L<<_fixed_shift)) 129 #define fixed_ceiling(x) (((x)+_fixed_fraction_v)&(-1L<<_fixed_shift)) 130 #define fixed_pixround(x) (((x)+_fixed_pixround_v)&(-1L<<_fixed_shift)) 131 #define fixed_fraction(x) ((int)(x)&_fixed_fraction_v) 132 /* I don't see how to do truncation towards 0 so easily.... */ 133 #define fixed_truncated(x) ((x) < 0 ? fixed_ceiling(x) : fixed_floor(x)) 134 135 /* Define the largest and smallest integer values that fit in a fixed. */ 136 #define max_int_in_fixed fixed2int(max_fixed) 137 #define min_int_in_fixed fixed2int(min_fixed) 138 139 /* 140 * Define a macro for checking for overflow of the sum of two fixed values 141 * and and setting the result to the sum if no overflow. 142 * This is a pseudo-function that returns a "limitcheck" if the result 143 * will overflow. Set the result to the max/min _fixed value (depending 144 * on the sign of the operands (note: overflow can only occur with like 145 * signed input values). While the result is only set once, the operand 146 * values are used multiply, so pointer modification operand use will 147 * result in MANY more increments/decrements of the pointer than desired. 148 */ 149 /* usage: (int)code = CHECK_SET_FIXED_SUM(fixed_result, fixed_op1, fixed_op2); */ 150 #define CHECK_SET_FIXED_SUM(r, a, b) \ 151 ((((a) ^ (b)) >= 0) && ((((a)+(b)) ^ (a)) < 0) ? \ 152 (((r)=(((a)<0) ? min_fixed : max_fixed)), gs_error_limitcheck) : \ 153 (((r) = ((a)+(b))), 0)) /* no overflow */ 154 /* 155 * Define a procedure for computing a * b / c when b and c are non-negative, 156 * b < c, and a * b exceeds (or might exceed) the capacity of a long. 157 * Note that this procedure takes the floor, rather than truncating 158 * towards zero, if a < 0: this ensures 0 <= R < c, where R is the remainder. 159 * 160 * It's really annoying that C doesn't provide any way to get at 161 * the double-length multiply/divide instructions that almost all hardware 162 * provides.... 163 */ 164 fixed fixed_mult_quo(fixed A, fixed B, fixed C); 165 166 /* 167 * Transforming coordinates involves multiplying two floats, or a float 168 * and a double, and then converting the result to a fixed. Since this 169 * operation is so common, we provide an alternative implementation of it 170 * on machines that use IEEE floating point representation but don't have 171 * floating point hardware. The implementation may be in either C or 172 * assembler. 173 */ 174 175 /* 176 * Define a function for finding intersection of small bars. 177 * Coordinates must be so small that their cubes fit into 60 bits. 178 * This function doesn't check intersections at end of bars, 179 * so the caller must care of them on necessity. 180 * Returns : *ry is the Y-coordinate of the intersection 181 * truncated to 'fixed'; *ey is 1 iff the precise Y coordinate of 182 * the intersection is greater than *ry (used by the shading algorithm). 183 */ 184 bool 185 gx_intersect_small_bars(fixed q0x, fixed q0y, fixed q1x, fixed q1y, fixed q2x, fixed q2y, 186 fixed q3x, fixed q3y, fixed *ry, fixed *ey); 187 188 /* 189 * The macros all use R for the (fixed) result, FB for the second (float) 190 * operand, and dtemp for a temporary double variable. The work is divided 191 * between the two macros of each set in order to avoid bogus "possibly 192 * uninitialized variable" messages from slow-witted compilers. 193 * 194 * For the case where the first operand is a float (FA): 195 * code = CHECK_FMUL2FIXED_VARS(R, FA, FB, dtemp); 196 * if (code < 0) ... 197 * FINISH_FMUL2FIXED_VARS(R, dtemp); 198 * 199 * For the case where the first operand is a double (DA): 200 * code = CHECK_DFMUL2FIXED_VARS(R, DA, FB, dtemp); 201 * if (code < 0) ...; 202 * FINISH_DFMUL2FIXED_VARS(R, dtemp); 203 */ 204 205 #define CHECK_FMUL2FIXED_VARS(vr, vfa, vfb, dtemp)\ 206 (dtemp = (vfa) * (vfb),\ 207 (f_fits_in_bits(dtemp, fixed_int_bits) ? 0 :\ 208 gs_note_error(gs_error_limitcheck))) 209 #define FINISH_FMUL2FIXED_VARS(vr, dtemp)\ 210 vr = float2fixed(dtemp) 211 #define CHECK_DFMUL2FIXED_VARS(vr, vda, vfb, dtemp)\ 212 CHECK_FMUL2FIXED_VARS(vr, vda, vfb, dtemp) 213 #define FINISH_DFMUL2FIXED_VARS(vr, dtemp)\ 214 FINISH_FMUL2FIXED_VARS(vr, dtemp) 215 216 /* 217 * set_float2fixed_vars(R, F) does the equivalent of R = float2fixed(F): 218 * R is a fixed, F is a float or a double. 219 * set_fixed2float_var(R, V) does the equivalent of R = fixed2float(V): 220 * R is a float or a double, V is a fixed. 221 * set_ldexp_fixed2double(R, V, E) does the equivalent of R=ldexp((double)V,E): 222 * R is a double, V is a fixed, E is an int. 223 * R and F must be variables, not expressions; V and E may be expressions. 224 */ 225 226 # define set_float2fixed_vars(vr,vf)\ 227 (f_fits_in_bits(vf, fixed_int_bits) ? (vr = float2fixed(vf), 0) :\ 228 gs_note_error(gs_error_limitcheck)) 229 # define set_fixed2float_var(vf,x)\ 230 (vf = fixed2float(x), 0) 231 # define set_ldexp_fixed2double(vd, x, exp)\ 232 discard(vd = ldexp((double)(x), exp)) 233 234 /* A point with fixed coordinates */ 235 typedef struct gs_fixed_point_s { 236 fixed x, y; 237 } gs_fixed_point; 238 239 /* A rectangle with fixed coordinates */ 240 typedef struct gs_fixed_rect_s { 241 gs_fixed_point p, q; 242 } gs_fixed_rect; 243 244 #endif /* gxfixed_INCLUDED */ 245