Subversion Repositories Scribus

Rev

Rev 14952 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
14952 fschmid 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
18122 mrdocs 16
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
14952 fschmid 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 Corporation
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_EPSILON    ((cairo_fixed_t)(1))
54
 
55
#define CAIRO_FIXED_FRAC_MASK  (((cairo_fixed_unsigned_t)(-1)) >> (CAIRO_FIXED_BITS - CAIRO_FIXED_FRAC_BITS))
56
#define CAIRO_FIXED_WHOLE_MASK (~CAIRO_FIXED_FRAC_MASK)
57
 
58
static inline cairo_fixed_t
59
_cairo_fixed_from_int (int i)
60
{
61
    return i << CAIRO_FIXED_FRAC_BITS;
62
}
63
 
64
/* This is the "magic number" approach to converting a double into fixed
65
 * point as described here:
66
 *
67
 * http://www.stereopsis.com/sree/fpu2006.html (an overview)
68
 * http://www.d6.com/users/checker/pdfs/gdmfp.pdf (in detail)
69
 *
70
 * The basic idea is to add a large enough number to the double that the
71
 * literal floating point is moved up to the extent that it forces the
72
 * double's value to be shifted down to the bottom of the mantissa (to make
73
 * room for the large number being added in). Since the mantissa is, at a
74
 * given moment in time, a fixed point integer itself, one can convert a
75
 * float to various fixed point representations by moving around the point
76
 * of a floating point number through arithmetic operations. This behavior
77
 * is reliable on most modern platforms as it is mandated by the IEEE-754
78
 * standard for floating point arithmetic.
79
 *
80
 * For our purposes, a "magic number" must be carefully selected that is
81
 * both large enough to produce the desired point-shifting effect, and also
82
 * has no lower bits in its representation that would interfere with our
83
 * value at the bottom of the mantissa. The magic number is calculated as
84
 * follows:
85
 *
86
 *          (2 ^ (MANTISSA_SIZE - FRACTIONAL_SIZE)) * 1.5
87
 *
88
 * where in our case:
89
 *  - MANTISSA_SIZE for 64-bit doubles is 52
90
 *  - FRACTIONAL_SIZE for 16.16 fixed point is 16
91
 *
92
 * Although this approach provides a very large speedup of this function
93
 * on a wide-array of systems, it does come with two caveats:
94
 *
95
 * 1) It uses banker's rounding as opposed to arithmetic rounding.
96
 * 2) It doesn't function properly if the FPU is in single-precision
97
 *    mode.
98
 */
99
 
100
/* The 16.16 number must always be available */
101
#define CAIRO_MAGIC_NUMBER_FIXED_16_16 (103079215104.0)
102
 
103
#if CAIRO_FIXED_BITS <= 32
104
#define CAIRO_MAGIC_NUMBER_FIXED ((1LL << (52 - CAIRO_FIXED_FRAC_BITS)) * 1.5)
105
 
106
/* For 32-bit fixed point numbers */
107
static inline cairo_fixed_t
108
_cairo_fixed_from_double (double d)
109
{
110
    union {
111
        double d;
112
        int32_t i[2];
113
    } u;
114
 
115
    u.d = d + CAIRO_MAGIC_NUMBER_FIXED;
116
#ifdef FLOAT_WORDS_BIGENDIAN
117
    return u.i[1];
118
#else
119
    return u.i[0];
120
#endif
121
}
122
 
123
#else
124
# error Please define a magic number for your fixed point type!
125
# error See cairo-fixed-private.h for details.
126
#endif
127
 
128
static inline cairo_fixed_t
129
_cairo_fixed_from_26_6 (uint32_t i)
130
{
131
#if CAIRO_FIXED_FRAC_BITS > 6
132
    return i << (CAIRO_FIXED_FRAC_BITS - 6);
133
#else
134
    return i >> (6 - CAIRO_FIXED_FRAC_BITS);
135
#endif
136
}
137
 
138
static inline double
139
_cairo_fixed_to_double (cairo_fixed_t f)
140
{
141
    return ((double) f) / CAIRO_FIXED_ONE_DOUBLE;
142
}
143
 
144
static inline int
145
_cairo_fixed_is_integer (cairo_fixed_t f)
146
{
147
    return (f & CAIRO_FIXED_FRAC_MASK) == 0;
148
}
149
 
150
static inline int
151
_cairo_fixed_integer_part (cairo_fixed_t f)
152
{
153
    return f >> CAIRO_FIXED_FRAC_BITS;
154
}
155
 
156
static inline int
157
_cairo_fixed_integer_floor (cairo_fixed_t f)
158
{
159
    if (f >= 0)
160
        return f >> CAIRO_FIXED_FRAC_BITS;
161
    else
162
        return -((-f - 1) >> CAIRO_FIXED_FRAC_BITS) - 1;
163
}
164
 
