Sequential conversion

This is the procedure "SSE" from sample code.

1. Before we start iterating over dots, we add artificial one to the dot bitmask, after the last character. Thanks to that we can handle all fields in exactly the same way.

   dotmask |= uint16_t(1) << ipv4.size();
   

2. In the next step we repeat the code four times. In each iteration we find the position of the first 1 in the dot mask. It tells us how many digits we have to convert. This is the place where we do additional validation: we check if the number of digits is 1, 2 or 3.

   Depending on the number of digits we use a specialised code path. Each path converts a number, validate its range and update the output word accordingly. We let the compiler to do its best.

   In each step we also shift out the processed bits from the dot mask.

   const uint8_t* data = (const uint8_t*)ipv4.data();
   for (int i=0; i < 4; i++) {
       const int n = __builtin_ctz(dotmask);
   
       switch (n) {
           case 1:
               res.byte[i] = (data[0] - '0');
   
               data += 2;
               dotmask >>= 2;
               break;
   
           case 2:
               {
                   const uint32_t tmp = 10 * (data[0] - '0') + (data[1] - '0');
                   if (tmp < 10) {
                       res.err = errLeadingZeros;
                       return res;
                   }
                   res.byte[i] = tmp;
               }
               data += 3;
               dotmask >>= 3;
               break;
   
           case 3:
               {
                   const uint32_t tmp = 100 * (data[0] - '0') + 10 * (data[1] - '0') + (data[2] - '0');
                   if (tmp > 0xff) {
                       res.err = errTooBig;
                       return res;
                   }
                   if (tmp < 100) {
                       res.err = errLeadingZeros;
                       return res;
                   }
   
                   res.byte[i] = tmp;
               }
   
               data += 4;
               dotmask >>= 4;
               break;
   
           default:
               if (n > 0) {
                   res.err = errTooManyDigits;
               } else {
                   res.err = errEmptyField;
               }
               return res;
       }
   }
   

Unrolled conversion

While we can learn upfront what are widths of all fields, we utilize this fact. For each possible valid combination we pre-compute a specialised path that converts given combination of numbers.

This is the procedure "SSE (v2)" from sample code.

1. As in the previous solution, we add an artificial one to the dot mask, just after the last character.

   dotmask |= uint16_t(1) << ipv4.size();
   

2. Convert from byte mask into 8-bit code. Although there are only 81 valid dot masks, they are stored as variable-length codes. We iterator over fields and encode their lengths on two bits, forming a byte. For our sample IPv4 "195.42.3.0" we have lengths [3, 2, 1, 1] and it's encoded as [0b11, 0b10, 0b01, 0b01] => 0b11100101 = 0xe5.

   In parallel to code building, we validate if all fields have valid lengths (1, 2 or 3 chars).

   const uint8_t* byte = (const uint8_t*)ipv4.data();
   uint8_t code = 0;
   for (int i=0; i < 4; i++) {
       const uint8_t n = __builtin_ctz(dotmask);
       if (n == 0) {
           res.err = errEmptyField;
           return res;
       }
       if (n > 3) {
           res.err = errTooManyDigits;
           return res;
       }
   
       code = (code << 2) | n;
       dotmask >>= n + 1;
   }
   

3. The next step is to use the code value to choose specialised converter. It's a huge switch generated by a program; here we show just a single case.

   uint32_t val0;
   uint32_t val1;
   uint32_t val2;
   uint32_t val3;
   switch (code) {
       // ...
       case 0xe5: // [3, 2, 1, 1]
           tmp = (data[0] - '0');                                  // 3-digit number
           tmp = 10 * tmp + (data[1] - '0');
           tmp = 10 * tmp + (data[2] - '0');
           if (tmp < 100) { res.err = errLeadingZeros; break; }
           if (tmp > 255) { res.err = errTooBig; break; }
           res.byte[0] = tmp;
           res.byte[1]  = 10 * (data[4] - '0') + (data[5] - '0');  // 2-byte number
           if (res.byte[1] < 10) { res.err = errLeadingZeros; break; }
           res.byte[2] = (data[7] - '0');                          // single-digit number
           res.byte[3] = (data[9] - '0');                          // single-digit number
           break;
       // ...
   }
   

Unrolled conversion (group by input length)

The approach is almost exactly as the previous one. The only difference is in how we choose the parsing specialisation.

We're doing that in two steps. First, we use the input length. This already limits the number of possibilities (see the table above). Next, we match the bitpattern as is, without any transcoding.

This is the procedure "SSE (v3)" from sample code.

