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 "ac.h"
11 #include "bbox.h"
12 
13 static HintVal *Vrejects, *Hrejects;
14 
15 void
InitPick(int32_t reason)16 InitPick(int32_t reason)
17 {
18     switch (reason) {
19         case STARTUP:
20         case RESTART:
21             Vrejects = Hrejects = NULL;
22     }
23 }
24 
25 #define LtPruneB(val) ((val) < FixOne && ((val) << 10) < gPruneB)
26 
27 static bool
ConsiderPicking(Fixed bestSpc,Fixed bestVal,HintVal * hintList,Fixed prevBestVal)28 ConsiderPicking(Fixed bestSpc, Fixed bestVal, HintVal* hintList,
29                 Fixed prevBestVal)
30 {
31     if (bestSpc > 0)
32         return true;
33     if (hintList == NULL)
34         return bestVal >= gPruneD;
35     if (bestVal > gPruneA)
36         return true;
37     if (LtPruneB(bestVal))
38         return false;
39     return (bestVal < FIXED_MAX / gPruneC) ? (prevBestVal <= bestVal * gPruneC)
40                                            : (prevBestVal / gPruneC <= bestVal);
41 }
42 
43 void
PickVVals(HintVal * valList)44 PickVVals(HintVal* valList)
45 {
46     HintVal *hintList, *rejectList, *vlist, *nxt;
47     Fixed bestVal = 0, prevBestVal;
48     hintList = rejectList = NULL;
49     prevBestVal = 0;
50     while (true) {
51         HintVal *prev, *bestPrev, *best;
52         Fixed lft, rght;
53         vlist = valList;
54         prev = bestPrev = best = NULL;
55         while (vlist != NULL) {
56             if ((best == NULL || CompareValues(vlist, best, spcBonus, 0)) &&
57                 ConsiderPicking(vlist->vSpc, vlist->vVal, hintList,
58                                 prevBestVal)) {
59                 best = vlist;
60                 bestPrev = prev;
61                 bestVal = vlist->vVal;
62             }
63             prev = vlist;
64             vlist = vlist->vNxt;
65         }
66         if (best == NULL)
67             break; /* no more */
68         if (bestPrev == NULL)
69             valList = best->vNxt;
70         else
71             bestPrev->vNxt = best->vNxt;
72         /* have now removed best from valList */
73         best->vNxt = hintList; /* add best to front of list */
74         hintList = best;
75         prevBestVal = bestVal;
76         lft = best->vLoc1 - gBandMargin;
77         rght = best->vLoc2 + gBandMargin;
78         /* remove segments from valList that overlap lft..rght */
79         vlist = valList;
80         prev = NULL;
81         while (vlist != NULL) {
82             Fixed vlft = vlist->vLoc1;
83             Fixed vrght = vlist->vLoc2;
84             if ((vlft <= rght) && (vrght >= lft)) {
85                 nxt = vlist->vNxt;
86                 vlist->vNxt = rejectList;
87                 rejectList = vlist;
88                 vlist = nxt;
89                 if (prev == NULL)
90                     valList = vlist;
91                 else
92                     prev->vNxt = vlist;
93             } else {
94                 prev = vlist;
95                 vlist = vlist->vNxt;
96             }
97         }
98     }
99     vlist = valList; /* move rest of valList to rejectList */
100     while (vlist != NULL) {
101         nxt = vlist->vNxt;
102         vlist->vNxt = rejectList;
103         rejectList = vlist;
104         vlist = nxt;
105     }
106     if (hintList == NULL)
107         HintVBnds();
108     gVHinting = hintList;
109     Vrejects = rejectList;
110 }
111 
112 static bool
InSerifBand(Fixed y0,Fixed y1,int32_t n,Fixed * p)113 InSerifBand(Fixed y0, Fixed y1, int32_t n, Fixed* p)
114 {
115     int32_t i;
116     if (n <= 0)
117         return false;
118     y0 = -y0;
119     y1 = -y1;
120     if (y0 > y1) {
121         Fixed tmp = y1;
122         y1 = y0;
123         y0 = tmp;
124     }
125     for (i = 0; i < n; i += 2)
126         if (p[i] <= y0 && p[i + 1] >= y1)
127             return true;
128     return false;
129 }
130 
131 static bool
ConsiderValForSeg(HintVal * val,HintSeg * seg,Fixed loc,int32_t nb,Fixed * b,int32_t ns,Fixed * s,bool primary)132 ConsiderValForSeg(HintVal* val, HintSeg* seg, Fixed loc, int32_t nb, Fixed* b,
133                   int32_t ns, Fixed* s, bool primary)
134 {
135     if (primary && val->vSpc > 0.0)
136         return true;
137     if (InBlueBand(loc, nb, b))
138         return true;
139     if (val->vSpc <= 0.0 && InSerifBand(seg->sMax, seg->sMin, ns, s))
140         return false;
141     if (LtPruneB(val->vVal))
142         return false;
143     return true;
144 }
145 
146 static HintVal*
FndBstVal(HintSeg * seg,bool seg1Flg,HintVal * cList,HintVal * rList,int32_t nb,Fixed * b,int32_t ns,Fixed * s,bool locFlg,bool hFlg)147 FndBstVal(HintSeg* seg, bool seg1Flg, HintVal* cList, HintVal* rList,
148           int32_t nb, Fixed* b, int32_t ns, Fixed* s, bool locFlg, bool hFlg)
149 {
150     Fixed loc, vloc;
151     HintVal *best, *vList;
152     HintSeg* vseg;
153     best = NULL;
154     loc = seg->sLoc;
155     vList = cList;
156     while (true) {
157         HintVal* initLst = vList;
158         while (vList != NULL) {
159             if (seg1Flg) {
160                 vseg = vList->vSeg1;
161                 vloc = vList->vLoc1;
162             } else {
163                 vseg = vList->vSeg2;
164                 vloc = vList->vLoc2;
165             }
166             if (abs(loc - vloc) <= gMaxMerge &&
167                 (locFlg ? !vList->vGhst
168                         : (vseg == seg || CloseSegs(seg, vseg, !hFlg))) &&
169                 (best == NULL ||
170                  (vList->vVal == best->vVal && vList->vSpc == best->vSpc &&
171                   vList->initVal > best->initVal) ||
172                  CompareValues(vList, best, spcBonus, 3)) &&
173                 /* last arg is "ghostshift" that penalizes ghost values */
174                 /* ghost values are set to 20 */
175                 /* so ghostshift of 3 means prefer nonghost if its
176                  value is > (20 >> 3) */
177                 ConsiderValForSeg(vList, seg, loc, nb, b, ns, s, true))
178                 best = vList;
179             vList = vList->vNxt;
180         }
181         if (initLst == rList)
182             break;
183         vList = rList;
184     }
185     ReportFndBstVal(seg, best, hFlg);
186     return best;
187 }
188 
189 #define FixSixteenth (0x10)
190 static HintVal*
FindBestValForSeg(HintSeg * seg,bool seg1Flg,HintVal * cList,HintVal * rList,int32_t nb,Fixed * b,int32_t ns,Fixed * s,bool hFlg)191 FindBestValForSeg(HintSeg* seg, bool seg1Flg, HintVal* cList, HintVal* rList,
192                   int32_t nb, Fixed* b, int32_t ns, Fixed* s, bool hFlg)
193 {
194     HintVal *best, *nonghst, *ghst = NULL;
195     best = FndBstVal(seg, seg1Flg, cList, rList, nb, b, ns, s, false, hFlg);
196     if (best != NULL && best->vGhst) {
197         nonghst =
198           FndBstVal(seg, seg1Flg, cList, rList, nb, b, ns, s, true, hFlg);
199         /* If nonghst hints are "better" use it instead of ghost band. */
200         if (nonghst != NULL && nonghst->vVal >= FixInt(2)) {
201             /* threshold must be greater than 1.004 for ITC Garamond Ultra "q"
202              */
203             ghst = best;
204             best = nonghst;
205         }
206     }
207     if (best != NULL) {
208         if (best->vVal < FixSixteenth &&
209             (ghst == NULL || ghst->vVal < FixSixteenth))
210             best = NULL;
211         /* threshold must be > .035 for Monotype/Plantin/Bold Thorn
212          and < .08 for Bookman2/Italic asterisk */
213         else
214             best->pruned = false;
215     }
216     return best;
217 }
218 
219 static bool
MembValList(HintVal * val,HintVal * vList)220 MembValList(HintVal* val, HintVal* vList)
221 {
222     while (vList != NULL) {
223         if (val == vList)
224             return true;
225         vList = vList->vNxt;
226     }
227     return false;
228 }
229 
230 static HintVal*
PrevVal(HintVal * val,HintVal * vList)231 PrevVal(HintVal* val, HintVal* vList)
232 {
233     HintVal* prev;
234     if (val == vList)
235         return NULL;
236     prev = vList;
237     while (true) {
238         vList = vList->vNxt;
239         if (vList == NULL) {
240             LogMsg(LOGERROR, NONFATALERROR, "Malformed value list.");
241             return NULL;
242         }
243 
244         if (vList == val)
245             return prev;
246         prev = vList;
247     }
248     return NULL;
249 }
250 
251 static void
FindRealVal(HintVal * vlist,Fixed top,Fixed bot,HintSeg ** pseg1,HintSeg ** pseg2)252 FindRealVal(HintVal* vlist, Fixed top, Fixed bot, HintSeg** pseg1,
253             HintSeg** pseg2)
254 {
255     while (vlist != NULL) {
256         if (vlist->vLoc2 == top && vlist->vLoc1 == bot && !vlist->vGhst) {
257             *pseg1 = vlist->vSeg1;
258             *pseg2 = vlist->vSeg2;
259             return;
260         }
261         vlist = vlist->vNxt;
262     }
263 }
264 
265 void
PickHVals(HintVal * valList)266 PickHVals(HintVal* valList)
267 {
268     HintVal *vlist, *hintList, *rejectList, *bestPrev, *prev, *best, *nxt;
269     Fixed bestVal = 0, prevBestVal;
270     Fixed bot, top, vtop, vbot;
271     HintVal* newBst;
272     HintSeg *seg1, *seg2;
273     hintList = rejectList = NULL;
274     prevBestVal = 0;
275     while (true) {
276         vlist = valList;
277         prev = bestPrev = best = NULL;
278         while (vlist != NULL) {
279             if ((best == NULL || CompareValues(vlist, best, spcBonus, 0)) &&
280                 ConsiderPicking(vlist->vSpc, vlist->vVal, hintList,
281                                 prevBestVal)) {
282                 best = vlist;
283                 bestPrev = prev;
284                 bestVal = vlist->vVal;
285             }
286             prev = vlist;
287             vlist = vlist->vNxt;
288         }
289         if (best != NULL) {
290             seg1 = best->vSeg1;
291             seg2 = best->vSeg2;
292             if (best->vGhst) { /* find float segments at same loc as best */
293                 FindRealVal(valList, best->vLoc2, best->vLoc1, &seg1, &seg2);
294             }
295             if (seg1->sType == sGHOST) {
296                 /*newBst = FindBestValForSeg(seg2, false, valList,
297                  NULL, 0, (Fixed *)NIL, 0, (Fixed *)NIL, true);*/
298                 newBst = seg2->sLnk;
299                 if (newBst != NULL && newBst != best &&
300                     MembValList(newBst, valList)) {
301                     best = newBst;
302                     bestPrev = PrevVal(best, valList);
303                 }
304             } else if (seg2->sType == sGHOST) {
305                 /*newBst = FindBestValForSeg(seg1, true, valList,
306                  NULL, 0, (Fixed *)NIL, 0, (Fixed *)NIL, true); */
307                 newBst = seg2->sLnk;
308                 if (newBst != NULL && newBst != best &&
309                     MembValList(newBst, valList)) {
310                     best = newBst;
311                     bestPrev = PrevVal(best, valList);
312                 }
313             }
314         }
315         if (best == NULL)
316             goto noMore;
317         prevBestVal = bestVal;
318         if (bestPrev == NULL)
319             valList = best->vNxt;
320         else
321             bestPrev->vNxt = best->vNxt;
322         /* have now removed best from valList */
323         best->vNxt = hintList;
324         hintList = best; /* add best to front of list */
325         bot = best->vLoc1;
326         top = best->vLoc2;
327         /* The next if statement was added so that ghost bands are given
328          0 width for doing the conflict tests for bands too close together.
329          This was a problem in Minion/DisplayItalic onequarter and onehalf. */
330         if (best->vGhst) { /* collapse width */
331             if (best->vSeg1->sType == sGHOST)
332                 bot = top;
333             else
334                 top = bot;
335         }
336         bot += gBandMargin;
337         top -= gBandMargin;
338         /* remove segments from valList that overlap bot..top */
339         vlist = valList;
340         prev = NULL;
341         while (vlist != NULL) {
342             vbot = vlist->vLoc1;
343             vtop = vlist->vLoc2;
344             /* The next if statement was added so that ghost bands are given
345              0 width for doing the conflict tests for bands too close together.
346              */
347             if (vlist->vGhst) { /* collapse width */
348                 if (vlist->vSeg1->sType == sGHOST)
349                     vbot = vtop;
350                 else
351                     vtop = vbot;
352             }
353             if ((vbot >= top) && (vtop <= bot)) {
354                 nxt = vlist->vNxt;
355                 vlist->vNxt = rejectList;
356                 rejectList = vlist;
357                 vlist = nxt;
358                 if (prev == NULL)
359                     valList = vlist;
360                 else
361                     prev->vNxt = vlist;
362             } else {
363                 prev = vlist;
364                 vlist = vlist->vNxt;
365             }
366         }
367     }
368 noMore:
369     vlist = valList; /* move rest of valList to rejectList */
370     while (vlist != NULL) {
371         nxt = vlist->vNxt;
372         vlist->vNxt = rejectList;
373         rejectList = vlist;
374         vlist = nxt;
375     }
376     if (hintList == NULL)
377         HintHBnds();
378     gHHinting = hintList;
379     Hrejects = rejectList;
380 }
381 
382 static void
FindBestValForSegs(HintSeg * sList,bool seg1Flg,HintVal * cList,HintVal * rList,int32_t nb,Fixed * b,int32_t ns,Fixed * s,bool hFlg)383 FindBestValForSegs(HintSeg* sList, bool seg1Flg, HintVal* cList, HintVal* rList,
384                    int32_t nb, Fixed* b, int32_t ns, Fixed* s, bool hFlg)
385 {
386     HintVal* best;
387     while (sList != NULL) {
388         best =
389           FindBestValForSeg(sList, seg1Flg, cList, rList, nb, b, ns, s, hFlg);
390         sList->sLnk = best;
391         sList = sList->sNxt;
392     }
393 }
394 
395 static void
SetPruned(void)396 SetPruned(void)
397 {
398     HintVal* vL = gValList;
399     while (vL != NULL) {
400         vL->pruned = true;
401         vL = vL->vNxt;
402     }
403 }
404 
405 void
FindBestHVals(void)406 FindBestHVals(void)
407 {
408     SetPruned();
409     FindBestValForSegs(topList, false, gValList, NULL, gLenTopBands, gTopBands,
410                        0, NULL, true);
411     FindBestValForSegs(botList, true, gValList, NULL, gLenBotBands, gBotBands,
412                        0, NULL, true);
413     DoPrune();
414 }
415 
416 void
FindBestVVals(void)417 FindBestVVals(void)
418 {
419     SetPruned();
420     FindBestValForSegs(leftList, true, gValList, NULL, 0, NULL, gNumSerifs,
421                        gSerifs, false);
422     FindBestValForSegs(rightList, false, gValList, NULL, 0, NULL, gNumSerifs,
423                        gSerifs, false);
424     DoPrune();
425 }
426