如何在不使用 Python 中的 ipaddress 模块的情况下检查 IP 地址是否已保留？

问题描述 投票：0回答：3

根据Wikipedia，以下是所有保留的IPv4地址：

RESERVED_IPV4 = [
    '0.0.0.0/8',
    '10.0.0.0/8',
    '100.64.0.0/10',
    '127.0.0.0/8',
    '169.254.0.0/16',
    '172.16.0.0/12',
    '192.0.0.0/24',
    '192.0.2.0/24',
    '192.88.99.0/24',
    '192.168.0.0/16',
    '198.18.0.0/15',
    '198.51.100.0/24',
    '203.0.113.0/24',
    '224.0.0.0/4',
    '233.252.0.0/24',
    '240.0.0.0/4',
    '255.255.255.255/32'
]

我想在不使用

ipaddress
的情况下检查是否保留了任何给定的IP地址，这很简单，我只需要检查它是否属于任何地址范围。

我已经以编程方式将保留网络转换为开始、结束 

int
s 的 IP 对：

RESERVED_IPV4 = [
    (0, 16777215),
    (167772160, 184549375),
    (1681915904, 1686110207),
    (2130706432, 2147483647),
    (2851995648, 2852061183),
    (2886729728, 2887778303),
    (3221225472, 3221225727),
    (3221225984, 3221226239),
    (3227017984, 3227018239),
    (3232235520, 3232301055),
    (3323068416, 3323199487),
    (3325256704, 3325256959),
    (3405803776, 3405804031),
    (3758096384, 4294967295)
]

一个天真的解决方案是检查数字是否落入任何范围，如下所示：

RESERVED_IPV4_RANGES = [range(*e) for e in RESERVED_IPV4]

def is_reserved_range(ip):
    return any(ip in e for e in RESERVED_IPV4_RANGES)

但这是低效的。由于这些是 IP 地址，同一范围内的所有 IP 地址共享相同的二进制前缀：

In [252]: [(f'{a:032b}', f'{b:032b}') for a, b in RESERVED_IPV4]
Out[252]:
[('00000000000000000000000000000000', '00000000111111111111111111111111'),
 ('00001010000000000000000000000000', '00001010111111111111111111111111'),
 ('01100100010000000000000000000000', '01100100011111111111111111111111'),
 ('01111111000000000000000000000000', '01111111111111111111111111111111'),
 ('10101001111111100000000000000000', '10101001111111101111111111111111'),
 ('10101100000100000000000000000000', '10101100000111111111111111111111'),
 ('11000000000000000000000000000000', '11000000000000000000000011111111'),
 ('11000000000000000000001000000000', '11000000000000000000001011111111'),
 ('11000000010110000110001100000000', '11000000010110000110001111111111'),
 ('11000000101010000000000000000000', '11000000101010001111111111111111'),
 ('11000110000100100000000000000000', '11000110000100111111111111111111'),
 ('11000110001100110110010000000000', '11000110001100110110010011111111'),
 ('11001011000000000111000100000000', '11001011000000000111000111111111'),
 ('11100000000000000000000000000000', '11111111111111111111111111111111')]

所以更聪明的方法是检查 IP 地址的二进制表示是否以任何前缀开头：

def longest_common_prefix(a, b):
    short = min(len(a), len(b))
    for i in range(short):
        if a[:i] != b[:i]:
            break
    return a[:i-1] if i else ''

RESERVED_IPV4_PREFIXES = tuple(longest_common_prefix(f'{a:032b}', f'{b:032b}') for a, b in RESERVED_IPV4)

def is_reserved_prefix(ip):
    return f'{ip:032b}'.startswith(RESERVED_IPV4_PREFIXES)

前缀是：

In [253]: RESERVED_IPV4_PREFIXES
Out[253]:
('00000000',
 '00001010',
 '0110010001',
 '01111111',
 '1010100111111110',
 '101011000001',
 '110000000000000000000000',
 '110000000000000000000010',
 '110000000101100001100011',
 '1100000010101000',
 '110001100001001',
 '110001100011001101100100',
 '110010110000000001110001',
 '111')

我已经确认第二种方法比第一种更有效：

In [254]: import random

In [255]: n = random.randrange(2**32)

In [256]: n
Out[256]: 634831452

In [257]: is_reserved_prefix(n)
Out[257]: False

In [258]: is_reserved_range(n)
Out[258]: False

In [259]: %timeit is_reserved_range(n)
1.92 µs ± 56 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [260]: %timeit is_reserved_prefix(n)
734 ns ± 6.59 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

但是它能变得更有效率吗？喜欢直接对 

int
s 使用按位运算吗？我知道如何使用按位运算与 IP 地址相互转换，但我不知道在这种情况下如何使用它们。

我已经确认直接比较

int
s也比智能方法慢：

In [261]: %timeit any(a <= n <= b for a, b in RESERVED_IPV4)
1.71 µs ± 6.31 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

我终于设法使用按位来完成它，但是我不知道为什么这实际上比基于 

str.startswith
的方法慢。最让我困惑的是 
any
实际上比提前返回的 
for
循环慢：

RESERVED_IPV4_MASKS = []

for a, b in RESERVED_IPV4:
    count = b - a + 1
    x = count.bit_length() - 1
    y = 32 - x
    mask = ((1<<y)-1)<<x
    RESERVED_IPV4_MASKS.append((a, mask))

RESERVED_IPV4_MASKS = tuple(RESERVED_IPV4_MASKS)

def is_reserved_mask(ip):
    return any(ip & mask == start for start, mask in RESERVED_IPV4_MASKS)

