src/borast/borast-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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 Corporation
  32  *
  33  * Contributor(s):
  34  *      Vladimir Vukicevic <vladimir@pobox.com>
  35  */
  36
  37 #ifndef BORAST_FIXED_PRIVATE_H
  38 #define BORAST_FIXED_PRIVATE_H
  39
  40 #include "borast-fixed-type-private.h"
  41
  42 #include "borast-wideint-private.h"
  43
  44 /* Implementation */
  45
  46 #if (BORAST_FIXED_BITS != 32)
  47 # error BORAST_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 BORAST_FIXED_ONE        ((borast_fixed_t)(1 << BORAST_FIXED_FRAC_BITS))
  52 #define BORAST_FIXED_ONE_DOUBLE ((double)(1 << BORAST_FIXED_FRAC_BITS))
  53 #define BORAST_FIXED_EPSILON    ((borast_fixed_t)(1))
  54
  55 #define BORAST_FIXED_FRAC_MASK  (((borast_fixed_unsigned_t)(-1)) >> (BORAST_FIXED_BITS - BORAST_FIXED_FRAC_BITS))
  56 #define BORAST_FIXED_WHOLE_MASK (~BORAST_FIXED_FRAC_MASK)
  57
  58 static inline borast_fixed_t
  59 _borast_fixed_from_int (int i)
  60 {
  61     return i << BORAST_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 BORAST_MAGIC_NUMBER_FIXED_16_16 (103079215104.0)
 102
 103 #if BORAST_FIXED_BITS <= 32
 104 #define BORAST_MAGIC_NUMBER_FIXED ((1LL << (52 - BORAST_FIXED_FRAC_BITS)) * 1.5)
 105
 106 /* For 32-bit fixed point numbers */
 107 static inline borast_fixed_t
 108 _borast_fixed_from_double (double d)
 109 {
 110     union {
 111         double d;
 112         int32_t i[2];
 113     } u;
 114
 115     u.d = d + BORAST_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 borast-fixed-private.h for details.
 126 #endif
 127
 128 static inline borast_fixed_t
 129 _borast_fixed_from_26_6 (uint32_t i)
 130 {
 131 #if BORAST_FIXED_FRAC_BITS > 6
 132     return i << (BORAST_FIXED_FRAC_BITS - 6);
 133 #else
 134     return i >> (6 - BORAST_FIXED_FRAC_BITS);
 135 #endif
 136 }
 137
 138 static inline double
 139 _borast_fixed_to_double (borast_fixed_t f)
 140 {
 141     return ((double) f) / BORAST_FIXED_ONE_DOUBLE;
 142 }
 143
 144 static inline int
 145 _borast_fixed_is_integer (borast_fixed_t f)
 146 {
 147     return (f & BORAST_FIXED_FRAC_MASK) == 0;
 148 }
 149
 150 static inline int
 151 _borast_fixed_integer_part (borast_fixed_t f)
 152 {
 153     return f >> BORAST_FIXED_FRAC_BITS;
 154 }
 155
 156 static inline int
 157 _borast_fixed_integer_floor (borast_fixed_t f)
 158 {
 159     if (f >= 0)
 160         return f >> BORAST_FIXED_FRAC_BITS;
 161     else
 162         return -((-f - 1) >> BORAST_FIXED_FRAC_BITS) - 1;
 163 }
 164
 165 static inline int
 166 _borast_fixed_integer_ceil (borast_fixed_t f)
 167 {
 168     if (f > 0)
 169         return ((f - 1)>>BORAST_FIXED_FRAC_BITS) + 1;
 170     else
 171         return - (-f >> BORAST_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 borast_fixed_16_16_t
 179 _borast_fixed_to_16_16 (borast_fixed_t f)
 180 {
 181 #if (BORAST_FIXED_FRAC_BITS == 16) && (BORAST_FIXED_BITS == 32)
 182     return f;
 183 #elif BORAST_FIXED_FRAC_BITS > 16
 184     /* We're just dropping the low bits, so we won't ever got over/underflow here */
 185     return f >> (BORAST_FIXED_FRAC_BITS - 16);
 186 #else
 187     borast_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 >> BORAST_FIXED_FRAC_BITS) < INT16_MIN) {
 193         x = INT32_MIN;
 194     } else if ((f >> BORAST_FIXED_FRAC_BITS) > INT16_MAX) {
 195         x = INT32_MAX;
 196     } else {
 197         x = f << (16 - BORAST_FIXED_FRAC_BITS);
 198     }
 199
 200     return x;
 201 #endif
 202 }
 203
 204 static inline borast_fixed_16_16_t
 205 _borast_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 + BORAST_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 BORAST_FIXED_BITS == 32
 221
 222 static inline borast_fixed_t
 223 _borast_fixed_mul (borast_fixed_t a, borast_fixed_t b)
 224 {
 225     borast_int64_t temp = _borast_int32x32_64_mul (a, b);
 226     return _borast_int64_to_int32(_borast_int64_rsl (temp, BORAST_FIXED_FRAC_BITS));
 227 }
 228
 229 /* computes round (a * b / c) */
 230 static inline borast_fixed_t
 231 _borast_fixed_mul_div (borast_fixed_t a, borast_fixed_t b, borast_fixed_t c)
 232 {
 233     borast_int64_t ab  = _borast_int32x32_64_mul (a, b);
 234     borast_int64_t c64 = _borast_int32_to_int64 (c);
 235     return _borast_int64_to_int32 (_borast_int64_divrem (ab, c64).quo);
 236 }
 237
 238 /* computes floor (a * b / c) */
 239 static inline borast_fixed_t
 240 _borast_fixed_mul_div_floor (borast_fixed_t a, borast_fixed_t b, borast_fixed_t c)
 241 {
 242     return _borast_int64_32_div (_borast_int32x32_64_mul (a, b), c);
 243 }
 244
 245
 246 static inline borast_fixed_t
 247 _borast_edge_compute_intersection_y_for_x (const borast_point_t *p1,
 248                                           const borast_point_t *p2,
 249                                           borast_fixed_t x)
 250 {
 251     borast_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 += _borast_fixed_mul_div_floor (x - p1->x, p2->y - p1->y, dx);
 262
 263     return y;
 264 }
 265
 266 static inline borast_fixed_t
 267 _borast_edge_compute_intersection_x_for_y (const borast_point_t *p1,
 268                                           const borast_point_t *p2,
 269                                           borast_fixed_t y)
 270 {
 271     borast_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 += _borast_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 /* BORAST_FIXED_PRIVATE_H */