package pdf

import "core:math"
import "core:mem"

// TrueType and OpenType font programs: the `glyf`/`loca` outlines, the `cmap`
// character map, `hmtx` advances and `post` glyph names.
//
// References are to ISO/IEC 14496-22 (Open Font Format), whose table layouts
// are identical to Apple's TrueType Reference Manual for everything read here.
//
// Nothing in this file knows about PDF. Bytes in, outlines out: a font program
// is a self-contained format that happens to be embedded in PDF, and keeping
// the two apart is what makes this separately testable and what lets the same
// reader serve a FontFile2, a CIDFontType2 and an OpenType wrapper alike.
//
// The fonts this sees are the most malformed data in a PDF. Subsetters strip
// tables, rewrite `loca` badly, leave `numGlyphs` disagreeing with the data,
// and truncate the last table in the file. Every offset here is therefore
// bounds-checked at the point of use and every loop is bounded, and a glyph
// that cannot be read draws nothing rather than failing the font: the page
// still has to come out.
//
// MEMORY: `tt_parse` takes an `allocator` and makes exactly two lasting
// allocations from it -- the TrueType_Font itself and, when the font has a
// usable `post` table, its glyph-name array. Everything else it keeps is a
// sub-slice of `data`, which the caller owns and must keep alive for as long
// as the font. There is no destructor: the intended allocator is the
// Document's arena. `tt_parse` and `tt_glyph_path` each take scratch from
// `context.allocator` as well, and free it before returning.

// A composite glyph may reference other composites. Five levels is deeper than
// any real font goes; a subsetter that produces a glyph referencing itself is
// stopped here.
@(private)
MAX_TT_COMPONENT_DEPTH :: 6
// Components one glyph may expand to, across all nesting levels. A composite
// chain is a graph the file controls, so it needs fuel as well as a depth cap.
@(private)
MAX_TT_COMPONENTS :: 512
// Points one glyph may expand to. The format's own ceiling is 32767 points per
// simple glyph; a composite can legitimately hold several of those.
@(private)
MAX_TT_GLYPH_POINTS :: 1 << 18
// `numGlyphs` is a u16 in `maxp`, so this is the format's own limit and not an
// invented one.
@(private)
MAX_TT_GLYPHS :: 65536
// Table records one directory may name. The format allows 65535; no real font
// has fifty.
@(private)
MAX_TT_TABLES :: 512

// Sfnt tags, big-endian, as they appear in the file.
@(private) TT_TAG_TTCF :: u32(0x74746366)   // 'ttcf', a TrueType Collection
@(private) TT_TAG_OTTO :: u32(0x4F54544F)   // 'OTTO', CFF outlines
@(private) TT_TAG_TRUE :: u32(0x74727565)   // 'true', Apple's variant
@(private) TT_TAG_V1   :: u32(0x00010000)
@(private) TT_TAG_V2   :: u32(0x00020000)

TrueType_Font :: struct {
    data: []byte,

    // Tables, as sub-slices of `data`. Empty when the font has none.
    glyf: []byte,
    loca: []byte,
    hmtx: []byte,
    cff:  []byte,

    units_per_em:  f64,
    num_glyphs:    int,
    num_h_metrics: int,
    // `head.indexToLocFormat`: false for u16 offsets stored halved, true for
    // u32 offsets.
    long_loca:     bool,
    // An OpenType font whose outlines are CFF: no `glyf`, and `tt_cff_data`
    // hands the table to the CFF reader.
    is_otto:       bool,

    // The `cmap` subtables worth having, chosen once when the font is parsed.
    // All three are exposed rather than merged because the rules for which one
    // a PDF font should use depend on the font dictionary's symbolic flag,
    // which this file deliberately knows nothing about.
    cmap_unicode: []byte,   // (3,10), (3,1) or a platform-0 table
    cmap_symbol:  []byte,   // (3,0): codes are conventionally 0xF000 + a byte
    cmap_mac:     []byte,   // (1,0): Mac Roman byte codes

    // `post` glyph names indexed by glyph id, "" where the font gives none.
    // Entries point into `data` or at a static name; the slice itself is the
    // font's only other allocation.
    names: []string,
}

// ---------------------------------------------------------------------------
// Byte access
//
// Every reader returns zero for an offset that is not wholly inside the slice.
// A header field that reads as zero degrades into a default a few lines later,
// which is what a truncated table should do; the loops that walk arrays check
// their own bounds before reading, because there a zero would be data.
// ---------------------------------------------------------------------------

@(private)
tt_u8 :: proc "contextless" (b: []byte, off: int) -> u8 {
    if off < 0 || off >= len(b) { return 0 }
    return b[off]
}

@(private)
tt_u16 :: proc "contextless" (b: []byte, off: int) -> u16 {
    if off < 0 || off + 2 > len(b) { return 0 }
    return u16(b[off]) << 8 | u16(b[off + 1])
}

@(private)
tt_i16 :: proc "contextless" (b: []byte, off: int) -> i16 {
    return i16(tt_u16(b, off))
}

@(private)
tt_u32 :: proc "contextless" (b: []byte, off: int) -> u32 {
    if off < 0 || off + 4 > len(b) { return 0 }
    return u32(b[off]) << 24 | u32(b[off + 1]) << 16 | u32(b[off + 2]) << 8 | u32(b[off + 3])
}

