nx_boyer_moore.nx source
↩ module page · 81 lines · 2912 B
1// nx_boyer_moore.nx -- Boyer-Moore string search (bad-character heuristic).
2//
3// Find the first occurrence of `pattern` in `text`, returning the
4// starting byte index or -1. Uses the bad-character rule (a.k.a.
5// Horspool-simplified BM): preprocess pattern into a 256-entry skip
6// table, then scan text right-to-left within each alignment; on
7// mismatch jump ahead by the table.
8//
9// genealogy_id: boyer_moore_1977_cacm
10// lineage_id: single_pattern_exact_string_search
11// references: Boyer & Moore "A Fast String Searching Algorithm",
12// CACM 20(10):762-772, October 1977.
13// license: public_domain (1977 academic publication)
14// complexity: best O(n/m), avg O(n+m), worst O(n*m) (this BM-bad-char
15// variant; full Galil/Apostolico-Giancarlo gives O(n+m)).
16
17// nx_safety_envelope:
18// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
19// sil_target: SIL1
20// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
21// verdict: NOT_YET_EVALUATED
22
23import "nx_syscalls.nx"
24import "nx_tier.nx"
25
26const NX_BM_BAD_TABLE_LEN: nx_size = 256
27
28// Build the bad-character skip table from pattern bytes.
29// table[c] = m - 1 - last_index_of_c_in_pattern (or m if c not in pattern).
30func nx_boyer_moore_build_table(pattern: *u8, m: nx_size, table: *nx_idx) -> nx_int {
31 var i: nx_idx = 0
32 while i < NX_BM_BAD_TABLE_LEN {
33 table[i] = m
34 i = i + 1
35 }
36 var j: nx_idx = 0
37 let last: nx_idx = m - 1
38 while j < last {
39 let c: nx_int = pattern[j] as nx_int
40 table[c] = last - j
41 j = j + 1
42 }
43 return 0
44}
45
46// Search `pattern` (length m) inside `text` (length n). Returns the
47// byte index of the first match, or -1 if no match.
48//
49// Edge cases:
50// m == 0: returns 0 (empty pattern matches at start)
51// m > n: returns -1 (pattern longer than text)
52func nx_boyer_moore_search(text: *u8, n: nx_size,
53 pattern: *u8, m: nx_size) -> nx_idx {
54 if m == 0 { return 0 }
55 if m > n { return -1 }
56
57 let table_raw: *u8 = sys_mmap(NX_BM_BAD_TABLE_LEN * 8)
58 let table: *nx_idx = table_raw as *nx_idx
59 nx_boyer_moore_build_table(pattern, m, table)
60
61 var i: nx_idx = 0 // alignment start in text
62 let limit: nx_idx = n - m
63 while i <= limit {
64 // Compare pattern to text[i..i+m] right-to-left.
65 var j: nx_idx = m - 1
66 var matched: nx_int = 1
67 while matched == 1 {
68 if text[i + j] != pattern[j] {
69 matched = 0
70 let c: nx_int = text[i + j] as nx_int
71 i = i + table[c]
72 j = 0 // break loop
73 }
74 if matched == 1 {
75 if j == 0 { return i } // full match
76 j = j - 1
77 }
78 }
79 }
80 return -1
81}