4
\$\begingroup\$
static const unsigned char from_base64[] = { 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,  
                                    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
                                    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,  62, 255,  62, 255,  63, 
                                     52,  53,  54,  55,  56,  57,  58,  59,  60,  61, 255, 255, 255, 255, 255, 255, 
                                    255,   0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,
                                     15,  16,  17,  18,  19,  20,  21,  22,  23,  24,  25, 255, 255, 255, 255,  63,
                                    255,  26,  27,  28,  29,  30,  31,  32,  33,  34,  35,  36,  37,  38,  39,  40, 
                                     41,  42,  43,  44,  45,  46,  47,  48,  49,  50,  51, 255, 255, 255, 255, 255};


static const char to_base64[] = 
             "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
             "abcdefghijklmnopqrstuvwxyz"
             "0123456789+/";


std::string base64_encode(unsigned char const* buf, unsigned int bufLen) {
    size_t ret_size = bufLen+2;

    ret_size = 4*ret_size/3;

    std::string ret;
    ret.reserve(ret_size);

    for (unsigned int i=0; i<ret_size/4; ++i)
    {
        size_t index = i*3;
        unsigned char b3[3];
        b3[0] = buf[index+0];
        b3[1] = buf[index+1];
        b3[2] = buf[index+2];

        ret.push_back(to_base64[ ((b3[0] & 0xfc) >> 2) ]);
        ret.push_back(to_base64[ ((b3[0] & 0x03) << 4) + ((b3[1] & 0xf0) >> 4) ]);
        ret.push_back(to_base64[ ((b3[1] & 0x0f) << 2) + ((b3[2] & 0xc0) >> 6) ]);
        ret.push_back(to_base64[ ((b3[2] & 0x3f)) ]);
    }

    return ret;
}

std::vector<unsigned char> base64_decode(std::string encoded_string) {
    size_t encoded_size = encoded_string.size();
    std::vector<unsigned char> ret;
    ret.reserve(3*encoded_size/4);

    for (size_t i=0; i<encoded_size; i += 4)
    {
        unsigned char b4[4];
        b4[0] = from_base64[encoded_string[i+0]];
        b4[1] = from_base64[encoded_string[i+1]];
        b4[2] = from_base64[encoded_string[i+2]];
        b4[3] = from_base64[encoded_string[i+3]];

        unsigned char b3[3];
        b3[0] = ((b4[0] & 0x3f) << 2) + ((b4[1] & 0x30) >> 4);
        b3[1] = ((b4[1] & 0x0f) << 4) + ((b4[2] & 0x3c) >> 2);
        b3[2] = ((b4[2] & 0x03) << 6) + ((b4[3] & 0x3f));

        ret.push_back(b3[0]);
        ret.push_back(b3[1]);
        ret.push_back(b3[2]);
    }

    return ret;
}

Is there any way to improve this code to make the encoding and decoding faster? If there is a way to improve the code that uses base85 encoding instead of base64 that is faster, that works too.

\$\endgroup\$
  • 3
    \$\begingroup\$ there's a bug or two when your inputs aren't multiples of 3 or 4. In decode you also don't account for input chars that aren't part of the encoding (like whitespace or the ending =) \$\endgroup\$ – ratchet freak Aug 16 '17 at 15:04
  • \$\begingroup\$ @ratchetfreak my inputs are always multiples of 3 or 4, that is checked when calling :) and okay, that didn't make a difference for me, but I'll account for it anyway. Thanks! \$\endgroup\$ – anc Aug 16 '17 at 15:27
3
\$\begingroup\$

Here are a few suggestions:

1. Don't write this

Many before you have needed, and gotten, a fast Base64 decoder. Why should you write this yourself? You don't seem to have a special twist on the decoding/encoding - unless you want "base85 decoding", a term I'm not quite sure I understand.

Specifically, here is a nice treatment of the subject (although still far from the optimum):

Fast Base64 encode and decode

2. Don't work on 8-bit values

The fact that base64 encoding has a 1-byte (or 1-ASCII-character) resolution the way it's defined does not mean that's how you need to decode it. Your machine is (probably) a 64-bit machine. So work on in 64-bits units unless you have reason to use another size (which you very well might - but probably not 8 bits). Work out the math for the larger sizes.

Now you might say "but what if the length of my output isn't divisible by 8?" - well, just handle the slack at the end, outside your main tight loop.

Similarly, you shouldn't use 4 distinct 8-bit variables for your input - use something bigger.

3. Don't mix decoding and allocation + don't force the use of std::vector

You should not be using an std::vector. Take a pointer to a nicely-aligned output buffer, or better yet - a gsl::span. (You could also take a templated iterator but I wouldn't bother) with sufficient memory pre-allocated, and write there.

If you insist on doing the allocation yourself for some reason, have a wrapper function do it. Right now you're allocating \$log(n)\$ times for decoding \$\frac{n}{6}\$ bits! C-R-A-Z-Y!.

At any rate, there's no reason to force the client code for your decoder to take an std::vector.

4. Are both lookup tables really helping you?

Using a look-up table means doing less computational work. But is the trade-off worth it? Not always. Now, if you be making your lookup table larger (which you may very well do, see the linked blog post and remember we want to work with more than 8 bits at a time) you might hit cache limits. And even if you aren't - maybe in-register arithmetic is good enough?

Now, I might be worrying you for nothing here, and maybe lookup tables are the best thing to do - but at least profile to make sure. In fact,

5. Profile profile profile

If @DJuracu wrote already - profile to find out what needs optimization. You can speed up something a zillion times, but if it's only 5% of the execution time you haven't saved much (Amdahl's law). Of course, after you've improved something else, those 5% may now become 50%, making it worthwhile to work on that part of the code after all. Still, you need to know what worked and what didn't.

6. You have to look at the compiled code

When you're writing code that's this low-level, you can't allow yourself the slack of ignoring the assembly. Learn to read it and do so. I know that's a tall order but you're the one who said you want to write something that's "fast"...

7. Multi-thread

If this is part of an application which already has multiple threads running, then forget this point. Otherwise - why use only one core, and with one thread on it? Assuming you're on a typical modern PC, you have 2 or 4 cores, and with 'HyperThreading', they can execute instructions from 4 or 8 threads overall. While you could theoretically be bottlenecked on memory bandwidth or some other resource at full 4 or 8 thread capacity, you might not. Especially if you're not well-enough SIMDized

8. Use SIMD for parallelism

Your processor supports vectorized instructions. Your decoding (and your decoding) does not have "dependency chains" between the values of consecutive characters, except at most when composing a larger word from fewer bits. So - you should be able to SIMDize all or almost all of this work. I'm a GPU guy more than a CPU guy, so I can't tell you which instructions you'll want to be using, but that would definitely be necessary for maximum speed. Probably best to work on this before going multi-threaded.

\$\endgroup\$
2
\$\begingroup\$

There's an inconsistency between to_base64 which maps integers to host characters and from_base64 which maps (char-sized) integers to integer values. The two transforms are consistent only when the host character coding represents the base-64 characters with the same code-points as in ASCII; not all character sets do so.

The correct portable way to fix this is to derive the decoder table from the encoder table.

\$\endgroup\$
1
\$\begingroup\$

Some optimizations scenarios just from looking at the code:

  • Don't pass std::string encoded_string by value as you're making a useless copy. As you're only interested in an array of bytes, passing a string_view (or the traditional pointer + size) is more flexible.
  • You know how big the resulting vectors will be, so using operator[] after increasing their size might be faster than constantly calling push_back().

For more opportunities for optimizations, profile the code to find bottlenecks.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.