Gather-based

Since AVX512F lacks of byte-level shuffling, loading data can be accomplished with a gather instruction. The gather does a parallel lookup in given table, indices are stored in vector's elements. Gather is significantly faster than individual loads, especially when it touches a small number of cache lines. In this case single gather would touch at most two cache lines.

An input is sequence 48 bytes, or twelve 32-bit lanes. The layout of an input:

[PPPO|OONN|NMMM|LLLK|KKJJ|JIII|HHHG|GGFF|FEEE|DDDC|CCBB|BAAA]
  11   10    9    8    7    6    5    4    3    2    1    0

The result vector's layout:

[.PPP|.OOO|.NNN|.MMM|.LLL|.KKK|.JJJ|.III|.HHH|.GGG|.FFF|.EEE|.DDD|.CCC|.BBB|.AAA]
  15   14   13   12   11   10    9    8    7    6    5    4    3    2    1    0

The 4th byte of each lane is not important.

Vector of indices contains a sequence of multiplies of 3: [0, 3, 6, 9, 12, ... and so on]. Loading data is then performed by a single instruction; please note that the last argument of _mm512_i32gather_epi32, scale, is 1.

static const uint32_t input_offsets[16] = {
     0*3,  1*3,  2*3,  3*3,
     4*3,  5*3,  6*3,  7*3,
     8*3,  9*3, 10*3, 11*3,
    12*3, 13*3, 14*3, 15*3
};

const __m512i input_gather = _mm512_loadu_si512(reinterpret_cast<const __m512i*>(input_offsets));

for (...) {
        const __m512i in = _mm512_i32gather_epi32(input_gather, (const int*)(input), 1);

        // ...
}

Vectorized approach

Although the gather-based loading is pretty simple and straightforward, the instruction's latency is really huge — it's 15 cycles.

A vectorized approach loads 64 bytes, where only 48 bytes are used, and performs all shifting and shuffling within registers. AVX512F offers shuffling instruction vpermd (_mm512_permutexvar_epi32), which works at 32-bit words level and can move words across lanes.

The algorithm:

1. Load 64 bytes:

   [PPPO|OONN|NMMM|LLLK|KKJJ|JIII|HHHG|GGFF|FEEE|DDDC|CCBB|BAAA]
     11   10    9    8    7    6    5    4    3    2    1    0
   

   The 48-byte array could be split into four 12-byte subarrays:

   t1 = [D2 D1 D0 C2|C1 C0 B2 B1|B0 A2 A1 A0] x 4
           word 2      word 1      word 0
   
               12-byte subarray
   

2. Each 12-byte array is then placed in a separate 128-bit lane. This is done by _mm512_permutexvar_epi32. Note the order of words: 0, 1, 1, 2.

   t2 = [D2 D1 D0 C2|C1 C0 B2 B1|C1 C0 B2 B1|B0 A2 A1 A0] x 4
   

3. Shift bytes C right by 16 bits (_mm512_mask_srli_epi64). Now bytes A and C are at correct places.

   t3 = [.. .. D2 D1|D0 C2 C1 C0|C1 C0 B2 B1|B0 A2 A1 A0] x 4
   

4. Shift bytes D and B left by 8 bit (_mm512_slli_epi64). And now these bytes are also at the correct position.

   t4 = [.. D2 D1 D0|C2 C1 C0 ..|C0 B2 B1 B0|A2 A1 A0 ..] x 4
   

5. Merge results from 3rd and 4th steps (_mm512_ternarylogic_epi32). The 3rd byte of each word will be omitted by a lookup procedure, thus no masking is needed.

   t5 = [.. D2 D1 D0|.. C2 C1 C0|C0 B2 B1 B0|.. A2 A1 A0] x 4
   

An excerpt from sample code.

const __m512i tmp1 = _mm512_loadu_si512(input + i);
const __m512i tmp2 = _mm512_permutexvar_epi32(
    _mm512_set_epi32(11, 10, 10, 9, 8, 7, 7, 6, 5, 4, 4, 3, 2, 1, 1, 0),
    tmp1
);
const __m512i tmp3 = _mm512_mask_srli_epi64(tmp2, 0xaa, tmp2, 16);
const __m512i tmp4 = _mm512_slli_epi64(tmp3, 8);
const __m512i tmp5 = _mm512_ternarylogic_epi64(_mm512_set1_epi64(0x00ffffff), tmp4, tmp3, BIT_MERGE);

