pdf2swf/ttf2pt1/pt1.c

   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 int      stdhw, stdvw;  /* dominant stems widths */
  31 int      stemsnaph[12], stemsnapv[12];  /* most typical stem width */
  32
  33 int      bluevalues[14];
  34 int      nblues;
  35 int      otherblues[10];
  36 int      notherb;
  37 int      bbox[4];       /* the FontBBox array */
  38 double   italic_angle;
  39
  40 GLYPH   *glyph_list;
  41 int    encoding[ENCTABSZ];      /* inverse of glyph[].char_no */
  42 int    kerning_pairs = 0;
  43
  44 /* prototypes */
  45 static int isign( int x);
  46 static int fsign( double x);
  47 static void fixcvdir( GENTRY * ge, int dir);
  48 static void fixcvends( GENTRY * ge);
  49 static int fgetcvdir( GENTRY * ge);
  50 static int igetcvdir( GENTRY * ge);
  51 static int fiszigzag( GENTRY *ge);
  52 static int iiszigzag( GENTRY *ge);
  53 static GENTRY * freethisge( GENTRY *ge);
  54 static void addgeafter( GENTRY *oge, GENTRY *nge );
  55 static GENTRY * newgentry( int flags);
  56 static void debugstems( char *name, STEM * hstems, int nhs, STEM * vstems, int nvs);
  57 static int addbluestems( STEM *s, int n);
  58 static void sortstems( STEM * s, int n);
  59 static int stemoverlap( STEM * s1, STEM * s2);
  60 static int steminblue( STEM *s);
  61 static void markbluestems( STEM *s, int nold);
  62 static int joinmainstems( STEM * s, int nold, int useblues);
  63 static void joinsubstems( STEM * s, short *pairs, int nold, int useblues);
  64 static void fixendpath( GENTRY *ge);
  65 static void fdelsmall( GLYPH *g, double minlen);
  66 static double fcvarea( GENTRY *ge);
  67 static int fckjoinedcv( GLYPH *g, double t, GENTRY *nge,
  68         GENTRY *old1, GENTRY *old2, double k);
  69 static double fcvval( GENTRY *ge, int axis, double t);
  70 static double fclosegap( GENTRY *from, GENTRY *to, int axis,
  71         double gap, double *ret);
  72
  73 static int
  74 isign(
  75      int x
  76 )
  77 {
  78         if (x > 0)
  79                 return 1;
  80         else if (x < 0)
  81                 return -1;
  82         else
  83                 return 0;
  84 }
  85
  86 static int
  87 fsign(
  88      double x
  89 )
  90 {
  91         if (x > 0.0)
  92                 return 1;
  93         else if (x < 0.0)
  94                 return -1;
  95         else
  96                 return 0;
  97 }
  98
  99 static GENTRY *
 100 newgentry(
 101         int flags
 102 )
 103 {
 104         GENTRY         *ge;
 105
 106         ge = calloc(1, sizeof(GENTRY));
 107
 108         if (ge == 0) {
 109                 fprintf(stderr, "***** Memory allocation error *****\n");
 110                 exit(255);
 111         }
 112         ge->stemid = -1;
 113         ge->flags = flags;
 114         /* the rest is set to 0 by calloc() */
 115         return ge;
 116 }
 117
 118 /*
 119  * Routines to print out Postscript functions with optimization
 120  */
 121
 122 void
 123 rmoveto(
 124         int dx,
 125         int dy
 126 )
 127 {
 128         if (optimize && dx == 0)
 129                 fprintf(pfa_file, "%d vmoveto\n", dy);
 130         else if (optimize && dy == 0)
 131                 fprintf(pfa_file, "%d hmoveto\n", dx);
 132         else
 133                 fprintf(pfa_file, "%d %d rmoveto\n", dx, dy);
 134 }
 135
 136 void
 137 rlineto(
 138         int dx,
 139         int dy
 140 )
 141 {
 142         if (optimize && dx == 0 && dy == 0)     /* for special pathologic
 143                                                  * case */
 144                 return;
 145         else if (optimize && dx == 0)
 146                 fprintf(pfa_file, "%d vlineto\n", dy);
 147         else if (optimize && dy == 0)
 148                 fprintf(pfa_file, "%d hlineto\n", dx);
 149         else
 150                 fprintf(pfa_file, "%d %d rlineto\n", dx, dy);
 151 }
 152
 153 void
 154 rrcurveto(
 155           int dx1,
 156           int dy1,
 157           int dx2,
 158           int dy2,
 159           int dx3,
 160           int dy3
 161 )
 162 {
 163         /* first two ifs are for crazy cases that occur surprisingly often */
 164         if (optimize && dx1 == 0 && dx2 == 0 && dx3 == 0)
 165                 rlineto(0, dy1 + dy2 + dy3);
 166         else if (optimize && dy1 == 0 && dy2 == 0 && dy3 == 0)
 167                 rlineto(dx1 + dx2 + dx3, 0);
 168         else if (optimize && dy1 == 0 && dx3 == 0)
 169                 fprintf(pfa_file, "%d %d %d %d hvcurveto\n",
 170                         dx1, dx2, dy2, dy3);
 171         else if (optimize && dx1 == 0 && dy3 == 0)
 172                 fprintf(pfa_file, "%d %d %d %d vhcurveto\n",
 173                         dy1, dx2, dy2, dx3);
 174         else
 175                 fprintf(pfa_file, "%d %d %d %d %d %d rrcurveto\n",
 176                         dx1, dy1, dx2, dy2, dx3, dy3);
 177 }
 178
 179 void
 180 closepath(void)
 181 {
 182         fprintf(pfa_file, "closepath\n");
 183 }
 184
 185 /*
 186  * Many of the path processing routines exist (or will exist) in
 187  * both floating-point and integer version. Fimally most of the
 188  * processing will go in floating point and the integer processing
 189  * will become legacy.
 190  * The names of floating routines start with f, names of integer
 191  * routines start with i, and those old routines existing in one
 192  * version only have no such prefix at all.
 193  */
 194
 195 /*
 196 ** Routine that checks integrity of the path, for debugging
 197 */
 198
 199 void
 200 assertpath(
 201            GENTRY * from,
 202            char *file,
 203            int line,
 204            char *name
 205 )
 206 {
 207         GENTRY         *first, *pe, *ge;
 208         int     isfloat;
 209
 210         if(from==0)
 211                 return;
 212         isfloat = (from->flags & GEF_FLOAT);
 213         pe = from->prev;
 214         for (ge = from; ge != 0; pe = ge, ge = ge->next) {
 215                 if( (ge->flags & GEF_FLOAT) ^ isfloat ) {
 216                         fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
 217                         fprintf(stderr, "float flag changes from %s to %s at 0x%p (type %c, prev type %c)\n",
 218                                 (isfloat ? "TRUE" : "FALSE"), (isfloat ? "FALSE" : "TRUE"), ge, ge->type, pe->type);
 219                         abort();
 220                 }
 221                 if (pe != ge->prev) {
 222                         fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
 223                         fprintf(stderr, "unidirectional chain 0x%x -next-> 0x%x -prev-> 0x%x \n",
 224                                 pe, ge, ge->prev);
 225                         abort();
 226                 }
 227
 228                 switch(ge->type) {
 229                 case GE_MOVE:
 230                         break;
 231                 case GE_PATH:
 232                         if (ge->prev == 0) {
 233                                 fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
 234                                 fprintf(stderr, "empty path at 0x%x \n", ge);
 235                                 abort();
 236                         }
 237                         break;
 238                 case GE_LINE:
 239                 case GE_CURVE:
 240                         if(ge->frwd->bkwd != ge) {
 241                                 fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
 242                                 fprintf(stderr, "unidirectional chain 0x%x -frwd-> 0x%x -bkwd-> 0x%x \n",
 243                                         ge, ge->frwd, ge->frwd->bkwd);
 244                                 abort();
 245                         }
 246                         if(ge->prev->type == GE_MOVE) {
 247                                 first = ge;
 248                                 if(ge->bkwd->next->type != GE_PATH) {
 249                                         fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
 250                                         fprintf(stderr, "broken first backlink 0x%x -bkwd-> 0x%x -next-> 0x%x \n",
 251                                                 ge, ge->bkwd, ge->bkwd->next);
 252                                         abort();
 253                                 }
 254                         }
 255                         if(ge->next->type == GE_PATH) {
 256                                 if(ge->frwd != first) {
 257                                         fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
 258                                         fprintf(stderr, "broken loop 0x%x -...-> 0x%x -frwd-> 0x%x \n",
 259                                                 first, ge, ge->frwd);
 260                                         abort();
 261                                 }
 262                         }
 263                         break;
 264                 }
 265
 266         }
 267 }
 268
 269 void
 270 assertisfloat(
 271         GLYPH *g,
 272         char *msg
 273 )
 274 {
 275         if( !(g->flags & GF_FLOAT) ) {
 276                 fprintf(stderr, "**! Glyph %s is not float: %s\n", g->name, msg);
 277                 abort();
 278         }
 279         if(g->lastentry) {
 280                 if( !(g->lastentry->flags & GEF_FLOAT) ) {
 281                         fprintf(stderr, "**! Glyphs %s last entry is int: %s\n", g->name, msg);
 282                         abort();
 283                 }
 284         }
 285 }
 286
 287 void
 288 assertisint(
 289         GLYPH *g,
 290         char *msg
 291 )
 292 {
 293         if( (g->flags & GF_FLOAT) ) {
 294                 fprintf(stderr, "**! Glyph %s is not int: %s\n", g->name, msg);
 295                 abort();
 296         }
 297         if(g->lastentry) {
 298                 if( (g->lastentry->flags & GEF_FLOAT) ) {
 299                         fprintf(stderr, "**! Glyphs %s last entry is float: %s\n", g->name, msg);
 300                         abort();
 301                 }
 302         }
 303 }
 304
 305
 306 /*
 307  * Routines to save the generated data about glyph
 308  */
 309
 310 void
 311 fg_rmoveto(
 312           GLYPH * g,
 313           double x,
 314           double y)
 315 {
 316         GENTRY         *oge;
 317
 318         if (ISDBG(BUILDG))
 319                 fprintf(stderr, "%s: f rmoveto(%g, %g)\n", g->name, x, y);
 320
 321         assertisfloat(g, "adding float MOVE");
 322
 323         if ((oge = g->lastentry) != 0) {
 324                 if (oge->type == GE_MOVE) {     /* just eat up the first move */
 325                         oge->fx3 = x;
 326                         oge->fy3 = y;
 327                 } else if (oge->type == GE_LINE || oge->type == GE_CURVE) {
 328                         fprintf(stderr, "Glyph %s: MOVE in middle of path\n", g->name);
 329                 } else {
 330                         GENTRY         *nge;
 331
 332                         nge = newgentry(GEF_FLOAT);
 333                         nge->type = GE_MOVE;
 334                         nge->fx3 = x;
 335                         nge->fy3 = y;
 336
 337                         oge->next = nge;
 338                         nge->prev = oge;
 339                         g->lastentry = nge;
 340                 }
 341         } else {
 342                 GENTRY         *nge;
 343
 344                 nge = newgentry(GEF_FLOAT);
 345                 nge->type = GE_MOVE;
 346                 nge->fx3 = x;
 347                 nge->fy3 = y;
 348                 nge->bkwd = (GENTRY*)&g->entries;
 349                 g->entries = g->lastentry = nge;
 350         }
 351
 352         if (0 && ISDBG(BUILDG))
 353                 dumppaths(g, NULL, NULL);
 354 }
 355
 356 void
 357 fg_rlineto(
 358           GLYPH * g,
 359           double x,
 360           double y)
 361 {
 362         GENTRY         *oge, *nge;
 363
 364         if (ISDBG(BUILDG))
 365                 fprintf(stderr, "%s: f rlineto(%g, %g)\n", g->name, x, y);
 366
 367         assertisfloat(g, "adding float LINE");
 368
 369         nge = newgentry(GEF_FLOAT);
 370         nge->type = GE_LINE;
 371         nge->fx3 = x;
 372         nge->fy3 = y;
 373
 374         if ((oge = g->lastentry) != 0) {
 375                 if (x == oge->fx3 && y == oge->fy3) {   /* empty line */
 376                         /* ignore it or we will get in troubles later */
 377                         free(nge);
 378                         return;
 379                 }
 380                 if (g->path == 0) {
 381                         g->path = nge;
 382                         nge->bkwd = nge->frwd = nge;
 383                 } else {
 384                         oge->frwd = nge;
 385                         nge->bkwd = oge;
 386                         g->path->bkwd = nge;
 387                         nge->frwd = g->path;
 388                 }
 389
 390                 oge->next = nge;
 391                 nge->prev = oge;
 392                 g->lastentry = nge;
 393         } else {
 394                 WARNING_1 fprintf(stderr, "Glyph %s: LINE outside of path\n", g->name);
 395                 free(nge);
 396         }
 397
 398         if (0 && ISDBG(BUILDG))
 399                 dumppaths(g, NULL, NULL);
 400 }
 401
 402 void
 403 fg_rrcurveto(
 404             GLYPH * g,
 405             double x1,
 406             double y1,
 407             double x2,
 408             double y2,
 409             double x3,
 410             double y3)
 411 {
 412         GENTRY         *oge, *nge;
 413
 414         oge = g->lastentry;
 415
 416         if (ISDBG(BUILDG))
 417                 fprintf(stderr, "%s: f rrcurveto(%g, %g, %g, %g, %g, %g)\n"
 418                         ,g->name, x1, y1, x2, y2, x3, y3);
 419
 420         assertisfloat(g, "adding float CURVE");
 421
 422         if (oge && oge->fx3 == x1 && x1 == x2 && x2 == x3)      /* check if it's
 423                                                                  * actually a line */
 424                 fg_rlineto(g, x1, y3);
 425         else if (oge && oge->fy3 == y1 && y1 == y2 && y2 == y3)
 426                 fg_rlineto(g, x3, y1);
 427         else {
 428                 nge = newgentry(GEF_FLOAT);
 429                 nge->type = GE_CURVE;
 430                 nge->fx1 = x1;
 431                 nge->fy1 = y1;
 432                 nge->fx2 = x2;
 433                 nge->fy2 = y2;
 434                 nge->fx3 = x3;
 435                 nge->fy3 = y3;
 436
 437                 if (oge != 0) {
 438                         if (x3 == oge->fx3 && y3 == oge->fy3) {
 439                                 free(nge);      /* consider this curve empty */
 440                                 /* ignore it or we will get in troubles later */
 441                                 return;
 442                         }
 443                         if (g->path == 0) {
 444                                 g->path = nge;
 445                                 nge->bkwd = nge->frwd = nge;
 446                         } else {
 447                                 oge->frwd = nge;
 448                                 nge->bkwd = oge;
 449                                 g->path->bkwd = nge;
 450                                 nge->frwd = g->path;
 451                         }
 452
 453                         oge->next = nge;
 454                         nge->prev = oge;
 455                         g->lastentry = nge;
 456                 } else {
 457                         WARNING_1 fprintf(stderr, "Glyph %s: CURVE outside of path\n", g->name);
 458                         free(nge);
 459                 }
 460         }
 461
 462         if (0 && ISDBG(BUILDG))
 463                 dumppaths(g, NULL, NULL);
 464 }
 465
 466 void
 467 g_closepath(
 468             GLYPH * g
 469 )
 470 {
 471         GENTRY         *oge, *nge;
 472
 473         if (ISDBG(BUILDG))
 474                 fprintf(stderr, "%s: closepath\n", g->name);
 475
 476         oge = g->lastentry;
 477
 478         if (g->path == 0) {
 479                 WARNING_1 fprintf(stderr, "Warning: **** closepath on empty path in glyph \"%s\" ****\n",
 480                         g->name);
 481                 if (oge == 0) {
 482                         WARNING_1 fprintf(stderr, "No previois entry\n");
 483                 } else {
 484                         WARNING_1 fprintf(stderr, "Previous entry type: %c\n", oge->type);
 485                         if (oge->type == GE_MOVE) {
 486                                 g->lastentry = oge->prev;
 487                                 if (oge->prev == 0)
 488                                         g->entries = 0;
 489                         }
 490                 }
 491                 return;
 492         }
 493
 494         nge = newgentry(oge->flags & GEF_FLOAT); /* keep the same type */
 495         nge->type = GE_PATH;
 496
 497         g->path = 0;
 498
 499         oge->next = nge;
 500         nge->prev = oge;
 501         g->lastentry = nge;
 502
 503         if (0 && ISDBG(BUILDG))
 504                 dumppaths(g, NULL, NULL);
 505 }
 506
 507 /*
 508  * * SB * Routines to smooth and fix the glyphs
 509  */
 510
 511 /*
 512 ** we don't want to see the curves with coinciding middle and
 513 ** outer points
 514 */
 515
 516 static void
 517 fixcvends(
 518           GENTRY * ge
 519 )
 520 {
 521         int             dx, dy;
 522         int             x0, y0, x1, y1, x2, y2, x3, y3;
 523
 524         if (ge->type != GE_CURVE)
 525                 return;
 526
 527         if(ge->flags & GEF_FLOAT) {
 528                 fprintf(stderr, "**! fixcvends(0x%x) on floating entry, ABORT\n", ge);
 529                 abort(); /* dump core */
 530         }
 531
 532         x0 = ge->prev->ix3;
 533         y0 = ge->prev->iy3;
 534         x1 = ge->ix1;
 535         y1 = ge->iy1;
 536         x2 = ge->ix2;
 537         y2 = ge->iy2;
 538         x3 = ge->ix3;
 539         y3 = ge->iy3;
 540
 541
 542         /* look at the start of the curve */
 543         if (x1 == x0 && y1 == y0) {
 544                 dx = x2 - x1;
 545                 dy = y2 - y1;
 546
 547                 if (dx == 0 && dy == 0
 548                     || x2 == x3 && y2 == y3) {
 549                         /* Oops, we actually have a straight line */
 550                         /*
 551                          * if it's small, we hope that it will get optimized
 552                          * later
 553                          */
 554                         if (abs(x3 - x0) <= 2 || abs(y3 - y0) <= 2) {
 555                                 ge->ix1 = x3;
 556                                 ge->iy1 = y3;
 557                                 ge->ix2 = x0;
 558                                 ge->iy2 = y0;
 559                         } else {/* just make it a line */
 560                                 ge->type = GE_LINE;
 561                         }
 562                 } else {
 563                         if (abs(dx) < 4 && abs(dy) < 4) {       /* consider it very
 564                                                                  * small */
 565                                 ge->ix1 = x2;
 566                                 ge->iy1 = y2;
 567                         } else if (abs(dx) < 8 && abs(dy) < 8) {        /* consider it small */
 568                                 ge->ix1 += dx / 2;
 569                                 ge->iy1 += dy / 2;
 570                         } else {
 571                                 ge->ix1 += dx / 4;
 572                                 ge->iy1 += dy / 4;
 573                         }
 574                         /* make sure that it's still on the same side */
 575                         if (abs(x3 - x0) * abs(dy) < abs(y3 - y0) * abs(dx)) {
 576                                 if (abs(x3 - x0) * abs(ge->iy1 - y0) > abs(y3 - y0) * abs(ge->ix1 - x0))
 577                                         ge->ix1 += isign(dx);
 578                         } else {
 579                                 if (abs(x3 - x0) * abs(ge->iy1 - y0) < abs(y3 - y0) * abs(ge->ix1 - x0))
 580                                         ge->iy1 += isign(dy);
 581                         }
 582
 583                         ge->ix2 += (x3 - x2) / 8;
 584                         ge->iy2 += (y3 - y2) / 8;
 585                         /* make sure that it's still on the same side */
 586                         if (abs(x3 - x0) * abs(y3 - y2) < abs(y3 - y0) * abs(x3 - x2)) {
 587                                 if (abs(x3 - x0) * abs(y3 - ge->iy2) > abs(y3 - y0) * abs(x3 - ge->ix2))
 588                                         ge->iy1 -= isign(y3 - y2);
 589                         } else {
 590                                 if (abs(x3 - x0) * abs(y3 - ge->iy2) < abs(y3 - y0) * abs(x3 - ge->ix2))
 591                                         ge->ix1 -= isign(x3 - x2);
 592                         }
 593
 594                 }
 595         } else if (x2 == x3 && y2 == y3) {
 596                 dx = x1 - x2;
 597                 dy = y1 - y2;
 598
 599                 if (dx == 0 && dy == 0) {
 600                         /* Oops, we actually have a straight line */
 601                         /*
 602                          * if it's small, we hope that it will get optimized
 603                          * later
 604                          */
 605                         if (abs(x3 - x0) <= 2 || abs(y3 - y0) <= 2) {
 606                                 ge->ix1 = x3;
 607                                 ge->iy1 = y3;
 608                                 ge->ix2 = x0;
 609                                 ge->iy2 = y0;
 610                         } else {/* just make it a line */
 611                                 ge->type = GE_LINE;
 612                         }
 613                 } else {
 614                         if (abs(dx) < 4 && abs(dy) < 4) {       /* consider it very
 615                                                                  * small */
 616                                 ge->ix2 = x1;
 617                                 ge->iy2 = y1;
 618                         } else if (abs(dx) < 8 && abs(dy) < 8) {        /* consider it small */
 619                                 ge->ix2 += dx / 2;
 620                                 ge->iy2 += dy / 2;
 621                         } else {
 622                                 ge->ix2 += dx / 4;
 623                                 ge->iy2 += dy / 4;
 624                         }
 625                         /* make sure that it's still on the same side */
 626                         if (abs(x3 - x0) * abs(dy) < abs(y3 - y0) * abs(dx)) {
 627                                 if (abs(x3 - x0) * abs(ge->iy2 - y3) > abs(y3 - y0) * abs(ge->ix2 - x3))
 628                                         ge->ix2 += isign(dx);
 629                         } else {
 630                                 if (abs(x3 - x0) * abs(ge->iy2 - y3) < abs(y3 - y0) * abs(ge->ix2 - x3))
 631                                         ge->iy2 += isign(dy);
 632                         }
 633
 634                         ge->ix1 += (x0 - x1) / 8;
 635                         ge->iy1 += (y0 - y1) / 8;
 636                         /* make sure that it's still on the same side */
 637                         if (abs(x3 - x0) * abs(y0 - y1) < abs(y3 - y0) * abs(x0 - x1)) {
 638                                 if (abs(x3 - x0) * abs(y0 - ge->iy1) > abs(y3 - y0) * abs(x0 - ge->ix1))
 639                                         ge->iy1 -= isign(y0 - y1);
 640                         } else {
 641                                 if (abs(x3 - x0) * abs(y0 - ge->iy1) < abs(y3 - y0) * abs(x0 - ge->ix1))
 642                                         ge->ix1 -= isign(x0 - x1);
 643                         }
 644
 645                 }
 646         }
 647 }
 648
 649 /* if we have any curves that are in fact flat but
 650 ** are not horizontal nor vertical, substitute
 651 ** them also with lines
 652 */
 653
 654 void
 655 flattencurves(
 656               GLYPH * g
 657 )
 658 {
 659         GENTRY         *ge;
 660         int             x0, y0, x1, y1, x2, y2, x3, y3;
 661
 662         assertisint(g, "flattencurves INT");
 663
 664         for (ge = g->entries; ge != 0; ge = ge->next) {
 665                 if (ge->type != GE_CURVE)
 666                         continue;
 667
 668                 x0 = ge->prev->ix3;
 669                 y0 = ge->prev->iy3;
 670                 x1 = ge->ix1;
 671                 y1 = ge->iy1;
 672                 x2 = ge->ix2;
 673                 y2 = ge->iy2;
 674                 x3 = ge->ix3;
 675                 y3 = ge->iy3;
 676
 677                 if ((x1 - x0) * (y2 - y1) == (x2 - x1) * (y1 - y0)
 678                     && (x1 - x0) * (y3 - y2) == (x3 - x2) * (y1 - y0)) {
 679                         ge->type = GE_LINE;
 680                 }
 681         }
 682 }
 683
 684 /*
 685 ** After transformations we want to make sure that the resulting
 686 ** curve is going in the same quadrant as the original one,
 687 ** because rounding errors introduced during transformations
 688 ** may make the result completeley wrong.
 689 **
 690 ** `dir' argument describes the direction of the original curve,
 691 ** it is the superposition of two values for the front and
 692 ** rear ends of curve:
 693 **
 694 ** >EQUAL - goes over the line connecting the ends
 695 ** =EQUAL - coincides with the line connecting the ends
 696 ** <EQUAL - goes under the line connecting the ends
 697 **
 698 ** See CVDIR_* for exact definitions.
 699 */
 700
 701 static void
 702 fixcvdir(
 703          GENTRY * ge,
 704          int dir
 705 )
 706 {
 707         int             a, b, c, d;
 708         double          kk, kk1, kk2;
 709         int             changed;
 710         int             fdir, rdir;
 711
 712         if(ge->flags & GEF_FLOAT) {
 713                 fprintf(stderr, "**! fixcvdir(0x%x) on floating entry, ABORT\n", ge);
 714                 abort(); /* dump core */
 715         }
 716
 717         fdir = (dir & CVDIR_FRONT) - CVDIR_FEQUAL;
 718         if ((dir & CVDIR_REAR) == CVDIR_RSAME)
 719                 rdir = fdir; /* we need only isign, exact value doesn't matter */
 720         else
 721                 rdir = (dir & CVDIR_REAR) - CVDIR_REQUAL;
 722
 723         fixcvends(ge);
 724
 725         c = isign(ge->ix3 - ge->prev->ix3);     /* note the direction of
 726                                                  * curve */
 727         d = isign(ge->iy3 - ge->prev->iy3);
 728
 729         a = ge->iy3 - ge->prev->iy3;
 730         b = ge->ix3 - ge->prev->ix3;
 731         kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 732         a = ge->iy1 - ge->prev->iy3;
 733         b = ge->ix1 - ge->prev->ix3;
 734         kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 735         a = ge->iy3 - ge->iy2;
 736         b = ge->ix3 - ge->ix2;
 737         kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 738
 739         changed = 1;
 740         while (changed) {
 741                 if (ISDBG(FIXCVDIR)) {
 742                         /* for debugging */
 743                         fprintf(stderr, "fixcvdir %d %d (%d %d %d %d %d %d) %f %f %f\n",
 744                                 fdir, rdir,
 745                                 ge->ix1 - ge->prev->ix3,
 746                                 ge->iy1 - ge->prev->iy3,
 747                                 ge->ix2 - ge->ix1,
 748                                 ge->iy2 - ge->iy1,
 749                                 ge->ix3 - ge->ix2,
 750                                 ge->iy3 - ge->iy2,
 751                                 kk1, kk, kk2);
 752                 }
 753                 changed = 0;
 754
 755                 if (fdir > 0) {
 756                         if (kk1 > kk) { /* the front end has problems */
 757                                 if (c * (ge->ix1 - ge->prev->ix3) > 0) {
 758                                         ge->ix1 -= c;
 759                                         changed = 1;
 760                                 } if (d * (ge->iy2 - ge->iy1) > 0) {
 761                                         ge->iy1 += d;
 762                                         changed = 1;
 763                                 }
 764                                 /* recalculate the coefficients */
 765                                 a = ge->iy3 - ge->prev->iy3;
 766                                 b = ge->ix3 - ge->prev->ix3;
 767                                 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 768                                 a = ge->iy1 - ge->prev->iy3;
 769                                 b = ge->ix1 - ge->prev->ix3;
 770                                 kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 771                         }
 772                 } else if (fdir < 0) {
 773                         if (kk1 < kk) { /* the front end has problems */
 774                                 if (c * (ge->ix2 - ge->ix1) > 0) {
 775                                         ge->ix1 += c;
 776                                         changed = 1;
 777                                 } if (d * (ge->iy1 - ge->prev->iy3) > 0) {
 778                                         ge->iy1 -= d;
 779                                         changed = 1;
 780                                 }
 781                                 /* recalculate the coefficients */
 782                                 a = ge->iy1 - ge->prev->iy3;
 783                                 b = ge->ix1 - ge->prev->ix3;
 784                                 kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 785                                 a = ge->iy3 - ge->prev->iy3;
 786                                 b = ge->ix3 - ge->prev->ix3;
 787                                 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 788                         }
 789                 }
 790                 if (rdir > 0) {
 791                         if (kk2 < kk) { /* the rear end has problems */
 792                                 if (c * (ge->ix2 - ge->ix1) > 0) {
 793                                         ge->ix2 -= c;
 794                                         changed = 1;
 795                                 } if (d * (ge->iy3 - ge->iy2) > 0) {
 796                                         ge->iy2 += d;
 797                                         changed = 1;
 798                                 }
 799                                 /* recalculate the coefficients */
 800                                 a = ge->iy3 - ge->prev->iy3;
 801                                 b = ge->ix3 - ge->prev->ix3;
 802                                 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 803                                 a = ge->iy3 - ge->iy2;
 804                                 b = ge->ix3 - ge->ix2;
 805                                 kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 806                         }
 807                 } else if (rdir < 0) {
 808                         if (kk2 > kk) { /* the rear end has problems */
 809                                 if (c * (ge->ix3 - ge->ix2) > 0) {
 810                                         ge->ix2 += c;
 811                                         changed = 1;
 812                                 } if (d * (ge->iy2 - ge->iy1) > 0) {
 813                                         ge->iy2 -= d;
 814                                         changed = 1;
 815                                 }
 816                                 /* recalculate the coefficients */
 817                                 a = ge->iy3 - ge->prev->iy3;
 818                                 b = ge->ix3 - ge->prev->ix3;
 819                                 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 820                                 a = ge->iy3 - ge->iy2;
 821                                 b = ge->ix3 - ge->ix2;
 822                                 kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 823                         }
 824                 }
 825         }
 826         fixcvends(ge);
 827 }
 828
 829 /* Get the directions of ends of curve for further usage */
 830
 831 /* expects that the previous element is also float */
 832
 833 static int
 834 fgetcvdir(
 835          GENTRY * ge
 836 )
 837 {
 838         double          a, b;
 839         double          k, k1, k2;
 840         int             dir = 0;
 841
 842         if( !(ge->flags & GEF_FLOAT) ) {
 843                 fprintf(stderr, "**! fgetcvdir(0x%x) on int entry, ABORT\n", ge);
 844                 abort(); /* dump core */
 845         }
 846
 847         a = ge->fy3 - ge->prev->fy3;
 848         b = ge->fx3 - ge->prev->fx3;
 849         k = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ( b / a));
 850         a = ge->fy1 - ge->prev->fy3;
 851         b = ge->fx1 - ge->prev->fx3;
 852         k1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ( b / a));
 853         a = ge->fy3 - ge->fy2;
 854         b = ge->fx3 - ge->fx2;
 855         k2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ( b / a));
 856
 857         if (k1 < k)
 858                 dir |= CVDIR_FUP;
 859         else if (k1 > k)
 860                 dir |= CVDIR_FDOWN;
 861         else
 862                 dir |= CVDIR_FEQUAL;
 863
 864         if (k2 > k)
 865                 dir |= CVDIR_RUP;
 866         else if (k2 < k)
 867                 dir |= CVDIR_RDOWN;
 868         else
 869                 dir |= CVDIR_REQUAL;
 870
 871         return dir;
 872 }
 873
 874
 875 /* expects that the previous element is also int */
 876
 877 static int
 878 igetcvdir(
 879          GENTRY * ge
 880 )
 881 {
 882         int             a, b;
 883         double          k, k1, k2;
 884         int             dir = 0;
 885
 886         if(ge->flags & GEF_FLOAT) {
 887                 fprintf(stderr, "**! igetcvdir(0x%x) on floating entry, ABORT\n", ge);
 888                 abort(); /* dump core */
 889         }
 890
 891         a = ge->iy3 - ge->prev->iy3;
 892         b = ge->ix3 - ge->prev->ix3;
 893         k = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 894         a = ge->iy1 - ge->prev->iy3;
 895         b = ge->ix1 - ge->prev->ix3;
 896         k1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 897         a = ge->iy3 - ge->iy2;
 898         b = ge->ix3 - ge->ix2;
 899         k2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
 900
 901         if (k1 < k)
 902                 dir |= CVDIR_FUP;
 903         else if (k1 > k)
 904                 dir |= CVDIR_FDOWN;
 905         else
 906                 dir |= CVDIR_FEQUAL;
 907
 908         if (k2 > k)
 909                 dir |= CVDIR_RUP;
 910         else if (k2 < k)
 911                 dir |= CVDIR_RDOWN;
 912         else
 913                 dir |= CVDIR_REQUAL;
 914
 915         return dir;
 916 }
 917
 918 #if 0
 919 /* a function just to test the work of fixcvdir() */
 920 static void
 921 testfixcvdir(
 922              GLYPH * g
 923 )
 924 {
 925         GENTRY         *ge;
 926         int             dir;
 927
 928         for (ge = g->entries; ge != 0; ge = ge->next) {
 929                 if (ge->type == GE_CURVE) {
 930                         dir = igetcvdir(ge);
 931                         fixcvdir(ge, dir);
 932                 }
 933         }
 934 }
 935 #endif
 936
 937 static int
 938 iround(
 939         double val
 940 )
 941 {
 942         return (int) (val > 0 ? val + 0.5 : val - 0.5);
 943 }
 944
 945 /* for debugging - dump the glyph
 946  * mark with a star the entries from start to end inclusive
 947  * (start == NULL means don't mark any, end == NULL means to the last)
 948  */
 949
 950 void
 951 dumppaths(
 952         GLYPH *g,
 953         GENTRY *start,
 954         GENTRY *end
 955 )
 956 {
 957         GENTRY *ge;
 958         int i;
 959         char mark=' ';
 960
 961         fprintf(stderr, "Glyph %s:\n", g->name);
 962
 963         /* now do the conversion */
 964         for(ge = g->entries; ge != 0; ge = ge->next) {
 965                 if(ge == start)
 966                         mark = '*';
 967                 fprintf(stderr, " %c %8x", mark, ge);
 968                 switch(ge->type) {
 969                 case GE_MOVE:
 970                 case GE_LINE:
 971                         if(ge->flags & GEF_FLOAT)
 972                                 fprintf(stderr," %c float (%g, %g)\n", ge->type, ge->fx3, ge->fy3);
 973                         else
 974                                 fprintf(stderr," %c int (%d, %d)\n", ge->type, ge->ix3, ge->iy3);
 975                         break;
 976                 case GE_CURVE:
 977                         if(ge->flags & GEF_FLOAT) {
 978                                 fprintf(stderr," C float ");
 979                                 for(i=0; i<3; i++)
 980                                         fprintf(stderr,"(%g, %g) ", ge->fxn[i], ge->fyn[i]);
 981                                 fprintf(stderr,"\n");
 982                         } else {
 983                                 fprintf(stderr," C int ");
 984                                 for(i=0; i<3; i++)
 985                                         fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
 986                                 fprintf(stderr,"\n");
 987                         }
 988                         break;
 989                 default:
 990                         fprintf(stderr, " %c\n", ge->type);
 991                         break;
 992                 }
 993                 if(ge == end)
 994                         mark = ' ';
 995         }
 996 }
 997
 998 /*
 999  * Routine that converts all entries in the path from float to int
1000  */
1001
1002 void
1003 pathtoint(
1004         GLYPH *g
1005 )
1006 {
1007         GENTRY *ge;
1008         int x[3], y[3];
1009         int i;
1010
1011
1012         if(ISDBG(TOINT))
1013                 fprintf(stderr, "TOINT: glyph %s\n", g->name);
1014         assertisfloat(g, "converting path to int\n");
1015
1016         fdelsmall(g, 1.0); /* get rid of sub-pixel contours */
1017         assertpath(g->entries, __FILE__, __LINE__, g->name);
1018
1019         /* 1st pass, collect the directions of the curves: have
1020          * to do that in advance, while everyting is float
1021          */
1022         for(ge = g->entries; ge != 0; ge = ge->next) {
1023                 if( !(ge->flags & GEF_FLOAT) ) {
1024                         fprintf(stderr, "**! glyphs %s has int entry, found in conversion to int\n",
1025                                 g->name);
1026                         exit(1);
1027                 }
1028                 if(ge->type == GE_CURVE) {
1029                         ge->dir = fgetcvdir(ge);
1030                 }
1031         }
1032
1033         /* now do the conversion */
1034         for(ge = g->entries; ge != 0; ge = ge->next) {
1035                 switch(ge->type) {
1036                 case GE_MOVE:
1037                 case GE_LINE:
1038                         if(ISDBG(TOINT))
1039                                 fprintf(stderr," %c float x=%g y=%g\n", ge->type, ge->fx3, ge->fy3);
1040                         x[0] = iround(ge->fx3);
1041                         y[0] = iround(ge->fy3);
1042                         for(i=0; i<3; i++) { /* put some valid values everywhere, for convenience */
1043                                 ge->ixn[i] = x[0];
1044                                 ge->iyn[i] = y[0];
1045                         }
1046                         if(ISDBG(TOINT))
1047                                 fprintf(stderr,"   int   x=%d y=%d\n", ge->ix3, ge->iy3);
1048                         break;
1049                 case GE_CURVE:
1050                         if(ISDBG(TOINT))
1051                                 fprintf(stderr," %c float ", ge->type);
1052
1053                         for(i=0; i<3; i++) {
1054                                 if(ISDBG(TOINT))
1055                                         fprintf(stderr,"(%g, %g) ", ge->fxn[i], ge->fyn[i]);
1056                                 x[i] = iround(ge->fxn[i]);
1057                                 y[i] = iround(ge->fyn[i]);
1058                         }
1059
1060                         if(ISDBG(TOINT))
1061                                 fprintf(stderr,"\n   int   ");
1062
1063                         for(i=0; i<3; i++) {
1064                                 ge->ixn[i] = x[i];
1065                                 ge->iyn[i] = y[i];
1066                                 if(ISDBG(TOINT))
1067                                         fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
1068                         }
1069                         ge->flags &= ~GEF_FLOAT; /* for fixcvdir */
1070                         fixcvdir(ge, ge->dir);
1071
1072                         if(ISDBG(TOINT)) {
1073                                 fprintf(stderr,"\n   fixed ");
1074                                 for(i=0; i<3; i++)
1075                                         fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
1076                                 fprintf(stderr,"\n");
1077                         }
1078
1079                         break;
1080                 }
1081                 ge->flags &= ~GEF_FLOAT;
1082         }
1083         g->flags &= ~GF_FLOAT;
1084 }
1085
1086
1087 /* check whether we can fix up the curve to change its size by (dx,dy) */
1088 /* 0 means NO, 1 means YES */
1089
1090 /* for float: if scaling would be under 10% */
1091
1092 int
1093 fcheckcv(
1094         GENTRY * ge,
1095         double dx,
1096         double dy
1097 )
1098 {
1099         if( !(ge->flags & GEF_FLOAT) ) {
1100                 fprintf(stderr, "**! fcheckcv(0x%x) on int entry, ABORT\n", ge);
1101                 abort(); /* dump core */
1102         }
1103
1104         if (ge->type != GE_CURVE)
1105                 return 0;
1106
1107         if( fabs(ge->fx3 - ge->prev->fx3) < fabs(dx) * 10 )
1108                 return 0;
1109
1110         if( fabs(ge->fy3 - ge->prev->fy3) < fabs(dy) * 10 )
1111                 return 0;
1112
1113         return 1;
1114 }
1115
1116 /* for int: if won't create new zigzags at the ends */
1117
1118 int
1119 icheckcv(
1120         GENTRY * ge,
1121         int dx,
1122         int dy
1123 )
1124 {
1125         int             xdep, ydep;
1126
1127         if(ge->flags & GEF_FLOAT) {
1128                 fprintf(stderr, "**! icheckcv(0x%x) on floating entry, ABORT\n", ge);
1129                 abort(); /* dump core */
1130         }
1131
1132         if (ge->type != GE_CURVE)
1133                 return 0;
1134
1135         xdep = ge->ix3 - ge->prev->ix3;
1136         ydep = ge->iy3 - ge->prev->iy3;
1137
1138         if (ge->type == GE_CURVE
1139             && (xdep * (xdep + dx)) > 0
1140             && (ydep * (ydep + dy)) > 0) {
1141                 return 1;
1142         } else
1143                 return 0;
1144 }
1145
1146 /* float connect the ends of open contours */
1147
1148 void
1149 fclosepaths(
1150            GLYPH * g
1151 )
1152 {
1153         GENTRY         *ge, *fge, *xge, *nge;
1154         int             i;
1155
1156         assertisfloat(g, "fclosepaths float\n");
1157
1158         for (xge = g->entries; xge != 0; xge = xge->next) {
1159                 if( xge->type != GE_PATH )
1160                         continue;
1161
1162                 ge = xge->prev;
1163                 if(ge == 0 || ge->type != GE_LINE && ge->type!= GE_CURVE) {
1164                         fprintf(stderr, "**! Glyph %s got empty path\n",
1165                                 g->name);
1166                         exit(1);
1167                 }
1168
1169                 fge = ge->frwd;
1170                 if (fge->prev == 0 || fge->prev->type != GE_MOVE) {
1171                         fprintf(stderr, "**! Glyph %s got strange beginning of path\n",
1172                                 g->name);
1173                         exit(1);
1174                 }
1175                 fge = fge->prev;
1176                 if (fge->fx3 != ge->fx3 || fge->fy3 != ge->fy3) {
1177                         /* we have to fix this open path */
1178
1179                         WARNING_4 fprintf(stderr, "Glyph %s got path open by dx=%g dy=%g\n",
1180                         g->name, fge->fx3 - ge->fx3, fge->fy3 - ge->fy3);
1181
1182
1183                         /* add a new line */
1184                         nge = newgentry(GEF_FLOAT);
1185                         (*nge) = (*ge);
1186                         nge->fx3 = fge->fx3;
1187                         nge->fy3 = fge->fy3;
1188                         nge->type = GE_LINE;
1189
1190                         addgeafter(ge, nge);
1191
1192                         if (fabs(ge->fx3 - fge->fx3) <= 2 && fabs(ge->fy3 - fge->fy3) <= 2) {
1193                                 /*
1194                                  * small change, try to get rid of the new entry
1195                                  */
1196
1197                                 double df[2];
1198
1199                                 for(i=0; i<2; i++) {
1200                                         df[i] = ge->fpoints[i][2] - fge->fpoints[i][2];
1201                                         df[i] = fclosegap(nge, nge, i, df[i], NULL);
1202                                 }
1203
1204                                 if(df[0] == 0. && df[1] == 0.) {
1205                                         /* closed gap successfully, remove the added entry */
1206                                         freethisge(nge);
1207                                 }
1208                         }
1209                 }
1210         }
1211 }
1212
1213 void
1214 smoothjoints(
1215              GLYPH * g
1216 )
1217 {
1218         GENTRY         *ge, *ne;
1219         int             dx1, dy1, dx2, dy2, k;
1220         int             dir;
1221
1222         return; /* this stuff seems to create problems */
1223
1224         assertisint(g, "smoothjoints int");
1225
1226         if (g->entries == 0)    /* nothing to do */
1227                 return;
1228
1229         for (ge = g->entries->next; ge != 0; ge = ge->next) {
1230                 ne = ge->frwd;
1231
1232                 /*
1233                  * although there should be no one-line path * and any path
1234                  * must end with CLOSEPATH, * nobody can say for sure
1235                  */
1236
1237                 if (ge == ne || ne == 0)
1238                         continue;
1239
1240                 /* now handle various joints */
1241
1242                 if (ge->type == GE_LINE && ne->type == GE_LINE) {
1243                         dx1 = ge->ix3 - ge->prev->ix3;
1244                         dy1 = ge->iy3 - ge->prev->iy3;
1245                         dx2 = ne->ix3 - ge->ix3;
1246                         dy2 = ne->iy3 - ge->iy3;
1247
1248                         /* check whether they have the same direction */
1249                         /* and the same slope */
1250                         /* then we can join them into one line */
1251
1252                         if (dx1 * dx2 >= 0 && dy1 * dy2 >= 0 && dx1 * dy2 == dy1 * dx2) {
1253                                 /* extend the previous line */
1254                                 ge->ix3 = ne->ix3;
1255                                 ge->iy3 = ne->iy3;
1256
1257                                 /* and get rid of the next line */
1258                                 freethisge(ne);
1259                         }
1260                 } else if (ge->type == GE_LINE && ne->type == GE_CURVE) {
1261                         fixcvends(ne);
1262
1263                         dx1 = ge->ix3 - ge->prev->ix3;
1264                         dy1 = ge->iy3 - ge->prev->iy3;
1265                         dx2 = ne->ix1 - ge->ix3;
1266                         dy2 = ne->iy1 - ge->iy3;
1267
1268                         /* if the line is nearly horizontal and we can fix it */
1269                         if (dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0
1270                             && icheckcv(ne, 0, -dy1)
1271                             && abs(dy1) <= 4) {
1272                                 dir = igetcvdir(ne);
1273                                 ge->iy3 -= dy1;
1274                                 ne->iy1 -= dy1;
1275                                 fixcvdir(ne, dir);
1276                                 if (ge->next != ne)
1277                                         ne->prev->iy3 -= dy1;
1278                                 dy1 = 0;
1279                         } else if (dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0
1280                                    && icheckcv(ne, -dx1, 0)
1281                                    && abs(dx1) <= 4) {
1282                                 /* the same but vertical */
1283                                 dir = igetcvdir(ne);
1284                                 ge->ix3 -= dx1;
1285                                 ne->ix1 -= dx1;
1286                                 fixcvdir(ne, dir);
1287                                 if (ge->next != ne)
1288                                         ne->prev->ix3 -= dx1;
1289                                 dx1 = 0;
1290                         }
1291                         /*
1292                          * if line is horizontal and curve begins nearly
1293                          * horizontally
1294                          */
1295                         if (dy1 == 0 && dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0) {
1296                                 dir = igetcvdir(ne);
1297                                 ne->iy1 -= dy2;
1298                                 fixcvdir(ne, dir);
1299                                 dy2 = 0;
1300                         } else if (dx1 == 0 && dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0) {
1301                                 /* the same but vertical */
1302                                 dir = igetcvdir(ne);
1303                                 ne->ix1 -= dx2;
1304                                 fixcvdir(ne, dir);
1305                                 dx2 = 0;
1306                         }
1307                 } else if (ge->type == GE_CURVE && ne->type == GE_LINE) {
1308                         fixcvends(ge);
1309
1310                         dx1 = ge->ix3 - ge->ix2;
1311                         dy1 = ge->iy3 - ge->iy2;
1312                         dx2 = ne->ix3 - ge->ix3;
1313                         dy2 = ne->iy3 - ge->iy3;
1314
1315                         /* if the line is nearly horizontal and we can fix it */
1316                         if (dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0
1317                             && icheckcv(ge, 0, dy2)
1318                             && abs(dy2) <= 4) {
1319                                 dir = igetcvdir(ge);
1320                                 ge->iy3 += dy2;
1321                                 ge->iy2 += dy2;
1322                                 fixcvdir(ge, dir);
1323                                 if (ge->next != ne)
1324                                         ne->prev->iy3 += dy2;
1325                                 dy2 = 0;
1326                         } else if (dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0
1327                                    && icheckcv(ge, dx2, 0)
1328                                    && abs(dx2) <= 4) {
1329                                 /* the same but vertical */
1330                                 dir = igetcvdir(ge);
1331                                 ge->ix3 += dx2;
1332                                 ge->ix2 += dx2;
1333                                 fixcvdir(ge, dir);
1334                                 if (ge->next != ne)
1335                                         ne->prev->ix3 += dx2;
1336                                 dx2 = 0;
1337                         }
1338                         /*
1339                          * if line is horizontal and curve ends nearly
1340                          * horizontally
1341                          */
1342                         if (dy2 == 0 && dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0) {
1343                                 dir = igetcvdir(ge);
1344                                 ge->iy2 += dy1;
1345                                 fixcvdir(ge, dir);
1346                                 dy1 = 0;
1347                         } else if (dx2 == 0 && dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0) {
1348                                 /* the same but vertical */
1349                                 dir = igetcvdir(ge);
1350                                 ge->ix2 += dx1;
1351                                 fixcvdir(ge, dir);
1352                                 dx1 = 0;
1353                         }
1354                 } else if (ge->type == GE_CURVE && ne->type == GE_CURVE) {
1355                         fixcvends(ge);
1356                         fixcvends(ne);
1357
1358                         dx1 = ge->ix3 - ge->ix2;
1359                         dy1 = ge->iy3 - ge->iy2;
1360                         dx2 = ne->ix1 - ge->ix3;
1361                         dy2 = ne->iy1 - ge->iy3;
1362
1363                         /*
1364                          * check if we have a rather smooth joint at extremal
1365                          * point
1366                          */
1367                         /* left or right extremal point */
1368                         if (abs(dx1) <= 4 && abs(dx2) <= 4
1369                             && dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0
1370                             && dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0
1371                             && (ge->iy3 < ge->prev->iy3 && ne->iy3 < ge->iy3
1372                                 || ge->iy3 > ge->prev->iy3 && ne->iy3 > ge->iy3)
1373                           && (ge->ix3 - ge->prev->ix3) * (ne->ix3 - ge->ix3) < 0
1374                                 ) {
1375                                 dir = igetcvdir(ge);
1376                                 ge->ix2 += dx1;
1377                                 dx1 = 0;
1378                                 fixcvdir(ge, dir);
1379                                 dir = igetcvdir(ne);
1380                                 ne->ix1 -= dx2;
1381                                 dx2 = 0;
1382                                 fixcvdir(ne, dir);
1383                         }
1384                         /* top or down extremal point */
1385                         else if (abs(dy1) <= 4 && abs(dy2) <= 4
1386                                  && dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0
1387                                  && dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0
1388                                  && (ge->ix3 < ge->prev->ix3 && ne->ix3 < ge->ix3
1389                                 || ge->ix3 > ge->prev->ix3 && ne->ix3 > ge->ix3)
1390                                  && (ge->iy3 - ge->prev->iy3) * (ne->iy3 - ge->iy3) < 0
1391                                 ) {
1392                                 dir = igetcvdir(ge);
1393                                 ge->iy2 += dy1;
1394                                 dy1 = 0;
1395                                 fixcvdir(ge, dir);
1396                                 dir = igetcvdir(ne);
1397                                 ne->iy1 -= dy2;
1398                                 dy2 = 0;
1399                                 fixcvdir(ne, dir);
1400                         }
1401                         /* or may be we just have a smooth junction */
1402                         else if (dx1 * dx2 >= 0 && dy1 * dy2 >= 0
1403                                  && 10 * abs(k = abs(dx1 * dy2) - abs(dy1 * dx2)) < (abs(dx1 * dy2) + abs(dy1 * dx2))) {
1404                                 int             tries[6][4];
1405                                 int             results[6];
1406                                 int             i, b;
1407
1408                                 /* build array of changes we are going to try */
1409                                 /* uninitalized entries are 0 */
1410                                 if (k > 0) {
1411                                         static int      t1[6][4] = {
1412                                                 {0, 0, 0, 0},
1413                                                 {-1, 0, 1, 0},
1414                                                 {-1, 0, 0, 1},
1415                                                 {0, -1, 1, 0},
1416                                                 {0, -1, 0, 1},
1417                                         {-1, -1, 1, 1}};
1418                                         memcpy(tries, t1, sizeof tries);
1419                                 } else {
1420                                         static int      t1[6][4] = {
1421                                                 {0, 0, 0, 0},
1422                                                 {1, 0, -1, 0},
1423                                                 {1, 0, 0, -1},
1424                                                 {0, 1, -1, 0},
1425                                                 {0, 1, 0, -1},
1426                                         {1, 1, -1, -1}};
1427                                         memcpy(tries, t1, sizeof tries);
1428                                 }
1429
1430                                 /* now try the changes */
1431                                 results[0] = abs(k);
1432                                 for (i = 1; i < 6; i++) {
1433                                         results[i] = abs((abs(dx1) + tries[i][0]) * (abs(dy2) + tries[i][1]) -
1434                                                          (abs(dy1) + tries[i][2]) * (abs(dx2) + tries[i][3]));
1435                                 }
1436
1437                                 /* and find the best try */
1438                                 k = abs(k);
1439                                 b = 0;
1440                                 for (i = 1; i < 6; i++)
1441                                         if (results[i] < k) {
1442                                                 k = results[i];
1443                                                 b = i;
1444                                         }
1445                                 /* and finally apply it */
1446                                 if (dx1 < 0)
1447                                         tries[b][0] = -tries[b][0];
1448                                 if (dy2 < 0)
1449                                         tries[b][1] = -tries[b][1];
1450                                 if (dy1 < 0)
1451                                         tries[b][2] = -tries[b][2];
1452                                 if (dx2 < 0)
1453                                         tries[b][3] = -tries[b][3];
1454
1455                                 dir = igetcvdir(ge);
1456                                 ge->ix2 -= tries[b][0];
1457                                 ge->iy2 -= tries[b][2];
1458                                 fixcvdir(ge, dir);
1459                                 dir = igetcvdir(ne);
1460                                 ne->ix1 += tries[b][3];
1461                                 ne->iy1 += tries[b][1];
1462                                 fixcvdir(ne, dir);
1463                         }
1464                 }
1465         }
1466 }
1467
1468 /* debugging: print out stems of a glyph */
1469 static void
1470 debugstems(
1471            char *name,
1472            STEM * hstems,
1473            int nhs,
1474            STEM * vstems,
1475            int nvs
1476 )
1477 {
1478         int             i;
1479
1480         fprintf(pfa_file, "%% %s\n", name);
1481         fprintf(pfa_file, "%% %d horizontal stems:\n", nhs);
1482         for (i = 0; i < nhs; i++)
1483                 fprintf(pfa_file, "%% %3d    %d (%d...%d) %c %c%c%c%c\n", i, hstems[i].value,
1484                         hstems[i].from, hstems[i].to,
1485                         ((hstems[i].flags & ST_UP) ? 'U' : 'D'),
1486                         ((hstems[i].flags & ST_END) ? 'E' : '-'),
1487                         ((hstems[i].flags & ST_FLAT) ? 'F' : '-'),
1488                         ((hstems[i].flags & ST_ZONE) ? 'Z' : ' '),
1489                         ((hstems[i].flags & ST_TOPZONE) ? 'T' : ' '));
1490         fprintf(pfa_file, "%% %d vertical stems:\n", nvs);
1491         for (i = 0; i < nvs; i++)
1492                 fprintf(pfa_file, "%% %3d    %d (%d...%d) %c %c%c\n", i, vstems[i].value,
1493                         vstems[i].from, vstems[i].to,
1494                         ((vstems[i].flags & ST_UP) ? 'U' : 'D'),
1495                         ((vstems[i].flags & ST_END) ? 'E' : '-'),
1496                         ((vstems[i].flags & ST_FLAT) ? 'F' : '-'));
1497 }
1498
1499 /* add pseudo-stems for the limits of the Blue zones to the stem array */
1500 static int
1501 addbluestems(
1502         STEM *s,
1503         int n
1504 )
1505 {
1506         int i;
1507
1508         for(i=0; i<nblues && i<2; i+=2) { /* baseline */
1509                 s[n].value=bluevalues[i];
1510                 s[n].flags=ST_UP|ST_ZONE;
1511                 /* don't overlap with anything */
1512                 s[n].origin=s[n].from=s[n].to= -10000+i;
1513                 n++;
1514                 s[n].value=bluevalues[i+1];
1515                 s[n].flags=ST_ZONE;
1516                 /* don't overlap with anything */
1517                 s[n].origin=s[n].from=s[n].to= -10000+i+1;
1518                 n++;
1519         }
1520         for(i=2; i<nblues; i+=2) { /* top zones */
1521                 s[n].value=bluevalues[i];
1522                 s[n].flags=ST_UP|ST_ZONE|ST_TOPZONE;
1523                 /* don't overlap with anything */
1524                 s[n].origin=s[n].from=s[n].to= -10000+i;
1525                 n++;
1526                 s[n].value=bluevalues[i+1];
1527                 s[n].flags=ST_ZONE|ST_TOPZONE;
1528                 /* don't overlap with anything */
1529                 s[n].origin=s[n].from=s[n].to= -10000+i+1;
1530                 n++;
1531         }
1532         for(i=0; i<notherb; i+=2) { /* bottom zones */
1533                 s[n].value=otherblues[i];
1534                 s[n].flags=ST_UP|ST_ZONE;
1535                 /* don't overlap with anything */
1536                 s[n].origin=s[n].from=s[n].to= -10000+i+nblues;
1537                 n++;
1538                 s[n].value=otherblues[i+1];
1539                 s[n].flags=ST_ZONE;
1540                 /* don't overlap with anything */
1541                 s[n].origin=s[n].from=s[n].to= -10000+i+1+nblues;
1542                 n++;
1543         }
1544         return n;
1545 }
1546
1547 /* sort stems in array */
1548 static void
1549 sortstems(
1550           STEM * s,
1551           int n
1552 )
1553 {
1554         int             i, j;
1555         STEM            x;
1556
1557
1558         /* a simple sorting */
1559         /* hm, the ordering criteria are not quite simple :-)
1560          * if the values are tied
1561          * ST_UP always goes under not ST_UP
1562          * ST_ZONE goes on the most outer side
1563          * ST_END goes towards inner side after ST_ZONE
1564          * ST_FLAT goes on the inner side
1565          */
1566
1567         for (i = 0; i < n; i++)
1568                 for (j = i + 1; j < n; j++) {
1569                         if(s[i].value < s[j].value)
1570                                 continue;
1571                         if(s[i].value == s[j].value) {
1572                                 if( (s[i].flags & ST_UP) < (s[j].flags & ST_UP) )
1573                                         continue;
1574                                 if( (s[i].flags & ST_UP) == (s[j].flags & ST_UP) ) {
1575                                         if( s[i].flags & ST_UP ) {
1576                                                 if(
1577                                                 (s[i].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1578                                                         >
1579                                                 (s[j].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1580                                                 )
1581                                                         continue;
1582                                         } else {
1583                                                 if(
1584                                                 (s[i].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1585                                                         <
1586                                                 (s[j].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1587                                                 )
1588                                                         continue;
1589                                         }
1590                                 }
1591                         }
1592                         x = s[j];
1593                         s[j] = s[i];
1594                         s[i] = x;
1595                 }
1596 }
1597
1598 /* check whether two stem borders overlap */
1599
1600 static int
1601 stemoverlap(
1602             STEM * s1,
1603             STEM * s2
1604 )
1605 {
1606         int             result;
1607
1608         if (s1->from <= s2->from && s1->to >= s2->from
1609             || s2->from <= s1->from && s2->to >= s1->from)
1610                 result = 1;
1611         else
1612                 result = 0;
1613
1614         if (ISDBG(STEMOVERLAP))
1615                 fprintf(pfa_file, "%% overlap %d(%d..%d)x%d(%d..%d)=%d\n",
1616                         s1->value, s1->from, s1->to, s2->value, s2->from, s2->to, result);
1617         return result;
1618 }
1619
1620 /*
1621  * check if the stem [border] is in an appropriate blue zone
1622  * (currently not used)
1623  */
1624
1625 static int
1626 steminblue(
1627         STEM *s
1628 )
1629 {
1630         int i, val;
1631
1632         val=s->value;
1633         if(s->flags & ST_UP) {
1634                 /* painted size up, look at lower zones */
1635                 if(nblues>=2 && val>=bluevalues[0] && val<=bluevalues[1] )
1636                         return 1;
1637                 for(i=0; i<notherb; i++) {
1638                         if( val>=otherblues[i] && val<=otherblues[i+1] )
1639                                 return 1;
1640                 }
1641         } else {
1642                 /* painted side down, look at upper zones */
1643                 for(i=2; i<nblues; i++) {
1644                         if( val>=bluevalues[i] && val<=bluevalues[i+1] )
1645                                 return 1;
1646                 }
1647         }
1648
1649         return 0;
1650 }
1651
1652 /* mark the outermost stem [borders] in the blue zones */
1653
1654 static void
1655 markbluestems(
1656         STEM *s,
1657         int nold
1658 )
1659 {
1660         int i, j, a, b, c;
1661         /*
1662          * traverse the list of Blue Values, mark the lowest upper
1663          * stem in each bottom zone and the topmost lower stem in
1664          * each top zone with ST_BLUE
1665          */
1666
1667         /* top zones */
1668         for(i=2; i<nblues; i+=2) {
1669                 a=bluevalues[i]; b=bluevalues[i+1];
1670                 if(ISDBG(BLUESTEMS))
1671                         fprintf(pfa_file, "%% looking at blue zone %d...%d\n", a, b);
1672                 for(j=nold-1; j>=0; j--) {
1673                         if( s[j].flags & (ST_ZONE|ST_UP|ST_END) )
1674                                 continue;
1675                         c=s[j].value;
1676                         if(c<a) /* too low */
1677                                 break;
1678                         if(c<=b) { /* found the topmost stem border */
1679                                 /* mark all the stems with the same value */
1680                                 if(ISDBG(BLUESTEMS))
1681                                         fprintf(pfa_file, "%% found D BLUE at %d\n", s[j].value);
1682                                 /* include ST_END values */
1683                                 while( s[j+1].value==c && (s[j+1].flags & ST_ZONE)==0 )
1684                                         j++;
1685                                 s[j].flags |= ST_BLUE;
1686                                 for(j--; j>=0 && s[j].value==c
1687                                                 && (s[j].flags & (ST_UP|ST_ZONE))==0 ; j--)
1688                                         s[j].flags |= ST_BLUE;
1689                                 break;
1690                         }
1691                 }
1692         }
1693         /* baseline */
1694         if(nblues>=2) {
1695                 a=bluevalues[0]; b=bluevalues[1];
1696                 for(j=0; j<nold; j++) {
1697                         if( (s[j].flags & (ST_ZONE|ST_UP|ST_END))!=ST_UP )
1698                                 continue;
1699                         c=s[j].value;
1700                         if(c>b) /* too high */
1701                                 break;
1702                         if(c>=a) { /* found the lowest stem border */
1703                                 /* mark all the stems with the same value */
1704                                 if(ISDBG(BLUESTEMS))
1705                                         fprintf(pfa_file, "%% found U BLUE at %d\n", s[j].value);
1706                                 /* include ST_END values */
1707                                 while( s[j-1].value==c && (s[j-1].flags & ST_ZONE)==0 )
1708                                         j--;
1709                                 s[j].flags |= ST_BLUE;
1710                                 for(j++; j<nold && s[j].value==c
1711                                                 && (s[j].flags & (ST_UP|ST_ZONE))==ST_UP ; j++)
1712                                         s[j].flags |= ST_BLUE;
1713                                 break;
1714                         }
1715                 }
1716         }
1717         /* bottom zones: the logic is the same as for baseline */
1718         for(i=0; i<notherb; i+=2) {
1719                 a=otherblues[i]; b=otherblues[i+1];
1720                 for(j=0; j<nold; j++) {
1721                         if( (s[j].flags & (ST_UP|ST_ZONE|ST_END))!=ST_UP )
1722                                 continue;
1723                         c=s[j].value;
1724                         if(c>b) /* too high */
1725                                 break;
1726                         if(c>=a) { /* found the lowest stem border */
1727                                 /* mark all the stems with the same value */
1728                                 if(ISDBG(BLUESTEMS))
1729                                         fprintf(pfa_file, "%% found U BLUE at %d\n", s[j].value);
1730                                 /* include ST_END values */
1731                                 while( s[j-1].value==c && (s[j-1].flags & ST_ZONE)==0 )
1732                                         j--;
1733                                 s[j].flags |= ST_BLUE;
1734                                 for(j++; j<nold && s[j].value==c
1735                                                 && (s[j].flags & (ST_UP|ST_ZONE))==ST_UP ; j++)
1736                                         s[j].flags |= ST_BLUE;
1737                                 break;
1738                         }
1739                 }
1740         }
1741 }
1742
1743 /* Eliminate invalid stems, join equivalent lines and remove nested stems
1744  * to build the main (non-substituted) set of stems.
1745  * XXX add consideration of the italic angle
1746  */
1747 static int
1748 joinmainstems(
1749           STEM * s,
1750           int nold,
1751           int useblues /* do we use the blue values ? */
1752 )
1753 {
1754 #define MAX_STACK       1000
1755         STEM            stack[MAX_STACK];
1756         int             nstack = 0;
1757         int             sbottom = 0;
1758         int             nnew;
1759         int             i, j, k;
1760         int             a, b, c, w1, w2, w3;
1761         int             fw, fd;
1762         /*
1763          * priority of the last found stem:
1764          * 0 - nothing found yet
1765          * 1 - has ST_END in it (one or more)
1766          * 2 - has no ST_END and no ST_FLAT, can override only one stem
1767          *     with priority 1
1768          * 3 - has no ST_END and at least one ST_FLAT, can override one
1769          *     stem with priority 2 or any number of stems with priority 1
1770          * 4 (handled separately) - has ST_BLUE, can override anything
1771          */
1772         int             readystem = 0;
1773         int             pri;
1774         int             nlps = 0;       /* number of non-committed
1775                                          * lowest-priority stems */
1776
1777
1778         for (i = 0, nnew = 0; i < nold; i++) {
1779                 if (s[i].flags & (ST_UP|ST_ZONE)) {
1780                         if(s[i].flags & ST_BLUE) {
1781                                 /* we just HAVE to use this value */
1782                                 if (readystem)
1783                                         nnew += 2;
1784                                 readystem=0;
1785
1786                                 /* remember the list of Blue zone stems with the same value */
1787                                 for(a=i, i++; i<nold && s[a].value==s[i].value
1788                                         && (s[i].flags & ST_BLUE); i++)
1789                                         {}
1790                                 b=i; /* our range is a <= i < b */
1791                                 c= -1; /* index of our best guess up to now */
1792                                 pri=0;
1793                                 /* try to find a match, don't cross blue zones */
1794                                 for(; i<nold && (s[i].flags & ST_BLUE)==0; i++) {
1795                                         if(s[i].flags & ST_UP) {
1796                                                 if(s[i].flags & ST_TOPZONE)
1797                                                         break;
1798                                                 else
1799                                                         continue;
1800                                         }
1801                                         for(j=a; j<b; j++) {
1802                                                 if(!stemoverlap(&s[j], &s[i]) )
1803                                                         continue;
1804                                                 /* consider priorities */
1805                                                 if( ( (s[j].flags|s[i].flags) & (ST_FLAT|ST_END) )==ST_FLAT ) {
1806                                                         c=i;
1807                                                         goto bluematch;
1808                                                 }
1809                                                 if( ((s[j].flags|s[i].flags) & ST_END)==0 )  {
1810                                                         if(pri < 2) {
1811                                                                 c=i; pri=2;
1812                                                         }
1813                                                 } else {
1814                                                         if(pri == 0) {
1815                                                                 c=i; pri=1;
1816                                                         }
1817                                                 }
1818                                         }
1819                                 }
1820                         bluematch:
1821                                 /* clean up the stack */
1822                                 nstack=sbottom=0;
1823                                 readystem=0;
1824                                 /* add this stem */
1825                                 s[nnew++]=s[a];
1826                                 if(c<0) { /* make one-dot-wide stem */
1827                                         if(nnew>=b) { /* have no free space */
1828                                                 for(j=nold; j>=b; j--) /* make free space */
1829                                                         s[j]=s[j-1];
1830                                                 b++;
1831                                                 nold++;
1832                                         }
1833                                         s[nnew]=s[a];
1834                                         s[nnew].flags &= ~(ST_UP|ST_BLUE);
1835                                         nnew++;
1836                                         i=b-1;
1837                                 } else {
1838                                         s[nnew++]=s[c];
1839                                         i=c; /* skip up to this point */
1840                                 }
1841                                 if (ISDBG(MAINSTEMS))
1842                                         fprintf(pfa_file, "%% +stem %d...%d U BLUE\n",
1843                                                 s[nnew-2].value, s[nnew-1].value);
1844                         } else {
1845                                 if (nstack >= MAX_STACK) {
1846                                         WARNING_1 fprintf(stderr, "Warning: **** converter's stem stack overflow ****\n");
1847                                         nstack = 0;
1848                                 }
1849                                 stack[nstack++] = s[i];
1850                         }
1851                 } else if(s[i].flags & ST_BLUE) {
1852                         /* again, we just HAVE to use this value */
1853                         if (readystem)
1854                                 nnew += 2;
1855                         readystem=0;
1856
1857                         /* remember the list of Blue zone stems with the same value */
1858                         for(a=i, i++; i<nold && s[a].value==s[i].value
1859                                 && (s[i].flags & ST_BLUE); i++)
1860                                 {}
1861                         b=i; /* our range is a <= i < b */
1862                         c= -1; /* index of our best guess up to now */
1863                         pri=0;
1864                         /* try to find a match */
1865                         for (i = nstack - 1; i >= 0; i--) {
1866                                 if( (stack[i].flags & ST_UP)==0 ) {
1867                                         if( (stack[i].flags & (ST_ZONE|ST_TOPZONE))==ST_ZONE )
1868                                                 break;
1869                                         else
1870                                                 continue;
1871                                 }
1872                                 for(j=a; j<b; j++) {
1873                                         if(!stemoverlap(&s[j], &stack[i]) )
1874                                                 continue;
1875                                         /* consider priorities */
1876                                         if( ( (s[j].flags|stack[i].flags) & (ST_FLAT|ST_END) )==ST_FLAT ) {
1877                                                 c=i;
1878                                                 goto bluedownmatch;
1879                                         }
1880                                         if( ((s[j].flags|stack[i].flags) & ST_END)==0 )  {
1881                                                 if(pri < 2) {
1882                                                         c=i; pri=2;
1883                                                 }
1884                                         } else {
1885                                                 if(pri == 0) {
1886                                                         c=i; pri=1;
1887                                                 }
1888                                         }
1889                                 }
1890                         }
1891                 bluedownmatch:
1892                         /* if found no match make a one-dot-wide stem */
1893                         if(c<0) {
1894                                 c=0;
1895                                 stack[0]=s[b-1];
1896                                 stack[0].flags |= ST_UP;
1897                                 stack[0].flags &= ~ST_BLUE;
1898                         }
1899                         /* remove all the stems conflicting with this one */
1900                         readystem=0;
1901                         for(j=nnew-2; j>=0; j-=2) {
1902                                 if (ISDBG(MAINSTEMS))
1903                                         fprintf(pfa_file, "%% ?stem %d...%d -- %d\n",
1904                                                 s[j].value, s[j+1].value, stack[c].value);
1905                                 if(s[j+1].value < stack[c].value) /* no conflict */
1906                                         break;
1907                                 if(s[j].flags & ST_BLUE) {
1908                                         /* oops, we don't want to spoil other blue zones */
1909                                         stack[c].value=s[j+1].value+1;
1910                                         break;
1911                                 }
1912                                 if( (s[j].flags|s[j+1].flags) & ST_END ) {
1913                                         if (ISDBG(MAINSTEMS))
1914                                                 fprintf(pfa_file, "%% -stem %d...%d p=1\n",
1915                                                         s[j].value, s[j+1].value);
1916                                         continue; /* pri==1, silently discard it */
1917                                 }
1918                                 /* we want to discard no nore than 2 stems of pri>=2 */
1919                                 if( ++readystem > 2 ) {
1920                                         /* change our stem to not conflict */
1921                                         stack[c].value=s[j+1].value+1;
1922                                         break;
1923                                 } else {
1924                                         if (ISDBG(MAINSTEMS))
1925                                                 fprintf(pfa_file, "%% -stem %d...%d p>=2\n",
1926                                                         s[j].value, s[j+1].value);
1927                                         continue;
1928                                 }
1929                         }
1930                         nnew=j+2;
1931                         /* add this stem */
1932                         if(nnew>=b-1) { /* have no free space */
1933                                 for(j=nold; j>=b-1; j--) /* make free space */
1934                                         s[j]=s[j-1];
1935                                 b++;
1936                                 nold++;
1937                         }
1938                         s[nnew++]=stack[c];
1939                         s[nnew++]=s[b-1];
1940                         /* clean up the stack */
1941                         nstack=sbottom=0;
1942                         readystem=0;
1943                         /* set the next position to search */
1944                         i=b-1;
1945                         if (ISDBG(MAINSTEMS))
1946                                 fprintf(pfa_file, "%% +stem %d...%d D BLUE\n",
1947                                         s[nnew-2].value, s[nnew-1].value);
1948                 } else if (nstack > 0) {
1949
1950                         /*
1951                          * check whether our stem overlaps with anything in
1952                          * stack
1953                          */
1954                         for (j = nstack - 1; j >= sbottom; j--) {
1955                                 if (s[i].value <= stack[j].value)
1956                                         break;
1957                                 if (stack[j].flags & ST_ZONE)
1958                                         continue;
1959
1960                                 if ((s[i].flags & ST_END)
1961                                     || (stack[j].flags & ST_END))
1962                                         pri = 1;
1963                                 else if ((s[i].flags & ST_FLAT)
1964                                          || (stack[j].flags & ST_FLAT))
1965                                         pri = 3;
1966                                 else
1967                                         pri = 2;
1968
1969                                 if (pri < readystem && s[nnew + 1].value >= stack[j].value
1970                                     || !stemoverlap(&stack[j], &s[i]))
1971                                         continue;
1972
1973                                 if (readystem > 1 && s[nnew + 1].value < stack[j].value) {
1974                                         nnew += 2;
1975                                         readystem = 0;
1976                                         nlps = 0;
1977                                 }
1978                                 /*
1979                                  * width of the previous stem (if it's
1980                                  * present)
1981                                  */
1982                                 w1 = s[nnew + 1].value - s[nnew].value;
1983
1984                                 /* width of this stem */
1985                                 w2 = s[i].value - stack[j].value;
1986
1987                                 if (readystem == 0) {
1988                                         /* nothing yet, just add a new stem */
1989                                         s[nnew] = stack[j];
1990                                         s[nnew + 1] = s[i];
1991                                         readystem = pri;
1992                                         if (pri == 1)
1993                                                 nlps = 1;
1994                                         else if (pri == 2)
1995                                                 sbottom = j;
1996                                         else {
1997                                                 sbottom = j + 1;
1998                                                 while (sbottom < nstack
1999                                                        && stack[sbottom].value <= stack[j].value)
2000                                                         sbottom++;
2001                                         }
2002                                         if (ISDBG(MAINSTEMS))
2003                                                 fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
2004                                                         stack[j].value, s[i].value, pri, nlps);
2005                                 } else if (pri == 1) {
2006                                         if (stack[j].value > s[nnew + 1].value) {
2007                                                 /*
2008                                                  * doesn't overlap with the
2009                                                  * previous one
2010                                                  */
2011                                                 nnew += 2;
2012                                                 nlps++;
2013                                                 s[nnew] = stack[j];
2014                                                 s[nnew + 1] = s[i];
2015                                                 if (ISDBG(MAINSTEMS))
2016                                                         fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
2017                                                                 stack[j].value, s[i].value, pri, nlps);
2018                                         } else if (w2 < w1) {
2019                                                 /* is narrower */
2020                                                 s[nnew] = stack[j];
2021                                                 s[nnew + 1] = s[i];
2022                                                 if (ISDBG(MAINSTEMS))
2023                                                         fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d %d->%d\n",
2024                                                                 stack[j].value, s[i].value, pri, nlps, w1, w2);
2025                                         }
2026                                 } else if (pri == 2) {
2027                                         if (readystem == 2) {
2028                                                 /* choose the narrower stem */
2029                                                 if (w1 > w2) {
2030                                                         s[nnew] = stack[j];
2031                                                         s[nnew + 1] = s[i];
2032                                                         sbottom = j;
2033                                                         if (ISDBG(MAINSTEMS))
2034                                                                 fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n",
2035                                                                         stack[j].value, s[i].value, pri, nlps);
2036                                                 }
2037                                                 /* else readystem==1 */
2038                                         } else if (stack[j].value > s[nnew + 1].value) {
2039                                                 /*
2040                                                  * value doesn't overlap with
2041                                                  * the previous one
2042                                                  */
2043                                                 nnew += 2;
2044                                                 nlps = 0;
2045                                                 s[nnew] = stack[j];
2046                                                 s[nnew + 1] = s[i];
2047                                                 sbottom = j;
2048                                                 readystem = pri;
2049                                                 if (ISDBG(MAINSTEMS))
2050                                                         fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
2051                                                                 stack[j].value, s[i].value, pri, nlps);
2052                                         } else if (nlps == 1
2053                                                    || stack[j].value > s[nnew - 1].value) {
2054                                                 /*
2055                                                  * we can replace the top
2056                                                  * stem
2057                                                  */
2058                                                 nlps = 0;
2059                                                 s[nnew] = stack[j];
2060                                                 s[nnew + 1] = s[i];
2061                                                 readystem = pri;
2062                                                 sbottom = j;
2063                                                 if (ISDBG(MAINSTEMS))
2064                                                         fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n",
2065                                                                 stack[j].value, s[i].value, pri, nlps);
2066                                         }
2067                                 } else if (readystem == 3) {    /* that means also
2068                                                                  * pri==3 */
2069                                         /* choose the narrower stem */
2070                                         if (w1 > w2) {
2071                                                 s[nnew] = stack[j];
2072                                                 s[nnew + 1] = s[i];
2073                                                 sbottom = j + 1;
2074                                                 while (sbottom < nstack
2075                                                        && stack[sbottom].value <= stack[j].value)
2076                                                         sbottom++;
2077                                                 if (ISDBG(MAINSTEMS))
2078                                                         fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n",
2079                                                                 stack[j].value, s[i].value, pri, nlps);
2080                                         }
2081                                 } else if (pri == 3) {
2082                                         /*
2083                                          * we can replace as many stems as
2084                                          * neccessary
2085                                          */
2086                                         nnew += 2;
2087                                         while (nnew > 0 && s[nnew - 1].value >= stack[j].value) {
2088                                                 nnew -= 2;
2089                                                 if (ISDBG(MAINSTEMS))
2090                                                         fprintf(pfa_file, "%% -stem %d..%d\n",
2091                                                                 s[nnew].value, s[nnew + 1].value);
2092                                         }
2093                                         nlps = 0;
2094                                         s[nnew] = stack[j];
2095                                         s[nnew + 1] = s[i];
2096                                         readystem = pri;
2097                                         sbottom = j + 1;
2098                                         while (sbottom < nstack
2099                                                && stack[sbottom].value <= stack[j].value)
2100                                                 sbottom++;
2101                                         if (ISDBG(MAINSTEMS))
2102                                                 fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
2103                                                         stack[j].value, s[i].value, pri, nlps);
2104                                 }
2105                         }
2106                 }
2107         }
2108         if (readystem)
2109                 nnew += 2;
2110
2111         /* change the 1-pixel-wide stems to 20-pixel-wide stems if possible
2112          * the constant 20 is recommended in the Type1 manual
2113          */
2114         if(useblues) {
2115                 for(i=0; i<nnew; i+=2) {
2116                         if(s[i].value != s[i+1].value)
2117                                 continue;
2118                         if( ((s[i].flags ^ s[i+1].flags) & ST_BLUE)==0 )
2119                                 continue;
2120                         if( s[i].flags & ST_BLUE ) {
2121                                 if(nnew>i+2 && s[i+2].value<s[i].value+22)
2122                                         s[i+1].value=s[i+2].value-2; /* compensate for fuzziness */
2123                                 else
2124                                         s[i+1].value+=20;
2125                         } else {
2126                                 if(i>0 && s[i-1].value>s[i].value-22)
2127                                         s[i].value=s[i-1].value+2; /* compensate for fuzziness */
2128                                 else
2129                                         s[i].value-=20;
2130                         }
2131                 }
2132         }
2133         /* make sure that no stem it stretched between
2134          * a top zone and a bottom zone
2135          */
2136         if(useblues) {
2137                 for(i=0; i<nnew; i+=2) {
2138                         a=10000; /* lowest border of top zone crosing the stem */
2139                         b= -10000; /* highest border of bottom zone crossing the stem */
2140
2141                         for(j=2; j<nblues; j++) {
2142                                 c=bluevalues[j];
2143                                 if( c>=s[i].value && c<=s[i+1].value && c<a )
2144                                         a=c;
2145                         }
2146                         if(nblues>=2) {
2147                                 c=bluevalues[1];
2148                                 if( c>=s[i].value && c<=s[i+1].value && c>b )
2149                                         b=c;
2150                         }
2151                         for(j=1; j<notherb; j++) {
2152                                 c=otherblues[j];
2153                                 if( c>=s[i].value && c<=s[i+1].value && c>b )
2154                                         b=c;
2155                         }
2156                         if( a!=10000 && b!= -10000 ) { /* it is stretched */
2157                                 /* split the stem into 2 ghost stems */
2158                                 for(j=nnew+1; j>i+1; j--) /* make free space */
2159                                         s[j]=s[j-2];
2160                                 nnew+=2;
2161
2162                                 if(s[i].value+22 >= a)
2163                                         s[i+1].value=a-2; /* leave space for fuzziness */
2164                                 else
2165                                         s[i+1].value=s[i].value+20;
2166
2167                                 if(s[i+3].value-22 <= b)
2168                                         s[i+2].value=b+2; /* leave space for fuzziness */
2169                                 else
2170                                         s[i+2].value=s[i+3].value-20;
2171
2172                                 i+=2;
2173                         }
2174                 }
2175         }
2176         /* look for triple stems */
2177         for (i = 0; i < nnew; i += 2) {
2178                 if (nnew - i >= 6) {
2179                         a = s[i].value + s[i + 1].value;
2180                         b = s[i + 2].value + s[i + 3].value;
2181                         c = s[i + 4].value + s[i + 5].value;
2182
2183                         w1 = s[i + 1].value - s[i].value;
2184                         w2 = s[i + 3].value - s[i + 2].value;
2185                         w3 = s[i + 5].value - s[i + 4].value;
2186
2187                         fw = w3 - w1;   /* fuzz in width */
2188                         fd = ((c - b) - (b - a));       /* fuzz in distance
2189                                                          * (doubled) */
2190
2191                         /* we are able to handle some fuzz */
2192                         /*
2193                          * it doesn't hurt if the declared stem is a bit
2194                          * narrower than actual unless it's an edge in
2195                          * a blue zone
2196                          */
2197                         if (abs(abs(fd) - abs(fw)) * 5 < w2
2198                             && abs(fw) * 20 < (w1 + w3)) {      /* width dirrerence <10% */
2199
2200                                 if(useblues) { /* check that we don't disturb any blue stems */
2201                                         j=c; k=a;
2202                                         if (fw > 0) {
2203                                                 if (fd > 0) {
2204                                                         if( s[i+5].flags & ST_BLUE )
2205                                                                 continue;
2206                                                         j -= fw;
2207                                                 } else {
2208                                                         if( s[i+4].flags & ST_BLUE )
2209                                                                 continue;
2210                                                         j += fw;
2211                                                 }
2212                                         } else if(fw < 0) {
2213                                                 if (fd > 0) {
2214                                                         if( s[i+1].flags & ST_BLUE )
2215                                                                 continue;
2216                                                         k -= fw;
2217                                                 } else {
2218                                                         if( s[i].flags & ST_BLUE )
2219                                                                 continue;
2220                                                         k += fw;
2221                                                 }
2222                                         }
2223                                         pri = ((j - b) - (b - k));
2224
2225                                         if (pri > 0) {
2226                                                 if( s[i+2].flags & ST_BLUE )
2227                                                         continue;
2228                                         } else if(pri < 0) {
2229                                                 if( s[i+3].flags & ST_BLUE )
2230                                                         continue;
2231                                         }
2232                                 }
2233
2234                                 /*
2235                                  * first fix up the width of 1st and 3rd
2236                                  * stems
2237                                  */
2238                                 if (fw > 0) {
2239                                         if (fd > 0) {
2240                                                 s[i + 5].value -= fw;
2241                                                 c -= fw;
2242                                         } else {
2243                                                 s[i + 4].value += fw;
2244                                                 c += fw;
2245                                         }
2246                                 } else {
2247                                         if (fd > 0) {
2248                                                 s[i + 1].value -= fw;
2249                                                 a -= fw;
2250                                         } else {
2251                                                 s[i].value += fw;
2252                                                 a += fw;
2253                                         }
2254                                 }
2255                                 fd = ((c - b) - (b - a));
2256
2257                                 if (fd > 0) {
2258                                         s[i + 2].value += abs(fd) / 2;
2259                                 } else {
2260                                         s[i + 3].value -= abs(fd) / 2;
2261                                 }
2262
2263                                 s[i].flags |= ST_3;
2264                                 i += 4;
2265                         }
2266                 }
2267         }
2268
2269         return (nnew & ~1);     /* number of lines must be always even */
2270 }
2271
2272 /*
2273  * these macros and function allow to set the base stem,
2274  * check that it's not empty and subtract another stem
2275  * from the base stem (possibly dividing it into multiple parts)
2276  */
2277
2278 /* pairs for pieces of the base stem */
2279 static short xbstem[MAX_STEMS*2];
2280 /* index of the last point */
2281 static int xblast= -1;
2282
2283 #define setbasestem(from, to) \
2284         (xbstem[0]=from, xbstem[1]=to, xblast=1)
2285 #define isbaseempty()   (xblast<=0)
2286
2287 /* returns 1 if was overlapping, 0 otherwise */
2288 static int
2289 subfrombase(
2290         int from,
2291         int to
2292 )
2293 {
2294         int a, b;
2295         int i, j;
2296
2297         if(isbaseempty())
2298                 return 0;
2299
2300         /* handle the simple case simply */
2301         if(from > xbstem[xblast] || to < xbstem[0])
2302                 return 0;
2303
2304         /* the binary search may be more efficient */
2305         /* but for now the linear search is OK */
2306         for(b=1; from > xbstem[b]; b+=2) {} /* result: from <= xbstem[b] */
2307         for(a=xblast-1; to < xbstem[a]; a-=2) {} /* result: to >= xbstem[a] */
2308
2309         /* now the interesting examples are:
2310          * (it was hard for me to understand, so I looked at the examples)
2311          * 1
2312          *     a|-----|          |-----|b   |-----|     |-----|
2313          *              f|-----|t
2314          * 2
2315          *     a|-----|b         |-----|    |-----|     |-----|
2316          *      f|--|t
2317          * 3
2318          *     a|-----|b         |-----|    |-----|     |-----|
2319          *           f|-----|t
2320          * 4
2321          *      |-----|b        a|-----|    |-----|     |-----|
2322          *          f|------------|t
2323          * 5
2324          *      |-----|          |-----|b   |-----|    a|-----|
2325          *                   f|-----------------------------|t
2326          * 6
2327          *      |-----|b         |-----|    |-----|    a|-----|
2328          *   f|--------------------------------------------------|t
2329          * 7
2330          *      |-----|b         |-----|   a|-----|     |-----|
2331          *          f|--------------------------|t
2332          */
2333
2334         if(a < b-1) /* hits a gap  - example 1 */
2335                 return 0;
2336
2337         /* now the subtraction itself */
2338
2339         if(a==b-1 && from > xbstem[a] && to < xbstem[b]) {
2340                 /* overlaps with only one subrange and splits it - example 2 */
2341                 j=xblast; i=(xblast+=2);
2342                 while(j>=b)
2343                         xbstem[i--]=xbstem[j--];
2344                 xbstem[b]=from-1;
2345                 xbstem[b+1]=to+1;
2346                 return 1;
2347         /* becomes
2348          * 2a
2349          *     a|b   ||          |-----|    |-----|     |-----|
2350          *      f|--|t
2351          */
2352         }
2353
2354         if(xbstem[b-1] < from) {
2355                 /* cuts the back of this subrange - examples 3, 4, 7 */
2356                 xbstem[b] = from-1;
2357                 b+=2;
2358         /* becomes
2359          * 3a
2360          *     a|----|           |-----|b   |-----|     |-----|
2361          *           f|-----|t
2362          * 4a
2363          *      |---|           a|-----|b   |-----|     |-----|
2364          *          f|------------|t
2365          * 7a
2366          *      |---|            |-----|b  a|-----|     |-----|
2367          *          f|--------------------------|t
2368          */
2369         }
2370
2371         if(xbstem[a+1] > to) {
2372                 /* cuts the front of this subrange - examples 4a, 5, 7a */
2373                 xbstem[a] = to+1;
2374                 a-=2;
2375         /* becomes
2376          * 4b
2377          *     a|---|              |---|b   |-----|     |-----|
2378          *          f|------------|t
2379          * 5b
2380          *      |-----|          |-----|b  a|-----|          ||
2381          *                   f|-----------------------------|t
2382          * 7b
2383          *      |---|           a|-----|b        ||     |-----|
2384          *          f|--------------------------|t
2385          */
2386         }
2387
2388         if(a < b-1) /* now after modification it hits a gap - examples 3a, 4b */
2389                 return 1; /* because we have removed something */
2390
2391         /* now remove the subranges completely covered by the new stem */
2392         /* examples 5b, 6, 7b */
2393         i=b-1; j=a+2;
2394         /* positioned as:
2395          * 5b                    i                           j
2396          *      |-----|          |-----|b  a|-----|          ||
2397          *                   f|-----------------------------|t
2398          * 6    i                                             xblast  j
2399          *      |-----|b         |-----|    |-----|    a|-----|
2400          *   f|--------------------------------------------------|t
2401          * 7b                    i               j
2402          *      |---|           a|-----|b        ||     |-----|
2403          *          f|--------------------------|t
2404          */
2405         while(j <= xblast)
2406                 xbstem[i++]=xbstem[j++];
2407         xblast=i-1;
2408         return 1;
2409 }
2410
2411 /* for debugging */
2412 static void
2413 printbasestem(void)
2414 {
2415         int i;
2416
2417         printf("( ");
2418         for(i=0; i<xblast; i+=2)
2419                 printf("%d-%d ", xbstem[i], xbstem[i+1]);
2420         printf(") %d\n", xblast);
2421 }
2422
2423 /*
2424  * Join the stem borders to build the sets of substituted stems
2425  * XXX add consideration of the italic angle
2426  */
2427 static void
2428 joinsubstems(
2429           STEM * s,
2430           short *pairs,
2431           int nold,
2432           int useblues /* do we use the blue values ? */
2433 )
2434 {
2435         int i, j, x;
2436         static unsigned char mx[MAX_STEMS][MAX_STEMS];
2437
2438         /* we do the substituted groups of stems first
2439          * and it looks like it's going to be REALLY SLOW
2440          * AND PAINFUL but let's bother about it later
2441          */
2442
2443         /* for the substituted stems we don't bother about [hv]stem3 -
2444          * anyway the X11R6 rasterizer does not bother about hstem3
2445          * at all and is able to handle only one global vstem3
2446          * per glyph
2447          */
2448
2449         /* clean the used part of matrix */
2450         for(i=0; i<nold; i++)
2451                 for(j=0; j<nold; j++)
2452                         mx[i][j]=0;
2453
2454         /* build the matrix of stem pairs */
2455         for(i=0; i<nold; i++) {
2456                 if( s[i].flags & ST_ZONE )
2457                         continue;
2458                 if(s[i].flags & ST_BLUE)
2459                         mx[i][i]=1; /* allow to pair with itself if no better pair */
2460                 if(s[i].flags & ST_UP) { /* the down-stems are already matched */
2461                         setbasestem(s[i].from, s[i].to);
2462                         for(j=i+1; j<nold; j++) {
2463                                 if(s[i].value==s[j].value
2464                                 || s[j].flags & ST_ZONE ) {
2465                                         continue;
2466                                 }
2467                                 x=subfrombase(s[j].from, s[j].to);
2468
2469                                 if(s[j].flags & ST_UP) /* match only up+down pairs */
2470                                         continue;
2471
2472                                 mx[i][j]=mx[j][i]=x;
2473
2474                                 if(isbaseempty()) /* nothing else to do */
2475                                         break;
2476                         }
2477                 }
2478         }
2479
2480         if(ISDBG(SUBSTEMS)) {
2481                 fprintf(pfa_file, "%%     ");
2482                 for(j=0; j<nold; j++)
2483                         putc( j%10==0 ? '0'+(j/10)%10 : ' ', pfa_file);
2484                 fprintf(pfa_file, "\n%%     ");
2485                 for(j=0; j<nold; j++)
2486                         putc('0'+j%10, pfa_file);
2487                 putc('\n', pfa_file);
2488                 for(i=0; i<nold; i++) {
2489                         fprintf(pfa_file, "%% %3d ",i);
2490                         for(j=0; j<nold; j++)
2491                                 putc( mx[i][j] ? 'X' : '.', pfa_file);
2492                         putc('\n', pfa_file);
2493                 }
2494         }
2495
2496         /* now use the matrix to find the best pair for each stem */
2497         for(i=0; i<nold; i++) {
2498                 int pri, lastpri, v, f;
2499
2500                 x= -1; /* best pair: none */
2501                 lastpri=0;
2502
2503                 v=s[i].value;
2504                 f=s[i].flags;
2505
2506                 if(f & ST_ZONE) {
2507                         pairs[i]= -1;
2508                         continue;
2509                 }
2510
2511                 if(f & ST_UP) {
2512                         for(j=i+1; j<nold; j++) {
2513                                 if(mx[i][j]==0)
2514                                         continue;
2515
2516                                 if( (f | s[j].flags) & ST_END )
2517                                         pri=1;
2518                                 else if( (f | s[j].flags) & ST_FLAT )
2519                                         pri=3;
2520                                 else
2521                                         pri=2;
2522
2523                                 if(lastpri==0
2524                                 || pri > lastpri
2525                                 && ( lastpri==1 || s[j].value-v<20 || (s[x].value-v)*2 >= s[j].value-v ) ) {
2526                                         lastpri=pri;
2527                                         x=j;
2528                                 }
2529                         }
2530                 } else {
2531                         for(j=i-1; j>=0; j--) {
2532                                 if(mx[i][j]==0)
2533                                         continue;
2534
2535                                 if( (f | s[j].flags) & ST_END )
2536                                         pri=1;
2537                                 else if( (f | s[j].flags) & ST_FLAT )
2538                                         pri=3;
2539                                 else
2540                                         pri=2;
2541
2542                                 if(lastpri==0
2543                                 || pri > lastpri
2544                                 && ( lastpri==1 || v-s[j].value<20 || (v-s[x].value)*2 >= v-s[j].value ) ) {
2545                                         lastpri=pri;
2546                                         x=j;
2547                                 }
2548                         }
2549                 }
2550                 if(x== -1 && mx[i][i])
2551                         pairs[i]=i; /* a special case */
2552                 else
2553                         pairs[i]=x;
2554         }
2555
2556         if(ISDBG(SUBSTEMS)) {
2557                 for(i=0; i<nold; i++) {
2558                         j=pairs[i];
2559                         if(j>0)
2560                                 fprintf(pfa_file, "%% %d...%d  (%d x %d)\n", s[i].value, s[j].value, i, j);
2561                 }
2562         }
2563 }
2564
2565 /*
2566  * Make all the stems originating at the same value get the
2567  * same width. Without this the rasterizer may move the dots
2568  * randomly up or down by one pixel, and that looks bad.
2569  * The prioritisation is the same as in findstemat().
2570  */
2571 static void
2572 uniformstems(
2573           STEM * s,
2574           short *pairs,
2575           int ns
2576 )
2577 {
2578         int i, j, from, to, val, dir;
2579         int pri, prevpri[2], wd, prevwd[2], prevbest[2];
2580
2581         for(from=0; from<ns; from=to) {
2582                 prevpri[0] = prevpri[1] = 0;
2583                 prevwd[0] = prevwd[1] = 0;
2584                 prevbest[0] = prevbest[1] = -1;
2585                 val = s[from].value;
2586
2587                 for(to = from; to<ns && s[to].value == val; to++) {
2588                         dir = ((s[to].flags & ST_UP)!=0);
2589
2590                         i=pairs[to]; /* the other side of this stem */
2591                         if(i<0 || i==to)
2592                                 continue; /* oops, no other side */
2593                         wd=abs(s[i].value-val);
2594                         if(wd == 0)
2595                                 continue;
2596                         pri=1;
2597                         if( (s[to].flags | s[i].flags) & ST_END )
2598                                 pri=0;
2599                         if( prevbest[dir] == -1 || pri > prevpri[dir] || wd<prevwd[dir] ) {
2600                                 prevbest[dir]=i;
2601                                 prevpri[dir]=pri;
2602                                 prevwd[dir]=wd;
2603                         }
2604                 }
2605
2606                 for(i=from; i<to; i++) {
2607                         dir = ((s[i].flags & ST_UP)!=0);
2608                         if(prevbest[dir] >= 0) {
2609                                 if(ISDBG(SUBSTEMS)) {
2610                                         fprintf(stderr, "at %d (%s %d) pair %d->%d(%d)\n", i,
2611                                                 (dir ? "UP":"DOWN"), s[i].value, pairs[i], prevbest[dir],
2612                                                 s[prevbest[dir]].value);
2613                                 }
2614                                 pairs[i] = prevbest[dir];
2615                         }
2616                 }
2617         }
2618 }
2619
2620 /*
2621  * Find the best stem in the array at the specified (value, origin),
2622  * related to the entry ge.
2623  * Returns its index in the array sp, -1 means "none".
2624  * prevbest is the result for the other end of the line, we must
2625  * find something better than it or leave it as it is.
2626  */
2627 static int
2628 findstemat(
2629         int value,
2630         int origin,
2631         GENTRY *ge,
2632         STEM *sp,
2633         short *pairs,
2634         int ns,
2635         int prevbest /* -1 means "none" */
2636 )
2637 {
2638         int i, min, max;
2639         int v, si;
2640         int pri, prevpri; /* priority, 0 = has ST_END, 1 = no ST_END */
2641         int wd, prevwd; /* stem width */
2642
2643         si= -1; /* nothing yet */
2644
2645         /* stems are ordered by value, binary search */
2646         min=0; max=ns; /* min <= i < max */
2647         while( min < max ) {
2648                 i=(min+max)/2;
2649                 v=sp[i].value;
2650                 if(v<value)
2651                         min=i+1;
2652                 else if(v>value)
2653                         max=i;
2654                 else {
2655                         si=i; /* temporary value */
2656                         break;
2657                 }
2658         }
2659
2660         if( si < 0 ) /* found nothing this time */
2661                 return prevbest;
2662
2663         /* find the priority of the prevbest */
2664         /* we expect that prevbest has a pair */
2665         if(prevbest>=0) {
2666                 i=pairs[prevbest];
2667                 prevpri=1;
2668                 if( (sp[prevbest].flags | sp[i].flags) & ST_END )
2669                         prevpri=0;
2670                 prevwd=abs(sp[i].value-value);
2671         }
2672
2673         /* stems are not ordered by origin, so now do the linear search */
2674
2675         while( si>0 && sp[si-1].value==value ) /* find the first one */
2676                 si--;
2677
2678         for(; si<ns && sp[si].value==value; si++) {
2679                 if(sp[si].origin != origin)
2680                         continue;
2681                 if(sp[si].ge != ge) {
2682                         if(ISDBG(SUBSTEMS)) {
2683                                 fprintf(stderr,
2684                                         "dbg: possible self-intersection at v=%d o=%d exp_ge=0x%x ge=0x%x\n",
2685                                         value, origin, ge, sp[si].ge);
2686                         }
2687                         continue;
2688                 }
2689                 i=pairs[si]; /* the other side of this stem */
2690                 if(i<0)
2691                         continue; /* oops, no other side */
2692                 pri=1;
2693                 if( (sp[si].flags | sp[i].flags) & ST_END )
2694                         pri=0;
2695                 wd=abs(sp[i].value-value);
2696                 if( prevbest == -1 || pri >prevpri
2697                 || pri==prevpri && prevwd==0 || wd!=0 && wd<prevwd ) {
2698                         prevbest=si;
2699                         prevpri=pri;
2700                         prevwd=wd;
2701                         continue;
2702                 }
2703         }
2704
2705         return prevbest;
2706 }
2707
2708 /* add the substems for one glyph entry
2709  * (called from groupsubstems())
2710  * returns 0 if all OK, 1 if too many groups
2711  */
2712
2713 static int gssentry_lastgrp=0; /* reset to 0 for each new glyph */
2714
2715 static int
2716 gssentry( /* crazy number of parameters */
2717         GENTRY *ge,
2718         STEM *hs, /* horizontal stems, sorted by value */
2719         short *hpairs,
2720         int nhs,
2721         STEM *vs, /* vertical stems, sorted by value */
2722         short *vpairs,
2723         int nvs,
2724         STEMBOUNDS *s,
2725         short *egp,
2726         int *nextvsi,
2727         int *nexthsi /* -2 means "check by yourself" */
2728 ) {
2729         enum {
2730                 SI_VP,  /* vertical primary */
2731                 SI_HP,  /* horizontal primary */
2732                 SI_SIZE /* size of the array */
2733         };
2734         int si[SI_SIZE]; /* indexes of relevant stems */
2735
2736         /* the bounds of the existing relevant stems */
2737         STEMBOUNDS r[ sizeof(si) / sizeof(si[0]) * 2 ];
2738         char rexpand; /* by how much we need to expand the group */
2739         int nr; /* and the number of them */
2740
2741         /* yet more temporary storage */
2742         short lb, hb, isvert;
2743         int conflict, grp;
2744         int i, j, x, y;
2745
2746
2747         /* for each line or curve we try to find a horizontal and
2748          * a vertical stem corresponding to its first point
2749          * (corresponding to the last point of the previous
2750          * glyph entry), because the directions of the lines
2751          * will be eventually reversed and it will then become the last
2752          * point. And the T1 rasterizer applies the hints to
2753          * the last point.
2754          *
2755          */
2756
2757         /* start with the common part, the first point */
2758         x=ge->prev->ix3;
2759         y=ge->prev->iy3;
2760
2761         if(*nextvsi == -2)
2762                 si[SI_VP]=findstemat(x, y, ge, vs, vpairs, nvs, -1);
2763         else {
2764                 si[SI_VP]= *nextvsi; *nextvsi= -2;
2765         }
2766         if(*nexthsi == -2)
2767                 si[SI_HP]=findstemat(y, x, ge, hs, hpairs, nhs, -1);
2768         else {
2769                 si[SI_HP]= *nexthsi; *nexthsi= -2;
2770         }
2771
2772         /*
2773          * For the horizontal lines we make sure that both
2774          * ends of the line have the same horizontal stem,
2775          * and the same thing for vertical lines and stems.
2776          * In both cases we enforce the stem for the next entry.
2777          * Otherwise unpleasant effects may arise.
2778          */
2779
2780         if(ge->type==GE_LINE) {
2781                 if(ge->ix3==x) { /* vertical line */
2782                         *nextvsi=si[SI_VP]=findstemat(x, ge->iy3, ge->frwd, vs, vpairs, nvs, si[SI_VP]);
2783                 } else if(ge->iy3==y) { /* horizontal line */
2784                         *nexthsi=si[SI_HP]=findstemat(y, ge->ix3, ge->frwd, hs, hpairs, nhs, si[SI_HP]);
2785                 }
2786         }
2787
2788         if(si[SI_VP]+si[SI_HP] == -2) /* no stems, leave it alone */
2789                 return 0;
2790
2791         /* build the array of relevant bounds */
2792         nr=0;
2793         for(i=0; i< sizeof(si) / sizeof(si[0]); i++) {
2794                 STEM *sp;
2795                 short *pairs;
2796                 int step;
2797                 int f;
2798                 int nzones, firstzone, binzone, einzone;
2799                 int btype, etype;
2800
2801                 if(si[i] < 0)
2802                         continue;
2803
2804                 if(i<SI_HP) {
2805                         r[nr].isvert=1; sp=vs; pairs=vpairs;
2806                 } else {
2807                         r[nr].isvert=0; sp=hs; pairs=hpairs;
2808                 }
2809
2810                 r[nr].low=sp[ si[i] ].value;
2811                 r[nr].high=sp[ pairs[ si[i] ] ].value;
2812
2813                 if(r[nr].low > r[nr].high) {
2814                         j=r[nr].low; r[nr].low=r[nr].high; r[nr].high=j;
2815                         step= -1;
2816                 } else {
2817                         step=1;
2818                 }
2819
2820                 /* handle the interaction with Blue Zones */
2821
2822                 if(i>=SI_HP) { /* only for horizontal stems */
2823                         if(si[i]==pairs[si[i]]) {
2824                                 /* special case, the outermost stem in the
2825                                  * Blue Zone without a pair, simulate it to 20-pixel
2826                                  */
2827                                 if(sp[ si[i] ].flags & ST_UP) {
2828                                         r[nr].high+=20;
2829                                         for(j=si[i]+1; j<nhs; j++)
2830                                                 if( (sp[j].flags & (ST_ZONE|ST_TOPZONE))
2831                                                 == (ST_ZONE|ST_TOPZONE) ) {
2832                                                         if(r[nr].high > sp[j].value-2)
2833                                                                 r[nr].high=sp[j].value-2;
2834                                                         break;
2835                                                 }
2836                                 } else {
2837                                         r[nr].low-=20;
2838                                         for(j=si[i]-1; j>=0; j--)
2839                                                 if( (sp[j].flags & (ST_ZONE|ST_TOPZONE))
2840                                                 == (ST_ZONE) ) {
2841                                                         if(r[nr].low < sp[j].value+2)
2842                                                                 r[nr].low=sp[j].value+2;
2843                                                         break;
2844                                                 }
2845                                 }
2846                         }
2847
2848                         /* check that the stem borders don't end up in
2849                          * different Blue Zones */
2850                         f=sp[ si[i] ].flags;
2851                         nzones=0; einzone=binzone=0;
2852                         for(j=si[i]; j!=pairs[ si[i] ]; j+=step) {
2853                                 if( (sp[j].flags & ST_ZONE)==0 )
2854                                         continue;
2855                                 /* if see a zone border going in the same direction */
2856                                 if( ((f ^ sp[j].flags) & ST_UP)==0 ) {
2857                                         if( ++nzones == 1 ) {
2858                                                 firstzone=sp[j].value; /* remember the first one */
2859                                                 etype=sp[j].flags & ST_TOPZONE;
2860                                         }
2861                                         einzone=1;
2862
2863                                 } else { /* the opposite direction */
2864                                         if(nzones==0) { /* beginning is in a blue zone */
2865                                                 binzone=1;
2866                                                 btype=sp[j].flags & ST_TOPZONE;
2867                                         }
2868                                         einzone=0;
2869                                 }
2870                         }
2871
2872                         /* beginning and end are in Blue Zones of different types */
2873                         if( binzone && einzone && (btype ^ etype)!=0 ) {
2874                                 if( sp[si[i]].flags & ST_UP ) {
2875                                         if(firstzone > r[nr].low+22)
2876                                                 r[nr].high=r[nr].low+20;
2877                                         else
2878                                                 r[nr].high=firstzone-2;
2879                                 } else {
2880                                         if(firstzone < r[nr].high-22)
2881                                                 r[nr].low=r[nr].high-20;
2882                                         else
2883                                                 r[nr].low=firstzone+2;
2884                                 }
2885                         }
2886                 }
2887
2888                 if(ISDBG(SUBSTEMS))
2889                         fprintf(pfa_file, "%%  at(%d,%d)[%d,%d] %d..%d %c (%d x %d)\n", x, y, i, nr,
2890                                 r[nr].low, r[nr].high, r[nr].isvert ? 'v' : 'h',
2891                                 si[i], pairs[si[i]]);
2892
2893                 nr++;
2894         }
2895
2896         /* now try to find a group */
2897         conflict=0; /* no conflicts found yet */
2898         for(j=0; j<nr; j++)
2899                 r[j].already=0;
2900
2901         /* check if it fits into the last group */
2902         grp = gssentry_lastgrp;
2903         i = (grp==0)? 0 : egp[grp-1];
2904         for(; i<egp[grp]; i++) {
2905                 lb=s[i].low; hb=s[i].high; isvert=s[i].isvert;
2906                 for(j=0; j<nr; j++)
2907                         if( r[j].isvert==isvert  /* intersects */
2908                         && r[j].low <= hb && r[j].high >= lb ) {
2909                                 if( r[j].low == lb && r[j].high == hb ) /* coincides */
2910                                         r[j].already=1;
2911                                 else
2912                                         conflict=1;
2913                         }
2914
2915                 if(conflict)
2916                         break;
2917         }
2918
2919         if(conflict) { /* nope, check all the groups */
2920                 for(j=0; j<nr; j++)
2921                         r[j].already=0;
2922
2923                 for(i=0, grp=0; i<egp[NSTEMGRP-1]; i++) {
2924                         if(i == egp[grp]) { /* checked all stems in a group */
2925                                 if(conflict) {
2926                                         grp++; conflict=0; /* check the next group */
2927                                         for(j=0; j<nr; j++)
2928                                                 r[j].already=0;
2929                                 } else
2930                                         break; /* insert into this group */
2931                         }
2932
2933                         lb=s[i].low; hb=s[i].high; isvert=s[i].isvert;
2934                         for(j=0; j<nr; j++)
2935                                 if( r[j].isvert==isvert  /* intersects */
2936                                 && r[j].low <= hb && r[j].high >= lb ) {
2937                                         if( r[j].low == lb && r[j].high == hb ) /* coincides */
2938                                                 r[j].already=1;
2939                                         else
2940                                                 conflict=1;
2941                                 }
2942
2943                         if(conflict)
2944                                 i=egp[grp]-1; /* fast forward to the next group */
2945                 }
2946         }
2947
2948         /* do we have any empty group ? */
2949         if(conflict && grp < NSTEMGRP-1) {
2950                 grp++; conflict=0;
2951                 for(j=0; j<nr; j++)
2952                         r[j].already=0;
2953         }
2954
2955         if(conflict) { /* oops, can't find any group to fit */
2956                 return 1;
2957         }
2958
2959         /* OK, add stems to this group */
2960
2961         rexpand = nr;
2962         for(j=0; j<nr; j++)
2963                 rexpand -= r[j].already;
2964
2965         if(rexpand > 0) {
2966                 for(i=egp[NSTEMGRP-1]-1; i>=egp[grp]; i--)
2967                         s[i+rexpand]=s[i];
2968                 for(i=0; i<nr; i++)
2969                         if(!r[i].already)
2970                                 s[egp[grp]++]=r[i];
2971                 for(i=grp+1; i<NSTEMGRP; i++)
2972                         egp[i]+=rexpand;
2973         }
2974
2975         ge->stemid = gssentry_lastgrp = grp;
2976         return 0;
2977 }
2978
2979 /*
2980  * Create the groups of substituted stems from the list.
2981  * Each group will be represented by a subroutine in the Subs
2982  * array.
2983  */
2984
2985 static void
2986 groupsubstems(
2987         GLYPH *g,
2988         STEM *hs, /* horizontal stems, sorted by value */
2989         short *hpairs,
2990         int nhs,
2991         STEM *vs, /* vertical stems, sorted by value */
2992         short *vpairs,
2993         int nvs
2994 )
2995 {
2996         GENTRY *ge;
2997         int i, j;
2998
2999         /* temporary storage */
3000         STEMBOUNDS s[MAX_STEMS*2];
3001         /* indexes in there, pointing past the end each stem group */
3002         short egp[NSTEMGRP];
3003
3004         int nextvsi, nexthsi; /* -2 means "check by yourself" */
3005
3006         for(i=0; i<NSTEMGRP; i++)
3007                 egp[i]=0;
3008
3009         nextvsi=nexthsi= -2; /* processed no horiz/vert line */
3010
3011         gssentry_lastgrp = 0; /* reset the last group for new glyph */
3012
3013         for (ge = g->entries; ge != 0; ge = ge->next) {
3014                 if(ge->type!=GE_LINE && ge->type!=GE_CURVE) {
3015                         nextvsi=nexthsi= -2; /* next path is independent */
3016                         continue;
3017                 }
3018
3019                 if( gssentry(ge, hs, hpairs, nhs, vs, vpairs, nvs, s, egp, &nextvsi, &nexthsi) ) {
3020                         WARNING_2 fprintf(stderr, "*** glyph %s requires over %d hint subroutines, ignored them\n",
3021                                 g->name, NSTEMGRP);
3022                         /* it's better to have no substituted hints at all than have only part */
3023                         for (ge = g->entries; ge != 0; ge = ge->next)
3024                                 ge->stemid= -1;
3025                         g->nsg=0; /* just to be safe, already is 0 by initialization */
3026                         return;
3027                 }
3028
3029                 /*
3030                  * handle the last vert/horiz line of the path specially,
3031                  * correct the hint for the first entry of the path
3032                  */
3033                 if(ge->frwd != ge->next && (nextvsi != -2 || nexthsi != -2) ) {
3034                         if( gssentry(ge->frwd, hs, hpairs, nhs, vs, vpairs, nvs, s, egp, &nextvsi, &nexthsi) ) {
3035                                 WARNING_2 fprintf(stderr, "*** glyph %s requires over %d hint subroutines, ignored them\n",
3036                                         g->name, NSTEMGRP);
3037                                 /* it's better to have no substituted hints at all than have only part */
3038                                 for (ge = g->entries; ge != 0; ge = ge->next)
3039                                         ge->stemid= -1;
3040                                 g->nsg=0; /* just to be safe, already is 0 by initialization */
3041                                 return;
3042                         }
3043                 }
3044
3045         }
3046
3047         /* find the index of the first empty group - same as the number of groups */
3048         if(egp[0]>0) {
3049                 for(i=1; i<NSTEMGRP && egp[i]!=egp[i-1]; i++)
3050                         {}
3051                 g->nsg=i;
3052         } else
3053                 g->nsg=0;
3054
3055         if(ISDBG(SUBSTEMS)) {
3056                 fprintf(pfa_file, "%% %d substem groups (%d %d %d)\n", g->nsg,
3057                         g->nsg>1 ? egp[g->nsg-2] : -1,
3058                         g->nsg>0 ? egp[g->nsg-1] : -1,
3059                         g->nsg<NSTEMGRP ? egp[g->nsg] : -1 );
3060                 j=0;
3061                 for(i=0; i<g->nsg; i++) {
3062                         fprintf(pfa_file, "%% grp %3d:      ", i);
3063                         for(; j<egp[i]; j++) {
3064                                 fprintf(pfa_file, " %4d...%-4d %c  ", s[j].low, s[j].high,
3065                                         s[j].isvert ? 'v' : 'h');
3066                         }
3067                         fprintf(pfa_file, "\n");
3068                 }
3069         }
3070
3071         if(g->nsg==1) { /* it would be the same as the main stems */
3072                 /* so erase it */
3073                 for (ge = g->entries; ge != 0; ge = ge->next)
3074                         ge->stemid= -1;
3075                 g->nsg=0;
3076         }
3077
3078         if(g->nsg>0) {
3079                 if( (g->nsbs=malloc(g->nsg * sizeof (egp[0]))) == 0 ) {
3080                         fprintf(stderr, "**** not enough memory for substituted hints ****\n");
3081                         exit(255);
3082                 }
3083                 memmove(g->nsbs, egp, g->nsg * sizeof(short));
3084                 if( (g->sbstems=malloc(egp[g->nsg-1] * sizeof (s[0]))) == 0 ) {
3085                         fprintf(stderr, "**** not enough memory for substituted hints ****\n");
3086                         exit(255);
3087                 }
3088                 memmove(g->sbstems, s, egp[g->nsg-1] * sizeof(s[0]));
3089         }
3090 }
3091
3092 void
3093 buildstems(
3094            GLYPH * g
3095 )
3096 {
3097         STEM            hs[MAX_STEMS], vs[MAX_STEMS];   /* temporary working
3098                                                          * storage */
3099         short   hs_pairs[MAX_STEMS], vs_pairs[MAX_STEMS]; /* best pairs for these stems */
3100         STEM           *sp;
3101         GENTRY         *ge, *nge, *pge;
3102         int             nx, ny;
3103         int ovalue;
3104         int totals, grp, lastgrp;
3105
3106         assertisint(g, "buildstems int");
3107
3108         g->nhs = g->nvs = 0;
3109         memset(hs, 0, sizeof hs);
3110         memset(vs, 0, sizeof vs);
3111
3112         /* first search the whole character for possible stem points */
3113
3114         for (ge = g->entries; ge != 0; ge = ge->next) {
3115                 if (ge->type == GE_CURVE) {
3116
3117                         /*
3118                          * SURPRISE!
3119                          * We consider the stems bound by the
3120                          * H/V ends of the curves as flat ones.
3121                          *
3122                          * But we don't include the point on the
3123                          * other end into the range.
3124                          */
3125
3126                         /* first check the beginning of curve */
3127                         /* if it is horizontal, add a hstem */
3128                         if (ge->iy1 == ge->prev->iy3) {
3129                                 hs[g->nhs].value = ge->iy1;
3130
3131                                 if (ge->ix1 < ge->prev->ix3)
3132                                         hs[g->nhs].flags = ST_FLAT | ST_UP;
3133                                 else
3134                                         hs[g->nhs].flags = ST_FLAT;
3135
3136                                 hs[g->nhs].origin = ge->prev->ix3;
3137                                 hs[g->nhs].ge = ge;
3138
3139                                 if (ge->ix1 < ge->prev->ix3) {
3140                                         hs[g->nhs].from = ge->ix1+1;
3141                                         hs[g->nhs].to = ge->prev->ix3;
3142                                         if(hs[g->nhs].from > hs[g->nhs].to)
3143                                                 hs[g->nhs].from--;
3144                                 } else {
3145                                         hs[g->nhs].from = ge->prev->ix3;
3146                                         hs[g->nhs].to = ge->ix1-1;
3147                                         if(hs[g->nhs].from > hs[g->nhs].to)
3148                                                 hs[g->nhs].to++;
3149                                 }
3150                                 if (ge->ix1 != ge->prev->ix3)
3151                                         g->nhs++;
3152                         }
3153                         /* if it is vertical, add a vstem */
3154                         else if (ge->ix1 == ge->prev->ix3) {
3155                                 vs[g->nvs].value = ge->ix1;
3156
3157                                 if (ge->iy1 > ge->prev->iy3)
3158                                         vs[g->nvs].flags = ST_FLAT | ST_UP;
3159                                 else
3160                                         vs[g->nvs].flags = ST_FLAT;
3161
3162                                 vs[g->nvs].origin = ge->prev->iy3;
3163                                 vs[g->nvs].ge = ge;
3164
3165                                 if (ge->iy1 < ge->prev->iy3) {
3166                                         vs[g->nvs].from = ge->iy1+1;
3167                                         vs[g->nvs].to = ge->prev->iy3;
3168                                         if(vs[g->nvs].from > vs[g->nvs].to)
3169                                                 vs[g->nvs].from--;
3170                                 } else {
3171                                         vs[g->nvs].from = ge->prev->iy3;
3172                                         vs[g->nvs].to = ge->iy1-1;
3173                                         if(vs[g->nvs].from > vs[g->nvs].to)
3174                                                 vs[g->nvs].to++;
3175                                 }
3176
3177                                 if (ge->iy1 != ge->prev->iy3)
3178                                         g->nvs++;
3179                         }
3180                         /* then check the end of curve */
3181                         /* if it is horizontal, add a hstem */
3182                         if (ge->iy3 == ge->iy2) {
3183                                 hs[g->nhs].value = ge->iy3;
3184
3185                                 if (ge->ix3 < ge->ix2)
3186                                         hs[g->nhs].flags = ST_FLAT | ST_UP;
3187                                 else
3188                                         hs[g->nhs].flags = ST_FLAT;
3189
3190                                 hs[g->nhs].origin = ge->ix3;
3191                                 hs[g->nhs].ge = ge->frwd;
3192
3193                                 if (ge->ix3 < ge->ix2) {
3194                                         hs[g->nhs].from = ge->ix3;
3195                                         hs[g->nhs].to = ge->ix2-1;
3196                                         if( hs[g->nhs].from > hs[g->nhs].to )
3197                                                 hs[g->nhs].to++;
3198                                 } else {
3199                                         hs[g->nhs].from = ge->ix2+1;
3200                                         hs[g->nhs].to = ge->ix3;
3201                                         if( hs[g->nhs].from > hs[g->nhs].to )
3202                                                 hs[g->nhs].from--;
3203                                 }
3204
3205                                 if (ge->ix3 != ge->ix2)
3206                                         g->nhs++;
3207                         }
3208                         /* if it is vertical, add a vstem */
3209                         else if (ge->ix3 == ge->ix2) {
3210                                 vs[g->nvs].value = ge->ix3;
3211
3212                                 if (ge->iy3 > ge->iy2)
3213                                         vs[g->nvs].flags = ST_FLAT | ST_UP;
3214                                 else
3215                                         vs[g->nvs].flags = ST_FLAT;
3216
3217                                 vs[g->nvs].origin = ge->iy3;
3218                                 vs[g->nvs].ge = ge->frwd;
3219
3220                                 if (ge->iy3 < ge->iy2) {
3221                                         vs[g->nvs].from = ge->iy3;
3222                                         vs[g->nvs].to = ge->iy2-1;
3223                                         if( vs[g->nvs].from > vs[g->nvs].to )
3224                                                 vs[g->nvs].to++;
3225                                 } else {
3226                                         vs[g->nvs].from = ge->iy2+1;
3227                                         vs[g->nvs].to = ge->iy3;
3228                                         if( vs[g->nvs].from > vs[g->nvs].to )
3229                                                 vs[g->nvs].from--;
3230                                 }
3231
3232                                 if (ge->iy3 != ge->iy2)
3233                                         g->nvs++;
3234                         } else {
3235
3236                                 /*
3237                                  * check the end of curve for a not smooth
3238                                  * local extremum
3239                                  */
3240                                 nge = ge->frwd;
3241
3242                                 if (nge == 0)
3243                                         continue;
3244                                 else if (nge->type == GE_LINE) {
3245                                         nx = nge->ix3;
3246                                         ny = nge->iy3;
3247                                 } else if (nge->type == GE_CURVE) {
3248                                         nx = nge->ix1;
3249                                         ny = nge->iy1;
3250                                 } else
3251                                         continue;
3252
3253                                 /* check for vertical extremums */
3254                                 if (ge->iy3 > ge->iy2 && ge->iy3 > ny
3255                                 || ge->iy3 < ge->iy2 && ge->iy3 < ny) {
3256                                         hs[g->nhs].value = ge->iy3;
3257                                         hs[g->nhs].from
3258                                                 = hs[g->nhs].to
3259                                                 = hs[g->nhs].origin = ge->ix3;
3260                                         hs[g->nhs].ge = ge->frwd;
3261
3262                                         if (ge->ix3 < ge->ix2
3263                                             || nx < ge->ix3)
3264                                                 hs[g->nhs].flags = ST_UP;
3265                                         else
3266                                                 hs[g->nhs].flags = 0;
3267
3268                                         if (ge->ix3 != ge->ix2 || nx != ge->ix3)
3269                                                 g->nhs++;
3270                                 }
3271                                 /*
3272                                  * the same point may be both horizontal and
3273                                  * vertical extremum
3274                                  */
3275                                 /* check for horizontal extremums */
3276                                 if (ge->ix3 > ge->ix2 && ge->ix3 > nx
3277                                 || ge->ix3 < ge->ix2 && ge->ix3 < nx) {
3278                                         vs[g->nvs].value = ge->ix3;
3279                                         vs[g->nvs].from
3280                                                 = vs[g->nvs].to
3281                                                 = vs[g->nvs].origin = ge->iy3;
3282                                         vs[g->nvs].ge = ge->frwd;
3283
3284                                         if (ge->iy3 > ge->iy2
3285                                             || ny > ge->iy3)
3286                                                 vs[g->nvs].flags = ST_UP;
3287                                         else
3288                                                 vs[g->nvs].flags = 0;
3289
3290                                         if (ge->iy3 != ge->iy2 || ny != ge->iy3)
3291                                                 g->nvs++;
3292                                 }
3293                         }
3294
3295                 } else if (ge->type == GE_LINE) {
3296                         nge = ge->frwd;
3297
3298                         /* if it is horizontal, add a hstem */
3299                         /* and the ends as vstems if they brace the line */
3300                         if (ge->iy3 == ge->prev->iy3
3301                         && ge->ix3 != ge->prev->ix3) {
3302                                 hs[g->nhs].value = ge->iy3;
3303                                 if (ge->ix3 < ge->prev->ix3) {
3304                                         hs[g->nhs].flags = ST_FLAT | ST_UP;
3305                                         hs[g->nhs].from = ge->ix3;
3306                                         hs[g->nhs].to = ge->prev->ix3;
3307                                 } else {
3308                                         hs[g->nhs].flags = ST_FLAT;
3309                                         hs[g->nhs].from = ge->prev->ix3;
3310                                         hs[g->nhs].to = ge->ix3;
3311                                 }
3312                                 hs[g->nhs].origin = ge->ix3;
3313                                 hs[g->nhs].ge = ge->frwd;
3314
3315                                 pge = ge->bkwd;
3316
3317                                 /* add beginning as vstem */
3318                                 vs[g->nvs].value = pge->ix3;
3319                                 vs[g->nvs].origin
3320                                         = vs[g->nvs].from
3321                                         = vs[g->nvs].to = pge->iy3;
3322                                 vs[g->nvs].ge = ge;
3323
3324                                 if(pge->type==GE_CURVE)
3325                                         ovalue=pge->iy2;
3326                                 else
3327                                         ovalue=pge->prev->iy3;
3328
3329                                 if (pge->iy3 > ovalue)
3330                                         vs[g->nvs].flags = ST_UP | ST_END;
3331                                 else if (pge->iy3 < ovalue)
3332                                         vs[g->nvs].flags = ST_END;
3333                                 else
3334                                         vs[g->nvs].flags = 0;
3335
3336                                 if( vs[g->nvs].flags != 0 )
3337                                         g->nvs++;
3338
3339                                 /* add end as vstem */
3340                                 vs[g->nvs].value = ge->ix3;
3341                                 vs[g->nvs].origin
3342                                         = vs[g->nvs].from
3343                                         = vs[g->nvs].to = ge->iy3;
3344                                 vs[g->nvs].ge = ge->frwd;
3345
3346                                 if(nge->type==GE_CURVE)
3347                                         ovalue=nge->iy1;
3348                                 else
3349                                         ovalue=nge->iy3;
3350
3351                                 if (ovalue > ge->iy3)
3352                                         vs[g->nvs].flags = ST_UP | ST_END;
3353                                 else if (ovalue < ge->iy3)
3354                                         vs[g->nvs].flags = ST_END;
3355                                 else
3356                                         vs[g->nvs].flags = 0;
3357
3358                                 if( vs[g->nvs].flags != 0 )
3359                                         g->nvs++;
3360
3361                                 g->nhs++;
3362                         }
3363                         /* if it is vertical, add a vstem */
3364                         /* and the ends as hstems if they brace the line  */
3365                         else if (ge->ix3 == ge->prev->ix3
3366                         && ge->iy3 != ge->prev->iy3) {
3367                                 vs[g->nvs].value = ge->ix3;
3368                                 if (ge->iy3 > ge->prev->iy3) {
3369                                         vs[g->nvs].flags = ST_FLAT | ST_UP;
3370                                         vs[g->nvs].from = ge->prev->iy3;
3371                                         vs[g->nvs].to = ge->iy3;
3372                                 } else {
3373                                         vs[g->nvs].flags = ST_FLAT;
3374                                         vs[g->nvs].from = ge->iy3;
3375                                         vs[g->nvs].to = ge->prev->iy3;
3376                                 }
3377                                 vs[g->nvs].origin = ge->iy3;
3378                                 vs[g->nvs].ge = ge->frwd;
3379
3380                                 pge = ge->bkwd;
3381
3382                                 /* add beginning as hstem */
3383                                 hs[g->nhs].value = pge->iy3;
3384                                 hs[g->nhs].origin
3385                                         = hs[g->nhs].from
3386                                         = hs[g->nhs].to = pge->ix3;
3387                                 hs[g->nhs].ge = ge;
3388
3389                                 if(pge->type==GE_CURVE)
3390                                         ovalue=pge->ix2;
3391                                 else
3392                                         ovalue=pge->prev->ix3;
3393
3394                                 if (pge->ix3 < ovalue)
3395                                         hs[g->nhs].flags = ST_UP | ST_END;
3396                                 else if (pge->ix3 > ovalue)
3397                                         hs[g->nhs].flags = ST_END;
3398                                 else
3399                                         hs[g->nhs].flags = 0;
3400
3401                                 if( hs[g->nhs].flags != 0 )
3402                                         g->nhs++;
3403
3404                                 /* add end as hstem */
3405                                 hs[g->nhs].value = ge->iy3;
3406                                 hs[g->nhs].origin
3407                                         = hs[g->nhs].from
3408                                         = hs[g->nhs].to = ge->ix3;
3409                                 hs[g->nhs].ge = ge->frwd;
3410
3411                                 if(nge->type==GE_CURVE)
3412                                         ovalue=nge->ix1;
3413                                 else
3414                                         ovalue=nge->ix3;
3415
3416                                 if (ovalue < ge->ix3)
3417                                         hs[g->nhs].flags = ST_UP | ST_END;
3418                                 else if (ovalue > ge->ix3)
3419                                         hs[g->nhs].flags = ST_END;
3420                                 else
3421                                         hs[g->nhs].flags = 0;
3422
3423                                 if( hs[g->nhs].flags != 0 )
3424                                         g->nhs++;
3425
3426                                 g->nvs++;
3427                         }
3428                         /*
3429                          * check the end of line for a not smooth local
3430                          * extremum
3431                          */
3432                         nge = ge->frwd;
3433
3434                         if (nge == 0)
3435                                 continue;
3436                         else if (nge->type == GE_LINE) {
3437                                 nx = nge->ix3;
3438                                 ny = nge->iy3;
3439                         } else if (nge->type == GE_CURVE) {
3440                                 nx = nge->ix1;
3441                                 ny = nge->iy1;
3442                         } else
3443                                 continue;
3444
3445                         /* check for vertical extremums */
3446                         if (ge->iy3 > ge->prev->iy3 && ge->iy3 > ny
3447                         || ge->iy3 < ge->prev->iy3 && ge->iy3 < ny) {
3448                                 hs[g->nhs].value = ge->iy3;
3449                                 hs[g->nhs].from
3450                                         = hs[g->nhs].to
3451                                         = hs[g->nhs].origin = ge->ix3;
3452                                 hs[g->nhs].ge = ge->frwd;
3453
3454                                 if (ge->ix3 < ge->prev->ix3
3455                                     || nx < ge->ix3)
3456                                         hs[g->nhs].flags = ST_UP;
3457                                 else
3458                                         hs[g->nhs].flags = 0;
3459
3460                                 if (ge->ix3 != ge->prev->ix3 || nx != ge->ix3)
3461                                         g->nhs++;
3462                         }
3463                         /*
3464                          * the same point may be both horizontal and vertical
3465                          * extremum
3466                          */
3467                         /* check for horizontal extremums */
3468                         if (ge->ix3 > ge->prev->ix3 && ge->ix3 > nx
3469                         || ge->ix3 < ge->prev->ix3 && ge->ix3 < nx) {
3470                                 vs[g->nvs].value = ge->ix3;
3471                                 vs[g->nvs].from
3472                                         = vs[g->nvs].to
3473                                         = vs[g->nvs].origin = ge->iy3;
3474                                 vs[g->nvs].ge = ge->frwd;
3475
3476                                 if (ge->iy3 > ge->prev->iy3
3477                                     || ny > ge->iy3)
3478                                         vs[g->nvs].flags = ST_UP;
3479                                 else
3480                                         vs[g->nvs].flags = 0;
3481
3482                                 if (ge->iy3 != ge->prev->iy3 || ny != ge->iy3)
3483                                         g->nvs++;
3484                         }
3485                 }
3486         }
3487
3488         g->nhs=addbluestems(hs, g->nhs);
3489         sortstems(hs, g->nhs);
3490         sortstems(vs, g->nvs);
3491
3492         if (ISDBG(STEMS))
3493                 debugstems(g->name, hs, g->nhs, vs, g->nvs);
3494
3495         /* find the stems interacting with the Blue Zones */
3496         markbluestems(hs, g->nhs);
3497
3498         if(subhints) {
3499                 if (ISDBG(SUBSTEMS))
3500                         fprintf(pfa_file, "%% %s: joining subst horizontal stems\n", g->name);
3501                 joinsubstems(hs, hs_pairs, g->nhs, 1);
3502                 uniformstems(hs, hs_pairs, g->nhs);
3503
3504                 if (ISDBG(SUBSTEMS))
3505                         fprintf(pfa_file, "%% %s: joining subst vertical stems\n", g->name);
3506                 joinsubstems(vs, vs_pairs, g->nvs, 0);
3507
3508                 groupsubstems(g, hs, hs_pairs, g->nhs, vs, vs_pairs, g->nvs);
3509         }
3510
3511         if (ISDBG(MAINSTEMS))
3512                 fprintf(pfa_file, "%% %s: joining main horizontal stems\n", g->name);
3513         g->nhs = joinmainstems(hs, g->nhs, 1);
3514         if (ISDBG(MAINSTEMS))
3515                 fprintf(pfa_file, "%% %s: joining main vertical stems\n", g->name);
3516         g->nvs = joinmainstems(vs, g->nvs, 0);
3517
3518         if (ISDBG(MAINSTEMS))
3519                 debugstems(g->name, hs, g->nhs, vs, g->nvs);
3520
3521         if(g->nhs > 0) {
3522                 if ((sp = malloc(sizeof(STEM) * g->nhs)) == 0) {
3523                         fprintf(stderr, "**** not enough memory for hints ****\n");
3524                         exit(255);
3525                 }
3526                 g->hstems = sp;
3527                 memcpy(sp, hs, sizeof(STEM) * g->nhs);
3528         } else
3529                 g->hstems = 0;
3530
3531         if(g->nvs > 0) {
3532                 if ((sp = malloc(sizeof(STEM) * g->nvs)) == 0) {
3533                         fprintf(stderr, "**** not enough memory for hints ****\n");
3534                         exit(255);
3535                 }
3536                 g->vstems = sp;
3537                 memcpy(sp, vs, sizeof(STEM) * g->nvs);
3538         } else
3539                 g->vstems = 0;
3540
3541         /* now check that the stems won't overflow the interpreter's stem stack:
3542          * some interpreters (like X11) push the stems on each change into
3543          * stack and pop them only after the whole glyphs is completed.
3544          */
3545
3546         totals = (g->nhs+g->nvs) / 2; /* we count whole stems, not halves */
3547         lastgrp = -1;
3548
3549         for (ge = g->entries; ge != 0; ge = ge->next) {
3550                 grp=ge->stemid;
3551                 if(grp >= 0 && grp != lastgrp)  {
3552                         if(grp==0)
3553                                 totals += g->nsbs[0];
3554                         else
3555                                 totals += g->nsbs[grp] - g->nsbs[grp-1];
3556
3557                         lastgrp = grp;
3558                 }
3559         }
3560
3561         /* be on the safe side, check for >= , not > */
3562         if(totals >= max_stemdepth) {  /* oops, too deep */
3563                 WARNING_2 {
3564                         fprintf(stderr, "Warning: glyph %s needs hint stack depth %d\n", g->name, totals);
3565                         fprintf(stderr, "  (limit %d): removed the substituted hints from it\n", max_stemdepth);
3566                 }
3567                 if(g->nsg > 0) {
3568                         for (ge = g->entries; ge != 0; ge = ge->next)
3569                                 ge->stemid = -1;
3570                         free(g->sbstems); g->sbstems = 0;
3571                         free(g->nsbs); g->nsbs = 0;
3572                         g->nsg = 0;
3573                 }
3574         }
3575
3576         /* now check if there are too many main stems */
3577         totals = (g->nhs+g->nvs) / 2; /* we count whole stems, not halves */
3578         if(totals >= max_stemdepth) {
3579                 /* even worse, too much of non-substituted stems */
3580                 WARNING_2 {
3581                         fprintf(stderr, "Warning: glyph %s has %d main hints\n", g->name, totals);
3582                         fprintf(stderr, "  (limit %d): removed the hints from it\n", max_stemdepth);
3583                 }
3584                 if(g->vstems) {
3585                         free(g->vstems); g->vstems = 0; g->nvs = 0;
3586                 }
3587                 if(g->hstems) {
3588                         free(g->hstems); g->hstems = 0; g->nhs = 0;
3589                 }
3590         }
3591 }
3592
3593 /* convert weird curves that are close to lines into lines.
3594 */
3595
3596 void
3597 fstraighten(
3598            GLYPH * g
3599 )
3600 {
3601         GENTRY         *ge, *pge, *nge, *ige;
3602         double          df;
3603         int             dir;
3604         double          iln, oln;
3605         int             svdir, i, o;
3606
3607         for (ige = g->entries; ige != 0; ige = ige->next) {
3608                 if (ige->type != GE_CURVE)
3609                         continue;
3610
3611                 ge = ige;
3612                 pge = ge->bkwd;
3613                 nge = ge->frwd;
3614
3615                 df = 0.;
3616
3617                 /* look for vertical then horizontal */
3618                 for(i=0; i<2; i++) {
3619                         o = !i; /* other axis */
3620
3621                         iln = fabs(ge->fpoints[i][2] - pge->fpoints[i][2]);
3622                         oln = fabs(ge->fpoints[o][2] - pge->fpoints[o][2]);
3623                         /*
3624                          * if current curve is almost a vertical line, and it
3625                          * doesn't begin or end horizontally (and the prev/next
3626                          * line doesn't join smoothly ?)
3627                          */
3628                         if( oln < 1.
3629                         || ge->fpoints[o][2] == ge->fpoints[o][1]
3630                         || ge->fpoints[o][0] == pge->fpoints[o][2]
3631                         || iln > 2.
3632                         || iln > 1.  && iln/oln > 0.1 )
3633                                 continue;
3634
3635
3636                         if(ISDBG(STRAIGHTEN))
3637                                 fprintf(stderr,"** straighten almost %s\n", (i? "horizontal":"vertical"));
3638
3639                         df = ge->fpoints[i][2] - pge->fpoints[i][2];
3640                         dir = fsign(ge->fpoints[o][2] - pge->fpoints[o][2]);
3641                         ge->type = GE_LINE;
3642
3643                         /*
3644                          * suck in all the sequence of such almost lines
3645                          * going in the same direction but not deviating
3646                          * too far from vertical
3647                          */
3648                         iln = fabs(nge->fpoints[i][2] - ge->fpoints[i][2]);
3649                         oln = nge->fpoints[o][2] - ge->fpoints[o][2];
3650
3651                         while (fabs(df) <= 5 && nge->type == GE_CURVE
3652                         && dir == fsign(oln) /* that also gives oln != 0 */
3653                         && iln <= 2.
3654                         && ( iln <= 1.  || iln/fabs(oln) <= 0.1 ) ) {
3655                                 ge->fx3 = nge->fx3;
3656                                 ge->fy3 = nge->fy3;
3657
3658                                 if(ISDBG(STRAIGHTEN))
3659                                         fprintf(stderr,"** straighten collapsing %s\n", (i? "horizontal":"vertical"));
3660                                 freethisge(nge);
3661                                 fixendpath(ge);
3662                                 pge = ge->bkwd;
3663                                 nge = ge->frwd;
3664
3665                                 df = ge->fpoints[i][2] - pge->fpoints[i][2];
3666
3667                                 iln = fabs(nge->fpoints[i][2] - ge->fpoints[i][2]);
3668                                 oln = nge->fpoints[o][2] - ge->fpoints[o][2];
3669                         }
3670
3671                         /* now check what do we have as previous/next line */
3672
3673                         if(ge != pge) {
3674                                 if( pge->type == GE_LINE && pge->fpoints[i][2] == pge->prev->fpoints[i][2]
3675                                 && fabs(pge->fpoints[o][2] != pge->prev->fpoints[o][2]) ) {
3676                                         if(ISDBG(STRAIGHTEN)) fprintf(stderr,"** straighten join with previous 0x%x 0x%x\n", pge, ge);
3677                                         /* join the previous line with current */
3678                                         pge->fx3 = ge->fx3;
3679                                         pge->fy3 = ge->fy3;
3680
3681                                         ige = freethisge(ge)->prev; /* keep the iterator valid */
3682                                         ge = pge;
3683                                         fixendpath(ge);
3684                                         pge = ge->bkwd;
3685                                 }
3686                         }
3687
3688                         if(ge != nge) {
3689                                 if (nge->type == GE_LINE && nge->fpoints[i][2] == ge->fpoints[i][2]
3690                                 && fabs(nge->fpoints[o][2] != ge->fpoints[o][2]) ) {
3691                                         if(ISDBG(STRAIGHTEN)) fprintf(stderr,"** straighten join with next 0x%x 0x%x\n", ge, nge);
3692                                         /* join the next line with current */
3693                                         ge->fx3 = nge->fx3;
3694                                         ge->fy3 = nge->fy3;
3695
3696                                         freethisge(nge);
3697                                         fixendpath(ge);
3698                                         pge = ge->bkwd;
3699                                         nge = ge->frwd;
3700
3701                                 }
3702                         }
3703
3704                         if(ge != pge) {
3705                                 /* try to align the lines if neccessary */
3706                                 if(df != 0.)
3707                                         fclosegap(ge, ge, i, df, NULL);
3708                         } else {
3709                                 /* contour consists of only one line, get rid of it */
3710                                 ige = freethisge(ge)->prev; /* keep the iterator valid */
3711                         }
3712
3713                         break; /* don't bother looking at the other axis */
3714                 }
3715         }
3716 }
3717
3718 /* solve a square equation,
3719  * returns the number of solutions found, the solutions
3720  * are stored in res which should point to array of two doubles.
3721  * min and max limit the area for solutions
3722  */
3723
3724 static int
3725 fsqequation(
3726         double a,
3727         double b,
3728         double c,
3729         double *res,
3730         double min,
3731         double max
3732 )
3733 {
3734         double D;
3735         int n;
3736
3737         if(ISDBG(SQEQ)) fprintf(stderr, "sqeq(%g,%g,%g) [%g;%g]\n", a, b, c, min, max);
3738
3739         if(fabs(a) < 0.000001) { /* if a linear equation */
3740                 n=0;
3741                 if(fabs(b) < 0.000001) /* not an equation at all */
3742                         return 0;
3743                 res[0] = -c/b;
3744                 if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: linear t=%g\n", res[0]);
3745                 if(res[0] >= min && res[0] <= max)
3746                         n++;
3747                 return n;
3748         }
3749
3750         D = b*b - 4.0*a*c;
3751         if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: D=%g\n", D);
3752         if(D<0)
3753                 return 0;
3754
3755         D = sqrt(D);
3756
3757         n=0;
3758         res[0] = (-b+D) / (2*a);
3759         if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: t1=%g\n", res[0]);
3760         if(res[0] >= min && res[0] <= max)
3761                 n++;
3762
3763         res[n] = (-b-D) / (2*a);
3764         if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: t2=%g\n", res[n]);
3765         if(res[n] >= min && res[n] <= max)
3766                 n++;
3767
3768         /* return 2nd solution only if it's different enough */
3769         if(n==2 && fabs(res[0]-res[1])<0.000001)
3770                 n=1;
3771
3772         return n;
3773 }
3774
3775 /* check that the curves don't cross quadrant boundary */
3776 /* (float) */
3777
3778 /*
3779   Here we make sure that the curve does not continue past
3780   horizontal or vertical extremums. The horizontal points are
3781   explained, vertical points are by analogy.
3782
3783   The horizontal points are where the derivative
3784   dy/dx is equal to 0. But the Bezier curves are defined by
3785   parametric formulas
3786    x=fx(t)
3787    y=fy(t)
3788   so finding this derivative is complicated.
3789   Also even if we find some point (x,y) splitting at this point
3790   is far not obvious. Fortunately we can use dy/dt = 0 instead,
3791   this gets to a rather simple square equation and splitting
3792   at a known value of t is simple.
3793
3794   The formulas are:
3795
3796   y = A*(1-t)^3 + 3*B*(1-t)^2*t + 3*C*(1-t)*t^2 + D*t^3
3797   y = (-A+3*B-3*C+D)*t^3 + (3*A-6*B+3*C)*t^2 + (-3*A+3*B)*t + A
3798   dy/dt = 3*(-A+3*B-3*C+D)*t^2 + 2*(3*A-6*B+3*C)*t + (-3*A+3*B)
3799  */
3800
3801 void
3802 ffixquadrants(
3803         GLYPH *g
3804 )
3805 {
3806         GENTRY         *ge, *nge;
3807         int     i, j, np, oldnp;
3808         double  sp[5]; /* split points, last one empty */
3809         char dir[5]; /* for debugging, direction by which split happened */
3810         double a, b, *pts; /* points of a curve */
3811
3812         for (ge = g->entries; ge != 0; ge = ge->next) {
3813                 if (ge->type != GE_CURVE)
3814                         continue;
3815
3816         doagain:
3817                 np = 0; /* no split points yet */
3818                 if(ISDBG(QUAD)) {
3819                         fprintf(stderr, "%s: trying 0x%x (%g %g) (%g %g) (%g %g) (%g %g)\n  ", g->name,
3820                                 ge,  ge->prev->fx3, ge->prev->fy3, ge->fx1, ge->fy1, ge->fx2, ge->fy2,
3821                                 ge->fx3, ge->fy3);
3822                 }
3823                 for(i=0; i<2; i++) { /* first for x then for y */
3824                         /* find the cooridnates of control points */
3825                         a = ge->prev->fpoints[i][2];
3826                         pts = &ge->fpoints[i][0];
3827
3828                         oldnp = np;
3829                         np += fsqequation(
3830                                 3.0*(-a + 3.0*pts[0] - 3.0*pts[1] + pts[2]),
3831                                 6.0*(a - 2.0*pts[0] + pts[1]),
3832                                 3.0*(-a + pts[0]),
3833                                 &sp[np],
3834                                 0.0, 1.0); /* XXX range is [0;1] */
3835
3836                         if(np == oldnp)
3837                                 continue;
3838
3839                         if(ISDBG(QUAD))
3840                                 fprintf(stderr, "%s: 0x%x: %d pts(%c): ",
3841                                         g->name, ge, np-oldnp, i? 'y':'x');
3842
3843                         /* remove points that are too close to the ends
3844                          * because hor/vert ends are permitted, also
3845                          * if the split point is VERY close to the ends
3846                          * but not exactly then just flatten it and check again.
3847                          */
3848                         for(j = oldnp; j<np; j++) {
3849                                 dir[j] = i;
3850                                 if(ISDBG(QUAD))
3851                                         fprintf(stderr, "%g ", sp[j]);
3852                                 if(sp[j] < 0.03) { /* front end of curve */
3853                                         if(ge->fpoints[i][0] != ge->prev->fpoints[i][2]) {
3854                                                 ge->fpoints[i][0] = ge->prev->fpoints[i][2];
3855                                                 if(ISDBG(QUAD)) fprintf(stderr, "flattened at front\n");
3856                                                 goto doagain;
3857                                         }
3858                                         if( ge->fpoints[i][1] != ge->fpoints[i][0]
3859                                         && fsign(ge->fpoints[i][2] - ge->fpoints[i][1])
3860                                                         != fsign(ge->fpoints[i][1] - ge->fpoints[i][0]) ) {
3861                                                 ge->fpoints[i][1] = ge->fpoints[i][0];
3862                                                 if(ISDBG(QUAD)) fprintf(stderr, "flattened zigzag at front\n");
3863                                                 goto doagain;
3864                                         }
3865                                         sp[j] = sp[j+1]; np--; j--;
3866                                         if(ISDBG(QUAD)) fprintf(stderr, "(front flat)  ");
3867                                 } else if(sp[j] > 0.97) { /* rear end of curve */
3868                                         if(ge->fpoints[i][1] != ge->fpoints[i][2]) {
3869                                                 ge->fpoints[i][1] = ge->fpoints[i][2];
3870                                                 if(ISDBG(QUAD)) fprintf(stderr, "flattened at rear\n");
3871                                                 goto doagain;
3872                                         }
3873                                         if( ge->fpoints[i][0] != ge->fpoints[i][1]
3874                                         && fsign(ge->prev->fpoints[i][2] - ge->fpoints[i][0])
3875                                                         != fsign(ge->fpoints[i][0] - ge->fpoints[i][1]) ) {
3876                                                 ge->fpoints[i][0] = ge->fpoints[i][1];
3877                                                 if(ISDBG(QUAD)) fprintf(stderr, "flattened zigzag at rear\n");
3878                                                 goto doagain;
3879                                         }
3880                                         sp[j] = sp[j+1]; np--; j--;
3881                                         if(ISDBG(QUAD)) fprintf(stderr, "(rear flat)  ");
3882                                 }
3883                         }
3884                         if(ISDBG(QUAD)) fprintf(stderr, "\n");
3885                 }
3886
3887                 if(np==0) /* no split points, leave it alone */
3888                         continue;
3889
3890                 if(ISDBG(QUAD)) {
3891                         fprintf(stderr, "%s: splitting 0x%x (%g %g) (%g %g) (%g %g) (%g %g) at %d points\n  ", g->name,
3892                                 ge,  ge->prev->fx3, ge->prev->fy3, ge->fx1, ge->fy1, ge->fx2, ge->fy2,
3893                                 ge->fx3, ge->fy3, np);
3894                         for(i=0; i<np; i++)
3895                                 fprintf(stderr, "%g(%c) ", sp[i], dir[i] ? 'y':'x');
3896                         fprintf(stderr, "\n");
3897                 }
3898
3899                 /* sort the points ascending */
3900                 for(i=0; i<np; i++)
3901                         for(j=i+1; j<np; j++)
3902                                 if(sp[i] > sp[j]) {
3903                                         a = sp[i]; sp[i] = sp[j]; sp[j] = a;
3904                                 }
3905
3906                 /* now finally do the split on each point */
3907                 for(j=0; j<np; j++) {
3908                         double k1, k2, c;
3909
3910                         k1 = sp[j];
3911                         k2 = 1 - k1;
3912
3913                         if(ISDBG(QUAD)) fprintf(stderr, "   0x%x %g/%g\n", ge, k1, k2);
3914
3915                         nge = newgentry(GEF_FLOAT);
3916                         (*nge) = (*ge);
3917
3918 #define SPLIT(pt1, pt2) ( (pt1) + k1*((pt2)-(pt1)) ) /* order is important! */
3919                         for(i=0; i<2; i++) { /* for x and y */
3920                                 a = ge->fpoints[i][0]; /* get the middle points */
3921                                 b = ge->fpoints[i][1];
3922
3923                                 /* calculate new internal points */
3924                                 c = SPLIT(a, b);
3925
3926                                 ge->fpoints[i][0] = SPLIT(ge->prev->fpoints[i][2], a);
3927                                 ge->fpoints[i][1] = SPLIT(ge->fpoints[i][0], c);
3928
3929                                 nge->fpoints[i][1] = SPLIT(b, nge->fpoints[i][2]);
3930                                 nge->fpoints[i][0] = SPLIT(c, nge->fpoints[i][1]);
3931
3932                                 ge->fpoints[i][2] = SPLIT(ge->fpoints[i][1],
3933                                         + nge->fpoints[i][0]);
3934                         }
3935 #undef SPLIT
3936
3937                         addgeafter(ge, nge);
3938
3939                         /* go to the next part, adjust remaining points */
3940                         ge = nge;
3941                         for(i=j+1; i<np; i++)
3942                                 sp[i] = (sp[i]-k1) / k2;
3943                 }
3944         }
3945
3946 }
3947
3948 /* check if a curve is a zigzag */
3949
3950 static int
3951 iiszigzag(
3952         GENTRY *ge
3953 )
3954 {
3955         double          k, k1, k2;
3956         double          a, b;
3957
3958         if (ge->type != GE_CURVE)
3959                 return 0;
3960
3961         a = ge->iy2 - ge->iy1;
3962         b = ge->ix2 - ge->ix1;
3963         k = fabs(a == 0 ? (b == 0 ? 1. : FBIGVAL) : (double) b / (double) a);
3964         a = ge->iy1 - ge->prev->iy3;
3965         b = ge->ix1 - ge->prev->ix3;
3966         k1 = fabs(a == 0 ? (b == 0 ? 1. : FBIGVAL) : (double) b / (double) a);
3967         a = ge->iy3 - ge->iy2;
3968         b = ge->ix3 - ge->ix2;
3969         k2 = fabs(a == 0 ? (b == 0 ? 1. : FBIGVAL) : (double) b / (double) a);
3970
3971         /* if the curve is not a zigzag */
3972         if (k1 >= k && k2 <= k || k1 <= k && k2 >= k)
3973                 return 0;
3974         else
3975                 return 1;
3976 }
3977
3978 /* check if a curve is a zigzag - floating */
3979
3980 static int
3981 fiszigzag(
3982         GENTRY *ge
3983 )
3984 {
3985         double          k, k1, k2;
3986         double          a, b;
3987
3988         if (ge->type != GE_CURVE)
3989                 return 0;
3990
3991         a = fabs(ge->fy2 - ge->fy1);
3992         b = fabs(ge->fx2 - ge->fx1);
3993         k = a < FEPS ? (b <FEPS ? 1. : FBIGVAL) : b / a;
3994         a = fabs(ge->fy1 - ge->prev->fy3);
3995         b = fabs(ge->fx1 - ge->prev->fx3);
3996         k1 = a < FEPS ? (b < FEPS ? 1. : FBIGVAL) : b / a;
3997         a = fabs(ge->fy3 - ge->fy2);
3998         b = fabs(ge->fx3 - ge->fx2);
3999         k2 = a < FEPS ? (b <FEPS ? 1. : FBIGVAL) : b / a;
4000
4001         /* if the curve is not a zigzag */
4002         if (k1 >= k && k2 <= k || k1 <= k && k2 >= k)
4003                 return 0;
4004         else
4005                 return 1;
4006 }
4007
4008 /* split the zigzag-like curves into two parts */
4009
4010 void
4011 fsplitzigzags(
4012              GLYPH * g
4013 )
4014 {
4015         GENTRY         *ge, *nge;
4016         double          a, b, c, d;
4017
4018         assertisfloat(g, "splitting zigzags");
4019         for (ge = g->entries; ge != 0; ge = ge->next) {
4020                 if (ge->type != GE_CURVE)
4021                         continue;
4022
4023                 /* if the curve is not a zigzag */
4024                 if ( !fiszigzag(ge) ) {
4025                         continue;
4026                 }
4027
4028                 /* split the curve by t=0.5 */
4029                 nge = newgentry(GEF_FLOAT);
4030                 (*nge) = (*ge);
4031                 nge->type = GE_CURVE;
4032
4033                 a = ge->prev->fx3;
4034                 b = ge->fx1;
4035                 c = ge->fx2;
4036                 d = ge->fx3;
4037                 nge->fx3 = d;
4038                 nge->fx2 = (c + d) / 2.;
4039                 nge->fx1 = (b + 2. * c + d) / 4.;
4040                 ge->fx3 = (a + b * 3. + c * 3. + d) / 8.;
4041                 ge->fx2 = (a + 2. * b + c) / 4.;
4042                 ge->fx1 = (a + b) / 2.;
4043
4044                 a = ge->prev->fy3;
4045                 b = ge->fy1;
4046                 c = ge->fy2;
4047                 d = ge->fy3;
4048                 nge->fy3 = d;
4049                 nge->fy2 = (c + d) / 2.;
4050                 nge->fy1 = (b + 2. * c + d) / 4.;
4051                 ge->fy3 = (a + b * 3. + c * 3. + d) / 8.;
4052                 ge->fy2 = (a + 2. * b + c) / 4.;
4053                 ge->fy1 = (a + b) / 2.;
4054
4055                 addgeafter(ge, nge);
4056         }
4057 }
4058
4059 /* free this GENTRY, returns what was ge->next
4060  * (ge must be of type GE_LINE or GE_CURVE)
4061  * works on both float and int entries
4062  */
4063
4064 static GENTRY *
4065 freethisge(
4066         GENTRY *ge
4067 )
4068 {
4069         GENTRY *xge;
4070
4071         if (ge->bkwd != ge->prev) {
4072                 /* at beginning of the contour */
4073
4074                 xge = ge->bkwd;
4075                 if(xge == ge) { /* was the only line in contour */
4076                         /* remove the contour completely */
4077                         /* prev is GE_MOVE, next is GE_PATH, remove them all */
4078
4079                         /* may be the first contour, then ->bkwd points to ge->entries */
4080                         if(ge->prev->prev == 0)
4081                                 *(GENTRY **)(ge->prev->bkwd) = ge->next->next;
4082                         else
4083                                 ge->prev->prev->next = ge->next->next;
4084
4085                         if(ge->next->next) {
4086                                 ge->next->next->prev = ge->prev->prev;
4087                                 ge->next->next->bkwd = ge->prev->bkwd;
4088                         }
4089
4090                         xge = ge->next->next;
4091                         free(ge->prev); free(ge->next); free(ge);
4092                         return xge;
4093                 }
4094
4095                 /* move the start point of the contour */
4096                 if(ge->flags & GEF_FLOAT) {
4097                         ge->prev->fx3 = xge->fx3;
4098                         ge->prev->fy3 = xge->fy3;
4099                 } else {
4100                         ge->prev->ix3 = xge->ix3;
4101                         ge->prev->iy3 = xge->iy3;
4102                 }
4103         } else if(ge->frwd != ge->next) {
4104                 /* at end of the contour */
4105
4106                 xge = ge->frwd->prev;
4107                 /* move the start point of the contour */
4108                 if(ge->flags & GEF_FLOAT) {
4109                         xge->fx3 = ge->bkwd->fx3;
4110                         xge->fy3 = ge->bkwd->fy3;
4111                 } else {
4112                         xge->ix3 = ge->bkwd->ix3;
4113                         xge->iy3 = ge->bkwd->iy3;
4114                 }
4115         }
4116
4117         ge->prev->next = ge->next;
4118         ge->next->prev = ge->prev;
4119         ge->bkwd->frwd = ge->frwd;
4120         ge->frwd->bkwd = ge->bkwd;
4121
4122         xge = ge->next;
4123         free(ge);
4124         return xge;
4125 }
4126
4127 /* inserts a new gentry (LINE or CURVE) after another (MOVE
4128  * or LINE or CURVE)
4129  * corrects the first GE_MOVE if neccessary
4130  */
4131
4132 static void
4133 addgeafter(
4134         GENTRY *oge, /* after this */
4135         GENTRY *nge /* insert this */
4136 )
4137 {
4138         if(oge->type == GE_MOVE) {
4139                 /* insert before next */
4140                 if(oge->next->type == GE_PATH) {
4141                         /* first and only GENTRY in path */
4142                         nge->frwd = nge->bkwd = nge;
4143                 } else {
4144                         nge->frwd = oge->next;
4145                         nge->bkwd = oge->next->bkwd;
4146                         oge->next->bkwd->frwd = nge;
4147                         oge->next->bkwd = nge;
4148                 }
4149         } else {
4150                 nge->frwd = oge->frwd;
4151                 nge->bkwd = oge;
4152                 oge->frwd->bkwd = nge;
4153                 oge->frwd = nge;
4154         }
4155
4156         nge->next = oge->next;
4157         nge->prev = oge;
4158         oge->next->prev = nge;
4159         oge->next = nge;
4160
4161         if(nge->frwd->prev->type == GE_MOVE) {
4162                 /* fix up the GE_MOVE entry */
4163                 if(nge->flags & GEF_FLOAT) {
4164                         nge->frwd->prev->fx3 = nge->fx3;
4165                         nge->frwd->prev->fy3 = nge->fy3;
4166                 } else {
4167                         nge->frwd->prev->ix3 = nge->ix3;
4168                         nge->frwd->prev->iy3 = nge->iy3;
4169                 }
4170         }
4171 }
4172
4173 /*
4174  * Check if this GENTRY happens to be at the end of path
4175  * and fix the first MOVETO accordingly
4176  * handles both int and float
4177  */
4178
4179 static void
4180 fixendpath(
4181         GENTRY *ge
4182 )
4183 {
4184         GENTRY *mge;
4185
4186         mge = ge->frwd->prev;
4187         if(mge->type == GE_MOVE) {
4188                 if(ge->flags & GEF_FLOAT) {
4189                         mge->fx3 = ge->fx3;
4190                         mge->fy3 = ge->fy3;
4191                 } else {
4192                         mge->ix3 = ge->ix3;
4193                         mge->iy3 = ge->iy3;
4194                 }
4195         }
4196 }
4197
4198 /*
4199  * This function adjusts the rest of path (the part from...to is NOT changed)
4200  * to cover the specified gap by the specified axis (0 - X, 1 - Y).
4201  * Gap is counted in direction (end_of_to - beginning_of_from).
4202  * Returns by how much the gap was not closed (0.0 if it was fully closed).
4203  * Ret contains by how much the first and last points of [from...to]
4204  * were moved to bring them in consistence to the rest of the path.
4205  * If ret==NULL then this info is not returned.
4206  */
4207
4208 static double
4209 fclosegap(
4210         GENTRY *from,
4211         GENTRY *to,
4212         int axis,
4213         double gap,
4214         double *ret
4215 )
4216 {
4217 #define TIMESLARGER 10. /* how many times larger must be a curve to not change too much */
4218         double rm[2];
4219         double oldpos[2];
4220         double times, limit, df, dx;
4221         int j, k;
4222         GENTRY *xge, *pge, *nge, *bge[2];
4223
4224         /* remember the old points to calculate ret */
4225         oldpos[0] = from->prev->fpoints[axis][2];
4226         oldpos[1] = to->fpoints[axis][2];
4227
4228         rm[0] = rm[1] = gap / 2. ;
4229
4230         bge[0] = from; /* this is convenient for iterations */
4231         bge[1] = to;
4232
4233         /* first try to modify large curves but if have none then settle for small */
4234         for(times = (TIMESLARGER-1); times > 0.1; times /= 2. ) {
4235
4236                 if(rm[0]+rm[1] == 0.)
4237                         break;
4238
4239                 /* iterate in both directions, backwards then forwards */
4240                 for(j = 0; j<2; j++) {
4241
4242                         if(rm[j] == 0.) /* if this direction is exhausted */
4243                                 continue;
4244
4245                         limit = fabs(rm[j]) * (1.+times);
4246
4247                         for(xge = bge[j]->cntr[j]; xge != bge[!j]; xge = xge->cntr[j]) {
4248                                 dx = xge->fpoints[axis][2] - xge->prev->fpoints[axis][2];
4249                                 df = fabs(dx) - limit;
4250                                 if( df <= FEPS ) /* curve is too small to change */
4251                                         continue;
4252
4253                                 if( df >= fabs(rm[j]) )
4254                                         df = rm[j];
4255                                 else
4256                                         df *= fsign(rm[j]); /* we may cover this part of rm */
4257
4258                                 rm[j] -= df;
4259                                 limit = fabs(rm[j]) * (1.+times);
4260
4261                                 if(xge->type == GE_CURVE) { /* correct internal points */
4262                                         double scale = ((dx+df) / dx) - 1.;
4263                                         double base;
4264
4265                                         if(j)
4266                                                 base = xge->fpoints[axis][2];
4267                                         else
4268                                                 base = xge->prev->fpoints[axis][2];
4269
4270                                         for(k = 0; k<2; k++)
4271                                                 xge->fpoints[axis][k] += scale *
4272                                                         (xge->fpoints[axis][k] - base);
4273                                 }
4274
4275                                 /* move all the intermediate lines */
4276                                 if(j) {
4277                                         df = -df; /* absolute direction */
4278                                         pge = bge[1]->bkwd;
4279                                         nge = xge->bkwd;
4280                                 } else {
4281                                         xge->fpoints[axis][2] += df;
4282                                         pge = bge[0];
4283                                         nge = xge->frwd;
4284                                 }
4285                                 while(nge != pge) {
4286                                         if(nge->type == GE_CURVE) {
4287                                                 nge->fpoints[axis][0] +=df;
4288                                                 nge->fpoints[axis][1] +=df;
4289                                         }
4290                                         nge->fpoints[axis][2] += df;
4291                                         if(nge->next != nge->frwd) { /* last entry of contour */
4292                                                 nge->frwd->prev->fpoints[axis][2] += df;
4293                                         }
4294                                         nge = nge->cntr[!j];
4295                                 }
4296
4297                                 if(rm[j] == 0.)
4298                                         break;
4299                         }
4300                 }
4301         }
4302
4303         /* find the difference */
4304         oldpos[0] -= from->prev->fpoints[axis][2];
4305         oldpos[1] -= to->fpoints[axis][2];
4306
4307         if(ret) {
4308                 ret[0] = oldpos[0] - from->prev->fpoints[axis][2];
4309                 ret[1] = oldpos[1] - to->fpoints[axis][2];
4310         }
4311
4312 #if 0
4313         if( rm[0]+rm[1] != gap - oldpos[1] + oldpos[0]) {
4314                 fprintf(stderr, "** gap=%g rm[0]=%g rm[1]=%g o[0]=%g o[1]=%g rg=%g og=%g\n",
4315                         gap, rm[0], rm[1], oldpos[0], oldpos[1], rm[0]+rm[1],
4316                         gap - oldpos[1] + oldpos[0]);
4317         }
4318 #endif
4319
4320         return rm[0]+rm[1];
4321 #undef TIMESLARGER
4322 }
4323
4324 /* remove the lines or curves smaller or equal to the size limit */
4325
4326 static void
4327 fdelsmall(
4328         GLYPH *g,
4329         double minlen
4330 )
4331 {
4332         GENTRY  *ge, *nge, *pge, *xge, *next;
4333         int i, k;
4334         double dx, dy, d2, d2m;
4335         double minlen2;
4336 #define TIMESLARGER 10. /* how much larger must be a curve to not change too much */
4337
4338         minlen2 = minlen*minlen;
4339
4340         for (ge = g->entries; ge != 0; ge = next) {
4341                 next = ge->next;
4342
4343                 if (ge->type != GE_CURVE && ge->type != GE_LINE)
4344                         continue;
4345
4346                 d2m = 0;
4347                 for(i= (ge->type==GE_CURVE? 0: 2); i<3; i++) {
4348                         dx = ge->fxn[i] - ge->prev->fx3;
4349                         dy = ge->fyn[i] - ge->prev->fy3;
4350                         d2 = dx*dx + dy*dy;
4351                         if(d2m < d2)
4352                                 d2m = d2;
4353                 }
4354
4355                 if( d2m > minlen2 ) { /* line is not too small */
4356                         /* XXX add more normalization here */
4357                         continue;
4358                 }
4359
4360                 /* if the line is too small */
4361
4362                 /* check forwards if we have a whole sequence of them */
4363                 nge = ge;
4364                 for(xge = ge->frwd; xge != ge; xge = xge->frwd) {
4365                         d2m = 0;
4366                         for(i= (xge->type==GE_CURVE? 0: 2); i<3; i++) {
4367                                 dx = xge->fxn[i] - xge->prev->fx3;
4368                                 dy = xge->fyn[i] - xge->prev->fy3;
4369                                 d2 = dx*dx + dy*dy;
4370                                 if(d2m < d2)
4371                                         d2m = d2;
4372                         }
4373                         if( d2m > minlen2 ) /* line is not too small */
4374                                 break;
4375                         nge = xge;
4376                         if(next == nge) /* move the next step past this sequence */
4377                                 next = next->next;
4378                 }
4379
4380                 /* check backwards if we have a whole sequence of them */
4381                 pge = ge;
4382                 for(xge = ge->bkwd; xge != ge; xge = xge->bkwd) {
4383                         d2m = 0;
4384                         for(i= (xge->type==GE_CURVE? 0: 2); i<3; i++) {
4385                                 dx = xge->fxn[i] - xge->prev->fx3;
4386                                 dy = xge->fyn[i] - xge->prev->fy3;
4387                                 d2 = dx*dx + dy*dy;
4388                                 if(d2m < d2)
4389                                         d2m = d2;
4390                         }
4391                         if( d2m > minlen2 ) /* line is not too small */
4392                                 break;
4393                         pge = xge;
4394                 }
4395
4396                 /* now we have a sequence of small fragments in pge...nge (inclusive) */
4397
4398                 if(ISDBG(FCONCISE))  {
4399                         fprintf(stderr, "glyph %s has very small fragments(%x..%x..%x)\n",
4400                         g->name, pge, ge, nge);
4401                         dumppaths(g, pge, nge);
4402                 }
4403
4404                 /* reduce whole sequence to one part and remember the middle point */
4405                 if(pge != nge) {
4406                         while(1) {
4407                                 xge = pge->frwd;
4408                                 if(xge == nge) {
4409                                         pge->fx1 = pge->fx2 = pge->fx3;
4410                                         pge->fx3 = nge->fx3;
4411                                         pge->fy1 = pge->fy2 = pge->fy3;
4412                                         pge->fy3 = nge->fy3;
4413                                         pge->type = GE_CURVE;
4414                                         freethisge(nge);
4415                                         break;
4416                                 }
4417                                 if(xge == nge->bkwd) {
4418                                         pge->fx1 = pge->fx2 = (pge->fx3+xge->fx3)/2.;
4419                                         pge->fx3 = nge->fx3;
4420                                         pge->fy1 = pge->fy2 = (pge->fy3+xge->fy3)/2.;
4421                                         pge->fy3 = nge->fy3;
4422                                         pge->type = GE_CURVE;
4423                                         freethisge(nge);
4424                                         freethisge(xge);
4425                                         break;
4426                                 }
4427                                 freethisge(pge); pge = xge;
4428                                 xge = nge->bkwd; freethisge(nge); nge = xge;
4429                         }
4430                 }
4431                 ge = pge;
4432
4433                 /* check if the whole sequence is small */
4434                 dx = ge->fx3 - ge->prev->fx3;
4435                 dy = ge->fy3 - ge->prev->fy3;
4436                 d2 = dx*dx + dy*dy;
4437
4438                 if( d2 > minlen2 ) { /* no, it is not */
4439                         double b, d;
4440
4441                         WARNING_3 fprintf(stderr, "glyph %s had a sequence of fragments < %g points each, reduced to one curve\n",
4442                                 g->name, minlen);
4443
4444                         /* check that we did not create a monstrosity spanning quadrants */
4445                         if(fsign(ge->fx1 - ge->prev->fx1) * fsign(ge->fx3 - ge->fx1) < 0
4446                         || fsign(ge->fy1 - ge->prev->fy1) * fsign(ge->fy3 - ge->fy1) < 0 ) {
4447                                 /* yes, we did; are both parts of this thing big enough ? */
4448                                 dx = ge->fx1 - ge->prev->fx3;
4449                                 dy = ge->fy1 - ge->prev->fy3;
4450                                 d2 = dx*dx + dy*dy;
4451
4452                                 dx = ge->fx3 - ge->fx1;
4453                                 dy = ge->fy3 - ge->fy1;
4454                                 d2m = dx*dx + dy*dy;
4455
4456                                 if(d2 > minlen2 && d2m > minlen2) { /* make two straights */
4457                                         nge = newgentry(GEF_FLOAT);
4458                                         *nge = *ge;
4459
4460                                         for(i=0; i<2; i++) {
4461                                                 ge->fpoints[i][2] = ge->fpoints[i][0];
4462                                                 b = nge->fpoints[i][0];
4463                                                 d = nge->fpoints[i][2] - b;
4464                                                 nge->fpoints[i][0] = b + 0.1*d;
4465                                                 nge->fpoints[i][1] = b + 0.9*d;
4466                                         }
4467                                 }
4468                                 for(i=0; i<2; i++) { /* make one straight or first of two straights */
4469                                         b = ge->prev->fpoints[i][2];
4470                                         d = ge->fpoints[i][2] - b;
4471                                         ge->fpoints[i][0] = b + 0.1*d;
4472                                         ge->fpoints[i][1] = b + 0.9*d;
4473                                 }
4474                         }
4475                         continue;
4476                 }
4477
4478                 if(ge->frwd == ge) { /* points to itself, just remove the path completely */
4479                         WARNING_3 fprintf(stderr, "glyph %s had a path made of fragments < %g points each, removed\n",
4480                                 g->name, minlen);
4481
4482                         next = freethisge(ge);
4483                         continue;
4484                 }
4485
4486                 /* now close the gap by x and y */
4487                 for(i=0; i<2; i++) {
4488                         double gap;
4489
4490                         gap = ge->fpoints[i][2] - ge->prev->fpoints[i][2];
4491                         if( fclosegap(ge, ge, i, gap, NULL) != 0.0 ) {
4492                                 double scale, base;
4493
4494                                 /* not good, as the last resort just scale the next line */
4495                                 gap = ge->fpoints[i][2] - ge->prev->fpoints[i][2];
4496
4497                                 if(ISDBG(FCONCISE))
4498                                         fprintf(stderr, "    last resort on %c: closing next by %g\n",
4499                                         (i==0 ? 'x' : 'y'), gap);
4500
4501                                 nge = ge->frwd;
4502                                 base = nge->fpoints[i][2];
4503                                 dx = ge->fpoints[i][2] - base;
4504                                 if(fabs(dx) < FEPS)
4505                                         continue;
4506
4507                                 scale = ((dx-gap) / dx);
4508
4509                                 if(nge->type == GE_CURVE)
4510                                         for(k = 0; k<2; k++)
4511                                                 nge->fpoints[i][k] = base +
4512                                                         scale * (nge->fpoints[i][k] - base);
4513
4514                                 ge->fpoints[i][2] -= gap;
4515                         }
4516                 }
4517
4518                 /* OK, the gap is closed - remove this useless GENTRY */
4519                 freethisge(ge);
4520         }
4521 #undef TIMESLARGER
4522 }
4523
4524 /* normalize curves to the form where their ends
4525  * can be safely used as derivatives
4526  */
4527
4528 static void
4529 fnormalizec(
4530              GLYPH * g
4531 )
4532 {
4533         GENTRY *ge;
4534         int midsame, frontsame, rearsame, i;
4535         double d, b;
4536
4537         assertisfloat(g, "normalizing curves");
4538
4539         for (ge = g->entries; ge != 0; ge = ge->next) {
4540                 if (ge->type != GE_CURVE)
4541                         continue;
4542
4543                 midsame = (fabs(ge->fx1-ge->fx2)<FEPS && fabs(ge->fy1-ge->fy2)<FEPS);
4544                 frontsame = (fabs(ge->fx1-ge->prev->fx3)<FEPS && fabs(ge->fy1-ge->prev->fy3)<FEPS);
4545                 rearsame = (fabs(ge->fx3-ge->fx2)<FEPS && fabs(ge->fy3-ge->fy2)<FEPS);
4546
4547                 if(midsame && (frontsame || rearsame) ) {
4548                         /* essentially a line */
4549                         for(i=0; i<2; i++) {
4550                                 b = ge->prev->fpoints[i][2];
4551                                 d = ge->fpoints[i][2] - b;
4552                                 ge->fpoints[i][0] = b + 0.1*d;
4553                                 ge->fpoints[i][1] = b + 0.9*d;
4554                         }
4555                 } else if(frontsame) {
4556                         for(i=0; i<2; i++) {
4557                                 b = ge->prev->fpoints[i][2];
4558                                 d = ge->fpoints[i][1] - b;
4559                                 ge->fpoints[i][0] = b + 0.01*d;
4560                         }
4561                 } else if(rearsame) {
4562                         for(i=0; i<2; i++) {
4563                                 b = ge->fpoints[i][2];
4564                                 d = ge->fpoints[i][0] - b;
4565                                 ge->fpoints[i][1] = b + 0.01*d;
4566                         }
4567                 } else
4568                         continue;
4569
4570                 if(ISDBG(FCONCISE)) fprintf(stderr, "glyph %g, normalized entry %x\n", g->name, ge);
4571         }
4572 }
4573
4574 /* find the point where two rays continuing vectors cross
4575  * rays are defined as beginning of curve1 and end of curve 2
4576  * returns 1 if they cross, 0 if they don't
4577  * If they cross returns the maximal scales for both vectors.
4578  * Expects that the curves are normalized.
4579  */
4580
4581 static int
4582 fcrossrays(
4583         GENTRY *ge1,
4584         GENTRY *ge2,
4585         double *max1,
4586         double *max2
4587 )
4588 {
4589         struct ray {
4590                 double x1, y1, x2, y2;
4591                 int isvert;
4592                 double k, b; /* lines are represented as y = k*x + b */
4593                 double *maxp;
4594         } ray [3];
4595         double x, y;
4596         int i;
4597
4598         ray[0].x1 = ge1->prev->fx3;
4599         ray[0].y1 = ge1->prev->fy3;
4600         ray[0].x2 = ge1->fx1;
4601         ray[0].y2 = ge1->fy1;
4602         ray[0].maxp = max1;
4603
4604         ray[1].x1 = ge2->fx3;
4605         ray[1].y1 = ge2->fy3;
4606         ray[1].x2 = ge2->fx2;
4607         ray[1].y2 = ge2->fy2;
4608         ray[1].maxp = max2;
4609
4610         for(i=0; i<2; i++) {
4611                 if(ray[i].x1 == ray[i].x2)
4612                         ray[i].isvert = 1;
4613                 else {
4614                         ray[i].isvert = 0;
4615                         ray[i].k = (ray[i].y2 - ray[i].y1) / (ray[i].x2 - ray[i].x1);
4616                         ray[i].b = ray[i].y2 - ray[i].k * ray[i].x2;
4617                 }
4618         }
4619
4620         if(ray[0].isvert && ray[1].isvert) {
4621                 if(ISDBG(FCONCISE)) fprintf(stderr, "crossrays: both vertical\n");
4622                 return 0; /* both vertical, don't cross */
4623         }
4624
4625         if(ray[1].isvert) {
4626                 ray[2] = ray[0]; /* exchange them */
4627                 ray[0] = ray[1];
4628                 ray[1] = ray[2];
4629         }
4630
4631         if(ray[0].isvert) {
4632                 x = ray[0].x1;
4633         } else {
4634                 if( fabs(ray[0].k - ray[1].k) < FEPS) {
4635                         if(ISDBG(FCONCISE)) fprintf(stderr, "crossrays: parallel lines, k = %g, %g\n",
4636                                 ray[0].k, ray[1].k);
4637                         return 0; /* parallel lines */
4638                 }
4639                 x = (ray[1].b - ray[0].b) / (ray[0].k - ray[1].k) ;
4640         }
4641         y = ray[1].k * x + ray[1].b;
4642
4643         for(i=0; i<2; i++) {
4644                 if(ray[i].isvert)
4645                         *ray[i].maxp = (y - ray[i].y1) / (ray[i].y2 - ray[i].y1);
4646                 else
4647                         *ray[i].maxp = (x - ray[i].x1) / (ray[i].x2 - ray[i].x1);
4648                 /* check if wrong sides of rays cross */
4649                 if( *ray[i].maxp < 0 ) {
4650                         if(ISDBG(FCONCISE)) fprintf(stderr, "crossrays: scale=%g @(%g,%g) (%g,%g)<-(%g,%g)\n",
4651                                 *ray[i].maxp, x, y, ray[i].x2, ray[i].y2, ray[i].x1, ray[i].y1);
4652                         return 0;
4653                 }
4654         }
4655         return 1;
4656 }
4657
4658 /* find the area covered by the curve
4659  * (limited by the projections to the X axis)
4660  */
4661
4662 static double
4663 fcvarea(
4664         GENTRY *ge
4665 )
4666 {
4667         double Ly, My, Ny, Py, Qx, Rx, Sx;
4668         double area;
4669
4670         /* y = Ly*t^3 + My*t^2 + Ny*t + Py */
4671         Ly = -ge->prev->fy3 + 3*(ge->fy1 - ge->fy2) + ge->fy3;
4672         My = 3*ge->prev->fy3 - 6*ge->fy1 + 3*ge->fy2;
4673         Ny = 3*(-ge->prev->fy3 + ge->fy1);
4674         Py = ge->prev->fy3;
4675
4676         /* dx/dt = Qx*t^2 + Rx*t + Sx */
4677         Qx = 3*(-ge->prev->fx3 + 3*(ge->fx1 - ge->fx2) + ge->fx3);
4678         Rx = 6*(ge->prev->fx3 - 2*ge->fx1 + ge->fx2);
4679         Sx = 3*(-ge->prev->fx3 + ge->fx1);
4680
4681         /* area is integral[from 0 to 1]( y(t) * dx(t)/dt *dt) */
4682         area = 1./6.*(Ly*Qx) + 1./5.*(Ly*Rx + My*Qx)
4683                 + 1./4.*(Ly*Sx + My*Rx + Ny*Qx) + 1./3.*(My*Sx + Ny*Rx + Py*Qx)
4684                 + 1./2.*(Ny*Sx + Py*Rx) + Py*Sx;
4685
4686         return area;
4687 }
4688
4689 /* find the value of point on the curve at the given parameter t,
4690  * along the given axis (0 - X, 1 - Y).
4691  */
4692
4693 static double
4694 fcvval(
4695         GENTRY *ge,
4696         int axis,
4697         double t
4698 )
4699 {
4700         double t2, mt, mt2;
4701
4702         /* val = A*(1-t)^3 + 3*B*(1-t)^2*t + 3*C*(1-t)*t^2 + D*t^3 */
4703         t2 = t*t;
4704         mt = 1-t;
4705         mt2 = mt*mt;
4706
4707         return ge->prev->fpoints[axis][2]*mt2*mt
4708                 + 3*(ge->fpoints[axis][0]*mt2*t + ge->fpoints[axis][1]*mt*t2)
4709                 + ge->fpoints[axis][2]*t*t2;
4710 }
4711
4712 /* Check that the new curve has the point identified by the
4713  * parameter t reasonably close to the corresponding point
4714  * in the old pair of curves which were joined in proportion k.
4715  * If old2 is NULL then just compare nge and old1 at the point t.
4716  * Returns 0 if OK, 1 if it's too far.
4717  */
4718
4719 static int
4720 fckjoinedcv(
4721         GLYPH *g,
4722         double t,
4723         GENTRY *nge,
4724         GENTRY *old1,
4725         GENTRY *old2,
4726         double k
4727 )
4728 {
4729         GENTRY *oge;
4730         double ot;
4731         double off;
4732         double lim;
4733         int i;
4734
4735         if(old2 == 0) {
4736                 oge = old1;
4737                 ot = t;
4738         } else if(t <= k && k!=0.) {
4739                 oge = old1;
4740                 ot = t/k;
4741         } else {
4742                 oge = old2;
4743                 ot = (t-k) / (1.-k);
4744         }
4745
4746         if(ISDBG(FCONCISE))
4747                 fprintf(stderr, "%s: t=%g ot=%g (%x) ", g->name, t, ot, oge);
4748
4749         for(i=0; i<2; i++) {
4750                 /* permitted tolerance is 5% */
4751                 lim = fabs(nge->fpoints[i][2] - nge->prev->fpoints[i][2])*0.05;
4752
4753                 if(lim < 3.)
4754                         lim = 3.; /* for small curves the tolerance is higher */
4755                 if(lim > 10.)
4756                         lim = 10.; /* for big curves the tolerance is limited anyway */
4757
4758                 off = fabs(fcvval(nge, i, t) - fcvval(oge, i, ot));
4759
4760                 if(off > lim) {
4761                         if(ISDBG(FCONCISE))
4762                                 fprintf(stderr, "out of range d%c=%.2f(%.2f)\n",
4763                                         (i==0 ? 'X' : 'Y'), off, lim);
4764                         return 1;
4765                 }
4766
4767                 if(ISDBG(FCONCISE))
4768                         fprintf(stderr, "valid d%c=%.2f(%.2f)  ", (i==0 ? 'X' : 'Y'), off, lim);
4769         }
4770         if(ISDBG(FCONCISE))
4771                 fprintf(stderr, "\n");
4772         return 0;
4773 }
4774
4775 /* force conciseness: substitute 2 or more curves going in the
4776 ** same quadrant with one curve
4777 ** in floating point
4778 */
4779
4780 void
4781 fforceconcise(
4782              GLYPH * g
4783 )
4784 {
4785         GENTRY         *ge, *nge;
4786         GENTRY          tge;
4787         double          firstlen, lastlen, sumlen, scale;
4788         double          dxw1, dyw1, dxw2, dyw2;
4789         double          dxb1, dyb1, dxe1, dye1;
4790         double          dxb2, dyb2, dxe2, dye2;
4791         double          maxsc1, maxsc2;
4792         int             i;
4793
4794         assertisfloat(g, "enforcing conciseness");
4795
4796         fdelsmall(g, 0.05);
4797         assertpath(g->entries, __FILE__, __LINE__, g->name);
4798         fnormalizec(g);
4799
4800
4801         for (ge = g->entries; ge != 0; ge = ge->next) {
4802                 if (ge->type != GE_CURVE)
4803                         continue;
4804
4805                 /* the whole direction of curve */
4806                 dxw1 = ge->fx3 - ge->prev->fx3;
4807                 dyw1 = ge->fy3 - ge->prev->fy3;
4808
4809                 while (1) {
4810                         /* the whole direction of curve */
4811                         dxw1 = ge->fx3 - ge->prev->fx3;
4812                         dyw1 = ge->fy3 - ge->prev->fy3;
4813
4814                         /* directions of  ends of curve */
4815                         dxb1 = ge->fx1 - ge->prev->fx3;
4816                         dyb1 = ge->fy1 - ge->prev->fy3;
4817                         dxe1 = ge->fx3 - ge->fx2;
4818                         dye1 = ge->fy3 - ge->fy2;
4819
4820                         nge = ge->frwd;
4821
4822                         if (nge->type != GE_CURVE)
4823                                 break;
4824
4825                         dxw2 = nge->fx3 - ge->fx3;
4826                         dyw2 = nge->fy3 - ge->fy3;
4827
4828                         dxb2 = nge->fx1 - ge->fx3;
4829                         dyb2 = nge->fy1 - ge->fy3;
4830                         dxe2 = nge->fx3 - nge->fx2;
4831                         dye2 = nge->fy3 - nge->fy2;
4832
4833                         /* if curve changes direction */
4834                         if (fsign(dxw1) != fsign(dxw2) || fsign(dyw1) != fsign(dyw2))
4835                                 break;
4836
4837                         /* if the arch is going in other direction */
4838                         if (fsign(fabs(dxb1 * dyw1) - fabs(dyb1 * dxw1))
4839                             * fsign(fabs(dxe2 * dyw2) - fabs(dye2 * dxw2)) > 0)
4840                                 break;
4841
4842                         /* get possible scale limits within which we won't cross quadrants */
4843                         if( fcrossrays(ge, nge, &maxsc1, &maxsc2) == 0 ) {
4844                                 if(ISDBG(FCONCISE)) {
4845                                         fprintf(stderr, "glyph %s has curves with strange ends\n", g->name);
4846                                         dumppaths(g, ge, nge);
4847                                 }
4848                                 break;
4849                         }
4850
4851                         if(maxsc1 < 1. || maxsc2 < 1. ) /* would create a zigzag */
4852                                 break;
4853
4854                         ge->dir = fgetcvdir(ge);
4855                         nge->dir = fgetcvdir(nge);
4856
4857                         if( ((ge->dir&CVDIR_FRONT)-CVDIR_FEQUAL) * ((nge->dir&CVDIR_REAR)-CVDIR_REQUAL) < 0 )
4858                                 /* would create a zigzag */
4859                                 break;
4860
4861                         firstlen = sqrt( dxe1*dxe1 + dye1*dye1 );
4862                         lastlen = sqrt( dxb2*dxb2 + dyb2*dyb2 );
4863                         sumlen = firstlen + lastlen;
4864
4865                         /* check the scale limits */
4866                         if( sumlen/firstlen > maxsc1 || sumlen/lastlen > maxsc2 ) {
4867                                 if(ISDBG(FCONCISE))
4868                                         fprintf(stderr, "%s: %x, %x would be crossing in forceconcise\n",
4869                                         g->name, ge, nge);
4870                                 break;
4871                         }
4872
4873                         /* OK, it seems like we can attempt to join these two curves */
4874                         tge.flags = ge->flags;
4875                         tge.prev = ge->prev;
4876                         tge.fx1 = ge->fx1;
4877                         tge.fy1 = ge->fy1;
4878                         tge.fx2 = nge->fx2;
4879                         tge.fy2 = nge->fy2;
4880                         tge.fx3 = nge->fx3;
4881                         tge.fy3 = nge->fy3;
4882
4883                         dxb1 = tge.fx1 - tge.prev->fx3;
4884                         dyb1 = tge.fy1 - tge.prev->fy3;
4885                         dxe1 = tge.fx3 - tge.fx2;
4886                         dye1 = tge.fy3 - tge.fy2;
4887
4888                         /* scale the first segment */
4889                         scale = sumlen / firstlen;
4890                         tge.fx1 = tge.prev->fx3 + scale * dxb1;
4891                         tge.fy1 = tge.prev->fy3 + scale * dyb1;
4892
4893                         /* scale the last segment */
4894                         scale = sumlen / lastlen;
4895                         tge.fx2 = tge.fx3 - scale * dxe1;
4896                         tge.fy2 = tge.fy3 - scale * dye1;
4897
4898                         /* now check if we got something sensible */
4899
4900                         /* check if some important points is too far from original */
4901                         scale = firstlen / sumlen;
4902                         {
4903                                 double pts[4] = { 0./*will be replaced*/, 0.5, 0.25, 0.75 };
4904                                 int i, bad;
4905
4906                                 pts[0] = scale;
4907                                 bad = 0;
4908
4909                                 for(i=0; i<sizeof(pts)/sizeof(pts[0]); i++)
4910                                         if(fckjoinedcv(g, pts[i], &tge, ge, nge, scale)) {
4911                                                 bad = 1;
4912                                                 break;
4913                                         }
4914                                 if(bad)
4915                                         break;
4916                         }
4917
4918                         /* OK, it looks reasonably, let's apply it */
4919                         if(ISDBG(FCONCISE))
4920                                 dumppaths(g, ge, nge);
4921
4922                         for(i=0; i<3; i++) {
4923                                 ge->fxn[i] = tge.fxn[i];
4924                                 ge->fyn[i] = tge.fyn[i];
4925                         }
4926
4927                         freethisge(nge);
4928                 }
4929         }
4930 }
4931
4932 void
4933 print_glyph(
4934            int glyphno
4935 )
4936 {
4937         GLYPH          *g;
4938         GENTRY         *ge;
4939         int             x = 0, y = 0;
4940         int             i;
4941         int             grp, lastgrp= -1;
4942
4943         g = &glyph_list[glyphno];
4944
4945         fprintf(pfa_file, "/%s { \n", g->name);
4946
4947         /* consider widths >MAXLEGALWIDTH as bugs */
4948         if( g->scaledwidth <= MAXLEGALWIDTH ) {
4949                 fprintf(pfa_file, "0 %d hsbw\n", g->scaledwidth);
4950         } else {
4951                 fprintf(pfa_file, "0 1000 hsbw\n");
4952                 WARNING_2 fprintf(stderr, "glyph %s: width %d seems to be buggy, set to 1000\n",
4953                         g->name, g->scaledwidth);
4954         }
4955
4956 #if 0
4957         fprintf(pfa_file, "%% contours: ");
4958         for (i = 0; i < g->ncontours; i++)
4959                 fprintf(pfa_file, "%s(%d,%d) ", (g->contours[i].direction == DIR_OUTER ? "out" : "in"),
4960                         g->contours[i].xofmin, g->contours[i].ymin);
4961         fprintf(pfa_file, "\n");
4962
4963         if (g->rymin < 5000)
4964                 fprintf(pfa_file, "%d lower%s\n", g->rymin, (g->flatymin ? "flat" : "curve"));
4965         if (g->rymax > -5000)
4966                 fprintf(pfa_file, "%d upper%s\n", g->rymax, (g->flatymax ? "flat" : "curve"));
4967 #endif
4968
4969         if (g->hstems)
4970                 for (i = 0; i < g->nhs; i += 2) {
4971                         if (g->hstems[i].flags & ST_3) {
4972                                 fprintf(pfa_file, "%d %d %d %d %d %d hstem3\n",
4973                                         g->hstems[i].value,
4974                                 g->hstems[i + 1].value - g->hstems[i].value,
4975                                         g->hstems[i + 2].value,
4976                                         g->hstems[i + 3].value - g->hstems[i + 2].value,
4977                                         g->hstems[i + 4].value,
4978                                         g->hstems[i + 5].value - g->hstems[i + 4].value
4979                                         );
4980                                 i += 4;
4981                         } else {
4982                                 fprintf(pfa_file, "%d %d hstem\n", g->hstems[i].value,
4983                                 g->hstems[i + 1].value - g->hstems[i].value);
4984                         }
4985                 }
4986
4987         if (g->vstems)
4988                 for (i = 0; i < g->nvs; i += 2) {
4989                         if (g->vstems[i].flags & ST_3) {
4990                                 fprintf(pfa_file, "%d %d %d %d %d %d vstem3\n",
4991                                         g->vstems[i].value,
4992                                 g->vstems[i + 1].value - g->vstems[i].value,
4993                                         g->vstems[i + 2].value,
4994                                         g->vstems[i + 3].value - g->vstems[i + 2].value,
4995                                         g->vstems[i + 4].value,
4996                                         g->vstems[i + 5].value - g->vstems[i + 4].value
4997                                         );
4998                                 i += 4;
4999                         } else {
5000                                 fprintf(pfa_file, "%d %d vstem\n", g->vstems[i].value,
5001                                 g->vstems[i + 1].value - g->vstems[i].value);
5002                         }
5003                 }
5004
5005         for (ge = g->entries; ge != 0; ge = ge->next) {
5006                 if(g->nsg>0) {
5007                         grp=ge->stemid;
5008                         if(grp >= 0 && grp != lastgrp)  {
5009                                 fprintf(pfa_file, "%d 4 callsubr\n", grp+g->firstsubr);
5010                                 lastgrp=grp;
5011                         }
5012                 }
5013
5014                 switch (ge->type) {
5015                 case GE_MOVE:
5016                         if (absolute)
5017                                 fprintf(pfa_file, "%d %d amoveto\n", ge->ix3, ge->iy3);
5018                         else
5019                                 rmoveto(ge->ix3 - x, ge->iy3 - y);
5020                         if (0)
5021                                 fprintf(stderr, "Glyph %s: print moveto(%d, %d)\n",
5022                                         g->name, ge->ix3, ge->iy3);
5023                         x = ge->ix3;
5024                         y = ge->iy3;
5025                         break;
5026                 case GE_LINE:
5027                         if (absolute)
5028                                 fprintf(pfa_file, "%d %d alineto\n", ge->ix3, ge->iy3);
5029                         else
5030                                 rlineto(ge->ix3 - x, ge->iy3 - y);
5031                         x = ge->ix3;
5032                         y = ge->iy3;
5033                         break;
5034                 case GE_CURVE:
5035                         if (absolute)
5036                                 fprintf(pfa_file, "%d %d %d %d %d %d arcurveto\n",
5037                                         ge->ix1, ge->iy1, ge->ix2, ge->iy2, ge->ix3, ge->iy3);
5038                         else
5039                                 rrcurveto(ge->ix1 - x, ge->iy1 - y,
5040                                           ge->ix2 - ge->ix1, ge->iy2 - ge->iy1,
5041                                           ge->ix3 - ge->ix2, ge->iy3 - ge->iy2);
5042                         x = ge->ix3;
5043                         y = ge->iy3;
5044                         break;
5045                 case GE_PATH:
5046                         closepath();
5047                         break;
5048                 default:
5049                         WARNING_1 fprintf(stderr, "**** Glyph %s: unknown entry type '%c'\n",
5050                                 g->name, ge->type);
5051                         break;
5052                 }
5053         }
5054
5055         fprintf(pfa_file, "endchar } ND\n");
5056 }
5057
5058 /* print the subroutines for this glyph, returns the number of them */
5059 int
5060 print_glyph_subs(
5061            int glyphno,
5062            int startid /* start numbering subroutines from this id */
5063 )
5064 {
5065         GLYPH *g;
5066         int i, grp;
5067
5068         g = &glyph_list[glyphno];
5069
5070         if(!hints || !subhints || g->nsg<1)
5071                 return 0;
5072
5073         g->firstsubr=startid;
5074
5075 #if 0
5076         fprintf(pfa_file, "%% %s %d\n", g->name, g->nsg);
5077 #endif
5078         for(grp=0; grp<g->nsg; grp++) {
5079                 fprintf(pfa_file, "dup %d {\n", startid++);
5080                 for(i= (grp==0)? 0 : g->nsbs[grp-1]; i<g->nsbs[grp]; i++)
5081                         fprintf(pfa_file, "\t%d %d %cstem\n", g->sbstems[i].low,
5082                                 g->sbstems[i].high-g->sbstems[i].low,
5083                                 g->sbstems[i].isvert ? 'v' : 'h');
5084                 fprintf(pfa_file, "\treturn\n\t} NP\n");
5085         }
5086
5087         return g->nsg;
5088 }
5089
5090 void
5091 print_glyph_metrics(
5092            int code,
5093            int glyphno
5094 )
5095 {
5096         GLYPH *g;
5097
5098         g = &glyph_list[glyphno];
5099
5100         if(transform)
5101           fprintf(afm_file, "C %d ; WX %d ; N %s ; B %d %d %d %d ;\n",
5102                   code, g->scaledwidth, g->name,
5103                   iscale(g->xMin), iscale(g->yMin), iscale(g->xMax), iscale(g->yMax));
5104         else
5105           fprintf(afm_file, "C %d ; WX %d ; N %s ; B %d %d %d %d ;\n",
5106                   code, g->scaledwidth, g->name,
5107                   g->xMin, g->yMin, g->xMax, g->yMax);
5108 }
5109
5110 /*
5111  SB:
5112  An important note about the BlueValues.
5113
5114  The Adobe documentation says that the maximal width of a Blue zone
5115  is connected to the value of BlueScale, which is by default 0.039625.
5116  The BlueScale value defines, at which point size the overshoot
5117  suppression be disabled.
5118
5119  The formula for it that is given in the manual is:
5120
5121   BlueScale=point_size/240, for a 300dpi device
5122
5123  that makes us wonder what is this 240 standing for. Incidentally
5124  240=72*1000/300, where 72 is the relation between inches and points,
5125  1000 is the size of the glyph matrix, and 300dpi is the resolution of
5126  the output device. Knowing that we can recalculate the formula for
5127  the font size in pixels rather than points:
5128
5129   BlueScale=pixel_size/1000
5130
5131  That looks a lot simpler than the original formula, does not it ?
5132  And the limitation about the maximal width of zone also looks
5133  a lot simpler after the transformation:
5134
5135   max_width < 1000/pixel_size
5136
5137  that ensures that even at the maximal pixel size when the overshoot
5138  suppression is disabled the zone width will be less than one pixel.
5139  This is important, failure to comply to this limit will result in
5140  really ugly fonts (been there, done that). But knowing the formula
5141  for the pixel width, we see that in fact we can use the maximal width
5142  of 24, not 23 as specified in the manual.
5143
5144 */
5145
5146 #define MAXBLUEWIDTH (24)
5147
5148 /*
5149  * Find the indexes of the most frequent values
5150  * in the hystogram, sort them in ascending order, and save which one
5151  * was the best one (if asked).
5152  * Returns the number of values found (may be less than maximal because
5153  * we ignore the zero values)
5154  */
5155
5156 #define MAXHYST (2000)          /* size of the hystogram */
5157 #define HYSTBASE 500
5158
5159 static int
5160 besthyst(
5161          int *hyst,             /* the hystogram */
5162          int base,              /* the base point of the hystogram */
5163          int *best,             /* the array for indexes of best values */
5164          int nbest,             /* its allocated size */
5165          int width,             /* minimal difference between indexes */
5166          int *bestindp          /* returned top point */
5167 )
5168 {
5169         unsigned char   hused[MAXHYST / 8 + 1];
5170         int             i, max, j, w, last = 0;
5171         int             nf = 0;
5172
5173         width--;
5174
5175         memset(hused, 0 , sizeof hused);
5176
5177         max = 1;
5178         for (i = 0; i < nbest && max != 0; i++) {
5179                 best[i] = 0;
5180                 max = 0;
5181                 for (j = 1; j < MAXHYST - 1; j++) {
5182                         w = hyst[j];
5183
5184                         if (w > max && (hused[j>>3] & (1 << (j & 0x07))) == 0) {
5185                                 best[i] = j;
5186                                 max = w;
5187                         }
5188                 }
5189                 if (max != 0) {
5190                         if (max < last/2) {
5191                                 /* do not pick the too low values */
5192                                 break;
5193                         }
5194                         for (j = best[i] - width; j <= best[i] + width; j++) {
5195                                 if (j >= 0 && j < MAXHYST)
5196                                         hused[j >> 3] |= (1 << (j & 0x07));
5197                         }
5198                         last = max;
5199                         best[i] -= base;
5200                         nf = i + 1;
5201                 }
5202         }
5203
5204         if (bestindp)
5205                 *bestindp = best[0];
5206
5207         /* sort the indexes in ascending order */
5208         for (i = 0; i < nf; i++) {
5209                 for (j = i + 1; j < nf; j++)
5210                         if (best[j] < best[i]) {
5211                                 w = best[i];
5212                                 best[i] = best[j];
5213                                 best[j] = w;
5214                         }
5215         }
5216
5217         return nf;
5218 }
5219
5220 /*
5221  * Find the next best Blue zone in the hystogram.
5222  * Return the weight of the found zone.
5223  */
5224
5225 static int
5226 bestblue(
5227          short *zhyst,          /* the zones hystogram */
5228          short *physt,          /* the points hystogram */
5229          short *ozhyst,         /* the other zones hystogram */
5230          int *bluetab           /* where to put the found zone */
5231 )
5232 {
5233         int             i, j, w, max, ind, first, last;
5234
5235         /* find the highest point in the zones hystogram */
5236         /* if we have a plateau, take its center */
5237         /* if we have multiple peaks, take the first one */
5238
5239         max = -1;
5240         first = last = -10;
5241         for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) {
5242                 w = zhyst[i];
5243                 if (w > max) {
5244                         first = last = i;
5245                         max = w;
5246                 } else if (w == max) {
5247                         if (last == i - 1)
5248                                 last = i;
5249                 }
5250         }
5251         ind = (first + last) / 2;
5252
5253         if (max == 0)           /* no zones left */
5254                 return 0;
5255
5256         /* now we reuse `first' and `last' as inclusive borders of the zone */
5257         first = ind;
5258         last = ind + (MAXBLUEWIDTH - 1);
5259
5260         /* our maximal width is far too big, so we try to make it narrower */
5261         w = max;
5262         j = (w & 1);            /* a pseudo-random bit */
5263         while (1) {
5264                 while (physt[first] == 0)
5265                         first++;
5266                 while (physt[last] == 0)
5267                         last--;
5268                 if (last - first < (MAXBLUEWIDTH * 2 / 3) || (max - w) * 10 > max)
5269                         break;
5270
5271                 if (physt[first] < physt[last]
5272                     || physt[first] == physt[last] && j) {
5273                         if (physt[first] * 20 > w)      /* if weight is >5%,
5274                                                          * stop */
5275                                 break;
5276                         w -= physt[first];
5277                         first++;
5278                         j = 0;
5279                 } else {
5280                         if (physt[last] * 20 > w)       /* if weight is >5%,
5281                                                          * stop */
5282                                 break;
5283                         w -= physt[last];
5284                         last--;
5285                         j = 1;
5286                 }
5287         }
5288
5289         /* save our zone */
5290         bluetab[0] = first - HYSTBASE;
5291         bluetab[1] = last - HYSTBASE;
5292
5293         /* invalidate all the zones overlapping with this one */
5294         /* the constant of 2 is determined by the default value of BlueFuzz */
5295         for (i = first - (MAXBLUEWIDTH - 1) - 2; i <= last + 2; i++)
5296                 if (i >= 0 && i < MAXHYST) {
5297                         zhyst[i] = 0;
5298                         ozhyst[i] = 0;
5299                 }
5300         return w;
5301 }
5302
5303 /*
5304  * Try to find the Blue Values, bounding box and italic angle
5305  */
5306
5307 void
5308 findblues(void)
5309 {
5310         /* hystograms for upper and lower zones */
5311         short           hystl[MAXHYST];
5312         short           hystu[MAXHYST];
5313         short           zuhyst[MAXHYST];
5314         short           zlhyst[MAXHYST];
5315         int             nchars;
5316         int             i, j, k, w, max;
5317         GENTRY         *ge;
5318         GLYPH          *g;
5319         double          ang;
5320
5321         /* find the lowest and highest points of glyphs */
5322         /* and by the way build the values for FontBBox */
5323         /* and build the hystogram for the ItalicAngle */
5324
5325         /* re-use hystl for the hystogram of italic angle */
5326
5327         bbox[0] = bbox[1] = 5000;
5328         bbox[2] = bbox[3] = -5000;
5329
5330         for (i = 0; i < MAXHYST; i++)
5331                 hystl[i] = 0;
5332
5333         nchars = 0;
5334
5335         for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
5336                 if (g->flags & GF_USED) {
5337                         nchars++;
5338
5339                         g->rymin = 5000;
5340                         g->rymax = -5000;
5341                         for (ge = g->entries; ge != 0; ge = ge->next) {
5342                                 if (ge->type == GE_LINE) {
5343
5344                                         j = ge->iy3 - ge->prev->iy3;
5345                                         k = ge->ix3 - ge->prev->ix3;
5346                                         if (j > 0)
5347                                                 ang = atan2(-k, j) * 180.0 / M_PI;
5348                                         else
5349                                                 ang = atan2(k, -j) * 180.0 / M_PI;
5350
5351                                         k /= 100;
5352                                         j /= 100;
5353                                         if (ang > -45.0 && ang < 45.0) {
5354                                                 /*
5355                                                  * be careful to not overflow
5356                                                  * the counter
5357                                                  */
5358                                                 hystl[HYSTBASE + (int) (ang * 10.0)] += (k * k + j * j) / 4;
5359                                         }
5360                                         if (ge->iy3 == ge->prev->iy3) {
5361                                                 if (ge->iy3 <= g->rymin) {
5362                                                         g->rymin = ge->iy3;
5363                                                         g->flatymin = 1;
5364                                                 }
5365                                                 if (ge->iy3 >= g->rymax) {
5366                                                         g->rymax = ge->iy3;
5367                                                         g->flatymax = 1;
5368                                                 }
5369                                         } else {
5370                                                 if (ge->iy3 < g->rymin) {
5371                                                         g->rymin = ge->iy3;
5372                                                         g->flatymin = 0;
5373                                                 }
5374                                                 if (ge->iy3 > g->rymax) {
5375                                                         g->rymax = ge->iy3;
5376                                                         g->flatymax = 0;
5377                                                 }
5378                                         }
5379                                 } else if (ge->type == GE_CURVE) {
5380                                         if (ge->iy3 < g->rymin) {
5381                                                 g->rymin = ge->iy3;
5382                                                 g->flatymin = 0;
5383                                         }
5384                                         if (ge->iy3 > g->rymax) {
5385                                                 g->rymax = ge->iy3;
5386                                                 g->flatymax = 0;
5387                                         }
5388                                 }
5389                                 if (ge->type == GE_LINE || ge->type == GE_CURVE) {
5390                                         if (ge->ix3 < bbox[0])
5391                                                 bbox[0] = ge->ix3;
5392                                         if (ge->ix3 > bbox[2])
5393                                                 bbox[2] = ge->ix3;
5394                                         if (ge->iy3 < bbox[1])
5395                                                 bbox[1] = ge->iy3;
5396                                         if (ge->iy3 > bbox[3])
5397                                                 bbox[3] = ge->iy3;
5398                                 }
5399                         }
5400                 }
5401         }
5402
5403         /* get the most popular angle */
5404         max = 0;
5405         w = 0;
5406         for (i = 0; i < MAXHYST; i++) {
5407                 if (hystl[i] > w) {
5408                         w = hystl[i];
5409                         max = i;
5410                 }
5411         }
5412         ang = (double) (max - HYSTBASE) / 10.0;
5413         WARNING_2 fprintf(stderr, "Guessed italic angle: %f\n", ang);
5414         if (italic_angle == 0.0)
5415                 italic_angle = ang;
5416
5417         /* build the hystogram of the lower points */
5418         for (i = 0; i < MAXHYST; i++)
5419                 hystl[i] = 0;
5420
5421         for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
5422                 if ((g->flags & GF_USED)
5423                     && g->rymin + HYSTBASE >= 0 && g->rymin < MAXHYST - HYSTBASE) {
5424                         hystl[g->rymin + HYSTBASE]++;
5425                 }
5426         }
5427
5428         /* build the hystogram of the upper points */
5429         for (i = 0; i < MAXHYST; i++)
5430                 hystu[i] = 0;
5431
5432         for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
5433                 if ((g->flags & GF_USED)
5434                     && g->rymax + HYSTBASE >= 0 && g->rymax < MAXHYST - HYSTBASE) {
5435                         hystu[g->rymax + HYSTBASE]++;
5436                 }
5437         }
5438
5439         /* build the hystogram of all the possible lower zones with max width */
5440         for (i = 0; i < MAXHYST; i++)
5441                 zlhyst[i] = 0;
5442
5443         for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) {
5444                 for (j = 0; j < MAXBLUEWIDTH; j++)
5445                         zlhyst[i] += hystl[i + j];
5446         }
5447
5448         /* build the hystogram of all the possible upper zones with max width */
5449         for (i = 0; i < MAXHYST; i++)
5450                 zuhyst[i] = 0;
5451
5452         for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) {
5453                 for (j = 0; j < MAXBLUEWIDTH; j++)
5454                         zuhyst[i] += hystu[i + j];
5455         }
5456
5457         /* find the baseline */
5458         w = bestblue(zlhyst, hystl, zuhyst, &bluevalues[0]);
5459         if (0)
5460                 fprintf(stderr, "BaselineBlue zone %d%% %d...%d\n", w * 100 / nchars,
5461                                 bluevalues[0], bluevalues[1]);
5462
5463         if (w == 0)             /* no baseline, something weird */
5464                 return;
5465
5466         /* find the upper zones */
5467         for (nblues = 2; nblues < 14; nblues += 2) {
5468                 w = bestblue(zuhyst, hystu, zlhyst, &bluevalues[nblues]);
5469
5470                 if (0)
5471                         fprintf(stderr, "Blue zone %d%% %d...%d\n", w * 100 / nchars,
5472                                 bluevalues[nblues], bluevalues[nblues+1]);
5473
5474                 if (w * 20 < nchars)
5475                         break;  /* don't save this zone */
5476         }
5477
5478         /* find the lower zones */
5479         for (notherb = 0; notherb < 10; notherb += 2) {
5480                 w = bestblue(zlhyst, hystl, zuhyst, &otherblues[notherb]);
5481
5482                 if (0)
5483                         fprintf(stderr, "OtherBlue zone %d%% %d...%d\n", w * 100 / nchars,
5484                                 otherblues[notherb], otherblues[notherb+1]);
5485
5486
5487                 if (w * 20 < nchars)
5488                         break;  /* don't save this zone */
5489         }
5490
5491 }
5492
5493 /*
5494  * Find the actual width of the glyph and modify the
5495  * description to reflect it. Not guaranteed to do
5496  * any good, may make character spacing too wide.
5497  */
5498
5499 void
5500 docorrectwidth(void)
5501 {
5502         int             i;
5503         GENTRY         *ge;
5504         GLYPH          *g;
5505         int             xmin, xmax;
5506         int             maxwidth, minsp;
5507
5508         /* enforce this minimal spacing,
5509          * we limit the amount of the enforced spacing to avoid
5510          * spacing the bold wonts too widely
5511          */
5512         minsp = (stdhw>60 || stdhw<10)? 60 : stdhw;
5513
5514         for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
5515                 g->oldwidth=g->scaledwidth; /* save the old width, will need for AFM */
5516
5517                 if (correctwidth && g->flags & GF_USED) {
5518                         xmin = 5000;
5519                         xmax = -5000;
5520                         for (ge = g->entries; ge != 0; ge = ge->next) {
5521                                 if (ge->type != GE_LINE && ge->type != GE_CURVE)
5522                                         continue;
5523
5524                                 if (ge->ix3 <= xmin) {
5525                                         xmin = ge->ix3;
5526                                 }
5527                                 if (ge->ix3 >= xmax) {
5528                                         xmax = ge->ix3;
5529                                 }
5530                         }
5531
5532                         maxwidth=xmax+minsp;
5533                         if( g->scaledwidth < maxwidth ) {
5534                                 g->scaledwidth = maxwidth;
5535                                 WARNING_3 fprintf(stderr, "glyph %s: extended from %d to %d\n",
5536                                         g->name, g->oldwidth, g->scaledwidth );
5537                         }
5538                 }
5539         }
5540
5541 }
5542
5543 /*
5544  * Try to find the typical stem widths
5545  */
5546
5547 void
5548 stemstatistics(void)
5549 {
5550 #define MINDIST 10 /* minimal distance between the widths */
5551         int             hyst[MAXHYST+MINDIST*2];
5552         int             best[12];
5553         int             i, j, k, w;
5554         int             nchars;
5555         int             ns;
5556         STEM           *s;
5557         GLYPH          *g;
5558
5559         /* start with typical stem width */
5560
5561         nchars=0;
5562
5563         /* build the hystogram of horizontal stem widths */
5564         memset(hyst, 0, sizeof hyst);
5565
5566         for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
5567                 if (g->flags & GF_USED) {
5568                         nchars++;
5569                         s = g->hstems;
5570                         for (j = 0; j < g->nhs; j += 2) {
5571                                 if ((s[j].flags | s[j + 1].flags) & ST_END)
5572                                         continue;
5573                                 w = s[j + 1].value - s[j].value+1;
5574                                 if(w==20) /* split stems should not be counted */
5575                                         continue;
5576                                 if (w > 0 && w < MAXHYST - 1) {
5577                                         /*
5578                                          * handle some fuzz present in
5579                                          * converted fonts
5580                                          */
5581                                         hyst[w+MINDIST] += MINDIST-1;
5582                                         for(k=1; k<MINDIST-1; k++) {
5583                                                 hyst[w+MINDIST + k] += MINDIST-1-k;
5584                                                 hyst[w+MINDIST - k] += MINDIST-1-k;
5585                                         }
5586                                 }
5587                         }
5588                 }
5589         }
5590
5591         /* find 12 most frequent values */
5592         ns = besthyst(hyst+MINDIST, 0, best, 12, MINDIST, &stdhw);
5593
5594         /* store data in stemsnaph */
5595         for (i = 0; i < ns; i++)
5596                 stemsnaph[i] = best[i];
5597         if (ns < 12)
5598                 stemsnaph[ns] = 0;
5599
5600         /* build the hystogram of vertical stem widths */
5601         memset(hyst, 0, sizeof hyst);
5602
5603         for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
5604                 if (g->flags & GF_USED) {
5605                         s = g->vstems;
5606                         for (j = 0; j < g->nvs; j += 2) {
5607                                 if ((s[j].flags | s[j + 1].flags) & ST_END)
5608                                         continue;
5609                                 w = s[j + 1].value - s[j].value+1;
5610                                 if (w > 0 && w < MAXHYST - 1) {
5611                                         /*
5612                                          * handle some fuzz present in
5613                                          * converted fonts
5614                                          */
5615                                         hyst[w+MINDIST] += MINDIST-1;
5616                                         for(k=1; k<MINDIST-1; k++) {
5617                                                 hyst[w+MINDIST + k] += MINDIST-1-k;
5618                                                 hyst[w+MINDIST - k] += MINDIST-1-k;
5619                                         }
5620                                 }
5621                         }
5622                 }
5623         }
5624
5625         /* find 12 most frequent values */
5626         ns = besthyst(hyst+MINDIST, 0, best, 12, MINDIST, &stdvw);
5627
5628         /* store data in stemsnaph */
5629         for (i = 0; i < ns; i++)
5630                 stemsnapv[i] = best[i];
5631         if (ns < 12)
5632                 stemsnapv[ns] = 0;
5633
5634 #undef MINDIST
5635 }
5636
5637 /*
5638  * SB
5639  * A funny thing: TTF paths are going in reverse direction compared
5640  * to Type1. So after all (because the rest of logic uses TTF
5641  * path directions) we have to reverse the paths.
5642  *
5643  * It was a big headache to discover that.
5644  */
5645
5646 /* works on both int and float paths */
5647
5648 void
5649 reversepathsfromto(
5650                    GENTRY * from,
5651                    GENTRY * to
5652 )
5653 {
5654         GENTRY         *ge, *nge, *pge;
5655         GENTRY         *cur, *next;
5656         int i, n, ilast[2];
5657         double flast[2], f;
5658
5659         for (ge = from; ge != 0 && ge != to; ge = ge->next) {
5660                 if(ge->type == GE_LINE || ge->type == GE_CURVE) {
5661                         if (ISDBG(REVERSAL))
5662                                 fprintf(stderr, "reverse path 0x%x <- 0x%x, 0x%x\n", ge, ge->prev, ge->bkwd);
5663
5664                         /* cut out the path itself */
5665                         pge = ge->prev; /* GE_MOVE */
5666                         if (pge == 0) {
5667                                 fprintf(stderr, "**! No MOVE before line !!! Fatal. ****\n");
5668                                 exit(1);
5669                         }
5670                         nge = ge->bkwd->next; /* GE_PATH */
5671                         pge->next = nge;
5672                         nge->prev = pge;
5673                         ge->bkwd->next = 0; /* mark end of chain */
5674
5675                         /* remember the starting point */
5676                         if(ge->flags & GEF_FLOAT) {
5677                                 flast[0] = pge->fx3;
5678                                 flast[1] = pge->fy3;
5679                         } else {
5680                                 ilast[0] = pge->ix3;
5681                                 ilast[1] = pge->iy3;
5682                         }
5683
5684                         /* then reinsert them in backwards order */
5685                         for(cur = ge; cur != 0; cur = next ) {
5686                                 next = cur->next; /* or addgeafter() will screw it up */
5687                                 if(cur->flags & GEF_FLOAT) {
5688                                         for(i=0; i<2; i++) {
5689                                                 /* reverse the direction of path element */
5690                                                 f = cur->fpoints[i][0];
5691                                                 cur->fpoints[i][0] = cur->fpoints[i][1];
5692                                                 cur->fpoints[i][1] = f;
5693                                                 f = flast[i];
5694                                                 flast[i] = cur->fpoints[i][2];
5695                                                 cur->fpoints[i][2] = f;
5696                                         }
5697                                 } else {
5698                                         for(i=0; i<2; i++) {
5699                                                 /* reverse the direction of path element */
5700                                                 n = cur->ipoints[i][0];
5701                                                 cur->ipoints[i][0] = cur->ipoints[i][1];
5702                                                 cur->ipoints[i][1] = n;
5703                                                 n = ilast[i];
5704                                                 ilast[i] = cur->ipoints[i][2];
5705                                                 cur->ipoints[i][2] = n;
5706                                         }
5707                                 }
5708                                 addgeafter(pge, cur);
5709                         }
5710
5711                         /* restore the starting point */
5712                         if(ge->flags & GEF_FLOAT) {
5713                                 pge->fx3 = flast[0];
5714                                 pge->fy3 = flast[1];
5715                         } else {
5716                                 pge->ix3 = ilast[0];
5717                                 pge->iy3 = ilast[1];
5718                         }
5719
5720                         ge = nge;
5721                 }
5722
5723         }
5724 }
5725
5726 void
5727 reversepaths(
5728              GLYPH * g
5729 )
5730 {
5731         reversepathsfromto(g->entries, NULL);
5732 }
5733
5734 /* add a kerning pair information, scales the value */
5735
5736 void
5737 addkernpair(
5738         unsigned id1,
5739         unsigned id2,
5740         int unscval
5741 )
5742 {
5743         static unsigned char *bits = 0;
5744         static int lastid;
5745         GLYPH *g = &glyph_list[id1];
5746         int i, n;
5747         struct kern *p;
5748
5749         if(unscval == 0 || id1 >= numglyphs || id2 >= numglyphs)
5750                 return;
5751
5752         if( (glyph_list[id1].flags & GF_USED)==0
5753         || (glyph_list[id2].flags & GF_USED)==0 )
5754                 return;
5755
5756         if(bits == 0) {
5757                 bits = calloc( BITMAP_BYTES(numglyphs), 1);
5758                 if (bits == NULL) {
5759                         fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
5760                         exit(255);
5761                 }
5762                 lastid = id1;
5763         }
5764
5765         if(lastid != id1) {
5766                 /* refill the bitmap cache */
5767                 memset(bits, 0,BITMAP_BYTES(numglyphs));
5768                 p = g->kern;
5769                 for(i=g->kerncount; i>0; i--) {
5770                         n = (p++)->id;
5771                         SET_BITMAP(bits, n);
5772                 }
5773                 lastid = id1;
5774         }
5775
5776         if(IS_BITMAP(bits, id2))
5777                 return; /* duplicate */
5778
5779         if(g->kerncount <= g->kernalloc) {
5780                 g->kernalloc += 8;
5781                 p = realloc(g->kern, sizeof(struct kern) * g->kernalloc);
5782                 if(p == 0) {
5783                         fprintf (stderr, "** realloc failed, kerning data will be incomplete\n");
5784                 }
5785                 g->kern = p;
5786         }
5787
5788         SET_BITMAP(bits, id2);
5789         p = &g->kern[g->kerncount];
5790         p->id = id2;
5791         p->val = iscale(unscval) - (g->scaledwidth - g->oldwidth);
5792         g->kerncount++;
5793         kerning_pairs++;
5794 }
5795
5796 /* print out the kerning information */
5797
5798 void
5799 print_kerning(
5800         FILE *afm_file
5801 )
5802 {
5803         int     i, j, n;
5804         GLYPH *g;
5805         struct kern *p;
5806
5807         if( kerning_pairs == 0 )
5808                 return;
5809
5810         fprintf(afm_file, "StartKernData\n");
5811         fprintf(afm_file, "StartKernPairs %hd\n", kerning_pairs);
5812
5813         for(i=0; i<numglyphs; i++)  {
5814                 g = &glyph_list[i];
5815                 if( (g->flags & GF_USED) ==0)
5816                         continue;
5817                 p = g->kern;
5818                 for(j=g->kerncount; j>0; j--, p++) {
5819                         fprintf(afm_file, "KPX %s %s %d\n", g->name,
5820                                 glyph_list[ p->id ].name, p->val );
5821                 }
5822         }
5823
5824         fprintf(afm_file, "EndKernPairs\n");
5825         fprintf(afm_file, "EndKernData\n");
5826 }
5827
5828
5829 #if 0
5830
5831 /*
5832 ** This function is commented out because the information
5833 ** collected by it is not used anywhere else yet. Now
5834 ** it only collects the directions of contours. And the
5835 ** direction of contours gets fixed already in draw_glyf().
5836 **
5837 ***********************************************
5838 **
5839 ** Here we expect that the paths are already closed.
5840 ** We also expect that the contours do not intersect
5841 ** and that curves doesn't cross any border of quadrant.
5842 **
5843 ** Find which contours go inside which and what is
5844 ** their proper direction. Then fix the direction
5845 ** to make it right.
5846 **
5847 */
5848
5849 #define MAXCONT 1000
5850
5851 void
5852 fixcontours(
5853             GLYPH * g
5854 )
5855 {
5856         CONTOUR         cont[MAXCONT];
5857         short           ymax[MAXCONT];  /* the highest point */
5858         short           xofmax[MAXCONT];        /* X-coordinate of any point
5859                                                  * at ymax */
5860         short           ymin[MAXCONT];  /* the lowest point */
5861         short           xofmin[MAXCONT];        /* X-coordinate of any point
5862                                                  * at ymin */
5863         short           count[MAXCONT]; /* count of lines */
5864         char            dir[MAXCONT];   /* in which direction they must go */
5865         GENTRY         *start[MAXCONT], *minptr[MAXCONT], *maxptr[MAXCONT];
5866         int             ncont;
5867         int             i;
5868         int             dx1, dy1, dx2, dy2;
5869         GENTRY         *ge, *nge;
5870
5871         /* find the contours and their most upper/lower points */
5872         ncont = 0;
5873         ymax[0] = -5000;
5874         ymin[0] = 5000;
5875         for (ge = g->entries; ge != 0; ge = ge->next) {
5876                 if (ge->type == GE_LINE || ge->type == GE_CURVE) {
5877                         if (ge->iy3 > ymax[ncont]) {
5878                                 ymax[ncont] = ge->iy3;
5879                                 xofmax[ncont] = ge->ix3;
5880                                 maxptr[ncont] = ge;
5881                         }
5882                         if (ge->iy3 < ymin[ncont]) {
5883                                 ymin[ncont] = ge->iy3;
5884                                 xofmin[ncont] = ge->ix3;
5885                                 minptr[ncont] = ge;
5886                         }
5887                 }
5888                 if (ge->frwd != ge->next) {
5889                         start[ncont++] = ge->frwd;
5890                         ymax[ncont] = -5000;
5891                         ymin[ncont] = 5000;
5892                 }
5893         }
5894
5895         /* determine the directions of contours */
5896         for (i = 0; i < ncont; i++) {
5897                 ge = minptr[i];
5898                 nge = ge->frwd;
5899
5900                 if (ge->type == GE_CURVE) {
5901                         dx1 = ge->ix3 - ge->ix2;
5902                         dy1 = ge->iy3 - ge->iy2;
5903
5904                         if (dx1 == 0 && dy1 == 0) {     /* a pathological case */
5905                                 dx1 = ge->ix3 - ge->ix1;
5906                                 dy1 = ge->iy3 - ge->iy1;
5907                         }
5908                         if (dx1 == 0 && dy1 == 0) {     /* a more pathological
5909                                                          * case */
5910                                 dx1 = ge->ix3 - ge->prev->ix3;
5911                                 dy1 = ge->iy3 - ge->prev->iy3;
5912                         }
5913                 } else {
5914                         dx1 = ge->ix3 - ge->prev->ix3;
5915                         dy1 = ge->iy3 - ge->prev->iy3;
5916                 }
5917                 if (nge->type == GE_CURVE) {
5918                         dx2 = ge->ix3 - nge->ix1;
5919                         dy2 = ge->iy3 - nge->iy1;
5920                         if (dx1 == 0 && dy1 == 0) {     /* a pathological case */
5921                                 dx2 = ge->ix3 - nge->ix2;
5922                                 dy2 = ge->iy3 - nge->iy2;
5923                         }
5924                         if (dx1 == 0 && dy1 == 0) {     /* a more pathological
5925                                                          * case */
5926                                 dx2 = ge->ix3 - nge->ix3;
5927                                 dy2 = ge->iy3 - nge->iy3;
5928                         }
5929                 } else {
5930                         dx2 = ge->ix3 - nge->ix3;
5931                         dy2 = ge->iy3 - nge->iy3;
5932                 }
5933
5934                 /* compare angles */
5935                 cont[i].direction = DIR_INNER;
5936                 if (dy1 == 0) {
5937                         if (dx1 < 0)
5938                                 cont[i].direction = DIR_OUTER;
5939                 } else if (dy2 == 0) {
5940                         if (dx2 > 0)
5941                                 cont[i].direction = DIR_OUTER;
5942                 } else if (dx2 * dy1 < dx1 * dy2)
5943                         cont[i].direction = DIR_OUTER;
5944
5945                 cont[i].ymin = ymin[i];
5946                 cont[i].xofmin = xofmin[i];
5947         }
5948
5949         /* save the information that may be needed further */
5950         g->ncontours = ncont;
5951         if (ncont > 0) {
5952                 g->contours = malloc(sizeof(CONTOUR) * ncont);
5953                 if (g->contours == 0) {
5954                         fprintf(stderr, "***** Memory allocation error *****\n");
5955                         exit(255);
5956                 }
5957                 memcpy(g->contours, cont, sizeof(CONTOUR) * ncont);
5958         }
5959 }
5960
5961 #endif
5962
5963 /*
5964  *
5965  */
5966