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