Compiler Explorer

Source code

fn u64_leading_zero_bytes(x: u64) -> u32 {
    x.leading_zeros() >> 3
}

fn u64_elementwise_bytes_lt(x: u64, y: u64) -> u64 {
    // ensure no elements in x are > 0x7f
    debug_assert!((x & 0x8080_8080_8080_8080) == 0);

let a = 0x7f7f_7f7f_7f7f_7f7f_u64;
    let b = 0x8080_8080_8080_8080_u64;
    let c = a - x;

// a = (0x7f << 56) + (0x7f << 48) + .. + (0x7f << 0)
    // x = (b7 << 56) + (b6 << 48) + .. + (b0 << 0)
    // c = ((0x7f - b7) << 56) + .. + ((0x7f - b0) << 0)
	//     iff. bi <= 0x7f forall i

// (((by & 0x7f) + (0x7f - bx) > 0x7f) || (by > 0x7f)
    // by' + 0x7f - bx > 0x7f
    // by' - bx > 0x7f
    // (by' > bx) || (by > 0x7f)

((y & a).wrapping_add(c) | y) & b
}

pub fn u64_leading_byte_idx_lt_ref(x: u64, y: u64) -> Option<u8> {
    IntoIterator::into_iter(x.to_le_bytes())
        .zip(IntoIterator::into_iter(y.to_le_bytes()))
        .rposition(|(bx, by)| bx < by)
        .map(|idx| idx as u8)
}

/// Given two u64's, `x` and `y`, where all bytes `bx` in `x` are in the range
/// `0 <= bx <= 0x7f (127)`, return the _byte index_ (i.e., idx = 0 = least
/// significant byte, idx = 7 = most-significant byte)  of the first leading byte
/// `by` in `y` where `by > bx`. (i.e., starting from the most-significant byte).
///
/// Returns `None` if there are no bytes in `y` greater than their corresponding
/// byte in `x`.
pub fn u64_leading_byte_idx_lt(x: u64, y: u64) -> Option<u8> {
    let mask_0x80 = u64_elementwise_bytes_lt(x, y);

if mask_0x80 != 0 {
        Some((7 - u64_leading_zero_bytes(mask_0x80)) as u8)
    } else {
        None
    }
}