"Fossies" - the Fresh Open Source Software Archive

Member "ttf2pt1-3.4.4/pt1.c" (31 Dec 2003, 178308 Bytes) of package /linux/misc/old/ttf2pt1-3.4.4.tgz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "pt1.c" see the Fossies "Dox" file reference documentation.

    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 "windows.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];
  116 int      notherb;
  117 int      bbox[4];   /* the FontBBox array */
  118 double   italic_angle;
  119 
  120 GLYPH   *glyph_list;
  121 int    encoding[ENCTABSZ];  /* inverse of glyph[].char_no */
  122 int    kerning_pairs = 0;
  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
  157 isign(
  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
  170 fsign(
  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 *
  183 newgentry(
  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
  206 rmoveto(
  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
  220 rlineto(
  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
  237 rrcurveto(
  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
  263 closepath(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
  283 assertpath(
  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%x -next-> 0x%x -prev-> 0x%x \n",
  307                 pe, ge, 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%x \n", 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%x -frwd-> 0x%x -bkwd-> 0x%x \n",
  326                     ge, ge->frwd, 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%x -bkwd-> 0x%x -next-> 0x%x \n",
  334                         ge, ge->bkwd, 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%x -...-> 0x%x -frwd-> 0x%x \n",
  342                         first, ge, ge->frwd);
  343                     abort();
  344                 }
  345             }
  346             break;
  347         }
  348 
  349     }
  350 }
  351 
  352 void
  353 assertisfloat(
  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
  371 assertisint(
  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
  394 fg_rmoveto(
  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
  440 ig_rmoveto(
  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
  484 fg_rlineto(
  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
  530 ig_rlineto(
  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
  574 fg_rrcurveto(
  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
  638 ig_rrcurveto(
  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
  699 g_closepath(
  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
  752 fixcvends(
  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%x) on floating entry, ABORT\n", 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
  902 fixcvdir(
  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%x) on floating entry, ABORT\n", ge);
  914         abort(); /* dump core */
  915     }
  916 
  917     fdir = (dir & CVDIR_FRONT) - CVDIR_FEQUAL;
  918     if ((dir & CVDIR_REAR) == CVDIR_RSAME)
  919         rdir = fdir; /* we need only isign, exact value doesn't matter */
  920     else
  921         rdir = (dir & CVDIR_REAR) - CVDIR_REQUAL;
  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
 1034 fgetcvdir(
 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%x) on int entry, ABORT\n", 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
 1096 igetcvdir(
 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%x) on floating entry, ABORT\n", 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
 1174 iround(
 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
 1187 dumppaths(
 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 %8x", mark, 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
 1239 pathtoint(
 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
 1329 fcheckcv(
 1330     GENTRY * ge,
 1331     double dx,
 1332     double dy
 1333 )
 1334 {
 1335     if( !(ge->flags & GEF_FLOAT) ) {
 1336         fprintf(stderr, "**! fcheckcv(0x%x) on int entry, ABORT\n", 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
 1355 icheckcv(
 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%x) on floating entry, ABORT\n", 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
 1385 fclosepaths(
 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
 1450 smoothjoints(
 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
 1706 debugstems(
 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
 1737 addbluestems(
 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
 1785 sortstems(
 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
 1837 stemoverlap(
 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
 1862 steminblue(
 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
 1891 markbluestems(
 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
 1984 joinmainstems(
 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
 2525 subfrombase(
 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
 2649 printbasestem(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
 2664 joinsubstems(
 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
 2808 uniformstems(
 2809       STEM * s,
 2810       short *pairs,
 2811       int ns
 2812 )
 2813 {
 2814     int i, j, 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
 2864 findstemat(
 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%x ge=0x%x\n",
 2921                     value, origin, ge, 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
 3222 groupsubstems(
 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
 3329 buildstems(
 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
 3833 fstraighten(
 3834        GLYPH * g
 3835 )
 3836 {
 3837     GENTRY         *ge, *pge, *nge, *ige;
 3838     double          df;
 3839     int             dir;
 3840     double          iln, oln;
 3841     int             svdir, 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%x 0x%x\n", pge, 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%x 0x%x\n", ge, 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
 3964 fsqequation(
 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
 4041 ffixquadrants(
 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%x (%g %g) (%g %g) (%g %g) (%g %g)\n  ", g->name,
 4059                 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%x: %d pts(%c): ", 
 4080                     g->name, 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%x (%g %g) (%g %g) (%g %g) (%g %g) at %d points\n  ", g->name,
 4131                 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%x %g/%g\n", 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
 4190 iiszigzag(
 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
 4240 fiszigzag(
 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
 4290 fsplitzigzags(
 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 *
 4358 freethisge(
 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
 4426 addgeafter(
 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
 4473 fixendpath(
 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
 4502 fclosegap(
 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->prev->fpoints[axis][2];
 4602         ret[1] = oldpos[1] - to->fpoints[axis][2];
 4603     }
 4604 
 4605 #if 0
 4606     if( rm[0]+rm[1] != gap - oldpos[1] + oldpos[0]) {
 4607         fprintf(stderr, "** gap=%g rm[0]=%g rm[1]=%g o[0]=%g o[1]=%g rg=%g og=%g\n",
 4608             gap, rm[0], rm[1], oldpos[0], oldpos[1], rm[0]+rm[1], 
 4609             gap - oldpos[1] + oldpos[0]);
 4610     }
 4611 #endif
 4612 
 4613     return rm[0]+rm[1];
 4614 #undef TIMESLARGER
 4615 }
 4616 
 4617 /* remove the lines or curves smaller or equal to the size limit */
 4618 
 4619 static void
 4620 fdelsmall(
 4621     GLYPH *g,
 4622     double minlen
 4623 )
 4624 {
 4625     GENTRY  *ge, *nge, *pge, *xge, *next;
 4626     int i, k;
 4627     double dx, dy, d2, d2m;
 4628     double minlen2;
 4629 #define TIMESLARGER 10. /* how much larger must be a curve to not change too much */
 4630 
 4631     minlen2 = minlen*minlen;
 4632 
 4633     for (ge = g->entries; ge != 0; ge = next) {
 4634         next = ge->next;
 4635 
 4636         if (ge->type != GE_CURVE && ge->type != GE_LINE)
 4637             continue;
 4638 
 4639         d2m = 0;
 4640         for(i= (ge->type==GE_CURVE? 0: 2); i<3; i++) {
 4641             dx = ge->fxn[i] - ge->prev->fx3;
 4642             dy = ge->fyn[i] - ge->prev->fy3;
 4643             d2 = dx*dx + dy*dy;
 4644             if(d2m < d2)
 4645                 d2m = d2;
 4646         }
 4647 
 4648         if( d2m > minlen2 ) { /* line is not too small */
 4649             /* XXX add more normalization here */
 4650             continue;
 4651         }
 4652 
 4653         /* if the line is too small */
 4654 
 4655         /* check forwards if we have a whole sequence of them */
 4656         nge = ge;
 4657         for(xge = ge->frwd; xge != ge; xge = xge->frwd) {
 4658             d2m = 0;
 4659             for(i= (xge->type==GE_CURVE? 0: 2); i<3; i++) {
 4660                 dx = xge->fxn[i] - xge->prev->fx3;
 4661                 dy = xge->fyn[i] - xge->prev->fy3;
 4662                 d2 = dx*dx + dy*dy;
 4663                 if(d2m < d2)
 4664                     d2m = d2;
 4665             }
 4666             if( d2m > minlen2 ) /* line is not too small */
 4667                 break;
 4668             nge = xge;
 4669             if(next == nge) /* move the next step past this sequence */
 4670                 next = next->next;
 4671         }
 4672 
 4673         /* check backwards if we have a whole sequence of them */
 4674         pge = ge;
 4675         for(xge = ge->bkwd; xge != ge; xge = xge->bkwd) {
 4676             d2m = 0;
 4677             for(i= (xge->type==GE_CURVE? 0: 2); i<3; i++) {
 4678                 dx = xge->fxn[i] - xge->prev->fx3;
 4679                 dy = xge->fyn[i] - xge->prev->fy3;
 4680                 d2 = dx*dx + dy*dy;
 4681                 if(d2m < d2)
 4682                     d2m = d2;
 4683             }
 4684             if( d2m > minlen2 ) /* line is not too small */
 4685                 break;
 4686             pge = xge;
 4687         }
 4688 
 4689         /* now we have a sequence of small fragments in pge...nge (inclusive) */
 4690 
 4691         if(ISDBG(FCONCISE))  {
 4692             fprintf(stderr, "glyph %s has very small fragments(%x..%x..%x)\n", 
 4693             g->name, pge, ge, nge);
 4694             dumppaths(g, pge, nge);
 4695         }
 4696 
 4697         /* reduce whole sequence to one part and remember the middle point */
 4698         if(pge != nge) {
 4699             while(1) {
 4700                 xge = pge->frwd;
 4701                 if(xge == nge) {
 4702                     pge->fx1 = pge->fx2 = pge->fx3;
 4703                     pge->fx3 = nge->fx3;
 4704                     pge->fy1 = pge->fy2 = pge->fy3;
 4705                     pge->fy3 = nge->fy3;
 4706                     pge->type = GE_CURVE;
 4707                     freethisge(nge);
 4708                     break;
 4709                 }
 4710                 if(xge == nge->bkwd) {
 4711                     pge->fx1 = pge->fx2 = (pge->fx3+xge->fx3)/2.;
 4712                     pge->fx3 = nge->fx3;
 4713                     pge->fy1 = pge->fy2 = (pge->fy3+xge->fy3)/2.;
 4714                     pge->fy3 = nge->fy3;
 4715                     pge->type = GE_CURVE;
 4716                     freethisge(nge);
 4717                     freethisge(xge);
 4718                     break;
 4719                 }
 4720                 freethisge(pge); pge = xge;
 4721                 xge = nge->bkwd; freethisge(nge); nge = xge;
 4722             }
 4723         }
 4724         ge = pge;
 4725 
 4726         /* check if the whole sequence is small */
 4727         dx = ge->fx3 - ge->prev->fx3;
 4728         dy = ge->fy3 - ge->prev->fy3;
 4729         d2 = dx*dx + dy*dy;
 4730 
 4731         if( d2 > minlen2 ) { /* no, it is not */
 4732             double b, d;
 4733 
 4734             WARNING_3 fprintf(stderr, "glyph %s had a sequence of fragments < %g points each, reduced to one curve\n",
 4735                 g->name, minlen);
 4736 
 4737             /* check that we did not create a monstrosity spanning quadrants */
 4738             if(fsign(ge->fx1 - ge->prev->fx1) * fsign(ge->fx3 - ge->fx1) < 0
 4739             || fsign(ge->fy1 - ge->prev->fy1) * fsign(ge->fy3 - ge->fy1) < 0 ) { 
 4740                 /* yes, we did; are both parts of this thing big enough ? */
 4741                 dx = ge->fx1 - ge->prev->fx3;
 4742                 dy = ge->fy1 - ge->prev->fy3;
 4743                 d2 = dx*dx + dy*dy;
 4744 
 4745                 dx = ge->fx3 - ge->fx1;
 4746                 dy = ge->fy3 - ge->fy1;
 4747                 d2m = dx*dx + dy*dy;
 4748 
 4749                 if(d2 > minlen2 && d2m > minlen2) { /* make two straights */
 4750                     nge = newgentry(GEF_FLOAT);
 4751                     *nge = *ge;
 4752                     
 4753                     for(i=0; i<2; i++) {
 4754                         ge->fpoints[i][2] = ge->fpoints[i][0];
 4755                         b = nge->fpoints[i][0];
 4756                         d = nge->fpoints[i][2] - b;
 4757                         nge->fpoints[i][0] = b + 0.1*d;
 4758                         nge->fpoints[i][1] = b + 0.9*d;
 4759                     }
 4760                 }
 4761                 for(i=0; i<2; i++) { /* make one straight or first of two straights */
 4762                     b = ge->prev->fpoints[i][2];
 4763                     d = ge->fpoints[i][2] - b;
 4764                     ge->fpoints[i][0] = b + 0.1*d;
 4765                     ge->fpoints[i][1] = b + 0.9*d;
 4766                 }
 4767             }
 4768             continue; 
 4769         }
 4770 
 4771         if(ge->frwd == ge) { /* points to itself, just remove the path completely */
 4772             WARNING_3 fprintf(stderr, "glyph %s had a path made of fragments < %g points each, removed\n",
 4773                 g->name, minlen);
 4774 
 4775             next = freethisge(ge);
 4776             continue;
 4777         } 
 4778 
 4779         /* now close the gap by x and y */
 4780         for(i=0; i<2; i++) {
 4781             double gap;
 4782 
 4783             gap = ge->fpoints[i][2] - ge->prev->fpoints[i][2];
 4784             if( fclosegap(ge, ge, i, gap, NULL) != 0.0 ) {
 4785                 double scale, base;
 4786 
 4787                 /* not good, as the last resort just scale the next line */
 4788                 gap = ge->fpoints[i][2] - ge->prev->fpoints[i][2];
 4789 
 4790                 if(ISDBG(FCONCISE)) 
 4791                     fprintf(stderr, "    last resort on %c: closing next by %g\n",
 4792                     (i==0 ? 'x' : 'y'), gap);
 4793 
 4794                 nge = ge->frwd;
 4795                 base = nge->fpoints[i][2];
 4796                 dx = ge->fpoints[i][2] - base;
 4797                 if(fabs(dx) < FEPS)
 4798                     continue;
 4799 
 4800                 scale = ((dx-gap) / dx);
 4801 
 4802                 if(nge->type == GE_CURVE)
 4803                     for(k = 0; k<2; k++)
 4804                         nge->fpoints[i][k] = base + 
 4805                             scale * (nge->fpoints[i][k] - base);
 4806 
 4807                 ge->fpoints[i][2] -= gap;
 4808             }
 4809         }
 4810 
 4811         /* OK, the gap is closed - remove this useless GENTRY */
 4812         freethisge(ge);
 4813     }
 4814 #undef TIMESLARGER
 4815 }
 4816 
 4817 /* find the point where two rays continuing vectors cross
 4818  * returns 1 if they cross, 0 if they don't
 4819  * If they cross optionally (if the pointers are not NULL) returns 
 4820  * the maximal scales for both vectors and also optionally the point 
 4821  * where the rays cross (twice).
 4822  * Expects that the curves are normalized.
 4823  *
 4824  * For convenience there are 2 front-end functions taking
 4825  * arguments in different formats
 4826  */
 4827