Below is shown the part of switch that handles pattern [3, 2, 1, 1].

uint32_t tmp;
switch (ipv4.size()) {
    case 7: // 1 case(s)
            // ...
    case 8: // 4 case(s)
            // ...
    case 9: // 10 case(s)
            // ...
    case 10: // 16 case(s)
        switch (dotmask & 0x3ff) {
            // ...
            case 0x148: // [3, 2, 1, 1]
                tmp = (byte[0] - '0');
                tmp = 10 * tmp + (byte[1] - '0');
                tmp = 10 * tmp + (byte[2] - '0');
                if (tmp < 100) { res.err = errLeadingZeros; break; }
                if (tmp > 255) { res.err = errTooBig; break; }
                res.byte[0] = tmp;
                res.byte[1]  = 10 * (byte[4] - '0') + (byte[5] - '0');
                if (res.byte[1] < 10) { res.err = errLeadingZeros; break; }
                res.byte[2] = (byte[7] - '0');
                res.byte[3] = (byte[9] - '0');
                break;
            // ...
        }
        break;
    // ...
}

Selecting procedure

A SIMD conversion procedure requires the following parameters:

• Pattern for the PSHUFB instruction — to layout input in the format required by a conversion procedure.
• Procedure number — a proper conversion procedure id (in practise maximum length of numeric field).
• The exact dot mask, that is compared with the current dot mask to filter out false negatives.

These parameters fit in 20 bytes. When we express the dot mask as a base-3 number or hash function #1, we may have a single array of parameters, having — respectively — 81 or 137 entries.

Procedures "SSE (v5)" and "SSE (v6)" follow the pattern:

hashcode = hash(dotmask)
if (hashcode > max_hashcode) {
    // return error
}
spec = lookup[hashcode]
if (dotmask != spec.expected_dotmask) {
    // return error
}

switch (spec.max_length) {
    case 1:
        res.ipv4 = conversion_max1(spec.pshufb_pattern)
        return res
    case 2:
        res.ipv4 = conversion_max2(spec.pshufb_pattern)
        return res
    case 3:
        res.ipv4 = conversion_max3(spec.pshufb_pattern)
        return res
    default:
        // return error
}

However, when we use hash function #2 which max value is 1228, we use two tables. The first lookup encodes transition from the hash value into length pattern. It should be number from 0 to 80 plus one special value for "not found". The second table of size 82 has actual parameters.

Procedure "SSE (v7)" follows the pattern:

hashcode = hash(dotmask)
if (hashcode > max_hashcode) {
    // return error
}
id = lookup1[hashcode]
if (id == not_found_value) {
    // return error
}
spec = lookup2[id]
if (dotmask != spec.expected_dotmask) {
    // return error
}

switch (spec.max_length) {
    case 1:
        res.ipv4 = conversion_max1(spec.pshufb_pattern)
        return res
    case 2:
        res.ipv4 = conversion_max2(spec.pshufb_pattern)
        return res
    case 3:
        res.ipv4 = conversion_max3(spec.pshufb_pattern)
        return res
    default:
        // return error
}

Conversion of 1-digit numbers

In this case there's no need to validate anything, just pick the bytes from even indices. PSHUFB layouts the input digits in the lower 32-bit word of an SSE register and we simply copy them with single instruction.

const __m128i pattern = _mm_setr_epi8(0, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1);
const __m128i t1 = _mm_shuffle_epi8(t0, pattern);
res.ipv4 = _mm_cvtsi128_si32(t1) & 0x0f0f0f0f;

Conversion of 1- and 2-digit numbers

In this case we have only to check if the 2-digit fields do not contain ASCII '0' on their most significant position. We lay digits in two 32-bit words. The lower one contains the most significant ASCII digits, or value 0 for 1-digit fields. The higher 32-bit word contains the least significant digits.

0. Let's see how we would parse address "12.3.45.6".

   ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
   │..│..│..│..│..│..│..│36│2e│35│34│2e│33│2e│32│31│ = input
   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
    ^                                             ^
    byte 15                                  byte 0
   

