rumtk_core/
cpu.rs

1/*
2 *     rumtk attempts to implement HL7 and medical protocols for interoperability in medicine.
3 *     This toolkit aims to be reliable, simple, performant, and standards compliant.
4 *     Copyright (C) 2026  Luis M. Santos, M.D. <lsantos@medicalmasses.com>
5 *     Copyright (C) 2026  MedicalMasses L.L.C. <contact@medicalmasses.com>
6 *
7 *     This program is free software: you can redistribute it and/or modify
8 *     it under the terms of the GNU General Public License as published by
9 *     the Free Software Foundation, either version 3 of the License, or
10 *     (at your option) any later version.
11 *
12 *     This program is distributed in the hope that it will be useful,
13 *     but WITHOUT ANY WARRANTY; without even the implied warranty of
14 *     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 *     GNU General Public License for more details.
16 *
17 *     You should have received a copy of the GNU General Public License
18 *     along with this program.  If not, see <https://www.gnu.org/licenses/>.
19 */
20use crate::base::RUMVec;
21pub use branches::{likely as cpu_likely_branch, prefetch_read_data, unlikely as cpu_unlikely_branch};
22pub use std::simd::prelude::*;
23
24pub const CPU_L1_PREFETCH: i32 = 0;
25pub const CPU_L2_PREFETCH: i32 = 1;
26pub const CPU_L3_PREFETCH: i32 = 2;
27pub const CPU_NONTEMPORAL_PREFETCH: i32 = 3;
28pub const CPU_L1_CACHE_LINE_SIZE: usize = 64; // Number of bytes in a typical x86_64 CPU L1 cache line.
29pub const CPU_L1_CACHE_SIZE: usize = 32 * 1024; // Number of bytes in a typical x86_64 CPU L1 cache per core.
30pub const CPU_PAGE_SIZE: usize = 4 * 1024; // Typical CPU page size
31pub const CPU_SIMD_64_SIZE: usize = 64;
32pub const CPU_SIMD_32_SIZE: usize = 32;
33pub const CPU_SIMD_16_SIZE: usize = 16;
34pub const CPU_SIMD_8_SIZE: usize = 8;
35pub const CPU_SEARCH_WINDOW_1024_SIZE: usize = 1024;
36pub const CPU_SEARCH_WINDOW_512_SIZE: usize = 512;
37pub const CPU_SEARCH_WINDOW_256_SIZE: usize = 256;
38pub const CPU_SEARCH_WINDOW_128_SIZE: usize = 128;
39pub const CPU_SEARCH_WINDOW_64_SIZE: usize = 64;
40pub const CPU_SEARCH_WINDOW_32_SIZE: usize = 32;
41pub const CPU_SEARCH_WINDOW_16_SIZE: usize = 16;
42
43
44pub type u8xN<const SEARCH_WINDOW_SIZE: usize> = Simd<u8, SEARCH_WINDOW_SIZE>;
45
46////////////////////////////////////////CPU CACHE HINTS///////////////////////////////
47#[inline]
48pub fn cpu_l3_prefetch(data: *const u8) {
49    prefetch_read_data::<u8, CPU_L3_PREFETCH>(data);
50}
51
52#[inline]
53pub fn cpu_l2_prefetch(data: *const u8) {
54    prefetch_read_data::<u8, CPU_L2_PREFETCH>(data);
55}
56
57#[inline]
58pub fn cpu_l1_prefetch(data: *const u8) {
59    prefetch_read_data::<u8, CPU_L1_PREFETCH>(data);
60}
61
62#[inline(always)]
63pub fn cpu_slice_to_array<const SLICE_SIZE: usize>(chunk: &[u8]) -> &[u8; SLICE_SIZE] {
64    chunk.try_into().expect("length mismatch")
65}
66
67#[inline(always)]
68pub fn cpu_slice_to_array_padded<const SLICE_SIZE: usize, const PAD: u8>(chunk: &[u8]) -> [u8; SLICE_SIZE] {
69    let mut result = [0u8; SLICE_SIZE];
70    let input_len = chunk.len();
71    let left = SLICE_SIZE - input_len;
72    let processed = SLICE_SIZE - left;
73
74    for i in 0..input_len {
75        result[i] = chunk[i];
76    }
77
78    for i in 0..left {
79        result[processed + i] = PAD;
80    }
81
82    result
83}
84
85#[inline(always)]
86pub fn cpu_slice_splat<const SLICE_SIZE: usize>(input: &[u8]) -> [u8; SLICE_SIZE] {
87    let mut result = [0u8; SLICE_SIZE];
88
89    for chunk in result.chunks_mut(input.len()) {
90        if chunk.len() == input.len() {
91            for i in 0..input.len() {
92                chunk[i] = input[i]
93            }
94        } else {
95            for i in 0..chunk.len() {
96                chunk[i] = input[i];
97            }
98        }
99    }
100
101    result
102}
103
104////////////////////////////////////////SIMD MASKS//////////////////////////////////////////
105#[inline(always)]
106pub fn cpu_simd_shift_right_n<const LANE_SIZE: usize, const SHIFT: usize, const PAD: u8>(item: &u8xN<LANE_SIZE>) -> u8xN<LANE_SIZE> {
107    item.shift_elements_right::<SHIFT>(PAD)
108}
109
110#[inline(always)]
111pub fn cpu_simd_masks<const LANE_SIZE: usize>(pattern: &[u8]) -> RUMVec<u8xN<LANE_SIZE>> {
112    let mask = u8xN::<LANE_SIZE>::from_array(cpu_slice_splat(pattern));
113    let mut masks = RUMVec::<u8xN<LANE_SIZE>>::with_capacity(pattern.len());
114
115    masks.push(mask);
116
117    for i in 1..pattern.len() {
118        let shifted = cpu_simd_shift_right_n::<LANE_SIZE, 1, 0>(&mask);
119        masks.push(shifted);
120    }
121
122    masks
123}
124
125////////////////////////////////////////SEARCH FOR NEEDLE IN HAYSTACK///////////////////////////////
126
127#[inline(always)]
128pub fn cpu_find_fallback(chunk: &[u8], byte: u8) -> Option<usize> {
129    chunk.iter().position(|c| *c==byte)
130}
131
132#[inline]
133fn cpu_find_simd_avx2_n<const SEARCH_WINDOW_SIZE: usize>(data_vec: &u8xN<SEARCH_WINDOW_SIZE>, target: u8xN<SEARCH_WINDOW_SIZE>) -> Option<usize> {
134    let mask = data_vec.simd_eq(target);
135
136    if mask.any() {
137        let bitmask = mask.to_bitmask();
138        let lane_i = bitmask.trailing_zeros() as usize;
139        return Some(lane_i);
140    }
141
142    None
143}
144
145#[inline]
146pub fn cpu_find_simd_n<const LANE_SIZE: usize>
147(
148    chunk: &[u8],
149    byte: u8,
150) -> Option<usize>
151{
152    let mask = u8xN::<LANE_SIZE>::splat(byte);
153    let (prefix, middle, postfix) = chunk.as_simd::<LANE_SIZE>();
154
155    match cpu_find_fallback(prefix, byte) {
156        Some(lane_i) => return Some(lane_i),
157        None => {},
158    }
159
160    for (i, window) in middle.into_iter().enumerate() {
161        match cpu_find_simd_avx2_n::<LANE_SIZE>(window, mask) {
162            Some(lane_i) => {
163                return Some(prefix.len() + (i * LANE_SIZE) + lane_i)
164            },
165            None => continue,
166        }
167    }
168
169    match cpu_find_fallback(postfix, byte) {
170        Some(lane_i) => Some(prefix.len() + (middle.len() * LANE_SIZE) + lane_i),
171        None => None,
172    }
173}
174
175#[inline]
176pub fn cpu_find_simd(window: &[u8], byte: u8) -> Option<usize> {
177    cpu_find_simd_n::<CPU_SIMD_64_SIZE>(
178        window,
179        byte,
180    )
181}
182
183/////////////////////////////Replacement Helpers///////////////////////////////
184
185#[inline(always)]
186pub fn cpu_find_replace_simd_n<const LANE_SIZE: usize>(chunk: &mut [u8], pattern: u8xN<LANE_SIZE>, replacement: u8xN<LANE_SIZE>) {
187    let simd_chunk = u8xN::<LANE_SIZE>::from_array(cpu_slice_to_array_padded::<LANE_SIZE, 0>(chunk));
188    let bitmask = simd_chunk.simd_eq(pattern);
189
190    if bitmask.any() {
191        replacement.store_select(chunk, bitmask);
192    }
193}
194
195#[inline(always)]
196pub fn cpu_replace_simd_n<const LANE_SIZE: usize>(data: &mut [u8], pattern: u8, replacement: u8) {
197    let mask = u8xN::<LANE_SIZE>::splat(pattern);
198    let simd_replacement = u8xN::<LANE_SIZE>::splat(replacement);
199
200    for mut chunk in data.chunks_mut(LANE_SIZE) {
201        cpu_find_replace_simd_n::<LANE_SIZE>(&mut chunk[..], mask, simd_replacement);
202    }
203}
204
205#[inline(always)]
206pub fn cpu_replace_simd(data: &mut [u8], pattern: u8, replacement: u8) {
207    cpu_replace_simd_n::<CPU_SIMD_64_SIZE>(data, pattern, replacement)
208}
209
210/////////////////////////////GATHER ALL INDICES OF NEEDLE IN HAYSTACK///////////////////////////////
211pub type CPUTokenStackIndex<const LANE_SIZE: usize> = [u32; LANE_SIZE];
212pub type CPUTokenRelativeStackInfo<const LANE_SIZE: usize> = (usize, CPUTokenStackIndex<LANE_SIZE>);
213pub type CPUTokenIndexCollection = RUMVec<u32>;
214pub type CPUTokenIndexSet = (u8, RUMVec<u32>);
215pub type CPUTokenSet = (u8, u32);
216pub type CPUTokenSetCollection = RUMVec<CPUTokenSet>;
217
218#[inline(always)]
219pub fn cpu_collect_fallback<const LANE_SIZE: usize>(chunk: &[u8], byte: u8, offset: usize) -> CPUTokenRelativeStackInfo<LANE_SIZE> {
220    let mut results: CPUTokenStackIndex<LANE_SIZE> = [0; LANE_SIZE];
221    let mut length = 0;
222
223    for i in 0..chunk.len() {
224        if chunk[i]==byte {
225            let pos = (offset + i) as usize;
226            results[length] = pos as u32;
227            length += 1;
228        }
229    }
230
231    (length, results)
232}
233
234#[inline]
235fn cpu_collect_simd_avx2_n<const LANE_SIZE: usize>(data_vec: &u8xN<LANE_SIZE>, target: u8xN<LANE_SIZE>, offset: usize) -> Option<CPUTokenRelativeStackInfo<LANE_SIZE>> {
236    let mut results: CPUTokenStackIndex<LANE_SIZE> = [0; LANE_SIZE];
237    let mut length = 0;
238
239    let mask = data_vec.simd_eq(target);
240
241    if cpu_unlikely_branch(mask.any()) {
242        let items = mask.to_array();
243
244        for i in 0..items.len() {
245            if cpu_unlikely_branch(items[i]) {
246                let pos = (offset + i) as usize;
247                results[length] = pos as u32;
248                length += 1;
249            }
250        }
251
252        return Some((length, results));
253    }
254
255    None
256}
257
258#[inline]
259pub fn cpu_collect_simd_n<const LANE_SIZE: usize>
260(
261    chunk: &[u8],
262    byte: u8,
263    offset: usize
264) -> CPUTokenIndexCollection
265{
266    let mask = u8xN::<LANE_SIZE>::splat(byte);
267    let (prefix, middle, postfix) = chunk.as_simd::<LANE_SIZE>();
268
269    let mut local_offset: usize = offset;
270    let (initial, data): CPUTokenRelativeStackInfo<LANE_SIZE> = cpu_collect_fallback(prefix, byte, local_offset);
271    let mut positions: CPUTokenIndexCollection = CPUTokenIndexCollection::from(&data[..initial]);
272    local_offset += prefix.len();
273
274    for window in middle.into_iter() {
275        match cpu_collect_simd_avx2_n::<LANE_SIZE>(window, mask, local_offset) {
276            Some((len, data)) => {
277                positions.extend_from_slice(&data[..len]);
278            },
279            None => {},
280        };
281        local_offset += LANE_SIZE;
282    }
283
284    let (len, data): CPUTokenRelativeStackInfo<LANE_SIZE> = cpu_collect_fallback(postfix, byte, local_offset);
285    positions.extend_from_slice(&data[..len]);
286
287    positions
288}
289
290#[inline]
291pub fn cpu_collect_simd(window: &[u8], byte: u8, offset: usize) -> CPUTokenIndexSet {
292    let indx = cpu_collect_simd_n::<CPU_SIMD_64_SIZE>(
293        window,
294        byte,
295        offset
296    );
297    (byte, indx)
298}
299
300#[inline]
301pub fn cpu_tokenize_simd<const WINDOW_SIZE: usize>(haystack: &[u8], bytes: &[u8]) -> CPUTokenSetCollection
302{
303    let mut results = CPUTokenSetCollection::with_capacity(1024 * size_of::<CPUTokenSet>());
304    let mut offset = 0;
305
306    for window in haystack.chunks(WINDOW_SIZE) {
307        for byte in bytes {
308            let (b, indx) = cpu_collect_simd(window, *byte, offset);
309
310            if !indx.is_empty() {
311                for tok_indx in indx {
312                    results.push((b, tok_indx));
313                }
314            }
315        }
316        offset += window.len();
317    }
318
319    results.sort_unstable_by(|a,b| a.1.cmp(&b.1));
320
321    results
322}
323
324#[inline]
325pub fn cpu_tokenize_simd_rev<const WINDOW_SIZE: usize>(haystack: &[u8], bytes: &[u8]) -> CPUTokenSetCollection
326{
327    let reversed: Vec<u8> = bytes.iter().rev().cloned().collect();
328    cpu_tokenize_simd::<WINDOW_SIZE>(haystack, &reversed)
329}
rumtk_core/cpu.rs

rumtk_core/
cpu.rs
