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
  24
  25 /* a test to check the validity of the first character */
  26 /* in a PostScript glyph name -- for simplicity, we include `.' also */
  27
  28 const char* namestart_chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  29                               "abcdefghijklmnopqrstuvwxyz"
  30                               "._";
  31
  32 static int
  33 isnamestart(int c)
  34 {
  35   return strchr(namestart_chars, c) != NULL;
  36 }
  37
  38
  39 static char*
  40 get_token(char** string_p)
  41 {
  42   const char* s = *string_p;
  43   const char* p = *string_p;
  44
  45
  46   while (*p && !isspace(*p))
  47     p++;
  48
  49   *string_p = (char*)p;
  50   return (char*)s;
  51 }
  52
  53
  54 /* in the following functions, `*string_p' is never '\0'; */
  55 /* in case of error, `*string_p' should be set to a meaningful position */
  56
  57 static TA_Error
  58 get_font_idx(FONT* font,
  59              char** string_p,
  60              long* font_idx_p)
  61 {
  62   const char* s = *string_p;
  63   char* endptr;
  64   long font_idx;
  65
  66   int saved_errno;
  67   char* saved_locale;
  68
  69
  70   saved_locale = setlocale(LC_NUMERIC, "C");
  71   errno = 0;
  72   font_idx = strtol(s, &endptr, 0);
  73   saved_errno = errno;
  74   setlocale(LC_NUMERIC, saved_locale);
  75
  76   if (saved_errno == ERANGE)
  77   {
  78     /* *string_p = s; */
  79     return TA_Err_Deltas_Invalid_Font_Index;
  80   }
  81
  82   /* there must be a whitespace character after the number */
  83   if (saved_errno || !isspace(*endptr))
  84   {
  85     *string_p = endptr;
  86     return TA_Err_Deltas_Syntax_Error;
  87   }
  88
  89   /* we have already tested that the first character in `s' is a digit, */
  90   /* so `font_idx' can't be negative */
  91   if (font_idx >= font->num_sfnts)
  92   {
  93     /* *string_p = s; */
  94     return TA_Err_Deltas_Invalid_Font_Index;
  95   }
  96
  97   *string_p = endptr;
  98   *font_idx_p = font_idx;
  99
 100   return TA_Err_Ok;
 101 }
 102
 103
 104 static TA_Error
 105 get_glyph_idx(FONT* font,
 106               long font_idx,
 107               char** string_p,
 108               long* glyph_idx_p)
 109 {
 110   const char* s = *string_p;
 111   char* endptr;
 112   long glyph_idx;
 113
 114   FT_Face face = font->sfnts[font_idx].face;
 115
 116
 117   if (isdigit(*s))
 118   {
 119     /* glyph index */
 120
 121     int saved_errno;
 122     char* saved_locale;
 123
 124
 125     saved_locale = setlocale(LC_NUMERIC, "C");
 126     errno = 0;
 127     glyph_idx = strtol(s, &endptr, 0);
 128     saved_errno = errno;
 129     setlocale(LC_NUMERIC, saved_locale);
 130
 131     if (saved_errno == ERANGE)
 132     {
 133       /* *string_p = s; */
 134       return TA_Err_Deltas_Invalid_Glyph_Index;
 135     }
 136
 137     /* there must be a whitespace character after the number */
 138     if (saved_errno || !isspace(*endptr))
 139     {
 140       *string_p = endptr;
 141       return TA_Err_Deltas_Syntax_Error;
 142     }
 143
 144     /* we have already tested that the first character in `s' is a digit, */
 145     /* so `glyph_idx' can't be negative */
 146     if (glyph_idx >= face->num_glyphs)
 147     {
 148       /* *string_p = s; */
 149       return TA_Err_Deltas_Invalid_Glyph_Index;
 150     }
 151   }
 152   else if (isnamestart(*s))
 153   {
 154     /* glyph name */
 155
 156     char* token;
 157
 158
 159     endptr = (char*)s;
 160     s = get_token(&endptr);
 161
 162     token = strndup(s, endptr - s);
 163     if (!token)
 164     {
 165       /* *string_p = s; */
 166       return TA_Err_Deltas_Allocation_Error;
 167     }
 168
 169     /* explicitly compare with `.notdef' */
 170     /* since `FT_Get_Name_Index' returns glyph index 0 */
 171     /* for both this glyph name and invalid ones */
 172     if (!strcmp(token, ".notdef"))
 173       glyph_idx = 0;
 174     else
 175     {
 176       glyph_idx = FT_Get_Name_Index(face, token);
 177       if (glyph_idx == 0)
 178         glyph_idx = -1;
 179     }
 180
 181     free(token);
 182
 183     if (glyph_idx < 0)
 184     {
 185       /* *string_p = s; */
 186       return TA_Err_Deltas_Invalid_Glyph_Name;
 187     }
 188   }
 189   else
 190   {
 191     /* invalid */
 192
 193     /* *string_p = s; */
 194     return TA_Err_Deltas_Syntax_Error;
 195   }
 196
 197   *string_p = endptr;
 198   *glyph_idx_p = glyph_idx;
 199
 200   return TA_Err_Ok;
 201 }
 202
 203
 204 static TA_Error
 205 get_range(char** string_p,
 206           number_range** number_set_p,
 207           int min,
 208           int max,
 209           const char* delims)
 210 {
 211   const char* s = *string_p;
 212   number_range* number_set = *number_set_p;
 213
 214   size_t s_len = strcspn(s, delims);
 215   char* token;
 216   char* endptr;
 217
 218
 219   /* there must be a whitespace character before the delimiter */
 220   /* if it is not \0 */
 221   if (*delims
 222       && (!s_len || !isspace(s[s_len - 1])))
 223   {
 224     *string_p = (char*)(s + s_len);
 225     return TA_Err_Deltas_Syntax_Error;
 226   }
 227
 228   token = strndup(s, s_len);
 229   if (!token)
 230   {
 231     /* *string_p = s; */
 232     return TA_Err_Deltas_Allocation_Error;
 233   }
 234
 235   endptr = (char*)number_set_parse(token, &number_set, min, max);
 236
 237   /* use offset relative to `s' */
 238   endptr = (char*)s + (endptr - token);
 239   free(token);
 240
 241   if (number_set == NUMBERSET_ALLOCATION_ERROR)
 242   {
 243     /* *string_p = s; */
 244     return TA_Err_Deltas_Allocation_Error;
 245   }
 246
 247   *string_p = endptr;
 248
 249   if (number_set == NUMBERSET_INVALID_CHARACTER)
 250     return TA_Err_Deltas_Invalid_Character;
 251   else if (number_set == NUMBERSET_OVERFLOW)
 252     return TA_Err_Deltas_Overflow;
 253   else if (number_set == NUMBERSET_INVALID_RANGE)
 254     /* this error code should be adjusted by the caller if necessary */
 255     return TA_Err_Deltas_Invalid_Point_Range;
 256   else if (number_set == NUMBERSET_OVERLAPPING_RANGES)
 257     return TA_Err_Deltas_Overlapping_Ranges;
 258   else if (number_set == NUMBERSET_NOT_ASCENDING)
 259     return TA_Err_Deltas_Ranges_Not_Ascending;
 260
 261   *number_set_p = number_set;
 262
 263   return TA_Err_Ok;
 264 }
 265
 266
 267 static TA_Error
 268 get_shift(char** string_p,
 269           char* shift_p)
 270 {
 271   const char* s = *string_p;
 272   char* endptr;
 273   double shift;
 274
 275   int saved_errno;
 276   char* saved_locale;
 277
 278
 279   saved_locale = setlocale(LC_NUMERIC, "C");
 280   errno = 0;
 281   shift = strtod(s, &endptr);
 282   saved_errno = errno;
 283   setlocale(LC_NUMERIC, saved_locale);
 284
 285   if (saved_errno == ERANGE)
 286   {
 287     /* *string_p = s; */
 288     /* this error code should be adjusted by the caller if necessary */
 289     return TA_Err_Deltas_Invalid_X_Range;
 290   }
 291
 292   /* there must be a whitespace character after the number */
 293   if (saved_errno || !isspace(*endptr))
 294   {
 295     *string_p = endptr;
 296     return TA_Err_Deltas_Syntax_Error;
 297   }
 298
 299   if (shift < DELTA_SHIFT_MIN || shift > DELTA_SHIFT_MAX)
 300   {
 301     /* *string_p = s; */
 302     return TA_Err_Deltas_Invalid_X_Range;
 303   }
 304
 305   *string_p = endptr;
 306
 307   /* we round the value to a multiple of 1/(2^DELTA_SHIFT) */
 308   *shift_p = (char)(shift * DELTA_FACTOR + (shift > 0 ? 0.5 : -0.5));
 309
 310   return TA_Err_Ok;
 311 }
 312
 313
 314 /*
 315  * Parse a delta exceptions line.
 316  *
 317  * In case of success (this is, the delta exceptions description in `s' is
 318  * valid), `pos' is a pointer to the final zero byte in string `s'.  In case
 319  * of an error, it points to the offending character in string `s'.
 320  *
 321  * If s is NULL, the function exits immediately, with NULL as the value of
 322  * `pos'.
 323  *
 324  * If the user provides a non-NULL `deltas' value, `deltas_parse' stores the
 325  * parsed result in `*deltas', allocating the necessary memory.  If there is
 326  * no data (for example, an empty string or whitespace only) nothing gets
 327  * allocated, and `*deltas' is set to NULL.
 328  *
 329  */
 330
 331 static TA_Error
 332 deltas_parse_line(FONT* font,
 333                   const char* s,
 334                   char** err_pos,
 335                   Deltas** deltas_p,
 336                   int ppem_min, int ppem_max)
 337 {
 338   TA_Error error;
 339
 340   typedef enum State_
 341   { START,
 342     HAD_TOKEN1,
 343     HAD_TOKEN2,
 344     HAD_FONT_IDX,
 345     HAD_GLYPH_IDX,
 346     HAD_P,
 347     HAD_POINTS,
 348     HAD_X,
 349     HAD_X_SHIFT,
 350     HAD_Y,
 351     HAD_Y_SHIFT,
 352     HAD_AT,
 353     HAD_PPEMS
 354   } State;
 355
 356   State state = START;
 357
 358   char* pos = (char*)s;
 359
 360   const char* token1;
 361   const char* token2;
 362
 363   long font_idx = 0;
 364   long glyph_idx = -1;
 365   number_range* points = NULL;
 366   char x_shift = 0;
 367   char y_shift = 0;
 368   number_range* ppems = NULL;
 369
 370
 371   if (!s)
 372   {
 373     *err_pos = NULL;
 374     return TA_Err_Ok;
 375   }
 376
 377   for (;;)
 378   {
 379     char c;
 380     int next_is_space;
 381     State old_state = state;
 382
 383
 384     error = TA_Err_Ok;
 385
 386     while (isspace(*pos))
 387       pos++;
 388
 389     /* skip comment */
 390     if (*pos == '#')
 391       while (*pos)
 392         pos++;
 393
 394     /* EOL */
 395     if (!*pos)
 396       break;
 397
 398     c = *pos;
 399     next_is_space = isspace(*(pos + 1));
 400
 401     switch (state)
 402     {
 403     case START:
 404       token1 = get_token(&pos);
 405       state = HAD_TOKEN1;
 406       break;
 407
 408     case HAD_TOKEN1:
 409       token2 = get_token(&pos);
 410       state = HAD_TOKEN2;
 411       break;
 412
 413     case HAD_TOKEN2:
 414       pos = (char*)token1;
 415
 416       /* possibility 1: <font idx> <glyph name> `p' */
 417       if (isdigit(*token1)
 418           && (isdigit(*token2) || isnamestart(*token2))
 419           && (c == 'p' && next_is_space))
 420       {
 421         if (!(error = get_font_idx(font, &pos, &font_idx)))
 422           state = HAD_FONT_IDX;
 423       }
 424       /* possibility 2: <glyph name> `p' */
 425       else if ((isdigit(*token1) || isnamestart(*token1))
 426                && (*token2 == 'p' && isspace(*(token2 + 1))))
 427       {
 428         if (!(error = get_glyph_idx(font, font_idx,
 429                                     &pos, &glyph_idx)))
 430           state = HAD_GLYPH_IDX;
 431       }
 432       break;
 433
 434     case HAD_FONT_IDX:
 435       /* <glyph idx> */
 436       if (!(error = get_glyph_idx(font, font_idx,
 437                                   &pos, &glyph_idx)))
 438         state = HAD_GLYPH_IDX;
 439       break;
 440
 441     case HAD_GLYPH_IDX:
 442       /* `p' */
 443       if (c == 'p' && next_is_space)
 444       {
 445         state = HAD_P;
 446         pos += 2;
 447       }
 448       break;
 449
 450     case HAD_P:
 451       /* <points> */
 452       {
 453         FT_Error ft_error;
 454         FT_Face face = font->sfnts[font_idx].face;
 455         int num_points;
 456
 457
 458         ft_error = FT_Load_Glyph(face, glyph_idx, FT_LOAD_NO_SCALE);
 459         if (ft_error)
 460         {
 461           error = TA_Err_Deltas_Invalid_Glyph;
 462           break;
 463         }
 464
 465         num_points = face->glyph->outline.n_points;
 466         if (!(error = get_range(&pos, deltas_p ? &points : NULL,
 467                                 0, num_points - 1, "xy@")))
 468           state = HAD_POINTS;
 469       }
 470       break;
 471
 472     case HAD_POINTS:
 473       /* `x' or `y' or `@' */
 474       if (next_is_space)
 475       {
 476         pos += 2;
 477         if (c == 'x')
 478           state = HAD_X;
 479         else if (c == 'y')
 480           state = HAD_Y;
 481         else if (c == '@')
 482           state = HAD_AT;
 483         else
 484           pos -= 2;
 485       }
 486       break;
 487
 488     case HAD_X:
 489       /* <x_shift> */
 490       if (!(error = get_shift(&pos, &x_shift)))
 491         state = HAD_X_SHIFT;
 492       break;
 493
 494     case HAD_X_SHIFT:
 495       /* 'y' or '@' */
 496       if (next_is_space)
 497       {
 498         pos += 2;
 499         if (c == 'y')
 500           state = HAD_Y;
 501         else if (c == '@')
 502           state = HAD_AT;
 503         else
 504           pos -= 2;
 505       }
 506       break;
 507
 508     case HAD_Y:
 509       /* <y shift> */
 510       if (!(error = get_shift(&pos, &y_shift)))
 511         state = HAD_Y_SHIFT;
 512       if (error == TA_Err_Deltas_Invalid_X_Range)
 513         error = TA_Err_Deltas_Invalid_Y_Range;
 514       break;
 515
 516     case HAD_Y_SHIFT:
 517       /* '@' */
 518       if (c == '@' && next_is_space)
 519       {
 520         state = HAD_AT;
 521         pos += 2;
 522       }
 523       break;
 524
 525     case HAD_AT:
 526       /* <ppems> */
 527       if (!(error = get_range(&pos, deltas_p ? &ppems : NULL,
 528                               ppem_min, ppem_max, "")))
 529         state = HAD_PPEMS;
 530       if (error == TA_Err_Deltas_Invalid_Point_Range)
 531         error = TA_Err_Deltas_Invalid_Ppem_Range;
 532       break;
 533
 534     case HAD_PPEMS:
 535       /* to make compiler happy */
 536       break;
 537     }
 538
 539     if (old_state == state)
 540       break;
 541   }
 542
 543   if (state == HAD_PPEMS)
 544   {
 545     /* success */
 546     if (deltas_p)
 547     {
 548       Deltas* deltas = (Deltas*)malloc(sizeof (Deltas));
 549
 550
 551       if (!deltas)
 552       {
 553         number_set_free(points);
 554         number_set_free(ppems);
 555
 556         *err_pos = (char*)s;
 557
 558         return TA_Err_Deltas_Allocation_Error;
 559       }
 560
 561       deltas->font_idx = font_idx;
 562       deltas->glyph_idx = glyph_idx;
 563       deltas->points = points;
 564       deltas->x_shift = x_shift;
 565       deltas->y_shift = y_shift;
 566       deltas->ppems = ppems;
 567       deltas->next = NULL;
 568
 569       *deltas_p = deltas;
 570     }
 571   }
 572   else
 573   {
 574     if (deltas_p)
 575     {
 576       number_set_free(points);
 577       number_set_free(ppems);
 578
 579       *deltas_p = NULL;
 580     }
 581
 582     if (!error && state != START)
 583       error = TA_Err_Deltas_Syntax_Error;
 584   }
 585
 586   *err_pos = pos;
 587
 588   return error;
 589 }
 590
 591
 592 void
 593 TA_deltas_free(Deltas* deltas)
 594 {
 595   while (deltas)
 596   {
 597     Deltas* tmp;
 598
 599
 600     number_set_free(deltas->points);
 601     number_set_free(deltas->ppems);
 602
 603     tmp = deltas;
 604     deltas = deltas->next;
 605     free(tmp);
 606   }
 607 }
 608
 609
 610 /* `len' is the length of the returned string */
 611
 612 char*
 613 deltas_show_line(FONT* font,
 614                  int* len,
 615                  Deltas* deltas)
 616 {
 617   int ret;
 618   char glyph_name_buf[64];
 619   char* points_buf = NULL;
 620   char* ppems_buf = NULL;
 621   char* deltas_buf = NULL;
 622
 623   FT_Face face;
 624
 625
 626   if (!deltas)
 627     return NULL;
 628
 629   if (deltas->font_idx >= font->num_sfnts)
 630     return NULL;
 631
 632   face = font->sfnts[deltas->font_idx].face;
 633   glyph_name_buf[0] = '\0';
 634   if (FT_HAS_GLYPH_NAMES(face))
 635     FT_Get_Glyph_Name(face, deltas->glyph_idx, glyph_name_buf, 64);
 636
 637   points_buf = number_set_show(deltas->points, -1, -1);
 638   if (!points_buf)
 639     goto Exit;
 640   ppems_buf = number_set_show(deltas->ppems, -1, -1);
 641   if (!ppems_buf)
 642     goto Exit;
 643
 644   /* display glyph index if we don't have a glyph name */
 645   if (*glyph_name_buf)
 646     ret = asprintf(&deltas_buf, "%ld %s p %s x %.20g y %.20g @ %s",
 647                    deltas->font_idx,
 648                    glyph_name_buf,
 649                    points_buf,
 650                    (double)deltas->x_shift / DELTA_FACTOR,
 651                    (double)deltas->y_shift / DELTA_FACTOR,
 652                    ppems_buf);
 653   else
 654     ret = asprintf(&deltas_buf, "%ld %ld p %s x %.20g y %.20g @ %s",
 655                    deltas->font_idx,
 656                    deltas->glyph_idx,
 657                    points_buf,
 658                    (double)deltas->x_shift / DELTA_FACTOR,
 659                    (double)deltas->y_shift / DELTA_FACTOR,
 660                    ppems_buf);
 661
 662 Exit:
 663   free(points_buf);
 664   free(ppems_buf);
 665
 666   if (ret == -1)
 667     return NULL;
 668
 669   *len = ret;
 670
 671   return deltas_buf;
 672 }
 673
 674
 675 char*
 676 TA_deltas_show(FONT* font,
 677                Deltas* deltas)
 678 {
 679   char* s;
 680   int s_len;
 681
 682
 683   /* we return an empty string if there is no data */
 684   s = (char*)malloc(1);
 685   if (!s)
 686     return NULL;
 687
 688   *s = '\0';
 689   s_len = 1;
 690
 691   while (deltas)
 692   {
 693     char* tmp;
 694     int tmp_len;
 695     char* s_new;
 696     int s_len_new;
 697
 698
 699     tmp = deltas_show_line(font, &tmp_len, deltas);
 700     if (!tmp)
 701     {
 702       free(s);
 703       return NULL;
 704     }
 705
 706     /* append current line to buffer, followed by a newline character */
 707     s_len_new = s_len + tmp_len + 1;
 708     s_new = (char*)realloc(s, s_len_new);
 709     if (!s_new)
 710     {
 711       free(s);
 712       free(tmp);
 713       return NULL;
 714     }
 715
 716     strcpy(s_new + s_len - 1, tmp);
 717     s_new[s_len_new - 2] = '\n';
 718     s_new[s_len_new - 1] = '\0';
 719
 720     s = s_new;
 721     s_len = s_len_new;
 722
 723     free(tmp);
 724
 725     deltas = deltas->next;
 726   }
 727
 728   return s;
 729 }
 730
 731
 732 /* Get a line from a buffer, starting at `pos'.  The final EOL */
 733 /* character (or character pair) of the line (if existing) gets removed. */
 734 /* After the call, `pos' points to the position right after the line in */
 735 /* the buffer.  The line is allocated with `malloc'; it returns NULL for */
 736 /* end of data and allocation errors; the latter can be recognized by a */
 737 /* changed value of `pos'.  */
 738
 739 static char*
 740 get_line(char** pos)
 741 {
 742   const char* start = *pos;
 743   const char* p = start;
 744   size_t len;
 745   char* s;
 746
 747
 748   if (!*p)
 749     return NULL;
 750
 751   while (*p)
 752   {
 753     if (*p == '\n' || *p == '\r')
 754       break;
 755
 756     p++;
 757   }
 758
 759   len = p - start + 1;
 760
 761   if (*p == '\r')
 762   {
 763     len--;
 764     p++;
 765
 766     if (*p == '\n')
 767       p++;
 768   }
 769   else if (*p == '\n')
 770   {
 771     len--;
 772     p++;
 773   }
 774
 775   *pos = (char*)p;
 776
 777   s = (char*)malloc(len + 1);
 778   if (!s)
 779     return NULL;
 780
 781   if (len)
 782     strncpy(s, start, len);
 783   s[len] = '\0';
 784
 785   return s;
 786 }
 787
 788
 789 TA_Error
 790 TA_deltas_parse(FONT* font,
 791                 Deltas** deltas,
 792                 unsigned int* errlinenum_p,
 793                 char** errline_p,
 794                 char** errpos_p)
 795 {
 796   FT_Error error;
 797
 798   Deltas* cur;
 799   Deltas* new_deltas;
 800   Deltas* tmp;
 801   Deltas* list;
 802
 803   unsigned int linenum;
 804
 805   char* bufpos;
 806   char* bufpos_old;
 807
 808
 809   /* nothing to do if no data */
 810   if (!font->deltas_buf)
 811   {
 812     *deltas = NULL;
 813     return TA_Err_Ok;
 814   }
 815
 816   bufpos = font->deltas_buf;
 817   bufpos_old = bufpos;
 818
 819   linenum = 0;
 820   cur = NULL;
 821
 822   /* parse line by line */
 823   for (;;)
 824   {
 825     char* line;
 826     char* errpos;
 827
 828
 829     line = get_line(&bufpos);
 830     if (!line)
 831     {
 832       if (bufpos == bufpos_old) /* end of data */
 833         break;
 834
 835       *errlinenum_p = linenum;
 836       *errline_p = NULL;
 837       *errpos_p = NULL;
 838
 839       return FT_Err_Out_Of_Memory;
 840     }
 841
 842     error = deltas_parse_line(font,
 843                               line,
 844                               &errpos,
 845                               deltas ? &new_deltas : NULL,
 846                               DELTA_PPEM_MIN, DELTA_PPEM_MAX);
 847     if (error)
 848     {
 849       *errlinenum_p = linenum;
 850       *errline_p = line;
 851       *errpos_p = errpos;
 852
 853       TA_deltas_free(cur);
 854
 855       return error;
 856     }
 857
 858     if (deltas && new_deltas)
 859     {
 860       new_deltas->next = cur;
 861       cur = new_deltas;
 862     }
 863
 864     free(line);
 865     linenum++;
 866     bufpos_old = bufpos;
 867   }
 868
 869   /* success; now reverse list to have elements in original order */
 870   list = NULL;
 871
 872   while (cur)
 873   {
 874     tmp = cur;
 875     cur = cur->next;
 876     tmp->next = list;
 877     list = tmp;
 878   }
 879
 880   if (deltas)
 881     *deltas = list;
 882
 883   return TA_Err_Ok;
 884 }
 885
 886
 887 /* node structure for delta exception data */
 888
 889 typedef struct Node Node;
 890 struct Node
 891 {
 892   LLRB_ENTRY(Node) entry;
 893   Delta delta;
 894 };
 895
 896
 897 /* comparison function for our red-black tree */
 898
 899 static int
 900 nodecmp(Node* e1,
 901         Node* e2)
 902 {
 903   long diff;
 904
 905
 906   /* sort by font index ... */
 907   diff = e1->delta.font_idx - e2->delta.font_idx;
 908   if (diff)
 909     goto Exit;
 910
 911   /* ... then by glyph index ... */
 912   diff = e1->delta.glyph_idx - e2->delta.glyph_idx;
 913   if (diff)
 914     goto Exit;
 915
 916   /* ... then by ppem ... */
 917   diff = e1->delta.ppem - e2->delta.ppem;
 918   if (diff)
 919     goto Exit;
 920
 921   /* ... then by point index */
 922   diff = e1->delta.point_idx - e2->delta.point_idx;
 923
 924 Exit:
 925   /* https://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign */
 926   return (diff > 0) - (diff < 0);
 927 }
 928
 929
 930 /* the red-black tree function body */
 931 typedef struct deltas_data deltas_data;
 932
 933 LLRB_HEAD(deltas_data, Node);
 934
 935 /* no trailing semicolon in the next line */
 936 LLRB_GENERATE_STATIC(deltas_data, Node, entry, nodecmp)
 937
 938
 939 void
 940 TA_deltas_free_tree(FONT* font)
 941 {
 942   deltas_data* deltas_data_head = (deltas_data*)font->deltas_data_head;
 943
 944   Node* node;
 945   Node* next_node;
 946
 947
 948   if (!deltas_data_head)
 949     return;
 950
 951   for (node = LLRB_MIN(deltas_data, deltas_data_head);
 952        node;
 953        node = next_node)
 954   {
 955     next_node = LLRB_NEXT(deltas_data, deltas_data_head, node);
 956     LLRB_REMOVE(deltas_data, deltas_data_head, node);
 957     free(node);
 958   }
 959
 960   free(deltas_data_head);
 961 }
 962
 963
 964 TA_Error
 965 TA_deltas_build_tree(FONT* font,
 966                      Deltas* deltas)
 967 {
 968   deltas_data* deltas_data_head;
 969   int emit_newline = 0;
 970
 971
 972   /* nothing to do if no data */
 973   if (!deltas)
 974   {
 975     font->deltas_data_head = NULL;
 976     return TA_Err_Ok;
 977   }
 978
 979   deltas_data_head = (deltas_data*)malloc(sizeof (deltas_data));
 980   if (!deltas_data_head)
 981     return FT_Err_Out_Of_Memory;
 982
 983   LLRB_INIT(deltas_data_head);
 984
 985   while (deltas)
 986   {
 987     long font_idx = deltas->font_idx;
 988     long glyph_idx = deltas->glyph_idx;
 989     char x_shift = deltas->x_shift;
 990     char y_shift = deltas->y_shift;
 991
 992     number_set_iter ppems_iter;
 993     int ppem;
 994
 995
 996     ppems_iter.range = deltas->ppems;
 997     ppem = number_set_get_first(&ppems_iter);
 998
 999     while (ppems_iter.range)
1000     {
1001       number_set_iter points_iter;
1002       int point_idx;
1003
1004
1005       points_iter.range = deltas->points;
1006       point_idx = number_set_get_first(&points_iter);
1007
1008       while (points_iter.range)
1009       {
1010         Node* node;
1011         Node* val;
1012
1013
1014         node = (Node*)malloc(sizeof (Node));
1015         if (!node)
1016           return FT_Err_Out_Of_Memory;
1017
1018         node->delta.font_idx = font_idx;
1019         node->delta.glyph_idx = glyph_idx;
1020         node->delta.ppem = ppem;
1021         node->delta.point_idx = point_idx;
1022         node->delta.x_shift = x_shift;
1023         node->delta.y_shift = y_shift;
1024
1025         val = LLRB_INSERT(deltas_data, deltas_data_head, node);
1026         if (val)
1027           free(node);
1028         if (val && font->debug)
1029         {
1030           /* entry is already present; we ignore it */
1031           Deltas deltas;
1032           number_range ppems;
1033           number_range points;
1034
1035           char* s;
1036           int s_len;
1037
1038
1039           /* construct Deltas entry for debugging output */
1040           ppems.start = ppem;
1041           ppems.end = ppem;
1042           ppems.next = NULL;
1043           points.start = point_idx;
1044           points.end = point_idx;
1045           points.next = NULL;
1046
1047           deltas.font_idx = font_idx;
1048           deltas.glyph_idx = glyph_idx;
1049           deltas.points = &points;
1050           deltas.x_shift = x_shift;
1051           deltas.y_shift = y_shift;
1052           deltas.ppems = &ppems;
1053           deltas.next = NULL;
1054
1055           s = deltas_show_line(font, &s_len, &deltas);
1056           if (s)
1057           {
1058             fprintf(stderr, "Delta exception %s ignored.\n", s);
1059             free(s);
1060           }
1061
1062           emit_newline = 1;
1063         }
1064
1065         point_idx = number_set_get_next(&points_iter);
1066       }
1067
1068       ppem = number_set_get_next(&ppems_iter);
1069     }
1070
1071     deltas = deltas->next;
1072   }
1073
1074   if (font->debug && emit_newline)
1075     fprintf(stderr, "\n");
1076
1077   font->deltas_data_head = deltas_data_head;
1078   font->deltas_data_cur = LLRB_MIN(deltas_data, deltas_data_head);
1079
1080   return TA_Err_Ok;
1081 }
1082
1083
1084 /* the next functions are intended to restrict the use of LLRB stuff */
1085 /* related to delta exceptions to this file, */
1086 /* providing a means to access the data sequentially */
1087
1088 void
1089 TA_deltas_get_next(FONT* font)
1090 {
1091   Node* node = (Node*)font->deltas_data_cur;
1092
1093
1094   if (!node)
1095     return;
1096
1097   node = LLRB_NEXT(deltas_data, /* unused */, node);
1098
1099   font->deltas_data_cur = node;
1100 }
1101
1102
1103 const Delta*
1104 TA_deltas_get_delta(FONT* font)
1105 {
1106   Node* node = (Node*)font->deltas_data_cur;
1107
1108
1109   return node ? &node->delta : NULL;
1110 }
1111
1112 /* end of tadeltas.c */