geometry.h

Go to the documentation of this file.

// Copyright (C) 2004-2025 Artifex Software, Inc.
//
// This file is part of MuPDF.
//
// MuPDF is free software: you can redistribute it and/or modify it under the
// terms of the GNU Affero General Public License as published by the Free
// Software Foundation, either version 3 of the License, or (at your option)
// any later version.
//
// MuPDF is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
// FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
// details.
//
// You should have received a copy of the GNU Affero General Public License
// along with MuPDF. If not, see <https://www.gnu.org/licenses/agpl-3.0.en.html>
//
// Alternative licensing terms are available from the licensor.
// For commercial licensing, see <https://www.artifex.com/> or contact
// Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,
// CA 94129, USA, for further information.
 
#ifndef MUPDF_FITZ_MATH_H
#define MUPDF_FITZ_MATH_H
 
#include "mupdf/fitz/system.h"
 
#include <math.h>
#include <assert.h>
 
#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif

static inline int fz_mul255(int a, int b)
{
    /* see Jim Blinn's book "Dirty Pixels" for how this works */
    int x = a * b + 128;
    x += x >> 8;
    return x >> 8;
}

static inline int fz_div255(int c, int a)
{
    return a ? c * (255 * 256 / a) >> 8 : 0;
}

#define FZ_EXPAND(A) ((A)+((A)>>7))

#define FZ_COMBINE(A,B) (((A)*(B))>>8)

#define FZ_COMBINE2(A,B,C,D) (((A) * (B) + (C) * (D))>>8)

#define FZ_BLEND(SRC, DST, AMOUNT) ((((SRC)-(DST))*(AMOUNT) + ((DST)<<8))>>8)

float fz_atof(const char *s);

int fz_atoi(const char *s);

int64_t fz_atoi64(const char *s);

size_t fz_atoz(const char *s);

static inline float fz_abs(float f)
{
    return (f < 0 ? -f : f);
}
 
static inline int fz_absi(int i)
{
    return (i < 0 ? -i : i);
}
 
static inline float fz_min(float a, float b)
{
    return (a < b ? a : b);
}
 
static inline int fz_mini(int a, int b)
{
    return (a < b ? a : b);
}
 
static inline size_t fz_minz(size_t a, size_t b)
{
    return (a < b ? a : b);
}
 
static inline int64_t fz_mini64(int64_t a, int64_t b)
{
    return (a < b ? a : b);
}
 
static inline float fz_max(float a, float b)
{
    return (a > b ? a : b);
}
 
static inline int fz_maxi(int a, int b)
{
    return (a > b ? a : b);
}
 
static inline size_t fz_maxz(size_t a, size_t b)
{
    return (a > b ? a : b);
}
 
static inline int64_t fz_maxi64(int64_t a, int64_t b)
{
    return (a > b ? a : b);
}
 
static inline float fz_clamp(float x, float min, float max)
{
    return x < min ? min : x > max ? max : x;
}
 
static inline int fz_clampi(int x, int min, int max)
{
    return x < min ? min : x > max ? max : x;
}
 
static inline int64_t fz_clamp64(int64_t x, int64_t min, int64_t max)
{
    return x < min ? min : x > max ? max : x;
}
 
static inline double fz_clampd(double x, double min, double max)
{
    return x < min ? min : x > max ? max : x;
}
 
static inline void *fz_clampp(void *x, void *min, void *max)
{
    return x < min ? min : x > max ? max : x;
}
 
#define DIV_BY_ZERO(a, b, min, max) (((a) < 0) ^ ((b) < 0) ? (min) : (max))

typedef struct
{
    float x, y;
} fz_point;
 
static inline fz_point fz_make_point(float x, float y)
{
    fz_point p = { x, y };
    return p;
}

#define FZ_MIN_INF_RECT ((int)0x80000000)
#define FZ_MAX_INF_RECT ((int)0x7fffff80)
 
typedef struct
{
    float x0, y0;
    float x1, y1;
} fz_rect;
 
static inline fz_rect fz_make_rect(float x0, float y0, float x1, float y1)
{
    fz_rect r = { x0, y0, x1, y1 };
    return r;
}

