Acme-Bitfield
view release on metacpan or search on metacpan
# Mark item 42 as present
$bf->set( 42 );
# Check if we have item 42
say 'Found it!' if $bf->get(42);
# Statistics
printf "Progress: %.2f%%\r", ($bf->count / $bf->size * 100);
# Export raw binary for network transfer
my $raw = $bf->data;
```
# DESCRIPTION
`Acme::Bitfield` provides a compact way to track a large set of big endian boolean flags. It is specifically designed
to follow the BitTorrent (BEP 03) bit-ordering convention, where the most significant bit of the first byte represents
index 0.
## Bit Ordering
Returns true if all bits are set to 1.
## `is_empty( )`
Returns true if all bits are set to 0.
## `size( )`
Returns the total capacity of the bitfield.
## `data( )`
Returns the raw binary string representation of the bitfield.
## `set_data( $string )`
Sets the raw binary representation. The input string will be truncated or padded to match the `size`, and any excess
bits in the last byte will be zeroed.
## `fill( )`
Sets all bits within the `size` to 1.
## `find_missing( )`
lib/Acme/Bitfield.pm view on Meta::CPAN
use v5.42;
use feature 'class';
no warnings 'experimental::class';
#
class Acme::Bitfield v1.1.0 {
field $size : reader : param;
field $data : reader : param = "\0" x int( ( $size + 7 ) / 8 );
ADJUST {
$self->_clean;
}
method set_data ($val) {
$data = $val;
$self->_clean; # We can't use the :writer because we must call this
}
# Internal helper to map BitTorrent bit index to vec index
# BT: bit 0 is 0x80, bit 7 is 0x01
# vec: bit 0 is 0x01, bit 7 is 0x80
sub _map ($index) { ( $index & ~7 ) | ( 7 - ( $index & 7 ) ) }
method get ($index) {
return 0 if $index < 0 || $index >= $size;
vec $data, _map($index), 1;
}
method set ($index) {
return if $index < 0 || $index >= $size;
vec( $data, _map($index), 1 ) = 1;
}
method clear ($index) {
return if $index < 0 || $index >= $size;
vec( $data, _map($index), 1 ) = 0;
}
method count () {
return unpack( '%32b*', $data );
}
method is_full () {
return $self->count == $size;
}
method is_empty () {
return $data =~ tr/\0//c ? 0 : 1;
}
method union ($other) {
my $new = __CLASS__->new( size => $size );
$new->set_data( $data|.$other->data );
return $new;
}
method intersection ($other) {
my $new = __CLASS__->new( size => $size );
$new->set_data( $data&.$other->data );
return $new;
}
method difference ($other) {
# Bits set in self but NOT in other
my $new = __CLASS__->new( size => $size );
$new->set_data( $data&.~.$other->data );
return $new;
}
method _clean () {
# internal method to automatically handle data truncation, padding, and bit masking
my $expected_len = int( ( $size + 7 ) / 8 );
if ( length($data) > $expected_len ) {
substr( $data, $expected_len ) = "";
}
elsif ( length($data) < $expected_len ) {
$data .= "\0" x ( $expected_len - length($data) );
}
my $bits_in_last_byte = $size % 8;
if ( $bits_in_last_byte != 0 && $expected_len > 0 ) {
my $mask = ( 0xFF << ( 8 - $bits_in_last_byte ) ) & 0xFF;
substr( $data, -1, 1 ) &.= chr($mask);
}
}
method fill () {
$data = "\xFF" x length($data);
$self->_clean;
}
method find_missing () {
my $index = index( unpack( 'B*', $data ), '0' );
return ( $index >= 0 && $index < $size ) ? $index : ();
}
method inverse () {
my $inverted = __CLASS__->new( size => $size );
$inverted->set_data( ~.$data );
return $inverted;
}
};
#
1;
lib/Acme/Bitfield.pod view on Meta::CPAN
# Mark item 42 as present
$bf->set( 42 );
# Check if we have item 42
say 'Found it!' if $bf->get(42);
# Statistics
printf "Progress: %.2f%%\r", ($bf->count / $bf->size * 100);
# Export raw binary for network transfer
my $raw = $bf->data;
=head1 DESCRIPTION
C<Acme::Bitfield> provides a compact way to track a large set of big endian boolean flags. It is specifically designed
to follow the BitTorrent (BEP 03) bit-ordering convention, where the most significant bit of the first byte represents
index 0.
=head2 Bit Ordering
* Byte 0, Bit 0 (0x80) -> Index 0 * Byte 0, Bit 7 (0x01) -> Index 7 * Byte 1, Bit 0 (0x80) -> Index 8
lib/Acme/Bitfield.pod view on Meta::CPAN
Returns true if all bits are set to 1.
=head2 C<is_empty( )>
Returns true if all bits are set to 0.
=head2 C<size( )>
Returns the total capacity of the bitfield.
=head2 C<data( )>
Returns the raw binary string representation of the bitfield.
=head2 C<set_data( $string )>
Sets the raw binary representation. The input string will be truncated or padded to match the C<size>, and any excess
bits in the last byte will be zeroed.
=head2 C<fill( )>
Sets all bits within the C<size> to 1.
=head2 C<find_missing( )>
ok $bf->get(9), 'Bit 9 set';
ok !$bf->get(5), 'Bit 5 not set';
is $bf->count, 2, 'Count is 2';
$bf->clear(0);
ok !$bf->get(0), 'Bit 0 cleared';
is $bf->count, 1, 'Count is 1';
};
subtest 'Bit Ordering (BEP 03)' => sub {
my $bf = Acme::Bitfield->new( size => 8 );
$bf->set(0); # Should be 0x80 in the first byte
is unpack( 'H*', $bf->data ), '80', 'Index 0 is high bit of first byte';
$bf->clear(0);
$bf->set(7); # Should be 0x01
is unpack( 'H*', $bf->data ), '01', 'Index 7 is low bit of first byte';
};
subtest 'Fill and Find Missing' => sub {
my $bf = Acme::Bitfield->new( size => 5 );
$bf->fill();
is $bf->count, 5, 'All 5 bits set';
is $bf->find_missing(), undef, 'No missing bits';
$bf->clear(2);
is $bf->find_missing(), 2, 'Found missing bit at index 2';
};
};
ok !$inv->get(0), 'Bit 0 is now 0';
ok $inv->get(1), 'Bit 1 is now 1';
ok !$inv->get(5), 'Bit 5 is now 0';
ok $inv->get(8), 'Bit 8 is now 1';
ok !$inv->get(9), 'Bit 9 is now 0';
};
subtest 'Inverse of Empty' => sub {
my $bf = Acme::Bitfield->new( size => 8 );
my $inv = $bf->inverse();
is $inv->count, 8, 'Inverse of empty is full';
is unpack( 'H*', $inv->data ), 'ff', 'Data is 0xFF';
};
subtest 'Inverse of Full' => sub {
my $bf = Acme::Bitfield->new( size => 8 );
$bf->fill();
my $inv = $bf->inverse();
is $inv->count, 0, 'Inverse of full is empty';
is unpack( 'H*', $inv->data ), '00', 'Data is 0x00';
};
subtest 'Excess Bits remain zero' => sub {
my $bf = Acme::Bitfield->new( size => 10 );
my $inv = $bf->inverse();
# 10 bits means 2 bytes.
# Inverted should have 10 bits set to 1.
# Bits 10-15 should remain 0.
# Byte 1: 11111111 (0xFF)
# Byte 2: 11000000 (0xC0 in BEP 03 order)
is unpack( 'H*', $inv->data ), 'ffc0', 'Excess bits are zeroed out in inverted bitfield';
};
};
subtest 'Bitwise Operations' => sub {
my $bf1 = Acme::Bitfield->new( size => 10 );
my $bf2 = Acme::Bitfield->new( size => 10 );
$bf1->set($_) for ( 0, 1, 2 );
$bf2->set($_) for ( 2, 3, 4 );
subtest 'Union' => sub {
my $union = $bf1->union($bf2);
is( $union->count, 5, 'Union count is 5' );
ok( !$bf->is_full, 'Not initially full' );
$bf->fill;
ok( $bf->is_full, 'Full after fill' );
ok( !$bf->is_empty, 'Not empty after fill' );
$bf->clear(0);
ok( !$bf->is_full, 'Not full after clearing one bit' );
};
subtest 'Edge Cases' => sub {
subtest 'Zero Size' => sub {
my $bf = Acme::Bitfield->new( size => 0 );
is( $bf->data, '', 'Data is empty string' );
is( $bf->count, 0, 'Count is 0' );
ok( $bf->is_full, 'Zero size is technically full' );
};
subtest 'Mismatched Data Length' => sub {
my $bf = Acme::Bitfield->new( size => 8 );
$bf->set_data("\xFF\xFF\xFF");
is( length( $bf->data ), 1, 'Data truncated to 1 byte' );
is( $bf->count, 8, 'Count is 8' );
$bf->set_data("");
is( length( $bf->data ), 1, 'Data padded to 1 byte' );
is( ord( $bf->data ), 0, 'Padded with zeros' );
};
subtest 'Last Byte Masking' => sub {
my $bf = Acme::Bitfield->new( size => 10 );
# 10 bits = 2 bytes. Last byte should only have 2 bits.
$bf->set_data("\xFF\xFF");
is( ord( substr( $bf->data, 1, 1 ) ), 0xC0, 'Last byte masked to 0xC0' );
is( $bf->count, 10, 'Count is 10' );
};
};
#
done_testing;
( run in 0.890 second using v1.01-cache-2.11-cpan-c966e8aa7e8 )