Compiler Explorer

Source code

#![feature(portable_simd)]

use std::simd::prelude::SimdPartialEq;
use std::simd::u8x16;
use std::convert::TryInto;

pub fn main() {
    let text = "1123213213213124234324231487qweqweasd9324879827349823467967234abc111237891284yudahsjkdjhk1hja11111";
    let substr = "abc11";

let contains = contains_substr(&text, &substr);

println!("contains?: {}", { contains });
}

// Asuming the string are ASCII 8-bit each
pub fn contains_substr(text: &str, substr: &str) -> bool {
    if substr.is_empty() || substr.len() > text.len() {
        return false;
    } else {
        let substr_bytes = substr.as_bytes();
        let substr_len = substr_bytes.len();

let first_char = substr_bytes[0];
        let last_char = substr_bytes[substr_len - 1];

// fingerprint from first and last character of the substring
        let first_fing = u8x16::splat(first_char.try_into().unwrap());
        let last_fing = u8x16::splat(last_char.try_into().unwrap());

// create 16-byte chunks for figerprint checks
        let text_bytes = pad_text(text.as_bytes(), substr_len);
        let total_chunks = text_bytes.len() / 16;
        for (i, chunk) in text_bytes.chunks(16).enumerate().take(total_chunks) {
            // blocks to compare fingerprints with
            let first_block = u8x16::from_slice(chunk);
            // second_block start from start + offset where offset = substr_len - 1
            let sb_start = (i * 16) + substr_len - 1;
            let second_block = u8x16::from_slice(&text_bytes[sb_start..sb_start + 16]);

let eq_a = first_block.simd_eq(first_fing);
            let eq_b = last_fing.simd_eq(second_block);

let mut mask = eq_a & eq_b;

// fingerprint match
            while mask.any() {
                // actual comparison, we can replace this with SIMD aswell but this should be
                // trivial enough for complier optimization
                let set_index = mask.first_set().unwrap();
                let f = set_index + (i * 16) + 1;
                if text_bytes[f..f + substr_len - 2] == substr_bytes[1..substr_len - 1] {
                    return true;
                }
                // f - 1 starting index of substring in the text
                mask.set(set_index, false);
            }
        }
        return false;
    }
}

// Padding could be done in a better way
fn pad_text(data: &[u8], substr_len: usize) -> Vec<u8> {
    // Determine the padding needed
    let padding_needed = (16 - (data.len() % 16)) % 16 + substr_len - 1;
    let mut padded_data = Vec::with_capacity(data.len() + padding_needed);
    padded_data.extend_from_slice(data);
    padded_data.resize(data.len() + padding_needed, b'\0');
    padded_data
}