// SPDX-License-Identifier: MIT
// In-place HTML character-reference decoder in two Wasm pages (Zig port).
// Entity mappings: WHATWG HTML named character references, from Python
// html.entities.html5. The table lives in a passive data segment, outside
// linear memory; each lookup copies one first-letter bucket into scratch.
//
// render() moves the input to the end of the buffer and decodes forward from
// the start, so output never overtakes unread input unless it has grown by
// more than the free space in front of the input. In that case render returns
// the failure bit rather than overwrite input.

const PAGES = 2;
const STACK = 256;
const SCRATCH = 586;
const BUF = PAGES * 65536 - STACK - SCRATCH - 1024;

var scratch: [SCRATCH]u8 = undefined;
var buf: [BUF]u8 = undefined;

const cp1252 = [32]u16{
    0x20AC, 0x81,   0x201A, 0x0192, 0x201E, 0x2026, 0x2020, 0x2021,
    0x02C6, 0x2030, 0x0160, 0x2039, 0x0152, 0x8D,   0x017D, 0x8F,
    0x90,   0x2018, 0x2019, 0x201C, 0x201D, 0x2022, 0x2013, 0x2014,
    0x02DC, 0x2122, 0x0161, 0x203A, 0x0153, 0x9D,   0x017E, 0x0178,
};

// Canonical Huffman tables generated by gen4.py: counts per code length, then symbols.
// PAIR holds byte-pair merges: symbol 128+i expands to PAIR[2i], PAIR[2i+1].
const P_CNT = 0;
const P_SYM = 10;
const C_CNT = 28;
const C_SYM = 40;
const K_CNT = 224;
const K_SYM = 230;
const S_CNT = 248;
const S_SYM = 251;
const PAIR = 255;
const huff = [_]u8{0,2,2,1,4,2,3,1,1,2,1,2,3,4,5,0,6,7,8,9,11,10,12,13,14,15,16,17,0,1,0,0,2,15,21,32,71,14,20,8,0,101,116,1,2,99,100,104,105,107,108,109,110,111,112,114,115,117,97,98,102,103,113,118,119,121,128,130,132,136,140,141,145,147,150,157,158,159,163,68,69,72,83,129,133,135,137,144,151,152,153,156,160,162,165,166,168,175,178,179,182,184,185,187,188,189,191,192,195,196,198,65,66,67,70,76,80,82,84,85,106,120,122,134,138,139,142,149,161,164,173,174,176,177,180,181,186,193,199,202,203,204,205,208,209,210,213,214,215,216,217,218,219,220,221,223,225,226,227,228,230,231,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,251,252,253,254,51,52,53,73,74,79,86,148,155,170,172,194,197,200,49,50,56,71,77,78,81,131,143,154,167,171,183,201,206,207,211,212,222,229,54,55,87,89,90,169,224,232,0,0,1,12,3,2,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,18,1,1,2,0,1,2,3,97,114,114,111,97,108,129,119,111,110,97,99,111,116,105,108,108,101,113,117,105,103,110,116,101,114,99,121,105,109,115,99,112,102,143,114,65,114,100,134,104,116,105,114,102,114,111,114,110,103,101,115,69,137,138,148,128,131,101,113,154,130,128,114,101,100,117,115,114,105,97,112,101,116,146,131,114,101,102,116,111,144,116,101,99,116,100,101,117,169,118,101,149,99,117,98,111,119,135,171,105,110,133,172,108,97,115,104,66,128,101,170,115,142,117,109,114,155,104,128,105,139,108,161,86,183,190,151,117,112,176,110,97,116,115,164,116,97,133,101,112,128,99,174,114,97,99,128,160,135,136,167,146,114,105,115,101,101,97,152,201,132,114,114,84,177,82,155,112,129,108,108,101,139,180,139,97,181,116,162,200,173,117,114,111,108,105,99,101,167,84,206,194,140,207,136,186,156,98,128,108,138,133,114,142,153,211,165,166,224,83,112,233,197,98,114,212,120,68,134,101,103,76,222,71,232,109,105,110,69,109,229,103,132,108,111,116,111,115,115,128,101,109,97,76,153,250,115,99,99,142,101,100,193};
const second_cp = [8]u32{ 106, 817, 819, 824, 8202, 8402, 8421, 65024 };

