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
 128   if (!deltas)
 129     goto Exit;
 130
 131   if (deltas->font_idx >= font->num_sfnts)
 132     goto Exit;
 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     s = sdscatprintf(s, "%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     s = sdscatprintf(s, "%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   return s;
 169 }
 170
 171
 172 char*
 173 TA_deltas_show(FONT* font)
 174 {
 175   sds s;
 176   size_t len;
 177   char* res;
 178
 179   Deltas* deltas = font->deltas;
 180
 181
 182   s = sdsempty();
 183
 184   while (deltas)
 185   {
 186     sds d;
 187
 188
 189     /* append current line to buffer, followed by a newline character */
 190     d = deltas_show_line(font, deltas);
 191     if (!d)
 192     {
 193       sdsfree(s);
 194       return NULL;
 195     }
 196     s = sdscatsds(s, d);
 197     sdsfree(d);
 198     s = sdscat(s, "\n");
 199
 200     deltas = deltas->next;
 201   }
 202
 203   if (!s)
 204     return NULL;
 205
 206   /* we return an empty string if there is no data */
 207   len = sdslen(s) + 1;
 208   res = (char*)malloc(len);
 209   if (res)
 210     memcpy(res, s, len);
 211
 212   sdsfree(s);
 213
 214   return res;
 215 }
 216
 217
 218 /* Parse delta exceptions in `font->deltas_buf'. */
 219
 220 TA_Error
 221 TA_deltas_parse_buffer(FONT* font,
 222                        char** error_string_p,
 223                        unsigned int* errlinenum_p,
 224                        char** errline_p,
 225                        char** errpos_p)
 226 {
 227   int bison_error;
 228
 229   Deltas_Context context;
 230
 231
 232   /* nothing to do if no data */
 233   if (!font->deltas_buf)
 234   {
 235     font->deltas = NULL;
 236     return TA_Err_Ok;
 237   }
 238
 239   TA_deltas_scanner_init(&context, font);
 240   if (context.error)
 241     goto Fail;
 242   /* this is `yyparse' in disguise */
 243   bison_error = TA_deltas_parse(&context);
 244   TA_deltas_scanner_done(&context);
 245
 246   if (bison_error)
 247   {
 248     if (bison_error == 2)
 249       context.error = TA_Err_Deltas_Allocation_Error;
 250
 251 Fail:
 252     font->deltas = NULL;
 253
 254     if (context.error == TA_Err_Deltas_Allocation_Error
 255         || context.error == TA_Err_Deltas_Flex_Error)
 256     {
 257       *errlinenum_p = 0;
 258       *errline_p = NULL;
 259       *errpos_p = NULL;
 260       if (context.errmsg)
 261         *error_string_p = strdup(context.errmsg);
 262       else
 263         *error_string_p = strdup(TA_get_error_message(context.error));
 264     }
 265     else
 266     {
 267       int i, ret;
 268       char auxbuf[128];
 269
 270       char* buf_end;
 271       char* p_start;
 272       char* p_end;
 273
 274
 275       /* construct data for `errline_p' */
 276       buf_end = font->deltas_buf + font->deltas_len;
 277
 278       p_start = font->deltas_buf;
 279       if (context.errline_num > 1)
 280       {
 281         i = 1;
 282         while (p_start < buf_end)
 283         {
 284           if (*p_start++ == '\n')
 285           {
 286             i++;
 287             if (i == context.errline_num)
 288               break;
 289           }
 290         }
 291       }
 292
 293       p_end = p_start;
 294       while (p_end < buf_end)
 295       {
 296         if (*p_end == '\n')
 297           break;
 298         p_end++;
 299       }
 300       *errline_p = strndup(p_start, p_end - p_start);
 301
 302       /* construct data for `error_string_p' */
 303       if (context.error == TA_Err_Deltas_Invalid_Font_Index)
 304         sprintf(auxbuf, " (valid range is [%ld;%ld])",
 305                 0L,
 306                 font->num_sfnts);
 307       else if (context.error == TA_Err_Deltas_Invalid_Glyph_Index)
 308         sprintf(auxbuf, " (valid range is [%ld;%ld])",
 309                 0L,
 310                 font->sfnts[context.font_idx].face->num_glyphs);
 311       else if (context.error == TA_Err_Deltas_Invalid_Shift)
 312         sprintf(auxbuf, " (valid interval is [%g;%g])",
 313                 DELTA_SHIFT_MIN,
 314                 DELTA_SHIFT_MAX);
 315       else if (context.error == TA_Err_Deltas_Invalid_Range)
 316         sprintf(auxbuf, " (values must be within [%ld;%ld])",
 317                 context.number_set_min,
 318                 context.number_set_max);
 319       else
 320         auxbuf[0] = '\0';
 321
 322       ret = asprintf(error_string_p, "%s%s",
 323                      *context.errmsg ? context.errmsg
 324                                      : TA_get_error_message(context.error),
 325                      auxbuf);
 326       if (ret == -1)
 327         *error_string_p = NULL;
 328
 329       if (errline_p)
 330         *errpos_p = *errline_p + context.errline_pos_left - 1;
 331       else
 332         *errpos_p = NULL;
 333
 334       *errlinenum_p = context.errline_num;
 335     }
 336   }
 337   else
 338     font->deltas = context.result;
 339
 340   return context.error;
 341 }
 342
 343
 344 /* node structure for delta exception data */
 345
 346 typedef struct Node Node;
 347 struct Node
 348 {
 349   LLRB_ENTRY(Node) entry;
 350   Delta delta;
 351 };
 352
 353
 354 /* comparison function for our red-black tree */
 355
 356 static int
 357 nodecmp(Node* e1,
 358         Node* e2)
 359 {
 360   long diff;
 361
 362
 363   /* sort by font index ... */
 364   diff = e1->delta.font_idx - e2->delta.font_idx;
 365   if (diff)
 366     goto Exit;
 367
 368   /* ... then by glyph index ... */
 369   diff = e1->delta.glyph_idx - e2->delta.glyph_idx;
 370   if (diff)
 371     goto Exit;
 372
 373   /* ... then by ppem ... */
 374   diff = e1->delta.ppem - e2->delta.ppem;
 375   if (diff)
 376     goto Exit;
 377
 378   /* ... then by point index */
 379   diff = e1->delta.point_idx - e2->delta.point_idx;
 380
 381 Exit:
 382   /* https://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign */
 383   return (diff > 0) - (diff < 0);
 384 }
 385
 386
 387 /* the red-black tree function body */
 388 typedef struct deltas_data deltas_data;
 389
 390 LLRB_HEAD(deltas_data, Node);
 391
 392 /* no trailing semicolon in the next line */
 393 LLRB_GENERATE_STATIC(deltas_data, Node, entry, nodecmp)
 394
 395
 396 void
 397 TA_deltas_free_tree(FONT* font)
 398 {
 399   deltas_data* deltas_data_head = (deltas_data*)font->deltas_data_head;
 400
 401   Node* node;
 402   Node* next_node;
 403
 404
 405   if (!deltas_data_head)
 406     return;
 407
 408   for (node = LLRB_MIN(deltas_data, deltas_data_head);
 409        node;
 410        node = next_node)
 411   {
 412     next_node = LLRB_NEXT(deltas_data, deltas_data_head, node);
 413     LLRB_REMOVE(deltas_data, deltas_data_head, node);
 414     free(node);
 415   }
 416
 417   free(deltas_data_head);
 418 }
 419
 420
 421 TA_Error
 422 TA_deltas_build_tree(FONT* font)
 423 {
 424   Deltas* deltas = font->deltas;
 425   deltas_data* deltas_data_head;
 426   int emit_newline = 0;
 427
 428
 429   /* nothing to do if no data */
 430   if (!deltas)
 431   {
 432     font->deltas_data_head = NULL;
 433     return TA_Err_Ok;
 434   }
 435
 436   deltas_data_head = (deltas_data*)malloc(sizeof (deltas_data));
 437   if (!deltas_data_head)
 438     return FT_Err_Out_Of_Memory;
 439
 440   LLRB_INIT(deltas_data_head);
 441
 442   while (deltas)
 443   {
 444     long font_idx = deltas->font_idx;
 445     long glyph_idx = deltas->glyph_idx;
 446     char x_shift = deltas->x_shift;
 447     char y_shift = deltas->y_shift;
 448
 449     number_set_iter ppems_iter;
 450     int ppem;
 451
 452
 453     ppems_iter.range = deltas->ppems;
 454     ppem = number_set_get_first(&ppems_iter);
 455
 456     while (ppems_iter.range)
 457     {
 458       number_set_iter points_iter;
 459       int point_idx;
 460
 461
 462       points_iter.range = deltas->points;
 463       point_idx = number_set_get_first(&points_iter);
 464
 465       while (points_iter.range)
 466       {
 467         Node* node;
 468         Node* val;
 469
 470
 471         node = (Node*)malloc(sizeof (Node));
 472         if (!node)
 473           return FT_Err_Out_Of_Memory;
 474
 475         node->delta.font_idx = font_idx;
 476         node->delta.glyph_idx = glyph_idx;
 477         node->delta.ppem = ppem;
 478         node->delta.point_idx = point_idx;
 479         node->delta.x_shift = x_shift;
 480         node->delta.y_shift = y_shift;
 481
 482         val = LLRB_INSERT(deltas_data, deltas_data_head, node);
 483         if (val)
 484           free(node);
 485         if (val && font->debug)
 486         {
 487           /* entry is already present; we ignore it */
 488           Deltas d;
 489           number_range ppems;
 490           number_range points;
 491
 492           sds s;
 493
 494
 495           /* construct Deltas entry for debugging output */
 496           ppems.start = ppem;
 497           ppems.end = ppem;
 498           ppems.next = NULL;
 499           points.start = point_idx;
 500           points.end = point_idx;
 501           points.next = NULL;
 502
 503           d.font_idx = font_idx;
 504           d.glyph_idx = glyph_idx;
 505           d.points = &points;
 506           d.x_shift = x_shift;
 507           d.y_shift = y_shift;
 508           d.ppems = &ppems;
 509           d.next = NULL;
 510
 511           s = deltas_show_line(font, &d);
 512           if (s)
 513           {
 514             fprintf(stderr, "Delta exception %s ignored.\n", s);
 515             sdsfree(s);
 516           }
 517
 518           emit_newline = 1;
 519         }
 520
 521         point_idx = number_set_get_next(&points_iter);
 522       }
 523
 524       ppem = number_set_get_next(&ppems_iter);
 525     }
 526
 527     deltas = deltas->next;
 528   }
 529
 530   if (font->debug && emit_newline)
 531     fprintf(stderr, "\n");
 532
 533   font->deltas_data_head = deltas_data_head;
 534   font->deltas_data_cur = LLRB_MIN(deltas_data, deltas_data_head);
 535
 536   return TA_Err_Ok;
 537 }
 538
 539
 540 /* the next functions are intended to restrict the use of LLRB stuff */
 541 /* related to delta exceptions to this file, */
 542 /* providing a means to access the data sequentially */
 543
 544 void
 545 TA_deltas_get_next(FONT* font)
 546 {
 547   Node* node = (Node*)font->deltas_data_cur;
 548
 549
 550   if (!node)
 551     return;
 552
 553   node = LLRB_NEXT(deltas_data, /* unused */, node);
 554
 555   font->deltas_data_cur = node;
 556 }
 557
 558
 559 const Delta*
 560 TA_deltas_get_delta(FONT* font)
 561 {
 562   Node* node = (Node*)font->deltas_data_cur;
 563
 564
 565   return node ? &node->delta : NULL;
 566 }
 567
 568 /* end of tadeltas.c */