Introduction

A lookup procedure considers five ranges assigned to characters: 'A'-'Z', 'a'-'z', '0'-'9', '+' and '/'. The procedure associates a range with shift value, a constant that added to the input value gives a proper ASCII code.

The simplest algorithm incrementally calculates shift, pseudocode shows the idea.

char lookup(uint8_t i) {

    uint8_t shift = 'A';

    shift ^= mask_7bit(i >= 26) & 6;
    shift ^= mask_8bit(i >= 52) & 187;
    shift ^= mask_7bit(i >= 62) & 17;
    shift ^= mask_7bit(i >= 63) & 29;

    return (shift + i) & 0xff; // add modulo 256
}

SWAR notes

The elementary operation is building a mask according to comparison result, the methods to do this are described earlier.

As we see, masks for all but one constants can be 7-bit. However, we could split constant 187 into MSB and lower part. The lower part contributes in shift, while the MSB will be used to adjust sum shift + i. This solution has one important advantage, the sum would never wrap, and plain addition can be used.

Pseudocode

Rewritten algorithm.

char lookup(uint8_t i) {

    uint8_t shift = 'A';

    shift  ^= mask_7bit(i >= 26) & 6;
    shift  ^= mask_7bit(i >= 62) & 17;
    shift  ^= mask_7bit(i >= 63) & 29;

    cmp_MSB = MSB(i >= 52);
    mask    = MSB - (MSB >> 7); // inlined mask_7bit

    // Note: order of updating shift isn't important
    shift  ^= mask & 59; // 187 & 0x7f

    uint8_t sum = shift + i;

    return sum ^ cmp_MSB;
}

C++ implementation

const uint8_t XOR_ALL = 0x96;

__m512i lookup_incremental_logic(const __m512i in) {

    __m512i shift = packed_byte('A');
    __m512i c0, c1, c2, c3;
    const __m512i MSB = packed_byte(0x80);

    // shift ^= cmp(i >= 26) & 6;
    c0 = _mm512_and_si512(_mm512_add_epi32(in, packed_byte(0x80 - 26)), MSB);
    c0 = _mm512_sub_epi32(c0, _mm512_srli_epi32(c0, 7));
    c0 = _mm512_and_si512(c0, packed_byte(6));

    // shift ^= cmp(i >= 52) & 187;
    c1 = _mm512_and_si512(_mm512_add_epi32(in, packed_byte(0x80 - 52)), MSB);
    const __m512i c1msb = c1;
    c1 = _mm512_sub_epi32(c1, _mm512_srli_epi32(c1, 7));
    c1 = _mm512_and_si512(c1, packed_byte(187 & 0x7f));

    // shift ^= cmp(i >= 62) & 17;
    c2 = _mm512_and_si512(_mm512_add_epi32(in, packed_byte(0x80 - 62)), MSB);
    c2 = _mm512_sub_epi32(c2, _mm512_srli_epi32(c2, 7));
    c2 = _mm512_and_si512(c2, packed_byte(17));

    // shift ^= cmp(i >= 63) & 29;
    c3 = _mm512_and_si512(_mm512_add_epi32(in, packed_byte(0x80 - 63)), MSB);
    c3 = _mm512_sub_epi32(c3, _mm512_srli_epi32(c3, 7));
    c3 = _mm512_and_si512(c3, packed_byte(29));

    shift = _mm512_ternarylogic_epi32(shift, c0, c1, XOR_ALL);
    shift = _mm512_ternarylogic_epi32(shift, c2, c3, XOR_ALL);

    // produce the result
    return _mm512_xor_si512(_mm512_add_epi32(in, shift), c1msb);
}

Number of constants: 10.

Number of instructions:

• bit-and: 8
• bit-xor: 1
• ternary: 2
• add/sub: 9
• shift: 4

Total 24 instructions.

Improved C++ implementation

An expression like shift ^= cmp(...) & const might be expressed with ternary logic. This transformation makes the above procedure slightly shorter, four bit-ands are replaced with two ternary logic instructions.

