---- config title: Bit Hacks on IP Ranges indent: 4 height: 18 width: 52 skip: 0 ---- center Bit Hacks on IP Ranges by Jake Gelbman ---- center IP::Range specification ---- center 1.2.3.5 ---- center 1.2.3.5,105,205 ---- center 1.2.3.5-55 ---- center 1.2.3.- ---- center 1.2.3.5 8.13.21.34 ---- center 1.2.3.4/24 ---- center 1.2.3.4/255.255.255.0 ---- center Just like nmap(1) ---- 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"); ---- perl $r->match("1.2.3.4"); # Nope $r->match("1.7.21.34"); # Yeah! ---- 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 ---- center 1.2.3.5/24 1.2.3.5/255.255.255.0 Needs to be handled specially, unless... ---- center 1.2.3.5/28 to 1.2.3.0-15 ---- center 1.2.3.5/255.255.255.0 to 1.2.3.- ---- center 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 ---- * Slower * Doesn't need special cases ---- center First convert /numbits to mask /24 becomes /255.255.255.0 ---- perl $m = ~0 << 32 - $numbits ---- perl [($m & 0xff000000) >> 24, ($m & 0x00ff0000) >> 16, ($m & 0x0000ff00) >> 8, ($m & 0x000000ff) >> 0]; ---- center Need to iterate through all possible values of the mask. e.g.,... ---- center x[given] = 0000 m = 1100 ---- center x[given] = 0000 m = 1100 0000 ---- center x[given] = 0000 m = 1100 0000, 0001 ---- center x[given] = 0000 m = 1100 0000, 0001, 0010 ---- center x[given] = 0000 m = 1100 0000, 0001, 0010, 0011 ---- center x[given] = 1010 m = 1001 ---- center x[given] = 1010 m = 1001 1000 ---- center x[given] = 1010 m = 1001 1000, 1010 ---- center x[given] = 1010 m = 1001 1000, 1010, 1100 ---- center x[given] = 1010 m = 1001 1000, 1010, 1100, 1110 ---- Naive for (0 .. 255) { next if $_ != $_ & $m; ... } +Too slow! ---- center Recursive subroutine? +Too complicated! ---- center Bit arithmetic ---- center And came up with nothing. ---- center Stackoverflow ---- center Knuth's "The Art of Computer Programming" volume 4A ยง7.1.3; p.150 ---- center Iterate through a mask. ---- i[n] = i[n-1] + m + 1 & ~m + i[0] = 0 ---- center i[n] = i[n-1] + m + 1 & ~m m = 0110 ---- 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. ---- center 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 ---- center Ranges? +function(unset least significant bits in 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; } ---- i (start of range) j (end of range) l (n unset lsb's) j = i + (1 << l) - 1 ---- perl sub create_range_from_mask { my ($x_given, $m) = @_; my @r; my $x = $x_given & $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 Convert from range to a mask? Combining ranges with range generated from mask?