1 /*
2  * Copyright 2014 Adobe Systems Incorporated (http://www.adobe.com/).
3  * All Rights Reserved.
4  *
5  * This software is licensed as OpenSource, under the Apache License, Version
6  * 2.0.
7  * This license is available at: http://opensource.org/licenses/Apache-2.0.
8  */
9 
10 #include <math.h>
11 
12 #include "ac.h"
13 #include "bbox.h"
14 
15 static SegLnkLst *Hlnks, *Vlnks;
16 static int32_t cpFrom, cpTo;
17 
18 void
InitGen(int32_t reason)19 InitGen(int32_t reason)
20 {
21     int32_t i;
22     switch (reason) {
23         case STARTUP:
24         case RESTART:
25             for (i = 0; i < 4; i++)
26                 gSegLists[i] = NULL;
27             Hlnks = Vlnks = NULL;
28     }
29 }
30 
31 static void
LinkSegment(PathElt * e,bool Hflg,HintSeg * seg)32 LinkSegment(PathElt* e, bool Hflg, HintSeg* seg)
33 {
34     SegLnk* newlnk;
35     SegLnkLst *newlst, *globlst;
36     newlnk = (SegLnk*)Alloc(sizeof(SegLnk));
37     newlnk->seg = seg;
38     newlst = (SegLnkLst*)Alloc(sizeof(SegLnkLst));
39     globlst = (SegLnkLst*)Alloc(sizeof(SegLnkLst));
40     globlst->lnk = newlnk;
41     newlst->lnk = newlnk;
42     if (Hflg) {
43         newlst->next = e->Hs;
44         e->Hs = newlst;
45         globlst->next = Hlnks;
46         Hlnks = globlst;
47     } else {
48         newlst->next = e->Vs;
49         e->Vs = newlst;
50         globlst->next = Vlnks;
51         Vlnks = globlst;
52     }
53 }
54 
55 static void
CopySegmentLink(PathElt * e1,PathElt * e2,bool Hflg)56 CopySegmentLink(PathElt* e1, PathElt* e2, bool Hflg)
57 {
58     /* copy reference to first link from e1 to e2 */
59     SegLnkLst* newlst;
60     newlst = (SegLnkLst*)Alloc(sizeof(SegLnkLst));
61     if (Hflg) {
62         newlst->lnk = e1->Hs->lnk;
63         newlst->next = e2->Hs;
64         e2->Hs = newlst;
65     } else {
66         newlst->lnk = e1->Vs->lnk;
67         newlst->next = e2->Vs;
68         e2->Vs = newlst;
69     }
70 }
71 
72 static void
AddSegment(Fixed from,Fixed to,Fixed loc,int32_t lftLstNm,int32_t rghtLstNm,PathElt * e1,PathElt * e2,bool Hflg,int32_t typ)73 AddSegment(Fixed from, Fixed to, Fixed loc, int32_t lftLstNm, int32_t rghtLstNm,
74            PathElt* e1, PathElt* e2, bool Hflg, int32_t typ)
75 {
76     HintSeg *seg, *segList, *prevSeg;
77     int32_t segNm;
78     seg = (HintSeg*)Alloc(sizeof(HintSeg));
79     seg->sLoc = loc;
80     if (from > to) {
81         seg->sMax = from;
82         seg->sMin = to;
83     } else {
84         seg->sMax = to;
85         seg->sMin = from;
86     }
87     seg->sBonus = gBonus;
88     seg->sType = (int16_t)typ;
89     if (e1 != NULL) {
90         if (e1->type == CLOSEPATH)
91             e1 = GetDest(e1);
92         LinkSegment(e1, Hflg, seg);
93         seg->sElt = e1;
94     }
95     if (e2 != NULL) {
96         if (e2->type == CLOSEPATH)
97             e2 = GetDest(e2);
98         if (e1 != NULL)
99             CopySegmentLink(e1, e2, Hflg);
100         if (e1 == NULL || e2 == e1->prev)
101             seg->sElt = e2;
102     }
103     segNm = (from > to) ? lftLstNm : rghtLstNm;
104     segList = gSegLists[segNm];
105     prevSeg = NULL;
106     while (true) {             /* keep list in increasing order by sLoc */
107         if (segList == NULL) { /* at end of list */
108             if (prevSeg == NULL) {
109                 gSegLists[segNm] = seg;
110                 break;
111             }
112             prevSeg->sNxt = seg;
113             break;
114         }
115         if (segList->sLoc >= loc) { /* insert before this one */
116             if (prevSeg == NULL)
117                 gSegLists[segNm] = seg;
118             else
119                 prevSeg->sNxt = seg;
120             seg->sNxt = segList;
121             break;
122         }
123         prevSeg = segList;
124         segList = segList->sNxt;
125     }
126 }
127 
128 void
AddVSegment(Fixed from,Fixed to,Fixed loc,PathElt * p1,PathElt * p2,int32_t typ,int32_t i)129 AddVSegment(Fixed from, Fixed to, Fixed loc, PathElt* p1, PathElt* p2,
130             int32_t typ, int32_t i)
131 {
132     LogMsg(LOGDEBUG, OK, "add vseg %g %g to %g %g %d", FixToDbl(loc),
133            FixToDbl(-from), FixToDbl(loc), FixToDbl(-to), i);
134 
135     AddSegment(from, to, loc, 1, 0, p1, p2, false, typ);
136 }
137 
138 void
AddHSegment(Fixed from,Fixed to,Fixed loc,PathElt * p1,PathElt * p2,int32_t typ,int32_t i)139 AddHSegment(Fixed from, Fixed to, Fixed loc, PathElt* p1, PathElt* p2,
140             int32_t typ, int32_t i)
141 {
142     LogMsg(LOGDEBUG, OK, "add hseg %g %g to %g %g %d", FixToDbl(from),
143            FixToDbl(-loc), FixToDbl(to), FixToDbl(-loc), i);
144 
145     AddSegment(from, to, loc, 2, 3, p1, p2, true, typ);
146 }
147 
148 static Fixed
CPFrom(Fixed cp2,Fixed cp3)149 CPFrom(Fixed cp2, Fixed cp3)
150 {
151     Fixed val =
152       2 * (((cp3 - cp2) * cpFrom) /
153            200); /*DEBUG 8 BIT: hack to get same rounding as old version */
154     val += cp2;
155 
156     DEBUG_ROUND(val)
157     return val; /* DEBUG 8 BIT to match results with 7 bit fractions */
158 }
159 
160 static Fixed
CPTo(Fixed cp0,Fixed cp1)161 CPTo(Fixed cp0, Fixed cp1)
162 {
163     Fixed val =
164       2 * (((cp1 - cp0) * cpTo) /
165            200); /*DEBUG 8 BIT: hack to get same rounding as old version */
166     val += cp0;
167     DEBUG_ROUND(val)
168     return val; /* DEBUG 8 BIT to match results with 7 bit fractions */
169 }
170 
171 static bool
TestBend(Fixed x0,Fixed y0,Fixed x1,Fixed y1,Fixed x2,Fixed y2)172 TestBend(Fixed x0, Fixed y0, Fixed x1, Fixed y1, Fixed x2, Fixed y2)
173 {
174     /* return true if bend angle is sharp enough (135 degrees or less) */
175     float dx1, dy1, dx2, dy2, dotprod, lensqprod;
176     acfixtopflt(x1 - x0, &dx1);
177     acfixtopflt(y1 - y0, &dy1);
178     acfixtopflt(x2 - x1, &dx2);
179     acfixtopflt(y2 - y1, &dy2);
180     dotprod = dx1 * dx2 + dy1 * dy2;
181     lensqprod = (dx1 * dx1 + dy1 * dy1) * (dx2 * dx2 + dy2 * dy2);
182     return roundf((dotprod * dotprod / lensqprod) * 1000) / 1000 <= .5f;
183 }
184 
185 #define TestTan(d1, d2) (abs(d1) > (abs(d2) * gBendTan) / 1000)
186 #define FRound(x) FTrunc(FRnd(x))
187 
188 static bool
IsCCW(Fixed x0,Fixed y0,Fixed x1,Fixed y1,Fixed x2,Fixed y2)189 IsCCW(Fixed x0, Fixed y0, Fixed x1, Fixed y1, Fixed x2, Fixed y2)
190 {
191     /* returns true if (x0,y0) -> (x1,y1) -> (x2,y2) is counter clockwise
192          in glyph space */
193     int32_t dx0, dy0, dx1, dy1;
194     bool ccw;
195     dx0 = FRound(x1 - x0);
196     dy0 = -FRound(y1 - y0);
197     dx1 = FRound(x2 - x1);
198     dy1 = -FRound(y2 - y1);
199     ccw = (dx0 * dy1) >= (dx1 * dy0);
200     return ccw;
201 }
202 
203 static void
DoHBendsNxt(Fixed x0,Fixed y0,Fixed x1,Fixed y1,PathElt * p)204 DoHBendsNxt(Fixed x0, Fixed y0, Fixed x1, Fixed y1, PathElt* p)
205 {
206     Fixed x2, y2, x3, y3;
207     bool ysame;
208     if (y0 == y1)
209         return;
210     NxtForBend(p, &x2, &y2, &x3, &y3);
211     ysame = ProdLt0(y2 - y1, y1 - y0); /* y0 and y2 on same side of y1 */
212     if (ysame ||
213         (TestTan(x1 - x2, y1 - y2) &&
214          (ProdLt0(x2 - x1, x1 - x0) ||
215           (IsVertical(x0, y0, x1, y1) && TestBend(x0, y0, x1, y1, x2, y2))))) {
216         Fixed strt, end;
217         Fixed delta = FixHalfMul(gBendLength);
218         bool doboth = false;
219         if ((x0 <= x1 && x1 < x2) || (x0 < x1 && x1 <= x2)) {
220             /* do nothing */
221         } else if ((x2 < x1 && x1 <= x0) || (x2 <= x1 && x1 < x0))
222             delta = -delta;
223         else if (ysame) {
224             bool ccw;
225             bool above = y0 < y1;
226             ccw = IsCCW(x0, y0, x1, y1, x2, y2);
227             if (above != ccw)
228                 delta = -delta;
229         } else
230             doboth = true;
231         strt = x1 - delta;
232         end = x1 + delta;
233         AddHSegment(strt, end, y1, p, NULL, sBEND, 0);
234         if (doboth)
235             AddHSegment(end, strt, y1, p, NULL, sBEND, 1);
236     }
237 }
238 
239 static void
DoHBendsPrv(Fixed x0,Fixed y0,Fixed x1,Fixed y1,PathElt * p)240 DoHBendsPrv(Fixed x0, Fixed y0, Fixed x1, Fixed y1, PathElt* p)
241 {
242     Fixed x2, y2;
243     bool ysame;
244     if (y0 == y1)
245         return;
246     PrvForBend(p, &x2, &y2);
247     ysame = ProdLt0(y2 - y0, y0 - y1);
248     if (ysame ||
249         (TestTan(x0 - x2, y0 - y2) &&
250          (ProdLt0(x2 - x0, x0 - x1) ||
251           (IsVertical(x0, y0, x1, y1) && TestBend(x2, y2, x0, y0, x1, y1))))) {
252         Fixed strt, end;
253         Fixed delta = FixHalfMul(gBendLength);
254         bool doboth = false;
255         if ((x2 < x0 && x0 <= x1) || (x2 <= x0 && x0 < x1)) {
256             /* do nothing */
257         } else if ((x1 < x0 && x0 <= x2) || (x1 <= x0 && x0 < x2))
258             delta = -delta;
259         else if (ysame) {
260             bool ccw;
261             bool above = y2 < y0;
262             ccw = IsCCW(x2, y2, x0, y0, x1, y1);
263             if (above != ccw)
264                 delta = -delta;
265         }
266         strt = x0 - delta;
267         end = x0 + delta;
268         AddHSegment(strt, end, y0, p->prev, NULL, sBEND, 2);
269         if (doboth)
270             AddHSegment(end, strt, y0, p->prev, NULL, sBEND, 3);
271     }
272 }
273 
274 static void
DoVBendsNxt(Fixed x0,Fixed y0,Fixed x1,Fixed y1,PathElt * p)275 DoVBendsNxt(Fixed x0, Fixed y0, Fixed x1, Fixed y1, PathElt* p)
276 {
277     Fixed x2, y2, x3, y3;
278     bool xsame;
279     if (x0 == x1)
280         return;
281     NxtForBend(p, &x2, &y2, &x3, &y3);
282     xsame = ProdLt0(x2 - x1, x1 - x0);
283     if (xsame ||
284         (TestTan(y1 - y2, x1 - x2) &&
285          (ProdLt0(y2 - y1, y1 - y0) || (IsHorizontal(x0, y0, x1, y1) &&
286                                         TestBend(x0, y0, x1, y1, x2, y2))))) {
287         Fixed strt, end;
288         Fixed delta = FixHalfMul(gBendLength);
289         bool doboth = false;
290         if ((y0 <= y1 && y1 < y2) || (y0 < y1 && y1 <= y2)) {
291             /* do nothing */
292         } else if ((y2 < y1 && y1 <= y0) || (y2 <= y1 && y1 < y0))
293             delta = -delta;
294         else if (xsame) {
295             bool right = x0 > x1;
296             bool ccw = IsCCW(x0, y0, x1, y1, x2, y2);
297             if (right != ccw)
298                 delta = -delta;
299             delta = -delta;
300         } else
301             doboth = true;
302         strt = y1 - delta;
303         end = y1 + delta;
304         AddVSegment(strt, end, x1, p, NULL, sBEND, 0);
305         if (doboth)
306             AddVSegment(end, strt, x1, p, NULL, sBEND, 1);
307     }
308 }
309 
310 static void
DoVBendsPrv(Fixed x0,Fixed y0,Fixed x1,Fixed y1,PathElt * p)311 DoVBendsPrv(Fixed x0, Fixed y0, Fixed x1, Fixed y1, PathElt* p)
312 {
313     Fixed x2, y2;
314     bool xsame;
315     if (x0 == x1)
316         return;
317     PrvForBend(p, &x2, &y2);
318     xsame = ProdLt0(x2 - x0, x0 - x1);
319     if (xsame ||
320         (TestTan(y0 - y2, x0 - x2) &&
321          (ProdLt0(y2 - y0, y0 - y1) || (IsHorizontal(x0, y0, x1, y1) &&
322                                         TestBend(x2, y2, x0, y0, x1, y1))))) {
323         Fixed strt, end;
324         Fixed delta = FixHalfMul(gBendLength);
325         bool doboth = false;
326         if ((y2 < y0 && y0 <= y1) || (y2 <= y0 && y0 < y1)) {
327             /* do nothing */
328         } else if ((y1 < y0 && y0 <= y2) || (y1 <= y0 && y0 < y2))
329             delta = -delta;
330         else if (xsame) {
331             bool right = x0 > x1;
332             bool ccw = IsCCW(x2, y2, x0, y0, x1, y1);
333             if (right != ccw)
334                 delta = -delta;
335             delta = -delta;
336         }
337         strt = y0 - delta;
338         end = y0 + delta;
339         AddVSegment(strt, end, x0, p->prev, NULL, sBEND, 2);
340         if (doboth)
341             AddVSegment(end, strt, x0, p->prev, NULL, sBEND, 3);
342     }
343 }
344 
345 static void
MergeLnkSegs(HintSeg * seg1,HintSeg * seg2,SegLnkLst * lst)346 MergeLnkSegs(HintSeg* seg1, HintSeg* seg2, SegLnkLst* lst)
347 {
348     /* replace lnk refs to seg1 by seg2 */
349     while (lst != NULL) {
350         SegLnk* lnk = lst->lnk;
351         if (lnk->seg == seg1)
352             lnk->seg = seg2;
353         lst = lst->next;
354     }
355 }
356 
357 static void
MergeHSegs(HintSeg * seg1,HintSeg * seg2)358 MergeHSegs(HintSeg* seg1, HintSeg* seg2)
359 {
360     MergeLnkSegs(seg1, seg2, Hlnks);
361 }
362 
363 static void
MergeVSegs(HintSeg * seg1,HintSeg * seg2)364 MergeVSegs(HintSeg* seg1, HintSeg* seg2)
365 {
366     MergeLnkSegs(seg1, seg2, Vlnks);
367 }
368 
369 static void
ReportRemSeg(int32_t l,HintSeg * lst)370 ReportRemSeg(int32_t l, HintSeg* lst)
371 {
372     Fixed from = 0, to = 0, loc = 0;
373     /* this assumes !YgoesUp */
374     switch (l) {
375         case 1:
376         case 2:
377             from = lst->sMax;
378             to = lst->sMin;
379             break;
380         case 0:
381         case 3:
382             from = lst->sMin;
383             to = lst->sMax;
384             break;
385     }
386     loc = lst->sLoc;
387     switch (l) {
388         case 0:
389         case 1:
390             LogMsg(LOGDEBUG, OK, "rem vseg %g %g to %g %g", FixToDbl(loc),
391                    FixToDbl(-from), FixToDbl(loc), FixToDbl(-to));
392             break;
393         case 2:
394         case 3:
395             LogMsg(LOGDEBUG, OK, "rem hseg %g %g to %g %g", FixToDbl(from),
396                    FixToDbl(-loc), FixToDbl(to), FixToDbl(-loc));
397             break;
398     }
399 }
400 
401 /* Filters out bogus bend segments. */
402 static void
RemExtraBends(int32_t l0,int32_t l1)403 RemExtraBends(int32_t l0, int32_t l1)
404 {
405     HintSeg* lst0 = gSegLists[l0];
406     HintSeg* prv = NULL;
407     while (lst0 != NULL) {
408         HintSeg* nxt = lst0->sNxt;
409         Fixed loc0 = lst0->sLoc;
410         HintSeg* lst = gSegLists[l1];
411         HintSeg* p = NULL;
412         while (lst != NULL) {
413             HintSeg* n = lst->sNxt;
414             Fixed loc = lst->sLoc;
415             if (loc > loc0)
416                 break; /* list in increasing order by sLoc */
417             if (loc == loc0 && lst->sMin < lst0->sMax &&
418                 lst->sMax > lst0->sMin) {
419                 if (lst0->sType == sBEND && lst->sType != sBEND &&
420                     lst->sType != sGHOST &&
421                     (lst->sMax - lst->sMin) > (lst0->sMax - lst0->sMin) * 3) {
422                     /* delete lst0 */
423                     if (prv == NULL)
424                         gSegLists[l0] = nxt;
425                     else
426                         prv->sNxt = nxt;
427                     ReportRemSeg(l0, lst0);
428                     lst0 = prv;
429                     break;
430                 }
431                 if (lst->sType == sBEND && lst0->sType != sBEND &&
432                     lst0->sType != sGHOST &&
433                     (lst0->sMax - lst0->sMin) > (lst->sMax - lst->sMin) * 3) {
434                     /* delete lst */
435                     if (p == NULL)
436                         gSegLists[l1] = n;
437                     else
438                         p->sNxt = n;
439                     ReportRemSeg(l1, lst);
440                     lst = p;
441                 }
442             }
443             p = lst;
444             lst = n;
445         }
446         prv = lst0;
447         lst0 = nxt;
448     }
449 }
450 
451 static void
CompactList(int32_t i,void (* nm)(HintSeg *,HintSeg *))452 CompactList(int32_t i, void (*nm)(HintSeg*, HintSeg*))
453 {
454     HintSeg* lst = gSegLists[i];
455     HintSeg* prv = NULL;
456     while (lst != NULL) {
457         bool flg;
458         HintSeg* nxt = lst->sNxt;
459         HintSeg* nxtprv = lst;
460         while (true) {
461             Fixed lstmin, lstmax, nxtmin, nxtmax;
462             if ((nxt == NULL) || (nxt->sLoc > lst->sLoc)) {
463                 flg = true;
464                 break;
465             }
466             lstmin = lst->sMin;
467             lstmax = lst->sMax;
468             nxtmin = nxt->sMin;
469             nxtmax = nxt->sMax;
470             if (lstmax >= nxtmin && lstmin <= nxtmax) {
471                 /* do not worry about YgoesUp since "sMax" is really max in
472                  device space, not in glyph space */
473                 if (abs(lstmax - lstmin) > abs(nxtmax - nxtmin)) {
474                     /* merge into lst and remove nxt */
475                     (*nm)(nxt, lst);
476                     lst->sMin = NUMMIN(lstmin, nxtmin);
477                     lst->sMax = NUMMAX(lstmax, nxtmax);
478                     lst->sBonus = NUMMAX(lst->sBonus, nxt->sBonus);
479                     nxtprv->sNxt = nxt->sNxt;
480                 } else { /* merge into nxt and remove lst */
481                     (*nm)(lst, nxt);
482                     nxt->sMin = NUMMIN(lstmin, nxtmin);
483                     nxt->sMax = NUMMAX(lstmax, nxtmax);
484                     nxt->sBonus = NUMMAX(lst->sBonus, nxt->sBonus);
485                     lst = lst->sNxt;
486                     if (prv == NULL)
487                         gSegLists[i] = lst;
488                     else
489                         prv->sNxt = lst;
490                 }
491                 flg = false;
492                 break;
493             }
494             nxtprv = nxt;
495             nxt = nxt->sNxt;
496         }
497         if (flg) {
498             prv = lst;
499             lst = lst->sNxt;
500         }
501     }
502 }
503 
504 static Fixed
PickVSpot(Fixed x0,Fixed y0,Fixed x1,Fixed y1,Fixed px1,Fixed py1,Fixed px2,Fixed py2,Fixed prvx,Fixed prvy,Fixed nxtx,Fixed nxty)505 PickVSpot(Fixed x0, Fixed y0, Fixed x1, Fixed y1, Fixed px1, Fixed py1,
506           Fixed px2, Fixed py2, Fixed prvx, Fixed prvy, Fixed nxtx, Fixed nxty)
507 {
508     Fixed a1, a2;
509     if (x0 == px1 && x1 != px2)
510         return x0;
511     if (x0 != px1 && x1 == px2)
512         return x1;
513     if (x0 == prvx && x1 != nxtx)
514         return x0;
515     if (x0 != prvx && x1 == nxtx)
516         return x1;
517     a1 = abs(py1 - y0);
518     a2 = abs(py2 - y1);
519     if (a1 > a2)
520         return x0;
521     a1 = abs(py2 - y1);
522     a2 = abs(py1 - y0);
523     if (a1 > a2)
524         return x1;
525     if (x0 == prvx && x1 == nxtx) {
526         a1 = abs(y0 - prvy);
527         a2 = abs(y1 - nxty);
528         if (a1 > a2)
529             return x0;
530         return x1;
531     }
532     return FixHalfMul(x0 + x1);
533 }
534 
535 static Fixed
AdjDist(Fixed d,Fixed q)536 AdjDist(Fixed d, Fixed q)
537 {
538     Fixed val;
539     if (q == FixOne) {
540         DEBUG_ROUND(d) /* DEBUG 8 BIT */
541         return d;
542     }
543     val = (d * q) >> 8;
544     DEBUG_ROUND(val) /* DEBUG 8 BIT */
545     return val;
546 }
547 
548 /* serifs of ITCGaramond Ultra have points that are not quite horizontal
549  e.g., in H: (53,51)(74,52)(116,54)
550  the following was added to let these through */
551 static bool
TstFlat(Fixed dmn,Fixed dmx)552 TstFlat(Fixed dmn, Fixed dmx)
553 {
554     if (dmn < 0)
555         dmn = -dmn;
556     if (dmx < 0)
557         dmx = -dmx;
558     return (dmx >= PSDist(50) && dmn <= PSDist(4));
559 }
560 
561 static bool
NxtHorz(Fixed x,Fixed y,PathElt * p)562 NxtHorz(Fixed x, Fixed y, PathElt* p)
563 {
564     Fixed x2, y2, x3, y3;
565     NxtForBend(p, &x2, &y2, &x3, &y3);
566     return TstFlat(y2 - y, x2 - x);
567 }
568 
569 static bool
PrvHorz(Fixed x,Fixed y,PathElt * p)570 PrvHorz(Fixed x, Fixed y, PathElt* p)
571 {
572     Fixed x2, y2;
573     PrvForBend(p, &x2, &y2);
574     return TstFlat(y2 - y, x2 - x);
575 }
576 
577 static bool
NxtVert(Fixed x,Fixed y,PathElt * p)578 NxtVert(Fixed x, Fixed y, PathElt* p)
579 {
580     Fixed x2, y2, x3, y3;
581     NxtForBend(p, &x2, &y2, &x3, &y3);
582     return TstFlat(x2 - x, y2 - y);
583 }
584 
585 static bool
PrvVert(Fixed x,Fixed y,PathElt * p)586 PrvVert(Fixed x, Fixed y, PathElt* p)
587 {
588     Fixed x2, y2;
589     PrvForBend(p, &x2, &y2);
590     return TstFlat(x2 - x, y2 - y);
591 }
592 
593 /* PrvSameDir and NxtSameDir were added to check the direction of a
594  path and not add a band if the point is not at an extreme and is
595  going in the same direction as the previous path. */
596 static bool
TstSameDir(Fixed x0,Fixed y0,Fixed x1,Fixed y1,Fixed x2,Fixed y2)597 TstSameDir(Fixed x0, Fixed y0, Fixed x1, Fixed y1, Fixed x2, Fixed y2)
598 {
599     if (ProdLt0(y0 - y1, y1 - y2) || ProdLt0(x0 - x1, x1 - x2))
600         return false;
601     return !TestBend(x0, y0, x1, y1, x2, y2);
602 }
603 
604 static bool
PrvSameDir(Fixed x0,Fixed y0,Fixed x1,Fixed y1,PathElt * p)605 PrvSameDir(Fixed x0, Fixed y0, Fixed x1, Fixed y1, PathElt* p)
606 {
607     Fixed x2, y2;
608     p = PrvForBend(p, &x2, &y2);
609     if (p != NULL && p->type == CURVETO && p->prev != NULL)
610         GetEndPoint(p->prev, &x2, &y2);
611     return TstSameDir(x0, y0, x1, y1, x2, y2);
612 }
613 
614 static bool
NxtSameDir(Fixed x0,Fixed y0,Fixed x1,Fixed y1,PathElt * p)615 NxtSameDir(Fixed x0, Fixed y0, Fixed x1, Fixed y1, PathElt* p)
616 {
617     Fixed x2, y2, x3, y3;
618     p = NxtForBend(p, &x2, &y2, &x3, &y3);
619     if (p != NULL && p->type == CURVETO) {
620         x2 = p->x3;
621         y2 = p->y3;
622     }
623     return TstSameDir(x0, y0, x1, y1, x2, y2);
624 }
625 
626 void
GenVPts(int32_t specialGlyphType)627 GenVPts(int32_t specialGlyphType)
628 {
629     /* specialGlyphType 1 = upper; -1 = lower; 0 = neither */
630     PathElt *p, *fl;
631     bool isVert, flex1, flex2;
632     Fixed flx0, fly0, llx, lly, urx, ury, yavg, yend, ydist, q, q2;
633     Fixed prvx, prvy, nxtx, nxty, xx, yy, yd2;
634     p = gPathStart;
635     flex1 = flex2 = false;
636     cpTo = gCPpercent;
637     cpFrom = 100 - cpTo;
638     flx0 = fly0 = 0;
639     fl = NULL;
640     while (p != NULL) {
641         Fixed x0, y0, x1, y1;
642         GetEndPoints(p, &x0, &y0, &x1, &y1);
643         if (p->type == CURVETO) {
644             Fixed px1, py1, px2, py2;
645             isVert = false;
646             if (p->isFlex) {
647                 if (flex1) {
648                     if (IsVertical(flx0, fly0, x1, y1))
649                         AddVSegment(fly0, y1, x1, fl->prev, p, sLINE, 4);
650                     flex1 = false;
651                     flex2 = true;
652                 } else {
653                     flex1 = true;
654                     flex2 = false;
655                     flx0 = x0;
656                     fly0 = y0;
657                     fl = p;
658                 }
659             } else
660                 flex1 = flex2 = false;
661             px1 = p->x1;
662             py1 = p->y1;
663             px2 = p->x2;
664             py2 = p->y2;
665             if (!flex2) {
666                 if ((q = VertQuo(px1, py1, x0, y0)) ==
667                     0) /* first two not vertical */
668                     DoVBendsPrv(x0, y0, px1, py1, p);
669                 else {
670                     isVert = true;
671                     if (px1 == x0 ||
672                         (px2 != x1 && (PrvVert(px1, py1, p) ||
673                                        !PrvSameDir(x1, y1, x0, y0, p)))) {
674                         if ((q2 = VertQuo(px2, py2, x0, y0)) > 0 &&
675                             ProdGe0(py1 - y0, py2 - y0) &&
676                             abs(py2 - y0) > abs(py1 - y0)) {
677                             ydist = AdjDist(CPTo(py1, py2) - y0, q2);
678                             yend = AdjDist(CPTo(y0, py1) - y0, q);
679                             if (abs(yend) > abs(ydist))
680                                 ydist = yend;
681                             AddVSegment(y0, y0 + ydist, x0, p->prev, p, sCURVE,
682                                         5);
683                         } else {
684                             ydist = AdjDist(CPTo(y0, py1) - y0, q);
685                             AddVSegment(y0, CPTo(y0, py1), x0, p->prev, p,
686                                         sCURVE, 6);
687                         }
688                     }
689                 }
690             }
691             if (!flex1) {
692                 if ((q = VertQuo(px2, py2, x1, y1)) ==
693                     0) /* last 2 not vertical */
694                     DoVBendsNxt(px2, py2, x1, y1, p);
695                 else if (px2 == x1 ||
696                          (px1 != x0 && (NxtVert(px2, py2, p) ||
697                                         !NxtSameDir(x0, y0, x1, y1, p)))) {
698                     ydist = AdjDist(y1 - CPFrom(py2, y1), q);
699                     isVert = true;
700                     q2 = VertQuo(x0, y0, x1, y1);
701                     yd2 = (q2 > 0) ? AdjDist(y1 - y0, q2) : 0;
702                     if (isVert && q2 > 0 && abs(yd2) > abs(ydist)) {
703                         if (x0 == px1 && px1 == px2 && px2 == x1)
704                             ReportLinearCurve(p, x0, y0, x1, y1);
705                         ydist = FixHalfMul(yd2);
706                         yavg = FixHalfMul(y0 + y1);
707                         PrvForBend(p, &prvx, &prvy);
708                         NxtForBend(p, &nxtx, &nxty, &xx, &yy);
709                         AddVSegment(yavg - ydist, yavg + ydist,
710                                     PickVSpot(x0, y0, x1, y1, px1, py1, px2,
711                                               py2, prvx, prvy, nxtx, nxty),
712                                     p, NULL, sCURVE, 7);
713                     } else {
714                         q2 = VertQuo(px1, py1, x1, y1);
715                         if (q2 > 0 && ProdGe0(py1 - y1, py2 - y1) &&
716                             abs(py2 - y1) < abs(py1 - y1)) {
717                             yend = AdjDist(y1 - CPFrom(py1, py2), q2);
718                             if (abs(yend) > abs(ydist))
719                                 ydist = yend;
720                             AddVSegment(y1 - ydist, y1, x1, p, NULL, sCURVE, 8);
721                         } else
722                             AddVSegment(y1 - ydist, y1, x1, p, NULL, sCURVE, 9);
723                     }
724                 }
725             }
726             if (!flex1 && !flex2) {
727                 Fixed minx, maxx;
728                 maxx = NUMMAX(x0, x1);
729                 minx = NUMMIN(x0, x1);
730                 if (px1 - maxx >= FixTwo || px2 - maxx >= FixTwo ||
731                     px1 - minx <= FixTwo || px2 - minx <= FixTwo) {
732                     FindCurveBBox(x0, y0, px1, py1, px2, py2, x1, y1, &llx,
733                                   &lly, &urx, &ury);
734                     if (urx - maxx > FixTwo || minx - llx > FixTwo) {
735                         Fixed loc, frst, lst;
736                         loc = (minx - llx > urx - maxx) ? llx : urx;
737                         CheckBBoxEdge(p, true, loc, &frst, &lst);
738                         yavg = FixHalfMul(frst + lst);
739                         ydist = (frst == lst) ? (y1 - y0) / 10
740                                               : FixHalfMul(lst - frst);
741                         if (abs(ydist) < gBendLength)
742                             ydist = (ydist > 0) ? FixHalfMul(gBendLength)
743                                                 : FixHalfMul(-gBendLength);
744                         AddVSegment(yavg - ydist, yavg + ydist, loc, p, NULL,
745                                     sCURVE, 10);
746                     }
747                 }
748             }
749         } else if (p->type == MOVETO) {
750             gBonus = 0;
751             if (specialGlyphType == -1) {
752                 if (IsLower(p))
753                     gBonus = FixInt(200);
754             } else if (specialGlyphType == 1) {
755                 if (IsUpper(p))
756                     gBonus = FixInt(200);
757             }
758         } else if (!IsTiny(p)) {
759             if ((q = VertQuo(x0, y0, x1, y1)) > 0) {
760                 if (x0 == x1)
761                     AddVSegment(y0, y1, x0, p->prev, p, sLINE, 11);
762                 else {
763                     if (q < FixQuarter)
764                         q = FixQuarter;
765                     ydist = FixHalfMul(AdjDist(y1 - y0, q));
766                     yavg = FixHalfMul(y0 + y1);
767                     PrvForBend(p, &prvx, &prvy);
768                     NxtForBend(p, &nxtx, &nxty, &xx, &yy);
769                     AddVSegment(yavg - ydist, yavg + ydist,
770                                 PickVSpot(x0, y0, x1, y1, x0, y0, x1, y1, prvx,
771                                           prvy, nxtx, nxty),
772                                 p, NULL, sLINE, 12);
773                     if (abs(x0 - x1) <= FixTwo)
774                         ReportNonVError(x0, y0, x1, y1);
775                 }
776             } else {
777                 DoVBendsNxt(x0, y0, x1, y1, p);
778                 DoVBendsPrv(x0, y0, x1, y1, p);
779             }
780         }
781         p = p->next;
782     }
783     CompactList(0, MergeVSegs);
784     CompactList(1, MergeVSegs);
785     RemExtraBends(0, 1);
786     leftList = gSegLists[0];
787     rightList = gSegLists[1];
788 }
789 
790 bool
InBlueBand(Fixed loc,int32_t n,Fixed * p)791 InBlueBand(Fixed loc, int32_t n, Fixed* p)
792 {
793     int i;
794     Fixed y;
795     if (n <= 0)
796         return false;
797     y = -loc;
798     /* Augment the blue band by bluefuzz in each direction.  This will
799        result in "near misses" being hinted and so adjusted by the
800        PS interpreter. */
801     for (i = 0; i < n; i += 2)
802         if ((p[i] - gBlueFuzz) <= y && (p[i + 1] + gBlueFuzz) >= y)
803             return true;
804     return false;
805 }
806 
807 static Fixed
PickHSpot(Fixed x0,Fixed y0,Fixed x1,Fixed y1,Fixed xdist,Fixed px1,Fixed py1,Fixed px2,Fixed py2,Fixed prvx,Fixed prvy,Fixed nxtx,Fixed nxty)808 PickHSpot(Fixed x0, Fixed y0, Fixed x1, Fixed y1, Fixed xdist, Fixed px1,
809           Fixed py1, Fixed px2, Fixed py2, Fixed prvx, Fixed prvy, Fixed nxtx,
810           Fixed nxty)
811 {
812     bool topSeg = (xdist < 0) ? true : false;
813     bool inBlue0, inBlue1;
814     if (topSeg) {
815         inBlue0 = InBlueBand(y0, gLenTopBands, gTopBands);
816         inBlue1 = InBlueBand(y1, gLenTopBands, gTopBands);
817     } else {
818         inBlue0 = InBlueBand(y0, gLenBotBands, gBotBands);
819         inBlue1 = InBlueBand(y1, gLenBotBands, gBotBands);
820     }
821     if (inBlue0 && !inBlue1)
822         return y0;
823     if (inBlue1 && !inBlue0)
824         return y1;
825     if (y0 == py1 && y1 != py2)
826         return y0;
827     if (y0 != py1 && y1 == py2)
828         return y1;
829     if (y0 == prvy && y1 != nxty)
830         return y0;
831     if (y0 != prvy && y1 == nxty)
832         return y1;
833     if (inBlue0 && inBlue1) {
834         Fixed upper, lower;
835         if (y0 > y1) {
836             upper = y1;
837             lower = y0;
838         } else {
839             upper = y0;
840             lower = y1;
841         }
842         return topSeg ? upper : lower;
843     }
844     if (abs(px1 - x0) > abs(px2 - x1))
845         return y0;
846     if (abs(px2 - x1) > abs(px1 - x0))
847         return y1;
848     if (y0 == prvy && y1 == nxty) {
849         if (abs(x0 - prvx) > abs(x1 - nxtx))
850             return y0;
851         return y1;
852     }
853     return FixHalfMul(y0 + y1);
854 }
855 
856 void
GenHPts(void)857 GenHPts(void)
858 {
859     PathElt *p, *fl;
860     bool isHoriz, flex1, flex2;
861     Fixed flx0, fly0, llx, lly, urx, ury, xavg, xend, xdist, q, q2;
862     Fixed prvx, prvy, nxtx, nxty, xx, yy, xd2;
863     p = gPathStart;
864     gBonus = 0;
865     flx0 = fly0 = 0;
866     fl = NULL;
867     flex1 = flex2 = false;
868     cpTo = gCPpercent;
869     cpFrom = 100 - cpTo;
870     while (p != NULL) {
871         Fixed x0, y0, x1, y1;
872         GetEndPoints(p, &x0, &y0, &x1, &y1);
873         if (p->type == CURVETO) {
874             Fixed px1, py1, px2, py2;
875             isHoriz = false;
876             if (p->isFlex) {
877                 if (flex1) {
878                     flex1 = false;
879                     flex2 = true;
880                     if (IsHorizontal(flx0, fly0, x1, y1))
881                         AddHSegment(flx0, x1, y1, fl->prev, p, sLINE, 4);
882                 } else {
883                     flex1 = true;
884                     flex2 = false;
885                     flx0 = x0;
886                     fly0 = y0;
887                     fl = p;
888                 }
889             } else
890                 flex1 = flex2 = false;
891             px1 = p->x1;
892             py1 = p->y1;
893             px2 = p->x2;
894             py2 = p->y2;
895             if (!flex2) {
896                 if ((q = HorzQuo(px1, py1, x0, y0)) == 0)
897                     DoHBendsPrv(x0, y0, px1, py1, p);
898                 else {
899                     isHoriz = true;
900                     if (py1 == y0 ||
901                         (py2 != y1 && (PrvHorz(px1, py1, p) ||
902                                        !PrvSameDir(x1, y1, x0, y0, p)))) {
903                         if ((q2 = HorzQuo(px2, py2, x0, y0)) > 0 &&
904                             ProdGe0(px1 - x0, px2 - x0) &&
905                             abs(px2 - x0) > abs(px1 - x0)) {
906                             xdist = AdjDist(CPTo(px1, px2) - x0, q2);
907                             xend = AdjDist(CPTo(x0, px1) - x0, q);
908                             if (abs(xend) > abs(xdist))
909                                 xdist = xend;
910                             AddHSegment(x0, x0 + xdist, y0, p->prev, p, sCURVE,
911                                         5);
912                         } else {
913                             xdist = AdjDist(CPTo(x0, px1) - x0, q);
914                             AddHSegment(x0, x0 + xdist, y0, p->prev, p, sCURVE,
915                                         6);
916                         }
917                     }
918                 }
919             }
920             if (!flex1) {
921                 if ((q = HorzQuo(px2, py2, x1, y1)) == 0)
922                     DoHBendsNxt(px2, py2, x1, y1, p);
923                 else if (py2 == y1 ||
924                          (py1 != y0 && (NxtHorz(px2, py2, p) ||
925                                         !NxtSameDir(x0, y0, x1, y1, p)))) {
926                     xdist = AdjDist(x1 - CPFrom(px2, x1), q);
927                     q2 = HorzQuo(x0, y0, x1, y1);
928                     isHoriz = true;
929                     xd2 = (q2 > 0) ? AdjDist(x1 - x0, q2) : 0;
930                     if (isHoriz && q2 > 0 && abs(xd2) > abs(xdist)) {
931                         Fixed hspot;
932                         if (y0 == py1 && py1 == py2 && py2 == y1)
933                             ReportLinearCurve(p, x0, y0, x1, y1);
934                         PrvForBend(p, &prvx, &prvy);
935                         NxtForBend(p, &nxtx, &nxty, &xx, &yy);
936                         xdist = FixHalfMul(xd2);
937                         xavg = FixHalfMul(x0 + x1);
938                         hspot = PickHSpot(x0, y0, x1, y1, xdist, px1, py1, px2,
939                                           py2, prvx, prvy, nxtx, nxty);
940                         AddHSegment(xavg - xdist, xavg + xdist, hspot, p, NULL,
941                                     sCURVE, 7);
942                     } else {
943                         q2 = HorzQuo(px1, py1, x1, y1);
944                         if (q2 > 0 && ProdGe0(px1 - x1, px2 - x1) &&
945                             abs(px2 - x1) < abs(px1 - x1)) {
946                             xend = AdjDist(x1 - CPFrom(px1, px2), q2);
947                             if (abs(xend) > abs(xdist))
948                                 xdist = xend;
949                             AddHSegment(x1 - xdist, x1, y1, p, NULL, sCURVE, 8);
950                         } else
951                             AddHSegment(x1 - xdist, x1, y1, p, NULL, sCURVE, 9);
952                     }
953                 }
954             }
955             if (!flex1 && !flex2) {
956                 Fixed miny, maxy;
957                 maxy = NUMMAX(y0, y1);
958                 miny = NUMMIN(y0, y1);
959                 if (py1 - maxy >= FixTwo || py2 - maxy >= FixTwo ||
960                     py1 - miny <= FixTwo || py2 - miny <= FixTwo) {
961                     FindCurveBBox(x0, y0, px1, py1, px2, py2, x1, y1, &llx,
962                                   &lly, &urx, &ury);
963                     if (ury - maxy > FixTwo || miny - lly > FixTwo) {
964                         Fixed loc, frst, lst;
965                         loc = (miny - lly > ury - maxy) ? lly : ury;
966                         CheckBBoxEdge(p, false, loc, &frst, &lst);
967                         xavg = FixHalfMul(frst + lst);
968                         xdist = (frst == lst) ? (x1 - x0) / 10
969                                               : FixHalfMul(lst - frst);
970                         if (abs(xdist) < gBendLength)
971                             xdist = (xdist > 0.0) ? FixHalfMul(gBendLength)
972                                                   : FixHalfMul(-gBendLength);
973                         AddHSegment(xavg - xdist, xavg + xdist, loc, p, NULL,
974                                     sCURVE, 10);
975                     }
976                 }
977             }
978         } else if (p->type != MOVETO && !IsTiny(p)) {
979             if ((q = HorzQuo(x0, y0, x1, y1)) > 0) {
980                 if (y0 == y1)
981                     AddHSegment(x0, x1, y0, p->prev, p, sLINE, 11);
982                 else {
983                     if (q < FixQuarter)
984                         q = FixQuarter;
985                     xdist = FixHalfMul(AdjDist(x1 - x0, q));
986                     xavg = FixHalfMul(x0 + x1);
987                     PrvForBend(p, &prvx, &prvy);
988                     NxtForBend(p, &nxtx, &nxty, &xx, &yy);
989                     yy = PickHSpot(x0, y0, x1, y1, xdist, x0, y0, x1, y1, prvx,
990                                    prvy, nxtx, nxty);
991                     AddHSegment(xavg - xdist, xavg + xdist, yy, p->prev, p,
992                                 sLINE, 12);
993                     if (abs(y0 - y1) <= FixTwo)
994                         ReportNonHError(x0, y0, x1, y1);
995                 }
996             } else {
997                 DoHBendsNxt(x0, y0, x1, y1, p);
998                 DoHBendsPrv(x0, y0, x1, y1, p);
999             }
1000         }
1001         p = p->next;
1002     }
1003     CompactList(2, MergeHSegs);
1004     CompactList(3, MergeHSegs);
1005     RemExtraBends(2, 3);
1006     topList = gSegLists[2]; /* this is probably unnecessary */
1007     botList = gSegLists[3];
1008     CheckTfmVal(topList, gTopBands, gLenTopBands);
1009     CheckTfmVal(botList, gBotBands, gLenBotBands);
1010 }
1011 
1012 void
PreGenPts(void)1013 PreGenPts(void)
1014 {
1015     Hlnks = Vlnks = NULL;
1016     gSegLists[0] = NULL;
1017     gSegLists[1] = NULL;
1018     gSegLists[2] = NULL;
1019     gSegLists[3] = NULL;
1020 }
1021