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