pdf-odin-llm/encoding.odin

package pdf

import "core:bytes"
import "core:strings"
import "core:unicode/utf8"

// Text strings, dates, and the name/number trees that hold a document's
// named destinations, embedded files and page labels.
//
// Everything here works on bytes that came out of a file, so everything here
// is written to survive nonsense: a truncated date reads as far as it can, an
// unpaired UTF-16 surrogate becomes U+FFFD rather than invalid UTF-8, and a
// tree whose /Kids point back at their parent terminates.

// ---------------------------------------------------------------------------
// Text strings (ISO 32000-2, 7.9.2.2)
// ---------------------------------------------------------------------------

// PDFDocEncoding as a byte -> Unicode table (ISO 32000-2, Annex D.2).
//
// It is Latin-1 apart from three regions: 0x18-0x1F, which hold the accents
// Latin-1 puts in the C1 area; 0x80-0x9F, which hold the typographic
// characters that Latin-1 has no room for; and 0xA0, which is the euro sign
// rather than a no-break space.
//
// A zero entry means "not defined by PDFDocEncoding" -- 0x00, 0x7F, 0x9F and
// 0xAD. Those decode to the byte's own value, which is what every viewer does
// and what keeps round-tripping a Latin-1 string through this table lossless.
@(private, rodata)
PDF_DOC_ENCODING := [256]rune{
    0x18 = 0x02D8,  // breve
    0x19 = 0x02C7,  // caron
    0x1A = 0x02C6,  // modifier letter circumflex accent
    0x1B = 0x02D9,  // dot above
    0x1C = 0x02DD,  // double acute accent
    0x1D = 0x02DB,  // ogonek
    0x1E = 0x02DA,  // ring above
    0x1F = 0x02DC,  // small tilde

    0x80 = 0x2022,  // bullet
    0x81 = 0x2020,  // dagger
    0x82 = 0x2021,  // double dagger
    0x83 = 0x2026,  // horizontal ellipsis
    0x84 = 0x2014,  // em dash
    0x85 = 0x2013,  // en dash
    0x86 = 0x0192,  // latin small letter f with hook
    0x87 = 0x2044,  // fraction slash
    0x88 = 0x2039,  // single left-pointing angle quotation mark
    0x89 = 0x203A,  // single right-pointing angle quotation mark
    0x8A = 0x2212,  // minus sign
    0x8B = 0x2030,  // per mille sign
    0x8C = 0x201E,  // double low-9 quotation mark
    0x8D = 0x201C,  // left double quotation mark
    0x8E = 0x201D,  // right double quotation mark
    0x8F = 0x2018,  // left single quotation mark
    0x90 = 0x2019,  // right single quotation mark
    0x91 = 0x201A,  // single low-9 quotation mark
    0x92 = 0x2122,  // trade mark sign
    0x93 = 0xFB01,  // latin small ligature fi
    0x94 = 0xFB02,  // latin small ligature fl
    0x95 = 0x0141,  // latin capital letter l with stroke
    0x96 = 0x0152,  // latin capital ligature oe
    0x97 = 0x0160,  // latin capital letter s with caron
    0x98 = 0x0178,  // latin capital letter y with diaeresis
    0x99 = 0x017D,  // latin capital letter z with caron
    0x9A = 0x0131,  // latin small letter dotless i
    0x9B = 0x0142,  // latin small letter l with stroke
    0x9C = 0x0153,  // latin small ligature oe
    0x9D = 0x0161,  // latin small letter s with caron
    0x9E = 0x017E,  // latin small letter z with caron

    0xA0 = 0x20AC,  // euro sign
}

