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