| /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */ |
| /* Cairo - a vector graphics library with display and print output |
| * |
| * Copyright © 2007 Mozilla Corporation |
| * |
| * This library is free software; you can redistribute it and/or |
| * modify it either under the terms of the GNU Lesser General Public |
| * License version 2.1 as published by the Free Software Foundation |
| * (the "LGPL") or, at your option, under the terms of the Mozilla |
| * Public License Version 1.1 (the "MPL"). If you do not alter this |
| * notice, a recipient may use your version of this file under either |
| * the MPL or the LGPL. |
| * |
| * You should have received a copy of the LGPL along with this library |
| * in the file COPYING-LGPL-2.1; if not, write to the Free Software |
| * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA |
| * You should have received a copy of the MPL along with this library |
| * in the file COPYING-MPL-1.1 |
| * |
| * The contents of this file are subject to the Mozilla Public License |
| * Version 1.1 (the "License"); you may not use this file except in |
| * compliance with the License. You may obtain a copy of the License at |
| * http://www.mozilla.org/MPL/ |
| * |
| * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY |
| * OF ANY KIND, either express or implied. See the LGPL or the MPL for |
| * the specific language governing rights and limitations. |
| * |
| * The Original Code is the cairo graphics library. |
| * |
| * The Initial Developer of the Original Code is Mozilla Foundation |
| * |
| * Contributor(s): |
| * Vladimir Vukicevic <vladimir@pobox.com> |
| */ |
| |
| #ifndef CAIRO_FIXED_PRIVATE_H |
| #define CAIRO_FIXED_PRIVATE_H |
| |
| #include "cairo-fixed-type-private.h" |
| |
| #include "cairo-wideint-private.h" |
| #include "cairoint.h" |
| |
| /* Implementation */ |
| |
| #if (CAIRO_FIXED_BITS != 32) |
| # error CAIRO_FIXED_BITS must be 32, and the type must be a 32-bit type. |
| # error To remove this limitation, you will have to fix the tessellator. |
| #endif |
| |
| #define CAIRO_FIXED_ONE ((cairo_fixed_t)(1 << CAIRO_FIXED_FRAC_BITS)) |
| #define CAIRO_FIXED_ONE_DOUBLE ((double)(1 << CAIRO_FIXED_FRAC_BITS)) |
| #define CAIRO_FIXED_EPSILON ((cairo_fixed_t)(1)) |
| |
| #define CAIRO_FIXED_ERROR_DOUBLE (1. / (2 * CAIRO_FIXED_ONE_DOUBLE)) |
| |
| #define CAIRO_FIXED_FRAC_MASK ((cairo_fixed_t)(((cairo_fixed_unsigned_t)(-1)) >> (CAIRO_FIXED_BITS - CAIRO_FIXED_FRAC_BITS))) |
| #define CAIRO_FIXED_WHOLE_MASK (~CAIRO_FIXED_FRAC_MASK) |
| |
| static inline cairo_fixed_t |
| _cairo_fixed_from_int (int i) |
| { |
| return i << CAIRO_FIXED_FRAC_BITS; |
| } |
| |
| /* This is the "magic number" approach to converting a double into fixed |
| * point as described here: |
| * |
| * http://www.stereopsis.com/sree/fpu2006.html (an overview) |
| * http://www.d6.com/users/checker/pdfs/gdmfp.pdf (in detail) |
| * |
| * The basic idea is to add a large enough number to the double that the |
| * literal floating point is moved up to the extent that it forces the |
| * double's value to be shifted down to the bottom of the mantissa (to make |
| * room for the large number being added in). Since the mantissa is, at a |
| * given moment in time, a fixed point integer itself, one can convert a |
| * float to various fixed point representations by moving around the point |
| * of a floating point number through arithmetic operations. This behavior |
| * is reliable on most modern platforms as it is mandated by the IEEE-754 |
| * standard for floating point arithmetic. |
| * |
| * For our purposes, a "magic number" must be carefully selected that is |
| * both large enough to produce the desired point-shifting effect, and also |
| * has no lower bits in its representation that would interfere with our |
| * value at the bottom of the mantissa. The magic number is calculated as |
| * follows: |
| * |
| * (2 ^ (MANTISSA_SIZE - FRACTIONAL_SIZE)) * 1.5 |
| * |
| * where in our case: |
| * - MANTISSA_SIZE for 64-bit doubles is 52 |
| * - FRACTIONAL_SIZE for 16.16 fixed point is 16 |
| * |
| * Although this approach provides a very large speedup of this function |
| * on a wide-array of systems, it does come with two caveats: |
| * |
| * 1) It uses banker's rounding as opposed to arithmetic rounding. |
| * 2) It doesn't function properly if the FPU is in single-precision |
| * mode. |
| */ |
| |
| /* The 16.16 number must always be available */ |
| #define CAIRO_MAGIC_NUMBER_FIXED_16_16 (103079215104.0) |
| |
| #if CAIRO_FIXED_BITS <= 32 |
| #define CAIRO_MAGIC_NUMBER_FIXED ((1LL << (52 - CAIRO_FIXED_FRAC_BITS)) * 1.5) |
| |
| /* For 32-bit fixed point numbers */ |
| static inline cairo_fixed_t |
| _cairo_fixed_from_double (double d) |
| { |
| union { |
| double d; |
| int32_t i[2]; |
| } u; |
| |
| u.d = d + CAIRO_MAGIC_NUMBER_FIXED; |
| #ifdef FLOAT_WORDS_BIGENDIAN |
| return u.i[1]; |
| #else |
| return u.i[0]; |
| #endif |
| } |
| |
| #else |
| # error Please define a magic number for your fixed point type! |
| # error See cairo-fixed-private.h for details. |
| #endif |
| |
| static inline cairo_fixed_t |
| _cairo_fixed_from_26_6 (uint32_t i) |
| { |
| #if CAIRO_FIXED_FRAC_BITS > 6 |
| return i << (CAIRO_FIXED_FRAC_BITS - 6); |
| #else |
| return i >> (6 - CAIRO_FIXED_FRAC_BITS); |
| #endif |
| } |
| |
| static inline cairo_fixed_t |
| _cairo_fixed_from_16_16 (uint32_t i) |
| { |
| #if CAIRO_FIXED_FRAC_BITS > 16 |
| return i << (CAIRO_FIXED_FRAC_BITS - 16); |
| #else |
| return i >> (16 - CAIRO_FIXED_FRAC_BITS); |
| #endif |
| } |
| |
| static inline double |
| _cairo_fixed_to_double (cairo_fixed_t f) |
| { |
| return ((double) f) / CAIRO_FIXED_ONE_DOUBLE; |
| } |
| |
| static inline int |
| _cairo_fixed_is_integer (cairo_fixed_t f) |
| { |
| return (f & CAIRO_FIXED_FRAC_MASK) == 0; |
| } |
| |
| static inline cairo_fixed_t |
| _cairo_fixed_floor (cairo_fixed_t f) |
| { |
| return f & ~CAIRO_FIXED_FRAC_MASK; |
| } |
| |
| static inline cairo_fixed_t |
| _cairo_fixed_ceil (cairo_fixed_t f) |
| { |
| return _cairo_fixed_floor (f + CAIRO_FIXED_FRAC_MASK); |
| } |
| |
| static inline cairo_fixed_t |
| _cairo_fixed_round (cairo_fixed_t f) |
| { |
| return _cairo_fixed_floor (f + (CAIRO_FIXED_FRAC_MASK+1)/2); |
| } |
| |
| static inline cairo_fixed_t |
| _cairo_fixed_round_down (cairo_fixed_t f) |
| { |
| return _cairo_fixed_floor (f + CAIRO_FIXED_FRAC_MASK/2); |
| } |
| |
| static inline int |
| _cairo_fixed_integer_part (cairo_fixed_t f) |
| { |
| return f >> CAIRO_FIXED_FRAC_BITS; |
| } |
| |
| static inline int |
| _cairo_fixed_integer_round (cairo_fixed_t f) |
| { |
| return _cairo_fixed_integer_part (f + (CAIRO_FIXED_FRAC_MASK+1)/2); |
| } |
| |
| static inline int |
| _cairo_fixed_integer_round_down (cairo_fixed_t f) |
| { |
| return _cairo_fixed_integer_part (f + CAIRO_FIXED_FRAC_MASK/2); |
| } |
| |
| static inline int |
| _cairo_fixed_fractional_part (cairo_fixed_t f) |
| { |
| return f & CAIRO_FIXED_FRAC_MASK; |
| } |
| |
| static inline int |
| _cairo_fixed_integer_floor (cairo_fixed_t f) |
| { |
| if (f >= 0) |
| return f >> CAIRO_FIXED_FRAC_BITS; |
| else |
| return -((-f - 1) >> CAIRO_FIXED_FRAC_BITS) - 1; |
| } |
| |
| static inline int |
| _cairo_fixed_integer_ceil (cairo_fixed_t f) |
| { |
| if (f > 0) |
| return ((f - 1)>>CAIRO_FIXED_FRAC_BITS) + 1; |
| else |
| return - (-f >> CAIRO_FIXED_FRAC_BITS); |
| } |
| |
| /* A bunch of explicit 16.16 operators; we need these |
| * to interface with pixman and other backends that require |
| * 16.16 fixed point types. |
| */ |
| static inline cairo_fixed_16_16_t |
| _cairo_fixed_to_16_16 (cairo_fixed_t f) |
| { |
| #if (CAIRO_FIXED_FRAC_BITS == 16) && (CAIRO_FIXED_BITS == 32) |
| return f; |
| #elif CAIRO_FIXED_FRAC_BITS > 16 |
| /* We're just dropping the low bits, so we won't ever got over/underflow here */ |
| return f >> (CAIRO_FIXED_FRAC_BITS - 16); |
| #else |
| cairo_fixed_16_16_t x; |
| |
| /* Handle overflow/underflow by clamping to the lowest/highest |
| * value representable as 16.16 |
| */ |
| if ((f >> CAIRO_FIXED_FRAC_BITS) < INT16_MIN) { |
| x = INT32_MIN; |
| } else if ((f >> CAIRO_FIXED_FRAC_BITS) > INT16_MAX) { |
| x = INT32_MAX; |
| } else { |
| x = f << (16 - CAIRO_FIXED_FRAC_BITS); |
| } |
| |
| return x; |
| #endif |
| } |
| |
| static inline cairo_fixed_16_16_t |
| _cairo_fixed_16_16_from_double (double d) |
| { |
| union { |
| double d; |
| int32_t i[2]; |
| } u; |
| |
| u.d = d + CAIRO_MAGIC_NUMBER_FIXED_16_16; |
| #ifdef FLOAT_WORDS_BIGENDIAN |
| return u.i[1]; |
| #else |
| return u.i[0]; |
| #endif |
| } |
| |
| static inline int |
| _cairo_fixed_16_16_floor (cairo_fixed_16_16_t f) |
| { |
| if (f >= 0) |
| return f >> 16; |
| else |
| return -((-f - 1) >> 16) - 1; |
| } |
| |
| static inline double |
| _cairo_fixed_16_16_to_double (cairo_fixed_16_16_t f) |
| { |
| return ((double) f) / (double) (1 << 16); |
| } |
| |
| #if CAIRO_FIXED_BITS == 32 |
| |
| static inline cairo_fixed_t |
| _cairo_fixed_mul (cairo_fixed_t a, cairo_fixed_t b) |
| { |
| cairo_int64_t temp = _cairo_int32x32_64_mul (a, b); |
| return _cairo_int64_to_int32(_cairo_int64_rsl (temp, CAIRO_FIXED_FRAC_BITS)); |
| } |
| |
| /* computes round (a * b / c) */ |
| static inline cairo_fixed_t |
| _cairo_fixed_mul_div (cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c) |
| { |
| cairo_int64_t ab = _cairo_int32x32_64_mul (a, b); |
| cairo_int64_t c64 = _cairo_int32_to_int64 (c); |
| return _cairo_int64_to_int32 (_cairo_int64_divrem (ab, c64).quo); |
| } |
| |
| /* computes floor (a * b / c) */ |
| static inline cairo_fixed_t |
| _cairo_fixed_mul_div_floor (cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c) |
| { |
| return _cairo_int64_32_div (_cairo_int32x32_64_mul (a, b), c); |
| } |
| |
| /* compute y from x so that (x,y), p1, and p2 are collinear */ |
| static inline cairo_fixed_t |
| _cairo_edge_compute_intersection_y_for_x (const cairo_point_t *p1, |
| const cairo_point_t *p2, |
| cairo_fixed_t x) |
| { |
| cairo_fixed_t y, dx; |
| |
| if (x == p1->x) |
| return p1->y; |
| if (x == p2->x) |
| return p2->y; |
| |
| y = p1->y; |
| dx = p2->x - p1->x; |
| if (dx != 0) |
| y += _cairo_fixed_mul_div_floor (x - p1->x, p2->y - p1->y, dx); |
| |
| return y; |
| } |
| |
| /* compute x from y so that (x,y), p1, and p2 are collinear */ |
| static inline cairo_fixed_t |
| _cairo_edge_compute_intersection_x_for_y (const cairo_point_t *p1, |
| const cairo_point_t *p2, |
| cairo_fixed_t y) |
| { |
| cairo_fixed_t x, dy; |
| |
| if (y == p1->y) |
| return p1->x; |
| if (y == p2->y) |
| return p2->x; |
| |
| x = p1->x; |
| dy = p2->y - p1->y; |
| if (dy != 0) |
| x += _cairo_fixed_mul_div_floor (y - p1->y, p2->x - p1->x, dy); |
| |
| return x; |
| } |
| |
| /* Intersect two segments based on the algorithm described at |
| * http://paulbourke.net/geometry/pointlineplane/. This implementation |
| * uses floating point math. */ |
| static inline 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) |
| { |
| double denominator, u_a, u_b; |
| double seg1_dx, seg1_dy, seg2_dx, seg2_dy, seg_start_dx, seg_start_dy; |
| |
| seg1_dx = _cairo_fixed_to_double (seg1_p2->x - seg1_p1->x); |
| seg1_dy = _cairo_fixed_to_double (seg1_p2->y - seg1_p1->y); |
| seg2_dx = _cairo_fixed_to_double (seg2_p2->x - seg2_p1->x); |
| seg2_dy = _cairo_fixed_to_double (seg2_p2->y - seg2_p1->y); |
| denominator = (seg2_dy * seg1_dx) - (seg2_dx * seg1_dy); |
| if (denominator == 0) |
| return FALSE; |
| |
| seg_start_dx = _cairo_fixed_to_double (seg1_p1->x - seg2_p1->x); |
| seg_start_dy = _cairo_fixed_to_double (seg1_p1->y - seg2_p1->y); |
| u_a = ((seg2_dx * seg_start_dy) - (seg2_dy * seg_start_dx)) / denominator; |
| u_b = ((seg1_dx * seg_start_dy) - (seg1_dy * seg_start_dx)) / denominator; |
| |
| if (u_a <= 0 || u_a >= 1 || u_b <= 0 || u_b >= 1) |
| return FALSE; |
| |
| intersection->x = seg1_p1->x + _cairo_fixed_from_double ((u_a * seg1_dx)); |
| intersection->y = seg1_p1->y + _cairo_fixed_from_double ((u_a * seg1_dy)); |
| return TRUE; |
| } |
| |
| #else |
| # error Please define multiplication and other operands for your fixed-point type size |
| #endif |
| |
| #endif /* CAIRO_FIXED_PRIVATE_H */ |