Algorithm-BitVector
view release on metacpan or search on metacpan
Examples/BitVectorDemo.pl view on Meta::CPAN
print "\nInt value of the previous bitvector as computed by int_value():\n";
print int($bv) . "\n"; # 123456
# Construct a bitvector from a very large integer:
use Math::BigInt;
my $x = Math::BigInt->new('12345678901234567890123456789012345678901234567890');
$bv = Algorithm::BitVector->new( intVal => $x );
print "\nHere is a bitvector constructed from a very large integer:\n";
print "$bv\n";
printf "The integer value of the above bitvector shown as a string is: %s\n", $bv->int_value();
print "Size of the bitvector: " . $bv->length() . "\n";
# Construct a bitvector of a specified length from a large integer:
$bv =Algorithm::BitVector->new(intVal => Math::BigInt->new("89485765"), size => 32);
print "\nHere is a bitvector of a specified size constructed from a large integer:\n";
my $len= $bv->length();
print "$bv\n";
print "size of bitvec: $len\n";
printf "The integer value of the above bitvector shown as a string is: %s\n", $bv->int_value();
print "Size of the bitvector: " . $bv->length() . "\n";
# Construct a bitvector directly from a bit string:
$bv = Algorithm::BitVector->new( bitstring => '00110011' );
print "\nBitvector constructed directly from a bit string:\n";
print "$bv\n"; # 00110011
$bv = Algorithm::BitVector->new( bitstring => '');
print "\nBitvector constructed directly from an empty bit string:\n";
print "$bv\n"; # nothing
print "\nInteger value of the previous bitvector:\n";
print int($bv) . "\n"; # 0
Examples/BitVectorDemo.pl view on Meta::CPAN
print "$bv\n"; # 0100
$bv = Algorithm::BitVector->new(intVal=>6) | Algorithm::BitVector->new(intVal=>13);
print "$bv\n"; # 1111
$bv = Algorithm::BitVector->new(intVal=>1) ^ Algorithm::BitVector->new(intVal=>13);
print "$bv\n"; # 1100
$bv = Algorithm::BitVector->new(intVal=>1) & Algorithm::BitVector->new(intVal=>13);
print "$bv\n"; # 0001
$bv = Algorithm::BitVector->new(intVal=>1) | Algorithm::BitVector->new(intVal=>13);
print "$bv\n"; # 1101
# Experiments with set_bit() and length():\n";
print "\nExperiments with set_bit() and length():\n";
$bv7->set_bit(7,0);
print "$bv7\n"; # 1111111011111111111
print length($bv7) . "\n"; # 19
my $bv8 = ($bv5 & $bv6) ^ $bv7;
print "$bv8\n"; # 1111111011111111111
# Constructing a bitvector from the contents of a disk file:
print "\nConstruct a bitvector from what is in the file testinput1.txt:\n";
$bv = Algorithm::BitVector->new( filename => 'testinput.txt' );
#print "$bv\n"; # nothing to show
$bv1 = $bv->read_bits_from_file(64);
print "\nPrint out the first 64 bits read from the file:\n";
print "$bv1\n";
Examples/BitVectorDemo.pl view on Meta::CPAN
print "$bv2\n"; # 1010
# Write an internally generated bitvector to a disk file:
print "\nExperiment with writing an internally generated bitvector out to a disk file:\n";
$bv1 = Algorithm::BitVector->new( bitstring => '00001010' );
open my $FILEOUT, ">test.txt";
$bv1->write_to_file( $FILEOUT );
close $FILEOUT;
$bv2 = Algorithm::BitVector->new( filename => 'test.txt' );
$bv3 = $bv2->read_bits_from_file( 32 );
print "\nDisplay bitvectors written out to file and read back from the file and their respective lengths:\n";
print "$bv1 $bv3\n"; # 00001010 00001010
print length($bv1) . " " . length($bv3) . "\n"; # 8 8
# Experiment with reading a file from beginning to end and constructing 64-bit bit
# vectors as you go along:
print "\nExperiments with reading a file from the beginning to end:\n";
$bv = Algorithm::BitVector->new( filename => 'testinput.txt' );
print "Here are all the bits read from the file:\n";
while ($bv->{more_to_read}) {
my $bv_read = $bv->read_bits_from_file( 64 );
print "$bv_read\n";
}
Examples/BitVectorDemo.pl view on Meta::CPAN
# Experiments with circular shifts to the left and to the right:
print "\nTry circular shifts to the left and to the right for the following bitvector:\n";
print "$bv3\n"; # 0100000100100000011010000111010101101110011001110111001001111001
print "Circular shift to the left by 7 positions:\n";
$bv3 = $bv3 << 7;
print "$bv3\n"; # 1001000000110100001110101011011100110011101110010011110010100000
print "\nCircular shift to the right by 7 positions:\n";
$bv3 = $bv3 >> 7;
print "$bv3\n"; # 0100000100100000011010000111010101101110011001110111001001111001
print "Test length on the above bitvector: ";
print length($bv3) . "\n"; # 64
print "\nExperiments with chained invocations of circular shifts:\n";
$bv = Algorithm::BitVector->new( bitlist => [1, 1, 1, 0, 0, 1] );
print "$bv\n"; # 111001
$bv = $bv >> 1;
print "$bv\n"; # 111100
$bv = $bv >> 1 >> 1;
print "$bv\n"; # 001111
$bv = Algorithm::BitVector->new( bitlist => [1, 1, 1, 0, 0, 1] );
print "$bv\n"; # 111001
lib/Algorithm/BitVector.pm view on Meta::CPAN
my $bitvector = shift;
my $block;
my $more_to_read;
my $i = 0;
my $byte_as_bits;
my $bitstring = '';
while ( $i < $blocksize / 8 ) {
$i++;
my $num_bytes_read = sysread($bitvector->{FILEIN}, my $byte, 1);
unless ($num_bytes_read) {
if (length($bitstring) < $blocksize) {
$bitvector->{more_to_read} = 0;
$more_to_read = 0;
}
return $bitstring;
} else {
my $bits_as_string = sprintf "%vb", $byte;
$bits_as_string = '0' x (8 - length($bits_as_string)) . $bits_as_string;
$bitstring .= $bits_as_string;
}
}
my $file_pos = tell $bitvector->{FILEIN};
# peek at the next byte; moves file position only if a
# byte is read
my $num_bytes_read = sysread($bitvector->{FILEIN}, my $next_byte, 1);
if ($num_bytes_read) {
# pretend we never read the byte
sysseek $bitvector->{FILEIN}, $file_pos - 1, SEEK_CUR;
lib/Algorithm/BitVector.pm view on Meta::CPAN
# if (ref($self->{intVal}) eq 'Math::BigInt') {
if (ref($self->{intVal}) eq 'Math::BigInt' && ! defined $self->{size}) {
my $bitlist_str = $self->{intVal}->as_bin();
$bitlist_str =~ s/^0b//;
@bitarray = split //, $bitlist_str;
} elsif (ref($self->{intVal}) eq 'Math::BigInt' && defined $self->{size}) { #new<<<<<<<<<<<<<
my $bitlist_str = $self->{intVal}->as_bin();
$bitlist_str =~ s/^0b//;
croak "\nThe value specified for size must be at least as large as for the " .
"smallest bitvector possible for the intVal integer: $!"
if $self->{size} < length $bitlist_str;
@bitarray = split //, $bitlist_str;
my $n = $self->{size} - @bitarray;
my $extended_bitlist_str = '0' x $n . $bitlist_str;
@bitarray = split //, $extended_bitlist_str;
} else {
my $bitlist_str = sprintf "%b", $self->{intVal};
if (defined $self->{size}) {
croak "\nThe value specified for size must be at least as large as for the " .
"smallest bitvector possible for the intVal integer: $!"
if $self->{size} < length $bitlist_str;
my $n = $self->{size} - length $bitlist_str;
my $extended_bitlist_str = '0' x $n . $bitlist_str;
@bitarray = split //, $extended_bitlist_str;
} else {
@bitarray = split //, $bitlist_str;
}
}
$self->{bitlist} = \@bitarray;
$self->{size} = scalar @{$self->{bitlist}};
}
} elsif (defined $self->{size}) {
lib/Algorithm/BitVector.pm view on Meta::CPAN
if $self->{filename} or $self->{intVal} or $self->{size}
or $self->{bitlist} or $self->{hexstring} or $self->{textstring};
my @bitlist_from_bitstring = split //, $self->{bitstring};
$self->{bitlist} = \@bitlist_from_bitstring;
$self->{size} = scalar @{$self->{bitlist}};
} elsif (defined $self->{textstring}) {
die "When using the `textstring' option in the constructor call, you cannot use any " .
"other option at the same time: $!"
if $self->{filename} or $self->{intVal} or $self->{size}
or $self->{bitlist} or $self->{hexstring} or $self->{bitstring};
my $bitstring_from_text = join '', map {length($_) == 8 ? $_
: ('0' x (8 - length($_))) . $_} map {sprintf "%b", $_}
map ord, split //, $self->{textstring};
my @bitlist_from_text = split //, $bitstring_from_text;
$self->{bitlist} = \@bitlist_from_text;
$self->{size} = scalar @{$self->{bitlist}};
} elsif (defined $self->{hexstring}) {
die "When using the `hexstring' option in the constructor call, you cannot use any " .
"other option at the same time: $!"
if $self->{filename} or $self->{intVal} or $self->{size}
or $self->{bitlist} or $self->{textstring} or $self->{bitstring};
my $bitstring_from_hex = join '', map {length($_) == 4 ? $_
: ('0' x (4 - length($_))) . $_} map {sprintf "%b", $_}
map {hex $_} split //, $self->{hexstring};
my @bitlist_from_hex = split //, $bitstring_from_hex;
$self->{bitlist} = \@bitlist_from_hex;
$self->{size} = scalar @{$self->{bitlist}};
}
my $shorts_needed = int( (@{$self->{bitlist}} + 15) / 16 );
@{$self->{_vector}} = map {unpack "n", pack("n", 0)} 0 .. $shorts_needed-1;
my @interleaved = (0..$self->{size}-1, @{$self->{bitlist}})
[map {$_,$_+$self->{size}} (0 .. $self->{size}-1)];
pairmap {$self->set_bit($a,$b)} @interleaved;
lib/Algorithm/BitVector.pm view on Meta::CPAN
map $slice_bv->set_bit($_ - $index_range->[0], $self->get_bit($_)), @$index_range[0..@$index_range-2];
return $slice_bv;
}
## Set a slice of a BitVector from the bits in the argument BitVector object:
sub set_slice {
my $self = shift;
my $index_range = shift;
my $values_bv = shift;
die "the width of the index range for slice setting does not equal the size of the values array"
unless @$index_range - 1 == $values_bv->length();
# unless @$index_range == $values_bv->length();
map $self->set_bit($_, $values_bv->get_bit($_ - $index_range->[0])), @$index_range[0..@$index_range-2];
}
## Overloading of the string conversion operator. Return the string representation
## of a bitvector.
sub _str {
my $self = shift;
return join '', map $self->get_bit($_), 0 .. $self->{size}-1;
}
lib/Algorithm/BitVector.pm view on Meta::CPAN
## Write the bitvector to the file object file_out. (A file object is returned
## by a call to open()). Since all file I/O is byte oriented, the bitvector must
## be multiple of 8 bits. Each byte treated as MSB first (0th index).
sub write_to_file {
my $self = shift;
die "Abort: The write_to_file() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
my $file_out = shift;
my $err_str = "Only a bitvector whose length is a multiple of 8 can " .
"be written to a file. Use the padding functions to satisfy " .
"this constraint.";
$self->{FILEOUT} = $file_out unless $self->{FILEOUT};
die $err_str if $self->{size} % 8;
for my $byte (0..$self->{size}/8 - 1){
my $value = 0;
foreach my $bit (0..7) {
$value += $self->get_bit( $byte*8+(7 - $bit) ) << $bit;
}
syswrite $file_out, chr($value), 1;
lib/Algorithm/BitVector.pm view on Meta::CPAN
$int_value = 0;
foreach my $i (0..$self->{size}-1) {
$int_value += $self->get_bit($i) * ( 2 ** ( $self->{size} - $i - 1 ) );
}
}
return $int_value;
}
## Return the text string formed by dividing the bitvector into bytes from the
## left and replacing each byte by its ASCII character (this is a useful thing
## to do only if the length of the vector is an integral multiple of 8 and every
## byte in your bitvector has a print representation)
sub get_bitvector_in_ascii {
my $self = shift;
die "Abort: The get_bitvector_in_ascii() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
die "\nThe bitvector for get_text_from_bitvector() must be an integral multiple of 8 bits: $!"
if $self->{size} % 8;
my $ascii = '';
for (my $i=0; $i < $self->{size}; $i += 8) {
lib/Algorithm/BitVector.pm view on Meta::CPAN
}
# for backward compatibility:
sub get_text_from_bitvector {
my $self = shift;
$self->get_bitvector_in_ascii(@_);
}
## Return a string of hex digits by scanning the bits from the left and
## replacing each sequence of 4 bits by its corresponding hex digit (this is a
## useful thing to do only if the length of the vector is an integral multiple
## of 4)
#sub get_hex_string_from_bitvector {
sub get_bitvector_in_hex {
my $self = shift;
die "Abort: The get_bitvector_in_hex() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
die "\nThe bitvector for get_hex_from_bitvector() must be a multiple of 4 bits: $!"
if $self->{size} % 4;
my $hex = '';
lib/Algorithm/BitVector.pm view on Meta::CPAN
sub read_bits_from_file {
my $self = shift;
die "Abort: The read_bits_from_file() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
my $blocksize = shift;
my $error_str = "You need to first construct a BitVector object with a filename as argument";
die "$error_str" unless $self->{filename};
die "block size must be a multiple of 8" if $blocksize % 8;
my $bitstr = _readblock( $blocksize, $self );
if (length $bitstr == 0) {
return Algorithm::BitVector->new( size => 0 );
print "file has no bits\n";
} else {
return Algorithm::BitVector->new( bitstring => $bitstr );
}
}
## For an in-place left circular shift by n bit positions
sub _lshift {
my $self = shift;
lib/Algorithm/BitVector.pm view on Meta::CPAN
$self->set_bit(0, $right_most_bit);
}
## Pad a bitvector with n zeros from the left
sub pad_from_left {
my $self = shift;
my $n = shift;
die "a negative value for index positions not allowed for padding from left" if $n < 0;
my $new_str = ('0' x $n) . "$self";
my $new_bitvec = Algorithm::BitVector->new( bitstring => $new_str );
$self->{size} = length $new_str;
$self->{_vector} = $new_bitvec->{_vector};
return $self;
}
## Pad a bitvector with n zeros from the right
sub pad_from_right {
my $self = shift;
my $n = shift;
my $new_str = "$self" . ('0' x $n);
my $new_bitvec = Algorithm::BitVector->new( bitstring => $new_str );
$self->{size} = length $new_str;
$self->{_vector} = $new_bitvec->{_vector};
return $self;
}
## Resets a previously created BitVector to either all zeros or all ones
## depending on the argument val.
sub reset {
my $self = shift;
my $val = shift;
die "Incorrect argument to reset(): $!" unless ($val == 0) or ($val == 1);
lib/Algorithm/BitVector.pm view on Meta::CPAN
}
## This method returns the "canonical" form of a BitVector instance that is obtained by
## circularly rotating the bit pattern through all possible shifts and returning the
## pattern with the maximum number of leading zeros. This is also the minimum int value
## version of a bit pattern. This method is useful in the "Local Binary Pattern"
## algorithm for characterizing image textures. If you are curious as to how, see my
## tutorial on "Measuring Texture and Color in Images."
sub min_canonical {
my $self = shift;
my @intvals_for_circular_shifts = map {int($self << 1)} 0 .. $self->length();
my $min_int_val = min @intvals_for_circular_shifts;
return Algorithm::BitVector->new( intVal => $min_int_val, size => $self->length() );
}
## Check if the integer value of the bitvector is a prime through the Miller-Rabin
## probabilistic test of primality. If not found to be a composite, estimate the
## probability of the bitvector being a prime using this test.
sub test_for_primality {
my $p = int(shift);
die "\nThe primality test method test_for_primality() is intended for only " .
"small integers --- integers that are relatively small in relation to " .
"the largest integer that can fit Perl's 4-byte int representation:$!"
lib/Algorithm/BitVector.pm view on Meta::CPAN
my $self = shift;
my $width = shift;
my $candidate_bits = "0b" . join '', Math::Random::random_uniform_integer($width, 0, 1);
my $candidate = oct $candidate_bits;
$candidate |= 1;
$candidate |= (1 << $width-1);
$candidate |= (2 << $width-3);
return Algorithm::BitVector->new( intVal => $candidate );
}
sub length {
my $self = shift;
return $self->{size};
}
sub _check_for_illegal_params {
my @params = @_;
my @legal_params = qw / filename
size
intVal
bitlist
lib/Algorithm/BitVector.pm view on Meta::CPAN
Version 1.26 incorporates the following changes: (1) It allows you to carry out
slice-based set and get operations on a BitVector object. The two new methods for
these operations are named C<get_slice()> and C<set_slice()>. (2) It includes a new
method named C<min_canonical()> that returns a circularly rotated version of a
BitVector with the least integer value. For obvious reasons, this version would also
have the largest number of leading zeros. And (3) It fixes a bug in the
implementation of the method C<gf_divide_by_modulus()>.
Version 1.25 incorporates bugfix for the case when you try to construct a bitvector
of a specified length from a large integer that is supplied to the module constructor
as a C<Math::BigInt> object.
Version 1.24 includes in the C<Makefile.PL> file the minimum version restriction on
the C<List::Util> module that is imported.
Version 1.23 mentions the required modules in the C<Makefile.PL> file but with no
minimum version numbers. Additionally, the documentation associated with the methods
was significantly upgraded in this version.
Version 1.22 removes the Perl version restriction from the module and the
lib/Algorithm/BitVector.pm view on Meta::CPAN
bitvectors. This was done to keep the usage of this operator the same as in the
Python version of this module.
By virtue of how the operators are overloaded, you can make the calls listed in the
rest of this section. To illustrate these calls, I will use the following two bit
vectors:
$bv1 = Algorithm::BitVector->new( bitstring => "111000" );
$bv2 = Algorithm::BitVector->new( bitstring => "000101000" );
These two bitvectors are intentionally of different lengths to illustrate what role
the size differences play in how the various operators work.
=over 4
=item B<Concatenating two bitvectors:>
$bv3 = $bv1 + $bv2; # 111000000101000
The concatenation of two bitvectors is returned as a new bitvector. This is made
possible by the overload definition for the C<+> operator.
lib/Algorithm/BitVector.pm view on Meta::CPAN
$bv3 = ~ $bv1;
print $bv3; # 000111
This is made possible by the overload definition for the C<~> operator. The original
bitvector on which this unary operator is invoked remains unchanged.
=item B<Taking logical OR of two bitvectors:>
$bv3 = $bv1 | $bv2; # 000111000
When two bitvectors are of unequal length (as is the case here), the shorter vector
is zero-padded on the left to equalize their lengths before the application of the
logical operation. If this auto-padding property is not something you want, you
should check the lengths of the argument bitvectors in your own script before
invoking this operator. The result of the logical OR operation is returned as a new
bitvector. The two operand bitvectors remain unchanged.
=item B<Taking logical AND of two bitvectors:>
$bv3 = $bv1 & $bv2; # 000101000
When two bitvectors are of unequal length (as is the case here), the shorter vector
is zero-padded on the left to equalize their lengths before the application of the
logical operation. If this auto-padding property is not something you want, you
should check the lengths of the argument bitvectors in your own script before
invoking this operator. The result of the logical AND operation is returned as a new
bitvector. The two operand bitvectors remain unchanged.
=item B<Taking logical XOR of two bitvectors:>
$bv3 = $bv1 ^ $bv2; # 000010000
When two bitvectors are of unequal length (as is the case here), the shorter vector
is zero-padded on the left to equalize their lengths before the application of the
logical operation. If this auto-padding property is not something you want, you
should check the lengths of the argument bitvectors in your own script before
invoking this operator. The result of the logical XOR operation is returned as a new
bitvector. The two operand bitvectors remain unchanged.
=item B<Comparing bitvectors:>
$bv1 < $bv2 ? print "yes\n" : print "no\n"; # no
$bv1 > $bv2 ? print "yes\n" : print "no\n"; # yes
lib/Algorithm/BitVector.pm view on Meta::CPAN
decrypts the encrypted bit stream. Since what comes out at the decryption end must
be the original text string, it would make sense to invoke this method to recover the
original text.
=back
=head3 get_bitvector_in_hex()
=over 4
Assuming that length of your bitvector is a multiple of 4, this methods returns a
hex representation of the bit pattern:
$bv = Algorithm::BitVector->new(bitstring => "0110100001100101011011000110110001101111");
print $bv->get_bitvector_in_hex(); # 68656c6c6f
The hex representation is returned in the form if a string of hex characters. This
method throws an exception if the size of the bitvector is not a multiple of 4.
=back
lib/Algorithm/BitVector.pm view on Meta::CPAN
This method returns a product of two bit patterns in the Galois Field C<GF(2)> field.
That is, given any two polynomials with their coefficients drawn from the 0 and 1
values in C<GF(2)>, this method returns the product polynomial.
$a = Algorithm::BitVector->new( bitstring => '0110001' );
$b = Algorithm::BitVector->new( bitstring => '0110' );
print $a->gf_multiply($b); #00010100110
As you would expect, in general, the bit pattern returned by this method will be
longer than the lengths of the two operand bitvectors. The result returned by the
method is in the form of a bitvector.
=back
=head3 gf_multiply_modular()
=over 4
This method carries out modular multiplication in the Galois Field C<GF(2^n)>. You
must supply it the bitvector for the modulus polynomial and the value of C<n>.
lib/Algorithm/BitVector.pm view on Meta::CPAN
Hamming distance is commonly used to measure dissimilarity between two bitvectors of
the same size.
$bv1 = Algorithm::BitVector->new( bitstring => '11111111' );
$bv2 = Algorithm::BitVector->new( bitstring => '00101011' );
print $bv1->hamming_distance( $bv2 ); # 4
This distance returns the number of bit positions in which two the bit patterns
differ. The method throws an exception if the two bitvectors are not of the same
length. The value returned is an integer.
=back
=head3 int_value()
=over 4
You can find the integer value of a bitvector by
$bv = Algorithm::BitVector->new( intVal => 5678 );
lib/Algorithm/BitVector.pm view on Meta::CPAN
pointed to by C<$bv1> and C<$bv2>:
$bv1 = Algorithm::BitVector->new( bitstring => '11111111' );
$bv2 = Algorithm::BitVector->new( bitstring => '10101011' );
print $bv1->jaccard_similarity( $bv2 ); # 0.675
The value returned by the method is a floating point number between 0 and 1.
=back
=head3 length()
=over 4
This method returns the total number of bits in a bitvector:
$bv = Algorithm::BitVector->new( intVal => 5678 );
print $bv; # 1011000101110
print $bv->length(); # 13
Note that what C<length()> returns is the total size of a bitvector, including any
leading zeros.
=back
=head3 min_canonical()
=over 4
This method returns the min-int-value circularly rotated version of a BitVector. I refer
to this form of a BitVector as its "min canonical form".
( run in 0.265 second using v1.01-cache-2.11-cpan-65fba6d93b7 )