// Placeholder: the build replaces this body with memory.init from the table.
export fn tbl(dst: [*]u8, off: u32, n: u32) void {
    @memcpy(dst[0..n], @as([*]const u8, @ptrFromInt(off))[0..n]);
}

export fn input_ptr() u32 {
    return @intFromPtr(&buf);
}
export fn input_utf8_cap() u32 {
    return BUF;
}
export fn output_utf8_cap() u32 {
    return BUF;
}

fn utf8Len(c: u32) u32 {
    return if (c < 0x80) 1 else if (c < 0x800) 2 else if (c < 0x10000) 3 else 4;
}

fn put(w0: u32, c: u32) u32 {
    var w = w0;
    if (c < 0x80) {
        buf[w] = @truncate(c);
        return w + 1;
    }
    if (c < 0x800) {
        buf[w] = @truncate(0xC0 | c >> 6);
        w += 1;
    } else {
        if (c < 0x10000) {
            buf[w] = @truncate(0xE0 | c >> 12);
            w += 1;
        } else {
            buf[w] = @truncate(0xF0 | c >> 18);
            buf[w + 1] = @truncate(0x80 | (c >> 12 & 63));
            w += 2;
        }
        buf[w] = @truncate(0x80 | (c >> 6 & 63));
        w += 1;
    }
    buf[w] = @truncate(0x80 | (c & 63));
    return w + 1;
}

var bits_pos: u32 = 0;

fn bits(n: u32) u32 {
    var v: u32 = 0;
    var i: u32 = 0;
    while (i < n) : (i += 1) {
        v |= @as(u32, scratch[bits_pos >> 3] >> @as(u3, @truncate(bits_pos)) & 1) << @as(u5, @truncate(i));
        bits_pos += 1;
    }
    return v;
}

// Canonical Huffman decode (as in zlib's puff): counts per length, then symbols.
fn dec(cnt: u32, sym: u32) u32 {
    var code: u32 = 0;
    var first: u32 = 0;
    var index: u32 = 0;
    var c = cnt;
    while (true) {
        code |= bits(1);
        const count: u32 = huff[c];
        c += 1;
        if (code < first + count) return huff[sym + index + code - first];
        index += count;
        first = (first + count) << 1;
        code <<= 1;
    }
}

// Appends symbol t to name, expanding byte-pair merges (t >= 128).
fn emit(name: [*]u8, len: u32, t: u32) u32 {
    if (t < 128) {
        name[len] = @truncate(t);
        return len + 1;
    }
    const i = PAIR + 2 * (t - 128);
    return emit(name, emit(name, len, huff[i]), huff[i + 1]);
}

var hist: [4]u32 = undefined;

const Match = struct { m: u32 = 0, c1: u32 = 0, c2: u32 = 0 };