165
static inline int
166
_cairo_fixed_integer_ceil (cairo_fixed_t f)
167
{
168
    if (f > 0)
169
        return ((f - 1)>>CAIRO_FIXED_FRAC_BITS) + 1;
170
    else
171
        return - (-f >> CAIRO_FIXED_FRAC_BITS);
172
}
173
 
174
/* A bunch of explicit 16.16 operators; we need these
175
 * to interface with pixman and other backends that require
176
 * 16.16 fixed point types.
177
 */
178
static inline cairo_fixed_16_16_t
179
_cairo_fixed_to_16_16 (cairo_fixed_t f)
180
{
181
#if (CAIRO_FIXED_FRAC_BITS == 16) && (CAIRO_FIXED_BITS == 32)
182
    return f;
183
#elif CAIRO_FIXED_FRAC_BITS > 16
184
    /* We're just dropping the low bits, so we won't ever got over/underflow here */
185
    return f >> (CAIRO_FIXED_FRAC_BITS - 16);
186
#else
187
    cairo_fixed_16_16_t x;
188
 
189
    /* Handle overflow/underflow by clamping to the lowest/highest
190
     * value representable as 16.16
191
     */
192
    if ((f >> CAIRO_FIXED_FRAC_BITS) < INT16_MIN) {
193
        x = INT32_MIN;
194
    } else if ((f >> CAIRO_FIXED_FRAC_BITS) > INT16_MAX) {
195
        x = INT32_MAX;
196
    } else {
197
        x = f << (16 - CAIRO_FIXED_FRAC_BITS);
198
    }
199
 
200
    return x;
201
#endif
202
}
203
 
204
static inline cairo_fixed_16_16_t
205
_cairo_fixed_16_16_from_double (double d)
206
{
207
    union {
208
        double d;
209
        int32_t i[2];
210
    } u;
211
 
212
    u.d = d + CAIRO_MAGIC_NUMBER_FIXED_16_16;
213
#ifdef FLOAT_WORDS_BIGENDIAN
214
    return u.i[1];
215
#else
216
    return u.i[0];
217
#endif
218
}
219
 
220
#if CAIRO_FIXED_BITS == 32
221
 
222
static inline cairo_fixed_t
223
_cairo_fixed_mul (cairo_fixed_t a, cairo_fixed_t b)
224
{
225
    cairo_int64_t temp = _cairo_int32x32_64_mul (a, b);
226
    return _cairo_int64_to_int32(_cairo_int64_rsl (temp, CAIRO_FIXED_FRAC_BITS));
227
}
228
 
229
/* computes round (a * b / c) */
230
static inline cairo_fixed_t
231
_cairo_fixed_mul_div (cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c)
232
{
233
    cairo_int64_t ab  = _cairo_int32x32_64_mul (a, b);
234
    cairo_int64_t c64 = _cairo_int32_to_int64 (c);
235
    return _cairo_int64_to_int32 (_cairo_int64_divrem (ab, c64).quo);
236
}
237
 
238
/* computes floor (a * b / c) */
239
static inline cairo_fixed_t
240
_cairo_fixed_mul_div_floor (cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c)
241
{
242
    return _cairo_int64_32_div (_cairo_int32x32_64_mul (a, b), c);
243
}
244
 
245
 
246
static inline cairo_fixed_t
247
_cairo_edge_compute_intersection_y_for_x (const cairo_point_t *p1,
248
                                          const cairo_point_t *p2,
249
                                          cairo_fixed_t x)
250
{
251
    cairo_fixed_t y, dx;
252
 
253
    if (x == p1->x)
254
        return p1->y;
255
    if (x == p2->x)
256
        return p2->y;
257
 
258
    y = p1->y;
259
    dx = p2->x - p1->x;
260
    if (dx != 0)
261
        y += _cairo_fixed_mul_div_floor (x - p1->x, p2->y - p1->y, dx);
262
 
263
    return y;
264
}
265
 
266
static inline cairo_fixed_t
267
_cairo_edge_compute_intersection_x_for_y (const cairo_point_t *p1,
268
                                          const cairo_point_t *p2,
269
                                          cairo_fixed_t y)
270
{
271
    cairo_fixed_t x, dy;
272
 
273
    if (y == p1->y)
274
        return p1->x;
275
    if (y == p2->y)
276
        return p2->x;
277
 
278
    x = p1->x;
279
    dy = p2->y - p1->y;
280
    if (dy != 0)
281
        x += _cairo_fixed_mul_div_floor (y - p1->y, p2->x - p1->x, dy);
282
 
283
    return x;
284
}
285
 
286
#else
287
# error Please define multiplication and other operands for your fixed-point type size
288
#endif
289
 
290
#endif /* CAIRO_FIXED_PRIVATE_H */