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