soyokaze 0.2.0

//! Word-at-a-time scanning over the octets of a message.
//!
//! Parsing HTTP/1.x means walking bytes looking for delimiters and rejecting
//! forbidden octets, which is most of the work in a small request. The
//! routines here do that eight octets at a time using the usual SWAR
//! bit-twiddling, and fall back to a byte loop for the tail.
//!
//! Everything here works on raw octets and makes no assumption about encoding.

/// How many octets one machine word holds.
pub const LANES: usize = size_of::<u64>();
/// The low bit of every lane.
pub const LOW: u64 = 0x0101_0101_0101_0101;
/// The high bit of every lane.
pub const HIGH: u64 = 0x8080_8080_8080_8080;

/// Marks the high bit of each lane of `word` that holds zero.
///
/// Non-zero exactly when some lane is zero, which is how a search for one
/// octet is done: exclusive-or the word against a broadcast of the needle and
/// ask whether any lane went to zero.
#[inline]
pub fn holds_zero(word: u64) -> u64 {
    word.wrapping_sub(LOW) & !word & HIGH
}

/// Reads the eight octets at `offset` as a little-endian word.
///
/// # Panics
///
/// Panics when fewer than [`LANES`] octets remain at `offset`.
#[inline]
pub fn word_at(haystack: &[u8], offset: usize) -> u64 {
    let mut octets = [0u8; LANES];
    octets.copy_from_slice(&haystack[offset..offset + LANES]);
    u64::from_le_bytes(octets)
}

/// The offset of the first `needle` in `haystack`, if it is there.
#[inline]
pub fn find(haystack: &[u8], needle: u8) -> Option<usize> {
    let broadcast = LOW.wrapping_mul(needle as u64);
    let mut offset = 0;

    while offset + LANES <= haystack.len() {
        let marked = holds_zero(word_at(haystack, offset) ^ broadcast);

        if marked != 0 {
            return Some(offset + (marked.trailing_zeros() / 8) as usize);
        }

        offset += LANES;
    }

    haystack[offset..].iter().position(|octet| *octet == needle).map(|index| offset + index)
}

/// Copies `source` to the front of `destination`.
///
/// Short copies — which is most of them, since field names and values usually
/// are — are done as a pair of overlapping fixed-width copies rather than a
/// length-driven loop.
///
/// # Panics
///
/// Debug builds assert that `destination` is long enough; release builds
/// panic on the slice bounds instead.
#[inline]
pub fn copy(destination: &mut [u8], source: &[u8]) {
    let len = source.len();
    debug_assert!(destination.len() >= len, "the destination is too short for the source");

    if len > 32 {
        destination[..len].copy_from_slice(source);
        return;
    }

    if len >= 16 {
        destination[..16].copy_from_slice(&source[..16]);
        destination[len - 16..len].copy_from_slice(&source[len - 16..]);
    } else if len >= 8 {
        destination[..8].copy_from_slice(&source[..8]);
        destination[len - 8..len].copy_from_slice(&source[len - 8..]);
    } else if len >= 4 {
        destination[..4].copy_from_slice(&source[..4]);
        destination[len - 4..len].copy_from_slice(&source[len - 4..]);
    } else if len >= 2 {
        destination[..2].copy_from_slice(&source[..2]);
        destination[len - 2..len].copy_from_slice(&source[len - 2..]);
    } else if len == 1 {
        destination[0] = source[0];
    }
}

/// [`classify_field_value`]: the value carries a control octet, and so is not
/// a valid field value.
pub const VALUE_CONTROL: u8 = 1 << 0;
/// [`classify_field_value`]: the value carries an octet at or above `0x80`.
///
/// Such a value is legal but not ASCII, so it has to go through UTF-8
/// validation rather than being taken as ASCII outright.
pub const VALUE_OBS_TEXT: u8 = 1 << 1;

/// Marks the high bit of each lane of `word` that holds less than `bound`.
///
/// # Panics
///
/// Debug builds assert `bound <= 0x80`; above that the subtraction borrows
/// across lane boundaries and the answer is meaningless.
#[inline]
pub fn holds_less(word: u64, bound: u64) -> u64 {
    debug_assert!(bound <= 0x80, "a bound above 0x80 can borrow out of its byte");

    let lowered = (word | HIGH).wrapping_sub(LOW.wrapping_mul(bound));
    !lowered & !word & HIGH
}

/// Marks the high bit of each lane of `word` that holds zero.
///
/// Unlike [`holds_zero`] this is exact rather than approximate, so it can be
/// used where the marks themselves are combined with other masks.
#[inline]
pub fn marks_zero(word: u64) -> u64 {
    !((word & !HIGH).wrapping_add(!HIGH) | word) & HIGH
}

/// Classifies a field value in one pass.
///
/// Returns the or of [`VALUE_CONTROL`] and [`VALUE_OBS_TEXT`]. A horizontal
/// tab is permitted and does not count as a control octet; every other octet
/// below `0x20`, and `0x7f`, does.
#[inline]
pub fn classify_field_value(text: &[u8]) -> u8 {
    let mut control = 0u64;
    let mut obs_text = 0u64;
    let mut offset = 0;

    while offset + LANES <= text.len() {
        let word = word_at(text, offset);

        let tab = marks_zero(word ^ LOW.wrapping_mul(b'\t' as u64));
        let del = marks_zero(word ^ LOW.wrapping_mul(0x7f));

        control |= (holds_less(word, 0x20) & !tab) | del;
        obs_text |= word & HIGH;

        offset += LANES;
    }

    let (control, obs_text) = text[offset..].iter().fold((control != 0, obs_text != 0), |(control, obs_text), octet| {
        (
            control || (*octet < 0x20 && *octet != b'\t') || *octet == 0x7f,
            obs_text || *octet >= 0x80,
        )
    });

    (control as u8) | (obs_text as u8) << 1
}

/// Whether `text` may be sent as a field value.
///
/// Octets at or above `0x80` are allowed; control octets other than tab are not.
#[inline]
pub fn is_field_value(text: &[u8]) -> bool {
    classify_field_value(text) & VALUE_CONTROL == 0
}