// tt_f2dot14 reads the fixed-point number composite transforms are written in:
// a signed 16-bit value with 14 fraction bits.
@(private)
tt_f2dot14 :: proc "contextless" (b: []byte, off: int) -> f64 {
    return f64(tt_i16(b, off)) / 16384
}

// tt_slice returns the sub-slice a table record names, clamped to the data
// that is actually there. A last table whose length runs past the end of the
// file is the single most common damage in an embedded font program, so it is
// truncated rather than dropped.
@(private)
tt_slice :: proc "contextless" (data: []byte, off, length: u32) -> []byte {
    if u64(off) >= u64(len(data)) { return nil }
    o := int(off)
    n := len(data) - o
    if u64(length) < u64(n) { n = int(length) }
    return data[o:][:n]
}

// ---------------------------------------------------------------------------
// Parsing
// ---------------------------------------------------------------------------

// tt_parse reads a font program's table directory.
//
// `data` is borrowed, not copied: the font holds sub-slices of it and the
// caller must keep it alive. The font and its glyph-name table come from
// `allocator`.
@(private)
tt_parse :: proc(data: []byte, allocator := context.allocator) -> (^TrueType_Font, Error) {
    if len(data) < 12 { return nil, .Bad_TrueType }

    base := 0
    tag := tt_u32(data, 0)
    if tag == TT_TAG_TTCF {
        // A TrueType Collection holds several fonts sharing tables. A PDF
        // FontFile2 has no way to say which face it means, so the first one is
        // the only defensible choice. ISO 14496-22, 5.2.
        if tt_u32(data, 8) == 0 { return nil, .Bad_TrueType }
        base = int(tt_u32(data, 12))
        if base < 0 || base + 12 > len(data) { return nil, .Bad_TrueType }
        tag = tt_u32(data, base)
    }
    otto := tag == TT_TAG_OTTO
    if tag != TT_TAG_V1 && tag != TT_TAG_V2 && tag != TT_TAG_TRUE && !otto {
        return nil, .Bad_TrueType
    }

    num_tables := int(tt_u16(data, base + 4))
    if num_tables > MAX_TT_TABLES { num_tables = MAX_TT_TABLES }
    // A directory truncated mid-record still names the tables before it.
    avail := (len(data) - (base + 12)) / 16
    if avail < 0 { avail = 0 }
    if num_tables > avail { num_tables = avail }
    if num_tables == 0 { return nil, .Bad_TrueType }

    head, maxp, hhea, post, cmap: []byte
    f := new(TrueType_Font, allocator)
    if f == nil { return nil, .Out_Of_Memory }
    f.data = data
    f.is_otto = otto

    for i in 0 ..< num_tables {
        rec := base + 12 + i * 16
        t := tt_slice(data, tt_u32(data, rec + 8), tt_u32(data, rec + 12))
        if len(t) == 0 { continue }
        // The first record for a tag wins. Directories with a tag twice exist,
        // and no reader agrees on which one is meant; taking the first at
        // least makes this deterministic.
        switch tt_u32(data, rec) {
        case 0x68656164: if head == nil { head = t }     // 'head'
        case 0x6D617870: if maxp == nil { maxp = t }     // 'maxp'
        case 0x68686561: if hhea == nil { hhea = t }     // 'hhea'
        case 0x686D7478: if f.hmtx == nil { f.hmtx = t } // 'hmtx'
        case 0x676C7966: if f.glyf == nil { f.glyf = t } // 'glyf'
        case 0x6C6F6361: if f.loca == nil { f.loca = t } // 'loca'
        case 0x706F7374: if post == nil { post = t }     // 'post'
        case 0x636D6170: if cmap == nil { cmap = t }     // 'cmap'
        case 0x43464620: if f.cff == nil { f.cff = t }   // 'CFF '
        }
    }

    // ISO 14496-22, 5.2.2: unitsPerEm at 18, indexToLocFormat at 50.
    f.units_per_em = f64(tt_u16(head, 18))
    if f.units_per_em == 0 {
        // Zero would make every glyph infinitely large. 1000 is the value a
        // PDF font matrix assumes when it has nothing better.
        f.units_per_em = 1000
    }
    f.long_loca = tt_i16(head, 50) != 0

    f.num_glyphs = int(tt_u16(maxp, 4))
    if f.num_glyphs == 0 {
        // No usable maxp. loca has one more entry than there are glyphs, which
        // is enough to keep the outlines reachable.
        if f.long_loca {
            f.num_glyphs = len(f.loca) / 4 - 1
        } else {
            f.num_glyphs = len(f.loca) / 2 - 1
        }
        if f.num_glyphs < 0 { f.num_glyphs = 0 }
    }
    if f.num_glyphs > MAX_TT_GLYPHS { f.num_glyphs = MAX_TT_GLYPHS }

    // ISO 14496-22, 5.2.3: numberOfHMetrics is the last field of hhea.
    f.num_h_metrics = int(tt_u16(hhea, 34))
    if f.num_h_metrics > f.num_glyphs { f.num_h_metrics = f.num_glyphs }
    if f.num_h_metrics == 0 && len(f.hmtx) >= 4 && f.num_glyphs > 0 {
        // A hhea that is missing or truncated leaves no metric count, but the
        // hmtx beside it is usually intact. One advance shared by every glyph
        // is a poor answer; zero for every glyph is a worse one, because it
        // piles the whole line of text on one spot.
        f.num_h_metrics = 1
    }

    tt_select_cmaps(f, cmap)
    tt_parse_post(f, post, allocator)
    return f, .None
}

