lib/tadeltas.c

   1 /* tadeltas.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
  22 #include "llrb.h" /* a red-black tree implementation */
  23 #include "tadeltas-bison.h"
  24
  25 Deltas*
  26 TA_deltas_new(long font_idx,
  27               long glyph_idx,
  28               number_range* point_set,
  29               double x_shift,
  30               double y_shift,
  31               number_range* ppem_set)
  32 {
  33   Deltas* deltas;
  34
  35
  36   deltas = (Deltas*)malloc(sizeof (Deltas));
  37   if (!deltas)
  38     return NULL;
  39
  40   deltas->font_idx = font_idx;
  41   deltas->glyph_idx = glyph_idx;
  42   deltas->points = number_set_reverse(point_set);
  43
  44   /* we round shift values to multiples of 1/(2^DELTA_SHIFT) */
  45   deltas->x_shift = (char)(x_shift * DELTA_FACTOR
  46                            + (x_shift > 0 ? 0.5 : -0.5));
  47   deltas->y_shift = (char)(y_shift * DELTA_FACTOR
  48                            + (y_shift > 0 ? 0.5 : -0.5));
  49
  50   deltas->ppems = number_set_reverse(ppem_set);
  51   deltas->next = NULL;
  52
  53   return deltas;
  54 }
  55
  56
  57 Deltas*
  58 TA_deltas_prepend(Deltas* list,
  59                   Deltas* element)
  60 {
  61   if (!element)
  62     return list;
  63
  64   element->next = list;
  65
  66   return element;
  67 }
  68
  69
  70 Deltas*
  71 TA_deltas_reverse(Deltas* list)
  72 {
  73   Deltas* cur;
  74
  75
  76   cur = list;
  77   list = NULL;
  78
  79   while (cur)
  80   {
  81     Deltas* tmp;
  82
  83
  84     tmp = cur;
  85     cur = cur->next;
  86     tmp->next = list;
  87     list = tmp;
  88   }
  89
  90   return list;
  91 }
  92
  93
  94 void
  95 TA_deltas_free(Deltas* deltas)
  96 {
  97   while (deltas)
  98   {
  99     Deltas* tmp;
 100
 101
 102     number_set_free(deltas->points);
 103     number_set_free(deltas->ppems);
 104
 105     tmp = deltas;
 106     deltas = deltas->next;
 107     free(tmp);
 108   }
 109 }
 110
 111
 112 /* `len' is the length of the returned string */
 113
 114 char*
 115 deltas_show_line(FONT* font,
 116                  int* len,
 117                  Deltas* deltas)
 118 {
 119   int ret;
 120   char glyph_name_buf[64];
 121   char* points_buf = NULL;
 122   char* ppems_buf = NULL;
 123   char* deltas_buf = NULL;
 124
 125   FT_Face face;
 126
 127
 128   if (!deltas)
 129     return NULL;
 130
 131   if (deltas->font_idx >= font->num_sfnts)
 132     return NULL;
 133
 134   face = font->sfnts[deltas->font_idx].face;
 135   glyph_name_buf[0] = '\0';
 136   if (FT_HAS_GLYPH_NAMES(face))
 137     FT_Get_Glyph_Name(face, deltas->glyph_idx, glyph_name_buf, 64);
 138
 139   points_buf = number_set_show(deltas->points, -1, -1);
 140   if (!points_buf)
 141     goto Exit;
 142   ppems_buf = number_set_show(deltas->ppems, -1, -1);
 143   if (!ppems_buf)
 144     goto Exit;
 145
 146   /* display glyph index if we don't have a glyph name */
 147   if (*glyph_name_buf)
 148     ret = asprintf(&deltas_buf, "%ld %s p %s x %.20g y %.20g @ %s",
 149                    deltas->font_idx,
 150                    glyph_name_buf,
 151                    points_buf,
 152                    (double)deltas->x_shift / DELTA_FACTOR,
 153                    (double)deltas->y_shift / DELTA_FACTOR,
 154                    ppems_buf);
 155   else
 156     ret = asprintf(&deltas_buf, "%ld %ld p %s x %.20g y %.20g @ %s",
 157                    deltas->font_idx,
 158                    deltas->glyph_idx,
 159                    points_buf,
 160                    (double)deltas->x_shift / DELTA_FACTOR,
 161                    (double)deltas->y_shift / DELTA_FACTOR,
 162                    ppems_buf);
 163
 164 Exit:
 165   free(points_buf);
 166   free(ppems_buf);
 167
 168   if (ret == -1)
 169     return NULL;
 170
 171   *len = ret;
 172
 173   return deltas_buf;
 174 }
 175
 176
 177 char*
 178 TA_deltas_show(FONT* font,
 179                Deltas* deltas)
 180 {
 181   char* s;
 182   int s_len;
 183
 184
 185   /* we return an empty string if there is no data */
 186   s = (char*)malloc(1);
 187   if (!s)
 188     return NULL;
 189
 190   *s = '\0';
 191   s_len = 1;
 192
 193   while (deltas)
 194   {
 195     char* tmp;
 196     int tmp_len;
 197     char* s_new;
 198     int s_len_new;
 199
 200
 201     tmp = deltas_show_line(font, &tmp_len, deltas);
 202     if (!tmp)
 203     {
 204       free(s);
 205       return NULL;
 206     }
 207
 208     /* append current line to buffer, followed by a newline character */
 209     s_len_new = s_len + tmp_len + 1;
 210     s_new = (char*)realloc(s, s_len_new);
 211     if (!s_new)
 212     {
 213       free(s);
 214       free(tmp);
 215       return NULL;
 216     }
 217
 218     strcpy(s_new + s_len - 1, tmp);
 219     s_new[s_len_new - 2] = '\n';
 220     s_new[s_len_new - 1] = '\0';
 221
 222     s = s_new;
 223     s_len = s_len_new;
 224
 225     free(tmp);
 226
 227     deltas = deltas->next;
 228   }
 229
 230   return s;
 231 }
 232
 233
 234 /* Parse delta exceptions in `font->deltas_buf'. */
 235
 236 TA_Error
 237 TA_deltas_parse_buffer(FONT* font,
 238                        Deltas** deltas,
 239                        char** error_string_p,
 240                        unsigned int* errlinenum_p,
 241                        char** errline_p,
 242                        char** errpos_p)
 243 {
 244   int bison_error;
 245
 246   Deltas_Context context;
 247
 248
 249   /* nothing to do if no data */
 250   if (!font->deltas_buf)
 251   {
 252     if (deltas)
 253       *deltas = NULL;
 254     return TA_Err_Ok;
 255   }
 256
 257   TA_deltas_scanner_init(&context, font);
 258   if (context.error)
 259     goto Fail;
 260   /* this is `yyparse' in disguise */
 261   bison_error = TA_deltas_parse(&context);
 262   TA_deltas_scanner_done(&context);
 263
 264   if (bison_error)
 265   {
 266     if (bison_error == 2)
 267       context.error = TA_Err_Deltas_Allocation_Error;
 268
 269 Fail:
 270     if (deltas)
 271       *deltas = NULL;
 272
 273     if (context.error == TA_Err_Deltas_Allocation_Error
 274         || context.error == TA_Err_Deltas_Flex_Error)
 275     {
 276       *errlinenum_p = 0;
 277       *errline_p = NULL;
 278       *errpos_p = NULL;
 279       if (context.errmsg)
 280         *error_string_p = strdup(context.errmsg);
 281       else
 282         *error_string_p = strdup(TA_get_error_message(context.error));
 283     }
 284     else
 285     {
 286       int i, ret;
 287       char auxbuf[128];
 288
 289       char* buf_end;
 290       char* p_start;
 291       char* p_end;
 292
 293
 294       /* construct data for `errline_p' */
 295       buf_end = font->deltas_buf + font->deltas_len;
 296
 297       p_start = font->deltas_buf;
 298       if (context.errline_num > 1)
 299       {
 300         i = 1;
 301         while (p_start < buf_end)
 302         {
 303           if (*p_start++ == '\n')
 304           {
 305             i++;
 306             if (i == context.errline_num)
 307               break;
 308           }
 309         }
 310       }
 311
 312       p_end = p_start;
 313       while (p_end < buf_end)
 314       {
 315         if (*p_end == '\n')
 316           break;
 317         p_end++;
 318       }
 319       *errline_p = strndup(p_start, p_end - p_start);
 320
 321       /* construct data for `error_string_p' */
 322       if (context.error == TA_Err_Deltas_Invalid_Font_Index)
 323         sprintf(auxbuf, " (valid range is [%ld;%ld])",
 324                 0L,
 325                 font->num_sfnts);
 326       else if (context.error == TA_Err_Deltas_Invalid_Glyph_Index)
 327         sprintf(auxbuf, " (valid range is [%ld;%ld])",
 328                 0L,
 329                 font->sfnts[context.font_idx].face->num_glyphs);
 330       else if (context.error == TA_Err_Deltas_Invalid_Shift)
 331         sprintf(auxbuf, " (valid interval is [%g;%g])",
 332                 DELTA_SHIFT_MIN,
 333                 DELTA_SHIFT_MAX);
 334       else if (context.error == TA_Err_Deltas_Invalid_Range)
 335         sprintf(auxbuf, " (values must be within [%ld;%ld])",
 336                 context.number_set_min,
 337                 context.number_set_max);
 338       else
 339         auxbuf[0] = '\0';
 340
 341       ret = asprintf(error_string_p, "%s%s",
 342                      *context.errmsg ? context.errmsg
 343                                      : TA_get_error_message(context.error),
 344                      auxbuf);
 345       if (ret == -1)
 346         *error_string_p = NULL;
 347
 348       if (errline_p)
 349         *errpos_p = *errline_p + context.errline_pos_left - 1;
 350       else
 351         *errpos_p = NULL;
 352
 353       *errlinenum_p = context.errline_num;
 354     }
 355   }
 356   else
 357   {
 358     if (deltas)
 359       *deltas = context.result;
 360     else
 361       TA_deltas_free(context.result);
 362   }
 363
 364   return context.error;
 365 }
 366
 367
 368 /* node structure for delta exception data */
 369
 370 typedef struct Node Node;
 371 struct Node
 372 {
 373   LLRB_ENTRY(Node) entry;
 374   Delta delta;
 375 };
 376
 377
 378 /* comparison function for our red-black tree */
 379
 380 static int
 381 nodecmp(Node* e1,
 382         Node* e2)
 383 {
 384   long diff;
 385
 386
 387   /* sort by font index ... */
 388   diff = e1->delta.font_idx - e2->delta.font_idx;
 389   if (diff)
 390     goto Exit;
 391
 392   /* ... then by glyph index ... */
 393   diff = e1->delta.glyph_idx - e2->delta.glyph_idx;
 394   if (diff)
 395     goto Exit;
 396
 397   /* ... then by ppem ... */
 398   diff = e1->delta.ppem - e2->delta.ppem;
 399   if (diff)
 400     goto Exit;
 401
 402   /* ... then by point index */
 403   diff = e1->delta.point_idx - e2->delta.point_idx;
 404
 405 Exit:
 406   /* https://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign */
 407   return (diff > 0) - (diff < 0);
 408 }
 409
 410
 411 /* the red-black tree function body */
 412 typedef struct deltas_data deltas_data;
 413
 414 LLRB_HEAD(deltas_data, Node);
 415
 416 /* no trailing semicolon in the next line */
 417 LLRB_GENERATE_STATIC(deltas_data, Node, entry, nodecmp)
 418
 419
 420 void
 421 TA_deltas_free_tree(FONT* font)
 422 {
 423   deltas_data* deltas_data_head = (deltas_data*)font->deltas_data_head;
 424
 425   Node* node;
 426   Node* next_node;
 427
 428
 429   if (!deltas_data_head)
 430     return;
 431
 432   for (node = LLRB_MIN(deltas_data, deltas_data_head);
 433        node;
 434        node = next_node)
 435   {
 436     next_node = LLRB_NEXT(deltas_data, deltas_data_head, node);
 437     LLRB_REMOVE(deltas_data, deltas_data_head, node);
 438     free(node);
 439   }
 440
 441   free(deltas_data_head);
 442 }
 443
 444
 445 TA_Error
 446 TA_deltas_build_tree(FONT* font,
 447                      Deltas* deltas)
 448 {
 449   deltas_data* deltas_data_head;
 450   int emit_newline = 0;
 451
 452
 453   /* nothing to do if no data */
 454   if (!deltas)
 455   {
 456     font->deltas_data_head = NULL;
 457     return TA_Err_Ok;
 458   }
 459
 460   deltas_data_head = (deltas_data*)malloc(sizeof (deltas_data));
 461   if (!deltas_data_head)
 462     return FT_Err_Out_Of_Memory;
 463
 464   LLRB_INIT(deltas_data_head);
 465
 466   while (deltas)
 467   {
 468     long font_idx = deltas->font_idx;
 469     long glyph_idx = deltas->glyph_idx;
 470     char x_shift = deltas->x_shift;
 471     char y_shift = deltas->y_shift;
 472
 473     number_set_iter ppems_iter;
 474     int ppem;
 475
 476
 477     ppems_iter.range = deltas->ppems;
 478     ppem = number_set_get_first(&ppems_iter);
 479
 480     while (ppems_iter.range)
 481     {
 482       number_set_iter points_iter;
 483       int point_idx;
 484
 485
 486       points_iter.range = deltas->points;
 487       point_idx = number_set_get_first(&points_iter);
 488
 489       while (points_iter.range)
 490       {
 491         Node* node;
 492         Node* val;
 493
 494
 495         node = (Node*)malloc(sizeof (Node));
 496         if (!node)
 497           return FT_Err_Out_Of_Memory;
 498
 499         node->delta.font_idx = font_idx;
 500         node->delta.glyph_idx = glyph_idx;
 501         node->delta.ppem = ppem;
 502         node->delta.point_idx = point_idx;
 503         node->delta.x_shift = x_shift;
 504         node->delta.y_shift = y_shift;
 505
 506         val = LLRB_INSERT(deltas_data, deltas_data_head, node);
 507         if (val)
 508           free(node);
 509         if (val && font->debug)
 510         {
 511           /* entry is already present; we ignore it */
 512           Deltas deltas;
 513           number_range ppems;
 514           number_range points;
 515
 516           char* s;
 517           int s_len;
 518
 519
 520           /* construct Deltas entry for debugging output */
 521           ppems.start = ppem;
 522           ppems.end = ppem;
 523           ppems.next = NULL;
 524           points.start = point_idx;
 525           points.end = point_idx;
 526           points.next = NULL;
 527
 528           deltas.font_idx = font_idx;
 529           deltas.glyph_idx = glyph_idx;
 530           deltas.points = &points;
 531           deltas.x_shift = x_shift;
 532           deltas.y_shift = y_shift;
 533           deltas.ppems = &ppems;
 534           deltas.next = NULL;
 535
 536           s = deltas_show_line(font, &s_len, &deltas);
 537           if (s)
 538           {
 539             fprintf(stderr, "Delta exception %s ignored.\n", s);
 540             free(s);
 541           }
 542
 543           emit_newline = 1;
 544         }
 545
 546         point_idx = number_set_get_next(&points_iter);
 547       }
 548
 549       ppem = number_set_get_next(&ppems_iter);
 550     }
 551
 552     deltas = deltas->next;
 553   }
 554
 555   if (font->debug && emit_newline)
 556     fprintf(stderr, "\n");
 557
 558   font->deltas_data_head = deltas_data_head;
 559   font->deltas_data_cur = LLRB_MIN(deltas_data, deltas_data_head);
 560
 561   return TA_Err_Ok;
 562 }
 563
 564
 565 /* the next functions are intended to restrict the use of LLRB stuff */
 566 /* related to delta exceptions to this file, */
 567 /* providing a means to access the data sequentially */
 568
 569 void
 570 TA_deltas_get_next(FONT* font)
 571 {
 572   Node* node = (Node*)font->deltas_data_cur;
 573
 574
 575   if (!node)
 576     return;
 577
 578   node = LLRB_NEXT(deltas_data, /* unused */, node);
 579
 580   font->deltas_data_cur = node;
 581 }
 582
 583
 584 const Delta*
 585 TA_deltas_get_delta(FONT* font)
 586 {
 587   Node* node = (Node*)font->deltas_data_cur;
 588
 589
 590   return node ? &node->delta : NULL;
 591 }
 592
 593 /* end of tadeltas.c */