// decode_text_string converts a PDF text string to UTF-8.
//
// A leading U+FEFF byte order mark (FE FF) means the rest is UTF-16BE; an
// EF BB BF mark means it is already UTF-8; anything else is PDFDocEncoding
// (ISO 32000-2, 7.9.2.2). An FF FE mark is not in the format, but enough
// producers emit little-endian UTF-16 with one that decoding it costs nothing
// and rescues those files -- no PDFDocEncoding text begins with "y-diaeresis,
// thorn".
//
// The result is always freshly allocated with `allocator` and owned by the
// caller. It is always valid UTF-8: a lone surrogate, a truncated UTF-16 code
// unit or a malformed UTF-8 sequence each become U+FFFD.
decode_text_string :: proc(raw: []byte, allocator := context.allocator) -> string {
    // +1 so that the empty string is still a real allocation the caller can
    // delete unconditionally.
    b := strings.builder_make(0, len(raw) + 1, allocator)
    switch {
    case len(raw) >= 2 && raw[0] == 0xFE && raw[1] == 0xFF:
        text_write_utf16(&b, raw[2:], true)
    case len(raw) >= 2 && raw[0] == 0xFF && raw[1] == 0xFE:
        text_write_utf16(&b, raw[2:], false)
    case len(raw) >= 3 && raw[0] == 0xEF && raw[1] == 0xBB && raw[2] == 0xBF:
        text_write_utf8(&b, raw[3:])
    case:
        text_write_pdfdoc(&b, raw)
    }
    return strings.to_string(b)
}

// decode_text_object is decode_text_string for a string object, and the form
// most callers want: /Title, /Author, /Subject and the rest are all strings
// that may be indirect.
decode_text_object :: proc(doc: ^Document, o: Object, allocator := context.allocator) -> string {
    raw, _ := to_bytes(resolve(doc, o))
    return decode_text_string(raw, allocator)
}

@(private)
text_write_pdfdoc :: proc(b: ^strings.Builder, raw: []byte) {
    for c in raw {
        r := PDF_DOC_ENCODING[c]
        if r == 0 {
            r = rune(c)
        }
        strings.write_rune(b, r)
    }
}

@(private)
text_write_utf8 :: proc(b: ^strings.Builder, raw: []byte) {
    // Re-encoding rather than copying: the mark only claims the bytes are
    // UTF-8, and a claim out of a file is not a guarantee.
    for i := 0; i < len(raw); {
        r, size := utf8.decode_rune(raw[i:])
        if size <= 0 {
            strings.write_rune(b, utf8.RUNE_ERROR)
            break
        }
        strings.write_rune(b, r)
        i += size
    }
}

@(private)
text_write_utf16 :: proc(b: ^strings.Builder, raw: []byte, big_endian: bool) {
    unit :: proc(raw: []byte, i: int, big_endian: bool) -> u16 {
        hi, lo := raw[i], raw[i + 1]
        if !big_endian {
            hi, lo = lo, hi
        }
        return u16(hi) << 8 | u16(lo)
    }

    i := 0
    for i + 1 < len(raw) {
        u := unit(raw, i, big_endian)
        i += 2
        switch {
        case u >= 0xD800 && u <= 0xDBFF:
            // High surrogate: only a following low surrogate completes it.
            if i + 1 < len(raw) {
                v := unit(raw, i, big_endian)
                if v >= 0xDC00 && v <= 0xDFFF {
                    i += 2
                    strings.write_rune(b, rune(0x10000 + (u32(u - 0xD800) << 10 | u32(v - 0xDC00))))
                    continue
                }
            }
            strings.write_rune(b, utf8.RUNE_ERROR)
        case u >= 0xDC00 && u <= 0xDFFF:
            // Low surrogate with nothing in front of it.
            strings.write_rune(b, utf8.RUNE_ERROR)
        case:
            strings.write_rune(b, rune(u))
        }
    }
    // A trailing half code unit: the string was truncated somewhere.
    if i < len(raw) {
        strings.write_rune(b, utf8.RUNE_ERROR)
    }
}

// ---------------------------------------------------------------------------
// Dates (ISO 32000-2, 7.9.4)
// ---------------------------------------------------------------------------

// Date is a decoded PDF date. Absent fields take their lowest legal value:
// month and day 1, everything else 0.
//
// `tz_hour` and `tz_minute` both carry the sign of the offset, so the offset
// from UT in minutes is always `tz_hour * 60 + tz_minute` and never needs a
// separate sign flag. They are meaningless unless `has_tz` is set -- a date
// with no offset is local time of an unknown locale, which is not the same
// thing as UT.
Date :: struct {
    year, month, day:     int,
    hour, minute, second: int,
    tz_hour, tz_minute:   int,
    has_tz:               bool,
}