// Matches name s. m is bytes consumed after '&': len + 1 for an exact match
// followed by ';', else the length of the longest legacy prefix, else 0.
fn lookup(s: []const u8, semi: bool) Match {
    const n: u32 = @intCast(s.len);
    var b: u32 = (s[0] | 32) -% 'a';
    if (b > 25) return .{};
    if (s[0] & 32 != 0) b += 26;
    var ix: [2]u16 = undefined;
    @call(.never_inline, tbl, .{ @as([*]u8, @ptrCast(&ix)), b * 2, 4 });
    @call(.never_inline, tbl, .{ @as([*]u8, &scratch), ix[0], @as(u32, ix[1] - ix[0]) });
    bits_pos = 0;
    var name: [32]u8 = undefined;
    var r = Match{};
    var nv: u32 = 0;
    hist = .{ 0, 0, 0, 0 };
    while (true) {
        var len = dec(P_CNT, P_SYM);
        if (len == 0) break;
        var t: u32 = undefined;
        while (true) {
            t = dec(C_CNT, C_SYM);
            if (t <= 3) break;
            len = emit(&name, len, t);
        }
        // Values are deltas from a prediction: Xfr/Xopf/Xscr map onto the
        // Mathematical Alphanumeric Symbols block; other names pick one of the
        // last four values in the bucket.
        const tail = @as(*align(1) const u32, @ptrCast(name[1..5])).*;
        const rule: u32 = if (len == 3 and @as(u16, @truncate(tail)) == 'f' | 'r' << 8)
            0x1D504
        else if (len == 4 and tail & 0xFFFFFF == 'o' | 'p' << 8 | 'f' << 16)
            0x1D538
        else if (len == 4 and tail & 0xFFFFFF == 's' | 'c' << 8 | 'r' << 16)
            0x1D49C
        else
            0;
        const pred = if (rule != 0) rule + b else hist[(nv -% 1 -% dec(S_CNT, S_SYM)) & 3];
        const k = dec(K_CNT, K_SYM);
        const z: u32 = if (k != 0) @as(u32, 1) << @as(u5, @truncate(k - 1)) | bits(k - 1) else 0;
        const v = pred +% ((z >> 1) ^ (0 -% (z & 1)));
        if (rule == 0) {
            hist[nv & 3] = v;
            nv += 1;
        }
        const v2: u32 = if (t & 2 != 0) second_cp[bits(3)] else 0;
        // Names are sorted, so once one sorts after s, none later can match.
        const lim = @min(len, n);
        var i: u32 = 1;
        while (i < lim and name[i] == s[i]) i += 1;
        if (i < lim) {
            if (name[i] > s[i]) break;
            continue;
        }
        if (len > n) break;
        if (semi and len == n) {
            r.m = n + 1;
        } else if (t & 1 == 0 or len <= r.m) {
            continue;
        } else r.m = len;
        r.c1 = v;
        r.c2 = v2;
        if (r.m > n) break;
    }
    return r;
}

fn stop(c: u8) bool {
    return switch (c) {
        '\t', '\n', 0x0C, ' ', '<', '&', '#', ';' => true,
        else => false,
    };
}

export fn render(len: u32) u64 {
    const end: u32 = BUF;
    var r: u32 = end - len;
    var w: u32 = 0;
    @memmove(buf[r..end], buf[0..len]);
    while (r < end) {
        const c = buf[r];
        if (c != '&') {
            buf[w] = c;
            w += 1;
            r += 1;
            continue;
        }
        var p = r + 1;
        var after: u32 = undefined;
        var c1: u32 = undefined;
        var c2: u32 = 0;
        if (p < end and buf[p] == '#') {
            p += 1;
            const hex = p < end and (buf[p] | 32) == 'x';
            if (hex) p += 1;
            const digits = p;
            var num: u32 = 0;
            while (p < end) : (p += 1) {
                var d: u32 = buf[p] -% '0';
                if (d > 9) {
                    if (!hex) break;
                    d = (buf[p] | 32) -% 'a';
                    if (d > 5) break;
                    d += 10;
                }
                num = num * @as(u32, if (hex) 16 else 10) + d;
                if (num > 0x10FFFF) num = 0x110000;
            }
            if (p == digits) {
                buf[w] = c;
                w += 1;
                r += 1;
                continue;
            }
            if (p < end and buf[p] == ';') p += 1;
            if (num == 0 or (num >= 0xD800 and num <= 0xDFFF) or num > 0x10FFFF) {
                num = 0xFFFD;
            } else if (num >= 0x80 and num <= 0x9F) num = cp1252[num - 0x80];
            c1 = num;
            after = p;
        } else {
            var n: u32 = 0;
            while (p + n < end and n < 32 and !stop(buf[p + n])) n += 1;
            const m = if (n != 0) lookup(buf[p .. p + n], p + n < end and buf[p + n] == ';') else Match{};
            if (m.m == 0) {
                buf[w] = c;
                w += 1;
                r += 1;
                continue;
            }
            c1 = m.c1;
            c2 = m.c2;
            after = p + m.m;
        }
        if (w + utf8Len(c1) + (if (c2 != 0) utf8Len(c2) else 0) > after) return 1 << 63;
        w = put(w, c1);
        if (c2 != 0) w = put(w, c2);
        r = after;
    }
    return @as(u64, input_ptr()) << 32 | w;
}

