1 package Scalar::Vec::Util;
10 Scalar::Vec::Util - Utility routines for vec strings.
23 XSLoader::load(__PACKAGE__, $VERSION);
26 *SVU_PP = sub () { 1 };
27 *SVU_SIZE = sub () { 1 };
36 use Scalar::Vec::Util qw<vfill vcopy veq>;
39 vfill $s, 0, 100, 1; # Fill with 100 bits 1 starting at 0.
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; # Overlapping areas DWIM.
44 if (veq $t, 10, $t, 20, 30) { ... } # Yes, they are equal now.
48 This module provides a set of utility routines that efficiently manipulate bits in vec strings.
49 Highly optimized XS functions are used whenever possible, but straightforward pure Perl replacements are also available for platforms without a C compiler.
51 Note that this module does not aim at reimplementing bit vectors : all its functions can be used on any Perl string, just like L<perlfunc/vec>.
57 True when pure Perl fallbacks are used instead of XS functions.
61 The size (in bits) of the unit used for bit operations.
62 The higher this value is, the faster the XS functions are.
63 It is usually C<CHAR_BIT * $Config{alignbytes}>, except on non-little-endian architectures where it currently falls back to C<CHAR_BIT> (e.g. SPARC).
69 vfill $vec, $start, $length, $bit;
71 Starting at C<$start> in C<$vec>, fills C<$length> bits with ones if C<$bit> is true and with zeros if C<$bit> is false.
73 C<$vec> is upgraded to a string and extended if necessary.
74 Bits that are outside of the specified area are left untouched.
79 my ($s, $l, $x) = @_[1 .. 3];
81 croak 'Invalid negative offset' if $s < 0;
82 croak 'Invalid negative length' if $l < 0;
85 my $t = int($s / $SIZE) + 1;
86 my $u = int(($s + $l) / $SIZE);
87 if ($SIZE * $t < $s + $l) { # implies $t <= $u
88 vec($_[0], $_, 1) = $x for $s .. $SIZE * $t - 1;
89 vec($_[0], $_, $SIZE) = $x for $t .. $u - 1;
90 vec($_[0], $_, 1) = $x for $SIZE * $u .. $s + $l - 1;
92 vec($_[0], $_, 1) = $x for $s .. $s + $l - 1;
98 vcopy $from => $from_start, $to => $to_start, $length;
100 Copies C<$length> bits starting at C<$from_start> in C<$from> to C<$to_start> in C<$to>.
102 C<$from> and C<$to> are allowed to be the same scalar, and the given areas can rightfully overlap.
104 C<$from> is upgraded to a string if it isn't one already.
105 If C<$from_start + $length> goes out of the bounds of C<$from>, then the extra bits are treated as zeros.
106 C<$to> is upgraded to a string and extended if necessary.
107 The content of C<$from> is not modified, except when it is equal to C<$to>.
108 Bits that are outside of the specified area are left untouched.
110 This function does not need to allocate any extra memory.
114 sub vcopy_pp ($$$$$) {
115 my ($fs, $ts, $l) = @_[1, 3, 4];
117 croak 'Invalid negative offset' if $fs < 0 or $ts < 0;
118 croak 'Invalid negative length' if $l < 0;
119 my $step = $ts - $fs;
121 vec($_[2], $_ + $step, 1) = vec($_[0], $_, 1) for $fs .. $fs + $l - 1;
122 } else { # There's a risk of overwriting if $_[0] and $_[2] are the same SV.
123 vec($_[2], $_ + $step, 1) = vec($_[0], $_, 1) for reverse $fs .. $fs + $l - 1;
129 vshift $v, $start, $length => $bits, $insert;
131 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.
133 When C<$insert> is defined, the resulting gap is also filled with ones if C<$insert> is true and with zeros if C<$insert> is false.
135 C<$v> is upgraded to a string if it isn't one already.
136 If C<$start + $length> goes out of the bounds of C<$v>, then the extra bits are treated as zeros.
137 Bits that are outside of the specified area are left untouched.
139 This function does not need to allocate any extra memory.
143 sub vshift ($$$$;$) {
144 my ($start, $length, $bits, $insert) = @_[1 .. 4];
145 return unless $length and $bits;
146 croak 'Invalid negative offset' if $start < 0;
147 croak 'Invalid negative length' if $length < 0;
153 if ($bits < $length) {
156 vcopy($_[0], $start, $_[0], $start + $bits, $length);
157 vfill($_[0], $start, $bits, $insert) if defined $insert;
159 vcopy($_[0], $start + $bits, $_[0], $start, $length);
160 vfill($_[0], $start + $length, $bits, $insert) if defined $insert;
163 vfill($_[0], $start, $length, $insert) if defined $insert;
169 vrot $v, $start, $length, $bits;
171 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.
173 C<$v> is upgraded to a string if it isn't one already.
174 If C<$start + $length> goes out of the bounds of C<$v>, then the extra bits are treated as zeros.
175 Bits that are outside of the specified area are left untouched.
177 This function currently allocates an extra buffer of size C<O($bits)>.
182 my ($start, $length, $bits) = @_[1 .. 3];
183 return unless $length and $bits;
184 croak 'Invalid negative offset' if $start < 0;
185 croak 'Invalid negative length' if $length < 0;
196 vcopy($_[0], $start + $length, $buf, 0, $bits);
197 vcopy($_[0], $start, $_[0], $start + $bits, $length);
198 vcopy($buf, 0, $_[0], $start, $bits);
200 vcopy($_[0], $start, $buf, 0, $bits);
201 vcopy($_[0], $start + $bits, $_[0], $start, $length);
202 vcopy($buf, 0, $_[0], $start + $length, $bits);
208 veq $v1 => $v1_start, $v2 => $v2_start, $length;
210 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.
212 C<$v1> and C<$v2> are upgraded to strings if they aren't already, but their contents are never modified.
213 If C<$v1_start + $length> (respectively C<$v2_start + $length>) goes out of the bounds of C<$v1> (respectively C<$v2>), then the extra bits are treated as zeros.
215 This function does not need to allocate any extra memory.
220 my ($s1, $s2, $l) = @_[1, 3, 4];
221 croak 'Invalid negative offset' if $s1 < 0 or $s2 < 0;
222 croak 'Invalid negative length' if $l < 0;
225 return 0 if vec($_[0], $s1 + $i, 1) != vec($_[2], $s2 + $i, 1);
233 The functions L</vfill>, L</vcopy>, L</vshift>, L</vrot> and L</veq> are only exported on request.
234 All of them are exported by the tags C<':funcs'> and C<':all'>.
236 The constants L</SVU_PP> and L</SVU_SIZE> are also only exported on request.
237 They are all exported by the tags C<':consts'> and C<':all'>.
241 use base qw<Exporter>;
245 'funcs' => [ qw<vfill vcopy vshift vrot veq> ],
246 'consts' => [ qw<SVU_PP SVU_SIZE> ]
248 our @EXPORT_OK = map { @$_ } values %EXPORT_TAGS;
249 $EXPORT_TAGS{'all'} = [ @EXPORT_OK ];
253 The following timings were obtained by running the C<samples/bench.pl> script.
254 The C<_pp> entries are the pure Perl versions, whereas C<_bv> are L<Bit::Vector> versions.
260 This is for perl 5.8.8 on a Core 2 Duo 2.66GHz machine (unit is 64 bits).
262 Filling bits at a given position :
263 Rate vfill_pp vfill_bv vfill
264 vfill_pp 80.3/s -- -100% -100%
265 vfill_bv 1053399/s 1312401% -- -11%
266 vfill 1180792/s 1471129% 12% --
268 Copying bits from a bit vector to a different one :
269 Rate vcopy_pp vcopy_bv vcopy
270 vcopy_pp 112/s -- -100% -100%
271 vcopy_bv 62599/s 55622% -- -89%
272 vcopy 558491/s 497036% 792% --
274 Moving bits in the same bit vector from a given position to a different one :
275 Rate vmove_pp vmove_bv vmove
276 vmove_pp 64.8/s -- -100% -100%
277 vmove_bv 64742/s 99751% -- -88%
278 vmove 547980/s 845043% 746% --
280 Testing bit equality from different positions of different bit vectors :
281 Rate veq_pp veq_bv veq
282 veq_pp 92.7/s -- -100% -100%
283 veq_bv 32777/s 35241% -- -94%
284 veq 505828/s 545300% 1443% --
288 This is for perl 5.10.0 on a Pentium 4 3.0GHz (unit is 32 bits).
290 Rate vfill_pp vfill_bv vfill
291 vfill_pp 185/s -- -100% -100%
292 vfill_bv 407979/s 220068% -- -16%
293 vfill 486022/s 262184% 19% --
295 Rate vcopy_pp vcopy_bv vcopy
296 vcopy_pp 61.5/s -- -100% -100%
297 vcopy_bv 32548/s 52853% -- -83%
298 vcopy 187360/s 304724% 476% --
300 Rate vmove_pp vmove_bv vmove
301 vmove_pp 63.1/s -- -100% -100%
302 vmove_bv 32829/s 51933% -- -83%
303 vmove 188572/s 298787% 474% --
305 Rate veq_pp veq_bv veq
306 veq_pp 34.2/s -- -100% -100%
307 veq_bv 17518/s 51190% -- -91%
308 veq 192181/s 562591% 997% --
312 This is for perl 5.10.0 on an UltraSPARC-IIi (unit is 8 bits).
314 Rate vfill_pp vfill vfill_bv
315 vfill_pp 4.23/s -- -100% -100%
316 vfill 30039/s 709283% -- -17%
317 vfill_bv 36022/s 850568% 20% --
319 Rate vcopy_pp vcopy_bv vcopy
320 vcopy_pp 2.74/s -- -100% -100%
321 vcopy_bv 8146/s 297694% -- -60%
322 vcopy 20266/s 740740% 149% --
324 Rate vmove_pp vmove_bv vmove
325 vmove_pp 2.66/s -- -100% -100%
326 vmove_bv 8274/s 311196% -- -59%
327 vmove 20287/s 763190% 145% --
329 Rate veq_pp veq_bv veq
330 veq_pp 7.33/s -- -100% -100%
331 veq_bv 2499/s 33978% -- -87%
332 veq 19675/s 268193% 687% --
338 Please report architectures where we can't use the alignment as the move unit.
339 I'll add exceptions for them.
346 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.
348 L<Carp>, L<Exporter> (core modules since perl 5), L<XSLoader> (since perl 5.006).
352 L<Bit::Vector> gives a complete reimplementation of bit vectors.
356 Vincent Pit, C<< <perl at profvince.com> >>, L<http://www.profvince.com>.
358 You can contact me by mail or on C<irc.perl.org> (vincent).
362 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>.
363 I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.
367 You can find documentation for this module with the perldoc command.
369 perldoc Scalar::Vec::Util
371 Tests code coverage report is available at L<http://www.profvince.com/perl/cover/Scalar-Vec-Util>.
373 =head1 COPYRIGHT & LICENSE
375 Copyright 2008,2009,2010,2011,2012 Vincent Pit, all rights reserved.
377 This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
381 1; # End of Scalar::Vec::Util