Scalar::Vec::Util - Utility routines for vec strings.

Scalar-Vec-Util documentation Contained in the Scalar-Vec-Util distribution.

Index

Code Index:

NAME

Top

Scalar::Vec::Util - Utility routines for vec strings.

VERSION

Top

Version 0.06

SYNOPSIS

Top

    use Scalar::Vec::Util qw/vfill vcopy veq/;

    my $s;
    vfill $s, 0, 100, 1; # Fill with 100 bits 1 starting at 0.
    my $t;
    vcopy $s, 20, $t, 10, 30; # Copy 30 bits from $s, starting at 20,
                              #                to $t, starting at 10.
    vcopy $t, 10, $t, 20, 30; # Overalapping areas DWIM.
    if (veq $t, 10, $t, 20, 30) { ... } # Yes, they are equal now.

DESCRIPTION

Top

A set of utilities to manipulate bits in vec strings. Highly optimized XS routines are used when available, but straightforward pure perl replacements are also provided for platforms without a C compiler.

This module doesn't reimplement bit vectors. It can be used on the very same scalars that vec builds, or actually on any Perl string (SVt_PV).

CONSTANTS

Top

SVU_PP

True when pure perl fallbacks are used instead of XS functions.

SVU_SIZE

Size in bits of the unit used for moves. The higher this value is, the faster the XS functions are. It's usually CHAR_BIT * $Config{alignbytes}, except on non-little-endian architectures where it currently falls back to CHAR_BIT (e.g. SPARC).

FUNCTIONS

Top

vfill $vec, $start, $length, $bit

Starting at $start in $vec, fills $length bits with $bit. Grows $vec if necessary.

vcopy $from => $from_start, $to => $to_start, $length

Copies $length bits starting at $from_start in $from to $to_start in $to. If $from_start + $length is too long for $from, zeros are copied past $length. Grows $to if necessary. Doesn't need to allocate any extra memory.

vshift $v, $start, $length => $bits [, $insert ]

In the area starting at $start and of length $length in $v, shift bits abs $bits positions left if $bits > 0 and right otherwise. If $insert is defined, also fills the resulting gap with ones if $insert is true and zeros if it's false. Bits outside of the specified area are left untouched. Doesn't need to allocate any extra memory.

vrot $v, $start, $length, $bits

In the area starting at $start and of length $length in $v, rotates bits abs $bits positions left if $bits > 0 and right otherwise. Bits outside of the specified area are left untouched. Currently allocates an extra buffer of size O($bits).

veq $v1 => $v1_start, $v2 => $v2_start, $length

Returns true if the $length bits starting at $v1_start in $v1 and $v2_start in $v2 are equal, and false otherwise. If needed, $length is decreased to fit inside $v1 and $v2 boundaries.

EXPORT

Top

The functions vfill, vcopy, vshift, vrot and veq are only exported on request. All of them are exported by the tags ':funcs' and ':all'.

The constants SVU_PP and SVU_SIZE are also only exported on request. They are all exported by the tags ':consts' and ':all'.

BENCHMARKS

Top

The following timings were obtained by running the samples/bench.pl script. The _pp entries are the pure Perl versions, whereas _bv are Bit::Vector versions.

This is for perl 5.8.8 on a Core 2 Duo 2.66GHz machine (unit is 64 bits).
    Filling bits at a given position :
                  Rate vfill_pp vfill_bv    vfill
    vfill_pp    80.3/s       --    -100%    -100%
    vfill_bv 1053399/s 1312401%       --     -11%
    vfill    1180792/s 1471129%      12%       --

    Copying bits from a bit vector to a different one :
                 Rate vcopy_pp vcopy_bv    vcopy
    vcopy_pp    112/s       --    -100%    -100%
    vcopy_bv  62599/s   55622%       --     -89%
    vcopy    558491/s  497036%     792%       --

    Moving bits in the same bit vector from a given position to a different one :
                 Rate vmove_pp vmove_bv    vmove
    vmove_pp   64.8/s       --    -100%    -100%
    vmove_bv  64742/s   99751%       --     -88%
    vmove    547980/s  845043%     746%       --

    Testing bit equality from different positions of different bit vectors :
               Rate  veq_pp  veq_bv     veq
    veq_pp   92.7/s      --   -100%   -100%
    veq_bv  32777/s  35241%      --    -94%
    veq    505828/s 545300%   1443%      --
