semx_bitops 0.1.6

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

extern crate alloc;

use core::mem::size_of;

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
}

/// 寻找下一个被设置的 bit
///
/// 如果没有找到则返回`size`
pub fn find_next_bit(addr: &[usize], mut size: usize, mut offset: usize) -> usize {
    let found_middle = |result: usize, tmp: usize| result + tmp.trailing_zeros() as usize;
    let found_first = |result: usize, mut tmp: usize, size: usize| {
        tmp &= usize::MAX >> (BITS_PER_LONG - size);
        if tmp == 0 {
            return result + size;
        }
        found_middle(result, tmp)
    };

    if offset >= size {
        return size;
    }
    let mut result = offset & !(BITS_PER_LONG - 1);
    size -= result;
    offset %= BITS_PER_LONG;
    let mut pos = bit_word(offset);
    if offset != 0 {
        let mut tmp = addr[pos];
        pos += 1;
        tmp &= usize::MAX << offset;
        if size < BITS_PER_LONG {
            return found_first(result, tmp, size);
        }
        if tmp != 0 {
            return found_middle(result, tmp);
        }
        size -= BITS_PER_LONG;
        result += BITS_PER_LONG;
    }
    while size >= 4 * BITS_PER_LONG {
        let tmp = addr[pos];
        let d1 = addr[pos + 1];
        let d2 = addr[pos + 2];
        let d3 = addr[pos + 3];
        if tmp != 0 {
            return found_middle(result, tmp);
        }
        if (d1 | d2 | d3) != 0 {
            break;
        }
        pos += 4;
        result += 4 * BITS_PER_LONG;
        size -= 4 * BITS_PER_LONG;
    }
    while size >= BITS_PER_LONG {
        let tmp = addr[pos];
        pos += 1;
        if tmp != 0 {
            return found_middle(result, tmp);
        }
        result += BITS_PER_LONG;
        size -= BITS_PER_LONG;
    }
    if size == 0 {
        return result;
    }
    let tmp = addr[pos];
    found_first(result, tmp, size)
}

/// 寻找下一个未设置的 bit
///
/// 如果没有未设置的 bit 位, 则返回 `size`
pub fn find_next_zero_bit(addr: &[usize], mut size: usize, mut offset: usize) -> usize {
    let found_middle = |result: usize, tmp: usize| result + (!tmp).trailing_zeros() as usize;
    let found_first = |result: usize, mut tmp: usize, size: usize| {
        tmp |= usize::MAX << size;
        if tmp == usize::MAX {
            return result + size;
        }
        found_middle(result, tmp)
    };

    if offset >= size {
        return size;
    }
    let mut result = offset & !(BITS_PER_LONG - 1);
    size -= result;
    offset %= BITS_PER_LONG;
    let mut pos = bit_word(offset);
    if offset != 0 {
        let mut tmp = addr[pos];
        pos += 1;
        tmp |= usize::MAX >> (BITS_PER_LONG - offset);
        if size < BITS_PER_LONG {
            return found_first(result, tmp, size);
        }
        if !tmp != 0 {
            return found_middle(result, tmp);
        }
        size -= BITS_PER_LONG;
        result += BITS_PER_LONG;
    }
    while size & !(BITS_PER_LONG - 1) != 0 {
        let tmp = addr[pos];
        pos += 1;
        if !tmp != 0 {
            return found_middle(result, tmp);
        }
        result += BITS_PER_LONG;
        size -= BITS_PER_LONG;
    }
    if size == 0 {
        return result;
    }
    let tmp = addr[pos];
    found_first(result, tmp, size)
}

/// 寻找第一个被设置的 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
}