// unescape_html in Zig 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 build-exe unescape-small.zig -target wasm32-freestanding
// -mcpu=generic+simd128+bulk_memory -O ReleaseSmall -fno-entry -rdynamic -fstrip --stack 8192
// --initial-memory=3145728 --max-memory=3145728
// then: wasm-opt -O1 --enable-simd --enable-bulk-memory
const std = @import("std");
const V = @Vector(16, u8);
const INPUT_CAP: usize = 1 << 20;
// The largest growth is `≫⃒` (5 bytes) becoming 6 bytes.
const OUTPUT_CAP: usize = INPUT_CAP / 5 * 6 + 8;
const PAD = 128;
const FAST_BITS = 12;
const FAST_TAIL = 32;
const LEG_BITS = 8;
const LEG_TAIL = 16;
const LONG_BITS = 11;
const LONG_MASK = (1 << LONG_BITS) - 1;
const EMPTY: u64 = ~@as(u64, 0);
// Bytes of input per stage-1 window; a multiple of 64.
const WINDOW = 4096;
const ONES: u64 = 0x0101010101010101;
const HIGH: u64 = 0x8080808080808080;
const HIST_SIZE = 16130;
const ENTITY_COUNT = 2125;
const LONG_COUNT = 506;
const MODEL_BITS = 18;
const MODEL_LIMIT = 5;
const FAST_MUL: u64 = 0xa59d054b12f5b905;
const LEG_MUL: u64 = 0xf880d97d1854e551;
const LONG_MUL: u64 = 0xa0c2995f40498cb3;
const packed_list = [6403]u8{
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.
const Entry = extern struct { key: u64, val: u64 };
const Long = extern struct { name: [32]u8, val: u64, len: u32, pad: u32 };
var input: [INPUT_CAP + PAD]u8 align(16) = undefined;
// Zeroed, because the packed list's model is built here on the first call.
var output align(16) = [_]u8{0} ** (OUTPUT_CAP + PAD);
var fast: [(1 << FAST_BITS) + FAST_TAIL]Entry = undefined;
var leg: [(1 << LEG_BITS) + LEG_TAIL]Entry = undefined;
var longs: [LONG_COUNT]Long align(16) = std.mem.zeroes([LONG_COUNT]Long);
var long_slots = [_]u16{0} ** (1 << LONG_BITS);
// Longest legacy name starting with these two bytes (hashed), or 0.
var leg_max = [_]u8{0} ** 4096;
var pos: [WINDOW + 16]u32 = undefined;
var ready: bool = false;
// Windows-1252 remapping for references to 0x80-0x9F.
const c1 = [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,
};
const utf8_marks = [5]u32{ 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.
var len_mask align(16) = [_]u8{0} ** 64;
inline fn ld(p: [*]const u8) V {
return p[0..16].*;
}
inline fn st(p: [*]u8, v: V) void {
p[0..16].* = v;
}
inline fn ld64(p: [*]const u8) u64 {
return @as(*align(1) const u64, @ptrCast(p)).*;
}
inline fn st64(p: [*]u8, x: u64) void {
@as(*align(1) u64, @ptrCast(p)).* = x;
}
inline fn st32(p: [*]u8, x: u32) void {
@as(*align(1) u32, @ptrCast(p)).* = x;
}
inline fn eqMask(v: V, c: u8) u32 {
return @as(u16, @bitCast(v == @as(V, @splat(c))));
}
inline fn legSlot(w: u64) usize {
return ((@as(u32, @truncate(w)) & 0xFFFF) *% 0x9E3779B1) >> 20;
}
inline fn longHash(head: u64, tail: u64, n: usize) usize {
return @intCast((((head ^ std.math.rotl(u64, tail, 29)) +% n) *% LONG_MUL) >> (64 - LONG_BITS));
}
// 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.
const K: u32 = 1 << 20;
// Step toward the bit just seen, as a 16-bit fraction: 2 / (2n + 3) after n uses.
const rate = [6]u16{ 43690, 26214, 18724, 14563, 11915, 10082 };
var rc_in: [*]const u8 = &packed_list;
var rc_range: u32 = 0xFFFFFFFF;
var rc_code: u32 = 0;
var hist = [_]u8{0} ** HIST_SIZE;
var last = [_]u16{0} ** 4096;
noinline fn sym(ctx: []const u32, nbits: u32) u32 {
@branchHint(.cold);
const model: [*]u32 = @ptrCast(@alignCast(&output));
const top = @as(u32, 1) << @intCast(nbits);
var node: u32 = 1;
while (node < top) {
var slot: [4]*u32 = undefined;
var num: u32 = 0;
var den: u32 = 0;
for (ctx, 0..) |c, k| {
const s = &model[((c +% node *% 0x2545F491) *% 0x9E3779B1) >> (32 - MODEL_BITS)];
slot[k] = s;
const p = (s.* >> 16) ^ 0x8000;
const a = if (p >= 0x8000) p - 0x8000 else 0x8000 - p;
// Weigh a context by its order, how often it was seen and how sure it is.
const w = ((s.* & 0xFFFF) * (1 + (a >> 12))) << @intCast(k);
num +%= p *% w;
den +%= w;
}
var p = (if (den != 0) num / den else 0x8000) >> 4;
if (p == 0) p = 1;
const bound = (rc_range >> 12) *% p;
const bit: u32 = @intFromBool(rc_code < bound);
if (bit != 0) {
rc_range = bound;
} else {
rc_code -%= bound;
rc_range -%= bound;
}
while (rc_range < 1 << 24) {
rc_range <<= 8;
rc_code = (rc_code << 8) | rc_in[0];
rc_in += 1;
}
for (slot[0..ctx.len]) |s| {
var q: i32 = @intCast((s.* >> 16) ^ 0x8000);
var n = s.* & 0xFFFF;
q += (((@as(i32, @intCast(bit)) << 16) - q) * @as(i32, rate[n])) >> 16;
if (n < MODEL_LIMIT) n += 1;
s.* = ((@as(u32, @intCast(q)) ^ 0x8000) << 16) | n;
}
node = node * 2 + bit;
}
return node - top;
}
// A code point as UTF-8 bytes in a word, low byte first.
noinline fn utf8(v: u32, len: *u32) u32 {
@branchHint(.cold);
const n: u32 = 1 + @as(u32, @intFromBool(v > 0x7F)) + @intFromBool(v > 0x7FF) + @intFromBool(v > 0xFFFF);
const bits = (v >> 18) | (((v >> 12) & 0x3F) << 8) | (((v >> 6) & 0x3F) << 16) | ((v & 0x3F) << 24);
len.* = n;
return if (n == 1) v else (bits >> @intCast(32 - 8 * n)) | utf8_marks[n];
}
noinline fn init() void {
@branchHint(.cold);
@memset(std.mem.asBytes(&fast), 0xFF);
@memset(std.mem.asBytes(&leg), 0xFF);
@memset(len_mask[0..32], 0xFF);
rc_code = std.mem.readInt(u32, packed_list[0..4], .big);
rc_in += 4;
var cp: u32 = 0;
var nl: usize = 0;
var hn: u32 = 1;
var ctx: [4]u32 = undefined;
for (0..ENTITY_COUNT) |_| {
// Step from the previous code point: its bit length, then the bits below the top one.
ctx[0] = K;
const nb = sym(ctx[0..1], 5);
var d = nb;
if (nb > 1) {
ctx[0] = 2 * K + nb;
d = (@as(u32, 1) << @intCast(nb - 1)) + sym(ctx[0..1], nb - 1);
}
cp += d;
var vn: u32 = 0;
var vn2: u32 = 0;
var val: u64 = utf8(cp, &vn);
ctx[0] = 3 * K + @intFromBool(d == 0);
if (sym(ctx[0..1], 1) != 0) {
ctx[0] = 4 * K;
val |= @as(u64, utf8(sym(ctx[0..1], 16), &vn2)) << @intCast(8 * vn);
}
val |= @as(u64, vn + vn2) << 56;
ctx[0] = 5 * K + @intFromBool(cp < 256);
const legacy = sym(ctx[0..1], 1) != 0;
// Names use a 6-bit alphabet: 0 ends the name, then digits, capitals, small letters.
var name = [_]u8{0} ** 40;
var n: usize = 0;
var h: u32 = 0;
var mp: usize = 0;
var ml: u32 = 0;
while (true) {
ctx[0] = 8 * K + (h & 63);
ctx[1] = 9 * K + (h & 4095);
ctx[2] = 13 * K + (if (ml != 0) @as(u32, hist[mp]) else 0) * 16 + @min(ml, 3);
ctx[3] = 10 * K + (h & 0x3FFFF);
const c = sym(&ctx, 6);
if (ml != 0 and hist[mp] == c) {
ml += 1;
mp += 1;
} else ml = 0;
hist[hn] = @intCast(c);
hn += 1;
if (c == 0) break;
const first: u32 = if (c < 11) '0' - 1 else if (c < 37) 'A' - 11 else 'a' - 37;
name[n] = @intCast(c + first);
n += 1;
h = (h << 6) | c;
if (n >= 2) {
const l = &last[h & 4095];
if (ml == 0 and l.* != 0) {
mp = l.*;
ml = 1;
}
l.* = @intCast(hn);
}
}
const nm: [*]const u8 = &name;
if (n <= 7) {
var key = ld64(nm) | (@as(u64, ';') << @intCast(8 * n));
var e: [*]Entry = @ptrCast(&fast[@intCast((key *% FAST_MUL) >> (64 - FAST_BITS))]);
while (e[0].key != EMPTY) e += 1;
e[0] = .{ .key = key, .val = val };
if (legacy) {
key = ld64(nm) | (@as(u64, n) << 56);
e = @ptrCast(&leg[@intCast((key *% LEG_MUL) >> (64 - LEG_BITS))]);
while (e[0].key != EMPTY) e += 1;
e[0] = .{ .key = key, .val = val };
const s = legSlot(key); // only the first two bytes matter
if (leg_max[s] < n) leg_max[s] = @intCast(n);
}
} else {
const l = &longs[nl];
nl += 1;
l.name = name[0..32].*;
l.val = val;
l.len = @intCast(n);
var hh = longHash(ld64(nm), ld64(nm + n - 8), n);
while (long_slots[hh] != 0) hh = (hh + 1) & LONG_MASK;
long_slots[hh] = @intCast(nl);
}
}
ready = true;
}
export fn input_ptr() u32 {
return @intCast(@intFromPtr(&input));
}
export fn input_utf8_cap() u32 {
return INPUT_CAP;
}
export fn output_ptr() u32 {
return @intCast(@intFromPtr(&output));
}
export fn output_utf8_cap() u32 {
return OUTPUT_CAP;
}
export fn render(n: u32) u64 {
if (!ready) init();
const size: usize = @min(n, INPUT_CAP);
const src: [*]u8 = &input;
const dst: [*]u8 = &output;
const zero: V = @splat(0);
st(src + size, zero);
st(src + size + 16, zero);
st(src + size + 32, zero);
st(src + size + 48, zero);
// Stage 1 lists the position of every `&` in a window; stage 2 copies the text between
// references and decodes each one.
var e: usize = 0;
var o: usize = 0;
var base: usize = 0;
while (base < size) {
const lim = if (size - base > WINDOW) base + WINDOW else size;
var out: [*]u32 = &pos;
while (true) {
const ma: u64 = eqMask(ld(src + base), '&');
const mb: u64 = eqMask(ld(src + base + 16), '&');
const mc: u64 = eqMask(ld(src + base + 32), '&');
const md: u64 = eqMask(ld(src + base + 48), '&');
var mm: u64 = ma | mb << 16 | mc << 32 | md << 48;
const cnt: usize = @popCount(mm);
const b: u32 = @intCast(base);
// Entries past cnt are garbage and are overwritten or ignored.
inline for (0..4) |k| {
out[k] = b + @ctz(mm);
mm &= mm -% 1;
}
if (cnt > 4) {
@branchHint(.unlikely);
inline for (4..8) |k| {
out[k] = b + @ctz(mm);
mm &= mm -% 1;
}
var k: usize = 8;
while (mm != 0) : (k += 1) {
out[k] = b + @ctz(mm);
mm &= mm -% 1;
}
}
out += cnt;
base += 64;
if (base >= lim) break;
}
var q: [*]const u32 = &pos;
while (@intFromPtr(q) < @intFromPtr(out)) : (q += 1) {
var i: usize = q[0];
// Copy the text since the last reference; src[i] is `&` and i < size.
{
const len = i - e;
st(dst + o, ld(src + e));
st(dst + o + 16, ld(src + e + 16));
if (len > 32) {
var j: usize = 32;
while (true) {
st(dst + o + j, ld(src + e + j));
j += 16;
if (j >= len) break;
}
}
o += len;
}
done: {
const w = ld64(src + i + 1);
if (@as(u8, @truncate(w)) == '#') numeric: {
// Decimal and hexadecimal share one branch-free path: classify 8 bytes,
// take the digits before the first other byte, and fold them pairwise.
const hex = (@as(u8, @truncate(w >> 8)) | 0x20) == 'x';
var p = src + i + 2 + @intFromBool(hex);
const d = ld64(p);
const t = d ^ 0x3030303030303030;
const digit = ~(((t & ~HIGH) +% 0x7676767676767676) | t) & HIGH;
const y = d | 0x2020202020202020;
const ty = y & ~HIGH;
const letter = (ty +% ONES * (0x80 - 'a')) & ~(ty +% ONES * (0x7F - 'f')) & ~y & HIGH;
const stop = ~(digit | (if (hex) letter else 0)) & HIGH;
var v: u32 = 0;
var end: usize = undefined;
if (stop != 0) {
const nb: u32 = @ctz(stop) & 0x38;
if (nb == 0) break :numeric;
var x = ((d & 0x0F0F0F0F0F0F0F0F) +% 9 * (letter >> 7)) << @intCast(64 - nb);
x = (x *% @as(u64, if (hex) 16 else 10) +% (x >> 8)) & 0x00FF00FF00FF00FF;
x = (x *% @as(u64, if (hex) 256 else 100) +% (x >> 16)) & 0x0000FFFF0000FFFF;
v = @truncate(x *% @as(u64, if (hex) 65536 else 10000) +% (x >> 32));
end = @intFromPtr(p) - @intFromPtr(src) + (nb >> 3);
} else {
// Eight or more digits: saturate past U+10FFFF.
@branchHint(.unlikely);
const radix: u32 = if (hex) 16 else 10;
while (true) {
var c: u32 = @as(u32, p[0]) -% '0';
if (c > 9) {
c = (@as(u32, p[0]) | 0x20) -% 'a' +% 10;
if (c < 10) c = 16;
}
if (c >= radix) break;
v = v * radix + c;
if (v > 0x10FFFF) v = 0x110000;
p += 1;
}
end = @intFromPtr(p) - @intFromPtr(src);
}
i = end + @intFromBool(src[end] == ';');
if (v -% 0x80 < 0x20) {
v = c1[v - 0x80];
} else if (v == 0 or v -% 0xD800 < 0x800 or v > 0x10FFFF) {
v = 0xFFFD;
}
// Lay the bits out as four UTF-8 bytes, then drop the unused leading ones.
const len: u32 = 1 + @as(u32, @intFromBool(v > 0x7F)) + @intFromBool(v > 0x7FF) + @intFromBool(v > 0xFFFF);
const bits = v >> 18 | (v >> 12 & 0x3F) << 8 | (v >> 6 & 0x3F) << 16 | (v & 0x3F) << 24;
const word = bits >> @intCast(32 - 8 * len) | utf8_marks[len];
st32(dst + o, if (len == 1) v else word);
o += len;
break :done;
} else {
const t = w ^ (ONES * ';');
const z = (t -% ONES) & ~t & HIGH;
if (z != 0) {
// Bit index of the `;` byte; the key is the name and its `;`.
const kb: u32 = @ctz(z) & 0x38;
const key = w & ((@as(u64, 2) << @intCast(kb + 7)) -% 1);
var en: [*]const Entry = @ptrCast(&fast[@intCast((key *% FAST_MUL) >> (64 - FAST_BITS))]);
while (true) {
const k = en[0].key;
if (k == key) {
const val = en[0].val;
st64(dst + o, val);
o += @intCast(val >> 56);
i += 2 + (kb >> 3);
break :done;
}
if (k == EMPTY) break;
en += 1;
}
} else {
// No `;` in 8 bytes: a name of 8 to 31 bytes needs its `;` in the next 24.
const s0 = ld(src + i + 1);
const s1 = ld(src + i + 17);
const sm: u32 = eqMask(s0, ';') | eqMask(s1, ';') << 16;
if (sm != 0) {
const len: usize = @ctz(sm);
var h = longHash(w, ld64(src + i + 1 + len - 8), len);
const lm: [*]const u8 = &len_mask;
const m0 = ld(lm + 32 - len);
const m1 = ld(lm + 48 - len);
while (true) {
const s = long_slots[h];
if (s == 0) break;
const l = &longs[s - 1];
const nm: [*]const u8 = &l.name;
const diff = ((s0 & m0) ^ ld(nm)) | ((s1 & m1) ^ ld(nm + 16));
if (l.len == len and @reduce(.Or, diff) == 0) {
st64(dst + o, l.val);
o += @intCast(l.val >> 56);
i += 2 + len;
break :done;
}
h = (h + 1) & LONG_MASK;
}
}
}
// Without `;`, the longest legacy name that is a prefix.
var k: usize = leg_max[legSlot(w)];
while (k >= 2) : (k -= 1) {
// The length is part of the key, so a NUL after a shorter name cannot match.
const key = (w & ((@as(u64, 1) << @intCast(8 * k)) - 1)) | @as(u64, k) << 56;
var en: [*]const Entry = @ptrCast(&leg[@intCast((key *% LEG_MUL) >> (64 - LEG_BITS))]);
while (true) {
if (en[0].key == key) {
st64(dst + o, en[0].val);
o += @intCast(en[0].val >> 56);
i += 1 + k;
break :done;
}
if (en[0].key == EMPTY) break;
en += 1;
}
}
}
dst[o] = '&';
o += 1;
i += 1;
}
e = i;
}
}
// Without a reference the input is the output.
if (e == 0) return @as(u64, @intFromPtr(&input)) << 32 | size;
var j = e;
while (j < size) : (j += 16) st(dst + o + (j - e), ld(src + j));
o += size - e;
return @as(u64, @intFromPtr(&output)) << 32 | o;
}
// pack.py, which produced `packed_list`:
//
// """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))