lib/tacontrol.c

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