;; unescape_html in hand-written WebAssembly text with 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 is the one from my C entry, written directly so that nothing a compiler adds
;; is left: no stack, no stack pointer, every table at a fixed address.
;; - 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 turns each 64-byte block into a bitmask of its `&`
;; and appends their 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 where they are; 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).
;; - 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.
;; - The entity list is stored packed (6.4 KB for 2,125 names) and unpacked on the first
;; call: see $sym and $init. pack.py, at the end of this file, is the matching packer.
;;
;; Memory map (bytes):
;; 0 packed entity list, then the Windows-1252 table, model rates, UTF-8 marks
;; 6592 ctx: the contexts of the symbol being unpacked; 6608 slot: their model entries
;; 6624 name: the name being unpacked, zero padded
;; 6672 leg_max: longest legacy name starting with two bytes (hashed), or 0
;; 10768 long_slots: hash of a long name -> its number in `longs`, or 0
;; 14864 last: match model, where two characters were last seen
;; 23056 pos: positions of `&` in the current window
;; 39504 hist: every name character unpacked so far
;; 55648 longs: 48-byte records (name[32], value, length) for names of 8 bytes or more
;; 79936 fast: (key, value) entries for names of up to 7 bytes; empty key = all ones
;; 145984 leg: the same for legacy names, keyed with the length in the top byte
;; 150336 len_mask: 32 bytes of 0xFF, then 32 of 0
;; 150400 output, and 262144 bytes into the same buffer:
;; 412544 input, 1048576 bytes and padding
;; Output and input share one buffer, a technique from my earlier entries (4a6e243a and
;; others): a reference grows by at most 1.2x (`≫⃒` is 5 bytes in, 6 out), so the write
;; position stays at least 52429 bytes behind the read position and decoding in
;; place is safe. The bytes before the input also hold the unpacker's model on the first call.
;; A value is its UTF-8 bytes in the low bytes of an i64 and its length in the top byte.
;;
;; Build: wat2wasm unescape.wat -o unescape-wat.wasm
(module
(memory (export "memory") 23 23)
;; Range coder state: the first four bytes of the list are folded into $code here.
(global $range (mut i32) (i32.const -1))
(global $code (mut i32) (i32.const 0xDEE11AE6))
(global $in (mut i32) (i32.const 4))
(global $ulen (mut i32) (i32.const 0))
(data (i32.const 0) "\de\e1\1a\e6\73\31\90\be\3a\8c\cc\da\91\d3\67\29\3c\e4\d7\59\c6\46\88\1f\78\6b\a1\3c\91\75\17\e0\3b\32\52\99\a6\ba\b9\e7\64\5b\5c\85\19\9e\a6\8d\dd\b5\df\5e\54\50\90\2c\6d\0d\64\c2\b1\5f\42\be\ac\b0\b7\b1\0e\d9\5a\7b\7a\89\43\e7\7a\43\ae\25\35\c1\68\c5\9c\c0\91\85\7c\c9\cb\96\45\97\54\78\45\f9\2f\c0\b1\94\59\f4\de\de\57\85\56\55\fb\be\cf\4a\20\69\a2\64\ae\04\9c\b6\20\68\65\29\aa\fc\fe\14\ca\02\4a\df\2a\4d\38\9f\47\01\49\35\5a\9b\32\55\af\3c\9b\a8\c4\9c\ca\20\ad\05\6d\51\1a\65\33\34\95\a3\cb\9c\bb\e9\7f\bf\8e\2c\5b\4c\4f\1b\e9\22\9e\cf\0a\79\3b\92\4b\21\de\e1\52\2a\aa\a3\10\14\f2\c0\28\e8\5c\7d\00\91\2d\ee\1c\46\59\1a\3d\1a\59\1f\e9\ec\3b\3e\92\7a\8b\e4\0f\47\d0\54\a6\62\b7\00\44\12\b6\b3\7e\67\02\bf\59\02\d9\b6\d3\a1\87\4b\19\43\bd\ac\25\07\37\8b\6f\00\bc\69\46\b3\8d\77\e8\38\c7\fa\96\a6\3d\d9\a0\2f\4e\4c\ac\66\f3\01\1e\f8\18\c0\e7\1a\6e\bf\48\c0\61\b3\3d\49\23\4a\93\93\db\bc\8d\73\20\d5\dd\87\15\d8\26\ad\50\4e\af\b5\be\51\ce\a8\8f\a2\46\41\6c\62\7a\79\53\6f\69\28\ad\eb\91\ca\cc\60\3e\d6\de\91\1e\f7\5a\df\fd\2c\2b\24\02\74\40\c3\c3\c2\90\39\f4\9f\b5\23\07\c5\18\b7\cd\47\46\f0\e1\4f\99\06\ea\f5\66\f3\aa\d9\3e\e8\12\27\f3\d6\b5\be\f7\47\1a\dc\cc\58\a1\d7\9a\f2\6e\fc\f7\32\84\da\5f\77\34\da\ed\cd\0f\15\a3\d7\41\36\02\48\7e\e6\ff\89\cc\5c\b6\4a\1a\c6\62\f6\10\95\78\3e\f4\b8\6d\59\b0\a1\6f\25\a2\14\ee\ac\77\98\df\b2\09\09\45\b9\10\82\bf\6e\27\2e\50\ff\ab\d7\f7\a7\1b\c7\8b\d6\a7\7c\98\79\07\0e\df\4f\53\c3\e7\61\30\81\8d\af\25\7d\87\1b\5d\f0\dc\f9\db\36\4d\3c\24\54\fa\21\7a\48\0d\d1\7a\0a\e9\5a\20\4d\95\49\1e\62\e3\0c\c6\b8\eb\b9\24\16\7b\6e\41\bd\6c\0e\0c\11\09\91\a2\70\60\2e\ce\12\43\41\9f\2b\c9\53\84\d3\54\06\05\bc\7d\37\ff\9e\30\fe\b6\ca\8d\e3\c2\ad\d3\79\1a\94\91\72\a8\54\26\79\0e\b5\9a\46\9d\cc\2f\82\56\a2\10\76\7a\46\e6\b0\1b\4e\c3\c3\4c\b1\ad\1d\7e\02\d9\b4\fb\11\62\35\5a\e8\47\3e\de\f2\93\c3\55\19\af\bf\2e\5a\f7\d4\ee\75\2e\3b\99\7d\92\1c\ae\ca\ea\23\3b\ac\39\87\d5\22\ba\12\4f\ff\74\0a\36\03\da\09\eb\24\86\a2\a4\17\46\ec\6c\8b\48\70\86\67\dc\bc\81\eb\7a\06\df\69\96\0b\28\c8\0d\7d\f6\b3\6a\34\e8\02\c0\21\43\52\98\05\c3\64\24\3b\95\62\ec\a2\83\78\7e\85\34\46\f8\74\ae\39\77\43\8b\ea\12\88\97\19\e7\78\e3\56\62\ed\b5\76\4d\a7\ad\dd\bd\84\e0\a5\99\bb\17\32\1e\77\a9\41\99\97\88\93\b9\7d\3d\f6\a3\e4\f2\b8\da\14\96\cc\ca\fd\d8\cf\f6\7d\fb\22\cb\15\83\53\80\f0\57\ed\93\95\59\2a\5f\a9\6d\d9\55\80\43\ab\24\c5\48\de\10\70\ca\09\56\bf\7a\28\59\45\76\20\fd\98\f4\53\3a\a1\65\f5\6e\38\5a\2a\37\39\2d\76\39\1f\87\0b\92\6d\05\49\69\dc\10\20\ef\cc\f3\ba\fd\85\ab\eb\97\f9\d5\1e\1a\b8\1a\4d\6f\fd\a2\b8\65\96\de\5b\2a\25\01\b1\b4\1e\97\d9\83\32\86\8c\8b\36\52\3d\2c\00\e1\b1\8f\47\ad\df\f5\ff\dd\b3\b4\1a\46\34\96\c1\8b\e7\86\75\5f\14\4f\c8\00\b1\18\ce\7f\42\f7\cc\a0\59\a2\13\5a\1e\3f\4c\29\98\7b\61\80\66\02\8c\58\9e\9f\e0\a0\0d\b6\1e\be\54\80\fd\c5\6d\72\05\e0\54\84\73\47\fc\24\42\c7\5e\d8\bd\51\67\1b\3e\66\08\f0\66\0c\15\4c\24\fc\24\6d\6f\ff\3b\74\52\0a\4e\75\99\35\17\d2\66\24\65\b6\9f\11\76\0f\1e\09\ab\d4\40\5c\e1\11\1e\e7\bf\e1\78\c1\9d\d2\ef\bd\a2\03\f0\c9\a0\e6\18\53\b7\0c\a3\76\9a\2b\e7\0d\9d\fb\6a\0b\77\8c\28\5d\0c\60\84\eb\85\12\c7\8b\cd\b6\7f\d7\e4\d0\d7\80\32\e1\cb\34\96\0f\83\e7\db\12\07\14\95\18\b7\2c\14\33\93\2b\a2\95\43\77\3e\79\12\76\59\d8\10\14\e8\23\d8\0a\b4\71\14\60\f2\2f\74\e5\33\ed\0f\11\a4\98\4e\56\f5\b5\90\9a\61\d5\52\9e\0c\b2\aa\0d\4d\f2\98\2a\b6\1d\b6\1a\d6\ea\33\0a\c5\24\4e\ef\ba\fd\9e\92\a4\e0\18\24\78\da\07\c0\bb\78\6f\6d\b2\1b\f4\04\07\88\c5\49\40\f0\ed\8c\f3\76\1d\43\56\1d\55\d5\88\85\77\7a\c3\e2\90\34\63\e0\9a\d8\9b\22\a2\ef\fd\fd\cd\af\62\0f\a6\34\e9\ab\fe\b6\4a\89\c8\d6\5f\d9\b7\9f\da\1f\5c\ac\62\6d\47\73\5f\5c\40\ef\80\fe\39\70\15\41\d7\db\e4\99\bf\76\27\98\70\c8\9b\7d\7a\38\71\1b\a8\4e\d8\f9\27\86\bd\8a\25\98\55\74\39\0d\23\6a\fb\f6\18\08\3e\ec\77\a6\fe\01\d4\31\90\5c\fe\fd\3a\8e\10\85\86\48\ea\2d\a0\3b\d0\99\52\a1\1a\29\d3\76\b7\d6\84\7b\87\ea\bc\9b\3b\3f\8d\65\08\d8\6d\86\68\10\74\f3\4b\73\c1\05\27\36\7a\7c\c9\3a\83\fc\f7\0b\98\1d\fe\7a\e5\19\ee\08\3a\3b\6e\5e\1f\2e\63\36\37\18\0f\19\99\55\06\51\b8\6f\ab\7c\18\e2\39\03\3f\8b\23\c3\6d\13\1b\cd\9a\10\44\7c\07\52\64\6a\8a\23\58\63\c7\8f\4f\72\e6\d7\91\58\a0\be\6a\31\e7\67\e8\ac\5c\47\1d\fc\b4\cc\e0\50\61\2c\16\66\16\66\c5\07\5a\38\f8\32\bb\88\95\76\fa\25\5c\d1\a0\de\70\c7\9a\73\c1\47\8f\36\ec\3f\a2\28\14\96\d9\a3\6d\a0\7b\29\9b\4f\d2\63\b2\c2\ea\f3\93\b5\0d\03\c3\30\6a\36\ec\70\4e\70\8d\93\2e\2b\39\23\37\f2\e4\c9\3c\ad\8f\99\f6\fe\88\5f\e5\40\2b\78\19\c1\21\58\79\09\75\d4\06\1e\3d\f7\26\14\cd\67\5e\c6\da\80\d6\b4\e8\66\ff\b1\1a\b3\06\b7\01\22\f6\e8\ce\7d\b2\fc\25\a4\82\0d\96\25\92\9f\60\8b\c4\19\eb\d7\7d\83\c5\ef\48\55\cb\f9\ac\64\31\ce\0f\a2\99\da\18\39\54\16\7b\3e\b6\92\3f\09\90\e1\46\ca\82\19\84\71\89\2a\ce\73\54\cc\bc\c5\d0\d6\b7\5b\a2\6a\04\25\59\05\4d\fa\d1\08\ea\93\1e\4a\88\2a\b7\ad\8e\c9\92\a9\20\0d\95\e5\21\25\ae\51\f9\6f\63\54\a7\da\45\e6\72\4f\ba\af\98\8b\4f\ff\80\43\04\e6\3f\5e\c2\4d\99\15\88\87\a7\ca\e1\42\eb\1a\a1\0b\7b\3a\5a\5b\91\fc\93\50\12\93\a3\a1\47\7c\d7\19\4b\0e\90\a5\3f\de\be\50\12\99\51\95\8d\9d\98\6c\48\32\24\86\b5\d9\e9\5f\50\b0\2d\8c\84\6d\a4\4e\ee\3c\d2\a5\9e\98\40\5e\8c\8c\b2\7b\ac\45\db\78\17\10\a9\a0\ae\50\88\4f\d8\f5\df\69\eb\a3\8b\f2\ba\a9\55\9e\73\21\b3\61\14\ac\5b\69\b0\68\12\65\94\99\0a\24\fc\9d\0a\9f\fc\aa\22\fb\5b\c8\ec\8f\4d\da\75\7e\f3\d1\4f\47\76\d9\74\e2\e6\8d\00\9c\dd\9e\38\46\1b\24\d1\dd\61\c3\ea\81\84\2a\2a\88\a1\f1\2e\a3\88\25\89\bb\97\5f\d4\24\e7\66\e8\1b\ec\ea\5d\96\4a\f5\4f\7c\43\6a\5a\e6\4d\a8\59\27\7b\5a\86\4d\ad\54\f3\ab\6a\f1\56\7d\c8\7b\4f\df\50\c9\73\3b\2c\85\53\8c\39\c5\6c\75\54\b6\78\71\79\a4\4a\fd\19\fb\b8\1d\de\c9\6e\41\c7\1d\4d\4e\11\7a\43\88\a2\ef\42\d6\28\ba\b7\82\a7\e0\61\88\d7\9d\03\4f\da\df\be\9f\37\5c\7f\fa\b3\1f\b4\ff\2e\0b\11\2f\f5\5b\3a\07\4d\6d\4d\3b\5a\20\d9\a6\34\26\4b\dd\e4\53\3a\e6\d6\e3\86\dd\31\5d\8a\5f\ef\c5\8d\be\48\f8\c3\07\57\33\31\b3\f8\50\3c\d2\bd\63\90\df\63\e4\5e\b1\52\ed\2d\75\d0\d5\b7\cb\a6\ce\bb\d3\46\3d\32\1b\0d\3f\87\89\0f\fa\c3\f0\34\04\d2\ca\8b\b0\fa\ee\a8\c6\7d\d5\18\a3\55\55\06\3b\7f\ce\a2\8b\f5\eb\ed\ba\02\53\f6\f0\2c\ca\75\55\07\d6\9b\9b\c6\97\2b\32\53\58\86\9d\b8\31\32\a9\b0\ac\bd\f6\92\43\b1\d1\2c\b0\7d\5e\d1\28\cd\9a\34\4b\fe\f9\c4\d6\d8\8c\95\4f\5a\a0\45\c0\2d\ce\ee\6f\c1\6f\df\da\51\78\ff\33\10\fb\0b\fc\ca\a9\10\39\f9\ff\3b\a0\98\0a\46\ef\68\94\f4\d2\69\4f\b1\8b\17\fe\90\d1\eb\b5\74\98\29\6d\33\b8\e6\a5\88\d7\97\92\90\bd\67\ac\65\ca\1f\d0\10\0b\23\73\b7\7e\b6\d5\a4\7b\96\58\0e\31\ae\1c\29\87\47\6b\c1\5b\f5\3b\96\dc\97\9f\0c\86\37\d7\fc\f4\52\60\0b\27\64\1b\6c\85\90\85\7e\63\8b\85\fa\04\97\a4\33\ee\c2\0f\28\4f\7a\fe\4c\d9\a3\8e\cb\bd\d2\d7\b7\cc\4d\58\de\49\25\5d\69\49\02\15\59\6b\04\eb\42\d4\f8\24\e6\17\8e\4b\d1\66\96\19\a2\9f\a2\2f\a5\42\a1\5d\96\d1\ed\68\61\25\38\68\fe\50\60\ac\24\09\21\db\7c\cc\06\36\bc\16\5b\f0\e2\e5\c0\12\19\6c\2a\87\6d\9d\1e\a6\82\86\5c\c8\9d\64\67\5f\2b\d3\01\c8\60\b7\94\17\4c\90\3f\2e\ec\b2\61\39\dc\ef\9c\3f\49\2a\fc\9d\e7\b8\17\e4\8e\58\8a\1d\cc\6b\fe\6a\ea\0a\a5\cb\40\b4\57\65\02\67\76\a1\8e\13\fd\3a\ee\d0\af\53\57\66\1f\60\51\36\be\af\35\a2\2e\e2\73\10\46\16\12\92\b6\4c\3c\c2\b8\54\62\de\8b\82\0b\bc\08\82\18\d4\05\ce\14\6f\58\74\1f\dd\7a\5b\e7\93\d5\4e\f3\5c\5e\56\b9\a2\c1\56\65\45\6f\97\f8\e9\bd\15\18\d0\cf\4d\5c\9b\f4\1e\25\06\3d\61\14\8a\7c\75\53\d3\3a\b4\42\d5\1b\12\25\1c\d7\d1\04\3b\be\c7\1d\1f\85\2e\06\bf\57\96\4b\2d\68\e3\7d\f3\27\e4\70\d0\6c\7a\a5\f8\70\99\59\d0\23\e1\85\13\00\e4\92\9b\80\ad\dd\86\1d\4b\00\fe\11\7e\0f\96\e1\25\ef\92\85\db\95\1d\cc\cb\ea\04\00\23\fd\2f\36\f7\a0\08\d3\88\36\f8\c1\bb\b3\9e\bb\e7\38\5b\10\e6\7a\b7\48\87\0b\b1\67\50\6a\98\43\13\ad\95\b2\9a\fe\6a\3d\dc\6a\2c\e8\7a\d3\13\74\af\3f\41\7b\bc\92\92\ed\cc\23\2a\e8\e3\17\16\84\af\34\72\a3\f4\e7\cc\3d\d2\18\39\89\aa\23\93\09\da\5f\c9\e3\8a\45\2c\1c\14\8c\29\4e\2f\ff\56\04\2e\38\c8\8e\4f\f4\5a\41\92\98\c8\f1\8a\af\bd\b3\2c\be\b7\ca\2f\ea\f0\95\55\55\5a\32\93\48\bf\22\62\65\70\12\ae\0c\fc\67\7d\88\90\d0\e9\39\50\e0\49\f1\5c\bf\5f\48\fc\1d\07\e6\77\df\cd\73\80\c1\90\a2\12\8c\c7\00\56\f7\75\1d\98\9e\9c\95\5c\40\4a\af\e3\af\c7\a9\88\29\3c\14\2c\a8\b8\d2\e7\14\b3\1b\3e\b5\dd\64\35\f2\77\ac\28\6d\33\5f\aa\23\23\03\d0\0f\98\a8\50\21\44\37\2a\14\27\0e\cd\eb\a8\91\18\79\b2\0a\ea\5c\26\15\f7\36\cd\9f\a7\38\93\c1\94\78\c8\b2\a0\a5\04\93\9e\ab\0a\bb\5b\f0\5e\ec\84\8e\7c\d2\d9\74\41\7b\8e\36\72\83\75\a0\b8\7a\98\87\1d\1a\7b\d3\9a\29\90\fa\50\28\de\bf\a7\c6\3d\de\d9\99\b2\2b\37\90\97\ee\85\95\8f\ff\fb\97\ba\86\ae\a0\99\44\1e\06\93\30\d1\bf\61\39\c4\2b\56\0b\0f\54\0e\d1\50\8a\8e\52\40\ce\25\24\a8\ed\9f\f0\99\59\24\e4\fc\2f\21\cf\eb\b3\55\b1\f4\22\5b\2d\41\64\08\b8\ae\d4\fb\a5\12\8c\1c\3d\77\9f\e9\a0\26\13\e7\a3\d4\89\5e\87\f2\e3\c1\1c\2c\51\0e\7d\c3\95\2e\5c\1b\02\f3\0b\92\b3\df\39\17\3d\61\8e\00\8e\d4\31\8d\5a\a5\f3\3b\4a\0b\4d\2a\87\1e\22\78\1a\ad\1a\9f\d8\71\cf\4f\11\16\a0\33\4c\4a\ab\00\d6\17\4b\c0\55\3b\0d\8f\e4\8c\fc\ce\dc\9f\a4\fc\ca\97\53\02\51\ad\83\78\49\86\aa\e2\5d\f8\e4\6d\6b\25\9d\19\ee\98\8f\b5\df\0c\d1\49\c4\76\b4\84\d0\48\e4\43\ac\0b\6a\0d\7f\b4\df\72\f2\3f\91\f2\54\55\ea\95\a6\4f\9b\8c\b8\de\05\36\6f\bf\33\26\8a\d0\e9\8b\c8\23\7b\36\fd\6b\f5\e4\59\e8\95\65\a1\4f\30\91\5a\7a\9f\d7\6e\8a\a5\38\8f\0b\e5\fe\d5\31\e7\1a\e0\8a\96\7f\19\01\e7\ec\19\59\52\8a\75\8c\c7\ef\fe\8c\2c\69\c2\72\cc\f9\c7\36\8e\33\71\1a\1c\69\ef\b1\87\7f\9f\92\14\81\0e\fa\dc\13\15\d0\1f\30\e7\61\c2\7b\49\37\8c\0c\37\79\20\02\37\6c\44\bf\ce\bb\03\c1\84\68\e6\3d\a9\96\a4\ea\94\4f\4f\4a\f6\50\7a\3d\3c\1a\8e\73\7e\5d\3e\5c\4b\7f\3f\f7\b9\b8\ad\58\9f\9b\e0\9b\56\50\72\36\7b\96\eb\76\e3\ea\de\11\60\8a\26\1b\9f\17\ea\aa\df\b3\60\80\a2\df\28\0e\bc\fe\46\2c\21\2d\ab\a8\34\bb\49\46\7b\09\c0\36\d4\3c\66\b1\c2\48\85\dd\21\bb\05\72\05\a0\9f\2c\49\c2\aa\1e\8b\45\eb\b2\53\f3\39\bd\92\5e\06\1e\b7\21\4c\f0\a3\84\50\9b\ee\3e\4d\f2\02\bd\4e\9e\59\88\77\e5\cb\c7\3a\0b\2a\59\78\cf\b3\59\5b\7d\6d\bd\c8\8c\73\73\49\1c\5a\ee\11\66\78\6f\0b\41\7f\44\5d\83\74\3b\5c\ec\17\fc\30\69\29\0d\ce\cc\0a\81\37\c9\6f\ac\50\eb\4f\85\3f\19\df\19\86\1b\45\8d\9e\75\c9\9e\c3\ab\f0\6a\e4\be\56\a1\21\63\71\7f\fc\67\91\0f\db\2b\74\1b\20\e1\ff\60\5f\6b\47\59\25\73\2d\cc\72\cf\ed\a8\de\64\c3\fd\42\0b\f3\2f\a5\d1\be\72\6e\2d\b1\c6\ef\48\20\05\ec\db\c4\87\22\d6\a2\92\dd\90\cd\fc\d9\4a\47\00\32\11\58\27\1a\74\e0\92\77\89\6e\32\34\fe\93\a3\08\b7\8c\23\be\7a\a6\fa\9e\c4\f2\b5\53\bb\0e\92\2a\69\a8\cf\93\fe\12\e1\77\da\5f\f2\9f\d2\a1\7e\4b\44\02\91\11\a7\90\55\b5\1c\b7\d6\04\56\f3\e3\ea\96\e4\21\d4\8c\c6\76\cd\06\ee\c0\fa\08\e9\89\6b\04\9c\47\4a\60\db\67\27\09\90\e3\3e\cc\15\cf\85\7d\e6\8e\54\18\db\97\5f\85\4a\34\dc\a3\f0\5c\0e\e2\4a\7f\84\72\be\fd\c3\d7\bf\64\2a\cf\b3\50\77\8d\eb\5d\6d\97\61\22\a4\e8\9d\c2\67\1c\b1\45\21\69\bc\ff\0d\f2\0b\2b\34\eb\b2\cb\20\1b\73\9b\a4\00\36\43\d0\79\52\f3\68\de\d8\79\fd\0b\bb\de\90\4e\2b\ea\a4\5f\18\dd\f8\52\7b\f7\d8\9b\08\13\7e\9c\e2\cf\83\bf\cc\8c\f0\88\b0\cb\0d\cd\6c\9a\38\29\55\57\bf\74\17\93\4e\b2\8f\52\37\68\71\79\f2\b9\6a\48\57\6a\82\bf\58\16\cc\36\02\12\ec\0e\1d\25\b9\95\ea\91\cb\e5\64\97\8d\9e\4d\57\0d\8c\5a\10\77\eb\34\23\72\c7\83\a4\34\ee\09\0a\f4\b4\75\5f\72\64\74\09\cf\22\f4\a4\8d\73\03\ca\de\3e\d1\aa\ab\92\99\95\7d\61\6a\56\09\b5\01\85\c8\d9\58\b0\ca\23\7c\b8\a1\15\4c\80\f3\15\ad\c8\0c\01\f8\a7\77\a4\05\b1\69\91\4f\b4\e6\2c\d2\b9\c3\e8\b5\31\39\6a\d5\e8\f9\0a\8a\e7\90\81\7c\4f\ae\52\ba\27\c0\60\f8\06\ca\b2\b2\de\ab\3d\e4\09\bf\4b\13\c6\b4\ec\09\7a\50\45\f9\ba\95\75\05\c0\f7\4a\43\b5\fe\c9\98\ea\45\4c\e6\52\59\c8\4d\4c\04\17\88\5f\5c\b9\4c\e5\98\40\b5\02\f9\68\31\e6\39\99\26\fd\57\76\31\53\67\41\02\5a\81\07\65\a4\08\93\a2\9a\56\0e\e5\3f\8e\ae\60\ee\d5\1d\33\55\09\e4\dd\eb\84\ea\11\8c\d3\0a\d2\0b\71\cf\aa\6f\ea\2a\84\9a\47\76\3a\5f\6c\1b\11\92\aa\49\68\ad\b4\d7\47\f3\c2\96\e7\fa\22\74\d6\ed\c7\6f\1f\c7\cc\3b\e5\24\f2\43\5e\14\ae\3c\7c\40\73\93\1c\5c\7d\6c\60\1b\ea\fa\2f\d1\83\c1\07\b1\01\be\56\cf\1f\7d\ab\41\e2\71\88\bc\b1\93\6e\dd\3e\71\07\be\66\83\81\81\16\fa\a8\a5\73\23\da\91\20\c6\4f\af\ca\b8\c8\12\7b\ff\53\74\a6\e4\6f\c5\4e\50\45\d0\59\26\14\73\a8\82\30\d0\e5\df\4f\83\2b\9a\bb\a7\ac\08\cd\4a\f2\6a\9d\6c\e5\34\74\2e\f9\e5\fb\36\46\8e\f6\10\44\9f\8c\7c\78\4b\f8\52\91\6c\8e\6a\28\f1\44\b6\10\4c\fc\64\f1\39\6c\42\05\38\bf\5b\5f\27\3e\6e\7a\92\9a\cd\8e\26\46\34\53\db\fe\de\0f\b7\58\97\16\23\aa\b2\2a\36\0a\cd\5c\11\31\a9\1d\d0\32\32\fa\60\cc\8a\69\de\57\dd\9e\08\6c\f0\8e\bb\83\4c\54\ea\12\2c\7e\2a\10\f3\4a\db\b6\ab\50\e4\15\91\10\f4\7d\ac\0b\26\d9\12\10\fb\96\68\02\10\87\29\60\60\bb\63\7b\66\1b\8b\ab\fb\db\9f\f7\d7\cc\0c\85\eb\03\df\11\28\08\7b\06\67\b7\30\88\7e\94\69\26\04\b4\aa\05\a9\89\de\3a\6f\68\4c\a2\6d\c1\d3\19\62\4c\5d\2e\6a\6d\60\41\44\42\e4\b6\69\5e\d6\54\68\3f\63\76\c7\09\a0\e6\c6\92\a3\58\63\d8\ba\22\9a\e7\44\6c\67\a2\88\77\06\ec\b5\b3\47\ab\da\4c\9a\a6\7f\1d\8a\7c\c4\71\59\2e\70\d0\50\a0\b1\75\ba\d6\56\6f\62\c3\82\aa\d7\2c\ef\cb\cb\02\81\e8\83\0e\a7\25\6d\56\61\d8\4d\d2\58\9f\ed\ce\e3\95\5d\81\db\b3\af\32\2a\a7\0d\ca\1b\04\9c\a6\6c\8b\05\cc\db\70\0a\26\6d\c0\b2\57\2a\9e\54\61\cf\06\e9\a8\70\33\57\7c\75\f7\51\0d\3a\1b\f8\17\3a\57\e0\c8\4b\5f\98\f4\15\78\1f\a2\cb\44\e5\a1\19\76\1e\2c\dd\76\9c\5f\ef\e8\9e\f7\c8\4a\bc\dd\75\1d\10\65\85\17\d5\8b\c0\88\0f\ea\5e\61\89\d5\90\01\83\8c\7e\ec\be\03\03\d0\7f\49\0a\4d\e2\f3\c3\ba\b4\e6\92\fa\c6\27\09\22\1e\d3\e3\f6\39\11\62\1a\96\9a\18\a1\75\72\f0\72\6d\cd\d3\34\f8\03\e8\1c\43\3d\16\c3\bb\0c\81\b6\e6\7e\6d\89\c2\22\c5\39\68\db\99\ea\1b\58\7a\e9\08\d3\c8\67\51\6b\49\34\37\aa\7c\d8\71\b4\8d\3b\ac\8e\6c\84\07\e4\c2\16\c9\98\80\39\03\d4\2d\fe\8f\2d\af\2d\10\c7\52\de\bc\0b\2b\75\2e\31\c3\d0\9f\75\b3\c2\ab\d3\b9\c5\fe\62\3e\fd\13\2e\b4\2f\96\09\d8\8d\3e\fc\e5\b1\bd\8e\ab\f7\7e\94\65\6e\01\fa\cf\95\f9\76\d7\5f\35\32\ee\82\19\3a\e8\3a\0f\db\a9\c9\f6\f3\34\b9\e9\2b\0a\8f\bd\a5\e0\d2\69\f7\0b\d0\1d\2d\67\56\d2\cf\9f\0b\97\a1\4f\13\40\70\44\50\fa\5f\77\d1\73\56\5c\7e\ac\17\e3\6f\20\97\54\c4\e1\62\fa\41\e3\82\f6\77\24\23\11\9c\84\0c\6a\82\a6\4e\d4\5e\5f\69\82\d1\1e\30\87\fd\ac\85\b7\d5\40\44\bb\ae\b2\71\f2\98\23\7a\1b\49\86\2b\64\86\b8\07\26\41\2c\f4\38\cd\cb\23\71\5a\cb\c9\78\83\a1\ef\55\2b\29\67\1e\9b\69\52\94\ad\72\21\e8\67\56\32\ff\b1\f3\29\61\2c\1d\55\e8\75\9c\0b\91\0b\9d\04\c2\42\60\a3\2a\ba\67\fd\2d\c4\8e\e3\33\cc\fa\df\25\08\e1\06\bb\f9\45\38\d1\2a\ab\99\56\db\73\07\81\ba\51\66\12\af\af\68\eb\a8\8c\e9\af\2a\45\14\07\23\b8\b0\c3\e4\1e\a9\8f\02\5f\98\13\c6\19\68\b7\a6\0d\b0\41\da\2f\65\88\7a\81\b8\a1\2d\5a\90\4b\b4\e9\86\41\70\62\df\f3\f4\49\e1\12\0b\d9\bc\fe\c6\7f\ee\53\70\a1\b3\e7\bb\5b\99\11\84\a3\1b\12\d2\bd\96\e2\f3\b2\a4\a0\2e\c0\ce\8d\a3\ea\36\39\ff\55\e8\7b\7a\3a\16\3c\73\7b\ee\c7\74\90\68\00\80\6f\80\c4\fb\7d\42\1e\ca\90\ff\fc\03\cc\73\bb\d5\f9\e8\49\1a\9f\05\d0\59\75\c3\83\56\ff\65\4e\e2\b3\6e\8f\ab\39\ef\41\eb\c3\b2\81\d1\26\ed\74\01\0b\a7\9a\07\34\bc\aa\54\1f\7f\9d\a8\f4\7a\21\0e\43\fd\c0\b7\da\18\58\7d\2d\7b\9e\74\1d\69\18\20\93\bc\9b\18\c0\e1\7a\3b\9a\fd\0f\5a\8e\a3\82\d2\e9\b4\df\40\ca\3d\68\0a\7d\ed\46\7c\fc\b9\3d\8c\ac\c5\2e\ac\ba\38\98\14\96\88\3d\52\a7\4a\1d\f4\7c\9a\04\2b\c7\61\15\69\6c\a6\67\38\09\46\1d\22\78\21\44\50\3e\ee\f4\59\85\f7\24\6c\01\ca\8b\c1\7d\c2\65\9a\d6\e0\b1\df\b9\3c\0e\43\04\4c\e6\69\f5\fa\12\98\d1\b1\b7\c9\92\ab\c7\13\11\3c\f4\48\68\d8\34\a2\2f\64\0b\89\a9\0e\97\38\16\7f\89\94\bc\ee\93\96\a8\b3\e4\0f\26\44\93\1e\99\e8\f7\5f\50\dd\da\13\24\ae\6b\53\19\16\83\80\7d\ad\1f\8a\80\40\16\eb\de\b3\4c\a0\25\4f\a3\bb\6e\7f\83\36\e5\04\cf\bc\05\b5\13\0b\2b\c4\e2\fc\06\c4\75\4b\a8\76\04\46\9b\c7\aa\bc\ee\c5\79\05\82\64\68\4d\5e\97\b3\25\f5\d3\8a\86\40\8c\b5\a3\79\3c\da\e2\a9\65\dc\4c\dc\34\6d\7a\de\26\a2\a1\e0\02\9d\dd\c2\d1\77\05\09\bf\51\fd\83\5c\40\06\a2\65\05\53\5e\a1\33\c4\24\73\63\92\00\cd\4c\7a\ae\de\b4\e6\22\22\18\38\88\27\74\23\c4\9b\29\80\ab\be\3f\11\97\6e\9a\53\b4\3d\16\a8\83\45\ea\7e\b4\de\39\3d\42\e2\69\af\be\24\4d\61\87\f2\a4\93\62\cf\c8\eb\15\25\aa\0b\bf\5f\9c\c2\65\77\b1\2d\62\63\81\1a\ab\c2\ea\2a\35\4a\21\0a\ef\aa\cd\09\95\b3\dc\13\f4\51\26\cc\28\0c\d4\1b\77\36\cc\13\72\5e\5b\ec\8c\b7\30\5c\6b\cc\89\73\e4\0f\41\cf\78\1e\75\ad\f1\8c\5c\23\26\00\ae\c8\55\3c\b9\f0\18\29\8e\d7\30\be\86\28\bb\52\6e\2e\e0\09\8c\93\b2\8e\6c\0f\a6\fd\51\d7\20\d4\16\a0\c4\c1\62\01\51\6d\e4\2f\41\33\3b\d0\9a\51\7e\4b\bb\30\b5\a9\5a\af\75\1f\bc\3f\f9\fb\f1\4c\43\21\27\89\24\20\d3\a3\1c\44\21\98\74\e3\79\3d\d9\29\69\68\17\d9\0a\45\6a\a1\f4\e1\87\78\fe\76\10\a2\ea\7e\23\50\35\01\12\74\61\59\2d\ab\da\83\e0\ca\73\c8\3a\12\8f\a0\7b\3c\eb\1e\5d\2d\6c\1a\28\5c\9d\49\dd\8e\d1\d6\75\a8\49\11\92\44\d5\87\54\64\c9\0c\2a\a3\6d\2c\ce\51\d4\b5\99\3e\af\be\ac\a7\f2\21\38\75\46\a0\ef\9f\97\dd\be\54\ea\bb\21\9e\21\40\f6\1a\5f\6d\3a\a5\6f\fe\fb\2d\81\62\36\20\bc\b7\92\16\5d\ca\5a\b8\ec\df\e8\78\16\d3\54\f6\d6\d0\d2\8d\48\bb\fb\57\2b\50\d1\9d\a2\31\fb\cb\56\97\d6\53\44\86\7d\f5\8d\95\1b\ee\fd\c1\1e\7d\1f\68\bb\9d\21\f4\c7\2e\8d\a8\97\b3\71\54\f8\4e\08\b7\86\57\78\c7\6e\0d\69\e6\3b\84\e2\ad\c3\fc\2f\76\8e\d1\4f\fb\cd\60\a8\42\fe\91\49\fc\f2\82\28\b7\96\25\70\23\69\7b\17\da\ba\23\ad\b9\be\9a\b4\e9\60\bc\a7\36\41\9b\cd\6f\1b\67\fb\ab\76\f6\86\80\f7\db\fe\84\8f\eb\d4\6c\9b\06\c3\86\d2\b5\43\0a\cf\e6\a8\97\3d\e0\31\20\d7\88\68\2a\30\c3\48\4d\d2\8b\b7\43\9c\f7\21\c5\e3\af\7e\ef\76\b2\f7\bf\ed\a8\7b\69\34\4e\e5\43\df\e4\3e\87\fa\10\5d\c5\c9\14\ab\b1\d2\1b\83\2f\3e\ff\51\a4\94\4f\c2\bd\0f\d0\fa\6a\ba\de\a4\fd\4f\b7\2e\ed\fe\8c\dc\bb\90\fd\53\85\e2\3e\d5\78\63\78\57\9f\f4\50\c8\65\cb\2b\50\3d\4d\52\8b\ba\c5\d5\02\bf\ff\af\f6\90\6c\03\d7\11\68\19\68\3f\30\b6\08\bb\f5\cc\ae\50\0f\46\1f\83\d4\22\03\67\e1\60\57\93\f8\a8\d5\9d\c4\7d\3a\8f\5e\b0\f0\e4\e4\a4\e2\ba\d5\ce\59\7a\39\10\be\da\64\e1\9f\c5\d7\9f\c4\3e\39\82\8f\36\41\fc\04\aa\d1\03\e2\80\88\ed\08\3c\62\17\29\1a\cd\93\02\8f\a2\54\8f\4c\2f\93\d4\57\73\6c\2c\fd\d5\12\a5\e8\4c\39\02\0d\35\e5\20\fb\9a\c4\8a\9d\54\95\64\0e\f9\3c\a2\f6\c2\28\42\01\a5\a2\d3\5a\2f\e7\eb\be\39\5e\eb\d9\6d\00\8d\60\07\4d\5e\cc\97\cc\02\44\33\ea\9a\6b\7f\af\e7\71\49\3f\6c\09\30\c5\e5\02\80\c7\af\a9\cb\ae\00\e0\93\cc\b5\e6\d9\d4\c2\f7\cf\91\4c\56\bd\bd\9d\cb\54\83\05\db\1a\60\92\dc\b4\df\67\6f\91\53\12\25\16\0d\1b\29\a9\97\96\c2\7b\8b\20\3e\62\3f\05\58\81\44\39\51\72\20\f6\b6\86\ab\76\08\71\73\b0\fd\17\12\d7\90\8f\66\77\33\ad\df\f1\a9\84\38\3f\dc\7d\7d\a2\9f\84\07\ab\b9\e0\75\88\74\6f\7e\08\af\2f\34\8b\ec\9d\51\1d\28\14\9f\c5\cd\22\a8\51\5e\2b\79\1c\da\0c\51\f3\15\69\d8\e7\d8\ab\0d\a2\3e\90\24\47\a0\de\10\25\5a\a4\c0\fc\6a\b8\34\80\e1\f1\35\f1\cc\99\09\2e\21\0e\f5\77\60\b3\3d\56\8a\93\da\b3\79\e8\02\fc\60\4e\db\56\01\ce\50\f8\1c\7c\76\42\1d\40\cf\5a\20\25\62\88\7d\69\87\ec\fb\a9\cc\94\41\e6\18\dc\87\5c\00\2f\46\97\be\4b\de\24\31\1e\5a\75\ba\ed\3b\80\f4\b3\35\57\7a\2a\56\87\aa\3a\69\4a\6f\a7\38\18\3e\fa\6b\d1\a3\1d\53\8d\28\6e\34\30\15\bb\8a\1f\35\ef\7f\a3\f8\82\08\f2\b5\d2\bc\74\d7\b5\94\29\d9\a7\a9\70\cf\71\04\40\e2\2e\b5\f4\af\75\75\a4\f6\0f\1a\b0\0c\ca\fc\40\15\9c\9e\87\26\6c\83\b0\60\f1\41\43\ab\46\34\0a\6d\f6\5b\78\27\19\02\b8\5c\40\94\fe\ad\65\cc\ba\0e\e5\10\6d\55\5d\4e\8f\85\43\fe\51\d2\d5\83\08\61\9a\0e\a6\92\70\58\d6\09\c7\bd\9e\71\a7\c7\8c\36\c9\08\92\ca\3a\1a\99\2d\02\4c\a4\64\21\ba\b1\3c\59\d0\62\18\ae\f6\97\7d\c7\7e\d0\4f\b2\74\f4\51\50\b1\67\f3\fc\45\c0\88\97\b1\13\b2\58\0b\04\e2\b9\27\70\47\f3\a7\46\4b\e9\90\50\1c\b2\c1\2c\2c\54\6e\b2\70\50\df\bc\88\fe\c0\b9\58\b5\1d\2e\82\61\a5\9c\0b\e0\4e\f2\30\c7\ba\05\ae\89\b6\99\b5\6e\b4\06\09\bc\fd\c9\fe\00\22\39\04\92\52\11\60\c5\27\1e\e8\75\a8\55\67\56\8d\1b\d4\40\44\7d\4e\bf\c2\d7\0f\e5\16\7a\6e\37\93\ec\89\bd\dd\2f\8f\7f\31\f4\34\ed\ca\92\95\59\f1\f3\4e\ee\57\48\1b\55\49\61\da\71\01\50\ea\09\16\f2\96\51\3b\24\ae\5b\f2\2e\46\ba\cd\58\19\54\cf\93\bf\c7\47\c6\4b\ed\a8\59\08\c9\71\55\7e\af\84\7c\15\a9\54\01\07\ad\ba\ca\2d\80\aa\b5\bc\7a\b2\8a\04\d9\29\b7\e7\1e\ce\a7\06\2c\d9\6f\b5\2b\4a\10\19\47\f2\45\b9\a5\08\89\b3\1d\f2\ff\aa\6e\24\6d\51\95\e9\d6\13\79\bf\bf\5f\24\0f\08\8a\1e\00\ac\20\81\00\1a\20\92\01\1e\20\26\20\20\20\21\20\c6\02\30\20\60\01\39\20\52\01\8d\00\7d\01\8f\00\90\00\18\20\19\20\1c\20\1d\20\22\20\13\20\14\20\dc\02\22\21\61\01\3a\20\53\01\9d\00\7e\01\78\01\aa\aa\66\66\24\49\e3\38\8b\2e\62\27\c0\80\00\00\e0\80\80\00\f0\80\80\80")
(func (export "input_ptr") (result i32) (i32.const 412544))
(func (export "input_utf8_cap") (result i32) (i32.const 1048576))
(func (export "output_utf8_cap") (result i32) (i32.const 1258298))
;; A code point as UTF-8 bytes in a word, low byte first; their count goes to $ulen.
;; The bits are laid out as four bytes, then the unused leading ones are shifted out.
(func $utf8 (param $v i32) (result i32)
(local $n i32)
(global.set $ulen (local.tee $n
(i32.add (i32.add (i32.add (i32.const 1)
(i32.gt_u (local.get $v) (i32.const 0x7F)))
(i32.gt_u (local.get $v) (i32.const 0x7FF)))
(i32.gt_u (local.get $v) (i32.const 0xFFFF)))))
(if (result i32) (i32.eq (local.get $n) (i32.const 1))
(then (local.get $v))
(else (i32.or
(i32.shr_u
(i32.or (i32.or (i32.or
(i32.shr_u (local.get $v) (i32.const 18))
(i32.shl (i32.and (i32.shr_u (local.get $v) (i32.const 12)) (i32.const 0x3F)) (i32.const 8)))
(i32.shl (i32.and (i32.shr_u (local.get $v) (i32.const 6)) (i32.const 0x3F)) (i32.const 16)))
(i32.shl (i32.and (local.get $v) (i32.const 0x3F)) (i32.const 24)))
(i32.sub (i32.const 32) (i32.shl (local.get $n) (i32.const 3))))
(i32.load offset=6564 (i32.shl (local.get $n) (i32.const 2)))))))
;; Unpacks one symbol of $nbits bits with an adaptive binary range coder (the LZMA one).
;; ctx holds $nctx4 / 4 contexts; each bit is predicted by mixing their model entries.
;; An entry is 16 bits: a 12-bit probability (stored XOR 0x800, so zeroed memory means
;; one half) above a 4-bit count of how often it was used.
(func $sym (param $nctx4 i32) (param $nbits i32) (result i32)
(local $node i32) (local $top i32) (local $k i32) (local $s i32) (local $e i32)
(local $r i32) (local $num i32) (local $den i32) (local $bit i32)
(local.set $node (i32.const 1))
(local.set $top (i32.shl (i32.const 1) (local.get $nbits)))
(loop $bits
(local.set $num (i32.const 0))
(local.set $den (i32.const 0))
(local.set $k (i32.const 0))
(loop $vote
(i32.store offset=6608 (local.get $k) (local.tee $s
(i32.and (i32.shr_u
(i32.mul
(i32.add (i32.load offset=6592 (local.get $k)) (i32.mul (local.get $node) (i32.const 0x2545F491)))
(i32.const 0x9E3779B1))
(i32.const 14)) (i32.const -2))))
(local.set $r (i32.shr_u (local.tee $e (i32.load16_u offset=150400 (local.get $s))) (i32.const 4)))
;; Weigh a context by its order, how often it was seen and how sure it is.
(local.set $e (i32.shl
(i32.mul
(i32.and (local.get $e) (i32.const 15))
(i32.add (i32.const 1) (i32.shr_u
(select (local.get $r) (i32.sub (i32.const 0x1000) (local.get $r))
(i32.lt_u (local.get $r) (i32.const 0x800)))
(i32.const 8))))
(i32.shr_u (local.get $k) (i32.const 2))))
(local.set $num (i32.add (local.get $num)
(i32.mul (i32.xor (local.get $r) (i32.const 0x800)) (local.get $e))))
(local.set $den (i32.add (local.get $den) (local.get $e)))
(br_if $vote (i32.lt_u (local.tee $k (i32.add (local.get $k) (i32.const 4))) (local.get $nctx4))))
;; $r: 12-bit probability that the bit is 1, never 0.
(local.set $r (if (result i32) (local.get $den)
(then (i32.div_u (local.get $num) (local.get $den)))
(else (i32.const 0x800))))
(local.set $r (i32.mul (i32.shr_u (global.get $range) (i32.const 12))
(select (local.get $r) (i32.const 1) (local.get $r))))
(if (local.tee $bit (i32.lt_u (global.get $code) (local.get $r)))
(then (global.set $range (local.get $r)))
(else
(global.set $code (i32.sub (global.get $code) (local.get $r)))
(global.set $range (i32.sub (global.get $range) (local.get $r)))))
(loop $norm
(if (i32.lt_u (global.get $range) (i32.const 0x1000000)) (then
(global.set $range (i32.shl (global.get $range) (i32.const 8)))
(global.set $code (i32.or (i32.shl (global.get $code) (i32.const 8)) (i32.load8_u (global.get $in))))
(global.set $in (i32.add (global.get $in) (i32.const 1)))
(br $norm))))
;; Move each entry toward the bit just seen, by 2 / (2n + 3) after n uses.
(local.set $k (i32.const 0))
(loop $learn
(local.set $r (i32.xor (i32.shr_u
(local.tee $e (i32.load16_u offset=150400 (local.tee $s (i32.load offset=6608 (local.get $k)))))
(i32.const 4)) (i32.const 0x800)))
(local.set $e (i32.and (local.get $e) (i32.const 15)))
(i32.store16 offset=150400 (local.get $s) (i32.or
(i32.shl
(i32.xor
(i32.add (local.get $r) (i32.shr_s
(i32.mul
(i32.sub (i32.shl (local.get $bit) (i32.const 12)) (local.get $r))
(i32.load16_u offset=6560 (i32.shl (local.get $e) (i32.const 1))))
(i32.const 16)))
(i32.const 0x800))
(i32.const 4))
(i32.add (local.get $e) (i32.lt_u (local.get $e) (i32.const 5)))))
(br_if $learn (i32.lt_u (local.tee $k (i32.add (local.get $k) (i32.const 4))) (local.get $nctx4))))
(br_if $bits (i32.lt_u
(local.tee $node (i32.add (i32.shl (local.get $node) (i32.const 1)) (local.get $bit)))
(local.get $top))))
(i32.sub (local.get $node) (local.get $top)))
;; Unpacks the entity list into the lookup tables. Entities are ordered by code point, so
;; a value is a small step from the one before. A name is coded character by character
;; from 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.
(func $init
(local $r i32) (local $cp i32) (local $nl i32) (local $hn i32) (local $d i32) (local $vn i32)
(local $legacy i32) (local $n i32) (local $h i32) (local $mp i32) (local $ml i32) (local $c i32)
(local $ep i32) (local $val i64) (local $key i64)
;; Empty keys in fast and leg, and the 0xFF half of len_mask, in one fill.
(memory.fill (i32.const 79936) (i32.const 255) (i32.const 70432))
(local.set $r (i32.const 2125))
(local.set $hn (i32.const 1))
(loop $entity
;; Step from the previous code point: its bit length, then the bits below the top one.
(i32.store (i32.const 6592) (i32.const 1048576))
(if (i32.gt_u (local.tee $d (call $sym (i32.const 4) (i32.const 5))) (i32.const 1)) (then
(i32.store (i32.const 6592) (i32.add (i32.const 2097152) (local.get $d)))
(local.set $d (i32.add
(i32.shl (i32.const 1) (local.tee $d (i32.sub (local.get $d) (i32.const 1))))
(call $sym (i32.const 4) (local.get $d))))))
(local.set $val (i64.extend_i32_u (call $utf8
(local.tee $cp (i32.add (local.get $cp) (local.get $d))))))
(local.set $vn (global.get $ulen))
;; A few values have a second code point.
(i32.store (i32.const 6592) (i32.add (i32.const 3145728) (i32.eqz (local.get $d))))
(if (call $sym (i32.const 4) (i32.const 1)) (then
(i32.store (i32.const 6592) (i32.const 4194304))
(local.set $val (i64.or (local.get $val) (i64.shl
(i64.extend_i32_u (call $utf8 (call $sym (i32.const 4) (i32.const 16))))
(i64.extend_i32_u (i32.shl (local.get $vn) (i32.const 3))))))
(local.set $vn (i32.add (local.get $vn) (global.get $ulen)))))
(local.set $val (i64.or (local.get $val)
(i64.shl (i64.extend_i32_u (local.get $vn)) (i64.const 56))))
(i32.store (i32.const 6592) (i32.add (i32.const 5242880) (i32.lt_u (local.get $cp) (i32.const 256))))
(local.set $legacy (call $sym (i32.const 4) (i32.const 1)))
;; Names use a 6-bit alphabet: 0 ends the name, then digits, capitals, small letters.
(memory.fill (i32.const 6624) (i32.const 0) (i32.const 40))
(local.set $n (i32.const 0))
(local.set $h (i32.const 0))
(local.set $ml (i32.const 0))
(loop $char
(i32.store (i32.const 6592) (i32.add (i32.const 8388608) (i32.and (local.get $h) (i32.const 63))))
(i32.store (i32.const 6596) (i32.add (i32.const 9437184) (i32.and (local.get $h) (i32.const 4095))))
(i32.store (i32.const 6600) (i32.add (i32.add (i32.const 13631488)
(i32.shl (select (i32.load8_u offset=39504 (local.get $mp)) (i32.const 0) (local.get $ml)) (i32.const 4)))
(select (local.get $ml) (i32.const 3) (i32.lt_u (local.get $ml) (i32.const 3)))))
(i32.store (i32.const 6604) (i32.add (i32.const 10485760) (i32.and (local.get $h) (i32.const 0x3FFFF))))
(local.set $c (call $sym (i32.const 16) (i32.const 6)))
(if (i32.and (i32.ne (local.get $ml) (i32.const 0))
(i32.eq (i32.load8_u offset=39504 (local.get $mp)) (local.get $c)))
(then
(local.set $ml (i32.add (local.get $ml) (i32.const 1)))
(local.set $mp (i32.add (local.get $mp) (i32.const 1))))
(else (local.set $ml (i32.const 0))))
(i32.store8 offset=39504 (local.get $hn) (local.get $c))
(local.set $hn (i32.add (local.get $hn) (i32.const 1)))
(if (local.get $c) (then
(i32.store8 offset=6624 (local.get $n) (i32.add (local.get $c)
(select (i32.const 47) (select (i32.const 54) (i32.const 60) (i32.lt_u (local.get $c) (i32.const 37)))
(i32.lt_u (local.get $c) (i32.const 11)))))
(local.set $h (i32.or (i32.shl (local.get $h) (i32.const 6)) (local.get $c)))
(if (i32.ge_u (local.tee $n (i32.add (local.get $n) (i32.const 1))) (i32.const 2)) (then
(local.set $c (i32.load16_u offset=14864
(local.tee $ep (i32.shl (i32.and (local.get $h) (i32.const 4095)) (i32.const 1)))))
(if (i32.and (i32.eqz (local.get $ml)) (i32.ne (local.get $c) (i32.const 0))) (then
(local.set $mp (local.get $c))
(local.set $ml (i32.const 1))))
(i32.store16 offset=14864 (local.get $ep) (local.get $hn))))
(br $char))))
(if (i32.le_u (local.get $n) (i32.const 7))
(then
;; fast: the key is the name and its `;`.
(local.set $key (i64.or (i64.load (i32.const 6624))
(i64.shl (i64.const 59) (i64.extend_i32_u (i32.shl (local.get $n) (i32.const 3))))))
(local.set $ep (i32.shl (i32.wrap_i64 (i64.shr_u
(i64.mul (local.get $key) (i64.const 0xA59D054B12F5B905)) (i64.const 52))) (i32.const 4)))
(loop $probe
(if (i64.ne (i64.load offset=79936 (local.get $ep)) (i64.const -1)) (then
(local.set $ep (i32.add (local.get $ep) (i32.const 16)))
(br $probe))))
(i64.store offset=79936 (local.get $ep) (local.get $key))
(i64.store offset=79944 (local.get $ep) (local.get $val))
(if (local.get $legacy) (then
;; leg: the length is part of the key, so a NUL after a shorter name cannot match.
(local.set $key (i64.or (i64.load (i32.const 6624))
(i64.shl (i64.extend_i32_u (local.get $n)) (i64.const 56))))
(local.set $ep (i32.shl (i32.wrap_i64 (i64.shr_u
(i64.mul (local.get $key) (i64.const 0xF880D97D1854E551)) (i64.const 56))) (i32.const 4)))
(loop $probe
(if (i64.ne (i64.load offset=145984 (local.get $ep)) (i64.const -1)) (then
(local.set $ep (i32.add (local.get $ep) (i32.const 16)))
(br $probe))))
(i64.store offset=145984 (local.get $ep) (local.get $key))
(i64.store offset=145992 (local.get $ep) (local.get $val))
(if (i32.lt_u
(i32.load8_u offset=6672 (local.tee $ep (i32.shr_u
(i32.mul (i32.load16_u (i32.const 6624)) (i32.const 0x9E3779B1)) (i32.const 20))))
(local.get $n))
(then (i32.store8 offset=6672 (local.get $ep) (local.get $n)))))))
(else
;; longs: record number $nl (from 1) is at 55600 + 48 * $nl.
(memory.copy
(i32.add (i32.const 55600) (local.tee $ep
(i32.mul (local.tee $nl (i32.add (local.get $nl) (i32.const 1))) (i32.const 48))))
(i32.const 6624) (i32.const 32))
(i64.store offset=55632 (local.get $ep) (local.get $val))
(i32.store offset=55640 (local.get $ep) (local.get $n))
(local.set $ep (i32.wrap_i64 (i64.shr_u (i64.mul
(i64.add
(i64.xor (i64.load (i32.const 6624))
(i64.rotl (i64.load offset=6616 (local.get $n)) (i64.const 29)))
(i64.extend_i32_u (local.get $n)))
(i64.const 0xA0C2995F40498CB3)) (i64.const 53))))
(loop $probe
(if (i32.load16_u offset=10768 (i32.shl (local.get $ep) (i32.const 1))) (then
(local.set $ep (i32.and (i32.add (local.get $ep) (i32.const 1)) (i32.const 2047)))
(br $probe))))
(i32.store16 offset=10768 (i32.shl (local.get $ep) (i32.const 1)) (local.get $nl))))
(br_if $entity (local.tee $r (i32.sub (local.get $r) (i32.const 1))))))
(func (export "render") (param $n i32) (result i64)
(local $size i32) (local $e i32) (local $o i32) (local $base i32) (local $lim i32)
(local $out i32) (local $q i32) (local $i i32) (local $len i32) (local $j i32)
(local $hex i32) (local $p i32) (local $v i32) (local $k i32) (local $ep i32) (local $h i32)
(local $w i64) (local $mm i64) (local $d i64) (local $t i64) (local $letter i64)
(local $x i64) (local $key i64) (local $val i64) (local $kb i64) (local $high i64)
(local $zero v128) (local $amp v128) (local $s0 v128) (local $s1 v128) (local $m0 v128) (local $m1 v128)
;; len_mask is filled by $init, so its first byte says whether the tables exist yet.
(if (i32.eqz (i32.load8_u (i32.const 150336))) (then (call $init)))
(local.set $size (select (local.get $n) (i32.const 1048576) (i32.lt_u (local.get $n) (i32.const 1048576))))
;; 64 zero bytes after the input: nothing stale can be mistaken for part of a reference.
(v128.store offset=412544 (local.get $size) (local.get $zero))
(v128.store offset=412560 (local.get $size) (local.get $zero))
(v128.store offset=412576 (local.get $size) (local.get $zero))
(v128.store offset=412592 (local.get $size) (local.get $zero))
(local.set $amp (i8x16.splat (i32.const 38)))
(local.set $high (i64.const 0x8080808080808080))
;; $e: end of the last reference in the input. $o: bytes of output so far.
(block $done
(loop $window
(br_if $done (i32.ge_u (local.get $base) (local.get $size)))
(local.set $lim (select (i32.add (local.get $base) (i32.const 4096)) (local.get $size)
(i32.gt_u (i32.sub (local.get $size) (local.get $base)) (i32.const 4096))))
;; Stage 1: list the position of every `&` in the window, 64 bytes at a time. The
;; first four positions of a block are written without looking at how many there
;; are; entries past the count are overwritten or ignored.
(local.set $out (i32.const 0))
(loop $scan
(local.set $mm (i64.or (i64.or (i64.or
(i64.extend_i32_u (i8x16.bitmask (i8x16.eq (v128.load offset=412544 (local.get $base)) (local.get $amp))))
(i64.shl (i64.extend_i32_u (i8x16.bitmask (i8x16.eq (v128.load offset=412560 (local.get $base)) (local.get $amp)))) (i64.const 16)))
(i64.shl (i64.extend_i32_u (i8x16.bitmask (i8x16.eq (v128.load offset=412576 (local.get $base)) (local.get $amp)))) (i64.const 32)))
(i64.shl (i64.extend_i32_u (i8x16.bitmask (i8x16.eq (v128.load offset=412592 (local.get $base)) (local.get $amp)))) (i64.const 48))))
(local.set $k (i32.add (local.get $out) (i32.shl (i32.wrap_i64 (i64.popcnt (local.get $mm))) (i32.const 2))))
(i32.store offset=23056 (local.get $out) (i32.add (local.get $base) (i32.wrap_i64 (i64.ctz (local.get $mm)))))
(local.set $mm (i64.and (local.get $mm) (i64.sub (local.get $mm) (i64.const 1))))
(i32.store offset=23060 (local.get $out) (i32.add (local.get $base) (i32.wrap_i64 (i64.ctz (local.get $mm)))))
(local.set $mm (i64.and (local.get $mm) (i64.sub (local.get $mm) (i64.const 1))))
(i32.store offset=23064 (local.get $out) (i32.add (local.get $base) (i32.wrap_i64 (i64.ctz (local.get $mm)))))
(local.set $mm (i64.and (local.get $mm) (i64.sub (local.get $mm) (i64.const 1))))
(i32.store offset=23068 (local.get $out) (i32.add (local.get $base) (i32.wrap_i64 (i64.ctz (local.get $mm)))))
(if (i64.ne (local.tee $mm (i64.and (local.get $mm) (i64.sub (local.get $mm) (i64.const 1)))) (i64.const 0)) (then
(loop $more
(i32.store offset=23072 (local.get $out) (i32.add (local.get $base) (i32.wrap_i64 (i64.ctz (local.get $mm)))))
(local.set $out (i32.add (local.get $out) (i32.const 4)))
(br_if $more (i64.ne (local.tee $mm (i64.and (local.get $mm) (i64.sub (local.get $mm) (i64.const 1)))) (i64.const 0))))))
(local.set $out (local.get $k))
(br_if $scan (i32.lt_u (local.tee $base (i32.add (local.get $base) (i32.const 64))) (local.get $lim))))
;; Stage 2: for each position, copy the text before it and decode the reference.
(local.set $q (i32.const 0))
(if (local.get $out) (then
(loop $ref
;; $i: position of this `&`; it becomes the end of the reference.
(local.set $len (i32.sub (local.tee $i (i32.load offset=23056 (local.get $q))) (local.get $e)))
(local.set $q (i32.add (local.get $q) (i32.const 4)))
(v128.store offset=150400 (local.get $o) (v128.load offset=412544 (local.get $e)))
(v128.store offset=150416 (local.get $o) (v128.load offset=412560 (local.get $e)))
(if (i32.gt_u (local.get $len) (i32.const 32)) (then
(local.set $j (i32.const 32))
(loop $copy
(v128.store offset=150400 (i32.add (local.get $o) (local.get $j))
(v128.load offset=412544 (i32.add (local.get $e) (local.get $j))))
(br_if $copy (i32.lt_u (local.tee $j (i32.add (local.get $j) (i32.const 16))) (local.get $len))))))
(local.set $o (i32.add (local.get $o) (local.get $len)))
;; $w: the 8 bytes after the `&`.
(local.set $w (i64.load offset=412545 (local.get $i)))
(block $next
(block $bare
(block $legacy
(if (i32.eq (i32.and (i32.wrap_i64 (local.get $w)) (i32.const 255)) (i32.const 35)) (then
;; Numeric. Decimal and hexadecimal share one path: classify 8 bytes,
;; take the digits before the first other byte, and fold them pairwise.
(local.set $hex (i32.eq
(i32.or (i32.and (i32.wrap_i64 (i64.shr_u (local.get $w) (i64.const 8))) (i32.const 255)) (i32.const 32))
(i32.const 120)))
(local.set $t (i64.xor
(local.tee $d (i64.load offset=412544
(local.tee $p (i32.add (i32.add (local.get $i) (i32.const 2)) (local.get $hex)))))
(i64.const 0x3030303030303030)))
;; $x: 0x80 in each byte that is a letter a-f or A-F.
(local.set $x (i64.and
(local.tee $key (i64.or (local.get $d) (i64.const 0x2020202020202020)))
(i64.xor (local.get $high) (i64.const -1))))
(local.set $letter (i64.and
(i64.and
(i64.add (local.get $x) (i64.const 0x1F1F1F1F1F1F1F1F))
(i64.xor
(i64.or (i64.add (local.get $x) (i64.const 0x1919191919191919)) (local.get $key))
(i64.const -1)))
(local.get $high)))
;; $t: 0x80 in each byte that is not a digit of this reference.
(if (i64.ne
(local.tee $t (i64.and
(i64.and
(i64.or
(i64.add (i64.and (local.get $t) (i64.xor (local.get $high) (i64.const -1)))
(i64.const 0x7676767676767676))
(local.get $t))
(local.get $high))
(i64.xor
(select (local.get $letter) (i64.const 0) (local.get $hex))
(i64.const -1))))
(i64.const 0))
(then
;; $kb: bits of digits. None: the `&` stands for itself.
(br_if $bare (i64.eqz (local.tee $kb (i64.and (i64.ctz (local.get $t)) (i64.const 56)))))
(local.set $x (i64.shl
(i64.add (i64.and (local.get $d) (i64.const 0x0F0F0F0F0F0F0F0F))
(i64.mul (i64.shr_u (local.get $letter) (i64.const 7)) (i64.const 9)))
(i64.sub (i64.const 64) (local.get $kb))))
(local.set $x (i64.and
(i64.add (i64.mul (local.get $x) (select (i64.const 16) (i64.const 10) (local.get $hex)))
(i64.shr_u (local.get $x) (i64.const 8)))
(i64.const 0x00FF00FF00FF00FF)))
(local.set $x (i64.and
(i64.add (i64.mul (local.get $x) (select (i64.const 256) (i64.const 100) (local.get $hex)))
(i64.shr_u (local.get $x) (i64.const 16)))
(i64.const 0x0000FFFF0000FFFF)))
(local.set $v (i32.wrap_i64
(i64.add (i64.mul (local.get $x) (select (i64.const 65536) (i64.const 10000) (local.get $hex)))
(i64.shr_u (local.get $x) (i64.const 32)))))
(local.set $p (i32.add (local.get $p) (i32.wrap_i64 (i64.shr_u (local.get $kb) (i64.const 3))))))
(else
;; Eight or more digits: one at a time, saturating past U+10FFFF.
(local.set $v (i32.const 0))
(local.set $k (select (i32.const 16) (i32.const 10) (local.get $hex)))
(block $end
(loop $digit
(if (i32.gt_u
(local.tee $h (i32.sub (i32.load8_u offset=412544 (local.get $p)) (i32.const 48)))
(i32.const 9))
(then
(if (i32.lt_u
(local.tee $h (i32.sub (i32.or (i32.load8_u offset=412544 (local.get $p)) (i32.const 32)) (i32.const 87)))
(i32.const 10))
(then (local.set $h (i32.const 16))))))
(br_if $end (i32.ge_u (local.get $h) (local.get $k)))
(if (i32.gt_u
(local.tee $v (i32.add (i32.mul (local.get $v) (local.get $k)) (local.get $h)))
(i32.const 0x10FFFF))
(then (local.set $v (i32.const 0x110000))))
(local.set $p (i32.add (local.get $p) (i32.const 1)))
(br $digit)))))
(local.set $i (i32.add (local.get $p)
(i32.eq (i32.load8_u offset=412544 (local.get $p)) (i32.const 59))))
;; 0x80-0x9F use the Windows-1252 table; 0, surrogates and values past
;; U+10FFFF become U+FFFD.
(if (i32.lt_u (i32.sub (local.get $v) (i32.const 0x80)) (i32.const 0x20))
(then (local.set $v (i32.load16_u offset=6240 (i32.shl (local.get $v) (i32.const 1)))))
(else
(if (i32.or
(i32.ge_u (i32.sub (local.get $v) (i32.const 1)) (i32.const 0x10FFFF))
(i32.lt_u (i32.sub (local.get $v) (i32.const 0xD800)) (i32.const 0x800)))
(then (local.set $v (i32.const 0xFFFD))))))
;; UTF-8, as in $utf8 but in line: a call here would cost the loop its registers.
(local.set $k
(i32.add (i32.add (i32.add (i32.const 1)
(i32.gt_u (local.get $v) (i32.const 0x7F)))
(i32.gt_u (local.get $v) (i32.const 0x7FF)))
(i32.gt_u (local.get $v) (i32.const 0xFFFF))))
(i32.store offset=150400 (local.get $o)
(select
(local.get $v)
(i32.or
(i32.shr_u
(i32.or (i32.or (i32.or
(i32.shr_u (local.get $v) (i32.const 18))
(i32.shl (i32.and (i32.shr_u (local.get $v) (i32.const 12)) (i32.const 0x3F)) (i32.const 8)))
(i32.shl (i32.and (i32.shr_u (local.get $v) (i32.const 6)) (i32.const 0x3F)) (i32.const 16)))
(i32.shl (i32.and (local.get $v) (i32.const 0x3F)) (i32.const 24)))
(i32.sub (i32.const 32) (i32.shl (local.get $k) (i32.const 3))))
(i32.load offset=6564 (i32.shl (local.get $k) (i32.const 2))))
(i32.eq (local.get $k) (i32.const 1))))
(local.set $o (i32.add (local.get $o) (local.get $k)))
(br $next)))
;; Named. $t: 0x80 in the first byte of $w that is `;`.
(local.set $t (i64.xor (local.get $w) (i64.const 0x3B3B3B3B3B3B3B3B)))
(if (i64.ne
(local.tee $t (i64.and
(i64.and (i64.sub (local.get $t) (i64.const 0x0101010101010101)) (i64.xor (local.get $t) (i64.const -1)))
(local.get $high)))
(i64.const 0))
(then
;; Up to 7 bytes: the name and its `;` are the key into fast.
(local.set $key (i64.and (local.get $w)
(i64.sub
(i64.shl (i64.const 2) (i64.add (local.tee $kb (i64.and (i64.ctz (local.get $t)) (i64.const 56))) (i64.const 7)))
(i64.const 1))))
(local.set $ep (i32.shl (i32.wrap_i64 (i64.shr_u
(i64.mul (local.get $key) (i64.const 0xA59D054B12F5B905)) (i64.const 52))) (i32.const 4)))
(loop $probe
(if (i64.eq (local.tee $val (i64.load offset=79936 (local.get $ep))) (local.get $key)) (then
(i64.store offset=150400 (local.get $o) (local.tee $val (i64.load offset=79944 (local.get $ep))))
(local.set $o (i32.add (local.get $o) (i32.wrap_i64 (i64.shr_u (local.get $val) (i64.const 56)))))
(local.set $i (i32.add (i32.add (local.get $i) (i32.const 2))
(i32.wrap_i64 (i64.shr_u (local.get $kb) (i64.const 3)))))
(br $next)))
(br_if $legacy (i64.eq (local.get $val) (i64.const -1)))
(local.set $ep (i32.add (local.get $ep) (i32.const 16)))
(br $probe)))
(else
;; No `;` in 8 bytes: a name of 8 to 31 bytes needs its `;` in the next 24.
(local.set $s0 (v128.load offset=412545 (local.get $i)))
(local.set $s1 (v128.load offset=412561 (local.get $i)))
(if (local.tee $h (i32.or
(i8x16.bitmask (i8x16.eq (local.get $s0) (local.tee $m0 (i8x16.splat (i32.const 59)))))
(i32.shl (i8x16.bitmask (i8x16.eq (local.get $s1) (local.get $m0))) (i32.const 16))))
(then
(local.set $len (i32.ctz (local.get $h)))
(local.set $h (i32.wrap_i64 (i64.shr_u (i64.mul
(i64.add
(i64.xor (local.get $w)
(i64.rotl (i64.load offset=412537 (i32.add (local.get $i) (local.get $len))) (i64.const 29)))
(i64.extend_i32_u (local.get $len)))
(i64.const 0xA0C2995F40498CB3)) (i64.const 53))))
;; Byte j of the 32 loaded at len_mask + 32 - len is 0xFF when j < len.
(local.set $m0 (v128.load offset=150336 (local.tee $k (i32.sub (i32.const 32) (local.get $len)))))
(local.set $m1 (v128.load offset=150352 (local.get $k)))
(block $miss
(loop $slot
(br_if $miss (i32.eqz (local.tee $ep
(i32.load16_u offset=10768 (i32.shl (local.get $h) (i32.const 1))))))
(if (i32.and
(i32.eq
(i32.load offset=55640 (local.tee $ep (i32.mul (local.get $ep) (i32.const 48))))
(local.get $len))
(i32.eqz (v128.any_true (v128.or
(v128.xor (v128.and (local.get $s0) (local.get $m0)) (v128.load offset=55600 (local.get $ep)))
(v128.xor (v128.and (local.get $s1) (local.get $m1)) (v128.load offset=55616 (local.get $ep)))))))
(then
(i64.store offset=150400 (local.get $o) (local.tee $val (i64.load offset=55632 (local.get $ep))))
(local.set $o (i32.add (local.get $o) (i32.wrap_i64 (i64.shr_u (local.get $val) (i64.const 56)))))
(local.set $i (i32.add (i32.add (local.get $i) (i32.const 2)) (local.get $len)))
(br $next)))
(local.set $h (i32.and (i32.add (local.get $h) (i32.const 1)) (i32.const 2047)))
(br $slot))))))))
;; Without `;`: the longest legacy name that is a prefix, longest first.
(local.set $k (i32.load8_u offset=6672 (i32.shr_u
(i32.mul (i32.and (i32.wrap_i64 (local.get $w)) (i32.const 0xFFFF)) (i32.const 0x9E3779B1))
(i32.const 20))))
(loop $try
(br_if $bare (i32.lt_u (local.get $k) (i32.const 2)))
(local.set $key (i64.or
(i64.and (local.get $w)
(i64.sub (i64.shl (i64.const 1) (i64.extend_i32_u (i32.shl (local.get $k) (i32.const 3)))) (i64.const 1)))
(i64.shl (i64.extend_i32_u (local.get $k)) (i64.const 56))))
(local.set $ep (i32.shl (i32.wrap_i64 (i64.shr_u
(i64.mul (local.get $key) (i64.const 0xF880D97D1854E551)) (i64.const 56))) (i32.const 4)))
(loop $probe
(if (i64.eq (local.tee $val (i64.load offset=145984 (local.get $ep))) (local.get $key)) (then
(i64.store offset=150400 (local.get $o) (local.tee $val (i64.load offset=145992 (local.get $ep))))
(local.set $o (i32.add (local.get $o) (i32.wrap_i64 (i64.shr_u (local.get $val) (i64.const 56)))))
(local.set $i (i32.add (i32.add (local.get $i) (i32.const 1)) (local.get $k)))
(br $next)))
(if (i64.ne (local.get $val) (i64.const -1)) (then
(local.set $ep (i32.add (local.get $ep) (i32.const 16)))
(br $probe))))
(local.set $k (i32.sub (local.get $k) (i32.const 1)))
(br $try)))
;; Not a reference: the `&` is copied.
(i32.store8 offset=150400 (local.get $o) (i32.const 38))
(local.set $o (i32.add (local.get $o) (i32.const 1)))
(local.set $i (i32.add (local.get $i) (i32.const 1))))
(local.set $e (local.get $i))
(br_if $ref (i32.lt_u (local.get $q) (local.get $out))))))
(br $window)))
;; Without a reference the input is the output.
(if (i32.eqz (local.get $e)) (then
(return (i64.or (i64.const 1771862988161024) (i64.extend_i32_u (local.get $size))))))
;; Copy the text after the last reference.
(local.set $o (i32.sub (local.get $o) (local.get $e)))
(loop $tail
(if (i32.lt_u (local.get $e) (local.get $size)) (then
(v128.store offset=150400 (i32.add (local.get $o) (local.get $e)) (v128.load offset=412544 (local.get $e)))
(local.set $e (i32.add (local.get $e) (i32.const 16)))
(br $tail))))
(i64.or (i64.const 645963081318400) (i64.extend_i32_u (i32.add (local.get $o) (local.get $size))))))
(; pack.py, which produced the packed entity 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, 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=17, limit=5, narrow=True)
;)