[pm-h] Thursday's Meeting: Lightning Talks?

[Jake Gelbman]

I recently was thinking about some bit hacks to convert IP Ranges with
a mask to ranged format. For example:

    1.2.3.5/28 to 1.2.3.0-15
    1.2.3.5/255.0.255.0 to 1.-.3.-

And can present a talk thats a bit longer than a lightning talk but
still less than a regular talk on a good way to do it.

Attached are the slides, they are in vroom format.

https://metacpan.org/module/Vroom

On Tue, Sep 06, 2011 at 07:25:15AM -0700, Mark Allen wrote:
> I have a couple of lightning talks but I won't be able to make the meeting this month unfortunately.  Maybe in October.  
>
> Speaking of October, is anyone from Houston.pm going to the Pittsburgh Perl Workshop?
>
> Mark
>
>
> ________________________________
> From: G. Wade Johnson <gwadej at anomaly.org>
> To: Houston Perl Mongers <houston at pm.org>
> Sent: Monday, September 5, 2011 8:28 PM
> Subject: [pm-h] Thursday's Meeting: Lightning Talks?
>
> Our next technical meeting is coming up this Thursday and I've only had
> one (provisional) volunteer for a lightning talk.
>
> Surely some of you are working on things or interested in things that
> you could present to the group in 5 minutes or less.
>
> If you have an idea for a talk, but you're not sure if anyone would be
> interested, here's a low-risk way to find out.
>
> If you're done a cool little hack that you'd like to share, now is the
> time.
>
> If you know of a module that has really saved you time or hassle, give
> it a shout out at the meeting.
>
> Anyone who is interested in doing a lightning talk, please let me know
> soon, so I can try to make certain we are prepared before the meeting,
> this Thursday.
>
> If we have time, I'll still accept "walk on" talks. But the more I know
> about ahead of time, the better.
>
> I look forward to seeing you there (even if you don't want to
> present<grin/>).
>
> G. Wade
> --
> DON'T PANIC! I'm a trained professional, and far more qualified to
> panic in this situation than you are.
> _______________________________________________
> Houston mailing list
> Houston at pm.org
> http://mail.pm.org/mailman/listinfo/houston
> Website: http://houston.pm.org/

> _______________________________________________
> Houston mailing list
> Houston at pm.org
> http://mail.pm.org/mailman/listinfo/houston
> Website: http://houston.pm.org/

-------------- next part --------------
---- config
title: Bit Hacks on IP Ranges
indent: 4
height: 18
width: 69
skip: 0

---- center
Bit Hacks on IP Ranges

by Jake Gelbman

----
IP::Range accepts the following formats:

----
* 1.2.3.5
+* 1.2.3.5,105,205
+* 1.2.3.5-55
+* 1.2.3.-
+* 1.2.3.5 8.13.21.34
+* 1.2.3.4/24
+* 1.2.3.4/255.255.255.0

----
Just like nmap(1)

http://nmap.org/book/man-target-specification.html

----
And parses it into a nested array ref structure:

---- perl
my $r = IP::Range->new("1.2-3,5-8,13.21.34");

---- perl
$VAR1 = bless({
    str => '1.2-3,5-8,13.21.34',
    ranges =>
        [
            [
                [1],
                [[2, 3], [5, 8], 13],
                [21],
                [34],
            ]
        ]
}, "IP::Range");

----
Which it uses to see if an IP address is in the range specified:

---- perl
$r->match("1.2.3.4"); # Nope
$r->match("1.7.21.34"); # Yeah!

----
And can create a mysql query out of it:

---- perl
$r->mysql("expr");

---- sql
-- expr in ip range 1.2-3,5-8,13.21.34
(inet_aton(expr) & 0xff000000) >> 24 = 1 and
((inet_aton(expr) & 0x00ff0000) >> 16 between 2 and 3 or
(inet_aton(expr) & 0x00ff0000) >> 16 between 5 and 8 or
(inet_aton(expr) & 0x00ff0000) >> 16 = 13) and
(inet_aton(expr) & 0x0000ff00) >> 8 = 21 and
(inet_aton(expr) & 0x000000ff) >> 0 = 34

----
However, the CIDR or bitmask style:

    1.2.3.5/24
    1.2.3.5/255.255.255.0

has to be handled specially when matching or generating the mysql
criteria.

----
So, I wanted some way to convert the specification into the other format
for ranges:

    1.2.3.5/28               to  1.2.3.0-15
    1.2.3.5/255.255.255.0    to  1.2.3.-

