Algorithm-BitVector
view release on metacpan or search on metacpan
lib/Algorithm/BitVector.pm view on Meta::CPAN
} elsif (defined $self->{size}) {
die "When using the `size' option in the constructor call, you CANNOT use `filename', " .
"`bitlist', 'bitstring', `hexstring', or `textstring' options: $!"
if $self->{filename} or $self->{intVal} or $self->{bitlist}
or $self->{bitstring} or $self->{hexstring} or $self->{textstring};
my $bitstring = "0" x $self->{size};
my @bitlist_from_bitstring = split '', $bitstring;
$self->{bitlist} = \@bitlist_from_bitstring;
} elsif ($self->{bitlist}) {
die "When using the `bitlist' 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->{bitstring} or $self->{hexstring} or $self->{textstring};
$self->{size} = scalar @{$self->{bitlist}};
} elsif (defined $self->{bitstring}) {
die "When using the `bitstring' 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->{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;
$self->{bitlist} = undef;
return $self;
}
## Set the bit at the designated position to the value shown
sub set_bit {
my $self = shift;
my $posn = shift;
my $val = shift;
croak "incorrect value for a bit" unless $val =~ /\d/ && ($val == 0 or $val == 1);
die "index range error" if ($posn >= $self->{size}) or ($posn < - $self->{size});
$posn = $self->{size} + $posn if $posn < 0;
my $block_index = int($posn / 16);
my $shift = $posn & 0xF;
my $cv = $self->{_vector}->[$block_index];
if ( ( ( $cv >> $shift ) & 1 ) != $val) {
$self->{_vector}->[$block_index] = $cv ^ (1 << $shift);
}
}
## Get the bit from the designated position. This method can also return a slice of a
## bitvector. HOWEVER, NOTE THAT THE SLICE IS RETURNED AS A LIST OF THE BITS IN THE
## INDEX RANGE YOU SPECIFIED. You can either easily convert the list of bits returned
## into a bitvector in your own code or, starting with Version 1.26, you can call the
## get_slice() method.
sub get_bit {
my $self = shift;
my $pos = shift;
unless (ref($pos) eq "ARRAY") {
die "index range error" if ($pos >= $self->{size}) or ($pos < - $self->{size});
$pos = $self->{size} + $pos if $pos < 0;
return ( $self->{_vector}->[int($pos/16)] >> ($pos&15) ) & 1;
}
# my @slice = map $self->get_bit($_), (@$pos)[0..@$pos-1];
my @slice = map $self->get_bit($_), (@$pos)[0..@$pos-2];
return \@slice;
}
## Get the slice of bits from the bitvector corresponding to the index range specified
## by the argument. The slice is returned as an instance of Algorithm::BitVector
sub get_slice {
my $self = shift;
my $index_range = shift;
my $slice_bv = Algorithm::BitVector->new( size => @$index_range - 1 );
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;
}
## Overloading of the `+' operator. Concatenate the argument bitvectors. Return the
## concatenated bitvector as a new BitVector instance.
sub _join {
my ($bv1, $bv2) = @_;
croak "Abort: The concatenation operator invoked with either undefined " .
"or wrong types of operands: $!"
unless UNIVERSAL::isa( $bv1, 'Algorithm::BitVector') and
UNIVERSAL::isa( $bv2, 'Algorithm::BitVector');
my $allbits = $bv1->_str() . $bv2->_str();
return Algorithm::BitVector->new( bitstring => $allbits );
}
sub _compare {
my ($bv1, $bv2) = @_;
croak "Abort: The comparison operator invoked with either undefined " .
"or wrong types of operands: $!"
unless UNIVERSAL::isa( $bv1, 'Algorithm::BitVector') and
UNIVERSAL::isa( $bv2, 'Algorithm::BitVector');
my $bigint1 = Math::BigInt->from_bin( "$bv1" );
my $bigint2 = Math::BigInt->from_bin( "$bv2" );
return $bigint1->bcmp($bigint2);
}
sub deep_copy {
lib/Algorithm/BitVector.pm view on Meta::CPAN
## 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) {
# $ascii .= chr oct "0b". join '', @{$self->get_bit([$i..$i+7])};
$ascii .= chr oct "0b". join '', @{$self->get_bit([$i..$i+8])};
}
return $ascii;
}
# 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 = '';
for (my $i=0; $i < $self->{size}; $i += 4) {
# $hex .= sprintf "%x", oct "0b". join '', @{$self->get_bit([$i..$i+3])};
$hex .= sprintf "%x", oct "0b". join '', @{$self->get_bit([$i..$i+4])};
}
return $hex;
}
# for backward compatibility:
sub get_hex_string_from_bitvector {
my $self = shift;
$self->get_bitvector_in_hex(@_);
}
## Read blocksize bits from a disk file and return a BitVector object containing
## the bits. If the file contains fewer bits than blocksize, construct the
## BitVector object from however many bits there are in the file. If the file
## contains zero bits, return a BitVector object of size attribute set to 0.
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;
my $n = shift;
die "Circular shift of an empty vector makes no sense" unless $self->{size};
return $self >> abs($n) if $n < 0;
foreach my $i (0..$n-1) {
$self->_circular_rotate_left_by_one();
}
return $self;
}
## For an in-place right circular shift by n bit positions
sub _rshift {
my $self = shift;
my $n = shift;
die "Circular shift of an empty vector makes no sense" unless $self->{size};
return $self << abs($n) if $n < 0;
foreach my $i (0..$n-1) {
$self->_circular_rotate_right_by_one();
}
return $self;
}
## For a one-bit in-place left circular shift
sub _circular_rotate_left_by_one {
my $self = shift;
my $max_index = int( ($self->{size} - 1) / 16 );
my $left_most_bit = $self->{_vector}->[0] & 1;
$self->{_vector}->[0] = $self->{_vector}->[0] >> 1;
foreach my $i (1 .. $max_index) {
my $left_bit = $self->{_vector}->[$i] & 1;
$self->{_vector}->[$i] = $self->{_vector}->[$i] >> 1;
$self->{_vector}->[$i-1] |= $left_bit << 15;
}
$self->set_bit($self->{size} - 1, $left_most_bit);
}
## For a one-bit in-place right circular shift
sub _circular_rotate_right_by_one {
my $self = shift;
my $max_index = int( ($self->{size} - 1) / 16 );
my $right_most_bit = $self->get_bit( $self->{size} - 1);
$self->{_vector}->[$max_index] &= ~0x8000;
$self->{_vector}->[$max_index] = $self->{_vector}->[$max_index] << 1;
for (my $i=$max_index-1; $i > -1; $i -= 1) {
my $right_bit = $self->{_vector}->[$i] & 0x8000;
$self->{_vector}->[$i] &= ~0x8000;
$self->{_vector}->[$i] = $self->{_vector}->[$i] << 1;
$self->{_vector}->[$i+1] |= $right_bit >> 15;
lib/Algorithm/BitVector.pm view on Meta::CPAN
$bv = Algorithm::BitVector->new( size => 7 );
print "$bv\n"; # 0000000
# Constructing a bitvector whose integer value is specified:
$bv = Algorithm::BitVector->new( intVal => 123456 );
print "$bv\n"; # 11110001001000000
print int($bv); # 123456
# Constructing a bitvector from a very large integer:
use Math::BigInt;
$x = Math::BigInt->new('12345678901234567890123456789012345678901234567890');
$bv = Algorithm::BitVector->new( intVal => $x );
# Constructing a bitvector from a given bit string:
$bv = Algorithm::BitVector->new( bitstring => '00110011' );
# Constructing a bitvector from an ASCII text string:
$bv = Algorithm::BitVector->new( textstring => "hello\njello" );
# Constructing a bitvector from a hex string:
$bv = Algorithm::BitVector->new( hexstring => "68656c6c6f" );
# Constructing a bitvector from a bit list passed as an anonymous array:
$bv = Algorithm::BitVector->new( bitlist => [1, 1, 0, 1] );
# Constructing a bitvector from the contents of a disk file:
$bv = Algorithm::BitVector->new( filename => 'testinput.txt' );
$bv1 = $bv->read_bits_from_file(64); # bitvector from the first 64 bits
# and so on
=head1 CHANGES
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
C<Makefile.PL> files and the C<PREREQ_PM> restrictions from the C<Makefile.PL> file.
Version 1.21 fixes a bug in the code for the Miller-Rabin primality test function
C<test_for_primality()>. This version also places a hard limit on the size of the
integers that are allowed to be tested for primality.
Version 1.2 fixes an important bug in creating bitvectors from the contents of a disk
file. This version also includes corrections for some of the documentation errors
discovered.
Version 1.1 incorporates additional type checking on the operands for the overloaded
operators. Also fixed some minor documentation formatting issues.
=head1 DESCRIPTION
My main motivation for creating this module was to provide the students at Purdue and
elsewhere with a Perl class whose API is the same as that of my Python based
C<BitVector> module that appears to have become popular for prototyping algorithms
for cryptography and hash functions.
This module stores the bits of a bitvector in 16-bit unsigned shorts. As you can see
in the constructor code for C<new()>, after resolving the arguments with which the
constructor is called, the very first thing the constructor does is to figure out how
many of those 2-byte shorts it needs for the bits. That does not imply that the size
of a bit array that is stored in a bitvector must be a multiple of 16. B<A bitvector
can be of any size whatsoever.> The C<Algorithm::BitVector> class keeps track of the
number of bits through its C<size> instance variable.
Note that, except for one case, the constructor must be called with a single keyword
argument, which determines how the bitvector will be constructed. The single
exception to this rule is for the keyword argument C<intVal> which you would normally
use for constructing a bitvector from an integer. The additional option you can
supply with C<intVal> is C<size>. When both C<intVal> and C<size> are specified in a
constructor call, you get a bitvector of the specified size provided the value
supplied for C<size> is larger than what it takes to accommodate the bits for the
C<intVal> integer.
In addition to constructing bitvectors from integers, this module can also construct
bitvectors from bit strings, from ASCII text strings, from hex strings, from a list
of bits, and from the contents of a file. With regards to constructing bitvectors
from integers, the module can construct very large bitvectors from very large
integers stored as C<Math::BigInt> objects.
=head1 OVERLOADED OPERATORS
The following C<use overload> declaration in the module gives the list of the
overloaded operators. Since C<fallback> is set to 1, several other operators become
overloaded by autogeneration from those shown below. For example, overloading of the
3-way numerical comparison operator C<< <=> >> automatically overloads the C<< < >>,
C<< <= >>, C<< > >>, C<< >= >>, C<< == >>, and C<< != >> operators.
use overload '+' => '_add',
'""' => '_str',
'0+' => '_int',
'~' => '_invert',
'|' => '_or',
'&' => '_and',
'^' => '_xor',
'<=>' => '_compare',
'<<' => '_lshift',
'>>' => '_rshift',
'<>' => '_iter',
'fallback' => 1;
It is B<important> to remember that the overloadings for the `C<<< << >>>' and `C<<<
>> >>>' operators are for B<circular> left and right shifts (their usual meaning as
bitwise operators is for non-circular shifts). This was done because the
applications for which this module is intended is more likely to use circular shifts
lib/Algorithm/BitVector.pm view on Meta::CPAN
BitVectorDemo.pl
In case there is any doubt about how exactly to invoke a method or how to use an
operator, please look at the usage in this script.
=head1 EXPORT
None by design.
=head1 BUGS
Please notify the author if you encounter any bugs. When sending email, please place
the string 'BitVector' in the subject line.
=head1 INSTALLATION
Download the archive from CPAN in any directory of your choice. Unpack the archive
with a command that on a Linux machine would look like:
tar zxvf Algorithm-BitVector-1.26.tar.gz
This will create an installation directory for you whose name will be
C<Algorithm-BitVector-1.26>. Enter this directory and execute the following commands
for a standard install of the module if you have root privileges:
perl Makefile.PL
make
make test
sudo make install
If you do not have root privileges, you can carry out a non-standard install the
module in any directory of your choice by:
perl Makefile.PL prefix=/some/other/directory/
make
make test
make install
With a non-standard install, you may also have to set your PERL5LIB environment
variable so that this module can find the required other modules. How you do that
would depend on what platform you are working on. In order to install this module in
a Linux machine on which I use tcsh for the shell, I set the PERL5LIB environment
variable by
setenv PERL5LIB /some/other/directory/lib64/perl5/:/some/other/directory/share/perl5/
If I used bash, I'd need to declare:
export PERL5LIB=/some/other/directory/lib64/perl5/:/some/other/directory/share/perl5/
=head1 THANKS
The bug in the primality test function, whose fix resulted in Version 1.21, was
reported by Dana Jacobsen in a bug report filed at C<rt.cpan.org>. Thanks Dana!
The restriction on the Perl version was removed on Slaven Rezic's recommendation. He
says the module runs fine with Perl 5.8.9. Thanks Slaven!
Austin Nobis reported a documentation error in Version 1.24 which was fixed in Version
1.25. Thanks Austin!
=head1 AUTHOR
The author, Avinash Kak, recently finished a 17-years long "Objects Trilogy Project"
with the publication of the book "Designing with Objects" by John-Wiley. If
interested, visit his web page at Purdue to find out what this project was all
about. You might like "Designing with Objects" especially if you enjoyed reading
Harry Potter as a kid (or even as an adult, for that matter).
For all issues related to this module, contact the author at kak@purdue.edu
If you send email, please place the string "BitVector" in your subject line to get
past the author's spam filter.
=head1 COPYRIGHT
This library is free software; you can redistribute it and/or modify it under the
same terms as Perl itself.
Copyright 2018 Avinash Kak
=cut
( run in 1.556 second using v1.01-cache-2.11-cpan-6b5c3043376 )