Bit fiddling madness

mbethke has asked for the wisdom of the Perl Monks concerning the following question:

Brothers, I'm going mad with this and probably just need a whack on the head to make me see what's right in front of my eyes. I'm the author of the Net::CIDR::Lookup module and have been getting a lot of cpantesters failures. While some of them are due to a broken/incomplete Socket implementation on Windows and thus Other People's Problem, there are some related to the _add method that always look like this:

#   Failed test 'add died (Modification of non-creatable array value attempted, subscript -1 at /home/cpan/pit/bare/conf/perl-5.16.0/.cpanplus/5.16.0/build/Net-CIDR-Lookup-0.51/blib/lib/Net/CIDR/Lookup.pm line 342.
# 	...propagated at t/lib/Net/CIDR/Lookup/Test.pm line 41.)'
#   at t/Net-CIDR-Lookup.t line 6.
#   (in Net::CIDR::Lookup::Test->add)

The code that fails here by resulting in a negative subscript is basically this (it's a bit more convoluted but as $bit isn't modified in between the initial assignment and the array creation, this is what it boils down to):

$bit = ($addr & 0x80000000) >> 31;                                    
+                                 
$addr <<= 1;                                                          
+                                 
$node->[$bit] ||= bless([], __PACKAGE__);
[download]

The idea is to make every node an array of one or two elements by using the current bit from the IP address as an index. Somehow this bit seems to come out -1 sometimes, on a wide range of systems and Perl versions. I've never been able to reproduce it though, nor can I think of a number that masked and shifted that way would result in -1. Even if the upper 32 bit on a 64 bit system should contain garbage for some reason, the mask should eliminate it, right?

Lately I've augmented the test so it first checks whether _add() dies, and if so, monkey-patches it with a version that tries to trace where the error happens. As soon as I do that---add a single print statement to the start and one after the bit shift, plus replaced some instances of __PACKAGE__ with 'Net::CIDR::Lookup' because of the different definition context---the heisenbug is gone. WTF?!

Comment on Bit fiddling madness Download Code

Replies are listed 'Best First'.

Re: Bit fiddling madness
by sn1987a (Deacon) on Feb 11, 2014 at 14:58 UTC

I notice that Net/CIDR/Lookup.pm has "use integer"

According to Shift Operators:

Note that both << and >> in Perl are implemented directly using << and >> in C. If use integer (see Integer Arithmetic) is in force then signed C integers are used."

$ perl -E 'use integer; say 0x80000000 >> 31'
-1
[download]

RichardK's suggestion above would avoid this issue.

[reply]
[d/l]

Re^2: Bit fiddling madness

by Athanasius (Archbishop) on Feb 11, 2014 at 15:51 UTC

++sn1987a (when the Vote Fairy next visits) for an ingenious observation! Unfortunately, I don’t think it answers the OP’s question, as masking with bitwise-AND does remove the sign bit, even with use integer in effect:

#! perl
use strict;
use warnings;

print "\nno integer\n";

my $bit = -1 >> 31;
printf "unmasked: 0x%x = %d\n", $bit, $bit;

$bit = (-1 & 0x80000000) >> 31;
printf "masked:   0x%x = %d\n", $bit, $bit;

use integer;

print "\nuse integer\n";

$bit = -1 >> 31;
printf "unmasked: 0x%x = %d\n", $bit, $bit;

$bit = (-1 & 0x80000000) >> 31;
printf "masked:   0x%x = %d\n", $bit, $bit;
[download]

Output:

 1:29 >perl 868_SoPW.pl

no integer
unmasked: 0x1ffffffff = 8589934591
masked:   0x1 = 1

use integer
unmasked: 0xffffffffffffffff = -1
masked:   0x1 = 1

 1:29 >perl -v

This is perl 5, version 18, subversion 2 (v5.18.2) built for MSWin32-x
+86-multi-thread-64int
[download]

:-(

Update: As BrowserUk observes below, masking removes the sign bit (in this case) only in perls built with 64-bit ints. For perls built with 32-bit ints, sn1987a’s observation does answer the OP’s question. (Moral for self: test, test, test!)

Athanasius <°(((>< contra mundum Iustus alius egestas vitae, eros Piratica,

[reply]
[d/l]
[select]

Re^3: Bit fiddling madness

by BrowserUk (Patriarch) on Feb 11, 2014 at 16:06 UTC

built for MSWin32-x86-multi-thread-64int

The problem only(*) occurs with 32-bit perls:

C:\test>type CIDRtest.pl
#! perl -slw
use strict;
use integer;

for my $n ( 0 .. 31 ) {
    my $addr = (1 << $n) + 1;
    printf "\r%u", $addr;
    my $nbits = 32;
    while( 1 ) {
        my $bit = ( $addr & 0x80000000 ) >> 31;
        die "$addr -> $bit" if $bit != 0 and $bit != 1;
        $addr <<= 1;
        last unless --$nbits;
    }
}

C:\test>CIDRtest.pl
2147483649

C:\test>\perl32\bin\perl.exe CIDRtest.pl
-2147483648 -> -1 at CIDRtest.pl line 11.
2
[download]

(*Or 64-bit perls, but with much higher numbers.)

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

[reply]
[d/l]

Re^4: Bit fiddling madness

by mbethke (Hermit) on Feb 11, 2014 at 16:36 UTC

Re^3: Bit fiddling madness

by sn1987a (Deacon) on Feb 11, 2014 at 16:07 UTC

Thanks for the update Athanasius. I was not aware of that feature. :)

Oh well, back to the drawing board...

[reply]

Re: Bit fiddling madness
by RichardK (Parson) on Feb 11, 2014 at 12:12 UTC

I have no clue as to what's going wrong and you only gave us a tiny code fragment so it's difficult to guess, however I wonder if this would help, or at least shed some light on what is happening.

my $bit = ($addr & $mask) ? 1 : 0;

[reply]
[d/l]

Re^2: Bit fiddling madness

by mbethke (Hermit) on Feb 11, 2014 at 16:24 UTC

Yeah, thanks for the input, that would certainly have fixed it. Actually I'd thought about it earlier but it seemed kinda kludgy to me because the bug shouldn't have been there in the first place and it wasn't on any of my systems, so I wanted get to the bottom of it. And of course because of the few extra cycles :)

[reply]


P is for Practical
	PerlMonks