从整数范围创建按位匹配的集合

Question

OVS文档

...以下列格式描述填充规则:

范围匹配可以表示为按位匹配的集合.例如,假设目标是匹配TCP源端口1000到1999(包括端点).1000和1999的二进制表示是:

01111101000
11111001111

以下一系列按位匹配将匹配1000和1999以及它们之间的所有值:

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

可以写成以下匹配:

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

我正在尝试根据perl中的最小和最大整数值来确定生成这些匹配的正确方法.我查看了模块Bit :: Vector,但我无法弄清楚如何有效地将它用于此目的.

Answer 1

让我们假设我们试图解决十进制的等效问题一秒钟.

假设你想要567(含)到1203(独家).

1. 扩大阶段
   1. 你增加1直到你得到10的倍数,否则你会超出范围.
      1. ⇒598(创建597-597)
      2. ⇒599(创建598-598)
      3. ⇒600(创建599-599)
   2. 你增加10,直到你有100的倍数或你会超出范围.
   3. 你增加100,直到你有1000的倍数或你会超出范围.
      1. ⇒700(创建600-699)
      2. ⇒800(创建700-799)
      3. ⇒900(创建800-899)
      4. ⇒1000(创建900-999)
   4. 您增加1000,直到您有10000的倍数或超出范围.
      1. [超出限制]
2. 缩小阶段
   1. 您将增加100,直到超出范围.
      1. ⇒1100(创建1000-1099)
      2. ⇒1200(创建1100-1199)
   2. 您将增加10,直到超出范围.
   3. 您将增加1,直到超出范围.
      1. ⇒1201(创建1200-1200)
      2. ⇒1202(创建1201-1201)
      3. ⇒1203(创建1202-1202)

二进制相同,但功率为2而不是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;

我们可以通过利用我们处理二进制的事实来优化它.

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;

输出:

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