typedef struct
{
    int x0, y0;
    int x1, y1;
} fz_irect;
 
static inline fz_irect fz_make_irect(int x0, int y0, int x1, int y1)
{
    fz_irect r = { x0, y0, x1, y1 };
    return r;
}

FZ_DATA extern const fz_rect fz_unit_rect;

FZ_DATA extern const fz_rect fz_empty_rect;
FZ_DATA extern const fz_irect fz_empty_irect;

FZ_DATA extern const fz_rect fz_infinite_rect;
FZ_DATA extern const fz_irect fz_infinite_irect;

FZ_DATA extern const fz_rect fz_invalid_rect;
FZ_DATA extern const fz_irect fz_invalid_irect;

static inline int fz_is_empty_rect(fz_rect r)
{
    return (r.x0 >= r.x1 || r.y0 >= r.y1);
}
 
static inline int fz_is_empty_irect(fz_irect r)
{
    return (r.x0 >= r.x1 || r.y0 >= r.y1);
}

static inline int fz_is_infinite_rect(fz_rect r)
{
    return (r.x0 == FZ_MIN_INF_RECT && r.x1 == FZ_MAX_INF_RECT &&
        r.y0 == FZ_MIN_INF_RECT && r.y1 == FZ_MAX_INF_RECT);
}

static inline int fz_is_infinite_irect(fz_irect r)
{
    return (r.x0 == FZ_MIN_INF_RECT && r.x1 == FZ_MAX_INF_RECT &&
        r.y0 == FZ_MIN_INF_RECT && r.y1 == FZ_MAX_INF_RECT);
}

static inline int fz_is_valid_rect(fz_rect r)
{
    return (r.x0 <= r.x1 && r.y0 <= r.y1);
}

static inline int fz_is_valid_irect(fz_irect r)
{
    return (r.x0 <= r.x1 && r.y0 <= r.y1);
}

static inline unsigned int
fz_irect_width(fz_irect r)
{
    unsigned int w;
    if (r.x0 >= r.x1)
        return 0;
    /* Check for w overflowing. This should never happen, but
     * if it does, it's pretty likely an indication of a severe
     * problem. */
    w = (unsigned int)r.x1 - r.x0;
    assert((int)w >= 0);
    if ((int)w < 0)
        return 0;
    return (int)w;
}

static inline int
fz_irect_height(fz_irect r)
{
    unsigned int h;
    if (r.y0 >= r.y1)
        return 0;
    /* Check for h overflowing. This should never happen, but
     * if it does, it's pretty likely an indication of a severe
     * problem. */
    h = (unsigned int)(r.y1 - r.y0);
    assert((int)h >= 0);
    if ((int)h < 0)
        return 0;
    return (int)h;
}

typedef struct
{
    float a, b, c, d, e, f;
} fz_matrix;

FZ_DATA extern const fz_matrix fz_identity;
 
static inline fz_matrix fz_make_matrix(float a, float b, float c, float d, float e, float f)
{
    fz_matrix m = { a, b, c, d, e, f };
    return m;
}
 
static inline int fz_is_identity(fz_matrix m)
{
    return m.a == 1 && m.b == 0 && m.c == 0 && m.d == 1 && m.e == 0 && m.f == 0;
}

fz_matrix fz_concat(fz_matrix left, fz_matrix right);

fz_matrix fz_scale(float sx, float sy);

fz_matrix fz_pre_scale(fz_matrix m, float sx, float sy);

fz_matrix fz_post_scale(fz_matrix m, float sx, float sy);

fz_matrix fz_shear(float sx, float sy);

fz_matrix fz_pre_shear(fz_matrix m, float sx, float sy);

fz_matrix fz_rotate(float degrees);

fz_matrix fz_pre_rotate(fz_matrix m, float degrees);

fz_matrix fz_translate(float tx, float ty);

fz_matrix fz_pre_translate(fz_matrix m, float tx, float ty);

fz_matrix fz_transform_page(fz_rect mediabox, float resolution, float rotate);