// parse_date decodes "D:YYYYMMDDHHmmSSOHH'mm'".
//
// Every field after the year is optional and truncated dates are the norm.
// So is malformation: the "D:" prefix is missing in plenty of files, the
// apostrophes around the offset minutes are variously absent, singular or
// doubled, and a colon or a space turns up where an apostrophe belongs. All of
// that is accepted. Out-of-range fields are clamped rather than rejected,
// because a viewer showing 31 December for a date that says month 13 is more
// useful than one showing nothing.
//
// ok is false only when no four-digit year could be found at all.
parse_date :: proc(raw: []byte) -> (date: Date, ok: bool) {
    // A date is a few dozen bytes. Anything longer is not a date with junk
    // after it, it is a different kind of object, and scanning all of it for
    // something year-shaped would only invent a date out of arbitrary digits.
    scan := raw
    if len(scan) > 64 {
        scan = scan[:64]
    }

    p := 0
    for p < len(scan) && date_is_space(scan[p]) {
        p += 1
    }
    if p + 1 < len(scan) && (scan[p] == 'D' || scan[p] == 'd') && scan[p + 1] == ':' {
        p += 2
    }
    // Producers put spaces, a second colon, or nothing at all between the
    // prefix and the year; skip forward to the first run of four digits.
    start := -1
    for j := p; j < len(scan); j += 1 {
        if date_digit_run(scan, j) >= 4 {
            start = j
            break
        }
    }
    if start < 0 {
        return {}, false
    }
    p = start

    y, _ := date_take(scan, &p, 4)
    date.year = clamp(y, 0, 9999)
    date.month, date.day = 1, 1

    if m, m_ok := date_take(scan, &p, 2); m_ok {
        date.month = clamp(m, 1, 12)
        if d, d_ok := date_take(scan, &p, 2); d_ok {
            date.day = clamp(d, 1, date_days_in_month(date.year, date.month))
            if h, h_ok := date_take(scan, &p, 2); h_ok {
                // 24 as "midnight ending the day" turns up; clamp it back
                // rather than rolling the date over.
                date.hour = clamp(h, 0, 23)
                if mi, mi_ok := date_take(scan, &p, 2); mi_ok {
                    date.minute = clamp(mi, 0, 59)
                    if s, s_ok := date_take(scan, &p, 2); s_ok {
                        // A leap second (60) is clamped: nothing downstream
                        // has a use for it.
                        date.second = clamp(s, 0, 59)
                    }
                }
            }
        }
    }

    date_parse_offset(scan, p, &date)
    return date, true
}

@(private)
date_parse_offset :: proc(raw: []byte, from: int, date: ^Date) {
    p := from
    for p < len(raw) && date_is_space(raw[p]) {
        p += 1
    }
    if p >= len(raw) {
        return
    }

    sign := 0
    switch raw[p] {
    case 'Z', 'z':
        // Z is UT. Some producers write "Z00'00'"; a non-zero offset after a
        // Z contradicts itself, so the Z wins and the digits are ignored.
        date.has_tz = true
        return
    case '+':
        sign = 1
    case '-':
        sign = -1
    case:
        return
    }
    p += 1

    h, h_ok := date_take(raw, &p, 2)
    if !h_ok {
        // A sign with no hours is not an offset.
        return
    }
    date.has_tz = true
    date.tz_hour = sign * clamp(h, 0, 23)

    for p < len(raw) && (raw[p] == '\'' || raw[p] == ':' || raw[p] == ' ') {
        p += 1
    }
    if m, m_ok := date_take(raw, &p, 2); m_ok {
        date.tz_minute = sign * clamp(m, 0, 59)
    }
}

// date_offset_minutes is the offset from UT in minutes, 0 when the date
// carries none.
date_offset_minutes :: proc(d: Date) -> int {
    if !d.has_tz {
        return 0
    }
    return d.tz_hour * 60 + d.tz_minute
}