This is for perl 5.10.0 on a Pentium 4 3.0GHz (unit is 32 bits).
                 Rate vfill_pp vfill_bv    vfill
    vfill_pp    185/s       --    -100%    -100%
    vfill_bv 407979/s  220068%       --     -16%
    vfill    486022/s  262184%      19%       --

                 Rate vcopy_pp vcopy_bv    vcopy
    vcopy_pp   61.5/s       --    -100%    -100%
    vcopy_bv  32548/s   52853%       --     -83%
    vcopy    187360/s  304724%     476%       --

                 Rate vmove_pp vmove_bv    vmove
    vmove_pp   63.1/s       --    -100%    -100%
    vmove_bv  32829/s   51933%       --     -83%
    vmove    188572/s  298787%     474%       --

               Rate  veq_pp  veq_bv     veq
    veq_pp   34.2/s      --   -100%   -100%
    veq_bv  17518/s  51190%      --    -91%
    veq    192181/s 562591%    997%      --
This is for perl 5.10.0 on an UltraSPARC-IIi (unit is 8 bits).
                Rate vfill_pp    vfill vfill_bv
    vfill_pp  4.23/s       --    -100%    -100%
    vfill    30039/s  709283%       --     -17%
    vfill_bv 36022/s  850568%      20%       --

                Rate vcopy_pp vcopy_bv    vcopy
    vcopy_pp  2.74/s       --    -100%    -100%
    vcopy_bv  8146/s  297694%       --     -60%
    vcopy    20266/s  740740%     149%       --

                Rate vmove_pp vmove_bv    vmove
    vmove_pp  2.66/s       --    -100%    -100%
    vmove_bv  8274/s  311196%       --     -59%
    vmove    20287/s  763190%     145%       --

              Rate  veq_pp  veq_bv     veq
    veq_pp  7.33/s      --   -100%   -100%
    veq_bv  2499/s  33978%      --    -87%
    veq    19675/s 268193%    687%      --

CAVEATS

Top

Please report architectures where we can't use the alignment as the move unit. I'll add exceptions for them.

DEPENDENCIES

Top

Carp, Exporter (core modules since perl 5), XSLoader (since perl 5.006).

SEE ALSO

Top

Bit::Vector gives a complete reimplementation of bit vectors.

AUTHOR

Top

Vincent Pit, <perl at profvince.com>, http://www.profvince.com.

You can contact me by mail or on irc.perl.org (vincent).

BUGS

Top

Please report any bugs or feature requests to bug-scalar-vec-util at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Scalar-Vec-Util. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

SUPPORT

Top

You can find documentation for this module with the perldoc command.

    perldoc Scalar::Vec::Util

Tests code coverage report is available at http://www.profvince.com/perl/cover/Scalar-Vec-Util.

COPYRIGHT & LICENSE

Top

Copyright 2008-2009 Vincent Pit, all rights reserved.

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

Scalar-Vec-Util documentation Contained in the Scalar-Vec-Util distribution. 
package Scalar::Vec::Util;

use strict;
use warnings;

use Carp qw/croak/;


our $VERSION;
BEGIN {
 $VERSION = '0.06';
 eval {
  require XSLoader;
  XSLoader::load(__PACKAGE__, $VERSION);
  1;
 } or do {
  *SVU_PP   = sub () { 1 };
  *SVU_SIZE = sub () { 1 };
  *vfill    = *vfill_pp;
  *vcopy    = *vcopy_pp;
  *veq      = *veq_pp;
 }
}