fz_matrix fz_invert_matrix(fz_matrix matrix);

int fz_try_invert_matrix(fz_matrix *inv, fz_matrix src);

int fz_is_rectilinear(fz_matrix m);

float fz_matrix_expansion(fz_matrix m);

fz_rect fz_intersect_rect(fz_rect a, fz_rect b);

fz_irect fz_intersect_irect(fz_irect a, fz_irect b);

fz_rect fz_union_rect(fz_rect a, fz_rect b);

fz_irect fz_irect_from_rect(fz_rect rect);

fz_irect fz_round_rect(fz_rect rect);

fz_rect fz_rect_from_irect(fz_irect bbox);

fz_rect fz_expand_rect(fz_rect b, float expand);
fz_irect fz_expand_irect(fz_irect a, int expand);

float fz_rect_area(fz_rect r);

fz_rect fz_include_point_in_rect(fz_rect r, fz_point p);

fz_rect fz_translate_rect(fz_rect a, float xoff, float yoff);
fz_irect fz_translate_irect(fz_irect a, int xoff, int yoff);

int fz_contains_rect(fz_rect a, fz_rect b);

int fz_overlaps_rect(fz_rect a, fz_rect b);

fz_point fz_transform_point(fz_point point, fz_matrix m);
fz_point fz_transform_point_xy(float x, float y, fz_matrix m);

fz_point fz_transform_vector(fz_point vector, fz_matrix m);

fz_rect fz_transform_rect(fz_rect rect, fz_matrix m);

fz_point fz_normalize_vector(fz_point p);

fz_matrix fz_gridfit_matrix(int as_tiled, fz_matrix m);

float fz_matrix_max_expansion(fz_matrix m);

typedef struct
{
    fz_point ul, ur, ll, lr;
} fz_quad;

static inline fz_quad fz_make_quad(
    float ul_x, float ul_y,
    float ur_x, float ur_y,
    float ll_x, float ll_y,
    float lr_x, float lr_y)
{
    fz_quad q = {
        { ul_x, ul_y },
        { ur_x, ur_y },
        { ll_x, ll_y },
        { lr_x, lr_y },
    };
    return q;
}
 
FZ_DATA extern const fz_quad fz_invalid_quad;
FZ_DATA extern const fz_quad fz_infinite_quad;

int fz_is_valid_quad(fz_quad q);

int fz_is_empty_quad(fz_quad q);

int fz_is_infinite_quad(fz_quad q);

fz_quad fz_quad_from_rect(fz_rect r);

fz_rect fz_rect_from_quad(fz_quad q);

fz_quad fz_transform_quad(fz_quad q, fz_matrix m);

int fz_is_point_inside_quad(fz_point p, fz_quad q);

int fz_is_point_inside_rect(fz_point p, fz_rect r);

int fz_is_point_inside_irect(int x, int y, fz_irect r);

int fz_is_rect_inside_rect(fz_rect inner, fz_rect outer);

int fz_is_irect_inside_irect(fz_irect inner, fz_irect outer);

int fz_is_quad_inside_quad(fz_quad needle, fz_quad haystack);

int fz_is_quad_intersecting_quad(fz_quad a, fz_quad b);
 
/* Checked integer arithmetic helpers -- return whether operation succeeded without overflow or underflow. */
/* Use builtin C23 ckd_mul, ckd_add, ckd_sub if available. */
 
#ifdef HAVE_STDCKDINT_H
 
#include <stdckdint.h>
 
/* We add explicit casts here to ensure that these match the non-C23 cases below. */
#define fz_ckd_mul_i32(O,A,B) ckd_mul(O,(int32_t)(A),(int32_t)(B))
#define fz_ckd_mul_u32(O,A,B) ckd_mul(O,(uint32_t)(A),(uint32_t)(B))
#define fz_ckd_mul_int(O,A,B) ckd_mul(O,(int)(A),(int)(B))
#define fz_ckd_mul_uint(O,A,B) ckd_mul(O,(unsigned int)(A),(unsigned int)(B))
#define fz_ckd_mul_size(O,A,B) ckd_mul(O,(size_t)(A),(size_t)(B))
#define fz_ckd_mul_i64(O,A,B) ckd_mul(O,(int64_t)(A),(int64_t)(B))
#define fz_ckd_mul_u64(O,A,B) ckd_mul(O,(uint64_t)(A),(uint64_t)(B))
 