@(private)
date_is_space :: proc "contextless" (c: byte) -> bool {
    return c == ' ' || c == '\t' || c == '\r' || c == '\n' || c == 0
}

@(private)
date_is_digit :: proc "contextless" (c: byte) -> bool {
    return c >= '0' && c <= '9'
}

// date_digit_run counts consecutive digits at `i`, stopping at 4: nothing
// here needs to tell a four-digit run from a fourteen-digit one.
@(private)
date_digit_run :: proc "contextless" (raw: []byte, i: int) -> int {
    n := 0
    for j := i; j < len(raw) && n < 4; j += 1 {
        if !date_is_digit(raw[j]) {
            break
        }
        n += 1
    }
    return n
}

// date_take reads exactly `n` digits, advancing `p` only if it finds them.
// A field with one digit where two belong is treated as absent: guessing
// whether "D:2005032" means the 2nd or the 20th is worse than stopping.
@(private)
date_take :: proc(raw: []byte, p: ^int, n: int) -> (value: int, ok: bool) {
    if p^ < 0 || p^ + n > len(raw) {
        return 0, false
    }
    v := 0
    for i in 0 ..< n {
        c := raw[p^ + i]
        if !date_is_digit(c) {
            return 0, false
        }
        v = v * 10 + int(c - '0')
    }
    p^ += n
    return v, true
}

@(private)
date_days_in_month :: proc "contextless" (year, month: int) -> int {
    switch month {
    case 4, 6, 9, 11:
        return 30
    case 2:
        leap := (year % 4 == 0 && year % 100 != 0) || year % 400 == 0
        return leap ? 29 : 28
    }
    return 31
}

// ---------------------------------------------------------------------------
// Name trees (ISO 32000-2, 7.9.6) and number trees (7.9.7)
// ---------------------------------------------------------------------------

// Work budget for one traversal, counted in nodes visited plus entries
// linearly scanned. A well-formed tree of any realistic size stays far below
// it; a tree built to make a reader spin does not get to.
@(private)
MAX_TREE_STEPS :: 1 << 16

// Entries a single collect will return. A file claiming more than this has a
// tree that is not going to be useful to anyone.
@(private)
MAX_TREE_ENTRIES :: 1 << 20

@(private)
Tree_Kind :: enum u8 {
    Name,
    Number,
}

// name_tree_lookup finds `key` in a name tree, or null if it is not there.
//
// `root` is the tree's root node -- the value of /Dests, /EmbeddedFiles and
// the rest of the catalog's /Names dictionary. Keys are compared by byte
// value, which is the order the format requires the /Names arrays to be in.
name_tree_lookup :: proc(doc: ^Document, root: ^Dict, key: []byte) -> Object {
    path: [MAX_DEPTH]^Dict
    steps := MAX_TREE_STEPS
    value, _ := tree_find(doc, root, .Name, key, 0, 0, &path, &steps)
    return value
}

// number_tree_lookup finds `key` in a number tree (/PageLabels, /ParentTree),
// or null.
number_tree_lookup :: proc(doc: ^Document, root: ^Dict, key: i64) -> Object {
    path: [MAX_DEPTH]^Dict
    steps := MAX_TREE_STEPS
    value, _ := tree_find(doc, root, .Number, nil, key, 0, &path, &steps)
    return value
}

