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