/* SPDX-License-Identifier: MIT
 * In-place HTML character-reference decoder in two Wasm pages.
 * 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.
 */
#include <stdint.h>
/* Generated by gen2.py (below) as huff.h. */
#define P_CNT 0
#define P_SYM 10
#define C_CNT 28
#define C_SYM 41
#define K_CNT 102
#define K_SYM 108
static const unsigned char huff[] = {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,5,7,8,7,4,5,8,10,2,4,0,97,101,111,114,116,99,105,108,110,112,115,117,100,102,103,104,109,113,119,121,1,2,65,69,98,107,118,66,68,83,84,72,76,82,86,120,67,70,71,73,80,85,106,122,50,51,52,53,56,74,77,78,79,81,49,54,55,87,89,90,0,0,3,6,7,2,12,15,18,3,9,10,11,13,14,0,1,2,4,5,7,8,6,17};
static const uint32_t second_cp[8] = {106,817,819,824,8202,8402,8421,65024};
#define SCRATCH 682
#define EXPORT __attribute__((visibility("default")))

#define PAGES 2
#define STACK 256
#define BUF (PAGES * 65536 - STACK - SCRATCH - 512)

static unsigned char scratch[SCRATCH];
static unsigned char buf[BUF];
static const uint16_t cp1252[32] = {
    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};

/* Placeholder: the build replaces this body with memory.init from the table. */
__attribute__((noinline)) EXPORT void tbl(void *dst, uint32_t off, uint32_t n) {
  __builtin_memcpy(dst, (const void *)off, n);
}

EXPORT uint32_t input_ptr(void) { return (uint32_t)buf; }
EXPORT uint32_t input_utf8_cap(void) { return BUF; }
EXPORT uint32_t output_utf8_cap(void) { return BUF; }

static unsigned utf8_len(uint32_t c) { return c < 0x80 ? 1 : c < 0x800 ? 2 : c < 0x10000 ? 3 : 4; }

static unsigned char *put(unsigned char *w, uint32_t c) {
  if (c < 0x80) { *w++ = c; return w; }
  if (c < 0x800) { *w++ = 0xC0 | c >> 6; }
  else {
    if (c < 0x10000) { *w++ = 0xE0 | c >> 12; }
    else { *w++ = 0xF0 | c >> 18; *w++ = 0x80 | (c >> 12 & 63); }
    *w++ = 0x80 | (c >> 6 & 63);
  }
  *w++ = 0x80 | (c & 63);
  return w;
}

static const unsigned char *bits_p;
static uint32_t bits_pos;

static uint32_t bits(unsigned n) {
  uint32_t v = 0;
  for (unsigned i = 0; i < n; i++, bits_pos++)
    v |= (uint32_t)(bits_p[bits_pos >> 3] >> (bits_pos & 7) & 1) << i;
  return v;
}

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

/* Matches name s[0..n). Returns bytes consumed after '&': n + 1 for an exact
 * match followed by ';', else the length of the longest legacy prefix, else 0. */
static unsigned lookup(const unsigned char *s, unsigned n, int semi, uint32_t *c1, uint32_t *c2) {
  unsigned b = (s[0] | 32) - 'a';
  if (b > 25) return 0;
  b += s[0] & 32 ? 26 : 0;
  uint16_t ix[2];
  tbl(ix, b * 2, 4);
  tbl(scratch, ix[0], ix[1] - ix[0]);
  bits_p = scratch; bits_pos = 0;
  unsigned char name[32];
  unsigned best = 0;
  uint32_t v = 0;
  for (;;) {
    unsigned len = dec(P_CNT, P_SYM), t;
    if (!len) break;
    while ((t = dec(C_CNT, C_SYM)) > 3) name[len++] = t;
    unsigned k = dec(K_CNT, K_SYM);
    uint32_t z = k ? 1u << (k - 1) | bits(k - 1) : 0;
    v += (z >> 1) ^ -(z & 1);
    uint32_t v2 = t & 2 ? second_cp[bits(3)] : 0;
    /* Names are sorted, so once one sorts after s[0..n), none later can match. */
    unsigned i = 1, lim = len < n ? len : n;
    while (i < lim && name[i] == s[i]) i++;
    if (i < lim) { if (name[i] > s[i]) break; continue; }
    if (len > n) break;
    if (semi && len == n) best = n + 1;
    else if (!(t & 1) || len <= best) continue;
    else best = len;
    *c1 = v; *c2 = v2;
    if (best > n) break;
  }
  return best;
}

static int stop(unsigned char c) {
  return c == '\t' || c == '\n' || c == '\f' || c == ' ' || c == '<' || c == '&' || c == '#' || c == ';';
}

