lib/Scalar/Vec/Util.pm

   1 package Scalar::Vec::Util;
   2
   3 use strict;
   4 use warnings;
   5
   6 use Carp qw<croak>;
   7
   8 =head1 NAME
   9
  10 Scalar::Vec::Util - Utility routines for vec strings.
  11
  12 =head1 VERSION
  13
  14 Version 0.06
  15
  16 =cut
  17
  18 our $VERSION;
  19 BEGIN {
  20  $VERSION = '0.06';
  21  eval {
  22   require XSLoader;
  23   XSLoader::load(__PACKAGE__, $VERSION);
  24   1;
  25  } or do {
  26   *SVU_PP   = sub () { 1 };
  27   *SVU_SIZE = sub () { 1 };
  28   *vfill    = *vfill_pp;
  29   *vcopy    = *vcopy_pp;
  30   *veq      = *veq_pp;
  31  }
  32 }
  33
  34 =head1 SYNOPSIS
  35
  36     use Scalar::Vec::Util qw<vfill vcopy veq>;
  37
  38     my $s;
  39     vfill $s, 0, 100, 1; # Fill with 100 bits 1 starting at 0.
  40     my $t;
  41     vcopy $s, 20, $t, 10, 30; # Copy 30 bits from $s, starting at 20,
  42                               #                to $t, starting at 10.
  43     vcopy $t, 10, $t, 20, 30; # Overalapping areas DWIM.
  44     if (veq $t, 10, $t, 20, 30) { ... } # Yes, they are equal now.
  45
  46 =head1 DESCRIPTION
  47
  48 A set of utilities to manipulate bits in vec strings.
  49 Highly optimized XS routines are used when available, but straightforward pure perl replacements are also provided for platforms without a C compiler.
  50
  51 This module doesn't reimplement bit vectors.
  52 It can be used on the very same scalars that C<vec> builds, or actually on any Perl string (C<SVt_PV>).
  53
  54 =head1 CONSTANTS
  55
  56 =head2 C<SVU_PP>
  57
  58 True when pure perl fallbacks are used instead of XS functions.
  59
  60 =head2 C<SVU_SIZE>
  61
  62 Size in bits of the unit used for moves.
  63 The higher this value is, the faster the XS functions are.
  64 It's usually C<CHAR_BIT * $Config{alignbytes}>, except on non-little-endian architectures where it currently falls back to C<CHAR_BIT> (e.g. SPARC).
  65
  66 =head1 FUNCTIONS
  67
  68 =head2 C<vfill $vec, $start, $length, $bit>
  69
  70 Starting at C<$start> in C<$vec>, fills C<$length> bits with C<$bit>.
  71 Grows C<$vec> if necessary.
  72
  73 =cut
  74
  75 sub vfill_pp ($$$$) {
  76  my ($s, $l, $x) = @_[1 .. 3];
  77  return unless $l;
  78  croak 'Invalid negative offset' if $s < 0;
  79  croak 'Invalid negative length' if $l < 0;
  80  $x = ~0 if $x;
  81  my $SIZE = 32;
  82  my $t = int($s / $SIZE) + 1;
  83  my $u = int(($s + $l) / $SIZE);
  84  if ($SIZE * $t < $s + $l) { # implies $t <= $u
  85   vec($_[0], $_, 1)     = $x for $s .. $SIZE * $t - 1;
  86   vec($_[0], $_, $SIZE) = $x for $t .. $u - 1;
  87   vec($_[0], $_, 1)     = $x for $SIZE * $u .. $s + $l - 1;
  88  } else {
  89   vec($_[0], $_, 1) = $x for $s .. $s + $l - 1;
  90  }
  91 }
  92
  93 =head2 C<< vcopy $from => $from_start, $to => $to_start, $length >>
  94
  95 Copies C<$length> bits starting at C<$from_start> in C<$from> to C<$to_start> in C<$to>.
  96 If C<$from_start + $length> is too long for C<$from>, zeros are copied past C<$length>.
  97 Grows C<$to> if necessary.
  98 Doesn't need to allocate any extra memory.
  99
 100 =cut
 101
 102 sub vcopy_pp ($$$$$) {
 103  my ($fs, $ts, $l) = @_[1, 3, 4];
 104  return unless $l;
 105  croak 'Invalid negative offset' if $fs < 0 or $ts < 0;
 106  croak 'Invalid negative length' if $l  < 0;
 107  my $step = $ts - $fs;
 108  if ($step <= 0) {
 109   vec($_[2], $_ + $step, 1) = vec($_[0], $_, 1) for $fs .. $fs + $l - 1;
 110  } else { # There's a risk of overwriting if $_[0] and $_[2] are the same SV.
 111   vec($_[2], $_ + $step, 1) = vec($_[0], $_, 1) for reverse $fs .. $fs + $l - 1;
 112  }
 113 }
 114
 115 =head2 C<< vshift $v, $start, $length => $bits [, $insert ] >>
 116
 117 In the area starting at C<$start> and of length C<$length> in C<$v>, shift bits C<abs $bits> positions left if C<< $bits > 0 >> and right otherwise.
 118 If C<$insert> is defined, also fills the resulting gap with ones if C<$insert> is true and zeros if it's false.
 119 Bits outside of the specified area are left untouched.
 120 Doesn't need to allocate any extra memory.
 121
 122 =cut
 123
 124 sub vshift ($$$$;$) {
 125  my ($start, $length, $bits, $insert) = @_[1 .. 4];
 126  return unless $length and $bits;
 127  croak 'Invalid negative offset' if $start  < 0;
 128  croak 'Invalid negative length' if $length < 0;
 129  my $left = 1;
 130  if ($bits < 0) {
 131   $left = 0;
 132   $bits = -$bits;
 133  }
 134  if ($bits < $length) {
 135   $length -= $bits;
 136   if ($left) {
 137    vcopy($_[0], $start, $_[0], $start + $bits, $length);
 138    vfill($_[0], $start, $bits, $insert) if defined $insert;
 139   } else {
 140    vcopy($_[0], $start + $bits, $_[0], $start, $length);
 141    vfill($_[0], $start + $length, $bits, $insert) if defined $insert;
 142   }
 143  } else {
 144   vfill($_[0], $start, $length, $insert) if defined $insert;
 145  }
 146 }
 147
 148 =head2 C<< vrot $v, $start, $length, $bits >>
 149
 150 In the area starting at C<$start> and of length C<$length> in C<$v>, rotates bits C<abs $bits> positions left if C<< $bits > 0 >> and right otherwise.
 151 Bits outside of the specified area are left untouched.
 152 Currently allocates an extra buffer of size C<O($bits)>.
 153
 154 =cut
 155
 156 sub vrot ($$$$) {
 157  my ($start, $length, $bits) = @_[1 .. 3];
 158  return unless $length and $bits;
 159  croak 'Invalid negative offset' if $start  < 0;
 160  croak 'Invalid negative length' if $length < 0;
 161  my $left = 1;
 162  if ($bits < 0) {
 163   $left = 0;
 164   $bits = -$bits;
 165  }
 166  $bits %= $length;
 167  return unless $bits;
 168  $length -= $bits;
 169  my $buf = '';
 170  if ($left) {
 171   vcopy($_[0], $start + $length, $buf,  0,              $bits);
 172   vcopy($_[0], $start,           $_[0], $start + $bits, $length);
 173   vcopy($buf,  0,                $_[0], $start,         $bits);
 174  } else {
 175   vcopy($_[0], $start,           $buf,  0,                $bits);
 176   vcopy($_[0], $start + $bits,   $_[0], $start,           $length);
 177   vcopy($buf,  0,                $_[0], $start + $length, $bits);
 178  }
 179 }
 180
 181 =head2 C<< veq $v1 => $v1_start, $v2 => $v2_start, $length >>
 182
 183 Returns true if the C<$length> bits starting at C<$v1_start> in C<$v1> and C<$v2_start> in C<$v2> are equal, and false otherwise.
 184 If needed, C<$length> is decreased to fit inside C<$v1> and C<$v2> boundaries.
 185
 186 =cut
 187
 188 sub veq_pp ($$$$$) {
 189  my ($s1, $s2, $l) = @_[1, 3, 4];
 190  croak 'Invalid negative offset' if $s1 < 0 or $s2 < 0;
 191  croak 'Invalid negative length' if $l  < 0;
 192  my $i = 0;
 193  while ($i < $l) {
 194   return 0 if vec($_[0], $s1 + $i, 1) != vec($_[2], $s2 + $i, 1);
 195   ++$i;
 196  }
 197  return 1;
 198 }
 199
 200 =head1 EXPORT
 201
 202 The functions L</vfill>, L</vcopy>, L</vshift>, L</vrot> and L</veq> are only exported on request.
 203 All of them are exported by the tags C<':funcs'> and C<':all'>.
 204
 205 The constants L</SVU_PP> and L</SVU_SIZE> are also only exported on request.
 206 They are all exported by the tags C<':consts'> and C<':all'>.
 207
 208 =cut
 209
 210 use base qw<Exporter>;
 211
 212 our @EXPORT         = ();
 213 our %EXPORT_TAGS    = (
 214  'funcs'  => [ qw<vfill vcopy vshift vrot veq> ],
 215  'consts' => [ qw<SVU_PP SVU_SIZE> ]
 216 );
 217 our @EXPORT_OK      = map { @$_ } values %EXPORT_TAGS;
 218 $EXPORT_TAGS{'all'} = [ @EXPORT_OK ];
 219
 220 =head1 BENCHMARKS
 221
 222 The following timings were obtained by running the C<samples/bench.pl> script.
 223 The C<_pp> entries are the pure Perl versions, whereas C<_bv> are L<Bit::Vector> versions.
 224
 225 =over 4
 226
 227 =item This is for perl 5.8.8 on a Core 2 Duo 2.66GHz machine (unit is 64 bits).
 228
 229     Filling bits at a given position :
 230                   Rate vfill_pp vfill_bv    vfill
 231     vfill_pp    80.3/s       --    -100%    -100%
 232     vfill_bv 1053399/s 1312401%       --     -11%
 233     vfill    1180792/s 1471129%      12%       --
 234
 235     Copying bits from a bit vector to a different one :
 236                  Rate vcopy_pp vcopy_bv    vcopy
 237     vcopy_pp    112/s       --    -100%    -100%
 238     vcopy_bv  62599/s   55622%       --     -89%
 239     vcopy    558491/s  497036%     792%       --
 240
 241     Moving bits in the same bit vector from a given position to a different one :
 242                  Rate vmove_pp vmove_bv    vmove
 243     vmove_pp   64.8/s       --    -100%    -100%
 244     vmove_bv  64742/s   99751%       --     -88%
 245     vmove    547980/s  845043%     746%       --
 246
 247     Testing bit equality from different positions of different bit vectors :
 248                Rate  veq_pp  veq_bv     veq
 249     veq_pp   92.7/s      --   -100%   -100%
 250     veq_bv  32777/s  35241%      --    -94%
 251     veq    505828/s 545300%   1443%      --
 252
 253 =item This is for perl 5.10.0 on a Pentium 4 3.0GHz (unit is 32 bits).
 254
 255                  Rate vfill_pp vfill_bv    vfill
 256     vfill_pp    185/s       --    -100%    -100%
 257     vfill_bv 407979/s  220068%       --     -16%
 258     vfill    486022/s  262184%      19%       --
 259
 260                  Rate vcopy_pp vcopy_bv    vcopy
 261     vcopy_pp   61.5/s       --    -100%    -100%
 262     vcopy_bv  32548/s   52853%       --     -83%
 263     vcopy    187360/s  304724%     476%       --
 264
 265                  Rate vmove_pp vmove_bv    vmove
 266     vmove_pp   63.1/s       --    -100%    -100%
 267     vmove_bv  32829/s   51933%       --     -83%
 268     vmove    188572/s  298787%     474%       --
 269
 270                Rate  veq_pp  veq_bv     veq
 271     veq_pp   34.2/s      --   -100%   -100%
 272     veq_bv  17518/s  51190%      --    -91%
 273     veq    192181/s 562591%    997%      --
 274
 275 =item This is for perl 5.10.0 on an UltraSPARC-IIi (unit is 8 bits).
 276
 277                 Rate vfill_pp    vfill vfill_bv
 278     vfill_pp  4.23/s       --    -100%    -100%
 279     vfill    30039/s  709283%       --     -17%
 280     vfill_bv 36022/s  850568%      20%       --
 281
 282                 Rate vcopy_pp vcopy_bv    vcopy
 283     vcopy_pp  2.74/s       --    -100%    -100%
 284     vcopy_bv  8146/s  297694%       --     -60%
 285     vcopy    20266/s  740740%     149%       --
 286
 287                 Rate vmove_pp vmove_bv    vmove
 288     vmove_pp  2.66/s       --    -100%    -100%
 289     vmove_bv  8274/s  311196%       --     -59%
 290     vmove    20287/s  763190%     145%       --
 291
 292               Rate  veq_pp  veq_bv     veq
 293     veq_pp  7.33/s      --   -100%   -100%
 294     veq_bv  2499/s  33978%      --    -87%
 295     veq    19675/s 268193%    687%      --
 296
 297 =back
 298
 299 =head1 CAVEATS
 300
 301 Please report architectures where we can't use the alignment as the move unit.
 302 I'll add exceptions for them.
 303
 304 =head1 DEPENDENCIES
 305
 306 L<perl> 5.6.
 307
 308 A C compiler.
 309 This module may happen to build with a C++ compiler as well, but don't rely on it, as no guarantee is made in this regard.
 310
 311 L<Carp>, L<Exporter> (core modules since perl 5), L<XSLoader> (since perl 5.006).
 312
 313 =head1 SEE ALSO
 314
 315 L<Bit::Vector> gives a complete reimplementation of bit vectors.
 316
 317 =head1 AUTHOR
 318
 319 Vincent Pit, C<< <perl at profvince.com> >>, L<http://www.profvince.com>.
 320
 321 You can contact me by mail or on C<irc.perl.org> (vincent).
 322
 323 =head1 BUGS
 324
 325 Please report any bugs or feature requests to C<bug-scalar-vec-util at rt.cpan.org>, or through the web interface at L<http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Scalar-Vec-Util>.
 326 I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.
 327
 328 =head1 SUPPORT
 329
 330 You can find documentation for this module with the perldoc command.
 331
 332     perldoc Scalar::Vec::Util
 333
 334 Tests code coverage report is available at L<http://www.profvince.com/perl/cover/Scalar-Vec-Util>.
 335
 336 =head1 COPYRIGHT & LICENSE
 337
 338 Copyright 2008,2009,2010,2011,2012 Vincent Pit, all rights reserved.
 339
 340 This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
 341
 342 =cut
 343
 344 1; # End of Scalar::Vec::Util