__m512i lookup_incremental_logic_improved(const __m512i in) {

    using namespace avx512f_swar;

    __m512i shift;
    __m512i c0, c1, c2, c3;
    const __m512i MSB = packed_byte(0x80);

    /*
        s m c | shift ^ (mask & constant)
        ------+--------------------------
        0 0 0 | 0
        0 0 1 | 0
        0 1 0 | 0
        0 1 1 | 1
        1 0 0 | 1
        1 0 1 | 1
        1 1 0 | 1
        1 1 1 | 0 -> 0x78
    */
    const uint8_t XOR_AND = 0x78;

    // shift ^= cmp(i >= 26) & 6;
    // shift ^= cmp(i >= 52) & 187;
    // shift ^= cmp(i >= 62) & 17;
    // shift ^= cmp(i >= 63) & 29;

    c0 = _mm512_cmpge_mask7bit(in, packed_byte(0x80 - 26));
    c1 = _mm512_and_si512(_mm512_add_epi32(in, packed_byte(0x80 - 52)), MSB);
    const __m512i c1msb = c1;
    c1 = _mm512_sub_epi32(c1, _mm512_srli_epi32(c1, 7));
    c2 = _mm512_cmpge_mask7bit(in, packed_byte(0x80 - 62));
    c3 = _mm512_cmpge_mask7bit(in, packed_byte(0x80 - 63));

    shift = _mm512_ternarylogic_epi32(packed_byte('A'), c0, packed_byte(6), XOR_AND);
    shift = _mm512_ternarylogic_epi32(shift, c1, packed_byte(187 & 0x7f), XOR_AND);
    shift = _mm512_ternarylogic_epi32(shift, c2, packed_byte(17), XOR_AND);
    shift = _mm512_ternarylogic_epi32(shift, c3, packed_byte(29), XOR_AND);

    // produce the result
    return _mm512_xor_si512(_mm512_add_epi32(in, shift), c1msb);
}

Introduction

The vectorized lookup uses in fact the linear search, but a kind of binary search can be used:

• In the first step we select if an input byte belongs to "letters" group ('A'-'Z' or 'a'-'z'), or to "digits" group ('0'-'9', '+' and '/'). At this step we select both shift value and comparison value for the next step.
• In the second step the input is compared with value selected in the previous step. At this point we exactly know if input byte should be mapped to 'A'-'Z', 'a'-'z', '0'-'9' or one of '+' or '/'.
• The last step is used to properly select shift value for '+' and '/' chars.

Pseudocode for scalar inputs shows the idea.

char lookup(uint8_t i) {

    uint8_t shift = 0;
    uint8_t value = 0;

    // 1st step
    if (x >= 52) {
        // 0-9, + or /
        shift  = '0' - 52;
        value  = 62;
        shift2 = '+' - 62;
    } else {
        // A-Z or a-z
        shift  = 'A';
        value  = 26;
        shift2 = 'a' - 26;
    }

    // 2nd step
    if (i >= value) {
        shift = shift2;
    }

    // 3rd step: fixup for /
    uint8_t mask;
    if (i == 63)
        mask = 29;
    else
        mask = 0;

    shift ^= mask;

    // produce result: add modulo the input and the shift
    shift06 = shift & 0x7f
    shift7  = shift & 0x80

    return (i + shift06) ^ shift7;
}

C++ implementation

The C++ implementation simply replaces all ifs with merge operations.

const uint8_t BIT_MERGE = 0xca;

