// SPDX-License-Identifier: MIT
// In-place HTML character-reference decoder in two Wasm pages (Rust 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.
#![no_std]
#![allow(static_mut_refs)]
const PAGES: usize = 2;
const STACK: usize = 256;
const SCRATCH: usize = 586;
const BUF: usize = PAGES * 65536 - STACK - SCRATCH - 1024;
static mut SCRATCH_BUF: [u8; SCRATCH] = [0; SCRATCH];
static mut BUFFER: [u8; BUF] = [0; BUF];
static mut BITS_POS: u32 = 0;
static mut HIST: [u32; 4] = [0; 4];
static CP1252: [u16; 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,
];
// 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: usize = 0;
const P_SYM: usize = 10;
const C_CNT: usize = 28;
const C_SYM: usize = 40;
const K_CNT: usize = 224;
const K_SYM: usize = 230;
const S_CNT: usize = 248;
const S_SYM: usize = 251;
const PAIR: usize = 255;
static HUFF: [u8; 509] = [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];
static SECOND_CP: [u32; 8] = [106, 817, 819, 824, 8202, 8402, 8421, 65024];
#[panic_handler]
fn panic(_: &core::panic::PanicInfo) -> ! {
core::arch::wasm32::unreachable()
}
/// Placeholder: the build replaces this body with memory.init from the table.
#[no_mangle]
#[inline(never)]
pub unsafe extern "C" fn tbl(dst: *mut u8, off: u32, n: u32) {
core::ptr::copy_nonoverlapping(off as usize as *const u8, dst, n as usize);
}
#[inline(always)]
unsafe fn base() -> *mut u8 {
BUFFER.as_mut_ptr()
}
#[no_mangle]
pub extern "C" fn input_ptr() -> u32 {
unsafe { base() as u32 }
}
#[no_mangle]
pub extern "C" fn input_utf8_cap() -> u32 {
BUF as u32
}
#[no_mangle]
pub extern "C" fn output_utf8_cap() -> u32 {
BUF as u32
}
fn utf8_len(c: u32) -> usize {
if c < 0x80 { 1 } else if c < 0x800 { 2 } else if c < 0x10000 { 3 } else { 4 }
}
unsafe fn put(mut w: *mut u8, c: u32) -> *mut u8 {
if c < 0x80 {
*w = c as u8;
return w.add(1);
}
if c < 0x800 {
*w = (0xC0 | c >> 6) as u8;
w = w.add(1);
} else {
if c < 0x10000 {
*w = (0xE0 | c >> 12) as u8;
w = w.add(1);
} else {
*w = (0xF0 | c >> 18) as u8;
*w.add(1) = (0x80 | (c >> 12 & 63)) as u8;
w = w.add(2);
}
*w = (0x80 | (c >> 6 & 63)) as u8;
w = w.add(1);
}
*w = (0x80 | (c & 63)) as u8;
w.add(1)
}
unsafe fn bits(n: u32) -> u32 {
let mut v = 0u32;
let s = SCRATCH_BUF.as_ptr();
let mut i = 0;
while i < n {
v |= ((*s.add((BITS_POS >> 3) as usize) >> (BITS_POS & 7)) as u32 & 1) << i;
BITS_POS += 1;
i += 1;
}
v
}
/// Canonical Huffman decode (as in zlib's puff): counts per length, then symbols.
unsafe fn dec(cnt: usize, sym: usize) -> u32 {
let h = HUFF.as_ptr();
let (mut code, mut first, mut index, mut c) = (0u32, 0u32, 0u32, cnt);
loop {
code |= bits(1);
let count = *h.add(c) as u32;
c += 1;
if code < first + count {
return *h.add(sym + (index + code - first) as usize) as u32;
}
index += count;
first = (first + count) << 1;
code <<= 1;
}
}
/// Appends symbol t to name, expanding byte-pair merges (t >= 128).
unsafe fn emit(name: *mut u8, len: usize, t: u32) -> usize {
if t < 128 {
*name.add(len) = t as u8;
return len + 1;
}
let p = HUFF.as_ptr().add(PAIR + 2 * (t as usize - 128));
emit(name, emit(name, len, *p as u32), *p.add(1) as u32)
}
/// 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.
unsafe fn lookup(s: *const u8, n: usize, semi: bool, c1: &mut u32, c2: &mut u32) -> usize {
let s0 = *s;
let mut b = ((s0 | 32) as u32).wrapping_sub(b'a' as u32);
if b > 25 {
return 0;
}
if s0 & 32 != 0 {
b += 26;
}
let mut ix = [0u16; 2];
tbl(ix.as_mut_ptr() as *mut u8, b * 2, 4);
tbl(SCRATCH_BUF.as_mut_ptr(), ix[0] as u32, (ix[1] - ix[0]) as u32);
BITS_POS = 0;
let mut name = [0u8; 32];
let name = name.as_mut_ptr();
let mut best = 0usize;
HIST = [0; 4];
let mut nv = 0usize;
loop {
let mut len = dec(P_CNT, P_SYM) as usize;
if len == 0 {
break;
}
let mut t;
loop {
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.
let tail = core::ptr::read_unaligned(name.add(1) as *const u32);
let rule = if len == 3 && tail as u16 == u16::from_le_bytes(*b"fr") {
0x1D504
} else if len == 4 && tail & 0xFFFFFF == u32::from_le_bytes(*b"opf\0") {
0x1D538
} else if len == 4 && tail & 0xFFFFFF == u32::from_le_bytes(*b"scr\0") {
0x1D49C
} else {
0
};
let pred = if rule != 0 { rule + b } else { *HIST.as_ptr().add(nv.wrapping_sub(1 + dec(S_CNT, S_SYM) as usize) & 3) };
let k = dec(K_CNT, K_SYM);
let z = if k != 0 { 1u32 << (k - 1) | bits(k - 1) } else { 0 };
let v = pred.wrapping_add((z >> 1) ^ (z & 1).wrapping_neg());
if rule == 0 {
*HIST.as_mut_ptr().add(nv & 3) = v;
nv += 1;
}
let v2 = if t & 2 != 0 { *SECOND_CP.as_ptr().add(bits(3) as usize) } else { 0 };
// Names are sorted, so once one sorts after s[0..n), none later can match.
let lim = if len < n { len } else { n };
let mut i = 1;
while i < lim && *name.add(i) == *s.add(i) {
i += 1;
}
if i < lim {
if *name.add(i) > *s.add(i) {
break;
}
continue;
}
if len > n {
break;
}
if semi && len == n {
best = n + 1;
} else if t & 1 == 0 || len <= best {
continue;
} else {
best = len;
}
*c1 = v;
*c2 = v2;
if best > n {
break;
}
}
best
}
fn stop(c: u8) -> bool {
matches!(c, b'\t' | b'\n' | 0x0C | b' ' | b'<' | b'&' | b'#' | b';')
}
#[no_mangle]
pub unsafe extern "C" fn render(len: u32) -> u64 {
let buf = base();
let end = buf.add(BUF);
let mut r = end.sub(len as usize);
let mut w = buf;
core::ptr::copy(buf, r, len as usize);
while r < end {
let c = *r;
if c != b'&' {
*w = c;
w = w.add(1);
r = r.add(1);
continue;
}
let mut p = r.add(1);
let after;
let mut c1 = 0u32;
let mut c2 = 0u32;
if p < end && *p == b'#' {
p = p.add(1);
let hex = p < end && (*p | 32) == b'x';
if hex {
p = p.add(1);
}
let digits = p;
let mut num = 0u32;
while p < end {
let mut d = (*p as u32).wrapping_sub(b'0' as u32);
if d > 9 {
if !hex {
break;
}
d = ((*p | 32) as u32).wrapping_sub(b'a' as u32);
if d > 5 {
break;
}
d += 10;
}
num = num * if hex { 16 } else { 10 } + d;
if num > 0x10FFFF {
num = 0x110000;
}
p = p.add(1);
}
if p == digits {
*w = c;
w = w.add(1);
r = r.add(1);
continue;
}
if p < end && *p == b';' {
p = p.add(1);
}
if num == 0 || (0xD800..=0xDFFF).contains(&num) || num > 0x10FFFF {
num = 0xFFFD;
} else if (0x80..=0x9F).contains(&num) {
num = *CP1252.as_ptr().add((num - 0x80) as usize) as u32;
}
c1 = num;
after = p;
} else {
let mut n = 0usize;
while p.add(n) < end && n < 32 && !stop(*p.add(n)) {
n += 1;
}
let m = if n != 0 {
lookup(p, n, p.add(n) < end && *p.add(n) == b';', &mut c1, &mut c2)
} else {
0
};
if m == 0 {
*w = c;
w = w.add(1);
r = r.add(1);
continue;
}
after = p.add(m);
}
if w.add(utf8_len(c1) + if c2 != 0 { utf8_len(c2) } else { 0 }) > after {
return 1 << 63;
}
w = put(w, c1);
if c2 != 0 {
w = put(w, c2);
}
r = after;
}
(buf as u64) << 32 | (w as usize - buf as usize) as u64
}
/* ---------------------------------------------------------------------------
* Build (rustc 1.93.0, wasm-tools 1.263.0:
* python3 gen4.py 127 # writes table4.bin; header constants inlined above
* rustc --edition 2021 --target wasm32-unknown-unknown --crate-type cdylib
* -C opt-level=z -C panic=abort -C lto -C codegen-units=1 -C strip=symbols
* -C target-cpu=mvp -C target-feature=+bulk-memory
* -C link-arg=-zstack-size=256 -C link-arg=--initial-memory=131072
* -C link-arg=--max-memory=131072 unescape.rs -o raw0.wasm
* wasm-tools print raw0.wasm | grep -v -E '\(export "__(data_end|heap_base)"'
* | wasm-tools parse -o 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)
*/