In [332]: RESERVED_IPV4_MASKS = []
     ...:
     ...: for a, b in RESERVED_IPV4:
     ...:     count = b - a + 1
     ...:     x = count.bit_length() - 1
     ...:     y = 32 - x
     ...:     mask = ((1<<y)-1)<<x
     ...:     RESERVED_IPV4_MASKS.append((a, mask))
     ...:
     ...: RESERVED_IPV4_MASKS = tuple(RESERVED_IPV4_MASKS)

In [333]: def is_reserved_mask(ip):
     ...:     return any(ip & mask == start for start, mask in RESERVED_IPV4_MASKS)

In [334]: %timeit is_reserved_mask(n)
2.12 µs ± 53.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [335]: def is_reserved_mask(ip):
     ...:     for start, mask in RESERVED_IPV4_MASKS:
     ...:         if ip & mask == start:
     ...:             return True
     ...:     return False

In [336]: %timeit is_reserved_mask(n)
1.3 µs ± 97.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

我不知道为什么我的代码没有我想象的那么高效

python python-3.x ip-address
3个回答
1
投票

我过去做过类似的事情。其实两个不同的东西相似：

  1. 使用 IP 地址，我在 IPAM 上工作，我需要手动进行有效检查一个地址或前缀是否在另一个前缀内。

    基于此，我同意您的直觉，原则上按位比较应该是最快的 - 如果我们可以在没有太多 Python 解释器开销的情况下执行这些按位操作。特别是在 CPython 中，你为每个字节码付出了巨大的代价，而像 

    string.startswith
    这样的东西可能完全是用 C 实现的。

  2. 我还必须手动实施一个有效的测试，这对于多前缀

    string.starswith
    很有意义，作为我的
    macaddress
    库如何解析格式的一部分    。

    我提到这个是因为如果我不得不猜测，

    string.startswith
    只是做了我在那里所做的简化版本：检查每个候选人的下一个字符，并扔掉不匹配的候选人 - 如果有足够的候选人为了值得，我们可以先对候选者进行排序，然后对输入中的每个字符进行二进制搜索，以缩小到目前为止匹配的候选者的开始和结束范围。

现在，至于这个：

最让我困惑的是

any
实际上比提前返回的
for
循环慢

这是因为您的 

any
包装了一个 Python 循环（基本上，生成器表达式只是一个包含在隐式生成器函数中的 Python 循环）：

any(ip & mask == start for start, mask in RESERVED_IPV4_MASKS)


any(...)
中的所有内容都支付与您的循环相同的开销，
any
只是为您优化了 
if
和 
break
（您还承担了 Python 的固有开销生成器实现，但相比之下这些可能也相对较小）。

在将测试+解包拉入函数后，您可以尝试用 

map
替换生成器表达式来提高性能。

另外，一个更大的注意事项：如果你需要优化 Python 性能，除非你完全坚持使用 CPython 和解释型 Python 源代码，否则你应该从查看 PyPy 或 Cython 开始——这通常是一种很大的浪费-twiddle Python 源代码，因为您只需将相关的 Python 片段编译为 C 或使用 JiT 优化的 Python 即可获得更大的收益。

0
投票

也许二进制搜索会更快一些。

RESERVED_IPV4 = [
    '0.0.0.0/8',
    '10.0.0.0/8',
    '100.64.0.0/10',
    '127.0.0.0/8',
    '169.254.0.0/16',
    '172.16.0.0/12',
    '192.0.0.0/24',
    '192.0.2.0/24',
    '192.88.99.0/24',
    '192.168.0.0/16',
    '198.18.0.0/15',
    '198.51.100.0/24',
    '203.0.113.0/24',
    '224.0.0.0/4',
    '233.252.0.0/24',
    '240.0.0.0/4',
    '255.255.255.255/32'
]

def ip2int(ip):
    return sum(int(p)<<i for i,p in zip([24,16,8,0],ip.split('.')))

ipRanges = ((ip2int(ip),ip2int(ip)+(1<<int(m))-1) 
            for rip in RESERVED_IPV4 for ip,m in [rip.split("/")])

ipStarts,ipEnds = zip(*sorted(ipRanges))

from bisect import bisect_right
def isReserved(ip):
    intip = ip2int(ip)
    i = max(0,bisect_right(ipStarts,intip)-1)
    return ipStarts[i] <= intip <= ipEnds[i]

输出：

>>> isReserved('10.0.1.23')
False
>>> isReserved('10.0.0.23')
True
-1
投票

如果与网络掩码相加的地址等于起始地址，则该地址被保留。

#!/usr/bin/python3
import sys

RESERVED_IPV4 = [
    '0.0.0.0/8',
    '10.0.0.0/8',
    '100.64.0.0/10',
    '127.0.0.0/8',
    '169.254.0.0/16',
    '172.16.0.0/12',
    '192.0.0.0/24',
    '192.0.2.0/24',
    '192.88.99.0/24',
    '192.168.0.0/16',
    '198.18.0.0/15',
    '198.51.100.0/24',
    '203.0.113.0/24',
    '224.0.0.0/4',
    '233.252.0.0/24',
    '240.0.0.0/4',
    '255.255.255.255/32'
]
def ip_bin( ip:str)->int: # convert address to integer
  parts = ip.split('.')
  b = int( parts[0])
  for i in [1,2,3]:
    b = (b << 8) + int( parts[i])
  return b

unknown = ip_bin( sys.argv[1])
rsvd = True  
for ip_a in RESERVED_IPV4:
  start_a,width_a = ip_a.split( '/') # split in 2 fields
  start = ip_bin( start_a)
  width = int( width_a)
  mask = ((1 << width) -1) << (32-width) # build network mask
  if (unknown & mask) == start: break
else:
  rsvd = False

print( "rsvd is", rsvd)
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.