// tree_find descends one node.
//
// `path` holds the ancestors of the current node so that a /Kids entry
// pointing back up the tree is detected; with the depth cap that is enough,
// because the walk only ever moves downwards. `steps` bounds the total work,
// which matters because a node with no /Limits has to be searched
// speculatively.
@(private)
tree_find :: proc(
    doc: ^Document, node: ^Dict, kind: Tree_Kind, skey: []byte, ikey: i64,
    depth: int, path: ^[MAX_DEPTH]^Dict, steps: ^int,
) -> (value: Object, found: bool) {
    if node == nil || depth >= MAX_DEPTH || steps^ <= 0 {
        return nil, false
    }
    for i in 0 ..< depth {
        if path[i] == node {
            return nil, false
        }
    }
    path[depth] = node
    steps^ -= 1

    leaf := dict_array(doc, node, kind == .Name ? "Names" : "Nums")
    if leaf != nil {
        if v, hit := tree_search_leaf(doc, leaf, kind, skey, ikey, steps); hit {
            return v, true
        }
    }

    kids := dict_array(doc, node, "Kids")
    for i in 0 ..< array_len(kids) {
        if steps^ <= 0 {
            break
        }
        kid, is_dict := to_dict(array_get(doc, kids, i))
        if !is_dict {
            continue
        }
        if !tree_limits_contain(doc, kid, kind, skey, ikey) {
            continue
        }
        if v, hit := tree_find(doc, kid, kind, skey, ikey, depth + 1, path, steps); hit {
            return v, true
        }
    }
    return nil, false
}

// tree_limits_contain tests a kid's /Limits. A node with no usable /Limits is
// searched rather than skipped: the entry is required, but files that omit it
// are readable and the alternative is losing every key below that node.
@(private)
tree_limits_contain :: proc(doc: ^Document, node: ^Dict, kind: Tree_Kind, skey: []byte, ikey: i64) -> bool {
    limits := dict_array(doc, node, "Limits")
    if array_len(limits) < 2 {
        return true
    }
    if kind == .Name {
        if lo, lo_ok := to_bytes(array_get(doc, limits, 0)); lo_ok && bytes.compare(skey, lo) < 0 {
            return false
        }
        if hi, hi_ok := to_bytes(array_get(doc, limits, 1)); hi_ok && bytes.compare(skey, hi) > 0 {
            return false
        }
        return true
    }
    if lo, lo_ok := to_int(array_get(doc, limits, 0)); lo_ok && ikey < lo {
        return false
    }
    if hi, hi_ok := to_int(array_get(doc, limits, 1)); hi_ok && ikey > hi {
        return false
    }
    return true
}

// tree_search_leaf binary-searches a leaf's key/value pairs.
//
// The format requires the pairs to be sorted, and a binary search over a few
// thousand named destinations is the whole point of the structure. But an
// unsorted (or ragged, or partly non-string) array does occur, and a miss
// there would silently lose a destination that is plainly present, so a miss
// falls back to a linear scan paid for out of the step budget.
@(private)
tree_search_leaf :: proc(
    doc: ^Document, leaf: ^Array, kind: Tree_Kind, skey: []byte, ikey: i64, steps: ^int,
) -> (value: Object, found: bool) {
    n := array_len(leaf) / 2
    lo, hi := 0, n
    for lo < hi {
        if steps^ <= 0 {
            return nil, false
        }
        steps^ -= 1
        mid := lo + (hi - lo) / 2
        cmp, ok := tree_compare(kind, array_get(doc, leaf, mid * 2), skey, ikey)
        if !ok {
            break
        }
        switch {
        case cmp == 0:
            return array_get(doc, leaf, mid * 2 + 1), true
        case cmp < 0:
            lo = mid + 1
        case:
            hi = mid
        }
    }

    for i in 0 ..< n {
        if steps^ <= 0 {
            return nil, false
        }
        steps^ -= 1
        if cmp, ok := tree_compare(kind, array_get(doc, leaf, i * 2), skey, ikey); ok && cmp == 0 {
            return array_get(doc, leaf, i * 2 + 1), true
        }
    }
    return nil, false
}

// tree_compare orders a key found in the file against the key being looked
// for. ok is false when the entry is not of the tree's key type, which the
// caller reads as "this array cannot be binary-searched".
@(private)
tree_compare :: proc(kind: Tree_Kind, entry: Object, skey: []byte, ikey: i64) -> (cmp: int, ok: bool) {
    if kind == .Name {
        b, is_str := to_bytes(entry)
        if !is_str {
            return 0, false
        }
        return bytes.compare(b, skey), true
    }
    v, is_int := to_int(entry)
    if !is_int {
        return 0, false
    }
    switch {
    case v < ikey: return -1, true
    case v > ikey: return +1, true
    }
    return 0, true
}