// tt_glyph_count is the number of glyph ids the font defines. Glyph 0 is
// .notdef and is included.
@(private)
tt_glyph_count :: proc(f: ^TrueType_Font) -> int {
    if f == nil { return 0 }
    return f.num_glyphs
}

// tt_units_per_em is the side of the em square in font units: the divisor that
// turns a glyph outline into text space. 1000 for a font that gives none.
@(private)
tt_units_per_em :: proc(f: ^TrueType_Font) -> f64 {
    if f == nil { return 1000 }
    return f.units_per_em
}

// tt_has_glyf reports whether the font carries TrueType outlines. An OpenType
// font with CFF outlines does not; `tt_cff_data` has its font program.
@(private)
tt_has_glyf :: proc(f: ^TrueType_Font) -> bool {
    if f == nil { return false }
    return len(f.glyf) > 0 && len(f.loca) >= 4
}

// tt_cff_data returns the 'CFF ' table for an OpenType font with CFF outlines,
// or an empty slice. The bytes belong to the data passed to `tt_parse`.
@(private)
tt_cff_data :: proc(f: ^TrueType_Font) -> []byte {
    if f == nil { return nil }
    return f.cff
}

// ---------------------------------------------------------------------------
// Advances
// ---------------------------------------------------------------------------

// tt_glyph_advance is the horizontal advance in font units, 0 when the font
// has no usable `hmtx`.
@(private)
tt_glyph_advance :: proc(f: ^TrueType_Font, gid: u16) -> f64 {
    if f == nil { return 0 }
    return f64(tt_hmtx_advance(f, tt_metrics_gid(f, gid, 0)))
}

// tt_hmtx_advance reads `hmtx` directly. The table stores advances only for
// the first numberOfHMetrics glyphs; every glyph after that shares the last
// one, which is how a monospaced or a right-heavy font stays small.
// ISO 14496-22, 5.2.4.
@(private)
tt_hmtx_advance :: proc(f: ^TrueType_Font, gid: u16) -> u16 {
    n := f.num_h_metrics
    if n <= 0 { return 0 }
    i := int(gid)
    if i >= n { i = n - 1 }
    off := i * 4
    if off + 2 > len(f.hmtx) {
        // A truncated hmtx still answers for the glyphs it does hold, and the
        // last of those stands in for the rest.
        have := len(f.hmtx) / 4
        if have <= 0 { return 0 }
        off = (have - 1) * 4
    }
    return tt_u16(f.hmtx, off)
}

// tt_metrics_gid follows USE_MY_METRICS: a composite that sets it on one of
// its components takes that component's advance rather than its own. In a
// well-formed font the two agree and this changes nothing; in a font whose
// hmtx was rewritten by a subsetter it is the only remaining truth.
@(private)
tt_metrics_gid :: proc(f: ^TrueType_Font, gid: u16, depth: int) -> u16 {
    if depth >= MAX_TT_COMPONENT_DEPTH || !tt_has_glyf(f) { return gid }
    g, ok := tt_glyph_data(f, gid)
    if !ok || len(g) < 10 || tt_i16(g, 0) >= 0 { return gid }

    p := 10
    for _ in 0 ..< MAX_TT_COMPONENTS {
        if p + 4 > len(g) { break }
        flags := tt_u16(g, p)
        cgid := tt_u16(g, p + 2)
        p += 4
        p += 4 if flags & 0x0001 != 0 else 2
        switch {
        case flags & 0x0008 != 0: p += 2
        case flags & 0x0040 != 0: p += 4
        case flags & 0x0080 != 0: p += 8
        }
        if flags & 0x0200 != 0 {
            return tt_metrics_gid(f, cgid, depth + 1)
        }
        if flags & 0x0020 == 0 { break }
    }
    return gid
}

// ---------------------------------------------------------------------------
// Outlines
// ---------------------------------------------------------------------------

@(private)
Tt_Point :: struct {
    x, y: f64,
    on:   bool,
}

// Tt_Contour is one closed contour as a half-open range of Tt_Outline.pts.
// Ranges are kept rather than end indices because a composite concatenates the
// points of several glyphs and a malformed contour in the middle must not
// shift the ones after it.
@(private)
Tt_Contour :: struct {
    start, end: int,
}

// Tt_Outline accumulates a glyph's points before any of them is emitted. A
// composite's point-matching offsets are expressed in point indices, so the
// points have to exist as an array at least until the component that follows
// them is placed.
@(private)
Tt_Outline :: struct {
    pts:      [dynamic]Tt_Point,
    contours: [dynamic]Tt_Contour,
    // Scratch for one simple glyph's flag array, reused across components.
    flags:    [dynamic]u8,
    fuel:     int,
}

