ttf2png.c

   1 /*
   2 ttf2png - True Type Font to PNG converter
   3 Copyright (c) 2004-2008 Mikko Rasa
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation; either version 2 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18 */
  19
  20 #include <stdio.h>
  21 #include <ctype.h>
  22 #include <unistd.h>
  23 #include <getopt.h>
  24 #include <png.h>
  25 #include <ft2build.h>
  26 #include FT_FREETYPE_H
  27
  28 typedef struct sImage
  29 {
  30         unsigned w, h;
  31         char *data;
  32 } Image;
  33
  34 typedef struct sGlyph
  35 {
  36         unsigned index;
  37         unsigned code;
  38         Image image;
  39         unsigned x, y;
  40         int offset_x;
  41         int offset_y;
  42         int advance;
  43 } Glyph;
  44
  45 typedef struct sKerning
  46 {
  47         unsigned left_code;
  48         unsigned right_code;
  49         int distance;
  50 } Kerning;
  51
  52 typedef struct sFont
  53 {
  54         unsigned size;
  55         int ascent;
  56         int descent;
  57         unsigned n_glyphs;
  58         Glyph *glyphs;
  59         unsigned n_kerning;
  60         Kerning *kerning;
  61         Image image;
  62 } Font;
  63
  64 typedef struct sRange
  65 {
  66         unsigned first;
  67         unsigned last;
  68 } Range;
  69
  70 typedef int bool;
  71
  72 void usage(void);
  73 int convert_numeric_option(char, int);
  74 void convert_code_point_range(char, Range *);
  75 unsigned str_to_code_point(const char *, char **);
  76 void convert_size(char, unsigned *, unsigned *);
  77 void sort_and_compact_ranges(Range *, unsigned *);
  78 int range_cmp(const void *, const void *);
  79 unsigned round_to_pot(unsigned);
  80 void *alloc_image_data(size_t, size_t);
  81 int init_font(Font *, FT_Face, const Range *, unsigned, bool);
  82 int init_glyphs(Font *, FT_Face, const Range *, bool);
  83 int render_grid(Font *, unsigned, unsigned, unsigned, bool);
  84 int render_packed(Font *, unsigned, unsigned);
  85 int save_defs(const char *, const Font *);
  86 int save_png(const char *, const Image *, char);
  87
  88 char verbose = 0;
  89
  90 int main(int argc, char **argv)
  91 {
  92         char *fn;
  93         Range *ranges = NULL;
  94         unsigned n_ranges = 0;
  95         unsigned size = 10;
  96         unsigned cpl = 0;
  97         unsigned cellw = 0;
  98         unsigned cellh = 0;
  99         bool autohinter = 0;
 100         bool seq = 0;
 101         bool alpha = 0;
 102         bool invert = 0;
 103         bool pack = 0;
 104         unsigned margin = 0;
 105         unsigned padding = 1;
 106
 107         FT_Library freetype;
 108         FT_Face face;
 109
 110         int err;
 111         int i;
 112
 113         char *out_fn = "font.png";
 114         char *def_fn = NULL;
 115
 116         Font font;
 117
 118         if(argc<2)
 119         {
 120                 usage();
 121                 return 1;
 122         }
 123
 124         while((i = getopt(argc, argv, "r:s:l:c:o:atvh?ed:pim:n:")) != -1)
 125         {
 126                 switch(i)
 127                 {
 128                 case 'r':
 129                         ranges = (Range *)realloc(ranges, (++n_ranges)*sizeof(Range));
 130                         convert_code_point_range('r', &ranges[n_ranges-1]);
 131                         break;
 132                 case 's':
 133                         size = convert_numeric_option('s', 1);
 134                         break;
 135                 case 'l':
 136                         cpl = convert_numeric_option('l', 1);
 137                         break;
 138                 case 'c':
 139                         convert_size('c', &cellw, &cellh);
 140                         break;
 141                 case 'o':
 142                         out_fn = optarg;
 143                         break;
 144                 case 'a':
 145                         autohinter = 1;
 146                         break;
 147                 case 't':
 148                         alpha = 1;
 149                         break;
 150                 case 'v':
 151                         ++verbose;
 152                         break;
 153                 case 'h':
 154                 case '?':
 155                         usage();
 156                         return 0;
 157                 case 'e':
 158                         seq = 1;
 159                         break;
 160                 case 'd':
 161                         def_fn = optarg;
 162                         break;
 163                 case 'p':
 164                         pack = 1;
 165                         break;
 166                 case 'i':
 167                         invert = 1;
 168                         break;
 169                 case 'm':
 170                         margin = convert_numeric_option('m', 0);
 171                         break;
 172                 case 'n':
 173                         padding = convert_numeric_option('n', 0);
 174                         break;
 175                 }
 176         }
 177         if(!strcmp(out_fn, "-"))
 178                 verbose = 0;
 179
 180         if(optind!=argc-1)
 181         {
 182                 usage();
 183                 return 1;
 184         }
 185
 186         fn = argv[optind];
 187
 188         err = FT_Init_FreeType(&freetype);
 189         if(err)
 190         {
 191                 fprintf(stderr, "Couldn't initialize FreeType library\n");
 192                 return 1;
 193         }
 194
 195         err = FT_New_Face(freetype, fn, 0, &face);
 196         if(err)
 197         {
 198                 fprintf(stderr, "Couldn't load font file\n");
 199                 if(err==FT_Err_Unknown_File_Format)
 200                         fprintf(stderr, "Unknown file format\n");
 201                 return 1;
 202         }
 203
 204         if(verbose)
 205         {
 206                 const char *name = FT_Get_Postscript_Name(face);
 207                 printf("Font name: %s\n", name);
 208                 printf("Glyphs:    %ld\n", face->num_glyphs);
 209         }
 210
 211         err = FT_Set_Pixel_Sizes(face, 0, size);
 212         if(err)
 213         {
 214                 fprintf(stderr, "Couldn't set size\n");
 215                 return 1;
 216         }
 217
 218         if(!n_ranges)
 219         {
 220                 ranges = malloc(sizeof(Range));
 221                 ranges[0].first = 0;
 222                 ranges[0].last = 255;
 223                 n_ranges = 1;
 224         }
 225         else
 226                 sort_and_compact_ranges(ranges, &n_ranges);
 227
 228         font.size = size;
 229         err = init_font(&font, face, ranges, n_ranges, autohinter);
 230         if(err)
 231                 return 1;
 232
 233         if(!font.n_glyphs)
 234         {
 235                 fprintf(stderr, "No glyphs found in the requested range\n");
 236                 return 1;
 237         }
 238
 239         if(pack)
 240                 err = render_packed(&font, margin, padding);
 241         else
 242                 err = render_grid(&font, cellw, cellh, cpl, seq);
 243         if(err)
 244                 return 1;
 245
 246         if(invert)
 247         {
 248                 for(i=0; (unsigned)i<font.image.w*font.image.h; ++i)
 249                         font.image.data[i] = 255-font.image.data[i];
 250         }
 251         err = save_png(out_fn, &font.image, alpha);
 252         if(err)
 253                 return 1;
 254
 255         if(def_fn)
 256                 save_defs(def_fn, &font);
 257
 258         for(i=0; (unsigned)i<font.n_glyphs; ++i)
 259                 free(font.glyphs[i].image.data);
 260         free(font.glyphs);
 261         free(font.kerning);
 262         free(font.image.data);
 263
 264         FT_Done_Face(face);
 265         FT_Done_FreeType(freetype);
 266
 267         return 0;
 268 }
 269
 270 void usage(void)
 271 {
 272         printf("ttf2png 1.1 - True Type Font to PNG converter\n"
 273                 "Copyright (c) 2004-2018  Mikko Rasa, Mikkosoft Productions\n"
 274                 "Distributed under the GNU General Public License\n\n");
 275
 276         printf("Usage: ttf2png [options] <TTF file>\n\n");
 277
 278         printf("Accepted options (default values in [brackets])\n"
 279                 "  -r  Range of code points to convert [0,255]\n"
 280                 "  -s  Font size to use, in pixels [10]\n"
 281                 "  -l  Number of glyphs to put in one line [auto]\n"
 282                 "  -c  Glyph cell size, in pixels (grid mode only) [auto]\n"
 283                 "  -o  Output file name (or - for stdout) [font.png]\n");
 284         printf("  -a  Force autohinter\n"
 285                 "  -t  Render glyphs to alpha channel\n"
 286                 "  -i  Invert colors of the glyphs\n"
 287                 "  -v  Increase the level of verbosity\n"
 288                 "  -e  Use cells in sequence, without gaps (grid mode only)\n"
 289                 "  -p  Pack the glyphs tightly instead of in a grid\n"
 290                 "  -m  Margin around image edges (packed mode only) [0]\n"
 291                 "  -n  Padding between glyphs (packed mode only) [1]\n"
 292                 "  -d  File name for writing glyph definitions\n"
 293                 "  -h  Print this message\n");
 294 }
 295
 296 int convert_numeric_option(char opt, int min_value)
 297 {
 298         int value;
 299         char *ptr;
 300
 301         value = strtol(optarg, &ptr, 0);
 302         if(value<min_value || *ptr)
 303         {
 304                 printf("Invalid option argument in -%c %s\n", opt, optarg);
 305                 exit(1);
 306         }
 307
 308         return value;
 309 }
 310
 311 void convert_code_point_range(char opt, Range *range)
 312 {
 313         int value;
 314         char *ptr;
 315
 316         if(!strcmp(optarg, "all"))
 317         {
 318                 range->first = 0;
 319                 range->last = 0x10FFFF;
 320                 return;
 321         }
 322
 323         value = str_to_code_point(optarg, &ptr);
 324         if(value>0 && *ptr==',')
 325         {
 326                 range->first = value;
 327                 value = str_to_code_point(ptr+1, &ptr);
 328                 if(value>0 && !*ptr)
 329                 {
 330                         range->last = value;
 331                         return;
 332                 }
 333         }
 334
 335         printf("Invalid option argument in -%c %s\n", opt, optarg);
 336         exit(1);
 337 }
 338
 339 unsigned str_to_code_point(const char *nptr, char **endptr)
 340 {
 341         if(nptr[0]=='U' && nptr[1]=='+')
 342                 return strtoul(nptr+2, endptr, 16);
 343         else if(nptr[0]&0x80)
 344         {
 345                 unsigned bytes;
 346                 unsigned code;
 347                 unsigned i;
 348
 349                 if(endptr)
 350                         *endptr = (char *)nptr;
 351
 352                 for(bytes=1; (bytes<4 && (nptr[0]&(0x80>>bytes))); ++bytes)
 353                         if((nptr[bytes]&0xC0)!=0x80)
 354                                 return 0;
 355                 if(bytes<2)
 356                         return 0;
 357
 358                 code = nptr[0]&(0x3F>>bytes);
 359                 for(i=1; i<bytes; ++i)
 360                         code = (code<<6)|(nptr[i]&0x3F);
 361
 362                 if(endptr)
 363                         *endptr = (char *)nptr+bytes;
 364
 365                 return code;
 366         }
 367         else if(isdigit(nptr[0]))
 368                 return strtoul(nptr, endptr, 0);
 369         else
 370         {
 371                 if(endptr)
 372                         *endptr = (char *)nptr+1;
 373                 return *nptr;
 374         }
 375 }
 376
 377 void convert_size(char opt, unsigned *width, unsigned *height)
 378 {
 379         int value;
 380         char *ptr;
 381
 382         if(!strcmp(optarg, "auto"))
 383         {
 384                 *width = 0;
 385                 *height = 0;
 386                 return;
 387         }
 388         else if(!strcmp(optarg, "autorect"))
 389         {
 390                 *width = 0;
 391                 *height = 1;
 392                 return;
 393         }
 394
 395         value = strtol(optarg, &ptr, 0);
 396         if(value>0)
 397         {
 398                 *width = value;
 399                 if(*ptr=='x')
 400                 {
 401                         value = strtol(ptr+1, &ptr, 0);
 402                         if(value>0 && !*ptr)
 403                         {
 404                                 *height = value;
 405                                 return;
 406                         }
 407                 }
 408                 else if(!*ptr)
 409                 {
 410                         *height = *width;
 411                         return;
 412                 }
 413         }
 414
 415         printf("Invalid option argument in -%c %s\n", opt, optarg);
 416         exit(1);
 417 }
 418
 419 void sort_and_compact_ranges(Range *ranges, unsigned *n_ranges)
 420 {
 421         unsigned i, j;
 422
 423         if(!*n_ranges)
 424                 return;
 425
 426         qsort(ranges, *n_ranges, sizeof(Range), &range_cmp);
 427         for(i=0, j=1; j<*n_ranges; ++j)
 428         {
 429                 if(ranges[i].last+1>=ranges[j].first)
 430                 {
 431                         if(ranges[j].last>ranges[i].last)
 432                                 ranges[i].last = ranges[j].last;
 433                 }
 434                 else
 435                 {
 436                         ++i;
 437                         if(i!=j)
 438                                 ranges[i] = ranges[j];
 439                 }
 440         }
 441
 442         *n_ranges = i+1;
 443 }
 444
 445 int range_cmp(const void *p1, const void *p2)
 446 {
 447         const Range *r1 = (const Range *)p1;
 448         const Range *r2 = (const Range *)p2;
 449         if(r1->first!=r2->first)
 450                 return (r1->first<r2->first ? -1 : 1);
 451         else if(r1->last!=r2->last)
 452                 return (r1->last<r2->last ? -1 : 1);
 453         else
 454                 return 0;
 455 }
 456
 457 unsigned round_to_pot(unsigned n)
 458 {
 459         n -= 1;
 460         n |= n>>1;
 461         n |= n>>2;
 462         n |= n>>4;
 463         n |= n>>8;
 464         n |= n>>16;
 465
 466         return n+1;
 467 }
 468
 469 void *alloc_image_data(size_t a, size_t b)
 470 {
 471         void *ptr;
 472
 473         /* Carry out the multiplication manually so we can check for overflow. */
 474         while(b>1)
 475         {
 476                 size_t c = a;
 477                 a *= 2;
 478                 if(b&1)
 479                         a += c;
 480                 if(a<c)
 481                 {
 482                         fprintf(stderr, "Cannot allocate %lu kbytes of memory for image\n", (unsigned long)(c/1024*b));
 483                         return NULL;
 484                 }
 485                 b /= 2;
 486         }
 487         ptr = malloc(a);
 488         if(!ptr)
 489                 fprintf(stderr, "Cannot allocate %lu kbytes of memory for image\n", (unsigned long)(a/1024*b));
 490         return ptr;
 491 }
 492
 493 int init_font(Font *font, FT_Face face, const Range *ranges, unsigned n_ranges, bool autohinter)
 494 {
 495         unsigned i, j;
 496         unsigned size = 0;
 497
 498         font->ascent = (face->size->metrics.ascender+63)>>6;
 499         font->descent = (face->size->metrics.descender+63)>>6;
 500
 501         if(verbose>=1)
 502         {
 503                 printf("Ascent:    %d\n", font->ascent);
 504                 printf("Descent:   %d\n", font->descent);
 505         }
 506
 507         font->n_glyphs = 0;
 508         font->glyphs = NULL;
 509         for(i=0; i<n_ranges; ++i)
 510                 if(init_glyphs(font, face, &ranges[i], autohinter))
 511                         return -1;
 512
 513         if(verbose>=1)
 514                 printf("Loaded %u glyphs\n", font->n_glyphs);
 515
 516         font->n_kerning = 0;
 517         font->kerning = NULL;
 518         for(i=0; i<font->n_glyphs; ++i) for(j=0; j<font->n_glyphs; ++j)
 519                 if(j!=i)
 520                 {
 521                         FT_Vector kerning;
 522                         FT_Get_Kerning(face, font->glyphs[i].index, font->glyphs[j].index, FT_KERNING_DEFAULT, &kerning);
 523
 524                         /* FreeType documentation says that vertical kerning is practically
 525                         never used, so we ignore it. */
 526                         if(kerning.x)
 527                         {
 528                                 Kerning *kern;
 529
 530                                 if(font->n_kerning>=size)
 531                                 {
 532                                         size += 16;
 533                                         font->kerning = (Kerning *)realloc(font->kerning, size*sizeof(Kerning));
 534                                 }
 535
 536                                 kern = &font->kerning[font->n_kerning++];
 537                                 kern->left_code = font->glyphs[i].code;
 538                                 kern->right_code = font->glyphs[j].code;
 539                                 kern->distance = kerning.x/64;
 540                         }
 541                 }
 542
 543         if(verbose>=1)
 544                 printf("Loaded %d kerning pairs\n", font->n_kerning);
 545
 546         return 0;
 547 }
 548
 549 int init_glyphs(Font *font, FT_Face face, const Range *range, bool autohinter)
 550 {
 551         unsigned i, j;
 552         unsigned size = font->n_glyphs;
 553
 554         for(i=range->first; i<=range->last; ++i)
 555         {
 556                 unsigned n;
 557                 FT_Bitmap *bmp = &face->glyph->bitmap;
 558                 unsigned x, y;
 559                 int flags = 0;
 560                 Glyph *glyph;
 561
 562                 n = FT_Get_Char_Index(face, i);
 563                 if(!n)
 564                         continue;
 565
 566                 if(autohinter)
 567                         flags |= FT_LOAD_FORCE_AUTOHINT;
 568                 FT_Load_Glyph(face, n, flags);
 569                 FT_Render_Glyph(face->glyph, FT_RENDER_MODE_NORMAL);
 570
 571                 if(verbose>=2)
 572                 {
 573                         printf("  Code point U+%04X", i);
 574                         if(i>=0x20 && i<0x7F)
 575                                 printf(" (%c)", i);
 576                         else if(i>=0xA0 && i<=0x10FFFF)
 577                         {
 578                                 char utf8[5];
 579                                 unsigned bytes;
 580
 581                                 for(bytes=2; i>>(1+bytes*5); ++bytes) ;
 582                                 for(j=0; j<bytes; ++j)
 583                                         utf8[j] = 0x80 | ((i>>((bytes-j-1)*6))&0x3F);
 584                                 utf8[0] |= 0xF0<<(4-bytes);
 585                                 utf8[j] = 0;
 586
 587                                 printf(" (%s)", utf8);
 588                         }
 589                         printf(": glyph %u, size %dx%d\n", n, bmp->width, bmp->rows);
 590                 }
 591
 592                 if(bmp->pixel_mode!=FT_PIXEL_MODE_GRAY)
 593                 {
 594                         fprintf(stderr, "Warning: Glyph %u skipped, not grayscale\n", n);
 595                         continue;
 596                 }
 597
 598                 if(font->n_glyphs>=size)
 599                 {
 600                         size += 16;
 601                         font->glyphs = (Glyph *)realloc(font->glyphs, size*sizeof(Glyph));
 602                 }
 603
 604                 glyph = &font->glyphs[font->n_glyphs++];
 605                 glyph->index = n;
 606                 glyph->code = i;
 607                 glyph->image.w = bmp->width;
 608                 glyph->image.h = bmp->rows;
 609                 glyph->image.data = (char *)malloc(bmp->width*bmp->rows);
 610                 if(!glyph->image.data)
 611                 {
 612                         fprintf(stderr, "Cannot allocate %d bytes of memory for glyph\n", bmp->width*bmp->rows);
 613                         return -1;
 614                 }
 615                 glyph->offset_x = face->glyph->bitmap_left;
 616                 glyph->offset_y = face->glyph->bitmap_top-bmp->rows;
 617                 glyph->advance = (int)(face->glyph->advance.x+32)/64;
 618
 619                 /* Copy the glyph image since FreeType uses a global buffer, which would
 620                 be overwritten by the next glyph.  Negative pitch means the scanlines
 621                 start from the bottom. */
 622                 if(bmp->pitch<0)
 623                 {
 624                         for(y=0; y<bmp->rows; ++y) for(x=0; x<bmp->width; ++x)
 625                                 glyph->image.data[x+(glyph->image.h-1-y)*glyph->image.w] = bmp->buffer[x-y*bmp->pitch];
 626                 }
 627                 else
 628                 {
 629                         for(y=0; y<bmp->rows; ++y) for(x=0; x<bmp->width; ++x)
 630                                 glyph->image.data[x+y*glyph->image.w] = bmp->buffer[x+y*bmp->pitch];
 631                 }
 632         }
 633
 634         return 0;
 635 }
 636
 637 int render_grid(Font *font, unsigned cellw, unsigned cellh, unsigned cpl, bool seq)
 638 {
 639         unsigned i;
 640         int top = 0, bot = 0;
 641         unsigned first, last;
 642         unsigned maxw = 0, maxh = 0;
 643
 644         /* Find extremes of the glyph images. */
 645         for(i=0; i<font->n_glyphs; ++i)
 646         {
 647                 int y;
 648
 649                 y = font->glyphs[i].offset_y+font->glyphs[i].image.h;
 650                 if(y>top)
 651                         top = y;
 652                 if(font->glyphs[i].offset_y<bot)
 653                         bot = font->glyphs[i].offset_y;
 654                 if(font->glyphs[i].image.w>maxw)
 655                         maxw = font->glyphs[i].image.w;
 656                 if(font->glyphs[i].image.h>maxh)
 657                         maxh = font->glyphs[i].image.h;
 658         }
 659
 660         if(cellw==0)
 661         {
 662                 /* Establish a large enough cell to hold all glyphs in the range. */
 663                 int square = (cellh==cellw);
 664                 cellw = maxw;
 665                 cellh = top-bot;
 666                 if(square)
 667                 {
 668                         if(cellh>cellw)
 669                                 cellw = cellh;
 670                         else
 671                                 cellh = cellw;
 672                 }
 673         }
 674
 675         if(verbose>=1)
 676         {
 677                 printf("Max size:  %u x %u\n", maxw, maxh);
 678                 printf("Y range:   [%d %d]\n", bot, top);
 679                 printf("Cell size: %u x %u\n", cellw, cellh);
 680                 if(maxw>cellw || (unsigned)(top-bot)>cellh)
 681                         fprintf(stderr, "Warning: character size exceeds cell size\n");
 682         }
 683
 684         if(cpl==0)
 685         {
 686                 /* Determine number of characters per line, trying to fit all the glyphs
 687                 in a square image. */
 688                 for(i=1;; i<<=1)
 689                 {
 690                         cpl = i/cellw;
 691                         if(cpl>0 && font->n_glyphs/cpl*cellh<=cpl*cellw)
 692                                 break;
 693                 }
 694         }
 695
 696         first = font->glyphs[0].code;
 697         if(!seq)
 698                 first -= first%cpl;
 699         last = font->glyphs[font->n_glyphs-1].code;
 700
 701         font->image.w = round_to_pot(cpl*cellw);
 702         if(seq)
 703                 font->image.h = round_to_pot((font->n_glyphs+cpl-1)/cpl*cellh);
 704         else
 705                 font->image.h = round_to_pot((last-first+cpl)/cpl*cellh);
 706
 707         font->image.data = (char *)alloc_image_data(font->image.w, font->image.h);
 708         if(!font->image.data)
 709                 return -1;
 710         memset(font->image.data, 255, font->image.w*font->image.h);
 711
 712         for(i=0; i<font->n_glyphs; ++i)
 713         {
 714                 Glyph *glyph;
 715                 unsigned ci, cx, cy;
 716                 unsigned x, y;
 717
 718                 glyph = &font->glyphs[i];
 719
 720                 if(seq)
 721                         ci = i;
 722                 else
 723                         ci = glyph->code-first;
 724
 725                 cx = (ci%cpl)*cellw;
 726                 cy = (ci/cpl)*cellh;
 727
 728                 if(cellw>glyph->image.w)
 729                         cx += (cellw-glyph->image.w)/2;
 730                 cy += top-glyph->offset_y-glyph->image.h;
 731
 732                 glyph->x = cx;
 733                 glyph->y = cy;
 734
 735                 for(y=0; y<glyph->image.h; ++y) for(x=0; x<glyph->image.w; ++x)
 736                 {
 737                         if(cx+x>=font->image.w || cy+y>=font->image.h)
 738                                 continue;
 739                         font->image.data[cx+x+(cy+y)*font->image.w] = 255-glyph->image.data[x+y*glyph->image.w];
 740                 }
 741         }
 742
 743         return 0;
 744 }
 745
 746 int render_packed(Font *font, unsigned margin, unsigned padding)
 747 {
 748         unsigned i;
 749         size_t area = 0;
 750         char *used_glyphs;
 751         unsigned *used_pixels;
 752         unsigned cx = margin, cy;
 753         unsigned used_h = 0;
 754
 755         /* Compute the total area occupied by glyphs and padding. */
 756         for(i=0; i<font->n_glyphs; ++i)
 757         {
 758                 size_t a = area+(font->glyphs[i].image.w+padding)*(font->glyphs[i].image.h+padding);
 759                 if(a<area)
 760                 {
 761                         fprintf(stderr, "Overflow in counting total glyph area\n");
 762                         return -1;
 763                 }
 764                 area = a;
 765         }
 766
 767         /* Find an image size that's no higher than wide, allowing for some
 768         imperfections in the packing. */
 769         for(font->image.w=1;; font->image.w<<=1)
 770         {
 771                 if(font->image.w<=margin*2)
 772                         continue;
 773                 font->image.h = (area*5/4)/(font->image.w-margin*2)+margin*2;
 774                 if(font->image.h<=font->image.w)
 775                         break;
 776         }
 777         font->image.h = round_to_pot(font->image.h);
 778
 779         /* Allocate arrays for storing the image and keeping track of used pixels and
 780         glyphs.  Since glyphs are rectangular and the image is filled starting from
 781         the top, it's enough to track the number of used pixels at the top of each
 782         column. */
 783         font->image.data = (char *)alloc_image_data(font->image.w, font->image.h);
 784         if(!font->image.data)
 785                 return -1;
 786         memset(font->image.data, 255, font->image.w*font->image.h);
 787         used_pixels = (unsigned *)malloc(font->image.w*sizeof(unsigned));
 788         memset(used_pixels, 0, font->image.w*sizeof(unsigned));
 789         used_glyphs = (char *)malloc(font->n_glyphs);
 790         memset(used_glyphs, 0, font->n_glyphs);
 791
 792         for(cy=margin; cy+margin<font->image.h;)
 793         {
 794                 unsigned w;
 795                 unsigned x, y;
 796                 Glyph *glyph = NULL;
 797                 unsigned best_score = 0;
 798                 unsigned target_h = 0;
 799
 800                 /* Find the leftmost free pixel on this row.  Also record the lowest
 801                 extent of glyphs to the left of the free position. */
 802                 for(; (cx+margin<font->image.w && used_pixels[cx]>cy); ++cx)
 803                         if(used_pixels[cx]-cy-padding>target_h)
 804                                 target_h = used_pixels[cx]-cy-padding;
 805
 806                 if(cx+margin>=font->image.w)
 807                 {
 808                         cx = margin;
 809                         ++cy;
 810                         continue;
 811                 }
 812
 813                 /* Count the free pixel at this position. */
 814                 for(w=0; (cx+w+margin<font->image.w && used_pixels[cx+w]<=cy); ++w) ;
 815
 816                 /* Find a suitable glyph to put here. */
 817                 for(i=0; i<font->n_glyphs; ++i)
 818                 {
 819                         Glyph *g;
 820
 821                         g = &font->glyphs[i];
 822                         if(!used_glyphs[i] && g->image.w<=w)
 823                         {
 824                                 unsigned score;
 825
 826                                 /* Prefer glyphs that would reach exactly as low as the ones left
 827                                 of here.  This aims to create a straight edge at the bottom for
 828                                 lining up further glyphs. */
 829                                 score = g->image.h+padding;
 830                                 if(g->image.h==target_h)
 831                                         score *= g->image.w;
 832                                 else
 833                                         score += g->image.w;
 834
 835                                 if(score>best_score)
 836                                 {
 837                                         glyph = g;
 838                                         best_score = score;
 839                                 }
 840                         }
 841                 }
 842
 843                 if(!glyph)
 844                 {
 845                         cx += w;
 846                         continue;
 847                 }
 848
 849                 used_glyphs[glyph-font->glyphs] = 1;
 850                 glyph->x = cx;
 851                 glyph->y = cy;
 852
 853                 for(y=0; y<glyph->image.h; ++y) for(x=0; x<glyph->image.w; ++x)
 854                 {
 855                         if(cx+x>=font->image.w || cy+y>=font->image.h)
 856                                 continue;
 857                         font->image.data[cx+x+(cy+y)*font->image.w] = 255-glyph->image.data[x+y*glyph->image.w];
 858                 }
 859                 for(x=0; x<glyph->image.w+2*padding; ++x)
 860                 {
 861                         if(cx+x<padding || cx+x>=font->image.w+padding)
 862                                 continue;
 863                         if(used_pixels[cx+x-padding]<cy+glyph->image.h+padding)
 864                                 used_pixels[cx+x-padding] = cy+glyph->image.h+padding;
 865                 }
 866
 867                 if(cy+glyph->image.h+margin>used_h)
 868                         used_h = cy+glyph->image.h+margin;
 869         }
 870
 871         /* Trim the image to the actually used size, in case the original estimate
 872         was too pessimistic. */
 873         font->image.h = round_to_pot(used_h);
 874
 875         free(used_glyphs);
 876         free(used_pixels);
 877
 878         return 0;
 879 }
 880
 881 int save_defs(const char *fn, const Font *font)
 882 {
 883         FILE *out;
 884         unsigned i;
 885
 886         out = fopen(fn, "w");
 887         if(!out)
 888         {
 889                 fprintf(stderr, "Couldn't open %s\n",fn);
 890                 return -1;
 891         }
 892
 893         fprintf(out, "# Image/font info:\n");
 894         fprintf(out, "# width height size ascent descent\n");
 895         fprintf(out, "font %d %d %d %d %d\n", font->image.w, font->image.h, font->size, font->ascent, font->descent);
 896         fprintf(out, "\n# Glyph info:\n");
 897         fprintf(out, "# code x y width height offset_x offset_y advance\n");
 898         for(i=0; i<font->n_glyphs; ++i)
 899         {
 900                 const Glyph *g = &font->glyphs[i];
 901                 fprintf(out, "glyph %u %u %u %u %u %d %d %d\n", g->code, g->x, g->y, g->image.w, g->image.h, g->offset_x, g->offset_y, g->advance);
 902         }
 903         fprintf(out, "\n# Kerning info:\n");
 904         fprintf(out, "# left right distance\n");
 905         for(i=0; i<font->n_kerning; ++i)
 906         {
 907                 const Kerning *k = &font->kerning[i];
 908                 fprintf(out, "kern %u %u %d\n", k->left_code, k->right_code, k->distance);
 909         }
 910
 911         fclose(out);
 912
 913         return 0;
 914 }
 915
 916 int save_png(const char *fn, const Image *image, char alpha)
 917 {
 918         FILE *out;
 919         png_struct *pngs;
 920         png_info *pngi;
 921         png_byte **rows;
 922         unsigned i;
 923         png_byte *data2 = 0;
 924         int color;
 925
 926         if(!strcmp(fn, "-"))
 927                 out = stdout;
 928         else
 929         {
 930                 out = fopen(fn, "wb");
 931                 if(!out)
 932                 {
 933                         fprintf(stderr, "Couldn't open %s\n",fn);
 934                         return -1;
 935                 }
 936         }
 937
 938         pngs = png_create_write_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL);
 939         if(!pngs)
 940         {
 941                 fprintf(stderr, "Error writing PNG file\n");
 942                 return -1;
 943         }
 944         pngi = png_create_info_struct(pngs);
 945         if(!pngi)
 946         {
 947                 png_destroy_write_struct(&pngs, NULL);
 948                 fprintf(stderr, "Error writing PNG file\n");
 949                 return -1;
 950         }
 951
 952         png_init_io(pngs, out);
 953         rows = (png_byte **)malloc(image->h*sizeof(png_byte *));
 954         if(alpha)
 955         {
 956                 data2 = (png_byte *)alloc_image_data(image->w*2, image->h);
 957                 if(!data2)
 958                         return -1;
 959                 for(i=0; i<image->w*image->h; ++i)
 960                 {
 961                         data2[i*2] = 255;
 962                         data2[i*2+1] = 255-image->data[i];
 963                 }
 964                 for(i=0; i<image->h; ++i)
 965                         rows[i] = (png_byte *)(data2+i*image->w*2);
 966                 color = PNG_COLOR_TYPE_GRAY_ALPHA;
 967         }
 968         else
 969         {
 970                 for(i=0; i<image->h; ++i)
 971                         rows[i] = (png_byte *)(image->data+i*image->w);
 972                 color = PNG_COLOR_TYPE_GRAY;
 973         }
 974         png_set_IHDR(pngs, pngi, image->w, image->h, 8, color, PNG_INTERLACE_NONE, PNG_COMPRESSION_TYPE_DEFAULT, PNG_FILTER_TYPE_DEFAULT);
 975         png_set_rows(pngs, pngi, rows);
 976         png_write_png(pngs, pngi, PNG_TRANSFORM_IDENTITY, NULL);
 977         png_destroy_write_struct(&pngs, &pngi);
 978         free(rows);
 979         if(alpha)
 980                 free(data2);
 981
 982         if(verbose)
 983                 printf("Saved %dx%d PNG image to %s\n", image->w, image->h, fn);
 984
 985         fclose(out);
 986
 987         return 0;
 988 }