source/libs/cairo/cairo-src/src/cairo-fixed-private.h

   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 #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
  62 _cairo_fixed_from_int (int i)
  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
 111 _cairo_fixed_from_double (double d)
 112 {
 113     union {
 114         double d;
 115         int32_t i[2];
 116     } u;
 117
 118     u.d = d + CAIRO_MAGIC_NUMBER_FIXED;
 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
 132 _cairo_fixed_from_26_6 (uint32_t i)
 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
 142 _cairo_fixed_from_16_16 (uint32_t i)
 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
 152 _cairo_fixed_to_double (cairo_fixed_t f)
 153 {
 154     return ((double) f) / CAIRO_FIXED_ONE_DOUBLE;
 155 }
 156
 157 static inline int
 158 _cairo_fixed_is_integer (cairo_fixed_t f)
 159 {
 160     return (f & CAIRO_FIXED_FRAC_MASK) == 0;
 161 }
 162
 163 static inline cairo_fixed_t
 164 _cairo_fixed_floor (cairo_fixed_t f)
 165 {
 166     return f & ~CAIRO_FIXED_FRAC_MASK;
 167 }
 168
 169 static inline cairo_fixed_t
 170 _cairo_fixed_ceil (cairo_fixed_t f)
 171 {
 172     return _cairo_fixed_floor (f + CAIRO_FIXED_FRAC_MASK);
 173 }
 174
 175 static inline cairo_fixed_t
 176 _cairo_fixed_round (cairo_fixed_t f)
 177 {
 178     return _cairo_fixed_floor (f + (CAIRO_FIXED_FRAC_MASK+1)/2);
 179 }
 180
 181 static inline cairo_fixed_t
 182 _cairo_fixed_round_down (cairo_fixed_t f)
 183 {
 184     return _cairo_fixed_floor (f + CAIRO_FIXED_FRAC_MASK/2);
 185 }
 186
 187 static inline int
 188 _cairo_fixed_integer_part (cairo_fixed_t f)
 189 {
 190     return f >> CAIRO_FIXED_FRAC_BITS;
 191 }
 192
 193 static inline int
 194 _cairo_fixed_integer_round (cairo_fixed_t f)
 195 {
 196     return _cairo_fixed_integer_part (f + (CAIRO_FIXED_FRAC_MASK+1)/2);
 197 }
 198
 199 static inline int
 200 _cairo_fixed_integer_round_down (cairo_fixed_t f)
 201 {
 202     return _cairo_fixed_integer_part (f + CAIRO_FIXED_FRAC_MASK/2);
 203 }
 204
 205 static inline int
 206 _cairo_fixed_fractional_part (cairo_fixed_t f)
 207 {
 208     return f & CAIRO_FIXED_FRAC_MASK;
 209 }
 210
 211 static inline int
 212 _cairo_fixed_integer_floor (cairo_fixed_t f)
 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
 221 _cairo_fixed_integer_ceil (cairo_fixed_t f)
 222 {
 223     if (f > 0)
 224         return ((f - 1)>>CAIRO_FIXED_FRAC_BITS) + 1;
 225     else
 226         return - (-f >> CAIRO_FIXED_FRAC_BITS);
 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
 234 _cairo_fixed_to_16_16 (cairo_fixed_t f)
 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
 242     cairo_fixed_16_16_t x;
 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
 260 _cairo_fixed_16_16_from_double (double d)
 261 {
 262     union {
 263         double d;
 264         int32_t i[2];
 265     } u;
 266
 267     u.d = d + CAIRO_MAGIC_NUMBER_FIXED_16_16;
 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
 276 _cairo_fixed_16_16_floor (cairo_fixed_16_16_t f)
 277 {
 278     if (f >= 0)
 279         return f >> 16;
 280     else
 281         return -((-f - 1) >> 16) - 1;
 282 }
 283
 284 static inline double
 285 _cairo_fixed_16_16_to_double (cairo_fixed_16_16_t f)
 286 {
 287     return ((double) f) / (double) (1 << 16);
 288 }
 289
 290 #if CAIRO_FIXED_BITS == 32
 291
 292 static inline cairo_fixed_t
 293 _cairo_fixed_mul (cairo_fixed_t a, cairo_fixed_t b)
 294 {
 295     cairo_int64_t temp = _cairo_int32x32_64_mul (a, b);
 296     return _cairo_int64_to_int32(_cairo_int64_rsl (temp, CAIRO_FIXED_FRAC_BITS));
 297 }
 298
 299 /* computes round (a * b / c) */
 300 static inline cairo_fixed_t
 301 _cairo_fixed_mul_div (cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c)
 302 {
 303     cairo_int64_t ab  = _cairo_int32x32_64_mul (a, b);
 304     cairo_int64_t c64 = _cairo_int32_to_int64 (c);
 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
 310 _cairo_fixed_mul_div_floor (cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c)
 311 {
 312     return _cairo_int64_32_div (_cairo_int32x32_64_mul (a, b), c);
 313 }
 314
 315 /* compute y from x so that (x,y), p1, and p2 are collinear */
 316 static inline cairo_fixed_t
 317 _cairo_edge_compute_intersection_y_for_x (const cairo_point_t *p1,
 318                                           const cairo_point_t *p2,
 319                                           cairo_fixed_t x)
 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
 338 _cairo_edge_compute_intersection_x_for_y (const cairo_point_t *p1,
 339                                           const cairo_point_t *p2,
 340                                           cairo_fixed_t y)
 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
 361 _slow_segment_intersection (const cairo_point_t *seg1_p1,
 362                             const cairo_point_t *seg1_p2,
 363                             const cairo_point_t *seg2_p1,
 364                             const cairo_point_t *seg2_p2,
 365                             cairo_point_t *intersection)
 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 */