@(private)
Tree_Collector :: struct {
    // All nil on the counting pass. A name tree fills `keys`, a number tree
    // fills `nums`; only one of the two is ever non-nil.
    keys:   [][]byte,
    nums:   []i64,
    values: []Object,
    n:      int,
    steps:  int,
}

// name_tree_collect returns every key and value in a name tree, in tree order.
//
// Both slices are allocated with `allocator` and are the caller's to free.
// The keys are *not* copies: each one points at the string bytes inside the
// Document and is only valid while that Document is open. Copy them if they
// have to outlive it.
name_tree_collect :: proc(
    doc: ^Document, root: ^Dict, allocator := context.allocator,
) -> (keys: [][]byte, values: []Object) {
    path: [MAX_DEPTH]^Dict

    count := Tree_Collector{steps = MAX_TREE_STEPS}
    tree_walk(doc, root, .Name, &count, 0, &path)
    n := min(count.n, MAX_TREE_ENTRIES)
    if n == 0 {
        return nil, nil
    }

    keys = make([][]byte, n, allocator)
    values = make([]Object, n, allocator)
    fill := Tree_Collector{keys = keys, values = values, steps = MAX_TREE_STEPS}
    tree_walk(doc, root, .Name, &fill, 0, &path)
    return keys, values
}

// number_tree_collect is name_tree_collect for a number tree. Same ownership
// rules; the keys are values, not pointers, so they outlive the Document.
number_tree_collect :: proc(
    doc: ^Document, root: ^Dict, allocator := context.allocator,
) -> (keys: []i64, values: []Object) {
    path: [MAX_DEPTH]^Dict

    count := Tree_Collector{steps = MAX_TREE_STEPS}
    tree_walk(doc, root, .Number, &count, 0, &path)
    n := min(count.n, MAX_TREE_ENTRIES)
    if n == 0 {
        return nil, nil
    }

    // The walker fills a [][]byte; a number tree's keys are gathered here
    // instead, out of the same values array, so only one walker exists.
    nkeys := make([]i64, n, allocator)
    values = make([]Object, n, allocator)
    fill := Tree_Collector{nums = nkeys, values = values, steps = MAX_TREE_STEPS}
    tree_walk(doc, root, .Number, &fill, 0, &path)
    return nkeys, values
}

@(private)
tree_walk :: proc(
    doc: ^Document, node: ^Dict, kind: Tree_Kind, c: ^Tree_Collector, depth: int, path: ^[MAX_DEPTH]^Dict,
) {
    if node == nil || depth >= MAX_DEPTH || c.steps <= 0 {
        return
    }
    for i in 0 ..< depth {
        if path[i] == node {
            return
        }
    }
    path[depth] = node
    c.steps -= 1

    leaf := dict_array(doc, node, kind == .Name ? "Names" : "Nums")
    for i in 0 ..< array_len(leaf) / 2 {
        if c.steps <= 0 || c.n >= MAX_TREE_ENTRIES {
            return
        }
        c.steps -= 1
        entry := array_get(doc, leaf, i * 2)
        if kind == .Name {
            kb, is_str := to_bytes(entry)
            if !is_str {
                continue
            }
            if c.keys != nil && c.n < len(c.keys) {
                c.keys[c.n] = kb
            }
        } else {
            kn, is_int := to_int(entry)
            if !is_int {
                continue
            }
            if c.nums != nil && c.n < len(c.nums) {
                c.nums[c.n] = kn
            }
        }
        if c.values != nil && c.n < len(c.values) {
            c.values[c.n] = array_get(doc, leaf, i * 2 + 1)
        }
        c.n += 1
    }

    kids := dict_array(doc, node, "Kids")
    for i in 0 ..< array_len(kids) {
        if c.steps <= 0 {
            return
        }
        kid, is_dict := to_dict(array_get(doc, kids, i))
        if !is_dict {
            continue
        }
        tree_walk(doc, kid, kind, c, depth + 1, path)
    }
}