// SPDX-License-Identifier: MIT
// In-place HTML character-reference decoder in two Wasm pages (Odin 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.
package unescape
import "base:intrinsics"
PAGES :: 2
STACK :: 256
SCRATCH :: 586
BUF :: PAGES * 65536 - STACK - SCRATCH - 1024
scratch: [SCRATCH]u8
buf: [BUF]u8
bits_pos: u32
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].
P_CNT :: 0
P_SYM :: 10
C_CNT :: 28
C_SYM :: 40
K_CNT :: 224
K_SYM :: 230
S_CNT :: 248
S_SYM :: 251
PAIR :: 255
huff := [509]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}
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)
tbl :: #force_no_inline proc "c" (dst: [^]u8, off: u32, n: u32) {
intrinsics.mem_copy_non_overlapping(dst, rawptr(uintptr(off)), int(n))
}
@(export)
input_ptr :: proc "c" () -> u32 { return u32(uintptr(&buf)) }
@(export)
input_utf8_cap :: proc "c" () -> u32 { return BUF }
@(export)
output_utf8_cap :: proc "c" () -> u32 { return BUF }
utf8_len :: proc "contextless" (c: u32) -> u32 {
return 1 if c < 0x80 else 2 if c < 0x800 else 3 if c < 0x10000 else 4
}
put :: proc "contextless" (w0: u32, c: u32) -> u32 {
w := w0
if c < 0x80 { buf[w] = u8(c); return w + 1 }
if c < 0x800 {
buf[w] = u8(0xC0 | c >> 6); w += 1
} else {
if c < 0x10000 {
buf[w] = u8(0xE0 | c >> 12); w += 1
} else {
buf[w] = u8(0xF0 | c >> 18)
buf[w + 1] = u8(0x80 | (c >> 12 & 63))
w += 2
}
buf[w] = u8(0x80 | (c >> 6 & 63)); w += 1
}
buf[w] = u8(0x80 | (c & 63))
return w + 1
}
bits :: proc "contextless" (n: u32) -> u32 {
v: u32 = 0
for i: u32 = 0; i < n; i += 1 {
v |= (u32(scratch[bits_pos >> 3] >> (bits_pos & 7)) & 1) << (i & 31)
bits_pos += 1
}
return v
}
// Canonical Huffman decode (as in zlib's puff): counts per length, then symbols.
dec :: proc "contextless" (cnt: u32, sym: u32) -> u32 {
code, first, index, c: u32 = 0, 0, 0, cnt
for {
code |= bits(1)
count := u32(huff[c]); c += 1
if code < first + count { return u32(huff[sym + index + code - first]) }
index += count
first = (first + count) << 1
code <<= 1
}
}
// Appends symbol t to name, expanding byte-pair merges (t >= 128).
emit :: proc "contextless" (name: [^]u8, len: u32, t: u32) -> u32 {
if t < 128 {
name[len] = u8(t)
return len + 1
}
i := PAIR + 2 * (t - 128)
return emit(name, emit(name, len, u32(huff[i])), u32(huff[i + 1]))
}
hist: [4]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.
lookup :: proc "contextless" (s: u32, n: u32, semi: bool, c1, c2: ^u32) -> u32 {
s0 := buf[s]
b := u32(s0 | 32) - 'a'
if b > 25 { return 0 }
if s0 & 32 != 0 { b += 26 }
ix: [2]u16 = ---
tbl(cast([^]u8)&ix, b * 2, 4)
tbl(&scratch[0], u32(ix[0]), u32(ix[1] - ix[0]))
bits_pos = 0
name: [32]u8 = ---
best: u32 = 0
nv: u32 = 0
hist = {}
for {
len := dec(P_CNT, P_SYM)
if len == 0 { break }
t: u32 = ---
for {
t = dec(C_CNT, C_SYM)
if t <= 3 { break }
len = emit(&name[0], 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.
tail := intrinsics.unaligned_load(cast(^u32)&name[1])
rule: u32 = 0
if len == 3 && u16(tail) == 'f' | 'r' << 8 {
rule = 0x1D504
} else if len == 4 && tail & 0xFFFFFF == 'o' | 'p' << 8 | 'f' << 16 {
rule = 0x1D538
} else if len == 4 && tail & 0xFFFFFF == 's' | 'c' << 8 | 'r' << 16 {
rule = 0x1D49C
}
pred := rule + b if rule != 0 else hist[(nv - 1 - dec(S_CNT, S_SYM)) & 3]
k := dec(K_CNT, K_SYM)
z: u32 = (u32(1) << ((k - 1) & 31) | bits(k - 1)) if k != 0 else 0
v := pred + ((z >> 1) ~ -(z & 1))
if rule == 0 {
hist[nv & 3] = v
nv += 1
}
v2: u32 = second_cp[bits(3)] if t & 2 != 0 else 0
// Names are sorted, so once one sorts after s[0..n), none later can match.
lim := min(len, n)
i: u32 = 1
for i < lim && name[i] == buf[s + i] { i += 1 }
if i < lim {
if name[i] > buf[s + 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 }
}
return best
}
stop :: proc "contextless" (c: u8) -> bool {
switch c {
case '\t', '\n', 0x0C, ' ', '<', '&', '#', ';': return true
}
return false
}
@(export)
render :: proc "c" (len: u32) -> u64 {
end: u32 = BUF
r := end - len
w: u32 = 0
intrinsics.mem_copy(&buf[r], &buf[0], int(len))
for r < end {
c := buf[r]
if c != '&' { buf[w] = c; w += 1; r += 1; continue }
p := r + 1
after: u32 = ---
c1, c2: u32
if p < end && buf[p] == '#' {
p += 1
hex := p < end && (buf[p] | 32) == 'x'
if hex { p += 1 }
digits := p
num: u32 = 0
for ; p < end; p += 1 {
d := u32(buf[p]) - '0'
if d > 9 {
if !hex { break }
d = u32(buf[p] | 32) - 'a'
if d > 5 { break }
d += 10
}
num = num * (16 if hex else 10) + d
if num > 0x10FFFF { num = 0x110000 }
}
if p == digits { buf[w] = c; w += 1; r += 1; continue }
if p < end && buf[p] == ';' { p += 1 }
if num == 0 || (num >= 0xD800 && num <= 0xDFFF) || num > 0x10FFFF {
num = 0xFFFD
} else if num >= 0x80 && num <= 0x9F {
num = u32(cp1252[num - 0x80])
}
c1 = num
after = p
} else {
n: u32 = 0
for p + n < end && n < 32 && !stop(buf[p + n]) { n += 1 }
m: u32 = lookup(p, n, p + n < end && buf[p + n] == ';', &c1, &c2) if n != 0 else 0
if m == 0 { buf[w] = c; w += 1; r += 1; continue }
after = p + m
}
if w + utf8_len(c1) + (utf8_len(c2) if c2 != 0 else 0) > after { return 1 << 63 }
w = put(w, c1)
if c2 != 0 { w = put(w, c2) }
r = after
}
return u64(input_ptr()) << 32 | u64(w)
}
/* ---------------------------------------------------------------------------
* Build (Odin dev-2026-10:84bc3fc21, wasm-tools 1.263.0:
* python3 gen4.py 127 # writes table4.bin; header constants inlined above
* odin build unescape.odin -file -target:freestanding_wasm32 -no-entry-point
* -o:size -no-bounds-check -disable-assert -default-to-nil-allocator -no-crt
* -target-features:bulk-memory -extra-linker-flags:"-zstack-size=256
* --initial-memory=131072 --max-memory=131072 --strip-all" -out: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)
*/