1. First, we split the input in the described way.

   const __m128i t1 = _mm_shuffle_epi8(t0, pattern);
   

   ┌───────────────────────┬──┬──┬──┬──┬──┬──┬──┬──┐
   │    unused 64 bits     │  │  │  │  │ 0│34│ 0│31│ = lower 32-bit word
   └───────────────────────┴──┴──┴──┴──┴──┴──┴──┴──┘
   ┌───────────────────────┬──┬──┬──┬──┬──┬──┬──┬──┐
   │    unused 64 bits     │36│35│33│32│  │  │  │  │ = higher 32-bit word
   └───────────────────────┴──┴──┴──┴──┴──┴──┴──┴──┘
   

   The actual byte layout is:

   ┌───────────────────────┬──┬──┬──┬──┬──┬──┬──┬──┐
   │    unused 64 bits     │36│35│33│32│ 0│34│ 0│31│ = t1
   └───────────────────────┴──┴──┴──┴──┴──┴──┴──┴──┘
   

2. Next, compare the t1 vector with ASCII '0' (hex 0x30). We are interested only in the lowest 32-bit result.

   const __m128i ascii0 = _mm_set1_epi8('0');
   const __m128i t2     = _mm_cmpeq_epi8(t1, ascii0);
   

   ┌───────────────────────────────────┬──┬──┬──┬──┐
   │            unused 96 bits         │30│30│30│30│ = ascii0
   └───────────────────────────────────┴──┴──┴──┴──┘
   ┌───────────────────────┬──┬──┬──┬──┬──┬──┬──┬──┐
   │    unused 64 bits     │36│35│33│32│ 0│34│ 0│31│ = t1
   └───────────────────────┴──┴──┴──┴──┴──┴──┴──┴──┘
   ┌───────────────────────────────────┬──┬──┬──┬──┐
   │            unused 96 bits         │00│00│00│00│ = t2 = cmp(ascii0, t1)
   └───────────────────────────────────┴──┴──┴──┴──┘
   

3. As the next step, we extract that lowest word from t2. If it is not zero, that means there is at least one 2-digit field having the leading zero.

   const uint64_t msd = _mm_cvtsi128_si64(t2);
   if (msd != 0) {
       res.err = errLeadingZeros;
       return res;
   }
   

4. Once we know the input is valid, we extract the lower 64 bits from t1 and get back to scalar code. There is simply too few data to use SIMD instructions for that.

   const uint64_t ascii = _mm_cvtsi128_si64(t1);
   const uint64_t w01   = ascii & 0x0f0f0f0f0f0f0f0f;
   const uint32_t w0    = w01 >> 32;
   const uint32_t w1    = w01 & 0xfffffffflu;
   

   ┌──┬──┬──┬──┬──┬──┬──┬──┐
   │36│35│33│32│ 0│34│ 0│31│ = ascii
   └──┴──┴──┴──┴──┴──┴──┴──┘
   ┌──┬──┬──┬──┬──┬──┬──┬──┐
   │ 6│ 5│ 3│ 2│ 0│ 4│ 0│ 1│ = w01
   └──┴──┴──┴──┴──┴──┴──┴──┘
   
               ┌──┬──┬──┬──┐
               │ 6│ 5│ 3│ 2│ = w0
               └──┴──┴──┴──┘
               ┌──┬──┬──┬──┐
               │ 0│28│ 0│ a│ = w1
               └──┴──┴──┴──┘
                   40    10 decimal
   

5. Finally, we convert the individual digits into actual values. We may freely multiply by 10 and add, as we will never get an overflow; the SWAR solution works fine.

   res.ipv4 = 10 * w1 + w0;
   

   ┌──┬──┬──┬──┐
   │ 6│2d│ 3│ c│ = IPv4
   └──┴──┴──┴──┘
   

Conversion of 1-, 2- and 3-digit numbers

In this case we split input into four sets of digits.

0. Let's analyse parsing of "127.45.6.222".

                 2  2  2  .  6  .  5  4  .  7  2  1
   ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
   │..│..│..│..│32│32│32│2e│36│2e│35│34│2e│37│32│31│ = input
   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
    ^                                             ^
    byte 15                                  byte 0
   