__m512i lookup_binary_search(const __m512i in) {

    using namespace avx512f_swar;

    __m512i cmp1_mask;
    __m512i shift;
    __m512i shift_step2;
    __m512i cmp2_mask;
    __m512i cmp2_value;
    __m512i cmp_63_mask;


    // 1st step

    // cmp1_mask   = cmp(i >= 52)
    // shift       = bit_merge(cmp1_mask, '0' - 52, 'A')
    // cmp2_value  = bit_merge(cmp1_mask, 62, 26)
    // shift_step2 = bit_merge(cmp1_mask, '+' - 62, 'a' - 26)

    cmp1_mask      = _mm512_cmpge_mask8bit(in, packed_byte(0x80 - 52));
    shift          = _mm512_ternarylogic_epi32(cmp1_mask, packed_byte('0' - 52), packed_byte('A'), BIT_MERGE);
    cmp2_value     = _mm512_ternarylogic_epi32(cmp1_mask, packed_byte(0x80 - 62), packed_byte(0x80 - 26), BIT_MERGE);
    shift_step2    = _mm512_ternarylogic_epi32(cmp1_mask, packed_byte('+' - 62), packed_byte('a' - 26), BIT_MERGE);

    // 2nd step

    // cmp2_mask   = cmp(i >= cmp_value)
    // shift       = bit_merge(cmp2_mask, shift, shift_step2)

    cmp2_mask      = _mm512_cmpge_mask8bit(in, cmp2_value);
    shift          = _mm512_ternarylogic_epi32(cmp2_mask, shift_step2, shift, BIT_MERGE);

    // 3rd step

    // cmp_63_mask = cmp(i >= 63)
    // shift       = shift ^ (cmp_63_mask & 29)
    cmp_63_mask    = _mm512_cmpge_mask7bit(in, packed_byte(0x80 - 63));
    shift          = _mm512_ternarylogic_epi32(shift, cmp_63_mask, packed_byte(29), 0x78);

    // add modulo 256
    return _mm512_add_epu8(in, shift);
}

Number of constants: 10.

Number of instructions:

• bit-and: 4
• bit-xor: 0
• bit-or: 2
• ternary: 6
• add/sub: 7
• shift: 3

Total 22 instructions.

Introduction

Unlike encoding, decoding has to care about input's validity. However, the scheme of decoding is similar to encoding: depending on byte range (A-Z, a-z, 0-9, + or /) a shift value is selected and the shift is added to byte forming a 6-bit value. If a byte doesn't match any range, then shift value is zero, denoting an invalid input.

Very important observation is that a valid input can't contains any extended ASCII characters, i.e. bytes should be less than 0x80. Before doing a lookup procedure the input bytes are reduced to 7-bit value. This leads to simpler code, as SWAR procedures don't have to deal with full 8-bit numbers. Information about invalid, extended ASCII chars is used during a validation step.

Pseudocode for decoding summing up the above observations.

uint8_t decode_byte(uint8_t byte)

    uint8_t shift = 0;          // invalid value

    input = byte & 0x7f;        // reducing range to 0..0x7f

    if (input >= 'A' && input <= 'Z')
        shift = -65;

    if (input >= 'a' && input <= 'z')
        shift = -71;

    if (input >= '0' && input <= '9')
        shift = 4;

    if (input == '+')
        shift = 19;

    if (input == '/')
        shift = 16;

    if (shift == invalid || (byte & 0x80))
        // an invalid byte or an extended ASCII char
        report error

    // sum modulo 256, as shift can be less than 0
    return (byte + shift) & 0xff;
}

SWAR notes

One of the most important part of procedure is range checking. Since we know how to express the relation >=, the range checking could be replaced with:

if (byte >= lo && !byte >= hi)
    // ...

This involves two additions and one and-not operation, followed by mask forming. And since building mask requires MSB value, we can use ternary logic to do all needed binary operations in one instruction:

const __m512i L = _mm512_add_epi32(a, packed_byte(lo));
const __m512i H = _mm512_add_epi32(a, packed_byte(hi));

// MSB = L & ~H & 0x80
const __m512i MSB = _mm512_ternarylogic_epi32(packed_byte(0x80), H, L, 0x20);

Equality comparison (required for chars '+' and '/') has surprisingly the same complexity as range checking, so the latter operation is used.

Adding shift and input uses arithmetic modulo 256.

Pseudocode

uint8_t decode_byte(uint8_t byte) {

    uint8_t shift = 0;

    input    = byte & 0x7f;        // reducing range to 0..0x7f

    // determine shift
    mask1    = mask_8bit(input >= 'A' && !input >= 'Z' + 1)
    range_AZ = mask1 & -65;

    mask2    = mask_8bit(input >= 'a' && !input >= 'z' + 1)
    range_az = mask2 & -71;

    MSB      = mask_1bit(input >= '0' && !input >= '9' + 1)
    range_09 = MSB >> 5; // value 4

    mask3    = mask_7bit(input >= '+' && !input >= '+' + 1)
    plus     = mask3 & 19;

    mask4    = mask_7bit(input >= '/' && !input >= '/' + 1)
    slash    = mask4 & 16;

    shift   = range_AZ | range_az | range_09 | plus | slash;

    // addition modulo 256
    shift06 = shift & 0x7f;
    shift7  = shift & 0x80;
    result  = (byte + shift) ^ shift7;

    // valid iff: shift is non-zero, input's MSB is zero

    non_zero_shift_7lower = shift06 + 0x7f;
    non_zero_shift_MSB    = shift7;

    valid = (non_zero_shift_7lower | non_zero_shift_MSB) & ~input

    if (valid & 0x80 != 0x80) {
        // invalid byte or extended ASCII char
        report error
    }

    return result;
}