// tt_glyph_path appends glyph `gid`'s outline to `out`, in font units (divide
// by `tt_units_per_em` for text space).
//
// Returns .No_Glyph when the font has no outline for the id at all, and
// .Bad_TrueType when the glyph's data is malformed -- in which case whatever
// could be decoded has still been appended, because half a glyph is closer to
// right than a blank page. An empty glyph, which is what a space is, is not an
// error.
@(private)
tt_glyph_path :: proc(f: ^TrueType_Font, gid: u16, out: ^Path) -> Error {
    if f == nil || out == nil { return .Invalid_Argument }
    if !tt_has_glyf(f) { return .No_Glyph }
    if int(gid) >= f.num_glyphs { return .No_Glyph }

    ol := Tt_Outline{
        pts      = make([dynamic]Tt_Point, 0, 64),
        contours = make([dynamic]Tt_Contour, 0, 8),
        flags    = make([dynamic]u8, 0, 64),
        fuel     = MAX_TT_COMPONENTS,
    }
    defer {
        delete(ol.pts)
        delete(ol.contours)
        delete(ol.flags)
    }

    err := tt_build_glyph(f, gid, MATRIX_IDENTITY, 0, &ol)
    for c in ol.contours {
        // Fewer than two points enclose no area; emitting them would leave a
        // degenerate subpath for the rasteriser to step over.
        if c.start < 0 || c.end > len(ol.pts) || c.end - c.start < 2 { continue }
        tt_emit_contour(out, ol.pts[c.start:c.end])
    }
    return err
}

// tt_glyph_data returns the bytes of one glyph's `glyf` entry.
//
// ok is false when `loca` does not cover the id; an empty slice with ok means
// the glyph is legitimately blank. A `loca` whose entries do not increase is a
// subsetter bug seen often enough that a non-increasing pair is read as a
// blank glyph rather than as damage.
@(private)
tt_glyph_data :: proc(f: ^TrueType_Font, gid: u16) -> ([]byte, bool) {
    i := int(gid)
    start, end: int
    if f.long_loca {
        if (i + 2) * 4 > len(f.loca) { return nil, false }
        start = int(tt_u32(f.loca, i * 4))
        end = int(tt_u32(f.loca, i * 4 + 4))
    } else {
        if (i + 2) * 2 > len(f.loca) { return nil, false }
        // Short offsets are stored halved, so the table can reach 128K.
        start = int(tt_u16(f.loca, i * 2)) * 2
        end = int(tt_u16(f.loca, i * 2 + 2)) * 2
    }
    if end <= start || start >= len(f.glyf) { return nil, true }
    if end > len(f.glyf) { end = len(f.glyf) }
    return f.glyf[start:end], true
}

@(private)
tt_build_glyph :: proc(f: ^TrueType_Font, gid: u16, m: Matrix, depth: int, ol: ^Tt_Outline) -> Error {
    if depth > MAX_TT_COMPONENT_DEPTH { return .Recursion_Limit }
    g, ok := tt_glyph_data(f, gid)
    if !ok { return .No_Glyph }
    if len(g) == 0 { return .None }
    // The glyph header is numberOfContours and a bounding box: 10 bytes.
    if len(g) < 10 { return .Bad_TrueType }
    nc := int(tt_i16(g, 0))
    if nc >= 0 {
        return tt_simple_glyph(g, nc, m, ol)
    }
    return tt_composite_glyph(f, g, m, depth, ol)
}

// tt_simple_glyph decodes one glyph's contours into `ol`, transformed by `m`.
// ISO 14496-22, 5.3.3.
@(private)
tt_simple_glyph :: proc(g: []byte, n_contours: int, m: Matrix, ol: ^Tt_Outline) -> Error {
    if n_contours == 0 { return .None }
    ends_off := 10
    if ends_off + 2 * n_contours + 2 > len(g) { return .Bad_TrueType }

    // The last contour's end point index gives the point count.
    n_pts := int(tt_u16(g, ends_off + 2 * (n_contours - 1))) + 1
    if n_pts <= 0 || n_pts > MAX_TT_GLYPH_POINTS { return .Bad_TrueType }
    if len(ol.pts) + n_pts > MAX_TT_GLYPH_POINTS { return .Bad_TrueType }

    p := ends_off + 2 * n_contours
    instr := int(tt_u16(g, p))
    p += 2 + instr
    if p > len(g) { return .Bad_TrueType }

    // Flags, with the run-length encoding: a flag with REPEAT set is followed
    // by a count of extra points that share it.
    clear(&ol.flags)
    for len(ol.flags) < n_pts {
        if p >= len(g) { return .Bad_TrueType }
        fl := g[p]
        p += 1
        append(&ol.flags, fl)
        if fl & 0x08 != 0 {
            if p >= len(g) { return .Bad_TrueType }
            rep := int(g[p])
            p += 1
            for _ in 0 ..< rep {
                if len(ol.flags) >= n_pts { break }
                append(&ol.flags, fl)
            }
        }
    }

    base := len(ol.pts)
    // X then Y, each a delta from the previous point. A short vector is one
    // unsigned byte whose sign comes from the SAME_OR_POSITIVE bit; a long one
    // is a signed word, and that same bit set with no short flag means the
    // coordinate simply repeats.
    x := 0
    for k in 0 ..< n_pts {
        fl := ol.flags[k]
        if fl & 0x02 != 0 {
            if p >= len(g) { return .Bad_TrueType }
            d := int(g[p])
            p += 1
            x += d if fl & 0x10 != 0 else -d
        } else if fl & 0x10 == 0 {
            if p + 2 > len(g) { return .Bad_TrueType }
            x += int(tt_i16(g, p))
            p += 2
        }
        append(&ol.pts, Tt_Point{x = f64(x), on = fl & 0x01 != 0})
    }
    y := 0
    for k in 0 ..< n_pts {
        fl := ol.flags[k]
        if fl & 0x04 != 0 {
            if p >= len(g) { return .Bad_TrueType }
            d := int(g[p])
            p += 1
            y += d if fl & 0x20 != 0 else -d
        } else if fl & 0x20 == 0 {
            if p + 2 > len(g) { return .Bad_TrueType }
            y += int(tt_i16(g, p))
            p += 2
        }
        ol.pts[base + k].y = f64(y)
    }

    if m != MATRIX_IDENTITY {
        for k in base ..< len(ol.pts) {
            pt := transform_point(m, Point{ol.pts[k].x, ol.pts[k].y})
            ol.pts[k].x = pt.x
            ol.pts[k].y = pt.y
        }
    }

    prev := 0
    for c in 0 ..< n_contours {
        e := int(tt_u16(g, ends_off + 2 * c)) + 1
        // End indices must increase and stay inside the point array. One that
        // does not is skipped rather than taken as a reason to drop the glyph.
        if e <= prev || e > n_pts { continue }
        append(&ol.contours, Tt_Contour{base + prev, base + e})
        prev = e
    }
    return .None
}

