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