semx_bitops 0.1.8

//! 基于 qemu 的 bitops 实现
#![no_std]
#![feature(likely_unlikely)]
#![allow(clippy::cast_possible_wrap)]

extern crate alloc;

use core::{hint::unlikely, mem::size_of};

use crate::bitmap::bitmap_first_word_mask;

pub mod bitmap;

/// BYTE bit 位数
pub const BITS_PER_BYTE: usize = 8;
/// LONG bit 位数
pub const BITS_PER_LONG: usize = size_of::<usize>() * BITS_PER_BYTE;

/// `BIT(nr)`
pub const fn bit(nr: usize) -> usize {
    1 << nr
}

/// `BIT_ULL(nr)`
pub const fn bit_ull(nr: u64) -> u64 {
    1 << nr
}

/// `BIT_MASK(nr)`
pub const fn bit_mask(nr: usize) -> usize {
    1 << (nr % BITS_PER_LONG)
}

/// `BIT_WORD(nr)`
pub const fn bit_word(nr: usize) -> usize {
    nr / BITS_PER_LONG
}

#[allow(clippy::manual_div_ceil)]
const fn div_round_up(n: usize, d: usize) -> usize {
    (n + d - 1) / d
}

/// `BIT_TO_LONGS(nr)`
pub const fn bits_to_longs(nr: usize) -> usize {
    div_round_up(nr, BITS_PER_BYTE * size_of::<usize>())
}

/// `MAKE_64BIT_MASK(shift, length)`
pub const fn make_64bit_mask(shift: usize, length: usize) -> u64 {
    (u64::MAX >> (64 - length)) << shift
}

/// 设置 bit
#[inline]
pub fn set_bit(nr: usize, addr: &mut [usize]) {
    let mask = bit_mask(nr);
    addr[bit_word(nr)] |= mask;
}

/// 清除 bit
#[inline]
pub fn clear_bit(nr: usize, addr: &mut [usize]) {
    let mask = bit_mask(nr);
    addr[bit_word(nr)] &= !mask;
}

/// 改变 bit
#[inline]
pub fn change_bit(nr: usize, addr: &mut [usize]) {
    let mask = bit_mask(nr);
    addr[bit_word(nr)] ^= mask;
}

/// 设置一个 bit 并且测试原来的值
#[inline]
pub fn test_and_set_bit(nr: usize, addr: &mut [usize]) -> bool {
    let mask = bit_mask(nr);
    let idx = bit_word(nr);
    let old = addr[idx];
    addr[idx] = old | mask;
    old & mask != 0
}

/// 清除一个 bit 并且测试原来的值
#[inline]
pub fn test_and_clear_bit(nr: usize, addr: &mut [usize]) -> bool {
    let mask = bit_mask(nr);
    let idx = bit_word(nr);
    let old = addr[idx];
    addr[idx] = old & !mask;
    old & mask != 0
}

/// 改变一个 bit 并且测试原来的值
#[inline]
pub fn test_and_change_bit(nr: usize, addr: &mut [usize]) -> bool {
    let mask = bit_mask(nr);
    let idx = bit_word(nr);
    let old = addr[idx];
    addr[idx] = old ^ mask;
    old & mask != 0
}

/// 测试一个 bit
pub fn test_bit(nr: usize, addr: &[usize]) -> bool {
    1 & addr[bit_word(nr)] >> (nr & (BITS_PER_LONG - 1)) != 0
}

/// 寻找最后一个被设置的 bit
///
/// 返回最后一个被设置 bit 的位置, 如果没有则返回 `size`
pub fn find_last_bit(addr: &[usize], size: usize) -> usize {
    let found = |words: usize, tmp: usize| {
        words * BITS_PER_LONG + BITS_PER_LONG - 1 - tmp.leading_zeros() as usize
    };

    let mut words = size / BITS_PER_LONG;
    if size & (BITS_PER_LONG - 1) != 0 {
        let tmp = addr[words] & (usize::MAX >> (BITS_PER_LONG - (size & (BITS_PER_LONG - 1))));
        if tmp != 0 {
            return found(words, tmp);
        }
    }

    while words != 0 {
        words -= 1;
        let tmp = addr[words];
        if tmp != 0 {
            return found(words, tmp);
        }
    }

    size
}

fn _find_next_bit(addr: &[usize], nbits: usize, mut start: usize, invert: usize) -> usize {
    if unlikely(start >= nbits) {
        return nbits;
    }

    let mut tmp = addr[start / BITS_PER_LONG];
    tmp ^= invert;

    tmp &= bitmap_first_word_mask(start);
    start &= !(BITS_PER_LONG - 1);

    while tmp == 0 {
        start += BITS_PER_LONG;
        if start >= nbits {
            return nbits;
        }

        tmp = addr[start / BITS_PER_LONG];
        tmp ^= invert;
    }

    (start + tmp.trailing_zeros() as usize).min(nbits)
}

/// 寻找下一个被设置的 bit
///
/// 如果没有找到则返回`size`
pub fn find_next_bit(addr: &[usize], size: usize, offset: usize) -> usize {
    _find_next_bit(addr, size, offset, 0)
}

/// 寻找下一个未设置的 bit
///
/// 如果没有未设置的 bit 位, 则返回 `size`
pub fn find_next_zero_bit(addr: &[usize], size: usize, offset: usize) -> usize {
    _find_next_bit(addr, size, offset, usize::MAX)
}

