// unescape_html in C with Wasm SIMD: decodes every HTML character reference in UTF-8 text
// the way Python's html.unescape does, and copies all other bytes unchanged.
//
// The design goal is a short path per reference with few unpredictable branches:
// - 64 zero bytes are written after the input, so no load or loop needs a bounds check and
// nothing stale from an earlier input can be mistaken for part of a reference.
// - Two stages per 4 KiB window. Stage 1 turns each 64-byte block into a bitmask of its `&`
// and appends their positions to a list, without branching on what it finds. Stage 2
// walks the list: copy the text since the last reference (32 bytes unconditionally, more
// in a loop), then decode. The next position is known before the current reference is
// decoded, so consecutive references do not wait on each other.
// - Inputs without `&` are returned in place; nothing is copied.
// - A name of up to 7 bytes ending in `;` is looked up without measuring it: the first `;`
// in the next 8 bytes is found with a SWAR zero-byte test, the bytes up to it are the key,
// and one multiply indexes an open-addressed table of 16-byte entries (key, value, length).
// A hit proves the name; legacy and common names sit in their home slot.
// - Longer names go through a second table and one masked 32-byte vector compare.
// - Without `;` only the 106 legacy names match. A filter on the first two bytes gives the
// longest legacy name that could start there, usually none.
// - Numeric references of up to 7 digits, decimal or hexadecimal, share one branch-free
// SWAR path, and the code point is encoded as UTF-8 without branching on its length.
// The lookup tables are built on the first call from a 6.4 KB packed entity list (24.5 KB
// unpacked), so the size of the list costs nothing per reference: see `sym` and `init`.
//
// Build: zig cc -target wasm32-freestanding -O3 -msimd128 -mbulk-memory -nostdlib
// -Wl,--no-entry -Wl,--export-memory -Wl,--initial-memory=3145728 -Wl,--max-memory=3145728
// -Wl,-z,stack-size=8192 -Wl,--strip-all -o unescape-small.wasm unescape-small.c
// then: wasm-opt -O3 --enable-simd --enable-bulk-memory unescape-small.wasm -o unescape-small.wasm
#include
#include
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
#define INPUT_CAP (1u << 20)
// The largest growth is `≫⃒` (5 bytes) becoming 6 bytes.
#define OUTPUT_CAP (INPUT_CAP / 5 * 6 + 8)
#define PAD 128
#define FAST_BITS 12
#define FAST_TAIL 32
#define LEG_BITS 8
#define LEG_TAIL 16
#define LONG_BITS 11
#define EMPTY (~(u64)0)
// Bytes of input per stage-1 window; a multiple of 64.
#define WINDOW 4096
#define HIST_SIZE 16130
#define ENTITY_COUNT 2125
#define LONG_COUNT 506
#define MODEL_BITS 18
#define MODEL_LIMIT 5
#define FAST_MUL 0xa59d054b12f5b905ull
#define LEG_MUL 0xf880d97d1854e551ull
#define LONG_MUL 0xa0c2995f40498cb3ull
static const u8 packed[6403] = {
222,225,26,230,115,49,156,154,131,111,47,238,23,226,36,124,177,10,212,147,22,18,106,98,
241,187,81,150,70,136,101,195,190,175,200,2,57,117,22,148,223,133,247,1,245,48,136,172,
158,15,4,210,106,239,138,145,213,20,255,183,153,220,207,159,81,179,120,249,67,103,45,186,
228,41,141,81,68,72,134,73,171,69,89,215,127,31,238,76,105,165,14,71,15,83,190,11,
179,202,70,217,98,226,211,59,6,154,27,161,3,30,215,225,31,79,105,226,225,101,231,23,
126,218,5,122,115,112,183,106,16,225,249,158,254,18,66,33,44,164,43,105,30,218,134,122,
132,224,196,61,77,183,23,150,12,198,174,224,95,10,79,232,121,7,21,239,253,74,129,242,
2,2,234,68,129,166,142,221,231,78,159,122,25,9,144,134,78,244,133,68,252,243,3,247,
240,160,184,129,69,207,235,151,174,249,167,243,37,254,194,192,4,244,9,68,130,225,99,254,
104,94,148,68,28,174,40,131,152,3,122,2,107,172,118,196,132,57,193,251,229,105,255,201,
57,57,231,201,148,138,220,68,100,136,102,210,11,156,44,215,46,126,30,129,72,77,100,16,
183,161,78,137,146,235,152,103,141,191,160,54,218,130,140,173,134,232,234,117,57,233,148,206,
223,240,159,49,248,77,84,188,46,94,219,119,240,15,180,221,185,227,36,2,39,13,127,186,
209,29,56,136,29,97,253,246,227,90,141,246,91,164,239,112,26,123,99,191,245,131,222,30,
125,246,39,217,164,130,160,224,55,82,138,76,104,238,115,48,249,48,159,236,232,224,145,184,
105,220,174,41,100,221,70,90,46,155,111,40,205,184,36,2,46,98,140,195,99,61,129,239,
22,9,45,87,178,95,175,255,134,126,142,178,50,110,151,79,130,148,123,230,51,143,48,116,
182,160,142,202,207,55,247,226,92,110,112,142,246,105,245,108,191,22,93,56,168,68,31,99,
114,232,136,24,80,208,76,246,101,6,224,23,43,156,155,121,35,60,215,104,82,68,140,149,
179,204,134,167,45,172,118,141,245,13,31,202,88,208,27,192,218,162,176,47,237,164,82,127,
116,112,149,57,89,70,89,208,3,79,207,118,73,35,67,88,72,158,118,2,69,140,128,110,
208,198,82,92,146,143,204,204,192,191,157,249,6,200,33,79,166,45,35,4,183,200,219,41,
174,113,171,62,60,249,222,97,112,89,162,90,59,195,229,121,140,156,117,157,221,99,166,89,
160,15,144,135,176,30,90,129,191,167,0,251,12,235,111,124,205,93,87,77,251,67,205,27,
146,120,173,224,115,65,54,92,200,86,87,26,15,146,127,240,124,97,121,84,164,17,110,201,
54,25,122,222,98,190,248,86,237,220,57,214,75,24,128,107,119,184,118,242,235,154,61,36,
236,216,153,24,89,233,81,21,15,72,123,2,94,201,60,80,21,172,111,220,119,95,250,131,
77,77,38,68,105,129,175,116,7,111,62,95,221,60,2,109,35,17,124,216,59,72,94,28,
119,251,193,132,48,99,105,54,222,197,219,151,252,93,102,162,246,1,126,250,9,34,132,37,
97,171,220,174,50,68,108,24,212,14,15,16,214,83,177,54,254,109,47,161,98,122,187,249,
20,193,250,77,89,95,173,189,26,57,225,211,153,227,179,181,53,216,89,142,117,14,63,29,
40,6,93,19,209,165,217,13,8,49,15,49,137,209,150,81,232,98,66,65,122,105,0,137,
167,12,103,188,200,158,245,141,218,220,124,198,64,41,33,9,177,73,71,133,11,227,136,209,
165,166,91,233,246,172,81,190,153,122,129,125,47,222,159,61,52,222,105,251,203,246,222,239,
136,76,92,164,208,60,139,254,110,183,151,223,231,69,245,146,59,241,57,85,162,119,219,124,
239,224,191,27,90,141,40,24,98,182,8,249,50,163,73,182,165,102,109,223,91,83,78,190,
253,230,192,138,239,138,174,31,96,125,207,175,70,235,65,249,232,206,190,68,157,52,138,141,
76,240,97,113,31,139,107,161,117,245,72,68,222,225,240,158,123,92,0,183,159,126,234,235,
26,245,77,59,70,128,152,110,18,0,123,38,124,78,10,84,118,22,0,148,222,112,218,182,
28,168,95,254,108,132,27,8,23,92,63,157,124,151,255,232,60,157,97,72,63,176,191,49,
113,34,147,151,161,108,144,30,98,219,141,186,33,247,70,2,216,174,58,26,145,35,36,167,
163,131,39,251,169,3,150,255,176,68,55,70,182,91,48,141,150,155,130,240,17,178,151,133,
227,232,65,99,196,227,130,254,99,31,171,209,140,104,186,89,22,217,159,52,227,28,192,2,
141,43,142,147,89,251,173,217,224,216,177,170,27,94,184,188,69,167,105,197,154,2,125,125,
251,207,246,147,83,36,87,64,18,140,172,69,49,84,115,150,16,31,58,202,178,248,98,42,
159,211,204,252,41,26,81,111,164,139,31,229,99,174,15,144,139,26,134,129,211,21,77,37,
173,14,2,179,62,109,80,171,236,177,50,250,69,179,238,118,180,175,49,138,194,14,132,66,
107,132,217,20,204,169,212,65,156,222,231,102,122,210,225,115,148,44,157,148,119,17,64,197,
21,159,230,103,131,174,31,0,123,165,247,62,81,7,170,211,132,122,76,147,107,217,200,111,
126,49,147,169,43,91,169,186,71,9,62,233,119,226,12,63,222,2,64,49,229,4,153,16,
223,115,198,216,120,181,229,228,11,231,244,178,50,150,77,10,132,214,241,79,24,25,180,31,
34,178,205,223,33,172,39,72,40,96,196,151,84,59,247,195,90,58,233,241,22,145,247,233,
175,22,178,151,166,177,141,170,162,221,192,23,33,57,203,238,73,102,49,108,99,2,222,151,
89,52,71,77,91,176,161,48,203,133,19,157,40,72,218,122,124,148,221,114,160,19,1,221,
229,46,3,63,243,26,201,119,52,79,78,119,84,152,222,166,92,155,104,16,117,203,36,218,
148,238,218,125,148,212,213,64,204,188,255,85,103,20,250,45,86,208,50,129,53,171,229,120,
202,224,165,90,110,168,200,149,224,147,12,89,64,151,116,217,78,52,86,193,126,59,255,172,
93,64,89,117,50,207,188,160,214,199,182,53,129,208,170,101,5,70,153,100,48,199,158,113,
124,163,248,87,95,226,234,40,111,169,85,60,233,125,62,64,106,235,164,88,215,175,35,160,
62,203,99,250,246,165,237,164,224,6,76,111,131,182,232,69,86,202,161,195,67,203,96,32,
207,102,3,116,102,250,236,106,205,107,171,209,132,189,241,185,158,156,208,184,73,94,55,126,
234,51,211,55,221,41,3,27,187,227,77,26,51,245,17,211,31,82,107,73,156,16,23,17,
184,3,188,33,218,15,196,255,181,11,76,221,36,102,59,5,55,191,242,141,233,217,159,51,
21,163,184,221,106,244,41,90,20,14,21,71,217,128,127,48,251,4,204,34,95,175,228,170,
188,221,241,184,179,22,130,160,159,9,199,14,222,101,79,111,20,226,238,196,172,191,14,246,
98,52,91,104,193,3,209,43,200,1,1,166,98,86,49,133,165,4,117,30,68,184,189,204,
234,148,230,154,191,48,61,251,105,176,254,236,72,38,55,223,216,119,83,121,67,34,249,251,
225,160,202,248,25,106,63,168,157,222,40,90,121,138,234,62,129,163,220,46,107,146,232,217,
8,244,186,230,28,76,149,143,88,181,195,40,49,241,45,111,13,78,188,108,226,237,177,18,
15,28,1,192,25,163,65,51,76,26,102,254,171,68,40,153,125,172,161,170,86,98,252,20,
187,173,222,198,50,233,119,158,229,226,218,229,162,169,95,181,113,92,75,10,165,61,226,195,
119,11,217,243,162,114,30,167,82,236,121,173,107,127,200,197,111,39,21,181,211,25,127,40,
44,203,196,207,154,63,141,143,49,53,28,223,103,163,3,38,227,220,63,188,184,189,36,255,
173,213,221,42,183,20,101,80,33,141,150,22,225,244,127,149,39,139,123,109,187,41,1,236,
50,225,171,130,27,91,41,88,210,24,176,234,244,192,144,254,145,165,122,186,69,186,61,174,
216,94,39,211,4,149,189,181,19,32,212,95,52,194,107,202,20,210,54,11,62,88,192,186,
119,105,200,20,170,110,141,181,143,235,186,206,253,100,27,89,6,226,107,45,36,60,112,79,
194,117,254,108,253,130,50,145,72,4,144,97,181,169,25,182,212,107,177,71,79,79,135,146,
182,98,143,9,78,235,9,10,135,0,175,195,195,152,62,186,136,81,39,155,40,232,70,175,
150,124,232,33,161,17,216,212,193,255,23,226,223,81,12,0,245,222,60,119,93,44,115,160,
128,254,144,41,152,218,237,211,158,191,154,218,199,249,54,36,201,143,141,171,11,121,71,25,
189,193,214,167,201,84,92,114,203,202,131,24,18,112,165,173,237,82,17,186,129,142,129,174,
50,111,55,86,169,100,172,176,127,179,120,89,224,230,92,171,4,100,110,125,237,175,233,80,
28,164,85,221,42,25,189,70,165,227,100,64,83,245,177,101,98,34,96,146,251,131,148,251,
199,73,40,251,57,126,86,53,10,114,250,35,85,49,168,215,197,145,101,95,135,152,249,201,
30,82,86,29,122,53,115,95,29,204,247,78,17,120,102,82,69,112,151,78,182,228,102,69,
192,21,159,219,155,42,26,175,221,161,225,136,175,219,115,121,151,11,83,142,158,182,206,236,
79,188,192,72,198,57,53,250,169,187,77,116,113,166,50,111,165,225,22,25,166,54,77,129,
19,194,179,186,138,41,77,181,166,58,94,4,205,221,111,156,121,247,227,69,97,194,1,5,
166,94,38,177,125,86,247,188,181,92,117,182,164,206,5,112,202,26,123,111,113,117,231,159,
117,78,113,164,135,179,168,43,138,79,159,152,48,21,184,247,215,42,115,50,193,40,243,82,
175,95,236,139,209,167,98,154,115,202,217,242,130,100,144,209,14,161,208,86,230,95,79,0,
66,74,212,132,63,97,12,22,122,176,170,33,175,24,145,166,18,144,166,202,63,86,64,214,
58,62,212,46,230,1,188,136,86,89,144,184,34,83,149,2,81,255,194,78,58,29,86,150,
155,216,225,10,181,185,85,169,221,68,217,208,123,31,37,96,183,231,72,164,247,118,19,124,
230,49,61,24,145,208,93,237,51,162,20,93,23,243,160,205,223,252,167,78,240,65,134,10,
114,157,0,84,148,183,15,248,213,233,203,116,24,144,119,164,156,4,120,171,28,165,107,27,
51,169,98,145,169,175,99,103,85,174,18,116,213,131,245,225,211,195,223,110,59,128,241,125,
71,211,192,141,220,157,229,171,202,52,61,68,194,109,46,23,135,166,68,122,11,200,247,101,
226,15,108,250,248,49,23,227,108,225,98,220,124,14,141,111,239,43,221,186,250,205,237,92,
251,126,117,154,97,48,85,84,68,188,235,128,47,156,112,173,6,211,81,165,152,121,220,18,
101,76,208,92,71,180,70,48,238,165,223,121,140,149,206,132,80,30,167,166,147,216,148,37,
184,182,120,199,162,161,207,94,228,194,219,31,125,237,143,132,167,165,148,185,195,245,140,178,
154,72,119,252,15,129,89,52,245,243,209,196,190,25,91,191,254,104,54,125,206,88,173,207,
72,33,22,27,113,196,176,44,216,148,70,65,240,6,74,150,169,103,229,23,102,52,180,150,
15,173,202,186,125,114,179,81,120,63,181,221,113,255,126,180,73,251,44,67,220,40,239,38,
236,47,210,61,165,218,67,222,242,193,140,215,29,27,69,105,124,203,243,174,194,192,169,156,
40,54,222,217,95,128,58,196,138,88,25,159,182,150,252,243,9,89,111,97,116,80,76,139,
126,153,90,15,114,173,158,32,106,232,118,32,87,46,47,68,107,157,91,64,44,88,247,246,
12,205,34,139,58,221,187,31,34,205,67,172,97,98,97,41,187,197,73,246,122,62,21,226,
246,153,69,12,156,136,27,26,181,182,91,237,47,57,8,210,184,219,59,43,228,83,46,103,
127,219,169,59,173,240,119,106,6,55,217,105,223,8,224,152,127,129,64,48,34,142,203,18,
168,17,248,173,38,126,63,143,215,53,195,29,201,124,22,234,88,214,219,161,8,105,183,172,
80,54,188,90,250,23,98,37,93,195,59,220,153,67,51,187,119,234,189,66,10,173,252,121,
226,64,217,179,91,118,228,90,51,165,141,182,201,10,201,15,28,178,128,93,195,183,248,252,
238,232,250,38,80,151,17,201,245,215,93,251,122,190,106,221,30,169,144,104,31,236,186,126,
205,35,50,12,100,250,188,78,136,77,148,193,39,168,238,196,110,28,224,5,97,178,198,15,
134,195,65,0,236,207,246,137,30,11,102,141,159,21,73,184,142,36,126,190,27,12,172,247,
207,157,162,48,159,237,195,185,231,41,22,177,116,216,234,33,231,45,186,214,194,60,183,65,
176,66,141,74,42,51,53,153,229,236,241,218,127,177,7,164,203,123,74,112,26,189,176,246,
55,91,134,29,248,118,247,215,182,127,19,208,168,80,37,89,33,55,203,117,30,168,169,36,
71,156,68,159,116,66,204,122,210,118,222,216,163,249,43,16,37,254,124,172,95,156,70,160,
114,167,32,27,6,94,209,166,118,191,119,0,228,7,222,56,232,117,184,39,163,164,98,34,
153,227,51,26,11,130,11,127,64,219,217,86,174,167,169,218,9,147,112,137,198,96,228,47,
136,147,225,107,5,186,47,150,6,71,132,235,196,79,117,201,192,108,93,106,22,5,146,87,
112,74,32,92,122,171,204,246,172,152,74,69,159,35,93,127,29,219,251,190,63,44,101,243,
89,65,64,28,194,120,189,30,51,56,249,109,99,25,145,156,188,74,67,122,157,127,34,136,
137,249,146,81,235,98,138,154,250,42,16,49,150,253,237,162,53,251,175,213,184,225,229,35,
32,255,251,53,141,207,164,216,152,225,210,196,54,113,24,105,36,61,165,131,241,47,11,144,
132,216,225,39,72,243,95,132,214,46,179,192,134,218,61,184,59,215,92,108,184,131,107,104,
24,71,27,214,196,114,86,178,188,46,145,211,115,43,6,212,135,105,36,146,87,97,237,176,
160,219,26,34,223,67,186,144,176,172,0,75,205,180,216,151,132,138,96,23,40,102,45,154,
219,124,188,153,23,20,162,139,205,143,136,145,184,191,188,102,239,119,68,18,84,233,16,40,
186,140,106,5,150,55,210,170,123,200,120,118,163,40,2,15,248,231,252,195,84,108,94,22,
101,72,200,177,119,180,21,210,113,127,233,187,124,110,183,173,229,107,3,170,140,246,27,27,
51,41,198,157,79,184,35,252,127,149,200,192,8,77,110,219,223,77,59,228,22,38,211,164,
205,148,214,239,69,137,151,162,24,215,153,247,119,91,95,86,191,179,28,180,174,219,151,220,
204,6,84,118,177,109,96,65,243,227,18,92,125,5,6,123,150,179,157,4,55,97,203,192,
133,242,200,209,168,14,101,165,188,218,119,152,144,10,18,196,92,133,210,134,188,231,90,74,
60,156,15,99,30,45,71,231,81,185,131,96,47,157,121,177,31,114,120,242,163,41,223,136,
110,150,115,13,79,148,85,55,187,96,3,79,182,255,184,125,106,162,241,91,148,38,213,175,
53,175,101,253,135,157,59,240,20,171,87,122,99,114,47,159,188,101,105,206,92,139,124,154,
5,146,171,190,108,206,152,182,153,212,169,228,100,189,143,203,179,118,69,139,137,229,131,18,
137,81,228,55,84,147,237,142,245,141,29,109,122,79,197,43,51,153,77,5,48,89,50,214,
22,56,189,110,178,15,108,118,168,131,67,224,57,128,16,183,6,6,81,0,24,234,149,21,
187,111,220,122,104,1,208,106,56,10,248,46,55,40,18,137,248,199,182,200,246,181,184,26,
119,243,59,21,214,241,142,205,97,145,80,94,27,233,127,163,201,196,159,142,132,61,60,200,
151,199,1,26,76,116,27,201,231,211,32,74,223,23,33,162,117,170,21,43,77,124,211,102,
95,187,204,59,46,181,249,93,92,40,193,53,143,239,157,29,130,144,5,24,113,88,202,106,
107,236,199,139,124,51,178,70,94,212,66,81,23,114,131,86,195,12,154,222,158,225,37,177,
196,51,244,247,64,129,120,176,90,183,239,147,49,130,105,118,160,107,23,238,254,169,214,245,
56,95,103,174,135,170,113,145,252,122,67,222,254,130,123,131,26,15,144,173,120,220,98,132,
113,70,210,231,131,160,248,50,101,15,58,82,203,158,159,64,207,218,12,55,213,197,139,207,
125,194,209,77,49,66,10,133,143,5,75,52,174,4,131,145,103,20,146,62,20,108,33,202,
229,152,232,134,76,23,255,84,24,183,90,196,239,49,254,7,116,100,153,241,99,220,167,116,
144,81,81,194,166,66,161,190,255,240,171,160,137,95,188,63,200,212,112,250,255,221,46,97,
28,97,163,129,124,22,51,194,134,25,21,137,57,47,212,56,57,90,98,104,160,112,59,13,
197,249,190,255,221,157,89,191,19,48,124,179,226,4,189,87,162,217,33,94,239,210,100,22,
38,249,215,124,115,6,15,40,169,37,88,146,210,182,11,217,59,158,155,55,12,44,198,82,
55,234,150,139,188,218,3,137,92,151,183,214,116,220,9,110,190,39,142,115,236,0,71,136,
248,221,36,171,242,252,51,150,203,98,21,53,197,224,203,247,177,113,84,89,134,118,177,125,
28,251,193,8,87,101,141,62,221,10,149,229,86,83,154,74,158,157,221,64,141,140,238,249,
120,65,9,212,103,35,35,33,118,66,117,77,71,55,168,6,77,195,219,33,156,226,125,178,
203,202,113,163,40,69,161,106,226,251,113,165,227,81,85,68,141,52,120,144,35,48,211,90,
24,184,100,255,226,11,72,28,185,104,233,140,80,114,176,86,209,126,80,144,214,65,225,241,
129,113,92,179,164,17,100,249,102,0,136,235,51,106,178,32,188,80,37,197,152,160,108,185,
203,27,204,98,99,61,203,88,98,141,55,55,154,183,209,123,111,18,236,123,82,36,225,103,
18,217,164,159,122,168,145,75,126,114,251,243,4,99,68,188,82,18,150,39,153,252,72,53,
219,193,125,36,216,254,62,202,159,72,94,245,6,153,179,195,174,111,175,63,85,89,221,140,
123,67,178,53,36,116,120,180,34,127,63,96,31,30,75,3,14,189,247,149,224,9,57,223,
162,211,225,168,244,141,143,81,174,51,118,102,61,239,85,232,163,61,80,106,86,111,21,5,
153,87,132,54,202,116,136,19,43,45,25,237,93,123,147,92,44,194,41,88,239,124,201,213,
101,198,215,99,194,130,10,234,24,196,16,162,131,200,230,82,192,94,226,157,172,201,202,130,
193,219,193,85,253,96,182,220,136,37,95,127,165,32,54,84,20,77,185,116,189,164,121,84,
228,200,15,179,15,242,20,37,113,167,150,31,45,45,223,213,33,238,113,133,128,117,65,231,
76,212,86,43,113,252,10,66,221,163,32,128,229,119,58,95,132,69,150,113,254,48,6,144,
5,125,56,144,81,226,192,237,154,74,214,211,111,152,235,174,21,14,239,17,192,141,147,119,
9,136,224,214,8,178,19,245,161,232,121,244,3,196,220,13,41,189,17,250,71,255,27,232,
65,92,160,51,165,187,142,38,249,27,184,94,239,237,133,180,29,215,226,193,236,55,66,107,
165,93,135,9,214,243,80,162,159,78,140,195,102,135,52,108,84,80,139,179,138,50,225,68,
248,92,80,13,1,77,148,215,179,196,101,208,38,39,244,236,219,159,96,194,68,254,103,251,
227,163,58,88,15,130,172,133,147,72,81,202,126,159,153,97,135,25,238,155,191,143,103,255,
186,96,122,83,63,178,202,251,233,140,59,93,71,235,87,161,221,46,45,57,211,41,57,169,
157,214,175,214,202,188,116,21,238,199,61,70,221,120,1,243,5,186,100,149,217,169,246,165,
226,215,175,2,91,158,109,170,162,206,226,206,182,173,156,82,169,170,105,42,124,57,134,92,
131,13,3,247,177,49,86,171,50,68,17,37,123,80,32,164,28,198,140,103,171,220,28,225,
9,191,234,150,213,184,29,115,160,50,218,90,200,130,146,252,182,190,124,248,255,61,96,62,
231,183,21,246,143,127,225,39,94,61,92,67,60,216,90,108,211,162,26,47,105,254,244,132,
207,30,15,71,22,16,169,138,150,48,51,124,171,112,165,245,239,21,119,53,208,110,31,25,
142,63,192,24,222,103,97,107,228,105,45,130,207,80,124,4,134,182,109,170,160,95,251,72,
53,81,248,19,92,181,73,148,27,146,183,224,23,93,216,233,81,116,30,182,38,28,100,253,
156,110,192,151,30,171,44,134,233,190,205,159,116,69,20,203,236,56,115,112,23,160,128,116,
80,63,178,190,44,42,81,101,8,20,80,234,55,154,19,89,247,134,87,155,9,68,187,121,
182,27,120,223,159,207,77,25,7,153,106,196,194,0,42,140,10,85,6,90,89,162,72,6,
156,119,251,56,213,113,109,83,233,165,35,38,192,242,44,165,79,47,89,208,112,175,171,195,
72,206,179,214,155,16,132,11,28,22,235,188,240,178,31,58,28,197,120,102,110,38,193,42,
42,28,68,44,89,224,146,193,227,201,247,36,245,227,201,162,69,76,141,37,55,216,176,247,
28,169,178,67,138,20,153,8,186,151,195,176,38,228,101,143,5,32,137,57,11,156,133,25,
139,85,146,226,191,235,105,17,217,9,173,143,16,71,155,22,251,185,177,169,2,104,155,91,
72,22,73,206,87,171,79,132,186,45,45,196,16,198,10,96,158,211,236,57,166,102,208,76,
128,207,188,31,116,204,225,212,144,61,62,92,142,77,211,137,226,179,184,234,96,1,24,247,
223,106,201,152,236,204,59,234,190,94,224,204,230,166,7,28,141,193,103,37,40,127,187,191,
55,215,206,85,253,218,215,251,7,38,233,140,64,113,240,109,210,187,11,106,252,211,201,47,
39,246,65,199,122,39,11,146,185,128,69,135,99,222,153,155,149,208,161,34,81,159,94,192,
43,107,59,119,119,232,152,213,113,140,221,153,206,64,17,60,210,202,118,31,55,145,184,145,
21,243,39,109,162,107,181,73,204,115,81,175,142,58,43,215,113,254,185,121,199,160,40,56,
219,219,129,55,184,27,98,115,96,167,77,230,145,206,51,194,48,5,224,194,72,123,69,233,
63,197,236,61,102,209,255,134,134,139,16,17,76,184,146,241,138,48,246,26,153,36,60,135,
166,11,200,132,138,152,186,47,114,230,237,77,76,51,124,75,51,55,228,239,48,218,202,141,
37,24,30,180,127,154,246,130,204,15,132,248,80,156,92,239,199,133,186,33,22,36,184,98,
209,69,165,95,33,216,34,222,12,109,46,99,81,24,253,226,205,89,159,128,62,211,132,246,
84,9,144,51,199,230,39,213,234,117,98,214,127,10,93,207,240,79,29,174,197,206,194,177,
229,96,229,255,123,145,200,34,82,128,34,240,24,79,83,217,29,189,88,241,133,56,0,155,
163,251,100,209,114,185,140,233,140,169,169,246,40,102,230,118,217,110,95,73,16,157,102,12,
225,141,171,248,5,61,219,17,14,2,48,204,149,26,100,200,93,169,253,143,68,201,234,130,
29,249,253,50,99,102,126,150,35,115,73,54,111,87,171,30,43,53,208,52,129,45,123,124,
178,44,216,100,176,44,122,94,163,239,139,226,166,85,198,53,143,1,249,152,125,78,78,96,
131,54,233,19,174,114,34,71,108,50,4,45,246,215,75,3,171,145,138,65,160,117,156,26,
136,220,145,112,64,201,18,46,217,253,119,3,254,191,47,188,83,99,220,62,201,229,119,69,
10,28,22,3,225,12,166,179,148,161,182,109,130,140,157,166,17,109,175,118,34,117,0,184,
85,154,143,160,70,73,52,128,65,159,213,65,118,248,202,134,113,229,28,57,212,15,133,102,
23,0,24,149,9,166,175,116,219,123,1,25,8,129,49,205,195,167,37,81,192,103,214,36,
160,226,126,182,177,96,108,94,24,27,70,67,127,151,56,59,93,44,172,161,19,162,24,77,
206,140,141,10,45,68,208,105,161,216,179,46,209,131,74,83,34,225,39,128,73,59,66,99,
24,194,107,180,245,60,75,165,113,132,151,201,102,202,250,71,47,121,62,7,182,184,82,60,
77,122,75,158,98,164,146,190,0,240,216,66,164,42,73,110,252,175,216,208,35,236,156,129,
127,120,128,38,54,208,127,230,86,80,69,158,211,255,171,183,205,16,119,140,245,62,99,80,
1,222,7,179,16,3,160,4,30,36,12,16,119,216,195,84,169,159,8,253,180,33,98,53,
35,129,43,121,199,83,7,28,113,95,30,3,183,216,232,174,174,216,144,66,225,203,248,123,
196,168,191,190,127,154,16,74,99,231,238,72,136,38,172,113,199,102,84,3,162,112,191,69,
75,89,40,74,164,42,222,121,150,247,27,82,135,39,29,80,56,220,97,249,89,105,147,209,
78,7,177,88,76,9,255,40,26,207,14,29,173,146,211,63,64,235,124,183,133,59,73,50,
116,187,64,165,113,184,49,192,49,241,139,240,72,248,113,37,232,89,16,179,210,249,152,240,
28,151,65,177,37,45,181,9,183,97,205,233,205,176,25,60,156,133,14,127,212,218,47,42,
26,202,63,35,157,52,155,114,67,143,94,11,139,217,89,61,18,228,34,250,4,150,136,187,
89,29,82,69,203,2,215,123,26,98,47,177,5,36,17,23,220,107,236,38,147,65,118,117,
101,18,249,78,9,238,103,163,78,80,52,68,185,21,114,183,208,192,162,67,182,179,128,117,
98,61,37,246,127,114,29,207,11,132,88,228,118,237,18,143,120,193,46,200,107,49,168,108,
0,77,193,107,7,184,110,105,34,61,92,140,218,17,42,226,136,188,62,126,197,150,237,81,
197,224,217,229,238,178,203,205,39,214,66,69,225,193,207,148,155,50,145,109,102,131,131,200,
149,232,68,153,209,61,12,146,176,45,181,234,131,75,81,59,57,152,229,81,76,113,96,231,
248,235,167,173,150,231,211,34,255,241,141,138,90,120,142,140,149,60,40,110,135,244,120,227,
252,168,192,69,172,66,25,238,20,37,80,74,234,218,239,35,228,131,91,223,179,179,202,245,
119,7,61,20,107,225,89,148,150,86,215,211,240,186,33,251,135,181,233,154,32,113,133,227,
24,52,2,205,85,111,124,224,165,138,152,239,99,120,122,132,222,109,20,134,183,77,40,168,
169,13,196,80,61,193,241,90,236,236,253,237,27,48,115,74,117,110,189,199,150,65,103,146,
41,137,231,33,81,148,148,55,198,93,101,187,179,185,93,164,24,88,64,114,184,51,82,57,
81,51,110,10,56,82,160,74,40,181,74,139,52,135,43,40,236,39,230,193,177,220,79,96,
29,126,21,2,5,234,5,197,134,64,49,62,32,141,56,23,41,93,113,84,7,159,137,255,
210,103,160,191,255,203,64,234,199,198,224,92,189,236,241,107,55,59,234,128,229,82,243,199,
37,81,159,20,136,169,63,146,233,80,178,241,219,251,37,216,223,202,227,113,159,112,189,91,
38,143,116,120,196,32,26,204,89,149,7,246,57,216,163,247,173,111,42,123,0,217,210,159,
99,63,33,136,159,34,215,19,98,2,141,160,246,8,184,226,93,47,66,111,58,155,138,37,
52,31,167,231,50,91,117,138,220,73,159,164,103,78,239,115,254,208,121,53,172,20,54,34,
220,32,44,182,243,59,29,38,153,218,195,23,224,148,33,236,120,173,117,78,156,125,186,37,
91,245,64,232,77,241,8,23,42,120,147,232,232,210,227,184,130,57,201,113,35,196,95,55,
132,127,11,4,147,254,13,244,17,104,135,239,93,175,157,22,213,184,15,201,67,34,44,181,
191,208,142,141,208,30,12,188,191,39,58,10,173,9,146,10,195,113,121,39,7,156,113,4,
176,203,205,40,214,188,150,191,145,247,63,219,132,225,208,48,86,196,40,255,46,232,138,150,
119,189,134,124,32,85,129,71,155,79,236,143,203,220,243,14,20,101,97,10,177,223,188,90,
113,202,34,188,11,253,34,78,60,1,196,133,60,204,142,188,151,196,8,132,214,136,214,52,
121,77,164,124,179,133,205,136,6,67,196,100,200,221,139,128,132,1,229,195,227,89,1,187,
81,35,70,61,230,188,50,11,42,219,98,222,126,129,37,80,200,5,113,134,62,7,101,182,
223,98,66,198,158,108,48,99,25,54,220,114,220,222,21,80,145,52,103,27,72,247,248,167,
103,48,151,148,231,63,76,48,141,181,212,24,238,67,28,191,45,124,30,231,216,87,113,118,
189,5,229,136,85,222,57,41,197,57,174,245,41,66,241,35,226,205,193,15,71,253,67,228,
202,93,20,90,194,43,150,173,136,136,39,11,53,157,238,84,129,131,125,
};
// The value's UTF-8 bytes in the low bytes and its length in the top byte.
typedef struct { u64 key, val; } Entry;
typedef struct { u8 name[32]; u64 val; u32 len; u32 pad; } Long;
static u8 input[INPUT_CAP + PAD] __attribute__((aligned(16)));
static u8 output[OUTPUT_CAP + PAD] __attribute__((aligned(16)));
static Entry fast[(1 << FAST_BITS) + FAST_TAIL];
static Entry leg[(1 << LEG_BITS) + LEG_TAIL];
static Long longs[LONG_COUNT] __attribute__((aligned(16)));
static u16 long_slots[1 << LONG_BITS];
// Longest legacy name starting with these two bytes (hashed), or 0.
static u8 leg_max[4096];
static u32 pos[WINDOW + 16];
static u32 ready;
// Windows-1252 remapping for references to 0x80-0x9F.
static const u16 c1[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,
};
static const u32 utf8_marks[5] = {0, 0, 0x80C0, 0x8080E0, 0x808080F0};
// Byte j of the 32 loaded at `len_mask + 32 - n` is 0xFF when j < n: 32 bytes of 0xFF, then 32 of 0.
static u8 len_mask[64] __attribute__((aligned(16)));
#define ONES 0x0101010101010101ull
#define HIGH 0x8080808080808080ull
#define LIKELY(x) __builtin_expect(!!(x), 1)
#define UNLIKELY(x) __builtin_expect(!!(x), 0)
static inline u64 ld64(const u8 *p) { u64 x; __builtin_memcpy(&x, p, 8); return x; }
static inline void st64(u8 *p, u64 x) { __builtin_memcpy(p, &x, 8); }
static inline void st32(u8 *p, u32 x) { __builtin_memcpy(p, &x, 4); }
static inline v128_t ld(const u8 *p) { return wasm_v128_load(p); }
static inline void st(u8 *p, v128_t v) { wasm_v128_store(p, v); }
static inline u32 amps(v128_t v) { return wasm_i8x16_bitmask(wasm_i8x16_eq(v, wasm_i8x16_splat('&'))); }
static inline u32 leg_slot(u64 w) { return (((u32)w & 0xFFFF) * 0x9E3779B1u) >> 20; }
static inline u64 rotl(u64 x, u32 r) { return x << r | x >> (64 - r); }
static inline u32 long_hash(u64 head, u64 tail, u32 n) {
return (u32)((((head ^ rotl(tail, 29)) + n) * LONG_MUL) >> (64 - LONG_BITS));
}
// Lay the bits of a code point out as four UTF-8 bytes, then drop the unused leading ones.
__attribute__((always_inline)) static inline u32 utf8(u32 v, u32 *len) {
u32 n = 1 + (v > 0x7F) + (v > 0x7FF) + (v > 0xFFFF);
u32 bits = v >> 18 | (v >> 12 & 0x3F) << 8 | (v >> 6 & 0x3F) << 16 | (v & 0x3F) << 24;
*len = n;
return n == 1 ? v : bits >> (32 - 8 * n) | utf8_marks[n];
}
// The entity list is stored packed and read once, on the first call. Entities are ordered
// by code point, so a value is a small step from the one before, and each name is coded
// with an adaptive binary range coder (the LZMA one) whose model mixes four contexts:
// the previous one, two and three characters, and a match model that predicts the
// character that followed the last place the previous two were seen. pack.py, printed
// at the end of this file, is the matching packer.
//
// A model entry is a 16-bit probability (stored XOR 0x8000, so zeroed memory means one
// half) and a count of how often it was used. The model lives in the output buffer, which
// is free until the first reference is decoded.
#define MODEL ((u32 *)output)
#define SMALL __attribute__((minsize, noinline))
#define K (1u << 20)
SMALL static u32 utf8_once(u32 v, u32 *len) { return utf8(v, len); }
// Step toward the bit just seen, as a 16-bit fraction: 2 / (2n + 3) after n uses.
static const u16 rate[6] = {43690, 26214, 18724, 14563, 11915, 10082};
static const u8 *rc_in;
static u8 hist[HIST_SIZE];
static u16 last[4096];
static u32 rc_range, rc_code;
SMALL static u32 sym(const u32 *ctx, u32 nctx, u32 nbits) {
u32 node = 1, top = 1u << nbits;
do {
u32 *slot[4], num = 0, den = 0;
for (u32 k = 0; k < nctx; k++) {
u32 *s = slot[k] = &MODEL[((ctx[k] + node * 0x2545F491u) * 0x9E3779B1u) >> (32 - MODEL_BITS)];
int32_t p = (int32_t)(*s >> 16 ^ 0x8000), a = p - 0x8000;
// Weigh a context by its order, how often it was seen and how sure it is.
u32 w = ((*s & 0xFFFF) * (1 + ((u32)(a < 0 ? -a : a) >> 12))) << k;
num += (u32)p * w;
den += w;
}
u32 p = (den ? num / den : 0x8000) >> 4;
if (!p) p = 1;
u32 bound = (rc_range >> 12) * p, bit = rc_code < bound;
if (bit) rc_range = bound;
else rc_code -= bound, rc_range -= bound;
while (rc_range < 1u << 24) {
rc_range <<= 8;
rc_code = rc_code << 8 | *rc_in++;
}
for (u32 k = 0; k < nctx; k++) {
int32_t q = (int32_t)(*slot[k] >> 16 ^ 0x8000), n = (int32_t)(*slot[k] & 0xFFFF);
q += ((((int32_t)bit << 16) - q) * rate[n]) >> 16;
if (n < MODEL_LIMIT) n++;
*slot[k] = ((u32)q ^ 0x8000) << 16 | (u32)n;
}
node = node * 2 + bit;
} while (node < top);
return node - top;
}
SMALL static void init(void) {
__builtin_memset(fast, 255, sizeof fast);
__builtin_memset(leg, 255, sizeof leg);
__builtin_memset(len_mask, 255, 32);
rc_in = packed + 4;
rc_range = ~0u;
rc_code = (u32)packed[0] << 24 | (u32)packed[1] << 16 | (u32)packed[2] << 8 | packed[3];
u32 cp = 0, nl = 0, hn = 1, ctx[4];
for (u32 r = 0; r < ENTITY_COUNT; r++) {
// Step from the previous code point: its bit length, then the bits below the top one.
ctx[0] = K;
u32 nb = sym(ctx, 1, 5), d = nb;
if (nb > 1) {
ctx[0] = 2 * K + nb;
d = (1u << (nb - 1)) + sym(ctx, 1, nb - 1);
}
cp += d;
u32 vn, vn2 = 0;
u64 val = utf8_once(cp, &vn);
ctx[0] = 3 * K + !d;
if (sym(ctx, 1, 1)) {
ctx[0] = 4 * K;
val |= (u64)utf8_once(sym(ctx, 1, 16), &vn2) << (8 * vn);
}
val |= (u64)(vn + vn2) << 56;
ctx[0] = 5 * K + (cp < 256);
u32 legacy = sym(ctx, 1, 1);
// Names use a 6-bit alphabet: 0 ends the name, then digits, capitals, small letters.
u8 name[40];
__builtin_memset(name, 0, 40);
u32 n = 0, h = 0, c, mp = 0, ml = 0;
for (;;) {
ctx[0] = 8 * K + (h & 63);
ctx[1] = 9 * K + (h & 4095);
ctx[2] = 13 * K + (ml ? hist[mp] : 0) * 16 + (ml < 3 ? ml : 3);
ctx[3] = 10 * K + (h & 0x3FFFF);
c = sym(ctx, 4, 6);
if (ml && hist[mp] == c) ml++, mp++;
else ml = 0;
hist[hn++] = (u8)c;
if (!c) break;
name[n++] = (u8)(c + (c < 11 ? '0' - 1 : c < 37 ? 'A' - 11 : 'a' - 37));
h = h << 6 | c;
if (n >= 2) {
u16 *l = &last[h & 4095];
if (!ml && *l) mp = *l, ml = 1;
*l = (u16)hn;
}
}
if (n <= 7) {
u64 key = ld64(name) | (u64)';' << (8 * n);
Entry *e = &fast[(key * FAST_MUL) >> (64 - FAST_BITS)];
while (e->key != EMPTY) e++;
e->key = key;
e->val = val;
if (legacy) {
key = ld64(name) | (u64)n << 56;
e = &leg[(key * LEG_MUL) >> (64 - LEG_BITS)];
while (e->key != EMPTY) e++;
e->key = key;
e->val = val;
u32 s = leg_slot(key); // only the first two bytes matter
if (leg_max[s] < n) leg_max[s] = n;
}
} else {
Long *l = &longs[nl++];
__builtin_memcpy(l->name, name, 32);
l->val = val;
l->len = n;
u32 hh = long_hash(ld64(name), ld64(name + n - 8), n);
while (long_slots[hh]) hh = (hh + 1) & ((1 << LONG_BITS) - 1);
long_slots[hh] = nl;
}
}
ready = 1;
}
__attribute__((export_name("input_ptr"))) u32 input_ptr(void) { return (u32)(uintptr_t)input; }
__attribute__((export_name("input_utf8_cap"))) u32 input_utf8_cap(void) { return INPUT_CAP; }
__attribute__((export_name("output_ptr"))) u32 output_ptr(void) { return (u32)(uintptr_t)output; }
__attribute__((export_name("output_utf8_cap"))) u32 output_utf8_cap(void) { return OUTPUT_CAP; }
__attribute__((export_name("render"))) u64 render(u32 n) {
if (UNLIKELY(!ready)) init();
u32 size = n < INPUT_CAP ? n : INPUT_CAP;
const u8 *src = input;
u8 *dst = output;
const v128_t zero = wasm_i8x16_splat(0);
st(input + size, zero);
st(input + size + 16, zero);
st(input + size + 32, zero);
st(input + size + 48, zero);
// Stage 1 lists the position of every `&` in a window; stage 2 copies the text between
// references and decodes each one. Knowing the next position before the current
// reference is decoded keeps the references independent of each other.
u32 e = 0, o = 0, base = 0;
while (base < size) {
u32 lim = size - base > WINDOW ? base + WINDOW : size;
u32 *out = pos;
do {
const v128_t amp = wasm_i8x16_splat('&');
v128_t ea = wasm_i8x16_eq(ld(src + base), amp), eb = wasm_i8x16_eq(ld(src + base + 16), amp);
v128_t ec = wasm_i8x16_eq(ld(src + base + 32), amp), ed = wasm_i8x16_eq(ld(src + base + 48), amp);
{
u64 mm = (u64)wasm_i8x16_bitmask(ea) | (u64)wasm_i8x16_bitmask(eb) << 16 |
(u64)wasm_i8x16_bitmask(ec) << 32 | (u64)wasm_i8x16_bitmask(ed) << 48;
u32 cnt = __builtin_popcountll(mm);
// Entries past cnt are garbage and are overwritten or ignored.
out[0] = base + __builtin_ctzll(mm); mm &= mm - 1;
out[1] = base + __builtin_ctzll(mm); mm &= mm - 1;
out[2] = base + __builtin_ctzll(mm); mm &= mm - 1;
out[3] = base + __builtin_ctzll(mm); mm &= mm - 1;
if (UNLIKELY(cnt > 4)) {
out[4] = base + __builtin_ctzll(mm); mm &= mm - 1;
out[5] = base + __builtin_ctzll(mm); mm &= mm - 1;
out[6] = base + __builtin_ctzll(mm); mm &= mm - 1;
out[7] = base + __builtin_ctzll(mm); mm &= mm - 1;
for (u32 k = 8; UNLIKELY(mm); k++) {
out[k] = base + __builtin_ctzll(mm);
mm &= mm - 1;
}
}
out += cnt;
}
base += 64;
} while (base < lim);
for (const u32 *q = pos; q < out; q++) {
u32 i = *q;
// Copy the text since the last reference; src[i] is `&` and i < size.
{
u32 len = i - e;
st(dst + o, ld(src + e));
st(dst + o + 16, ld(src + e + 16));
if (len > 32) {
u32 j = 32;
do {
st(dst + o + j, ld(src + e + j));
j += 16;
} while (j < len);
}
o += len;
}
u64 w = ld64(src + i + 1);
if ((u8)w == '#') {
// Decimal and hexadecimal share one branch-free path: classify 8 bytes, take
// the digits before the first other byte, and fold them pairwise.
u32 hex = (((u32)w >> 8 & 0xFF) | 0x20) == 'x';
const u8 *p = src + i + 2 + hex;
u64 d = ld64(p);
u64 t = d ^ 0x3030303030303030ull;
u64 digit = ~(((t & ~HIGH) + 0x7676767676767676ull) | t) & HIGH;
u64 y = d | 0x2020202020202020ull, ty = y & ~HIGH;
u64 letter = (ty + ONES * (0x80 - 'a')) & ~(ty + ONES * (0x7F - 'f')) & ~y & HIGH;
u64 stop = ~(digit | (hex ? letter : 0)) & HIGH;
u32 v, end;
if (LIKELY(stop)) {
u32 nb = __builtin_ctzll(stop) & 0x38;
if (UNLIKELY(!nb)) goto bare;
u64 x = ((d & 0x0F0F0F0F0F0F0F0Full) + 9 * (letter >> 7)) << (64 - nb);
x = (x * (hex ? 16 : 10) + (x >> 8)) & 0x00FF00FF00FF00FFull;
x = (x * (hex ? 256 : 100) + (x >> 16)) & 0x0000FFFF0000FFFFull;
v = (u32)(x * (hex ? 65536 : 10000) + (x >> 32));
end = (u32)(p - src) + (nb >> 3);
} else {
// Eight or more digits: saturate past U+10FFFF.
u32 c, base = hex ? 16 : 10;
v = 0;
for (;;) {
c = *p - '0';
if (c > 9) c = ((*p | 0x20) - 'a') + 10, c = c < 10 ? 16 : c;
if (c >= base) break;
v = v * base + c;
if (v > 0x10FFFF) v = 0x110000;
p++;
}
end = (u32)(p - src);
}
i = end + (src[end] == ';');
if (UNLIKELY(v - 0x80 < 0x20)) v = c1[v - 0x80];
else if (UNLIKELY(v == 0 || v - 0xD800 < 0x800 || v > 0x10FFFF)) v = 0xFFFD;
u32 len, word = utf8(v, &len);
st32(dst + o, word);
o += len;
goto next;
}
{
u64 t = w ^ (ONES * ';');
u64 z = (t - ONES) & ~t & HIGH;
if (LIKELY(z)) {
// Bit index of the `;` byte; the key is the name and its `;`.
u32 kb = __builtin_ctzll(z) & 0x38;
u64 key = w & (((u64)2 << (kb + 7)) - 1);
const Entry *e = &fast[(key * FAST_MUL) >> (64 - FAST_BITS)];
for (;;) {
u64 k = e->key;
if (LIKELY(k == key)) {
u64 val = e->val;
st64(dst + o, val);
o += (u32)(val >> 56);
i += 2 + (kb >> 3);
goto next;
}
if (k == EMPTY) break;
e++;
}
} else {
// No `;` in 8 bytes: a name of 8 to 31 bytes needs its `;` in the next 24.
v128_t s0 = ld(src + i + 1), s1 = ld(src + i + 17);
const v128_t semi = wasm_i8x16_splat(';');
u32 sm = wasm_i8x16_bitmask(wasm_i8x16_eq(s0, semi)) | wasm_i8x16_bitmask(wasm_i8x16_eq(s1, semi)) << 16;
if (sm) {
u32 len = __builtin_ctz(sm);
u32 h = long_hash(w, ld64(src + i + 1 + len - 8), len);
v128_t m0 = ld(len_mask + 32 - len), m1 = ld(len_mask + 48 - len);
for (u32 s; (s = long_slots[h]) != 0; h = (h + 1) & ((1 << LONG_BITS) - 1)) {
const Long *l = &longs[s - 1];
v128_t diff = wasm_v128_or(
wasm_v128_xor(wasm_v128_and(s0, m0), ld(l->name)),
wasm_v128_xor(wasm_v128_and(s1, m1), ld(l->name + 16)));
if (l->len == len && !wasm_v128_any_true(diff)) {
st64(dst + o, l->val);
o += (u32)(l->val >> 56);
i += 2 + len;
goto next;
}
}
}
}
// Without `;`, the longest legacy name that is a prefix.
for (u32 k = leg_max[leg_slot(w)]; k >= 2; k--) {
// The length is part of the key, so a NUL after a shorter name cannot match.
u64 key = (w & (((u64)1 << (8 * k)) - 1)) | (u64)k << 56;
const Entry *e = &leg[(key * LEG_MUL) >> (64 - LEG_BITS)];
for (;;) {
if (e->key == key) {
st64(dst + o, e->val);
o += (u32)(e->val >> 56);
i += 1 + k;
goto next;
}
if (e->key == EMPTY) break;
e++;
}
}
}
bare:
dst[o] = '&';
o += 1;
i += 1;
next:
e = i;
}
}
// Without a reference the input is the output.
if (e == 0) return (u64)(u32)(uintptr_t)input << 32 | size;
for (u32 j = e; j < size; j += 16) st(dst + o + (j - e), ld(src + j));
o += size - e;
return (u64)(u32)(uintptr_t)output << 32 | o;
}
/* pack.py, which produced `packed`:
"""Packs the entity list for unescape-small: entities ordered by code point, coded with an
adaptive binary range coder whose contexts are the previous one, two and three name
characters and a match model. The C unpacker in unescape-small.in.c mirrors Model and Decoder exactly.
"""
import html.entities
M32 = 0xFFFFFFFF
K = 1 << 20
HASH_A, HASH_B = 0x2545F491, 0x9E3779B1
# Step toward the bit just seen, as a 16-bit fraction: 2 / (2n + 3) after n uses.
RATE = [43690, 26214, 18724, 14563, 11915, 10082]
html5 = html.entities.html5
NAMES = {k[:-1]: v for k, v in html5.items() if k.endswith(';')}
LEGACY = {k for k in html5 if not k.endswith(';')}
ALPHA = '\0' + '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
CODE = {c: i for i, c in enumerate(ALPHA)}
ORDER = sorted(NAMES, key=lambda n: ([ord(c) for c in NAMES[n]], n))
def tdiv(a, b):
"""Division truncating toward zero, as in C."""
q = abs(a) // abs(b)
return q if (a < 0) == (b < 0) else -q
class Model:
def __init__(self, bits=16, limit=6):
self.t = [0] * (1 << bits)
self.bits, self.limit = bits, limit
def slots(self, ctxs, node):
return [(((c + node * HASH_A) * HASH_B) & M32) >> (32 - self.bits) for c in ctxs]
def predict(self, slots):
"""12-bit probability that the bit is 1."""
num = den = 0
for k, s in enumerate(slots):
e = self.t[s]
p, n = (e >> 16) ^ 0x8000, e & 0xFFFF
w = (n * (1 + (abs(p - 0x8000) >> 12))) << k
num += p * w
den += w
p = num // den if den else 0x8000
return min(max(p >> 4, 1), 4095)
def update(self, slots, bit):
for s in slots:
e = self.t[s]
p, n = (e >> 16) ^ 0x8000, e & 0xFFFF
p += (((0x10000 if bit else 0) - p) * RATE[n]) >> 16
if n < self.limit:
n += 1
self.t[s] = (p ^ 0x8000) << 16 | n
class Encoder:
def __init__(self):
self.low, self.range, self.cache, self.pending, self.out = 0, M32, 0, 1, bytearray()
def shift_low(self):
if self.low < 0xFF000000 or self.low > M32:
carry = self.low >> 32
byte = self.cache
while self.pending:
self.out.append((byte + carry) & 0xFF)
byte = 0xFF
self.pending -= 1
self.cache = self.low >> 24 & 0xFF
self.pending += 1
self.low = (self.low << 8) & M32
def bit(self, p, bit):
bound = (self.range >> 12) * p
if bit:
self.range = bound
else:
self.low += bound
self.range -= bound
while self.range < 1 << 24:
self.range = (self.range << 8) & M32
self.shift_low()
def finish(self):
for _ in range(5):
self.shift_low()
assert self.out[0] == 0
return bytes(self.out[1:])
class Decoder:
def __init__(self, data):
self.data, self.pos, self.range = data + bytes(8), 4, M32
self.code = int.from_bytes(data[:4], 'big')
def bit(self, p):
bound = (self.range >> 12) * p
if self.code < bound:
self.range = bound
bit = 1
else:
self.code -= bound
self.range -= bound
bit = 0
while self.range < 1 << 24:
self.range = (self.range << 8) & M32
self.code = (self.code << 8 | self.data[self.pos]) & M32
self.pos += 1
return bit
class Coder:
"""Runs the same field sequence for packing (values given) and unpacking (values None)."""
def __init__(self, data=None, **kw):
self.m = Model(**kw)
self.enc = Encoder() if data is None else None
self.dec = Decoder(data) if data is not None else None
self.hist, self.last = [0], [0] * 4096
def sym(self, ctxs, nbits, value=None):
node = 1
for i in range(nbits - 1, -1, -1):
slots = self.m.slots(ctxs, node)
p = self.m.predict(slots)
if self.enc:
b = value >> i & 1
self.enc.bit(p, b)
else:
b = self.dec.bit(p)
self.m.update(slots, b)
node = node * 2 + b
return node - (1 << nbits)
def entity(self, cp, rec=None):
"""rec = (name, [code points], legacy) when packing. Returns the same when unpacking."""
name, cps, legacy = rec if rec else (None, None, None)
d = cps[0] - cp if rec else None
nb = self.sym([1 * K], 5, d.bit_length() if rec else None)
if nb > 1:
d = (1 << (nb - 1)) + self.sym([2 * K + nb], nb - 1, d - (1 << (nb - 1)) if rec else None)
else:
d = nb
cp += d
second = 0
if self.sym([3 * K + (d == 0)], 1, len(cps) - 1 if rec else None):
second = self.sym([4 * K], 16, cps[1] if rec else None)
leg = self.sym([5 * K + (cp < 256)], 1, int(legacy) if rec else None)
# The match model predicts the character that followed the last place the previous
# two characters were seen, and how many predictions in a row have been right.
h, out, mp, ml = 0, '', 0, 0
for i in range(64):
ctxs = [8 * K + (h & 63), 9 * K + (h & 4095),
13 * K + (self.hist[mp] if ml else 0) * 16 + min(ml, 3), 10 * K + (h & 0x3FFFF)]
c = self.sym(ctxs, 6, CODE[(name + '\0')[i]] if rec else None)
if ml and self.hist[mp] == c:
ml += 1
mp += 1
else:
ml = 0
self.hist.append(c)
if c == 0:
break
out += ALPHA[c]
h = h << 6 | c
if i >= 1:
if ml == 0 and self.last[h & 4095]:
mp, ml = self.last[h & 4095], 1
self.last[h & 4095] = len(self.hist)
return out, [cp, second] if second else [cp], bool(leg)
def records():
return [(n, [ord(c) for c in NAMES[n]], n in LEGACY) for n in ORDER]
def pack(**kw):
c = Coder(**kw)
cp = 0
for rec in records():
assert len(rec[1]) <= 2 and rec[1][0] >= cp and (len(rec[1]) == 1 or rec[1][1] < 0x10000)
c.entity(cp, rec)
cp = rec[1][0]
return c.enc.finish()
def unpack(data, count, **kw):
c = Coder(data, **kw)
cp, out = 0, []
for _ in range(count):
rec = c.entity(cp)
cp = rec[1][0]
out.append(rec)
return out
if __name__ == '__main__':
import sys
blob = pack(bits=18, limit=5)
assert unpack(blob, len(ORDER), bits=18, limit=5) == records()
print('round trip ok', len(blob))
*/