frizbee 0.11.0

//! Rates the likelihood of a byte appearing in a haystack
//! Source: <https://github.com/BurntSushi/memchr/blob/master/src/arch/all/packedpair/default_rank.rs>
//! MIT License
//! Copyright (c) 2015 Andrew Gallant

pub(super) const RANK: [u8; 256] = [
    55,  // '\x00'
    52,  // '\x01'
    51,  // '\x02'
    50,  // '\x03'
    49,  // '\x04'
    48,  // '\x05'
    47,  // '\x06'
    46,  // '\x07'
    45,  // '\x08'
    103, // '\t'
    242, // '\n'
    66,  // '\x0b'
    67,  // '\x0c'
    229, // '\r'
    44,  // '\x0e'
    43,  // '\x0f'
    42,  // '\x10'
    41,  // '\x11'
    40,  // '\x12'
    39,  // '\x13'
    38,  // '\x14'
    37,  // '\x15'
    36,  // '\x16'
    35,  // '\x17'
    34,  // '\x18'
    33,  // '\x19'
    56,  // '\x1a'
    32,  // '\x1b'
    31,  // '\x1c'
    30,  // '\x1d'
    29,  // '\x1e'
    28,  // '\x1f'
    255, // ' '
    148, // '!'
    164, // '"'
    149, // '#'
    136, // '$'
    160, // '%'
    155, // '&'
    173, // "'"
    221, // '('
    222, // ')'
    134, // '*'
    122, // '+'
    232, // ','
    202, // '-'
    215, // '.'
    224, // '/'
    208, // '0'
    220, // '1'
    204, // '2'
    187, // '3'
    183, // '4'
    179, // '5'
    177, // '6'
    168, // '7'
    178, // '8'
    200, // '9'
    226, // ':'
    195, // ';'
    154, // '<'
    184, // '='
    174, // '>'
    126, // '?'
    120, // '@'
    191, // 'A'
    157, // 'B'
    194, // 'C'
    170, // 'D'
    189, // 'E'
    162, // 'F'
    161, // 'G'
    150, // 'H'
    193, // 'I'
    142, // 'J'
    137, // 'K'
    171, // 'L'
    176, // 'M'
    185, // 'N'
    167, // 'O'
    186, // 'P'
    112, // 'Q'
    175, // 'R'
    192, // 'S'
    188, // 'T'
    156, // 'U'
    140, // 'V'
    143, // 'W'
    123, // 'X'
    133, // 'Y'
    128, // 'Z'
    147, // '['
    138, // '\\'
    146, // ']'
    114, // '^'
    223, // '_'
    151, // '`'
    249, // 'a'
    216, // 'b'
    238, // 'c'
    236, // 'd'
    253, // 'e'
    227, // 'f'
    218, // 'g'
    230, // 'h'
    247, // 'i'
    135, // 'j'
    180, // 'k'
    241, // 'l'
    233, // 'm'
    246, // 'n'
    244, // 'o'
    231, // 'p'
    139, // 'q'
    245, // 'r'
    243, // 's'
    251, // 't'
    235, // 'u'
    201, // 'v'
    196, // 'w'
    240, // 'x'
    214, // 'y'
    152, // 'z'
    182, // '{'
    205, // '|'
    181, // '}'
    127, // '~'
    27,  // '\x7f'
    212, // '\x80'
    211, // '\x81'
    210, // '\x82'
    213, // '\x83'
    228, // '\x84'
    197, // '\x85'
    169, // '\x86'
    159, // '\x87'
    131, // '\x88'
    172, // '\x89'
    105, // '\x8a'
    80,  // '\x8b'
    98,  // '\x8c'
    96,  // '\x8d'
    97,  // '\x8e'
    81,  // '\x8f'
    207, // '\x90'
    145, // '\x91'
    116, // '\x92'
    115, // '\x93'
    144, // '\x94'
    130, // '\x95'
    153, // '\x96'
    121, // '\x97'
    107, // '\x98'
    132, // '\x99'
    109, // '\x9a'
    110, // '\x9b'
    124, // '\x9c'
    111, // '\x9d'
    82,  // '\x9e'
    108, // '\x9f'
    118, // '\xa0'
    141, // '¡'
    113, // '¢'
    129, // '£'
    119, // '¤'
    125, // '¥'
    165, // '¦'
    117, // '§'
    92,  // '¨'
    106, // '©'
    83,  // 'ª'
    72,  // '«'
    99,  // '¬'
    93,  // '\xad'
    65,  // '®'
    79,  // '¯'
    166, // '°'
    237, // '±'
    163, // '²'
    199, // '³'
    190, // '´'
    225, // 'µ'
    209, // '¶'
    203, // '·'
    198, // '¸'
    217, // '¹'
    219, // 'º'
    206, // '»'
    234, // '¼'
    248, // '½'
    158, // '¾'
    239, // '¿'
    255, // 'À'
    255, // 'Á'
    255, // 'Â'
    255, // 'Ã'
    255, // 'Ä'
    255, // 'Å'
    255, // 'Æ'
    255, // 'Ç'
    255, // 'È'
    255, // 'É'
    255, // 'Ê'
    255, // 'Ë'
    255, // 'Ì'
    255, // 'Í'
    255, // 'Î'
    255, // 'Ï'
    255, // 'Ð'
    255, // 'Ñ'
    255, // 'Ò'
    255, // 'Ó'
    255, // 'Ô'
    255, // 'Õ'
    255, // 'Ö'
    255, // '×'
    255, // 'Ø'
    255, // 'Ù'
    255, // 'Ú'
    255, // 'Û'
    255, // 'Ü'
    255, // 'Ý'
    255, // 'Þ'
    255, // 'ß'
    255, // 'à'
    255, // 'á'
    255, // 'â'
    255, // 'ã'
    255, // 'ä'
    255, // 'å'
    255, // 'æ'
    255, // 'ç'
    255, // 'è'
    255, // 'é'
    255, // 'ê'
    255, // 'ë'
    255, // 'ì'
    255, // 'í'
    255, // 'î'
    255, // 'ï'
    255, // 'ð'
    255, // 'ñ'
    255, // 'ò'
    255, // 'ó'
    255, // 'ô'
    255, // 'õ'
    255, // 'ö'
    255, // '÷'
    255, // 'ø'
    255, // 'ù'
    255, // 'ú'
    255, // 'û'
    255, // 'ü'
    255, // 'ý'
    255, // 'þ'
    255, // 'ÿ'
];

