Introduction

Base64 algorithms were subject of my interest last year and I proposed a few different SIMD approaches for both encoding and encoding. This text sums up my experiments with ARM Neon implementation. For algorithms' details please refer to Base64 encoding with SIMD instructions and Base64 decoding with SIMD instructions.

ARM Neon

ARM Neon is a pretty rich instruction set, it supports common SIMD logic and arithmetic operations, as well as vector lookups. The base register size is 64 bit (called doubleword), but there is support for 128-bit operations (quadword). Such a wide register is composed from two 64-bit registers, thus there is no cost of getting lower or higher part of quadword register; however at intrinsics level we need to use pseudo-functions vget_{low,high} or vcompose (to construct a new vector). All instructions accept doubleword registers, most work on quadwords.

// input bytes (3 * 16): [a0|b0|c0|a1|b1|c1|...|a15|b15|c15]
const uint8x16x3_t in = vld3q_u8(input + i);

// content of registers:
// in.val[0] = [a0|a1|...|a15]
// in.val[1] = [b0|b1|...|b15]
// in.val[2] = [c0|c1|...|c15]

Base64 encoding

Encoding is done in four steps:

• load three-byte blocks having bit layout [ccdddddd|bbbbcccc|aaaaaabb];
• isolate four 6-bit values, the fields a, b, c and d;
• translate them into ASCII codes;
• save the text.

The first step is accomplished with described earlier interleaved loading, we load 16 three-byte fields and after this step the first register has got bytes [aaaaaabb], the second one [bbbbcccc] and the third one [ccdddddd]. Using standard bitwise and, bitwise or and shifts we build four vectors having bytes [00aaaaaa], [00bbbbbb], [00cccccc] and [00dddddd].

Then we translate these values into ASCII codes. I literally rewritten three procedures from Intel SSE:

• lookup_naive — the most naive, comparison-based approach;
• lookup_version2 — also uses comparisons, but is a bit smarter;
• lookup_pshufb_improved — uses vector lookup instruction vtbl (I kept name pshufb, though). The only important note is that vtbl doesn't support quadword registers, so two invocation of the instruction are needed.

The last step, saving the result, i.e. four vectors, also uses interleaved transfer.

The whole encoding template.

template <typename LOOKUP_FN>
void encode(LOOKUP_FN lookup, const uint8_t* input, size_t bytes, uint8_t* output) {

    uint8_t* out = output;

    for (size_t i = 0; i < bytes; i += 16*3) {
        // load 3 x 16 bytes, each three-byte block has following layout:
        //
        //      [ccdddddd|bbbbcccc|aaaaaabb]
        //        byte 2   byte 1   byte 0
        const uint8x16x3_t in = vld3q_u8(input + i);

        // isolate fields into
        const uint8x16_t field_a = vshrq_n_u8(in.val[0], 2);
        const uint8x16_t field_b = vandq_u8(
                                    vorrq_u8(vshrq_n_u8(in.val[1], 4), vshlq_n_u8(in.val[0], 4)),
                                    packed_byte(0x3f));
        const uint8x16_t field_c = vandq_u8(
                                    vorrq_u8(vshrq_n_u8(in.val[2], 6), vshlq_n_u8(in.val[1], 2)),
                                    packed_byte(0x3f));
        const uint8x16_t field_d = vandq_u8(in.val[2], packed_byte(0x3f));

        // translate fields
        uint8x16x4_t result;
        result.val[0] = lookup(field_a);
        result.val[1] = lookup(field_b);
        result.val[2] = lookup(field_c);
        result.val[3] = lookup(field_d);

        // save 4 x 16 bytes with interleave
        vst4q_u8(out, result);
        out += 64;
    }
}

Base64 decoding

Base64 decoding requires four steps:

• load four-character blocks;
• translate the characters into 6-bit values;
• pack four 6-bit values into 24-bit words;
• save 24-bit words.

The first step uses — no surprise — interleaved loading; we load 16 four-characters chunks. Then each character is translated into 6-bit value, i.e. each of four register has bytes [00aaaaaa], [00bbbbbb], [00cccccc] and [00dddddd]. I rewritten two SSE procedures:

• lookup_byte_blend — naive, comparison-based algorithm, it uses the bit select instruction to blend vectors;
• lookup_pshufb_bitmask — very compact approach heavily using the vector lookup instruction.

Now we compose three registers that will have bytes [aaaaaabb], [bbbbcccc] and [ccdddddd]. This is done with shifts and bitwise ors. The final step is to save these bytes, and again, we use interleaved store.

The decoding template.

template <typename FN_LOOKUP>
void decode(FN_LOOKUP lookup, const uint8_t* input, size_t size, uint8_t* output) {

    uint8_t* out = output;

    uint8x8_t field_a;
    uint8x8_t field_b;
    uint8x8_t field_c;
    uint8x8_t field_d;

    uint8x8_t error_a;
    uint8x8_t error_b;
    uint8x8_t error_c;
    uint8x8_t error_d;

    union {
        uint8_t  error_mem[8];
        uint32_t error_word[2];
    };

    uint8x8x3_t result;

    for (size_t i=0; i < size; i += 8*4) {

        const uint8x8x4_t in = vld4_u8(input + i);

        field_a = lookup(in.val[0], error_a);
        field_b = lookup(in.val[1], error_b);
        field_c = lookup(in.val[2], error_c);
        field_d = lookup(in.val[3], error_d);

        const uint8x8_t error = vorr_u8(vorr_u8(error_a, error_b), vorr_u8(error_c, error_d));

        vst1_u8(error_mem, error);
        if (error_word[0] | error_word[1]) {
            // report an error
        }

        result.val[0] = vorr_u8(vshr_n_u8(field_b, 4), vshl_n_u8(field_a, 2));
        result.val[1] = vorr_u8(vshr_n_u8(field_c, 2), vshl_n_u8(field_b, 4));
        result.val[2] = vorr_u8(field_d, vshl_n_u8(field_c, 6));

        vst3_u8(out, result);
        out += 8*3;
    }
}

As it was said, communication between the Neon unit and main unit is expansive. In the result error reporting path uses a temporary memory to save information.

Performance results

I purchased Raspberry Pi 3 with Cortex-ARMv8, however, the operating system doesn't support the 64-bit mode yet. Everything was tested in the 32-bit mode.

My first implementations used only doubleword instructions (that performed pretty well), later I used quadword in both encoding and decoding. Performance of encoding become better, but decoding was almost 40% slower. I suppose that I omitted something due to lack of experience. Any hints are warmly welcomed.

CPU: ARMv7 Processor rev 4 (v7l)

Compiler: GCC 4.9.2

See also

• Matthieu Darbois developed a really nice algorithm for base64 decoding that uses 64-bit ARM Neon instructions, see file lib/arch/neon64/codec.c (a part of great base64 library by Alfred Klomp).
• "Neon Programmer's Guide", 2013, ARM (DEN0018A — free, but required registration)
• List of all intrinsic functions supported by GCC

Source code

Github repository contains all procedures and sample programs.