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