// tt_composite_glyph places other glyphs into this one. ISO 14496-22, 5.3.4.
@(private)
tt_composite_glyph :: proc(f: ^TrueType_Font, g: []byte, m: Matrix, depth: int, ol: ^Tt_Outline) -> Error {
    // Point-matching offsets index the points of the composite being built, so
    // where its own points start has to be remembered.
    glyph_base := len(ol.pts)
    p := 10
    err := Error.None
    for {
        if ol.fuel <= 0 { return .Recursion_Limit }
        ol.fuel -= 1
        if p + 4 > len(g) { return .Bad_TrueType }
        flags := tt_u16(g, p)
        cgid := tt_u16(g, p + 2)
        p += 4

        xy := flags & 0x0002 != 0     // ARGS_ARE_XY_VALUES
        a1, a2: int
        if flags & 0x0001 != 0 {      // ARG_1_AND_2_ARE_WORDS
            if p + 4 > len(g) { return .Bad_TrueType }
            if xy {
                a1 = int(tt_i16(g, p))
                a2 = int(tt_i16(g, p + 2))
            } else {
                a1 = int(tt_u16(g, p))
                a2 = int(tt_u16(g, p + 2))
            }
            p += 4
        } else {
            if p + 2 > len(g) { return .Bad_TrueType }
            if xy {
                a1 = int(i8(g[p]))
                a2 = int(i8(g[p + 1]))
            } else {
                a1 = int(g[p])
                a2 = int(g[p + 1])
            }
            p += 2
        }

        cm := MATRIX_IDENTITY
        switch {
        case flags & 0x0008 != 0:     // WE_HAVE_A_SCALE
            if p + 2 > len(g) { return .Bad_TrueType }
            s := tt_f2dot14(g, p)
            p += 2
            cm.a, cm.d = s, s
        case flags & 0x0040 != 0:     // WE_HAVE_AN_X_AND_Y_SCALE
            if p + 4 > len(g) { return .Bad_TrueType }
            cm.a = tt_f2dot14(g, p)
            cm.d = tt_f2dot14(g, p + 2)
            p += 4
        case flags & 0x0080 != 0:     // WE_HAVE_A_TWO_BY_TWO
            if p + 8 > len(g) { return .Bad_TrueType }
            cm.a = tt_f2dot14(g, p)
            cm.b = tt_f2dot14(g, p + 2)
            cm.c = tt_f2dot14(g, p + 4)
            cm.d = tt_f2dot14(g, p + 6)
            p += 8
        }

        if xy {
            dx, dy := f64(a1), f64(a2)
            // Whether the offset is in the component's own space or the
            // composite's is a genuine disagreement between Apple and
            // Microsoft. Unscaled is both the Microsoft behaviour and the
            // default every font is drawn with, so it takes an explicit
            // SCALED_COMPONENT_OFFSET to get the other one.
            if flags & 0x0800 != 0 && flags & 0x1000 == 0 {
                v := transform_vector(cm, Point{dx, dy})
                dx, dy = v.x, v.y
            }
            if flags & 0x0004 != 0 {  // ROUND_XY_TO_GRID
                dx = math.round(dx)
                dy = math.round(dy)
            }
            cm.e, cm.f = dx, dy
        }

        base := len(ol.pts)
        cerr := tt_build_glyph(f, cgid, matrix_mul(cm, m), depth + 1, ol)
        if cerr != .None && err == .None { err = cerr }

        if !xy {
            // The alternative to an offset: arg1 names a point already placed
            // in this composite and arg2 the matching point of the component,
            // and the component moves so that the two coincide.
            i1 := glyph_base + a1
            i2 := base + a2
            if i1 >= glyph_base && i1 < base && i2 >= base && i2 < len(ol.pts) {
                dx := ol.pts[i1].x - ol.pts[i2].x
                dy := ol.pts[i1].y - ol.pts[i2].y
                if flags & 0x0004 != 0 {
                    dx = math.round(dx)
                    dy = math.round(dy)
                }
                for k in base ..< len(ol.pts) {
                    ol.pts[k].x += dx
                    ol.pts[k].y += dy
                }
            }
        }

        if flags & 0x0020 == 0 { break }   // MORE_COMPONENTS
    }
    return err
}

