use crate::mem;
const LO_USIZE: usize = usize::repeat_u8(0x01);
const HI_USIZE: usize = usize::repeat_u8(0x80);
const USIZE_BYTES: usize = mem::size_of::<usize>();
#[inline]
#[rustc_const_stable(feature = "const_memchr", since = "1.65.0")]
const fn contains_zero_byte(x: usize) -> bool {
x.wrapping_sub(LO_USIZE) & !x & HI_USIZE != 0
}
#[inline]
#[cfg(target_pointer_width = "16")]
#[rustc_const_stable(feature = "const_memchr", since = "1.65.0")]
const fn repeat_byte(b: u8) -> usize {
(b as usize) << 8 | b as usize
}
#[inline]
#[cfg(not(target_pointer_width = "16"))]
#[rustc_const_stable(feature = "const_memchr", since = "1.65.0")]
const fn repeat_byte(b: u8) -> usize {
(b as usize) * (usize::MAX / 255)
}
#[inline]
#[must_use]
#[rustc_const_stable(feature = "const_memchr", since = "1.65.0")]
pub const fn memchr(x: u8, text: &[u8]) -> Option<usize> {
if text.len() < 2 * USIZE_BYTES {
return memchr_naive(x, text);
}
memchr_aligned(x, text)
}
#[inline]
#[rustc_const_stable(feature = "const_memchr", since = "1.65.0")]
const fn memchr_naive(x: u8, text: &[u8]) -> Option<usize> {
let mut i = 0;
while i < text.len() {
if text[i] == x {
return Some(i);
}
i += 1;
}
None
}
#[rustc_allow_const_fn_unstable(const_cmp)]
#[rustc_allow_const_fn_unstable(const_slice_index)]
#[rustc_allow_const_fn_unstable(const_align_offset)]
#[rustc_const_stable(feature = "const_memchr", since = "1.65.0")]
const fn memchr_aligned(x: u8, text: &[u8]) -> Option<usize> {
let len = text.len();
let ptr = text.as_ptr();
let mut offset = ptr.align_offset(USIZE_BYTES);
if offset > 0 {
offset = if offset < len { offset } else { len };
let slice = unsafe { super::from_raw_parts(text.as_ptr(), offset) };
if let Some(index) = memchr_naive(x, slice) {
return Some(index);
}
}
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);
let zu = contains_zero_byte(u ^ repeated_x);
let zv = contains_zero_byte(v ^ repeated_x);
if zu || zv {
break;
}
}
offset += USIZE_BYTES * 2;
}
let slice = unsafe { super::from_raw_parts(text.as_ptr().add(offset), text.len() - offset) };
if let Some(i) = memchr_naive(x, slice) { Some(offset + i) } else { None }
}
#[must_use]
pub fn memrchr(x: u8, text: &[u8]) -> Option<usize> {
let len = text.len();
let ptr = text.as_ptr();
type Chunk = usize;
let (min_aligned_offset, max_aligned_offset) = {
let (prefix, _, suffix) = unsafe { text.align_to::<(Chunk, Chunk)>() };
(prefix.len(), len - suffix.len())
};
let mut offset = max_aligned_offset;
if let Some(index) = text[offset..].iter().rposition(|elt| *elt == x) {
return Some(offset + index);
}
let repeated_x = repeat_byte(x);
let chunk_bytes = mem::size_of::<Chunk>();
while offset > min_aligned_offset {
unsafe {
let u = *(ptr.add(offset - 2 * chunk_bytes) as *const Chunk);
let v = *(ptr.add(offset - chunk_bytes) as *const Chunk);
let zu = contains_zero_byte(u ^ repeated_x);
let zv = contains_zero_byte(v ^ repeated_x);
if zu || zv {
break;
}
}
offset -= 2 * chunk_bytes;
}
text[..offset].iter().rposition(|elt| *elt == x)
}