/// Picks the byte offsets of the two rarest bytes in `needle` (lowest [`RANK`], i.e. least likely to
/// appear in a haystack), returning them ordered as `(lower, higher)`. The two offsets always differ
/// and, when possible, point at two distinct byte values, maximizing the selectivity of the
/// two-byte substring prefilter. Mirrors the heuristic in memchr's `packedpair`.
///
/// Requires `needle.len() >= 2`.
pub(super) fn rare_byte_offsets(needle: &[u8]) -> (usize, usize) {
    debug_assert!(
        needle.len() >= 2,
        "rare_byte_offsets requires at least two bytes"
    );

    let rank = |byte: u8| RANK[byte as usize];

    // Seed the search with the first two bytes, keeping the rarer of the two as `rare1`.
    let (mut rare1, mut offset1) = (needle[0], 0usize);
    let (mut rare2, mut offset2) = (needle[1], 1usize);
    if rank(rare2) < rank(rare1) {
        std::mem::swap(&mut rare1, &mut rare2);
        std::mem::swap(&mut offset1, &mut offset2);
    }

    for (offset, &byte) in needle.iter().enumerate().skip(2) {
        if rank(byte) < rank(rare1) {
            // A new rarest byte; the previous rarest becomes the runner-up.
            rare2 = rare1;
            offset2 = offset1;
            rare1 = byte;
            offset1 = offset;
        } else if byte != rare1 && rank(byte) < rank(rare2) {
            rare2 = byte;
            offset2 = offset;
        }
    }

    if offset1 <= offset2 {
        (offset1, offset2)
    } else {
        (offset2, offset1)
    }
}

#[cfg(test)]
mod tests {
    use super::{RANK, rare_byte_offsets};

    #[test]
    fn returns_two_distinct_ordered_offsets() {
        let (a, b) = rare_byte_offsets(b"abcd");
        assert!(
            a < b && b < 4,
            "expected ordered distinct offsets, got ({a}, {b})"
        );
    }

    #[test]
    fn prefers_rarer_bytes_over_position() {
        // 'z' is far rarer than 'a', so it must be chosen even though it is neither first nor last.
        assert!(RANK[b'z' as usize] < RANK[b'a' as usize]);
        let (a, b) = rare_byte_offsets(b"aazaa");
        assert!(
            a == 2 || b == 2,
            "expected the 'z' at offset 2 to be a seed, got ({a}, {b})"
        );
    }

    #[test]
    fn all_identical_bytes_fall_back_to_adjacent_offsets() {
        assert_eq!(rare_byte_offsets(b"aaaa"), (0, 1));
    }
}