use std::mem;
use std::ops;
pub trait BlockType: Copy +
PartialEq +
Ord +
ops::BitAnd<Output = Self> +
ops::BitOr<Output = Self> +
ops::BitXor<Output = Self> +
ops::Not<Output = Self> +
ops::Shl<usize, Output = Self> +
ops::Shr<usize, Output = Self> +
ops::Sub<Output = Self>
{
#[inline]
fn nbits() -> usize {
8 * mem::size_of::<Self>()
}
#[inline]
fn div_nbits(index: u64) -> usize {
(index >> Self::lg_nbits()) as usize
}
#[inline]
fn checked_div_nbits(index: u64) -> Option<usize> {
(index >> Self::lg_nbits()).to_usize()
}
#[inline]
fn ceil_div_nbits(index: u64) -> usize {
Self::div_nbits(index + (Self::nbits() as u64 - 1))
}
#[inline]
fn checked_ceil_div_nbits(index: u64) -> Option<usize> {
Self::checked_div_nbits(index + (Self::nbits() as u64 - 1))
}
#[inline]
fn mod_nbits(index: u64) -> usize {
let mask: u64 = Self::lg_nbits_mask();
(index & mask) as usize
}
#[inline]
fn mul_nbits(index: usize) -> u64 {
(index as u64) << Self::lg_nbits()
}
#[inline]
fn block_bits(len: u64, position: usize) -> usize {
let block_start = Self::mul_nbits(position);
let block_limit = block_start + Self::nbits() as u64;
debug_assert!( block_start <= len,
"BlockType::block_bits: precondition" );
usize::if_then_else(
block_limit <= len,
Self::nbits(),
len.wrapping_sub(block_start) as usize
)
}
#[inline]
fn lg_nbits() -> usize {
Self::nbits().floor_lg()
}
#[inline]
fn lg_nbits_mask<Result: BlockType>() -> Result {
Result::low_mask(Self::lg_nbits())
}
#[inline]
fn low_mask(element_bits: usize) -> Self {
debug_assert!(element_bits <= Self::nbits());
if element_bits == Self::nbits() {
!Self::zero()
} else {
(Self::one() << element_bits) - Self::one()
}
}
#[inline]
fn nth_mask(bit_index: usize) -> Self {
Self::one() << bit_index
}
#[inline]
fn get_bit(self, bit_index: usize) -> bool {
assert!(bit_index < Self::nbits(), "Block::get_bit: out of bounds");
self & Self::nth_mask(bit_index) != Self::zero()
}
#[inline]
fn with_bit(self, bit_index: usize, bit_value: bool) -> Self {
assert!(bit_index < Self::nbits(), "Block::with_bit: out of bounds");
if bit_value {
self | Self::nth_mask(bit_index)
} else {
self & !Self::nth_mask(bit_index)
}
}
#[inline]
fn get_bits(self, start: usize, len: usize) -> Self {
assert!(start + len <= Self::nbits(),
"Block::get_bits: out of bounds");
(self >> start) & Self::low_mask(len)
}
#[inline]
fn with_bits(self, start: usize, len: usize, value: Self) -> Self {
assert!(start + len <= Self::nbits(),
"Block::with_bits: out of bounds");
let mask = Self::low_mask(len) << start;
let shifted_value = value << start;
(self & !mask) | (shifted_value & mask)
}
#[inline]
fn ceil_lg(self) -> usize {
usize::if_then(
self > Self::one(),
Self::nbits().wrapping_sub((self.wrapping_sub(Self::one())).leading_zeros() as usize)
)
}
#[inline]
fn floor_lg(self) -> usize {
usize::if_then(
self > Self::one(),
Self::nbits().wrapping_sub(1).wrapping_sub(self.leading_zeros() as usize)
)
}
fn wrapping_shl(self, shift: u32) -> Self;
fn wrapping_sub(self, other: Self) -> Self;
fn leading_zeros(self) -> usize;
fn to_usize(self) -> Option<usize>;
fn zero() -> Self;
fn one() -> Self;
}
trait IfThenElse {
fn if_then_else(cond: bool, then_val: Self, else_val: Self) -> Self;
fn if_then(cond: bool, then_val: Self) -> Self;
}
macro_rules! impl_block_type {
( $ty:ident )
=>
{
impl IfThenElse for $ty {
#[inline]
fn if_then_else(cond: bool, then_val: Self, else_val: Self) -> Self {
let then_cond = cond as Self;
let else_cond = 1 - then_cond;
(then_cond * then_val) | (else_cond * else_val)
}
#[inline]
fn if_then(cond: bool, then_val: Self) -> Self {
(cond as Self) * then_val
}
}
impl BlockType for $ty {
#[inline]
fn low_mask(k: usize) -> Self {
debug_assert!(k <= Self::nbits());
let a = Self::one().wrapping_shl(k as u32).wrapping_sub(1);
let b = (Self::div_nbits(k as u64) & 1) as Self * !0;
a | b
}
#[inline]
fn wrapping_shl(self, shift: u32) -> Self {
self.wrapping_shl(shift)
}
#[inline]
fn wrapping_sub(self, other: Self) -> Self {
self.wrapping_sub(other)
}
#[inline]
fn leading_zeros(self) -> usize {
self.leading_zeros() as usize
}
#[inline]
fn to_usize(self) -> Option<usize> {
if self as usize as Self == self {
Some(self as usize)
} else {
None
}
}
#[inline]
fn zero() -> Self {
0
}
#[inline]
fn one() -> Self {
1
}
}
}
}
impl_block_type!(u8);
impl_block_type!(u16);
impl_block_type!(u32);
impl_block_type!(u64);
#[cfg(int_128)]
impl_block_type!(u128);
impl_block_type!(usize);
#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct Address {
pub block_index: usize,
pub bit_offset: usize,
}
impl Address {
#[inline]
pub fn new<Block: BlockType>(bit_index: u64) -> Self {
Address {
block_index: Block::checked_div_nbits(bit_index)
.expect("Address::new: index overflow"),
bit_offset: Block::mod_nbits(bit_index),
}
}
}
#[cfg(test)]
mod test {
use super::*;
use quickcheck::{quickcheck, TestResult};
#[test]
fn nbits() {
assert_eq!(8, u8::nbits());
assert_eq!(16, u16::nbits());
assert_eq!(32, u32::nbits());
assert_eq!(64, u64::nbits());
}
quickcheck!{
fn prop_div_nbits(n: u32) -> bool {
u32::div_nbits(n as u64) == (n / 32) as usize
}
fn prop_ceil_div_nbits1(n: u32) -> bool {
u32::ceil_div_nbits(n as u64) ==
(n as f32 / 32.0f32).ceil() as usize
}
fn prop_ceil_div_nbits2(n: u32) -> bool {
let result = u32::ceil_div_nbits(n as u64);
result * 32 >= n as usize &&
(result == 0 || (result - 1) * 32 < n as usize)
}
fn prop_mod_nbits(n: u32) -> bool {
u32::mod_nbits(n as u64) == n as usize % 32
}
fn prop_mul_nbits(n: u32) -> bool {
u32::mul_nbits(n as usize) == n as u64 * 32
}
}
#[test]
fn lg_nbits() {
assert_eq!( u8::lg_nbits(), 3 );
assert_eq!( u16::lg_nbits(), 4 );
assert_eq!( u32::lg_nbits(), 5 );
assert_eq!( u64::lg_nbits(), 6 );
}
#[test]
fn low_mask() {
assert_eq!(0b00011111, u8::low_mask(5));
assert_eq!(0b0011111111111111, u16::low_mask(14));
assert_eq!(0b1111111111111111, u16::low_mask(16));
}
#[test]
fn nth_mask() {
assert_eq!(0b10000000, u8::nth_mask(7));
assert_eq!(0b01000000, u8::nth_mask(6));
assert_eq!(0b00100000, u8::nth_mask(5));
assert_eq!(0b00000010, u8::nth_mask(1));
assert_eq!(0b00000001, u8::nth_mask(0));
assert_eq!(0b0000000000000001, u16::nth_mask(0));
assert_eq!(0b1000000000000000, u16::nth_mask(15));
}
#[test]
fn get_bits() {
assert_eq!(0b0,
0b0100110001110000u16.get_bits(0, 0));
assert_eq!(0b010,
0b0100110001110000u16.get_bits(13, 3));
assert_eq!( 0b110001,
0b0100110001110000u16.get_bits(6, 6));
assert_eq!( 0b10000,
0b0100110001110000u16.get_bits(0, 5));
assert_eq!(0b0100110001110000,
0b0100110001110000u16.get_bits(0, 16));
}
#[test]
fn with_bits() {
assert_eq!(0b0111111111000001,
0b0110001111000001u16.with_bits(10, 3, 0b111));
assert_eq!(0b0101110111000001,
0b0110001111000001u16.with_bits(9, 5, 0b01110));
assert_eq!(0b0110001111000001,
0b0110001111000001u16.with_bits(14, 0, 0b01110));
assert_eq!(0b0110001110101010,
0b0110001111000001u16.with_bits(0, 8, 0b10101010));
assert_eq!(0b0000000000000010,
0b0110001111000001u16.with_bits(0, 16, 0b10));
}
#[test]
fn get_bit() {
assert!(! 0b00000000u8.get_bit(0));
assert!(! 0b00000000u8.get_bit(1));
assert!(! 0b00000000u8.get_bit(2));
assert!(! 0b00000000u8.get_bit(3));
assert!(! 0b00000000u8.get_bit(7));
assert!(! 0b10101010u8.get_bit(0));
assert!( 0b10101010u8.get_bit(1));
assert!(! 0b10101010u8.get_bit(2));
assert!( 0b10101010u8.get_bit(3));
assert!( 0b10101010u8.get_bit(7));
}
#[test]
fn with_bit() {
assert_eq!(0b00100000, 0b00000000u8.with_bit(5, true));
assert_eq!(0b00000000, 0b00000000u8.with_bit(5, false));
assert_eq!(0b10101010, 0b10101010u8.with_bit(7, true));
assert_eq!(0b00101010, 0b10101010u8.with_bit(7, false));
assert_eq!(0b10101011, 0b10101010u8.with_bit(0, true));
assert_eq!(0b10101010, 0b10101010u8.with_bit(0, false));
}
#[test]
fn floor_lg() {
assert_eq!(0, 1u32.floor_lg());
assert_eq!(1, 2u32.floor_lg());
assert_eq!(1, 3u32.floor_lg());
assert_eq!(2, 4u32.floor_lg());
assert_eq!(2, 5u32.floor_lg());
assert_eq!(2, 7u32.floor_lg());
assert_eq!(3, 8u32.floor_lg());
fn prop(n: u64) -> TestResult {
if n == 0 { return TestResult::discard(); }
TestResult::from_bool(
2u64.pow(n.floor_lg() as u32) <= n
&& 2u64.pow(n.floor_lg() as u32 + 1) > n)
}
quickcheck(prop as fn(u64) -> TestResult);
}
#[test]
fn ceil_lg() {
assert_eq!(0, 1u32.ceil_lg());
assert_eq!(1, 2u32.ceil_lg());
assert_eq!(2, 3u32.ceil_lg());
assert_eq!(2, 4u32.ceil_lg());
assert_eq!(3, 5u32.ceil_lg());
assert_eq!(3, 7u32.ceil_lg());
assert_eq!(3, 8u32.ceil_lg());
assert_eq!(4, 9u32.ceil_lg());
fn prop(n: u64) -> TestResult {
if n <= 1 { return TestResult::discard(); }
TestResult::from_bool(
2u64.pow(n.ceil_lg() as u32) >= n
&& 2u64.pow(n.ceil_lg() as u32 - 1) < n)
}
quickcheck(prop as fn(u64) -> TestResult);
}
#[test]
fn block_bits() {
assert_eq!( u16::block_bits(1, 0), 1 );
assert_eq!( u16::block_bits(2, 0), 2 );
assert_eq!( u16::block_bits(16, 0), 16 );
assert_eq!( u16::block_bits(16, 1), 0 );
assert_eq!( u16::block_bits(23, 0), 16 );
assert_eq!( u16::block_bits(23, 1), 7 );
assert_eq!( u16::block_bits(35, 0), 16 );
assert_eq!( u16::block_bits(35, 1), 16 );
assert_eq!( u16::block_bits(35, 2), 3 );
assert_eq!( u16::block_bits(48, 0), 16 );
assert_eq!( u16::block_bits(48, 1), 16 );
assert_eq!( u16::block_bits(48, 2), 16 );
assert_eq!( u16::block_bits(48, 3), 0 );
}
}