/// 寻找第一个被设置的 bit
///
/// 如果没有找到, 则返回`size`
#[inline]
pub fn find_first_bit(addr: &[usize], size: usize) -> usize {
    for (pos, mut result) in (0..size).take(BITS_PER_LONG).enumerate() {
        let tmp = addr[pos];
        if tmp != 0 {
            result += tmp.trailing_zeros() as usize;
            if result < size {
                return result;
            } else {
                return size;
            }
        }
    }
    size
}

/// 寻找第一个未被设置的 bit
#[inline]
pub fn find_first_zero_bit(addr: &[usize], size: usize) -> usize {
    find_next_zero_bit(addr, size, 0)
}

/// 提取 u8 字段
#[inline]
#[allow(clippy::cast_possible_truncation)]
pub fn extract8(value: u8, start: usize, length: usize) -> u8 {
    debug_assert!(length > 0 && length <= 8 - start);
    extract32(u32::from(value), start, length) as u8
}

/// 提取 u16 字段
#[inline]
#[allow(clippy::cast_possible_truncation)]
pub fn extract16(value: u16, start: usize, length: usize) -> u16 {
    debug_assert!(length > 0 && length <= 16 - start);
    extract32(u32::from(value), start, length) as u16
}

/// 提取 u32 字段
#[inline]
pub fn extract32(value: u32, start: usize, length: usize) -> u32 {
    debug_assert!(length > 0 && length <= 32 - start);
    (value >> start) & (u32::MAX >> (32 - length))
}

/// 提取 u64 字段
#[inline]
pub fn extract64(value: u64, start: usize, length: usize) -> u64 {
    debug_assert!(length > 0 && length <= 64 - start);
    (value >> start) & (u64::MAX >> (64 - length))
}

/// 向 u32 插入字段
#[inline]
pub fn deposit32(value: u32, start: usize, length: usize, fieldval: u32) -> u32 {
    debug_assert!(length > 0 && length <= 32 - start);
    let mask = (u32::MAX >> (32 - length)) << start;
    (value & !mask) | ((fieldval << start) & mask)
}

/// 向 u64 插入字段
#[inline]
pub fn deposit64(value: u64, start: usize, length: usize, fieldval: u64) -> u64 {
    debug_assert!(length > 0 && length <= 64 - start);
    let mask = (u64::MAX >> (64 - length)) << start;
    (value & !mask) | ((fieldval << start) & mask)
}

/// 清洗 u32 底部数据
///
/// Given an input `value`:
/// * xxxx xxxx xxxx xxxx ABCD EFGH IJKL MNOP
///
/// return the value where the bottom 16 bits are spread out into
/// the odd bits in the word, and the even bits are `zeroed`:
/// * 0A0B 0C0D 0E0F 0G0H 0I0J 0K0L 0M0N 0O0P
#[inline]
pub fn half_shuffle32(mut x: u32) -> u32 {
    x = ((x & 0xFF00) << 8) | (x & 0x00FF);
    x = ((x << 4) | x) & 0x0F0F0F0F;
    x = ((x << 2) | x) & 0x33333333;
    x = ((x << 1) | x) & 0x55555555;
    x
}

/// 清洗 u64 底部数据
///
/// Given an input `value`:
/// * `xxxx xxxx xxxx .... xxxx xxxx ABCD EFGH IJKL MNOP QRST UVWX YZab cdef`
///
/// return the value where the bottom 32 bits are spread out into
/// the odd bits in the word, and the even bits are `zeroed`:
/// * `0A0B 0C0D 0E0F 0G0H 0I0J 0K0L 0M0N .... 0U0V 0W0X 0Y0Z 0a0b 0c0d 0e0f`
#[inline]
pub fn half_shuffle64(mut x: u64) -> u64 {
    x = ((x & 0xFFFF0000) << 16) | (x & 0xFFFF);
    x = ((x << 8) | x) & 0x00FF00FF00FF00FF;
    x = ((x << 4) | x) & 0x0F0F0F0F0F0F0F0F;
    x = ((x << 2) | x) & 0x3333333333333333;
    x = ((x << 1) | x) & 0x5555555555555555;
    x
}

/// 还原 u32 底部数据
///
/// Given an input `value`:
/// * `xAxB xCxD xExF xGxH xIxJ xKxL xMxN xOxP`
///
/// return the value where all the odd bits are compressed down
/// into the low half of the word, and the high half is `zeroed`:
/// * `0000 0000 0000 0000 ABCD EFGH IJKL MNOP`
#[inline]
pub fn half_unshuffle32(mut x: u32) -> u32 {
    x &= 0x55555555;
    x = ((x >> 1) | x) & 0x33333333;
    x = ((x >> 2) | x) & 0x0F0F0F0F;
    x = ((x >> 4) | x) & 0x00FF00FF;
    x = ((x >> 8) | x) & 0x0000FFFF;
    x
}

/// 还原 u64 底部数据
///
/// Given an input `value`:
/// * `xAxB xCxD xExF xGxH xIxJ xKxL xMxN .... xUxV xWxX xYxZ xaxb xcxd xexf`
///
/// return the value where all the odd bits are compressed down
/// into the low half of the word, and the high half is `zeroed`:
/// * `0000 0000 0000 .... 0000 0000 ABCD EFGH IJKL MNOP QRST UVWX YZab cdef`
#[inline]
pub fn half_unshuffle64(mut x: u64) -> u64 {
    x &= 0x5555555555555555;
    x = ((x >> 1) | x) & 0x3333333333333333;
    x = ((x >> 2) | x) & 0x0F0F0F0F0F0F0F0F;
    x = ((x >> 4) | x) & 0x00FF00FF00FF00FF;
    x = ((x >> 8) | x) & 0x0000FFFF0000FFFF;
    x = ((x >> 16) | x) & 0x00000000FFFFFFFF;
    x
}