Compiler Explorer

Source code

#![no_std]

mod f {

use core::cmp;
    use core::mem;

const LO_U64: u64 = 0x0101010101010101;
    const HI_U64: u64 = 0x8080808080808080;

// Use truncation.
    const LO_USIZE: usize = LO_U64 as usize;
    const HI_USIZE: usize = HI_U64 as usize;

/// Returns `true` if `x` contains any zero byte.
    ///
    /// From *Matters Computational*, J. Arndt:
    ///
    /// "The idea is to subtract one from each of the bytes and then look for
    /// bytes where the borrow propagated all the way to the most significant
    /// bit."
    #[inline]
    fn contains_zero_byte(x: usize) -> bool {
        x.wrapping_sub(LO_USIZE) & !x & HI_USIZE != 0
    }

#[cfg(target_pointer_width = "16")]
    #[inline]
    fn repeat_byte(b: u8) -> usize {
        (b as usize) << 8 | b as usize
    }

#[cfg(not(target_pointer_width = "16"))]
    #[inline]
    fn repeat_byte(b: u8) -> usize {
        (b as usize) * (usize::MAX / 255)
    }

fn memchr(x: u8, text: &[u8]) -> Option<usize> {
        // Scan for a single byte value by reading two `usize` words at a time.
        //
        // Split `text` in three parts
        // - unaligned initial part, before the first word aligned address in text
        // - body, scan by 2 words at a time
        // - the last remaining part, < 2 word size
        let len = text.len();
        let usize_bytes = mem::size_of::<usize>();

// Fast path for small slices
        if len < 2 * usize_bytes {
            return text.iter().position(|elt| *elt == x);
        }

// search up to an aligned boundary
        let ptr = text.as_ptr();
        let mut offset = ptr.align_offset(usize_bytes);

if offset > 0 {
            offset = cmp::min(offset, len);
            if let Some(index) = text[..offset].iter().position(|elt| *elt == x) {
                return Some(index);
            }
        }

// search the body of the text
        let repeated_x = repeat_byte(x);
        while offset <= len - 2 * usize_bytes {
            unsafe {
                let u = *(ptr.add(offset) as *const usize);
                let v = *(ptr.add(offset + usize_bytes) as *const usize);

// break if there is a matching byte
                let zu = contains_zero_byte(u ^ repeated_x);
                let zv = contains_zero_byte(v ^ repeated_x);
                if zu || zv {
                    break;
                }
            }
            offset += usize_bytes * 2;
        }

// Find the byte after the point the body loop stopped.
        text[offset..].iter().position(|elt| *elt == x).map(|i| offset + i)
    }

trait Contains {    
        fn slice_contains2(&self, x: &[u8]) -> bool;
    }

pub(crate) trait Sl {
        fn contains2(&self, x: &u8) -> bool;
    }

impl Contains for u8 {
        fn slice_contains2(&self, x: &[u8]) -> bool {
            memchr(*self, x).is_some()
        }
    }

impl Sl for [u8] {
        fn contains2(&self, x: &u8) -> bool
        {
            x.slice_contains2(self)
        }
    }
}

use f::Sl;

pub fn foo16(x: u8, data: &[u8; 4]) -> bool {
    data.contains2(&x)
}