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