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