Daniel Lemire's blog

, 9 min read

Parsing IP addresses crazily fast

12 thoughts on “Parsing IP addresses crazily fast”

  1. wieschade says:

    Worth to mention. There are several IPv4 notations.

    For example:

    $ ping 0300.0250.1.0376
    PING 0300.0250.1.0376 (192.168.1.254) 56(84) bytes of data.
    …

    That’s the reason why inet_pton checks “IPv4 field has octet with leading zero” condition.

    1. Daniel Lemire says:

      I am benchmarking against the standard function inet_pton which does not support these variations.

      Our URL parsing library supports all of these variations, and IPv6 as well.

  2. Ralph Corderoy says:

    Just to point out that inet_pton() differs from inet_addr() in that the latter accepts more formats. inet_ntop(3p) spells that out. This is why one can ping 127.1, ping 0x8080808, or ping 2130706433. Callers of sse_inet_aton() need to be certain their inputs are compatible, especially if taking IP addresses from external users.

    1. Daniel Lemire says:

      The documentation of inet_pton is as follows:

      src points to a character string containing an IPv4 network address in
      dotted-decimal format, “ddd.ddd.ddd.ddd”, where ddd is a decimal
      number of up to three digits in the range 0 to 255.

      I tested on both macOS and Linux, and inet_pton cannot parse 0x8080808. You can verify yourself by running this program:

      #include <stdio.h>
#include <arpa/inet.h>

      int main(int argc, char **arg) {
char buf[4];
printf("%d\n", inet_pton(AF_INET, "127.0.1.1", buf));
printf("%d\n", inet_pton(AF_INET, "127.1", buf));
printf("%d\n", inet_pton(AF_INET, "0x8080808", buf));
printf("%d\n", inet_pton(AF_INET, "2130706433", buf));
}

      If you run this program, you get 1 (success), 0 (failure), 0 (failure), and 0 (failure). Meaning that only “127.0.1.1” is recognized as a valid address.

      1. Ralph Corderoy says:

        Hi Daniel, you have misread my comment: I never claimed inet_pton() can parse 0x8080808. I’m pointing out it can’t.

        1. Daniel Lemire says:

          I was actually not arguing “against you”. I was just clarifying what the function does, for the benefit of the readers.

  3. Sig-I/O says:

    IP addresses can also be IPv6…. or in IPv6 notation while being IPv4… So be wary of this 😉
    ::ffff:12.34.56.78

    1. Daniel Lemire says:

      Yes, my code does not support IPv6 or uncommon IPv4 formats. It is equivalent to “inet_pton(AF_INET,…)”.

  4. aqrit says:

    Has this been tested exhaustively?

    If the perfect hash function hashes an invalid string to one of the valid entries…
    then the shuffle would discard bytes without them ever being validated?

    1. Daniel Lemire says:

      We have checks in place to verify that the string length is as expected.

    2. Daniel Lemire says:

      Of course, bugs are always possible.

  5. Alex Porter says:

    I think there are some opportunities for optimizing the performance of what you have already.

    For string loading, the string length isn’t strictly necessary as long as it’s a null terminated string by comparing to 0 doing _mm_movemask_epi8 and then leading zero count.

    I’m sure your hashing algorithm could be improved to include the string length, since there are only so many options, given a dotmask.

    Lines 189 – 196 can be simplified by just checking no value is greater than 9, since any other value that has ‘0’ subtracted from it will be greater than 9 by either wrapping around or by having an ascii code greater than ‘9’.

    Lines 175 through 182 and 198 through 209 can be simplified by re-arranging the weights to be in most-significant to least-significant order and leaving a gap for each octet like such: (100, 10, 0, 1). This obviates the restriction on leading zero digits. After this, use _mm256_maddubs_epi16 as before, but replace everything after with _mm256_hadd_epi16 and _mm_shuffle_epi8 to move the proper bytes to the least significant i32 for use with _mm_cvtsi128_si32.

    I’m certainly no CS professor, so I could be way off on some of these things, but I wanted to take a crack at learning about SIMD and seeing if I could identify and areas for improvement.

    Thanks!