libass/ass_font.c

   1 /*
   2  * Copyright (C) 2006 Evgeniy Stepanov <eugeni.stepanov@gmail.com>
   3  *
   4  * This file is part of libass.
   5  *
   6  * Permission to use, copy, modify, and distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18
  19 #include "config.h"
  20
  21 #include <inttypes.h>
  22 #include <ft2build.h>
  23 #include FT_FREETYPE_H
  24 #include FT_SYNTHESIS_H
  25 #include FT_GLYPH_H
  26 #include FT_TRUETYPE_TABLES_H
  27 #include FT_OUTLINE_H
  28 #include <strings.h>
  29
  30 #include "ass.h"
  31 #include "ass_library.h"
  32 #include "ass_font.h"
  33 #include "ass_fontconfig.h"
  34 #include "ass_utils.h"
  35
  36 #define VERTICAL_LOWER_BOUND 0x02f1
  37
  38 /**
  39  * Select a good charmap, prefer Microsoft Unicode charmaps.
  40  * Otherwise, let FreeType decide.
  41  */
  42 static void charmap_magic(ASS_Library *library, FT_Face face)
  43 {
  44     int i;
  45     int ms_cmap = -1;
  46
  47     // Search for a Microsoft Unicode cmap
  48     for (i = 0; i < face->num_charmaps; ++i) {
  49         FT_CharMap cmap = face->charmaps[i];
  50         unsigned pid = cmap->platform_id;
  51         unsigned eid = cmap->encoding_id;
  52         if (pid == 3 /*microsoft */
  53             && (eid == 1 /*unicode bmp */
  54                 || eid == 10 /*full unicode */ )) {
  55             FT_Set_Charmap(face, cmap);
  56             return;
  57         } else if (pid == 3 && ms_cmap < 0)
  58             ms_cmap = i;
  59     }
  60
  61     // Try the first Microsoft cmap if no Microsoft Unicode cmap was found
  62     if (ms_cmap >= 0) {
  63         FT_CharMap cmap = face->charmaps[ms_cmap];
  64         FT_Set_Charmap(face, cmap);
  65         return;
  66     }
  67
  68     if (!face->charmap) {
  69         if (face->num_charmaps == 0) {
  70             ass_msg(library, MSGL_WARN, "Font face with no charmaps");
  71             return;
  72         }
  73         ass_msg(library, MSGL_WARN,
  74                 "No charmap autodetected, trying the first one");
  75         FT_Set_Charmap(face, face->charmaps[0]);
  76         return;
  77     }
  78 }
  79
  80 /**
  81  * \brief find a memory font by name
  82  */
  83 static int find_font(ASS_Library *library, char *name)
  84 {
  85     int i;
  86     for (i = 0; i < library->num_fontdata; ++i)
  87         if (strcasecmp(name, library->fontdata[i].name) == 0)
  88             return i;
  89     return -1;
  90 }
  91
  92 static void face_set_size(FT_Face face, double size);
  93
  94 static void buggy_font_workaround(FT_Face face)
  95 {
  96     // Some fonts have zero Ascender/Descender fields in 'hhea' table.
  97     // In this case, get the information from 'os2' table or, as
  98     // a last resort, from face.bbox.
  99     if (face->ascender + face->descender == 0 || face->height == 0) {
 100         TT_OS2 *os2 = FT_Get_Sfnt_Table(face, ft_sfnt_os2);
 101         if (os2) {
 102             face->ascender = os2->sTypoAscender;
 103             face->descender = os2->sTypoDescender;
 104             face->height = face->ascender - face->descender;
 105         } else {
 106             face->ascender = face->bbox.yMax;
 107             face->descender = face->bbox.yMin;
 108             face->height = face->ascender - face->descender;
 109         }
 110     }
 111 }
 112
 113 /**
 114  * \brief Select a face with the given charcode and add it to ASS_Font
 115  * \return index of the new face in font->faces, -1 if failed
 116  */
 117 static int add_face(void *fc_priv, ASS_Font *font, uint32_t ch)
 118 {
 119     char *path;
 120     int index;
 121     FT_Face face;
 122     int error;
 123     int mem_idx;
 124
 125     if (font->n_faces == ASS_FONT_MAX_FACES)
 126         return -1;
 127
 128     path =
 129         fontconfig_select(font->library, fc_priv, font->desc.family,
 130                           font->desc.treat_family_as_pattern,
 131                           font->desc.bold, font->desc.italic, &index, ch);
 132     if (!path)
 133         return -1;
 134
 135     mem_idx = find_font(font->library, path);
 136     if (mem_idx >= 0) {
 137         error =
 138             FT_New_Memory_Face(font->ftlibrary,
 139                                (unsigned char *) font->library->
 140                                fontdata[mem_idx].data,
 141                                font->library->fontdata[mem_idx].size, index,
 142                                &face);
 143         if (error) {
 144             ass_msg(font->library, MSGL_WARN,
 145                     "Error opening memory font: '%s'", path);
 146             free(path);
 147             return -1;
 148         }
 149     } else {
 150         error = FT_New_Face(font->ftlibrary, path, index, &face);
 151         if (error) {
 152             ass_msg(font->library, MSGL_WARN,
 153                     "Error opening font: '%s', %d", path, index);
 154             free(path);
 155             return -1;
 156         }
 157     }
 158     charmap_magic(font->library, face);
 159     buggy_font_workaround(face);
 160
 161     font->faces[font->n_faces++] = face;
 162     face_set_size(face, font->size);
 163     free(path);
 164     return font->n_faces - 1;
 165 }
 166
 167 /**
 168  * \brief Create a new ASS_Font according to "desc" argument
 169  */
 170 ASS_Font *ass_font_new(Cache *font_cache, ASS_Library *library,
 171                        FT_Library ftlibrary, void *fc_priv,
 172                        ASS_FontDesc *desc)
 173 {
 174     int error;
 175     ASS_Font *fontp;
 176     ASS_Font font;
 177
 178     fontp = ass_cache_get(font_cache, desc);
 179     if (fontp)
 180         return fontp;
 181
 182     font.library = library;
 183     font.ftlibrary = ftlibrary;
 184     font.n_faces = 0;
 185     font.desc.family = strdup(desc->family);
 186     font.desc.treat_family_as_pattern = desc->treat_family_as_pattern;
 187     font.desc.bold = desc->bold;
 188     font.desc.italic = desc->italic;
 189     font.desc.vertical = desc->vertical;
 190
 191     font.scale_x = font.scale_y = 1.;
 192     font.v.x = font.v.y = 0;
 193     font.size = 0.;
 194
 195     error = add_face(fc_priv, &font, 0);
 196     if (error == -1) {
 197         free(font.desc.family);
 198         return 0;
 199     } else
 200         return ass_cache_put(font_cache, &font.desc, &font);
 201 }
 202
 203 /**
 204  * \brief Set font transformation matrix and shift vector
 205  **/
 206 void ass_font_set_transform(ASS_Font *font, double scale_x,
 207                             double scale_y, FT_Vector *v)
 208 {
 209     font->scale_x = scale_x;
 210     font->scale_y = scale_y;
 211     if (v) {
 212         font->v.x = v->x;
 213         font->v.y = v->y;
 214     }
 215 }
 216
 217 static void face_set_size(FT_Face face, double size)
 218 {
 219     TT_HoriHeader *hori = FT_Get_Sfnt_Table(face, ft_sfnt_hhea);
 220     TT_OS2 *os2 = FT_Get_Sfnt_Table(face, ft_sfnt_os2);
 221     double mscale = 1.;
 222     FT_Size_RequestRec rq;
 223     FT_Size_Metrics *m = &face->size->metrics;
 224     // VSFilter uses metrics from TrueType OS/2 table
 225     // The idea was borrowed from asa (http://asa.diac24.net)
 226     if (hori && os2) {
 227         int hori_height = hori->Ascender - hori->Descender;
 228         int os2_height = os2->usWinAscent + os2->usWinDescent;
 229         if (hori_height && os2_height)
 230             mscale = (double) hori_height / os2_height;
 231     }
 232     memset(&rq, 0, sizeof(rq));
 233     rq.type = FT_SIZE_REQUEST_TYPE_REAL_DIM;
 234     rq.width = 0;
 235     rq.height = double_to_d6(size * mscale);
 236     rq.horiResolution = rq.vertResolution = 0;
 237     FT_Request_Size(face, &rq);
 238     m->ascender /= mscale;
 239     m->descender /= mscale;
 240     m->height /= mscale;
 241 }
 242
 243 /**
 244  * \brief Set font size
 245  **/
 246 void ass_font_set_size(ASS_Font *font, double size)
 247 {
 248     int i;
 249     if (font->size != size) {
 250         font->size = size;
 251         for (i = 0; i < font->n_faces; ++i)
 252             face_set_size(font->faces[i], size);
 253     }
 254 }
 255
 256 /**
 257  * \brief Get maximal font ascender and descender.
 258  * \param ch character code
 259  * The values are extracted from the font face that provides glyphs for the given character
 260  **/
 261 void ass_font_get_asc_desc(ASS_Font *font, uint32_t ch, int *asc,
 262                            int *desc)
 263 {
 264     int i;
 265     for (i = 0; i < font->n_faces; ++i) {
 266         FT_Face face = font->faces[i];
 267         TT_OS2 *os2 = FT_Get_Sfnt_Table(face, ft_sfnt_os2);
 268         if (FT_Get_Char_Index(face, ch)) {
 269             int y_scale = face->size->metrics.y_scale;
 270             if (os2) {
 271                 *asc = FT_MulFix(os2->usWinAscent, y_scale);
 272                 *desc = FT_MulFix(os2->usWinDescent, y_scale);
 273             } else {
 274                 *asc = FT_MulFix(face->ascender, y_scale);
 275                 *desc = FT_MulFix(-face->descender, y_scale);
 276             }
 277             if (font->desc.vertical && ch >= VERTICAL_LOWER_BOUND) {
 278                 *asc = FT_MulFix(face->max_advance_width, y_scale);
 279             }
 280             return;
 281         }
 282     }
 283
 284     *asc = *desc = 0;
 285 }
 286
 287 /*
 288  * Strike a glyph with a horizontal line; it's possible to underline it
 289  * and/or strike through it.  For the line's position and size, truetype
 290  * tables are consulted.  Obviously this relies on the data in the tables
 291  * being accurate.
 292  *
 293  */
 294 static int ass_strike_outline_glyph(FT_Face face, ASS_Font *font,
 295                                     FT_Glyph glyph, int under, int through)
 296 {
 297     TT_OS2 *os2 = FT_Get_Sfnt_Table(face, ft_sfnt_os2);
 298     TT_Postscript *ps = FT_Get_Sfnt_Table(face, ft_sfnt_post);
 299     FT_Outline *ol = &((FT_OutlineGlyph) glyph)->outline;
 300     int bear, advance, y_scale, i, dir;
 301
 302     if (!under && !through)
 303         return 0;
 304
 305     // Grow outline
 306     i = (under ? 4 : 0) + (through ? 4 : 0);
 307     ol->points = realloc(ol->points, sizeof(FT_Vector) *
 308                          (ol->n_points + i));
 309     ol->tags = realloc(ol->tags, ol->n_points + i);
 310     i = !!under + !!through;
 311     ol->contours = realloc(ol->contours, sizeof(short) *
 312                            (ol->n_contours + i));
 313
 314     // If the bearing is negative, the glyph starts left of the current
 315     // pen position
 316     bear = FFMIN(face->glyph->metrics.horiBearingX, 0);
 317     // We're adding half a pixel to avoid small gaps
 318     advance = d16_to_d6(glyph->advance.x) + 32;
 319     y_scale = face->size->metrics.y_scale;
 320
 321     // Reverse drawing direction for non-truetype fonts
 322     dir = FT_Outline_Get_Orientation(ol);
 323
 324     // Add points to the outline
 325     if (under && ps) {
 326         int pos, size;
 327         pos = FT_MulFix(ps->underlinePosition, y_scale * font->scale_y);
 328         size = FT_MulFix(ps->underlineThickness,
 329                          y_scale * font->scale_y / 2);
 330
 331         if (pos > 0 || size <= 0)
 332             return 1;
 333
 334         FT_Vector points[4] = {
 335             {.x = bear,      .y = pos + size},
 336             {.x = advance,   .y = pos + size},
 337             {.x = advance,   .y = pos - size},
 338             {.x = bear,      .y = pos - size},
 339         };
 340
 341         if (dir == FT_ORIENTATION_TRUETYPE) {
 342             for (i = 0; i < 4; i++) {
 343                 ol->points[ol->n_points] = points[i];
 344                 ol->tags[ol->n_points++] = 1;
 345             }
 346         } else {
 347             for (i = 3; i >= 0; i--) {
 348                 ol->points[ol->n_points] = points[i];
 349                 ol->tags[ol->n_points++] = 1;
 350             }
 351         }
 352
 353         ol->contours[ol->n_contours++] = ol->n_points - 1;
 354     }
 355
 356     if (through && os2) {
 357         int pos, size;
 358         pos = FT_MulFix(os2->yStrikeoutPosition, y_scale * font->scale_y);
 359         size = FT_MulFix(os2->yStrikeoutSize, y_scale * font->scale_y / 2);
 360
 361         if (pos < 0 || size <= 0)
 362             return 1;
 363
 364         FT_Vector points[4] = {
 365             {.x = bear,      .y = pos + size},
 366             {.x = advance,   .y = pos + size},
 367             {.x = advance,   .y = pos - size},
 368             {.x = bear,      .y = pos - size},
 369         };
 370
 371         if (dir == FT_ORIENTATION_TRUETYPE) {
 372             for (i = 0; i < 4; i++) {
 373                 ol->points[ol->n_points] = points[i];
 374                 ol->tags[ol->n_points++] = 1;
 375             }
 376         } else {
 377             for (i = 3; i >= 0; i--) {
 378                 ol->points[ol->n_points] = points[i];
 379                 ol->tags[ol->n_points++] = 1;
 380             }
 381         }
 382
 383         ol->contours[ol->n_contours++] = ol->n_points - 1;
 384     }
 385
 386     return 0;
 387 }
 388
 389 void outline_copy(FT_Library lib, FT_Outline *source, FT_Outline **dest)
 390 {
 391     if (source == NULL) {
 392         *dest = NULL;
 393         return;
 394     }
 395     *dest = calloc(1, sizeof(**dest));
 396
 397     FT_Outline_New(lib, source->n_points, source->n_contours, *dest);
 398     FT_Outline_Copy(source, *dest);
 399 }
 400
 401 void outline_free(FT_Library lib, FT_Outline *outline)
 402 {
 403     if (outline)
 404         FT_Outline_Done(lib, outline);
 405     free(outline);
 406 }
 407
 408 /**
 409  * Slightly embold a glyph without touching its metrics
 410  */
 411 static void ass_glyph_embolden(FT_GlyphSlot slot)
 412 {
 413     int str;
 414
 415     if (slot->format != FT_GLYPH_FORMAT_OUTLINE)
 416         return;
 417
 418     str = FT_MulFix(slot->face->units_per_EM,
 419                     slot->face->size->metrics.y_scale) / 64;
 420
 421     FT_Outline_Embolden(&slot->outline, str);
 422 }
 423
 424 /**
 425  * \brief Get glyph and face index
 426  * Finds a face that has the requested codepoint and returns both face
 427  * and glyph index.
 428  */
 429 int ass_font_get_index(void *fcpriv, ASS_Font *font, uint32_t symbol,
 430                        int *face_index, int *glyph_index)
 431 {
 432     int index = 0;
 433     int i;
 434     FT_Face face = 0;
 435
 436     *glyph_index = 0;
 437
 438     if (symbol < 0x20) {
 439         *face_index = 0;
 440         return 0;
 441     }
 442     // Handle NBSP like a regular space when rendering the glyph
 443     if (symbol == 0xa0)
 444         symbol = ' ';
 445     if (font->n_faces == 0) {
 446         *face_index = 0;
 447         return 0;
 448     }
 449
 450     // try with the requested face
 451     if (*face_index < font->n_faces) {
 452         face = font->faces[i];
 453         index = FT_Get_Char_Index(face, symbol);
 454     }
 455
 456     // not found in requested face, try all others
 457     for (i = 0; i < font->n_faces && index == 0; ++i) {
 458         face = font->faces[i];
 459         index = FT_Get_Char_Index(face, symbol);
 460         if (index)
 461             *face_index = i;
 462     }
 463
 464 #ifdef CONFIG_FONTCONFIG
 465     if (index == 0) {
 466         int face_idx;
 467         ass_msg(font->library, MSGL_INFO,
 468                 "Glyph 0x%X not found, selecting one more "
 469                 "font for (%s, %d, %d)", symbol, font->desc.family,
 470                 font->desc.bold, font->desc.italic);
 471         face_idx = *face_index = add_face(fcpriv, font, symbol);
 472         if (face_idx >= 0) {
 473             face = font->faces[face_idx];
 474             index = FT_Get_Char_Index(face, symbol);
 475             if (index == 0 && face->num_charmaps > 0) {
 476                 int i;
 477                 ass_msg(font->library, MSGL_WARN,
 478                     "Glyph 0x%X not found, broken font? Trying all charmaps", symbol);
 479                 for (i = 0; i < face->num_charmaps; i++) {
 480                     FT_Set_Charmap(face, face->charmaps[i]);
 481                     if ((index = FT_Get_Char_Index(face, symbol)) != 0) break;
 482                 }
 483             }
 484             if (index == 0) {
 485                 ass_msg(font->library, MSGL_ERR,
 486                         "Glyph 0x%X not found in font for (%s, %d, %d)",
 487                         symbol, font->desc.family, font->desc.bold,
 488                         font->desc.italic);
 489             }
 490         }
 491     }
 492 #endif
 493     *glyph_index = index;
 494
 495     return 1;
 496 }
 497
 498 /**
 499  * \brief Get a glyph
 500  * \param ch character code
 501  **/
 502 FT_Glyph ass_font_get_glyph(void *fontconfig_priv, ASS_Font *font,
 503                             uint32_t ch, int face_index, int index,
 504                             ASS_Hinting hinting, int deco)
 505 {
 506     int error;
 507     FT_Glyph glyph;
 508     FT_Face face = font->faces[face_index];
 509     int flags = 0;
 510     int vertical = font->desc.vertical;
 511
 512     flags = FT_LOAD_NO_BITMAP | FT_LOAD_IGNORE_GLOBAL_ADVANCE_WIDTH
 513             | FT_LOAD_IGNORE_TRANSFORM;
 514     switch (hinting) {
 515     case ASS_HINTING_NONE:
 516         flags |= FT_LOAD_NO_HINTING;
 517         break;
 518     case ASS_HINTING_LIGHT:
 519         flags |= FT_LOAD_FORCE_AUTOHINT | FT_LOAD_TARGET_LIGHT;
 520         break;
 521     case ASS_HINTING_NORMAL:
 522         flags |= FT_LOAD_FORCE_AUTOHINT;
 523         break;
 524     case ASS_HINTING_NATIVE:
 525         break;
 526     }
 527
 528     error = FT_Load_Glyph(face, index, flags);
 529     if (error) {
 530         ass_msg(font->library, MSGL_WARN, "Error loading glyph, index %d",
 531                 index);
 532         return 0;
 533     }
 534     if (!(face->style_flags & FT_STYLE_FLAG_ITALIC) &&
 535         (font->desc.italic > 55)) {
 536         FT_GlyphSlot_Oblique(face->glyph);
 537     }
 538
 539     if (!(face->style_flags & FT_STYLE_FLAG_BOLD) &&
 540         (font->desc.bold > 80)) {
 541         ass_glyph_embolden(face->glyph);
 542     }
 543     error = FT_Get_Glyph(face->glyph, &glyph);
 544     if (error) {
 545         ass_msg(font->library, MSGL_WARN, "Error loading glyph, index %d",
 546                 index);
 547         return 0;
 548     }
 549
 550     // Rotate glyph, if needed
 551     if (vertical && ch >= VERTICAL_LOWER_BOUND) {
 552         FT_Matrix m = { 0, double_to_d16(-1.0), double_to_d16(1.0), 0 };
 553         FT_Outline_Transform(&((FT_OutlineGlyph) glyph)->outline, &m);
 554         FT_Outline_Translate(&((FT_OutlineGlyph) glyph)->outline,
 555                              face->glyph->metrics.vertAdvance,
 556                              0);
 557         glyph->advance.x = face->glyph->linearVertAdvance;
 558     }
 559
 560     // Apply scaling and shift
 561     FT_Matrix scale = { double_to_d16(font->scale_x), 0, 0,
 562                         double_to_d16(font->scale_y) };
 563     FT_Outline *outl = &((FT_OutlineGlyph) glyph)->outline;
 564     FT_Outline_Transform(outl, &scale);
 565     FT_Outline_Translate(outl, font->v.x, font->v.y);
 566     glyph->advance.x *= font->scale_x;
 567
 568     ass_strike_outline_glyph(face, font, glyph, deco & DECO_UNDERLINE,
 569                              deco & DECO_STRIKETHROUGH);
 570
 571     return glyph;
 572 }
 573
 574 /**
 575  * \brief Get kerning for the pair of glyphs.
 576  **/
 577 FT_Vector ass_font_get_kerning(ASS_Font *font, uint32_t c1, uint32_t c2)
 578 {
 579     FT_Vector v = { 0, 0 };
 580     int i;
 581
 582     if (font->desc.vertical)
 583         return v;
 584
 585     for (i = 0; i < font->n_faces; ++i) {
 586         FT_Face face = font->faces[i];
 587         int i1 = FT_Get_Char_Index(face, c1);
 588         int i2 = FT_Get_Char_Index(face, c2);
 589         if (i1 && i2) {
 590             if (FT_HAS_KERNING(face))
 591                 FT_Get_Kerning(face, i1, i2, FT_KERNING_DEFAULT, &v);
 592             return v;
 593         }
 594         if (i1 || i2)           // these glyphs are from different font faces, no kerning information
 595             return v;
 596     }
 597     return v;
 598 }
 599
 600 /**
 601  * \brief Deallocate ASS_Font
 602  **/
 603 void ass_font_free(ASS_Font *font)
 604 {
 605     int i;
 606     for (i = 0; i < font->n_faces; ++i)
 607         if (font->faces[i])
 608             FT_Done_Face(font->faces[i]);
 609     free(font->desc.family);
 610     free(font);
 611 }
 612
 613 /**
 614  * \brief Calculate the cbox of a series of points
 615  */
 616 static void
 617 get_contour_cbox(FT_BBox *box, FT_Vector *points, int start, int end)
 618 {
 619     box->xMin = box->yMin = INT_MAX;
 620     box->xMax = box->yMax = INT_MIN;
 621     int i;
 622
 623     for (i = start; i <= end; i++) {
 624         box->xMin = (points[i].x < box->xMin) ? points[i].x : box->xMin;
 625         box->xMax = (points[i].x > box->xMax) ? points[i].x : box->xMax;
 626         box->yMin = (points[i].y < box->yMin) ? points[i].y : box->yMin;
 627         box->yMax = (points[i].y > box->yMax) ? points[i].y : box->yMax;
 628     }
 629 }
 630
 631 /**
 632  * \brief Determine winding direction of a contour
 633  * \return direction; 0 = clockwise
 634  */
 635 static int get_contour_direction(FT_Vector *points, int start, int end)
 636 {
 637     int i;
 638     long long sum = 0;
 639     int x = points[start].x;
 640     int y = points[start].y;
 641     for (i = start + 1; i <= end; i++) {
 642         sum += x * (points[i].y - y) - y * (points[i].x - x);
 643         x = points[i].x;
 644         y = points[i].y;
 645     }
 646     sum += x * (points[start].y - y) - y * (points[start].x - x);
 647     return sum > 0;
 648 }
 649
 650 /**
 651  * \brief Fix-up stroker result for huge borders by removing inside contours
 652  * that would reverse in size
 653  */
 654 void fix_freetype_stroker(FT_Outline *outline, int border_x, int border_y)
 655 {
 656     int nc = outline->n_contours;
 657     int begin, stop;
 658     char modified = 0;
 659     char *valid_cont = malloc(nc);
 660     int start = 0;
 661     int end = -1;
 662     FT_BBox *boxes = malloc(nc * sizeof(FT_BBox));
 663     int i, j;
 664     int inside_direction;
 665
 666     inside_direction = FT_Outline_Get_Orientation(outline) ==
 667         FT_ORIENTATION_TRUETYPE;
 668
 669     // create a list of cboxes of the contours
 670     for (i = 0; i < nc; i++) {
 671         start = end + 1;
 672         end = outline->contours[i];
 673         get_contour_cbox(&boxes[i], outline->points, start, end);
 674     }
 675
 676     // for each contour, check direction and whether it's "outside"
 677     // or contained in another contour
 678     end = -1;
 679     for (i = 0; i < nc; i++) {
 680         start = end + 1;
 681         end = outline->contours[i];
 682         int dir = get_contour_direction(outline->points, start, end);
 683         valid_cont[i] = 1;
 684         if (dir == inside_direction) {
 685             for (j = 0; j < nc; j++) {
 686                 if (i == j)
 687                     continue;
 688                 if (boxes[i].xMin >= boxes[j].xMin &&
 689                     boxes[i].xMax <= boxes[j].xMax &&
 690                     boxes[i].yMin >= boxes[j].yMin &&
 691                     boxes[i].yMax <= boxes[j].yMax)
 692                     goto check_inside;
 693             }
 694             /* "inside" contour but we can't find anything it could be
 695              * inside of - assume the font is buggy and it should be
 696              * an "outside" contour, and reverse it */
 697             for (j = 0; j < (end + 1 - start) / 2; j++) {
 698                 FT_Vector temp = outline->points[start + j];
 699                 char temp2 = outline->tags[start + j];
 700                 outline->points[start + j] = outline->points[end - j];
 701                 outline->points[end - j] = temp;
 702                 outline->tags[start + j] = outline->tags[end - j];
 703                 outline->tags[end - j] = temp2;
 704             }
 705             dir ^= 1;
 706         }
 707         check_inside:
 708         if (dir == inside_direction) {
 709             FT_BBox box;
 710             get_contour_cbox(&box, outline->points, start, end);
 711             int width = box.xMax - box.xMin;
 712             int height = box.yMax - box.yMin;
 713             if (width < border_x * 2 || height < border_y * 2) {
 714                 valid_cont[i] = 0;
 715                 modified = 1;
 716             }
 717         }
 718     }
 719
 720     // zero-out contours that can be removed; much simpler than copying
 721     if (modified) {
 722         for (i = 0; i < nc; i++) {
 723             if (valid_cont[i])
 724                 continue;
 725             begin = (i == 0) ? 0 : outline->contours[i - 1] + 1;
 726             stop = outline->contours[i];
 727             for (j = begin; j <= stop; j++) {
 728                 outline->points[j].x = 0;
 729                 outline->points[j].y = 0;
 730                 outline->tags[j] = 0;
 731             }
 732         }
 733     }
 734
 735     free(boxes);
 736     free(valid_cont);
 737 }
 738