perlbinaryopenvswitch

Create collection of bitwise matches from an integer range


The OVS documentation

... describes populating rules in the following format:

Range matches can be expressed as a collection of bitwise matches. For example, suppose that the goal is to match TCP source ports 1000 to 1999, inclusive. The binary representations of 1000 and 1999 are:

01111101000
11111001111

The following series of bitwise matches will match 1000 and 1999 and all the values in between:

01111101xxx
0111111xxxx
10xxxxxxxxx
110xxxxxxxx
1110xxxxxxx
11110xxxxxx
1111100xxxx

which can be written as the following matches:

tcp,tp_src=0x03e8/0xfff8
tcp,tp_src=0x03f0/0xfff0
tcp,tp_src=0x0400/0xfe00
tcp,tp_src=0x0600/0xff00
tcp,tp_src=0x0700/0xff80
tcp,tp_src=0x0780/0xffc0
tcp,tp_src=0x07c0/0xfff0

I'm trying to determine the correct way to generate those matches based on a minimum and maximum integer value in perl. I looked at the module Bit::Vector , but I wasn't able to figure out how to effectively use it for this purpose.


Solution

  • Let's pretend we trying to solve the equivalent problem for decimal for a second.

    Say you want 567 (inclusive) to 1203 (exclusive).

    1. Enlarging phase
      1. You increment by 1 until you have the a multiple of 10 or you would exceed the range.
        1. ⇒598 (Creates 597-597)
        2. ⇒599 (Creates 598-598)
        3. ⇒600 (Creates 599-599)
      2. You increment by 10 until you have a multiple of 100 or you would exceed the range.
      3. You increment by 100 until you have a multiple of 1000 or you would exceed the range.
        1. ⇒700 (Creates 600-699)
        2. ⇒800 (Creates 700-799)
        3. ⇒900 (Creates 800-899)
        4. ⇒1000 (Creates 900-999)
      4. You increment by 1000 until you have a multiple of 10000 or you would exceed the range.
        1. [Would exceed limit]
    2. Shrinking phase
      1. You increment by 100 until you would exceed the range.
        1. ⇒1100 (Creates 1000-1099)
        2. ⇒1200 (Creates 1100-1199)
      2. You increment by 10 until you would exceed the range.
      3. You increment by 1 until you would exceed the range.
        1. ⇒1201 (Creates 1200-1200)
        2. ⇒1202 (Creates 1201-1201)
        3. ⇒1203 (Creates 1202-1202)

    Same in binary, but with powers of 2 instead of powers of 10.

    my $start = 1000;
    my $end   = 1999 + 1;
    
    my @ranges;
    
    my $this = $start;
    my $this_power = 1;
    OUTER: while (1) {
       my $next_power = $this_power * 2;
       while ($this % $next_power) {
          my $next = $this + $this_power;
          last OUTER if $next > $end;
    
          my $mask = ~($this_power - 1) & 0xFFFF;
          push @ranges, sprintf("0x%04x/0x%x", $this, $mask);
          $this = $next;
       }
    
       $this_power = $next_power;
    }
    
    while ($this_power > 1) {
       $this_power /= 2;
       while (1) {
          my $next = $this + $this_power;
          last if $next > $end;
    
          my $mask = ~($this_power - 1) & 0xFFFF;
          push @ranges, sprintf("0x%04x/0x%x", $this, $mask);
          $this = $next;
       }
    }
    
    say for @ranges;
    

    We can optimize that by taking advantage of the fact that we're dealing with binary.

    my $start = 1000;
    my $end   = 1999 + 1;
    
    my @ranges;
    
    my $this = $start;
    my $power = 1;
    my $mask = 0xFFFF;
    while ($start & $mask) {
       if ($this & $power) {
          push @ranges, sprintf("0x%04x/0x%x", $this, $mask);
          $this += $power;
       }
    
       $mask &= ~$power;
       $power <<= 1;
    }
    
    while ($end & ~$mask) {
       $power >>= 1;
       $mask |= $power;
    
       if ($end & $power) {
          push @ranges, sprintf("0x%04x/0x%x", $this, $mask);
          $this |= $power;
       }
    }
    
    say for @ranges;
    

    Output:

    0x03e8/0xfff8
    0x03f0/0xfff0
    0x0400/0xfe00
    0x0600/0xff00
    0x0700/0xff80
    0x0780/0xffc0
    0x07c0/0xfff0