1 #include "mupdf/fitz.h"
2
3 #include <math.h>
4 #include <float.h>
5 #include <limits.h>
6
7 #define MAX4(a,b,c,d) fz_max(fz_max(a,b), fz_max(c,d))
8 #define MIN4(a,b,c,d) fz_min(fz_min(a,b), fz_min(c,d))
9
10 /* A useful macro to add with overflow detection and clamping.
11
12 We want to do "b = a + x", but to allow for overflow. Consider the
13 top bits, and the cases in which overflow occurs:
14
15 overflow a x b ~a^x a^b (~a^x)&(a^b)
16 no 0 0 0 1 0 0
17 yes 0 0 1 1 1 1
18 no 0 1 0 0 0 0
19 no 0 1 1 0 1 0
20 no 1 0 0 0 1 0
21 no 1 0 1 0 0 0
22 yes 1 1 0 1 1 1
23 no 1 1 1 1 0 0
24 */
25 #define ADD_WITH_SAT(b,a,x) \
26 ((b) = (a) + (x), (b) = (((~(a)^(x))&((a)^(b))) < 0 ? ((x) < 0 ? INT_MIN : INT_MAX) : (b)))
27
28 /* Matrices, points and affine transformations */
29
30 const fz_matrix fz_identity = { 1, 0, 0, 1, 0, 0 };
31
32 fz_matrix
fz_concat(fz_matrix one,fz_matrix two)33 fz_concat(fz_matrix one, fz_matrix two)
34 {
35 fz_matrix dst;
36 dst.a = one.a * two.a + one.b * two.c;
37 dst.b = one.a * two.b + one.b * two.d;
38 dst.c = one.c * two.a + one.d * two.c;
39 dst.d = one.c * two.b + one.d * two.d;
40 dst.e = one.e * two.a + one.f * two.c + two.e;
41 dst.f = one.e * two.b + one.f * two.d + two.f;
42 return dst;
43 }
44
45 fz_matrix
fz_scale(float sx,float sy)46 fz_scale(float sx, float sy)
47 {
48 fz_matrix m;
49 m.a = sx; m.b = 0;
50 m.c = 0; m.d = sy;
51 m.e = 0; m.f = 0;
52 return m;
53 }
54
55 fz_matrix
fz_pre_scale(fz_matrix m,float sx,float sy)56 fz_pre_scale(fz_matrix m, float sx, float sy)
57 {
58 m.a *= sx;
59 m.b *= sx;
60 m.c *= sy;
61 m.d *= sy;
62 return m;
63 }
64
65 fz_matrix
fz_post_scale(fz_matrix m,float sx,float sy)66 fz_post_scale(fz_matrix m, float sx, float sy)
67 {
68 m.a *= sx;
69 m.b *= sy;
70 m.c *= sx;
71 m.d *= sy;
72 m.e *= sx;
73 m.f *= sy;
74 return m;
75 }
76
77 fz_matrix
fz_shear(float h,float v)78 fz_shear(float h, float v)
79 {
80 fz_matrix m;
81 m.a = 1; m.b = v;
82 m.c = h; m.d = 1;
83 m.e = 0; m.f = 0;
84 return m;
85 }
86
87 fz_matrix
fz_pre_shear(fz_matrix m,float h,float v)88 fz_pre_shear(fz_matrix m, float h, float v)
89 {
90 float a = m.a;
91 float b = m.b;
92 m.a += v * m.c;
93 m.b += v * m.d;
94 m.c += h * a;
95 m.d += h * b;
96 return m;
97 }
98
99 fz_matrix
fz_rotate(float theta)100 fz_rotate(float theta)
101 {
102 fz_matrix m;
103 float s;
104 float c;
105
106 while (theta < 0)
107 theta += 360;
108 while (theta >= 360)
109 theta -= 360;
110
111 if (fabsf(0 - theta) < FLT_EPSILON)
112 {
113 s = 0;
114 c = 1;
115 }
116 else if (fabsf(90.0f - theta) < FLT_EPSILON)
117 {
118 s = 1;
119 c = 0;
120 }
121 else if (fabsf(180.0f - theta) < FLT_EPSILON)
122 {
123 s = 0;
124 c = -1;
125 }
126 else if (fabsf(270.0f - theta) < FLT_EPSILON)
127 {
128 s = -1;
129 c = 0;
130 }
131 else
132 {
133 s = sinf(theta * FZ_PI / 180);
134 c = cosf(theta * FZ_PI / 180);
135 }
136
137 m.a = c; m.b = s;
138 m.c = -s; m.d = c;
139 m.e = 0; m.f = 0;
140 return m;
141 }
142
143 fz_matrix
fz_pre_rotate(fz_matrix m,float theta)144 fz_pre_rotate(fz_matrix m, float theta)
145 {
146 while (theta < 0)
147 theta += 360;
148 while (theta >= 360)
149 theta -= 360;
150
151 if (fabsf(0 - theta) < FLT_EPSILON)
152 {
153 /* Nothing to do */
154 }
155 else if (fabsf(90.0f - theta) < FLT_EPSILON)
156 {
157 float a = m.a;
158 float b = m.b;
159 m.a = m.c;
160 m.b = m.d;
161 m.c = -a;
162 m.d = -b;
163 }
164 else if (fabsf(180.0f - theta) < FLT_EPSILON)
165 {
166 m.a = -m.a;
167 m.b = -m.b;
168 m.c = -m.c;
169 m.d = -m.d;
170 }
171 else if (fabsf(270.0f - theta) < FLT_EPSILON)
172 {
173 float a = m.a;
174 float b = m.b;
175 m.a = -m.c;
176 m.b = -m.d;
177 m.c = a;
178 m.d = b;
179 }
180 else
181 {
182 float s = sinf(theta * FZ_PI / 180);
183 float c = cosf(theta * FZ_PI / 180);
184 float a = m.a;
185 float b = m.b;
186 m.a = c * a + s * m.c;
187 m.b = c * b + s * m.d;
188 m.c =-s * a + c * m.c;
189 m.d =-s * b + c * m.d;
190 }
191
192 return m;
193 }
194
195 fz_matrix
fz_translate(float tx,float ty)196 fz_translate(float tx, float ty)
197 {
198 fz_matrix m;
199 m.a = 1; m.b = 0;
200 m.c = 0; m.d = 1;
201 m.e = tx; m.f = ty;
202 return m;
203 }
204
205 fz_matrix
fz_pre_translate(fz_matrix m,float tx,float ty)206 fz_pre_translate(fz_matrix m, float tx, float ty)
207 {
208 m.e += tx * m.a + ty * m.c;
209 m.f += tx * m.b + ty * m.d;
210 return m;
211 }
212
213 fz_matrix
fz_transform_page(fz_rect mediabox,float resolution,float rotate)214 fz_transform_page(fz_rect mediabox, float resolution, float rotate)
215 {
216 float user_w, user_h, pixel_w, pixel_h;
217 fz_rect pixel_box;
218 fz_matrix matrix;
219
220 /* Adjust scaling factors to cover whole pixels */
221 user_w = mediabox.x1 - mediabox.x0;
222 user_h = mediabox.y1 - mediabox.y0;
223 pixel_w = floorf(user_w * resolution / 72 + 0.5f);
224 pixel_h = floorf(user_h * resolution / 72 + 0.5f);
225
226 matrix = fz_pre_rotate(fz_scale(pixel_w / user_w, pixel_h / user_h), rotate);
227
228 /* Adjust the page origin to sit at 0,0 after rotation */
229 pixel_box = fz_transform_rect(mediabox, matrix);
230 matrix.e -= pixel_box.x0;
231 matrix.f -= pixel_box.y0;
232
233 return matrix;
234 }
235
236 fz_matrix
fz_invert_matrix(fz_matrix src)237 fz_invert_matrix(fz_matrix src)
238 {
239 float a = src.a;
240 float det = a * src.d - src.b * src.c;
241 if (det < -FLT_EPSILON || det > FLT_EPSILON)
242 {
243 fz_matrix dst;
244 float rdet = 1 / det;
245 dst.a = src.d * rdet;
246 dst.b = -src.b * rdet;
247 dst.c = -src.c * rdet;
248 dst.d = a * rdet;
249 a = -src.e * dst.a - src.f * dst.c;
250 dst.f = -src.e * dst.b - src.f * dst.d;
251 dst.e = a;
252 return dst;
253 }
254 return src;
255 }
256
257 int
fz_try_invert_matrix(fz_matrix * dst,fz_matrix src)258 fz_try_invert_matrix(fz_matrix *dst, fz_matrix src)
259 {
260 double sa = (double)src.a;
261 double sb = (double)src.b;
262 double sc = (double)src.c;
263 double sd = (double)src.d;
264 double da, db, dc, dd;
265 double det = sa * sd - sb * sc;
266 if (det >= -DBL_EPSILON && det <= DBL_EPSILON)
267 return 1;
268 det = 1 / det;
269 da = sd * det;
270 dst->a = (float)da;
271 db = -sb * det;
272 dst->b = (float)db;
273 dc = -sc * det;
274 dst->c = (float)dc;
275 dd = sa * det;
276 dst->d = (float)dd;
277 da = -src.e * da - src.f * dc;
278 dst->f = (float)(-src.e * db - src.f * dd);
279 dst->e = (float)da;
280 return 0;
281 }
282
283 int
fz_is_rectilinear(fz_matrix m)284 fz_is_rectilinear(fz_matrix m)
285 {
286 return (fabsf(m.b) < FLT_EPSILON && fabsf(m.c) < FLT_EPSILON) ||
287 (fabsf(m.a) < FLT_EPSILON && fabsf(m.d) < FLT_EPSILON);
288 }
289
290 float
fz_matrix_expansion(fz_matrix m)291 fz_matrix_expansion(fz_matrix m)
292 {
293 return sqrtf(fabsf(m.a * m.d - m.b * m.c));
294 }
295
296 float
fz_matrix_max_expansion(fz_matrix m)297 fz_matrix_max_expansion(fz_matrix m)
298 {
299 float max = fabsf(m.a);
300 float x = fabsf(m.b);
301 if (max < x)
302 max = x;
303 x = fabsf(m.c);
304 if (max < x)
305 max = x;
306 x = fabsf(m.d);
307 if (max < x)
308 max = x;
309 return max;
310 }
311
312 fz_point
fz_transform_point(fz_point p,fz_matrix m)313 fz_transform_point(fz_point p, fz_matrix m)
314 {
315 float x = p.x;
316 p.x = x * m.a + p.y * m.c + m.e;
317 p.y = x * m.b + p.y * m.d + m.f;
318 return p;
319 }
320
321 fz_point
fz_transform_point_xy(float x,float y,fz_matrix m)322 fz_transform_point_xy(float x, float y, fz_matrix m)
323 {
324 fz_point p;
325 p.x = x * m.a + y * m.c + m.e;
326 p.y = x * m.b + y * m.d + m.f;
327 return p;
328 }
329
330 fz_point
fz_transform_vector(fz_point p,fz_matrix m)331 fz_transform_vector(fz_point p, fz_matrix m)
332 {
333 float x = p.x;
334 p.x = x * m.a + p.y * m.c;
335 p.y = x * m.b + p.y * m.d;
336 return p;
337 }
338
339 fz_point
fz_normalize_vector(fz_point p)340 fz_normalize_vector(fz_point p)
341 {
342 float len = p.x * p.x + p.y * p.y;
343 if (len != 0)
344 {
345 len = sqrtf(len);
346 p.x /= len;
347 p.y /= len;
348 }
349 return p;
350 }
351
352 /* Rectangles and bounding boxes */
353
354 /* biggest and smallest integers that a float can represent perfectly (i.e. 24 bits) */
355 #define MAX_SAFE_INT 16777216
356 #define MIN_SAFE_INT -16777216
357
358 const fz_rect fz_infinite_rect = { 1, 1, -1, -1 };
359 const fz_rect fz_empty_rect = { 0, 0, 0, 0 };
360 const fz_rect fz_unit_rect = { 0, 0, 1, 1 };
361
362 const fz_irect fz_infinite_irect = { 1, 1, -1, -1 };
363 const fz_irect fz_empty_irect = { 0, 0, 0, 0 };
364 const fz_irect fz_unit_bbox = { 0, 0, 1, 1 };
365
366 fz_irect
fz_irect_from_rect(fz_rect r)367 fz_irect_from_rect(fz_rect r)
368 {
369 fz_irect b;
370 if (fz_is_empty_rect(r))
371 {
372 b.x0 = 0;
373 b.y0 = 0;
374 b.x1 = 0;
375 b.y1 = 0;
376 }
377 else
378 {
379 b.x0 = fz_clamp(floorf(r.x0), MIN_SAFE_INT, MAX_SAFE_INT);
380 b.y0 = fz_clamp(floorf(r.y0), MIN_SAFE_INT, MAX_SAFE_INT);
381 b.x1 = fz_clamp(ceilf(r.x1), MIN_SAFE_INT, MAX_SAFE_INT);
382 b.y1 = fz_clamp(ceilf(r.y1), MIN_SAFE_INT, MAX_SAFE_INT);
383 }
384 return b;
385 }
386
387 fz_rect
fz_rect_from_irect(fz_irect a)388 fz_rect_from_irect(fz_irect a)
389 {
390 fz_rect r;
391 r.x0 = a.x0;
392 r.y0 = a.y0;
393 r.x1 = a.x1;
394 r.y1 = a.y1;
395 return r;
396 }
397
398 fz_irect
fz_round_rect(fz_rect r)399 fz_round_rect(fz_rect r)
400 {
401 fz_irect b;
402 int i;
403
404 i = floorf(r.x0 + 0.001f);
405 b.x0 = fz_clamp(i, MIN_SAFE_INT, MAX_SAFE_INT);
406 i = floorf(r.y0 + 0.001f);
407 b.y0 = fz_clamp(i, MIN_SAFE_INT, MAX_SAFE_INT);
408 i = ceilf(r.x1 - 0.001f);
409 b.x1 = fz_clamp(i, MIN_SAFE_INT, MAX_SAFE_INT);
410 i = ceilf(r.y1 - 0.001f);
411 b.y1 = fz_clamp(i, MIN_SAFE_INT, MAX_SAFE_INT);
412
413 return b;
414 }
415
416 fz_rect
fz_intersect_rect(fz_rect a,fz_rect b)417 fz_intersect_rect(fz_rect a, fz_rect b)
418 {
419 /* Check for empty box before infinite box */
420 if (fz_is_empty_rect(a)) return fz_empty_rect;
421 if (fz_is_empty_rect(b)) return fz_empty_rect;
422 if (fz_is_infinite_rect(b)) return a;
423 if (fz_is_infinite_rect(a)) return b;
424 if (a.x0 < b.x0)
425 a.x0 = b.x0;
426 if (a.y0 < b.y0)
427 a.y0 = b.y0;
428 if (a.x1 > b.x1)
429 a.x1 = b.x1;
430 if (a.y1 > b.y1)
431 a.y1 = b.y1;
432 if (a.x1 < a.x0 || a.y1 < a.y0)
433 return fz_empty_rect;
434 return a;
435 }
436
437 fz_irect
fz_intersect_irect(fz_irect a,fz_irect b)438 fz_intersect_irect(fz_irect a, fz_irect b)
439 {
440 /* Check for empty box before infinite box */
441 if (fz_is_empty_irect(a)) return fz_empty_irect;
442 if (fz_is_empty_irect(b)) return fz_empty_irect;
443 if (fz_is_infinite_irect(b)) return a;
444 if (fz_is_infinite_irect(a)) return b;
445 if (a.x0 < b.x0)
446 a.x0 = b.x0;
447 if (a.y0 < b.y0)
448 a.y0 = b.y0;
449 if (a.x1 > b.x1)
450 a.x1 = b.x1;
451 if (a.y1 > b.y1)
452 a.y1 = b.y1;
453 if (a.x1 < a.x0 || a.y1 < a.y0)
454 return fz_empty_irect;
455 return a;
456 }
457
458 fz_rect
fz_union_rect(fz_rect a,fz_rect b)459 fz_union_rect(fz_rect a, fz_rect b)
460 {
461 /* Check for empty box before infinite box */
462 if (fz_is_empty_rect(b)) return a;
463 if (fz_is_empty_rect(a)) return b;
464 if (fz_is_infinite_rect(a)) return a;
465 if (fz_is_infinite_rect(b)) return b;
466 if (a.x0 > b.x0)
467 a.x0 = b.x0;
468 if (a.y0 > b.y0)
469 a.y0 = b.y0;
470 if (a.x1 < b.x1)
471 a.x1 = b.x1;
472 if (a.y1 < b.y1)
473 a.y1 = b.y1;
474 return a;
475 }
476
477 fz_rect
fz_translate_rect(fz_rect a,float xoff,float yoff)478 fz_translate_rect(fz_rect a, float xoff, float yoff)
479 {
480 if (fz_is_empty_rect(a)) return a;
481 if (fz_is_infinite_rect(a)) return a;
482 a.x0 += xoff;
483 a.y0 += yoff;
484 a.x1 += xoff;
485 a.y1 += yoff;
486 return a;
487 }
488
489 fz_irect
fz_translate_irect(fz_irect a,int xoff,int yoff)490 fz_translate_irect(fz_irect a, int xoff, int yoff)
491 {
492 int t;
493
494 if (fz_is_empty_irect(a)) return a;
495 if (fz_is_infinite_irect(a)) return a;
496 a.x0 = ADD_WITH_SAT(t, a.x0, xoff);
497 a.y0 = ADD_WITH_SAT(t, a.y0, yoff);
498 a.x1 = ADD_WITH_SAT(t, a.x1, xoff);
499 a.y1 = ADD_WITH_SAT(t, a.y1, yoff);
500 return a;
501 }
502
503 fz_rect
fz_transform_rect(fz_rect r,fz_matrix m)504 fz_transform_rect(fz_rect r, fz_matrix m)
505 {
506 fz_point s, t, u, v;
507
508 if (fz_is_infinite_rect(r))
509 return r;
510
511 if (fabsf(m.b) < FLT_EPSILON && fabsf(m.c) < FLT_EPSILON)
512 {
513 if (m.a < 0)
514 {
515 float f = r.x0;
516 r.x0 = r.x1;
517 r.x1 = f;
518 }
519 if (m.d < 0)
520 {
521 float f = r.y0;
522 r.y0 = r.y1;
523 r.y1 = f;
524 }
525 s = fz_transform_point_xy(r.x0, r.y0, m);
526 t = fz_transform_point_xy(r.x1, r.y1, m);
527 r.x0 = s.x; r.y0 = s.y;
528 r.x1 = t.x; r.y1 = t.y;
529 return r;
530 }
531
532 s.x = r.x0; s.y = r.y0;
533 t.x = r.x0; t.y = r.y1;
534 u.x = r.x1; u.y = r.y1;
535 v.x = r.x1; v.y = r.y0;
536 s = fz_transform_point(s, m);
537 t = fz_transform_point(t, m);
538 u = fz_transform_point(u, m);
539 v = fz_transform_point(v, m);
540 r.x0 = MIN4(s.x, t.x, u.x, v.x);
541 r.y0 = MIN4(s.y, t.y, u.y, v.y);
542 r.x1 = MAX4(s.x, t.x, u.x, v.x);
543 r.y1 = MAX4(s.y, t.y, u.y, v.y);
544 return r;
545 }
546
547 fz_irect
fz_expand_irect(fz_irect a,int expand)548 fz_expand_irect(fz_irect a, int expand)
549 {
550 if (fz_is_infinite_irect(a)) return a;
551 a.x0 -= expand;
552 a.y0 -= expand;
553 a.x1 += expand;
554 a.y1 += expand;
555 return a;
556 }
557
558 fz_rect
fz_expand_rect(fz_rect a,float expand)559 fz_expand_rect(fz_rect a, float expand)
560 {
561 if (fz_is_infinite_rect(a)) return a;
562 a.x0 -= expand;
563 a.y0 -= expand;
564 a.x1 += expand;
565 a.y1 += expand;
566 return a;
567 }
568
fz_include_point_in_rect(fz_rect r,fz_point p)569 fz_rect fz_include_point_in_rect(fz_rect r, fz_point p)
570 {
571 if (fz_is_infinite_rect(r)) return r;
572 if (p.x < r.x0) r.x0 = p.x;
573 if (p.x > r.x1) r.x1 = p.x;
574 if (p.y < r.y0) r.y0 = p.y;
575 if (p.y > r.y1) r.y1 = p.y;
576 return r;
577 }
578
fz_contains_rect(fz_rect a,fz_rect b)579 int fz_contains_rect(fz_rect a, fz_rect b)
580 {
581 if (fz_is_empty_rect(b))
582 return 1;
583 if (fz_is_empty_rect(a))
584 return 0;
585 return ((a.x0 <= b.x0) &&
586 (a.y0 <= b.y0) &&
587 (a.x1 >= b.x1) &&
588 (a.y1 >= b.y1));
589 }
590
591 fz_rect
fz_rect_from_quad(fz_quad q)592 fz_rect_from_quad(fz_quad q)
593 {
594 fz_rect r;
595 r.x0 = MIN4(q.ll.x, q.lr.x, q.ul.x, q.ur.x);
596 r.y0 = MIN4(q.ll.y, q.lr.y, q.ul.y, q.ur.y);
597 r.x1 = MAX4(q.ll.x, q.lr.x, q.ul.x, q.ur.x);
598 r.y1 = MAX4(q.ll.y, q.lr.y, q.ul.y, q.ur.y);
599 return r;
600 }
601
602 fz_quad
fz_transform_quad(fz_quad q,fz_matrix m)603 fz_transform_quad(fz_quad q, fz_matrix m)
604 {
605 q.ul = fz_transform_point(q.ul, m);
606 q.ur = fz_transform_point(q.ur, m);
607 q.ll = fz_transform_point(q.ll, m);
608 q.lr = fz_transform_point(q.lr, m);
609 return q;
610 }
611
612 fz_quad
fz_quad_from_rect(fz_rect r)613 fz_quad_from_rect(fz_rect r)
614 {
615 fz_quad q;
616 q.ul = fz_make_point(r.x0, r.y0);
617 q.ur = fz_make_point(r.x1, r.y0);
618 q.ll = fz_make_point(r.x0, r.y1);
619 q.lr = fz_make_point(r.x1, r.y1);
620 return q;
621 }
622
fz_is_point_inside_rect(fz_point p,fz_rect r)623 int fz_is_point_inside_rect(fz_point p, fz_rect r)
624 {
625 return (p.x >= r.x0 && p.x < r.x1 && p.y >= r.y0 && p.y < r.y1);
626 }
627
fz_is_point_inside_irect(int x,int y,fz_irect r)628 int fz_is_point_inside_irect(int x, int y, fz_irect r)
629 {
630 return (x >= r.x0 && x < r.x1 && y >= r.y0 && y < r.y1);
631 }
632
fz_is_point_inside_triangle(fz_point p,fz_point a,fz_point b,fz_point c)633 static int fz_is_point_inside_triangle(fz_point p, fz_point a, fz_point b, fz_point c)
634 {
635 float s, t, area;
636 s = a.y * c.x - a.x * c.y + (c.y - a.y) * p.x + (a.x - c.x) * p.y;
637 t = a.x * b.y - a.y * b.x + (a.y - b.y) * p.x + (b.x - a.x) * p.y;
638
639 if ((s < 0) != (t < 0))
640 return 0;
641
642 area = -b.y * c.x + a.y * (c.x - b.x) + a.x * (b.y - c.y) + b.x * c.y;
643
644 return area < 0 ?
645 (s <= 0 && s + t >= area) :
646 (s >= 0 && s + t <= area);
647 }
648
fz_is_point_inside_quad(fz_point p,fz_quad q)649 int fz_is_point_inside_quad(fz_point p, fz_quad q)
650 {
651 return
652 fz_is_point_inside_triangle(p, q.ul, q.ur, q.lr) ||
653 fz_is_point_inside_triangle(p, q.ul, q.lr, q.ll);
654 }
655
fz_is_quad_inside_quad(fz_quad needle,fz_quad haystack)656 int fz_is_quad_inside_quad(fz_quad needle, fz_quad haystack)
657 {
658 return
659 fz_is_point_inside_quad(needle.ul, haystack) &&
660 fz_is_point_inside_quad(needle.ur, haystack) &&
661 fz_is_point_inside_quad(needle.ll, haystack) &&
662 fz_is_point_inside_quad(needle.lr, haystack);
663 }
664
fz_is_quad_intersecting_quad(fz_quad a,fz_quad b)665 int fz_is_quad_intersecting_quad(fz_quad a, fz_quad b)
666 {
667 fz_rect ar = fz_rect_from_quad(a);
668 fz_rect br = fz_rect_from_quad(b);
669 return !fz_is_empty_rect(fz_intersect_rect(ar, br));
670 }
671