lib/tacontrol.c

   1 /* tacontrol.c */
   2
   3 /*
   4  * Copyright (C) 2014 by Werner Lemberg.
   5  *
   6  * This file is part of the ttfautohint library, and may only be used,
   7  * modified, and distributed under the terms given in `COPYING'.  By
   8  * continuing to use, modify, or distribute this file you indicate that you
   9  * have read `COPYING' and understand and accept it fully.
  10  *
  11  * The file `COPYING' mentioned in the previous paragraph is distributed
  12  * with the ttfautohint library.
  13  */
  14
  15 #include "ta.h"
  16
  17 #include <locale.h>
  18 #include <errno.h>
  19 #include <ctype.h>
  20 #include <math.h>
  21 #include <stdbool.h> /* for llrb.h */
  22
  23 #include "llrb.h" /* a red-black tree implementation */
  24 #include "tacontrol-bison.h"
  25
  26 Control*
  27 TA_control_new(Control_Type type,
  28                long font_idx,
  29                long glyph_idx,
  30                number_range* point_set,
  31                double x_shift,
  32                double y_shift,
  33                number_range* ppem_set)
  34 {
  35   Control* control;
  36
  37
  38   control = (Control*)malloc(sizeof (Control));
  39   if (!control)
  40     return NULL;
  41
  42   control->type = type;
  43
  44   control->font_idx = font_idx;
  45   control->glyph_idx = glyph_idx;
  46   control->points = number_set_reverse(point_set);
  47
  48   switch (control->type)
  49   {
  50   case Control_Delta_before_IUP:
  51   case Control_Delta_after_IUP:
  52     /* we round shift values to multiples of 1/(2^CONTROL_DELTA_SHIFT) */
  53     control->x_shift = (char)(x_shift * CONTROL_DELTA_FACTOR
  54                               + (x_shift > 0 ? 0.5 : -0.5));
  55     control->y_shift = (char)(y_shift * CONTROL_DELTA_FACTOR
  56                               + (y_shift > 0 ? 0.5 : -0.5));
  57     break;
  58
  59   case Control_Point_Dir:
  60     /* values -1, 1, and 4 mean `left', `right', and `none', respectively */
  61     control->x_shift = x_shift;
  62     control->y_shift = 0;
  63     break;
  64   }
  65
  66   control->ppems = number_set_reverse(ppem_set);
  67   control->next = NULL;
  68
  69   return control;
  70 }
  71
  72
  73 Control*
  74 TA_control_prepend(Control* list,
  75                    Control* element)
  76 {
  77   if (!element)
  78     return list;
  79
  80   element->next = list;
  81
  82   return element;
  83 }
  84
  85
  86 Control*
  87 TA_control_reverse(Control* list)
  88 {
  89   Control* cur;
  90
  91
  92   cur = list;
  93   list = NULL;
  94
  95   while (cur)
  96   {
  97     Control* tmp;
  98
  99
 100     tmp = cur;
 101     cur = cur->next;
 102     tmp->next = list;
 103     list = tmp;
 104   }
 105
 106   return list;
 107 }
 108
 109
 110 void
 111 TA_control_free(Control* control)
 112 {
 113   while (control)
 114   {
 115     Control* tmp;
 116
 117
 118     number_set_free(control->points);
 119     number_set_free(control->ppems);
 120
 121     tmp = control;
 122     control = control->next;
 123     free(tmp);
 124   }
 125 }
 126
 127
 128 sds
 129 control_show_line(FONT* font,
 130                   Control* control)
 131 {
 132   char glyph_name_buf[64];
 133   char* points_buf = NULL;
 134   char* ppems_buf = NULL;
 135
 136   sds s;
 137
 138   FT_Face face;
 139
 140
 141   s = sdsempty();
 142
 143   if (!control)
 144     goto Exit;
 145
 146   if (control->font_idx >= font->num_sfnts)
 147     goto Exit;
 148
 149   face = font->sfnts[control->font_idx].face;
 150   glyph_name_buf[0] = '\0';
 151   if (FT_HAS_GLYPH_NAMES(face))
 152     FT_Get_Glyph_Name(face, control->glyph_idx, glyph_name_buf, 64);
 153
 154   points_buf = number_set_show(control->points, -1, -1);
 155   if (!points_buf)
 156     goto Exit;
 157   ppems_buf = number_set_show(control->ppems, -1, -1);
 158   if (!ppems_buf)
 159     goto Exit;
 160
 161   switch (control->type)
 162   {
 163   case Control_Delta_before_IUP:
 164     /* not implemented yet */
 165     break;
 166
 167   case Control_Delta_after_IUP:
 168     /* display glyph index if we don't have a glyph name */
 169     if (*glyph_name_buf)
 170       s = sdscatprintf(s, "%ld %s p %s x %.20g y %.20g @ %s",
 171                        control->font_idx,
 172                        glyph_name_buf,
 173                        points_buf,
 174                        (double)control->x_shift / CONTROL_DELTA_FACTOR,
 175                        (double)control->y_shift / CONTROL_DELTA_FACTOR,
 176                        ppems_buf);
 177     else
 178       s = sdscatprintf(s, "%ld %ld p %s x %.20g y %.20g @ %s",
 179                        control->font_idx,
 180                        control->glyph_idx,
 181                        points_buf,
 182                        (double)control->x_shift / CONTROL_DELTA_FACTOR,
 183                        (double)control->y_shift / CONTROL_DELTA_FACTOR,
 184                        ppems_buf);
 185     break;
 186
 187   case Control_Point_Dir:
 188     /* display glyph index if we don't have a glyph name */
 189     if (*glyph_name_buf)
 190       s = sdscatprintf(s, "%ld %s %c %s",
 191                        control->font_idx,
 192                        glyph_name_buf,
 193                        control->x_shift == TA_DIR_LEFT ? 'l'
 194                          : control->x_shift == TA_DIR_RIGHT ? 'r'
 195                            : 'n',
 196                        points_buf);
 197     else
 198       s = sdscatprintf(s, "%ld %ld %c %s",
 199                        control->font_idx,
 200                        control->glyph_idx,
 201                        control->x_shift == TA_DIR_LEFT ? 'l'
 202                          : control->x_shift == TA_DIR_RIGHT ? 'r'
 203                            : 'n',
 204                        points_buf);
 205     break;
 206   }
 207
 208 Exit:
 209   free(points_buf);
 210   free(ppems_buf);
 211
 212   return s;
 213 }
 214
 215
 216 char*
 217 TA_control_show(FONT* font)
 218 {
 219   sds s;
 220   size_t len;
 221   char* res;
 222
 223   Control* control = font->control;
 224
 225
 226   s = sdsempty();
 227
 228   while (control)
 229   {
 230     sds d;
 231
 232
 233     /* append current line to buffer, followed by a newline character */
 234     d = control_show_line(font, control);
 235     if (!d)
 236     {
 237       sdsfree(s);
 238       return NULL;
 239     }
 240     s = sdscatsds(s, d);
 241     sdsfree(d);
 242     s = sdscat(s, "\n");
 243
 244     control = control->next;
 245   }
 246
 247   if (!s)
 248     return NULL;
 249
 250   /* we return an empty string if there is no data */
 251   len = sdslen(s) + 1;
 252   res = (char*)malloc(len);
 253   if (res)
 254     memcpy(res, s, len);
 255
 256   sdsfree(s);
 257
 258   return res;
 259 }
 260
 261
 262 /* Parse control instructions in `font->control_buf'. */
 263
 264 TA_Error
 265 TA_control_parse_buffer(FONT* font,
 266                         char** error_string_p,
 267                         unsigned int* errlinenum_p,
 268                         char** errline_p,
 269                         char** errpos_p)
 270 {
 271   int bison_error;
 272
 273   Control_Context context;
 274
 275
 276   /* nothing to do if no data */
 277   if (!font->control_buf)
 278   {
 279     font->control = NULL;
 280     return TA_Err_Ok;
 281   }
 282
 283   TA_control_scanner_init(&context, font);
 284   if (context.error)
 285     goto Fail;
 286   /* this is `yyparse' in disguise */
 287   bison_error = TA_control_parse(&context);
 288   TA_control_scanner_done(&context);
 289
 290   if (bison_error)
 291   {
 292     if (bison_error == 2)
 293       context.error = TA_Err_Control_Allocation_Error;
 294
 295 Fail:
 296     font->control = NULL;
 297
 298     if (context.error == TA_Err_Control_Allocation_Error
 299         || context.error == TA_Err_Control_Flex_Error)
 300     {
 301       *errlinenum_p = 0;
 302       *errline_p = NULL;
 303       *errpos_p = NULL;
 304       if (context.errmsg)
 305         *error_string_p = strdup(context.errmsg);
 306       else
 307         *error_string_p = strdup(TA_get_error_message(context.error));
 308     }
 309     else
 310     {
 311       int i, ret;
 312       char auxbuf[128];
 313
 314       char* buf_end;
 315       char* p_start;
 316       char* p_end;
 317
 318
 319       /* construct data for `errline_p' */
 320       buf_end = font->control_buf + font->control_len;
 321
 322       p_start = font->control_buf;
 323       if (context.errline_num > 1)
 324       {
 325         i = 1;
 326         while (p_start < buf_end)
 327         {
 328           if (*p_start++ == '\n')
 329           {
 330             i++;
 331             if (i == context.errline_num)
 332               break;
 333           }
 334         }
 335       }
 336
 337       p_end = p_start;
 338       while (p_end < buf_end)
 339       {
 340         if (*p_end == '\n')
 341           break;
 342         p_end++;
 343       }
 344       *errline_p = strndup(p_start, p_end - p_start);
 345
 346       /* construct data for `error_string_p' */
 347       if (context.error == TA_Err_Control_Invalid_Font_Index)
 348         sprintf(auxbuf, " (valid range is [%ld;%ld])",
 349                 0L,
 350                 font->num_sfnts);
 351       else if (context.error == TA_Err_Control_Invalid_Glyph_Index)
 352         sprintf(auxbuf, " (valid range is [%ld;%ld])",
 353                 0L,
 354                 font->sfnts[context.font_idx].face->num_glyphs);
 355       else if (context.error == TA_Err_Control_Invalid_Shift)
 356         sprintf(auxbuf, " (valid interval is [%g;%g])",
 357                 CONTROL_DELTA_SHIFT_MIN,
 358                 CONTROL_DELTA_SHIFT_MAX);
 359       else if (context.error == TA_Err_Control_Invalid_Range)
 360         sprintf(auxbuf, " (values must be within [%ld;%ld])",
 361                 context.number_set_min,
 362                 context.number_set_max);
 363       else
 364         auxbuf[0] = '\0';
 365
 366       ret = asprintf(error_string_p, "%s%s",
 367                      *context.errmsg ? context.errmsg
 368                                      : TA_get_error_message(context.error),
 369                      auxbuf);
 370       if (ret == -1)
 371         *error_string_p = NULL;
 372
 373       if (errline_p)
 374         *errpos_p = *errline_p + context.errline_pos_left - 1;
 375       else
 376         *errpos_p = NULL;
 377
 378       *errlinenum_p = context.errline_num;
 379     }
 380   }
 381   else
 382     font->control = context.result;
 383
 384   return context.error;
 385 }
 386
 387
 388 /* node structure for control instruction data */
 389
 390 typedef struct Node Node;
 391 struct Node
 392 {
 393   LLRB_ENTRY(Node) entry;
 394   Ctrl ctrl;
 395 };
 396
 397
 398 /* comparison function for our red-black tree */
 399
 400 static int
 401 nodecmp(Node* e1,
 402         Node* e2)
 403 {
 404   long diff;
 405
 406
 407   /* sort by font index ... */
 408   diff = e1->ctrl.font_idx - e2->ctrl.font_idx;
 409   if (diff)
 410     goto Exit;
 411
 412   /* ... then by glyph index ... */
 413   diff = e1->ctrl.glyph_idx - e2->ctrl.glyph_idx;
 414   if (diff)
 415     goto Exit;
 416
 417   /* ... then by ppem ... */
 418   diff = e1->ctrl.ppem - e2->ctrl.ppem;
 419   if (diff)
 420     goto Exit;
 421
 422   /* ... then by point index */
 423   diff = e1->ctrl.point_idx - e2->ctrl.point_idx;
 424
 425 Exit:
 426   /* https://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign */
 427   return (diff > 0) - (diff < 0);
 428 }
 429
 430
 431 /* the red-black tree function body */
 432 typedef struct control_data control_data;
 433
 434 LLRB_HEAD(control_data, Node);
 435
 436 /* no trailing semicolon in the next line */
 437 LLRB_GENERATE_STATIC(control_data, Node, entry, nodecmp)
 438
 439
 440 void
 441 TA_control_free_tree(FONT* font)
 442 {
 443   control_data* control_data_head = (control_data*)font->control_data_head;
 444   number_range* control_point_dirs = font->control_point_dirs;
 445
 446   Node* node;
 447   Node* next_node;
 448
 449
 450   if (!control_data_head)
 451     return;
 452
 453   for (node = LLRB_MIN(control_data, control_data_head);
 454        node;
 455        node = next_node)
 456   {
 457     next_node = LLRB_NEXT(control_data, control_data_head, node);
 458     LLRB_REMOVE(control_data, control_data_head, node);
 459     free(node);
 460   }
 461
 462   free(control_data_head);
 463   number_set_free(control_point_dirs);
 464 }
 465
 466
 467 TA_Error
 468 TA_control_build_tree(FONT* font)
 469 {
 470   Control* control = font->control;
 471   control_data* control_data_head;
 472   int emit_newline = 0;
 473
 474
 475   font->control_point_dirs = NULL;
 476   font->control_point_dir_iter.range = NULL;
 477
 478   /* nothing to do if no data */
 479   if (!control)
 480   {
 481     font->control_data_head = NULL;
 482     font->control_data_cur = NULL;
 483     return TA_Err_Ok;
 484   }
 485
 486   control_data_head = (control_data*)malloc(sizeof (control_data));
 487   if (!control_data_head)
 488     return FT_Err_Out_Of_Memory;
 489
 490   LLRB_INIT(control_data_head);
 491
 492   while (control)
 493   {
 494     Control_Type type = control->type;
 495     long font_idx = control->font_idx;
 496     long glyph_idx = control->glyph_idx;
 497     char x_shift = control->x_shift;
 498     char y_shift = control->y_shift;
 499
 500     number_set_iter ppems_iter;
 501     int ppem;
 502
 503
 504     ppems_iter.range = control->ppems;
 505     ppem = number_set_get_first(&ppems_iter);
 506
 507     if (type == Control_Point_Dir)
 508       goto Points_Loop;
 509
 510     while (ppems_iter.range)
 511     {
 512       number_set_iter points_iter;
 513       int point_idx;
 514
 515
 516     Points_Loop:
 517       points_iter.range = control->points;
 518       point_idx = number_set_get_first(&points_iter);
 519
 520       while (points_iter.range)
 521       {
 522         Node* node;
 523         Node* val;
 524
 525
 526         node = (Node*)malloc(sizeof (Node));
 527         if (!node)
 528           return FT_Err_Out_Of_Memory;
 529
 530         node->ctrl.type = type;
 531         node->ctrl.font_idx = font_idx;
 532         node->ctrl.glyph_idx = glyph_idx;
 533         node->ctrl.ppem = ppem;
 534         node->ctrl.point_idx = point_idx;
 535         node->ctrl.x_shift = x_shift;
 536         node->ctrl.y_shift = y_shift;
 537
 538         val = LLRB_INSERT(control_data, control_data_head, node);
 539         if (val)
 540           free(node);
 541         if (val && font->debug)
 542         {
 543           /* entry is already present; we ignore it */
 544           Control d;
 545           number_range ppems;
 546           number_range points;
 547
 548           sds s;
 549
 550
 551           /* construct Control entry for debugging output */
 552           ppems.start = ppem;
 553           ppems.end = ppem;
 554           ppems.next = NULL;
 555           points.start = point_idx;
 556           points.end = point_idx;
 557           points.next = NULL;
 558
 559           d.type = type;
 560           d.font_idx = font_idx;
 561           d.glyph_idx = glyph_idx;
 562           d.points = &points;
 563           d.x_shift = x_shift;
 564           d.y_shift = y_shift;
 565           d.ppems = &ppems;
 566           d.next = NULL;
 567
 568           s = control_show_line(font, &d);
 569           if (s)
 570           {
 571             fprintf(stderr, "Control instruction %s ignored.\n", s);
 572             sdsfree(s);
 573           }
 574
 575           emit_newline = 1;
 576         }
 577
 578         point_idx = number_set_get_next(&points_iter);
 579       }
 580
 581       ppem = number_set_get_next(&ppems_iter);
 582     }
 583
 584     control = control->next;
 585   }
 586
 587   if (font->debug && emit_newline)
 588     fprintf(stderr, "\n");
 589
 590   font->control_data_head = control_data_head;
 591   font->control_data_cur = LLRB_MIN(control_data, control_data_head);
 592
 593   return TA_Err_Ok;
 594 }
 595
 596
 597 /* the next functions are intended to restrict the use of LLRB stuff */
 598 /* related to control instructions to this file, */
 599 /* providing a means to access the data sequentially */
 600
 601 void
 602 TA_control_get_next(FONT* font)
 603 {
 604   Node* node = (Node*)font->control_data_cur;
 605
 606
 607   if (!node)
 608     return;
 609
 610   node = LLRB_NEXT(control_data, /* unused */, node);
 611
 612   font->control_data_cur = node;
 613 }
 614
 615
 616 const Ctrl*
 617 TA_control_get_ctrl(FONT* font)
 618 {
 619   Node* node = (Node*)font->control_data_cur;
 620
 621
 622   return node ? &node->ctrl : NULL;
 623 }
 624
 625
 626 TA_Error
 627 TA_control_point_dir_collect(FONT* font,
 628                              long font_idx,
 629                              long glyph_idx)
 630 {
 631   number_range* control_point_dirs = font->control_point_dirs;
 632
 633
 634   /* nothing to do if no data */
 635   if (!font->control_data_head)
 636     return TA_Err_Ok;
 637
 638   if (control_point_dirs)
 639   {
 640     number_set_free(control_point_dirs);
 641     control_point_dirs = NULL;
 642   }
 643
 644   /*
 645    * The PPEM value for one-point segments is always zero; such control
 646    * instructions are thus sorted before other control instructions for the
 647    * same glyph index -- this fits nicely with the call to
 648    * `TA_control_get_next' in the loop of `TA_sfnt_build_delta_exceptions',
 649    * assuring proper sequential access to the red-black tree.
 650    */
 651   for (;;)
 652   {
 653     const Ctrl* ctrl = TA_control_get_ctrl(font);
 654     number_range* elem;
 655     int point_idx;
 656
 657
 658     if (!ctrl)
 659       break;
 660
 661     /* check type */
 662     if (ctrl->type != Control_Point_Dir)
 663       break;
 664
 665     /* too large values of font and glyph indices in `ctrl' */
 666     /* are handled by later calls of this function */
 667     if (font_idx < ctrl->font_idx
 668         || glyph_idx < ctrl->glyph_idx)
 669       break;
 670
 671     /* we store point index and direction together */
 672     point_idx = (ctrl->point_idx << 2)
 673                 + (ctrl->x_shift == TA_DIR_LEFT ? 0
 674                      : ctrl->x_shift == TA_DIR_RIGHT ? 1
 675                        : 2);
 676
 677     /* don't care about checking valid point indices */
 678     elem = number_set_new(point_idx, point_idx, point_idx, point_idx);
 679     if (elem == NUMBERSET_ALLOCATION_ERROR)
 680     {
 681       number_set_free(control_point_dirs);
 682       return TA_Err_Control_Allocation_Error;
 683     }
 684     control_point_dirs = number_set_prepend(control_point_dirs, elem);
 685
 686     TA_control_get_next(font);
 687   }
 688
 689   font->control_point_dirs = number_set_reverse(control_point_dirs);
 690
 691   return TA_Err_Ok;
 692 }
 693
 694
 695 int
 696 TA_control_point_dir_get_next(FONT* font,
 697                               int* point_idx,
 698                               TA_Direction* dir)
 699 {
 700   number_range* control_point_dirs = font->control_point_dirs;
 701   number_set_iter* control_point_dir_iter = &font->control_point_dir_iter;
 702   int pd_idx;
 703
 704
 705   if (!control_point_dir_iter->range)
 706   {
 707     control_point_dir_iter->range = control_point_dirs;
 708     pd_idx = number_set_get_first(control_point_dir_iter);
 709   }
 710   else
 711     pd_idx = number_set_get_next(control_point_dir_iter);
 712
 713   *point_idx = pd_idx >> 2;
 714   *dir = pd_idx % 4 == 0 ? TA_DIR_LEFT
 715            : pd_idx % 4 == 1 ? TA_DIR_RIGHT
 716              : TA_DIR_NONE;
 717
 718   return control_point_dir_iter->range != NULL;
 719 }
 720
 721 /* end of tacontrol.c */