C++ implementation

The vectorized version of pseudocode, most binary operations were expressed with ternary logic instructions:

__m512i lookup_comparisons(const __m512i input) {

    const __m512i in = _mm512_and_si512(input, packed_byte(0x7f));

    #define GET_RANGE_SHIFT_7BIT(shift, lo, hi) \
    _mm512_and_si512(packed_byte(uint8_t(shift)), \
                     _mm512_range_mask_7bit(in, packed_byte(0x80 - (lo)), packed_byte(0x80 - (hi))))

    #define GET_RANGE_SHIFT_8BIT(shift, lo, hi) \
    _mm512_and_si512(packed_byte(uint8_t(shift)), \
                     _mm512_range_mask_8bit(in, packed_byte(0x80 - (lo)), packed_byte(0x80 - (hi))))

    #define GET_RANGE_SHIFT_3RD_BIT(lo, hi) \
    _mm512_range_3rd_bit(in, packed_byte(0x80 - (lo)), packed_byte(0x80 - (hi)))


    const __m512i range_AZ   = GET_RANGE_SHIFT_8BIT   (-65, 'A', 'Z' + 1);
    const __m512i range_az   = GET_RANGE_SHIFT_8BIT   (-71, 'a', 'z' + 1);
    const __m512i range_09   = GET_RANGE_SHIFT_3RD_BIT('0', '9' + 1);
    const __m512i char_plus  = GET_RANGE_SHIFT_7BIT   (19, '+', '+' + 1);
    const __m512i char_slash = GET_RANGE_SHIFT_7BIT   (16, '/', '/' + 1);

    // shift = range_AZ | range_az | range_09 | char_plus | char_slash
    const uint8_t OR_ALL  = 0xfe;
    const __m512i tmp     = _mm512_ternarylogic_epi32(range_AZ, range_az, range_09, OR_ALL);
    const __m512i shift   = _mm512_ternarylogic_epi32(char_plus, char_slash, tmp,   OR_ALL);

    // (shift + input) & 0xff
    const __m512i shift06 = _mm512_and_si512(shift, packed_byte(0x7f));
    const __m512i shift7  = _mm512_and_si512(shift, packed_byte(0x80));
    const __m512i result  = _mm512_xor_si512(_mm512_add_epi32(in, shift06), shift7);

    // validation
    const __m512i non_zero_7lower = _mm512_add_epi32(shift06, packed_byte(0x7f));
    const __m512i MSB = packed_byte(0x80);
    const __m512i valid = _mm512_ternarylogic_epi32(non_zero_7lower, shift, input, 0x54);

    const auto mask = _mm512_cmpneq_epi32_mask(MSB, _mm512_and_si512(valid, MSB));
    if (mask) {
        report_exception(input);
    }

    return result;
}

And SWAR procedures for mask calculations:

// returns packed (a[i] >= lo and a[i] <= hi) ? 0x7f : 0x00;
__m512i _mm512_range_mask_7bit(const __m512i a, const __m512i lo, const __m512i hi) {

    const __m512i L = _mm512_add_epi32(a, lo);
    const __m512i H = _mm512_add_epi32(a, hi);

    // MSB = L & ~H & 0x80
    const __m512i MSB = _mm512_ternarylogic_epi32(packed_byte(0x80), H, L, 0x20);

    // MSB - (MSB >> 7)
    return _mm512_sub_epi32(MSB, _mm512_srli_epi32(MSB, 7));
}

// returns packed (a[i] >= lo and a[i] <= hi) ? 0xff : 0x00;
__m512i _mm512_range_mask_8bit(const __m512i a, const __m512i lo, const __m512i hi) {

    const __m512i L = _mm512_add_epi32(a, lo);
    const __m512i H = _mm512_add_epi32(a, hi);

    const __m512i MSB = _mm512_ternarylogic_epi32(packed_byte(0x80), H, L, 0x20);

    // MSB | (MSB - (MSB >> 7))
    return _mm512_or_si512(MSB, _mm512_sub_epi32(MSB, _mm512_srli_epi32(MSB, 7)));
}


