Kernel Substring Search: An Exploration of Ring 0 Vectorization

An empirical case study and exploration into high-performance UTF-8 (8-bit) and UTF-16 (16-bit wchar_t) substring searching within the Windows kernel environment. The study examines how the cost of entering vector execution in Ring 0 changes the optimal substring-search strategy across buffer sizes, pattern characteristics, and execution environments. Combining Boyer-Moore-Horspool, SWAR, AVX-512, AVX2, and ARM64 NEON, this project examines the low-level trade-offs of kernel-mode vector optimization, cache locality, and general-purpose register (GPR) fallback algorithms. While not strictly benchmark-driven during its design, the repository includes comprehensive hardware telemetry to validate its architectural findings.

Dynamic Ring 0 Routing: Bypasses vector registers for small buffers to eliminate the KeSaveExtendedProcessorState extended processor-state save/restore overhead.
Hybrid Boyer-Moore-Horspool (BMH): Blends sub-linear bad-character skipping with 4x unrolled SIMD memory sliding.
L1 Cache–Conscious Golden Ratio Hashing: Folds wide UTF-16 skip tables from an unfeasible 256KB footprint down to 8KB to ensure residency in the L1 D-Cache.
Hardware-Agnostic SWAR Fallbacks: Implements 64-bit SIMD-Within-A-Register bit-manipulation hacks to process 8 bytes (or 4 wide characters) per cycle without engaging FPU/YMM/ZMM state.
Cross-Architecture Vector Pipelines: Native implementations for x86_64 (AVX-512BW, AVX2) and ARM64 (NEON) with OS XSTATE (XCR0) feature verification.
Experimental BNDM Evaluation: Features Backward Nondeterministic DAWG Matching implementations with an empirical analysis of why bit-parallel automata underperform BMH in kernel workloads.

1. The Kernel Optimization Landscape & Ring 0 Trade-offs

In user-mode applications, maximizing substring search performance is often a matter of streaming vectors directly through AVX-512 or AVX2 pipelines. In Windows kernel mode (Ring 0), vector optimization introduces strict architectural trade-offs:

+-------------------------------------------------------------------------+
|                              Call: Find()                               |
+------------------------------------+------------------------------------+
                                     |
                         Buffer > 20KB (AVX-512) or 6KB (AVX2)?
                                     |
                  +------------------+------------------+
                  | NO                                  | YES
                  v                                     v
     +---------------------------+          +-----------------------+
     |      GPR SWAR /           |          |  KeSaveExtendedState  |
     |     BMH Fast Path         |          +-----------+-----------+
     | (Zero FPU State Overhead) |                      |
     +---------------------------+          +-----------v-----------+
                                            | AVX-512/AVX2/NEON     |
                                            |    4x Unrolled Slide  |
                                            +-----------+-----------+
                                                        |
                                            +-----------v-----------+
                                            | KeRestoreExtendedState|
                                            +-----------------------+

The Ring 0 Extended Processor State Overhead

The Windows kernel does not preserve floating-point and extended vector (XMM/YMM/ZMM) registers across thread context switches by default. To safely issue SIMD instructions in Ring 0 without corrupting user-mode thread state, the caller must allocate an XSTATE_SAVE structure and invoke KeSaveExtendedProcessorState (or KeSaveFloatingPointState on ARM64).

This state preservation routine writes processor context to memory via XSAVE/XRSTOR, introducing fixed microsecond overheads that severely penalize short operations:

AVX2 (XSTATE_MASK_AVX): Requires backing up ~800 bytes of YMM register state.
AVX-512 (XSTATE_MASK_AVX512_FULL): Requires backing up ~2.7 KB of ZMM and Opmask (k0–k7) register state, drastically increasing the context switch penalty.

Smart Auto Routing & Bypass

Smart Auto is the default runtime routing mode (SearchEngine::Auto) that selects between the GPR/SWAR/BMH path and the vectorized path according to the implementation's buffer-size threshold, minimum unroll window, and OS-enabled processor capabilities (RtlGetEnabledExtendedFeatures):

