w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

cairo-fixed-private.h
Go to the documentation of this file.
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 
41 
42 #include "cairo-wideint-private.h"
43 #include "cairoint.h"
44 
45 /* Implementation */
46 
47 #if (CAIRO_FIXED_BITS != 32)
48 # error CAIRO_FIXED_BITS must be 32, and the type must be a 32-bit type.
49 # error To remove this limitation, you will have to fix the tessellator.
50 #endif
51 
52 #define CAIRO_FIXED_ONE ((cairo_fixed_t)(1 << CAIRO_FIXED_FRAC_BITS))
53 #define CAIRO_FIXED_ONE_DOUBLE ((double)(1 << CAIRO_FIXED_FRAC_BITS))
54 #define CAIRO_FIXED_EPSILON ((cairo_fixed_t)(1))
55 
56 #define CAIRO_FIXED_ERROR_DOUBLE (1. / (2 * CAIRO_FIXED_ONE_DOUBLE))
57 
58 #define CAIRO_FIXED_FRAC_MASK ((cairo_fixed_t)(((cairo_fixed_unsigned_t)(-1)) >> (CAIRO_FIXED_BITS - CAIRO_FIXED_FRAC_BITS)))
59 #define CAIRO_FIXED_WHOLE_MASK (~CAIRO_FIXED_FRAC_MASK)
60 
61 static inline cairo_fixed_t
63 {
64  return i << CAIRO_FIXED_FRAC_BITS;
65 }
66 
67 /* This is the "magic number" approach to converting a double into fixed
68  * point as described here:
69  *
70  * http://www.stereopsis.com/sree/fpu2006.html (an overview)
71  * http://www.d6.com/users/checker/pdfs/gdmfp.pdf (in detail)
72  *
73  * The basic idea is to add a large enough number to the double that the
74  * literal floating point is moved up to the extent that it forces the
75  * double's value to be shifted down to the bottom of the mantissa (to make
76  * room for the large number being added in). Since the mantissa is, at a
77  * given moment in time, a fixed point integer itself, one can convert a
78  * float to various fixed point representations by moving around the point
79  * of a floating point number through arithmetic operations. This behavior
80  * is reliable on most modern platforms as it is mandated by the IEEE-754
81  * standard for floating point arithmetic.
82  *
83  * For our purposes, a "magic number" must be carefully selected that is
84  * both large enough to produce the desired point-shifting effect, and also
85  * has no lower bits in its representation that would interfere with our
86  * value at the bottom of the mantissa. The magic number is calculated as
87  * follows:
88  *
89  * (2 ^ (MANTISSA_SIZE - FRACTIONAL_SIZE)) * 1.5
90  *
91  * where in our case:
92  * - MANTISSA_SIZE for 64-bit doubles is 52
93  * - FRACTIONAL_SIZE for 16.16 fixed point is 16
94  *
95  * Although this approach provides a very large speedup of this function
96  * on a wide-array of systems, it does come with two caveats:
97  *
98  * 1) It uses banker's rounding as opposed to arithmetic rounding.
99  * 2) It doesn't function properly if the FPU is in single-precision
100  * mode.
101  */
102 
103 /* The 16.16 number must always be available */
104 #define CAIRO_MAGIC_NUMBER_FIXED_16_16 (103079215104.0)
105 
106 #if CAIRO_FIXED_BITS <= 32
107 #define CAIRO_MAGIC_NUMBER_FIXED ((1LL << (52 - CAIRO_FIXED_FRAC_BITS)) * 1.5)
108 
109 /* For 32-bit fixed point numbers */
110 static inline cairo_fixed_t
112 {
113  union {
114  double d;
115  int32_t i[2];
116  } u;
117 
119 #ifdef FLOAT_WORDS_BIGENDIAN
120  return u.i[1];
121 #else
122  return u.i[0];
123 #endif
124 }
125 
126 #else
127 # error Please define a magic number for your fixed point type!
128 # error See cairo-fixed-private.h for details.
129 #endif
130 
131 static inline cairo_fixed_t
133 {
134 #if CAIRO_FIXED_FRAC_BITS > 6
135  return i << (CAIRO_FIXED_FRAC_BITS - 6);
136 #else
137  return i >> (6 - CAIRO_FIXED_FRAC_BITS);
138 #endif
139 }
140 
141 static inline cairo_fixed_t
143 {
144 #if CAIRO_FIXED_FRAC_BITS > 16
145  return i << (CAIRO_FIXED_FRAC_BITS - 16);
146 #else
147  return i >> (16 - CAIRO_FIXED_FRAC_BITS);
148 #endif
149 }
150 
151 static inline double
153 {
154  return ((double) f) / CAIRO_FIXED_ONE_DOUBLE;
155 }
156 
157 static inline int
159 {
160  return (f & CAIRO_FIXED_FRAC_MASK) == 0;
161 }
162 
163 static inline cairo_fixed_t
165 {
166  return f & ~~CAIRO_FIXED_FRAC_MASK;
167 }
168 
169 static inline cairo_fixed_t
171 {
173 }
174 
175 static inline cairo_fixed_t
177 {
178  return _cairo_fixed_floor (f + (CAIRO_FIXED_FRAC_MASK+1)/2);
179 }
180 
181 static inline cairo_fixed_t
183 {
185 }
186 
187 static inline int
189 {
190  return f >> CAIRO_FIXED_FRAC_BITS;
191 }
192 
193 static inline int
195 {
197 }
198 
199 static inline int
201 {
203 }
204 
205 static inline int
207 {
208  return f & CAIRO_FIXED_FRAC_MASK;
209 }
210 
211 static inline int
213 {
214  if (f >= 0)
215  return f >> CAIRO_FIXED_FRAC_BITS;
216  else
217  return -((-f - 1) >> CAIRO_FIXED_FRAC_BITS) - 1;
218 }
219 
220 static inline int
222 {
223  if (f > 0)
224  return ((f - 1)>>CAIRO_FIXED_FRAC_BITS) + 1;
225  else
227 }
228 
229 /* A bunch of explicit 16.16 operators; we need these
230  * to interface with pixman and other backends that require
231  * 16.16 fixed point types.
232  */
233 static inline cairo_fixed_16_16_t
235 {
236 #if (CAIRO_FIXED_FRAC_BITS == 16) && (CAIRO_FIXED_BITS == 32)
237  return f;
238 #elif CAIRO_FIXED_FRAC_BITS > 16
239  /* We're just dropping the low bits, so we won't ever got over/underflow here */
240  return f >> (CAIRO_FIXED_FRAC_BITS - 16);
241 #else
243 
244  /* Handle overflow/underflow by clamping to the lowest/highest
245  * value representable as 16.16
246  */
247  if ((f >> CAIRO_FIXED_FRAC_BITS) < INT16_MIN) {
248  x = INT32_MIN;
249  } else if ((f >> CAIRO_FIXED_FRAC_BITS) > INT16_MAX) {
250  x = INT32_MAX;
251  } else {
252  x = f << (16 - CAIRO_FIXED_FRAC_BITS);
253  }
254 
255  return x;
256 #endif
257 }
258 
259 static inline cairo_fixed_16_16_t
261 {
262  union {
263  double d;
264  int32_t i[2];
265  } u;
266 
268 #ifdef FLOAT_WORDS_BIGENDIAN
269  return u.i[1];
270 #else
271  return u.i[0];
272 #endif
273 }
274 
275 static inline int
277 {
278  if (f >= 0)
279  return f >> 16;
280  else
281  return -((-f - 1) >> 16) - 1;
282 }
283 
284 static inline double
286 {
287  return ((double) f) / (double) (1 << 16);
288 }
289 
290 #if CAIRO_FIXED_BITS == 32
291 
292 static inline cairo_fixed_t
294 {
297 }
298 
299 /* computes round (a * b / c) */
300 static inline cairo_fixed_t
302 {
305  return _cairo_int64_to_int32 (_cairo_int64_divrem (ab, c64).quo);
306 }
307 
308 /* computes floor (a * b / c) */
309 static inline cairo_fixed_t
311 {
313 }
314 
315 /* compute y from x so that (x,y), p1, and p2 are collinear */
316 static inline cairo_fixed_t
318  const cairo_point_t *p2,
320 {
321  cairo_fixed_t y, dx;
322 
323  if (x == p1->x)
324  return p1->y;
325  if (x == p2->x)
326  return p2->y;
327 
328  y = p1->y;
329  dx = p2->x - p1->x;
330  if (dx != 0)
331  y += _cairo_fixed_mul_div_floor (x - p1->x, p2->y - p1->y, dx);
332 
333  return y;
334 }
335 
336 /* compute x from y so that (x,y), p1, and p2 are collinear */
337 static inline cairo_fixed_t
339  const cairo_point_t *p2,
341 {
342  cairo_fixed_t x, dy;
343 
344  if (y == p1->y)
345  return p1->x;
346  if (y == p2->y)
347  return p2->x;
348 
349  x = p1->x;
350  dy = p2->y - p1->y;
351  if (dy != 0)
352  x += _cairo_fixed_mul_div_floor (y - p1->y, p2->x - p1->x, dy);
353 
354  return x;
355 }
356 
357 /* Intersect two segments based on the algorithm described at
358  * http://paulbourke.net/geometry/pointlineplane/. This implementation
359  * uses floating point math. */
360 static inline cairo_bool_t
362  const cairo_point_t *seg1_p2,
363  const cairo_point_t *seg2_p1,
364  const cairo_point_t *seg2_p2,
366 {
367  double denominator, u_a, u_b;
368  double seg1_dx, seg1_dy, seg2_dx, seg2_dy, seg_start_dx, seg_start_dy;
369 
370  seg1_dx = _cairo_fixed_to_double (seg1_p2->x - seg1_p1->x);
371  seg1_dy = _cairo_fixed_to_double (seg1_p2->y - seg1_p1->y);
372  seg2_dx = _cairo_fixed_to_double (seg2_p2->x - seg2_p1->x);
373  seg2_dy = _cairo_fixed_to_double (seg2_p2->y - seg2_p1->y);
374  denominator = (seg2_dy * seg1_dx) - (seg2_dx * seg1_dy);
375  if (denominator == 0)
376  return FALSE;
377 
378  seg_start_dx = _cairo_fixed_to_double (seg1_p1->x - seg2_p1->x);
379  seg_start_dy = _cairo_fixed_to_double (seg1_p1->y - seg2_p1->y);
380  u_a = ((seg2_dx * seg_start_dy) - (seg2_dy * seg_start_dx)) / denominator;
381  u_b = ((seg1_dx * seg_start_dy) - (seg1_dy * seg_start_dx)) / denominator;
382 
383  if (u_a <= 0 || u_a >= 1 || u_b <= 0 || u_b >= 1)
384  return FALSE;
385 
386  intersection->x = seg1_p1->x + _cairo_fixed_from_double ((u_a * seg1_dx));
387  intersection->y = seg1_p1->y + _cairo_fixed_from_double ((u_a * seg1_dy));
388  return TRUE;
389 }
390 
391 #else
392 # error Please define multiplication and other operands for your fixed-point type size
393 #endif
394 
395 #endif /* CAIRO_FIXED_PRIVATE_H */
#define denominator
char * p2
Definition: bmpfont.h:62
char * p1
Definition: bmpfont.h:62
static cairo_fixed_16_16_t _cairo_fixed_to_16_16(cairo_fixed_t f)
static int _cairo_fixed_integer_round(cairo_fixed_t f)
static cairo_fixed_t _cairo_fixed_ceil(cairo_fixed_t f)
static cairo_fixed_t _cairo_fixed_from_16_16(uint32_t i)
static cairo_fixed_t _cairo_fixed_from_int(int i)
static int _cairo_fixed_integer_round_down(cairo_fixed_t f)
#define CAIRO_MAGIC_NUMBER_FIXED
static int _cairo_fixed_integer_floor(cairo_fixed_t f)
static cairo_fixed_t _cairo_edge_compute_intersection_x_for_y(const cairo_point_t *p1, const cairo_point_t *p2, cairo_fixed_t y)
static cairo_bool_t _slow_segment_intersection(const cairo_point_t *seg1_p1, const cairo_point_t *seg1_p2, const cairo_point_t *seg2_p1, const cairo_point_t *seg2_p2, cairo_point_t *intersection)
static int _cairo_fixed_is_integer(cairo_fixed_t f)
static cairo_fixed_t _cairo_fixed_mul(cairo_fixed_t a, cairo_fixed_t b)
static cairo_fixed_t _cairo_fixed_mul_div_floor(cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c)
static cairo_fixed_t _cairo_fixed_mul_div(cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c)
static int _cairo_fixed_fractional_part(cairo_fixed_t f)
static double _cairo_fixed_16_16_to_double(cairo_fixed_16_16_t f)
static int _cairo_fixed_integer_ceil(cairo_fixed_t f)
#define CAIRO_MAGIC_NUMBER_FIXED_16_16
static cairo_fixed_t _cairo_fixed_round(cairo_fixed_t f)
static cairo_fixed_t _cairo_edge_compute_intersection_y_for_x(const cairo_point_t *p1, const cairo_point_t *p2, cairo_fixed_t x)
#define CAIRO_FIXED_ONE_DOUBLE
static int _cairo_fixed_16_16_floor(cairo_fixed_16_16_t f)
static cairo_fixed_t _cairo_fixed_from_double(double d)
static int _cairo_fixed_integer_part(cairo_fixed_t f)
static double _cairo_fixed_to_double(cairo_fixed_t f)
static cairo_fixed_t _cairo_fixed_from_26_6(uint32_t i)
static cairo_fixed_16_16_t _cairo_fixed_16_16_from_double(double d)
static cairo_fixed_t _cairo_fixed_round_down(cairo_fixed_t f)
#define CAIRO_FIXED_FRAC_MASK
static cairo_fixed_t _cairo_fixed_floor(cairo_fixed_t f)
uint32_t cairo_fixed_unsigned_t
int32_t cairo_fixed_16_16_t
#define CAIRO_FIXED_FRAC_BITS
int32_t cairo_fixed_t
#define _cairo_int64_to_int32(a)
static cairo_quorem64_t _cairo_int64_divrem(cairo_int64_t num, cairo_int64_t den)
cairo_int64_t _cairo_int32_to_int64(int32_t i)
#define _cairo_int64_rsl(a, b)
static int32_t _cairo_int64_32_div(cairo_int64_t num, int32_t den)
cairo_int64_t _cairo_int32x32_64_mul(int32_t a, int32_t b)
int cairo_bool_t
Definition: cairo.h:107
#define b
Definition: jpegint.h:372
@ FALSE
Definition: dd.h:101
@ TRUE
Definition: dd.h:102
char * temp
Definition: dvidvi.c:137
mpz_t * f
Definition: gen-fib.c:34
#define c(n)
Definition: gpos-common.c:150
#define a(n)
Definition: gpos-common.c:148
#define d(n)
Definition: gpos-common.c:151
small capitals from c petite p scientific f u
Definition: afcover.h:88
small capitals from c petite p scientific i
Definition: afcover.h:80
kerning y
Definition: ttdriver.c:212
#define INT32_MAX
Definition: stdint.h:137
unsigned int uint32_t
Definition: stdint.h:80
#define INT32_MIN
Definition: stdint.h:136
signed int int32_t
Definition: stdint.h:77
#define INT16_MAX
Definition: stdint.h:135
#define INT16_MIN
Definition: stdint.h:134
static const UChar u_a
float x
Definition: cordic.py:15