// tt_emit_contour turns one quadratic contour into cubics on `out`.
//
// A TrueType contour is a closed quadratic B-spline: on-curve points are on the
// outline, off-curve points are control points, and two consecutive off-curve
// points imply an on-curve point at their midpoint. A contour with no on-curve
// point at all -- an ellipse drawn as four control points -- starts at the
// midpoint of its last and first points.
@(private)
tt_emit_contour :: proc(out: ^Path, pts: []Tt_Point) {
    n := len(pts)
    if n < 2 { return }

    first := -1
    for i in 0 ..< n {
        if pts[i].on {
            first = i
            break
        }
    }

    sx, sy: f64
    start_i, count: int
    if first < 0 {
        sx = (pts[n - 1].x + pts[0].x) * 0.5
        sy = (pts[n - 1].y + pts[0].y) * 0.5
        start_i = 0
        count = n
    } else {
        sx, sy = pts[first].x, pts[first].y
        // Walk the other n-1 points; the closing segment back to the start is
        // the Close verb, or the trailing curve below.
        start_i = first + 1
        count = n - 1
    }

    path_move_to(out, sx, sy)
    cx, cy := sx, sy
    ctl_x, ctl_y: f64
    have_ctl := false

    for k in 0 ..< count {
        pt := pts[(start_i + k) % n]
        if pt.on {
            if have_ctl {
                tt_quad_to(out, cx, cy, ctl_x, ctl_y, pt.x, pt.y)
                have_ctl = false
            } else {
                path_line_to(out, pt.x, pt.y)
            }
            cx, cy = pt.x, pt.y
        } else {
            if have_ctl {
                mx := (ctl_x + pt.x) * 0.5
                my := (ctl_y + pt.y) * 0.5
                tt_quad_to(out, cx, cy, ctl_x, ctl_y, mx, my)
                cx, cy = mx, my
            }
            ctl_x, ctl_y = pt.x, pt.y
            have_ctl = true
        }
    }
    if have_ctl {
        tt_quad_to(out, cx, cy, ctl_x, ctl_y, sx, sy)
    }
    path_close(out)
}

// tt_quad_to appends the cubic equal to the quadratic from (cx,cy) through
// control (qx,qy) to (x,y). The two are exactly interconvertible: a cubic whose
// controls sit two thirds of the way from each end towards the quadratic's
// control traces the same curve, so nothing is approximated here.
@(private)
tt_quad_to :: proc(out: ^Path, cx, cy, qx, qy, x, y: f64) {
    K :: 2.0 / 3.0
    path_curve_to(out,
        cx + (qx - cx) * K, cy + (qy - cy) * K,
        x + (qx - x) * K, y + (qy - y) * K,
        x, y)
}

// ---------------------------------------------------------------------------
// cmap
// ---------------------------------------------------------------------------

// tt_select_cmaps picks the best subtable of each of the three kinds this
// reader offers. ISO 14496-22, 5.2.6.
//
// Choosing among the platform/encoding pairs is where readers get symbolic
// fonts wrong, so all three kinds are kept and none is merged into another:
// which one a PDF font should consult depends on its descriptor flags and its
// /Encoding, and that decision belongs in font.odin.
@(private)
tt_select_cmaps :: proc(f: ^TrueType_Font, cm: []byte) {
    if len(cm) < 4 { return }
    n := int(tt_u16(cm, 2))
    avail := (len(cm) - 4) / 8
    if avail < 0 { avail = 0 }
    if n > avail { n = avail }

    best := 0
    for i in 0 ..< n {
        rec := 4 + i * 8
        plat := tt_u16(cm, rec)
        enc := tt_u16(cm, rec + 2)
        off := tt_u32(cm, rec + 4)
        if u64(off) >= u64(len(cm)) { continue }
        // A subtable runs to the end of the cmap table rather than to its own
        // declared length: format 4 tables whose length excludes the trailing
        // glyphIdArray are a well-known producer bug, and reading past a
        // correct length costs nothing.
        sub := cm[off:]
        if len(sub) < 4 { continue }
        format := tt_u16(sub, 0)
        if !tt_cmap_supported(format) { continue }

        // (3,0) and (1,0) are not Unicode and are kept as themselves.
        if plat == 3 && enc == 0 {
            if f.cmap_symbol == nil { f.cmap_symbol = sub }
            continue
        }
        if plat == 1 && enc == 0 {
            if f.cmap_mac == nil { f.cmap_mac = sub }
            continue
        }

        score := 0
        switch {
        case plat == 3 && enc == 10: score = 5   // Windows, full repertoire
        case plat == 3 && enc == 1:  score = 4   // Windows, BMP
        case plat == 0 && enc >= 4:  score = 3   // Unicode, full repertoire
        case plat == 0:              score = 2   // Unicode, BMP
        }
        if score > best {
            best = score
            f.cmap_unicode = sub
        }
    }
}

@(private)
tt_cmap_supported :: proc "contextless" (format: u16) -> bool {
    // Format 2 is the high-byte scheme for legacy CJK encodings, format 8 and
    // 10 were never produced. Refusing them here rather than at lookup time
    // means a font with both an unreadable (3,1) and a readable (1,0) still
    // gets the (1,0).
    return format == 0 || format == 4 || format == 6 || format == 12
}

