1 #ifndef MUPDF_FITZ_MATH_H
2 #define MUPDF_FITZ_MATH_H
3
4 #include "mupdf/fitz/system.h"
5
6 /**
7 Multiply scaled two integers in the 0..255 range
8 */
fz_mul255(int a,int b)9 static inline int fz_mul255(int a, int b)
10 {
11 /* see Jim Blinn's book "Dirty Pixels" for how this works */
12 int x = a * b + 128;
13 x += x >> 8;
14 return x >> 8;
15 }
16
17 /**
18 Undo alpha premultiplication.
19 */
fz_div255(int c,int a)20 static inline int fz_div255(int c, int a)
21 {
22 return a ? c * (255 * 256 / a) >> 8 : 0;
23 }
24
25 /**
26 Expand a value A from the 0...255 range to the 0..256 range
27 */
28 #define FZ_EXPAND(A) ((A)+((A)>>7))
29
30 /**
31 Combine values A (in any range) and B (in the 0..256 range),
32 to give a single value in the same range as A was.
33 */
34 #define FZ_COMBINE(A,B) (((A)*(B))>>8)
35
36 /**
37 Combine values A and C (in the same (any) range) and B and D (in
38 the 0..256 range), to give a single value in the same range as A
39 and C were.
40 */
41 #define FZ_COMBINE2(A,B,C,D) (((A) * (B) + (C) * (D))>>8)
42
43 /**
44 Blend SRC and DST (in the same range) together according to
45 AMOUNT (in the 0...256 range).
46 */
47 #define FZ_BLEND(SRC, DST, AMOUNT) ((((SRC)-(DST))*(AMOUNT) + ((DST)<<8))>>8)
48
49 /**
50 Range checking atof
51 */
52 float fz_atof(const char *s);
53
54 /**
55 atoi that copes with NULL
56 */
57 int fz_atoi(const char *s);
58
59 /**
60 64bit atoi that copes with NULL
61 */
62 int64_t fz_atoi64(const char *s);
63
64 /**
65 Some standard math functions, done as static inlines for speed.
66 People with compilers that do not adequately implement inline
67 may like to reimplement these using macros.
68 */
fz_abs(float f)69 static inline float fz_abs(float f)
70 {
71 return (f < 0 ? -f : f);
72 }
73
fz_absi(int i)74 static inline int fz_absi(int i)
75 {
76 return (i < 0 ? -i : i);
77 }
78
fz_min(float a,float b)79 static inline float fz_min(float a, float b)
80 {
81 return (a < b ? a : b);
82 }
83
fz_mini(int a,int b)84 static inline int fz_mini(int a, int b)
85 {
86 return (a < b ? a : b);
87 }
88
fz_minz(size_t a,size_t b)89 static inline size_t fz_minz(size_t a, size_t b)
90 {
91 return (a < b ? a : b);
92 }
93
fz_max(float a,float b)94 static inline float fz_max(float a, float b)
95 {
96 return (a > b ? a : b);
97 }
98
fz_maxi(int a,int b)99 static inline int fz_maxi(int a, int b)
100 {
101 return (a > b ? a : b);
102 }
103
fz_maxz(size_t a,size_t b)104 static inline size_t fz_maxz(size_t a, size_t b)
105 {
106 return (a > b ? a : b);
107 }
108
fz_maxi64(int64_t a,int64_t b)109 static inline int64_t fz_maxi64(int64_t a, int64_t b)
110 {
111 return (a > b ? a : b);
112 }
113
fz_clamp(float f,float min,float max)114 static inline float fz_clamp(float f, float min, float max)
115 {
116 return (f > min ? (f < max ? f : max) : min);
117 }
118
fz_clampi(int i,int min,int max)119 static inline int fz_clampi(int i, int min, int max)
120 {
121 return (i > min ? (i < max ? i : max) : min);
122 }
123
fz_clampd(double d,double min,double max)124 static inline double fz_clampd(double d, double min, double max)
125 {
126 return (d > min ? (d < max ? d : max) : min);
127 }
128
fz_clampp(void * p,void * min,void * max)129 static inline void *fz_clampp(void *p, void *min, void *max)
130 {
131 return (p > min ? (p < max ? p : max) : min);
132 }
133
134 #define DIV_BY_ZERO(a, b, min, max) (((a) < 0) ^ ((b) < 0) ? (min) : (max))
135
136 /**
137 fz_point is a point in a two-dimensional space.
138 */
139 typedef struct
140 {
141 float x, y;
142 } fz_point;
143
fz_make_point(float x,float y)144 static inline fz_point fz_make_point(float x, float y)
145 {
146 fz_point p = { x, y };
147 return p;
148 }
149
150 /**
151 fz_rect is a rectangle represented by two diagonally opposite
152 corners at arbitrary coordinates.
153
154 Rectangles are always axis-aligned with the X- and Y- axes.
155 The relationship between the coordinates are that x0 <= x1 and
156 y0 <= y1 in all cases except for infinite rectangles. The area
157 of a rectangle is defined as (x1 - x0) * (y1 - y0). If either
158 x0 > x1 or y0 > y1 is true for a given rectangle then it is
159 defined to be infinite.
160
161 To check for empty or infinite rectangles use fz_is_empty_rect
162 and fz_is_infinite_rect.
163
164 x0, y0: The top left corner.
165
166 x1, y1: The bottom right corner.
167 */
168 typedef struct
169 {
170 float x0, y0;
171 float x1, y1;
172 } fz_rect;
173
fz_make_rect(float x0,float y0,float x1,float y1)174 static inline fz_rect fz_make_rect(float x0, float y0, float x1, float y1)
175 {
176 fz_rect r = { x0, y0, x1, y1 };
177 return r;
178 }
179
180 /**
181 fz_irect is a rectangle using integers instead of floats.
182
183 It's used in the draw device and for pixmap dimensions.
184 */
185 typedef struct
186 {
187 int x0, y0;
188 int x1, y1;
189 } fz_irect;
190
fz_make_irect(int x0,int y0,int x1,int y1)191 static inline fz_irect fz_make_irect(int x0, int y0, int x1, int y1)
192 {
193 fz_irect r = { x0, y0, x1, y1 };
194 return r;
195 }
196
197 /**
198 A rectangle with sides of length one.
199
200 The bottom left corner is at (0, 0) and the top right corner
201 is at (1, 1).
202 */
203 extern const fz_rect fz_unit_rect;
204
205 /**
206 An empty rectangle with an area equal to zero.
207
208 Both the top left and bottom right corner are at (0, 0).
209 */
210 extern const fz_rect fz_empty_rect;
211 extern const fz_irect fz_empty_irect;
212
213 /**
214 An infinite rectangle with negative area.
215
216 The corner (x0, y0) is at (1, 1) while the corner (x1, y1) is
217 at (-1, -1).
218 */
219 extern const fz_rect fz_infinite_rect;
220 extern const fz_irect fz_infinite_irect;
221
222 /**
223 Check if rectangle is empty.
224
225 An empty rectangle is defined as one whose area is zero.
226 */
fz_is_empty_rect(fz_rect r)227 static inline int fz_is_empty_rect(fz_rect r)
228 {
229 return (r.x0 == r.x1 || r.y0 == r.y1);
230 }
231
fz_is_empty_irect(fz_irect r)232 static inline int fz_is_empty_irect(fz_irect r)
233 {
234 return (r.x0 == r.x1 || r.y0 == r.y1);
235 }
236
237 /**
238 Check if rectangle is infinite.
239
240 An infinite rectangle is defined as one where either of the
241 two relationships between corner coordinates are not true.
242 */
fz_is_infinite_rect(fz_rect r)243 static inline int fz_is_infinite_rect(fz_rect r)
244 {
245 return (r.x0 > r.x1 || r.y0 > r.y1);
246 }
247
248 /**
249 Check if an integer rectangle
250 is infinite.
251
252 An infinite rectangle is defined as one where either of the
253 two relationships between corner coordinates are not true.
254 */
fz_is_infinite_irect(fz_irect r)255 static inline int fz_is_infinite_irect(fz_irect r)
256 {
257 return (r.x0 > r.x1 || r.y0 > r.y1);
258 }
259
260 /**
261 fz_matrix is a row-major 3x3 matrix used for representing
262 transformations of coordinates throughout MuPDF.
263
264 Since all points reside in a two-dimensional space, one vector
265 is always a constant unit vector; hence only some elements may
266 vary in a matrix. Below is how the elements map between
267 different representations.
268
269 / a b 0 \
270 | c d 0 | normally represented as [ a b c d e f ].
271 \ e f 1 /
272 */
273 typedef struct
274 {
275 float a, b, c, d, e, f;
276 } fz_matrix;
277
278 /**
279 Identity transform matrix.
280 */
281 extern const fz_matrix fz_identity;
282
fz_make_matrix(float a,float b,float c,float d,float e,float f)283 static inline fz_matrix fz_make_matrix(float a, float b, float c, float d, float e, float f)
284 {
285 fz_matrix m = { a, b, c, d, e, f };
286 return m;
287 }
288
fz_is_identity(fz_matrix m)289 static inline int fz_is_identity(fz_matrix m)
290 {
291 return m.a == 1 && m.b == 0 && m.c == 0 && m.d == 1 && m.e == 0 && m.f == 0;
292 }
293
294 /**
295 Multiply two matrices.
296
297 The order of the two matrices are important since matrix
298 multiplication is not commutative.
299
300 Returns result.
301 */
302 fz_matrix fz_concat(fz_matrix left, fz_matrix right);
303
304 /**
305 Create a scaling matrix.
306
307 The returned matrix is of the form [ sx 0 0 sy 0 0 ].
308
309 m: Pointer to the matrix to populate
310
311 sx, sy: Scaling factors along the X- and Y-axes. A scaling
312 factor of 1.0 will not cause any scaling along the relevant
313 axis.
314
315 Returns m.
316 */
317 fz_matrix fz_scale(float sx, float sy);
318
319 /**
320 Scale a matrix by premultiplication.
321
322 m: Pointer to the matrix to scale
323
324 sx, sy: Scaling factors along the X- and Y-axes. A scaling
325 factor of 1.0 will not cause any scaling along the relevant
326 axis.
327
328 Returns m (updated).
329 */
330 fz_matrix fz_pre_scale(fz_matrix m, float sx, float sy);
331
332 /**
333 Scale a matrix by postmultiplication.
334
335 m: Pointer to the matrix to scale
336
337 sx, sy: Scaling factors along the X- and Y-axes. A scaling
338 factor of 1.0 will not cause any scaling along the relevant
339 axis.
340
341 Returns m (updated).
342 */
343 fz_matrix fz_post_scale(fz_matrix m, float sx, float sy);
344
345 /**
346 Create a shearing matrix.
347
348 The returned matrix is of the form [ 1 sy sx 1 0 0 ].
349
350 m: pointer to place to store returned matrix
351
352 sx, sy: Shearing factors. A shearing factor of 0.0 will not
353 cause any shearing along the relevant axis.
354
355 Returns m.
356 */
357 fz_matrix fz_shear(float sx, float sy);
358
359 /**
360 Premultiply a matrix with a shearing matrix.
361
362 The shearing matrix is of the form [ 1 sy sx 1 0 0 ].
363
364 m: pointer to matrix to premultiply
365
366 sx, sy: Shearing factors. A shearing factor of 0.0 will not
367 cause any shearing along the relevant axis.
368
369 Returns m (updated).
370 */
371 fz_matrix fz_pre_shear(fz_matrix m, float sx, float sy);
372
373 /**
374 Create a rotation matrix.
375
376 The returned matrix is of the form
377 [ cos(deg) sin(deg) -sin(deg) cos(deg) 0 0 ].
378
379 m: Pointer to place to store matrix
380
381 degrees: Degrees of counter clockwise rotation. Values less
382 than zero and greater than 360 are handled as expected.
383
384 Returns m.
385 */
386 fz_matrix fz_rotate(float degrees);
387
388 /**
389 Rotate a transformation by premultiplying.
390
391 The premultiplied matrix is of the form
392 [ cos(deg) sin(deg) -sin(deg) cos(deg) 0 0 ].
393
394 m: Pointer to matrix to premultiply.
395
396 degrees: Degrees of counter clockwise rotation. Values less
397 than zero and greater than 360 are handled as expected.
398
399 Returns m (updated).
400 */
401 fz_matrix fz_pre_rotate(fz_matrix m, float degrees);
402
403 /**
404 Create a translation matrix.
405
406 The returned matrix is of the form [ 1 0 0 1 tx ty ].
407
408 m: A place to store the created matrix.
409
410 tx, ty: Translation distances along the X- and Y-axes. A
411 translation of 0 will not cause any translation along the
412 relevant axis.
413
414 Returns m.
415 */
416 fz_matrix fz_translate(float tx, float ty);
417
418 /**
419 Translate a matrix by premultiplication.
420
421 m: The matrix to translate
422
423 tx, ty: Translation distances along the X- and Y-axes. A
424 translation of 0 will not cause any translation along the
425 relevant axis.
426
427 Returns m.
428 */
429 fz_matrix fz_pre_translate(fz_matrix m, float tx, float ty);
430
431 /**
432 Create transform matrix to draw page
433 at a given resolution and rotation. Adjusts the scaling
434 factors so that the page covers whole number of
435 pixels and adjust the page origin to be at 0,0.
436 */
437 fz_matrix fz_transform_page(fz_rect mediabox, float resolution, float rotate);
438
439 /**
440 Create an inverse matrix.
441
442 inverse: Place to store inverse matrix.
443
444 matrix: Matrix to invert. A degenerate matrix, where the
445 determinant is equal to zero, can not be inverted and the
446 original matrix is returned instead.
447
448 Returns inverse.
449 */
450 fz_matrix fz_invert_matrix(fz_matrix matrix);
451
452 /**
453 Attempt to create an inverse matrix.
454
455 inverse: Place to store inverse matrix.
456
457 matrix: Matrix to invert. A degenerate matrix, where the
458 determinant is equal to zero, can not be inverted.
459
460 Returns 1 if matrix is degenerate (singular), or 0 otherwise.
461 */
462 int fz_try_invert_matrix(fz_matrix *inv, fz_matrix src);
463
464 /**
465 Check if a transformation is rectilinear.
466
467 Rectilinear means that no shearing is present and that any
468 rotations present are a multiple of 90 degrees. Usually this
469 is used to make sure that axis-aligned rectangles before the
470 transformation are still axis-aligned rectangles afterwards.
471 */
472 int fz_is_rectilinear(fz_matrix m);
473
474 /**
475 Calculate average scaling factor of matrix.
476 */
477 float fz_matrix_expansion(fz_matrix m);
478
479 /**
480 Compute intersection of two rectangles.
481
482 Given two rectangles, update the first to be the smallest
483 axis-aligned rectangle that covers the area covered by both
484 given rectangles. If either rectangle is empty then the
485 intersection is also empty. If either rectangle is infinite
486 then the intersection is simply the non-infinite rectangle.
487 Should both rectangles be infinite, then the intersection is
488 also infinite.
489 */
490 fz_rect fz_intersect_rect(fz_rect a, fz_rect b);
491
492 /**
493 Compute intersection of two bounding boxes.
494
495 Similar to fz_intersect_rect but operates on two bounding
496 boxes instead of two rectangles.
497 */
498 fz_irect fz_intersect_irect(fz_irect a, fz_irect b);
499
500 /**
501 Compute union of two rectangles.
502
503 Given two rectangles, update the first to be the smallest
504 axis-aligned rectangle that encompasses both given rectangles.
505 If either rectangle is infinite then the union is also infinite.
506 If either rectangle is empty then the union is simply the
507 non-empty rectangle. Should both rectangles be empty, then the
508 union is also empty.
509 */
510 fz_rect fz_union_rect(fz_rect a, fz_rect b);
511
512 /**
513 Convert a rect into the minimal bounding box
514 that covers the rectangle.
515
516 Coordinates in a bounding box are integers, so rounding of the
517 rects coordinates takes place. The top left corner is rounded
518 upwards and left while the bottom right corner is rounded
519 downwards and to the right.
520 */
521 fz_irect fz_irect_from_rect(fz_rect rect);
522
523 /**
524 Round rectangle coordinates.
525
526 Coordinates in a bounding box are integers, so rounding of the
527 rects coordinates takes place. The top left corner is rounded
528 upwards and left while the bottom right corner is rounded
529 downwards and to the right.
530
531 This differs from fz_irect_from_rect, in that fz_irect_from_rect
532 slavishly follows the numbers (i.e any slight over/under
533 calculations can cause whole extra pixels to be added).
534 fz_round_rect allows for a small amount of rounding error when
535 calculating the bbox.
536 */
537 fz_irect fz_round_rect(fz_rect rect);
538
539 /**
540 Convert a bbox into a rect.
541
542 For our purposes, a rect can represent all the values we meet in
543 a bbox, so nothing can go wrong.
544
545 rect: A place to store the generated rectangle.
546
547 bbox: The bbox to convert.
548
549 Returns rect (updated).
550 */
551 fz_rect fz_rect_from_irect(fz_irect bbox);
552
553 /**
554 Expand a bbox by a given amount in all directions.
555 */
556 fz_rect fz_expand_rect(fz_rect b, float expand);
557 fz_irect fz_expand_irect(fz_irect a, int expand);
558
559 /**
560 Expand a bbox to include a given point.
561 To create a rectangle that encompasses a sequence of points, the
562 rectangle must first be set to be the empty rectangle at one of
563 the points before including the others.
564 */
565 fz_rect fz_include_point_in_rect(fz_rect r, fz_point p);
566
567 /**
568 Translate bounding box.
569
570 Translate a bbox by a given x and y offset. Allows for overflow.
571 */
572 fz_rect fz_translate_rect(fz_rect a, float xoff, float yoff);
573 fz_irect fz_translate_irect(fz_irect a, int xoff, int yoff);
574
575 /**
576 Test rectangle inclusion.
577
578 Return true if a entirely contains b.
579 */
580 int fz_contains_rect(fz_rect a, fz_rect b);
581
582 /**
583 Apply a transformation to a point.
584
585 transform: Transformation matrix to apply. See fz_concat,
586 fz_scale, fz_rotate and fz_translate for how to create a
587 matrix.
588
589 point: Pointer to point to update.
590
591 Returns transform (unchanged).
592 */
593 fz_point fz_transform_point(fz_point point, fz_matrix m);
594 fz_point fz_transform_point_xy(float x, float y, fz_matrix m);
595
596 /**
597 Apply a transformation to a vector.
598
599 transform: Transformation matrix to apply. See fz_concat,
600 fz_scale and fz_rotate for how to create a matrix. Any
601 translation will be ignored.
602
603 vector: Pointer to vector to update.
604 */
605 fz_point fz_transform_vector(fz_point vector, fz_matrix m);
606
607 /**
608 Apply a transform to a rectangle.
609
610 After the four corner points of the axis-aligned rectangle
611 have been transformed it may not longer be axis-aligned. So a
612 new axis-aligned rectangle is created covering at least the
613 area of the transformed rectangle.
614
615 transform: Transformation matrix to apply. See fz_concat,
616 fz_scale and fz_rotate for how to create a matrix.
617
618 rect: Rectangle to be transformed. The two special cases
619 fz_empty_rect and fz_infinite_rect, may be used but are
620 returned unchanged as expected.
621 */
622 fz_rect fz_transform_rect(fz_rect rect, fz_matrix m);
623
624 /**
625 Normalize a vector to length one.
626 */
627 fz_point fz_normalize_vector(fz_point p);
628
629 /**
630 Grid fit a matrix.
631
632 as_tiled = 0 => adjust the matrix so that the image of the unit
633 square completely covers any pixel that was touched by the
634 image of the unit square under the original matrix.
635
636 as_tiled = 1 => adjust the matrix so that the corners of the
637 image of the unit square align with the closest integer corner
638 of the image of the unit square under the original matrix.
639 */
640 fz_matrix fz_gridfit_matrix(int as_tiled, fz_matrix m);
641
642 /**
643 Find the largest expansion performed by this matrix.
644 (i.e. max(abs(m.a),abs(m.b),abs(m.c),abs(m.d))
645 */
646 float fz_matrix_max_expansion(fz_matrix m);
647
648 /**
649 A representation for a region defined by 4 points.
650
651 The significant difference between quads and rects is that
652 the edges of quads are not axis aligned.
653 */
654 typedef struct
655 {
656 fz_point ul, ur, ll, lr;
657 } fz_quad;
658
659 /**
660 Inline convenience construction function.
661 */
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)662 static inline fz_quad fz_make_quad(
663 float ul_x, float ul_y,
664 float ur_x, float ur_y,
665 float ll_x, float ll_y,
666 float lr_x, float lr_y)
667 {
668 fz_quad q = {
669 { ul_x, ul_y },
670 { ur_x, ur_y },
671 { ll_x, ll_y },
672 { lr_x, lr_y },
673 };
674 return q;
675 }
676
677 /**
678 Convert a rect to a quad (losslessly).
679 */
680 fz_quad fz_quad_from_rect(fz_rect r);
681
682 /**
683 Convert a quad to the smallest rect that covers it.
684 */
685 fz_rect fz_rect_from_quad(fz_quad q);
686
687 /**
688 Transform a quad by a matrix.
689 */
690 fz_quad fz_transform_quad(fz_quad q, fz_matrix m);
691
692 /**
693 Inclusion test for quads.
694 */
695 int fz_is_point_inside_quad(fz_point p, fz_quad q);
696
697 /**
698 Inclusion test for rects.
699 */
700 int fz_is_point_inside_rect(fz_point p, fz_rect r);
701
702 /**
703 Inclusion test for irects.
704 */
705 int fz_is_point_inside_irect(int x, int y, fz_irect r);
706
707 /**
708 Inclusion test for quad in quad.
709
710 This may break down if quads are not 'well formed'.
711 */
712 int fz_is_quad_inside_quad(fz_quad needle, fz_quad haystack);
713
714 /**
715 Intersection test for quads.
716
717 This may break down if quads are not 'well formed'.
718 */
719 int fz_is_quad_intersecting_quad(fz_quad a, fz_quad b);
720
721 #endif
722