README

   1 NAME
   2     Scalar::Vec::Util - Utility routines for vec strings.
   3
   4 VERSION
   5     Version 0.08
   6
   7 SYNOPSIS
   8         use Scalar::Vec::Util qw<vfill vcopy veq>;
   9
  10         my $s;
  11         vfill $s, 0, 100, 1; # Fill with 100 bits 1 starting at 0.
  12         my $t;
  13         vcopy $s, 20, $t, 10, 30; # Copy 30 bits from $s, starting at 20,
  14                                   #                to $t, starting at 10.
  15         vcopy $t, 10, $t, 20, 30; # Overlapping areas DWIM.
  16         if (veq $t, 10, $t, 20, 30) { ... } # Yes, they are equal now.
  17
  18 DESCRIPTION
  19     This module provides a set of utility routines that efficiently
  20     manipulate bits in vec strings. Highly optimized XS functions are used
  21     whenever possible, but straightforward pure Perl replacements are also
  22     available for platforms without a C compiler.
  23
  24     Note that this module does not aim at reimplementing bit vectors : all
  25     its functions can be used on any Perl string, just like "vec" in
  26     perlfunc.
  27
  28 CONSTANTS
  29   "SVU_PP"
  30     True when pure Perl fallbacks are used instead of XS functions.
  31
  32   "SVU_SIZE"
  33     The size (in bits) of the unit used for bit operations. The higher this
  34     value is, the faster the XS functions are. It is usually "CHAR_BIT *
  35     $Config{alignbytes}", except on non-little-endian architectures where it
  36     currently falls back to "CHAR_BIT" (e.g. SPARC).
  37
  38 FUNCTIONS
  39   "vfill"
  40         vfill $vec, $start, $length, $bit;
  41
  42     Starting at $start in $vec, fills $length bits with ones if $bit is true
  43     and with zeros if $bit is false.
  44
  45     $vec is upgraded to a string and extended if necessary. Bits that are
  46     outside of the specified area are left untouched.
  47
  48   "vcopy"
  49         vcopy $from => $from_start, $to => $to_start, $length;
  50
  51     Copies $length bits starting at $from_start in $from to $to_start in
  52     $to.
  53
  54     $from and $to are allowed to be the same scalar, and the given areas can
  55     rightfully overlap.
  56
  57     $from is upgraded to a string if it isn't one already. If "$from_start +
  58     $length" goes out of the bounds of $from, then the extra bits are
  59     treated as zeros. $to is upgraded to a string and extended if necessary.
  60     The content of $from is not modified, except when it is equal to $to.
  61     Bits that are outside of the specified area are left untouched.
  62
  63     This function does not need to allocate any extra memory.
  64
  65   "vshift"
  66         vshift $v, $start, $length => $bits, $insert;
  67
  68     In the area starting at $start and of length $length in $v, shift bits
  69     "abs $bits" positions left if "$bits > 0" and right otherwise.
  70
  71     When $insert is defined, the resulting gap is also filled with ones if
  72     $insert is true and with zeros if $insert is false.
  73
  74     $v is upgraded to a string if it isn't one already. If "$start +
  75     $length" goes out of the bounds of $v, then the extra bits are treated
  76     as zeros. Bits that are outside of the specified area are left
  77     untouched.
  78
  79     This function does not need to allocate any extra memory.
  80
  81   "vrot"
  82         vrot $v, $start, $length, $bits;
  83
  84     In the area starting at $start and of length $length in $v, rotates bits
  85     "abs $bits" positions left if "$bits > 0" and right otherwise.
  86
  87     $v is upgraded to a string if it isn't one already. If "$start +
  88     $length" goes out of the bounds of $v, then the extra bits are treated
  89     as zeros. Bits that are outside of the specified area are left
  90     untouched.
  91
  92     This function currently allocates an extra buffer of size "O($bits)".
  93
  94   "veq"
  95         veq $v1 => $v1_start, $v2 => $v2_start, $length;
  96
  97     Returns true if the $length bits starting at $v1_start in $v1 and
  98     $v2_start in $v2 are equal, and false otherwise.
  99
 100     $v1 and $v2 are upgraded to strings if they aren't already, but their
 101     contents are never modified. If "$v1_start + $length" (respectively
 102     "$v2_start + $length") goes out of the bounds of $v1 (respectively $v2),
 103     then the extra bits are treated as zeros.
 104
 105     This function does not need to allocate any extra memory.
 106
 107 EXPORT
 108     The functions "vfill", "vcopy", "vshift", "vrot" and "veq" are only
 109     exported on request. All of them are exported by the tags ':funcs' and
 110     ':all'.
 111
 112     The constants "SVU_PP" and "SVU_SIZE" are also only exported on request.
 113     They are all exported by the tags ':consts' and ':all'.
 114
 115 BENCHMARKS
 116     The following timings were obtained by running the "samples/bench.pl"
 117     script. The "_pp" entries are the pure Perl versions, whereas "_bv" are
 118     Bit::Vector versions.
 119
 120     *   This is for perl 5.8.8 on a Core 2 Duo 2.66GHz machine (unit is 64
 121         bits).
 122
 123             Filling bits at a given position :
 124                           Rate vfill_pp vfill_bv    vfill
 125             vfill_pp    80.3/s       --    -100%    -100%
 126             vfill_bv 1053399/s 1312401%       --     -11%
 127             vfill    1180792/s 1471129%      12%       --
 128
 129             Copying bits from a bit vector to a different one :
 130                          Rate vcopy_pp vcopy_bv    vcopy
 131             vcopy_pp    112/s       --    -100%    -100%
 132             vcopy_bv  62599/s   55622%       --     -89%
 133             vcopy    558491/s  497036%     792%       --
 134
 135             Moving bits in the same bit vector from a given position
 136             to a different one :
 137                          Rate vmove_pp vmove_bv    vmove
 138             vmove_pp   64.8/s       --    -100%    -100%
 139             vmove_bv  64742/s   99751%       --     -88%
 140             vmove    547980/s  845043%     746%       --
 141
 142             Testing bit equality from different positions of different
 143             bit vectors :
 144                        Rate  veq_pp  veq_bv     veq
 145             veq_pp   92.7/s      --   -100%   -100%
 146             veq_bv  32777/s  35241%      --    -94%
 147             veq    505828/s 545300%   1443%      --
 148
 149     *   This is for perl 5.10.0 on a Pentium 4 3.0GHz (unit is 32 bits).
 150
 151                          Rate vfill_pp vfill_bv    vfill
 152             vfill_pp    185/s       --    -100%    -100%
 153             vfill_bv 407979/s  220068%       --     -16%
 154             vfill    486022/s  262184%      19%       --
 155
 156                          Rate vcopy_pp vcopy_bv    vcopy
 157             vcopy_pp   61.5/s       --    -100%    -100%
 158             vcopy_bv  32548/s   52853%       --     -83%
 159             vcopy    187360/s  304724%     476%       --
 160
 161                          Rate vmove_pp vmove_bv    vmove
 162             vmove_pp   63.1/s       --    -100%    -100%
 163             vmove_bv  32829/s   51933%       --     -83%
 164             vmove    188572/s  298787%     474%       --
 165
 166                        Rate  veq_pp  veq_bv     veq
 167             veq_pp   34.2/s      --   -100%   -100%
 168             veq_bv  17518/s  51190%      --    -91%
 169             veq    192181/s 562591%    997%      --
 170
 171     *   This is for perl 5.10.0 on an UltraSPARC-IIi (unit is 8 bits).
 172
 173                         Rate vfill_pp    vfill vfill_bv
 174             vfill_pp  4.23/s       --    -100%    -100%
 175             vfill    30039/s  709283%       --     -17%
 176             vfill_bv 36022/s  850568%      20%       --
 177
 178                         Rate vcopy_pp vcopy_bv    vcopy
 179             vcopy_pp  2.74/s       --    -100%    -100%
 180             vcopy_bv  8146/s  297694%       --     -60%
 181             vcopy    20266/s  740740%     149%       --
 182
 183                         Rate vmove_pp vmove_bv    vmove
 184             vmove_pp  2.66/s       --    -100%    -100%
 185             vmove_bv  8274/s  311196%       --     -59%
 186             vmove    20287/s  763190%     145%       --
 187
 188                       Rate  veq_pp  veq_bv     veq
 189             veq_pp  7.33/s      --   -100%   -100%
 190             veq_bv  2499/s  33978%      --    -87%
 191             veq    19675/s 268193%    687%      --
 192
 193 CAVEATS
 194     Please report architectures where we can't use the alignment as the move
 195     unit. I'll add exceptions for them.
 196
 197 DEPENDENCIES
 198     perl 5.6.
 199
 200     A C compiler. This module may happen to build with a C++ compiler as
 201     well, but don't rely on it, as no guarantee is made in this regard.
 202
 203     Carp, Exporter (core modules since perl 5), XSLoader (since perl 5.6.0).
 204
 205 SEE ALSO
 206     Bit::Vector gives a complete reimplementation of bit vectors.
 207
 208 AUTHOR
 209     Vincent Pit, "<perl at profvince.com>", <http://www.profvince.com>.
 210
 211     You can contact me by mail or on "irc.perl.org" (vincent).
 212
 213 BUGS
 214     Please report any bugs or feature requests to "bug-scalar-vec-util at
 215     rt.cpan.org", or through the web interface at
 216     <http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Scalar-Vec-Util>. I will
 217     be notified, and then you'll automatically be notified of progress on
 218     your bug as I make changes.
 219
 220 SUPPORT
 221     You can find documentation for this module with the perldoc command.
 222
 223         perldoc Scalar::Vec::Util
 224
 225     Tests code coverage report is available at
 226     <http://www.profvince.com/perl/cover/Scalar-Vec-Util>.
 227
 228 COPYRIGHT & LICENSE
 229     Copyright 2008,2009,2010,2011,2012,2013 Vincent Pit, all rights
 230     reserved.
 231
 232     This program is free software; you can redistribute it and/or modify it
 233     under the same terms as Perl itself.
 234