#define fz_ckd_add_i32(O,A,B) ckd_add(O,(int32_t)(A),(int32_t)(B))
#define fz_ckd_add_u32(O,A,B) ckd_add(O,(uint32_t)(A),(uint32_t)(B))
#define fz_ckd_add_int(O,A,B) ckd_add(O,(int)(A),(int)(B))
#define fz_ckd_add_uint(O,A,B) ckd_add(O,(unsigned int)(A),(unsigned int)(B))
#define fz_ckd_add_size(O,A,B) ckd_add(O,(size_t)(A),(size_t)(B))
#define fz_ckd_add_i64(O,A,B) ckd_add(O,(int64_t)(A),(int64_t)(B))
#define fz_ckd_add_u64(O,A,B) ckd_add(O,(uint64_t)(A),(uint64_t)(B))
 
#define fz_ckd_sub_i32(O,A,B) ckd_sub(O,(int32_t)(A),(int32_t)(B))
#define fz_ckd_sub_u32(O,A,B) ckd_sub(O,(uint32_t)(A),(uint32_t)(B))
#define fz_ckd_sub_int(O,A,B) ckd_sub(O,(int)(A),(int)(B))
#define fz_ckd_sub_uint(O,A,B) ckd_sub(O,(unsigned int)(A),(unsigned int)(B))
#define fz_ckd_sub_size(O,A,B) ckd_sub(O,(size_t)(A),(size_t)(B))
#define fz_ckd_sub_i64(O,A,B) ckd_sub(O,(int64_t)(A),(int64_t)(B))
#define fz_ckd_sub_u64(O,A,B) ckd_sub(O,(uint64_t)(A),(uint64_t)(B))
 
#else
 
int fz_ckd_mul_i32(int32_t *out, int32_t a, int32_t b);
int fz_ckd_add_i32(int32_t *out, int32_t a, int32_t b);
int fz_ckd_sub_i32(int32_t *out, int32_t a, int32_t b);
 
int fz_ckd_mul_u32(uint32_t *out, uint32_t a, uint32_t b);
int fz_ckd_add_u32(uint32_t *out, uint32_t a, uint32_t b);
int fz_ckd_sub_u32(uint32_t *out, uint32_t a, uint32_t b);
 
int fz_ckd_mul_int(int *out, int a, int b);
int fz_ckd_add_int(int *out, int a, int b);
int fz_ckd_sub_int(int *out, int a, int b);
 
int fz_ckd_mul_uint(unsigned int *out, unsigned int a, unsigned int b);
int fz_ckd_add_uint(unsigned int *out, unsigned int a, unsigned int b);
int fz_ckd_sub_uint(unsigned int *out, unsigned int a, unsigned int b);
 
int fz_ckd_mul_size(size_t *out, size_t a, size_t b);
int fz_ckd_add_size(size_t *out, size_t a, size_t b);
int fz_ckd_sub_size(size_t *out, size_t a, size_t b);
 
int fz_ckd_mul_i64(int64_t *out, int64_t a, int64_t b);
int fz_ckd_add_i64(int64_t *out, int64_t a, int64_t b);
int fz_ckd_sub_i64(int64_t *out, int64_t a, int64_t b);
 
int fz_ckd_mul_u64(uint64_t *out, uint64_t a, uint64_t b);
int fz_ckd_add_u64(uint64_t *out, uint64_t a, uint64_t b);
int fz_ckd_sub_u64(uint64_t *out, uint64_t a, uint64_t b);
 
#endif
 
#define fz_bytes_from_bits(A)  (((A)>>3) + !!((A) & 7))
 
int fz_ckd_size_from_i64(size_t *out, int64_t in);
int fz_ckd_int_from_i64(int *out, int64_t in);
 
#endif