summaryrefslogtreecommitdiffstats
path: root/src/js/wasm
diff options
context:
space:
mode:
Diffstat (limited to 'src/js/wasm')
-rw-r--r--src/js/wasm/README.md24
-rw-r--r--src/js/wasm/biditrie.wasmbin0 -> 990 bytes
-rw-r--r--src/js/wasm/biditrie.wat728
-rw-r--r--src/js/wasm/hntrie.wasmbin0 -> 1034 bytes
-rw-r--r--src/js/wasm/hntrie.wat724
5 files changed, 1476 insertions, 0 deletions
diff --git a/src/js/wasm/README.md b/src/js/wasm/README.md
new file mode 100644
index 0000000..32aef07
--- /dev/null
+++ b/src/js/wasm/README.md
@@ -0,0 +1,24 @@
+### For code reviewers
+
+All `wasm` files in that directory where created by compiling the
+corresponding `wat` file using the command (using `hntrie.wat`/`hntrie.wasm`
+as example):
+
+ wat2wasm hntrie.wat -o hntrie.wasm
+
+Assuming:
+
+- The command is executed from within the present directory.
+
+### `wat2wasm` tool
+
+The `wat2wasm` tool can be downloaded from an official WebAssembly project:
+<https://github.com/WebAssembly/wabt/releases>.
+
+### `wat2wasm` tool online
+
+You can also use the following online `wat2wasm` tool:
+<https://webassembly.github.io/wabt/demo/wat2wasm/>.
+
+Just paste the whole content of the `wat` file to compile into the WAT pane.
+Click "Download" button to retrieve the resulting `wasm` file. \ No newline at end of file
diff --git a/src/js/wasm/biditrie.wasm b/src/js/wasm/biditrie.wasm
new file mode 100644
index 0000000..5bfc6b7
--- /dev/null
+++ b/src/js/wasm/biditrie.wasm
Binary files differ
diff --git a/src/js/wasm/biditrie.wat b/src/js/wasm/biditrie.wat
new file mode 100644
index 0000000..a6c80ba
--- /dev/null
+++ b/src/js/wasm/biditrie.wat
@@ -0,0 +1,728 @@
+;;
+;; uBlock Origin - a comprehensive, efficient content blocker
+;; Copyright (C) 2019-present Raymond Hill
+;;
+;; This program is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+;;
+;; This program is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+;; GNU General Public License for more details.
+;;
+;; You should have received a copy of the GNU General Public License
+;; along with this program. If not, see {http://www.gnu.org/licenses/}.
+;;
+;; Home: https://github.com/gorhill/uBlock
+;; File: biditrie.wat
+;; Description: WebAssembly code used by src/js/biditrie.js
+;; How to compile: See README.md in this directory.
+
+(module
+;;
+;; module start
+;;
+
+(memory (import "imports" "memory") 1)
+(func $extraHandler (import "imports" "extraHandler") (param i32 i32 i32) (result i32))
+
+;; Trie container
+;;
+;; Memory layout, byte offset:
+;; const HAYSTACK_START = 0;
+;; const HAYSTACK_SIZE = 2048; // i32 / i8
+;; const HAYSTACK_SIZE_SLOT = HAYSTACK_SIZE >>> 2; // 512 / 2048
+;; const TRIE0_SLOT = HAYSTACK_SIZE_SLOT + 1; // 513 / 2052
+;; const TRIE1_SLOT = HAYSTACK_SIZE_SLOT + 2; // 514 / 2056
+;; const CHAR0_SLOT = HAYSTACK_SIZE_SLOT + 3; // 515 / 2060
+;; const CHAR1_SLOT = HAYSTACK_SIZE_SLOT + 4; // 516 / 2064
+;; const RESULT_L_SLOT = HAYSTACK_SIZE_SLOT + 5; // 517 / 2068
+;; const RESULT_R_SLOT = HAYSTACK_SIZE_SLOT + 6; // 518 / 2072
+;; const RESULT_IU_SLOT = HAYSTACK_SIZE_SLOT + 7; // 519 / 2076
+;; const TRIE0_START = HAYSTACK_SIZE_SLOT + 8 << 2; // 2080
+;;
+
+;;
+;; Public functions
+;;
+
+;;
+;; unsigned int matches(icell, ai)
+;;
+;; Test whether the trie at icell matches the haystack content at position ai.
+;;
+(func (export "matches")
+ (param $icell i32) ;; start offset in haystack
+ (param $ai i32) ;; offset in haystack
+ (result i32) ;; result: 0 = no match, 1 = match
+ (local $char0 i32)
+ (local $aR i32)
+ (local $al i32)
+ (local $bl i32)
+ (local $x i32)
+ (local $y i32)
+ ;; trie index is a uint32 offset, need to convert to uint8 offset
+ local.get $icell
+ i32.const 2
+ i32.shl
+ local.set $icell
+ ;; const buf32 = this.buf32;
+ ;; const buf8 = this.buf8;
+ ;; const char0 = buf32[CHAR0_SLOT];
+ i32.const 2060
+ i32.load align=4
+ local.set $char0
+ ;; const aR = buf32[HAYSTACK_SIZE_SLOT];
+ i32.const 2048
+ i32.load align=4
+ local.set $aR
+ ;; let al = ai;
+ local.get $ai
+ local.set $al
+ block $matchFound
+ block $matchNotFound
+ ;; for (;;) {
+ loop $mainLoop
+ ;; x = buf8[al];
+ local.get $al
+ i32.load8_u
+ local.set $x
+ ;; al += 1;
+ local.get $al
+ i32.const 1
+ i32.add
+ local.set $al
+ ;; // find matching segment
+ ;; for (;;) {
+ block $nextSegment loop $findSegment
+ ;; y = buf32[icell+SEGMENT_INFO];
+ local.get $icell
+ i32.load offset=8 align=4
+ local.tee $y
+ ;; bl = char0 + (y & 0x00FFFFFF);
+ i32.const 0x00FFFFFF
+ i32.and
+ local.get $char0
+ i32.add
+ local.tee $bl
+ ;; if ( buf8[bl] === x ) {
+ i32.load8_u
+ local.get $x
+ i32.eq
+ if
+ ;; y = (y >>> 24) - 1;
+ local.get $y
+ i32.const 24
+ i32.shr_u
+ i32.const 1
+ i32.sub
+ local.tee $y
+ ;; if ( n !== 0 ) {
+ if
+ ;; x = al + y;
+ local.get $y
+ local.get $al
+ i32.add
+ local.tee $x
+ ;; if ( x > aR ) { return 0; }
+ local.get $aR
+ i32.gt_u
+ br_if $matchNotFound
+ ;; for (;;) {
+ loop
+ ;; bl += 1;
+ local.get $bl
+ i32.const 1
+ i32.add
+ local.tee $bl
+ ;; if ( buf8[bl] !== buf8[al] ) { return 0; }
+ i32.load8_u
+ local.get $al
+ i32.load8_u
+ i32.ne
+ br_if $matchNotFound
+ ;; al += 1;
+ local.get $al
+ i32.const 1
+ i32.add
+ local.tee $al
+ ;; if ( al === x ) { break; }
+ local.get $x
+ i32.ne
+ br_if 0
+ end
+ ;; }
+ end
+ br $nextSegment
+ end
+ ;; icell = buf32[icell+CELL_OR];
+ local.get $icell
+ i32.load offset=4 align=4
+ i32.const 2
+ i32.shl
+ local.tee $icell
+ ;; if ( icell === 0 ) { return 0; }
+ i32.eqz
+ br_if $matchNotFound
+ br $findSegment
+ ;; }
+ end end
+ ;; // next segment
+ ;; icell = buf32[icell+CELL_AND];
+ local.get $icell
+ i32.load align=4
+ i32.const 2
+ i32.shl
+ local.tee $icell
+ ;; const x = buf32[icell+BCELL_EXTRA];
+ i32.load offset=8 align=4
+ local.tee $x
+ ;; if ( x <= BCELL_EXTRA_MAX ) {
+ i32.const 0x00FFFFFF
+ i32.le_u
+ if
+ ;; if ( x !== 0 && this.matchesExtra(ai, al, x) !== 0 ) {
+ ;; return 1;
+ ;; }
+ local.get $x
+ if
+ local.get $ai
+ local.get $al
+ local.get $x
+ call $matchesExtra
+ br_if $matchFound
+ end
+ ;; x = buf32[icell+BCELL_ALT_AND];
+ local.get $icell
+ i32.load offset=4 align=4
+ i32.const 2
+ i32.shl
+ local.tee $x
+ ;; if ( x !== 0 && this.matchesLeft(x, ai, al) !== 0 ) {
+ if
+ local.get $x
+ local.get $ai
+ local.get $al
+ call $matchesLeft
+ br_if $matchFound
+ ;; }
+ end
+ ;; icell = buf32[icell+BCELL_NEXT_AND];
+ local.get $icell
+ i32.load align=4
+ i32.const 2
+ i32.shl
+ local.tee $icell
+ ;; if ( icell === 0 ) { return 0; }
+ i32.eqz
+ br_if $matchNotFound
+ ;; }
+ end
+ ;; if ( al === aR ) { return 0; }
+ local.get $al
+ local.get $aR
+ i32.ne
+ br_if $mainLoop
+ ;; }
+ end ;; $mainLoop
+ end ;; $matchNotFound
+ i32.const 0
+ return
+ end ;; $matchFound
+ i32.const 1
+ return
+)
+
+;;
+;; unsigned int matchesLeft(icell, ar, r)
+;;
+;; Test whether the trie at icell matches the haystack content at position ai.
+;;
+(func $matchesLeft
+ (param $icell i32) ;; start offset in haystack
+ (param $ar i32) ;; offset of where to start in haystack
+ (param $r i32) ;; right bound of match so far
+ (result i32) ;; result: 0 = no match, 1 = match
+ (local $char0 i32)
+ (local $bl i32)
+ (local $br i32)
+ (local $x i32)
+ (local $y i32)
+ ;; const buf32 = this.buf32;
+ ;; const buf8 = this.buf8;
+ ;; const char0 = buf32[CHAR0_SLOT];
+ i32.const 2060
+ i32.load align=4
+ local.set $char0
+ block $matchFound
+ block $matchNotFound
+ ;; for (;;) {
+ loop $mainLoop
+ ;; if ( ar === 0 ) { return 0; }
+ local.get $ar
+ i32.eqz
+ br_if $matchNotFound
+ ;; ar -= 1;
+ local.get $ar
+ i32.const 1
+ i32.sub
+ local.tee $ar
+ ;; x = buf8[ar];
+ i32.load8_u
+ local.set $x
+ ;; // find matching segment
+ ;; for (;;) {
+ block $nextSegment loop $findSegment
+ ;; y = buf32[icell+SEGMENT_INFO];
+ local.get $icell
+ i32.load offset=8 align=4
+ local.tee $y
+ ;; br = char0 + (y & 0x00FFFFFF);
+ i32.const 0x00FFFFFF
+ i32.and
+ local.get $char0
+ i32.add
+ local.tee $br
+ ;; y = (y >>> 24) - 1;
+ local.get $y
+ i32.const 24
+ i32.shr_u
+ i32.const 1
+ i32.sub
+ local.tee $y
+ ;; br += y;
+ i32.add
+ local.tee $br
+ ;; if ( buf8[br] === x ) {
+ i32.load8_u
+ local.get $x
+ i32.eq
+ if
+ ;; // all characters in segment must match
+ ;; if ( y !== 0 ) {
+ local.get $y
+ if
+ ;; x = ar - y;
+ local.get $ar
+ local.get $y
+ i32.sub
+ local.tee $x
+ ;; if ( x < 0 ) { return 0; }
+ i32.const 0
+ i32.lt_s
+ br_if $matchNotFound
+ ;; for (;;) {
+ loop
+ ;; ar -= 1; br -= 1;
+ ;; if ( buf8[ar] !== buf8[br] ) { return 0; }
+ local.get $ar
+ i32.const 1
+ i32.sub
+ local.tee $ar
+ i32.load8_u
+ local.get $br
+ i32.const 1
+ i32.sub
+ local.tee $br
+ i32.load8_u
+ i32.ne
+ br_if $matchNotFound
+ ;; if ( ar === x ) { break; }
+ local.get $ar
+ local.get $x
+ i32.ne
+ br_if 0
+ end
+ ;; }
+ end
+ br $nextSegment
+ end
+ ;; icell = buf32[icell+CELL_OR];
+ local.get $icell
+ i32.load offset=4 align=4
+ i32.const 2
+ i32.shl
+ local.tee $icell
+ ;; if ( icell === 0 ) { return 0; }
+ i32.eqz
+ br_if $matchNotFound
+ br $findSegment
+ ;; }
+ end end
+ ;; // next segment
+ ;; icell = buf32[icell+CELL_AND];
+ local.get $icell
+ i32.load align=4
+ i32.const 2
+ i32.shl
+ local.tee $icell
+ ;; const x = buf32[icell+BCELL_EXTRA];
+ i32.load offset=8 align=4
+ local.tee $x
+ ;; if ( x <= BCELL_EXTRA_MAX ) {
+ i32.const 0x00FFFFFF
+ i32.le_u
+ if
+ ;; if ( x !== 0 && this.matchesExtra(ar, r, x) !== 0 ) {
+ ;; return 1;
+ ;; }
+ local.get $x
+ if
+ local.get $ar
+ local.get $r
+ local.get $x
+ call $matchesExtra
+ br_if $matchFound
+ end
+ ;; icell = buf32[icell+BCELL_NEXT_AND];
+ local.get $icell
+ i32.load align=4
+ i32.const 2
+ i32.shl
+ local.tee $icell
+ ;; if ( icell === 0 ) { return 0; }
+ i32.eqz
+ br_if $matchNotFound
+ ;; }
+ end
+ br $mainLoop
+ ;; }
+ end ;; $mainLoop
+ end ;; $matchNotFound
+ i32.const 0
+ return
+ end ;; $matchFound
+ i32.const 1
+ return
+)
+
+;;
+;; int matchExtra(l, r, ix)
+;;
+;; Test whether extra handler returns a match.
+;;
+(func $matchesExtra
+ (param $l i32) ;; left bound of match so far
+ (param $r i32) ;; right bound of match so far
+ (param $ix i32) ;; extra token
+ (result i32) ;; result: 0 = no match, 1 = match
+ (local $iu i32) ;; filter unit
+ block $fail
+ block $succeed
+ ;; if ( ix !== 1 ) {
+ ;; const iu = this.extraHandler(l, r, ix);
+ ;; if ( iu === 0 ) { return 0; }
+ local.get $ix
+ i32.const 1
+ i32.ne
+ if
+ local.get $l
+ local.get $r
+ local.get $ix
+ call $extraHandler
+ local.tee $iu
+ i32.eqz
+ br_if $fail
+ ;; } else {
+ ;; iu = -1;
+ else
+ i32.const -1
+ local.set $iu
+ ;; }
+ end
+ ;; this.buf32[RESULT_IU_SLOT] = iu;
+ i32.const 2076
+ local.get $iu
+ i32.store align=4
+ ;; this.buf32[RESULT_L_SLOT] = l;
+ i32.const 2068
+ local.get $l
+ i32.store align=4
+ ;; this.buf32[RESULT_R_SLOT] = r;
+ i32.const 2072
+ local.get $r
+ i32.store align=4
+ end ;; $succeed
+ i32.const 1
+ return
+ end ;; $fail
+ i32.const 0
+)
+
+;;
+;; unsigned int startsWith(haystackLeft, haystackRight, needleLeft, needleLen)
+;;
+;; Test whether the string at needleOffset and of length needleLen matches
+;; the haystack at offset haystackOffset.
+;;
+(func (export "startsWith")
+ (param $haystackLeft i32) ;; start offset in haystack
+ (param $haystackRight i32) ;; end offset in haystack
+ (param $needleLeft i32) ;; start of needle in character buffer
+ (param $needleLen i32) ;; number of characters to match
+ (result i32) ;; result: 0 = no match, 1 = match
+ (local $needleRight i32)
+ block $fail
+ block $succeed
+ ;;
+ ;; if ( haystackLeft < 0 || (haystackLeft + needleLen) > haystackRight ) {
+ ;; return 0;
+ ;; }
+ local.get $haystackLeft
+ i32.const 0
+ i32.lt_s
+ br_if $fail
+ local.get $haystackLeft
+ local.get $needleLen
+ i32.add
+ local.get $haystackRight
+ i32.gt_u
+ br_if $fail
+ ;; const charCodes = this.buf8;
+ ;; needleLeft += this.buf32[CHAR0_SLOT];
+ local.get $needleLeft
+ i32.const 2060 ;; CHAR0_SLOT memory address
+ i32.load align=4 ;; CHAR0 memory address
+ i32.add ;; needle memory address
+ local.tee $needleLeft
+ ;; const needleRight = needleLeft + needleLen;
+ local.get $needleLen
+ i32.add
+ local.set $needleRight
+ ;; while ( charCodes[haystackLeft] === charCodes[needleLeft] ) {
+ loop $compare
+ local.get $haystackLeft
+ i32.load8_u
+ local.get $needleLeft
+ i32.load8_u
+ i32.ne
+ br_if $fail
+ ;; needleLeft += 1;
+ local.get $needleLeft
+ i32.const 1
+ i32.add
+ local.tee $needleLeft
+ ;; if ( needleLeft === needleRight ) { return 1; }
+ local.get $needleRight
+ i32.eq
+ br_if $succeed
+ ;; haystackLeft += 1;
+ i32.const 1
+ local.get $haystackLeft
+ i32.add
+ local.set $haystackLeft
+ br $compare
+ end
+ ;; }
+ ;; return 1;
+ end ;; $succeed
+ i32.const 1
+ return
+ ;; return 0;
+ end ;; $fail
+ i32.const 0
+)
+
+;;
+;; int indexOf(haystackLeft, haystackEnd, needleLeft, needleLen)
+;;
+;; Test whether the string at needleOffset and of length needleLen is found in
+;; the haystack at or to the left of haystackLeft, but not farther than
+;; haystackEnd.
+;;
+(func (export "indexOf")
+ (param $haystackLeft i32) ;; start offset in haystack
+ (param $haystackEnd i32) ;; end offset in haystack
+ (param $needleLeft i32) ;; start of needle in character buffer
+ (param $needleLen i32) ;; number of characters to match
+ (result i32) ;; result: index of match, -1 = no match
+ (local $needleRight i32)
+ (local $i i32)
+ (local $j i32)
+ (local $c0 i32)
+ block $fail
+ block $succeed
+ ;; if ( needleLen === 0 ) { return haystackLeft; }
+ local.get $needleLen
+ i32.eqz
+ br_if $succeed
+ ;; haystackEnd -= needleLen;
+ local.get $haystackEnd
+ local.get $needleLen
+ i32.sub
+ local.tee $haystackEnd
+ ;; if ( haystackEnd < haystackLeft ) { return -1; }
+ local.get $haystackLeft
+ i32.lt_s
+ br_if $fail
+ ;; needleLeft += this.buf32[CHAR0_SLOT];
+ local.get $needleLeft
+ i32.const 2060 ;; CHAR0_SLOT memory address
+ i32.load align=4 ;; CHAR0 memory address
+ i32.add ;; needle memory address
+ local.tee $needleLeft
+ ;; const needleRight = needleLeft + needleLen;
+ local.get $needleLen
+ i32.add
+ local.set $needleRight
+ ;; const charCodes = this.buf8;
+ ;; for (;;) {
+ loop $mainLoop
+ ;; let i = haystackLeft;
+ ;; let j = needleLeft;
+ local.get $haystackLeft
+ local.set $i
+ local.get $needleLeft
+ local.set $j
+ ;; while ( charCodes[i] === charCodes[j] ) {
+ block $breakMatchChars loop $matchChars
+ local.get $i
+ i32.load8_u
+ local.get $j
+ i32.load8_u
+ i32.ne
+ br_if $breakMatchChars
+ ;; j += 1;
+ local.get $j
+ i32.const 1
+ i32.add
+ local.tee $j
+ ;; if ( j === needleRight ) { return haystackLeft; }
+ local.get $needleRight
+ i32.eq
+ br_if $succeed
+ ;; i += 1;
+ local.get $i
+ i32.const 1
+ i32.add
+ local.set $i
+ br $matchChars
+ ;; }
+ end end
+ ;; haystackLeft += 1;
+ local.get $haystackLeft
+ i32.const 1
+ i32.add
+ local.tee $haystackLeft
+ ;; if ( haystackLeft > haystackEnd ) { break; }
+ local.get $haystackEnd
+ i32.gt_u
+ br_if $fail
+ br $mainLoop
+ ;; }
+ end
+ end ;; $succeed
+ local.get $haystackLeft
+ return
+ end ;; $fail
+ ;; return -1;
+ i32.const -1
+)
+
+;;
+;; int lastIndexOf(haystackBeg, haystackEnd, needleLeft, needleLen)
+;;
+;; Test whether the string at needleOffset and of length needleLen is found in
+;; the haystack at or to the right of haystackBeg, but not farther than
+;; haystackEnd.
+;;
+(func (export "lastIndexOf")
+ (param $haystackBeg i32) ;; start offset in haystack
+ (param $haystackEnd i32) ;; end offset in haystack
+ (param $needleLeft i32) ;; start of needle in character buffer
+ (param $needleLen i32) ;; number of characters to match
+ (result i32) ;; result: index of match, -1 = no match
+ (local $haystackLeft i32)
+ (local $needleRight i32)
+ (local $i i32)
+ (local $j i32)
+ (local $c0 i32)
+ ;; if ( needleLen === 0 ) { return haystackBeg; }
+ local.get $needleLen
+ i32.eqz
+ if
+ local.get $haystackBeg
+ return
+ end
+ block $fail
+ block $succeed
+ ;; let haystackLeft = haystackEnd - needleLen;
+ local.get $haystackEnd
+ local.get $needleLen
+ i32.sub
+ local.tee $haystackLeft
+ ;; if ( haystackLeft < haystackBeg ) { return -1; }
+ local.get $haystackBeg
+ i32.lt_s
+ br_if $fail
+ ;; needleLeft += this.buf32[CHAR0_SLOT];
+ local.get $needleLeft
+ i32.const 2060 ;; CHAR0_SLOT memory address
+ i32.load align=4 ;; CHAR0 memory address
+ i32.add ;; needle memory address
+ local.tee $needleLeft
+ ;; const needleRight = needleLeft + needleLen;
+ local.get $needleLen
+ i32.add
+ local.set $needleRight
+ ;; const charCodes = this.buf8;
+ ;; for (;;) {
+ loop $mainLoop
+ ;; let i = haystackLeft;
+ ;; let j = needleLeft;
+ local.get $haystackLeft
+ local.set $i
+ local.get $needleLeft
+ local.set $j
+ ;; while ( charCodes[i] === charCodes[j] ) {
+ block $breakMatchChars loop $matchChars
+ local.get $i
+ i32.load8_u
+ local.get $j
+ i32.load8_u
+ i32.ne
+ br_if $breakMatchChars
+ ;; j += 1;
+ local.get $j
+ i32.const 1
+ i32.add
+ local.tee $j
+ ;; if ( j === needleRight ) { return haystackLeft; }
+ local.get $needleRight
+ i32.eq
+ br_if $succeed
+ ;; i += 1;
+ local.get $i
+ i32.const 1
+ i32.add
+ local.set $i
+ br $matchChars
+ ;; }
+ end end
+ ;; if ( haystackLeft === haystackBeg ) { break; }
+ ;; haystackLeft -= 1;
+ local.get $haystackLeft
+ local.get $haystackBeg
+ i32.eq
+ br_if $fail
+ local.get $haystackLeft
+ i32.const 1
+ i32.sub
+ local.set $haystackLeft
+ br $mainLoop
+ ;; }
+ end
+ end ;; $succeed
+ local.get $haystackLeft
+ return
+ end ;; $fail
+ ;; return -1;
+ i32.const -1
+)
+
+;;
+;; module end
+;;
+)
diff --git a/src/js/wasm/hntrie.wasm b/src/js/wasm/hntrie.wasm
new file mode 100644
index 0000000..9067f42
--- /dev/null
+++ b/src/js/wasm/hntrie.wasm
Binary files differ
diff --git a/src/js/wasm/hntrie.wat b/src/js/wasm/hntrie.wat
new file mode 100644
index 0000000..666c44e
--- /dev/null
+++ b/src/js/wasm/hntrie.wat
@@ -0,0 +1,724 @@
+;;
+;; uBlock Origin - a comprehensive, efficient content blocker
+;; Copyright (C) 2018-present Raymond Hill
+;;
+;; This program is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+;;
+;; This program is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+;; GNU General Public License for more details.
+;;
+;; You should have received a copy of the GNU General Public License
+;; along with this program. If not, see {http://www.gnu.org/licenses/}.
+;;
+;; Home: https://github.com/gorhill/uBlock
+;; File: hntrie.wat
+;; Description: WebAssembly code used by src/js/hntrie.js
+;; How to compile: See README.md in this directory.
+
+(module
+;;
+;; module start
+;;
+
+(func $growBuf (import "imports" "growBuf"))
+(memory (import "imports" "memory") 1)
+
+;; Trie container
+;;
+;; Memory layout, byte offset:
+;; 0-254: needle being processed
+;; 255: length of needle
+;; 256-259: offset to start of trie data section (=> trie0)
+;; 260-263: offset to end of trie data section (=> trie1)
+;; 264-267: offset to start of character data section (=> char0)
+;; 268-271: offset to end of character data section (=> char1)
+;; 272: start of trie data section
+;;
+
+;;
+;; Public functions
+;;
+
+;;
+;; unsigned int matches(icell)
+;;
+;; Test whether the currently set needle matches the trie at specified trie
+;; offset.
+;;
+(func (export "matches")
+ (param $iroot i32) ;; offset to root cell of the trie
+ (result i32) ;; result = match index, -1 = miss
+ (local $icell i32) ;; offset to the current cell
+ (local $char0 i32) ;; offset to first character data
+ (local $ineedle i32) ;; current needle offset
+ (local $c i32)
+ (local $v i32)
+ (local $n i32)
+ (local $i0 i32)
+ (local $i1 i32)
+ ;;
+ i32.const 264 ;; start of char section is stored at addr 264
+ i32.load
+ local.set $char0
+ ;; let ineedle = this.buf[255];
+ i32.const 255 ;; addr of needle is stored at addr 255
+ i32.load8_u
+ local.set $ineedle
+ ;; let icell = this.buf32[iroot+0];
+ local.get $iroot
+ i32.const 2
+ i32.shl
+ i32.load
+ i32.const 2
+ i32.shl
+ local.tee $icell
+ ;; if ( icell === 0 ) { return -1; }
+ i32.eqz
+ if
+ i32.const -1
+ return
+ end
+ ;; for (;;) {
+ block $noSegment loop $nextSegment
+ ;; if ( ineedle === 0 ) { return -1; }
+ local.get $ineedle
+ i32.eqz
+ if
+ i32.const -1
+ return
+ end
+ ;; ineedle -= 1;
+ local.get $ineedle
+ i32.const -1
+ i32.add
+ local.tee $ineedle
+ ;; let c = this.buf[ineedle];
+ i32.load8_u
+ local.set $c
+ ;; for (;;) {
+ block $foundSegment loop $findSegment
+ ;; v = this.buf32[icell+2];
+ local.get $icell
+ i32.load offset=8
+ local.tee $v
+ ;; i0 = char0 + (v >>> 8);
+ i32.const 8
+ i32.shr_u
+ local.get $char0
+ i32.add
+ local.tee $i0
+ ;; if ( this.buf[i0] === c ) { break; }
+ i32.load8_u
+ local.get $c
+ i32.eq
+ br_if $foundSegment
+ ;; icell = this.buf32[icell+0];
+ local.get $icell
+ i32.load
+ i32.const 2
+ i32.shl
+ local.tee $icell
+ i32.eqz
+ if
+ i32.const -1
+ return
+ end
+ br 0
+ end end
+ ;; let n = v & 0x7F;
+ local.get $v
+ i32.const 0x7F
+ i32.and
+ local.tee $n
+ ;; if ( n > 1 ) {
+ i32.const 1
+ i32.gt_u
+ if
+ ;; n -= 1;
+ local.get $n
+ i32.const -1
+ i32.add
+ local.tee $n
+ ;; if ( n > ineedle ) { return -1; }
+ local.get $ineedle
+ i32.gt_u
+ if
+ i32.const -1
+ return
+ end
+ local.get $i0
+ i32.const 1
+ i32.add
+ local.tee $i0
+ ;; const i1 = i0 + n;
+ local.get $n
+ i32.add
+ local.set $i1
+ ;; do {
+ loop
+ ;; ineedle -= 1;
+ local.get $ineedle
+ i32.const -1
+ i32.add
+ local.tee $ineedle
+ ;; if ( this.buf[i0] !== this.buf[ineedle] ) { return -1; }
+ i32.load8_u
+ local.get $i0
+ i32.load8_u
+ i32.ne
+ if
+ i32.const -1
+ return
+ end
+ ;; i0 += 1;
+ local.get $i0
+ i32.const 1
+ i32.add
+ local.tee $i0
+ ;; } while ( i0 < i1 );
+ local.get $i1
+ i32.lt_u
+ br_if 0
+ end
+ end
+ ;; if ( (v & 0x80) !== 0 ) {
+ local.get $v
+ i32.const 0x80
+ i32.and
+ if
+ ;; if ( ineedle === 0 || buf8[ineedle-1] === 0x2E /* '.' */ ) {
+ ;; return ineedle;
+ ;; }
+ local.get $ineedle
+ i32.eqz
+ if
+ i32.const 0
+ return
+ end
+ local.get $ineedle
+ i32.const -1
+ i32.add
+ i32.load8_u
+ i32.const 0x2E
+ i32.eq
+ if
+ local.get $ineedle
+ return
+ end
+ end
+ ;; icell = this.buf32[icell+1];
+ local.get $icell
+ i32.load offset=4
+ i32.const 2
+ i32.shl
+ local.tee $icell
+ ;; if ( icell === 0 ) { break; }
+ br_if 0
+ end end
+ ;; return -1;
+ i32.const -1
+)
+
+;;
+;; unsigned int add(icell)
+;;
+;; Add a new hostname to a trie which root cell is passed as argument.
+;;
+(func (export "add")
+ (param $iroot i32) ;; index of root cell of the trie
+ (result i32) ;; result: 0 not added, 1 = added
+ (local $icell i32) ;; index of current cell in the trie
+ (local $lhnchar i32) ;; number of characters left to process in hostname
+ (local $char0 i32) ;; offset to start of character data section
+ (local $v i32) ;; integer value describing a segment
+ (local $isegchar0 i32) ;; offset to start of current segment's character data
+ (local $isegchar i32)
+ (local $lsegchar i32) ;; number of character in current segment
+ (local $inext i32) ;; index of next cell to process
+ (local $boundaryBit i32) ;; the boundary bit state of the current cell
+ ;;
+ ;; let lhnchar = this.buf[255];
+ i32.const 255
+ i32.load8_u
+ local.tee $lhnchar
+ ;; if ( lhnchar === 0 ) { return 0; }
+ i32.eqz
+ if
+ i32.const 0
+ return
+ end
+ ;; if (
+ ;; (this.buf32[HNBIGTRIE_CHAR0_SLOT] - this.buf32[HNBIGTRIE_TRIE1_SLOT]) < 24 ||
+ ;; (this.buf.length - this.buf32[HNBIGTRIE_CHAR1_SLOT]) < 256
+ ;; ) {
+ ;; this.growBuf();
+ ;; }
+ i32.const 264
+ i32.load
+ i32.const 260
+ i32.load
+ i32.sub
+ i32.const 24
+ i32.lt_u
+ if
+ call $growBuf
+ else
+ memory.size
+ i32.const 16
+ i32.shl
+ i32.const 268
+ i32.load
+ i32.sub
+ i32.const 256
+ i32.lt_u
+ if
+ call $growBuf
+ end
+ end
+ ;; let icell = this.buf32[iroot+0];
+ local.get $iroot
+ i32.const 2
+ i32.shl
+ local.tee $iroot
+ i32.load
+ i32.const 2
+ i32.shl
+ local.tee $icell
+ ;; if ( this.buf32[icell+2] === 0 ) {
+ i32.eqz
+ if
+ ;; this.buf32[iroot+0] = this.addLeafCell(lhnchar);
+ ;; return 1;
+ local.get $iroot
+ local.get $lhnchar
+ call $addLeafCell
+ i32.store
+ i32.const 1
+ return
+ end
+ ;; const char0 = this.buf32[HNBIGTRIE_CHAR0_SLOT];
+ i32.const 264
+ i32.load
+ local.set $char0
+ ;; for (;;) {
+ loop $nextSegment
+ ;; const v = this.buf32[icell+2];
+ local.get $icell
+ i32.load offset=8
+ local.tee $v
+ ;; let isegchar0 = char0 + (v >>> 8);
+ i32.const 8
+ i32.shr_u
+ local.get $char0
+ i32.add
+ local.tee $isegchar0
+ ;; if ( this.buf[isegchar0] !== this.buf[lhnchar-1] ) {
+ i32.load8_u
+ local.get $lhnchar
+ i32.const -1
+ i32.add
+ i32.load8_u
+ i32.ne
+ if
+ ;; inext = this.buf32[icell+0];
+ local.get $icell
+ i32.load
+ local.tee $inext
+ ;; if ( inext === 0 ) {
+ i32.eqz
+ if
+ ;; this.buf32[icell+0] = this.addLeafCell(lhnchar);
+ local.get $icell
+ local.get $lhnchar
+ call $addLeafCell
+ i32.store
+ ;; return 1;
+ i32.const 1
+ return
+ end
+ ;; icell = inext;
+ local.get $inext
+ i32.const 2
+ i32.shl
+ local.set $icell
+ br $nextSegment
+ end
+ ;; let isegchar = 1;
+ i32.const 1
+ local.set $isegchar
+ ;; lhnchar -= 1;
+ local.get $lhnchar
+ i32.const -1
+ i32.add
+ local.set $lhnchar
+ ;; const lsegchar = v & 0x7F;
+ local.get $v
+ i32.const 0x7F
+ i32.and
+ local.tee $lsegchar
+ ;; if ( lsegchar !== 1 ) {
+ i32.const 1
+ i32.ne
+ if
+ ;; for (;;) {
+ block $mismatch loop
+ ;; if ( isegchar === lsegchar ) { break; }
+ local.get $isegchar
+ local.get $lsegchar
+ i32.eq
+ br_if $mismatch
+ local.get $lhnchar
+ i32.eqz
+ br_if $mismatch
+ ;; if ( this.buf[isegchar0+isegchar] !== this.buf[lhnchar-1] ) { break; }
+ local.get $isegchar0
+ local.get $isegchar
+ i32.add
+ i32.load8_u
+ local.get $lhnchar
+ i32.const -1
+ i32.add
+ i32.load8_u
+ i32.ne
+ br_if $mismatch
+ ;; isegchar += 1;
+ local.get $isegchar
+ i32.const 1
+ i32.add
+ local.set $isegchar
+ ;; lhnchar -= 1;
+ local.get $lhnchar
+ i32.const -1
+ i32.add
+ local.set $lhnchar
+ br 0
+ end end
+ end
+ ;; const boundaryBit = v & 0x80;
+ local.get $v
+ i32.const 0x80
+ i32.and
+ local.set $boundaryBit
+ ;; if ( isegchar === lsegchar ) {
+ local.get $isegchar
+ local.get $lsegchar
+ i32.eq
+ if
+ ;; if ( lhnchar === 0 ) {
+ local.get $lhnchar
+ i32.eqz
+ if
+ ;; if ( boundaryBit !== 0 ) { return 0; }
+ local.get $boundaryBit
+ if
+ i32.const 0
+ return
+ end
+ ;; this.buf32[icell+2] = v | 0x80;
+ local.get $icell
+ local.get $v
+ i32.const 0x80
+ i32.or
+ i32.store offset=8
+ else
+ ;; if ( boundaryBit !== 0 ) {
+ local.get $boundaryBit
+ if
+ ;; if ( this.buf[lhnchar-1] === 0x2E /* '.' */ ) { return -1; }
+ local.get $lhnchar
+ i32.const -1
+ i32.add
+ i32.load8_u
+ i32.const 0x2E
+ i32.eq
+ if
+ i32.const -1
+ return
+ end
+ end
+ ;; inext = this.buf32[icell+1];
+ local.get $icell
+ i32.load offset=4
+ local.tee $inext
+ ;; if ( inext !== 0 ) {
+ if
+ ;; icell = inext;
+ local.get $inext
+ i32.const 2
+ i32.shl
+ local.set $icell
+ ;; continue;
+ br $nextSegment
+ end
+ ;; this.buf32[icell+1] = this.addLeafCell(lhnchar);
+ local.get $icell
+ local.get $lhnchar
+ call $addLeafCell
+ i32.store offset=4
+ end
+ else
+ ;; isegchar0 -= char0;
+ local.get $icell
+ local.get $isegchar0
+ local.get $char0
+ i32.sub
+ local.tee $isegchar0
+ ;; this.buf32[icell+2] = isegchar0 << 8 | isegchar;
+ i32.const 8
+ i32.shl
+ local.get $isegchar
+ i32.or
+ i32.store offset=8
+ ;; inext = this.addCell(
+ ;; 0,
+ ;; this.buf32[icell+1],
+ ;; isegchar0 + isegchar << 8 | boundaryBit | lsegchar - isegchar
+ ;; );
+ local.get $icell
+ i32.const 0
+ local.get $icell
+ i32.load offset=4
+ local.get $isegchar0
+ local.get $isegchar
+ i32.add
+ i32.const 8
+ i32.shl
+ local.get $boundaryBit
+ i32.or
+ local.get $lsegchar
+ local.get $isegchar
+ i32.sub
+ i32.or
+ call $addCell
+ local.tee $inext
+ ;; this.buf32[icell+1] = inext;
+ i32.store offset=4
+ ;; if ( lhnchar !== 0 ) {
+ local.get $lhnchar
+ if
+ ;; this.buf32[inext+0] = this.addLeafCell(lhnchar);
+ local.get $inext
+ i32.const 2
+ i32.shl
+ local.get $lhnchar
+ call $addLeafCell
+ i32.store
+ else
+ ;; this.buf32[icell+2] |= 0x80;
+ local.get $icell
+ local.get $icell
+ i32.load offset=8
+ i32.const 0x80
+ i32.or
+ i32.store offset=8
+ end
+ end
+ ;; return 1;
+ i32.const 1
+ return
+ end
+ ;;
+ i32.const 1
+)
+
+;;
+;; Private functions
+;;
+
+;;
+;; unsigned int addCell(idown, iright, v)
+;;
+;; Add a new cell, return cell index.
+;;
+(func $addCell
+ (param $idown i32)
+ (param $iright i32)
+ (param $v i32)
+ (result i32) ;; result: index of added cell
+ (local $icell i32)
+ ;;
+ ;; let icell = this.buf32[HNBIGTRIE_TRIE1_SLOT];
+ ;; this.buf32[HNBIGTRIE_TRIE1_SLOT] = icell + 12;
+ i32.const 260
+ i32.const 260
+ i32.load
+ local.tee $icell
+ i32.const 12
+ i32.add
+ i32.store
+ ;; this.buf32[icell+0] = idown;
+ local.get $icell
+ local.get $idown
+ i32.store
+ ;; this.buf32[icell+1] = iright;
+ local.get $icell
+ local.get $iright
+ i32.store offset=4
+ ;; this.buf32[icell+2] = v;
+ local.get $icell
+ local.get $v
+ i32.store offset=8
+ ;; return icell;
+ local.get $icell
+ i32.const 2
+ i32.shr_u
+)
+
+;;
+;; unsigned int addLeafCell(lsegchar)
+;;
+;; Add a new cell, return cell index.
+;;
+(func $addLeafCell
+ (param $lsegchar i32)
+ (result i32) ;; result: index of added cell
+ (local $r i32)
+ (local $i i32)
+ ;; const r = this.buf32[TRIE1_SLOT] >>> 2;
+ i32.const 260
+ i32.load
+ local.tee $r
+ ;; let i = r;
+ local.set $i
+ ;; while ( lsegchar > 127 ) {
+ block $lastSegment loop
+ local.get $lsegchar
+ i32.const 127
+ i32.le_u
+ br_if $lastSegment
+ ;; this.buf32[i+0] = 0;
+ local.get $i
+ i32.const 0
+ i32.store
+ ;; this.buf32[i+1] = i + 3;
+ local.get $i
+ local.get $i
+ i32.const 12
+ i32.add
+ i32.const 2
+ i32.shr_u
+ i32.store offset=4
+ ;; this.buf32[i+2] = this.addSegment(lsegchar, lsegchar - 127);
+ local.get $i
+ local.get $lsegchar
+ local.get $lsegchar
+ i32.const 127
+ i32.sub
+ call $addSegment
+ i32.store offset=8
+ ;; lsegchar -= 127;
+ local.get $lsegchar
+ i32.const 127
+ i32.sub
+ local.set $lsegchar
+ ;; i += 3;
+ local.get $i
+ i32.const 12
+ i32.add
+ local.set $i
+ br 0
+ end end
+ ;; this.buf32[i+0] = 0;
+ local.get $i
+ i32.const 0
+ i32.store
+ ;; this.buf32[i+1] = 0;
+ local.get $i
+ i32.const 0
+ i32.store offset=4
+ ;; this.buf32[i+2] = this.addSegment(lsegchar, 0) | 0x80;
+ local.get $i
+ local.get $lsegchar
+ i32.const 0
+ call $addSegment
+ i32.const 0x80
+ i32.or
+ i32.store offset=8
+ ;; this.buf32[TRIE1_SLOT] = i + 3 << 2;
+ i32.const 260
+ local.get $i
+ i32.const 12
+ i32.add
+ i32.store
+ ;; return r;
+ local.get $r
+ i32.const 2
+ i32.shr_u
+)
+
+;;
+;; unsigned int addSegment(lsegchar, lsegend)
+;;
+;; Store a segment of characters and return a segment descriptor. The segment
+;; is created from the character data in the needle buffer.
+;;
+(func $addSegment
+ (param $lsegchar i32)
+ (param $lsegend i32)
+ (result i32) ;; result: segment descriptor
+ (local $char1 i32) ;; offset to end of character data section
+ (local $isegchar i32) ;; relative offset to first character of segment
+ (local $i i32) ;; iterator
+ ;;
+ ;; if ( lsegchar === 0 ) { return 0; }
+ local.get $lsegchar
+ i32.eqz
+ if
+ i32.const 0
+ return
+ end
+ ;; let char1 = this.buf32[HNBIGTRIE_CHAR1_SLOT];
+ i32.const 268
+ i32.load
+ local.tee $char1
+ ;; const isegchar = char1 - this.buf32[HNBIGTRIE_CHAR0_SLOT];
+ i32.const 264
+ i32.load
+ i32.sub
+ local.set $isegchar
+ ;; let i = lsegchar;
+ local.get $lsegchar
+ local.set $i
+ ;; do {
+ loop
+ ;; this.buf[char1++] = this.buf[--i];
+ local.get $char1
+ local.get $i
+ i32.const -1
+ i32.add
+ local.tee $i
+ i32.load8_u
+ i32.store8
+ local.get $char1
+ i32.const 1
+ i32.add
+ local.set $char1
+ ;; } while ( i !== lsegend );
+ local.get $i
+ local.get $lsegend
+ i32.ne
+ br_if 0
+ end
+ ;; this.buf32[HNBIGTRIE_CHAR1_SLOT] = char1;
+ i32.const 268
+ local.get $char1
+ i32.store
+ ;; return isegchar << 8 | lsegchar - lsegend;
+ local.get $isegchar
+ i32.const 8
+ i32.shl
+ local.get $lsegchar
+ local.get $lsegend
+ i32.sub
+ i32.or
+)
+
+;;
+;; module end
+;;
+)
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-22 12:42:01 +0000