// unescape_html in Odin 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: odin build unescape-small.odin -file -target:freestanding_wasm32 -target-features:simd128
// -o:size -no-entry-point -no-bounds-check -disable-assert -default-to-nil-allocator -no-crt
// -out:unescape-small-odin.wasm -extra-linker-flags:"--initial-memory=3145728
// --max-memory=3145728 -z stack-size=8192 --strip-all"
// then: wasm-opt -O3 --converge --enable-simd --enable-bulk-memory
package unescape
import "base:intrinsics"
INPUT_CAP :: 1 << 20
// The largest growth is `≫⃒` (5 bytes) becoming 6 bytes.
OUTPUT_CAP :: INPUT_CAP / 5 * 6 + 8
PAD :: 128
FAST_BITS :: 12
FAST_TAIL :: 32
LEG_BITS :: 8
LEG_TAIL :: 16
LONG_BITS :: 11
LONG_MASK :: (1 << LONG_BITS) - 1
EMPTY :: max(u64)
// Bytes of input per stage-1 window; a multiple of 64.
WINDOW :: 4096
ONES :: u64(0x0101010101010101)
HIGH :: u64(0x8080808080808080)
HIST_SIZE :: 16130
ENTITY_COUNT :: 2125
LONG_COUNT :: 506
MODEL_BITS :: 18
MODEL_LIMIT :: 5
FAST_MUL :: u64(0xa59d054b12f5b905)
LEG_MUL :: u64(0xf880d97d1854e551)
LONG_MUL :: u64(0xa0c2995f40498cb3)
@(rodata)
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.
Entry :: struct {
key, val: u64,
}
Long :: struct {
name: [32]u8,
val: u64,
len: u32,
pad: u32,
}
input: [INPUT_CAP + PAD]u8
output: [OUTPUT_CAP + PAD]u8
fast: [(1 << FAST_BITS) + FAST_TAIL]Entry
leg: [(1 << LEG_BITS) + LEG_TAIL]Entry
longs: [LONG_COUNT]Long
long_slots: [1 << LONG_BITS]u16
// Longest legacy name starting with these two bytes (hashed), or 0.
leg_max: [4096]u8
pos: [WINDOW + 16]u32
ready: bool
// Windows-1252 remapping for references to 0x80-0x9F.
@(rodata)
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,
}
@(rodata)
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.
@(rodata)
len_mask := [64]u8 {
0 ..< 32 = 0xFF,
}
V :: #simd[16]u8
ld :: #force_inline proc "contextless" (p: [^]u8) -> V {
return intrinsics.unaligned_load((^V)(p))
}
st :: #force_inline proc "contextless" (p: [^]u8, v: V) {
intrinsics.unaligned_store((^V)(p), v)
}
ld64 :: #force_inline proc "contextless" (p: [^]u8) -> u64 {
return intrinsics.unaligned_load((^u64)(p))
}
st64 :: #force_inline proc "contextless" (p: [^]u8, x: u64) {
intrinsics.unaligned_store((^u64)(p), x)
}
st32 :: #force_inline proc "contextless" (p: [^]u8, x: u32) {
intrinsics.unaligned_store((^u32)(p), x)
}
eq_mask :: #force_inline proc "contextless" (v: V, c: u8) -> u32 {
return u32(transmute(u16)intrinsics.simd_extract_msbs(intrinsics.simd_lanes_eq(v, V(c))))
}
leg_slot :: #force_inline proc "contextless" (w: u64) -> u32 {
return ((u32(w) & 0xFFFF) * 0x9E3779B1) >> 20
}
long_hash :: #force_inline proc "contextless" (head, tail: u64, n: u32) -> u32 {
return u32((((head ~ ((tail << 29) | (tail >> 35))) + u64(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.
K :: u32(1 << 20)
// Step toward the bit just seen, as a 16-bit fraction: 2 / (2n + 3) after n uses.
@(rodata)
rate := [6]u16{43690, 26214, 18724, 14563, 11915, 10082}
rc_in: u32
rc_range: u32
rc_code: u32
hist: [HIST_SIZE]u8
last: [4096]u16
sym :: #force_no_inline proc "contextless" (ctx: ^[4]u32, nctx: u32, nbits: u32) -> u32 {
model := ([^]u32)(&output[0])
top := u32(1) << nbits
node: u32 = 1
for node < top {
slot: [4]u32
num, den: u32
for k in 0 ..< nctx {
s := ((ctx[k] + node * 0x2545F491) * 0x9E3779B1) >> (32 - MODEL_BITS)
slot[k] = s
e := model[s]
p := (e >> 16) ~ 0x8000
a := p - 0x8000 if p >= 0x8000 else 0x8000 - p
// Weigh a context by its order, how often it was seen and how sure it is.
w := ((e & 0xFFFF) * (1 + (a >> 12))) << k
num += p * w
den += w
}
p := (num / den if den != 0 else 0x8000) >> 4
if p == 0 do p = 1
bound := (rc_range >> 12) * p
bit: u32 = 1 if rc_code < bound else 0
if bit != 0 {
rc_range = bound
} else {
rc_code -= bound
rc_range -= bound
}
for rc_range < 1 << 24 {
rc_range <<= 8
rc_code = (rc_code << 8) | u32(packed_list[rc_in])
rc_in += 1
}
for k in 0 ..< nctx {
e := model[slot[k]]
q := i32((e >> 16) ~ 0x8000)
n := e & 0xFFFF
q += (((i32(bit) << 16) - q) * i32(rate[n])) >> 16
if n < MODEL_LIMIT do n += 1
model[slot[k]] = ((u32(q) ~ 0x8000) << 16) | n
}
node = node * 2 + bit
}
return node - top
}
// A code point as UTF-8 bytes in a word, low byte first, and their count.
utf8 :: #force_no_inline proc "contextless" (v: u32) -> (word: u32, n: u32) {
n = 1
if v > 0x7F do n += 1
if v > 0x7FF do n += 1
if v > 0xFFFF do n += 1
bits := (v >> 18) | (((v >> 12) & 0x3F) << 8) | (((v >> 6) & 0x3F) << 16) | ((v & 0x3F) << 24)
word = v if n == 1 else (bits >> (32 - 8 * n)) | utf8_marks[n]
return
}
init :: proc "contextless" () {
for &x in fast do x.key = EMPTY
for &x in leg do x.key = EMPTY
rc_range = max(u32)
rc_code = u32(packed_list[0]) << 24 | u32(packed_list[1]) << 16 | u32(packed_list[2]) << 8 | u32(packed_list[3])
rc_in = 4
cp, nl: u32
hn: u32 = 1
ctx: [4]u32
for _ in 0 ..< ENTITY_COUNT {
// Step from the previous code point: its bit length, then the bits below the top one.
ctx[0] = K
nb := sym(&ctx, 1, 5)
d := nb
if nb > 1 {
ctx[0] = 2 * K + nb
d = (u32(1) << (nb - 1)) + sym(&ctx, 1, nb - 1)
}
cp += d
word, vn := utf8(cp)
val := u64(word)
vn2: u32
ctx[0] = 3 * K + (1 if d == 0 else 0)
if sym(&ctx, 1, 1) != 0 {
ctx[0] = 4 * K
word, vn2 = utf8(sym(&ctx, 1, 16))
val |= u64(word) << (8 * vn)
}
val |= u64(vn + vn2) << 56
ctx[0] = 5 * K + (1 if cp < 256 else 0)
legacy := sym(&ctx, 1, 1) != 0
// Names use a 6-bit alphabet: 0 ends the name, then digits, capitals, small letters.
name: [40]u8
n, h, mp, ml: u32
for {
ctx[0] = 8 * K + (h & 63)
ctx[1] = 9 * K + (h & 4095)
ctx[2] = 13 * K + (u32(hist[mp]) if ml != 0 else 0) * 16 + min(ml, 3)
ctx[3] = 10 * K + (h & 0x3FFFF)
c := sym(&ctx, 4, 6)
if ml != 0 && u32(hist[mp]) == c {
ml += 1
mp += 1
} else {
ml = 0
}
hist[hn] = u8(c)
hn += 1
if c == 0 do break
first: u32 = 'a' - 37
if c < 37 do first = 'A' - 11
if c < 11 do first = '0' - 1
name[n] = u8(c + first)
n += 1
h = (h << 6) | c
if n >= 2 {
l := &last[h & 4095]
if ml == 0 && l^ != 0 {
mp = u32(l^)
ml = 1
}
l^ = u16(hn)
}
}
nm := ([^]u8)(&name[0])
if n <= 7 {
key := ld64(nm) | (u64(';') << (8 * n))
e := u32((key * FAST_MUL) >> (64 - FAST_BITS))
for fast[e].key != EMPTY do e += 1
fast[e] = Entry{key, val}
if legacy {
key = ld64(nm) | (u64(n) << 56)
e = u32((key * LEG_MUL) >> (64 - LEG_BITS))
for leg[e].key != EMPTY do e += 1
leg[e] = Entry{key, val}
s := leg_slot(key) // only the first two bytes matter
if u32(leg_max[s]) < n do leg_max[s] = u8(n)
}
} else {
l := &longs[nl]
nl += 1
st(([^]u8)(&l.name[0]), ld(nm))
st(([^]u8)(&l.name[16]), ld(nm[16:]))
l.val = val
l.len = n
hh := long_hash(ld64(nm), ld64(nm[n - 8:]), n)
for long_slots[hh] != 0 do hh = (hh + 1) & LONG_MASK
long_slots[hh] = u16(nl)
}
}
ready = true
}
@(export)
input_ptr :: proc "c" () -> u32 {return u32(uintptr(&input[0]))}
@(export)
input_utf8_cap :: proc "c" () -> u32 {return INPUT_CAP}
@(export)
output_ptr :: proc "c" () -> u32 {return u32(uintptr(&output[0]))}
@(export)
output_utf8_cap :: proc "c" () -> u32 {return OUTPUT_CAP}
@(export)
render :: proc "c" (n: u32) -> u64 {
if !ready do #force_no_inline init()
size: u32 = min(n, INPUT_CAP)
src := ([^]u8)(&input[0])
dst := ([^]u8)(&output[0])
zero: V = 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.
e, o, base: u32
for base < size {
lim := size - base > WINDOW ? base + WINDOW : size
out: u32 = 0
for {
ma := u64(eq_mask(ld(src[base:]), '&'))
mb := u64(eq_mask(ld(src[base + 16:]), '&'))
mc := u64(eq_mask(ld(src[base + 32:]), '&'))
md := u64(eq_mask(ld(src[base + 48:]), '&'))
mm := ma | (mb << 16) | (mc << 32) | (md << 48)
cnt := u32(intrinsics.count_ones(mm))
// Entries past cnt are garbage and are overwritten or ignored.
#unroll for k in u32(0) ..< 4 {
pos[out + k] = base + u32(intrinsics.count_trailing_zeros(mm))
mm &= mm - 1
}
if cnt > 4 {
#unroll for k in u32(4) ..< 8 {
pos[out + k] = base + u32(intrinsics.count_trailing_zeros(mm))
mm &= mm - 1
}
for k := out + 8; mm != 0; k += 1 {
pos[k] = base + u32(intrinsics.count_trailing_zeros(mm))
mm &= mm - 1
}
}
out += cnt
base += 64
if base >= lim do break
}
for q in 0 ..< out {
i := pos[q]
// Copy the text since the last reference; src[i] is `&` and i < size.
{
gap := i - e
st(dst[o:], ld(src[e:]))
st(dst[o + 16:], ld(src[e + 16:]))
if gap > 32 {
j: u32 = 32
for {
st(dst[o + j:], ld(src[e + j:]))
j += 16
if j >= gap do break
}
}
o += gap
}
done: {
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.
numeric: {
hex := (u8(w >> 8) | 0x20) == 'x'
p := i + 2 + u32(hex)
d := ld64(src[p:])
t := d ~ 0x3030303030303030
digit := ~(((t & ~HIGH) + 0x7676767676767676) | t) & HIGH
y := d | 0x2020202020202020
ty := y & ~HIGH
// Letters a-f: 0x80 - 'a' = 0x1F, 0x7F - 'f' = 0x19.
letter := (ty + ONES * 0x1F) & ~(ty + ONES * 0x19) & ~y & HIGH
stop := ~(digit | (hex ? letter : 0)) & HIGH
v, end: u32
if stop != 0 {
nb := u32(intrinsics.count_trailing_zeros(stop)) & 0x38
if nb == 0 do break numeric
x := ((d & 0x0F0F0F0F0F0F0F0F) + 9 * (letter >> 7)) << (64 - nb)
x = (x * (hex ? 16 : 10) + (x >> 8)) & 0x00FF00FF00FF00FF
x = (x * (hex ? 256 : 100) + (x >> 16)) & 0x0000FFFF0000FFFF
v = u32(x * (hex ? 65536 : 10000) + (x >> 32))
end = p + (nb >> 3)
} else {
// Eight or more digits: saturate past U+10FFFF.
radix: u32 = hex ? 16 : 10
for {
c := u32(src[p]) - '0'
if c > 9 {
c = (u32(src[p]) | 0x20) - 'a' + 10
if c < 10 do c = 16
}
if c >= radix do break
v = v * radix + c
if v > 0x10FFFF do v = 0x110000
p += 1
}
end = p
}
i = end + u32(src[end] == ';')
if v - 0x80 < 0x20 {
v = u32(c1[v - 0x80])
} else if v == 0 || v - 0xD800 < 0x800 || v > 0x10FFFF {
v = 0xFFFD
}
// Lay the bits out as four UTF-8 bytes, then drop the unused leading ones.
ln := 1 + u32(v > 0x7F) + u32(v > 0x7FF) + u32(v > 0xFFFF)
bits := (v >> 18) | (((v >> 12) & 0x3F) << 8) | (((v >> 6) & 0x3F) << 16) | ((v & 0x3F) << 24)
word := (bits >> (32 - 8 * ln)) | utf8_marks[ln]
st32(dst[o:], ln == 1 ? v : word)
o += ln
break done
}
} else {
t := w ~ (ONES * 0x3B)
z := (t - ONES) & ~t & HIGH
if z != 0 {
// Bit index of the `;` byte; the key is the name and its `;`.
kb := u32(intrinsics.count_trailing_zeros(z)) & 0x38
key := w & ((u64(2) << (kb + 7)) - 1)
en := u32((key * FAST_MUL) >> (64 - FAST_BITS))
for {
k := fast[en].key
if k == key {
val := fast[en].val
st64(dst[o:], val)
o += u32(val >> 56)
i += 2 + (kb >> 3)
break done
}
if k == EMPTY do break
en += 1
}
} else {
// No `;` in 8 bytes: a name of 8 to 31 bytes needs its `;` in the next 24.
s0 := ld(src[i + 1:])
s1 := ld(src[i + 17:])
sm := eq_mask(s0, ';') | (eq_mask(s1, ';') << 16)
if sm != 0 {
ln := u32(intrinsics.count_trailing_zeros(sm))
h := long_hash(w, ld64(src[i + 1 + ln - 8:]), ln)
lm := ([^]u8)(&len_mask[0])
m0 := ld(lm[32 - ln:])
m1 := ld(lm[48 - ln:])
for {
s := u32(long_slots[h])
if s == 0 do break
l := &longs[s - 1]
nm := ([^]u8)(&l.name[0])
diff := ((s0 & m0) ~ ld(nm)) | ((s1 & m1) ~ ld(nm[16:]))
if l.len == ln && intrinsics.simd_reduce_or(diff) == 0 {
st64(dst[o:], l.val)
o += u32(l.val >> 56)
i += 2 + ln
break done
}
h = (h + 1) & LONG_MASK
}
}
}
// Without `;`, the longest legacy name that is a prefix.
for k := u32(leg_max[leg_slot(w)]); k >= 2; k -= 1 {
// The length is part of the key, so a NUL after a shorter name cannot match.
key := (w & ((u64(1) << (8 * k)) - 1)) | (u64(k) << 56)
en := u32((key * LEG_MUL) >> (64 - LEG_BITS))
for {
if leg[en].key == key {
st64(dst[o:], leg[en].val)
o += u32(leg[en].val >> 56)
i += 1 + k
break done
}
if leg[en].key == EMPTY do break
en += 1
}
}
}
dst[o] = '&'
o += 1
i += 1
}
e = i
}
}
// Without a reference the input is the output.
if e == 0 do return (u64(uintptr(src)) << 32) | u64(size)
for j := e; j < size; j += 16 do st(dst[o + (j - e):], ld(src[j:]))
o += size - e
return (u64(uintptr(dst)) << 32) | u64(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))
*/