Line data Source code
1 : /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
2 : /* Cairo - a vector graphics library with display and print output
3 : *
4 : * Copyright © 2007 Mozilla Corporation
5 : *
6 : * This library is free software; you can redistribute it and/or
7 : * modify it either under the terms of the GNU Lesser General Public
8 : * License version 2.1 as published by the Free Software Foundation
9 : * (the "LGPL") or, at your option, under the terms of the Mozilla
10 : * Public License Version 1.1 (the "MPL"). If you do not alter this
11 : * notice, a recipient may use your version of this file under either
12 : * the MPL or the LGPL.
13 : *
14 : * You should have received a copy of the LGPL along with this library
15 : * in the file COPYING-LGPL-2.1; if not, write to the Free Software
16 : * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
17 : * You should have received a copy of the MPL along with this library
18 : * in the file COPYING-MPL-1.1
19 : *
20 : * The contents of this file are subject to the Mozilla Public License
21 : * Version 1.1 (the "License"); you may not use this file except in
22 : * compliance with the License. You may obtain a copy of the License at
23 : * http://www.mozilla.org/MPL/
24 : *
25 : * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26 : * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27 : * the specific language governing rights and limitations.
28 : *
29 : * The Original Code is the cairo graphics library.
30 : *
31 : * The Initial Developer of the Original Code is Mozilla Foundation
32 : *
33 : * Contributor(s):
34 : * Vladimir Vukicevic <vladimir@pobox.com>
35 : */
36 :
37 : #ifndef CAIRO_FIXED_PRIVATE_H
38 : #define CAIRO_FIXED_PRIVATE_H
39 :
40 : #include "cairo-fixed-type-private.h"
41 :
42 : #include "cairo-wideint-private.h"
43 :
44 : /* Implementation */
45 :
46 : #if (CAIRO_FIXED_BITS != 32)
47 : # error CAIRO_FIXED_BITS must be 32, and the type must be a 32-bit type.
48 : # error To remove this limitation, you will have to fix the tesselator.
49 : #endif
50 :
51 : #define CAIRO_FIXED_ONE ((cairo_fixed_t)(1 << CAIRO_FIXED_FRAC_BITS))
52 : #define CAIRO_FIXED_ONE_DOUBLE ((double)(1 << CAIRO_FIXED_FRAC_BITS))
53 : #define CAIRO_FIXED_ONE_FLOAT ((float)(1 << CAIRO_FIXED_FRAC_BITS))
54 : #define CAIRO_FIXED_EPSILON ((cairo_fixed_t)(1))
55 :
56 : #define CAIRO_FIXED_FRAC_MASK ((cairo_fixed_t)(((cairo_fixed_unsigned_t)(-1)) >> (CAIRO_FIXED_BITS - CAIRO_FIXED_FRAC_BITS)))
57 : #define CAIRO_FIXED_WHOLE_MASK (~CAIRO_FIXED_FRAC_MASK)
58 :
59 : static inline cairo_fixed_t
60 0 : _cairo_fixed_from_int (int i)
61 : {
62 0 : return i << CAIRO_FIXED_FRAC_BITS;
63 : }
64 :
65 : /* This is the "magic number" approach to converting a double into fixed
66 : * point as described here:
67 : *
68 : * http://www.stereopsis.com/sree/fpu2006.html (an overview)
69 : * http://www.d6.com/users/checker/pdfs/gdmfp.pdf (in detail)
70 : *
71 : * The basic idea is to add a large enough number to the double that the
72 : * literal floating point is moved up to the extent that it forces the
73 : * double's value to be shifted down to the bottom of the mantissa (to make
74 : * room for the large number being added in). Since the mantissa is, at a
75 : * given moment in time, a fixed point integer itself, one can convert a
76 : * float to various fixed point representations by moving around the point
77 : * of a floating point number through arithmetic operations. This behavior
78 : * is reliable on most modern platforms as it is mandated by the IEEE-754
79 : * standard for floating point arithmetic.
80 : *
81 : * For our purposes, a "magic number" must be carefully selected that is
82 : * both large enough to produce the desired point-shifting effect, and also
83 : * has no lower bits in its representation that would interfere with our
84 : * value at the bottom of the mantissa. The magic number is calculated as
85 : * follows:
86 : *
87 : * (2 ^ (MANTISSA_SIZE - FRACTIONAL_SIZE)) * 1.5
88 : *
89 : * where in our case:
90 : * - MANTISSA_SIZE for 64-bit doubles is 52
91 : * - FRACTIONAL_SIZE for 16.16 fixed point is 16
92 : *
93 : * Although this approach provides a very large speedup of this function
94 : * on a wide-array of systems, it does come with two caveats:
95 : *
96 : * 1) It uses banker's rounding as opposed to arithmetic rounding.
97 : * 2) It doesn't function properly if the FPU is in single-precision
98 : * mode.
99 : */
100 :
101 : /* The 16.16 number must always be available */
102 : #define CAIRO_MAGIC_NUMBER_FIXED_16_16 (103079215104.0)
103 :
104 : #if CAIRO_FIXED_BITS <= 32
105 : #define CAIRO_MAGIC_NUMBER_FIXED ((1LL << (52 - CAIRO_FIXED_FRAC_BITS)) * 1.5)
106 :
107 : /* For 32-bit fixed point numbers */
108 : static inline cairo_fixed_t
109 528 : _cairo_fixed_from_double (double d)
110 : {
111 : union {
112 : double d;
113 : int32_t i[2];
114 : } u;
115 :
116 528 : u.d = d + CAIRO_MAGIC_NUMBER_FIXED;
117 : #ifdef FLOAT_WORDS_BIGENDIAN
118 : return u.i[1];
119 : #else
120 528 : return u.i[0];
121 : #endif
122 : }
123 :
124 : #else
125 : # error Please define a magic number for your fixed point type!
126 : # error See cairo-fixed-private.h for details.
127 : #endif
128 :
129 : static inline cairo_fixed_t
130 0 : _cairo_fixed_from_26_6 (uint32_t i)
131 : {
132 : #if CAIRO_FIXED_FRAC_BITS > 6
133 0 : return i << (CAIRO_FIXED_FRAC_BITS - 6);
134 : #else
135 : return i >> (6 - CAIRO_FIXED_FRAC_BITS);
136 : #endif
137 : }
138 :
139 : static inline cairo_fixed_t
140 : _cairo_fixed_from_16_16 (uint32_t i)
141 : {
142 : #if CAIRO_FIXED_FRAC_BITS > 16
143 : return i << (CAIRO_FIXED_FRAC_BITS - 16);
144 : #else
145 : return i >> (16 - CAIRO_FIXED_FRAC_BITS);
146 : #endif
147 : }
148 :
149 : static inline double
150 0 : _cairo_fixed_to_double (cairo_fixed_t f)
151 : {
152 0 : return ((double) f) / CAIRO_FIXED_ONE_DOUBLE;
153 : }
154 :
155 : static inline float
156 : _cairo_fixed_to_float (cairo_fixed_t f)
157 : {
158 : return ((float) f) / CAIRO_FIXED_ONE_FLOAT;
159 : }
160 :
161 : static inline int
162 0 : _cairo_fixed_is_integer (cairo_fixed_t f)
163 : {
164 0 : return (f & CAIRO_FIXED_FRAC_MASK) == 0;
165 : }
166 :
167 : static inline cairo_fixed_t
168 0 : _cairo_fixed_floor (cairo_fixed_t f)
169 : {
170 0 : return f & ~CAIRO_FIXED_FRAC_MASK;
171 : }
172 :
173 : static inline cairo_fixed_t
174 : _cairo_fixed_round (cairo_fixed_t f)
175 : {
176 : return _cairo_fixed_floor (f + (CAIRO_FIXED_FRAC_MASK+1)/2);
177 : }
178 :
179 : static inline cairo_fixed_t
180 0 : _cairo_fixed_round_down (cairo_fixed_t f)
181 : {
182 0 : return _cairo_fixed_floor (f + CAIRO_FIXED_FRAC_MASK/2);
183 : }
184 :
185 : static inline int
186 0 : _cairo_fixed_integer_part (cairo_fixed_t f)
187 : {
188 0 : return f >> CAIRO_FIXED_FRAC_BITS;
189 : }
190 :
191 : static inline int
192 : _cairo_fixed_integer_round (cairo_fixed_t f)
193 : {
194 : return _cairo_fixed_integer_part (f + (CAIRO_FIXED_FRAC_MASK+1)/2);
195 : }
196 :
197 : static inline int
198 0 : _cairo_fixed_integer_round_down (cairo_fixed_t f)
199 : {
200 0 : return _cairo_fixed_integer_part (f + CAIRO_FIXED_FRAC_MASK/2);
201 : }
202 :
203 : static inline int
204 0 : _cairo_fixed_fractional_part (cairo_fixed_t f)
205 : {
206 0 : return f & CAIRO_FIXED_FRAC_MASK;
207 : }
208 :
209 : static inline int
210 0 : _cairo_fixed_integer_floor (cairo_fixed_t f)
211 : {
212 0 : if (f >= 0)
213 0 : return f >> CAIRO_FIXED_FRAC_BITS;
214 : else
215 0 : return -((-f - 1) >> CAIRO_FIXED_FRAC_BITS) - 1;
216 : }
217 :
218 : static inline int
219 0 : _cairo_fixed_integer_ceil (cairo_fixed_t f)
220 : {
221 0 : if (f > 0)
222 0 : return ((f - 1)>>CAIRO_FIXED_FRAC_BITS) + 1;
223 : else
224 0 : return - (-f >> CAIRO_FIXED_FRAC_BITS);
225 : }
226 :
227 : /* A bunch of explicit 16.16 operators; we need these
228 : * to interface with pixman and other backends that require
229 : * 16.16 fixed point types.
230 : */
231 : static inline cairo_fixed_16_16_t
232 0 : _cairo_fixed_to_16_16 (cairo_fixed_t f)
233 : {
234 : #if (CAIRO_FIXED_FRAC_BITS == 16) && (CAIRO_FIXED_BITS == 32)
235 : return f;
236 : #elif CAIRO_FIXED_FRAC_BITS > 16
237 : /* We're just dropping the low bits, so we won't ever got over/underflow here */
238 : return f >> (CAIRO_FIXED_FRAC_BITS - 16);
239 : #else
240 : cairo_fixed_16_16_t x;
241 :
242 : /* Handle overflow/underflow by clamping to the lowest/highest
243 : * value representable as 16.16
244 : */
245 0 : if ((f >> CAIRO_FIXED_FRAC_BITS) < INT16_MIN) {
246 0 : x = INT32_MIN;
247 0 : } else if ((f >> CAIRO_FIXED_FRAC_BITS) > INT16_MAX) {
248 0 : x = INT32_MAX;
249 : } else {
250 0 : x = f << (16 - CAIRO_FIXED_FRAC_BITS);
251 : }
252 :
253 0 : return x;
254 : #endif
255 : }
256 :
257 : static inline cairo_fixed_16_16_t
258 0 : _cairo_fixed_16_16_from_double (double d)
259 : {
260 : union {
261 : double d;
262 : int32_t i[2];
263 : } u;
264 :
265 0 : u.d = d + CAIRO_MAGIC_NUMBER_FIXED_16_16;
266 : #ifdef FLOAT_WORDS_BIGENDIAN
267 : return u.i[1];
268 : #else
269 0 : return u.i[0];
270 : #endif
271 : }
272 :
273 : static inline int
274 0 : _cairo_fixed_16_16_floor (cairo_fixed_16_16_t f)
275 : {
276 0 : if (f >= 0)
277 0 : return f >> 16;
278 : else
279 0 : return -((-f - 1) >> 16) - 1;
280 : }
281 :
282 : static inline double
283 : _cairo_fixed_16_16_to_double (cairo_fixed_16_16_t f)
284 : {
285 : return ((double) f) / (double) (1 << 16);
286 : }
287 :
288 : #if CAIRO_FIXED_BITS == 32
289 :
290 : static inline cairo_fixed_t
291 0 : _cairo_fixed_mul (cairo_fixed_t a, cairo_fixed_t b)
292 : {
293 0 : cairo_int64_t temp = _cairo_int32x32_64_mul (a, b);
294 0 : return _cairo_int64_to_int32(_cairo_int64_rsl (temp, CAIRO_FIXED_FRAC_BITS));
295 : }
296 :
297 : /* computes round (a * b / c) */
298 : static inline cairo_fixed_t
299 : _cairo_fixed_mul_div (cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c)
300 : {
301 : cairo_int64_t ab = _cairo_int32x32_64_mul (a, b);
302 : cairo_int64_t c64 = _cairo_int32_to_int64 (c);
303 : return _cairo_int64_to_int32 (_cairo_int64_divrem (ab, c64).quo);
304 : }
305 :
306 : /* computes floor (a * b / c) */
307 : static inline cairo_fixed_t
308 0 : _cairo_fixed_mul_div_floor (cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c)
309 : {
310 0 : return _cairo_int64_32_div (_cairo_int32x32_64_mul (a, b), c);
311 : }
312 :
313 :
314 : static inline cairo_fixed_t
315 0 : _cairo_edge_compute_intersection_y_for_x (const cairo_point_t *p1,
316 : const cairo_point_t *p2,
317 : cairo_fixed_t x)
318 : {
319 : cairo_fixed_t y, dx;
320 :
321 0 : if (x == p1->x)
322 0 : return p1->y;
323 0 : if (x == p2->x)
324 0 : return p2->y;
325 :
326 0 : y = p1->y;
327 0 : dx = p2->x - p1->x;
328 0 : if (dx != 0)
329 0 : y += _cairo_fixed_mul_div_floor (x - p1->x, p2->y - p1->y, dx);
330 :
331 0 : return y;
332 : }
333 :
334 : static inline cairo_fixed_t
335 0 : _cairo_edge_compute_intersection_x_for_y (const cairo_point_t *p1,
336 : const cairo_point_t *p2,
337 : cairo_fixed_t y)
338 : {
339 : cairo_fixed_t x, dy;
340 :
341 0 : if (y == p1->y)
342 0 : return p1->x;
343 0 : if (y == p2->y)
344 0 : return p2->x;
345 :
346 0 : x = p1->x;
347 0 : dy = p2->y - p1->y;
348 0 : if (dy != 0)
349 0 : x += _cairo_fixed_mul_div_floor (y - p1->y, p2->x - p1->x, dy);
350 :
351 0 : return x;
352 : }
353 :
354 : #else
355 : # error Please define multiplication and other operands for your fixed-point type size
356 : #endif
357 :
358 : #endif /* CAIRO_FIXED_PRIVATE_H */
|