// tt_cmap_lookup maps one character code through one subtable. Zero means the
// subtable has no glyph for the code -- glyph 0 is .notdef, which is the same
// answer.
@(private)
tt_cmap_lookup :: proc(sub: []byte, c: u32) -> u16 {
    if len(sub) < 4 { return 0 }
    switch tt_u16(sub, 0) {
    case 0:
        // Byte encoding: 256 one-byte glyph ids at offset 6.
        if c > 255 { return 0 }
        off := 6 + int(c)
        return u16(tt_u8(sub, off)) if off < len(sub) else 0

    case 4:
        if c > 0xFFFF { return 0 }
        seg := int(tt_u16(sub, 6)) / 2
        if seg == 0 { return 0 }
        cc := u16(c)
        // The segments are sorted by endCode, so the one that can hold the
        // code is the first whose endCode is not below it. The format also
        // ships searchRange/entrySelector for exactly this search; they are
        // ignored because a wrong pair is a common damage and recomputing the
        // bounds costs nothing.
        lo, hi := 0, seg
        for lo < hi {
            mid := lo + (hi - lo) / 2
            if tt_u16(sub, 14 + 2 * mid) < cc {
                lo = mid + 1
            } else {
                hi = mid
            }
        }
        if lo >= seg { return 0 }
        start_off := 16 + 2 * seg
        delta_off := 16 + 4 * seg
        range_off := 16 + 6 * seg
        start := tt_u16(sub, start_off + 2 * lo)
        if cc < start { return 0 }
        delta := u32(u16(tt_i16(sub, delta_off + 2 * lo)))
        ro := int(tt_u16(sub, range_off + 2 * lo))
        if ro == 0 {
            // idDelta is added modulo 65536, which is why it is signed and why
            // the sum has to wrap rather than saturate.
            return u16((u32(cc) + delta) & 0xFFFF)
        }
        // idRangeOffset is a byte offset from its own slot, which is what lets
        // several segments share one glyphIdArray.
        addr := range_off + 2 * lo + ro + 2 * int(cc - start)
        if addr < 0 || addr + 2 > len(sub) { return 0 }
        g := tt_u16(sub, addr)
        if g == 0 { return 0 }
        return u16((u32(g) + delta) & 0xFFFF)

    case 6:
        // A single trimmed range.
        first := u32(tt_u16(sub, 6))
        count := u32(tt_u16(sub, 8))
        if c < first || c - first >= count { return 0 }
        off := 10 + 2 * int(c - first)
        if off + 2 > len(sub) { return 0 }
        return tt_u16(sub, off)

    case 12:
        // Sorted groups covering the whole code space.
        n := int(min(tt_u32(sub, 12), u32(1 << 24)))
        have := (len(sub) - 16) / 12
        if have < 0 { have = 0 }
        if n > have { n = have }
        lo, hi := 0, n
        for lo < hi {
            mid := lo + (hi - lo) / 2
            rec := 16 + mid * 12
            if c < tt_u32(sub, rec) {
                hi = mid
            } else if c > tt_u32(sub, rec + 4) {
                lo = mid + 1
            } else {
                g := u64(tt_u32(sub, rec + 8)) + u64(c - tt_u32(sub, rec))
                return u16(g) if g <= 0xFFFF else 0
            }
        }
        return 0
    }
    return 0
}

// tt_gid_for_unicode maps a Unicode code point through the font's Unicode
// cmap. ok is false when the font has no such table or no glyph for the
// character.
@(private)
tt_gid_for_unicode :: proc(f: ^TrueType_Font, r: rune) -> (u16, bool) {
    if f == nil || r < 0 || r > 0x10FFFF { return 0, false }
    g := tt_cmap_lookup(f.cmap_unicode, u32(r))
    return g, g != 0
}

// tt_gid_for_mac_code maps a byte through the (1,0) Mac Roman cmap, which is
// what a non-symbolic TrueType font's built-in encoding amounts to.
@(private)
tt_gid_for_mac_code :: proc(f: ^TrueType_Font, code: u8) -> (u16, bool) {
    if f == nil { return 0, false }
    g := tt_cmap_lookup(f.cmap_mac, u32(code))
    return g, g != 0
}

// tt_gid_for_symbol maps a byte through the (3,0) symbol cmap.
//
// A symbol font's cmap is keyed in the private-use area: the convention is
// 0xF000 plus the byte, and it is only a convention -- fonts exist that map the
// bare byte, and fonts exist that do both. Both are tried, which is what every
// viewer does and the only way Wingdings and Symbol come out right.
@(private)
tt_gid_for_symbol :: proc(f: ^TrueType_Font, code: u8) -> (u16, bool) {
    if f == nil { return 0, false }
    if g := tt_cmap_lookup(f.cmap_symbol, u32(code)); g != 0 {
        return g, true
    }
    if g := tt_cmap_lookup(f.cmap_symbol, 0xF000 | u32(code)); g != 0 {
        return g, true
    }
    return 0, false
}

// ---------------------------------------------------------------------------
// post
// ---------------------------------------------------------------------------