sub vfill_pp ($$$$) {
 my ($s, $l, $x) = @_[1 .. 3];
 return unless $l;
 croak 'Invalid negative offset' if $s < 0;
 croak 'Invalid negative length' if $l < 0;
 $x = ~0 if $x;
 my $SIZE = 32;
 my $t = int($s / $SIZE) + 1;
 my $u = int(($s + $l) / $SIZE);
 if ($SIZE * $t < $s + $l) { # implies $t <= $u
  vec($_[0], $_, 1)     = $x for $s .. $SIZE * $t - 1;
  vec($_[0], $_, $SIZE) = $x for $t .. $u - 1;
  vec($_[0], $_, 1)     = $x for $SIZE * $u .. $s + $l - 1;
 } else {
  vec($_[0], $_, 1) = $x for $s .. $s + $l - 1;
 }
}


sub vcopy_pp ($$$$$) {
 my ($fs, $ts, $l) = @_[1, 3, 4];
 return unless $l;
 croak 'Invalid negative offset' if $fs < 0 or $ts < 0;
 croak 'Invalid negative length' if $l  < 0;
 my $step = $ts - $fs;
 if ($step <= 0) { 
  vec($_[2], $_ + $step, 1) = vec($_[0], $_, 1) for $fs .. $fs + $l - 1;
 } else { # There's a risk of overwriting if $_[0] and $_[2] are the same SV.
  vec($_[2], $_ + $step, 1) = vec($_[0], $_, 1) for reverse $fs .. $fs + $l - 1;
 }
}


sub vshift ($$$$;$) {
 my ($start, $length, $bits, $insert) = @_[1 .. 4];
 return unless $length and $bits;
 croak 'Invalid negative offset' if $start  < 0;
 croak 'Invalid negative length' if $length < 0;
 my $left = 1;
 if ($bits < 0) {
  $left = 0;
  $bits = -$bits;
 }
 if ($bits < $length) {
  $length -= $bits;
  if ($left) {
   vcopy($_[0], $start, $_[0], $start + $bits, $length);
   vfill($_[0], $start, $bits, $insert) if defined $insert;
  } else {
   vcopy($_[0], $start + $bits, $_[0], $start, $length);
   vfill($_[0], $start + $length, $bits, $insert) if defined $insert;
  }
 } else {
  vfill($_[0], $start, $length, $insert) if defined $insert;
 }
}


sub vrot ($$$$) {
 my ($start, $length, $bits) = @_[1 .. 3];
 return unless $length and $bits;
 croak 'Invalid negative offset' if $start  < 0;
 croak 'Invalid negative length' if $length < 0;
 my $left = 1;
 if ($bits < 0) {
  $left = 0;
  $bits = -$bits;
 }
 $bits %= $length;
 return unless $bits;
 $length -= $bits;
 my $buf = '';
 if ($left) {
  vcopy($_[0], $start + $length, $buf,  0,              $bits);
  vcopy($_[0], $start,           $_[0], $start + $bits, $length);
  vcopy($buf,  0,                $_[0], $start,         $bits);
 } else {
  vcopy($_[0], $start,           $buf,  0,                $bits);
  vcopy($_[0], $start + $bits,   $_[0], $start,           $length);
  vcopy($buf,  0,                $_[0], $start + $length, $bits);
 }
}


sub veq_pp ($$$$$) {
 my ($s1, $s2, $l) = @_[1, 3, 4];
 croak 'Invalid negative offset' if $s1 < 0 or $s2 < 0;
 croak 'Invalid negative length' if $l  < 0;
 my $i = 0;
 while ($i < $l) {
  return 0 if vec($_[0], $s1 + $i, 1) != vec($_[2], $s2 + $i, 1);
  ++$i;
 }
 return 1;
}


use base qw/Exporter/;

our @EXPORT         = ();
our %EXPORT_TAGS    = (
 'funcs'  => [ qw/vfill vcopy vshift vrot veq/ ],
 'consts' => [ qw/SVU_PP SVU_SIZE/ ]
);
our @EXPORT_OK      = map { @$_ } values %EXPORT_TAGS;
$EXPORT_TAGS{'all'} = [ @EXPORT_OK ];


1; # End of Scalar::Vec::Util