#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Bitfield {
bits: Vec<u8>,
num_bits: usize,
}
impl Bitfield {
pub fn new(num_bits: usize) -> Self {
let num_bytes = num_bits.div_ceil(8);
Bitfield {
bits: vec![0u8; num_bytes],
num_bits,
}
}
pub fn all_set(num_bits: usize) -> Self {
let num_bytes = num_bits.div_ceil(8);
let mut bits = vec![0xFFu8; num_bytes];
let remaining_bits = num_bits % 8;
if remaining_bits > 0 && num_bytes > 0 {
let mask = ((1u8 << remaining_bits) - 1) << (8 - remaining_bits);
bits[num_bytes - 1] = mask;
}
Bitfield { bits, num_bits }
}
pub fn from_bytes(data: &[u8], num_bits: usize) -> Self {
let num_bytes = num_bits.div_ceil(8);
let mut bits = vec![0u8; num_bytes];
let copy_len = std::cmp::min(data.len(), num_bytes);
if copy_len > 0 {
bits[..copy_len].copy_from_slice(&data[..copy_len]);
}
let remaining_bits = num_bits % 8;
if remaining_bits > 0 && num_bytes > 0 {
let mask = ((1u8 << remaining_bits) - 1) << (8 - remaining_bits);
bits[num_bytes - 1] &= mask;
}
Bitfield { bits, num_bits }
}
pub fn as_bytes(&self) -> &[u8] {
&self.bits
}
pub fn len(&self) -> usize {
self.num_bits
}
pub fn is_empty(&self) -> bool {
self.num_bits == 0
}
pub fn set(&mut self, index: usize) -> Option<()> {
if index >= self.num_bits {
return None;
}
let byte_index = index / 8;
let bit_offset = index % 8;
self.bits[byte_index] |= 1 << (7 - bit_offset);
Some(())
}
pub fn clear(&mut self, index: usize) -> Option<()> {
if index >= self.num_bits {
return None;
}
let byte_index = index / 8;
let bit_offset = index % 8;
self.bits[byte_index] &= !(1 << (7 - bit_offset));
Some(())
}
pub fn test(&self, index: usize) -> bool {
if index >= self.num_bits {
return false;
}
let byte_index = index / 8;
let bit_offset = index % 8;
(self.bits[byte_index] & (1 << (7 - bit_offset))) != 0
}
pub fn count_set(&self) -> usize {
let mut count = 0;
let full_bytes = self.num_bits / 8;
for byte in self.bits.iter().take(full_bytes) {
count += byte.count_ones() as usize;
}
let remaining_bits = self.num_bits % 8;
if remaining_bits > 0 && full_bytes < self.bits.len() {
let last_byte = self.bits[full_bytes];
for bit in 0..remaining_bits {
if last_byte & (1 << (7 - bit)) != 0 {
count += 1;
}
}
}
count
}
pub fn count_clear(&self) -> usize {
self.num_bits - self.count_set()
}
pub fn is_all_set(&self) -> bool {
self.count_set() == self.num_bits
}
pub fn is_all_clear(&self) -> bool {
self.bits.iter().all(|&b| b == 0)
}
pub fn find_first_set(&self) -> Option<usize> {
for (byte_index, &byte) in self.bits.iter().enumerate() {
if byte != 0 {
for bit_offset in 0..8 {
let index = byte_index * 8 + bit_offset;
if index < self.num_bits && (byte & (1 << (7 - bit_offset))) != 0 {
return Some(index);
}
}
}
}
None
}
pub fn find_first_clear(&self) -> Option<usize> {
for (byte_index, &byte) in self.bits.iter().enumerate() {
let start_bit = byte_index * 8;
let end_bit = std::cmp::min(start_bit + 8, self.num_bits);
for bit_offset in 0..(end_bit - start_bit) {
let index = start_bit + bit_offset;
if (byte & (1 << (7 - bit_offset))) == 0 {
return Some(index);
}
}
}
None
}
pub fn find_next_set(&self, after: usize) -> Option<usize> {
let start = after + 1;
if start >= self.num_bits {
return None;
}
let byte_index = start / 8;
let bit_offset = start % 8;
let byte = self.bits[byte_index];
for bit in bit_offset..8 {
let index = byte_index * 8 + bit;
if index < self.num_bits && (byte & (1 << (7 - bit))) != 0 {
return Some(index);
}
}
for (bi, &b) in self.bits.iter().enumerate().skip(byte_index + 1) {
if b != 0 {
for bit_offset in 0..8 {
let index = bi * 8 + bit_offset;
if index < self.num_bits && (b & (1 << (7 - bit_offset))) != 0 {
return Some(index);
}
}
}
}
None
}
pub fn iter_set(&self) -> SetBitIter<'_> {
SetBitIter::new(self)
}
pub fn iter_clear(&self) -> ClearBitIter<'_> {
ClearBitIter::new(self)
}
pub fn memory_usage(&self) -> usize {
self.bits.len()
}
pub fn vec_bool_memory_usage(&self) -> usize {
self.num_bits
}
pub fn memory_savings_ratio(&self) -> f64 {
if self.bits.is_empty() {
return 1.0;
}
self.num_bits as f64 / self.bits.len() as f64
}
pub fn set_all(&mut self) {
self.bits.fill(0xFF);
let remaining_bits = self.num_bits % 8;
if remaining_bits > 0 && !self.bits.is_empty() {
let mask = ((1u8 << remaining_bits) - 1) << (8 - remaining_bits);
let last_idx = self.bits.len() - 1;
self.bits[last_idx] = mask;
}
}
pub fn clear_all(&mut self) {
self.bits.fill(0);
}
pub fn bitand_assign(&mut self, other: &Bitfield) {
assert_eq!(self.num_bits, other.num_bits, "Bitfield lengths must match");
for (a, b) in self.bits.iter_mut().zip(other.bits.iter()) {
*a &= b;
}
}
pub fn bitor_assign(&mut self, other: &Bitfield) {
assert_eq!(self.num_bits, other.num_bits, "Bitfield lengths must match");
for (a, b) in self.bits.iter_mut().zip(other.bits.iter()) {
*a |= b;
}
}
pub fn bitxor_assign(&mut self, other: &Bitfield) {
assert_eq!(self.num_bits, other.num_bits, "Bitfield lengths must match");
for (a, b) in self.bits.iter_mut().zip(other.bits.iter()) {
*a ^= b;
}
}
}
pub struct SetBitIter<'a> {
bitfield: &'a Bitfield,
current: usize,
}
impl<'a> SetBitIter<'a> {
fn new(bitfield: &'a Bitfield) -> Self {
SetBitIter {
bitfield,
current: 0,
}
}
}
impl<'a> Iterator for SetBitIter<'a> {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
while self.current < self.bitfield.num_bits {
if self.bitfield.test(self.current) {
let result = self.current;
self.current += 1;
return Some(result);
}
self.current += 1;
}
None
}
}
pub struct ClearBitIter<'a> {
bitfield: &'a Bitfield,
current: usize,
}
impl<'a> ClearBitIter<'a> {
fn new(bitfield: &'a Bitfield) -> Self {
ClearBitIter {
bitfield,
current: 0,
}
}
}
impl<'a> Iterator for ClearBitIter<'a> {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
while self.current < self.bitfield.num_bits {
if !self.bitfield.test(self.current) {
let result = self.current;
self.current += 1;
return Some(result);
}
self.current += 1;
}
None
}
}
#[cfg(test)]
#[path = "bitfield_tests.rs"]
mod tests;