semx_bitops 0.1.61

//! 位操作原语与位域操作
#![no_std]
#![feature(likely_unlikely)]

extern crate alloc;

pub mod bitmap;

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

use crate::bitmap::bitmap_first_word_mask;

/// 每字节位数
pub const BITS_PER_BYTE: usize = 8;
/// 每 `usize` 位数
pub const BITS_PER_LONG: usize = size_of::<usize>() * BITS_PER_BYTE;

/// 返回仅第 `nr` 位为一的 `usize` 掩码
pub const fn bit(nr: usize) -> usize {
    1 << nr
}

/// 返回仅第 `nr` 位为一的 `u64` 掩码
pub const fn bit_ull(nr: u64) -> u64 {
    1 << nr
}

/// 返回第 `nr` 位在其所在 word 内的掩码
pub const fn bit_mask(nr: usize) -> usize {
    1 << (nr % BITS_PER_LONG)
}

/// 返回第 `nr` 位所在的 word 索引
pub const fn bit_word(nr: usize) -> usize {
    nr / BITS_PER_LONG
}

/// 计算存储 `nr` 位所需的 `usize` word 数
pub const fn bits_to_longs(nr: usize) -> usize {
    nr.div_ceil(BITS_PER_BYTE * size_of::<usize>())
}

/// 生成从 `shift` 起长度为 `length` 的 64 位掩码
pub const fn make_64bit_mask(shift: usize, length: usize) -> u64 {
    (u64::MAX >> (64 - length)) << shift
}

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

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

/// 翻转第 `nr` 位
#[inline]
pub fn change_bit(nr: usize, addr: &mut [usize]) {
    let mask = bit_mask(nr);
    addr[bit_word(nr)] ^= mask;
}

/// 置位第 `nr` 位, 返回该位的旧值
#[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
}

/// 清除第 `nr` 位, 返回该位的旧值
#[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
}

/// 翻转第 `nr` 位, 返回该位的旧值
#[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
}

/// 测试第 `nr` 位是否为一
#[inline]
pub fn test_bit(nr: usize, addr: &[usize]) -> bool {
    addr[bit_word(nr)] & bit_mask(nr) != 0
}

/// 查找最后一个为一的位, 找不到时返回 `size`
#[inline]
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
}

#[inline]
fn find_next_bit_inner(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)
}

/// 从 `offset` 起查找下一个为一的位, 找不到时返回 `size`
#[inline]
pub fn find_next_bit(addr: &[usize], size: usize, offset: usize) -> usize {
    find_next_bit_inner(addr, size, offset, 0)
}

/// 从 `offset` 起查找下一个为零的位, 找不到时返回 `size`
#[inline]
pub fn find_next_zero_bit(addr: &[usize], size: usize, offset: usize) -> usize {
    find_next_bit_inner(addr, size, offset, usize::MAX)
}

/// 查找第一个为一的位, 找不到时返回 `size`
#[inline]
pub fn find_first_bit(addr: &[usize], size: usize) -> usize {
    for (pos, &word) in addr.iter().enumerate().take(bits_to_longs(size)) {
        if word != 0 {
            return (pos * BITS_PER_LONG + word.trailing_zeros() as usize).min(size);
        }
    }
    size
}

/// 查找第一个为零的位, 找不到时返回 `size`
#[inline]
pub fn find_first_zero_bit(addr: &[usize], size: usize) -> usize {
    find_next_zero_bit(addr, size, 0)
}

/// 从 `value` 中提取 `[start, start + length)` 位域（u8）
#[inline]
pub fn extract8(value: u8, start: usize, length: usize) -> u8 {
    debug_assert!(length > 0 && length <= 8 - start);
    (value >> start) & (u8::MAX >> (8 - length))
}

/// 从 `value` 中提取 `[start, start + length)` 位域（u16）
#[inline]
pub fn extract16(value: u16, start: usize, length: usize) -> u16 {
    debug_assert!(length > 0 && length <= 16 - start);
    (value >> start) & (u16::MAX >> (16 - length))
}

/// 从 `value` 中提取 `[start, start + length)` 位域（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))
}

/// 从 `value` 中提取 `[start, start + 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))
}

/// 将 `fieldval` 写入 `value` 的 `[start, start + 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)
}

/// 将 `fieldval` 写入 `value` 的 `[start, start + length)` 位域（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)
}

/// 将低 16 位交错展开到奇数位, 偶数位清零（u32）
///
/// `xxxx xxxx xxxx xxxx ABCD EFGH IJKL MNOP`
/// → `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
}

/// 将低 32 位交错展开到奇数位, 偶数位清零（u64）
///
/// `xxxx xxxx ... ABCD EFGH IJKL MNOP QRST UVWX YZab cdef`
/// → `0A0B 0C0D ... 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）
///
/// `xAxB xCxD xExF xGxH xIxJ xKxL xMxN xOxP`
/// → `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）
///
/// `xAxB xCxD ... xcxd xexf`
/// → `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
}