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.
258 =item This is for perl 5.8.8 on a Core 2 Duo 2.66GHz machine (unit is 64 bits).
260 Filling bits at a given position :
261 Rate vfill_pp vfill_bv vfill
262 vfill_pp 80.3/s -- -100% -100%
263 vfill_bv 1053399/s 1312401% -- -11%
264 vfill 1180792/s 1471129% 12% --
266 Copying bits from a bit vector to a different one :
267 Rate vcopy_pp vcopy_bv vcopy
268 vcopy_pp 112/s -- -100% -100%
269 vcopy_bv 62599/s 55622% -- -89%
270 vcopy 558491/s 497036% 792% --
272 Moving bits in the same bit vector from a given position to a different one :
273 Rate vmove_pp vmove_bv vmove
274 vmove_pp 64.8/s -- -100% -100%
275 vmove_bv 64742/s 99751% -- -88%
276 vmove 547980/s 845043% 746% --
278 Testing bit equality from different positions of different bit vectors :
279 Rate veq_pp veq_bv veq
280 veq_pp 92.7/s -- -100% -100%
281 veq_bv 32777/s 35241% -- -94%
282 veq 505828/s 545300% 1443% --
284 =item This is for perl 5.10.0 on a Pentium 4 3.0GHz (unit is 32 bits).
286 Rate vfill_pp vfill_bv vfill
287 vfill_pp 185/s -- -100% -100%
288 vfill_bv 407979/s 220068% -- -16%
289 vfill 486022/s 262184% 19% --
291 Rate vcopy_pp vcopy_bv vcopy
292 vcopy_pp 61.5/s -- -100% -100%
293 vcopy_bv 32548/s 52853% -- -83%
294 vcopy 187360/s 304724% 476% --
296 Rate vmove_pp vmove_bv vmove
297 vmove_pp 63.1/s -- -100% -100%
298 vmove_bv 32829/s 51933% -- -83%
299 vmove 188572/s 298787% 474% --
301 Rate veq_pp veq_bv veq
302 veq_pp 34.2/s -- -100% -100%
303 veq_bv 17518/s 51190% -- -91%
304 veq 192181/s 562591% 997% --
306 =item This is for perl 5.10.0 on an UltraSPARC-IIi (unit is 8 bits).
308 Rate vfill_pp vfill vfill_bv
309 vfill_pp 4.23/s -- -100% -100%
310 vfill 30039/s 709283% -- -17%
311 vfill_bv 36022/s 850568% 20% --
313 Rate vcopy_pp vcopy_bv vcopy
314 vcopy_pp 2.74/s -- -100% -100%
315 vcopy_bv 8146/s 297694% -- -60%
316 vcopy 20266/s 740740% 149% --
318 Rate vmove_pp vmove_bv vmove
319 vmove_pp 2.66/s -- -100% -100%
320 vmove_bv 8274/s 311196% -- -59%
321 vmove 20287/s 763190% 145% --
323 Rate veq_pp veq_bv veq
324 veq_pp 7.33/s -- -100% -100%
325 veq_bv 2499/s 33978% -- -87%
326 veq 19675/s 268193% 687% --
332 Please report architectures where we can't use the alignment as the move unit.
333 I'll add exceptions for them.
340 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.
342 L<Carp>, L<Exporter> (core modules since perl 5), L<XSLoader> (since perl 5.006).
346 L<Bit::Vector> gives a complete reimplementation of bit vectors.
350 Vincent Pit, C<< <perl at profvince.com> >>, L<http://www.profvince.com>.
352 You can contact me by mail or on C<irc.perl.org> (vincent).
356 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>.
357 I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.
361 You can find documentation for this module with the perldoc command.
363 perldoc Scalar::Vec::Util
365 Tests code coverage report is available at L<http://www.profvince.com/perl/cover/Scalar-Vec-Util>.
367 =head1 COPYRIGHT & LICENSE
369 Copyright 2008,2009,2010,2011,2012 Vincent Pit, all rights reserved.
371 This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
375 1; # End of Scalar::Vec::Util