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