EXPORT uint64_t render(uint32_t len) {
  unsigned char *end = buf + BUF, *r = end - len, *w = buf;
  __builtin_memmove(r, buf, len);
  while (r < end) {
    unsigned char c = *r;
    if (c != '&') { *w++ = c; r++; continue; }
    unsigned char *p = r + 1, *after;
    uint32_t c1, c2 = 0;
    if (p < end && *p == '#') {
      p++;
      unsigned hex = p < end && (*p | 32) == 'x';
      p += hex;
      unsigned char *digits = p;
      uint32_t num = 0;
      while (p < end) {
        unsigned d = *p - '0';
        if (d > 9) {
          if (!hex) break;
          d = (*p | 32) - 'a';
          if (d > 5) break;
          d += 10;
        }
        num = num * (hex ? 16 : 10) + d;
        if (num > 0x10FFFF) num = 0x110000;
        p++;
      }
      if (p == digits) { *w++ = c; r++; continue; }
      if (p < end && *p == ';') p++;
      if (num == 0 || (num >= 0xD800 && num <= 0xDFFF) || num > 0x10FFFF) num = 0xFFFD;
      else if (num >= 0x80 && num <= 0x9F) num = cp1252[num - 0x80];
      c1 = num;
      after = p;
    } else {
      unsigned n = 0;
      while (p + n < end && n < 32 && !stop(p[n])) n++;
      unsigned m = n ? lookup(p, n, p + n < end && p[n] == ';', &c1, &c2) : 0;
      if (!m) { *w++ = c; r++; continue; }
      after = p + m;
    }
    if (w + utf8_len(c1) + (c2 ? utf8_len(c2) : 0) > after) return 1ULL << 63;
    w = put(w, c1);
    if (c2) w = put(w, c2);
    r = after;
  }
  return (uint64_t)(uint32_t)buf << 32 | (uint32_t)(w - buf);
}

/* ---------------------------------------------------------------------------
 * Build (zig 0.15.2, wasm-tools):
 *   python3 gen2.py            # writes table2.bin and huff.h (inlined above)
 *   zig cc -target wasm32-freestanding -Oz -mbulk-memory -nostdlib
 *     -Wl,--no-entry -Wl,--export-memory -Wl,-z,stack-size=256
 *     -Wl,--initial-memory=131072 -Wl,--max-memory=131072
 *     -Wl,--export=input_ptr -Wl,--export=input_utf8_cap
 *     -Wl,--export=output_utf8_cap -Wl,--export=render -Wl,--export=tbl
 *     -Wl,--strip-all unescape.c -o raw.wasm
 *   python3 patch.py raw.wasm table2.bin unescape.wasm
 * patch.py swaps the tbl placeholder for memory.init and appends table2.bin
 * as a passive data segment.
 *
 * ----- gen2.py -----
# Compact passive table: per first-letter bucket, a byte-aligned LSB-first bit stream.
# Record: Huffman(prefix len, >=1) Huffman(chars..., terminator 0-3 = legacy|pair<<1)
#         Huffman(k = bit length of zigzag delta of cp1) + (k-1) raw bits; pair: 3-bit index.
# Writes table.bin (53 u16 bucket offsets + streams) and huff.h (canonical tables).
import html.entities as e, collections, heapq, sys
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})
assert len(SECOND) <= 8
order = [chr(c) for c in range(65, 91)] + [chr(c) for c in range(97, 123)]

recs = []  # (bucket, prefix, suffix, term, k, mant, second)
prev = ''; pv = 0
for n in names:
    if prev[:1] != n[:1]: prev = n[0]; pv = 0
    p = 1
    while p < min(len(n), len(prev)) and n[p] == prev[p]: p += 1
    v = [ord(c) for c in h[n + ';']]
    d = v[0] - pv; pv = v[0]; z = (d << 1) ^ (d >> 63)
    term = (n in h) | ((len(v) > 1) << 1)
    recs.append((n[0], p, n[p:], term, z.bit_length(), z, SECOND.index(v[1]) if len(v) > 1 else 0))
    prev = n

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)
    if len(hp) == 1: return {s: 1 for s in cnt}
    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
    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 = {'P': collections.Counter(), 'C': collections.Counter(), 'K': collections.Counter()}
alph['P'][0] += len(order)
for b, p, s, t, k, z, sec in recs:
    alph['P'][p] += 1; alph['K'][k] += 1
    for c in s: alph['C'][ord(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):  # raw, LSB first
        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 in recs:
    w = streams[b]; w.huff('P', p)
    for c in s: w.huff('C', ord(c))
    w.huff('C', t); 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('table2.bin', 'wb').write(idx + body)
mx = max(len(s.out) for s in streams.values())
with open('huff.h', 'w') as f:
    hdr = bytearray()
    for a in 'PCK':
        codes, cnt, syms = tabs[a]
        top = max(i for i in range(16) if cnt[i])
        f.write(f'#define {a}_CNT {len(hdr)}\n'); hdr += bytes(cnt[1:top + 1]) + b'\0' * 0  # lengths 1..top
        f.write(f'#define {a}_SYM {len(hdr)}\n'); hdr += bytes(syms)
    f.write('static const unsigned char huff[] = {' + ','.join(map(str, hdr)) + '};\n')
    f.write('static const uint32_t second_cp[8] = {' + ','.join(map(str, SECOND + [0] * (8 - len(SECOND)))) + '};\n')
    f.write(f'#define SCRATCH {mx + 8}\n')
print('table2', len(idx + body), 'huff hdr', len(hdr), 'max bucket', 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)
 */