1 /* Copyright (C) 1989, 2000 artofcode LLC. All rights reserved. 2 3 This program is free software; you can redistribute it and/or modify it 4 under the terms of the GNU General Public License as published by the 5 Free Software Foundation; either version 2 of the License, or (at your 6 option) any later version. 7 8 This program is distributed in the hope that it will be useful, but 9 WITHOUT ANY WARRANTY; without even the implied warranty of 10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 11 General Public License for more details. 12 13 You should have received a copy of the GNU General Public License along 14 with this program; if not, write to the Free Software Foundation, Inc., 15 59 Temple Place, Suite 330, Boston, MA, 02111-1307. 16 17 */ 18 19 /*$Id: gxfixed.h,v 1.3.4.1.2.1 2003/01/17 00:49:03 giles Exp $ */ 20 /* Fixed-point arithmetic for Ghostscript */ 21 22 #ifndef gxfixed_INCLUDED 23 # define gxfixed_INCLUDED 24 25 /* 26 * Coordinates are generally represented internally by fixed-point 27 * quantities: integers lose accuracy in crucial places, 28 * and floating point arithmetic is slow. 29 */ 30 #if ARCH_SIZEOF_INT == 4 31 typedef int fixed; 32 typedef uint ufixed; /* only used in a very few places */ 33 # define ARCH_SIZEOF_FIXED ARCH_SIZEOF_INT 34 # define max_fixed max_int 35 # define min_fixed min_int 36 #else 37 # if ARCH_SIZEOF_LONG == 4 38 typedef long fixed; 39 typedef ulong ufixed; /* only used in a very few places */ 40 # define ARCH_SIZEOF_FIXED ARCH_SIZEOF_LONG 41 # define max_fixed max_long 42 # define min_fixed min_long 43 # endif 44 #endif 45 46 #define fixed_0 0L 47 #define fixed_epsilon 1L 48 /* 49 * 12 bits of fraction provides both the necessary accuracy and 50 * a sufficiently large range of coordinates. 51 */ 52 #define _fixed_shift 12 53 #define fixed_fraction_bits _fixed_shift 54 #define fixed_int_bits (sizeof(fixed) * 8 - _fixed_shift) 55 #define fixed_scale (1<<_fixed_shift) 56 #define _fixed_rshift(x) arith_rshift(x,_fixed_shift) 57 #define _fixed_round_v (fixed_scale>>1) 58 #define _fixed_fraction_v (fixed_scale-1) 59 /* 60 * We use a center-of-pixel filling rule; Adobe specifies that coordinates 61 * designate half-open regions. Because of this, we need special rounding 62 * to go from a coordinate to the pixel it falls in. We use the term 63 * "pixel rounding" for this kind of rounding. 64 */ 65 #define _fixed_pixround_v (_fixed_round_v - fixed_epsilon) 66 67 /* 68 * Most operations can be done directly on fixed-point quantities: 69 * addition, subtraction, shifting, multiplication or division by 70 * (integer) constants; assignment, assignment with zero; 71 * comparison, comparison against zero. 72 * Multiplication and division by floats is OK if the result is 73 * explicitly cast back to fixed. 74 * Conversion to and from int and float types must be done explicitly. 75 * Note that if we are casting a fixed to a float in a context where 76 * only ratios and not actual values are involved, we don't need to take 77 * the scale factor into account: we can simply cast to float directly. 78 */ 79 #define int2fixed(i) ((fixed)(i)<<_fixed_shift) 80 /* Define some useful constants. */ 81 /* Avoid casts, so strict ANSI compilers will accept them in #ifs. */ 82 #define fixed_1 (fixed_epsilon << _fixed_shift) 83 #define fixed_half (fixed_1 >> 1) 84 /* 85 * On 16-bit systems, we can convert fixed variables to ints more efficiently 86 * than general fixed quantities. For this reason, we define two separate 87 * sets of conversion macros. 88 */ 89 #define fixed2int(x) ((int)_fixed_rshift(x)) 90 #define fixed2int_rounded(x) ((int)_fixed_rshift((x)+_fixed_round_v)) 91 #define fixed2int_ceiling(x) ((int)_fixed_rshift((x)+_fixed_fraction_v)) 92 #define fixed_pre_pixround(x) ((x)+_fixed_pixround_v) 93 #define fixed2int_pixround(x) fixed2int(fixed_pre_pixround(x)) 94 #define fixed_is_int(x) !((x)&_fixed_fraction_v) 95 #if arch_ints_are_short & !arch_is_big_endian 96 /* Do some of the shifting and extraction ourselves. */ 97 # define _fixed_hi(x) *((const uint *)&(x)+1) 98 # define _fixed_lo(x) *((const uint *)&(x)) 99 # define fixed2int_var(x)\ 100 ((int)((_fixed_hi(x) << (16-_fixed_shift)) +\ 101 (_fixed_lo(x) >> _fixed_shift))) 102 # define fixed2int_var_rounded(x)\ 103 ((int)((_fixed_hi(x) << (16-_fixed_shift)) +\ 104 (((_fixed_lo(x) >> (_fixed_shift-1))+1)>>1))) 105 # define fixed2int_var_ceiling(x)\ 106 (fixed2int_var(x) -\ 107 arith_rshift((int)-(_fixed_lo(x) & _fixed_fraction_v), _fixed_shift)) 108 #else 109 /* Use reasonable definitions. */ 110 # define fixed2int_var(x) fixed2int(x) 111 # define fixed2int_var_rounded(x) fixed2int_rounded(x) 112 # define fixed2int_var_ceiling(x) fixed2int_ceiling(x) 113 #endif 114 #define fixed2int_var_pixround(x) fixed2int_pixround(x) 115 #define fixed2long(x) ((long)_fixed_rshift(x)) 116 #define fixed2long_rounded(x) ((long)_fixed_rshift((x)+_fixed_round_v)) 117 #define fixed2long_ceiling(x) ((long)_fixed_rshift((x)+_fixed_fraction_v)) 118 #define fixed2long_pixround(x) ((long)_fixed_rshift((x)+_fixed_pixround_v)) 119 #define float2fixed(f) ((fixed)((f)*(float)fixed_scale)) 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 #ifdef USE_FPU 137 # define USE_FPU_FIXED (USE_FPU < 0 && arch_floats_are_IEEE && arch_sizeof_long == 4) 138 #else 139 # define USE_FPU_FIXED 0 140 #endif 141 142 /* 143 * Define a procedure for computing a * b / c when b and c are non-negative, 144 * b < c, and a * b exceeds (or might exceed) the capacity of a long. 145 * Note that this procedure takes the floor, rather than truncating 146 * towards zero, if a < 0: this ensures 0 <= R < c, where R is the remainder. 147 * 148 * It's really annoying that C doesn't provide any way to get at 149 * the double-length multiply/divide instructions that almost all hardware 150 * provides.... 151 */ 152 fixed fixed_mult_quo(P3(fixed A, fixed B, fixed C)); 153 154 /* 155 * Transforming coordinates involves multiplying two floats, or a float 156 * and a double, and then converting the result to a fixed. Since this 157 * operation is so common, we provide an alternative implementation of it 158 * on machines that use IEEE floating point representation but don't have 159 * floating point hardware. The implementation may be in either C or 160 * assembler. 161 */ 162 163 /* 164 * The macros all use R for the (fixed) result, FB for the second (float) 165 * operand, and dtemp for a temporary double variable. The work is divided 166 * between the two macros of each set in order to avoid bogus "possibly 167 * uninitialized variable" messages from slow-witted compilers. 168 * 169 * For the case where the first operand is a float (FA): 170 * code = CHECK_FMUL2FIXED_VARS(R, FA, FB, dtemp); 171 * if (code < 0) ... 172 * FINISH_FMUL2FIXED_VARS(R, dtemp); 173 * 174 * For the case where the first operand is a double (DA): 175 * code = CHECK_DFMUL2FIXED_VARS(R, DA, FB, dtemp); 176 * if (code < 0) ...; 177 * FINISH_DFMUL2FIXED_VARS(R, dtemp); 178 */ 179 #if USE_FPU_FIXED && arch_sizeof_short == 2 180 #define NEED_SET_FMUL2FIXED 181 int set_fmul2fixed_(P3(fixed *, long, long)); 182 #define CHECK_FMUL2FIXED_VARS(vr, vfa, vfb, dtemp)\ 183 set_fmul2fixed_(&vr, *(const long *)&vfa, *(const long *)&vfb) 184 #define FINISH_FMUL2FIXED_VARS(vr, dtemp)\ 185 DO_NOTHING 186 int set_dfmul2fixed_(P4(fixed *, ulong, long, long)); 187 # if arch_is_big_endian 188 # define CHECK_DFMUL2FIXED_VARS(vr, vda, vfb, dtemp)\ 189 set_dfmul2fixed_(&vr, ((const ulong *)&vda)[1], *(const long *)&vfb, *(const long *)&vda) 190 # else 191 # define CHECK_DFMUL2FIXED_VARS(vr, vda, vfb, dtemp)\ 192 set_dfmul2fixed_(&vr, *(const ulong *)&vda, *(const long *)&vfb, ((const long *)&vda)[1]) 193 # endif 194 #define FINISH_DFMUL2FIXED_VARS(vr, dtemp)\ 195 DO_NOTHING 196 197 #else /* don't bother */ 198 199 #undef NEED_SET_FMUL2FIXED 200 #define CHECK_FMUL2FIXED_VARS(vr, vfa, vfb, dtemp)\ 201 (dtemp = (vfa) * (vfb),\ 202 (f_fits_in_bits(dtemp, fixed_int_bits) ? 0 :\ 203 gs_note_error(gs_error_limitcheck))) 204 #define FINISH_FMUL2FIXED_VARS(vr, dtemp)\ 205 vr = float2fixed(dtemp) 206 #define CHECK_DFMUL2FIXED_VARS(vr, vda, vfb, dtemp)\ 207 CHECK_FMUL2FIXED_VARS(vr, vda, vfb, dtemp) 208 #define FINISH_DFMUL2FIXED_VARS(vr, dtemp)\ 209 FINISH_FMUL2FIXED_VARS(vr, dtemp) 210 211 #endif 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 #if USE_FPU_FIXED 223 int set_float2fixed_(P3(fixed *, long, int)); 224 int set_double2fixed_(P4(fixed *, ulong, long, int)); 225 226 # define set_float2fixed_vars(vr,vf)\ 227 (sizeof(vf) == sizeof(float) ?\ 228 set_float2fixed_(&vr, *(const long *)&vf, fixed_fraction_bits) :\ 229 set_double2fixed_(&vr, ((const ulong *)&vf)[arch_is_big_endian],\ 230 ((const long *)&vf)[1 - arch_is_big_endian],\ 231 fixed_fraction_bits)) 232 long fixed2float_(P2(fixed, int)); 233 void set_fixed2double_(P3(double *, fixed, int)); 234 235 /* 236 * We need the (double *)&vf cast to prevent compile-time error messages, 237 * even though the call will only be executed if vf has the correct type. 238 */ 239 # define set_fixed2float_var(vf,x)\ 240 (sizeof(vf) == sizeof(float) ?\ 241 (*(long *)&vf = fixed2float_(x, fixed_fraction_bits), 0) :\ 242 (set_fixed2double_((double *)&vf, x, fixed_fraction_bits), 0)) 243 #define set_ldexp_fixed2double(vd, x, exp)\ 244 set_fixed2double_(&vd, x, -(exp)) 245 #else 246 # define set_float2fixed_vars(vr,vf)\ 247 (f_fits_in_bits(vf, fixed_int_bits) ? (vr = float2fixed(vf), 0) :\ 248 gs_note_error(gs_error_limitcheck)) 249 # define set_fixed2float_var(vf,x)\ 250 (vf = fixed2float(x), 0) 251 # define set_ldexp_fixed2double(vd, x, exp)\ 252 discard(vd = ldexp((double)(x), exp)) 253 #endif 254 255 /* A point with fixed coordinates */ 256 typedef struct gs_fixed_point_s { 257 fixed x, y; 258 } gs_fixed_point; 259 260 /* A rectangle with fixed coordinates */ 261 typedef struct gs_fixed_rect_s { 262 gs_fixed_point p, q; 263 } gs_fixed_rect; 264 265 #endif /* gxfixed_INCLUDED */ 266