1. We split the input into four subwords:

   • digits #0;
   • digits #1 or zero for single-digit numbers;
   • digits #2 or zero for 1- and 2-digit numbers;
   • most significant ASCII digits of 2- and 3-digit numbers, 0 otherwise.

   const __m128i t1 = _mm_shuffle_epi8(t0, pattern);
   

   127.45.6.234
   │││ ││ │ │││
   ││└──┴─┴───┴── digit #0 [7, 5, 6, 4]
   ││  │    ││
   │└──┴─────┴─── digit #1 [2, 4, -, 3]
   │        │
   └────────┴──── digit #2 [1, -, -, 2]
   

   ┌───────────────────────┬──┬──┬──┬──┬──┬──┬──┬──┐
   │                       │  │37│  │35│  │36│  │34│ = digit #0
   └───────────────────────┴──┴──┴──┴──┴──┴──┴──┴──┘
   ┌───────────────────────┬──┬──┬──┬──┬──┬──┬──┬──┐
   │                       │32│  │34│  │ 0│  │33│  │ = digit #1
   └───────────────────────┴──┴──┴──┴──┴──┴──┴──┴──┘
   ┌──┬──┬──┬──┬──┬──┬──┬──┬───────────────────────┐
   │  │31│  │ 0│  │ 0│  │32│                       │ = digit #2
   └──┴──┴──┴──┴──┴──┴──┴──┴───────────────────────┘
   ┌──┬──┬──┬──┬──┬──┬──┬──┬───────────────────────┐
   │31│  │34│  │ 0│  │32│  │                       │ = most significant digits
   └──┴──┴──┴──┴──┴──┴──┴──┴───────────────────────┘
   

   The actual layout after PSHUFB:

   ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
   │31│31│34│ 0│ 0│ 0│32│32│32│37│34│35│ 0│36│33│34│ = t1
   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
   

2. Check if any significant digit is ASCII '0'. We only use the results for odd bytes from the higher half of word t1, thus masking with 0xAA00.

   const __m128i ascii0 = _mm_set1_epi8('0'); // 0x30
   const __m128i eq0    = _mm_cmpeq_epi8(t1, ascii0);
   const uint16_t res   = _mm_movemask_epi8(eq0);
   if ((res & 0xaa00) != 0) {
       // report leading zeros
   }
   

3. Convert from ASCII to digits. It's sufficient to subtract with saturation value 0x30 (ASCII '0').

   const __m128i t2 = _mm_subs_epu8(t1, ascii0);
   

   ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
   │ 1│ 1│ 4│ 0│ 0│ 0│ 2│ 2│ 2│ 7│ 4│ 5│ 0│ 6│ 3│ 4│ = t2
   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
   

4. Then, we calculate 10 * digit #1 + digit #0 in the lower half, and 100 * digit #2. To do this, we use instruction PMADDUBSW that multiplies horizontally bytes and add adjacent results into 16-bit values.

   The multipliers for most significant digits from upper half are set to zero, thanks to that we do not need any extra masking.

   const __m128i weights = _mm_setr_epi8(
       10, 1, 10, 1, 10, 1, 10, 1,     //  10 = 0x0a
       100, 0, 100, 0, 100, 0, 100)    // 100 = 0x64
   
   const __m128i t3 = _mm_maddubs_epi16(t2, weights)
   

   ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
   │ 0│64│ 0│64│ 0│64│ 0│64│ a│ 1│ a│ 1│ a│ 1│ a│ 1│ = weights
   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
   ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
   │ 1│ 1│ 4│ 0│ 0│ 0│ 2│ 2│ 2│ 7│ 4│ 5│ 0│ 6│ 3│ 4│ = t2
   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
   ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
   │  100│    0│    0│  200│   27│   45│    6│   34│ = t3 = maddubs(t2, weights)
   └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘        [shown in decimal]
   

5. Now we have to combine these partial results. Simply shift right the t3 by 8 bytes (with PALIGNR) and add with the original constant of t3.

   const __m128i t4 = _mm_alignr_epi8(t3, 8);
   const __m128i t5 = _mm_add_epi16(t4);
   

   ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
   │  100│    0│    0│  200│   27│   45│    6│   34│ = t3
   └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
   ┌───────────────────────┬─────┬─────┬─────┬─────┐
   │        unused         │  100│    0│    0│  200│ = t4
   └───────────────────────┴─────┴─────┴─────┴─────┘
   ┌───────────────────────┬─────┬─────┬─────┬─────┐
   │        unused         │  127│   45│    6│  234│ = t5 = t3 + t4
   └───────────────────────┴─────┴─────┴─────┴─────┘
                             0x3F  0x2D  0x06  0xEA
   

6. The almost final result is stored in t4 on 16-bit values. We have to check if all are not greater than 255. It's done by a regular comparison.

   const __m128i  gt     = _mm_cmpgt_epi16(t4, _mm_set1_epi16(255));
   const uint16_t gtmask = _mm_movemask_epi8(gt);
   if ((gtmask & 0x00ff) != 0) {
       // report too big fields
   }
   

7. Finally, we need to convert from uint16 to uint8. Since we know the values in t4 fit in a byte, pack with unsigned saturation is sufficient.

   const __m128i t6 = _mm_packus_epi16(t5, t5);
   ipv4 = _mm_cvtsi128_si32(t6);