----
Or 1.2.3.5/160.225.152.186 to

    0-31,64-95
    .
    0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30
    .
    0-7,32-39,64-71,96-103
    .
    0-1,4-5,64-65,68-69

----
Which is a bit slower than using the mask, but has the benefit of not
needing to handle special cases when matching.

----
First convert /numbits to a mask. Which is the more general case.

    /24 becomes /255.255.255.0

---- perl
my $m = ~0 << 32 - $numbits

----
The initial IP range and mask are then converted to an array of 4 one
byte numbers.

---- perl
[($m & 0xff000000) >> 24,
 ($m & 0x00ff0000) >> 16,
 ($m & 0x0000ff00) >> 8,
 ($m & 0x000000ff) >> 0];

----
For each of the octets of the range, I needed to iterate through all
the possible values. So If the number, x, was 0000 and the mask, m,
was 1100, I would need to iterate:

    0000, 0001, 0010, 0011

If x was 1010 and m was 1001:

    1000, 1010, 1100, 1110

----
The easiest way to do this would be to iterate all numbers

    for ($x & $m .. ($x & $m) + (~$m & 0xff)) {
        next if $_ != $_ & $m;
        ...
    }

----
But that would make too many iterations, 2**(sizeof octet) instead of
2**(number of bits unset in the mask). Which isnt so bad for an octet
of 8 bits but huge if it was a 32 bit number or greater.

----
At first I thought to do it with a recursive subroutine, starting at
bit 8 decrementing and each time the mask was 0 (bit not held constant)
I would branch.

----
But I really wanted to do it with simple bit arithmetic. So I thought
about it for a while...

----
And came up with nothing.

----
So I asked a question on stackoverflow for a good way to do it.

----
And someone pointed to Knuth's "The Art of Computer Programming" volume
4A §7.1.3; see p.150

----
And that described how to count up through a mask.

    i[n] = i[n-1] + m + 1 & ~m
+    i[0] = 0

+Which works because adding the number to the mask and adding 1 skips
over the set bits. Masking the additional bits at the end if the number
carries past.

----
i[0] = 0, m = 0110

+i[n] = i[n-1] + m + 1 & ~m
+i[1] = 0000 + 0110 + 1 & 1001 =  0111 & 1001 = 0001
+i[2] = 0001 + 0110 + 1 & 1001 =  1000 & 1001 = 1000
+i[3] = 1000 + 0110 + 1 & 1001 =  1111 & 1001 = 1001
+i[4] = 1001 + 0110 + 1 & 1001 = 10000 & 1001 = 0000 # done!

----
In my case, the given value of x can be any number, so to drop the number
to the lowest in the range, it needs to be and-ed with the mask.

    x[0] = x[given] & m

----
Calculating the next value becomes:

    x[n] = x[0] + i[n]
+         = x[0] + (i[n-1] + m + 1 & ~m)

----
x[given] = 1100, m = 0110

+x[0] = x[given] & m = 1100 & 0110 = 0100
+x[n] = x[0] + i[n]
+x[1] = x[0] + i[1] = 0100 + 0001 = 0101
+x[2] = x[0] + i[2] = 0100 + 1000 = 1100
+x[3] = x[0] + i[3] = 0100 + 1001 = 1101

----
But that only gave a list of numbers which the IP range could match
against. I wanted to consolidate consecutive numbers.

+To do this I needed the number unset least significant bits before a
set bit in the mask.

----
For example, a mask of 0110 has one unset least significant bit, so it
ranges 2**1, or 2, numbers before it "jumps"

+i = [0000, 0001, 1000, 1001]
   = [0, 1, 8, 9];

----
A mask of 0100 has two unset lsb's, so it ranges 2**2, or 4
numbers before it "jumps".

+i = [0000, 0001, 0010, 0011, 1000, 1001, 1010, 1011]
   = [0, 1, 2, 3, 8, 9, 10, 11];

---- perl

sub n_unset_lsbs {
    my ($m) = @_;
    for (1 .. 8) {
        return $_ - 1 if ~(~0 << $_) & $m;
    }
    8;
}

----
The next value of i is generated from the end of the range of lsb's:

---- perl

sub create_range_from_mask {
    my ($o, $m) = @_;
    my $r = [];
    my $x = $o & $m;
    my $l = n_unset_lsbs($m);
    my $i = 0;
    while (1) {
        my $j = $i + (1 << $l) - 1;
        push @$r, $l ? [$x + $i, $x + $j] : $x + $i;
        $i = $j + $m + 1 & ~$m & 0xff;
        last if !$i;
    }
    $r;
}

----
The library and slides can be found here:

http://10.1.4.65/lab/iprange/

----
== The End