Small Buffers (<= 6 KB on x64 / <= 1 KB on ARM64): Bypasses vector registers completely and routes directly to the GPR-based BMH/SWAR fallback, incurring zero floating-point state-save overhead.
Medium Buffers (6 KB – 20 KB): Wraps execution in safe YMM state-saving calls to unleash the AVX2 pipeline. AVX-512 is restricted here because its massive 2.7 KB state-save latency eclipses the throughput gains on buffers of this size.
Large Buffers (>= 20 KB): Fully amortizes the AVX-512 ZMM state-saving overhead, unleashing extreme 64-byte unrolled memory streaming.

IRQL Constraints & Memory Allocation

Table precomputation in Initialize() allocates the skip/mask tables from the Non-Paged Pool (ExAllocatePool2 with POOL_FLAG_NON_PAGED | POOL_FLAG_UNINITIALIZED | POOL_FLAG_CACHE_ALIGNED). While Initialize() is annotated with PAGED_CODE() and must execute at PASSIVE_LEVEL or APC_LEVEL, keeping the lookup table in non-paged cache-aligned memory allows Find() to execute safely at up to DISPATCH_LEVEL (provided the caller's Text and Pattern buffers are also resident in non-paged memory).

2. Algorithm Architecture: Hybrid BMH

The primary production engines (CKmStrSearch8 and CKmStrSearch16) combine Boyer-Moore-Horspool bad-character shift rules with unrolled vector sliding.

8-Bit Architecture (`CKmStrSearch8`)

Flat 256-Entry Lookup Table: Precomputes a 1KB bad-character jump table for all ASCII/extended-ASCII byte values in non-paged pool.
Pattern Length Bifurcation: Long patterns (>= 128 chars for AVX2/NEON; >= 256 chars for AVX-512) benefit from sub-linear jumping because the skip distance overcomes the latency of memory table lookups. Short patterns bypass table lookups entirely to avoid pipeline-stalling memory dependencies, executing a 4x unrolled pure vector slide across the text buffer.

16-Bit Architecture (`CKmStrSearch16`)

UTF-16 characters (wchar_t) span a 65,536 value space. A naive BMH table would require 256KB (65536 * 4 bytes), guaranteed to blow out the CPU's L1 Data Cache (typically 32KB–48KB per core), leading to continuous L2/L3 cache misses.

16-Bit Character (ch) 
        |
        v
 [ ch * 0x9E3779B9U ]  ---> Multiplicative Hash (Golden Ratio 2^32 / phi)
        |
   (hash >> 21)        ---> 11-Bit Extraction (0 .. 2047)
        |
        v
  [ 8KB Table ]        ---> 2,048-entry skip table designed to remain L1-cache resident

Golden Ratio Multiplicative Hashing: Characters are hashed into an 11-bit index (2048 entries). By folding the sparse 256KB state space into a dense 8KB footprint, the algorithm inherently prevents the cache thrashing that degrades standard wide-character BMH implementations.
Cache Residency & Allocation: The table occupies 8KB, keeping it well within a typical L1 D-cache footprint, allocated with POOL_FLAG_NON_PAGED | POOL_FLAG_CACHE_ALIGNED to prevent Translation Lookaside Buffer (TLB) invalidation and page faults during high-IRQL memory scanning.
Collision Safety: On bucket collisions, the smallest jump distance is stored. While hash collisions slightly reduce skip aggressiveness, correctness is preserved.

3. Execution Engines: SIMD vs. SWAR

AVX-512BW (ZMM Registers & Native Opmasks)

The highest-throughput engine utilizes AVX-512 Byte/Word instructions. It evaluates 256 bytes per iteration using four unrolled 64-byte ZMM registers. Unlike AVX2, which requires expensive bit-packing (_mm256_movemask_epi8), AVX-512 generates hardware bitmasks (__mmask64 / __mmask32) natively from the comparison instruction.

AVX-512 Vectorization Pipeline (4x Unrolled)
+-----------------------------------------------------------------------------------+
| Lane 0: [ 64 Bytes ZMM0 ] === cmpeq_epi8_mask(vLast) ===> __mmask64 mask0         |
| Lane 1: [ 64 Bytes ZMM1 ] === cmpeq_epi8_mask(vLast) ===> __mmask64 mask1         |
| Lane 2: [ 64 Bytes ZMM2 ] === cmpeq_epi8_mask(vLast) ===> __mmask64 mask2         |
| Lane 3: [ 64 Bytes ZMM3 ] === cmpeq_epi8_mask(vLast) ===> __mmask64 mask3         |
|                                                                                   |
| Evaluate: if ((mask0 | mask1 | mask2 | mask3) != 0) -> _BitScanForward64()        |
+-----------------------------------------------------------------------------------+

AVX2 & ARM64 NEON Engines

The AVX2 pipeline evaluates 128 bytes per iteration using four unrolled YMM registers (_mm256_cmpeq_epi8 / _mm256_cmpeq_epi16).

SIMD Vectorization Pipeline (4x Unrolled AVX2)
+-----------------------------------------------------------------------------+
| Lane 0: [ 32 Bytes YMM0 ] === cmpeq(vLast) ===> Mask0                       |
| Lane 1: [ 32 Bytes YMM1 ] === cmpeq(vLast) ===> Mask1                       |
| Lane 2: [ 32 Bytes YMM2 ] === cmpeq(vLast) ===> Mask2  ===> OR ===> testz   |
| Lane 3: [ 32 Bytes YMM3 ] === cmpeq(vLast) ===> Mask3                       |
+-----------------------------------------------------------------------------+

AVX2 (x86_64): Candidate match offsets are extracted by folding lanes together via _mm256_or_si256, rejecting non-matches with _mm256_testz_si256, and isolating the precise byte offset with _BitScanForward.
NEON (ARM64): Processes 64 bytes per iteration using four 128-bit vector registers (vceqq_u8 / vceqq_u16). Emulates x86 movemask functionality by applying a register-hoisted power-of-two bitshift mask (vandq_u8 / vandq_u16) followed by an across-vector horizontal addition (vaddv_u8 / vaddvq_u16).

SWAR Fallback (SIMD Within A Register)

When operating beneath the 6KB vector threshold, the engine uses 64-bit general-purpose registers to evaluate memory without invoking FPU state.

Using Mycroft’s bit-twiddling zero-byte detection algorithm coupled with hardware bit-scanning:

// 8-Bit SWAR Byte Matching:
ULONGLONG chunk = *reinterpret_cast<const ULONGLONG*>(ptr);
ULONGLONG v     = chunk ^ c8; // Matching bytes become 0x00
ULONGLONG mask  = (v - 0x0101010101010101ULL) & ~v & 0x8080808080808080ULL;
if (mask != 0) [[unlikely]]
{
    ULONG bit;
    _BitScanForward64(&bit, mask);
    return ptr + (bit >> 3); // Exact matching byte offset
}

4. The Experimental Branch: Why BNDM Falls Behind

Located in the Experimental/ directory, KmBndmSearch8 and KmBndmSearch16 explore an alternative algorithmic theory based on Backward Nondeterministic DAWG Matching (BNDM).

These implementations are not pure BNDM. They are heavily hybridized to survive the constraints of the kernel environment:

SWAR Fast-Forwarding & Pre-Stepped Initial State: To prevent CPU branch prediction stalls and severe $O(N \cdot M)$ degradation on repetitive inputs, the algorithm does not blindly execute the automaton. Instead, it uses the GPR-based SWAR technique to rapidly scan for the last character of the pattern and enters the backward automaton pre-stepped past the final character.
State Capacity Bifurcation: The non-deterministic suffix automaton's state is packed entirely into a single 64-bit General Purpose Register (ULONGLONG uD). Therefore, patterns exceeding 64 characters bypass the BNDM logic entirely, defaulting to a fast SWAR linear slide or explicit vector streaming.
Bitmask Bloom Merging (16-bit): To avoid an unfeasible 65,536-entry (512KB) array for 16-bit characters, the wide engine hashes characters into a 16KB (2,048-entry) table. Hash collisions are handled by logically ORing (|=) the bitmasks together. This essentially acts as a Bloom filter, allowing false positive prefix matches that are later discarded by a 64-bit word-accelerated full-string verification loop.
SIMD Bypass: BNDM is utilized strictly as the scalar fallback. For buffers large enough to justify the context switch overhead, BNDM is bypassed entirely in favor of a pure 4x unrolled AVX-512/AVX2/NEON memory slide.

Despite its favorable theoretical/algorithmic characteristics, the BNDM variant consistently lags behind the Hybrid BMH implementation in kernel evaluations. Across both test platforms, Hybrid BMH is 1.4x to 1.7x faster than BNDM on Tiny and Small buffers (<= 6 KB), and up to 2x faster in forced scalar execution on larger workloads. Even on large buffers (1 MB–2 MB) where Smart Auto engages 4x unrolled SIMD streaming, BMH maintains a 20% to 40% throughput lead on bare metal due to its lighter instruction footprint and faster scalar tail handling.

Hardware telemetry reveals four persistent architectural bottlenecks behind this gap:

Scalar Inner Loop Overhead: The Boyer-Moore-Horspool algorithm computes multi-byte jumps with a single bad-character table lookup, whereas BNDM must repeatedly step backward, compute hash lookups, and execute bitwise AND/shift operations per character (uD &= Mask[Hash(ch)]; uD <<= 1;).
Loop-Carried Data Dependencies: BMH streams linear memory chunks that interact predictably with CPU branch predictors and prefetchers, while BNDM creates a strict sequential dependency on the single register state uD, stalling instruction-level parallelism (ILP).
Wide-Character Hash Collision Penalties: In BMH, 16-bit hash collisions only reduce the optimal jump distance, but in wide-character BNDM, collisions force bitmasks to logically merge (|=), generating false prefix matches that require full-string verification loops.
Pre-SIMD Scalar Threshold Deficit: While both algorithms rely on 4x unrolled vector sliding for large buffers, BNDM lags in smaller buffers and unaligned tails due to the heavier overhead of the automaton fallback.

5. Benchmark Analysis

Testing was performed using a multi-threaded kernel test harness (KmStrSearchShared.h). Threads synchronize on a fast mutex before initiating the search loops simultaneously, ensuring the CPU and memory bus are completely saturated to calculate accurate GB/s throughput. CRT strstr/wcsstr serves as the baseline reference.

Environment 1: Intel Core i7-1165G7 (Bare-Metal Windows 11)

Features full AVX-512BW support and 1.25 MB of private L2 cache per core.

8-Bit UTF-8 Performance Profiles

Standard Execution (Single match near end):

Buffer Size	CRT Baseline	Scalar Hybrid	AVX2 Explicit	AVX-512 Explicit	Smart Auto
Tiny (40 B)	3.49 GB/s	1.81 GB/s	1.70 GB/s	1.69 GB/s	1.71 GB/s
Small (256 B)	14.66 GB/s	4.75 GB/s	1.88 GB/s	1.87 GB/s	4.52 GB/s
Medium (10 KB)	22.44 GB/s	8.32 GB/s	39.85 GB/s	45.96 GB/s	41.45 GB/s
Large (1 MB)	22.53 GB/s	8.48 GB/s	64.88 GB/s	83.48 GB/s	83.42 GB/s

Realistic Log Corpus (Simulates real-world kernel log scanning to test skip table entropy and realistic jump distances):

Buffer Size	CRT Baseline	Scalar Hybrid	AVX2 Explicit	AVX-512 Explicit	Smart Auto
Tiny (40 B)	3.32 GB/s	1.62 GB/s	1.54 GB/s	1.53 GB/s	1.53 GB/s
Small (256 B)	14.81 GB/s	4.89 GB/s	1.86 GB/s	1.85 GB/s	4.62 GB/s
Medium (10 KB)	22.60 GB/s	12.14 GB/s	42.49 GB/s	46.41 GB/s	43.57 GB/s
Large (1 MB)	22.58 GB/s	12.65 GB/s	75.93 GB/s	94.15 GB/s	99.98 GB/s

Mismatched Dense Text (Worst-case repetitive partial matches):

Buffer Size	CRT Baseline	Scalar Hybrid	AVX2 Explicit	AVX-512 Explicit	Smart Auto
Tiny (40 B)	0.55 GB/s	1.69 GB/s	1.63 GB/s	1.62 GB/s	1.61 GB/s
Small (256 B)	0.24 GB/s	4.76 GB/s	1.82 GB/s	1.86 GB/s	4.42 GB/s
Medium (10 KB)	0.21 GB/s	12.65 GB/s	39.82 GB/s	45.55 GB/s	42.00 GB/s
Large (1 MB)	0.21 GB/s	13.33 GB/s	66.28 GB/s	84.58 GB/s	84.90 GB/s

16-Bit UTF-16 Performance Profiles

Standard Execution (Single match near end):

Buffer Size	CRT Baseline	Scalar Hybrid	AVX2 Explicit	AVX-512 Explicit	Smart Auto
Tiny (80 B)	6.46 GB/s	3.67 GB/s	3.45 GB/s	3.46 GB/s	3.36 GB/s
Small (512 B)	13.04 GB/s	7.64 GB/s	3.85 GB/s	3.58 GB/s	7.39 GB/s
Medium (20 KB)	26.94 GB/s	12.38 GB/s	56.64 GB/s	66.55 GB/s	61.47 GB/s
Large (2 MB)	23.24 GB/s	12.57 GB/s	45.96 GB/s	49.34 GB/s	51.29 GB/s

Realistic Log Corpus (Simulates real-world kernel log scanning to test skip table entropy and realistic jump distances):

Buffer Size	CRT Baseline	Scalar Hybrid	AVX2 Explicit	AVX-512 Explicit	Smart Auto
Tiny (80 B)	6.15 GB/s	2.97 GB/s	2.97 GB/s	2.88 GB/s	2.76 GB/s
Small (512 B)	15.38 GB/s	7.66 GB/s	4.10 GB/s	3.63 GB/s	7.29 GB/s
Medium (20 KB)	26.78 GB/s	17.90 GB/s	59.33 GB/s	73.27 GB/s	67.22 GB/s
Large (2 MB)	22.98 GB/s	15.06 GB/s	49.26 GB/s	49.92 GB/s	56.35 GB/s

Mismatched Dense Text (Worst-case repetitive partial matches):

Buffer Size	CRT Baseline	Scalar Hybrid	AVX2 Explicit	AVX-512 Explicit	Smart Auto
Tiny (80 B)	0.78 GB/s	3.48 GB/s	3.22 GB/s	3.17 GB/s	3.13 GB/s
Small (512 B)	0.36 GB/s	7.08 GB/s	3.86 GB/s	3.52 GB/s	6.80 GB/s
Medium (20 KB)	0.32 GB/s	13.06 GB/s	55.63 GB/s	65.61 GB/s	59.77 GB/s
Large (2 MB)	0.31 GB/s	13.15 GB/s	49.57 GB/s	54.87 GB/s	55.09 GB/s

Environment 2: Intel Core i7-8086K (VMware Guest Windows 11)

AVX2 supported, AVX-512 not supported.

8-Bit UTF-8 Performance Profiles

Standard Execution (Single match near end):

Buffer Size	CRT Baseline	Scalar Hybrid	AVX2 Explicit	Smart Auto
Tiny (40 B)	2.06 GB/s	1.85 GB/s	1.71 GB/s	1.71 GB/s
Small (256 B)	1.56 GB/s	4.71 GB/s	0.94 GB/s	4.52 GB/s
Medium (10 KB)	1.48 GB/s	8.72 GB/s	31.38 GB/s	22.61 GB/s
Large (1 MB)	1.35 GB/s	8.60 GB/s	49.26 GB/s	48.09 GB/s

Realistic Log Corpus (Simulates real-world kernel log scanning to test skip table entropy and realistic jump distances):

Buffer Size	CRT Baseline	Scalar Hybrid	AVX2 Explicit	Smart Auto
Tiny (40 B)	2.12 GB/s	1.57 GB/s	1.46 GB/s	1.51 GB/s
Small (256 B)	1.59 GB/s	4.76 GB/s	1.04 GB/s	4.57 GB/s
Medium (10 KB)	1.49 GB/s	12.67 GB/s	31.94 GB/s	25.24 GB/s
Large (1 MB)	1.36 GB/s	12.49 GB/s	52.68 GB/s	53.63 GB/s

Mismatched Dense Text (Worst-case repetitive partial matches):

Buffer Size	CRT Baseline	Scalar Hybrid	AVX2 Explicit	Smart Auto
Tiny (40 B)	0.53 GB/s	1.79 GB/s	1.62 GB/s	1.70 GB/s
Small (256 B)	0.25 GB/s	5.22 GB/s	0.57 GB/s	5.00 GB/s
Medium (10 KB)	0.22 GB/s	13.36 GB/s	29.36 GB/s	18.07 GB/s
Large (1 MB)	0.22 GB/s	13.40 GB/s	50.59 GB/s	48.43 GB/s

16-Bit UTF-16 Performance Profiles

Standard Execution (Single match near end):

Buffer Size	CRT Baseline	Scalar Hybrid	AVX2 Explicit	Smart Auto
Tiny (80 B)	3.16 GB/s	3.62 GB/s	3.43 GB/s	3.34 GB/s
Small (512 B)	1.67 GB/s	8.23 GB/s	1.38 GB/s	7.74 GB/s
Medium (20 KB)	1.47 GB/s	12.90 GB/s	45.57 GB/s	26.57 GB/s
Large (2 MB)	1.47 GB/s	12.41 GB/s	51.55 GB/s	51.60 GB/s

Realistic Log Corpus (Simulates real-world kernel log scanning to test skip table entropy and realistic jump distances):

Buffer Size	CRT Baseline	Scalar Hybrid	AVX2 Explicit	Smart Auto
Tiny (80 B)	4.12 GB/s	3.25 GB/s	3.08 GB/s	3.05 GB/s
Small (512 B)	1.72 GB/s	8.64 GB/s	1.68 GB/s	8.10 GB/s
Medium (20 KB)	1.49 GB/s	18.43 GB/s	48.17 GB/s	30.78 GB/s
Large (2 MB)	1.49 GB/s	14.18 GB/s	50.24 GB/s	55.13 GB/s

Mismatched Dense Text (Worst-case repetitive partial matches):

Buffer Size	CRT Baseline	Scalar Hybrid	AVX2 Explicit	Smart Auto
Tiny (80 B)	0.92 GB/s	3.49 GB/s	3.27 GB/s	3.36 GB/s
Small (512 B)	0.41 GB/s	7.39 GB/s	2.50 GB/s	7.00 GB/s
Medium (20 KB)	0.37 GB/s	13.46 GB/s	45.45 GB/s	44.26 GB/s
Large (2 MB)	0.37 GB/s	13.35 GB/s	50.16 GB/s	49.21 GB/s

Telemetry Takeaways

L2 Cache Saturation vs. Memory Bus Boundaries: On the i7-1165G7, 8-bit AVX-512 streaming on 1 MB realistic log corpuses peaked at 99.98 GB/s (Smart Auto) and 94.15 GB/s (AVX-512 Explicit). Since the 1 MB buffer fits entirely within the Tiger Lake 1.25 MB L2 cache, 64-byte ZMM streaming saturated the internal cache bus. When scanning 2 MB 16-bit buffers, throughput settled at ~49–56 GB/s across all SIMD engines, hitting the physical dual-channel DDR4-3200 saturation barrier.
Severe Pathological Degradation in CRT: Under mismatched dense text (aaaaaaaaab inside aaaaaaaa...), CRT collapses to 0.21–0.37 GB/s across both bare-metal and virtualized platforms due to $O(N \cdot M)$ mismatch backtracking. The hybrid last-character heuristic and SWAR fast-forwarding bypass this completely, delivering 48–85 GB/s on large buffers (up to 393x faster).
Hypervisor State-Saving Latency: On the i7-8086K VMware guest, entering vector execution on Small buffers (256 B / 512 B) is penalized severely by KeSaveExtendedProcessorState (AVX2 Explicit drops to 0.57–2.50 GB/s vs. 4.52–8.10 GB/s for Smart Auto). On Tiny buffers (40 B / 80 B) that fall below the 4x SIMD unroll window, the engine automatically bypasses XSTATE saving even when SIMD is requested explicitly.
AVX-512 Instruction Efficiency: On cache-bound medium buffers (10 KB / 20 KB), AVX-512 Explicit delivers 9–23% higher throughput than AVX2 Explicit (65.61–73.27 GB/s vs. 55.63–59.33 GB/s on 16-bit) by emitting direct __mmask32 / __mmask64 bitmasks via _mm512_cmpeq_epi16_mask and _mm512_cmpeq_epi8_mask, avoiding the movemask/bit-packing overhead of AVX2.

6. Repository Structure

├── Assets/                  # Benchmark visualization charts (PNG)
├── Experimental/
│   ├── KmBndmSearch8.h      # 8-bit BNDM bit-parallel class declaration
│   ├── KmBndmSearch8.cpp    # 8-bit BNDM implementation
│   ├── KmBndmSearch16.h     # 16-bit BNDM bitmask bloom merger declaration
│   └── KmBndmSearch16.cpp   # 16-bit BNDM implementation
├── Shared/
│   └── KmStrSearchShared.h  # Unified Kernel/User multi-threaded test harness
├── StrSearch/
│   ├── KmStrSearch8.h       # 8-bit substring search class declaration
│   ├── KmStrSearch8.cpp     # AVX-512, AVX2, NEON, SWAR, and BMH implementation (8-bit)
│   ├── KmStrSearch16.h      # UTF-16 Hybrid BMH class declaration
│   └── KmStrSearch16.cpp    # Golden Ratio Hash, AVX-512, AVX2, NEON, SWAR (16-bit)
├── TestKm/
│   └── KmStrSearchDrv.cpp   # Kernel driver for test execution
└── TestUm/
    └── KmStrSearchUm.cpp    # User-mode test suite wrapper

7. API Reference & Usage

The classes CKmStrSearch8 (for char / UTF-8) and CKmStrSearch16 (for wchar_t / UTF-16) provide matching APIs.

#include <ntddk.h>
#include "KmStrSearch16.h"

VOID SearchExample(const wchar_t* pKernelLogBuffer, size_t cchLogLength)
{
    PAGED_CODE(); // Initialize() must run at PASSIVE_LEVEL or APC_LEVEL

    CKmStrSearch16 searchEngine;
    const wchar_t needle[] = L"BUGCHECK_CODE_CRITICAL";

    // 1. Initialize table (PASSIVE_LEVEL or APC_LEVEL; allocates from Non-Paged Pool)
    if (!searchEngine.Initialize(needle, wcslen(needle)))
    {
        return; // Allocation failure or invalid length
    }

    // 2. Execute Search using 'Auto' routing (Safe up to DISPATCH_LEVEL if buffers are non-paged)
    int matchIndex = searchEngine.Find(pKernelLogBuffer, cchLogLength);

    if (matchIndex != -1)
    {
        // Pattern matched at pKernelLogBuffer[matchIndex]
    }
}

Explicit Engine Selection

Callers can override the auto-bypass heuristic by explicitly specifying an execution engine:

// Force scalar GPR execution (guarantees zero XSTATE context saving)
int idxScalar = searchEngine.Find(pBuffer, cchLen, CKmStrSearch16::SearchEngine::Scalar);

// Explicitly execute AVX2 or AVX-512 (automatically wraps KeSaveExtendedProcessorState)
int idxAVX2   = searchEngine.Find(pBuffer, cchLen, CKmStrSearch16::SearchEngine::AVX2);
int idxAVX512 = searchEngine.Find(pBuffer, cchLen, CKmStrSearch16::SearchEngine::AVX512);

8. Building & Testing

Prerequisites

Visual Studio 2026
C++20 Toolset Support: Ensure /std:c++20 is enabled in your compilation flags.
Windows Driver Kit (WDK): The latest MS WDK is required to compile the kernel driver targets.

Compilation

Native MSVC 2026 solution and project files are provided in the repository to build both the test kernel driver and the user mode test suite code.

TestKm (Kernel Driver): Compiles the KmStrSearchDrv.sys test kernel driver containing the complete performance and correctness test suite. This represents the primary evaluation environment.
TestUm (User Mode): Compiles the user mode test suite code wrapping the shared test logic, designed exclusively for rapid functional validation, unit testing, and debugging.

Execution & Telemetry Output

Live Tracing: The kernel driver outputs benchmark results and correctness validations in real-time using DbgPrintEx traces. These logs are broadcast under the DPFLTR_IHVDRIVER_ID component filter using DPFLTR_INFO_LEVEL and DPFLTR_ERROR_LEVEL levels, making them easily viewable via WinDbg or Sysinternals DebugView.
Persistent Logging: At the conclusion of the test suite, the driver flushes all accumulated output strings and saves the complete telemetry report to a text file located at \SystemRoot\Temp\KmStrSearchPerf.txt.

⚠️ Performance Caveat: While the user-mode (TestUm) test suite code is provided for convenience and logic verification, its performance metrics cannot be trusted to reflect true system capabilities. The search engines, specifically the dynamic SIMD/SWAR routing logic and state-saving bypasses, are designed exclusively for the Windows kernel architecture. User-mode environments handle thread context switching and vector register preservation entirely differently. Always refer to the KmStrSearchDrv.sys kernel driver telemetry for accurate Ring 0 performance evaluations.

9. License

This project is licensed under the MIT License. See the LICENSE file for details.

Navigation Menu

Repository navigation

About

Repository files navigation

Kernel Substring Search: An Exploration of Ring 0 Vectorization

Table of Contents

1. The Kernel Optimization Landscape & Ring 0 Trade-offs

The Ring 0 Extended Processor State Overhead

Smart Auto Routing & Bypass

IRQL Constraints & Memory Allocation

2. Algorithm Architecture: Hybrid BMH

8-Bit Architecture (`CKmStrSearch8`)

16-Bit Architecture (`CKmStrSearch16`)

3. Execution Engines: SIMD vs. SWAR

AVX-512BW (ZMM Registers & Native Opmasks)

AVX2 & ARM64 NEON Engines

SWAR Fallback (SIMD Within A Register)

4. The Experimental Branch: Why BNDM Falls Behind

5. Benchmark Analysis

Environment 1: Intel Core i7-1165G7 (Bare-Metal Windows 11)

8-Bit UTF-8 Performance Profiles

16-Bit UTF-16 Performance Profiles

Environment 2: Intel Core i7-8086K (VMware Guest Windows 11)

8-Bit UTF-8 Performance Profiles

16-Bit UTF-16 Performance Profiles

Telemetry Takeaways

6. Repository Structure

7. API Reference & Usage

Explicit Engine Selection

8. Building & Testing

Prerequisites

Compilation

Execution & Telemetry Output

9. License

About

Releases

Packages

Contributors

Languages

Name		Name	Last commit message	Last commit date
Assets		Assets
Experimental		Experimental
Shared		Shared
StrSearch		StrSearch
TestKm		TestKm
TestUm		TestUm
.gitignore		.gitignore
LICENSE		LICENSE
Readme.md		Readme.md

Latest commit

History

Folders and files

Repository files navigation

Kernel Substring Search: An Exploration of Ring 0 Vectorization

Table of Contents

1. The Kernel Optimization Landscape & Ring 0 Trade-offs

The Ring 0 Extended Processor State Overhead

Smart Auto Routing & Bypass

IRQL Constraints & Memory Allocation

2. Algorithm Architecture: Hybrid BMH

8-Bit Architecture (CKmStrSearch8)

16-Bit Architecture (CKmStrSearch16)

3. Execution Engines: SIMD vs. SWAR

AVX-512BW (ZMM Registers & Native Opmasks)

AVX2 & ARM64 NEON Engines

SWAR Fallback (SIMD Within A Register)

4. The Experimental Branch: Why BNDM Falls Behind

5. Benchmark Analysis

Environment 1: Intel Core i7-1165G7 (Bare-Metal Windows 11)

8-Bit UTF-8 Performance Profiles

16-Bit UTF-16 Performance Profiles

Environment 2: Intel Core i7-8086K (VMware Guest Windows 11)

8-Bit UTF-8 Performance Profiles

16-Bit UTF-16 Performance Profiles

Telemetry Takeaways

6. Repository Structure

7. API Reference & Usage

Explicit Engine Selection

8. Building & Testing

Prerequisites

Compilation

Execution & Telemetry Output

9. License

About

Topics

Resources

Stars

Watchers

Forks

Releases

Packages

Contributors

Languages

8-Bit Architecture (`CKmStrSearch8`)

16-Bit Architecture (`CKmStrSearch16`)