// tt_parse_post reads glyph names. ISO 14496-22, 5.2.9.
//
// Format 2.0 is the only one that carries names of its own; 1.0 says the font
// is exactly the 258 standard Macintosh glyphs in order, and 3.0 -- what a
// subsetter emits -- says there are no names at all, which is not an error.
@(private)
tt_parse_post :: proc(f: ^TrueType_Font, post: []byte, allocator: mem.Allocator) {
    if len(post) < 32 || f.num_glyphs <= 0 { return }
    switch tt_u32(post, 0) {
    case 0x00010000:
        n := min(f.num_glyphs, len(MAC_GLYPH_NAMES))
        names := make([]string, n, allocator)
        for i in 0 ..< n {
            names[i] = MAC_GLYPH_NAMES[i]
        }
        f.names = names

    case 0x00020000:
        n := int(tt_u16(post, 32))
        if n > f.num_glyphs { n = f.num_glyphs }
        // A post whose index array is cut short still names the glyphs it
        // reaches.
        if 34 + 2 * n > len(post) { n = (len(post) - 34) / 2 }
        if n <= 0 { return }

        // The names themselves are Pascal strings in one run after the index
        // array, and an index of 258 or more selects the (index-258)th of
        // them. A well-formed font has at most one string per glyph, so
        // collecting more than that would only be following damage.
        strs := make([dynamic]string, 0, min(n, 64), context.allocator)
        defer delete(strs)
        q := 34 + 2 * n
        for len(strs) < n && q < len(post) {
            l := int(post[q])
            q += 1
            if q + l > len(post) { break }
            append(&strs, string(post[q:][:l]))
            q += l
        }

        names := make([]string, n, allocator)
        for i in 0 ..< n {
            idx := int(tt_u16(post, 34 + 2 * i))
            if idx < len(MAC_GLYPH_NAMES) {
                names[i] = MAC_GLYPH_NAMES[idx]
            } else if idx - len(MAC_GLYPH_NAMES) < len(strs) {
                names[i] = strs[idx - len(MAC_GLYPH_NAMES)]
            }
        }
        f.names = names
    }
}

// tt_gid_for_name looks a glyph up by the name its `post` table gives it. ok is
// false when the font has no names or none of them match.
//
// The scan is linear. A simple font asks at most 256 times and a CID font never
// asks at all, so the index a binary search would need would cost more memory
// than the search saves.
@(private)
tt_gid_for_name :: proc(f: ^TrueType_Font, name: string) -> (u16, bool) {
    if f == nil || len(name) == 0 { return 0, false }
    for i in 0 ..< len(f.names) {
        if f.names[i] == name {
            return u16(i), true
        }
    }
    return 0, false
}

// The standard Macintosh glyph ordering: the 258 names a `post` table refers to
// by index alone. ISO 14496-22, 5.2.9, table 32.
@(private, rodata)
MAC_GLYPH_NAMES := [258]string{
    ".notdef", ".null", "nonmarkingreturn", "space", "exclam", "quotedbl",
    "numbersign", "dollar", "percent", "ampersand", "quotesingle", "parenleft",
    "parenright", "asterisk", "plus", "comma", "hyphen", "period", "slash",
    "zero", "one", "two", "three", "four", "five", "six", "seven", "eight",
    "nine", "colon", "semicolon", "less", "equal", "greater", "question", "at",
    "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O",
    "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "bracketleft",
    "backslash", "bracketright", "asciicircum", "underscore", "grave",
    "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o",
    "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "braceleft", "bar",
    "braceright", "asciitilde", "Adieresis", "Aring", "Ccedilla", "Eacute",
    "Ntilde", "Odieresis", "Udieresis", "aacute", "agrave", "acircumflex",
    "adieresis", "atilde", "aring", "ccedilla", "eacute", "egrave",
    "ecircumflex", "edieresis", "iacute", "igrave", "icircumflex", "idieresis",
    "ntilde", "oacute", "ograve", "ocircumflex", "odieresis", "otilde",
    "uacute", "ugrave", "ucircumflex", "udieresis", "dagger", "degree", "cent",
    "sterling", "section", "bullet", "paragraph", "germandbls", "registered",
    "copyright", "trademark", "acute", "dieresis", "notequal", "AE", "Oslash",
    "infinity", "plusminus", "lessequal", "greaterequal", "yen", "mu",
    "partialdiff", "summation", "product", "pi", "integral", "ordfeminine",
    "ordmasculine", "Omega", "ae", "oslash", "questiondown", "exclamdown",
    "logicalnot", "radical", "florin", "approxequal", "Delta", "guillemotleft",
    "guillemotright", "ellipsis", "nonbreakingspace", "Agrave", "Atilde",
    "Otilde", "OE", "oe", "endash", "emdash", "quotedblleft", "quotedblright",
    "quoteleft", "quoteright", "divide", "lozenge", "ydieresis", "Ydieresis",
    "fraction", "currency", "guilsinglleft", "guilsinglright", "fi", "fl",
    "daggerdbl", "periodcentered", "quotesinglbase", "quotedblbase",
    "perthousand", "Acircumflex", "Ecircumflex", "Aacute", "Edieresis",
    "Egrave", "Iacute", "Icircumflex", "Idieresis", "Igrave", "Oacute",
    "Ocircumflex", "apple", "Ograve", "Uacute", "Ucircumflex", "Ugrave",
    "dotlessi", "circumflex", "tilde", "macron", "breve", "dotaccent", "ring",
    "cedilla", "hungarumlaut", "ogonek", "caron", "Lslash", "lslash", "Scaron",
    "scaron", "Zcaron", "zcaron", "brokenbar", "Eth", "eth", "Yacute", "yacute",
    "Thorn", "thorn", "minus", "multiply", "onesuperior", "twosuperior",
    "threesuperior", "onehalf", "onequarter", "threequarters", "franc",
    "Gbreve", "gbreve", "Idotaccent", "Scedilla", "scedilla", "Cacute",
    "cacute", "Ccaron", "ccaron", "dcroat",
}