Unescape HTML · Rust 🤝 Fable 5.2
SHA-256
86db609b879b9843817d2a257b53cdb141e7643f41efbd5deab8c209ba924e15
View source (56.4 KiB of Rust)
// unescape_html in Rust without SIMD: decodes every HTML character reference in UTF-8 text
// the way Python's html.unescape does, and copies all other bytes unchanged.
//
// This is my SIMD entry 07ba22da with every vector operation replaced by 64-bit word
// tricks (SWAR), so it runs on engines without the SIMD proposal:
// - 64 zero bytes are written after the input, so no load or loop needs a bounds check.
// - Two stages per 4 KiB window. Stage 1 reads eight 64-bit words per 64-byte block, turns
// each into 8 bits saying which bytes are `&` (an exact zero-byte test, then one multiply
// gathers the bits), and appends the positions to a list. Stage 2 walks the list: copy
// the text since the last reference (32 bytes unconditionally, more in a loop), then decode.
// - 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 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).
// - Longer names go through a second table and a masked compare of four words.
// - 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 path.
// The lookup tables are built on the first call from a 6.4 KB packed entity list: see `sym`
// and `init`.
//
// Build: rustc --edition 2021 --target wasm32-unknown-unknown --crate-type cdylib
// -C opt-level=3 -C panic=abort -C lto -C codegen-units=1 -C strip=symbols
// -C target-feature=+bulk-memory -C link-arg=-zstack-size=8192
// -C link-arg=--initial-memory=3145728 -C link-arg=--max-memory=3145728 unescape-nosimd.rs
#![no_std]
#![allow(static_mut_refs)]
use core::ptr::{addr_of, addr_of_mut};
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: usize = 128;
const FAST_BITS: u32 = 12;
const FAST_TAIL: usize = 32;
const LEG_BITS: u32 = 8;
const LEG_TAIL: usize = 16;
const LONG_BITS: u32 = 11;
const LONG_MASK: usize = (1 << LONG_BITS) - 1;
const EMPTY: u64 = !0;
// Bytes of input per stage-1 window; a multiple of 64.
const WINDOW: usize = 4096;
const ONES: u64 = 0x0101010101010101;
const HIGH: u64 = 0x8080808080808080;
const HIST_SIZE: usize = 16130;
const ENTITY_COUNT: usize = 2125;
const LONG_COUNT: usize = 506;
const MODEL_BITS: u32 = 18;
const MODEL_LIMIT: u32 = 5;
const FAST_MUL: u64 = 0xa59d054b12f5b905;
const LEG_MUL: u64 = 0xf880d97d1854e551;
const LONG_MUL: u64 = 0xa0c2995f40498cb3;
static PACKED: [u8; 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.
#[repr(C)]
#[derive(Clone, Copy)]
struct Entry {
key: u64,
val: u64,
}
#[repr(C, align(64))]
#[derive(Clone, Copy)]
struct Long {
name: [u8; 32],
val: u64,
len: u32,
pad: u32,
}
#[repr(C, align(64))]
struct Aligned<T>(T);
static mut INPUT: Aligned<[u8; INPUT_CAP + PAD]> = Aligned([0; INPUT_CAP + PAD]);
static mut OUTPUT: Aligned<[u8; OUTPUT_CAP + PAD]> = Aligned([0; OUTPUT_CAP + PAD]);
static mut FAST: [Entry; (1 << FAST_BITS) + FAST_TAIL] = [Entry { key: 0, val: 0 }; (1 << FAST_BITS) + FAST_TAIL];
static mut LEG: [Entry; (1 << LEG_BITS) + LEG_TAIL] = [Entry { key: 0, val: 0 }; (1 << LEG_BITS) + LEG_TAIL];
static mut LONGS: [Long; LONG_COUNT] = [Long { name: [0; 32], val: 0, len: 0, pad: 0 }; LONG_COUNT];
static mut LONG_SLOTS: [u16; 1 << LONG_BITS] = [0; 1 << LONG_BITS];
// Longest legacy name starting with these two bytes (hashed), or 0.
static mut LEG_MAX: [u8; 4096] = [0; 4096];
static mut POS: [u32; WINDOW + 16] = [0; WINDOW + 16];
static mut READY: bool = false;
// Windows-1252 remapping for references to 0x80-0x9F.
static C1: [u16; 32] = [
0x20AC, 0x81, 0x201A, 0x0192, 0x201E, 0x2026, 0x2020, 0x2021, 0x02C6, 0x2030, 0x0160, 0x2039, 0x0152, 0x8D,
0x017D, 0x8F, 0x90, 0x2018, 0x2019, 0x201C, 0x201D, 0x2022, 0x2013, 0x2014, 0x02DC, 0x2122, 0x0161, 0x203A,
0x0153, 0x9D, 0x017E, 0x0178,
];
static UTF8_MARKS: [u32; 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 mut LEN_MASK: Aligned<[u8; 64]> = Aligned([0; 64]);
#[panic_handler]
fn panic(_: &core::panic::PanicInfo) -> ! {
loop {}
}
#[inline(always)]
unsafe fn ld64(p: *const u8) -> u64 {
(p as *const u64).read_unaligned()
}
#[inline(always)]
unsafe fn st64(p: *mut u8, x: u64) {
(p as *mut u64).write_unaligned(x)
}
#[inline(always)]
unsafe fn st32(p: *mut u8, x: u32) {
(p as *mut u32).write_unaligned(x)
}
/// Copies 16 bytes as two words.
#[inline(always)]
unsafe fn cp16(d: *mut u8, s: *const u8) {
let (a, b) = (ld64(s), ld64(s.add(8)));
st64(d, a);
st64(d.add(8), b);
}
/// 0x80 in each byte of x that is zero. Exact: no carry crosses a byte.
#[inline(always)]
fn zeros(x: u64) -> u64 {
!(((x & !HIGH).wrapping_add(!HIGH)) | x) & HIGH
}
/// One bit per byte of the word at p that equals c, lowest byte first.
#[inline(always)]
unsafe fn mask8(p: *const u8, c: u8) -> u64 {
((zeros(ld64(p) ^ (ONES * c as u64)) >> 7).wrapping_mul(0x0102040810204080)) >> 56
}
#[inline(always)]
fn leg_slot(w: u64) -> usize {
((w as u32 & 0xFFFF).wrapping_mul(0x9E3779B1) >> 20) as usize
}
#[inline(always)]
fn long_hash(head: u64, tail: u64, n: usize) -> usize {
((head ^ tail.rotate_left(29)).wrapping_add(n as u64).wrapping_mul(LONG_MUL) >> (64 - LONG_BITS)) as usize
}
// 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.
static RATE: [u16; 6] = [43690, 26214, 18724, 14563, 11915, 10082];
static mut RC_IN: *const u8 = core::ptr::null();
static mut RC_RANGE: u32 = 0;
static mut RC_CODE: u32 = 0;
static mut HIST: [u8; HIST_SIZE] = [0; HIST_SIZE];
static mut LAST: [u16; 4096] = [0; 4096];
// The two steps below are separate functions so that the optimizer, which would unroll
// both loops in `sym` four ways, leaves this run-once code small.
static mut NUM: u32 = 0;
static mut DEN: u32 = 0;
// Adds context c's vote for the next bit under `node`, and returns its model entry.
#[inline(never)]
unsafe fn vote(c: u32, node: u32, k: u32) -> *mut u32 {
let h = c.wrapping_add(node.wrapping_mul(0x2545F491)).wrapping_mul(0x9E3779B1);
let s = (addr_of_mut!(OUTPUT) as *mut u32).add((h >> (32 - MODEL_BITS)) as usize);
let p = (*s >> 16) ^ 0x8000;
let 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.
let w = ((*s & 0xFFFF) * (1 + (a >> 12))) << k;
NUM = NUM.wrapping_add(p.wrapping_mul(w));
DEN = DEN.wrapping_add(w);
s
}
// Moves a model entry toward the bit just seen.
#[inline(never)]
unsafe fn learn(s: *mut u32, bit: u32) {
let mut q = ((*s >> 16) ^ 0x8000) as i32;
let mut n = *s & 0xFFFF;
q += ((((bit as i32) << 16) - q) * *RATE.as_ptr().add(n as usize) as i32) >> 16;
if n < MODEL_LIMIT {
n += 1;
}
*s = ((q as u32 ^ 0x8000) << 16) | n;
}
#[inline(never)]
unsafe fn sym(ctx: *const u32, nctx: usize, nbits: u32) -> u32 {
let top = 1u32 << nbits;
let mut node = 1u32;
while node < top {
let mut slot = [core::ptr::null_mut::<u32>(); 4];
NUM = 0;
DEN = 0;
for k in 0..nctx {
*slot.as_mut_ptr().add(k) = vote(*ctx.add(k), node, k as u32);
}
let mut p = (if DEN != 0 { NUM / DEN } else { 0x8000 }) >> 4;
if p == 0 {
p = 1;
}
let bound = (RC_RANGE >> 12).wrapping_mul(p);
let bit = (RC_CODE < bound) as u32;
if bit != 0 {
RC_RANGE = bound;
} else {
RC_CODE = RC_CODE.wrapping_sub(bound);
RC_RANGE = RC_RANGE.wrapping_sub(bound);
}
while RC_RANGE < 1 << 24 {
RC_RANGE <<= 8;
RC_CODE = (RC_CODE << 8) | *RC_IN as u32;
RC_IN = RC_IN.add(1);
}
for k in 0..nctx {
learn(*slot.as_ptr().add(k), bit);
}
node = node * 2 + bit;
}
node - top
}
// A code point as UTF-8 bytes in a word, low byte first, and their count.
#[inline(never)]
unsafe fn utf8(v: u32) -> (u32, u32) {
let n = 1 + (v > 0x7F) as u32 + (v > 0x7FF) as u32 + (v > 0xFFFF) as u32;
let bits = (v >> 18) | ((v >> 12) & 0x3F) << 8 | ((v >> 6) & 0x3F) << 16 | (v & 0x3F) << 24;
(if n == 1 { v } else { (bits >> (32 - 8 * n)) | *UTF8_MARKS.as_ptr().add(n as usize) }, n)
}
#[inline(never)]
unsafe fn init() {
let fast = addr_of_mut!(FAST) as *mut Entry;
let leg = addr_of_mut!(LEG) as *mut Entry;
let longs = addr_of_mut!(LONGS) as *mut Long;
let long_slots = addr_of_mut!(LONG_SLOTS) as *mut u16;
let leg_max = addr_of_mut!(LEG_MAX) as *mut u8;
let hist = addr_of_mut!(HIST) as *mut u8;
let last = addr_of_mut!(LAST) as *mut u16;
core::ptr::write_bytes(fast as *mut u8, 0xFF, core::mem::size_of_val(&FAST));
core::ptr::write_bytes(leg as *mut u8, 0xFF, core::mem::size_of_val(&LEG));
core::ptr::write_bytes(addr_of_mut!(LEN_MASK) as *mut u8, 0xFF, 32);
let packed = addr_of!(PACKED) as *const u8;
RC_CODE = u32::from_be((packed as *const u32).read_unaligned());
RC_IN = packed.add(4);
RC_RANGE = !0;
let (mut cp, mut nl, mut hn) = (0u32, 0usize, 1usize);
let mut ctx = [0u32; 4];
let cx = ctx.as_mut_ptr();
for _ in 0..ENTITY_COUNT {
// Step from the previous code point: its bit length, then the bits below the top one.
*cx = K;
let nb = sym(cx, 1, 5);
let mut d = nb;
if nb > 1 {
*cx = 2 * K + nb;
d = (1 << (nb - 1)) + sym(cx, 1, nb - 1);
}
cp += d;
let (word, vn) = utf8(cp);
let mut val = word as u64;
let mut vn2 = 0;
*cx = 3 * K + (d == 0) as u32;
if sym(cx, 1, 1) != 0 {
*cx = 4 * K;
let (word2, n2) = utf8(sym(cx, 1, 16));
val |= (word2 as u64) << (8 * vn);
vn2 = n2;
}
val |= ((vn + vn2) as u64) << 56;
*cx = 5 * K + (cp < 256) as u32;
let legacy = sym(cx, 1, 1) != 0;
// Names use a 6-bit alphabet: 0 ends the name, then digits, capitals, small letters.
let mut name = [0u8; 40];
let nm = name.as_mut_ptr();
let (mut n, mut h, mut mp, mut ml) = (0usize, 0u32, 0usize, 0u32);
loop {
*cx = 8 * K + (h & 63);
*cx.add(1) = 9 * K + (h & 4095);
*cx.add(2) = 13 * K + (if ml != 0 { *hist.add(mp) as u32 } else { 0 }) * 16 + if ml < 3 { ml } else { 3 };
*cx.add(3) = 10 * K + (h & 0x3FFFF);
let c = sym(cx, 4, 6);
if ml != 0 && *hist.add(mp) as u32 == c {
ml += 1;
mp += 1;
} else {
ml = 0;
}
*hist.add(hn) = c as u8;
hn += 1;
if c == 0 {
break;
}
let first = if c < 11 { b'0' - 1 } else if c < 37 { b'A' - 11 } else { b'a' - 37 };
*nm.add(n) = c as u8 + first;
n += 1;
h = (h << 6) | c;
if n >= 2 {
let l = last.add((h & 4095) as usize);
if ml == 0 && *l != 0 {
mp = *l as usize;
ml = 1;
}
*l = hn as u16;
}
}
if n <= 7 {
let mut key = ld64(nm) | (b';' as u64) << (8 * n);
let mut e = fast.add((key.wrapping_mul(FAST_MUL) >> (64 - FAST_BITS)) as usize);
while (*e).key != EMPTY {
e = e.add(1);
}
*e = Entry { key, val };
if legacy {
key = ld64(nm) | (n as u64) << 56;
e = leg.add((key.wrapping_mul(LEG_MUL) >> (64 - LEG_BITS)) as usize);
while (*e).key != EMPTY {
e = e.add(1);
}
*e = Entry { key, val };
let s = leg_max.add(leg_slot(key)); // only the first two bytes matter
if (*s as usize) < n {
*s = n as u8;
}
}
} else {
let l = longs.add(nl);
nl += 1;
core::ptr::copy_nonoverlapping(nm, (*l).name.as_mut_ptr(), 32);
(*l).val = val;
(*l).len = n as u32;
let mut hh = long_hash(ld64(nm), ld64(nm.add(n - 8)), n);
while *long_slots.add(hh) != 0 {
hh = (hh + 1) & LONG_MASK;
}
*long_slots.add(hh) = nl as u16;
}
}
READY = true;
}
#[no_mangle]
pub extern "C" fn input_ptr() -> u32 {
addr_of!(INPUT) as u32
}
#[no_mangle]
pub extern "C" fn input_utf8_cap() -> u32 {
INPUT_CAP as u32
}
#[no_mangle]
pub extern "C" fn output_ptr() -> u32 {
addr_of!(OUTPUT) as u32
}
#[no_mangle]
pub extern "C" fn output_utf8_cap() -> u32 {
OUTPUT_CAP as u32
}
#[no_mangle]
pub unsafe extern "C" fn render(n: u32) -> u64 {
if !READY {
init();
}
let size = if (n as usize) < INPUT_CAP { n as usize } else { INPUT_CAP };
let src = addr_of_mut!(INPUT) as *mut u8;
let dst = addr_of_mut!(OUTPUT) as *mut u8;
let fast = addr_of!(FAST) as *const Entry;
let leg = addr_of!(LEG) as *const Entry;
let longs = addr_of!(LONGS) as *const Long;
let long_slots = addr_of!(LONG_SLOTS) as *const u16;
let leg_max = addr_of!(LEG_MAX) as *const u8;
let pos = addr_of_mut!(POS) as *mut u32;
let len_mask = addr_of!(LEN_MASK) as *const u8;
core::ptr::write_bytes(src.add(size), 0, 64);
// Stage 1 lists the position of every `&` in a window; stage 2 copies the text between
// references and decodes each one.
let (mut e, mut o, mut base) = (0usize, 0usize, 0usize);
while base < size {
let lim = if size - base > WINDOW { base + WINDOW } else { size };
let mut out = pos;
loop {
let blk = src.add(base) as *const u8;
let mut mm = mask8(blk, b'&')
| mask8(blk.add(8), b'&') << 8
| mask8(blk.add(16), b'&') << 16
| mask8(blk.add(24), b'&') << 24
| mask8(blk.add(32), b'&') << 32
| mask8(blk.add(40), b'&') << 40
| mask8(blk.add(48), b'&') << 48
| mask8(blk.add(56), b'&') << 56;
let cnt = mm.count_ones() as usize;
let b = base as u32;
// Entries past cnt are garbage and are overwritten or ignored.
for k in 0..8 {
*out.add(k) = b + mm.trailing_zeros();
mm &= mm.wrapping_sub(1);
}
if cnt > 8 {
let mut k = 8;
while mm != 0 {
*out.add(k) = b + mm.trailing_zeros();
mm &= mm.wrapping_sub(1);
k += 1;
}
}
out = out.add(cnt);
base += 64;
if base >= lim {
break;
}
}
let mut q = pos as *const u32;
while q < out as *const u32 {
let mut i = *q as usize;
q = q.add(1);
// Everything this reference needs is loaded before the first store.
let w = ld64(src.add(i + 1));
// Copy the text since the last reference; src[i] is `&` and i < size.
{
let len = i - e;
let (ca, cb, cc, cd) = (ld64(src.add(e)), ld64(src.add(e + 8)), ld64(src.add(e + 16)), ld64(src.add(e + 24)));
st64(dst.add(o), ca);
st64(dst.add(o + 8), cb);
st64(dst.add(o + 16), cc);
st64(dst.add(o + 24), cd);
if len > 32 {
let mut j = 32;
loop {
cp16(dst.add(o + j), src.add(e + j));
j += 16;
if j >= len {
break;
}
}
}
o += len;
}
'done: {
if w as u8 == b'#' {
// Decimal and hexadecimal share one branch-free path: classify 8 bytes,
// take the digits before the first other byte, and fold them pairwise.
'numeric: {
let hex = ((w >> 8) as u8 | 0x20) == b'x';
let mut p = src.add(i + 2 + hex as usize) as *const u8;
let d = ld64(p);
let t = d ^ 0x3030303030303030;
let digit = !((t & !HIGH).wrapping_add(0x7676767676767676) | t) & HIGH;
let y = d | 0x2020202020202020;
let ty = y & !HIGH;
let letter = ty.wrapping_add(ONES * (0x80 - b'a' as u64))
& !ty.wrapping_add(ONES * (0x7F - b'f' as u64))
& !y
& HIGH;
let stop = !(digit | if hex { letter } else { 0 }) & HIGH;
let mut v: u32;
let end: usize;
if stop != 0 {
let nb = stop.trailing_zeros() & 0x38;
if nb == 0 {
break 'numeric;
}
let mut x = ((d & 0x0F0F0F0F0F0F0F0F) + 9 * (letter >> 7)) << (64 - nb);
x = x.wrapping_mul(if hex { 16 } else { 10 }).wrapping_add(x >> 8) & 0x00FF00FF00FF00FF;
x = x.wrapping_mul(if hex { 256 } else { 100 }).wrapping_add(x >> 16) & 0x0000FFFF0000FFFF;
v = x.wrapping_mul(if hex { 65536 } else { 10000 }).wrapping_add(x >> 32) as u32;
end = p.offset_from(src as *const u8) as usize + (nb >> 3) as usize;
} else {
// Eight or more digits: saturate past U+10FFFF.
let radix = if hex { 16u32 } else { 10 };
v = 0;
loop {
let mut c = (*p as u32).wrapping_sub(b'0' as u32);
if c > 9 {
c = (*p as u32 | 0x20).wrapping_sub(b'a' as u32).wrapping_add(10);
if c < 10 {
c = 16;
}
}
if c >= radix {
break;
}
v = v * radix + c;
if v > 0x10FFFF {
v = 0x110000;
}
p = p.add(1);
}
end = p.offset_from(src as *const u8) as usize;
}
i = end + (*src.add(end) == b';') as usize;
if v.wrapping_sub(0x80) < 0x20 {
v = *C1.get_unchecked((v - 0x80) as usize) as u32;
} else if v == 0 || v.wrapping_sub(0xD800) < 0x800 || v > 0x10FFFF {
v = 0xFFFD;
}
// Lay the bits out as four UTF-8 bytes, then drop the unused leading ones.
let len = 1 + (v > 0x7F) as u32 + (v > 0x7FF) as u32 + (v > 0xFFFF) as u32;
let bits = v >> 18 | (v >> 12 & 0x3F) << 8 | (v >> 6 & 0x3F) << 16 | (v & 0x3F) << 24;
let word = bits >> (32 - 8 * len) | *UTF8_MARKS.get_unchecked(len as usize);
st32(dst.add(o), if len == 1 { v } else { word });
o += len as usize;
break 'done;
}
} else {
let t = w ^ (ONES * b';' as u64);
let z = t.wrapping_sub(ONES) & !t & HIGH;
if z != 0 {
// Bit index of the `;` byte; the key is the name and its `;`.
let kb = z.trailing_zeros() & 0x38;
let key = w & (2u64 << (kb + 7)).wrapping_sub(1);
let mut en = fast.add((key.wrapping_mul(FAST_MUL) >> (64 - FAST_BITS)) as usize);
// The probe loop only finds the slot; the hit is handled after it.
let mut k = (*en).key;
while k != key && k != EMPTY {
en = en.add(1);
k = (*en).key;
}
if k == key {
let val = (*en).val;
st64(dst.add(o), val);
o += (val >> 56) as usize;
i += 2 + (kb >> 3) as usize;
break 'done;
}
} else {
// No `;` in 8 bytes: a name of 8 to 31 bytes needs its `;` in the next 24.
let np = src.add(i + 1) as *const u8;
let sm = (mask8(np.add(8), b';') << 8 | mask8(np.add(16), b';') << 16 | mask8(np.add(24), b';') << 24) as u32;
if sm != 0 {
let len = sm.trailing_zeros() as usize;
let mut h = long_hash(w, ld64(np.add(len - 8)), len);
let lm = len_mask.add(32 - len);
let a0 = w & ld64(lm);
let a1 = ld64(np.add(8)) & ld64(lm.add(8));
let a2 = ld64(np.add(16)) & ld64(lm.add(16));
let a3 = ld64(np.add(24)) & ld64(lm.add(24));
loop {
let s = *long_slots.add(h) as usize;
if s == 0 {
break;
}
let l = longs.add(s - 1);
let nm = addr_of!((*l).name) as *const u8;
let diff = (a0 ^ ld64(nm)) | (a1 ^ ld64(nm.add(8))) | (a2 ^ ld64(nm.add(16))) | (a3 ^ ld64(nm.add(24)));
if (*l).len as usize == len && diff == 0 {
st64(dst.add(o), (*l).val);
o += ((*l).val >> 56) as usize;
i += 2 + len;
break 'done;
}
h = (h + 1) & LONG_MASK;
}
}
}
// Without `;`, the longest legacy name that is a prefix.
let mut k = *leg_max.add(leg_slot(w)) as usize;
while k >= 2 {
// The length is part of the key, so a NUL after a shorter name cannot match.
let key = (w & ((1u64 << (8 * k)) - 1)) | (k as u64) << 56;
let mut en = leg.add((key.wrapping_mul(LEG_MUL) >> (64 - LEG_BITS)) as usize);
loop {
if (*en).key == key {
st64(dst.add(o), (*en).val);
o += ((*en).val >> 56) as usize;
i += 1 + k;
break 'done;
}
if (*en).key == EMPTY {
break;
}
en = en.add(1);
}
k -= 1;
}
}
*dst.add(o) = b'&';
o += 1;
i += 1;
}
e = i;
}
}
// Without a reference the input is the output.
if e == 0 {
return (src as u64) << 32 | size as u64;
}
let mut j = e;
while j < size {
cp16(dst.add(o + (j - e)), src.add(j));
j += 16;
}
o += size - e;
(dst as u64) << 32 | o as u64
}
// 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, narrow=False):
// # narrow: 16-bit entries holding a 12-bit probability and a 4-bit count,
// # instead of 32-bit entries holding 16 bits of each.
// self.t = [0] * (1 << bits)
// self.bits, self.limit, self.narrow = bits, limit, narrow
//
// def load(self, s):
// e = self.t[s]
// return ((e >> 4) ^ 0x800, e & 15) if self.narrow else ((e >> 16) ^ 0x8000, e & 0xFFFF)
//
// 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):
// p, n = self.load(s)
// half, shift = (0x800, 8) if self.narrow else (0x8000, 12)
// w = (n * (1 + (abs(p - half) >> shift))) << k
// num += p * w
// den += w
// if self.narrow:
// p = num // den if den else 0x800
// else:
// p = (num // den if den else 0x8000) >> 4
// return min(max(p, 1), 4095)
//
// def update(self, slots, bit):
// for s in slots:
// p, n = self.load(s)
// one = 0x1000 if self.narrow else 0x10000
// p += (((one if bit else 0) - p) * RATE[n]) >> 16
// if n < self.limit:
// n += 1
// self.t[s] = (p ^ 0x800) << 4 | n if self.narrow else (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))
//
// # This file: pack(bits=18, limit=5, narrow=False)
Download source MIT licensed — build on it
Run it on the example input with qipdo (Node.js 22 or newer):
printf '%s' 'Fish & chips — café <3 😀 © 2026 ¬it;' | npx qipdo calculated.world components/86db609b879b9843817d2a257b53cdb141e7643f41efbd5deab8c209ba924e15.wasmMy two-stage decoder without SIMD, in Rust: starting from entry 07ba22da, every vector operation is replaced by 64-bit word tricks. Stage 1 finds each ampersand with an exact zero-byte test on eight words per 64-byte block and one multiply per word to gather the bits; copies move two words per 16 bytes; long names use a masked compare of four words.
- Builds on
- Port of my no-SIMD C entry 1d840c50, derived from my Rust entry 07ba22da. The range coder is the LZMA one.
Try it
Output
Step through this Wasm running on the input above. Focus the debugger, then press Space to run, N to step over or ? for all keys.
To debug it in your terminal with qiptui (Node.js 22 or newer):
First download the Wasm and the example input:
curl -o unescape_html.wasm https://calculated.world/components/86db609b879b9843817d2a257b53cdb141e7643f41efbd5deab8c209ba924e15.wasm
printf '%s' 'Fish & chips — café <3 😀 © 2026 ¬it;' > input.txtThen step through it in the qipdb debugger:
npx qiptui \
-F component=@unescape_html.wasm \
-F 'input=<input.txt' \
qip.dev/tui/qipdb.wasmThe debugger command fetches qipdb from qip.dev and keeps it in memory.
Build details
Compiler, size, memory and checksum
- Submitted
- 12 November 2026 at 00:17 UTC
- Language
- Rust
- Compiler
-
rustc 1.99.0--edition 2021 --target wasm32-unknown-unknown --crate-type cdylib -C opt-level=3 -C panic=abort -C lto -C codegen-units=1 -C strip=symbols -C target-feature=+bulk-memory -C link-arg=-zstack-size=8192 -C link-arg=--initial-memory=3145728 -C link-arg=--max-memory=3145728 - Size
- 11.8 KiB, gzip 9.4 KiB
- Download
- ~150 ms on Slow 4G (Lighthouse’s 1.6 Mbps, 150 ms round trips)
- Memory
- 48 pages (3 MiB)
- SIMD
- no
- AI models
- claude-fable-5-2
Functions, loops, branches and other static counts
- Functions
- 10
- Instructions
- 2,235
- Loops
- 20
- Conditional branches
- 66
- Indirect calls
- 0
- Memory loads
- 78
- Memory stores
- 84
- SIMD instructions
- 0
- Potentially trapping instructions
- 165
Instruction sites in the binary, not executions, counted by qip.dev’s wasm-counts.