// ---------------------------------------------------------------------------
// Build (Zig 0.15.2, wasm-tools 1.263.0:
//   python3 gen4.py 127        # writes table4.bin; header constants inlined above
//   zig build-exe unescape.zig -target wasm32-freestanding -mcpu=mvp+bulk_memory
//     -O ReleaseSmall -fno-entry -rdynamic --stack 256 --initial-memory=131072
//     --max-memory=131072 -fstrip -femit-bin=raw.wasm
//   python3 patch.py raw.wasm table4.bin unescape.wasm
// patch.py swaps the tbl placeholder for memory.init and appends table4.bin
// as a passive data segment.
//
// ----- gen4.py -----
// # gen4.py NMERGE: builds the passive entity table (table4.bin) and the Huffman
// # header constants (tab4.json, inlined into the source). Per first-letter bucket,
// # a byte-aligned LSB-first bit stream of records, names in sorted order:
// #   Huffman P(prefix length shared with the previous name, >= 1; 0 ends bucket)
// #   Huffman C(name symbols..., then terminator 0-3 = legacy | pair << 1)
// #     symbols 128+i are byte-pair merges expanding to PAIR[2i], PAIR[2i+1]
// #   value prediction: Xfr/Xopf/Xscr use base + letter index; other names take
// #     Huffman S(choice among the last four values in the bucket)
// #   Huffman K(k = bit length of zigzag delta from prediction) + (k-1) raw bits
// #   if pair: 3-bit index into second_cp.
// import html.entities as e, collections, heapq, sys, json
// NM = int(sys.argv[1])
// h = e.html5
// names = sorted({k.rstrip(';') for k in h})
// SECOND = sorted({ord(h[n + ';'][1]) for n in names if len(h[n + ';']) > 1})
// order = [chr(c) for c in range(65, 91)] + [chr(c) for c in range(97, 123)]
// BASE = {'fr': 0x1D504, 'opf': 0x1D538, 'scr': 0x1D49C}
// recs = []; prev = ''
// for n in names:
//     if prev[:1] != n[:1]: prev = n[0]; hist = [0] * 4
//     p = 1
//     while p < min(len(n), len(prev)) and n[p] == prev[p]: p += 1
//     v = [ord(c) for c in h[n + ';']]
//     rule = n[1:] in BASE
//     if rule: cands = [BASE[n[1:]] + order.index(n[0])]
//     else: cands = hist[::-1]
//     best = None
//     for i, pv in enumerate(cands):
//         d = v[0] - pv; z = (d << 1) ^ (d >> 63)
//         if best is None or z.bit_length() < best[0]: best = (z.bit_length(), i, z)
//     if not rule: hist = hist[1:] + [v[0]]
//     term = (n in h) | ((len(v) > 1) << 1)
//     recs.append([n[0], p, [ord(c) for c in n[p:]], term, best[0], best[2], SECOND.index(v[1]) if len(v) > 1 else 0, None if rule else best[1]])
//     prev = n
// pairs = []
// for i in range(NM):
//     pc = collections.Counter()
//     for r in recs:
//         s = r[2]
//         for a, b in zip(s, s[1:]): pc[a, b] += 1
//     if not pc: break
//     (a, b), c = pc.most_common(1)[0]
//     if c < 3: break
//     sym = 128 + i; pairs += [a, b]
//     for r in recs:
//         s = r[2]; o = []; j = 0
//         while j < len(s):
//             if j + 1 < len(s) and s[j] == a and s[j + 1] == b: o.append(sym); j += 2
//             else: o.append(s[j]); j += 1
//         r[2] = o
//
// def lengths(cnt):
//     hp = [(c, i, [s]) for i, (s, c) in enumerate(sorted(cnt.items()))]; heapq.heapify(hp)
//     L = {s: 0 for s in cnt}; k = len(hp)
//     while len(hp) > 1:
//         a = heapq.heappop(hp); b = heapq.heappop(hp)
//         for s in a[2] + b[2]: L[s] += 1
//         heapq.heappush(hp, (a[0] + b[0], k, a[2] + b[2])); k += 1
//     assert max(L.values()) <= 15, max(L.values())
//     return L
// def canon(L):
//     syms = sorted(L, key=lambda s: (L[s], s)); code = 0; codes = {}; last = 0
//     for s in syms:
//         code <<= (L[s] - last); last = L[s]; codes[s] = (code, L[s]); code += 1
//     cnt = [0] * 16
//     for s in syms: cnt[L[s]] += 1
//     return codes, cnt, syms
// alph = {a: collections.Counter() for a in 'PCKS'}
// alph['P'][0] += len(order)
// for b, p, s, t, k, z, sec, sel in recs:
//     if sel is not None: alph['S'][sel] += 1
//     alph['P'][p] += 1; alph['K'][k] += 1
//     for c in s: alph['C'][c] += 1
//     alph['C'][t] += 1
// tabs = {a: canon(lengths(c)) for a, c in alph.items()}
// class Bits:
//     def __init__(s): s.out = bytearray(); s.acc = 0; s.n = 0
//     def put(s, v, n):
//         for i in range(n): s.bit((v >> i) & 1)
//     def bit(s, b):
//         s.acc |= b << s.n; s.n += 1
//         if s.n == 8: s.out.append(s.acc); s.acc = 0; s.n = 0
//     def huff(s, a, sym):
//         code, n = tabs[a][0][sym]
//         for i in range(n - 1, -1, -1): s.bit((code >> i) & 1)
//     def done(s):
//         if s.n: s.out.append(s.acc); s.acc = 0; s.n = 0
//         return s.out
// streams = {c: Bits() for c in order}
// for b, p, s, t, k, z, sec, sel in recs:
//     w = streams[b]; w.huff('P', p)
//     for c in s: w.huff('C', c)
//     w.huff('C', t)
//     if sel is not None: w.huff('S', sel)
//     w.huff('K', k)
//     if k > 1: w.put(z, k - 1)
//     if t & 2: w.put(sec, 3)
// idx = bytearray(); body = bytearray(); base = 2 * 53
// for c in order:
//     streams[c].huff('P', 0)
//     idx += (base + len(body)).to_bytes(2, 'little'); body += streams[c].done()
// idx += (base + len(body)).to_bytes(2, 'little')
// open('table4.bin', 'wb').write(idx + body)
// hdr = bytearray(); off = {}
// for a in 'PCKS':
//     codes, cnt, syms = tabs[a]
//     top = max(i for i in range(16) if cnt[i])
//     off[a + '_CNT'] = len(hdr); hdr += bytes(cnt[1:top + 1])
//     off[a + '_SYM'] = len(hdr); hdr += bytes(syms)
// off['PAIR'] = len(hdr); hdr += bytes(pairs)
// mx = max(len(s.out) for s in streams.values())
// json.dump(dict(off=off, huff=list(hdr), second=SECOND + [0] * (8 - len(SECOND)), scratch=mx + 8), open('tab4.json', 'w'))
// print(NM, 'table', len(idx + body), 'hdr', len(hdr), 'total', len(idx + body) + len(hdr), 'maxbucket', mx, file=sys.stderr)
//
// ----- patch.py -----
// # Replace the exported `tbl` placeholder with memory.init from a passive table segment.
// import re, subprocess, sys
// raw, table, out = sys.argv[1:4]
// wat = subprocess.run(['wasm-tools', 'print', raw], check=True, capture_output=True, text=True).stdout
// m = re.search(r'\(export "tbl" \(func (\d+)\)\)\n', wat)
// fn = m.group(1); wat = wat.replace(m.group(0), '')
// start = wat.index(f'(func (;{fn};) ')
// depth, i = 0, start
// while True:
//     if wat[i] == '(': depth += 1
//     elif wat[i] == ')':
//         depth -= 1
//         if depth == 0: break
//     i += 1
// head = wat[start:wat.index('\n', start)]
// seg = sum(1 for _ in re.finditer(r'^\s*\(data ', wat, re.M))
// wat = wat[:start] + head + f'\n    local.get 0\n    local.get 1\n    local.get 2\n    memory.init {seg}\n  )' + wat[i + 1:]
// data = open(table, 'rb').read()
// esc = ''.join(f'\\{b:02x}' for b in data)
// k = wat.rstrip().rindex(')')
// wat = wat[:k] + f'  (data "{esc}")\n)\n'
// open(out + '.wat', 'w').write(wat)
// subprocess.run(['wasm-tools', 'parse', out + '.wat', '-o', out], check=True)
// subprocess.run(['wasm-tools', 'validate', out], check=True)