1// Copyright 2014 PDFium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6
7#include "../../include/fxcrt/fx_ext.h"
8void FX_RECT::Normalize()
9{
10    if (left > right) {
11        int temp = left;
12        left = right;
13        right = temp;
14    }
15    if (top > bottom) {
16        int temp = top;
17        top = bottom;
18        bottom = temp;
19    }
20}
21void FX_RECT::Intersect(const FX_RECT& src)
22{
23    FX_RECT src_n = src;
24    src_n.Normalize();
25    Normalize();
26    left = left > src_n.left ? left : src_n.left;
27    top = top > src_n.top ? top : src_n.top;
28    right = right < src_n.right ? right : src_n.right;
29    bottom = bottom < src_n.bottom ? bottom : src_n.bottom;
30    if (left > right || top > bottom) {
31        left = top = right = bottom = 0;
32    }
33}
34void FX_RECT::Union(const FX_RECT& other_rect)
35{
36    Normalize();
37    FX_RECT other = other_rect;
38    other.Normalize();
39    left = left < other.left ? left : other.left;
40    right = right > other.right ? right : other.right;
41    bottom = bottom > other.bottom ? bottom : other.bottom;
42    top = top < other.top ? top : other.top;
43}
44FX_BOOL GetIntersection(FX_FLOAT low1, FX_FLOAT high1, FX_FLOAT low2, FX_FLOAT high2,
45                        FX_FLOAT& interlow, FX_FLOAT& interhigh)
46{
47    if (low1 >= high2 || low2 >= high1) {
48        return FALSE;
49    }
50    interlow = low1 > low2 ? low1 : low2;
51    interhigh = high1 > high2 ? high2 : high1;
52    return TRUE;
53}
54extern "C" int FXSYS_round(FX_FLOAT d)
55{
56    int iRet = 0;
57    if (d >= 0.0f) {
58        iRet = (int)(d + 0.5f);
59        if (iRet >= 0) {
60            return iRet;
61        }
62        return -iRet;
63    }
64    return (int)(d - 0.5f);
65}
66CFX_FloatRect::CFX_FloatRect(const FX_RECT& rect)
67{
68    left = (FX_FLOAT)(rect.left);
69    right = (FX_FLOAT)(rect.right);
70    bottom = (FX_FLOAT)(rect.top);
71    top = (FX_FLOAT)(rect.bottom);
72}
73void CFX_FloatRect::Normalize()
74{
75    FX_FLOAT temp;
76    if (left > right) {
77        temp = left;
78        left = right;
79        right = temp;
80    }
81    if (bottom > top) {
82        temp = top;
83        top = bottom;
84        bottom = temp;
85    }
86}
87void CFX_FloatRect::Intersect(const CFX_FloatRect& other_rect)
88{
89    Normalize();
90    CFX_FloatRect other = other_rect;
91    other.Normalize();
92    left = left > other.left ? left : other.left;
93    right = right < other.right ? right : other.right;
94    bottom = bottom > other.bottom ? bottom : other.bottom;
95    top = top < other.top ? top : other.top;
96    if (left > right || bottom > top) {
97        left = right = bottom = top = 0;
98    }
99}
100void CFX_FloatRect::Union(const CFX_FloatRect& other_rect)
101{
102    Normalize();
103    CFX_FloatRect other = other_rect;
104    other.Normalize();
105    left = left < other.left ? left : other.left;
106    right = right > other.right ? right : other.right;
107    bottom = bottom < other.bottom ? bottom : other.bottom;
108    top = top > other.top ? top : other.top;
109}
110void CFX_FloatRect::Transform(const CFX_Matrix* pMatrix)
111{
112    pMatrix->TransformRect(left, right, top, bottom);
113}
114int CFX_FloatRect::Substract4(CFX_FloatRect& s, CFX_FloatRect* pRects)
115{
116    Normalize();
117    s.Normalize();
118    int nRects = 0;
119    CFX_FloatRect rects[4];
120    if (left < s.left) {
121        rects[nRects].left = left;
122        rects[nRects].right = s.left;
123        rects[nRects].bottom = bottom;
124        rects[nRects].top = top;
125        nRects ++;
126    }
127    if (s.left < right && s.top < top) {
128        rects[nRects].left = s.left;
129        rects[nRects].right = right;
130        rects[nRects].bottom = s.top;
131        rects[nRects].top = top;
132        nRects ++;
133    }
134    if (s.top > bottom && s.right < right) {
135        rects[nRects].left = s.right;
136        rects[nRects].right = right;
137        rects[nRects].bottom = bottom;
138        rects[nRects].top = s.top;
139        nRects ++;
140    }
141    if (s.bottom > bottom) {
142        rects[nRects].left = s.left;
143        rects[nRects].right = s.right;
144        rects[nRects].bottom = bottom;
145        rects[nRects].top = s.bottom;
146        nRects ++;
147    }
148    if (nRects == 0) {
149        return 0;
150    }
151    for (int i = 0; i < nRects; i ++) {
152        pRects[i] = rects[i];
153        pRects[i].Intersect(*this);
154    }
155    return nRects;
156}
157FX_RECT CFX_FloatRect::GetOutterRect() const
158{
159    CFX_FloatRect rect1 = *this;
160    FX_RECT rect;
161    rect.left = (int)FXSYS_floor(rect1.left);
162    rect.right = (int)FXSYS_ceil(rect1.right);
163    rect.top = (int)FXSYS_floor(rect1.bottom);
164    rect.bottom = (int)FXSYS_ceil(rect1.top);
165    rect.Normalize();
166    return rect;
167}
168FX_RECT CFX_FloatRect::GetInnerRect() const
169{
170    CFX_FloatRect rect1 = *this;
171    FX_RECT rect;
172    rect.left = (int)FXSYS_ceil(rect1.left);
173    rect.right = (int)FXSYS_floor(rect1.right);
174    rect.top = (int)FXSYS_ceil(rect1.bottom);
175    rect.bottom = (int)FXSYS_floor(rect1.top);
176    rect.Normalize();
177    return rect;
178}
179static void _MatchFloatRange(FX_FLOAT f1, FX_FLOAT f2, int& i1, int& i2)
180{
181    int length = (int)FXSYS_ceil(f2 - f1);
182    int i1_1 = (int)FXSYS_floor(f1);
183    int i1_2 = (int)FXSYS_ceil(f1);
184    FX_FLOAT error1 = f1 - i1_1 + (FX_FLOAT)FXSYS_fabs(f2 - i1_1 - length);
185    FX_FLOAT error2 = i1_2 - f1 + (FX_FLOAT)FXSYS_fabs(f2 - i1_2 - length);
186    i1 = (error1 > error2) ? i1_2 : i1_1;
187    i2 = i1 + length;
188}
189FX_RECT CFX_FloatRect::GetClosestRect() const
190{
191    CFX_FloatRect rect1 = *this;
192    FX_RECT rect;
193    _MatchFloatRange(rect1.left, rect1.right, rect.left, rect.right);
194    _MatchFloatRange(rect1.bottom, rect1.top, rect.top, rect.bottom);
195    rect.Normalize();
196    return rect;
197}
198FX_BOOL CFX_FloatRect::Contains(const CFX_FloatRect& other_rect) const
199{
200    CFX_FloatRect n1 = *this;
201    n1.Normalize();
202    CFX_FloatRect n2 = other_rect;
203    n2.Normalize();
204    if (n2.left >= n1.left && n2.right <= n1.right && n2.bottom >= n1.bottom && n2.top <= n1.top) {
205        return TRUE;
206    }
207    return FALSE;
208}
209FX_BOOL CFX_FloatRect::Contains(FX_FLOAT x, FX_FLOAT y) const
210{
211    CFX_FloatRect n1 = *this;
212    n1.Normalize();
213    return x <= n1.right && x >= n1.left && y <= n1.top && y >= n1.bottom;
214}
215void CFX_FloatRect::UpdateRect(FX_FLOAT x, FX_FLOAT y)
216{
217    if (left > x) {
218        left = x;
219    }
220    if (right < x) {
221        right = x;
222    }
223    if (bottom > y) {
224        bottom = y;
225    }
226    if (top < y) {
227        top = y;
228    }
229}
230CFX_FloatRect CFX_FloatRect::GetBBox(const CFX_FloatPoint* pPoints, int nPoints)
231{
232    if (nPoints == 0) {
233        return CFX_FloatRect();
234    }
235    FX_FLOAT min_x = pPoints->x, max_x = pPoints->x, min_y = pPoints->y, max_y = pPoints->y;
236    for (int i = 1; i < nPoints; i ++) {
237        if (min_x > pPoints[i].x) {
238            min_x = pPoints[i].x;
239        }
240        if (max_x < pPoints[i].x) {
241            max_x = pPoints[i].x;
242        }
243        if (min_y > pPoints[i].y) {
244            min_y = pPoints[i].y;
245        }
246        if (max_y < pPoints[i].y) {
247            max_y = pPoints[i].y;
248        }
249    }
250    return CFX_FloatRect(min_x, min_y, max_x, max_y);
251}
252void CFX_Matrix::Set(FX_FLOAT a, FX_FLOAT b, FX_FLOAT c, FX_FLOAT d, FX_FLOAT e, FX_FLOAT f)
253{
254    this->a = a;
255    this->b = b;
256    this->c = c;
257    this->d = d;
258    this->e = e;
259    this->f = f;
260}
261void CFX_Matrix::Set(const FX_FLOAT n[6])
262{
263    this->a = n[0];
264    this->b = n[1];
265    this->c = n[2];
266    this->d = n[3];
267    this->e = n[4];
268    this->f = n[5];
269}
270void CFX_Matrix::SetReverse(const CFX_Matrix &m)
271{
272    FX_FLOAT i = m.a * m.d - m.b * m.c;
273    if (FXSYS_fabs(i) == 0) {
274        return;
275    }
276    FX_FLOAT j = -i;
277    a = m.d / i;
278    b = m.b / j;
279    c = m.c / j;
280    d = m.a / i;
281    e = (m.c * m.f - m.d * m.e) / i;
282    f = (m.a * m.f - m.b * m.e) / j;
283}
284static void FXCRT_Matrix_Concat(CFX_Matrix &m, const CFX_Matrix &m1, const CFX_Matrix &m2)
285{
286    FX_FLOAT aa = m1.a * m2.a + m1.b * m2.c;
287    FX_FLOAT bb = m1.a * m2.b + m1.b * m2.d;
288    FX_FLOAT cc = m1.c * m2.a + m1.d * m2.c;
289    FX_FLOAT dd = m1.c * m2.b + m1.d * m2.d;
290    FX_FLOAT ee = m1.e * m2.a + m1.f * m2.c + m2.e;
291    FX_FLOAT ff = m1.e * m2.b + m1.f * m2.d + m2.f;
292    m.a = aa, m.b = bb, m.c = cc, m.d = dd, m.e = ee, m.f = ff;
293}
294void CFX_Matrix::Concat(FX_FLOAT a, FX_FLOAT b, FX_FLOAT c, FX_FLOAT d, FX_FLOAT e, FX_FLOAT f, FX_BOOL bPrepended)
295{
296    CFX_Matrix m;
297    m.Set(a, b, c, d, e, f);
298    Concat(m, bPrepended);
299}
300void CFX_Matrix::Concat(const CFX_Matrix &m, FX_BOOL bPrepended)
301{
302    if (bPrepended) {
303        FXCRT_Matrix_Concat(*this, m, *this);
304    } else {
305        FXCRT_Matrix_Concat(*this, *this, m);
306    }
307}
308void CFX_Matrix::ConcatInverse(const CFX_Matrix& src, FX_BOOL bPrepended)
309{
310    CFX_Matrix m;
311    m.SetReverse(src);
312    Concat(m, bPrepended);
313}
314FX_BOOL CFX_Matrix::IsInvertible() const
315{
316    return FXSYS_fabs(a * d - b * c) >= 0.0001f;
317}
318FX_BOOL CFX_Matrix::Is90Rotated() const
319{
320    return FXSYS_fabs(a * 1000) < FXSYS_fabs(b) && FXSYS_fabs(d * 1000) < FXSYS_fabs(c);
321}
322FX_BOOL CFX_Matrix::IsScaled() const
323{
324    return FXSYS_fabs(b * 1000) < FXSYS_fabs(a) && FXSYS_fabs(c * 1000) < FXSYS_fabs(d);
325}
326void CFX_Matrix::Translate(FX_FLOAT x, FX_FLOAT y, FX_BOOL bPrepended)
327{
328    if (bPrepended) {
329        e += x * a + y * c;
330        f += y * d + x * b;
331    } else {
332        e += x, f += y;
333    }
334}
335void CFX_Matrix::Scale(FX_FLOAT sx, FX_FLOAT sy, FX_BOOL bPrepended)
336{
337    a *= sx, d *= sy;
338    if (bPrepended) {
339        b *= sx;
340        c *= sy;
341    } else {
342        b *= sy;
343        c *= sx;
344        e *= sx;
345        f *= sy;
346    }
347}
348void CFX_Matrix::Rotate(FX_FLOAT fRadian, FX_BOOL bPrepended)
349{
350    FX_FLOAT cosValue = FXSYS_cos(fRadian);
351    FX_FLOAT sinValue = FXSYS_sin(fRadian);
352    CFX_Matrix m;
353    m.Set(cosValue, sinValue, -sinValue, cosValue, 0, 0);
354    if (bPrepended) {
355        FXCRT_Matrix_Concat(*this, m, *this);
356    } else {
357        FXCRT_Matrix_Concat(*this, *this, m);
358    }
359}
360void CFX_Matrix::RotateAt(FX_FLOAT fRadian, FX_FLOAT dx, FX_FLOAT dy, FX_BOOL bPrepended)
361{
362    Translate(dx, dy, bPrepended);
363    Rotate(fRadian, bPrepended);
364    Translate(-dx, -dy, bPrepended);
365}
366void CFX_Matrix::Shear(FX_FLOAT fAlphaRadian, FX_FLOAT fBetaRadian, FX_BOOL bPrepended)
367{
368    CFX_Matrix m;
369    m.Set(1, FXSYS_tan(fAlphaRadian), FXSYS_tan(fBetaRadian), 1, 0, 0);
370    if (bPrepended) {
371        FXCRT_Matrix_Concat(*this, m, *this);
372    } else {
373        FXCRT_Matrix_Concat(*this, *this, m);
374    }
375}
376void CFX_Matrix::MatchRect(const CFX_FloatRect& dest, const CFX_FloatRect& src)
377{
378    FX_FLOAT fDiff = src.left - src.right;
379    a = FXSYS_fabs(fDiff) < 0.001f ? 1 : (dest.left - dest.right) / fDiff;
380    fDiff = src.bottom - src.top;
381    d = FXSYS_fabs(fDiff) < 0.001f ? 1 : (dest.bottom - dest.top) / fDiff;
382    e = dest.left - src.left * a;
383    f = dest.bottom - src.bottom * d;
384    b = 0;
385    c = 0;
386}
387FX_FLOAT CFX_Matrix::GetXUnit() const
388{
389    if (b == 0) {
390        return (a > 0 ? a : -a);
391    }
392    if (a == 0) {
393        return (b > 0 ? b : -b);
394    }
395    return FXSYS_sqrt(a * a + b * b);
396}
397FX_FLOAT CFX_Matrix::GetYUnit() const
398{
399    if (c == 0) {
400        return (d > 0 ? d : -d);
401    }
402    if (d == 0) {
403        return (c > 0 ? c : -c);
404    }
405    return FXSYS_sqrt(c * c + d * d);
406}
407void CFX_Matrix::GetUnitRect(CFX_RectF &rect) const
408{
409    rect.left = rect.top = 0;
410    rect.width = rect.height = 1;
411    TransformRect(rect);
412}
413CFX_FloatRect CFX_Matrix::GetUnitRect() const
414{
415    CFX_FloatRect rect(0, 0, 1, 1);
416    rect.Transform((const CFX_Matrix*)this);
417    return rect;
418}
419FX_FLOAT CFX_Matrix::GetUnitArea() const
420{
421    FX_FLOAT A = FXSYS_sqrt(a * a + b * b);
422    FX_FLOAT B = FXSYS_sqrt(c * c + d * d);
423    FX_FLOAT ac = a + c, bd = b + d;
424    FX_FLOAT C = FXSYS_sqrt(ac * ac + bd * bd);
425    FX_FLOAT P = (A + B + C ) / 2;
426    return FXSYS_sqrt(P * (P - A) * (P - B) * (P - C)) * 2;
427}
428FX_FLOAT CFX_Matrix::TransformXDistance(FX_FLOAT dx) const
429{
430    FX_FLOAT fx = a * dx, fy = b * dx;
431    return FXSYS_sqrt(fx * fx + fy * fy);
432}
433FX_INT32 CFX_Matrix::TransformXDistance(FX_INT32 dx) const
434{
435    FX_FLOAT fx = a * dx, fy = b * dx;
436    return FXSYS_round(FXSYS_sqrt(fx * fx + fy * fy));
437}
438FX_FLOAT CFX_Matrix::TransformYDistance(FX_FLOAT dy) const
439{
440    FX_FLOAT fx = c * dy, fy = d * dy;
441    return FXSYS_sqrt(fx * fx + fy * fy);
442}
443FX_INT32 CFX_Matrix::TransformYDistance(FX_INT32 dy) const
444{
445    FX_FLOAT fx = c * dy, fy = d * dy;
446    return FXSYS_round(FXSYS_sqrt(fx * fx + fy * fy));
447}
448FX_FLOAT CFX_Matrix::TransformDistance(FX_FLOAT dx, FX_FLOAT dy) const
449{
450    FX_FLOAT fx = a * dx + c * dy, fy = b * dx + d * dy;
451    return FXSYS_sqrt(fx * fx + fy * fy);
452}
453FX_INT32 CFX_Matrix::TransformDistance(FX_INT32 dx, FX_INT32 dy) const
454{
455    FX_FLOAT fx = a * dx + c * dy, fy = b * dx + d * dy;
456    return FXSYS_round(FXSYS_sqrt(fx * fx + fy * fy));
457}
458FX_FLOAT CFX_Matrix::TransformDistance(FX_FLOAT distance) const
459{
460    return distance * (GetXUnit() + GetYUnit()) / 2;
461}
462void CFX_Matrix::TransformVector(CFX_VectorF &v) const
463{
464    FX_FLOAT fx = a * v.x + c * v.y;
465    FX_FLOAT fy = b * v.x + d * v.y;
466    v.x = fx, v.y = fy;
467}
468void CFX_Matrix::TransformVector(CFX_Vector &v) const
469{
470    FX_FLOAT fx = a * v.x + c * v.y;
471    FX_FLOAT fy = b * v.x + d * v.y;
472    v.x = FXSYS_round(fx);
473    v.y = FXSYS_round(fy);
474}
475void CFX_Matrix::TransformPoints(CFX_Point *points, FX_INT32 iCount) const
476{
477    FXSYS_assert(iCount > 0);
478    FX_FLOAT fx, fy;
479    for (FX_INT32 i = 0; i < iCount; i ++) {
480        fx = a * points->x + c * points->y + e;
481        fy = b * points->x + d * points->y + f;
482        points->x = FXSYS_round(fx);
483        points->y = FXSYS_round(fy);
484        points ++;
485    }
486}
487void CFX_Matrix::TransformPoints(CFX_PointF *points, FX_INT32 iCount) const
488{
489    FXSYS_assert(iCount > 0);
490    FX_FLOAT fx, fy;
491    for (FX_INT32 i = 0; i < iCount; i ++) {
492        fx = a * points->x + c * points->y + e;
493        fy = b * points->x + d * points->y + f;
494        points->x = fx, points->y = fy;
495        points ++;
496    }
497}
498void CFX_Matrix::TransformPoint(FX_FLOAT &x, FX_FLOAT &y) const
499{
500    FX_FLOAT fx = a * x + c * y + e;
501    FX_FLOAT fy = b * x + d * y + f;
502    x = fx, y = fy;
503}
504void CFX_Matrix::TransformPoint(FX_INT32 &x, FX_INT32 &y) const
505{
506    FX_FLOAT fx = a * x + c * y + e;
507    FX_FLOAT fy = b * x + d * y + f;
508    x = FXSYS_round(fx);
509    y = FXSYS_round(fy);
510}
511void CFX_Matrix::TransformRect(CFX_RectF &rect) const
512{
513    FX_FLOAT right = rect.right(), bottom = rect.bottom();
514    TransformRect(rect.left, right, bottom, rect.top);
515    rect.width = right - rect.left;
516    rect.height = bottom - rect.top;
517}
518void CFX_Matrix::TransformRect(CFX_Rect &rect) const
519{
520    FX_FLOAT left = (FX_FLOAT)rect.left;
521    FX_FLOAT top = (FX_FLOAT)rect.bottom();
522    FX_FLOAT right = (FX_FLOAT)rect.right();
523    FX_FLOAT bottom = (FX_FLOAT)rect.top;
524    TransformRect(left, right, top, bottom);
525    rect.left = FXSYS_round(left);
526    rect.top = FXSYS_round(bottom);
527    rect.width = FXSYS_round(right - left);
528    rect.height = FXSYS_round(top - bottom);
529}
530void CFX_Matrix::TransformRect(FX_FLOAT& left, FX_FLOAT& right, FX_FLOAT& top, FX_FLOAT& bottom) const
531{
532    FX_FLOAT x[4], y[4];
533    x[0] = left;
534    y[0] = top;
535    x[1] = left;
536    y[1] = bottom;
537    x[2] = right;
538    y[2] = top;
539    x[3] = right;
540    y[3] = bottom;
541    int i;
542    for (i = 0; i < 4; i ++) {
543        Transform(x[i], y[i], x[i], y[i]);
544    }
545    right = left = x[0];
546    top = bottom = y[0];
547    for (i = 1; i < 4; i ++) {
548        if (right < x[i]) {
549            right = x[i];
550        }
551        if (left > x[i]) {
552            left = x[i];
553        }
554        if (top < y[i]) {
555            top = y[i];
556        }
557        if (bottom > y[i]) {
558            bottom = y[i];
559        }
560    }
561}
562