Algorithm-BitVector
view release on metacpan or search on metacpan
lib/Algorithm/BitVector.pm view on Meta::CPAN
# incorporated in it:
return sub {
if ($self->[1] >= $bitvec->{size}) {
delete $bitvec->{_iter_called};
return;
}
my $bit = $bitvec->get_bit($self->[1]);
$self->[1] = $self->[1] + 1;
return $bit;
}
}
}
# for the overloading of the numification operator:
sub _int {
my $self = shift;
return $self->int_value();
}
## Divides an even-sized bitvector into two and returns the two halves as a
## list of two bitvectors.
sub divide_into_two {
my $self = shift;
die "Abort: The divide_into_two() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
die "The bitvector to be divided must have even number of bits: $!"
if $self->{size} % 2;
my @outlist1 = ();
foreach my $i (0..$self->{size} / 2 - 1) {
push @outlist1, $self->get_bit($i);
}
my @outlist2 = ();
foreach my $i ( ($self->{size} / 2) .. ($self->{size} - 1) ) {
push @outlist2, $self->get_bit($i);
}
return Algorithm::BitVector->new( bitlist => \@outlist1 ),
Algorithm::BitVector->new( bitlist => \@outlist2 );
}
## Permute a bitvector according to the indices shown in the second argument list.
## Return the permuted bitvector as a new bitvector.
sub permute {
my $self = shift;
die "Abort: The permute() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
my $permute_list = shift;
die "Bad permutation index in your permutation list"
if max(@$permute_list) > $self->{size} - 1;
my @outlist = ();
foreach my $index (@$permute_list) {
push @outlist, $self->get_bit($index);
}
return Algorithm::BitVector->new( bitlist => \@outlist );
}
## Unpermute the bitvector according to the permutation list supplied as the
## second argument. If you first permute a bitvector by using permute() and
## then unpermute() it using the same permutation list, you will get back the
## original bitvector.
sub unpermute {
my $self = shift;
die "Abort: The unpermute() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
my $permute_list = shift;
die "Bad permutation index in your permutation list: $!"
if max(@$permute_list) > $self->{size} - 1;
die "Size of the permute list for unpermuting not consistent with the size of the bet vector:$!"
unless $self->{size} == @$permute_list;
my $out_bv = Algorithm::BitVector->new( size => $self->{size} );
foreach my $i (0..@$permute_list-1) {
$out_bv->set_bit( $permute_list->[$i], $self->get_bit($i) );
}
return $out_bv;
}
## 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;
}
}
## For closing a file object that was used for reading the bits into one or more
## BitVector objects.
sub close_file_handle {
my $self = shift;
die "Abort: The close_file_handle() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
die "No open file currently associated with the file handle: $!"
unless $self->{FILEIN};
close $self->{FILEIN};
}
## Return the integer value of a bitvector. If the original integer from which the
## bitvector was constructed is a Math::BigInt object, then return the string
## representation of the integer value.
sub int_value {
my $self = shift;
die "Abort: The int() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
my $int_value;
if (defined($self->{intVal}) && (ref($self->{intVal}) eq 'Math::BigInt')) {
$int_value = $self->{intVal}->bstr();
} else {
$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) {
# $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])};
lib/Algorithm/BitVector.pm view on Meta::CPAN
'<>' => '_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
of bit fields than non-circular shifts. You can still carry out non-circular shifts
by calling the methods C<shift_left()> and C<shift_right()> as illustrated elsewhere
in this documentation.
Another B<important> thing to bear in mind is the overloading of the `C<+>' operator.
It is B<NOT> addition. On the other hand, it is a concatenation of the two operand
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.
Note that the following also works:
print $bv1 . "hello"; # 111000hello
In this case, Perl implicitly converts the left operand of the `.' operator into a
string (which is made possible by the overloading for the stringification operator in
this module) and then returns the result as a string.
=item B<Creating the string representation of a bitvector:>
print "$bv1"; # 111000
This is made possible for the overload definition for the C<""> operator.
=item B<Converting a bitvector to its integer value:>
print int($bv1); # 56
This is made possible by the overload definition for the C<0+> operator.
=item B<Inverting a bitvector>
$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
$bv1 <= $bv2 ? print "yes\n" : print "no\n"; # no
$bv1 >= $bv2 ? print "yes\n" : print "no\n"; # yes
$bv1 == $bv2 ? print "yes\n" : print "no\n"; # no
$bv1 != $bv2 ? print "yes\n" : print "no\n"; # yes
The overload definitions for all these operators are autogenerated from the overload
definition for the 3-way numerical comparison operator 'C<< <=> >>'. B<The
bitvectors are compared on the basis of their integer values.> That is, C<$bv1> is
less than C<$bv2> if C<int($bv1)> is less than C<int($bv2)>.
=item B<In-place circular shifting:>
$n = 3;
lib/Algorithm/BitVector.pm view on Meta::CPAN
=head3 gen_random_bits()
=over 4
$bv = Algorithm::BitVector->new( intVal => 0 );
$bv = $bv->gen_random_bits(16); # 1100111001010101
The call to C<gen_random_bits()> returns a bitvector whose bits are randomly
generated. The number of bits in the returned bitvector equals the argument integer.
=back
=head3 get_bit()
=over 4
This method gives you array-like access to the individual bits of a bitvector.
$bv = Algorithm::BitVector->new( bitstring => '10111' );
print $bv->get_bit(0); # 1 (the first bit)
print $bv->get_bit(1); # 0
print $bv->get_bit(4); # 1 (the last bit)
Negative values for the index scan a bitvector from right to left, with the C<-1>
index standing for the last (meaning the right-most) bit in the vector:
print $bv->get_bit(-1); # 1 (the last bit)
print $bv->get_bit(-2); # 1
print $bv->get_bit(-5); # 1 (the first bit)
The C<get_bit()> can also return a slice of a bitvector if the argument to the
method is an anonymous array of the index range you desire, as in the second
statement below:
$bv = Algorithm::BitVector->new( bitstring => "10111011");
my $arr = $bv->get_bit( [3..7] );
print "@$arr\n"; # 1 1 0 1 1
In this example, we want C<get_bit()> to return all bits at positions indexed 3
through 7, both ends inclusive. Note that the slice is returned as an array of bits.
=back
=head3 get_bitvector_in_ascii()
=over 4
$bv = Algorithm::BitVector->new( textstring => "hello" );
print "$bv\n"; # 0110100001100101011011000110110001101111
print $bv->get_bitvector_in_ascrii(); # hello
The method returns a string of ASCII characters by converting successive 8-bit slices
of the bitvector into an ASCII character. It throws an exception if the size of the
bit pattern is not a multiple of 8. Calling this method to create a text-based print
representation of a bit vector makes sense only if you don't expect to see any
unprintable characters in the successive 8-bit slices of the bitvector. Let's say
you have created a bitvector from a text string using the appropriate constructor
call. Subsequently, you encrypted this text string. Next, you or someone else
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
=head3 get_slice()
=over 4
You can use this method to get a slice of a BitVector that is within a specified range.
You can specify the index range with the usual range operator in Perl. If the index
range is, say, '5..11', the method will return all bits at index values 5 through 10.
my $bv9 = Algorithm::BitVector->new( intVal => 63437, size => 16 );
print "BitVector for testing get_slice(): $bv9\n"; # 1111011111001101
my $slice_bv = $bv9->get_slice( [5..11] );
print "slice BitVector for index values 5 through 10: $slice_bv\n"; # 111110
Note that the method returns the slice in the form of a BitVector object.
=back
=head3 gf_divide_by_modulus()
=over 4
This method is for modular division in the Galois Field C<GF(2^n)>. You must specify
the modulus polynomial through a bit pattern and also the value of the integer C<n>:
$mod = Algorithm::BitVector->new( bitstring => '100011011' ); # AES modulus
$n = 8;
$a = Algorithm::BitVector->new( bitstring => '11100010110001' );
($quotient, $remainder) = $a->gf_divide_by_modulus($mod, $n);
print "$quotient\n"; # 00000000111010
print "$remainder\n"; # 10001111
What this example illustrates is dividing the bitvector C<$a> by the modulus bit
vector C<$mod>. For a more general division of one bitvector C<$a> by another bit
vector C<$b>, you would carry out a multiplication of C<$a> by the MI of C<$b>, where
MI stands for "multiplicative inverse" as returned by a call to the method
C<gf_MI()>. A call to C<gf_divide_by_modulus()> returns two bitvectors, one for the
quotient and the other for the remainder.
=back
=head3 gf_MI()
( run in 1.221 second using v1.01-cache-2.11-cpan-8f98c5d2c55 )