Prepare v2023.10
[platform/kernel/u-boot.git] / drivers / video / stb_truetype.h
1 // stb_truetype.h - v1.26 - public domain
2 // authored from 2009-2021 by Sean Barrett / RAD Game Tools
3 //
4 // =======================================================================
5 //
6 //    NO SECURITY GUARANTEE -- DO NOT USE THIS ON UNTRUSTED FONT FILES
7 //
8 // This library does no range checking of the offsets found in the file,
9 // meaning an attacker can use it to read arbitrary memory.
10 //
11 // =======================================================================
12 //
13 //   This library processes TrueType files:
14 //        parse files
15 //        extract glyph metrics
16 //        extract glyph shapes
17 //        render glyphs to one-channel bitmaps with antialiasing (box filter)
18 //        render glyphs to one-channel SDF bitmaps (signed-distance field/function)
19 //
20 //   Todo:
21 //        non-MS cmaps
22 //        crashproof on bad data
23 //        hinting? (no longer patented)
24 //        cleartype-style AA?
25 //        optimize: use simple memory allocator for intermediates
26 //        optimize: build edge-list directly from curves
27 //        optimize: rasterize directly from curves?
28 //
29 // ADDITIONAL CONTRIBUTORS
30 //
31 //   Mikko Mononen: compound shape support, more cmap formats
32 //   Tor Andersson: kerning, subpixel rendering
33 //   Dougall Johnson: OpenType / Type 2 font handling
34 //   Daniel Ribeiro Maciel: basic GPOS-based kerning
35 //
36 //   Misc other:
37 //       Ryan Gordon
38 //       Simon Glass
39 //       github:IntellectualKitty
40 //       Imanol Celaya
41 //       Daniel Ribeiro Maciel
42 //
43 //   Bug/warning reports/fixes:
44 //       "Zer" on mollyrocket       Fabian "ryg" Giesen   github:NiLuJe
45 //       Cass Everitt               Martins Mozeiko       github:aloucks
46 //       stoiko (Haemimont Games)   Cap Petschulat        github:oyvindjam
47 //       Brian Hook                 Omar Cornut           github:vassvik
48 //       Walter van Niftrik         Ryan Griege
49 //       David Gow                  Peter LaValle
50 //       David Given                Sergey Popov
51 //       Ivan-Assen Ivanov          Giumo X. Clanjor
52 //       Anthony Pesch              Higor Euripedes
53 //       Johan Duparc               Thomas Fields
54 //       Hou Qiming                 Derek Vinyard
55 //       Rob Loach                  Cort Stratton
56 //       Kenney Phillis Jr.         Brian Costabile
57 //       Ken Voskuil (kaesve)
58 //
59 // VERSION HISTORY
60 //
61 //   1.26 (2021-08-28) fix broken rasterizer
62 //   1.25 (2021-07-11) many fixes
63 //   1.24 (2020-02-05) fix warning
64 //   1.23 (2020-02-02) query SVG data for glyphs; query whole kerning table (but only kern not GPOS)
65 //   1.22 (2019-08-11) minimize missing-glyph duplication; fix kerning if both 'GPOS' and 'kern' are defined
66 //   1.21 (2019-02-25) fix warning
67 //   1.20 (2019-02-07) PackFontRange skips missing codepoints; GetScaleFontVMetrics()
68 //   1.19 (2018-02-11) GPOS kerning, STBTT_fmod
69 //   1.18 (2018-01-29) add missing function
70 //   1.17 (2017-07-23) make more arguments const; doc fix
71 //   1.16 (2017-07-12) SDF support
72 //   1.15 (2017-03-03) make more arguments const
73 //   1.14 (2017-01-16) num-fonts-in-TTC function
74 //   1.13 (2017-01-02) support OpenType fonts, certain Apple fonts
75 //   1.12 (2016-10-25) suppress warnings about casting away const with -Wcast-qual
76 //   1.11 (2016-04-02) fix unused-variable warning
77 //   1.10 (2016-04-02) user-defined fabs(); rare memory leak; remove duplicate typedef
78 //   1.09 (2016-01-16) warning fix; avoid crash on outofmem; use allocation userdata properly
79 //   1.08 (2015-09-13) document stbtt_Rasterize(); fixes for vertical & horizontal edges
80 //   1.07 (2015-08-01) allow PackFontRanges to accept arrays of sparse codepoints;
81 //                     variant PackFontRanges to pack and render in separate phases;
82 //                     fix stbtt_GetFontOFfsetForIndex (never worked for non-0 input?);
83 //                     fixed an assert() bug in the new rasterizer
84 //                     replace assert() with STBTT_assert() in new rasterizer
85 //
86 //   Full history can be found at the end of this file.
87 //
88 // LICENSE
89 //
90 //   See end of file for license information.
91 //
92 // USAGE
93 //
94 //   Include this file in whatever places need to refer to it. In ONE C/C++
95 //   file, write:
96 //      #define STB_TRUETYPE_IMPLEMENTATION
97 //   before the #include of this file. This expands out the actual
98 //   implementation into that C/C++ file.
99 //
100 //   To make the implementation private to the file that generates the implementation,
101 //      #define STBTT_STATIC
102 //
103 //   Simple 3D API (don't ship this, but it's fine for tools and quick start)
104 //           stbtt_BakeFontBitmap()               -- bake a font to a bitmap for use as texture
105 //           stbtt_GetBakedQuad()                 -- compute quad to draw for a given char
106 //
107 //   Improved 3D API (more shippable):
108 //           #include "stb_rect_pack.h"           -- optional, but you really want it
109 //           stbtt_PackBegin()
110 //           stbtt_PackSetOversampling()          -- for improved quality on small fonts
111 //           stbtt_PackFontRanges()               -- pack and renders
112 //           stbtt_PackEnd()
113 //           stbtt_GetPackedQuad()
114 //
115 //   "Load" a font file from a memory buffer (you have to keep the buffer loaded)
116 //           stbtt_InitFont()
117 //           stbtt_GetFontOffsetForIndex()        -- indexing for TTC font collections
118 //           stbtt_GetNumberOfFonts()             -- number of fonts for TTC font collections
119 //
120 //   Render a unicode codepoint to a bitmap
121 //           stbtt_GetCodepointBitmap()           -- allocates and returns a bitmap
122 //           stbtt_MakeCodepointBitmap()          -- renders into bitmap you provide
123 //           stbtt_GetCodepointBitmapBox()        -- how big the bitmap must be
124 //
125 //   Character advance/positioning
126 //           stbtt_GetCodepointHMetrics()
127 //           stbtt_GetFontVMetrics()
128 //           stbtt_GetFontVMetricsOS2()
129 //           stbtt_GetCodepointKernAdvance()
130 //
131 //   Starting with version 1.06, the rasterizer was replaced with a new,
132 //   faster and generally-more-precise rasterizer. The new rasterizer more
133 //   accurately measures pixel coverage for anti-aliasing, except in the case
134 //   where multiple shapes overlap, in which case it overestimates the AA pixel
135 //   coverage. Thus, anti-aliasing of intersecting shapes may look wrong. If
136 //   this turns out to be a problem, you can re-enable the old rasterizer with
137 //        #define STBTT_RASTERIZER_VERSION 1
138 //   which will incur about a 15% speed hit.
139 //
140 // ADDITIONAL DOCUMENTATION
141 //
142 //   Immediately after this block comment are a series of sample programs.
143 //
144 //   After the sample programs is the "header file" section. This section
145 //   includes documentation for each API function.
146 //
147 //   Some important concepts to understand to use this library:
148 //
149 //      Codepoint
150 //         Characters are defined by unicode codepoints, e.g. 65 is
151 //         uppercase A, 231 is lowercase c with a cedilla, 0x7e30 is
152 //         the hiragana for "ma".
153 //
154 //      Glyph
155 //         A visual character shape (every codepoint is rendered as
156 //         some glyph)
157 //
158 //      Glyph index
159 //         A font-specific integer ID representing a glyph
160 //
161 //      Baseline
162 //         Glyph shapes are defined relative to a baseline, which is the
163 //         bottom of uppercase characters. Characters extend both above
164 //         and below the baseline.
165 //
166 //      Current Point
167 //         As you draw text to the screen, you keep track of a "current point"
168 //         which is the origin of each character. The current point's vertical
169 //         position is the baseline. Even "baked fonts" use this model.
170 //
171 //      Vertical Font Metrics
172 //         The vertical qualities of the font, used to vertically position
173 //         and space the characters. See docs for stbtt_GetFontVMetrics.
174 //
175 //      Font Size in Pixels or Points
176 //         The preferred interface for specifying font sizes in stb_truetype
177 //         is to specify how tall the font's vertical extent should be in pixels.
178 //         If that sounds good enough, skip the next paragraph.
179 //
180 //         Most font APIs instead use "points", which are a common typographic
181 //         measurement for describing font size, defined as 72 points per inch.
182 //         stb_truetype provides a point API for compatibility. However, true
183 //         "per inch" conventions don't make much sense on computer displays
184 //         since different monitors have different number of pixels per
185 //         inch. For example, Windows traditionally uses a convention that
186 //         there are 96 pixels per inch, thus making 'inch' measurements have
187 //         nothing to do with inches, and thus effectively defining a point to
188 //         be 1.333 pixels. Additionally, the TrueType font data provides
189 //         an explicit scale factor to scale a given font's glyphs to points,
190 //         but the author has observed that this scale factor is often wrong
191 //         for non-commercial fonts, thus making fonts scaled in points
192 //         according to the TrueType spec incoherently sized in practice.
193 //
194 // DETAILED USAGE:
195 //
196 //  Scale:
197 //    Select how high you want the font to be, in points or pixels.
198 //    Call ScaleForPixelHeight or ScaleForMappingEmToPixels to compute
199 //    a scale factor SF that will be used by all other functions.
200 //
201 //  Baseline:
202 //    You need to select a y-coordinate that is the baseline of where
203 //    your text will appear. Call GetFontBoundingBox to get the baseline-relative
204 //    bounding box for all characters. SF*-y0 will be the distance in pixels
205 //    that the worst-case character could extend above the baseline, so if
206 //    you want the top edge of characters to appear at the top of the
207 //    screen where y=0, then you would set the baseline to SF*-y0.
208 //
209 //  Current point:
210 //    Set the current point where the first character will appear. The
211 //    first character could extend left of the current point; this is font
212 //    dependent. You can either choose a current point that is the leftmost
213 //    point and hope, or add some padding, or check the bounding box or
214 //    left-side-bearing of the first character to be displayed and set
215 //    the current point based on that.
216 //
217 //  Displaying a character:
218 //    Compute the bounding box of the character. It will contain signed values
219 //    relative to <current_point, baseline>. I.e. if it returns x0,y0,x1,y1,
220 //    then the character should be displayed in the rectangle from
221 //    <current_point+SF*x0, baseline+SF*y0> to <current_point+SF*x1,baseline+SF*y1).
222 //
223 //  Advancing for the next character:
224 //    Call GlyphHMetrics, and compute 'current_point += SF * advance'.
225 //
226 //
227 // ADVANCED USAGE
228 //
229 //   Quality:
230 //
231 //    - Use the functions with Subpixel at the end to allow your characters
232 //      to have subpixel positioning. Since the font is anti-aliased, not
233 //      hinted, this is very import for quality. (This is not possible with
234 //      baked fonts.)
235 //
236 //    - Kerning is now supported, and if you're supporting subpixel rendering
237 //      then kerning is worth using to give your text a polished look.
238 //
239 //   Performance:
240 //
241 //    - Convert Unicode codepoints to glyph indexes and operate on the glyphs;
242 //      if you don't do this, stb_truetype is forced to do the conversion on
243 //      every call.
244 //
245 //    - There are a lot of memory allocations. We should modify it to take
246 //      a temp buffer and allocate from the temp buffer (without freeing),
247 //      should help performance a lot.
248 //
249 // NOTES
250 //
251 //   The system uses the raw data found in the .ttf file without changing it
252 //   and without building auxiliary data structures. This is a bit inefficient
253 //   on little-endian systems (the data is big-endian), but assuming you're
254 //   caching the bitmaps or glyph shapes this shouldn't be a big deal.
255 //
256 //   It appears to be very hard to programmatically determine what font a
257 //   given file is in a general way. I provide an API for this, but I don't
258 //   recommend it.
259 //
260 //
261 // PERFORMANCE MEASUREMENTS FOR 1.06:
262 //
263 //                      32-bit     64-bit
264 //   Previous release:  8.83 s     7.68 s
265 //   Pool allocations:  7.72 s     6.34 s
266 //   Inline sort     :  6.54 s     5.65 s
267 //   New rasterizer  :  5.63 s     5.00 s
268
269 //////////////////////////////////////////////////////////////////////////////
270 //////////////////////////////////////////////////////////////////////////////
271 ////
272 ////  SAMPLE PROGRAMS
273 ////
274 //
275 //  Incomplete text-in-3d-api example, which draws quads properly aligned to be lossless.
276 //  See "tests/truetype_demo_win32.c" for a complete version.
277 #if 0
278 #define STB_TRUETYPE_IMPLEMENTATION  // force following include to generate implementation
279 #include "stb_truetype.h"
280
281 unsigned char ttf_buffer[1<<20];
282 unsigned char temp_bitmap[512*512];
283
284 stbtt_bakedchar cdata[96]; // ASCII 32..126 is 95 glyphs
285 GLuint ftex;
286
287 void my_stbtt_initfont(void)
288 {
289    fread(ttf_buffer, 1, 1<<20, fopen("c:/windows/fonts/times.ttf", "rb"));
290    stbtt_BakeFontBitmap(ttf_buffer,0, 32.0, temp_bitmap,512,512, 32,96, cdata); // no guarantee this fits!
291    // can free ttf_buffer at this point
292    glGenTextures(1, &ftex);
293    glBindTexture(GL_TEXTURE_2D, ftex);
294    glTexImage2D(GL_TEXTURE_2D, 0, GL_ALPHA, 512,512, 0, GL_ALPHA, GL_UNSIGNED_BYTE, temp_bitmap);
295    // can free temp_bitmap at this point
296    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
297 }
298
299 void my_stbtt_print(float x, float y, char *text)
300 {
301    // assume orthographic projection with units = screen pixels, origin at top left
302    glEnable(GL_BLEND);
303    glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
304    glEnable(GL_TEXTURE_2D);
305    glBindTexture(GL_TEXTURE_2D, ftex);
306    glBegin(GL_QUADS);
307    while (*text) {
308       if (*text >= 32 && *text < 128) {
309          stbtt_aligned_quad q;
310          stbtt_GetBakedQuad(cdata, 512,512, *text-32, &x,&y,&q,1);//1=opengl & d3d10+,0=d3d9
311          glTexCoord2f(q.s0,q.t0); glVertex2f(q.x0,q.y0);
312          glTexCoord2f(q.s1,q.t0); glVertex2f(q.x1,q.y0);
313          glTexCoord2f(q.s1,q.t1); glVertex2f(q.x1,q.y1);
314          glTexCoord2f(q.s0,q.t1); glVertex2f(q.x0,q.y1);
315       }
316       ++text;
317    }
318    glEnd();
319 }
320 #endif
321 //
322 //
323 //////////////////////////////////////////////////////////////////////////////
324 //
325 // Complete program (this compiles): get a single bitmap, print as ASCII art
326 //
327 #if 0
328 #include <stdio.h>
329 #define STB_TRUETYPE_IMPLEMENTATION  // force following include to generate implementation
330 #include "stb_truetype.h"
331
332 char ttf_buffer[1<<25];
333
334 int main(int argc, char **argv)
335 {
336    stbtt_fontinfo font;
337    unsigned char *bitmap;
338    int w,h,i,j,c = (argc > 1 ? atoi(argv[1]) : 'a'), s = (argc > 2 ? atoi(argv[2]) : 20);
339
340    fread(ttf_buffer, 1, 1<<25, fopen(argc > 3 ? argv[3] : "c:/windows/fonts/arialbd.ttf", "rb"));
341
342    stbtt_InitFont(&font, ttf_buffer, stbtt_GetFontOffsetForIndex(ttf_buffer,0));
343    bitmap = stbtt_GetCodepointBitmap(&font, 0,stbtt_ScaleForPixelHeight(&font, s), c, &w, &h, 0,0);
344
345    for (j=0; j < h; ++j) {
346       for (i=0; i < w; ++i)
347          putchar(" .:ioVM@"[bitmap[j*w+i]>>5]);
348       putchar('\n');
349    }
350    return 0;
351 }
352 #endif
353 //
354 // Output:
355 //
356 //     .ii.
357 //    @@@@@@.
358 //   V@Mio@@o
359 //   :i.  V@V
360 //     :oM@@M
361 //   :@@@MM@M
362 //   @@o  o@M
363 //  :@@.  M@M
364 //   @@@o@@@@
365 //   :M@@V:@@.
366 //
367 //////////////////////////////////////////////////////////////////////////////
368 //
369 // Complete program: print "Hello World!" banner, with bugs
370 //
371 #if 0
372 char buffer[24<<20];
373 unsigned char screen[20][79];
374
375 int main(int arg, char **argv)
376 {
377    stbtt_fontinfo font;
378    int i,j,ascent,baseline,ch=0;
379    float scale, xpos=2; // leave a little padding in case the character extends left
380    char *text = "Heljo World!"; // intentionally misspelled to show 'lj' brokenness
381
382    fread(buffer, 1, 1000000, fopen("c:/windows/fonts/arialbd.ttf", "rb"));
383    stbtt_InitFont(&font, buffer, 0);
384
385    scale = stbtt_ScaleForPixelHeight(&font, 15);
386    stbtt_GetFontVMetrics(&font, &ascent,0,0);
387    baseline = (int) (ascent*scale);
388
389    while (text[ch]) {
390       int advance,lsb,x0,y0,x1,y1;
391       float x_shift = xpos - (float) floor(xpos);
392       stbtt_GetCodepointHMetrics(&font, text[ch], &advance, &lsb);
393       stbtt_GetCodepointBitmapBoxSubpixel(&font, text[ch], scale,scale,x_shift,0, &x0,&y0,&x1,&y1);
394       stbtt_MakeCodepointBitmapSubpixel(&font, &screen[baseline + y0][(int) xpos + x0], x1-x0,y1-y0, 79, scale,scale,x_shift,0, text[ch]);
395       // note that this stomps the old data, so where character boxes overlap (e.g. 'lj') it's wrong
396       // because this API is really for baking character bitmaps into textures. if you want to render
397       // a sequence of characters, you really need to render each bitmap to a temp buffer, then
398       // "alpha blend" that into the working buffer
399       xpos += (advance * scale);
400       if (text[ch+1])
401          xpos += scale*stbtt_GetCodepointKernAdvance(&font, text[ch],text[ch+1]);
402       ++ch;
403    }
404
405    for (j=0; j < 20; ++j) {
406       for (i=0; i < 78; ++i)
407          putchar(" .:ioVM@"[screen[j][i]>>5]);
408       putchar('\n');
409    }
410
411    return 0;
412 }
413 #endif
414
415
416 //////////////////////////////////////////////////////////////////////////////
417 //////////////////////////////////////////////////////////////////////////////
418 ////
419 ////   INTEGRATION WITH YOUR CODEBASE
420 ////
421 ////   The following sections allow you to supply alternate definitions
422 ////   of C library functions used by stb_truetype, e.g. if you don't
423 ////   link with the C runtime library.
424
425 #ifdef STB_TRUETYPE_IMPLEMENTATION
426    // #define your own (u)stbtt_int8/16/32 before including to override this
427    #ifndef stbtt_uint8
428    typedef unsigned char   stbtt_uint8;
429    typedef signed   char   stbtt_int8;
430    typedef unsigned short  stbtt_uint16;
431    typedef signed   short  stbtt_int16;
432    typedef unsigned int    stbtt_uint32;
433    typedef signed   int    stbtt_int32;
434    #endif
435
436    typedef char stbtt__check_size32[sizeof(stbtt_int32)==4 ? 1 : -1];
437    typedef char stbtt__check_size16[sizeof(stbtt_int16)==2 ? 1 : -1];
438
439    // e.g. #define your own STBTT_ifloor/STBTT_iceil() to avoid math.h
440    #ifndef STBTT_ifloor
441    #include <math.h>
442    #define STBTT_ifloor(x)   ((int) floor(x))
443    #define STBTT_iceil(x)    ((int) ceil(x))
444    #endif
445
446    #ifndef STBTT_sqrt
447    #include <math.h>
448    #define STBTT_sqrt(x)      sqrt(x)
449    #define STBTT_pow(x,y)     pow(x,y)
450    #endif
451
452    #ifndef STBTT_fmod
453    #include <math.h>
454    #define STBTT_fmod(x,y)    fmod(x,y)
455    #endif
456
457    #ifndef STBTT_cos
458    #include <math.h>
459    #define STBTT_cos(x)       cos(x)
460    #define STBTT_acos(x)      acos(x)
461    #endif
462
463    #ifndef STBTT_fabs
464    #include <math.h>
465    #define STBTT_fabs(x)      fabs(x)
466    #endif
467
468    // #define your own functions "STBTT_malloc" / "STBTT_free" to avoid malloc.h
469    #ifndef STBTT_malloc
470    #include <stdlib.h>
471    #define STBTT_malloc(x,u)  ((void)(u),malloc(x))
472    #define STBTT_free(x,u)    ((void)(u),free(x))
473    #endif
474
475    #ifndef STBTT_assert
476    #include <assert.h>
477    #define STBTT_assert(x)    assert(x)
478    #endif
479
480    #ifndef STBTT_strlen
481    #include <string.h>
482    #define STBTT_strlen(x)    strlen(x)
483    #endif
484
485    #ifndef STBTT_memcpy
486    #include <memory.h>
487    #define STBTT_memcpy       memcpy
488    #define STBTT_memset       memset
489    #endif
490 #endif
491
492 ///////////////////////////////////////////////////////////////////////////////
493 ///////////////////////////////////////////////////////////////////////////////
494 ////
495 ////   INTERFACE
496 ////
497 ////
498
499 #ifndef __STB_INCLUDE_STB_TRUETYPE_H__
500 #define __STB_INCLUDE_STB_TRUETYPE_H__
501
502 #ifdef STBTT_STATIC
503 #define STBTT_DEF static
504 #else
505 #define STBTT_DEF extern
506 #endif
507
508 #ifdef __cplusplus
509 extern "C" {
510 #endif
511
512 // private structure
513 typedef struct
514 {
515    unsigned char *data;
516    int cursor;
517    int size;
518 } stbtt__buf;
519
520 //////////////////////////////////////////////////////////////////////////////
521 //
522 // TEXTURE BAKING API
523 //
524 // If you use this API, you only have to call two functions ever.
525 //
526
527 typedef struct
528 {
529    unsigned short x0,y0,x1,y1; // coordinates of bbox in bitmap
530    float xoff,yoff,xadvance;
531 } stbtt_bakedchar;
532
533 STBTT_DEF int stbtt_BakeFontBitmap(const unsigned char *data, int offset,  // font location (use offset=0 for plain .ttf)
534                                 float pixel_height,                     // height of font in pixels
535                                 unsigned char *pixels, int pw, int ph,  // bitmap to be filled in
536                                 int first_char, int num_chars,          // characters to bake
537                                 stbtt_bakedchar *chardata);             // you allocate this, it's num_chars long
538 // if return is positive, the first unused row of the bitmap
539 // if return is negative, returns the negative of the number of characters that fit
540 // if return is 0, no characters fit and no rows were used
541 // This uses a very crappy packing.
542
543 typedef struct
544 {
545    float x0,y0,s0,t0; // top-left
546    float x1,y1,s1,t1; // bottom-right
547 } stbtt_aligned_quad;
548
549 STBTT_DEF void stbtt_GetBakedQuad(const stbtt_bakedchar *chardata, int pw, int ph,  // same data as above
550                                int char_index,             // character to display
551                                float *xpos, float *ypos,   // pointers to current position in screen pixel space
552                                stbtt_aligned_quad *q,      // output: quad to draw
553                                int opengl_fillrule);       // true if opengl fill rule; false if DX9 or earlier
554 // Call GetBakedQuad with char_index = 'character - first_char', and it
555 // creates the quad you need to draw and advances the current position.
556 //
557 // The coordinate system used assumes y increases downwards.
558 //
559 // Characters will extend both above and below the current position;
560 // see discussion of "BASELINE" above.
561 //
562 // It's inefficient; you might want to c&p it and optimize it.
563
564 STBTT_DEF void stbtt_GetScaledFontVMetrics(const unsigned char *fontdata, int index, float size, float *ascent, float *descent, float *lineGap);
565 // Query the font vertical metrics without having to create a font first.
566
567
568 //////////////////////////////////////////////////////////////////////////////
569 //
570 // NEW TEXTURE BAKING API
571 //
572 // This provides options for packing multiple fonts into one atlas, not
573 // perfectly but better than nothing.
574
575 typedef struct
576 {
577    unsigned short x0,y0,x1,y1; // coordinates of bbox in bitmap
578    float xoff,yoff,xadvance;
579    float xoff2,yoff2;
580 } stbtt_packedchar;
581
582 typedef struct stbtt_pack_context stbtt_pack_context;
583 typedef struct stbtt_fontinfo stbtt_fontinfo;
584 #ifndef STB_RECT_PACK_VERSION
585 typedef struct stbrp_rect stbrp_rect;
586 #endif
587
588 STBTT_DEF int  stbtt_PackBegin(stbtt_pack_context *spc, unsigned char *pixels, int width, int height, int stride_in_bytes, int padding, void *alloc_context);
589 // Initializes a packing context stored in the passed-in stbtt_pack_context.
590 // Future calls using this context will pack characters into the bitmap passed
591 // in here: a 1-channel bitmap that is width * height. stride_in_bytes is
592 // the distance from one row to the next (or 0 to mean they are packed tightly
593 // together). "padding" is the amount of padding to leave between each
594 // character (normally you want '1' for bitmaps you'll use as textures with
595 // bilinear filtering).
596 //
597 // Returns 0 on failure, 1 on success.
598
599 STBTT_DEF void stbtt_PackEnd  (stbtt_pack_context *spc);
600 // Cleans up the packing context and frees all memory.
601
602 #define STBTT_POINT_SIZE(x)   (-(x))
603
604 STBTT_DEF int  stbtt_PackFontRange(stbtt_pack_context *spc, const unsigned char *fontdata, int font_index, float font_size,
605                                 int first_unicode_char_in_range, int num_chars_in_range, stbtt_packedchar *chardata_for_range);
606 // Creates character bitmaps from the font_index'th font found in fontdata (use
607 // font_index=0 if you don't know what that is). It creates num_chars_in_range
608 // bitmaps for characters with unicode values starting at first_unicode_char_in_range
609 // and increasing. Data for how to render them is stored in chardata_for_range;
610 // pass these to stbtt_GetPackedQuad to get back renderable quads.
611 //
612 // font_size is the full height of the character from ascender to descender,
613 // as computed by stbtt_ScaleForPixelHeight. To use a point size as computed
614 // by stbtt_ScaleForMappingEmToPixels, wrap the point size in STBTT_POINT_SIZE()
615 // and pass that result as 'font_size':
616 //       ...,                  20 , ... // font max minus min y is 20 pixels tall
617 //       ..., STBTT_POINT_SIZE(20), ... // 'M' is 20 pixels tall
618
619 typedef struct
620 {
621    float font_size;
622    int first_unicode_codepoint_in_range;  // if non-zero, then the chars are continuous, and this is the first codepoint
623    int *array_of_unicode_codepoints;       // if non-zero, then this is an array of unicode codepoints
624    int num_chars;
625    stbtt_packedchar *chardata_for_range; // output
626    unsigned char h_oversample, v_oversample; // don't set these, they're used internally
627 } stbtt_pack_range;
628
629 STBTT_DEF int  stbtt_PackFontRanges(stbtt_pack_context *spc, const unsigned char *fontdata, int font_index, stbtt_pack_range *ranges, int num_ranges);
630 // Creates character bitmaps from multiple ranges of characters stored in
631 // ranges. This will usually create a better-packed bitmap than multiple
632 // calls to stbtt_PackFontRange. Note that you can call this multiple
633 // times within a single PackBegin/PackEnd.
634
635 STBTT_DEF void stbtt_PackSetOversampling(stbtt_pack_context *spc, unsigned int h_oversample, unsigned int v_oversample);
636 // Oversampling a font increases the quality by allowing higher-quality subpixel
637 // positioning, and is especially valuable at smaller text sizes.
638 //
639 // This function sets the amount of oversampling for all following calls to
640 // stbtt_PackFontRange(s) or stbtt_PackFontRangesGatherRects for a given
641 // pack context. The default (no oversampling) is achieved by h_oversample=1
642 // and v_oversample=1. The total number of pixels required is
643 // h_oversample*v_oversample larger than the default; for example, 2x2
644 // oversampling requires 4x the storage of 1x1. For best results, render
645 // oversampled textures with bilinear filtering. Look at the readme in
646 // stb/tests/oversample for information about oversampled fonts
647 //
648 // To use with PackFontRangesGather etc., you must set it before calls
649 // call to PackFontRangesGatherRects.
650
651 STBTT_DEF void stbtt_PackSetSkipMissingCodepoints(stbtt_pack_context *spc, int skip);
652 // If skip != 0, this tells stb_truetype to skip any codepoints for which
653 // there is no corresponding glyph. If skip=0, which is the default, then
654 // codepoints without a glyph recived the font's "missing character" glyph,
655 // typically an empty box by convention.
656
657 STBTT_DEF void stbtt_GetPackedQuad(const stbtt_packedchar *chardata, int pw, int ph,  // same data as above
658                                int char_index,             // character to display
659                                float *xpos, float *ypos,   // pointers to current position in screen pixel space
660                                stbtt_aligned_quad *q,      // output: quad to draw
661                                int align_to_integer);
662
663 STBTT_DEF int  stbtt_PackFontRangesGatherRects(stbtt_pack_context *spc, const stbtt_fontinfo *info, stbtt_pack_range *ranges, int num_ranges, stbrp_rect *rects);
664 STBTT_DEF void stbtt_PackFontRangesPackRects(stbtt_pack_context *spc, stbrp_rect *rects, int num_rects);
665 STBTT_DEF int  stbtt_PackFontRangesRenderIntoRects(stbtt_pack_context *spc, const stbtt_fontinfo *info, stbtt_pack_range *ranges, int num_ranges, stbrp_rect *rects);
666 // Calling these functions in sequence is roughly equivalent to calling
667 // stbtt_PackFontRanges(). If you more control over the packing of multiple
668 // fonts, or if you want to pack custom data into a font texture, take a look
669 // at the source to of stbtt_PackFontRanges() and create a custom version
670 // using these functions, e.g. call GatherRects multiple times,
671 // building up a single array of rects, then call PackRects once,
672 // then call RenderIntoRects repeatedly. This may result in a
673 // better packing than calling PackFontRanges multiple times
674 // (or it may not).
675
676 // this is an opaque structure that you shouldn't mess with which holds
677 // all the context needed from PackBegin to PackEnd.
678 struct stbtt_pack_context {
679    void *user_allocator_context;
680    void *pack_info;
681    int   width;
682    int   height;
683    int   stride_in_bytes;
684    int   padding;
685    int   skip_missing;
686    unsigned int   h_oversample, v_oversample;
687    unsigned char *pixels;
688    void  *nodes;
689 };
690
691 //////////////////////////////////////////////////////////////////////////////
692 //
693 // FONT LOADING
694 //
695 //
696
697 STBTT_DEF int stbtt_GetNumberOfFonts(const unsigned char *data);
698 // This function will determine the number of fonts in a font file.  TrueType
699 // collection (.ttc) files may contain multiple fonts, while TrueType font
700 // (.ttf) files only contain one font. The number of fonts can be used for
701 // indexing with the previous function where the index is between zero and one
702 // less than the total fonts. If an error occurs, -1 is returned.
703
704 STBTT_DEF int stbtt_GetFontOffsetForIndex(const unsigned char *data, int index);
705 // Each .ttf/.ttc file may have more than one font. Each font has a sequential
706 // index number starting from 0. Call this function to get the font offset for
707 // a given index; it returns -1 if the index is out of range. A regular .ttf
708 // file will only define one font and it always be at offset 0, so it will
709 // return '0' for index 0, and -1 for all other indices.
710
711 // The following structure is defined publicly so you can declare one on
712 // the stack or as a global or etc, but you should treat it as opaque.
713 struct stbtt_fontinfo
714 {
715    void           * userdata;
716    unsigned char  * data;              // pointer to .ttf file
717    int              fontstart;         // offset of start of font
718
719    int numGlyphs;                     // number of glyphs, needed for range checking
720
721    int loca,head,glyf,hhea,hmtx,kern,gpos,svg; // table locations as offset from start of .ttf
722    int index_map;                     // a cmap mapping for our chosen character encoding
723    int indexToLocFormat;              // format needed to map from glyph index to glyph
724
725    stbtt__buf cff;                    // cff font data
726    stbtt__buf charstrings;            // the charstring index
727    stbtt__buf gsubrs;                 // global charstring subroutines index
728    stbtt__buf subrs;                  // private charstring subroutines index
729    stbtt__buf fontdicts;              // array of font dicts
730    stbtt__buf fdselect;               // map from glyph to fontdict
731 };
732
733 STBTT_DEF int stbtt_InitFont(stbtt_fontinfo *info, const unsigned char *data, int offset);
734 // Given an offset into the file that defines a font, this function builds
735 // the necessary cached info for the rest of the system. You must allocate
736 // the stbtt_fontinfo yourself, and stbtt_InitFont will fill it out. You don't
737 // need to do anything special to free it, because the contents are pure
738 // value data with no additional data structures. Returns 0 on failure.
739
740
741 //////////////////////////////////////////////////////////////////////////////
742 //
743 // CHARACTER TO GLYPH-INDEX CONVERSIOn
744
745 STBTT_DEF int stbtt_FindGlyphIndex(const stbtt_fontinfo *info, int unicode_codepoint);
746 // If you're going to perform multiple operations on the same character
747 // and you want a speed-up, call this function with the character you're
748 // going to process, then use glyph-based functions instead of the
749 // codepoint-based functions.
750 // Returns 0 if the character codepoint is not defined in the font.
751
752
753 //////////////////////////////////////////////////////////////////////////////
754 //
755 // CHARACTER PROPERTIES
756 //
757
758 STBTT_DEF float stbtt_ScaleForPixelHeight(const stbtt_fontinfo *info, float pixels);
759 // computes a scale factor to produce a font whose "height" is 'pixels' tall.
760 // Height is measured as the distance from the highest ascender to the lowest
761 // descender; in other words, it's equivalent to calling stbtt_GetFontVMetrics
762 // and computing:
763 //       scale = pixels / (ascent - descent)
764 // so if you prefer to measure height by the ascent only, use a similar calculation.
765
766 STBTT_DEF float stbtt_ScaleForMappingEmToPixels(const stbtt_fontinfo *info, float pixels);
767 // computes a scale factor to produce a font whose EM size is mapped to
768 // 'pixels' tall. This is probably what traditional APIs compute, but
769 // I'm not positive.
770
771 STBTT_DEF void stbtt_GetFontVMetrics(const stbtt_fontinfo *info, int *ascent, int *descent, int *lineGap);
772 // ascent is the coordinate above the baseline the font extends; descent
773 // is the coordinate below the baseline the font extends (i.e. it is typically negative)
774 // lineGap is the spacing between one row's descent and the next row's ascent...
775 // so you should advance the vertical position by "*ascent - *descent + *lineGap"
776 //   these are expressed in unscaled coordinates, so you must multiply by
777 //   the scale factor for a given size
778
779 STBTT_DEF int  stbtt_GetFontVMetricsOS2(const stbtt_fontinfo *info, int *typoAscent, int *typoDescent, int *typoLineGap);
780 // analogous to GetFontVMetrics, but returns the "typographic" values from the OS/2
781 // table (specific to MS/Windows TTF files).
782 //
783 // Returns 1 on success (table present), 0 on failure.
784
785 STBTT_DEF void stbtt_GetFontBoundingBox(const stbtt_fontinfo *info, int *x0, int *y0, int *x1, int *y1);
786 // the bounding box around all possible characters
787
788 STBTT_DEF void stbtt_GetCodepointHMetrics(const stbtt_fontinfo *info, int codepoint, int *advanceWidth, int *leftSideBearing);
789 // leftSideBearing is the offset from the current horizontal position to the left edge of the character
790 // advanceWidth is the offset from the current horizontal position to the next horizontal position
791 //   these are expressed in unscaled coordinates
792
793 STBTT_DEF int  stbtt_GetCodepointKernAdvance(const stbtt_fontinfo *info, int ch1, int ch2);
794 // an additional amount to add to the 'advance' value between ch1 and ch2
795
796 STBTT_DEF int stbtt_GetCodepointBox(const stbtt_fontinfo *info, int codepoint, int *x0, int *y0, int *x1, int *y1);
797 // Gets the bounding box of the visible part of the glyph, in unscaled coordinates
798
799 STBTT_DEF void stbtt_GetGlyphHMetrics(const stbtt_fontinfo *info, int glyph_index, int *advanceWidth, int *leftSideBearing);
800 STBTT_DEF int  stbtt_GetGlyphKernAdvance(const stbtt_fontinfo *info, int glyph1, int glyph2);
801 STBTT_DEF int  stbtt_GetGlyphBox(const stbtt_fontinfo *info, int glyph_index, int *x0, int *y0, int *x1, int *y1);
802 // as above, but takes one or more glyph indices for greater efficiency
803
804 typedef struct stbtt_kerningentry
805 {
806    int glyph1; // use stbtt_FindGlyphIndex
807    int glyph2;
808    int advance;
809 } stbtt_kerningentry;
810
811 STBTT_DEF int  stbtt_GetKerningTableLength(const stbtt_fontinfo *info);
812 STBTT_DEF int  stbtt_GetKerningTable(const stbtt_fontinfo *info, stbtt_kerningentry* table, int table_length);
813 // Retrieves a complete list of all of the kerning pairs provided by the font
814 // stbtt_GetKerningTable never writes more than table_length entries and returns how many entries it did write.
815 // The table will be sorted by (a.glyph1 == b.glyph1)?(a.glyph2 < b.glyph2):(a.glyph1 < b.glyph1)
816
817 //////////////////////////////////////////////////////////////////////////////
818 //
819 // GLYPH SHAPES (you probably don't need these, but they have to go before
820 // the bitmaps for C declaration-order reasons)
821 //
822
823 #ifndef STBTT_vmove // you can predefine these to use different values (but why?)
824    enum {
825       STBTT_vmove=1,
826       STBTT_vline,
827       STBTT_vcurve,
828       STBTT_vcubic
829    };
830 #endif
831
832 #ifndef stbtt_vertex // you can predefine this to use different values
833                    // (we share this with other code at RAD)
834    #define stbtt_vertex_type short // can't use stbtt_int16 because that's not visible in the header file
835    typedef struct
836    {
837       stbtt_vertex_type x,y,cx,cy,cx1,cy1;
838       unsigned char type,padding;
839    } stbtt_vertex;
840 #endif
841
842 STBTT_DEF int stbtt_IsGlyphEmpty(const stbtt_fontinfo *info, int glyph_index);
843 // returns non-zero if nothing is drawn for this glyph
844
845 STBTT_DEF int stbtt_GetCodepointShape(const stbtt_fontinfo *info, int unicode_codepoint, stbtt_vertex **vertices);
846 STBTT_DEF int stbtt_GetGlyphShape(const stbtt_fontinfo *info, int glyph_index, stbtt_vertex **vertices);
847 // returns # of vertices and fills *vertices with the pointer to them
848 //   these are expressed in "unscaled" coordinates
849 //
850 // The shape is a series of contours. Each one starts with
851 // a STBTT_moveto, then consists of a series of mixed
852 // STBTT_lineto and STBTT_curveto segments. A lineto
853 // draws a line from previous endpoint to its x,y; a curveto
854 // draws a quadratic bezier from previous endpoint to
855 // its x,y, using cx,cy as the bezier control point.
856
857 STBTT_DEF void stbtt_FreeShape(const stbtt_fontinfo *info, stbtt_vertex *vertices);
858 // frees the data allocated above
859
860 STBTT_DEF unsigned char *stbtt_FindSVGDoc(const stbtt_fontinfo *info, int gl);
861 STBTT_DEF int stbtt_GetCodepointSVG(const stbtt_fontinfo *info, int unicode_codepoint, const char **svg);
862 STBTT_DEF int stbtt_GetGlyphSVG(const stbtt_fontinfo *info, int gl, const char **svg);
863 // fills svg with the character's SVG data.
864 // returns data size or 0 if SVG not found.
865
866 //////////////////////////////////////////////////////////////////////////////
867 //
868 // BITMAP RENDERING
869 //
870
871 STBTT_DEF void stbtt_FreeBitmap(unsigned char *bitmap, void *userdata);
872 // frees the bitmap allocated below
873
874 STBTT_DEF unsigned char *stbtt_GetCodepointBitmap(const stbtt_fontinfo *info, float scale_x, float scale_y, int codepoint, int *width, int *height, int *xoff, int *yoff);
875 // allocates a large-enough single-channel 8bpp bitmap and renders the
876 // specified character/glyph at the specified scale into it, with
877 // antialiasing. 0 is no coverage (transparent), 255 is fully covered (opaque).
878 // *width & *height are filled out with the width & height of the bitmap,
879 // which is stored left-to-right, top-to-bottom.
880 //
881 // xoff/yoff are the offset it pixel space from the glyph origin to the top-left of the bitmap
882
883 STBTT_DEF unsigned char *stbtt_GetCodepointBitmapSubpixel(const stbtt_fontinfo *info, float scale_x, float scale_y, float shift_x, float shift_y, int codepoint, int *width, int *height, int *xoff, int *yoff);
884 // the same as stbtt_GetCodepoitnBitmap, but you can specify a subpixel
885 // shift for the character
886
887 STBTT_DEF void stbtt_MakeCodepointBitmap(const stbtt_fontinfo *info, unsigned char *output, int out_w, int out_h, int out_stride, float scale_x, float scale_y, int codepoint);
888 // the same as stbtt_GetCodepointBitmap, but you pass in storage for the bitmap
889 // in the form of 'output', with row spacing of 'out_stride' bytes. the bitmap
890 // is clipped to out_w/out_h bytes. Call stbtt_GetCodepointBitmapBox to get the
891 // width and height and positioning info for it first.
892
893 STBTT_DEF void stbtt_MakeCodepointBitmapSubpixel(const stbtt_fontinfo *info, unsigned char *output, int out_w, int out_h, int out_stride, float scale_x, float scale_y, float shift_x, float shift_y, int codepoint);
894 // same as stbtt_MakeCodepointBitmap, but you can specify a subpixel
895 // shift for the character
896
897 STBTT_DEF void stbtt_MakeCodepointBitmapSubpixelPrefilter(const stbtt_fontinfo *info, unsigned char *output, int out_w, int out_h, int out_stride, float scale_x, float scale_y, float shift_x, float shift_y, int oversample_x, int oversample_y, float *sub_x, float *sub_y, int codepoint);
898 // same as stbtt_MakeCodepointBitmapSubpixel, but prefiltering
899 // is performed (see stbtt_PackSetOversampling)
900
901 STBTT_DEF void stbtt_GetCodepointBitmapBox(const stbtt_fontinfo *font, int codepoint, float scale_x, float scale_y, int *ix0, int *iy0, int *ix1, int *iy1);
902 // get the bbox of the bitmap centered around the glyph origin; so the
903 // bitmap width is ix1-ix0, height is iy1-iy0, and location to place
904 // the bitmap top left is (leftSideBearing*scale,iy0).
905 // (Note that the bitmap uses y-increases-down, but the shape uses
906 // y-increases-up, so CodepointBitmapBox and CodepointBox are inverted.)
907
908 STBTT_DEF void stbtt_GetCodepointBitmapBoxSubpixel(const stbtt_fontinfo *font, int codepoint, float scale_x, float scale_y, float shift_x, float shift_y, int *ix0, int *iy0, int *ix1, int *iy1);
909 // same as stbtt_GetCodepointBitmapBox, but you can specify a subpixel
910 // shift for the character
911
912 // the following functions are equivalent to the above functions, but operate
913 // on glyph indices instead of Unicode codepoints (for efficiency)
914 STBTT_DEF unsigned char *stbtt_GetGlyphBitmap(const stbtt_fontinfo *info, float scale_x, float scale_y, int glyph, int *width, int *height, int *xoff, int *yoff);
915 STBTT_DEF unsigned char *stbtt_GetGlyphBitmapSubpixel(const stbtt_fontinfo *info, float scale_x, float scale_y, float shift_x, float shift_y, int glyph, int *width, int *height, int *xoff, int *yoff);
916 STBTT_DEF void stbtt_MakeGlyphBitmap(const stbtt_fontinfo *info, unsigned char *output, int out_w, int out_h, int out_stride, float scale_x, float scale_y, int glyph);
917 STBTT_DEF void stbtt_MakeGlyphBitmapSubpixel(const stbtt_fontinfo *info, unsigned char *output, int out_w, int out_h, int out_stride, float scale_x, float scale_y, float shift_x, float shift_y, int glyph);
918 STBTT_DEF void stbtt_MakeGlyphBitmapSubpixelPrefilter(const stbtt_fontinfo *info, unsigned char *output, int out_w, int out_h, int out_stride, float scale_x, float scale_y, float shift_x, float shift_y, int oversample_x, int oversample_y, float *sub_x, float *sub_y, int glyph);
919 STBTT_DEF void stbtt_GetGlyphBitmapBox(const stbtt_fontinfo *font, int glyph, float scale_x, float scale_y, int *ix0, int *iy0, int *ix1, int *iy1);
920 STBTT_DEF void stbtt_GetGlyphBitmapBoxSubpixel(const stbtt_fontinfo *font, int glyph, float scale_x, float scale_y,float shift_x, float shift_y, int *ix0, int *iy0, int *ix1, int *iy1);
921
922
923 // @TODO: don't expose this structure
924 typedef struct
925 {
926    int w,h,stride;
927    unsigned char *pixels;
928 } stbtt__bitmap;
929
930 // rasterize a shape with quadratic beziers into a bitmap
931 STBTT_DEF void stbtt_Rasterize(stbtt__bitmap *result,        // 1-channel bitmap to draw into
932                                float flatness_in_pixels,     // allowable error of curve in pixels
933                                stbtt_vertex *vertices,       // array of vertices defining shape
934                                int num_verts,                // number of vertices in above array
935                                float scale_x, float scale_y, // scale applied to input vertices
936                                float shift_x, float shift_y, // translation applied to input vertices
937                                int x_off, int y_off,         // another translation applied to input
938                                int invert,                   // if non-zero, vertically flip shape
939                                void *userdata);              // context for to STBTT_MALLOC
940
941 //////////////////////////////////////////////////////////////////////////////
942 //
943 // Signed Distance Function (or Field) rendering
944
945 STBTT_DEF void stbtt_FreeSDF(unsigned char *bitmap, void *userdata);
946 // frees the SDF bitmap allocated below
947
948 STBTT_DEF unsigned char * stbtt_GetGlyphSDF(const stbtt_fontinfo *info, float scale, int glyph, int padding, unsigned char onedge_value, float pixel_dist_scale, int *width, int *height, int *xoff, int *yoff);
949 STBTT_DEF unsigned char * stbtt_GetCodepointSDF(const stbtt_fontinfo *info, float scale, int codepoint, int padding, unsigned char onedge_value, float pixel_dist_scale, int *width, int *height, int *xoff, int *yoff);
950 // These functions compute a discretized SDF field for a single character, suitable for storing
951 // in a single-channel texture, sampling with bilinear filtering, and testing against
952 // larger than some threshold to produce scalable fonts.
953 //        info              --  the font
954 //        scale             --  controls the size of the resulting SDF bitmap, same as it would be creating a regular bitmap
955 //        glyph/codepoint   --  the character to generate the SDF for
956 //        padding           --  extra "pixels" around the character which are filled with the distance to the character (not 0),
957 //                                 which allows effects like bit outlines
958 //        onedge_value      --  value 0-255 to test the SDF against to reconstruct the character (i.e. the isocontour of the character)
959 //        pixel_dist_scale  --  what value the SDF should increase by when moving one SDF "pixel" away from the edge (on the 0..255 scale)
960 //                                 if positive, > onedge_value is inside; if negative, < onedge_value is inside
961 //        width,height      --  output height & width of the SDF bitmap (including padding)
962 //        xoff,yoff         --  output origin of the character
963 //        return value      --  a 2D array of bytes 0..255, width*height in size
964 //
965 // pixel_dist_scale & onedge_value are a scale & bias that allows you to make
966 // optimal use of the limited 0..255 for your application, trading off precision
967 // and special effects. SDF values outside the range 0..255 are clamped to 0..255.
968 //
969 // Example:
970 //      scale = stbtt_ScaleForPixelHeight(22)
971 //      padding = 5
972 //      onedge_value = 180
973 //      pixel_dist_scale = 180/5.0 = 36.0
974 //
975 //      This will create an SDF bitmap in which the character is about 22 pixels
976 //      high but the whole bitmap is about 22+5+5=32 pixels high. To produce a filled
977 //      shape, sample the SDF at each pixel and fill the pixel if the SDF value
978 //      is greater than or equal to 180/255. (You'll actually want to antialias,
979 //      which is beyond the scope of this example.) Additionally, you can compute
980 //      offset outlines (e.g. to stroke the character border inside & outside,
981 //      or only outside). For example, to fill outside the character up to 3 SDF
982 //      pixels, you would compare against (180-36.0*3)/255 = 72/255. The above
983 //      choice of variables maps a range from 5 pixels outside the shape to
984 //      2 pixels inside the shape to 0..255; this is intended primarily for apply
985 //      outside effects only (the interior range is needed to allow proper
986 //      antialiasing of the font at *smaller* sizes)
987 //
988 // The function computes the SDF analytically at each SDF pixel, not by e.g.
989 // building a higher-res bitmap and approximating it. In theory the quality
990 // should be as high as possible for an SDF of this size & representation, but
991 // unclear if this is true in practice (perhaps building a higher-res bitmap
992 // and computing from that can allow drop-out prevention).
993 //
994 // The algorithm has not been optimized at all, so expect it to be slow
995 // if computing lots of characters or very large sizes.
996
997
998
999 //////////////////////////////////////////////////////////////////////////////
1000 //
1001 // Finding the right font...
1002 //
1003 // You should really just solve this offline, keep your own tables
1004 // of what font is what, and don't try to get it out of the .ttf file.
1005 // That's because getting it out of the .ttf file is really hard, because
1006 // the names in the file can appear in many possible encodings, in many
1007 // possible languages, and e.g. if you need a case-insensitive comparison,
1008 // the details of that depend on the encoding & language in a complex way
1009 // (actually underspecified in truetype, but also gigantic).
1010 //
1011 // But you can use the provided functions in two possible ways:
1012 //     stbtt_FindMatchingFont() will use *case-sensitive* comparisons on
1013 //             unicode-encoded names to try to find the font you want;
1014 //             you can run this before calling stbtt_InitFont()
1015 //
1016 //     stbtt_GetFontNameString() lets you get any of the various strings
1017 //             from the file yourself and do your own comparisons on them.
1018 //             You have to have called stbtt_InitFont() first.
1019
1020
1021 STBTT_DEF int stbtt_FindMatchingFont(const unsigned char *fontdata, const char *name, int flags);
1022 // returns the offset (not index) of the font that matches, or -1 if none
1023 //   if you use STBTT_MACSTYLE_DONTCARE, use a font name like "Arial Bold".
1024 //   if you use any other flag, use a font name like "Arial"; this checks
1025 //     the 'macStyle' header field; i don't know if fonts set this consistently
1026 #define STBTT_MACSTYLE_DONTCARE     0
1027 #define STBTT_MACSTYLE_BOLD         1
1028 #define STBTT_MACSTYLE_ITALIC       2
1029 #define STBTT_MACSTYLE_UNDERSCORE   4
1030 #define STBTT_MACSTYLE_NONE         8   // <= not same as 0, this makes us check the bitfield is 0
1031
1032 STBTT_DEF int stbtt_CompareUTF8toUTF16_bigendian(const char *s1, int len1, const char *s2, int len2);
1033 // returns 1/0 whether the first string interpreted as utf8 is identical to
1034 // the second string interpreted as big-endian utf16... useful for strings from next func
1035
1036 STBTT_DEF const char *stbtt_GetFontNameString(const stbtt_fontinfo *font, int *length, int platformID, int encodingID, int languageID, int nameID);
1037 // returns the string (which may be big-endian double byte, e.g. for unicode)
1038 // and puts the length in bytes in *length.
1039 //
1040 // some of the values for the IDs are below; for more see the truetype spec:
1041 //     http://developer.apple.com/textfonts/TTRefMan/RM06/Chap6name.html
1042 //     http://www.microsoft.com/typography/otspec/name.htm
1043
1044 enum { // platformID
1045    STBTT_PLATFORM_ID_UNICODE   =0,
1046    STBTT_PLATFORM_ID_MAC       =1,
1047    STBTT_PLATFORM_ID_ISO       =2,
1048    STBTT_PLATFORM_ID_MICROSOFT =3
1049 };
1050
1051 enum { // encodingID for STBTT_PLATFORM_ID_UNICODE
1052    STBTT_UNICODE_EID_UNICODE_1_0    =0,
1053    STBTT_UNICODE_EID_UNICODE_1_1    =1,
1054    STBTT_UNICODE_EID_ISO_10646      =2,
1055    STBTT_UNICODE_EID_UNICODE_2_0_BMP=3,
1056    STBTT_UNICODE_EID_UNICODE_2_0_FULL=4
1057 };
1058
1059 enum { // encodingID for STBTT_PLATFORM_ID_MICROSOFT
1060    STBTT_MS_EID_SYMBOL        =0,
1061    STBTT_MS_EID_UNICODE_BMP   =1,
1062    STBTT_MS_EID_SHIFTJIS      =2,
1063    STBTT_MS_EID_UNICODE_FULL  =10
1064 };
1065
1066 enum { // encodingID for STBTT_PLATFORM_ID_MAC; same as Script Manager codes
1067    STBTT_MAC_EID_ROMAN        =0,   STBTT_MAC_EID_ARABIC       =4,
1068    STBTT_MAC_EID_JAPANESE     =1,   STBTT_MAC_EID_HEBREW       =5,
1069    STBTT_MAC_EID_CHINESE_TRAD =2,   STBTT_MAC_EID_GREEK        =6,
1070    STBTT_MAC_EID_KOREAN       =3,   STBTT_MAC_EID_RUSSIAN      =7
1071 };
1072
1073 enum { // languageID for STBTT_PLATFORM_ID_MICROSOFT; same as LCID...
1074        // problematic because there are e.g. 16 english LCIDs and 16 arabic LCIDs
1075    STBTT_MS_LANG_ENGLISH     =0x0409,   STBTT_MS_LANG_ITALIAN     =0x0410,
1076    STBTT_MS_LANG_CHINESE     =0x0804,   STBTT_MS_LANG_JAPANESE    =0x0411,
1077    STBTT_MS_LANG_DUTCH       =0x0413,   STBTT_MS_LANG_KOREAN      =0x0412,
1078    STBTT_MS_LANG_FRENCH      =0x040c,   STBTT_MS_LANG_RUSSIAN     =0x0419,
1079    STBTT_MS_LANG_GERMAN      =0x0407,   STBTT_MS_LANG_SPANISH     =0x0409,
1080    STBTT_MS_LANG_HEBREW      =0x040d,   STBTT_MS_LANG_SWEDISH     =0x041D
1081 };
1082
1083 enum { // languageID for STBTT_PLATFORM_ID_MAC
1084    STBTT_MAC_LANG_ENGLISH      =0 ,   STBTT_MAC_LANG_JAPANESE     =11,
1085    STBTT_MAC_LANG_ARABIC       =12,   STBTT_MAC_LANG_KOREAN       =23,
1086    STBTT_MAC_LANG_DUTCH        =4 ,   STBTT_MAC_LANG_RUSSIAN      =32,
1087    STBTT_MAC_LANG_FRENCH       =1 ,   STBTT_MAC_LANG_SPANISH      =6 ,
1088    STBTT_MAC_LANG_GERMAN       =2 ,   STBTT_MAC_LANG_SWEDISH      =5 ,
1089    STBTT_MAC_LANG_HEBREW       =10,   STBTT_MAC_LANG_CHINESE_SIMPLIFIED =33,
1090    STBTT_MAC_LANG_ITALIAN      =3 ,   STBTT_MAC_LANG_CHINESE_TRAD =19
1091 };
1092
1093 #ifdef __cplusplus
1094 }
1095 #endif
1096
1097 #endif // __STB_INCLUDE_STB_TRUETYPE_H__
1098
1099 ///////////////////////////////////////////////////////////////////////////////
1100 ///////////////////////////////////////////////////////////////////////////////
1101 ////
1102 ////   IMPLEMENTATION
1103 ////
1104 ////
1105
1106 #ifdef STB_TRUETYPE_IMPLEMENTATION
1107
1108 #ifndef STBTT_MAX_OVERSAMPLE
1109 #define STBTT_MAX_OVERSAMPLE   8
1110 #endif
1111
1112 #if STBTT_MAX_OVERSAMPLE > 255
1113 #error "STBTT_MAX_OVERSAMPLE cannot be > 255"
1114 #endif
1115
1116 typedef int stbtt__test_oversample_pow2[(STBTT_MAX_OVERSAMPLE & (STBTT_MAX_OVERSAMPLE-1)) == 0 ? 1 : -1];
1117
1118 #ifndef STBTT_RASTERIZER_VERSION
1119 #define STBTT_RASTERIZER_VERSION 2
1120 #endif
1121
1122 #ifdef _MSC_VER
1123 #define STBTT__NOTUSED(v)  (void)(v)
1124 #else
1125 #define STBTT__NOTUSED(v)  (void)sizeof(v)
1126 #endif
1127
1128 //////////////////////////////////////////////////////////////////////////
1129 //
1130 // stbtt__buf helpers to parse data from file
1131 //
1132
1133 static stbtt_uint8 stbtt__buf_get8(stbtt__buf *b)
1134 {
1135    if (b->cursor >= b->size)
1136       return 0;
1137    return b->data[b->cursor++];
1138 }
1139
1140 static stbtt_uint8 stbtt__buf_peek8(stbtt__buf *b)
1141 {
1142    if (b->cursor >= b->size)
1143       return 0;
1144    return b->data[b->cursor];
1145 }
1146
1147 static void stbtt__buf_seek(stbtt__buf *b, int o)
1148 {
1149    STBTT_assert(!(o > b->size || o < 0));
1150    b->cursor = (o > b->size || o < 0) ? b->size : o;
1151 }
1152
1153 static void stbtt__buf_skip(stbtt__buf *b, int o)
1154 {
1155    stbtt__buf_seek(b, b->cursor + o);
1156 }
1157
1158 static stbtt_uint32 stbtt__buf_get(stbtt__buf *b, int n)
1159 {
1160    stbtt_uint32 v = 0;
1161    int i;
1162    STBTT_assert(n >= 1 && n <= 4);
1163    for (i = 0; i < n; i++)
1164       v = (v << 8) | stbtt__buf_get8(b);
1165    return v;
1166 }
1167
1168 static stbtt__buf stbtt__new_buf(const void *p, size_t size)
1169 {
1170    stbtt__buf r;
1171    STBTT_assert(size < 0x40000000);
1172    r.data = (stbtt_uint8*) p;
1173    r.size = (int) size;
1174    r.cursor = 0;
1175    return r;
1176 }
1177
1178 #define stbtt__buf_get16(b)  stbtt__buf_get((b), 2)
1179 #define stbtt__buf_get32(b)  stbtt__buf_get((b), 4)
1180
1181 static stbtt__buf stbtt__buf_range(const stbtt__buf *b, int o, int s)
1182 {
1183    stbtt__buf r = stbtt__new_buf(NULL, 0);
1184    if (o < 0 || s < 0 || o > b->size || s > b->size - o) return r;
1185    r.data = b->data + o;
1186    r.size = s;
1187    return r;
1188 }
1189
1190 static stbtt__buf stbtt__cff_get_index(stbtt__buf *b)
1191 {
1192    int count, start, offsize;
1193    start = b->cursor;
1194    count = stbtt__buf_get16(b);
1195    if (count) {
1196       offsize = stbtt__buf_get8(b);
1197       STBTT_assert(offsize >= 1 && offsize <= 4);
1198       stbtt__buf_skip(b, offsize * count);
1199       stbtt__buf_skip(b, stbtt__buf_get(b, offsize) - 1);
1200    }
1201    return stbtt__buf_range(b, start, b->cursor - start);
1202 }
1203
1204 static stbtt_uint32 stbtt__cff_int(stbtt__buf *b)
1205 {
1206    int b0 = stbtt__buf_get8(b);
1207    if (b0 >= 32 && b0 <= 246)       return b0 - 139;
1208    else if (b0 >= 247 && b0 <= 250) return (b0 - 247)*256 + stbtt__buf_get8(b) + 108;
1209    else if (b0 >= 251 && b0 <= 254) return -(b0 - 251)*256 - stbtt__buf_get8(b) - 108;
1210    else if (b0 == 28)               return stbtt__buf_get16(b);
1211    else if (b0 == 29)               return stbtt__buf_get32(b);
1212    STBTT_assert(0);
1213    return 0;
1214 }
1215
1216 static void stbtt__cff_skip_operand(stbtt__buf *b) {
1217    int v, b0 = stbtt__buf_peek8(b);
1218    STBTT_assert(b0 >= 28);
1219    if (b0 == 30) {
1220       stbtt__buf_skip(b, 1);
1221       while (b->cursor < b->size) {
1222          v = stbtt__buf_get8(b);
1223          if ((v & 0xF) == 0xF || (v >> 4) == 0xF)
1224             break;
1225       }
1226    } else {
1227       stbtt__cff_int(b);
1228    }
1229 }
1230
1231 static stbtt__buf stbtt__dict_get(stbtt__buf *b, int key)
1232 {
1233    stbtt__buf_seek(b, 0);
1234    while (b->cursor < b->size) {
1235       int start = b->cursor, end, op;
1236       while (stbtt__buf_peek8(b) >= 28)
1237          stbtt__cff_skip_operand(b);
1238       end = b->cursor;
1239       op = stbtt__buf_get8(b);
1240       if (op == 12)  op = stbtt__buf_get8(b) | 0x100;
1241       if (op == key) return stbtt__buf_range(b, start, end-start);
1242    }
1243    return stbtt__buf_range(b, 0, 0);
1244 }
1245
1246 static void stbtt__dict_get_ints(stbtt__buf *b, int key, int outcount, stbtt_uint32 *out)
1247 {
1248    int i;
1249    stbtt__buf operands = stbtt__dict_get(b, key);
1250    for (i = 0; i < outcount && operands.cursor < operands.size; i++)
1251       out[i] = stbtt__cff_int(&operands);
1252 }
1253
1254 static int stbtt__cff_index_count(stbtt__buf *b)
1255 {
1256    stbtt__buf_seek(b, 0);
1257    return stbtt__buf_get16(b);
1258 }
1259
1260 static stbtt__buf stbtt__cff_index_get(stbtt__buf b, int i)
1261 {
1262    int count, offsize, start, end;
1263    stbtt__buf_seek(&b, 0);
1264    count = stbtt__buf_get16(&b);
1265    offsize = stbtt__buf_get8(&b);
1266    STBTT_assert(i >= 0 && i < count);
1267    STBTT_assert(offsize >= 1 && offsize <= 4);
1268    stbtt__buf_skip(&b, i*offsize);
1269    start = stbtt__buf_get(&b, offsize);
1270    end = stbtt__buf_get(&b, offsize);
1271    return stbtt__buf_range(&b, 2+(count+1)*offsize+start, end - start);
1272 }
1273
1274 //////////////////////////////////////////////////////////////////////////
1275 //
1276 // accessors to parse data from file
1277 //
1278
1279 // on platforms that don't allow misaligned reads, if we want to allow
1280 // truetype fonts that aren't padded to alignment, define ALLOW_UNALIGNED_TRUETYPE
1281
1282 #define ttBYTE(p)     (* (stbtt_uint8 *) (p))
1283 #define ttCHAR(p)     (* (stbtt_int8 *) (p))
1284 #define ttFixed(p)    ttLONG(p)
1285
1286 static stbtt_uint16 ttUSHORT(stbtt_uint8 *p) { return p[0]*256 + p[1]; }
1287 static stbtt_int16 ttSHORT(stbtt_uint8 *p)   { return p[0]*256 + p[1]; }
1288 static stbtt_uint32 ttULONG(stbtt_uint8 *p)  { return (p[0]<<24) + (p[1]<<16) + (p[2]<<8) + p[3]; }
1289 static stbtt_int32 ttLONG(stbtt_uint8 *p)    { return (p[0]<<24) + (p[1]<<16) + (p[2]<<8) + p[3]; }
1290
1291 #define stbtt_tag4(p,c0,c1,c2,c3) ((p)[0] == (c0) && (p)[1] == (c1) && (p)[2] == (c2) && (p)[3] == (c3))
1292 #define stbtt_tag(p,str)           stbtt_tag4(p,str[0],str[1],str[2],str[3])
1293
1294 static int stbtt__isfont(stbtt_uint8 *font)
1295 {
1296    // check the version number
1297    if (stbtt_tag4(font, '1',0,0,0))  return 1; // TrueType 1
1298    if (stbtt_tag(font, "typ1"))   return 1; // TrueType with type 1 font -- we don't support this!
1299    if (stbtt_tag(font, "OTTO"))   return 1; // OpenType with CFF
1300    if (stbtt_tag4(font, 0,1,0,0)) return 1; // OpenType 1.0
1301    if (stbtt_tag(font, "true"))   return 1; // Apple specification for TrueType fonts
1302    return 0;
1303 }
1304
1305 // @OPTIMIZE: binary search
1306 static stbtt_uint32 stbtt__find_table(stbtt_uint8 *data, stbtt_uint32 fontstart, const char *tag)
1307 {
1308    stbtt_int32 num_tables = ttUSHORT(data+fontstart+4);
1309    stbtt_uint32 tabledir = fontstart + 12;
1310    stbtt_int32 i;
1311    for (i=0; i < num_tables; ++i) {
1312       stbtt_uint32 loc = tabledir + 16*i;
1313       if (stbtt_tag(data+loc+0, tag))
1314          return ttULONG(data+loc+8);
1315    }
1316    return 0;
1317 }
1318
1319 static int stbtt_GetFontOffsetForIndex_internal(unsigned char *font_collection, int index)
1320 {
1321    // if it's just a font, there's only one valid index
1322    if (stbtt__isfont(font_collection))
1323       return index == 0 ? 0 : -1;
1324
1325    // check if it's a TTC
1326    if (stbtt_tag(font_collection, "ttcf")) {
1327       // version 1?
1328       if (ttULONG(font_collection+4) == 0x00010000 || ttULONG(font_collection+4) == 0x00020000) {
1329          stbtt_int32 n = ttLONG(font_collection+8);
1330          if (index >= n)
1331             return -1;
1332          return ttULONG(font_collection+12+index*4);
1333       }
1334    }
1335    return -1;
1336 }
1337
1338 static int stbtt_GetNumberOfFonts_internal(unsigned char *font_collection)
1339 {
1340    // if it's just a font, there's only one valid font
1341    if (stbtt__isfont(font_collection))
1342       return 1;
1343
1344    // check if it's a TTC
1345    if (stbtt_tag(font_collection, "ttcf")) {
1346       // version 1?
1347       if (ttULONG(font_collection+4) == 0x00010000 || ttULONG(font_collection+4) == 0x00020000) {
1348          return ttLONG(font_collection+8);
1349       }
1350    }
1351    return 0;
1352 }
1353
1354 static stbtt__buf stbtt__get_subrs(stbtt__buf cff, stbtt__buf fontdict)
1355 {
1356    stbtt_uint32 subrsoff = 0, private_loc[2] = { 0, 0 };
1357    stbtt__buf pdict;
1358    stbtt__dict_get_ints(&fontdict, 18, 2, private_loc);
1359    if (!private_loc[1] || !private_loc[0]) return stbtt__new_buf(NULL, 0);
1360    pdict = stbtt__buf_range(&cff, private_loc[1], private_loc[0]);
1361    stbtt__dict_get_ints(&pdict, 19, 1, &subrsoff);
1362    if (!subrsoff) return stbtt__new_buf(NULL, 0);
1363    stbtt__buf_seek(&cff, private_loc[1]+subrsoff);
1364    return stbtt__cff_get_index(&cff);
1365 }
1366
1367 // since most people won't use this, find this table the first time it's needed
1368 static int stbtt__get_svg(stbtt_fontinfo *info)
1369 {
1370    stbtt_uint32 t;
1371    if (info->svg < 0) {
1372       t = stbtt__find_table(info->data, info->fontstart, "SVG ");
1373       if (t) {
1374          stbtt_uint32 offset = ttULONG(info->data + t + 2);
1375          info->svg = t + offset;
1376       } else {
1377          info->svg = 0;
1378       }
1379    }
1380    return info->svg;
1381 }
1382
1383 static int stbtt_InitFont_internal(stbtt_fontinfo *info, unsigned char *data, int fontstart)
1384 {
1385    stbtt_uint32 cmap, t;
1386    stbtt_int32 i,numTables;
1387
1388    info->data = data;
1389    info->fontstart = fontstart;
1390    info->cff = stbtt__new_buf(NULL, 0);
1391
1392    cmap = stbtt__find_table(data, fontstart, "cmap");       // required
1393    info->loca = stbtt__find_table(data, fontstart, "loca"); // required
1394    info->head = stbtt__find_table(data, fontstart, "head"); // required
1395    info->glyf = stbtt__find_table(data, fontstart, "glyf"); // required
1396    info->hhea = stbtt__find_table(data, fontstart, "hhea"); // required
1397    info->hmtx = stbtt__find_table(data, fontstart, "hmtx"); // required
1398    info->kern = stbtt__find_table(data, fontstart, "kern"); // not required
1399    info->gpos = stbtt__find_table(data, fontstart, "GPOS"); // not required
1400
1401    if (!cmap || !info->head || !info->hhea || !info->hmtx)
1402       return 0;
1403    if (info->glyf) {
1404       // required for truetype
1405       if (!info->loca) return 0;
1406    } else {
1407       // initialization for CFF / Type2 fonts (OTF)
1408       stbtt__buf b, topdict, topdictidx;
1409       stbtt_uint32 cstype = 2, charstrings = 0, fdarrayoff = 0, fdselectoff = 0;
1410       stbtt_uint32 cff;
1411
1412       cff = stbtt__find_table(data, fontstart, "CFF ");
1413       if (!cff) return 0;
1414
1415       info->fontdicts = stbtt__new_buf(NULL, 0);
1416       info->fdselect = stbtt__new_buf(NULL, 0);
1417
1418       // @TODO this should use size from table (not 512MB)
1419       info->cff = stbtt__new_buf(data+cff, 512*1024*1024);
1420       b = info->cff;
1421
1422       // read the header
1423       stbtt__buf_skip(&b, 2);
1424       stbtt__buf_seek(&b, stbtt__buf_get8(&b)); // hdrsize
1425
1426       // @TODO the name INDEX could list multiple fonts,
1427       // but we just use the first one.
1428       stbtt__cff_get_index(&b);  // name INDEX
1429       topdictidx = stbtt__cff_get_index(&b);
1430       topdict = stbtt__cff_index_get(topdictidx, 0);
1431       stbtt__cff_get_index(&b);  // string INDEX
1432       info->gsubrs = stbtt__cff_get_index(&b);
1433
1434       stbtt__dict_get_ints(&topdict, 17, 1, &charstrings);
1435       stbtt__dict_get_ints(&topdict, 0x100 | 6, 1, &cstype);
1436       stbtt__dict_get_ints(&topdict, 0x100 | 36, 1, &fdarrayoff);
1437       stbtt__dict_get_ints(&topdict, 0x100 | 37, 1, &fdselectoff);
1438       info->subrs = stbtt__get_subrs(b, topdict);
1439
1440       // we only support Type 2 charstrings
1441       if (cstype != 2) return 0;
1442       if (charstrings == 0) return 0;
1443
1444       if (fdarrayoff) {
1445          // looks like a CID font
1446          if (!fdselectoff) return 0;
1447          stbtt__buf_seek(&b, fdarrayoff);
1448          info->fontdicts = stbtt__cff_get_index(&b);
1449          info->fdselect = stbtt__buf_range(&b, fdselectoff, b.size-fdselectoff);
1450       }
1451
1452       stbtt__buf_seek(&b, charstrings);
1453       info->charstrings = stbtt__cff_get_index(&b);
1454    }
1455
1456    t = stbtt__find_table(data, fontstart, "maxp");
1457    if (t)
1458       info->numGlyphs = ttUSHORT(data+t+4);
1459    else
1460       info->numGlyphs = 0xffff;
1461
1462    info->svg = -1;
1463
1464    // find a cmap encoding table we understand *now* to avoid searching
1465    // later. (todo: could make this installable)
1466    // the same regardless of glyph.
1467    numTables = ttUSHORT(data + cmap + 2);
1468    info->index_map = 0;
1469    for (i=0; i < numTables; ++i) {
1470       stbtt_uint32 encoding_record = cmap + 4 + 8 * i;
1471       // find an encoding we understand:
1472       switch(ttUSHORT(data+encoding_record)) {
1473          case STBTT_PLATFORM_ID_MICROSOFT:
1474             switch (ttUSHORT(data+encoding_record+2)) {
1475                case STBTT_MS_EID_UNICODE_BMP:
1476                case STBTT_MS_EID_UNICODE_FULL:
1477                   // MS/Unicode
1478                   info->index_map = cmap + ttULONG(data+encoding_record+4);
1479                   break;
1480             }
1481             break;
1482         case STBTT_PLATFORM_ID_UNICODE:
1483             // Mac/iOS has these
1484             // all the encodingIDs are unicode, so we don't bother to check it
1485             info->index_map = cmap + ttULONG(data+encoding_record+4);
1486             break;
1487       }
1488    }
1489    if (info->index_map == 0)
1490       return 0;
1491
1492    info->indexToLocFormat = ttUSHORT(data+info->head + 50);
1493    return 1;
1494 }
1495
1496 STBTT_DEF int stbtt_FindGlyphIndex(const stbtt_fontinfo *info, int unicode_codepoint)
1497 {
1498    stbtt_uint8 *data = info->data;
1499    stbtt_uint32 index_map = info->index_map;
1500
1501    stbtt_uint16 format = ttUSHORT(data + index_map + 0);
1502    if (format == 0) { // apple byte encoding
1503       stbtt_int32 bytes = ttUSHORT(data + index_map + 2);
1504       if (unicode_codepoint < bytes-6)
1505          return ttBYTE(data + index_map + 6 + unicode_codepoint);
1506       return 0;
1507    } else if (format == 6) {
1508       stbtt_uint32 first = ttUSHORT(data + index_map + 6);
1509       stbtt_uint32 count = ttUSHORT(data + index_map + 8);
1510       if ((stbtt_uint32) unicode_codepoint >= first && (stbtt_uint32) unicode_codepoint < first+count)
1511          return ttUSHORT(data + index_map + 10 + (unicode_codepoint - first)*2);
1512       return 0;
1513    } else if (format == 2) {
1514       STBTT_assert(0); // @TODO: high-byte mapping for japanese/chinese/korean
1515       return 0;
1516    } else if (format == 4) { // standard mapping for windows fonts: binary search collection of ranges
1517       stbtt_uint16 segcount = ttUSHORT(data+index_map+6) >> 1;
1518       stbtt_uint16 searchRange = ttUSHORT(data+index_map+8) >> 1;
1519       stbtt_uint16 entrySelector = ttUSHORT(data+index_map+10);
1520       stbtt_uint16 rangeShift = ttUSHORT(data+index_map+12) >> 1;
1521
1522       // do a binary search of the segments
1523       stbtt_uint32 endCount = index_map + 14;
1524       stbtt_uint32 search = endCount;
1525
1526       if (unicode_codepoint > 0xffff)
1527          return 0;
1528
1529       // they lie from endCount .. endCount + segCount
1530       // but searchRange is the nearest power of two, so...
1531       if (unicode_codepoint >= ttUSHORT(data + search + rangeShift*2))
1532          search += rangeShift*2;
1533
1534       // now decrement to bias correctly to find smallest
1535       search -= 2;
1536       while (entrySelector) {
1537          stbtt_uint16 end;
1538          searchRange >>= 1;
1539          end = ttUSHORT(data + search + searchRange*2);
1540          if (unicode_codepoint > end)
1541             search += searchRange*2;
1542          --entrySelector;
1543       }
1544       search += 2;
1545
1546       {
1547          stbtt_uint16 offset, start, last;
1548          stbtt_uint16 item = (stbtt_uint16) ((search - endCount) >> 1);
1549
1550          start = ttUSHORT(data + index_map + 14 + segcount*2 + 2 + 2*item);
1551          last = ttUSHORT(data + endCount + 2*item);
1552          if (unicode_codepoint < start || unicode_codepoint > last)
1553             return 0;
1554
1555          offset = ttUSHORT(data + index_map + 14 + segcount*6 + 2 + 2*item);
1556          if (offset == 0)
1557             return (stbtt_uint16) (unicode_codepoint + ttSHORT(data + index_map + 14 + segcount*4 + 2 + 2*item));
1558
1559          return ttUSHORT(data + offset + (unicode_codepoint-start)*2 + index_map + 14 + segcount*6 + 2 + 2*item);
1560       }
1561    } else if (format == 12 || format == 13) {
1562       stbtt_uint32 ngroups = ttULONG(data+index_map+12);
1563       stbtt_int32 low,high;
1564       low = 0; high = (stbtt_int32)ngroups;
1565       // Binary search the right group.
1566       while (low < high) {
1567          stbtt_int32 mid = low + ((high-low) >> 1); // rounds down, so low <= mid < high
1568          stbtt_uint32 start_char = ttULONG(data+index_map+16+mid*12);
1569          stbtt_uint32 end_char = ttULONG(data+index_map+16+mid*12+4);
1570          if ((stbtt_uint32) unicode_codepoint < start_char)
1571             high = mid;
1572          else if ((stbtt_uint32) unicode_codepoint > end_char)
1573             low = mid+1;
1574          else {
1575             stbtt_uint32 start_glyph = ttULONG(data+index_map+16+mid*12+8);
1576             if (format == 12)
1577                return start_glyph + unicode_codepoint-start_char;
1578             else // format == 13
1579                return start_glyph;
1580          }
1581       }
1582       return 0; // not found
1583    }
1584    // @TODO
1585    STBTT_assert(0);
1586    return 0;
1587 }
1588
1589 STBTT_DEF int stbtt_GetCodepointShape(const stbtt_fontinfo *info, int unicode_codepoint, stbtt_vertex **vertices)
1590 {
1591    return stbtt_GetGlyphShape(info, stbtt_FindGlyphIndex(info, unicode_codepoint), vertices);
1592 }
1593
1594 static void stbtt_setvertex(stbtt_vertex *v, stbtt_uint8 type, stbtt_int32 x, stbtt_int32 y, stbtt_int32 cx, stbtt_int32 cy)
1595 {
1596    v->type = type;
1597    v->x = (stbtt_int16) x;
1598    v->y = (stbtt_int16) y;
1599    v->cx = (stbtt_int16) cx;
1600    v->cy = (stbtt_int16) cy;
1601 }
1602
1603 static int stbtt__GetGlyfOffset(const stbtt_fontinfo *info, int glyph_index)
1604 {
1605    int g1,g2;
1606
1607    STBTT_assert(!info->cff.size);
1608
1609    if (glyph_index >= info->numGlyphs) return -1; // glyph index out of range
1610    if (info->indexToLocFormat >= 2)    return -1; // unknown index->glyph map format
1611
1612    if (info->indexToLocFormat == 0) {
1613       g1 = info->glyf + ttUSHORT(info->data + info->loca + glyph_index * 2) * 2;
1614       g2 = info->glyf + ttUSHORT(info->data + info->loca + glyph_index * 2 + 2) * 2;
1615    } else {
1616       g1 = info->glyf + ttULONG (info->data + info->loca + glyph_index * 4);
1617       g2 = info->glyf + ttULONG (info->data + info->loca + glyph_index * 4 + 4);
1618    }
1619
1620    return g1==g2 ? -1 : g1; // if length is 0, return -1
1621 }
1622
1623 static int stbtt__GetGlyphInfoT2(const stbtt_fontinfo *info, int glyph_index, int *x0, int *y0, int *x1, int *y1);
1624
1625 STBTT_DEF int stbtt_GetGlyphBox(const stbtt_fontinfo *info, int glyph_index, int *x0, int *y0, int *x1, int *y1)
1626 {
1627    if (info->cff.size) {
1628       stbtt__GetGlyphInfoT2(info, glyph_index, x0, y0, x1, y1);
1629    } else {
1630       int g = stbtt__GetGlyfOffset(info, glyph_index);
1631       if (g < 0) return 0;
1632
1633       if (x0) *x0 = ttSHORT(info->data + g + 2);
1634       if (y0) *y0 = ttSHORT(info->data + g + 4);
1635       if (x1) *x1 = ttSHORT(info->data + g + 6);
1636       if (y1) *y1 = ttSHORT(info->data + g + 8);
1637    }
1638    return 1;
1639 }
1640
1641 STBTT_DEF int stbtt_GetCodepointBox(const stbtt_fontinfo *info, int codepoint, int *x0, int *y0, int *x1, int *y1)
1642 {
1643    return stbtt_GetGlyphBox(info, stbtt_FindGlyphIndex(info,codepoint), x0,y0,x1,y1);
1644 }
1645
1646 STBTT_DEF int stbtt_IsGlyphEmpty(const stbtt_fontinfo *info, int glyph_index)
1647 {
1648    stbtt_int16 numberOfContours;
1649    int g;
1650    if (info->cff.size)
1651       return stbtt__GetGlyphInfoT2(info, glyph_index, NULL, NULL, NULL, NULL) == 0;
1652    g = stbtt__GetGlyfOffset(info, glyph_index);
1653    if (g < 0) return 1;
1654    numberOfContours = ttSHORT(info->data + g);
1655    return numberOfContours == 0;
1656 }
1657
1658 static int stbtt__close_shape(stbtt_vertex *vertices, int num_vertices, int was_off, int start_off,
1659     stbtt_int32 sx, stbtt_int32 sy, stbtt_int32 scx, stbtt_int32 scy, stbtt_int32 cx, stbtt_int32 cy)
1660 {
1661    if (start_off) {
1662       if (was_off)
1663          stbtt_setvertex(&vertices[num_vertices++], STBTT_vcurve, (cx+scx)>>1, (cy+scy)>>1, cx,cy);
1664       stbtt_setvertex(&vertices[num_vertices++], STBTT_vcurve, sx,sy,scx,scy);
1665    } else {
1666       if (was_off)
1667          stbtt_setvertex(&vertices[num_vertices++], STBTT_vcurve,sx,sy,cx,cy);
1668       else
1669          stbtt_setvertex(&vertices[num_vertices++], STBTT_vline,sx,sy,0,0);
1670    }
1671    return num_vertices;
1672 }
1673
1674 static int stbtt__GetGlyphShapeTT(const stbtt_fontinfo *info, int glyph_index, stbtt_vertex **pvertices)
1675 {
1676    stbtt_int16 numberOfContours;
1677    stbtt_uint8 *endPtsOfContours;
1678    stbtt_uint8 *data = info->data;
1679    stbtt_vertex *vertices=0;
1680    int num_vertices=0;
1681    int g = stbtt__GetGlyfOffset(info, glyph_index);
1682
1683    *pvertices = NULL;
1684
1685    if (g < 0) return 0;
1686
1687    numberOfContours = ttSHORT(data + g);
1688
1689    if (numberOfContours > 0) {
1690       stbtt_uint8 flags=0,flagcount;
1691       stbtt_int32 ins, i,j=0,m,n, next_move, was_off=0, off, start_off=0;
1692       stbtt_int32 x,y,cx,cy,sx,sy, scx,scy;
1693       stbtt_uint8 *points;
1694       endPtsOfContours = (data + g + 10);
1695       ins = ttUSHORT(data + g + 10 + numberOfContours * 2);
1696       points = data + g + 10 + numberOfContours * 2 + 2 + ins;
1697
1698       n = 1+ttUSHORT(endPtsOfContours + numberOfContours*2-2);
1699
1700       m = n + 2*numberOfContours;  // a loose bound on how many vertices we might need
1701       vertices = (stbtt_vertex *) STBTT_malloc(m * sizeof(vertices[0]), info->userdata);
1702       if (vertices == 0)
1703          return 0;
1704
1705       next_move = 0;
1706       flagcount=0;
1707
1708       // in first pass, we load uninterpreted data into the allocated array
1709       // above, shifted to the end of the array so we won't overwrite it when
1710       // we create our final data starting from the front
1711
1712       off = m - n; // starting offset for uninterpreted data, regardless of how m ends up being calculated
1713
1714       // first load flags
1715
1716       for (i=0; i < n; ++i) {
1717          if (flagcount == 0) {
1718             flags = *points++;
1719             if (flags & 8)
1720                flagcount = *points++;
1721          } else
1722             --flagcount;
1723          vertices[off+i].type = flags;
1724       }
1725
1726       // now load x coordinates
1727       x=0;
1728       for (i=0; i < n; ++i) {
1729          flags = vertices[off+i].type;
1730          if (flags & 2) {
1731             stbtt_int16 dx = *points++;
1732             x += (flags & 16) ? dx : -dx; // ???
1733          } else {
1734             if (!(flags & 16)) {
1735                x = x + (stbtt_int16) (points[0]*256 + points[1]);
1736                points += 2;
1737             }
1738          }
1739          vertices[off+i].x = (stbtt_int16) x;
1740       }
1741
1742       // now load y coordinates
1743       y=0;
1744       for (i=0; i < n; ++i) {
1745          flags = vertices[off+i].type;
1746          if (flags & 4) {
1747             stbtt_int16 dy = *points++;
1748             y += (flags & 32) ? dy : -dy; // ???
1749          } else {
1750             if (!(flags & 32)) {
1751                y = y + (stbtt_int16) (points[0]*256 + points[1]);
1752                points += 2;
1753             }
1754          }
1755          vertices[off+i].y = (stbtt_int16) y;
1756       }
1757
1758       // now convert them to our format
1759       num_vertices=0;
1760       sx = sy = cx = cy = scx = scy = 0;
1761       for (i=0; i < n; ++i) {
1762          flags = vertices[off+i].type;
1763          x     = (stbtt_int16) vertices[off+i].x;
1764          y     = (stbtt_int16) vertices[off+i].y;
1765
1766          if (next_move == i) {
1767             if (i != 0)
1768                num_vertices = stbtt__close_shape(vertices, num_vertices, was_off, start_off, sx,sy,scx,scy,cx,cy);
1769
1770             // now start the new one
1771             start_off = !(flags & 1);
1772             if (start_off) {
1773                // if we start off with an off-curve point, then when we need to find a point on the curve
1774                // where we can start, and we need to save some state for when we wraparound.
1775                scx = x;
1776                scy = y;
1777                if (!(vertices[off+i+1].type & 1)) {
1778                   // next point is also a curve point, so interpolate an on-point curve
1779                   sx = (x + (stbtt_int32) vertices[off+i+1].x) >> 1;
1780                   sy = (y + (stbtt_int32) vertices[off+i+1].y) >> 1;
1781                } else {
1782                   // otherwise just use the next point as our start point
1783                   sx = (stbtt_int32) vertices[off+i+1].x;
1784                   sy = (stbtt_int32) vertices[off+i+1].y;
1785                   ++i; // we're using point i+1 as the starting point, so skip it
1786                }
1787             } else {
1788                sx = x;
1789                sy = y;
1790             }
1791             stbtt_setvertex(&vertices[num_vertices++], STBTT_vmove,sx,sy,0,0);
1792             was_off = 0;
1793             next_move = 1 + ttUSHORT(endPtsOfContours+j*2);
1794             ++j;
1795          } else {
1796             if (!(flags & 1)) { // if it's a curve
1797                if (was_off) // two off-curve control points in a row means interpolate an on-curve midpoint
1798                   stbtt_setvertex(&vertices[num_vertices++], STBTT_vcurve, (cx+x)>>1, (cy+y)>>1, cx, cy);
1799                cx = x;
1800                cy = y;
1801                was_off = 1;
1802             } else {
1803                if (was_off)
1804                   stbtt_setvertex(&vertices[num_vertices++], STBTT_vcurve, x,y, cx, cy);
1805                else
1806                   stbtt_setvertex(&vertices[num_vertices++], STBTT_vline, x,y,0,0);
1807                was_off = 0;
1808             }
1809          }
1810       }
1811       num_vertices = stbtt__close_shape(vertices, num_vertices, was_off, start_off, sx,sy,scx,scy,cx,cy);
1812    } else if (numberOfContours < 0) {
1813       // Compound shapes.
1814       int more = 1;
1815       stbtt_uint8 *comp = data + g + 10;
1816       num_vertices = 0;
1817       vertices = 0;
1818       while (more) {
1819          stbtt_uint16 flags, gidx;
1820          int comp_num_verts = 0, i;
1821          stbtt_vertex *comp_verts = 0, *tmp = 0;
1822          float mtx[6] = {1,0,0,1,0,0}, m, n;
1823
1824          flags = ttSHORT(comp); comp+=2;
1825          gidx = ttSHORT(comp); comp+=2;
1826
1827          if (flags & 2) { // XY values
1828             if (flags & 1) { // shorts
1829                mtx[4] = ttSHORT(comp); comp+=2;
1830                mtx[5] = ttSHORT(comp); comp+=2;
1831             } else {
1832                mtx[4] = ttCHAR(comp); comp+=1;
1833                mtx[5] = ttCHAR(comp); comp+=1;
1834             }
1835          }
1836          else {
1837             // @TODO handle matching point
1838             STBTT_assert(0);
1839          }
1840          if (flags & (1<<3)) { // WE_HAVE_A_SCALE
1841             mtx[0] = mtx[3] = ttSHORT(comp)/16384.0f; comp+=2;
1842             mtx[1] = mtx[2] = 0;
1843          } else if (flags & (1<<6)) { // WE_HAVE_AN_X_AND_YSCALE
1844             mtx[0] = ttSHORT(comp)/16384.0f; comp+=2;
1845             mtx[1] = mtx[2] = 0;
1846             mtx[3] = ttSHORT(comp)/16384.0f; comp+=2;
1847          } else if (flags & (1<<7)) { // WE_HAVE_A_TWO_BY_TWO
1848             mtx[0] = ttSHORT(comp)/16384.0f; comp+=2;
1849             mtx[1] = ttSHORT(comp)/16384.0f; comp+=2;
1850             mtx[2] = ttSHORT(comp)/16384.0f; comp+=2;
1851             mtx[3] = ttSHORT(comp)/16384.0f; comp+=2;
1852          }
1853
1854          // Find transformation scales.
1855          m = (float) STBTT_sqrt(mtx[0]*mtx[0] + mtx[1]*mtx[1]);
1856          n = (float) STBTT_sqrt(mtx[2]*mtx[2] + mtx[3]*mtx[3]);
1857
1858          // Get indexed glyph.
1859          comp_num_verts = stbtt_GetGlyphShape(info, gidx, &comp_verts);
1860          if (comp_num_verts > 0) {
1861             // Transform vertices.
1862             for (i = 0; i < comp_num_verts; ++i) {
1863                stbtt_vertex* v = &comp_verts[i];
1864                stbtt_vertex_type x,y;
1865                x=v->x; y=v->y;
1866                v->x = (stbtt_vertex_type)(m * (mtx[0]*x + mtx[2]*y + mtx[4]));
1867                v->y = (stbtt_vertex_type)(n * (mtx[1]*x + mtx[3]*y + mtx[5]));
1868                x=v->cx; y=v->cy;
1869                v->cx = (stbtt_vertex_type)(m * (mtx[0]*x + mtx[2]*y + mtx[4]));
1870                v->cy = (stbtt_vertex_type)(n * (mtx[1]*x + mtx[3]*y + mtx[5]));
1871             }
1872             // Append vertices.
1873             tmp = (stbtt_vertex*)STBTT_malloc((num_vertices+comp_num_verts)*sizeof(stbtt_vertex), info->userdata);
1874             if (!tmp) {
1875                if (vertices) STBTT_free(vertices, info->userdata);
1876                if (comp_verts) STBTT_free(comp_verts, info->userdata);
1877                return 0;
1878             }
1879             if (num_vertices > 0 && vertices) STBTT_memcpy(tmp, vertices, num_vertices*sizeof(stbtt_vertex));
1880             STBTT_memcpy(tmp+num_vertices, comp_verts, comp_num_verts*sizeof(stbtt_vertex));
1881             if (vertices) STBTT_free(vertices, info->userdata);
1882             vertices = tmp;
1883             STBTT_free(comp_verts, info->userdata);
1884             num_vertices += comp_num_verts;
1885          }
1886          // More components ?
1887          more = flags & (1<<5);
1888       }
1889    } else {
1890       // numberOfCounters == 0, do nothing
1891    }
1892
1893    *pvertices = vertices;
1894    return num_vertices;
1895 }
1896
1897 typedef struct
1898 {
1899    int bounds;
1900    int started;
1901    float first_x, first_y;
1902    float x, y;
1903    stbtt_int32 min_x, max_x, min_y, max_y;
1904
1905    stbtt_vertex *pvertices;
1906    int num_vertices;
1907 } stbtt__csctx;
1908
1909 #define STBTT__CSCTX_INIT(bounds) {bounds,0, 0,0, 0,0, 0,0,0,0, NULL, 0}
1910
1911 static void stbtt__track_vertex(stbtt__csctx *c, stbtt_int32 x, stbtt_int32 y)
1912 {
1913    if (x > c->max_x || !c->started) c->max_x = x;
1914    if (y > c->max_y || !c->started) c->max_y = y;
1915    if (x < c->min_x || !c->started) c->min_x = x;
1916    if (y < c->min_y || !c->started) c->min_y = y;
1917    c->started = 1;
1918 }
1919
1920 static void stbtt__csctx_v(stbtt__csctx *c, stbtt_uint8 type, stbtt_int32 x, stbtt_int32 y, stbtt_int32 cx, stbtt_int32 cy, stbtt_int32 cx1, stbtt_int32 cy1)
1921 {
1922    if (c->bounds) {
1923       stbtt__track_vertex(c, x, y);
1924       if (type == STBTT_vcubic) {
1925          stbtt__track_vertex(c, cx, cy);
1926          stbtt__track_vertex(c, cx1, cy1);
1927       }
1928    } else {
1929       stbtt_setvertex(&c->pvertices[c->num_vertices], type, x, y, cx, cy);
1930       c->pvertices[c->num_vertices].cx1 = (stbtt_int16) cx1;
1931       c->pvertices[c->num_vertices].cy1 = (stbtt_int16) cy1;
1932    }
1933    c->num_vertices++;
1934 }
1935
1936 static void stbtt__csctx_close_shape(stbtt__csctx *ctx)
1937 {
1938    if (ctx->first_x != ctx->x || ctx->first_y != ctx->y)
1939       stbtt__csctx_v(ctx, STBTT_vline, (int)ctx->first_x, (int)ctx->first_y, 0, 0, 0, 0);
1940 }
1941
1942 static void stbtt__csctx_rmove_to(stbtt__csctx *ctx, float dx, float dy)
1943 {
1944    stbtt__csctx_close_shape(ctx);
1945    ctx->first_x = ctx->x = ctx->x + dx;
1946    ctx->first_y = ctx->y = ctx->y + dy;
1947    stbtt__csctx_v(ctx, STBTT_vmove, (int)ctx->x, (int)ctx->y, 0, 0, 0, 0);
1948 }
1949
1950 static void stbtt__csctx_rline_to(stbtt__csctx *ctx, float dx, float dy)
1951 {
1952    ctx->x += dx;
1953    ctx->y += dy;
1954    stbtt__csctx_v(ctx, STBTT_vline, (int)ctx->x, (int)ctx->y, 0, 0, 0, 0);
1955 }
1956
1957 static void stbtt__csctx_rccurve_to(stbtt__csctx *ctx, float dx1, float dy1, float dx2, float dy2, float dx3, float dy3)
1958 {
1959    float cx1 = ctx->x + dx1;
1960    float cy1 = ctx->y + dy1;
1961    float cx2 = cx1 + dx2;
1962    float cy2 = cy1 + dy2;
1963    ctx->x = cx2 + dx3;
1964    ctx->y = cy2 + dy3;
1965    stbtt__csctx_v(ctx, STBTT_vcubic, (int)ctx->x, (int)ctx->y, (int)cx1, (int)cy1, (int)cx2, (int)cy2);
1966 }
1967
1968 static stbtt__buf stbtt__get_subr(stbtt__buf idx, int n)
1969 {
1970    int count = stbtt__cff_index_count(&idx);
1971    int bias = 107;
1972    if (count >= 33900)
1973       bias = 32768;
1974    else if (count >= 1240)
1975       bias = 1131;
1976    n += bias;
1977    if (n < 0 || n >= count)
1978       return stbtt__new_buf(NULL, 0);
1979    return stbtt__cff_index_get(idx, n);
1980 }
1981
1982 static stbtt__buf stbtt__cid_get_glyph_subrs(const stbtt_fontinfo *info, int glyph_index)
1983 {
1984    stbtt__buf fdselect = info->fdselect;
1985    int nranges, start, end, v, fmt, fdselector = -1, i;
1986
1987    stbtt__buf_seek(&fdselect, 0);
1988    fmt = stbtt__buf_get8(&fdselect);
1989    if (fmt == 0) {
1990       // untested
1991       stbtt__buf_skip(&fdselect, glyph_index);
1992       fdselector = stbtt__buf_get8(&fdselect);
1993    } else if (fmt == 3) {
1994       nranges = stbtt__buf_get16(&fdselect);
1995       start = stbtt__buf_get16(&fdselect);
1996       for (i = 0; i < nranges; i++) {
1997          v = stbtt__buf_get8(&fdselect);
1998          end = stbtt__buf_get16(&fdselect);
1999          if (glyph_index >= start && glyph_index < end) {
2000             fdselector = v;
2001             break;
2002          }
2003          start = end;
2004       }
2005    }
2006    if (fdselector == -1) stbtt__new_buf(NULL, 0);
2007    return stbtt__get_subrs(info->cff, stbtt__cff_index_get(info->fontdicts, fdselector));
2008 }
2009
2010 static int stbtt__run_charstring(const stbtt_fontinfo *info, int glyph_index, stbtt__csctx *c)
2011 {
2012    int in_header = 1, maskbits = 0, subr_stack_height = 0, sp = 0, v, i, b0;
2013    int has_subrs = 0, clear_stack;
2014    float s[48];
2015    stbtt__buf subr_stack[10], subrs = info->subrs, b;
2016    float f;
2017
2018 #define STBTT__CSERR(s) (0)
2019
2020    // this currently ignores the initial width value, which isn't needed if we have hmtx
2021    b = stbtt__cff_index_get(info->charstrings, glyph_index);
2022    while (b.cursor < b.size) {
2023       i = 0;
2024       clear_stack = 1;
2025       b0 = stbtt__buf_get8(&b);
2026       switch (b0) {
2027       // @TODO implement hinting
2028       case 0x13: // hintmask
2029       case 0x14: // cntrmask
2030          if (in_header)
2031             maskbits += (sp / 2); // implicit "vstem"
2032          in_header = 0;
2033          stbtt__buf_skip(&b, (maskbits + 7) / 8);
2034          break;
2035
2036       case 0x01: // hstem
2037       case 0x03: // vstem
2038       case 0x12: // hstemhm
2039       case 0x17: // vstemhm
2040          maskbits += (sp / 2);
2041          break;
2042
2043       case 0x15: // rmoveto
2044          in_header = 0;
2045          if (sp < 2) return STBTT__CSERR("rmoveto stack");
2046          stbtt__csctx_rmove_to(c, s[sp-2], s[sp-1]);
2047          break;
2048       case 0x04: // vmoveto
2049          in_header = 0;
2050          if (sp < 1) return STBTT__CSERR("vmoveto stack");
2051          stbtt__csctx_rmove_to(c, 0, s[sp-1]);
2052          break;
2053       case 0x16: // hmoveto
2054          in_header = 0;
2055          if (sp < 1) return STBTT__CSERR("hmoveto stack");
2056          stbtt__csctx_rmove_to(c, s[sp-1], 0);
2057          break;
2058
2059       case 0x05: // rlineto
2060          if (sp < 2) return STBTT__CSERR("rlineto stack");
2061          for (; i + 1 < sp; i += 2)
2062             stbtt__csctx_rline_to(c, s[i], s[i+1]);
2063          break;
2064
2065       // hlineto/vlineto and vhcurveto/hvcurveto alternate horizontal and vertical
2066       // starting from a different place.
2067
2068       case 0x07: // vlineto
2069          if (sp < 1) return STBTT__CSERR("vlineto stack");
2070          goto vlineto;
2071       case 0x06: // hlineto
2072          if (sp < 1) return STBTT__CSERR("hlineto stack");
2073          for (;;) {
2074             if (i >= sp) break;
2075             stbtt__csctx_rline_to(c, s[i], 0);
2076             i++;
2077       vlineto:
2078             if (i >= sp) break;
2079             stbtt__csctx_rline_to(c, 0, s[i]);
2080             i++;
2081          }
2082          break;
2083
2084       case 0x1F: // hvcurveto
2085          if (sp < 4) return STBTT__CSERR("hvcurveto stack");
2086          goto hvcurveto;
2087       case 0x1E: // vhcurveto
2088          if (sp < 4) return STBTT__CSERR("vhcurveto stack");
2089          for (;;) {
2090             if (i + 3 >= sp) break;
2091             stbtt__csctx_rccurve_to(c, 0, s[i], s[i+1], s[i+2], s[i+3], (sp - i == 5) ? s[i + 4] : 0.0f);
2092             i += 4;
2093       hvcurveto:
2094             if (i + 3 >= sp) break;
2095             stbtt__csctx_rccurve_to(c, s[i], 0, s[i+1], s[i+2], (sp - i == 5) ? s[i+4] : 0.0f, s[i+3]);
2096             i += 4;
2097          }
2098          break;
2099
2100       case 0x08: // rrcurveto
2101          if (sp < 6) return STBTT__CSERR("rcurveline stack");
2102          for (; i + 5 < sp; i += 6)
2103             stbtt__csctx_rccurve_to(c, s[i], s[i+1], s[i+2], s[i+3], s[i+4], s[i+5]);
2104          break;
2105
2106       case 0x18: // rcurveline
2107          if (sp < 8) return STBTT__CSERR("rcurveline stack");
2108          for (; i + 5 < sp - 2; i += 6)
2109             stbtt__csctx_rccurve_to(c, s[i], s[i+1], s[i+2], s[i+3], s[i+4], s[i+5]);
2110          if (i + 1 >= sp) return STBTT__CSERR("rcurveline stack");
2111          stbtt__csctx_rline_to(c, s[i], s[i+1]);
2112          break;
2113
2114       case 0x19: // rlinecurve
2115          if (sp < 8) return STBTT__CSERR("rlinecurve stack");
2116          for (; i + 1 < sp - 6; i += 2)
2117             stbtt__csctx_rline_to(c, s[i], s[i+1]);
2118          if (i + 5 >= sp) return STBTT__CSERR("rlinecurve stack");
2119          stbtt__csctx_rccurve_to(c, s[i], s[i+1], s[i+2], s[i+3], s[i+4], s[i+5]);
2120          break;
2121
2122       case 0x1A: // vvcurveto
2123       case 0x1B: // hhcurveto
2124          if (sp < 4) return STBTT__CSERR("(vv|hh)curveto stack");
2125          f = 0.0;
2126          if (sp & 1) { f = s[i]; i++; }
2127          for (; i + 3 < sp; i += 4) {
2128             if (b0 == 0x1B)
2129                stbtt__csctx_rccurve_to(c, s[i], f, s[i+1], s[i+2], s[i+3], 0.0);
2130             else
2131                stbtt__csctx_rccurve_to(c, f, s[i], s[i+1], s[i+2], 0.0, s[i+3]);
2132             f = 0.0;
2133          }
2134          break;
2135
2136       case 0x0A: // callsubr
2137          if (!has_subrs) {
2138             if (info->fdselect.size)
2139                subrs = stbtt__cid_get_glyph_subrs(info, glyph_index);
2140             has_subrs = 1;
2141          }
2142          // FALLTHROUGH
2143       case 0x1D: // callgsubr
2144          if (sp < 1) return STBTT__CSERR("call(g|)subr stack");
2145          v = (int) s[--sp];
2146          if (subr_stack_height >= 10) return STBTT__CSERR("recursion limit");
2147          subr_stack[subr_stack_height++] = b;
2148          b = stbtt__get_subr(b0 == 0x0A ? subrs : info->gsubrs, v);
2149          if (b.size == 0) return STBTT__CSERR("subr not found");
2150          b.cursor = 0;
2151          clear_stack = 0;
2152          break;
2153
2154       case 0x0B: // return
2155          if (subr_stack_height <= 0) return STBTT__CSERR("return outside subr");
2156          b = subr_stack[--subr_stack_height];
2157          clear_stack = 0;
2158          break;
2159
2160       case 0x0E: // endchar
2161          stbtt__csctx_close_shape(c);
2162          return 1;
2163
2164       case 0x0C: { // two-byte escape
2165          float dx1, dx2, dx3, dx4, dx5, dx6, dy1, dy2, dy3, dy4, dy5, dy6;
2166          float dx, dy;
2167          int b1 = stbtt__buf_get8(&b);
2168          switch (b1) {
2169          // @TODO These "flex" implementations ignore the flex-depth and resolution,
2170          // and always draw beziers.
2171          case 0x22: // hflex
2172             if (sp < 7) return STBTT__CSERR("hflex stack");
2173             dx1 = s[0];
2174             dx2 = s[1];
2175             dy2 = s[2];
2176             dx3 = s[3];
2177             dx4 = s[4];
2178             dx5 = s[5];
2179             dx6 = s[6];
2180             stbtt__csctx_rccurve_to(c, dx1, 0, dx2, dy2, dx3, 0);
2181             stbtt__csctx_rccurve_to(c, dx4, 0, dx5, -dy2, dx6, 0);
2182             break;
2183
2184          case 0x23: // flex
2185             if (sp < 13) return STBTT__CSERR("flex stack");
2186             dx1 = s[0];
2187             dy1 = s[1];
2188             dx2 = s[2];
2189             dy2 = s[3];
2190             dx3 = s[4];
2191             dy3 = s[5];
2192             dx4 = s[6];
2193             dy4 = s[7];
2194             dx5 = s[8];
2195             dy5 = s[9];
2196             dx6 = s[10];
2197             dy6 = s[11];
2198             //fd is s[12]
2199             stbtt__csctx_rccurve_to(c, dx1, dy1, dx2, dy2, dx3, dy3);
2200             stbtt__csctx_rccurve_to(c, dx4, dy4, dx5, dy5, dx6, dy6);
2201             break;
2202
2203          case 0x24: // hflex1
2204             if (sp < 9) return STBTT__CSERR("hflex1 stack");
2205             dx1 = s[0];
2206             dy1 = s[1];
2207             dx2 = s[2];
2208             dy2 = s[3];
2209             dx3 = s[4];
2210             dx4 = s[5];
2211             dx5 = s[6];
2212             dy5 = s[7];
2213             dx6 = s[8];
2214             stbtt__csctx_rccurve_to(c, dx1, dy1, dx2, dy2, dx3, 0);
2215             stbtt__csctx_rccurve_to(c, dx4, 0, dx5, dy5, dx6, -(dy1+dy2+dy5));
2216             break;
2217
2218          case 0x25: // flex1
2219             if (sp < 11) return STBTT__CSERR("flex1 stack");
2220             dx1 = s[0];
2221             dy1 = s[1];
2222             dx2 = s[2];
2223             dy2 = s[3];
2224             dx3 = s[4];
2225             dy3 = s[5];
2226             dx4 = s[6];
2227             dy4 = s[7];
2228             dx5 = s[8];
2229             dy5 = s[9];
2230             dx6 = dy6 = s[10];
2231             dx = dx1+dx2+dx3+dx4+dx5;
2232             dy = dy1+dy2+dy3+dy4+dy5;
2233             if (STBTT_fabs(dx) > STBTT_fabs(dy))
2234                dy6 = -dy;
2235             else
2236                dx6 = -dx;
2237             stbtt__csctx_rccurve_to(c, dx1, dy1, dx2, dy2, dx3, dy3);
2238             stbtt__csctx_rccurve_to(c, dx4, dy4, dx5, dy5, dx6, dy6);
2239             break;
2240
2241          default:
2242             return STBTT__CSERR("unimplemented");
2243          }
2244       } break;
2245
2246       default:
2247          if (b0 != 255 && b0 != 28 && b0 < 32)
2248             return STBTT__CSERR("reserved operator");
2249
2250          // push immediate
2251          if (b0 == 255) {
2252             f = (float)(stbtt_int32)stbtt__buf_get32(&b) / 0x10000;
2253          } else {
2254             stbtt__buf_skip(&b, -1);
2255             f = (float)(stbtt_int16)stbtt__cff_int(&b);
2256          }
2257          if (sp >= 48) return STBTT__CSERR("push stack overflow");
2258          s[sp++] = f;
2259          clear_stack = 0;
2260          break;
2261       }
2262       if (clear_stack) sp = 0;
2263    }
2264    return STBTT__CSERR("no endchar");
2265
2266 #undef STBTT__CSERR
2267 }
2268
2269 static int stbtt__GetGlyphShapeT2(const stbtt_fontinfo *info, int glyph_index, stbtt_vertex **pvertices)
2270 {
2271    // runs the charstring twice, once to count and once to output (to avoid realloc)
2272    stbtt__csctx count_ctx = STBTT__CSCTX_INIT(1);
2273    stbtt__csctx output_ctx = STBTT__CSCTX_INIT(0);
2274    if (stbtt__run_charstring(info, glyph_index, &count_ctx)) {
2275       *pvertices = (stbtt_vertex*)STBTT_malloc(count_ctx.num_vertices*sizeof(stbtt_vertex), info->userdata);
2276       output_ctx.pvertices = *pvertices;
2277       if (stbtt__run_charstring(info, glyph_index, &output_ctx)) {
2278          STBTT_assert(output_ctx.num_vertices == count_ctx.num_vertices);
2279          return output_ctx.num_vertices;
2280       }
2281    }
2282    *pvertices = NULL;
2283    return 0;
2284 }
2285
2286 static int stbtt__GetGlyphInfoT2(const stbtt_fontinfo *info, int glyph_index, int *x0, int *y0, int *x1, int *y1)
2287 {
2288    stbtt__csctx c = STBTT__CSCTX_INIT(1);
2289    int r = stbtt__run_charstring(info, glyph_index, &c);
2290    if (x0)  *x0 = r ? c.min_x : 0;
2291    if (y0)  *y0 = r ? c.min_y : 0;
2292    if (x1)  *x1 = r ? c.max_x : 0;
2293    if (y1)  *y1 = r ? c.max_y : 0;
2294    return r ? c.num_vertices : 0;
2295 }
2296
2297 STBTT_DEF int stbtt_GetGlyphShape(const stbtt_fontinfo *info, int glyph_index, stbtt_vertex **pvertices)
2298 {
2299    if (!info->cff.size)
2300       return stbtt__GetGlyphShapeTT(info, glyph_index, pvertices);
2301    else
2302       return stbtt__GetGlyphShapeT2(info, glyph_index, pvertices);
2303 }
2304
2305 STBTT_DEF void stbtt_GetGlyphHMetrics(const stbtt_fontinfo *info, int glyph_index, int *advanceWidth, int *leftSideBearing)
2306 {
2307    stbtt_uint16 numOfLongHorMetrics = ttUSHORT(info->data+info->hhea + 34);
2308    if (glyph_index < numOfLongHorMetrics) {
2309       if (advanceWidth)     *advanceWidth    = ttSHORT(info->data + info->hmtx + 4*glyph_index);
2310       if (leftSideBearing)  *leftSideBearing = ttSHORT(info->data + info->hmtx + 4*glyph_index + 2);
2311    } else {
2312       if (advanceWidth)     *advanceWidth    = ttSHORT(info->data + info->hmtx + 4*(numOfLongHorMetrics-1));
2313       if (leftSideBearing)  *leftSideBearing = ttSHORT(info->data + info->hmtx + 4*numOfLongHorMetrics + 2*(glyph_index - numOfLongHorMetrics));
2314    }
2315 }
2316
2317 STBTT_DEF int  stbtt_GetKerningTableLength(const stbtt_fontinfo *info)
2318 {
2319    stbtt_uint8 *data = info->data + info->kern;
2320
2321    // we only look at the first table. it must be 'horizontal' and format 0.
2322    if (!info->kern)
2323       return 0;
2324    if (ttUSHORT(data+2) < 1) // number of tables, need at least 1
2325       return 0;
2326    if (ttUSHORT(data+8) != 1) // horizontal flag must be set in format
2327       return 0;
2328
2329    return ttUSHORT(data+10);
2330 }
2331
2332 STBTT_DEF int stbtt_GetKerningTable(const stbtt_fontinfo *info, stbtt_kerningentry* table, int table_length)
2333 {
2334    stbtt_uint8 *data = info->data + info->kern;
2335    int k, length;
2336
2337    // we only look at the first table. it must be 'horizontal' and format 0.
2338    if (!info->kern)
2339       return 0;
2340    if (ttUSHORT(data+2) < 1) // number of tables, need at least 1
2341       return 0;
2342    if (ttUSHORT(data+8) != 1) // horizontal flag must be set in format
2343       return 0;
2344
2345    length = ttUSHORT(data+10);
2346    if (table_length < length)
2347       length = table_length;
2348
2349    for (k = 0; k < length; k++)
2350    {
2351       table[k].glyph1 = ttUSHORT(data+18+(k*6));
2352       table[k].glyph2 = ttUSHORT(data+20+(k*6));
2353       table[k].advance = ttSHORT(data+22+(k*6));
2354    }
2355
2356    return length;
2357 }
2358
2359 static int stbtt__GetGlyphKernInfoAdvance(const stbtt_fontinfo *info, int glyph1, int glyph2)
2360 {
2361    stbtt_uint8 *data = info->data + info->kern;
2362    stbtt_uint32 needle, straw;
2363    int l, r, m;
2364
2365    // we only look at the first table. it must be 'horizontal' and format 0.
2366    if (!info->kern)
2367       return 0;
2368    if (ttUSHORT(data+2) < 1) // number of tables, need at least 1
2369       return 0;
2370    if (ttUSHORT(data+8) != 1) // horizontal flag must be set in format
2371       return 0;
2372
2373    l = 0;
2374    r = ttUSHORT(data+10) - 1;
2375    needle = glyph1 << 16 | glyph2;
2376    while (l <= r) {
2377       m = (l + r) >> 1;
2378       straw = ttULONG(data+18+(m*6)); // note: unaligned read
2379       if (needle < straw)
2380          r = m - 1;
2381       else if (needle > straw)
2382          l = m + 1;
2383       else
2384          return ttSHORT(data+22+(m*6));
2385    }
2386    return 0;
2387 }
2388
2389 static stbtt_int32 stbtt__GetCoverageIndex(stbtt_uint8 *coverageTable, int glyph)
2390 {
2391    stbtt_uint16 coverageFormat = ttUSHORT(coverageTable);
2392    switch (coverageFormat) {
2393       case 1: {
2394          stbtt_uint16 glyphCount = ttUSHORT(coverageTable + 2);
2395
2396          // Binary search.
2397          stbtt_int32 l=0, r=glyphCount-1, m;
2398          int straw, needle=glyph;
2399          while (l <= r) {
2400             stbtt_uint8 *glyphArray = coverageTable + 4;
2401             stbtt_uint16 glyphID;
2402             m = (l + r) >> 1;
2403             glyphID = ttUSHORT(glyphArray + 2 * m);
2404             straw = glyphID;
2405             if (needle < straw)
2406                r = m - 1;
2407             else if (needle > straw)
2408                l = m + 1;
2409             else {
2410                return m;
2411             }
2412          }
2413          break;
2414       }
2415
2416       case 2: {
2417          stbtt_uint16 rangeCount = ttUSHORT(coverageTable + 2);
2418          stbtt_uint8 *rangeArray = coverageTable + 4;
2419
2420          // Binary search.
2421          stbtt_int32 l=0, r=rangeCount-1, m;
2422          int strawStart, strawEnd, needle=glyph;
2423          while (l <= r) {
2424             stbtt_uint8 *rangeRecord;
2425             m = (l + r) >> 1;
2426             rangeRecord = rangeArray + 6 * m;
2427             strawStart = ttUSHORT(rangeRecord);
2428             strawEnd = ttUSHORT(rangeRecord + 2);
2429             if (needle < strawStart)
2430                r = m - 1;
2431             else if (needle > strawEnd)
2432                l = m + 1;
2433             else {
2434                stbtt_uint16 startCoverageIndex = ttUSHORT(rangeRecord + 4);
2435                return startCoverageIndex + glyph - strawStart;
2436             }
2437          }
2438          break;
2439       }
2440
2441       default: return -1; // unsupported
2442    }
2443
2444    return -1;
2445 }
2446
2447 static stbtt_int32  stbtt__GetGlyphClass(stbtt_uint8 *classDefTable, int glyph)
2448 {
2449    stbtt_uint16 classDefFormat = ttUSHORT(classDefTable);
2450    switch (classDefFormat)
2451    {
2452       case 1: {
2453          stbtt_uint16 startGlyphID = ttUSHORT(classDefTable + 2);
2454          stbtt_uint16 glyphCount = ttUSHORT(classDefTable + 4);
2455          stbtt_uint8 *classDef1ValueArray = classDefTable + 6;
2456
2457          if (glyph >= startGlyphID && glyph < startGlyphID + glyphCount)
2458             return (stbtt_int32)ttUSHORT(classDef1ValueArray + 2 * (glyph - startGlyphID));
2459          break;
2460       }
2461
2462       case 2: {
2463          stbtt_uint16 classRangeCount = ttUSHORT(classDefTable + 2);
2464          stbtt_uint8 *classRangeRecords = classDefTable + 4;
2465
2466          // Binary search.
2467          stbtt_int32 l=0, r=classRangeCount-1, m;
2468          int strawStart, strawEnd, needle=glyph;
2469          while (l <= r) {
2470             stbtt_uint8 *classRangeRecord;
2471             m = (l + r) >> 1;
2472             classRangeRecord = classRangeRecords + 6 * m;
2473             strawStart = ttUSHORT(classRangeRecord);
2474             strawEnd = ttUSHORT(classRangeRecord + 2);
2475             if (needle < strawStart)
2476                r = m - 1;
2477             else if (needle > strawEnd)
2478                l = m + 1;
2479             else
2480                return (stbtt_int32)ttUSHORT(classRangeRecord + 4);
2481          }
2482          break;
2483       }
2484
2485       default:
2486          return -1; // Unsupported definition type, return an error.
2487    }
2488
2489    // "All glyphs not assigned to a class fall into class 0". (OpenType spec)
2490    return 0;
2491 }
2492
2493 // Define to STBTT_assert(x) if you want to break on unimplemented formats.
2494 #define STBTT_GPOS_TODO_assert(x)
2495
2496 static stbtt_int32 stbtt__GetGlyphGPOSInfoAdvance(const stbtt_fontinfo *info, int glyph1, int glyph2)
2497 {
2498    stbtt_uint16 lookupListOffset;
2499    stbtt_uint8 *lookupList;
2500    stbtt_uint16 lookupCount;
2501    stbtt_uint8 *data;
2502    stbtt_int32 i, sti;
2503
2504    if (!info->gpos) return 0;
2505
2506    data = info->data + info->gpos;
2507
2508    if (ttUSHORT(data+0) != 1) return 0; // Major version 1
2509    if (ttUSHORT(data+2) != 0) return 0; // Minor version 0
2510
2511    lookupListOffset = ttUSHORT(data+8);
2512    lookupList = data + lookupListOffset;
2513    lookupCount = ttUSHORT(lookupList);
2514
2515    for (i=0; i<lookupCount; ++i) {
2516       stbtt_uint16 lookupOffset = ttUSHORT(lookupList + 2 + 2 * i);
2517       stbtt_uint8 *lookupTable = lookupList + lookupOffset;
2518
2519       stbtt_uint16 lookupType = ttUSHORT(lookupTable);
2520       stbtt_uint16 subTableCount = ttUSHORT(lookupTable + 4);
2521       stbtt_uint8 *subTableOffsets = lookupTable + 6;
2522       if (lookupType != 2) // Pair Adjustment Positioning Subtable
2523          continue;
2524
2525       for (sti=0; sti<subTableCount; sti++) {
2526          stbtt_uint16 subtableOffset = ttUSHORT(subTableOffsets + 2 * sti);
2527          stbtt_uint8 *table = lookupTable + subtableOffset;
2528          stbtt_uint16 posFormat = ttUSHORT(table);
2529          stbtt_uint16 coverageOffset = ttUSHORT(table + 2);
2530          stbtt_int32 coverageIndex = stbtt__GetCoverageIndex(table + coverageOffset, glyph1);
2531          if (coverageIndex == -1) continue;
2532
2533          switch (posFormat) {
2534             case 1: {
2535                stbtt_int32 l, r, m;
2536                int straw, needle;
2537                stbtt_uint16 valueFormat1 = ttUSHORT(table + 4);
2538                stbtt_uint16 valueFormat2 = ttUSHORT(table + 6);
2539                if (valueFormat1 == 4 && valueFormat2 == 0) { // Support more formats?
2540                   stbtt_int32 valueRecordPairSizeInBytes = 2;
2541                   stbtt_uint16 pairSetCount = ttUSHORT(table + 8);
2542                   stbtt_uint16 pairPosOffset = ttUSHORT(table + 10 + 2 * coverageIndex);
2543                   stbtt_uint8 *pairValueTable = table + pairPosOffset;
2544                   stbtt_uint16 pairValueCount = ttUSHORT(pairValueTable);
2545                   stbtt_uint8 *pairValueArray = pairValueTable + 2;
2546
2547                   if (coverageIndex >= pairSetCount) return 0;
2548
2549                   needle=glyph2;
2550                   r=pairValueCount-1;
2551                   l=0;
2552
2553                   // Binary search.
2554                   while (l <= r) {
2555                      stbtt_uint16 secondGlyph;
2556                      stbtt_uint8 *pairValue;
2557                      m = (l + r) >> 1;
2558                      pairValue = pairValueArray + (2 + valueRecordPairSizeInBytes) * m;
2559                      secondGlyph = ttUSHORT(pairValue);
2560                      straw = secondGlyph;
2561                      if (needle < straw)
2562                         r = m - 1;
2563                      else if (needle > straw)
2564                         l = m + 1;
2565                      else {
2566                         stbtt_int16 xAdvance = ttSHORT(pairValue + 2);
2567                         return xAdvance;
2568                      }
2569                   }
2570                } else
2571                   return 0;
2572                break;
2573             }
2574
2575             case 2: {
2576                stbtt_uint16 valueFormat1 = ttUSHORT(table + 4);
2577                stbtt_uint16 valueFormat2 = ttUSHORT(table + 6);
2578                if (valueFormat1 == 4 && valueFormat2 == 0) { // Support more formats?
2579                   stbtt_uint16 classDef1Offset = ttUSHORT(table + 8);
2580                   stbtt_uint16 classDef2Offset = ttUSHORT(table + 10);
2581                   int glyph1class = stbtt__GetGlyphClass(table + classDef1Offset, glyph1);
2582                   int glyph2class = stbtt__GetGlyphClass(table + classDef2Offset, glyph2);
2583
2584                   stbtt_uint16 class1Count = ttUSHORT(table + 12);
2585                   stbtt_uint16 class2Count = ttUSHORT(table + 14);
2586                   stbtt_uint8 *class1Records, *class2Records;
2587                   stbtt_int16 xAdvance;
2588
2589                   if (glyph1class < 0 || glyph1class >= class1Count) return 0; // malformed
2590                   if (glyph2class < 0 || glyph2class >= class2Count) return 0; // malformed
2591
2592                   class1Records = table + 16;
2593                   class2Records = class1Records + 2 * (glyph1class * class2Count);
2594                   xAdvance = ttSHORT(class2Records + 2 * glyph2class);
2595                   return xAdvance;
2596                } else
2597                   return 0;
2598                break;
2599             }
2600
2601             default:
2602                return 0; // Unsupported position format
2603          }
2604       }
2605    }
2606
2607    return 0;
2608 }
2609
2610 STBTT_DEF int  stbtt_GetGlyphKernAdvance(const stbtt_fontinfo *info, int g1, int g2)
2611 {
2612    int xAdvance = 0;
2613
2614    if (info->gpos)
2615       xAdvance += stbtt__GetGlyphGPOSInfoAdvance(info, g1, g2);
2616    else if (info->kern)
2617       xAdvance += stbtt__GetGlyphKernInfoAdvance(info, g1, g2);
2618
2619    return xAdvance;
2620 }
2621
2622 STBTT_DEF int  stbtt_GetCodepointKernAdvance(const stbtt_fontinfo *info, int ch1, int ch2)
2623 {
2624    if (!info->kern && !info->gpos) // if no kerning table, don't waste time looking up both codepoint->glyphs
2625       return 0;
2626    return stbtt_GetGlyphKernAdvance(info, stbtt_FindGlyphIndex(info,ch1), stbtt_FindGlyphIndex(info,ch2));
2627 }
2628
2629 STBTT_DEF void stbtt_GetCodepointHMetrics(const stbtt_fontinfo *info, int codepoint, int *advanceWidth, int *leftSideBearing)
2630 {
2631    stbtt_GetGlyphHMetrics(info, stbtt_FindGlyphIndex(info,codepoint), advanceWidth, leftSideBearing);
2632 }
2633
2634 STBTT_DEF void stbtt_GetFontVMetrics(const stbtt_fontinfo *info, int *ascent, int *descent, int *lineGap)
2635 {
2636    if (ascent ) *ascent  = ttSHORT(info->data+info->hhea + 4);
2637    if (descent) *descent = ttSHORT(info->data+info->hhea + 6);
2638    if (lineGap) *lineGap = ttSHORT(info->data+info->hhea + 8);
2639 }
2640
2641 STBTT_DEF int  stbtt_GetFontVMetricsOS2(const stbtt_fontinfo *info, int *typoAscent, int *typoDescent, int *typoLineGap)
2642 {
2643    int tab = stbtt__find_table(info->data, info->fontstart, "OS/2");
2644    if (!tab)
2645       return 0;
2646    if (typoAscent ) *typoAscent  = ttSHORT(info->data+tab + 68);
2647    if (typoDescent) *typoDescent = ttSHORT(info->data+tab + 70);
2648    if (typoLineGap) *typoLineGap = ttSHORT(info->data+tab + 72);
2649    return 1;
2650 }
2651
2652 STBTT_DEF void stbtt_GetFontBoundingBox(const stbtt_fontinfo *info, int *x0, int *y0, int *x1, int *y1)
2653 {
2654    *x0 = ttSHORT(info->data + info->head + 36);
2655    *y0 = ttSHORT(info->data + info->head + 38);
2656    *x1 = ttSHORT(info->data + info->head + 40);
2657    *y1 = ttSHORT(info->data + info->head + 42);
2658 }
2659
2660 STBTT_DEF float stbtt_ScaleForPixelHeight(const stbtt_fontinfo *info, float height)
2661 {
2662    int fheight = ttSHORT(info->data + info->hhea + 4) - ttSHORT(info->data + info->hhea + 6);
2663    return (float) height / fheight;
2664 }
2665
2666 STBTT_DEF float stbtt_ScaleForMappingEmToPixels(const stbtt_fontinfo *info, float pixels)
2667 {
2668    int unitsPerEm = ttUSHORT(info->data + info->head + 18);
2669    return pixels / unitsPerEm;
2670 }
2671
2672 STBTT_DEF void stbtt_FreeShape(const stbtt_fontinfo *info, stbtt_vertex *v)
2673 {
2674    STBTT_free(v, info->userdata);
2675 }
2676
2677 STBTT_DEF stbtt_uint8 *stbtt_FindSVGDoc(const stbtt_fontinfo *info, int gl)
2678 {
2679    int i;
2680    stbtt_uint8 *data = info->data;
2681    stbtt_uint8 *svg_doc_list = data + stbtt__get_svg((stbtt_fontinfo *) info);
2682
2683    int numEntries = ttUSHORT(svg_doc_list);
2684    stbtt_uint8 *svg_docs = svg_doc_list + 2;
2685
2686    for(i=0; i<numEntries; i++) {
2687       stbtt_uint8 *svg_doc = svg_docs + (12 * i);
2688       if ((gl >= ttUSHORT(svg_doc)) && (gl <= ttUSHORT(svg_doc + 2)))
2689          return svg_doc;
2690    }
2691    return 0;
2692 }
2693
2694 STBTT_DEF int stbtt_GetGlyphSVG(const stbtt_fontinfo *info, int gl, const char **svg)
2695 {
2696    stbtt_uint8 *data = info->data;
2697    stbtt_uint8 *svg_doc;
2698
2699    if (info->svg == 0)
2700       return 0;
2701
2702    svg_doc = stbtt_FindSVGDoc(info, gl);
2703    if (svg_doc != NULL) {
2704       *svg = (char *) data + info->svg + ttULONG(svg_doc + 4);
2705       return ttULONG(svg_doc + 8);
2706    } else {
2707       return 0;
2708    }
2709 }
2710
2711 STBTT_DEF int stbtt_GetCodepointSVG(const stbtt_fontinfo *info, int unicode_codepoint, const char **svg)
2712 {
2713    return stbtt_GetGlyphSVG(info, stbtt_FindGlyphIndex(info, unicode_codepoint), svg);
2714 }
2715
2716 //////////////////////////////////////////////////////////////////////////////
2717 //
2718 // antialiasing software rasterizer
2719 //
2720
2721 STBTT_DEF void stbtt_GetGlyphBitmapBoxSubpixel(const stbtt_fontinfo *font, int glyph, float scale_x, float scale_y,float shift_x, float shift_y, int *ix0, int *iy0, int *ix1, int *iy1)
2722 {
2723    int x0=0,y0=0,x1,y1; // =0 suppresses compiler warning
2724    if (!stbtt_GetGlyphBox(font, glyph, &x0,&y0,&x1,&y1)) {
2725       // e.g. space character
2726       if (ix0) *ix0 = 0;
2727       if (iy0) *iy0 = 0;
2728       if (ix1) *ix1 = 0;
2729       if (iy1) *iy1 = 0;
2730    } else {
2731       // move to integral bboxes (treating pixels as little squares, what pixels get touched)?
2732       if (ix0) *ix0 = STBTT_ifloor( x0 * scale_x + shift_x);
2733       if (iy0) *iy0 = STBTT_ifloor(-y1 * scale_y + shift_y);
2734       if (ix1) *ix1 = STBTT_iceil ( x1 * scale_x + shift_x);
2735       if (iy1) *iy1 = STBTT_iceil (-y0 * scale_y + shift_y);
2736    }
2737 }
2738
2739 STBTT_DEF void stbtt_GetGlyphBitmapBox(const stbtt_fontinfo *font, int glyph, float scale_x, float scale_y, int *ix0, int *iy0, int *ix1, int *iy1)
2740 {
2741    stbtt_GetGlyphBitmapBoxSubpixel(font, glyph, scale_x, scale_y,0.0f,0.0f, ix0, iy0, ix1, iy1);
2742 }
2743
2744 STBTT_DEF void stbtt_GetCodepointBitmapBoxSubpixel(const stbtt_fontinfo *font, int codepoint, float scale_x, float scale_y, float shift_x, float shift_y, int *ix0, int *iy0, int *ix1, int *iy1)
2745 {
2746    stbtt_GetGlyphBitmapBoxSubpixel(font, stbtt_FindGlyphIndex(font,codepoint), scale_x, scale_y,shift_x,shift_y, ix0,iy0,ix1,iy1);
2747 }
2748
2749 STBTT_DEF void stbtt_GetCodepointBitmapBox(const stbtt_fontinfo *font, int codepoint, float scale_x, float scale_y, int *ix0, int *iy0, int *ix1, int *iy1)
2750 {
2751    stbtt_GetCodepointBitmapBoxSubpixel(font, codepoint, scale_x, scale_y,0.0f,0.0f, ix0,iy0,ix1,iy1);
2752 }
2753
2754 //////////////////////////////////////////////////////////////////////////////
2755 //
2756 //  Rasterizer
2757
2758 typedef struct stbtt__hheap_chunk
2759 {
2760    struct stbtt__hheap_chunk *next;
2761 } stbtt__hheap_chunk;
2762
2763 typedef struct stbtt__hheap
2764 {
2765    struct stbtt__hheap_chunk *head;
2766    void   *first_free;
2767    int    num_remaining_in_head_chunk;
2768 } stbtt__hheap;
2769
2770 static void *stbtt__hheap_alloc(stbtt__hheap *hh, size_t size, void *userdata)
2771 {
2772    if (hh->first_free) {
2773       void *p = hh->first_free;
2774       hh->first_free = * (void **) p;
2775       return p;
2776    } else {
2777       if (hh->num_remaining_in_head_chunk == 0) {
2778          int count = (size < 32 ? 2000 : size < 128 ? 800 : 100);
2779          stbtt__hheap_chunk *c = (stbtt__hheap_chunk *) STBTT_malloc(sizeof(stbtt__hheap_chunk) + size * count, userdata);
2780          if (c == NULL)
2781             return NULL;
2782          c->next = hh->head;
2783          hh->head = c;
2784          hh->num_remaining_in_head_chunk = count;
2785       }
2786       --hh->num_remaining_in_head_chunk;
2787       return (char *) (hh->head) + sizeof(stbtt__hheap_chunk) + size * hh->num_remaining_in_head_chunk;
2788    }
2789 }
2790
2791 static void stbtt__hheap_free(stbtt__hheap *hh, void *p)
2792 {
2793    *(void **) p = hh->first_free;
2794    hh->first_free = p;
2795 }
2796
2797 static void stbtt__hheap_cleanup(stbtt__hheap *hh, void *userdata)
2798 {
2799    stbtt__hheap_chunk *c = hh->head;
2800    while (c) {
2801       stbtt__hheap_chunk *n = c->next;
2802       STBTT_free(c, userdata);
2803       c = n;
2804    }
2805 }
2806
2807 typedef struct stbtt__edge {
2808    float x0,y0, x1,y1;
2809    int invert;
2810 } stbtt__edge;
2811
2812
2813 typedef struct stbtt__active_edge
2814 {
2815    struct stbtt__active_edge *next;
2816    #if STBTT_RASTERIZER_VERSION==1
2817    int x,dx;
2818    float ey;
2819    int direction;
2820    #elif STBTT_RASTERIZER_VERSION==2
2821    float fx,fdx,fdy;
2822    float direction;
2823    float sy;
2824    float ey;
2825    #else
2826    #error "Unrecognized value of STBTT_RASTERIZER_VERSION"
2827    #endif
2828 } stbtt__active_edge;
2829
2830 #if STBTT_RASTERIZER_VERSION == 1
2831 #define STBTT_FIXSHIFT   10
2832 #define STBTT_FIX        (1 << STBTT_FIXSHIFT)
2833 #define STBTT_FIXMASK    (STBTT_FIX-1)
2834
2835 static stbtt__active_edge *stbtt__new_active(stbtt__hheap *hh, stbtt__edge *e, int off_x, float start_point, void *userdata)
2836 {
2837    stbtt__active_edge *z = (stbtt__active_edge *) stbtt__hheap_alloc(hh, sizeof(*z), userdata);
2838    float dxdy = (e->x1 - e->x0) / (e->y1 - e->y0);
2839    STBTT_assert(z != NULL);
2840    if (!z) return z;
2841
2842    // round dx down to avoid overshooting
2843    if (dxdy < 0)
2844       z->dx = -STBTT_ifloor(STBTT_FIX * -dxdy);
2845    else
2846       z->dx = STBTT_ifloor(STBTT_FIX * dxdy);
2847
2848    z->x = STBTT_ifloor(STBTT_FIX * e->x0 + z->dx * (start_point - e->y0)); // use z->dx so when we offset later it's by the same amount
2849    z->x -= off_x * STBTT_FIX;
2850
2851    z->ey = e->y1;
2852    z->next = 0;
2853    z->direction = e->invert ? 1 : -1;
2854    return z;
2855 }
2856 #elif STBTT_RASTERIZER_VERSION == 2
2857 static stbtt__active_edge *stbtt__new_active(stbtt__hheap *hh, stbtt__edge *e, int off_x, float start_point, void *userdata)
2858 {
2859    stbtt__active_edge *z = (stbtt__active_edge *) stbtt__hheap_alloc(hh, sizeof(*z), userdata);
2860    float dxdy = (e->x1 - e->x0) / (e->y1 - e->y0);
2861    STBTT_assert(z != NULL);
2862    //STBTT_assert(e->y0 <= start_point);
2863    if (!z) return z;
2864    z->fdx = dxdy;
2865    z->fdy = dxdy != 0.0f ? (1.0f/dxdy) : 0.0f;
2866    z->fx = e->x0 + dxdy * (start_point - e->y0);
2867    z->fx -= off_x;
2868    z->direction = e->invert ? 1.0f : -1.0f;
2869    z->sy = e->y0;
2870    z->ey = e->y1;
2871    z->next = 0;
2872    return z;
2873 }
2874 #else
2875 #error "Unrecognized value of STBTT_RASTERIZER_VERSION"
2876 #endif
2877
2878 #if STBTT_RASTERIZER_VERSION == 1
2879 // note: this routine clips fills that extend off the edges... ideally this
2880 // wouldn't happen, but it could happen if the truetype glyph bounding boxes
2881 // are wrong, or if the user supplies a too-small bitmap
2882 static void stbtt__fill_active_edges(unsigned char *scanline, int len, stbtt__active_edge *e, int max_weight)
2883 {
2884    // non-zero winding fill
2885    int x0=0, w=0;
2886
2887    while (e) {
2888       if (w == 0) {
2889          // if we're currently at zero, we need to record the edge start point
2890          x0 = e->x; w += e->direction;
2891       } else {
2892          int x1 = e->x; w += e->direction;
2893          // if we went to zero, we need to draw
2894          if (w == 0) {
2895             int i = x0 >> STBTT_FIXSHIFT;
2896             int j = x1 >> STBTT_FIXSHIFT;
2897
2898             if (i < len && j >= 0) {
2899                if (i == j) {
2900                   // x0,x1 are the same pixel, so compute combined coverage
2901                   scanline[i] = scanline[i] + (stbtt_uint8) ((x1 - x0) * max_weight >> STBTT_FIXSHIFT);
2902                } else {
2903                   if (i >= 0) // add antialiasing for x0
2904                      scanline[i] = scanline[i] + (stbtt_uint8) (((STBTT_FIX - (x0 & STBTT_FIXMASK)) * max_weight) >> STBTT_FIXSHIFT);
2905                   else
2906                      i = -1; // clip
2907
2908                   if (j < len) // add antialiasing for x1
2909                      scanline[j] = scanline[j] + (stbtt_uint8) (((x1 & STBTT_FIXMASK) * max_weight) >> STBTT_FIXSHIFT);
2910                   else
2911                      j = len; // clip
2912
2913                   for (++i; i < j; ++i) // fill pixels between x0 and x1
2914                      scanline[i] = scanline[i] + (stbtt_uint8) max_weight;
2915                }
2916             }
2917          }
2918       }
2919
2920       e = e->next;
2921    }
2922 }
2923
2924 static void stbtt__rasterize_sorted_edges(stbtt__bitmap *result, stbtt__edge *e, int n, int vsubsample, int off_x, int off_y, void *userdata)
2925 {
2926    stbtt__hheap hh = { 0, 0, 0 };
2927    stbtt__active_edge *active = NULL;
2928    int y,j=0;
2929    int max_weight = (255 / vsubsample);  // weight per vertical scanline
2930    int s; // vertical subsample index
2931    unsigned char scanline_data[512], *scanline;
2932
2933    if (result->w > 512)
2934       scanline = (unsigned char *) STBTT_malloc(result->w, userdata);
2935    else
2936       scanline = scanline_data;
2937
2938    y = off_y * vsubsample;
2939    e[n].y0 = (off_y + result->h) * (float) vsubsample + 1;
2940
2941    while (j < result->h) {
2942       STBTT_memset(scanline, 0, result->w);
2943       for (s=0; s < vsubsample; ++s) {
2944          // find center of pixel for this scanline
2945          float scan_y = y + 0.5f;
2946          stbtt__active_edge **step = &active;
2947
2948          // update all active edges;
2949          // remove all active edges that terminate before the center of this scanline
2950          while (*step) {
2951             stbtt__active_edge * z = *step;
2952             if (z->ey <= scan_y) {
2953                *step = z->next; // delete from list
2954                STBTT_assert(z->direction);
2955                z->direction = 0;
2956                stbtt__hheap_free(&hh, z);
2957             } else {
2958                z->x += z->dx; // advance to position for current scanline
2959                step = &((*step)->next); // advance through list
2960             }
2961          }
2962
2963          // resort the list if needed
2964          for(;;) {
2965             int changed=0;
2966             step = &active;
2967             while (*step && (*step)->next) {
2968                if ((*step)->x > (*step)->next->x) {
2969                   stbtt__active_edge *t = *step;
2970                   stbtt__active_edge *q = t->next;
2971
2972                   t->next = q->next;
2973                   q->next = t;
2974                   *step = q;
2975                   changed = 1;
2976                }
2977                step = &(*step)->next;
2978             }
2979             if (!changed) break;
2980          }
2981
2982          // insert all edges that start before the center of this scanline -- omit ones that also end on this scanline
2983          while (e->y0 <= scan_y) {
2984             if (e->y1 > scan_y) {
2985                stbtt__active_edge *z = stbtt__new_active(&hh, e, off_x, scan_y, userdata);
2986                if (z != NULL) {
2987                   // find insertion point
2988                   if (active == NULL)
2989                      active = z;
2990                   else if (z->x < active->x) {
2991                      // insert at front
2992                      z->next = active;
2993                      active = z;
2994                   } else {
2995                      // find thing to insert AFTER
2996                      stbtt__active_edge *p = active;
2997                      while (p->next && p->next->x < z->x)
2998                         p = p->next;
2999                      // at this point, p->next->x is NOT < z->x
3000                      z->next = p->next;
3001                      p->next = z;
3002                   }
3003                }
3004             }
3005             ++e;
3006          }
3007
3008          // now process all active edges in XOR fashion
3009          if (active)
3010             stbtt__fill_active_edges(scanline, result->w, active, max_weight);
3011
3012          ++y;
3013       }
3014       STBTT_memcpy(result->pixels + j * result->stride, scanline, result->w);
3015       ++j;
3016    }
3017
3018    stbtt__hheap_cleanup(&hh, userdata);
3019
3020    if (scanline != scanline_data)
3021       STBTT_free(scanline, userdata);
3022 }
3023
3024 #elif STBTT_RASTERIZER_VERSION == 2
3025
3026 // the edge passed in here does not cross the vertical line at x or the vertical line at x+1
3027 // (i.e. it has already been clipped to those)
3028 static void stbtt__handle_clipped_edge(float *scanline, int x, stbtt__active_edge *e, float x0, float y0, float x1, float y1)
3029 {
3030    if (y0 == y1) return;
3031    STBTT_assert(y0 < y1);
3032    STBTT_assert(e->sy <= e->ey);
3033    if (y0 > e->ey) return;
3034    if (y1 < e->sy) return;
3035    if (y0 < e->sy) {
3036       x0 += (x1-x0) * (e->sy - y0) / (y1-y0);
3037       y0 = e->sy;
3038    }
3039    if (y1 > e->ey) {
3040       x1 += (x1-x0) * (e->ey - y1) / (y1-y0);
3041       y1 = e->ey;
3042    }
3043
3044    if (x0 == x)
3045       STBTT_assert(x1 <= x+1);
3046    else if (x0 == x+1)
3047       STBTT_assert(x1 >= x);
3048    else if (x0 <= x)
3049       STBTT_assert(x1 <= x);
3050    else if (x0 >= x+1)
3051       STBTT_assert(x1 >= x+1);
3052    else
3053       STBTT_assert(x1 >= x && x1 <= x+1);
3054
3055    if (x0 <= x && x1 <= x)
3056       scanline[x] += e->direction * (y1-y0);
3057    else if (x0 >= x+1 && x1 >= x+1)
3058       ;
3059    else {
3060       STBTT_assert(x0 >= x && x0 <= x+1 && x1 >= x && x1 <= x+1);
3061       scanline[x] += e->direction * (y1-y0) * (1-((x0-x)+(x1-x))/2); // coverage = 1 - average x position
3062    }
3063 }
3064
3065 static float stbtt__sized_trapezoid_area(float height, float top_width, float bottom_width)
3066 {
3067    STBTT_assert(top_width >= 0);
3068    STBTT_assert(bottom_width >= 0);
3069    return (top_width + bottom_width) / 2.0f * height;
3070 }
3071
3072 static float stbtt__position_trapezoid_area(float height, float tx0, float tx1, float bx0, float bx1)
3073 {
3074    return stbtt__sized_trapezoid_area(height, tx1 - tx0, bx1 - bx0);
3075 }
3076
3077 static float stbtt__sized_triangle_area(float height, float width)
3078 {
3079    return height * width / 2;
3080 }
3081
3082 static void stbtt__fill_active_edges_new(float *scanline, float *scanline_fill, int len, stbtt__active_edge *e, float y_top)
3083 {
3084    float y_bottom = y_top+1;
3085
3086    while (e) {
3087       // brute force every pixel
3088
3089       // compute intersection points with top & bottom
3090       STBTT_assert(e->ey >= y_top);
3091
3092       if (e->fdx == 0) {
3093          float x0 = e->fx;
3094          if (x0 < len) {
3095             if (x0 >= 0) {
3096                stbtt__handle_clipped_edge(scanline,(int) x0,e, x0,y_top, x0,y_bottom);
3097                stbtt__handle_clipped_edge(scanline_fill-1,(int) x0+1,e, x0,y_top, x0,y_bottom);
3098             } else {
3099                stbtt__handle_clipped_edge(scanline_fill-1,0,e, x0,y_top, x0,y_bottom);
3100             }
3101          }
3102       } else {
3103          float x0 = e->fx;
3104          float dx = e->fdx;
3105          float xb = x0 + dx;
3106          float x_top, x_bottom;
3107          float sy0,sy1;
3108          float dy = e->fdy;
3109          STBTT_assert(e->sy <= y_bottom && e->ey >= y_top);
3110
3111          // compute endpoints of line segment clipped to this scanline (if the
3112          // line segment starts on this scanline. x0 is the intersection of the
3113          // line with y_top, but that may be off the line segment.
3114          if (e->sy > y_top) {
3115             x_top = x0 + dx * (e->sy - y_top);
3116             sy0 = e->sy;
3117          } else {
3118             x_top = x0;
3119             sy0 = y_top;
3120          }
3121          if (e->ey < y_bottom) {
3122             x_bottom = x0 + dx * (e->ey - y_top);
3123             sy1 = e->ey;
3124          } else {
3125             x_bottom = xb;
3126             sy1 = y_bottom;
3127          }
3128
3129          if (x_top >= 0 && x_bottom >= 0 && x_top < len && x_bottom < len) {
3130             // from here on, we don't have to range check x values
3131
3132             if ((int) x_top == (int) x_bottom) {
3133                float height;
3134                // simple case, only spans one pixel
3135                int x = (int) x_top;
3136                height = (sy1 - sy0) * e->direction;
3137                STBTT_assert(x >= 0 && x < len);
3138                scanline[x]      += stbtt__position_trapezoid_area(height, x_top, x+1.0f, x_bottom, x+1.0f);
3139                scanline_fill[x] += height; // everything right of this pixel is filled
3140             } else {
3141                int x,x1,x2;
3142                float y_crossing, y_final, step, sign, area;
3143                // covers 2+ pixels
3144                if (x_top > x_bottom) {
3145                   // flip scanline vertically; signed area is the same
3146                   float t;
3147                   sy0 = y_bottom - (sy0 - y_top);
3148                   sy1 = y_bottom - (sy1 - y_top);
3149                   t = sy0, sy0 = sy1, sy1 = t;
3150                   t = x_bottom, x_bottom = x_top, x_top = t;
3151                   dx = -dx;
3152                   dy = -dy;
3153                   t = x0, x0 = xb, xb = t;
3154                }
3155                STBTT_assert(dy >= 0);
3156                STBTT_assert(dx >= 0);
3157
3158                x1 = (int) x_top;
3159                x2 = (int) x_bottom;
3160                // compute intersection with y axis at x1+1
3161                y_crossing = y_top + dy * (x1+1 - x0);
3162
3163                // compute intersection with y axis at x2
3164                y_final = y_top + dy * (x2 - x0);
3165
3166                //           x1    x_top                            x2    x_bottom
3167                //     y_top  +------|-----+------------+------------+--------|---+------------+
3168                //            |            |            |            |            |            |
3169                //            |            |            |            |            |            |
3170                //       sy0  |      Txxxxx|............|............|............|............|
3171                // y_crossing |            *xxxxx.......|............|............|............|
3172                //            |            |     xxxxx..|............|............|............|
3173                //            |            |     /-   xx*xxxx........|............|............|
3174                //            |            | dy <       |    xxxxxx..|............|............|
3175                //   y_final  |            |     \-     |          xx*xxx.........|............|
3176                //       sy1  |            |            |            |   xxxxxB...|............|
3177                //            |            |            |            |            |            |
3178                //            |            |            |            |            |            |
3179                //  y_bottom  +------------+------------+------------+------------+------------+
3180                //
3181                // goal is to measure the area covered by '.' in each pixel
3182
3183                // if x2 is right at the right edge of x1, y_crossing can blow up, github #1057
3184                // @TODO: maybe test against sy1 rather than y_bottom?
3185                if (y_crossing > y_bottom)
3186                   y_crossing = y_bottom;
3187
3188                sign = e->direction;
3189
3190                // area of the rectangle covered from sy0..y_crossing
3191                area = sign * (y_crossing-sy0);
3192
3193                // area of the triangle (x_top,sy0), (x1+1,sy0), (x1+1,y_crossing)
3194                scanline[x1] += stbtt__sized_triangle_area(area, x1+1 - x_top);
3195
3196                // check if final y_crossing is blown up; no test case for this
3197                if (y_final > y_bottom) {
3198                   y_final = y_bottom;
3199                   dy = (y_final - y_crossing ) / (x2 - (x1+1)); // if denom=0, y_final = y_crossing, so y_final <= y_bottom
3200                }
3201
3202                // in second pixel, area covered by line segment found in first pixel
3203                // is always a rectangle 1 wide * the height of that line segment; this
3204                // is exactly what the variable 'area' stores. it also gets a contribution
3205                // from the line segment within it. the THIRD pixel will get the first
3206                // pixel's rectangle contribution, the second pixel's rectangle contribution,
3207                // and its own contribution. the 'own contribution' is the same in every pixel except
3208                // the leftmost and rightmost, a trapezoid that slides down in each pixel.
3209                // the second pixel's contribution to the third pixel will be the
3210                // rectangle 1 wide times the height change in the second pixel, which is dy.
3211
3212                step = sign * dy * 1; // dy is dy/dx, change in y for every 1 change in x,
3213                // which multiplied by 1-pixel-width is how much pixel area changes for each step in x
3214                // so the area advances by 'step' every time
3215
3216                for (x = x1+1; x < x2; ++x) {
3217                   scanline[x] += area + step/2; // area of trapezoid is 1*step/2
3218                   area += step;
3219                }
3220                STBTT_assert(STBTT_fabs(area) <= 1.01f); // accumulated error from area += step unless we round step down
3221                STBTT_assert(sy1 > y_final-0.01f);
3222
3223                // area covered in the last pixel is the rectangle from all the pixels to the left,
3224                // plus the trapezoid filled by the line segment in this pixel all the way to the right edge
3225                scanline[x2] += area + sign * stbtt__position_trapezoid_area(sy1-y_final, (float) x2, x2+1.0f, x_bottom, x2+1.0f);
3226
3227                // the rest of the line is filled based on the total height of the line segment in this pixel
3228                scanline_fill[x2] += sign * (sy1-sy0);
3229             }
3230          } else {
3231             // if edge goes outside of box we're drawing, we require
3232             // clipping logic. since this does not match the intended use
3233             // of this library, we use a different, very slow brute
3234             // force implementation
3235             // note though that this does happen some of the time because
3236             // x_top and x_bottom can be extrapolated at the top & bottom of
3237             // the shape and actually lie outside the bounding box
3238             int x;
3239             for (x=0; x < len; ++x) {
3240                // cases:
3241                //
3242                // there can be up to two intersections with the pixel. any intersection
3243                // with left or right edges can be handled by splitting into two (or three)
3244                // regions. intersections with top & bottom do not necessitate case-wise logic.
3245                //
3246                // the old way of doing this found the intersections with the left & right edges,
3247                // then used some simple logic to produce up to three segments in sorted order
3248                // from top-to-bottom. however, this had a problem: if an x edge was epsilon
3249                // across the x border, then the corresponding y position might not be distinct
3250                // from the other y segment, and it might ignored as an empty segment. to avoid
3251                // that, we need to explicitly produce segments based on x positions.
3252
3253                // rename variables to clearly-defined pairs
3254                float y0 = y_top;
3255                float x1 = (float) (x);
3256                float x2 = (float) (x+1);
3257                float x3 = xb;
3258                float y3 = y_bottom;
3259
3260                // x = e->x + e->dx * (y-y_top)
3261                // (y-y_top) = (x - e->x) / e->dx
3262                // y = (x - e->x) / e->dx + y_top
3263                float y1 = (x - x0) / dx + y_top;
3264                float y2 = (x+1 - x0) / dx + y_top;
3265
3266                if (x0 < x1 && x3 > x2) {         // three segments descending down-right
3267                   stbtt__handle_clipped_edge(scanline,x,e, x0,y0, x1,y1);
3268                   stbtt__handle_clipped_edge(scanline,x,e, x1,y1, x2,y2);
3269                   stbtt__handle_clipped_edge(scanline,x,e, x2,y2, x3,y3);
3270                } else if (x3 < x1 && x0 > x2) {  // three segments descending down-left
3271                   stbtt__handle_clipped_edge(scanline,x,e, x0,y0, x2,y2);
3272                   stbtt__handle_clipped_edge(scanline,x,e, x2,y2, x1,y1);
3273                   stbtt__handle_clipped_edge(scanline,x,e, x1,y1, x3,y3);
3274                } else if (x0 < x1 && x3 > x1) {  // two segments across x, down-right
3275                   stbtt__handle_clipped_edge(scanline,x,e, x0,y0, x1,y1);
3276                   stbtt__handle_clipped_edge(scanline,x,e, x1,y1, x3,y3);
3277                } else if (x3 < x1 && x0 > x1) {  // two segments across x, down-left
3278                   stbtt__handle_clipped_edge(scanline,x,e, x0,y0, x1,y1);
3279                   stbtt__handle_clipped_edge(scanline,x,e, x1,y1, x3,y3);
3280                } else if (x0 < x2 && x3 > x2) {  // two segments across x+1, down-right
3281                   stbtt__handle_clipped_edge(scanline,x,e, x0,y0, x2,y2);
3282                   stbtt__handle_clipped_edge(scanline,x,e, x2,y2, x3,y3);
3283                } else if (x3 < x2 && x0 > x2) {  // two segments across x+1, down-left
3284                   stbtt__handle_clipped_edge(scanline,x,e, x0,y0, x2,y2);
3285                   stbtt__handle_clipped_edge(scanline,x,e, x2,y2, x3,y3);
3286                } else {  // one segment
3287                   stbtt__handle_clipped_edge(scanline,x,e, x0,y0, x3,y3);
3288                }
3289             }
3290          }
3291       }
3292       e = e->next;
3293    }
3294 }
3295
3296 // directly AA rasterize edges w/o supersampling
3297 static void stbtt__rasterize_sorted_edges(stbtt__bitmap *result, stbtt__edge *e, int n, int vsubsample, int off_x, int off_y, void *userdata)
3298 {
3299    stbtt__hheap hh = { 0, 0, 0 };
3300    stbtt__active_edge *active = NULL;
3301    int y,j=0, i;
3302    float scanline_data[129], *scanline, *scanline2;
3303
3304    STBTT__NOTUSED(vsubsample);
3305
3306    if (result->w > 64)
3307       scanline = (float *) STBTT_malloc((result->w*2+1) * sizeof(float), userdata);
3308    else
3309       scanline = scanline_data;
3310
3311    scanline2 = scanline + result->w;
3312
3313    y = off_y;
3314    e[n].y0 = (float) (off_y + result->h) + 1;
3315
3316    while (j < result->h) {
3317       // find center of pixel for this scanline
3318       float scan_y_top    = y + 0.0f;
3319       float scan_y_bottom = y + 1.0f;
3320       stbtt__active_edge **step = &active;
3321
3322       STBTT_memset(scanline , 0, result->w*sizeof(scanline[0]));
3323       STBTT_memset(scanline2, 0, (result->w+1)*sizeof(scanline[0]));
3324
3325       // update all active edges;
3326       // remove all active edges that terminate before the top of this scanline
3327       while (*step) {
3328          stbtt__active_edge * z = *step;
3329          if (z->ey <= scan_y_top) {
3330             *step = z->next; // delete from list
3331             STBTT_assert(z->direction);
3332             z->direction = 0;
3333             stbtt__hheap_free(&hh, z);
3334          } else {
3335             step = &((*step)->next); // advance through list
3336          }
3337       }
3338
3339       // insert all edges that start before the bottom of this scanline
3340       while (e->y0 <= scan_y_bottom) {
3341          if (e->y0 != e->y1) {
3342             stbtt__active_edge *z = stbtt__new_active(&hh, e, off_x, scan_y_top, userdata);
3343             if (z != NULL) {
3344                if (j == 0 && off_y != 0) {
3345                   if (z->ey < scan_y_top) {
3346                      // this can happen due to subpixel positioning and some kind of fp rounding error i think
3347                      z->ey = scan_y_top;
3348                   }
3349                }
3350                STBTT_assert(z->ey >= scan_y_top); // if we get really unlucky a tiny bit of an edge can be out of bounds
3351                // insert at front
3352                z->next = active;
3353                active = z;
3354             }
3355          }
3356          ++e;
3357       }
3358
3359       // now process all active edges
3360       if (active)
3361          stbtt__fill_active_edges_new(scanline, scanline2+1, result->w, active, scan_y_top);
3362
3363       {
3364          float sum = 0;
3365          for (i=0; i < result->w; ++i) {
3366             float k;
3367             int m;
3368             sum += scanline2[i];
3369             k = scanline[i] + sum;
3370             k = (float) STBTT_fabs(k)*255 + 0.5f;
3371             m = (int) k;
3372             if (m > 255) m = 255;
3373             result->pixels[j*result->stride + i] = (unsigned char) m;
3374          }
3375       }
3376       // advance all the edges
3377       step = &active;
3378       while (*step) {
3379          stbtt__active_edge *z = *step;
3380          z->fx += z->fdx; // advance to position for current scanline
3381          step = &((*step)->next); // advance through list
3382       }
3383
3384       ++y;
3385       ++j;
3386    }
3387
3388    stbtt__hheap_cleanup(&hh, userdata);
3389
3390    if (scanline != scanline_data)
3391       STBTT_free(scanline, userdata);
3392 }
3393 #else
3394 #error "Unrecognized value of STBTT_RASTERIZER_VERSION"
3395 #endif
3396
3397 #define STBTT__COMPARE(a,b)  ((a)->y0 < (b)->y0)
3398
3399 static void stbtt__sort_edges_ins_sort(stbtt__edge *p, int n)
3400 {
3401    int i,j;
3402    for (i=1; i < n; ++i) {
3403       stbtt__edge t = p[i], *a = &t;
3404       j = i;
3405       while (j > 0) {
3406          stbtt__edge *b = &p[j-1];
3407          int c = STBTT__COMPARE(a,b);
3408          if (!c) break;
3409          p[j] = p[j-1];
3410          --j;
3411       }
3412       if (i != j)
3413          p[j] = t;
3414    }
3415 }
3416
3417 static void stbtt__sort_edges_quicksort(stbtt__edge *p, int n)
3418 {
3419    /* threshold for transitioning to insertion sort */
3420    while (n > 12) {
3421       stbtt__edge t;
3422       int c01,c12,c,m,i,j;
3423
3424       /* compute median of three */
3425       m = n >> 1;
3426       c01 = STBTT__COMPARE(&p[0],&p[m]);
3427       c12 = STBTT__COMPARE(&p[m],&p[n-1]);
3428       /* if 0 >= mid >= end, or 0 < mid < end, then use mid */
3429       if (c01 != c12) {
3430          /* otherwise, we'll need to swap something else to middle */
3431          int z;
3432          c = STBTT__COMPARE(&p[0],&p[n-1]);
3433          /* 0>mid && mid<n:  0>n => n; 0<n => 0 */
3434          /* 0<mid && mid>n:  0>n => 0; 0<n => n */
3435          z = (c == c12) ? 0 : n-1;
3436          t = p[z];
3437          p[z] = p[m];
3438          p[m] = t;
3439       }
3440       /* now p[m] is the median-of-three */
3441       /* swap it to the beginning so it won't move around */
3442       t = p[0];
3443       p[0] = p[m];
3444       p[m] = t;
3445
3446       /* partition loop */
3447       i=1;
3448       j=n-1;
3449       for(;;) {
3450          /* handling of equality is crucial here */
3451          /* for sentinels & efficiency with duplicates */
3452          for (;;++i) {
3453             if (!STBTT__COMPARE(&p[i], &p[0])) break;
3454          }
3455          for (;;--j) {
3456             if (!STBTT__COMPARE(&p[0], &p[j])) break;
3457          }
3458          /* make sure we haven't crossed */
3459          if (i >= j) break;
3460          t = p[i];
3461          p[i] = p[j];
3462          p[j] = t;
3463
3464          ++i;
3465          --j;
3466       }
3467       /* recurse on smaller side, iterate on larger */
3468       if (j < (n-i)) {
3469          stbtt__sort_edges_quicksort(p,j);
3470          p = p+i;
3471          n = n-i;
3472       } else {
3473          stbtt__sort_edges_quicksort(p+i, n-i);
3474          n = j;
3475       }
3476    }
3477 }
3478
3479 static void stbtt__sort_edges(stbtt__edge *p, int n)
3480 {
3481    stbtt__sort_edges_quicksort(p, n);
3482    stbtt__sort_edges_ins_sort(p, n);
3483 }
3484
3485 typedef struct
3486 {
3487    float x,y;
3488 } stbtt__point;
3489
3490 static void stbtt__rasterize(stbtt__bitmap *result, stbtt__point *pts, int *wcount, int windings, float scale_x, float scale_y, float shift_x, float shift_y, int off_x, int off_y, int invert, void *userdata)
3491 {
3492    float y_scale_inv = invert ? -scale_y : scale_y;
3493    stbtt__edge *e;
3494    int n,i,j,k,m;
3495 #if STBTT_RASTERIZER_VERSION == 1
3496    int vsubsample = result->h < 8 ? 15 : 5;
3497 #elif STBTT_RASTERIZER_VERSION == 2
3498    int vsubsample = 1;
3499 #else
3500    #error "Unrecognized value of STBTT_RASTERIZER_VERSION"
3501 #endif
3502    // vsubsample should divide 255 evenly; otherwise we won't reach full opacity
3503
3504    // now we have to blow out the windings into explicit edge lists
3505    n = 0;
3506    for (i=0; i < windings; ++i)
3507       n += wcount[i];
3508
3509    e = (stbtt__edge *) STBTT_malloc(sizeof(*e) * (n+1), userdata); // add an extra one as a sentinel
3510    if (e == 0) return;
3511    n = 0;
3512
3513    m=0;
3514    for (i=0; i < windings; ++i) {
3515       stbtt__point *p = pts + m;
3516       m += wcount[i];
3517       j = wcount[i]-1;
3518       for (k=0; k < wcount[i]; j=k++) {
3519          int a=k,b=j;
3520          // skip the edge if horizontal
3521          if (p[j].y == p[k].y)
3522             continue;
3523          // add edge from j to k to the list
3524          e[n].invert = 0;
3525          if (invert ? p[j].y > p[k].y : p[j].y < p[k].y) {
3526             e[n].invert = 1;
3527             a=j,b=k;
3528          }
3529          e[n].x0 = p[a].x * scale_x + shift_x;
3530          e[n].y0 = (p[a].y * y_scale_inv + shift_y) * vsubsample;
3531          e[n].x1 = p[b].x * scale_x + shift_x;
3532          e[n].y1 = (p[b].y * y_scale_inv + shift_y) * vsubsample;
3533          ++n;
3534       }
3535    }
3536
3537    // now sort the edges by their highest point (should snap to integer, and then by x)
3538    //STBTT_sort(e, n, sizeof(e[0]), stbtt__edge_compare);
3539    stbtt__sort_edges(e, n);
3540
3541    // now, traverse the scanlines and find the intersections on each scanline, use xor winding rule
3542    stbtt__rasterize_sorted_edges(result, e, n, vsubsample, off_x, off_y, userdata);
3543
3544    STBTT_free(e, userdata);
3545 }
3546
3547 static void stbtt__add_point(stbtt__point *points, int n, float x, float y)
3548 {
3549    if (!points) return; // during first pass, it's unallocated
3550    points[n].x = x;
3551    points[n].y = y;
3552 }
3553
3554 // tessellate until threshold p is happy... @TODO warped to compensate for non-linear stretching
3555 static int stbtt__tesselate_curve(stbtt__point *points, int *num_points, float x0, float y0, float x1, float y1, float x2, float y2, float objspace_flatness_squared, int n)
3556 {
3557    // midpoint
3558    float mx = (x0 + 2*x1 + x2)/4;
3559    float my = (y0 + 2*y1 + y2)/4;
3560    // versus directly drawn line
3561    float dx = (x0+x2)/2 - mx;
3562    float dy = (y0+y2)/2 - my;
3563    if (n > 16) // 65536 segments on one curve better be enough!
3564       return 1;
3565    if (dx*dx+dy*dy > objspace_flatness_squared) { // half-pixel error allowed... need to be smaller if AA
3566       stbtt__tesselate_curve(points, num_points, x0,y0, (x0+x1)/2.0f,(y0+y1)/2.0f, mx,my, objspace_flatness_squared,n+1);
3567       stbtt__tesselate_curve(points, num_points, mx,my, (x1+x2)/2.0f,(y1+y2)/2.0f, x2,y2, objspace_flatness_squared,n+1);
3568    } else {
3569       stbtt__add_point(points, *num_points,x2,y2);
3570       *num_points = *num_points+1;
3571    }
3572    return 1;
3573 }
3574
3575 static void stbtt__tesselate_cubic(stbtt__point *points, int *num_points, float x0, float y0, float x1, float y1, float x2, float y2, float x3, float y3, float objspace_flatness_squared, int n)
3576 {
3577    // @TODO this "flatness" calculation is just made-up nonsense that seems to work well enough
3578    float dx0 = x1-x0;
3579    float dy0 = y1-y0;
3580    float dx1 = x2-x1;
3581    float dy1 = y2-y1;
3582    float dx2 = x3-x2;
3583    float dy2 = y3-y2;
3584    float dx = x3-x0;
3585    float dy = y3-y0;
3586    float longlen = (float) (STBTT_sqrt(dx0*dx0+dy0*dy0)+STBTT_sqrt(dx1*dx1+dy1*dy1)+STBTT_sqrt(dx2*dx2+dy2*dy2));
3587    float shortlen = (float) STBTT_sqrt(dx*dx+dy*dy);
3588    float flatness_squared = longlen*longlen-shortlen*shortlen;
3589
3590    if (n > 16) // 65536 segments on one curve better be enough!
3591       return;
3592
3593    if (flatness_squared > objspace_flatness_squared) {
3594       float x01 = (x0+x1)/2;
3595       float y01 = (y0+y1)/2;
3596       float x12 = (x1+x2)/2;
3597       float y12 = (y1+y2)/2;
3598       float x23 = (x2+x3)/2;
3599       float y23 = (y2+y3)/2;
3600
3601       float xa = (x01+x12)/2;
3602       float ya = (y01+y12)/2;
3603       float xb = (x12+x23)/2;
3604       float yb = (y12+y23)/2;
3605
3606       float mx = (xa+xb)/2;
3607       float my = (ya+yb)/2;
3608
3609       stbtt__tesselate_cubic(points, num_points, x0,y0, x01,y01, xa,ya, mx,my, objspace_flatness_squared,n+1);
3610       stbtt__tesselate_cubic(points, num_points, mx,my, xb,yb, x23,y23, x3,y3, objspace_flatness_squared,n+1);
3611    } else {
3612       stbtt__add_point(points, *num_points,x3,y3);
3613       *num_points = *num_points+1;
3614    }
3615 }
3616
3617 // returns number of contours
3618 static stbtt__point *stbtt_FlattenCurves(stbtt_vertex *vertices, int num_verts, float objspace_flatness, int **contour_lengths, int *num_contours, void *userdata)
3619 {
3620    stbtt__point *points=0;
3621    int num_points=0;
3622
3623    float objspace_flatness_squared = objspace_flatness * objspace_flatness;
3624    int i,n=0,start=0, pass;
3625
3626    // count how many "moves" there are to get the contour count
3627    for (i=0; i < num_verts; ++i)
3628       if (vertices[i].type == STBTT_vmove)
3629          ++n;
3630
3631    *num_contours = n;
3632    if (n == 0) return 0;
3633
3634    *contour_lengths = (int *) STBTT_malloc(sizeof(**contour_lengths) * n, userdata);
3635
3636    if (*contour_lengths == 0) {
3637       *num_contours = 0;
3638       return 0;
3639    }
3640
3641    // make two passes through the points so we don't need to realloc
3642    for (pass=0; pass < 2; ++pass) {
3643       float x=0,y=0;
3644       if (pass == 1) {
3645          points = (stbtt__point *) STBTT_malloc(num_points * sizeof(points[0]), userdata);
3646          if (points == NULL) goto error;
3647       }
3648       num_points = 0;
3649       n= -1;
3650       for (i=0; i < num_verts; ++i) {
3651          switch (vertices[i].type) {
3652             case STBTT_vmove:
3653                // start the next contour
3654                if (n >= 0)
3655                   (*contour_lengths)[n] = num_points - start;
3656                ++n;
3657                start = num_points;
3658
3659                x = vertices[i].x, y = vertices[i].y;
3660                stbtt__add_point(points, num_points++, x,y);
3661                break;
3662             case STBTT_vline:
3663                x = vertices[i].x, y = vertices[i].y;
3664                stbtt__add_point(points, num_points++, x, y);
3665                break;
3666             case STBTT_vcurve:
3667                stbtt__tesselate_curve(points, &num_points, x,y,
3668                                         vertices[i].cx, vertices[i].cy,
3669                                         vertices[i].x,  vertices[i].y,
3670                                         objspace_flatness_squared, 0);
3671                x = vertices[i].x, y = vertices[i].y;
3672                break;
3673             case STBTT_vcubic:
3674                stbtt__tesselate_cubic(points, &num_points, x,y,
3675                                         vertices[i].cx, vertices[i].cy,
3676                                         vertices[i].cx1, vertices[i].cy1,
3677                                         vertices[i].x,  vertices[i].y,
3678                                         objspace_flatness_squared, 0);
3679                x = vertices[i].x, y = vertices[i].y;
3680                break;
3681          }
3682       }
3683       (*contour_lengths)[n] = num_points - start;
3684    }
3685
3686    return points;
3687 error:
3688    STBTT_free(points, userdata);
3689    STBTT_free(*contour_lengths, userdata);
3690    *contour_lengths = 0;
3691    *num_contours = 0;
3692    return NULL;
3693 }
3694
3695 STBTT_DEF void stbtt_Rasterize(stbtt__bitmap *result, float flatness_in_pixels, stbtt_vertex *vertices, int num_verts, float scale_x, float scale_y, float shift_x, float shift_y, int x_off, int y_off, int invert, void *userdata)
3696 {
3697    float scale            = scale_x > scale_y ? scale_y : scale_x;
3698    int winding_count      = 0;
3699    int *winding_lengths   = NULL;
3700    stbtt__point *windings = stbtt_FlattenCurves(vertices, num_verts, flatness_in_pixels / scale, &winding_lengths, &winding_count, userdata);
3701    if (windings) {
3702       stbtt__rasterize(result, windings, winding_lengths, winding_count, scale_x, scale_y, shift_x, shift_y, x_off, y_off, invert, userdata);
3703       STBTT_free(winding_lengths, userdata);
3704       STBTT_free(windings, userdata);
3705    }
3706 }
3707
3708 STBTT_DEF void stbtt_FreeBitmap(unsigned char *bitmap, void *userdata)
3709 {
3710    STBTT_free(bitmap, userdata);
3711 }
3712
3713 STBTT_DEF unsigned char *stbtt_GetGlyphBitmapSubpixel(const stbtt_fontinfo *info, float scale_x, float scale_y, float shift_x, float shift_y, int glyph, int *width, int *height, int *xoff, int *yoff)
3714 {
3715    int ix0,iy0,ix1,iy1;
3716    stbtt__bitmap gbm;
3717    stbtt_vertex *vertices;
3718    int num_verts = stbtt_GetGlyphShape(info, glyph, &vertices);
3719
3720    if (scale_x == 0) scale_x = scale_y;
3721    if (scale_y == 0) {
3722       if (scale_x == 0) {
3723          STBTT_free(vertices, info->userdata);
3724          return NULL;
3725       }
3726       scale_y = scale_x;
3727    }
3728
3729    stbtt_GetGlyphBitmapBoxSubpixel(info, glyph, scale_x, scale_y, shift_x, shift_y, &ix0,&iy0,&ix1,&iy1);
3730
3731    // now we get the size
3732    gbm.w = (ix1 - ix0);
3733    gbm.h = (iy1 - iy0);
3734    gbm.pixels = NULL; // in case we error
3735
3736    if (width ) *width  = gbm.w;
3737    if (height) *height = gbm.h;
3738    if (xoff  ) *xoff   = ix0;
3739    if (yoff  ) *yoff   = iy0;
3740
3741    if (gbm.w && gbm.h) {
3742       gbm.pixels = (unsigned char *) STBTT_malloc(gbm.w * gbm.h, info->userdata);
3743       if (gbm.pixels) {
3744          gbm.stride = gbm.w;
3745
3746          stbtt_Rasterize(&gbm, 0.35f, vertices, num_verts, scale_x, scale_y, shift_x, shift_y, ix0, iy0, 1, info->userdata);
3747       }
3748    }
3749    STBTT_free(vertices, info->userdata);
3750    return gbm.pixels;
3751 }
3752
3753 STBTT_DEF unsigned char *stbtt_GetGlyphBitmap(const stbtt_fontinfo *info, float scale_x, float scale_y, int glyph, int *width, int *height, int *xoff, int *yoff)
3754 {
3755    return stbtt_GetGlyphBitmapSubpixel(info, scale_x, scale_y, 0.0f, 0.0f, glyph, width, height, xoff, yoff);
3756 }
3757
3758 STBTT_DEF void stbtt_MakeGlyphBitmapSubpixel(const stbtt_fontinfo *info, unsigned char *output, int out_w, int out_h, int out_stride, float scale_x, float scale_y, float shift_x, float shift_y, int glyph)
3759 {
3760    int ix0,iy0;
3761    stbtt_vertex *vertices;
3762    int num_verts = stbtt_GetGlyphShape(info, glyph, &vertices);
3763    stbtt__bitmap gbm;
3764
3765    stbtt_GetGlyphBitmapBoxSubpixel(info, glyph, scale_x, scale_y, shift_x, shift_y, &ix0,&iy0,0,0);
3766    gbm.pixels = output;
3767    gbm.w = out_w;
3768    gbm.h = out_h;
3769    gbm.stride = out_stride;
3770
3771    if (gbm.w && gbm.h)
3772       stbtt_Rasterize(&gbm, 0.35f, vertices, num_verts, scale_x, scale_y, shift_x, shift_y, ix0,iy0, 1, info->userdata);
3773
3774    STBTT_free(vertices, info->userdata);
3775 }
3776
3777 STBTT_DEF void stbtt_MakeGlyphBitmap(const stbtt_fontinfo *info, unsigned char *output, int out_w, int out_h, int out_stride, float scale_x, float scale_y, int glyph)
3778 {
3779    stbtt_MakeGlyphBitmapSubpixel(info, output, out_w, out_h, out_stride, scale_x, scale_y, 0.0f,0.0f, glyph);
3780 }
3781
3782 STBTT_DEF unsigned char *stbtt_GetCodepointBitmapSubpixel(const stbtt_fontinfo *info, float scale_x, float scale_y, float shift_x, float shift_y, int codepoint, int *width, int *height, int *xoff, int *yoff)
3783 {
3784    return stbtt_GetGlyphBitmapSubpixel(info, scale_x, scale_y,shift_x,shift_y, stbtt_FindGlyphIndex(info,codepoint), width,height,xoff,yoff);
3785 }
3786
3787 STBTT_DEF void stbtt_MakeCodepointBitmapSubpixelPrefilter(const stbtt_fontinfo *info, unsigned char *output, int out_w, int out_h, int out_stride, float scale_x, float scale_y, float shift_x, float shift_y, int oversample_x, int oversample_y, float *sub_x, float *sub_y, int codepoint)
3788 {
3789    stbtt_MakeGlyphBitmapSubpixelPrefilter(info, output, out_w, out_h, out_stride, scale_x, scale_y, shift_x, shift_y, oversample_x, oversample_y, sub_x, sub_y, stbtt_FindGlyphIndex(info,codepoint));
3790 }
3791
3792 STBTT_DEF void stbtt_MakeCodepointBitmapSubpixel(const stbtt_fontinfo *info, unsigned char *output, int out_w, int out_h, int out_stride, float scale_x, float scale_y, float shift_x, float shift_y, int codepoint)
3793 {
3794    stbtt_MakeGlyphBitmapSubpixel(info, output, out_w, out_h, out_stride, scale_x, scale_y, shift_x, shift_y, stbtt_FindGlyphIndex(info,codepoint));
3795 }
3796
3797 STBTT_DEF unsigned char *stbtt_GetCodepointBitmap(const stbtt_fontinfo *info, float scale_x, float scale_y, int codepoint, int *width, int *height, int *xoff, int *yoff)
3798 {
3799    return stbtt_GetCodepointBitmapSubpixel(info, scale_x, scale_y, 0.0f,0.0f, codepoint, width,height,xoff,yoff);
3800 }
3801
3802 STBTT_DEF void stbtt_MakeCodepointBitmap(const stbtt_fontinfo *info, unsigned char *output, int out_w, int out_h, int out_stride, float scale_x, float scale_y, int codepoint)
3803 {
3804    stbtt_MakeCodepointBitmapSubpixel(info, output, out_w, out_h, out_stride, scale_x, scale_y, 0.0f,0.0f, codepoint);
3805 }
3806
3807 //////////////////////////////////////////////////////////////////////////////
3808 //
3809 // bitmap baking
3810 //
3811 // This is SUPER-CRAPPY packing to keep source code small
3812
3813 static int stbtt_BakeFontBitmap_internal(unsigned char *data, int offset,  // font location (use offset=0 for plain .ttf)
3814                                 float pixel_height,                     // height of font in pixels
3815                                 unsigned char *pixels, int pw, int ph,  // bitmap to be filled in
3816                                 int first_char, int num_chars,          // characters to bake
3817                                 stbtt_bakedchar *chardata)
3818 {
3819    float scale;
3820    int x,y,bottom_y, i;
3821    stbtt_fontinfo f;
3822    f.userdata = NULL;
3823    if (!stbtt_InitFont(&f, data, offset))
3824       return -1;
3825    STBTT_memset(pixels, 0, pw*ph); // background of 0 around pixels
3826    x=y=1;
3827    bottom_y = 1;
3828
3829    scale = stbtt_ScaleForPixelHeight(&f, pixel_height);
3830
3831    for (i=0; i < num_chars; ++i) {
3832       int advance, lsb, x0,y0,x1,y1,gw,gh;
3833       int g = stbtt_FindGlyphIndex(&f, first_char + i);
3834       stbtt_GetGlyphHMetrics(&f, g, &advance, &lsb);
3835       stbtt_GetGlyphBitmapBox(&f, g, scale,scale, &x0,&y0,&x1,&y1);
3836       gw = x1-x0;
3837       gh = y1-y0;
3838       if (x + gw + 1 >= pw)
3839          y = bottom_y, x = 1; // advance to next row
3840       if (y + gh + 1 >= ph) // check if it fits vertically AFTER potentially moving to next row
3841          return -i;
3842       STBTT_assert(x+gw < pw);
3843       STBTT_assert(y+gh < ph);
3844       stbtt_MakeGlyphBitmap(&f, pixels+x+y*pw, gw,gh,pw, scale,scale, g);
3845       chardata[i].x0 = (stbtt_int16) x;
3846       chardata[i].y0 = (stbtt_int16) y;
3847       chardata[i].x1 = (stbtt_int16) (x + gw);
3848       chardata[i].y1 = (stbtt_int16) (y + gh);
3849       chardata[i].xadvance = scale * advance;
3850       chardata[i].xoff     = (float) x0;
3851       chardata[i].yoff     = (float) y0;
3852       x = x + gw + 1;
3853       if (y+gh+1 > bottom_y)
3854          bottom_y = y+gh+1;
3855    }
3856    return bottom_y;
3857 }
3858
3859 STBTT_DEF void stbtt_GetBakedQuad(const stbtt_bakedchar *chardata, int pw, int ph, int char_index, float *xpos, float *ypos, stbtt_aligned_quad *q, int opengl_fillrule)
3860 {
3861    float d3d_bias = opengl_fillrule ? 0 : -0.5f;
3862    float ipw = 1.0f / pw, iph = 1.0f / ph;
3863    const stbtt_bakedchar *b = chardata + char_index;
3864    int round_x = STBTT_ifloor((*xpos + b->xoff) + 0.5f);
3865    int round_y = STBTT_ifloor((*ypos + b->yoff) + 0.5f);
3866
3867    q->x0 = round_x + d3d_bias;
3868    q->y0 = round_y + d3d_bias;
3869    q->x1 = round_x + b->x1 - b->x0 + d3d_bias;
3870    q->y1 = round_y + b->y1 - b->y0 + d3d_bias;
3871
3872    q->s0 = b->x0 * ipw;
3873    q->t0 = b->y0 * iph;
3874    q->s1 = b->x1 * ipw;
3875    q->t1 = b->y1 * iph;
3876
3877    *xpos += b->xadvance;
3878 }
3879
3880 //////////////////////////////////////////////////////////////////////////////
3881 //
3882 // rectangle packing replacement routines if you don't have stb_rect_pack.h
3883 //
3884
3885 #ifndef STB_RECT_PACK_VERSION
3886
3887 typedef int stbrp_coord;
3888
3889 ////////////////////////////////////////////////////////////////////////////////////
3890 //                                                                                //
3891 //                                                                                //
3892 // COMPILER WARNING ?!?!?                                                         //
3893 //                                                                                //
3894 //                                                                                //
3895 // if you get a compile warning due to these symbols being defined more than      //
3896 // once, move #include "stb_rect_pack.h" before #include "stb_truetype.h"         //
3897 //                                                                                //
3898 ////////////////////////////////////////////////////////////////////////////////////
3899
3900 typedef struct
3901 {
3902    int width,height;
3903    int x,y,bottom_y;
3904 } stbrp_context;
3905
3906 typedef struct
3907 {
3908    unsigned char x;
3909 } stbrp_node;
3910
3911 struct stbrp_rect
3912 {
3913    stbrp_coord x,y;
3914    int id,w,h,was_packed;
3915 };
3916
3917 static void stbrp_init_target(stbrp_context *con, int pw, int ph, stbrp_node *nodes, int num_nodes)
3918 {
3919    con->width  = pw;
3920    con->height = ph;
3921    con->x = 0;
3922    con->y = 0;
3923    con->bottom_y = 0;
3924    STBTT__NOTUSED(nodes);
3925    STBTT__NOTUSED(num_nodes);
3926 }
3927
3928 static void stbrp_pack_rects(stbrp_context *con, stbrp_rect *rects, int num_rects)
3929 {
3930    int i;
3931    for (i=0; i < num_rects; ++i) {
3932       if (con->x + rects[i].w > con->width) {
3933          con->x = 0;
3934          con->y = con->bottom_y;
3935       }
3936       if (con->y + rects[i].h > con->height)
3937          break;
3938       rects[i].x = con->x;
3939       rects[i].y = con->y;
3940       rects[i].was_packed = 1;
3941       con->x += rects[i].w;
3942       if (con->y + rects[i].h > con->bottom_y)
3943          con->bottom_y = con->y + rects[i].h;
3944    }
3945    for (   ; i < num_rects; ++i)
3946       rects[i].was_packed = 0;
3947 }
3948 #endif
3949
3950 //////////////////////////////////////////////////////////////////////////////
3951 //
3952 // bitmap baking
3953 //
3954 // This is SUPER-AWESOME (tm Ryan Gordon) packing using stb_rect_pack.h. If
3955 // stb_rect_pack.h isn't available, it uses the BakeFontBitmap strategy.
3956
3957 STBTT_DEF int stbtt_PackBegin(stbtt_pack_context *spc, unsigned char *pixels, int pw, int ph, int stride_in_bytes, int padding, void *alloc_context)
3958 {
3959    stbrp_context *context = (stbrp_context *) STBTT_malloc(sizeof(*context)            ,alloc_context);
3960    int            num_nodes = pw - padding;
3961    stbrp_node    *nodes   = (stbrp_node    *) STBTT_malloc(sizeof(*nodes  ) * num_nodes,alloc_context);
3962
3963    if (context == NULL || nodes == NULL) {
3964       if (context != NULL) STBTT_free(context, alloc_context);
3965       if (nodes   != NULL) STBTT_free(nodes  , alloc_context);
3966       return 0;
3967    }
3968
3969    spc->user_allocator_context = alloc_context;
3970    spc->width = pw;
3971    spc->height = ph;
3972    spc->pixels = pixels;
3973    spc->pack_info = context;
3974    spc->nodes = nodes;
3975    spc->padding = padding;
3976    spc->stride_in_bytes = stride_in_bytes != 0 ? stride_in_bytes : pw;
3977    spc->h_oversample = 1;
3978    spc->v_oversample = 1;
3979    spc->skip_missing = 0;
3980
3981    stbrp_init_target(context, pw-padding, ph-padding, nodes, num_nodes);
3982
3983    if (pixels)
3984       STBTT_memset(pixels, 0, pw*ph); // background of 0 around pixels
3985
3986    return 1;
3987 }
3988
3989 STBTT_DEF void stbtt_PackEnd  (stbtt_pack_context *spc)
3990 {
3991    STBTT_free(spc->nodes    , spc->user_allocator_context);
3992    STBTT_free(spc->pack_info, spc->user_allocator_context);
3993 }
3994
3995 STBTT_DEF void stbtt_PackSetOversampling(stbtt_pack_context *spc, unsigned int h_oversample, unsigned int v_oversample)
3996 {
3997    STBTT_assert(h_oversample <= STBTT_MAX_OVERSAMPLE);
3998    STBTT_assert(v_oversample <= STBTT_MAX_OVERSAMPLE);
3999    if (h_oversample <= STBTT_MAX_OVERSAMPLE)
4000       spc->h_oversample = h_oversample;
4001    if (v_oversample <= STBTT_MAX_OVERSAMPLE)
4002       spc->v_oversample = v_oversample;
4003 }
4004
4005 STBTT_DEF void stbtt_PackSetSkipMissingCodepoints(stbtt_pack_context *spc, int skip)
4006 {
4007    spc->skip_missing = skip;
4008 }
4009
4010 #define STBTT__OVER_MASK  (STBTT_MAX_OVERSAMPLE-1)
4011
4012 static void stbtt__h_prefilter(unsigned char *pixels, int w, int h, int stride_in_bytes, unsigned int kernel_width)
4013 {
4014    unsigned char buffer[STBTT_MAX_OVERSAMPLE];
4015    int safe_w = w - kernel_width;
4016    int j;
4017    STBTT_memset(buffer, 0, STBTT_MAX_OVERSAMPLE); // suppress bogus warning from VS2013 -analyze
4018    for (j=0; j < h; ++j) {
4019       int i;
4020       unsigned int total;
4021       STBTT_memset(buffer, 0, kernel_width);
4022
4023       total = 0;
4024
4025       // make kernel_width a constant in common cases so compiler can optimize out the divide
4026       switch (kernel_width) {
4027          case 2:
4028             for (i=0; i <= safe_w; ++i) {
4029                total += pixels[i] - buffer[i & STBTT__OVER_MASK];
4030                buffer[(i+kernel_width) & STBTT__OVER_MASK] = pixels[i];
4031                pixels[i] = (unsigned char) (total / 2);
4032             }
4033             break;
4034          case 3:
4035             for (i=0; i <= safe_w; ++i) {
4036                total += pixels[i] - buffer[i & STBTT__OVER_MASK];
4037                buffer[(i+kernel_width) & STBTT__OVER_MASK] = pixels[i];
4038                pixels[i] = (unsigned char) (total / 3);
4039             }
4040             break;
4041          case 4:
4042             for (i=0; i <= safe_w; ++i) {
4043                total += pixels[i] - buffer[i & STBTT__OVER_MASK];
4044                buffer[(i+kernel_width) & STBTT__OVER_MASK] = pixels[i];
4045                pixels[i] = (unsigned char) (total / 4);
4046             }
4047             break;
4048          case 5:
4049             for (i=0; i <= safe_w; ++i) {
4050                total += pixels[i] - buffer[i & STBTT__OVER_MASK];
4051                buffer[(i+kernel_width) & STBTT__OVER_MASK] = pixels[i];
4052                pixels[i] = (unsigned char) (total / 5);
4053             }
4054             break;
4055          default:
4056             for (i=0; i <= safe_w; ++i) {
4057                total += pixels[i] - buffer[i & STBTT__OVER_MASK];
4058                buffer[(i+kernel_width) & STBTT__OVER_MASK] = pixels[i];
4059                pixels[i] = (unsigned char) (total / kernel_width);
4060             }
4061             break;
4062       }
4063
4064       for (; i < w; ++i) {
4065          STBTT_assert(pixels[i] == 0);
4066          total -= buffer[i & STBTT__OVER_MASK];
4067          pixels[i] = (unsigned char) (total / kernel_width);
4068       }
4069
4070       pixels += stride_in_bytes;
4071    }
4072 }
4073
4074 static void stbtt__v_prefilter(unsigned char *pixels, int w, int h, int stride_in_bytes, unsigned int kernel_width)
4075 {
4076    unsigned char buffer[STBTT_MAX_OVERSAMPLE];
4077    int safe_h = h - kernel_width;
4078    int j;
4079    STBTT_memset(buffer, 0, STBTT_MAX_OVERSAMPLE); // suppress bogus warning from VS2013 -analyze
4080    for (j=0; j < w; ++j) {
4081       int i;
4082       unsigned int total;
4083       STBTT_memset(buffer, 0, kernel_width);
4084
4085       total = 0;
4086
4087       // make kernel_width a constant in common cases so compiler can optimize out the divide
4088       switch (kernel_width) {
4089          case 2:
4090             for (i=0; i <= safe_h; ++i) {
4091                total += pixels[i*stride_in_bytes] - buffer[i & STBTT__OVER_MASK];
4092                buffer[(i+kernel_width) & STBTT__OVER_MASK] = pixels[i*stride_in_bytes];
4093                pixels[i*stride_in_bytes] = (unsigned char) (total / 2);
4094             }
4095             break;
4096          case 3:
4097             for (i=0; i <= safe_h; ++i) {
4098                total += pixels[i*stride_in_bytes] - buffer[i & STBTT__OVER_MASK];
4099                buffer[(i+kernel_width) & STBTT__OVER_MASK] = pixels[i*stride_in_bytes];
4100                pixels[i*stride_in_bytes] = (unsigned char) (total / 3);
4101             }
4102             break;
4103          case 4:
4104             for (i=0; i <= safe_h; ++i) {
4105                total += pixels[i*stride_in_bytes] - buffer[i & STBTT__OVER_MASK];
4106                buffer[(i+kernel_width) & STBTT__OVER_MASK] = pixels[i*stride_in_bytes];
4107                pixels[i*stride_in_bytes] = (unsigned char) (total / 4);
4108             }
4109             break;
4110          case 5:
4111             for (i=0; i <= safe_h; ++i) {
4112                total += pixels[i*stride_in_bytes] - buffer[i & STBTT__OVER_MASK];
4113                buffer[(i+kernel_width) & STBTT__OVER_MASK] = pixels[i*stride_in_bytes];
4114                pixels[i*stride_in_bytes] = (unsigned char) (total / 5);
4115             }
4116             break;
4117          default:
4118             for (i=0; i <= safe_h; ++i) {
4119                total += pixels[i*stride_in_bytes] - buffer[i & STBTT__OVER_MASK];
4120                buffer[(i+kernel_width) & STBTT__OVER_MASK] = pixels[i*stride_in_bytes];
4121                pixels[i*stride_in_bytes] = (unsigned char) (total / kernel_width);
4122             }
4123             break;
4124       }
4125
4126       for (; i < h; ++i) {
4127          STBTT_assert(pixels[i*stride_in_bytes] == 0);
4128          total -= buffer[i & STBTT__OVER_MASK];
4129          pixels[i*stride_in_bytes] = (unsigned char) (total / kernel_width);
4130       }
4131
4132       pixels += 1;
4133    }
4134 }
4135
4136 static float stbtt__oversample_shift(int oversample)
4137 {
4138    if (!oversample)
4139       return 0.0f;
4140
4141    // The prefilter is a box filter of width "oversample",
4142    // which shifts phase by (oversample - 1)/2 pixels in
4143    // oversampled space. We want to shift in the opposite
4144    // direction to counter this.
4145    return (float)-(oversample - 1) / (2.0f * (float)oversample);
4146 }
4147
4148 // rects array must be big enough to accommodate all characters in the given ranges
4149 STBTT_DEF int stbtt_PackFontRangesGatherRects(stbtt_pack_context *spc, const stbtt_fontinfo *info, stbtt_pack_range *ranges, int num_ranges, stbrp_rect *rects)
4150 {
4151    int i,j,k;
4152    int missing_glyph_added = 0;
4153
4154    k=0;
4155    for (i=0; i < num_ranges; ++i) {
4156       float fh = ranges[i].font_size;
4157       float scale = fh > 0 ? stbtt_ScaleForPixelHeight(info, fh) : stbtt_ScaleForMappingEmToPixels(info, -fh);
4158       ranges[i].h_oversample = (unsigned char) spc->h_oversample;
4159       ranges[i].v_oversample = (unsigned char) spc->v_oversample;
4160       for (j=0; j < ranges[i].num_chars; ++j) {
4161          int x0,y0,x1,y1;
4162          int codepoint = ranges[i].array_of_unicode_codepoints == NULL ? ranges[i].first_unicode_codepoint_in_range + j : ranges[i].array_of_unicode_codepoints[j];
4163          int glyph = stbtt_FindGlyphIndex(info, codepoint);
4164          if (glyph == 0 && (spc->skip_missing || missing_glyph_added)) {
4165             rects[k].w = rects[k].h = 0;
4166          } else {
4167             stbtt_GetGlyphBitmapBoxSubpixel(info,glyph,
4168                                             scale * spc->h_oversample,
4169                                             scale * spc->v_oversample,
4170                                             0,0,
4171                                             &x0,&y0,&x1,&y1);
4172             rects[k].w = (stbrp_coord) (x1-x0 + spc->padding + spc->h_oversample-1);
4173             rects[k].h = (stbrp_coord) (y1-y0 + spc->padding + spc->v_oversample-1);
4174             if (glyph == 0)
4175                missing_glyph_added = 1;
4176          }
4177          ++k;
4178       }
4179    }
4180
4181    return k;
4182 }
4183
4184 STBTT_DEF void stbtt_MakeGlyphBitmapSubpixelPrefilter(const stbtt_fontinfo *info, unsigned char *output, int out_w, int out_h, int out_stride, float scale_x, float scale_y, float shift_x, float shift_y, int prefilter_x, int prefilter_y, float *sub_x, float *sub_y, int glyph)
4185 {
4186    stbtt_MakeGlyphBitmapSubpixel(info,
4187                                  output,
4188                                  out_w - (prefilter_x - 1),
4189                                  out_h - (prefilter_y - 1),
4190                                  out_stride,
4191                                  scale_x,
4192                                  scale_y,
4193                                  shift_x,
4194                                  shift_y,
4195                                  glyph);
4196
4197    if (prefilter_x > 1)
4198       stbtt__h_prefilter(output, out_w, out_h, out_stride, prefilter_x);
4199
4200    if (prefilter_y > 1)
4201       stbtt__v_prefilter(output, out_w, out_h, out_stride, prefilter_y);
4202
4203    *sub_x = stbtt__oversample_shift(prefilter_x);
4204    *sub_y = stbtt__oversample_shift(prefilter_y);
4205 }
4206
4207 // rects array must be big enough to accommodate all characters in the given ranges
4208 STBTT_DEF int stbtt_PackFontRangesRenderIntoRects(stbtt_pack_context *spc, const stbtt_fontinfo *info, stbtt_pack_range *ranges, int num_ranges, stbrp_rect *rects)
4209 {
4210    int i,j,k, missing_glyph = -1, return_value = 1;
4211
4212    // save current values
4213    int old_h_over = spc->h_oversample;
4214    int old_v_over = spc->v_oversample;
4215
4216    k = 0;
4217    for (i=0; i < num_ranges; ++i) {
4218       float fh = ranges[i].font_size;
4219       float scale = fh > 0 ? stbtt_ScaleForPixelHeight(info, fh) : stbtt_ScaleForMappingEmToPixels(info, -fh);
4220       float recip_h,recip_v,sub_x,sub_y;
4221       spc->h_oversample = ranges[i].h_oversample;
4222       spc->v_oversample = ranges[i].v_oversample;
4223       recip_h = 1.0f / spc->h_oversample;
4224       recip_v = 1.0f / spc->v_oversample;
4225       sub_x = stbtt__oversample_shift(spc->h_oversample);
4226       sub_y = stbtt__oversample_shift(spc->v_oversample);
4227       for (j=0; j < ranges[i].num_chars; ++j) {
4228          stbrp_rect *r = &rects[k];
4229          if (r->was_packed && r->w != 0 && r->h != 0) {
4230             stbtt_packedchar *bc = &ranges[i].chardata_for_range[j];
4231             int advance, lsb, x0,y0,x1,y1;
4232             int codepoint = ranges[i].array_of_unicode_codepoints == NULL ? ranges[i].first_unicode_codepoint_in_range + j : ranges[i].array_of_unicode_codepoints[j];
4233             int glyph = stbtt_FindGlyphIndex(info, codepoint);
4234             stbrp_coord pad = (stbrp_coord) spc->padding;
4235
4236             // pad on left and top
4237             r->x += pad;
4238             r->y += pad;
4239             r->w -= pad;
4240             r->h -= pad;
4241             stbtt_GetGlyphHMetrics(info, glyph, &advance, &lsb);
4242             stbtt_GetGlyphBitmapBox(info, glyph,
4243                                     scale * spc->h_oversample,
4244                                     scale * spc->v_oversample,
4245                                     &x0,&y0,&x1,&y1);
4246             stbtt_MakeGlyphBitmapSubpixel(info,
4247                                           spc->pixels + r->x + r->y*spc->stride_in_bytes,
4248                                           r->w - spc->h_oversample+1,
4249                                           r->h - spc->v_oversample+1,
4250                                           spc->stride_in_bytes,
4251                                           scale * spc->h_oversample,
4252                                           scale * spc->v_oversample,
4253                                           0,0,
4254                                           glyph);
4255
4256             if (spc->h_oversample > 1)
4257                stbtt__h_prefilter(spc->pixels + r->x + r->y*spc->stride_in_bytes,
4258                                   r->w, r->h, spc->stride_in_bytes,
4259                                   spc->h_oversample);
4260
4261             if (spc->v_oversample > 1)
4262                stbtt__v_prefilter(spc->pixels + r->x + r->y*spc->stride_in_bytes,
4263                                   r->w, r->h, spc->stride_in_bytes,
4264                                   spc->v_oversample);
4265
4266             bc->x0       = (stbtt_int16)  r->x;
4267             bc->y0       = (stbtt_int16)  r->y;
4268             bc->x1       = (stbtt_int16) (r->x + r->w);
4269             bc->y1       = (stbtt_int16) (r->y + r->h);
4270             bc->xadvance =                scale * advance;
4271             bc->xoff     =       (float)  x0 * recip_h + sub_x;
4272             bc->yoff     =       (float)  y0 * recip_v + sub_y;
4273             bc->xoff2    =                (x0 + r->w) * recip_h + sub_x;
4274             bc->yoff2    =                (y0 + r->h) * recip_v + sub_y;
4275
4276             if (glyph == 0)
4277                missing_glyph = j;
4278          } else if (spc->skip_missing) {
4279             return_value = 0;
4280          } else if (r->was_packed && r->w == 0 && r->h == 0 && missing_glyph >= 0) {
4281             ranges[i].chardata_for_range[j] = ranges[i].chardata_for_range[missing_glyph];
4282          } else {
4283             return_value = 0; // if any fail, report failure
4284          }
4285
4286          ++k;
4287       }
4288    }
4289
4290    // restore original values
4291    spc->h_oversample = old_h_over;
4292    spc->v_oversample = old_v_over;
4293
4294    return return_value;
4295 }
4296
4297 STBTT_DEF void stbtt_PackFontRangesPackRects(stbtt_pack_context *spc, stbrp_rect *rects, int num_rects)
4298 {
4299    stbrp_pack_rects((stbrp_context *) spc->pack_info, rects, num_rects);
4300 }
4301
4302 STBTT_DEF int stbtt_PackFontRanges(stbtt_pack_context *spc, const unsigned char *fontdata, int font_index, stbtt_pack_range *ranges, int num_ranges)
4303 {
4304    stbtt_fontinfo info;
4305    int i,j,n, return_value = 1;
4306    //stbrp_context *context = (stbrp_context *) spc->pack_info;
4307    stbrp_rect    *rects;
4308
4309    // flag all characters as NOT packed
4310    for (i=0; i < num_ranges; ++i)
4311       for (j=0; j < ranges[i].num_chars; ++j)
4312          ranges[i].chardata_for_range[j].x0 =
4313          ranges[i].chardata_for_range[j].y0 =
4314          ranges[i].chardata_for_range[j].x1 =
4315          ranges[i].chardata_for_range[j].y1 = 0;
4316
4317    n = 0;
4318    for (i=0; i < num_ranges; ++i)
4319       n += ranges[i].num_chars;
4320
4321    rects = (stbrp_rect *) STBTT_malloc(sizeof(*rects) * n, spc->user_allocator_context);
4322    if (rects == NULL)
4323       return 0;
4324
4325    info.userdata = spc->user_allocator_context;
4326    stbtt_InitFont(&info, fontdata, stbtt_GetFontOffsetForIndex(fontdata,font_index));
4327
4328    n = stbtt_PackFontRangesGatherRects(spc, &info, ranges, num_ranges, rects);
4329
4330    stbtt_PackFontRangesPackRects(spc, rects, n);
4331
4332    return_value = stbtt_PackFontRangesRenderIntoRects(spc, &info, ranges, num_ranges, rects);
4333
4334    STBTT_free(rects, spc->user_allocator_context);
4335    return return_value;
4336 }
4337
4338 STBTT_DEF int stbtt_PackFontRange(stbtt_pack_context *spc, const unsigned char *fontdata, int font_index, float font_size,
4339             int first_unicode_codepoint_in_range, int num_chars_in_range, stbtt_packedchar *chardata_for_range)
4340 {
4341    stbtt_pack_range range;
4342    range.first_unicode_codepoint_in_range = first_unicode_codepoint_in_range;
4343    range.array_of_unicode_codepoints = NULL;
4344    range.num_chars                   = num_chars_in_range;
4345    range.chardata_for_range          = chardata_for_range;
4346    range.font_size                   = font_size;
4347    return stbtt_PackFontRanges(spc, fontdata, font_index, &range, 1);
4348 }
4349
4350 STBTT_DEF void stbtt_GetScaledFontVMetrics(const unsigned char *fontdata, int index, float size, float *ascent, float *descent, float *lineGap)
4351 {
4352    int i_ascent, i_descent, i_lineGap;
4353    float scale;
4354    stbtt_fontinfo info;
4355    stbtt_InitFont(&info, fontdata, stbtt_GetFontOffsetForIndex(fontdata, index));
4356    scale = size > 0 ? stbtt_ScaleForPixelHeight(&info, size) : stbtt_ScaleForMappingEmToPixels(&info, -size);
4357    stbtt_GetFontVMetrics(&info, &i_ascent, &i_descent, &i_lineGap);
4358    *ascent  = (float) i_ascent  * scale;
4359    *descent = (float) i_descent * scale;
4360    *lineGap = (float) i_lineGap * scale;
4361 }
4362
4363 STBTT_DEF void stbtt_GetPackedQuad(const stbtt_packedchar *chardata, int pw, int ph, int char_index, float *xpos, float *ypos, stbtt_aligned_quad *q, int align_to_integer)
4364 {
4365    float ipw = 1.0f / pw, iph = 1.0f / ph;
4366    const stbtt_packedchar *b = chardata + char_index;
4367
4368    if (align_to_integer) {
4369       float x = (float) STBTT_ifloor((*xpos + b->xoff) + 0.5f);
4370       float y = (float) STBTT_ifloor((*ypos + b->yoff) + 0.5f);
4371       q->x0 = x;
4372       q->y0 = y;
4373       q->x1 = x + b->xoff2 - b->xoff;
4374       q->y1 = y + b->yoff2 - b->yoff;
4375    } else {
4376       q->x0 = *xpos + b->xoff;
4377       q->y0 = *ypos + b->yoff;
4378       q->x1 = *xpos + b->xoff2;
4379       q->y1 = *ypos + b->yoff2;
4380    }
4381
4382    q->s0 = b->x0 * ipw;
4383    q->t0 = b->y0 * iph;
4384    q->s1 = b->x1 * ipw;
4385    q->t1 = b->y1 * iph;
4386
4387    *xpos += b->xadvance;
4388 }
4389
4390 //////////////////////////////////////////////////////////////////////////////
4391 //
4392 // sdf computation
4393 //
4394
4395 #define STBTT_min(a,b)  ((a) < (b) ? (a) : (b))
4396 #define STBTT_max(a,b)  ((a) < (b) ? (b) : (a))
4397
4398 static int stbtt__ray_intersect_bezier(float orig[2], float ray[2], float q0[2], float q1[2], float q2[2], float hits[2][2])
4399 {
4400    float q0perp = q0[1]*ray[0] - q0[0]*ray[1];
4401    float q1perp = q1[1]*ray[0] - q1[0]*ray[1];
4402    float q2perp = q2[1]*ray[0] - q2[0]*ray[1];
4403    float roperp = orig[1]*ray[0] - orig[0]*ray[1];
4404
4405    float a = q0perp - 2*q1perp + q2perp;
4406    float b = q1perp - q0perp;
4407    float c = q0perp - roperp;
4408
4409    float s0 = 0., s1 = 0.;
4410    int num_s = 0;
4411
4412    if (a != 0.0) {
4413       float discr = b*b - a*c;
4414       if (discr > 0.0) {
4415          float rcpna = -1 / a;
4416          float d = (float) STBTT_sqrt(discr);
4417          s0 = (b+d) * rcpna;
4418          s1 = (b-d) * rcpna;
4419          if (s0 >= 0.0 && s0 <= 1.0)
4420             num_s = 1;
4421          if (d > 0.0 && s1 >= 0.0 && s1 <= 1.0) {
4422             if (num_s == 0) s0 = s1;
4423             ++num_s;
4424          }
4425       }
4426    } else {
4427       // 2*b*s + c = 0
4428       // s = -c / (2*b)
4429       s0 = c / (-2 * b);
4430       if (s0 >= 0.0 && s0 <= 1.0)
4431          num_s = 1;
4432    }
4433
4434    if (num_s == 0)
4435       return 0;
4436    else {
4437       float rcp_len2 = 1 / (ray[0]*ray[0] + ray[1]*ray[1]);
4438       float rayn_x = ray[0] * rcp_len2, rayn_y = ray[1] * rcp_len2;
4439
4440       float q0d =   q0[0]*rayn_x +   q0[1]*rayn_y;
4441       float q1d =   q1[0]*rayn_x +   q1[1]*rayn_y;
4442       float q2d =   q2[0]*rayn_x +   q2[1]*rayn_y;
4443       float rod = orig[0]*rayn_x + orig[1]*rayn_y;
4444
4445       float q10d = q1d - q0d;
4446       float q20d = q2d - q0d;
4447       float q0rd = q0d - rod;
4448
4449       hits[0][0] = q0rd + s0*(2.0f - 2.0f*s0)*q10d + s0*s0*q20d;
4450       hits[0][1] = a*s0+b;
4451
4452       if (num_s > 1) {
4453          hits[1][0] = q0rd + s1*(2.0f - 2.0f*s1)*q10d + s1*s1*q20d;
4454          hits[1][1] = a*s1+b;
4455          return 2;
4456       } else {
4457          return 1;
4458       }
4459    }
4460 }
4461
4462 static int equal(float *a, float *b)
4463 {
4464    return (a[0] == b[0] && a[1] == b[1]);
4465 }
4466
4467 static int stbtt__compute_crossings_x(float x, float y, int nverts, stbtt_vertex *verts)
4468 {
4469    int i;
4470    float orig[2], ray[2] = { 1, 0 };
4471    float y_frac;
4472    int winding = 0;
4473
4474    // make sure y never passes through a vertex of the shape
4475    y_frac = (float) STBTT_fmod(y, 1.0f);
4476    if (y_frac < 0.01f)
4477       y += 0.01f;
4478    else if (y_frac > 0.99f)
4479       y -= 0.01f;
4480
4481    orig[0] = x;
4482    orig[1] = y;
4483
4484    // test a ray from (-infinity,y) to (x,y)
4485    for (i=0; i < nverts; ++i) {
4486       if (verts[i].type == STBTT_vline) {
4487          int x0 = (int) verts[i-1].x, y0 = (int) verts[i-1].y;
4488          int x1 = (int) verts[i  ].x, y1 = (int) verts[i  ].y;
4489          if (y > STBTT_min(y0,y1) && y < STBTT_max(y0,y1) && x > STBTT_min(x0,x1)) {
4490             float x_inter = (y - y0) / (y1 - y0) * (x1-x0) + x0;
4491             if (x_inter < x)
4492                winding += (y0 < y1) ? 1 : -1;
4493          }
4494       }
4495       if (verts[i].type == STBTT_vcurve) {
4496          int x0 = (int) verts[i-1].x , y0 = (int) verts[i-1].y ;
4497          int x1 = (int) verts[i  ].cx, y1 = (int) verts[i  ].cy;
4498          int x2 = (int) verts[i  ].x , y2 = (int) verts[i  ].y ;
4499          int ax = STBTT_min(x0,STBTT_min(x1,x2)), ay = STBTT_min(y0,STBTT_min(y1,y2));
4500          int by = STBTT_max(y0,STBTT_max(y1,y2));
4501          if (y > ay && y < by && x > ax) {
4502             float q0[2],q1[2],q2[2];
4503             float hits[2][2];
4504             q0[0] = (float)x0;
4505             q0[1] = (float)y0;
4506             q1[0] = (float)x1;
4507             q1[1] = (float)y1;
4508             q2[0] = (float)x2;
4509             q2[1] = (float)y2;
4510             if (equal(q0,q1) || equal(q1,q2)) {
4511                x0 = (int)verts[i-1].x;
4512                y0 = (int)verts[i-1].y;
4513                x1 = (int)verts[i  ].x;
4514                y1 = (int)verts[i  ].y;
4515                if (y > STBTT_min(y0,y1) && y < STBTT_max(y0,y1) && x > STBTT_min(x0,x1)) {
4516                   float x_inter = (y - y0) / (y1 - y0) * (x1-x0) + x0;
4517                   if (x_inter < x)
4518                      winding += (y0 < y1) ? 1 : -1;
4519                }
4520             } else {
4521                int num_hits = stbtt__ray_intersect_bezier(orig, ray, q0, q1, q2, hits);
4522                if (num_hits >= 1)
4523                   if (hits[0][0] < 0)
4524                      winding += (hits[0][1] < 0 ? -1 : 1);
4525                if (num_hits >= 2)
4526                   if (hits[1][0] < 0)
4527                      winding += (hits[1][1] < 0 ? -1 : 1);
4528             }
4529          }
4530       }
4531    }
4532    return winding;
4533 }
4534
4535 static float stbtt__cuberoot( float x )
4536 {
4537    if (x<0)
4538       return -(float) STBTT_pow(-x,1.0f/3.0f);
4539    else
4540       return  (float) STBTT_pow( x,1.0f/3.0f);
4541 }
4542
4543 // x^3 + a*x^2 + b*x + c = 0
4544 static int stbtt__solve_cubic(float a, float b, float c, float* r)
4545 {
4546    float s = -a / 3;
4547    float p = b - a*a / 3;
4548    float q = a * (2*a*a - 9*b) / 27 + c;
4549    float p3 = p*p*p;
4550    float d = q*q + 4*p3 / 27;
4551    if (d >= 0) {
4552       float z = (float) STBTT_sqrt(d);
4553       float u = (-q + z) / 2;
4554       float v = (-q - z) / 2;
4555       u = stbtt__cuberoot(u);
4556       v = stbtt__cuberoot(v);
4557       r[0] = s + u + v;
4558       return 1;
4559    } else {
4560       float u = (float) STBTT_sqrt(-p/3);
4561       float v = (float) STBTT_acos(-STBTT_sqrt(-27/p3) * q / 2) / 3; // p3 must be negative, since d is negative
4562       float m = (float) STBTT_cos(v);
4563       float n = (float) STBTT_cos(v-3.141592/2)*1.732050808f;
4564       r[0] = s + u * 2 * m;
4565       r[1] = s - u * (m + n);
4566       r[2] = s - u * (m - n);
4567
4568       //STBTT_assert( STBTT_fabs(((r[0]+a)*r[0]+b)*r[0]+c) < 0.05f);  // these asserts may not be safe at all scales, though they're in bezier t parameter units so maybe?
4569       //STBTT_assert( STBTT_fabs(((r[1]+a)*r[1]+b)*r[1]+c) < 0.05f);
4570       //STBTT_assert( STBTT_fabs(((r[2]+a)*r[2]+b)*r[2]+c) < 0.05f);
4571       return 3;
4572    }
4573 }
4574
4575 STBTT_DEF unsigned char * stbtt_GetGlyphSDF(const stbtt_fontinfo *info, float scale, int glyph, int padding, unsigned char onedge_value, float pixel_dist_scale, int *width, int *height, int *xoff, int *yoff)
4576 {
4577    float scale_x = scale, scale_y = scale;
4578    int ix0,iy0,ix1,iy1;
4579    int w,h;
4580    unsigned char *data;
4581
4582    if (scale == 0) return NULL;
4583
4584    stbtt_GetGlyphBitmapBoxSubpixel(info, glyph, scale, scale, 0.0f,0.0f, &ix0,&iy0,&ix1,&iy1);
4585
4586    // if empty, return NULL
4587    if (ix0 == ix1 || iy0 == iy1)
4588       return NULL;
4589
4590    ix0 -= padding;
4591    iy0 -= padding;
4592    ix1 += padding;
4593    iy1 += padding;
4594
4595    w = (ix1 - ix0);
4596    h = (iy1 - iy0);
4597
4598    if (width ) *width  = w;
4599    if (height) *height = h;
4600    if (xoff  ) *xoff   = ix0;
4601    if (yoff  ) *yoff   = iy0;
4602
4603    // invert for y-downwards bitmaps
4604    scale_y = -scale_y;
4605
4606    {
4607       int x,y,i,j;
4608       float *precompute;
4609       stbtt_vertex *verts;
4610       int num_verts = stbtt_GetGlyphShape(info, glyph, &verts);
4611       data = (unsigned char *) STBTT_malloc(w * h, info->userdata);
4612       precompute = (float *) STBTT_malloc(num_verts * sizeof(float), info->userdata);
4613
4614       for (i=0,j=num_verts-1; i < num_verts; j=i++) {
4615          if (verts[i].type == STBTT_vline) {
4616             float x0 = verts[i].x*scale_x, y0 = verts[i].y*scale_y;
4617             float x1 = verts[j].x*scale_x, y1 = verts[j].y*scale_y;
4618             float dist = (float) STBTT_sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0));
4619             precompute[i] = (dist == 0) ? 0.0f : 1.0f / dist;
4620          } else if (verts[i].type == STBTT_vcurve) {
4621             float x2 = verts[j].x *scale_x, y2 = verts[j].y *scale_y;
4622             float x1 = verts[i].cx*scale_x, y1 = verts[i].cy*scale_y;
4623             float x0 = verts[i].x *scale_x, y0 = verts[i].y *scale_y;
4624             float bx = x0 - 2*x1 + x2, by = y0 - 2*y1 + y2;
4625             float len2 = bx*bx + by*by;
4626             if (len2 != 0.0f)
4627                precompute[i] = 1.0f / (bx*bx + by*by);
4628             else
4629                precompute[i] = 0.0f;
4630          } else
4631             precompute[i] = 0.0f;
4632       }
4633
4634       for (y=iy0; y < iy1; ++y) {
4635          for (x=ix0; x < ix1; ++x) {
4636             float val;
4637             float min_dist = 999999.0f;
4638             float sx = (float) x + 0.5f;
4639             float sy = (float) y + 0.5f;
4640             float x_gspace = (sx / scale_x);
4641             float y_gspace = (sy / scale_y);
4642
4643             int winding = stbtt__compute_crossings_x(x_gspace, y_gspace, num_verts, verts); // @OPTIMIZE: this could just be a rasterization, but needs to be line vs. non-tesselated curves so a new path
4644
4645             for (i=0; i < num_verts; ++i) {
4646                float x0 = verts[i].x*scale_x, y0 = verts[i].y*scale_y;
4647
4648                if (verts[i].type == STBTT_vline && precompute[i] != 0.0f) {
4649                   float x1 = verts[i-1].x*scale_x, y1 = verts[i-1].y*scale_y;
4650
4651                   float dist,dist2 = (x0-sx)*(x0-sx) + (y0-sy)*(y0-sy);
4652                   if (dist2 < min_dist*min_dist)
4653                      min_dist = (float) STBTT_sqrt(dist2);
4654
4655                   // coarse culling against bbox
4656                   //if (sx > STBTT_min(x0,x1)-min_dist && sx < STBTT_max(x0,x1)+min_dist &&
4657                   //    sy > STBTT_min(y0,y1)-min_dist && sy < STBTT_max(y0,y1)+min_dist)
4658                   dist = (float) STBTT_fabs((x1-x0)*(y0-sy) - (y1-y0)*(x0-sx)) * precompute[i];
4659                   STBTT_assert(i != 0);
4660                   if (dist < min_dist) {
4661                      // check position along line
4662                      // x' = x0 + t*(x1-x0), y' = y0 + t*(y1-y0)
4663                      // minimize (x'-sx)*(x'-sx)+(y'-sy)*(y'-sy)
4664                      float dx = x1-x0, dy = y1-y0;
4665                      float px = x0-sx, py = y0-sy;
4666                      // minimize (px+t*dx)^2 + (py+t*dy)^2 = px*px + 2*px*dx*t + t^2*dx*dx + py*py + 2*py*dy*t + t^2*dy*dy
4667                      // derivative: 2*px*dx + 2*py*dy + (2*dx*dx+2*dy*dy)*t, set to 0 and solve
4668                      float t = -(px*dx + py*dy) / (dx*dx + dy*dy);
4669                      if (t >= 0.0f && t <= 1.0f)
4670                         min_dist = dist;
4671                   }
4672                } else if (verts[i].type == STBTT_vcurve) {
4673                   float x2 = verts[i-1].x *scale_x, y2 = verts[i-1].y *scale_y;
4674                   float x1 = verts[i  ].cx*scale_x, y1 = verts[i  ].cy*scale_y;
4675                   float box_x0 = STBTT_min(STBTT_min(x0,x1),x2);
4676                   float box_y0 = STBTT_min(STBTT_min(y0,y1),y2);
4677                   float box_x1 = STBTT_max(STBTT_max(x0,x1),x2);
4678                   float box_y1 = STBTT_max(STBTT_max(y0,y1),y2);
4679                   // coarse culling against bbox to avoid computing cubic unnecessarily
4680                   if (sx > box_x0-min_dist && sx < box_x1+min_dist && sy > box_y0-min_dist && sy < box_y1+min_dist) {
4681                      int num=0;
4682                      float ax = x1-x0, ay = y1-y0;
4683                      float bx = x0 - 2*x1 + x2, by = y0 - 2*y1 + y2;
4684                      float mx = x0 - sx, my = y0 - sy;
4685                      float res[3] = {0.f,0.f,0.f};
4686                      float px,py,t,it,dist2;
4687                      float a_inv = precompute[i];
4688                      if (a_inv == 0.0) { // if a_inv is 0, it's 2nd degree so use quadratic formula
4689                         float a = 3*(ax*bx + ay*by);
4690                         float b = 2*(ax*ax + ay*ay) + (mx*bx+my*by);
4691                         float c = mx*ax+my*ay;
4692                         if (a == 0.0) { // if a is 0, it's linear
4693                            if (b != 0.0) {
4694                               res[num++] = -c/b;
4695                            }
4696                         } else {
4697                            float discriminant = b*b - 4*a*c;
4698                            if (discriminant < 0)
4699                               num = 0;
4700                            else {
4701                               float root = (float) STBTT_sqrt(discriminant);
4702                               res[0] = (-b - root)/(2*a);
4703                               res[1] = (-b + root)/(2*a);
4704                               num = 2; // don't bother distinguishing 1-solution case, as code below will still work
4705                            }
4706                         }
4707                      } else {
4708                         float b = 3*(ax*bx + ay*by) * a_inv; // could precompute this as it doesn't depend on sample point
4709                         float c = (2*(ax*ax + ay*ay) + (mx*bx+my*by)) * a_inv;
4710                         float d = (mx*ax+my*ay) * a_inv;
4711                         num = stbtt__solve_cubic(b, c, d, res);
4712                      }
4713                      dist2 = (x0-sx)*(x0-sx) + (y0-sy)*(y0-sy);
4714                      if (dist2 < min_dist*min_dist)
4715                         min_dist = (float) STBTT_sqrt(dist2);
4716
4717                      if (num >= 1 && res[0] >= 0.0f && res[0] <= 1.0f) {
4718                         t = res[0], it = 1.0f - t;
4719                         px = it*it*x0 + 2*t*it*x1 + t*t*x2;
4720                         py = it*it*y0 + 2*t*it*y1 + t*t*y2;
4721                         dist2 = (px-sx)*(px-sx) + (py-sy)*(py-sy);
4722                         if (dist2 < min_dist * min_dist)
4723                            min_dist = (float) STBTT_sqrt(dist2);
4724                      }
4725                      if (num >= 2 && res[1] >= 0.0f && res[1] <= 1.0f) {
4726                         t = res[1], it = 1.0f - t;
4727                         px = it*it*x0 + 2*t*it*x1 + t*t*x2;
4728                         py = it*it*y0 + 2*t*it*y1 + t*t*y2;
4729                         dist2 = (px-sx)*(px-sx) + (py-sy)*(py-sy);
4730                         if (dist2 < min_dist * min_dist)
4731                            min_dist = (float) STBTT_sqrt(dist2);
4732                      }
4733                      if (num >= 3 && res[2] >= 0.0f && res[2] <= 1.0f) {
4734                         t = res[2], it = 1.0f - t;
4735                         px = it*it*x0 + 2*t*it*x1 + t*t*x2;
4736                         py = it*it*y0 + 2*t*it*y1 + t*t*y2;
4737                         dist2 = (px-sx)*(px-sx) + (py-sy)*(py-sy);
4738                         if (dist2 < min_dist * min_dist)
4739                            min_dist = (float) STBTT_sqrt(dist2);
4740                      }
4741                   }
4742                }
4743             }
4744             if (winding == 0)
4745                min_dist = -min_dist;  // if outside the shape, value is negative
4746             val = onedge_value + pixel_dist_scale * min_dist;
4747             if (val < 0)
4748                val = 0;
4749             else if (val > 255)
4750                val = 255;
4751             data[(y-iy0)*w+(x-ix0)] = (unsigned char) val;
4752          }
4753       }
4754       STBTT_free(precompute, info->userdata);
4755       STBTT_free(verts, info->userdata);
4756    }
4757    return data;
4758 }
4759
4760 STBTT_DEF unsigned char * stbtt_GetCodepointSDF(const stbtt_fontinfo *info, float scale, int codepoint, int padding, unsigned char onedge_value, float pixel_dist_scale, int *width, int *height, int *xoff, int *yoff)
4761 {
4762    return stbtt_GetGlyphSDF(info, scale, stbtt_FindGlyphIndex(info, codepoint), padding, onedge_value, pixel_dist_scale, width, height, xoff, yoff);
4763 }
4764
4765 STBTT_DEF void stbtt_FreeSDF(unsigned char *bitmap, void *userdata)
4766 {
4767    STBTT_free(bitmap, userdata);
4768 }
4769
4770 //////////////////////////////////////////////////////////////////////////////
4771 //
4772 // font name matching -- recommended not to use this
4773 //
4774
4775 // check if a utf8 string contains a prefix which is the utf16 string; if so return length of matching utf8 string
4776 static stbtt_int32 stbtt__CompareUTF8toUTF16_bigendian_prefix(stbtt_uint8 *s1, stbtt_int32 len1, stbtt_uint8 *s2, stbtt_int32 len2)
4777 {
4778    stbtt_int32 i=0;
4779
4780    // convert utf16 to utf8 and compare the results while converting
4781    while (len2) {
4782       stbtt_uint16 ch = s2[0]*256 + s2[1];
4783       if (ch < 0x80) {
4784          if (i >= len1) return -1;
4785          if (s1[i++] != ch) return -1;
4786       } else if (ch < 0x800) {
4787          if (i+1 >= len1) return -1;
4788          if (s1[i++] != 0xc0 + (ch >> 6)) return -1;
4789          if (s1[i++] != 0x80 + (ch & 0x3f)) return -1;
4790       } else if (ch >= 0xd800 && ch < 0xdc00) {
4791          stbtt_uint32 c;
4792          stbtt_uint16 ch2 = s2[2]*256 + s2[3];
4793          if (i+3 >= len1) return -1;
4794          c = ((ch - 0xd800) << 10) + (ch2 - 0xdc00) + 0x10000;
4795          if (s1[i++] != 0xf0 + (c >> 18)) return -1;
4796          if (s1[i++] != 0x80 + ((c >> 12) & 0x3f)) return -1;
4797          if (s1[i++] != 0x80 + ((c >>  6) & 0x3f)) return -1;
4798          if (s1[i++] != 0x80 + ((c      ) & 0x3f)) return -1;
4799          s2 += 2; // plus another 2 below
4800          len2 -= 2;
4801       } else if (ch >= 0xdc00 && ch < 0xe000) {
4802          return -1;
4803       } else {
4804          if (i+2 >= len1) return -1;
4805          if (s1[i++] != 0xe0 + (ch >> 12)) return -1;
4806          if (s1[i++] != 0x80 + ((ch >> 6) & 0x3f)) return -1;
4807          if (s1[i++] != 0x80 + ((ch     ) & 0x3f)) return -1;
4808       }
4809       s2 += 2;
4810       len2 -= 2;
4811    }
4812    return i;
4813 }
4814
4815 static int stbtt_CompareUTF8toUTF16_bigendian_internal(char *s1, int len1, char *s2, int len2)
4816 {
4817    return len1 == stbtt__CompareUTF8toUTF16_bigendian_prefix((stbtt_uint8*) s1, len1, (stbtt_uint8*) s2, len2);
4818 }
4819
4820 // returns results in whatever encoding you request... but note that 2-byte encodings
4821 // will be BIG-ENDIAN... use stbtt_CompareUTF8toUTF16_bigendian() to compare
4822 STBTT_DEF const char *stbtt_GetFontNameString(const stbtt_fontinfo *font, int *length, int platformID, int encodingID, int languageID, int nameID)
4823 {
4824    stbtt_int32 i,count,stringOffset;
4825    stbtt_uint8 *fc = font->data;
4826    stbtt_uint32 offset = font->fontstart;
4827    stbtt_uint32 nm = stbtt__find_table(fc, offset, "name");
4828    if (!nm) return NULL;
4829
4830    count = ttUSHORT(fc+nm+2);
4831    stringOffset = nm + ttUSHORT(fc+nm+4);
4832    for (i=0; i < count; ++i) {
4833       stbtt_uint32 loc = nm + 6 + 12 * i;
4834       if (platformID == ttUSHORT(fc+loc+0) && encodingID == ttUSHORT(fc+loc+2)
4835           && languageID == ttUSHORT(fc+loc+4) && nameID == ttUSHORT(fc+loc+6)) {
4836          *length = ttUSHORT(fc+loc+8);
4837          return (const char *) (fc+stringOffset+ttUSHORT(fc+loc+10));
4838       }
4839    }
4840    return NULL;
4841 }
4842
4843 static int stbtt__matchpair(stbtt_uint8 *fc, stbtt_uint32 nm, stbtt_uint8 *name, stbtt_int32 nlen, stbtt_int32 target_id, stbtt_int32 next_id)
4844 {
4845    stbtt_int32 i;
4846    stbtt_int32 count = ttUSHORT(fc+nm+2);
4847    stbtt_int32 stringOffset = nm + ttUSHORT(fc+nm+4);
4848
4849    for (i=0; i < count; ++i) {
4850       stbtt_uint32 loc = nm + 6 + 12 * i;
4851       stbtt_int32 id = ttUSHORT(fc+loc+6);
4852       if (id == target_id) {
4853          // find the encoding
4854          stbtt_int32 platform = ttUSHORT(fc+loc+0), encoding = ttUSHORT(fc+loc+2), language = ttUSHORT(fc+loc+4);
4855
4856          // is this a Unicode encoding?
4857          if (platform == 0 || (platform == 3 && encoding == 1) || (platform == 3 && encoding == 10)) {
4858             stbtt_int32 slen = ttUSHORT(fc+loc+8);
4859             stbtt_int32 off = ttUSHORT(fc+loc+10);
4860
4861             // check if there's a prefix match
4862             stbtt_int32 matchlen = stbtt__CompareUTF8toUTF16_bigendian_prefix(name, nlen, fc+stringOffset+off,slen);
4863             if (matchlen >= 0) {
4864                // check for target_id+1 immediately following, with same encoding & language
4865                if (i+1 < count && ttUSHORT(fc+loc+12+6) == next_id && ttUSHORT(fc+loc+12) == platform && ttUSHORT(fc+loc+12+2) == encoding && ttUSHORT(fc+loc+12+4) == language) {
4866                   slen = ttUSHORT(fc+loc+12+8);
4867                   off = ttUSHORT(fc+loc+12+10);
4868                   if (slen == 0) {
4869                      if (matchlen == nlen)
4870                         return 1;
4871                   } else if (matchlen < nlen && name[matchlen] == ' ') {
4872                      ++matchlen;
4873                      if (stbtt_CompareUTF8toUTF16_bigendian_internal((char*) (name+matchlen), nlen-matchlen, (char*)(fc+stringOffset+off),slen))
4874                         return 1;
4875                   }
4876                } else {
4877                   // if nothing immediately following
4878                   if (matchlen == nlen)
4879                      return 1;
4880                }
4881             }
4882          }
4883
4884          // @TODO handle other encodings
4885       }
4886    }
4887    return 0;
4888 }
4889
4890 static int stbtt__matches(stbtt_uint8 *fc, stbtt_uint32 offset, stbtt_uint8 *name, stbtt_int32 flags)
4891 {
4892    stbtt_int32 nlen = (stbtt_int32) STBTT_strlen((char *) name);
4893    stbtt_uint32 nm,hd;
4894    if (!stbtt__isfont(fc+offset)) return 0;
4895
4896    // check italics/bold/underline flags in macStyle...
4897    if (flags) {
4898       hd = stbtt__find_table(fc, offset, "head");
4899       if ((ttUSHORT(fc+hd+44) & 7) != (flags & 7)) return 0;
4900    }
4901
4902    nm = stbtt__find_table(fc, offset, "name");
4903    if (!nm) return 0;
4904
4905    if (flags) {
4906       // if we checked the macStyle flags, then just check the family and ignore the subfamily
4907       if (stbtt__matchpair(fc, nm, name, nlen, 16, -1))  return 1;
4908       if (stbtt__matchpair(fc, nm, name, nlen,  1, -1))  return 1;
4909       if (stbtt__matchpair(fc, nm, name, nlen,  3, -1))  return 1;
4910    } else {
4911       if (stbtt__matchpair(fc, nm, name, nlen, 16, 17))  return 1;
4912       if (stbtt__matchpair(fc, nm, name, nlen,  1,  2))  return 1;
4913       if (stbtt__matchpair(fc, nm, name, nlen,  3, -1))  return 1;
4914    }
4915
4916    return 0;
4917 }
4918
4919 static int stbtt_FindMatchingFont_internal(unsigned char *font_collection, char *name_utf8, stbtt_int32 flags)
4920 {
4921    stbtt_int32 i;
4922    for (i=0;;++i) {
4923       stbtt_int32 off = stbtt_GetFontOffsetForIndex(font_collection, i);
4924       if (off < 0) return off;
4925       if (stbtt__matches((stbtt_uint8 *) font_collection, off, (stbtt_uint8*) name_utf8, flags))
4926          return off;
4927    }
4928 }
4929
4930 #if defined(__GNUC__) || defined(__clang__)
4931 #pragma GCC diagnostic push
4932 #pragma GCC diagnostic ignored "-Wcast-qual"
4933 #endif
4934
4935 STBTT_DEF int stbtt_BakeFontBitmap(const unsigned char *data, int offset,
4936                                 float pixel_height, unsigned char *pixels, int pw, int ph,
4937                                 int first_char, int num_chars, stbtt_bakedchar *chardata)
4938 {
4939    return stbtt_BakeFontBitmap_internal((unsigned char *) data, offset, pixel_height, pixels, pw, ph, first_char, num_chars, chardata);
4940 }
4941
4942 STBTT_DEF int stbtt_GetFontOffsetForIndex(const unsigned char *data, int index)
4943 {
4944    return stbtt_GetFontOffsetForIndex_internal((unsigned char *) data, index);
4945 }
4946
4947 STBTT_DEF int stbtt_GetNumberOfFonts(const unsigned char *data)
4948 {
4949    return stbtt_GetNumberOfFonts_internal((unsigned char *) data);
4950 }
4951
4952 STBTT_DEF int stbtt_InitFont(stbtt_fontinfo *info, const unsigned char *data, int offset)
4953 {
4954    return stbtt_InitFont_internal(info, (unsigned char *) data, offset);
4955 }
4956
4957 STBTT_DEF int stbtt_FindMatchingFont(const unsigned char *fontdata, const char *name, int flags)
4958 {
4959    return stbtt_FindMatchingFont_internal((unsigned char *) fontdata, (char *) name, flags);
4960 }
4961
4962 STBTT_DEF int stbtt_CompareUTF8toUTF16_bigendian(const char *s1, int len1, const char *s2, int len2)
4963 {
4964    return stbtt_CompareUTF8toUTF16_bigendian_internal((char *) s1, len1, (char *) s2, len2);
4965 }
4966
4967 #if defined(__GNUC__) || defined(__clang__)
4968 #pragma GCC diagnostic pop
4969 #endif
4970
4971 #endif // STB_TRUETYPE_IMPLEMENTATION
4972
4973
4974 // FULL VERSION HISTORY
4975 //
4976 //   1.25 (2021-07-11) many fixes
4977 //   1.24 (2020-02-05) fix warning
4978 //   1.23 (2020-02-02) query SVG data for glyphs; query whole kerning table (but only kern not GPOS)
4979 //   1.22 (2019-08-11) minimize missing-glyph duplication; fix kerning if both 'GPOS' and 'kern' are defined
4980 //   1.21 (2019-02-25) fix warning
4981 //   1.20 (2019-02-07) PackFontRange skips missing codepoints; GetScaleFontVMetrics()
4982 //   1.19 (2018-02-11) OpenType GPOS kerning (horizontal only), STBTT_fmod
4983 //   1.18 (2018-01-29) add missing function
4984 //   1.17 (2017-07-23) make more arguments const; doc fix
4985 //   1.16 (2017-07-12) SDF support
4986 //   1.15 (2017-03-03) make more arguments const
4987 //   1.14 (2017-01-16) num-fonts-in-TTC function
4988 //   1.13 (2017-01-02) support OpenType fonts, certain Apple fonts
4989 //   1.12 (2016-10-25) suppress warnings about casting away const with -Wcast-qual
4990 //   1.11 (2016-04-02) fix unused-variable warning
4991 //   1.10 (2016-04-02) allow user-defined fabs() replacement
4992 //                     fix memory leak if fontsize=0.0
4993 //                     fix warning from duplicate typedef
4994 //   1.09 (2016-01-16) warning fix; avoid crash on outofmem; use alloc userdata for PackFontRanges
4995 //   1.08 (2015-09-13) document stbtt_Rasterize(); fixes for vertical & horizontal edges
4996 //   1.07 (2015-08-01) allow PackFontRanges to accept arrays of sparse codepoints;
4997 //                     allow PackFontRanges to pack and render in separate phases;
4998 //                     fix stbtt_GetFontOFfsetForIndex (never worked for non-0 input?);
4999 //                     fixed an assert() bug in the new rasterizer
5000 //                     replace assert() with STBTT_assert() in new rasterizer
5001 //   1.06 (2015-07-14) performance improvements (~35% faster on x86 and x64 on test machine)
5002 //                     also more precise AA rasterizer, except if shapes overlap
5003 //                     remove need for STBTT_sort
5004 //   1.05 (2015-04-15) fix misplaced definitions for STBTT_STATIC
5005 //   1.04 (2015-04-15) typo in example
5006 //   1.03 (2015-04-12) STBTT_STATIC, fix memory leak in new packing, various fixes
5007 //   1.02 (2014-12-10) fix various warnings & compile issues w/ stb_rect_pack, C++
5008 //   1.01 (2014-12-08) fix subpixel position when oversampling to exactly match
5009 //                        non-oversampled; STBTT_POINT_SIZE for packed case only
5010 //   1.00 (2014-12-06) add new PackBegin etc. API, w/ support for oversampling
5011 //   0.99 (2014-09-18) fix multiple bugs with subpixel rendering (ryg)
5012 //   0.9  (2014-08-07) support certain mac/iOS fonts without an MS platformID
5013 //   0.8b (2014-07-07) fix a warning
5014 //   0.8  (2014-05-25) fix a few more warnings
5015 //   0.7  (2013-09-25) bugfix: subpixel glyph bug fixed in 0.5 had come back
5016 //   0.6c (2012-07-24) improve documentation
5017 //   0.6b (2012-07-20) fix a few more warnings
5018 //   0.6  (2012-07-17) fix warnings; added stbtt_ScaleForMappingEmToPixels,
5019 //                        stbtt_GetFontBoundingBox, stbtt_IsGlyphEmpty
5020 //   0.5  (2011-12-09) bugfixes:
5021 //                        subpixel glyph renderer computed wrong bounding box
5022 //                        first vertex of shape can be off-curve (FreeSans)
5023 //   0.4b (2011-12-03) fixed an error in the font baking example
5024 //   0.4  (2011-12-01) kerning, subpixel rendering (tor)
5025 //                    bugfixes for:
5026 //                        codepoint-to-glyph conversion using table fmt=12
5027 //                        codepoint-to-glyph conversion using table fmt=4
5028 //                        stbtt_GetBakedQuad with non-square texture (Zer)
5029 //                    updated Hello World! sample to use kerning and subpixel
5030 //                    fixed some warnings
5031 //   0.3  (2009-06-24) cmap fmt=12, compound shapes (MM)
5032 //                    userdata, malloc-from-userdata, non-zero fill (stb)
5033 //   0.2  (2009-03-11) Fix unsigned/signed char warnings
5034 //   0.1  (2009-03-09) First public release
5035 //
5036
5037 /*
5038 ------------------------------------------------------------------------------
5039 This software is available under 2 licenses -- choose whichever you prefer.
5040 ------------------------------------------------------------------------------
5041 ALTERNATIVE A - MIT License
5042 Copyright (c) 2017 Sean Barrett
5043 Permission is hereby granted, free of charge, to any person obtaining a copy of
5044 this software and associated documentation files (the "Software"), to deal in
5045 the Software without restriction, including without limitation the rights to
5046 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
5047 of the Software, and to permit persons to whom the Software is furnished to do
5048 so, subject to the following conditions:
5049 The above copyright notice and this permission notice shall be included in all
5050 copies or substantial portions of the Software.
5051 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
5052 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
5053 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
5054 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
5055 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
5056 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
5057 SOFTWARE.
5058 ------------------------------------------------------------------------------
5059 ALTERNATIVE B - Public Domain (www.unlicense.org)
5060 This is free and unencumbered software released into the public domain.
5061 Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
5062 software, either in source code form or as a compiled binary, for any purpose,
5063 commercial or non-commercial, and by any means.
5064 In jurisdictions that recognize copyright laws, the author or authors of this
5065 software dedicate any and all copyright interest in the software to the public
5066 domain. We make this dedication for the benefit of the public at large and to
5067 the detriment of our heirs and successors. We intend this dedication to be an
5068 overt act of relinquishment in perpetuity of all present and future rights to
5069 this software under copyright law.
5070 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
5071 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
5072 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
5073 AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
5074 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
5075 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
5076 ------------------------------------------------------------------------------
5077 */