w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

pt1.c
Go to the documentation of this file.
1 /*
2  * see COPYRIGHT
3  */
4 
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8 #include <sys/types.h>
9 #include <sys/stat.h>
10 #include <fcntl.h>
11 #include <time.h>
12 #include <ctype.h>
13 #include <math.h>
14 
15 #ifndef WINDOWS
16 # include <netinet/in.h>
17 # include <unistd.h>
18 #else
19 # include "winport.h"
20 #endif
21 
22 #include "ttf.h"
23 #include "pt1.h"
24 #include "global.h"
25 
26 /* big and small values for comparisons */
27 #define FBIGVAL (1e20)
28 #define FEPS (100000./FBIGVAL)
29 
30 /* names of the axes */
31 #define X 0
32 #define Y 1
33 
34 /* the GENTRY extension structure used in fforceconcise() */
35 
36 struct gex_con {
37  double d[2 /*X, Y*/]; /* sizes of curve */
38  double sin2; /* squared sinus of the angle to the next gentry */
39  double len2; /* squared distance between the endpoints */
40 
41 /* number of reference dots taken from each curve */
42 #define NREFDOTS 3
43 
44  double dots[NREFDOTS][2]; /* reference dots */
45 
46  int flags; /* flags for gentry and tits joint to the next gentry */
47 /* a vertical or horizontal line may be in 2 quadrants at once */
48 #define GEXF_QUL 0x00000001 /* in up-left quadrant */
49 #define GEXF_QUR 0x00000002 /* in up-right quadrant */
50 #define GEXF_QDR 0x00000004 /* in down-right quadrant */
51 #define GEXF_QDL 0x00000008 /* in down-left quadrant */
52 #define GEXF_QMASK 0x0000000F /* quadrant mask */
53 
54 /* if a line is nearly vertical or horizontal, we remember that idealized quartant too */
55 #define GEXF_QTO_IDEAL(f) (((f)&0xF)<<4)
56 #define GEXF_QFROM_IDEAL(f) (((f)&0xF0)>>4)
57 #define GEXF_IDQ_L 0x00000090 /* left */
58 #define GEXF_IDQ_R 0x00000060 /* right */
59 #define GEXF_IDQ_U 0x00000030 /* up */
60 #define GEXF_IDQ_D 0x000000C0 /* down */
61 
62 /* possibly can be joined with conditions:
63  * (in order of increasing preference, the numeric order is important)
64  */
65 #define GEXF_JLINE 0x00000100 /* into one line */
66 #define GEXF_JIGN 0x00000200 /* if one entry's tangent angle is ignored */
67 #define GEXF_JID 0x00000400 /* if one entry is idealized to hor/vert */
68 #define GEXF_JFLAT 0x00000800 /* if one entry is flattened */
69 #define GEXF_JGOOD 0x00001000 /* perfectly, no additional maodifications */
70 
71 #define GEXF_JMASK 0x00001F00 /* the mask of all above */
72 #define GEXF_JCVMASK 0x00001E00 /* the mask of all above except JLINE */
73 
74 /* which entry needs to be modified for conditional joining */
75 #define GEXF_JIGN1 0x00002000
76 #define GEXF_JIGN2 0x00004000
77 #define GEXF_JIGNDIR(dir) (GEXF_JIGN1<<(dir))
78 #define GEXF_JID1 0x00008000
79 #define GEXF_JID2 0x00010000
80 #define GEXF_JIDDIR(dir) (GEXF_JID1<<(dir))
81 #define GEXF_JFLAT1 0x00020000
82 #define GEXF_JFLAT2 0x00040000
83 #define GEXF_JFLATDIR(dir) (GEXF_JFLAT1<<(dir))
84 
85 #define GEXF_VERT 0x00100000 /* is nearly vertical */
86 #define GEXF_HOR 0x00200000 /* is nearly horizontal */
87 #define GEXF_FLAT 0x00400000 /* is nearly flat */
88 
89 #define GEXF_VDOTS 0x01000000 /* the dots are valid */
90 
91  signed char isd[2 /*X,Y*/]; /* signs of the sizes */
92 };
93 typedef struct gex_con GEX_CON;
94 
95 /* convenience macros */
96 #define X_CON(ge) ((GEX_CON *)((ge)->ext))
97 #define X_CON_D(ge) (X_CON(ge)->d)
98 #define X_CON_DX(ge) (X_CON(ge)->d[0])
99 #define X_CON_DY(ge) (X_CON(ge)->d[1])
100 #define X_CON_ISD(ge) (X_CON(ge)->isd)
101 #define X_CON_ISDX(ge) (X_CON(ge)->isd[0])
102 #define X_CON_ISDY(ge) (X_CON(ge)->isd[1])
103 #define X_CON_SIN2(ge) (X_CON(ge)->sin2)
104 #define X_CON_LEN2(ge) (X_CON(ge)->len2)
105 #define X_CON_F(ge) (X_CON(ge)->flags)
106 
107 /* performance statistics about guessing the concise curves */
108 static int ggoodcv=0, ggoodcvdots=0, gbadcv=0, gbadcvdots=0;
109 
110 int stdhw, stdvw; /* dominant stems widths */
111 int stemsnaph[12], stemsnapv[12]; /* most typical stem width */
112 
113 int bluevalues[14];
114 int nblues;
115 int otherblues[10];
117 int bbox[4]; /* the FontBBox array */
119 
121 int encoding[ENCTABSZ]; /* inverse of glyph[].char_no */
123 
124 /* prototypes */
125 static void fixcvdir( GENTRY * ge, int dir);
126 static void fixcvends( GENTRY * ge);
127 static int fgetcvdir( GENTRY * ge);
128 static int igetcvdir( GENTRY * ge);
129 static int fiszigzag( GENTRY *ge);
130 static int iiszigzag( GENTRY *ge);
131 static GENTRY * freethisge( GENTRY *ge);
132 static void addgeafter( GENTRY *oge, GENTRY *nge );
133 static GENTRY * newgentry( int flags);
134 static void debugstems( char *name, STEM * hstems, int nhs, STEM * vstems, int nvs);
135 static int addbluestems( STEM *s, int n);
136 static void sortstems( STEM * s, int n);
137 static int stemoverlap( STEM * s1, STEM * s2);
138 static int steminblue( STEM *s);
139 static void markbluestems( STEM *s, int nold);
140 static int joinmainstems( STEM * s, int nold, int useblues);
141 static void joinsubstems( STEM * s, short *pairs, int nold, int useblues);
142 static void fixendpath( GENTRY *ge);
143 static void fdelsmall( GLYPH *g, double minlen);
144 static void alloc_gex_con( GENTRY *ge);
145 static double fjointsin2( GENTRY *ge1, GENTRY *ge2);
146 static double fcvarea( GENTRY *ge);
147 static double fcvval( GENTRY *ge, int axis, double t);
148 static void fsampledots( GENTRY *ge, double dots[][2], int ndots);
149 static void fnormalizege( GENTRY *ge);
150 static void fanalyzege( GENTRY *ge);
151 static void fanalyzejoint( GENTRY *ge);
152 static void fconcisecontour( GLYPH *g, GENTRY *ge);
153 static double fclosegap( GENTRY *from, GENTRY *to, int axis,
154  double gap, double *ret);
155 
156 int
158  int x
159 )
160 {
161  if (x > 0)
162  return 1;
163  else if (x < 0)
164  return -1;
165  else
166  return 0;
167 }
168 
169 int
171  double x
172 )
173 {
174  if (x > 0.0)
175  return 1;
176  else if (x < 0.0)
177  return -1;
178  else
179  return 0;
180 }
181 
182 static GENTRY *
184  int flags
185 )
186 {
187  GENTRY *ge;
188 
189  ge = calloc(1, sizeof(GENTRY));
190 
191  if (ge == 0) {
192  fprintf(stderr, "***** Memory allocation error *****\n");
193  exit(255);
194  }
195  ge->stemid = -1;
196  ge->flags = flags;
197  /* the rest is set to 0 by calloc() */
198  return ge;
199 }
200 
201 /*
202  * Routines to print out Postscript functions with optimization
203  */
204 
205 void
207  int dx,
208  int dy
209 )
210 {
211  if (optimize && dx == 0)
212  fprintf(pfa_file, "%d vmoveto\n", dy);
213  else if (optimize && dy == 0)
214  fprintf(pfa_file, "%d hmoveto\n", dx);
215  else
216  fprintf(pfa_file, "%d %d rmoveto\n", dx, dy);
217 }
218 
219 void
221  int dx,
222  int dy
223 )
224 {
225  if (optimize && dx == 0 && dy == 0) /* for special pathologic
226  * case */
227  return;
228  else if (optimize && dx == 0)
229  fprintf(pfa_file, "%d vlineto\n", dy);
230  else if (optimize && dy == 0)
231  fprintf(pfa_file, "%d hlineto\n", dx);
232  else
233  fprintf(pfa_file, "%d %d rlineto\n", dx, dy);
234 }
235 
236 void
238  int dx1,
239  int dy1,
240  int dx2,
241  int dy2,
242  int dx3,
243  int dy3
244 )
245 {
246  /* first two ifs are for crazy cases that occur surprisingly often */
247  if (optimize && dx1 == 0 && dx2 == 0 && dx3 == 0)
248  rlineto(0, dy1 + dy2 + dy3);
249  else if (optimize && dy1 == 0 && dy2 == 0 && dy3 == 0)
250  rlineto(dx1 + dx2 + dx3, 0);
251  else if (optimize && dy1 == 0 && dx3 == 0)
252  fprintf(pfa_file, "%d %d %d %d hvcurveto\n",
253  dx1, dx2, dy2, dy3);
254  else if (optimize && dx1 == 0 && dy3 == 0)
255  fprintf(pfa_file, "%d %d %d %d vhcurveto\n",
256  dy1, dx2, dy2, dx3);
257  else
258  fprintf(pfa_file, "%d %d %d %d %d %d rrcurveto\n",
259  dx1, dy1, dx2, dy2, dx3, dy3);
260 }
261 
262 void
264 {
265  fprintf(pfa_file, "closepath\n");
266 }
267 
268 /*
269  * Many of the path processing routines exist (or will exist) in
270  * both floating-point and integer version. Fimally most of the
271  * processing will go in floating point and the integer processing
272  * will become legacy.
273  * The names of floating routines start with f, names of integer
274  * routines start with i, and those old routines existing in one
275  * version only have no such prefix at all.
276  */
277 
278 /*
279 ** Routine that checks integrity of the path, for debugging
280 */
281 
282 void
284  GENTRY * from,
285  char *file,
286  int line,
287  char *name
288 )
289 {
290  GENTRY *first, *pe, *ge;
291  int isfloat;
292 
293  if(from==0)
294  return;
295  isfloat = (from->flags & GEF_FLOAT);
296  pe = from->prev;
297  for (ge = from; ge != 0; pe = ge, ge = ge->next) {
298  if( (ge->flags & GEF_FLOAT) ^ isfloat ) {
299  fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
300  fprintf(stderr, "float flag changes from %s to %s at 0x%p (type %c, prev type %c)\n",
301  (isfloat ? "TRUE" : "FALSE"), (isfloat ? "FALSE" : "TRUE"), ge, ge->type, pe->type);
302  abort();
303  }
304  if (pe != ge->prev) {
305  fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
306  fprintf(stderr, "unidirectional chain 0x%zx -next-> 0x%zx -prev-> 0x%zx \n",
307  (size_t)pe, (size_t)ge, (size_t)ge->prev);
308  abort();
309  }
310 
311  switch(ge->type) {
312  case GE_MOVE:
313  break;
314  case GE_PATH:
315  if (ge->prev == 0) {
316  fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
317  fprintf(stderr, "empty path at 0x%zx \n", (size_t)ge);
318  abort();
319  }
320  break;
321  case GE_LINE:
322  case GE_CURVE:
323  if(ge->frwd->bkwd != ge) {
324  fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
325  fprintf(stderr, "unidirectional chain 0x%zx -frwd-> 0x%zx -bkwd-> 0x%zx \n",
326  (size_t)ge, (size_t)ge->frwd, (size_t)ge->frwd->bkwd);
327  abort();
328  }
329  if(ge->prev->type == GE_MOVE) {
330  first = ge;
331  if(ge->bkwd->next->type != GE_PATH) {
332  fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
333  fprintf(stderr, "broken first backlink 0x%zx -bkwd-> 0x%zx -next-> 0x%zx \n",
334  (size_t)ge, (size_t)ge->bkwd, (size_t)ge->bkwd->next);
335  abort();
336  }
337  }
338  if(ge->next->type == GE_PATH) {
339  if(ge->frwd != first) {
340  fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
341  fprintf(stderr, "broken loop 0x%zx -...-> 0x%zx -frwd-> 0x%zx \n",
342  (size_t)first, (size_t)ge, (size_t)ge->frwd);
343  abort();
344  }
345  }
346  break;
347  }
348 
349  }
350 }
351 
352 void
354  GLYPH *g,
355  char *msg
356 )
357 {
358  if( !(g->flags & GF_FLOAT) ) {
359  fprintf(stderr, "**! Glyph %s is not float: %s\n", g->name, msg);
360  abort();
361  }
362  if(g->lastentry) {
363  if( !(g->lastentry->flags & GEF_FLOAT) ) {
364  fprintf(stderr, "**! Glyphs %s last entry is int: %s\n", g->name, msg);
365  abort();
366  }
367  }
368 }
369 
370 void
372  GLYPH *g,
373  char *msg
374 )
375 {
376  if( (g->flags & GF_FLOAT) ) {
377  fprintf(stderr, "**! Glyph %s is not int: %s\n", g->name, msg);
378  abort();
379  }
380  if(g->lastentry) {
381  if( (g->lastentry->flags & GEF_FLOAT) ) {
382  fprintf(stderr, "**! Glyphs %s last entry is float: %s\n", g->name, msg);
383  abort();
384  }
385  }
386 }
387 
388 
389 /*
390  * Routines to save the generated data about glyph
391  */
392 
393 void
395  GLYPH * g,
396  double x,
397  double y)
398 {
399  GENTRY *oge;
400 
401  if (ISDBG(BUILDG))
402  fprintf(stderr, "%s: f rmoveto(%g, %g)\n", g->name, x, y);
403 
404  assertisfloat(g, "adding float MOVE");
405 
406  if ((oge = g->lastentry) != 0) {
407  if (oge->type == GE_MOVE) { /* just eat up the first move */
408  oge->fx3 = x;
409  oge->fy3 = y;
410  } else if (oge->type == GE_LINE || oge->type == GE_CURVE) {
411  fprintf(stderr, "Glyph %s: MOVE in middle of path\n", g->name);
412  } else {
413  GENTRY *nge;
414 
415  nge = newgentry(GEF_FLOAT);
416  nge->type = GE_MOVE;
417  nge->fx3 = x;
418  nge->fy3 = y;
419 
420  oge->next = nge;
421  nge->prev = oge;
422  g->lastentry = nge;
423  }
424  } else {
425  GENTRY *nge;
426 
427  nge = newgentry(GEF_FLOAT);
428  nge->type = GE_MOVE;
429  nge->fx3 = x;
430  nge->fy3 = y;
431  nge->bkwd = (GENTRY*)&g->entries;
432  g->entries = g->lastentry = nge;
433  }
434 
435  if (0 && ISDBG(BUILDG))
436  dumppaths(g, NULL, NULL);
437 }
438 
439 void
441  GLYPH * g,
442  int x,
443  int y)
444 {
445  GENTRY *oge;
446 
447  if (ISDBG(BUILDG))
448  fprintf(stderr, "%s: i rmoveto(%d, %d)\n", g->name, x, y);
449 
450  assertisint(g, "adding int MOVE");
451 
452  if ((oge = g->lastentry) != 0) {
453  if (oge->type == GE_MOVE) { /* just eat up the first move */
454  oge->ix3 = x;
455  oge->iy3 = y;
456  } else if (oge->type == GE_LINE || oge->type == GE_CURVE) {
457  fprintf(stderr, "Glyph %s: MOVE in middle of path, ignored\n", g->name);
458  } else {
459  GENTRY *nge;
460 
461  nge = newgentry(0);
462  nge->type = GE_MOVE;
463  nge->ix3 = x;
464  nge->iy3 = y;
465 
466  oge->next = nge;
467  nge->prev = oge;
468  g->lastentry = nge;
469  }
470  } else {
471  GENTRY *nge;
472 
473  nge = newgentry(0);
474  nge->type = GE_MOVE;
475  nge->ix3 = x;
476  nge->iy3 = y;
477  nge->bkwd = (GENTRY*)&g->entries;
478  g->entries = g->lastentry = nge;
479  }
480 
481 }
482 
483 void
485  GLYPH * g,
486  double x,
487  double y)
488 {
489  GENTRY *oge, *nge;
490 
491  if (ISDBG(BUILDG))
492  fprintf(stderr, "%s: f rlineto(%g, %g)\n", g->name, x, y);
493 
494  assertisfloat(g, "adding float LINE");
495 
496  nge = newgentry(GEF_FLOAT);
497  nge->type = GE_LINE;
498  nge->fx3 = x;
499  nge->fy3 = y;
500 
501  if ((oge = g->lastentry) != 0) {
502  if (x == oge->fx3 && y == oge->fy3) { /* empty line */
503  /* ignore it or we will get in troubles later */
504  free(nge);
505  return;
506  }
507  if (g->path == 0) {
508  g->path = nge;
509  nge->bkwd = nge->frwd = nge;
510  } else {
511  oge->frwd = nge;
512  nge->bkwd = oge;
513  g->path->bkwd = nge;
514  nge->frwd = g->path;
515  }
516 
517  oge->next = nge;
518  nge->prev = oge;
519  g->lastentry = nge;
520  } else {
521  WARNING_1 fprintf(stderr, "Glyph %s: LINE outside of path\n", g->name);
522  free(nge);
523  }
524 
525  if (0 && ISDBG(BUILDG))
526  dumppaths(g, NULL, NULL);
527 }
528 
529 void
531  GLYPH * g,
532  int x,
533  int y)
534 {
535  GENTRY *oge, *nge;
536 
537  if (ISDBG(BUILDG))
538  fprintf(stderr, "%s: i rlineto(%d, %d)\n", g->name, x, y);
539 
540  assertisint(g, "adding int LINE");
541 
542  nge = newgentry(0);
543  nge->type = GE_LINE;
544  nge->ix3 = x;
545  nge->iy3 = y;
546 
547  if ((oge = g->lastentry) != 0) {
548  if (x == oge->ix3 && y == oge->iy3) { /* empty line */
549  /* ignore it or we will get in troubles later */
550  free(nge);
551  return;
552  }
553  if (g->path == 0) {
554  g->path = nge;
555  nge->bkwd = nge->frwd = nge;
556  } else {
557  oge->frwd = nge;
558  nge->bkwd = oge;
559  g->path->bkwd = nge;
560  nge->frwd = g->path;
561  }
562 
563  oge->next = nge;
564  nge->prev = oge;
565  g->lastentry = nge;
566  } else {
567  WARNING_1 fprintf(stderr, "Glyph %s: LINE outside of path\n", g->name);
568  free(nge);
569  }
570 
571 }
572 
573 void
575  GLYPH * g,
576  double x1,
577  double y1,
578  double x2,
579  double y2,
580  double x3,
581  double y3)
582 {
583  GENTRY *oge, *nge;
584 
585  oge = g->lastentry;
586 
587  if (ISDBG(BUILDG))
588  fprintf(stderr, "%s: f rrcurveto(%g, %g, %g, %g, %g, %g)\n"
589  ,g->name, x1, y1, x2, y2, x3, y3);
590 
591  assertisfloat(g, "adding float CURVE");
592 
593  if (oge && oge->fx3 == x1 && x1 == x2 && x2 == x3) /* check if it's
594  * actually a line */
595  fg_rlineto(g, x1, y3);
596  else if (oge && oge->fy3 == y1 && y1 == y2 && y2 == y3)
597  fg_rlineto(g, x3, y1);
598  else {
599  nge = newgentry(GEF_FLOAT);
600  nge->type = GE_CURVE;
601  nge->fx1 = x1;
602  nge->fy1 = y1;
603  nge->fx2 = x2;
604  nge->fy2 = y2;
605  nge->fx3 = x3;
606  nge->fy3 = y3;
607 
608  if (oge != 0) {
609  if (x3 == oge->fx3 && y3 == oge->fy3) {
610  free(nge); /* consider this curve empty */
611  /* ignore it or we will get in troubles later */
612  return;
613  }
614  if (g->path == 0) {
615  g->path = nge;
616  nge->bkwd = nge->frwd = nge;
617  } else {
618  oge->frwd = nge;
619  nge->bkwd = oge;
620  g->path->bkwd = nge;
621  nge->frwd = g->path;
622  }
623 
624  oge->next = nge;
625  nge->prev = oge;
626  g->lastentry = nge;
627  } else {
628  WARNING_1 fprintf(stderr, "Glyph %s: CURVE outside of path\n", g->name);
629  free(nge);
630  }
631  }
632 
633  if (0 && ISDBG(BUILDG))
634  dumppaths(g, NULL, NULL);
635 }
636 
637 void
639  GLYPH * g,
640  int x1,
641  int y1,
642  int x2,
643  int y2,
644  int x3,
645  int y3)
646 {
647  GENTRY *oge, *nge;
648 
649  oge = g->lastentry;
650 
651  if (ISDBG(BUILDG))
652  fprintf(stderr, "%s: i rrcurveto(%d, %d, %d, %d, %d, %d)\n"
653  ,g->name, x1, y1, x2, y2, x3, y3);
654 
655  assertisint(g, "adding int CURVE");
656 
657  if (oge && oge->ix3 == x1 && x1 == x2 && x2 == x3) /* check if it's
658  * actually a line */
659  ig_rlineto(g, x1, y3);
660  else if (oge && oge->iy3 == y1 && y1 == y2 && y2 == y3)
661  ig_rlineto(g, x3, y1);
662  else {
663  nge = newgentry(0);
664  nge->type = GE_CURVE;
665  nge->ix1 = x1;
666  nge->iy1 = y1;
667  nge->ix2 = x2;
668  nge->iy2 = y2;
669  nge->ix3 = x3;
670  nge->iy3 = y3;
671 
672  if (oge != 0) {
673  if (x3 == oge->ix3 && y3 == oge->iy3) {
674  free(nge); /* consider this curve empty */
675  /* ignore it or we will get in troubles later */
676  return;
677  }
678  if (g->path == 0) {
679  g->path = nge;
680  nge->bkwd = nge->frwd = nge;
681  } else {
682  oge->frwd = nge;
683  nge->bkwd = oge;
684  g->path->bkwd = nge;
685  nge->frwd = g->path;
686  }
687 
688  oge->next = nge;
689  nge->prev = oge;
690  g->lastentry = nge;
691  } else {
692  WARNING_1 fprintf(stderr, "Glyph %s: CURVE outside of path\n", g->name);
693  free(nge);
694  }
695  }
696 }
697 
698 void
700  GLYPH * g
701 )
702 {
703  GENTRY *oge, *nge;
704 
705  if (ISDBG(BUILDG))
706  fprintf(stderr, "%s: closepath\n", g->name);
707 
708  oge = g->lastentry;
709 
710  if (g->path == 0) {
711  WARNING_1 fprintf(stderr, "Warning: **** closepath on empty path in glyph \"%s\" ****\n",
712  g->name);
713  if (oge == 0) {
714  WARNING_1 fprintf(stderr, "No previois entry\n");
715  } else {
716  WARNING_1 fprintf(stderr, "Previous entry type: %c\n", oge->type);
717  if (oge->type == GE_MOVE) {
718  g->lastentry = oge->prev;
719  if (oge->prev == 0)
720  g->entries = 0;
721  else
722  g->lastentry->next = 0;
723  free(oge);
724  }
725  }
726  return;
727  }
728 
729  nge = newgentry(oge->flags & GEF_FLOAT); /* keep the same type */
730  nge->type = GE_PATH;
731 
732  g->path = 0;
733 
734  oge->next = nge;
735  nge->prev = oge;
736  g->lastentry = nge;
737 
738  if (0 && ISDBG(BUILDG))
739  dumppaths(g, NULL, NULL);
740 }
741 
742 /*
743  * * SB * Routines to smooth and fix the glyphs
744  */
745 
746 /*
747 ** we don't want to see the curves with coinciding middle and
748 ** outer points
749 */
750 
751 static void
753  GENTRY * ge
754 )
755 {
756  int dx, dy;
757  int x0, y0, x1, y1, x2, y2, x3, y3;
758 
759  if (ge->type != GE_CURVE)
760  return;
761 
762  if(ge->flags & GEF_FLOAT) {
763  fprintf(stderr, "**! fixcvends(0x%zx) on floating entry, ABORT\n", (size_t)ge);
764  abort(); /* dump core */
765  }
766 
767  x0 = ge->prev->ix3;
768  y0 = ge->prev->iy3;
769  x1 = ge->ix1;
770  y1 = ge->iy1;
771  x2 = ge->ix2;
772  y2 = ge->iy2;
773  x3 = ge->ix3;
774  y3 = ge->iy3;
775 
776 
777  /* look at the start of the curve */
778  if (x1 == x0 && y1 == y0) {
779  dx = x2 - x1;
780  dy = y2 - y1;
781 
782  if (dx == 0 && dy == 0
783  || x2 == x3 && y2 == y3) {
784  /* Oops, we actually have a straight line */
785  /*
786  * if it's small, we hope that it will get optimized
787  * later
788  */
789  if (abs(x3 - x0) <= 2 || abs(y3 - y0) <= 2) {
790  ge->ix1 = x3;
791  ge->iy1 = y3;
792  ge->ix2 = x0;
793  ge->iy2 = y0;
794  } else {/* just make it a line */
795  ge->type = GE_LINE;
796  }
797  } else {
798  if (abs(dx) < 4 && abs(dy) < 4) { /* consider it very
799  * small */
800  ge->ix1 = x2;
801  ge->iy1 = y2;
802  } else if (abs(dx) < 8 && abs(dy) < 8) { /* consider it small */
803  ge->ix1 += dx / 2;
804  ge->iy1 += dy / 2;
805  } else {
806  ge->ix1 += dx / 4;
807  ge->iy1 += dy / 4;
808  }
809  /* make sure that it's still on the same side */
810  if (abs(x3 - x0) * abs(dy) < abs(y3 - y0) * abs(dx)) {
811  if (abs(x3 - x0) * abs(ge->iy1 - y0) > abs(y3 - y0) * abs(ge->ix1 - x0))
812  ge->ix1 += isign(dx);
813  } else {
814  if (abs(x3 - x0) * abs(ge->iy1 - y0) < abs(y3 - y0) * abs(ge->ix1 - x0))
815  ge->iy1 += isign(dy);
816  }
817 
818  ge->ix2 += (x3 - x2) / 8;
819  ge->iy2 += (y3 - y2) / 8;
820  /* make sure that it's still on the same side */
821  if (abs(x3 - x0) * abs(y3 - y2) < abs(y3 - y0) * abs(x3 - x2)) {
822  if (abs(x3 - x0) * abs(y3 - ge->iy2) > abs(y3 - y0) * abs(x3 - ge->ix2))
823  ge->iy1 -= isign(y3 - y2);
824  } else {
825  if (abs(x3 - x0) * abs(y3 - ge->iy2) < abs(y3 - y0) * abs(x3 - ge->ix2))
826  ge->ix1 -= isign(x3 - x2);
827  }
828 
829  }
830  } else if (x2 == x3 && y2 == y3) {
831  dx = x1 - x2;
832  dy = y1 - y2;
833 
834  if (dx == 0 && dy == 0) {
835  /* Oops, we actually have a straight line */
836  /*
837  * if it's small, we hope that it will get optimized
838  * later
839  */
840  if (abs(x3 - x0) <= 2 || abs(y3 - y0) <= 2) {
841  ge->ix1 = x3;
842  ge->iy1 = y3;
843  ge->ix2 = x0;
844  ge->iy2 = y0;
845  } else {/* just make it a line */
846  ge->type = GE_LINE;
847  }
848  } else {
849  if (abs(dx) < 4 && abs(dy) < 4) { /* consider it very
850  * small */
851  ge->ix2 = x1;
852  ge->iy2 = y1;
853  } else if (abs(dx) < 8 && abs(dy) < 8) { /* consider it small */
854  ge->ix2 += dx / 2;
855  ge->iy2 += dy / 2;
856  } else {
857  ge->ix2 += dx / 4;
858  ge->iy2 += dy / 4;
859  }
860  /* make sure that it's still on the same side */
861  if (abs(x3 - x0) * abs(dy) < abs(y3 - y0) * abs(dx)) {
862  if (abs(x3 - x0) * abs(ge->iy2 - y3) > abs(y3 - y0) * abs(ge->ix2 - x3))
863  ge->ix2 += isign(dx);
864  } else {
865  if (abs(x3 - x0) * abs(ge->iy2 - y3) < abs(y3 - y0) * abs(ge->ix2 - x3))
866  ge->iy2 += isign(dy);
867  }
868 
869  ge->ix1 += (x0 - x1) / 8;
870  ge->iy1 += (y0 - y1) / 8;
871  /* make sure that it's still on the same side */
872  if (abs(x3 - x0) * abs(y0 - y1) < abs(y3 - y0) * abs(x0 - x1)) {
873  if (abs(x3 - x0) * abs(y0 - ge->iy1) > abs(y3 - y0) * abs(x0 - ge->ix1))
874  ge->iy1 -= isign(y0 - y1);
875  } else {
876  if (abs(x3 - x0) * abs(y0 - ge->iy1) < abs(y3 - y0) * abs(x0 - ge->ix1))
877  ge->ix1 -= isign(x0 - x1);
878  }
879 
880  }
881  }
882 }
883 
884 /*
885 ** After transformations we want to make sure that the resulting
886 ** curve is going in the same quadrant as the original one,
887 ** because rounding errors introduced during transformations
888 ** may make the result completeley wrong.
889 **
890 ** `dir' argument describes the direction of the original curve,
891 ** it is the superposition of two values for the front and
892 ** rear ends of curve:
893 **
894 ** >EQUAL - goes over the line connecting the ends
895 ** =EQUAL - coincides with the line connecting the ends
896 ** <EQUAL - goes under the line connecting the ends
897 **
898 ** See CVDIR_* for exact definitions.
899 */
900 
901 static void
903  GENTRY * ge,
904  int dir
905 )
906 {
907  int a, b, c, d;
908  double kk, kk1, kk2;
909  int changed;
910  int fdir, rdir;
911 
912  if(ge->flags & GEF_FLOAT) {
913  fprintf(stderr, "**! fixcvdir(0x%zx) on floating entry, ABORT\n", (size_t)ge);
914  abort(); /* dump core */
915  }
916 
918  if ((dir & CVDIR_REAR) == CVDIR_RSAME)
919  rdir = fdir; /* we need only isign, exact value doesn't matter */
920  else
922 
923  fixcvends(ge);
924 
925  c = isign(ge->ix3 - ge->prev->ix3); /* note the direction of
926  * curve */
927  d = isign(ge->iy3 - ge->prev->iy3);
928 
929  a = ge->iy3 - ge->prev->iy3;
930  b = ge->ix3 - ge->prev->ix3;
931  kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
932  a = ge->iy1 - ge->prev->iy3;
933  b = ge->ix1 - ge->prev->ix3;
934  kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
935  a = ge->iy3 - ge->iy2;
936  b = ge->ix3 - ge->ix2;
937  kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
938 
939  changed = 1;
940  while (changed) {
941  if (ISDBG(FIXCVDIR)) {
942  /* for debugging */
943  fprintf(stderr, "fixcvdir %d %d (%d %d %d %d %d %d) %f %f %f\n",
944  fdir, rdir,
945  ge->ix1 - ge->prev->ix3,
946  ge->iy1 - ge->prev->iy3,
947  ge->ix2 - ge->ix1,
948  ge->iy2 - ge->iy1,
949  ge->ix3 - ge->ix2,
950  ge->iy3 - ge->iy2,
951  kk1, kk, kk2);
952  }
953  changed = 0;
954 
955  if (fdir > 0) {
956  if (kk1 > kk) { /* the front end has problems */
957  if (c * (ge->ix1 - ge->prev->ix3) > 0) {
958  ge->ix1 -= c;
959  changed = 1;
960  } if (d * (ge->iy2 - ge->iy1) > 0) {
961  ge->iy1 += d;
962  changed = 1;
963  }
964  /* recalculate the coefficients */
965  a = ge->iy3 - ge->prev->iy3;
966  b = ge->ix3 - ge->prev->ix3;
967  kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
968  a = ge->iy1 - ge->prev->iy3;
969  b = ge->ix1 - ge->prev->ix3;
970  kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
971  }
972  } else if (fdir < 0) {
973  if (kk1 < kk) { /* the front end has problems */
974  if (c * (ge->ix2 - ge->ix1) > 0) {
975  ge->ix1 += c;
976  changed = 1;
977  } if (d * (ge->iy1 - ge->prev->iy3) > 0) {
978  ge->iy1 -= d;
979  changed = 1;
980  }
981  /* recalculate the coefficients */
982  a = ge->iy1 - ge->prev->iy3;
983  b = ge->ix1 - ge->prev->ix3;
984  kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
985  a = ge->iy3 - ge->prev->iy3;
986  b = ge->ix3 - ge->prev->ix3;
987  kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
988  }
989  }
990  if (rdir > 0) {
991  if (kk2 < kk) { /* the rear end has problems */
992  if (c * (ge->ix2 - ge->ix1) > 0) {
993  ge->ix2 -= c;
994  changed = 1;
995  } if (d * (ge->iy3 - ge->iy2) > 0) {
996  ge->iy2 += d;
997  changed = 1;
998  }
999  /* recalculate the coefficients */
1000  a = ge->iy3 - ge->prev->iy3;
1001  b = ge->ix3 - ge->prev->ix3;
1002  kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
1003  a = ge->iy3 - ge->iy2;
1004  b = ge->ix3 - ge->ix2;
1005  kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
1006  }
1007  } else if (rdir < 0) {
1008  if (kk2 > kk) { /* the rear end has problems */
1009  if (c * (ge->ix3 - ge->ix2) > 0) {
1010  ge->ix2 += c;
1011  changed = 1;
1012  } if (d * (ge->iy2 - ge->iy1) > 0) {
1013  ge->iy2 -= d;
1014  changed = 1;
1015  }
1016  /* recalculate the coefficients */
1017  a = ge->iy3 - ge->prev->iy3;
1018  b = ge->ix3 - ge->prev->ix3;
1019  kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
1020  a = ge->iy3 - ge->iy2;
1021  b = ge->ix3 - ge->ix2;
1022  kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
1023  }
1024  }
1025  }
1026  fixcvends(ge);
1027 }
1028 
1029 /* Get the directions of ends of curve for further usage */
1030 
1031 /* expects that the previous element is also float */
1032 
1033 static int
1035  GENTRY * ge
1036 )
1037 {
1038  double a, b;
1039  double k, k1, k2;
1040  int dir = 0;
1041 
1042  if( !(ge->flags & GEF_FLOAT) ) {
1043  fprintf(stderr, "**! fgetcvdir(0x%zx) on int entry, ABORT\n", (size_t)ge);
1044  abort(); /* dump core */
1045  }
1046 
1047  a = fabs(ge->fy3 - ge->prev->fy3);
1048  b = fabs(ge->fx3 - ge->prev->fx3);
1049  k = a < FEPS ? (b < FEPS ? 1. : 100000.) : ( b / a);
1050 
1051  a = fabs(ge->fy1 - ge->prev->fy3);
1052  b = fabs(ge->fx1 - ge->prev->fx3);
1053  if(a < FEPS) {
1054  if(b < FEPS) {
1055  a = fabs(ge->fy2 - ge->prev->fy3);
1056  b = fabs(ge->fx2 - ge->prev->fx3);
1057  k1 = a < FEPS ? (b < FEPS ? k : 100000.) : ( b / a);
1058  } else
1059  k1 = FBIGVAL;
1060  } else
1061  k1 = b / a;
1062 
1063  a = fabs(ge->fy3 - ge->fy2);
1064  b = fabs(ge->fx3 - ge->fx2);
1065  if(a < FEPS) {
1066  if(b < FEPS) {
1067  a = fabs(ge->fy3 - ge->fy1);
1068  b = fabs(ge->fx3 - ge->fx1);
1069  k2 = a < FEPS ? (b < FEPS ? k : 100000.) : ( b / a);
1070  } else
1071  k2 = FBIGVAL;
1072  } else
1073  k2 = b / a;
1074 
1075  if(fabs(k1-k) < 0.0001)
1076  dir |= CVDIR_FEQUAL;
1077  else if (k1 < k)
1078  dir |= CVDIR_FUP;
1079  else
1080  dir |= CVDIR_FDOWN;
1081 
1082  if(fabs(k2-k) < 0.0001)
1083  dir |= CVDIR_REQUAL;
1084  else if (k2 > k)
1085  dir |= CVDIR_RUP;
1086  else
1087  dir |= CVDIR_RDOWN;
1088 
1089  return dir;
1090 }
1091 
1092 
1093 /* expects that the previous element is also int */
1094 
1095 static int
1097  GENTRY * ge
1098 )
1099 {
1100  int a, b;
1101  double k, k1, k2;
1102  int dir = 0;
1103 
1104  if(ge->flags & GEF_FLOAT) {
1105  fprintf(stderr, "**! igetcvdir(0x%zx) on floating entry, ABORT\n", (size_t)ge);
1106  abort(); /* dump core */
1107  }
1108 
1109  a = ge->iy3 - ge->prev->iy3;
1110  b = ge->ix3 - ge->prev->ix3;
1111  k = (a == 0) ? (b == 0 ? 1. : 100000.) : fabs((double) b / (double) a);
1112 
1113  a = ge->iy1 - ge->prev->iy3;
1114  b = ge->ix1 - ge->prev->ix3;
1115  if(a == 0) {
1116  if(b == 0) {
1117  a = ge->iy2 - ge->prev->iy3;
1118  b = ge->ix2 - ge->prev->ix3;
1119  k1 = (a == 0) ? (b == 0 ? k : 100000.) : fabs((double) b / (double) a);
1120  } else
1121  k1 = FBIGVAL;
1122  } else
1123  k1 = fabs((double) b / (double) a);
1124 
1125  a = ge->iy3 - ge->iy2;
1126  b = ge->ix3 - ge->ix2;
1127  if(a == 0) {
1128  if(b == 0) {
1129  a = ge->iy3 - ge->iy1;
1130  b = ge->ix3 - ge->ix1;
1131  k2 = (a == 0) ? (b == 0 ? k : 100000.) : fabs((double) b / (double) a);
1132  } else
1133  k2 = FBIGVAL;
1134  } else
1135  k2 = fabs((double) b / (double) a);
1136 
1137  if(fabs(k1-k) < 0.0001)
1138  dir |= CVDIR_FEQUAL;
1139  else if (k1 < k)
1140  dir |= CVDIR_FUP;
1141  else
1142  dir |= CVDIR_FDOWN;
1143 
1144  if(fabs(k2-k) < 0.0001)
1145  dir |= CVDIR_REQUAL;
1146  else if (k2 > k)
1147  dir |= CVDIR_RUP;
1148  else
1149  dir |= CVDIR_RDOWN;
1150 
1151  return dir;
1152 }
1153 
1154 #if 0
1155 /* a function just to test the work of fixcvdir() */
1156 static void
1157 testfixcvdir(
1158  GLYPH * g
1159 )
1160 {
1161  GENTRY *ge;
1162  int dir;
1163 
1164  for (ge = g->entries; ge != 0; ge = ge->next) {
1165  if (ge->type == GE_CURVE) {
1166  dir = igetcvdir(ge);
1167  fixcvdir(ge, dir);
1168  }
1169  }
1170 }
1171 #endif
1172 
1173 static int
1175  double val
1176 )
1177 {
1178  return (int) (val > 0 ? val + 0.5 : val - 0.5);
1179 }
1180 
1181 /* for debugging - dump the glyph
1182  * mark with a star the entries from start to end inclusive
1183  * (start == NULL means don't mark any, end == NULL means to the last)
1184  */
1185 
1186 void
1188  GLYPH *g,
1189  GENTRY *start,
1190  GENTRY *end
1191 )
1192 {
1193  GENTRY *ge;
1194  int i;
1195  char mark=' ';
1196 
1197  fprintf(stderr, "Glyph %s:\n", g->name);
1198 
1199  /* now do the conversion */
1200  for(ge = g->entries; ge != 0; ge = ge->next) {
1201  if(ge == start)
1202  mark = '*';
1203  fprintf(stderr, " %c %16zx", mark, (size_t)ge);
1204  switch(ge->type) {
1205  case GE_MOVE:
1206  case GE_LINE:
1207  if(ge->flags & GEF_FLOAT)
1208  fprintf(stderr," %c float (%g, %g)\n", ge->type, ge->fx3, ge->fy3);
1209  else
1210  fprintf(stderr," %c int (%d, %d)\n", ge->type, ge->ix3, ge->iy3);
1211  break;
1212  case GE_CURVE:
1213  if(ge->flags & GEF_FLOAT) {
1214  fprintf(stderr," C float ");
1215  for(i=0; i<3; i++)
1216  fprintf(stderr,"(%g, %g) ", ge->fxn[i], ge->fyn[i]);
1217  fprintf(stderr,"\n");
1218  } else {
1219  fprintf(stderr," C int ");
1220  for(i=0; i<3; i++)
1221  fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
1222  fprintf(stderr,"\n");
1223  }
1224  break;
1225  default:
1226  fprintf(stderr, " %c\n", ge->type);
1227  break;
1228  }
1229  if(ge == end)
1230  mark = ' ';
1231  }
1232 }
1233 
1234 /*
1235  * Routine that converts all entries in the path from float to int
1236  */
1237 
1238 void
1240  GLYPH *g
1241 )
1242 {
1243  GENTRY *ge;
1244  int x[3], y[3];
1245  int i;
1246 
1247 
1248  if(ISDBG(TOINT))
1249  fprintf(stderr, "TOINT: glyph %s\n", g->name);
1250  assertisfloat(g, "converting path to int\n");
1251 
1252  fdelsmall(g, 1.0); /* get rid of sub-pixel contours */
1253  assertpath(g->entries, __FILE__, __LINE__, g->name);
1254 
1255  /* 1st pass, collect the directions of the curves: have
1256  * to do that in advance, while everyting is float
1257  */
1258  for(ge = g->entries; ge != 0; ge = ge->next) {
1259  if( !(ge->flags & GEF_FLOAT) ) {
1260  fprintf(stderr, "**! glyphs %s has int entry, found in conversion to int\n",
1261  g->name);
1262  exit(1);
1263  }
1264  if(ge->type == GE_CURVE) {
1265  ge->dir = fgetcvdir(ge);
1266  }
1267  }
1268 
1269  /* now do the conversion */
1270  for(ge = g->entries; ge != 0; ge = ge->next) {
1271  switch(ge->type) {
1272  case GE_MOVE:
1273  case GE_LINE:
1274  if(ISDBG(TOINT))
1275  fprintf(stderr," %c float x=%g y=%g\n", ge->type, ge->fx3, ge->fy3);
1276  x[0] = iround(ge->fx3);
1277  y[0] = iround(ge->fy3);
1278  for(i=0; i<3; i++) { /* put some valid values everywhere, for convenience */
1279  ge->ixn[i] = x[0];
1280  ge->iyn[i] = y[0];
1281  }
1282  if(ISDBG(TOINT))
1283  fprintf(stderr," int x=%d y=%d\n", ge->ix3, ge->iy3);
1284  break;
1285  case GE_CURVE:
1286  if(ISDBG(TOINT))
1287  fprintf(stderr," %c float ", ge->type);
1288 
1289  for(i=0; i<3; i++) {
1290  if(ISDBG(TOINT))
1291  fprintf(stderr,"(%g, %g) ", ge->fxn[i], ge->fyn[i]);
1292  x[i] = iround(ge->fxn[i]);
1293  y[i] = iround(ge->fyn[i]);
1294  }
1295 
1296  if(ISDBG(TOINT))
1297  fprintf(stderr,"\n int ");
1298 
1299  for(i=0; i<3; i++) {
1300  ge->ixn[i] = x[i];
1301  ge->iyn[i] = y[i];
1302  if(ISDBG(TOINT))
1303  fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
1304  }
1305  ge->flags &= ~~GEF_FLOAT; /* for fixcvdir */
1306  fixcvdir(ge, ge->dir);
1307 
1308  if(ISDBG(TOINT)) {
1309  fprintf(stderr,"\n fixed ");
1310  for(i=0; i<3; i++)
1311  fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
1312  fprintf(stderr,"\n");
1313  }
1314 
1315  break;
1316  }
1317  ge->flags &= ~~GEF_FLOAT;
1318  }
1319  g->flags &= ~~GF_FLOAT;
1320 }
1321 
1322 
1323 /* check whether we can fix up the curve to change its size by (dx,dy) */
1324 /* 0 means NO, 1 means YES */
1325 
1326 /* for float: if scaling would be under 10% */
1327 
1328 int
1330  GENTRY * ge,
1331  double dx,
1332  double dy
1333 )
1334 {
1335  if( !(ge->flags & GEF_FLOAT) ) {
1336  fprintf(stderr, "**! fcheckcv(0x%zx) on int entry, ABORT\n", (size_t)ge);
1337  abort(); /* dump core */
1338  }
1339 
1340  if (ge->type != GE_CURVE)
1341  return 0;
1342 
1343  if( fabs(ge->fx3 - ge->prev->fx3) < fabs(dx) * 10 )
1344  return 0;
1345 
1346  if( fabs(ge->fy3 - ge->prev->fy3) < fabs(dy) * 10 )
1347  return 0;
1348 
1349  return 1;
1350 }
1351 
1352 /* for int: if won't create new zigzags at the ends */
1353 
1354 int
1356  GENTRY * ge,
1357  int dx,
1358  int dy
1359 )
1360 {
1361  int xdep, ydep;
1362 
1363  if(ge->flags & GEF_FLOAT) {
1364  fprintf(stderr, "**! icheckcv(0x%zx) on floating entry, ABORT\n", (size_t)ge);
1365  abort(); /* dump core */
1366  }
1367 
1368  if (ge->type != GE_CURVE)
1369  return 0;
1370 
1371  xdep = ge->ix3 - ge->prev->ix3;
1372  ydep = ge->iy3 - ge->prev->iy3;
1373 
1374  if (ge->type == GE_CURVE
1375  && (xdep * (xdep + dx)) > 0
1376  && (ydep * (ydep + dy)) > 0) {
1377  return 1;
1378  } else
1379  return 0;
1380 }
1381 
1382 /* float connect the ends of open contours */
1383 
1384 void
1386  GLYPH * g
1387 )
1388 {
1389  GENTRY *ge, *fge, *xge, *nge;
1390  int i;
1391 
1392  assertisfloat(g, "fclosepaths float\n");
1393 
1394  for (xge = g->entries; xge != 0; xge = xge->next) {
1395  if( xge->type != GE_PATH )
1396  continue;
1397 
1398  ge = xge->prev;
1399  if(ge == 0 || ge->type != GE_LINE && ge->type!= GE_CURVE) {
1400  fprintf(stderr, "**! Glyph %s got empty path\n",
1401  g->name);
1402  exit(1);
1403  }
1404 
1405  fge = ge->frwd;
1406  if (fge->prev == 0 || fge->prev->type != GE_MOVE) {
1407  fprintf(stderr, "**! Glyph %s got strange beginning of path\n",
1408  g->name);
1409  exit(1);
1410  }
1411  fge = fge->prev;
1412  if (fge->fx3 != ge->fx3 || fge->fy3 != ge->fy3) {
1413  /* we have to fix this open path */
1414 
1415  WARNING_4 fprintf(stderr, "Glyph %s got path open by dx=%g dy=%g\n",
1416  g->name, fge->fx3 - ge->fx3, fge->fy3 - ge->fy3);
1417 
1418 
1419  /* add a new line */
1420  nge = newgentry(GEF_FLOAT);
1421  (*nge) = (*ge);
1422  nge->fx3 = fge->fx3;
1423  nge->fy3 = fge->fy3;
1424  nge->type = GE_LINE;
1425 
1426  addgeafter(ge, nge);
1427 
1428  if (fabs(ge->fx3 - fge->fx3) <= 2 && fabs(ge->fy3 - fge->fy3) <= 2) {
1429  /*
1430  * small change, try to get rid of the new entry
1431  */
1432 
1433  double df[2];
1434 
1435  for(i=0; i<2; i++) {
1436  df[i] = ge->fpoints[i][2] - fge->fpoints[i][2];
1437  df[i] = fclosegap(nge, nge, i, df[i], NULL);
1438  }
1439 
1440  if(df[0] == 0. && df[1] == 0.) {
1441  /* closed gap successfully, remove the added entry */
1442  freethisge(nge);
1443  }
1444  }
1445  }
1446  }
1447 }
1448 
1449 void
1451  GLYPH * g
1452 )
1453 {
1454  GENTRY *ge, *ne;
1455  int dx1, dy1, dx2, dy2, k;
1456  int dir;
1457 
1458  return; /* this stuff seems to create problems */
1459 
1460  assertisint(g, "smoothjoints int");
1461 
1462  if (g->entries == 0) /* nothing to do */
1463  return;
1464 
1465  for (ge = g->entries->next; ge != 0; ge = ge->next) {
1466  ne = ge->frwd;
1467 
1468  /*
1469  * although there should be no one-line path * and any path
1470  * must end with CLOSEPATH, * nobody can say for sure
1471  */
1472 
1473  if (ge == ne || ne == 0)
1474  continue;
1475 
1476  /* now handle various joints */
1477 
1478  if (ge->type == GE_LINE && ne->type == GE_LINE) {
1479  dx1 = ge->ix3 - ge->prev->ix3;
1480  dy1 = ge->iy3 - ge->prev->iy3;
1481  dx2 = ne->ix3 - ge->ix3;
1482  dy2 = ne->iy3 - ge->iy3;
1483 
1484  /* check whether they have the same direction */
1485  /* and the same slope */
1486  /* then we can join them into one line */
1487 
1488  if (dx1 * dx2 >= 0 && dy1 * dy2 >= 0 && dx1 * dy2 == dy1 * dx2) {
1489  /* extend the previous line */
1490  ge->ix3 = ne->ix3;
1491  ge->iy3 = ne->iy3;
1492 
1493  /* and get rid of the next line */
1494  freethisge(ne);
1495  }
1496  } else if (ge->type == GE_LINE && ne->type == GE_CURVE) {
1497  fixcvends(ne);
1498 
1499  dx1 = ge->ix3 - ge->prev->ix3;
1500  dy1 = ge->iy3 - ge->prev->iy3;
1501  dx2 = ne->ix1 - ge->ix3;
1502  dy2 = ne->iy1 - ge->iy3;
1503 
1504  /* if the line is nearly horizontal and we can fix it */
1505  if (dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0
1506  && icheckcv(ne, 0, -dy1)
1507  && abs(dy1) <= 4) {
1508  dir = igetcvdir(ne);
1509  ge->iy3 -= dy1;
1510  ne->iy1 -= dy1;
1511  fixcvdir(ne, dir);
1512  if (ge->next != ne)
1513  ne->prev->iy3 -= dy1;
1514  dy1 = 0;
1515  } else if (dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0
1516  && icheckcv(ne, -dx1, 0)
1517  && abs(dx1) <= 4) {
1518  /* the same but vertical */
1519  dir = igetcvdir(ne);
1520  ge->ix3 -= dx1;
1521  ne->ix1 -= dx1;
1522  fixcvdir(ne, dir);
1523  if (ge->next != ne)
1524  ne->prev->ix3 -= dx1;
1525  dx1 = 0;
1526  }
1527  /*
1528  * if line is horizontal and curve begins nearly
1529  * horizontally
1530  */
1531  if (dy1 == 0 && dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0) {
1532  dir = igetcvdir(ne);
1533  ne->iy1 -= dy2;
1534  fixcvdir(ne, dir);
1535  dy2 = 0;
1536  } else if (dx1 == 0 && dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0) {
1537  /* the same but vertical */
1538  dir = igetcvdir(ne);
1539  ne->ix1 -= dx2;
1540  fixcvdir(ne, dir);
1541  dx2 = 0;
1542  }
1543  } else if (ge->type == GE_CURVE && ne->type == GE_LINE) {
1544  fixcvends(ge);
1545 
1546  dx1 = ge->ix3 - ge->ix2;
1547  dy1 = ge->iy3 - ge->iy2;
1548  dx2 = ne->ix3 - ge->ix3;
1549  dy2 = ne->iy3 - ge->iy3;
1550 
1551  /* if the line is nearly horizontal and we can fix it */
1552  if (dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0
1553  && icheckcv(ge, 0, dy2)
1554  && abs(dy2) <= 4) {
1555  dir = igetcvdir(ge);
1556  ge->iy3 += dy2;
1557  ge->iy2 += dy2;
1558  fixcvdir(ge, dir);
1559  if (ge->next != ne)
1560  ne->prev->iy3 += dy2;
1561  dy2 = 0;
1562  } else if (dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0
1563  && icheckcv(ge, dx2, 0)
1564  && abs(dx2) <= 4) {
1565  /* the same but vertical */
1566  dir = igetcvdir(ge);
1567  ge->ix3 += dx2;
1568  ge->ix2 += dx2;
1569  fixcvdir(ge, dir);
1570  if (ge->next != ne)
1571  ne->prev->ix3 += dx2;
1572  dx2 = 0;
1573  }
1574  /*
1575  * if line is horizontal and curve ends nearly
1576  * horizontally
1577  */
1578  if (dy2 == 0 && dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0) {
1579  dir = igetcvdir(ge);
1580  ge->iy2 += dy1;
1581  fixcvdir(ge, dir);
1582  dy1 = 0;
1583  } else if (dx2 == 0 && dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0) {
1584  /* the same but vertical */
1585  dir = igetcvdir(ge);
1586  ge->ix2 += dx1;
1587  fixcvdir(ge, dir);
1588  dx1 = 0;
1589  }
1590  } else if (ge->type == GE_CURVE && ne->type == GE_CURVE) {
1591  fixcvends(ge);
1592  fixcvends(ne);
1593 
1594  dx1 = ge->ix3 - ge->ix2;
1595  dy1 = ge->iy3 - ge->iy2;
1596  dx2 = ne->ix1 - ge->ix3;
1597  dy2 = ne->iy1 - ge->iy3;
1598 
1599  /*
1600  * check if we have a rather smooth joint at extremal
1601  * point
1602  */
1603  /* left or right extremal point */
1604  if (abs(dx1) <= 4 && abs(dx2) <= 4
1605  && dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0
1606  && dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0
1607  && (ge->iy3 < ge->prev->iy3 && ne->iy3 < ge->iy3
1608  || ge->iy3 > ge->prev->iy3 && ne->iy3 > ge->iy3)
1609  && (ge->ix3 - ge->prev->ix3) * (ne->ix3 - ge->ix3) < 0
1610  ) {
1611  dir = igetcvdir(ge);
1612  ge->ix2 += dx1;
1613  dx1 = 0;
1614  fixcvdir(ge, dir);
1615  dir = igetcvdir(ne);
1616  ne->ix1 -= dx2;
1617  dx2 = 0;
1618  fixcvdir(ne, dir);
1619  }
1620  /* top or down extremal point */
1621  else if (abs(dy1) <= 4 && abs(dy2) <= 4
1622  && dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0
1623  && dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0
1624  && (ge->ix3 < ge->prev->ix3 && ne->ix3 < ge->ix3
1625  || ge->ix3 > ge->prev->ix3 && ne->ix3 > ge->ix3)
1626  && (ge->iy3 - ge->prev->iy3) * (ne->iy3 - ge->iy3) < 0
1627  ) {
1628  dir = igetcvdir(ge);
1629  ge->iy2 += dy1;
1630  dy1 = 0;
1631  fixcvdir(ge, dir);
1632  dir = igetcvdir(ne);
1633  ne->iy1 -= dy2;
1634  dy2 = 0;
1635  fixcvdir(ne, dir);
1636  }
1637  /* or may be we just have a smooth junction */
1638  else if (dx1 * dx2 >= 0 && dy1 * dy2 >= 0
1639  && 10 * abs(k = abs(dx1 * dy2) - abs(dy1 * dx2)) < (abs(dx1 * dy2) + abs(dy1 * dx2))) {
1640  int tries[6][4];
1641  int results[6];
1642  int i, b;
1643 
1644  /* build array of changes we are going to try */
1645  /* uninitalized entries are 0 */
1646  if (k > 0) {
1647  static int t1[6][4] = {
1648  {0, 0, 0, 0},
1649  {-1, 0, 1, 0},
1650  {-1, 0, 0, 1},
1651  {0, -1, 1, 0},
1652  {0, -1, 0, 1},
1653  {-1, -1, 1, 1}};
1654  memcpy(tries, t1, sizeof tries);
1655  } else {
1656  static int t1[6][4] = {
1657  {0, 0, 0, 0},
1658  {1, 0, -1, 0},
1659  {1, 0, 0, -1},
1660  {0, 1, -1, 0},
1661  {0, 1, 0, -1},
1662  {1, 1, -1, -1}};
1663  memcpy(tries, t1, sizeof tries);
1664  }
1665 
1666  /* now try the changes */
1667  results[0] = abs(k);
1668  for (i = 1; i < 6; i++) {
1669  results[i] = abs((abs(dx1) + tries[i][0]) * (abs(dy2) + tries[i][1]) -
1670  (abs(dy1) + tries[i][2]) * (abs(dx2) + tries[i][3]));
1671  }
1672 
1673  /* and find the best try */
1674  k = abs(k);
1675  b = 0;
1676  for (i = 1; i < 6; i++)
1677  if (results[i] < k) {
1678  k = results[i];
1679  b = i;
1680  }
1681  /* and finally apply it */
1682  if (dx1 < 0)
1683  tries[b][0] = -tries[b][0];
1684  if (dy2 < 0)
1685  tries[b][1] = -tries[b][1];
1686  if (dy1 < 0)
1687  tries[b][2] = -tries[b][2];
1688  if (dx2 < 0)
1689  tries[b][3] = -tries[b][3];
1690 
1691  dir = igetcvdir(ge);
1692  ge->ix2 -= tries[b][0];
1693  ge->iy2 -= tries[b][2];
1694  fixcvdir(ge, dir);
1695  dir = igetcvdir(ne);
1696  ne->ix1 += tries[b][3];
1697  ne->iy1 += tries[b][1];
1698  fixcvdir(ne, dir);
1699  }
1700  }
1701  }
1702 }
1703 
1704 /* debugging: print out stems of a glyph */
1705 static void
1707  char *name,
1708  STEM * hstems,
1709  int nhs,
1710  STEM * vstems,
1711  int nvs
1712 )
1713 {
1714  int i;
1715 
1716  fprintf(pfa_file, "%% %s\n", name);
1717  fprintf(pfa_file, "%% %d horizontal stems:\n", nhs);
1718  for (i = 0; i < nhs; i++)
1719  fprintf(pfa_file, "%% %3d %d (%d...%d) %c %c%c%c%c\n", i, hstems[i].value,
1720  hstems[i].from, hstems[i].to,
1721  ((hstems[i].flags & ST_UP) ? 'U' : 'D'),
1722  ((hstems[i].flags & ST_END) ? 'E' : '-'),
1723  ((hstems[i].flags & ST_FLAT) ? 'F' : '-'),
1724  ((hstems[i].flags & ST_ZONE) ? 'Z' : ' '),
1725  ((hstems[i].flags & ST_TOPZONE) ? 'T' : ' '));
1726  fprintf(pfa_file, "%% %d vertical stems:\n", nvs);
1727  for (i = 0; i < nvs; i++)
1728  fprintf(pfa_file, "%% %3d %d (%d...%d) %c %c%c\n", i, vstems[i].value,
1729  vstems[i].from, vstems[i].to,
1730  ((vstems[i].flags & ST_UP) ? 'U' : 'D'),
1731  ((vstems[i].flags & ST_END) ? 'E' : '-'),
1732  ((vstems[i].flags & ST_FLAT) ? 'F' : '-'));
1733 }
1734 
1735 /* add pseudo-stems for the limits of the Blue zones to the stem array */
1736 static int
1738  STEM *s,
1739  int n
1740 )
1741 {
1742  int i;
1743 
1744  for(i=0; i<nblues && i<2; i+=2) { /* baseline */
1745  s[n].value=bluevalues[i];
1746  s[n].flags=ST_UP|ST_ZONE;
1747  /* don't overlap with anything */
1748  s[n].origin=s[n].from=s[n].to= -10000+i;
1749  n++;
1750  s[n].value=bluevalues[i+1];
1751  s[n].flags=ST_ZONE;
1752  /* don't overlap with anything */
1753  s[n].origin=s[n].from=s[n].to= -10000+i+1;
1754  n++;
1755  }
1756  for(i=2; i<nblues; i+=2) { /* top zones */
1757  s[n].value=bluevalues[i];
1758  s[n].flags=ST_UP|ST_ZONE|ST_TOPZONE;
1759  /* don't overlap with anything */
1760  s[n].origin=s[n].from=s[n].to= -10000+i;
1761  n++;
1762  s[n].value=bluevalues[i+1];
1763  s[n].flags=ST_ZONE|ST_TOPZONE;
1764  /* don't overlap with anything */
1765  s[n].origin=s[n].from=s[n].to= -10000+i+1;
1766  n++;
1767  }
1768  for(i=0; i<notherb; i+=2) { /* bottom zones */
1769  s[n].value=otherblues[i];
1770  s[n].flags=ST_UP|ST_ZONE;
1771  /* don't overlap with anything */
1772  s[n].origin=s[n].from=s[n].to= -10000+i+nblues;
1773  n++;
1774  s[n].value=otherblues[i+1];
1775  s[n].flags=ST_ZONE;
1776  /* don't overlap with anything */
1777  s[n].origin=s[n].from=s[n].to= -10000+i+1+nblues;
1778  n++;
1779  }
1780  return n;
1781 }
1782 
1783 /* sort stems in array */
1784 static void
1786  STEM * s,
1787  int n
1788 )
1789 {
1790  int i, j;
1791  STEM x;
1792 
1793 
1794  /* a simple sorting */
1795  /* hm, the ordering criteria are not quite simple :-)
1796  * if the values are tied
1797  * ST_UP always goes under not ST_UP
1798  * ST_ZONE goes on the most outer side
1799  * ST_END goes towards inner side after ST_ZONE
1800  * ST_FLAT goes on the inner side
1801  */
1802 
1803  for (i = 0; i < n; i++)
1804  for (j = i + 1; j < n; j++) {
1805  if(s[i].value < s[j].value)
1806  continue;
1807  if(s[i].value == s[j].value) {
1808  if( (s[i].flags & ST_UP) < (s[j].flags & ST_UP) )
1809  continue;
1810  if( (s[i].flags & ST_UP) == (s[j].flags & ST_UP) ) {
1811  if( s[i].flags & ST_UP ) {
1812  if(
1813  (s[i].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1814  >
1815  (s[j].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1816  )
1817  continue;
1818  } else {
1819  if(
1820  (s[i].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1821  <
1822  (s[j].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1823  )
1824  continue;
1825  }
1826  }
1827  }
1828  x = s[j];
1829  s[j] = s[i];
1830  s[i] = x;
1831  }
1832 }
1833 
1834 /* check whether two stem borders overlap */
1835 
1836 static int
1838  STEM * s1,
1839  STEM * s2
1840 )
1841 {
1842  int result;
1843 
1844  if (s1->from <= s2->from && s1->to >= s2->from
1845  || s2->from <= s1->from && s2->to >= s1->from)
1846  result = 1;
1847  else
1848  result = 0;
1849 
1850  if (ISDBG(STEMOVERLAP))
1851  fprintf(pfa_file, "%% overlap %d(%d..%d)x%d(%d..%d)=%d\n",
1852  s1->value, s1->from, s1->to, s2->value, s2->from, s2->to, result);
1853  return result;
1854 }
1855 
1856 /*
1857  * check if the stem [border] is in an appropriate blue zone
1858  * (currently not used)
1859  */
1860 
1861 static int
1863  STEM *s
1864 )
1865 {
1866  int i, val;
1867 
1868  val=s->value;
1869  if(s->flags & ST_UP) {
1870  /* painted size up, look at lower zones */
1871  if(nblues>=2 && val>=bluevalues[0] && val<=bluevalues[1] )
1872  return 1;
1873  for(i=0; i<notherb; i++) {
1874  if( val>=otherblues[i] && val<=otherblues[i+1] )
1875  return 1;
1876  }
1877  } else {
1878  /* painted side down, look at upper zones */
1879  for(i=2; i<nblues; i++) {
1880  if( val>=bluevalues[i] && val<=bluevalues[i+1] )
1881  return 1;
1882  }
1883  }
1884 
1885  return 0;
1886 }
1887 
1888 /* mark the outermost stem [borders] in the blue zones */
1889 
1890 static void
1892  STEM *s,
1893  int nold
1894 )
1895 {
1896  int i, j, a, b, c;
1897  /*
1898  * traverse the list of Blue Values, mark the lowest upper
1899  * stem in each bottom zone and the topmost lower stem in
1900  * each top zone with ST_BLUE
1901  */
1902 
1903  /* top zones */
1904  for(i=2; i<nblues; i+=2) {
1905  a=bluevalues[i]; b=bluevalues[i+1];
1906  if(ISDBG(BLUESTEMS))
1907  fprintf(pfa_file, "%% looking at blue zone %d...%d\n", a, b);
1908  for(j=nold-1; j>=0; j--) {
1909  if( s[j].flags & (ST_ZONE|ST_UP|ST_END) )
1910  continue;
1911  c=s[j].value;
1912  if(c<a) /* too low */
1913  break;
1914  if(c<=b) { /* found the topmost stem border */
1915  /* mark all the stems with the same value */
1916  if(ISDBG(BLUESTEMS))
1917  fprintf(pfa_file, "%% found D BLUE at %d\n", s[j].value);
1918  /* include ST_END values */
1919  while( s[j+1].value==c && (s[j+1].flags & ST_ZONE)==0 )
1920  j++;
1921  s[j].flags |= ST_BLUE;
1922  for(j--; j>=0 && s[j].value==c
1923  && (s[j].flags & (ST_UP|ST_ZONE))==0 ; j--)
1924  s[j].flags |= ST_BLUE;
1925  break;
1926  }
1927  }
1928  }
1929  /* baseline */
1930  if(nblues>=2) {
1931  a=bluevalues[0]; b=bluevalues[1];
1932  for(j=0; j<nold; j++) {
1933  if( (s[j].flags & (ST_ZONE|ST_UP|ST_END))!=ST_UP )
1934  continue;
1935  c=s[j].value;
1936  if(c>b) /* too high */
1937  break;
1938  if(c>=a) { /* found the lowest stem border */
1939  /* mark all the stems with the same value */
1940  if(ISDBG(BLUESTEMS))
1941  fprintf(pfa_file, "%% found U BLUE at %d\n", s[j].value);
1942  /* include ST_END values */
1943  while( s[j-1].value==c && (s[j-1].flags & ST_ZONE)==0 )
1944  j--;
1945  s[j].flags |= ST_BLUE;
1946  for(j++; j<nold && s[j].value==c
1947  && (s[j].flags & (ST_UP|ST_ZONE))==ST_UP ; j++)
1948  s[j].flags |= ST_BLUE;
1949  break;
1950  }
1951  }
1952  }
1953  /* bottom zones: the logic is the same as for baseline */
1954  for(i=0; i<notherb; i+=2) {
1955  a=otherblues[i]; b=otherblues[i+1];
1956  for(j=0; j<nold; j++) {
1957  if( (s[j].flags & (ST_UP|ST_ZONE|ST_END))!=ST_UP )
1958  continue;
1959  c=s[j].value;
1960  if(c>b) /* too high */
1961  break;
1962  if(c>=a) { /* found the lowest stem border */
1963  /* mark all the stems with the same value */
1964  if(ISDBG(BLUESTEMS))
1965  fprintf(pfa_file, "%% found U BLUE at %d\n", s[j].value);
1966  /* include ST_END values */
1967  while( s[j-1].value==c && (s[j-1].flags & ST_ZONE)==0 )
1968  j--;
1969  s[j].flags |= ST_BLUE;
1970  for(j++; j<nold && s[j].value==c
1971  && (s[j].flags & (ST_UP|ST_ZONE))==ST_UP ; j++)
1972  s[j].flags |= ST_BLUE;
1973  break;
1974  }
1975  }
1976  }
1977 }
1978 
1979 /* Eliminate invalid stems, join equivalent lines and remove nested stems
1980  * to build the main (non-substituted) set of stems.
1981  * XXX add consideration of the italic angle
1982  */
1983 static int
1985  STEM * s,
1986  int nold,
1987  int useblues /* do we use the blue values ? */
1988 )
1989 {
1990 #define MAX_STACK 1000
1991  STEM stack[MAX_STACK];
1992  int nstack = 0;
1993  int sbottom = 0;
1994  int nnew;
1995  int i, j, k;
1996  int a, b, c, w1, w2, w3;
1997  int fw, fd;
1998  /*
1999  * priority of the last found stem:
2000  * 0 - nothing found yet
2001  * 1 - has ST_END in it (one or more)
2002  * 2 - has no ST_END and no ST_FLAT, can override only one stem
2003  * with priority 1
2004  * 3 - has no ST_END and at least one ST_FLAT, can override one
2005  * stem with priority 2 or any number of stems with priority 1
2006  * 4 (handled separately) - has ST_BLUE, can override anything
2007  */
2008  int readystem = 0;
2009  int pri;
2010  int nlps = 0; /* number of non-committed
2011  * lowest-priority stems */
2012 
2013 
2014  for (i = 0, nnew = 0; i < nold; i++) {
2015  if (s[i].flags & (ST_UP|ST_ZONE)) {
2016  if(s[i].flags & ST_BLUE) {
2017  /* we just HAVE to use this value */
2018  if (readystem)
2019  nnew += 2;
2020  readystem=0;
2021 
2022  /* remember the list of Blue zone stems with the same value */
2023  for(a=i, i++; i<nold && s[a].value==s[i].value
2024  && (s[i].flags & ST_BLUE); i++)
2025  {}
2026  b=i; /* our range is a <= i < b */
2027  c= -1; /* index of our best guess up to now */
2028  pri=0;
2029  /* try to find a match, don't cross blue zones */
2030  for(; i<nold && (s[i].flags & ST_BLUE)==0; i++) {
2031  if(s[i].flags & ST_UP) {
2032  if(s[i].flags & ST_TOPZONE)
2033  break;
2034  else
2035  continue;
2036  }
2037  for(j=a; j<b; j++) {
2038  if(!stemoverlap(&s[j], &s[i]) )
2039  continue;
2040  /* consider priorities */
2041  if( ( (s[j].flags|s[i].flags) & (ST_FLAT|ST_END) )==ST_FLAT ) {
2042  c=i;
2043  goto bluematch;
2044  }
2045  if( ((s[j].flags|s[i].flags) & ST_END)==0 ) {
2046  if(pri < 2) {
2047  c=i; pri=2;
2048  }
2049  } else {
2050  if(pri == 0) {
2051  c=i; pri=1;
2052  }
2053  }
2054  }
2055  }
2056  bluematch:
2057  /* clean up the stack */
2058  nstack=sbottom=0;
2059  readystem=0;
2060  /* add this stem */
2061  s[nnew++]=s[a];
2062  if(c<0) { /* make one-dot-wide stem */
2063  if(nnew>=b) { /* have no free space */
2064  for(j=nold; j>=b; j--) /* make free space */
2065  s[j]=s[j-1];
2066  b++;
2067  nold++;
2068  }
2069  s[nnew]=s[a];
2070  s[nnew].flags &= ~(ST_UP|ST_BLUE);
2071  nnew++;
2072  i=b-1;
2073  } else {
2074  s[nnew++]=s[c];
2075  i=c; /* skip up to this point */
2076  }
2077  if (ISDBG(MAINSTEMS))
2078  fprintf(pfa_file, "%% +stem %d...%d U BLUE\n",
2079  s[nnew-2].value, s[nnew-1].value);
2080  } else {
2081  if (nstack >= MAX_STACK) {
2082  WARNING_1 fprintf(stderr, "Warning: **** converter's stem stack overflow ****\n");
2083  nstack = 0;
2084  }
2085  stack[nstack++] = s[i];
2086  }
2087  } else if(s[i].flags & ST_BLUE) {
2088  /* again, we just HAVE to use this value */
2089  if (readystem)
2090  nnew += 2;
2091  readystem=0;
2092 
2093  /* remember the list of Blue zone stems with the same value */
2094  for(a=i, i++; i<nold && s[a].value==s[i].value
2095  && (s[i].flags & ST_BLUE); i++)
2096  {}
2097  b=i; /* our range is a <= i < b */
2098  c= -1; /* index of our best guess up to now */
2099  pri=0;
2100  /* try to find a match */
2101  for (i = nstack - 1; i >= 0; i--) {
2102  if( (stack[i].flags & ST_UP)==0 ) {
2103  if( (stack[i].flags & (ST_ZONE|ST_TOPZONE))==ST_ZONE )
2104  break;
2105  else
2106  continue;
2107  }
2108  for(j=a; j<b; j++) {
2109  if(!stemoverlap(&s[j], &stack[i]) )
2110  continue;
2111  /* consider priorities */
2112  if( ( (s[j].flags|stack[i].flags) & (ST_FLAT|ST_END) )==ST_FLAT ) {
2113  c=i;
2114  goto bluedownmatch;
2115  }
2116  if( ((s[j].flags|stack[i].flags) & ST_END)==0 ) {
2117  if(pri < 2) {
2118  c=i; pri=2;
2119  }
2120  } else {
2121  if(pri == 0) {
2122  c=i; pri=1;
2123  }
2124  }
2125  }
2126  }
2127  bluedownmatch:
2128  /* if found no match make a one-dot-wide stem */
2129  if(c<0) {
2130  c=0;
2131  stack[0]=s[b-1];
2132  stack[0].flags |= ST_UP;
2133  stack[0].flags &= ~~ST_BLUE;
2134  }
2135  /* remove all the stems conflicting with this one */
2136  readystem=0;
2137  for(j=nnew-2; j>=0; j-=2) {
2138  if (ISDBG(MAINSTEMS))
2139  fprintf(pfa_file, "%% ?stem %d...%d -- %d\n",
2140  s[j].value, s[j+1].value, stack[c].value);
2141  if(s[j+1].value < stack[c].value) /* no conflict */
2142  break;
2143  if(s[j].flags & ST_BLUE) {
2144  /* oops, we don't want to spoil other blue zones */
2145  stack[c].value=s[j+1].value+1;
2146  break;
2147  }
2148  if( (s[j].flags|s[j+1].flags) & ST_END ) {
2149  if (ISDBG(MAINSTEMS))
2150  fprintf(pfa_file, "%% -stem %d...%d p=1\n",
2151  s[j].value, s[j+1].value);
2152  continue; /* pri==1, silently discard it */
2153  }
2154  /* we want to discard no nore than 2 stems of pri>=2 */
2155  if( ++readystem > 2 ) {
2156  /* change our stem to not conflict */
2157  stack[c].value=s[j+1].value+1;
2158  break;
2159  } else {
2160  if (ISDBG(MAINSTEMS))
2161  fprintf(pfa_file, "%% -stem %d...%d p>=2\n",
2162  s[j].value, s[j+1].value);
2163  continue;
2164  }
2165  }
2166  nnew=j+2;
2167  /* add this stem */
2168  if(nnew>=b-1) { /* have no free space */
2169  for(j=nold; j>=b-1; j--) /* make free space */
2170  s[j]=s[j-1];
2171  b++;
2172  nold++;
2173  }
2174  s[nnew++]=stack[c];
2175  s[nnew++]=s[b-1];
2176  /* clean up the stack */
2177  nstack=sbottom=0;
2178  readystem=0;
2179  /* set the next position to search */
2180  i=b-1;
2181  if (ISDBG(MAINSTEMS))
2182  fprintf(pfa_file, "%% +stem %d...%d D BLUE\n",
2183  s[nnew-2].value, s[nnew-1].value);
2184  } else if (nstack > 0) {
2185 
2186  /*
2187  * check whether our stem overlaps with anything in
2188  * stack
2189  */
2190  for (j = nstack - 1; j >= sbottom; j--) {
2191  if (s[i].value <= stack[j].value)
2192  break;
2193  if (stack[j].flags & ST_ZONE)
2194  continue;
2195 
2196  if ((s[i].flags & ST_END)
2197  || (stack[j].flags & ST_END))
2198  pri = 1;
2199  else if ((s[i].flags & ST_FLAT)
2200  || (stack[j].flags & ST_FLAT))
2201  pri = 3;
2202  else
2203  pri = 2;
2204 
2205  if (pri < readystem && s[nnew + 1].value >= stack[j].value
2206  || !stemoverlap(&stack[j], &s[i]))
2207  continue;
2208 
2209  if (readystem > 1 && s[nnew + 1].value < stack[j].value) {
2210  nnew += 2;
2211  readystem = 0;
2212  nlps = 0;
2213  }
2214  /*
2215  * width of the previous stem (if it's
2216  * present)
2217  */
2218  w1 = s[nnew + 1].value - s[nnew].value;
2219 
2220  /* width of this stem */
2221  w2 = s[i].value - stack[j].value;
2222 
2223  if (readystem == 0) {
2224  /* nothing yet, just add a new stem */
2225  s[nnew] = stack[j];
2226  s[nnew + 1] = s[i];
2227  readystem = pri;
2228  if (pri == 1)
2229  nlps = 1;
2230  else if (pri == 2)
2231  sbottom = j;
2232  else {
2233  sbottom = j + 1;
2234  while (sbottom < nstack
2235  && stack[sbottom].value <= stack[j].value)
2236  sbottom++;
2237  }
2238  if (ISDBG(MAINSTEMS))
2239  fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
2240  stack[j].value, s[i].value, pri, nlps);
2241  } else if (pri == 1) {
2242  if (stack[j].value > s[nnew + 1].value) {
2243  /*
2244  * doesn't overlap with the
2245  * previous one
2246  */
2247  nnew += 2;
2248  nlps++;
2249  s[nnew] = stack[j];
2250  s[nnew + 1] = s[i];
2251  if (ISDBG(MAINSTEMS))
2252  fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
2253  stack[j].value, s[i].value, pri, nlps);
2254  } else if (w2 < w1) {
2255  /* is narrower */
2256  s[nnew] = stack[j];
2257  s[nnew + 1] = s[i];
2258  if (ISDBG(MAINSTEMS))
2259  fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d %d->%d\n",
2260  stack[j].value, s[i].value, pri, nlps, w1, w2);
2261  }
2262  } else if (pri == 2) {
2263  if (readystem == 2) {
2264  /* choose the narrower stem */
2265  if (w1 > w2) {
2266  s[nnew] = stack[j];
2267  s[nnew + 1] = s[i];
2268  sbottom = j;
2269  if (ISDBG(MAINSTEMS))
2270  fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n",
2271  stack[j].value, s[i].value, pri, nlps);
2272  }
2273  /* else readystem==1 */
2274  } else if (stack[j].value > s[nnew + 1].value) {
2275  /*
2276  * value doesn't overlap with
2277  * the previous one
2278  */
2279  nnew += 2;
2280  nlps = 0;
2281  s[nnew] = stack[j];
2282  s[nnew + 1] = s[i];
2283  sbottom = j;
2284  readystem = pri;
2285  if (ISDBG(MAINSTEMS))
2286  fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
2287  stack[j].value, s[i].value, pri, nlps);
2288  } else if (nlps == 1
2289  || stack[j].value > s[nnew - 1].value) {
2290  /*
2291  * we can replace the top
2292  * stem
2293  */
2294  nlps = 0;
2295  s[nnew] = stack[j];
2296  s[nnew + 1] = s[i];
2297  readystem = pri;
2298  sbottom = j;
2299  if (ISDBG(MAINSTEMS))
2300  fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n",
2301  stack[j].value, s[i].value, pri, nlps);
2302  }
2303  } else if (readystem == 3) { /* that means also
2304  * pri==3 */
2305  /* choose the narrower stem */
2306  if (w1 > w2) {
2307  s[nnew] = stack[j];
2308  s[nnew + 1] = s[i];
2309  sbottom = j + 1;
2310  while (sbottom < nstack
2311  && stack[sbottom].value <= stack[j].value)
2312  sbottom++;
2313  if (ISDBG(MAINSTEMS))
2314  fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n",
2315  stack[j].value, s[i].value, pri, nlps);
2316  }
2317  } else if (pri == 3) {
2318  /*
2319  * we can replace as many stems as
2320  * neccessary
2321  */
2322  nnew += 2;
2323  while (nnew > 0 && s[nnew - 1].value >= stack[j].value) {
2324  nnew -= 2;
2325  if (ISDBG(MAINSTEMS))
2326  fprintf(pfa_file, "%% -stem %d..%d\n",
2327  s[nnew].value, s[nnew + 1].value);
2328  }
2329  nlps = 0;
2330  s[nnew] = stack[j];
2331  s[nnew + 1] = s[i];
2332  readystem = pri;
2333  sbottom = j + 1;
2334  while (sbottom < nstack
2335  && stack[sbottom].value <= stack[j].value)
2336  sbottom++;
2337  if (ISDBG(MAINSTEMS))
2338  fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
2339  stack[j].value, s[i].value, pri, nlps);
2340  }
2341  }
2342  }
2343  }
2344  if (readystem)
2345  nnew += 2;
2346 
2347  /* change the 1-pixel-wide stems to 20-pixel-wide stems if possible
2348  * the constant 20 is recommended in the Type1 manual
2349  */
2350  if(useblues) {
2351  for(i=0; i<nnew; i+=2) {
2352  if(s[i].value != s[i+1].value)
2353  continue;
2354  if( ((s[i].flags ^ s[i+1].flags) & ST_BLUE)==0 )
2355  continue;
2356  if( s[i].flags & ST_BLUE ) {
2357  if(nnew>i+2 && s[i+2].value<s[i].value+22)
2358  s[i+1].value=s[i+2].value-2; /* compensate for fuzziness */
2359  else
2360  s[i+1].value+=20;
2361  } else {
2362  if(i>0 && s[i-1].value>s[i].value-22)
2363  s[i].value=s[i-1].value+2; /* compensate for fuzziness */
2364  else
2365  s[i].value-=20;
2366  }
2367  }
2368  }
2369  /* make sure that no stem it stretched between
2370  * a top zone and a bottom zone
2371  */
2372  if(useblues) {
2373  for(i=0; i<nnew; i+=2) {
2374  a=10000; /* lowest border of top zone crosing the stem */
2375  b= -10000; /* highest border of bottom zone crossing the stem */
2376 
2377  for(j=2; j<nblues; j++) {
2378  c=bluevalues[j];
2379  if( c>=s[i].value && c<=s[i+1].value && c<a )
2380  a=c;
2381  }
2382  if(nblues>=2) {
2383  c=bluevalues[1];
2384  if( c>=s[i].value && c<=s[i+1].value && c>b )
2385  b=c;
2386  }
2387  for(j=1; j<notherb; j++) {
2388  c=otherblues[j];
2389  if( c>=s[i].value && c<=s[i+1].value && c>b )
2390  b=c;
2391  }
2392  if( a!=10000 && b!= -10000 ) { /* it is stretched */
2393  /* split the stem into 2 ghost stems */
2394  for(j=nnew+1; j>i+1; j--) /* make free space */
2395  s[j]=s[j-2];
2396  nnew+=2;
2397 
2398  if(s[i].value+22 >= a)
2399  s[i+1].value=a-2; /* leave space for fuzziness */
2400  else
2401  s[i+1].value=s[i].value+20;
2402 
2403  if(s[i+3].value-22 <= b)
2404  s[i+2].value=b+2; /* leave space for fuzziness */
2405  else
2406  s[i+2].value=s[i+3].value-20;
2407 
2408  i+=2;
2409  }
2410  }
2411  }
2412  /* look for triple stems */
2413  for (i = 0; i < nnew; i += 2) {
2414  if (nnew - i >= 6) {
2415  a = s[i].value + s[i + 1].value;
2416  b = s[i + 2].value + s[i + 3].value;
2417  c = s[i + 4].value + s[i + 5].value;
2418 
2419  w1 = s[i + 1].value - s[i].value;
2420  w2 = s[i + 3].value - s[i + 2].value;
2421  w3 = s[i + 5].value - s[i + 4].value;
2422 
2423  fw = w3 - w1; /* fuzz in width */
2424  fd = ((c - b) - (b - a)); /* fuzz in distance
2425  * (doubled) */
2426 
2427  /* we are able to handle some fuzz */
2428  /*
2429  * it doesn't hurt if the declared stem is a bit
2430  * narrower than actual unless it's an edge in
2431  * a blue zone
2432  */
2433  if (abs(abs(fd) - abs(fw)) * 5 < w2
2434  && abs(fw) * 20 < (w1 + w3)) { /* width dirrerence <10% */
2435 
2436  if(useblues) { /* check that we don't disturb any blue stems */
2437  j=c; k=a;
2438  if (fw > 0) {
2439  if (fd > 0) {
2440  if( s[i+5].flags & ST_BLUE )
2441  continue;
2442  j -= fw;
2443  } else {
2444  if( s[i+4].flags & ST_BLUE )
2445  continue;
2446  j += fw;
2447  }
2448  } else if(fw < 0) {
2449  if (fd > 0) {
2450  if( s[i+1].flags & ST_BLUE )
2451  continue;
2452  k -= fw;
2453  } else {
2454  if( s[i].flags & ST_BLUE )
2455  continue;
2456  k += fw;
2457  }
2458  }
2459  pri = ((j - b) - (b - k));
2460 
2461  if (pri > 0) {
2462  if( s[i+2].flags & ST_BLUE )
2463  continue;
2464  } else if(pri < 0) {
2465  if( s[i+3].flags & ST_BLUE )
2466  continue;
2467  }
2468  }
2469 
2470  /*
2471  * first fix up the width of 1st and 3rd
2472  * stems
2473  */
2474  if (fw > 0) {
2475  if (fd > 0) {
2476  s[i + 5].value -= fw;
2477  c -= fw;
2478  } else {
2479  s[i + 4].value += fw;
2480  c += fw;
2481  }
2482  } else {
2483  if (fd > 0) {
2484  s[i + 1].value -= fw;
2485  a -= fw;
2486  } else {
2487  s[i].value += fw;
2488  a += fw;
2489  }
2490  }
2491  fd = ((c - b) - (b - a));
2492 
2493  if (fd > 0) {
2494  s[i + 2].value += abs(fd) / 2;
2495  } else {
2496  s[i + 3].value -= abs(fd) / 2;
2497  }
2498 
2499  s[i].flags |= ST_3;
2500  i += 4;
2501  }
2502  }
2503  }
2504 
2505  return (nnew & ~1); /* number of lines must be always even */
2506 }
2507 
2508 /*
2509  * these macros and function allow to set the base stem,
2510  * check that it's not empty and subtract another stem
2511  * from the base stem (possibly dividing it into multiple parts)
2512  */
2513 
2514 /* pairs for pieces of the base stem */
2515 static short xbstem[MAX_STEMS*2];
2516 /* index of the last point */
2517 static int xblast= -1;
2518 
2519 #define setbasestem(from, to) \
2520  (xbstem[0]=from, xbstem[1]=to, xblast=1)
2521 #define isbaseempty() (xblast<=0)
2522 
2523 /* returns 1 if was overlapping, 0 otherwise */
2524 static int
2526  int from,
2527  int to
2528 )
2529 {
2530  int a, b;
2531  int i, j;
2532 
2533  if(isbaseempty())
2534  return 0;
2535 
2536  /* handle the simple case simply */
2537  if(from > xbstem[xblast] || to < xbstem[0])
2538  return 0;
2539 
2540  /* the binary search may be more efficient */
2541  /* but for now the linear search is OK */
2542  for(b=1; from > xbstem[b]; b+=2) {} /* result: from <= xbstem[b] */
2543  for(a=xblast-1; to < xbstem[a]; a-=2) {} /* result: to >= xbstem[a] */
2544 
2545  /* now the interesting examples are:
2546  * (it was hard for me to understand, so I looked at the examples)
2547  * 1
2548  * a|-----| |-----|b |-----| |-----|
2549  * f|-----|t
2550  * 2
2551  * a|-----|b |-----| |-----| |-----|
2552  * f|--|t
2553  * 3
2554  * a|-----|b |-----| |-----| |-----|
2555  * f|-----|t
2556  * 4
2557  * |-----|b a|-----| |-----| |-----|
2558  * f|------------|t
2559  * 5
2560  * |-----| |-----|b |-----| a|-----|
2561  * f|-----------------------------|t
2562  * 6
2563  * |-----|b |-----| |-----| a|-----|
2564  * f|--------------------------------------------------|t
2565  * 7
2566  * |-----|b |-----| a|-----| |-----|
2567  * f|--------------------------|t
2568  */
2569 
2570  if(a < b-1) /* hits a gap - example 1 */
2571  return 0;
2572 
2573  /* now the subtraction itself */
2574 
2575  if(a==b-1 && from > xbstem[a] && to < xbstem[b]) {
2576  /* overlaps with only one subrange and splits it - example 2 */
2577  j=xblast; i=(xblast+=2);
2578  while(j>=b)
2579  xbstem[i--]=xbstem[j--];
2580  xbstem[b]=from-1;
2581  xbstem[b+1]=to+1;
2582  return 1;
2583  /* becomes
2584  * 2a
2585  * a|b || |-----| |-----| |-----|
2586  * f|--|t
2587  */
2588  }
2589 
2590  if(xbstem[b-1] < from) {
2591  /* cuts the back of this subrange - examples 3, 4, 7 */
2592  xbstem[b] = from-1;
2593  b+=2;
2594  /* becomes
2595  * 3a
2596  * a|----| |-----|b |-----| |-----|
2597  * f|-----|t
2598  * 4a
2599  * |---| a|-----|b |-----| |-----|
2600  * f|------------|t
2601  * 7a
2602  * |---| |-----|b a|-----| |-----|
2603  * f|--------------------------|t
2604  */
2605  }
2606 
2607  if(xbstem[a+1] > to) {
2608  /* cuts the front of this subrange - examples 4a, 5, 7a */
2609  xbstem[a] = to+1;
2610  a-=2;
2611  /* becomes
2612  * 4b
2613  * a|---| |---|b |-----| |-----|
2614  * f|------------|t
2615  * 5b
2616  * |-----| |-----|b a|-----| ||
2617  * f|-----------------------------|t
2618  * 7b
2619  * |---| a|-----|b || |-----|
2620  * f|--------------------------|t
2621  */
2622  }
2623 
2624  if(a < b-1) /* now after modification it hits a gap - examples 3a, 4b */
2625  return 1; /* because we have removed something */
2626 
2627  /* now remove the subranges completely covered by the new stem */
2628  /* examples 5b, 6, 7b */
2629  i=b-1; j=a+2;
2630  /* positioned as:
2631  * 5b i j
2632  * |-----| |-----|b a|-----| ||
2633  * f|-----------------------------|t
2634  * 6 i xblast j
2635  * |-----|b |-----| |-----| a|-----|
2636  * f|--------------------------------------------------|t
2637  * 7b i j
2638  * |---| a|-----|b || |-----|
2639  * f|--------------------------|t
2640  */
2641  while(j <= xblast)
2642  xbstem[i++]=xbstem[j++];
2643  xblast=i-1;
2644  return 1;
2645 }
2646 
2647 /* for debugging */
2648 static void
2650 {
2651  int i;
2652 
2653  printf("( ");
2654  for(i=0; i<xblast; i+=2)
2655  printf("%d-%d ", xbstem[i], xbstem[i+1]);
2656  printf(") %d\n", xblast);
2657 }
2658 
2659 /*
2660  * Join the stem borders to build the sets of substituted stems
2661  * XXX add consideration of the italic angle
2662  */
2663 static void
2665  STEM * s,
2666  short *pairs,
2667  int nold,
2668  int useblues /* do we use the blue values ? */
2669 )
2670 {
2671  int i, j, x;
2672  static unsigned char mx[MAX_STEMS][MAX_STEMS];
2673 
2674  /* we do the substituted groups of stems first
2675  * and it looks like it's going to be REALLY SLOW
2676  * AND PAINFUL but let's bother about it later
2677  */
2678 
2679  /* for the substituted stems we don't bother about [hv]stem3 -
2680  * anyway the X11R6 rasterizer does not bother about hstem3
2681  * at all and is able to handle only one global vstem3
2682  * per glyph
2683  */
2684 
2685  /* clean the used part of matrix */
2686  for(i=0; i<nold; i++)
2687  for(j=0; j<nold; j++)
2688  mx[i][j]=0;
2689 
2690  /* build the matrix of stem pairs */
2691  for(i=0; i<nold; i++) {
2692  if( s[i].flags & ST_ZONE )
2693  continue;
2694  if(s[i].flags & ST_BLUE)
2695  mx[i][i]=1; /* allow to pair with itself if no better pair */
2696  if(s[i].flags & ST_UP) { /* the down-stems are already matched */
2697  setbasestem(s[i].from, s[i].to);
2698  for(j=i+1; j<nold; j++) {
2699  if(s[i].value==s[j].value
2700  || s[j].flags & ST_ZONE ) {
2701  continue;
2702  }
2703  x=subfrombase(s[j].from, s[j].to);
2704 
2705  if(s[j].flags & ST_UP) /* match only up+down pairs */
2706  continue;
2707 
2708  mx[i][j]=mx[j][i]=x;
2709 
2710  if(isbaseempty()) /* nothing else to do */
2711  break;
2712  }
2713  }
2714  }
2715 
2716  if(ISDBG(SUBSTEMS)) {
2717  fprintf(pfa_file, "%% ");
2718  for(j=0; j<nold; j++)
2719  putc( j%10==0 ? '0'+(j/10)%10 : ' ', pfa_file);
2720  fprintf(pfa_file, "\n%% ");
2721  for(j=0; j<nold; j++)
2722  putc('0'+j%10, pfa_file);
2723  putc('\n', pfa_file);
2724  for(i=0; i<nold; i++) {
2725  fprintf(pfa_file, "%% %3d ",i);
2726  for(j=0; j<nold; j++)
2727  putc( mx[i][j] ? 'X' : '.', pfa_file);
2728  putc('\n', pfa_file);
2729  }
2730  }
2731 
2732  /* now use the matrix to find the best pair for each stem */
2733  for(i=0; i<nold; i++) {
2734  int pri, lastpri, v, f;
2735 
2736  x= -1; /* best pair: none */
2737  lastpri=0;
2738 
2739  v=s[i].value;
2740  f=s[i].flags;
2741 
2742  if(f & ST_ZONE) {
2743  pairs[i]= -1;
2744  continue;
2745  }
2746 
2747  if(f & ST_UP) {
2748  for(j=i+1; j<nold; j++) {
2749  if(mx[i][j]==0)
2750  continue;
2751 
2752  if( (f | s[j].flags) & ST_END )
2753  pri=1;
2754  else if( (f | s[j].flags) & ST_FLAT )
2755  pri=3;
2756  else
2757  pri=2;
2758 
2759  if(lastpri==0
2760  || pri > lastpri
2761  && ( lastpri==1 || s[j].value-v<20 || (s[x].value-v)*2 >= s[j].value-v ) ) {
2762  lastpri=pri;
2763  x=j;
2764  }
2765  }
2766  } else {
2767  for(j=i-1; j>=0; j--) {
2768  if(mx[i][j]==0)
2769  continue;
2770 
2771  if( (f | s[j].flags) & ST_END )
2772  pri=1;
2773  else if( (f | s[j].flags) & ST_FLAT )
2774  pri=3;
2775  else
2776  pri=2;
2777 
2778  if(lastpri==0
2779  || pri > lastpri
2780  && ( lastpri==1 || v-s[j].value<20 || (v-s[x].value)*2 >= v-s[j].value ) ) {
2781  lastpri=pri;
2782  x=j;
2783  }
2784  }
2785  }
2786  if(x== -1 && mx[i][i])
2787  pairs[i]=i; /* a special case */
2788  else
2789  pairs[i]=x;
2790  }
2791 
2792  if(ISDBG(SUBSTEMS)) {
2793  for(i=0; i<nold; i++) {
2794  j=pairs[i];
2795  if(j>0)
2796  fprintf(pfa_file, "%% %d...%d (%d x %d)\n", s[i].value, s[j].value, i, j);
2797  }
2798  }
2799 }
2800 
2801 /*
2802  * Make all the stems originating at the same value get the
2803  * same width. Without this the rasterizer may move the dots
2804  * randomly up or down by one pixel, and that looks bad.
2805  * The prioritisation is the same as in findstemat().
2806  */
2807 static void
2809  STEM * s,
2810  short *pairs,
2811  int ns
2812 )
2813 {
2814  int i, from, to, val, dir;
2815  int pri, prevpri[2], wd, prevwd[2], prevbest[2];
2816 
2817  for(from=0; from<ns; from=to) {
2818  prevpri[0] = prevpri[1] = 0;
2819  prevwd[0] = prevwd[1] = 0;
2820  prevbest[0] = prevbest[1] = -1;
2821  val = s[from].value;
2822 
2823  for(to = from; to<ns && s[to].value == val; to++) {
2824  dir = ((s[to].flags & ST_UP)!=0);
2825 
2826  i=pairs[to]; /* the other side of this stem */
2827  if(i<0 || i==to)
2828  continue; /* oops, no other side */
2829  wd=abs(s[i].value-val);
2830  if(wd == 0)
2831  continue;
2832  pri=1;
2833  if( (s[to].flags | s[i].flags) & ST_END )
2834  pri=0;
2835  if( prevbest[dir] == -1 || pri > prevpri[dir] || wd<prevwd[dir] ) {
2836  prevbest[dir]=i;
2837  prevpri[dir]=pri;
2838  prevwd[dir]=wd;
2839  }
2840  }
2841 
2842  for(i=from; i<to; i++) {
2843  dir = ((s[i].flags & ST_UP)!=0);
2844  if(prevbest[dir] >= 0) {
2845  if(ISDBG(SUBSTEMS)) {
2846  fprintf(stderr, "at %d (%s %d) pair %d->%d(%d)\n", i,
2847  (dir ? "UP":"DOWN"), s[i].value, pairs[i], prevbest[dir],
2848  s[prevbest[dir]].value);
2849  }
2850  pairs[i] = prevbest[dir];
2851  }
2852  }
2853  }
2854 }
2855 
2856 /*
2857  * Find the best stem in the array at the specified (value, origin),
2858  * related to the entry ge.
2859  * Returns its index in the array sp, -1 means "none".
2860  * prevbest is the result for the other end of the line, we must
2861  * find something better than it or leave it as it is.
2862  */
2863 static int
2865  int value,
2866  int origin,
2867  GENTRY *ge,
2868  STEM *sp,
2869  short *pairs,
2870  int ns,
2871  int prevbest /* -1 means "none" */
2872 )
2873 {
2874  int i, min, max;
2875  int v, si;
2876  int pri, prevpri; /* priority, 0 = has ST_END, 1 = no ST_END */
2877  int wd, prevwd; /* stem width */
2878 
2879  si= -1; /* nothing yet */
2880 
2881  /* stems are ordered by value, binary search */
2882  min=0; max=ns; /* min <= i < max */
2883  while( min < max ) {
2884  i=(min+max)/2;
2885  v=sp[i].value;
2886  if(v<value)
2887  min=i+1;
2888  else if(v>value)
2889  max=i;
2890  else {
2891  si=i; /* temporary value */
2892  break;
2893  }
2894  }
2895 
2896  if( si < 0 ) /* found nothing this time */
2897  return prevbest;
2898 
2899  /* find the priority of the prevbest */
2900  /* we expect that prevbest has a pair */
2901  if(prevbest>=0) {
2902  i=pairs[prevbest];
2903  prevpri=1;
2904  if( (sp[prevbest].flags | sp[i].flags) & ST_END )
2905  prevpri=0;
2906  prevwd=abs(sp[i].value-value);
2907  }
2908 
2909  /* stems are not ordered by origin, so now do the linear search */
2910 
2911  while( si>0 && sp[si-1].value==value ) /* find the first one */
2912  si--;
2913 
2914  for(; si<ns && sp[si].value==value; si++) {
2915  if(sp[si].origin != origin)
2916  continue;
2917  if(sp[si].ge != ge) {
2918  if(ISDBG(SUBSTEMS)) {
2919  fprintf(stderr,
2920  "dbg: possible self-intersection at v=%d o=%d exp_ge=0x%zx ge=0x%zx\n",
2921  value, origin, (size_t)ge, (size_t)sp[si].ge);
2922  }
2923  continue;
2924  }
2925  i=pairs[si]; /* the other side of this stem */
2926  if(i<0)
2927  continue; /* oops, no other side */
2928  pri=1;
2929  if( (sp[si].flags | sp[i].flags) & ST_END )
2930  pri=0;
2931  wd=abs(sp[i].value-value);
2932  if( prevbest == -1 || pri >prevpri
2933  || pri==prevpri && prevwd==0 || wd!=0 && wd<prevwd ) {
2934  prevbest=si;
2935  prevpri=pri;
2936  prevwd=wd;
2937  continue;
2938  }
2939  }
2940 
2941  return prevbest;
2942 }
2943 
2944 /* add the substems for one glyph entry
2945  * (called from groupsubstems())
2946  * returns 0 if all OK, 1 if too many groups
2947  */
2948 
2949 static int gssentry_lastgrp=0; /* reset to 0 for each new glyph */
2950 
2951 static int
2952 gssentry( /* crazy number of parameters */
2953  GENTRY *ge,
2954  STEM *hs, /* horizontal stems, sorted by value */
2955  short *hpairs,
2956  int nhs,
2957  STEM *vs, /* vertical stems, sorted by value */
2958  short *vpairs,
2959  int nvs,
2960  STEMBOUNDS *s,
2961  short *egp,
2962  int *nextvsi,
2963  int *nexthsi /* -2 means "check by yourself" */
2964 ) {
2965  enum {
2966  SI_VP, /* vertical primary */
2967  SI_HP, /* horizontal primary */
2968  SI_SIZE /* size of the array */
2969  };
2970  int si[SI_SIZE]; /* indexes of relevant stems */
2971 
2972  /* the bounds of the existing relevant stems */
2973  STEMBOUNDS r[ sizeof(si) / sizeof(si[0]) * 2 ];
2974  char rexpand; /* by how much we need to expand the group */
2975  int nr; /* and the number of them */
2976 
2977  /* yet more temporary storage */
2978  short lb, hb, isvert;
2979  int conflict, grp;
2980  int i, j, x, y;
2981 
2982 
2983  /* for each line or curve we try to find a horizontal and
2984  * a vertical stem corresponding to its first point
2985  * (corresponding to the last point of the previous
2986  * glyph entry), because the directions of the lines
2987  * will be eventually reversed and it will then become the last
2988  * point. And the T1 rasterizer applies the hints to
2989  * the last point.
2990  *
2991  */
2992 
2993  /* start with the common part, the first point */
2994  x=ge->prev->ix3;
2995  y=ge->prev->iy3;
2996 
2997  if(*nextvsi == -2)
2998  si[SI_VP]=findstemat(x, y, ge, vs, vpairs, nvs, -1);
2999  else {
3000  si[SI_VP]= *nextvsi; *nextvsi= -2;
3001  }
3002  if(*nexthsi == -2)
3003  si[SI_HP]=findstemat(y, x, ge, hs, hpairs, nhs, -1);
3004  else {
3005  si[SI_HP]= *nexthsi; *nexthsi= -2;
3006  }
3007 
3008  /*
3009  * For the horizontal lines we make sure that both
3010  * ends of the line have the same horizontal stem,
3011  * and the same thing for vertical lines and stems.
3012  * In both cases we enforce the stem for the next entry.
3013  * Otherwise unpleasant effects may arise.
3014  */
3015 
3016  if(ge->type==GE_LINE) {
3017  if(ge->ix3==x) { /* vertical line */
3018  *nextvsi=si[SI_VP]=findstemat(x, ge->iy3, ge->frwd, vs, vpairs, nvs, si[SI_VP]);
3019  } else if(ge->iy3==y) { /* horizontal line */
3020  *nexthsi=si[SI_HP]=findstemat(y, ge->ix3, ge->frwd, hs, hpairs, nhs, si[SI_HP]);
3021  }
3022  }
3023 
3024  if(si[SI_VP]+si[SI_HP] == -2) /* no stems, leave it alone */
3025  return 0;
3026 
3027  /* build the array of relevant bounds */
3028  nr=0;
3029  for(i=0; i< sizeof(si) / sizeof(si[0]); i++) {
3030  STEM *sp;
3031  short *pairs;
3032  int step;
3033  int f;
3034  int nzones, firstzone, binzone, einzone;
3035  int btype, etype;
3036 
3037  if(si[i] < 0)
3038  continue;
3039 
3040  if(i<SI_HP) {
3041  r[nr].isvert=1; sp=vs; pairs=vpairs;
3042  } else {
3043  r[nr].isvert=0; sp=hs; pairs=hpairs;
3044  }
3045 
3046  r[nr].low=sp[ si[i] ].value;
3047  r[nr].high=sp[ pairs[ si[i] ] ].value;
3048 
3049  if(r[nr].low > r[nr].high) {
3050  j=r[nr].low; r[nr].low=r[nr].high; r[nr].high=j;
3051  step= -1;
3052  } else {
3053  step=1;
3054  }
3055 
3056  /* handle the interaction with Blue Zones */
3057 
3058  if(i>=SI_HP) { /* only for horizontal stems */
3059  if(si[i]==pairs[si[i]]) {
3060  /* special case, the outermost stem in the
3061  * Blue Zone without a pair, simulate it to 20-pixel
3062  */
3063  if(sp[ si[i] ].flags & ST_UP) {
3064  r[nr].high+=20;
3065  for(j=si[i]+1; j<nhs; j++)
3066  if( (sp[j].flags & (ST_ZONE|ST_TOPZONE))
3067  == (ST_ZONE|ST_TOPZONE) ) {
3068  if(r[nr].high > sp[j].value-2)
3069  r[nr].high=sp[j].value-2;
3070  break;
3071  }
3072  } else {
3073  r[nr].low-=20;
3074  for(j=si[i]-1; j>=0; j--)
3075  if( (sp[j].flags & (ST_ZONE|ST_TOPZONE))
3076  == (ST_ZONE) ) {
3077  if(r[nr].low < sp[j].value+2)
3078  r[nr].low=sp[j].value+2;
3079  break;
3080  }
3081  }
3082  }
3083 
3084  /* check that the stem borders don't end up in
3085  * different Blue Zones */
3086  f=sp[ si[i] ].flags;
3087  nzones=0; einzone=binzone=0;
3088  for(j=si[i]; j!=pairs[ si[i] ]; j+=step) {
3089  if( (sp[j].flags & ST_ZONE)==0 )
3090  continue;
3091  /* if see a zone border going in the same direction */
3092  if( ((f ^ sp[j].flags) & ST_UP)==0 ) {
3093  if( ++nzones == 1 ) {
3094  firstzone=sp[j].value; /* remember the first one */
3095  etype=sp[j].flags & ST_TOPZONE;
3096  }
3097  einzone=1;
3098 
3099  } else { /* the opposite direction */
3100  if(nzones==0) { /* beginning is in a blue zone */
3101  binzone=1;
3102  btype=sp[j].flags & ST_TOPZONE;
3103  }
3104  einzone=0;
3105  }
3106  }
3107 
3108  /* beginning and end are in Blue Zones of different types */
3109  if( binzone && einzone && (btype ^ etype)!=0 ) {
3110  if( sp[si[i]].flags & ST_UP ) {
3111  if(firstzone > r[nr].low+22)
3112  r[nr].high=r[nr].low+20;
3113  else
3114  r[nr].high=firstzone-2;
3115  } else {
3116  if(firstzone < r[nr].high-22)
3117  r[nr].low=r[nr].high-20;
3118  else
3119  r[nr].low=firstzone+2;
3120  }
3121  }
3122  }
3123 
3124  if(ISDBG(SUBSTEMS))
3125  fprintf(pfa_file, "%% at(%d,%d)[%d,%d] %d..%d %c (%d x %d)\n", x, y, i, nr,
3126  r[nr].low, r[nr].high, r[nr].isvert ? 'v' : 'h',
3127  si[i], pairs[si[i]]);
3128 
3129  nr++;
3130  }
3131 
3132  /* now try to find a group */
3133  conflict=0; /* no conflicts found yet */
3134  for(j=0; j<nr; j++)
3135  r[j].already=0;
3136 
3137  /* check if it fits into the last group */
3138  grp = gssentry_lastgrp;
3139  i = (grp==0)? 0 : egp[grp-1];
3140  for(; i<egp[grp]; i++) {
3141  lb=s[i].low; hb=s[i].high; isvert=s[i].isvert;
3142  for(j=0; j<nr; j++)
3143  if( r[j].isvert==isvert /* intersects */
3144  && r[j].low <= hb && r[j].high >= lb ) {
3145  if( r[j].low == lb && r[j].high == hb ) /* coincides */
3146  r[j].already=1;
3147  else
3148  conflict=1;
3149  }
3150 
3151  if(conflict)
3152  break;
3153  }
3154 
3155  if(conflict) { /* nope, check all the groups */
3156  for(j=0; j<nr; j++)
3157  r[j].already=0;
3158 
3159  for(i=0, grp=0; i<egp[NSTEMGRP-1]; i++) {
3160  if(i == egp[grp]) { /* checked all stems in a group */
3161  if(conflict) {
3162  grp++; conflict=0; /* check the next group */
3163  for(j=0; j<nr; j++)
3164  r[j].already=0;
3165  } else
3166  break; /* insert into this group */
3167  }
3168 
3169  lb=s[i].low; hb=s[i].high; isvert=s[i].isvert;
3170  for(j=0; j<nr; j++)
3171  if( r[j].isvert==isvert /* intersects */
3172  && r[j].low <= hb && r[j].high >= lb ) {
3173  if( r[j].low == lb && r[j].high == hb ) /* coincides */
3174  r[j].already=1;
3175  else
3176  conflict=1;
3177  }
3178 
3179  if(conflict)
3180  i=egp[grp]-1; /* fast forward to the next group */
3181  }
3182  }
3183 
3184  /* do we have any empty group ? */
3185  if(conflict && grp < NSTEMGRP-1) {
3186  grp++; conflict=0;
3187  for(j=0; j<nr; j++)
3188  r[j].already=0;
3189  }
3190 
3191  if(conflict) { /* oops, can't find any group to fit */
3192  return 1;
3193  }
3194 
3195  /* OK, add stems to this group */
3196 
3197  rexpand = nr;
3198  for(j=0; j<nr; j++)
3199  rexpand -= r[j].already;
3200 
3201  if(rexpand > 0) {
3202  for(i=egp[NSTEMGRP-1]-1; i>=egp[grp]; i--)
3203  s[i+rexpand]=s[i];
3204  for(i=0; i<nr; i++)
3205  if(!r[i].already)
3206  s[egp[grp]++]=r[i];
3207  for(i=grp+1; i<NSTEMGRP; i++)
3208  egp[i]+=rexpand;
3209  }
3210 
3211  ge->stemid = gssentry_lastgrp = grp;
3212  return 0;
3213 }
3214 
3215 /*
3216  * Create the groups of substituted stems from the list.
3217  * Each group will be represented by a subroutine in the Subs
3218  * array.
3219  */
3220 
3221 static void
3223  GLYPH *g,
3224  STEM *hs, /* horizontal stems, sorted by value */
3225  short *hpairs,
3226  int nhs,
3227  STEM *vs, /* vertical stems, sorted by value */
3228  short *vpairs,
3229  int nvs
3230 )
3231 {
3232  GENTRY *ge;
3233  int i, j;
3234 
3235  /* temporary storage */
3236  STEMBOUNDS s[MAX_STEMS*2];
3237  /* indexes in there, pointing past the end each stem group */
3238  short egp[NSTEMGRP];
3239 
3240  int nextvsi, nexthsi; /* -2 means "check by yourself" */
3241 
3242  for(i=0; i<NSTEMGRP; i++)
3243  egp[i]=0;
3244 
3245  nextvsi=nexthsi= -2; /* processed no horiz/vert line */
3246 
3247  gssentry_lastgrp = 0; /* reset the last group for new glyph */
3248 
3249  for (ge = g->entries; ge != 0; ge = ge->next) {
3250  if(ge->type!=GE_LINE && ge->type!=GE_CURVE) {
3251  nextvsi=nexthsi= -2; /* next path is independent */
3252  continue;
3253  }
3254 
3255  if( gssentry(ge, hs, hpairs, nhs, vs, vpairs, nvs, s, egp, &nextvsi, &nexthsi) ) {
3256  WARNING_2 fprintf(stderr, "*** glyph %s requires over %d hint subroutines, ignored them\n",
3257  g->name, NSTEMGRP);
3258  /* it's better to have no substituted hints at all than have only part */
3259  for (ge = g->entries; ge != 0; ge = ge->next)
3260  ge->stemid= -1;
3261  g->nsg=0; /* just to be safe, already is 0 by initialization */
3262  return;
3263  }
3264 
3265  /*
3266  * handle the last vert/horiz line of the path specially,
3267  * correct the hint for the first entry of the path
3268  */
3269  if(ge->frwd != ge->next && (nextvsi != -2 || nexthsi != -2) ) {
3270  if( gssentry(ge->frwd, hs, hpairs, nhs, vs, vpairs, nvs, s, egp, &nextvsi, &nexthsi) ) {
3271  WARNING_2 fprintf(stderr, "*** glyph %s requires over %d hint subroutines, ignored them\n",
3272  g->name, NSTEMGRP);
3273  /* it's better to have no substituted hints at all than have only part */
3274  for (ge = g->entries; ge != 0; ge = ge->next)
3275  ge->stemid= -1;
3276  g->nsg=0; /* just to be safe, already is 0 by initialization */
3277  return;
3278  }
3279  }
3280 
3281  }
3282 
3283  /* find the index of the first empty group - same as the number of groups */
3284  if(egp[0]>0) {
3285  for(i=1; i<NSTEMGRP && egp[i]!=egp[i-1]; i++)
3286  {}
3287  g->nsg=i;
3288  } else
3289  g->nsg=0;
3290 
3291  if(ISDBG(SUBSTEMS)) {
3292  fprintf(pfa_file, "%% %d substem groups (%d %d %d)\n", g->nsg,
3293  g->nsg>1 ? egp[g->nsg-2] : -1,
3294  g->nsg>0 ? egp[g->nsg-1] : -1,
3295  g->nsg<NSTEMGRP ? egp[g->nsg] : -1 );
3296  j=0;
3297  for(i=0; i<g->nsg; i++) {
3298  fprintf(pfa_file, "%% grp %3d: ", i);
3299  for(; j<egp[i]; j++) {
3300  fprintf(pfa_file, " %4d...%-4d %c ", s[j].low, s[j].high,
3301  s[j].isvert ? 'v' : 'h');
3302  }
3303  fprintf(pfa_file, "\n");
3304  }
3305  }
3306 
3307  if(g->nsg==1) { /* it would be the same as the main stems */
3308  /* so erase it */
3309  for (ge = g->entries; ge != 0; ge = ge->next)
3310  ge->stemid= -1;
3311  g->nsg=0;
3312  }
3313 
3314  if(g->nsg>0) {
3315  if( (g->nsbs=malloc(g->nsg * sizeof (egp[0]))) == 0 ) {
3316  fprintf(stderr, "**** not enough memory for substituted hints ****\n");
3317  exit(255);
3318  }
3319  memmove(g->nsbs, egp, g->nsg * sizeof(short));
3320  if( (g->sbstems=malloc(egp[g->nsg-1] * sizeof (s[0]))) == 0 ) {
3321  fprintf(stderr, "**** not enough memory for substituted hints ****\n");
3322  exit(255);
3323  }
3324  memmove(g->sbstems, s, egp[g->nsg-1] * sizeof(s[0]));
3325  }
3326 }
3327 
3328 void
3330  GLYPH * g
3331 )
3332 {
3333  STEM hs[MAX_STEMS], vs[MAX_STEMS]; /* temporary working
3334  * storage */
3335  short hs_pairs[MAX_STEMS], vs_pairs[MAX_STEMS]; /* best pairs for these stems */
3336  STEM *sp;
3337  GENTRY *ge, *nge, *pge;
3338  int nx, ny;
3339  int ovalue;
3340  int totals, grp, lastgrp;
3341 
3342  assertisint(g, "buildstems int");
3343 
3344  g->nhs = g->nvs = 0;
3345  memset(hs, 0, sizeof hs);
3346  memset(vs, 0, sizeof vs);
3347 
3348  /* first search the whole character for possible stem points */
3349 
3350  for (ge = g->entries; ge != 0; ge = ge->next) {
3351  if (ge->type == GE_CURVE) {
3352 
3353  /*
3354  * SURPRISE!
3355  * We consider the stems bound by the
3356  * H/V ends of the curves as flat ones.
3357  *
3358  * But we don't include the point on the
3359  * other end into the range.
3360  */
3361 
3362  /* first check the beginning of curve */
3363  /* if it is horizontal, add a hstem */
3364  if (ge->iy1 == ge->prev->iy3) {
3365  hs[g->nhs].value = ge->iy1;
3366 
3367  if (ge->ix1 < ge->prev->ix3)
3368  hs[g->nhs].flags = ST_FLAT | ST_UP;
3369  else
3370  hs[g->nhs].flags = ST_FLAT;
3371 
3372  hs[g->nhs].origin = ge->prev->ix3;
3373  hs[g->nhs].ge = ge;
3374 
3375  if (ge->ix1 < ge->prev->ix3) {
3376  hs[g->nhs].from = ge->ix1+1;
3377  hs[g->nhs].to = ge->prev->ix3;
3378  if(hs[g->nhs].from > hs[g->nhs].to)
3379  hs[g->nhs].from--;
3380  } else {
3381  hs[g->nhs].from = ge->prev->ix3;
3382  hs[g->nhs].to = ge->ix1-1;
3383  if(hs[g->nhs].from > hs[g->nhs].to)
3384  hs[g->nhs].to++;
3385  }
3386  if (ge->ix1 != ge->prev->ix3)
3387  g->nhs++;
3388  }
3389  /* if it is vertical, add a vstem */
3390  else if (ge->ix1 == ge->prev->ix3) {
3391  vs[g->nvs].value = ge->ix1;
3392 
3393  if (ge->iy1 > ge->prev->iy3)
3394  vs[g->nvs].flags = ST_FLAT | ST_UP;
3395  else
3396  vs[g->nvs].flags = ST_FLAT;
3397 
3398  vs[g->nvs].origin = ge->prev->iy3;
3399  vs[g->nvs].ge = ge;
3400 
3401  if (ge->iy1 < ge->prev->iy3) {
3402  vs[g->nvs].from = ge->iy1+1;
3403  vs[g->nvs].to = ge->prev->iy3;
3404  if(vs[g->nvs].from > vs[g->nvs].to)
3405  vs[g->nvs].from--;
3406  } else {
3407  vs[g->nvs].from = ge->prev->iy3;
3408  vs[g->nvs].to = ge->iy1-1;
3409  if(vs[g->nvs].from > vs[g->nvs].to)
3410  vs[g->nvs].to++;
3411  }
3412 
3413  if (ge->iy1 != ge->prev->iy3)
3414  g->nvs++;
3415  }
3416  /* then check the end of curve */
3417  /* if it is horizontal, add a hstem */
3418  if (ge->iy3 == ge->iy2) {
3419  hs[g->nhs].value = ge->iy3;
3420 
3421  if (ge->ix3 < ge->ix2)
3422  hs[g->nhs].flags = ST_FLAT | ST_UP;
3423  else
3424  hs[g->nhs].flags = ST_FLAT;
3425 
3426  hs[g->nhs].origin = ge->ix3;
3427  hs[g->nhs].ge = ge->frwd;
3428 
3429  if (ge->ix3 < ge->ix2) {
3430  hs[g->nhs].from = ge->ix3;
3431  hs[g->nhs].to = ge->ix2-1;
3432  if( hs[g->nhs].from > hs[g->nhs].to )
3433  hs[g->nhs].to++;
3434  } else {
3435  hs[g->nhs].from = ge->ix2+1;
3436  hs[g->nhs].to = ge->ix3;
3437  if( hs[g->nhs].from > hs[g->nhs].to )
3438  hs[g->nhs].from--;
3439  }
3440 
3441  if (ge->ix3 != ge->ix2)
3442  g->nhs++;
3443  }
3444  /* if it is vertical, add a vstem */
3445  else if (ge->ix3 == ge->ix2) {
3446  vs[g->nvs].value = ge->ix3;
3447 
3448  if (ge->iy3 > ge->iy2)
3449  vs[g->nvs].flags = ST_FLAT | ST_UP;
3450  else
3451  vs[g->nvs].flags = ST_FLAT;
3452 
3453  vs[g->nvs].origin = ge->iy3;
3454  vs[g->nvs].ge = ge->frwd;
3455 
3456  if (ge->iy3 < ge->iy2) {
3457  vs[g->nvs].from = ge->iy3;
3458  vs[g->nvs].to = ge->iy2-1;
3459  if( vs[g->nvs].from > vs[g->nvs].to )
3460  vs[g->nvs].to++;
3461  } else {
3462  vs[g->nvs].from = ge->iy2+1;
3463  vs[g->nvs].to = ge->iy3;
3464  if( vs[g->nvs].from > vs[g->nvs].to )
3465  vs[g->nvs].from--;
3466  }
3467 
3468  if (ge->iy3 != ge->iy2)
3469  g->nvs++;
3470  } else {
3471 
3472  /*
3473  * check the end of curve for a not smooth
3474  * local extremum
3475  */
3476  nge = ge->frwd;
3477 
3478  if (nge == 0)
3479  continue;
3480  else if (nge->type == GE_LINE) {
3481  nx = nge->ix3;
3482  ny = nge->iy3;
3483  } else if (nge->type == GE_CURVE) {
3484  nx = nge->ix1;
3485  ny = nge->iy1;
3486  } else
3487  continue;
3488 
3489  /* check for vertical extremums */
3490  if (ge->iy3 > ge->iy2 && ge->iy3 > ny
3491  || ge->iy3 < ge->iy2 && ge->iy3 < ny) {
3492  hs[g->nhs].value = ge->iy3;
3493  hs[g->nhs].from
3494  = hs[g->nhs].to
3495  = hs[g->nhs].origin = ge->ix3;
3496  hs[g->nhs].ge = ge->frwd;
3497 
3498  if (ge->ix3 < ge->ix2
3499  || nx < ge->ix3)
3500  hs[g->nhs].flags = ST_UP;
3501  else
3502  hs[g->nhs].flags = 0;
3503 
3504  if (ge->ix3 != ge->ix2 || nx != ge->ix3)
3505  g->nhs++;
3506  }
3507  /*
3508  * the same point may be both horizontal and
3509  * vertical extremum
3510  */
3511  /* check for horizontal extremums */
3512  if (ge->ix3 > ge->ix2 && ge->ix3 > nx
3513  || ge->ix3 < ge->ix2 && ge->ix3 < nx) {
3514  vs[g->nvs].value = ge->ix3;
3515  vs[g->nvs].from
3516  = vs[g->nvs].to
3517  = vs[g->nvs].origin = ge->iy3;
3518  vs[g->nvs].ge = ge->frwd;
3519 
3520  if (ge->iy3 > ge->iy2
3521  || ny > ge->iy3)
3522  vs[g->nvs].flags = ST_UP;
3523  else
3524  vs[g->nvs].flags = 0;
3525 
3526  if (ge->iy3 != ge->iy2 || ny != ge->iy3)
3527  g->nvs++;
3528  }
3529  }
3530 
3531  } else if (ge->type == GE_LINE) {
3532  nge = ge->frwd;
3533 
3534  /* if it is horizontal, add a hstem */
3535  /* and the ends as vstems if they brace the line */
3536  if (ge->iy3 == ge->prev->iy3
3537  && ge->ix3 != ge->prev->ix3) {
3538  hs[g->nhs].value = ge->iy3;
3539  if (ge->ix3 < ge->prev->ix3) {
3540  hs[g->nhs].flags = ST_FLAT | ST_UP;
3541  hs[g->nhs].from = ge->ix3;
3542  hs[g->nhs].to = ge->prev->ix3;
3543  } else {
3544  hs[g->nhs].flags = ST_FLAT;
3545  hs[g->nhs].from = ge->prev->ix3;
3546  hs[g->nhs].to = ge->ix3;
3547  }
3548  hs[g->nhs].origin = ge->ix3;
3549  hs[g->nhs].ge = ge->frwd;
3550 
3551  pge = ge->bkwd;
3552 
3553  /* add beginning as vstem */
3554  vs[g->nvs].value = pge->ix3;
3555  vs[g->nvs].origin
3556  = vs[g->nvs].from
3557  = vs[g->nvs].to = pge->iy3;
3558  vs[g->nvs].ge = ge;
3559 
3560  if(pge->type==GE_CURVE)
3561  ovalue=pge->iy2;
3562  else
3563  ovalue=pge->prev->iy3;
3564 
3565  if (pge->iy3 > ovalue)
3566  vs[g->nvs].flags = ST_UP | ST_END;
3567  else if (pge->iy3 < ovalue)
3568  vs[g->nvs].flags = ST_END;
3569  else
3570  vs[g->nvs].flags = 0;
3571 
3572  if( vs[g->nvs].flags != 0 )
3573  g->nvs++;
3574 
3575  /* add end as vstem */
3576  vs[g->nvs].value = ge->ix3;
3577  vs[g->nvs].origin
3578  = vs[g->nvs].from
3579  = vs[g->nvs].to = ge->iy3;
3580  vs[g->nvs].ge = ge->frwd;
3581 
3582  if(nge->type==GE_CURVE)
3583  ovalue=nge->iy1;
3584  else
3585  ovalue=nge->iy3;
3586 
3587  if (ovalue > ge->iy3)
3588  vs[g->nvs].flags = ST_UP | ST_END;
3589  else if (ovalue < ge->iy3)
3590  vs[g->nvs].flags = ST_END;
3591  else
3592  vs[g->nvs].flags = 0;
3593 
3594  if( vs[g->nvs].flags != 0 )
3595  g->nvs++;
3596 
3597  g->nhs++;
3598  }
3599  /* if it is vertical, add a vstem */
3600  /* and the ends as hstems if they brace the line */
3601  else if (ge->ix3 == ge->prev->ix3
3602  && ge->iy3 != ge->prev->iy3) {
3603  vs[g->nvs].value = ge->ix3;
3604  if (ge->iy3 > ge->prev->iy3) {
3605  vs[g->nvs].flags = ST_FLAT | ST_UP;
3606  vs[g->nvs].from = ge->prev->iy3;
3607  vs[g->nvs].to = ge->iy3;
3608  } else {
3609  vs[g->nvs].flags = ST_FLAT;
3610  vs[g->nvs].from = ge->iy3;
3611  vs[g->nvs].to = ge->prev->iy3;
3612  }
3613  vs[g->nvs].origin = ge->iy3;
3614  vs[g->nvs].ge = ge->frwd;
3615 
3616  pge = ge->bkwd;
3617 
3618  /* add beginning as hstem */
3619  hs[g->nhs].value = pge->iy3;
3620  hs[g->nhs].origin
3621  = hs[g->nhs].from
3622  = hs[g->nhs].to = pge->ix3;
3623  hs[g->nhs].ge = ge;
3624 
3625  if(pge->type==GE_CURVE)
3626  ovalue=pge->ix2;
3627  else
3628  ovalue=pge->prev->ix3;
3629 
3630  if (pge->ix3 < ovalue)
3631  hs[g->nhs].flags = ST_UP | ST_END;
3632  else if (pge->ix3 > ovalue)
3633  hs[g->nhs].flags = ST_END;
3634  else
3635  hs[g->nhs].flags = 0;
3636 
3637  if( hs[g->nhs].flags != 0 )
3638  g->nhs++;
3639 
3640  /* add end as hstem */
3641  hs[g->nhs].value = ge->iy3;
3642  hs[g->nhs].origin
3643  = hs[g->nhs].from
3644  = hs[g->nhs].to = ge->ix3;
3645  hs[g->nhs].ge = ge->frwd;
3646 
3647  if(nge->type==GE_CURVE)
3648  ovalue=nge->ix1;
3649  else
3650  ovalue=nge->ix3;
3651 
3652  if (ovalue < ge->ix3)
3653  hs[g->nhs].flags = ST_UP | ST_END;
3654  else if (ovalue > ge->ix3)
3655  hs[g->nhs].flags = ST_END;
3656  else
3657  hs[g->nhs].flags = 0;
3658 
3659  if( hs[g->nhs].flags != 0 )
3660  g->nhs++;
3661 
3662  g->nvs++;
3663  }
3664  /*
3665  * check the end of line for a not smooth local
3666  * extremum
3667  */
3668  nge = ge->frwd;
3669 
3670  if (nge == 0)
3671  continue;
3672  else if (nge->type == GE_LINE) {
3673  nx = nge->ix3;
3674  ny = nge->iy3;
3675  } else if (nge->type == GE_CURVE) {
3676  nx = nge->ix1;
3677  ny = nge->iy1;
3678  } else
3679  continue;
3680 
3681  /* check for vertical extremums */
3682  if (ge->iy3 > ge->prev->iy3 && ge->iy3 > ny
3683  || ge->iy3 < ge->prev->iy3 && ge->iy3 < ny) {
3684  hs[g->nhs].value = ge->iy3;
3685  hs[g->nhs].from
3686  = hs[g->nhs].to
3687  = hs[g->nhs].origin = ge->ix3;
3688  hs[g->nhs].ge = ge->frwd;
3689 
3690  if (ge->ix3 < ge->prev->ix3
3691  || nx < ge->ix3)
3692  hs[g->nhs].flags = ST_UP;
3693  else
3694  hs[g->nhs].flags = 0;
3695 
3696  if (ge->ix3 != ge->prev->ix3 || nx != ge->ix3)
3697  g->nhs++;
3698  }
3699  /*
3700  * the same point may be both horizontal and vertical
3701  * extremum
3702  */
3703  /* check for horizontal extremums */
3704  if (ge->ix3 > ge->prev->ix3 && ge->ix3 > nx
3705  || ge->ix3 < ge->prev->ix3 && ge->ix3 < nx) {
3706  vs[g->nvs].value = ge->ix3;
3707  vs[g->nvs].from
3708  = vs[g->nvs].to
3709  = vs[g->nvs].origin = ge->iy3;
3710  vs[g->nvs].ge = ge->frwd;
3711 
3712  if (ge->iy3 > ge->prev->iy3
3713  || ny > ge->iy3)
3714  vs[g->nvs].flags = ST_UP;
3715  else
3716  vs[g->nvs].flags = 0;
3717 
3718  if (ge->iy3 != ge->prev->iy3 || ny != ge->iy3)
3719  g->nvs++;
3720  }
3721  }
3722  }
3723 
3724  g->nhs=addbluestems(hs, g->nhs);
3725  sortstems(hs, g->nhs);
3726  sortstems(vs, g->nvs);
3727 
3728  if (ISDBG(STEMS))
3729  debugstems(g->name, hs, g->nhs, vs, g->nvs);
3730 
3731  /* find the stems interacting with the Blue Zones */
3732  markbluestems(hs, g->nhs);
3733 
3734  if(subhints) {
3735  if (ISDBG(SUBSTEMS))
3736  fprintf(pfa_file, "%% %s: joining subst horizontal stems\n", g->name);
3737  joinsubstems(hs, hs_pairs, g->nhs, 1);
3738  uniformstems(hs, hs_pairs, g->nhs);
3739 
3740  if (ISDBG(SUBSTEMS))
3741  fprintf(pfa_file, "%% %s: joining subst vertical stems\n", g->name);
3742  joinsubstems(vs, vs_pairs, g->nvs, 0);
3743 
3744  groupsubstems(g, hs, hs_pairs, g->nhs, vs, vs_pairs, g->nvs);
3745  }
3746 
3747  if (ISDBG(MAINSTEMS))
3748  fprintf(pfa_file, "%% %s: joining main horizontal stems\n", g->name);
3749  g->nhs = joinmainstems(hs, g->nhs, 1);
3750  if (ISDBG(MAINSTEMS))
3751  fprintf(pfa_file, "%% %s: joining main vertical stems\n", g->name);
3752  g->nvs = joinmainstems(vs, g->nvs, 0);
3753 
3754  if (ISDBG(MAINSTEMS))
3755  debugstems(g->name, hs, g->nhs, vs, g->nvs);
3756 
3757  if(g->nhs > 0) {
3758  if ((sp = malloc(sizeof(STEM) * g->nhs)) == 0) {
3759  fprintf(stderr, "**** not enough memory for hints ****\n");
3760  exit(255);
3761  }
3762  g->hstems = sp;
3763  memcpy(sp, hs, sizeof(STEM) * g->nhs);
3764  } else
3765  g->hstems = 0;
3766 
3767  if(g->nvs > 0) {
3768  if ((sp = malloc(sizeof(STEM) * g->nvs)) == 0) {
3769  fprintf(stderr, "**** not enough memory for hints ****\n");
3770  exit(255);
3771  }
3772  g->vstems = sp;
3773  memcpy(sp, vs, sizeof(STEM) * g->nvs);
3774  } else
3775  g->vstems = 0;
3776 
3777  /* now check that the stems won't overflow the interpreter's stem stack:
3778  * some interpreters (like X11) push the stems on each change into
3779  * stack and pop them only after the whole glyphs is completed.
3780  */
3781 
3782  totals = (g->nhs+g->nvs) / 2; /* we count whole stems, not halves */
3783  lastgrp = -1;
3784 
3785  for (ge = g->entries; ge != 0; ge = ge->next) {
3786  grp=ge->stemid;
3787  if(grp >= 0 && grp != lastgrp) {
3788  if(grp==0)
3789  totals += g->nsbs[0];
3790  else
3791  totals += g->nsbs[grp] - g->nsbs[grp-1];
3792 
3793  lastgrp = grp;
3794  }
3795  }
3796 
3797  /* be on the safe side, check for >= , not > */
3798  if(totals >= max_stemdepth) { /* oops, too deep */
3799  WARNING_2 {
3800  fprintf(stderr, "Warning: glyph %s needs hint stack depth %d\n", g->name, totals);
3801  fprintf(stderr, " (limit %d): removed the substituted hints from it\n", max_stemdepth);
3802  }
3803  if(g->nsg > 0) {
3804  for (ge = g->entries; ge != 0; ge = ge->next)
3805  ge->stemid = -1;
3806  free(g->sbstems); g->sbstems = 0;
3807  free(g->nsbs); g->nsbs = 0;
3808  g->nsg = 0;
3809  }
3810  }
3811 
3812  /* now check if there are too many main stems */
3813  totals = (g->nhs+g->nvs) / 2; /* we count whole stems, not halves */
3814  if(totals >= max_stemdepth) {
3815  /* even worse, too much of non-substituted stems */
3816  WARNING_2 {
3817  fprintf(stderr, "Warning: glyph %s has %d main hints\n", g->name, totals);
3818  fprintf(stderr, " (limit %d): removed the hints from it\n", max_stemdepth);
3819  }
3820  if(g->vstems) {
3821  free(g->vstems); g->vstems = 0; g->nvs = 0;
3822  }
3823  if(g->hstems) {
3824  free(g->hstems); g->hstems = 0; g->nhs = 0;
3825  }
3826  }
3827 }
3828 
3829 /* convert weird curves that are close to lines into lines.
3830 */
3831 
3832 void
3834  GLYPH * g
3835 )
3836 {
3837  GENTRY *ge, *pge, *nge, *ige;
3838  double df;
3839  int dir;
3840  double iln, oln;
3841  int i, o;
3842 
3843  for (ige = g->entries; ige != 0; ige = ige->next) {
3844  if (ige->type != GE_CURVE)
3845  continue;
3846 
3847  ge = ige;
3848  pge = ge->bkwd;
3849  nge = ge->frwd;
3850 
3851  df = 0.;
3852 
3853  /* look for vertical then horizontal */
3854  for(i=0; i<2; i++) {
3855  o = !i; /* other axis */
3856 
3857  iln = fabs(ge->fpoints[i][2] - pge->fpoints[i][2]);
3858  oln = fabs(ge->fpoints[o][2] - pge->fpoints[o][2]);
3859  /*
3860  * if current curve is almost a vertical line, and it
3861  * doesn't begin or end horizontally (and the prev/next
3862  * line doesn't join smoothly ?)
3863  */
3864  if( oln < 1.
3865  || ge->fpoints[o][2] == ge->fpoints[o][1]
3866  || ge->fpoints[o][0] == pge->fpoints[o][2]
3867  || iln > 2.
3868  || iln > 1. && iln/oln > 0.1 )
3869  continue;
3870 
3871 
3872  if(ISDBG(STRAIGHTEN))
3873  fprintf(stderr,"** straighten almost %s\n", (i? "horizontal":"vertical"));
3874 
3875  df = ge->fpoints[i][2] - pge->fpoints[i][2];
3876  dir = fsign(ge->fpoints[o][2] - pge->fpoints[o][2]);
3877  ge->type = GE_LINE;
3878 
3879  /*
3880  * suck in all the sequence of such almost lines
3881  * going in the same direction but not deviating
3882  * too far from vertical
3883  */
3884  iln = fabs(nge->fpoints[i][2] - ge->fpoints[i][2]);
3885  oln = nge->fpoints[o][2] - ge->fpoints[o][2];
3886 
3887  while (fabs(df) <= 5 && nge->type == GE_CURVE
3888  && dir == fsign(oln) /* that also gives oln != 0 */
3889  && iln <= 2.
3890  && ( iln <= 1. || iln/fabs(oln) <= 0.1 ) ) {
3891  ge->fx3 = nge->fx3;
3892  ge->fy3 = nge->fy3;
3893 
3894  if(ISDBG(STRAIGHTEN))
3895  fprintf(stderr,"** straighten collapsing %s\n", (i? "horizontal":"vertical"));
3896  freethisge(nge);
3897  fixendpath(ge);
3898  pge = ge->bkwd;
3899  nge = ge->frwd;
3900 
3901  df = ge->fpoints[i][2] - pge->fpoints[i][2];
3902 
3903  iln = fabs(nge->fpoints[i][2] - ge->fpoints[i][2]);
3904  oln = nge->fpoints[o][2] - ge->fpoints[o][2];
3905  }
3906 
3907  /* now check what do we have as previous/next line */
3908 
3909  if(ge != pge) {
3910  if( pge->type == GE_LINE && pge->fpoints[i][2] == pge->prev->fpoints[i][2]
3911  && fabs(pge->fpoints[o][2] != pge->prev->fpoints[o][2]) ) {
3912  if(ISDBG(STRAIGHTEN)) fprintf(stderr,"** straighten join with previous 0x%zx 0x%zx\n", (size_t)pge, (size_t)ge);
3913  /* join the previous line with current */
3914  pge->fx3 = ge->fx3;
3915  pge->fy3 = ge->fy3;
3916 
3917  ige = freethisge(ge)->prev; /* keep the iterator valid */
3918  ge = pge;
3919  fixendpath(ge);
3920  pge = ge->bkwd;
3921  }
3922  }
3923 
3924  if(ge != nge) {
3925  if (nge->type == GE_LINE && nge->fpoints[i][2] == ge->fpoints[i][2]
3926  && fabs(nge->fpoints[o][2] != ge->fpoints[o][2]) ) {
3927  if(ISDBG(STRAIGHTEN)) fprintf(stderr,"** straighten join with next 0x%zx 0x%zx\n", (size_t)ge, (size_t)nge);
3928  /* join the next line with current */
3929  ge->fx3 = nge->fx3;
3930  ge->fy3 = nge->fy3;
3931 
3932  freethisge(nge);
3933  fixendpath(ge);
3934  pge = ge->bkwd;
3935  nge = ge->frwd;
3936 
3937  }
3938  }
3939 
3940  if(ge != pge) {
3941  /* try to align the lines if neccessary */
3942  if(df != 0.)
3943  fclosegap(ge, ge, i, df, NULL);
3944  } else {
3945  /* contour consists of only one line, get rid of it */
3946  ige = freethisge(ge); /* keep the iterator valid */
3947  if(ige == 0) /* this was the last contour */
3948  return;
3949  ige = ige->prev;
3950  }
3951 
3952  break; /* don't bother looking at the other axis */
3953  }
3954  }
3955 }
3956 
3957 /* solve a square equation,
3958  * returns the number of solutions found, the solutions
3959  * are stored in res which should point to array of two doubles.
3960  * min and max limit the area for solutions
3961  */
3962 
3963 static int
3965  double a,
3966  double b,
3967  double c,
3968  double *res,
3969  double min,
3970  double max
3971 )
3972 {
3973  double D;
3974  int n;
3975 
3976  if(ISDBG(SQEQ)) fprintf(stderr, "sqeq(%g,%g,%g) [%g;%g]\n", a, b, c, min, max);
3977 
3978  if(fabs(a) < 0.000001) { /* if a linear equation */
3979  n=0;
3980  if(fabs(b) < 0.000001) /* not an equation at all */
3981  return 0;
3982  res[0] = -c/b;
3983  if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: linear t=%g\n", res[0]);
3984  if(res[0] >= min && res[0] <= max)
3985  n++;
3986  return n;
3987  }
3988 
3989  D = b*b - 4.0*a*c;
3990  if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: D=%g\n", D);
3991  if(D<0)
3992  return 0;
3993 
3994  D = sqrt(D);
3995 
3996  n=0;
3997  res[0] = (-b+D) / (2*a);
3998  if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: t1=%g\n", res[0]);
3999  if(res[0] >= min && res[0] <= max)
4000  n++;
4001 
4002  res[n] = (-b-D) / (2*a);
4003  if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: t2=%g\n", res[n]);
4004  if(res[n] >= min && res[n] <= max)
4005  n++;
4006 
4007  /* return 2nd solution only if it's different enough */
4008  if(n==2 && fabs(res[0]-res[1])<0.000001)
4009  n=1;
4010 
4011  return n;
4012 }
4013 
4014 /* check that the curves don't cross quadrant boundary */
4015 /* (float) */
4016 
4017 /*
4018  Here we make sure that the curve does not continue past
4019  horizontal or vertical extremums. The horizontal points are
4020  explained, vertical points are by analogy.
4021 
4022  The horizontal points are where the derivative
4023  dy/dx is equal to 0. But the Bezier curves are defined by
4024  parametric formulas
4025  x=fx(t)
4026  y=fy(t)
4027  so finding this derivative is complicated.
4028  Also even if we find some point (x,y) splitting at this point
4029  is far not obvious. Fortunately we can use dy/dt = 0 instead,
4030  this gets to a rather simple square equation and splitting
4031  at a known value of t is simple.
4032 
4033  The formulas are:
4034 
4035  y = A*(1-t)^3 + 3*B*(1-t)^2*t + 3*C*(1-t)*t^2 + D*t^3
4036  y = (-A+3*B-3*C+D)*t^3 + (3*A-6*B+3*C)*t^2 + (-3*A+3*B)*t + A
4037  dy/dt = 3*(-A+3*B-3*C+D)*t^2 + 2*(3*A-6*B+3*C)*t + (-3*A+3*B)
4038  */
4039 
4040 void
4042  GLYPH *g
4043 )
4044 {
4045  GENTRY *ge, *nge;
4046  int i, j, np, oldnp;
4047  double sp[5]; /* split points, last one empty */
4048  char dir[5]; /* for debugging, direction by which split happened */
4049  double a, b, *pts; /* points of a curve */
4050 
4051  for (ge = g->entries; ge != 0; ge = ge->next) {
4052  if (ge->type != GE_CURVE)
4053  continue;
4054 
4055  doagain:
4056  np = 0; /* no split points yet */
4057  if(ISDBG(QUAD)) {
4058  fprintf(stderr, "%s: trying 0x%zx (%g %g) (%g %g) (%g %g) (%g %g)\n ", g->name,
4059  (size_t)ge, ge->prev->fx3, ge->prev->fy3, ge->fx1, ge->fy1, ge->fx2, ge->fy2,
4060  ge->fx3, ge->fy3);
4061  }
4062  for(i=0; i<2; i++) { /* first for x then for y */
4063  /* find the cooridnates of control points */
4064  a = ge->prev->fpoints[i][2];
4065  pts = &ge->fpoints[i][0];
4066 
4067  oldnp = np;
4068  np += fsqequation(
4069  3.0*(-a + 3.0*pts[0] - 3.0*pts[1] + pts[2]),
4070  6.0*(a - 2.0*pts[0] + pts[1]),
4071  3.0*(-a + pts[0]),
4072  &sp[np],
4073  0.0, 1.0); /* XXX range is [0;1] */
4074 
4075  if(np == oldnp)
4076  continue;
4077 
4078  if(ISDBG(QUAD))
4079  fprintf(stderr, "%s: 0x%zx: %d pts(%c): ",
4080  g->name, (size_t)ge, np-oldnp, i? 'y':'x');
4081 
4082  /* remove points that are too close to the ends
4083  * because hor/vert ends are permitted, also
4084  * if the split point is VERY close to the ends
4085  * but not exactly then just flatten it and check again.
4086  */
4087  for(j = oldnp; j<np; j++) {
4088  dir[j] = i;
4089  if(ISDBG(QUAD))
4090  fprintf(stderr, "%g ", sp[j]);
4091  if(sp[j] < 0.03) { /* front end of curve */
4092  if(ge->fpoints[i][0] != ge->prev->fpoints[i][2]) {
4093  ge->fpoints[i][0] = ge->prev->fpoints[i][2];
4094  if(ISDBG(QUAD)) fprintf(stderr, "flattened at front\n");
4095  goto doagain;
4096  }
4097  if( ge->fpoints[i][1] != ge->fpoints[i][0]
4098  && fsign(ge->fpoints[i][2] - ge->fpoints[i][1])
4099  != fsign(ge->fpoints[i][1] - ge->fpoints[i][0]) ) {
4100  ge->fpoints[i][1] = ge->fpoints[i][0];
4101  if(ISDBG(QUAD)) fprintf(stderr, "flattened zigzag at front\n");
4102  goto doagain;
4103  }
4104  sp[j] = sp[j+1]; np--; j--;
4105  if(ISDBG(QUAD)) fprintf(stderr, "(front flat) ");
4106  } else if(sp[j] > 0.97) { /* rear end of curve */
4107  if(ge->fpoints[i][1] != ge->fpoints[i][2]) {
4108  ge->fpoints[i][1] = ge->fpoints[i][2];
4109  if(ISDBG(QUAD)) fprintf(stderr, "flattened at rear\n");
4110  goto doagain;
4111  }
4112  if( ge->fpoints[i][0] != ge->fpoints[i][1]
4113  && fsign(ge->prev->fpoints[i][2] - ge->fpoints[i][0])
4114  != fsign(ge->fpoints[i][0] - ge->fpoints[i][1]) ) {
4115  ge->fpoints[i][0] = ge->fpoints[i][1];
4116  if(ISDBG(QUAD)) fprintf(stderr, "flattened zigzag at rear\n");
4117  goto doagain;
4118  }
4119  sp[j] = sp[j+1]; np--; j--;
4120  if(ISDBG(QUAD)) fprintf(stderr, "(rear flat) ");
4121  }
4122  }
4123  if(ISDBG(QUAD)) fprintf(stderr, "\n");
4124  }
4125 
4126  if(np==0) /* no split points, leave it alone */
4127  continue;
4128 
4129  if(ISDBG(QUAD)) {
4130  fprintf(stderr, "%s: splitting 0x%zx (%g %g) (%g %g) (%g %g) (%g %g) at %d points\n ", g->name,
4131  (size_t)ge, ge->prev->fx3, ge->prev->fy3, ge->fx1, ge->fy1, ge->fx2, ge->fy2,
4132  ge->fx3, ge->fy3, np);
4133  for(i=0; i<np; i++)
4134  fprintf(stderr, "%g(%c) ", sp[i], dir[i] ? 'y':'x');
4135  fprintf(stderr, "\n");
4136  }
4137 
4138  /* sort the points ascending */
4139  for(i=0; i<np; i++)
4140  for(j=i+1; j<np; j++)
4141  if(sp[i] > sp[j]) {
4142  a = sp[i]; sp[i] = sp[j]; sp[j] = a;
4143  }
4144 
4145  /* now finally do the split on each point */
4146  for(j=0; j<np; j++) {
4147  double k1, k2, c;
4148 
4149  k1 = sp[j];
4150  k2 = 1 - k1;
4151 
4152  if(ISDBG(QUAD)) fprintf(stderr, " 0x%zx %g/%g\n", (size_t)ge, k1, k2);
4153 
4154  nge = newgentry(GEF_FLOAT);
4155  (*nge) = (*ge);
4156 
4157 #define SPLIT(pt1, pt2) ( (pt1) + k1*((pt2)-(pt1)) ) /* order is important! */
4158  for(i=0; i<2; i++) { /* for x and y */
4159  a = ge->fpoints[i][0]; /* get the middle points */
4160  b = ge->fpoints[i][1];
4161 
4162  /* calculate new internal points */
4163  c = SPLIT(a, b);
4164 
4165  ge->fpoints[i][0] = SPLIT(ge->prev->fpoints[i][2], a);
4166  ge->fpoints[i][1] = SPLIT(ge->fpoints[i][0], c);
4167 
4168  nge->fpoints[i][1] = SPLIT(b, nge->fpoints[i][2]);
4169  nge->fpoints[i][0] = SPLIT(c, nge->fpoints[i][1]);
4170 
4171  ge->fpoints[i][2] = SPLIT(ge->fpoints[i][1],
4172  + nge->fpoints[i][0]);
4173  }
4174 #undef SPLIT
4175 
4176  addgeafter(ge, nge);
4177 
4178  /* go to the next part, adjust remaining points */
4179  ge = nge;
4180  for(i=j+1; i<np; i++)
4181  sp[i] = (sp[i]-k1) / k2;
4182  }
4183  }
4184 
4185 }
4186 
4187 /* check if a curve is a zigzag */
4188 
4189 static int
4191  GENTRY *ge
4192 )
4193 {
4194  double k, k1, k2;
4195  int a, b;
4196 
4197  if (ge->type != GE_CURVE)
4198  return 0;
4199 
4200  a = ge->iy2 - ge->iy1;
4201  b = ge->ix2 - ge->ix1;
4202  if(a == 0) {
4203  if(b == 0) {
4204  return 0;
4205  } else
4206  k = FBIGVAL;
4207  } else
4208  k = fabs((double) b / (double) a);
4209 
4210  a = ge->iy1 - ge->prev->iy3;
4211  b = ge->ix1 - ge->prev->ix3;
4212  if(a == 0) {
4213  if(b == 0) {
4214  return 0;
4215  } else
4216  k1 = FBIGVAL;
4217  } else
4218  k1 = fabs((double) b / (double) a);
4219 
4220  a = ge->iy3 - ge->iy2;
4221  b = ge->ix3 - ge->ix2;
4222  if(a == 0) {
4223  if(b == 0) {
4224  return 0;
4225  } else
4226  k2 = FBIGVAL;
4227  } else
4228  k2 = fabs((double) b / (double) a);
4229 
4230  /* if the curve is not a zigzag */
4231  if (k1+0.0001 >= k && k2 <= k+0.0001 || k1 <= k+0.0001 && k2+0.0001 >= k)
4232  return 0;
4233  else
4234  return 1;
4235 }
4236 
4237 /* check if a curve is a zigzag - floating */
4238 
4239 static int
4241  GENTRY *ge
4242 )
4243 {
4244  double k, k1, k2;
4245  double a, b;
4246 
4247  if (ge->type != GE_CURVE)
4248  return 0;
4249 
4250  a = fabs(ge->fy2 - ge->fy1);
4251  b = fabs(ge->fx2 - ge->fx1);
4252  if(a < FEPS) {
4253  if(b < FEPS) {
4254  return 0;
4255  } else
4256  k = FBIGVAL;
4257  } else
4258  k = b / a;
4259 
4260  a = fabs(ge->fy1 - ge->prev->fy3);
4261  b = fabs(ge->fx1 - ge->prev->fx3);
4262  if(a < FEPS) {
4263  if(b < FEPS) {
4264  return 0;
4265  } else
4266  k1 = FBIGVAL;
4267  } else
4268  k1 = b / a;
4269 
4270  a = fabs(ge->fy3 - ge->fy2);
4271  b = fabs(ge->fx3 - ge->fx2);
4272  if(a < FEPS) {
4273  if(b < FEPS) {
4274  return 0;
4275  } else
4276  k2 = FBIGVAL;
4277  } else
4278  k2 = b / a;
4279 
4280  /* if the curve is not a zigzag */
4281  if (k1+0.0001 >= k && k2 <= k+0.0001 || k1 <= k+0.0001 && k2+0.0001 >= k)
4282  return 0;
4283  else
4284  return 1;
4285 }
4286 
4287 /* split the zigzag-like curves into two parts */
4288 
4289 void
4291  GLYPH * g
4292 )
4293 {
4294  GENTRY *ge, *nge;
4295  double a, b, c, d;
4296 
4297  assertisfloat(g, "splitting zigzags");
4298  for (ge = g->entries; ge != 0; ge = ge->next) {
4299  if (ge->type != GE_CURVE)
4300  continue;
4301 
4302  /* if the curve is not a zigzag */
4303  if ( !fiszigzag(ge) ) {
4304  continue;
4305  }
4306 
4307  if(ISDBG(FCONCISE)) {
4308  double maxsc1, maxsc2;
4309  fprintf(stderr, "split a zigzag ");
4310  fnormalizege(ge);
4311  if( fcrossraysge(ge, ge, &maxsc1, &maxsc2, NULL) ) {
4312  fprintf(stderr, "sc1=%g sc2=%g\n", maxsc1, maxsc2);
4313  } else {
4314  fprintf(stderr, "(rays don't cross)\n");
4315  }
4316  }
4317  /* split the curve by t=0.5 */
4318  nge = newgentry(GEF_FLOAT);
4319  (*nge) = (*ge);
4320  nge->type = GE_CURVE;
4321 
4322  a = ge->prev->fx3;
4323  b = ge->fx1;
4324  c = ge->fx2;
4325  d = ge->fx3;
4326  nge->fx3 = d;
4327  nge->fx2 = (c + d) / 2.;
4328  nge->fx1 = (b + 2. * c + d) / 4.;
4329  ge->fx3 = (a + b * 3. + c * 3. + d) / 8.;
4330  ge->fx2 = (a + 2. * b + c) / 4.;
4331  ge->fx1 = (a + b) / 2.;
4332 
4333  a = ge->prev->fy3;
4334  b = ge->fy1;
4335  c = ge->fy2;
4336  d = ge->fy3;
4337  nge->fy3 = d;
4338  nge->fy2 = (c + d) / 2.;
4339  nge->fy1 = (b + 2. * c + d) / 4.;
4340  ge->fy3 = (a + b * 3. + c * 3. + d) / 8.;
4341  ge->fy2 = (a + 2. * b + c) / 4.;
4342  ge->fy1 = (a + b) / 2.;
4343 
4344  addgeafter(ge, nge);
4345 
4346  if(ISDBG(FCONCISE)) {
4347  dumppaths(g, ge, nge);
4348  }
4349  }
4350 }
4351 
4352 /* free this GENTRY, returns what was ge->next
4353  * (ge must be of type GE_LINE or GE_CURVE)
4354  * works on both float and int entries
4355  */
4356 
4357 static GENTRY *
4359  GENTRY *ge
4360 )
4361 {
4362  GENTRY *xge;
4363 
4364  if (ge->bkwd != ge->prev) {
4365  /* at beginning of the contour */
4366 
4367  xge = ge->bkwd;
4368  if(xge == ge) { /* was the only line in contour */
4369  /* remove the contour completely */
4370  /* prev is GE_MOVE, next is GE_PATH, remove them all */
4371 
4372  /* may be the first contour, then ->bkwd points to ge->entries */
4373  if(ge->prev->prev == 0)
4374  *(GENTRY **)(ge->prev->bkwd) = ge->next->next;
4375  else
4376  ge->prev->prev->next = ge->next->next;
4377 
4378  if(ge->next->next) {
4379  ge->next->next->prev = ge->prev->prev;
4380  ge->next->next->bkwd = ge->prev->bkwd;
4381  }
4382 
4383  xge = ge->next->next;
4384  free(ge->prev); free(ge->next); free(ge);
4385  return xge;
4386  }
4387 
4388  /* move the start point of the contour */
4389  if(ge->flags & GEF_FLOAT) {
4390  ge->prev->fx3 = xge->fx3;
4391  ge->prev->fy3 = xge->fy3;
4392  } else {
4393  ge->prev->ix3 = xge->ix3;
4394  ge->prev->iy3 = xge->iy3;
4395  }
4396  } else if(ge->frwd != ge->next) {
4397  /* at end of the contour */
4398 
4399  xge = ge->frwd->prev;
4400  /* move the start point of the contour */
4401  if(ge->flags & GEF_FLOAT) {
4402  xge->fx3 = ge->bkwd->fx3;
4403  xge->fy3 = ge->bkwd->fy3;
4404  } else {
4405  xge->ix3 = ge->bkwd->ix3;
4406  xge->iy3 = ge->bkwd->iy3;
4407  }
4408  }
4409 
4410  ge->prev->next = ge->next;
4411  ge->next->prev = ge->prev;
4412  ge->bkwd->frwd = ge->frwd;
4413  ge->frwd->bkwd = ge->bkwd;
4414 
4415  xge = ge->next;
4416  free(ge);
4417  return xge;
4418 }
4419 
4420 /* inserts a new gentry (LINE or CURVE) after another (MOVE
4421  * or LINE or CURVE)
4422  * corrects the first GE_MOVE if neccessary
4423  */
4424 
4425 static void
4427  GENTRY *oge, /* after this */
4428  GENTRY *nge /* insert this */
4429 )
4430 {
4431  if(oge->type == GE_MOVE) {
4432  /* insert before next */
4433  if(oge->next->type == GE_PATH) {
4434  /* first and only GENTRY in path */
4435  nge->frwd = nge->bkwd = nge;
4436  } else {
4437  nge->frwd = oge->next;
4438  nge->bkwd = oge->next->bkwd;
4439  oge->next->bkwd->frwd = nge;
4440  oge->next->bkwd = nge;
4441  }
4442  } else {
4443  nge->frwd = oge->frwd;
4444  nge->bkwd = oge;
4445  oge->frwd->bkwd = nge;
4446  oge->frwd = nge;
4447  }
4448 
4449  nge->next = oge->next;
4450  nge->prev = oge;
4451  oge->next->prev = nge;
4452  oge->next = nge;
4453 
4454  if(nge->frwd->prev->type == GE_MOVE) {
4455  /* fix up the GE_MOVE entry */
4456  if(nge->flags & GEF_FLOAT) {
4457  nge->frwd->prev->fx3 = nge->fx3;
4458  nge->frwd->prev->fy3 = nge->fy3;
4459  } else {
4460  nge->frwd->prev->ix3 = nge->ix3;
4461  nge->frwd->prev->iy3 = nge->iy3;
4462  }
4463  }
4464 }
4465 
4466 /*
4467  * Check if this GENTRY happens to be at the end of path
4468  * and fix the first MOVETO accordingly
4469  * handles both int and float
4470  */
4471 
4472 static void
4474  GENTRY *ge
4475 )
4476 {
4477  GENTRY *mge;
4478 
4479  mge = ge->frwd->prev;
4480  if(mge->type == GE_MOVE) {
4481  if(ge->flags & GEF_FLOAT) {
4482  mge->fx3 = ge->fx3;
4483  mge->fy3 = ge->fy3;
4484  } else {
4485  mge->ix3 = ge->ix3;
4486  mge->iy3 = ge->iy3;
4487  }
4488  }
4489 }
4490 
4491 /*
4492  * This function adjusts the rest of path (the part from...to is NOT changed)
4493  * to cover the specified gap by the specified axis (0 - X, 1 - Y).
4494  * Gap is counted in direction (end_of_to - beginning_of_from).
4495  * Returns by how much the gap was not closed (0.0 if it was fully closed).
4496  * Ret contains by how much the first and last points of [from...to]
4497  * were moved to bring them in consistence to the rest of the path.
4498  * If ret==NULL then this info is not returned.
4499  */
4500 
4501 static double
4503  GENTRY *from,
4504  GENTRY *to,
4505  int axis,
4506  double gap,
4507  double *ret
4508 )
4509 {
4510 #define TIMESLARGER 10. /* how many times larger must be a curve to not change too much */
4511  double rm[2];
4512  double oldpos[2];
4513  double times, limit, df, dx;
4514  int j, k;
4515  GENTRY *xge, *pge, *nge, *bge[2];
4516 
4517  /* remember the old points to calculate ret */
4518  oldpos[0] = from->prev->fpoints[axis][2];
4519  oldpos[1] = to->fpoints[axis][2];
4520 
4521  rm[0] = rm[1] = gap / 2. ;
4522 
4523  bge[0] = from; /* this is convenient for iterations */
4524  bge[1] = to;
4525 
4526  /* first try to modify large curves but if have none then settle for small */
4527  for(times = (TIMESLARGER-1); times > 0.1; times /= 2. ) {
4528 
4529  if(rm[0]+rm[1] == 0.)
4530  break;
4531 
4532  /* iterate in both directions, backwards then forwards */
4533  for(j = 0; j<2; j++) {
4534 
4535  if(rm[j] == 0.) /* if this direction is exhausted */
4536  continue;
4537 
4538  limit = fabs(rm[j]) * (1.+times);
4539 
4540  for(xge = bge[j]->cntr[j]; xge != bge[!j]; xge = xge->cntr[j]) {
4541  dx = xge->fpoints[axis][2] - xge->prev->fpoints[axis][2];
4542  df = fabs(dx) - limit;
4543  if( df <= FEPS ) /* curve is too small to change */
4544  continue;
4545 
4546  if( df >= fabs(rm[j]) )
4547  df = rm[j];
4548  else
4549  df *= fsign(rm[j]); /* we may cover this part of rm */
4550 
4551  rm[j] -= df;
4552  limit = fabs(rm[j]) * (1.+times);
4553 
4554  if(xge->type == GE_CURVE) { /* correct internal points */
4555  double scale = ((dx+df) / dx) - 1.;
4556  double base;
4557 
4558  if(j)
4559  base = xge->fpoints[axis][2];
4560  else
4561  base = xge->prev->fpoints[axis][2];
4562 
4563  for(k = 0; k<2; k++)
4564  xge->fpoints[axis][k] += scale *
4565  (xge->fpoints[axis][k] - base);
4566  }
4567 
4568  /* move all the intermediate lines */
4569  if(j) {
4570  df = -df; /* absolute direction */
4571  pge = bge[1]->bkwd;
4572  nge = xge->bkwd;
4573  } else {
4574  xge->fpoints[axis][2] += df;
4575  pge = bge[0];
4576  nge = xge->frwd;
4577  }
4578  while(nge != pge) {
4579  if(nge->type == GE_CURVE) {
4580  nge->fpoints[axis][0] +=df;
4581  nge->fpoints[axis][1] +=df;
4582  }
4583  nge->fpoints[axis][2] += df;
4584  if(nge->next != nge->frwd) { /* last entry of contour */
4585  nge->frwd->prev->fpoints[axis][2] += df;
4586  }
4587  nge = nge->cntr[!j];
4588  }
4589 
4590  if(rm[j] == 0.)
4591  break;
4592  }
4593  }
4594  }
4595 
4596  /* find the difference */
4597  oldpos[0] -= from->prev->fpoints[axis][2];
4598  oldpos[1] -= to->fpoints[axis][2];
4599 
4600  if(ret) {
4601  ret[0] = oldpos[0] - from->