// returns packed (a[i] >= lo and a[i] <= hi) ? 0x04 : 0x00;
__m512i _mm512_range_3rd_bit(const __m512i a, const __m512i lo, const __m512i hi) {

    const __m512i L = _mm512_add_epi32(a, lo);
    const __m512i H = _mm512_add_epi32(a, hi);

    const __m512i MSB = _mm512_ternarylogic_epi32(packed_byte(0x80), H, L, 0x20);

    return _mm512_srli_epi32(MSB, 5);
}

Scatter-based

We can store 48 bytes using the scatter instruction, which saves 32-bit lanes at certain offsets [0, 3, 6, 9, and so on]; the vector of offset is exactly the same as encoding use.

According to the documentation, scatter stores items sequentially. Since indices are in ascending order, all 4th bytes of lane will be overwritten by data from the next lane.

_mm512_i32scatter_epi32(out, scatter_offsets, result, 1);

Vectorized approach

It is possible to do all shifting within registers, unfortunately there is no instruction allowing to shift across 64-bit boundary. This make decoding procedure more complicated than compared to the encoding counterpart.

The algorithm:

1. Input is treated as four 128-bit lanes. The layout of a lane:

   [.. D2 D1 D0|.. C2 C1 C0|.. B2 B1 B0|.. A2 A1 A0] x 4
     3           2           1           0
   

2. Shift fields C and A left by 8 bits (_mm512_mask_slli_epi32):

   [.. D2 D1 D0|C2 C1 C0 ..|.. B2 B1 B0|A2 A1 A0 ..] x 4
   

3. Shift fields D, B and A right by 8 and 24 bits (_mm512_srlv_epi64):

   [.. .. .. ..|D2 D1 D0 C2|.. .. B2 B1|B0 A2 A1 A0] x 4
   

   Now only bytes C2 and C1 have to be moved to word 1, and this is an expansive procedure.

4. Shift the input vector right by a word (_mm512_alignr_epi32):

   [E2 E1 E0 ..|.. D2 D1 D0|C2 C1 C0 ..|.. B2 B1 B0] x 4
                            ^^^^^
                   only these bytes are needed
   

5. Shift and mask bytes C2 and C1 (_mm512_maskz_slli_epi32):

   [.. .. .. ..|.. .. .. ..|C1 C0 .. ..|.. .. .. ..] x 4
   

6. Merge vectors from 3rd and 5th steps (_mm512_ternarylogic_epi32):

   [.. .. .. ..|D2 D1 D0 C2|C1 C0 B2 B1|B0 A2 A1 A0] x 4
   

7. Shuffle words from 128-bit lanes to form 48-byte result (_mm512_permutexvar_epi32).

An excerpt from sample code.

const uint32_t BIT_MERGE = 0xca;

const __m512i t1 = _mm512_mask_slli_epi32(packed, 0x5555, input, 8);

const __m512i s2 = _mm512_setr_epi64(8, 24, 8, 24, 8, 24, 8, 24);
const __m512i t2 = _mm512_srlv_epi64(t1, s2);

const __m512i t3 = _mm512_alignr_epi32(t1, t1, 1);

const __m512i t4 = _mm512_maskz_slli_epi32(0x2222, t3, 8);

const __m512i m5 = _mm512_setr_epi32(
    0x00000000, 0xffff0000, 0x00000000, 0x00000000,
    0x00000000, 0xffff0000, 0x00000000, 0x00000000,
    0x00000000, 0xffff0000, 0x00000000, 0x00000000,
    0x00000000, 0xffff0000, 0x00000000, 0x00000000);

const __m512i t5 = _mm512_ternarylogic_epi32(m5, t4, t2, BIT_MERGE);

const __m512i s6 = _mm512_setr_epi32(
     0,  1,  2,
     4,  5,  6,
     8,  9, 10,
    12, 13, 14,
    // unused
     0,  0,  0, 0);

const __m512i t6 = _mm512_permutexvar_epi32(s6, t5);