Re: Improving address exclusion matching

On Thu, Nov 01, 2018 at 12:35:30AM -0500, Daniel Miller wrote:
> The new system uses a radix tree, or "trie," data structure, where each node
> represents an address prefix. Comparison is done using bitwise operations to
> mask off the less-significant portion of the address and compare only the
> relevant portion. When a prefix matches, the next bit of the candidate address
> after the prefix determines which branch of the tree to descend. Some branches
> are dead-ends: the candidate doesn't match and can be scanned. Others are
> always-match nodes, caused when an exclusion specification had a CIDR-style
> netmask like [2]192.168.0.0/24. In all, a worst-case maximum of 128
> "comparisons" is done for any given IPv6 address (32 for IPv4), no matter how
> many excluded addresses are provided.

That's great! Nice work.
_______________________________________________
Sent through the dev mailing list
https://nmap.org/mailman/listinfo/dev
Archived at http://seclists.org/nmap-dev/