Base64 encoder/decoder optimizations

Question

I've written a Base64 encoder/decoder, which works great. Now I want to see if I can get it working better. I've optimized as much as I can think of, but it may be missing some things. The encoder can encode a 160 MB file in 30 seconds, but the decoder takes nearly 60.

So far the optimizations I've done are:

1. Pre-allocated the file size using the formula on Wikipedia for encoding.
2. Pre-allocate the file size using the reciprocal of the encoding formula for decoding.
3. Use bitwise operations for byte and symbol manipulation.
4. Use a in-memory array for encoding.

One possible optimization that I don't know how to make better is the use of a std::map for decoding. O(log n) for searching and O(log n) for inserting for building the map (albeit only once).

Encoder:

#include "Base64Encoder.h"

#include <fstream>
#include <algorithm>

const char Base64Encoder::EncodingTable[64] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z', //0-25
                                               'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z', //26-51
                                               '0','1','2','3','4','5','6','7','8','9',                                                                 //52-61
                                               '+','/'};                                                                                                //62-63

const char Base64Encoder::PADDING_CHAR = '=';


Base64Encoder::Base64Encoder() { /* DO NOTHING */ }

Base64Encoder::~Base64Encoder() { /* DO NOTHING */ }


int Base64Encoder::GetFirstSymbolIndex(char* encoding_buffer) {
    return ((encoding_buffer[0] & 0xFC) >> 2);
}

int Base64Encoder::GetSecondSymbolIndex(char* encoding_buffer) {
    return (((encoding_buffer[0] & 0x03) << 4) | ((encoding_buffer[1] & 0xF0) >> 4));
}

int Base64Encoder::GetThirdSymbolIndex(char* encoding_buffer) {
    return (((encoding_buffer[1] & 0x0F) << 2) | ((encoding_buffer[2] & 0xC0) >> 6));
}

int Base64Encoder::GetFourthSymbolIndex(char* encoding_buffer) {
    return (encoding_buffer[2] & 0x3F);
}

//Gets the 6 most significant digits of the first byte.
char Base64Encoder::GetFirstSymbol(char* encoding_buffer) {
    return Base64Encoder::EncodingTable[Base64Encoder::GetFirstSymbolIndex(encoding_buffer)];
}

//Gets the 2 least significant digits from previous (first) byte and 4 most significant from the second byte.
char Base64Encoder::GetSecondSymbol(char* encoding_buffer) {
    return Base64Encoder::EncodingTable[Base64Encoder::GetSecondSymbolIndex(encoding_buffer)];
}

//Gets the 4 least significant digits from previous (second) byte and 2 least significant from the third byte.
char Base64Encoder::GetThirdSymbol(char* encoding_buffer) {
    return Base64Encoder::EncodingTable[Base64Encoder::GetThirdSymbolIndex(encoding_buffer)];
}

//Gets the 6 least significant digits from the third byte.
char Base64Encoder::GetFourthSymbol(char* encoding_buffer) {
    return Base64Encoder::EncodingTable[Base64Encoder::GetFourthSymbolIndex(encoding_buffer)];
}

std::string Base64Encoder::Encode(const std::string& file_path) {
    std::string output;
    std::ifstream ifs;
    ifs.open(file_path.c_str(), std::ios_base::binary);
    try {
        output = Encode(ifs);
        ifs.close();
    } catch(...) {
        ifs.close();
    }
    return output;
}

std::string Base64Encoder::Encode(std::istream& input_stream) {

    if(input_stream.fail()) return "";

    unsigned long file_size = 0;
    char encoding_buffer[3] = {'\0', '\0', '\0'};

    input_stream.seekg(0, std::ios::end);
    file_size = static_cast<unsigned long>(input_stream.tellg());
    input_stream.seekg(0);

    std::string output(static_cast<unsigned long>(4 * std::ceil(file_size / 3.0)), '\0');

    if(file_size == 0) {
        output.clear();
        input_stream.clear();
        return output;
    }

    while(input_stream.read(reinterpret_cast<char*>(encoding_buffer), sizeof(encoding_buffer))) {

        char firstsymbol = GetFirstSymbol(encoding_buffer);
        char secondsymbol = GetSecondSymbol(encoding_buffer);
        char thirdsymbol = GetThirdSymbol(encoding_buffer);
        char fourthsymbol = GetFourthSymbol(encoding_buffer);

        unsigned long s = 4 * static_cast<unsigned long>(input_stream.tellg()) / 3;

        output[s - 4] = firstsymbol;
        output[s - 3] = secondsymbol;
        output[s - 2] = thirdsymbol;
        output[s - 1] = fourthsymbol;

    }

    output.erase(output.find_first_of('\0'));

    if(input_stream.fail()) {
        switch(input_stream.gcount()) {
        case 0:
            /* DO NOTHING. Evenly divisible by 4. */
            break;
        case 1: {
            /* Only one byte read */
            encoding_buffer[2] = 0;
            encoding_buffer[1] = 0;

            char firstsymbol = GetFirstSymbol(encoding_buffer);
            char secondsymbol = GetSecondSymbol(encoding_buffer);
            char thirdsymbol = GetThirdSymbol(encoding_buffer);
            char fourthsymbol = GetFourthSymbol(encoding_buffer);

            output.push_back(firstsymbol);
            output.push_back(secondsymbol);
            output.push_back(Base64Encoder::PADDING_CHAR);
            output.push_back(Base64Encoder::PADDING_CHAR);

            break;
        } case 2: {
            /* Only two bytes read */
            encoding_buffer[2] = 0;

            char firstsymbol = GetFirstSymbol(encoding_buffer);
            char secondsymbol = GetSecondSymbol(encoding_buffer);
            char thirdsymbol = GetThirdSymbol(encoding_buffer);
            char fourthsymbol = GetFourthSymbol(encoding_buffer);

            output.push_back(firstsymbol);
            output.push_back(secondsymbol);
            output.push_back(thirdsymbol);
            output.push_back(Base64Encoder::PADDING_CHAR);

            break;
        } case 3:
            /* DO NOTHING All three bytes read. */
            break;
        default:
            /* DO NOTHING */;
        }
    }

    input_stream.clear();

    return output;
}

std::string Base64Encoder::Execute(std::istream& input_stream) {
    return Encode(input_stream);
}

std::string Base64Encoder::Execute(const std::string& file_path) {
    return Encode(file_path);
}

Decoder:

#include "Base64Decoder.h"

#include <fstream>

const char Base64Decoder::PADDING_CHAR = '=';
Base64Decoder::DecodingMap Base64Decoder::DecodingTable;

Base64Decoder::Base64Decoder() {
    BuildDecodingTable(DecodingTable);
}

Base64Decoder::~Base64Decoder() {

}

void Base64Decoder::BuildDecodingTable(DecodingMap& table) {
    table.clear();
    char cur_char = 'A';
    for(int i = 0; i < 26; ++i) {
        table.insert(std::make_pair(cur_char++, i));
    }
    cur_char = 'a';
    for(int i = 26; i < 52; ++i) {
        table.insert(std::make_pair(cur_char++, i));
    }
    cur_char = '0';
    for(int i = 52; i < 62; ++i) {
        table.insert(std::make_pair(cur_char++, i));
    }
    table.insert(std::make_pair('+', 62));
    table.insert(std::make_pair('/', 63));

}
//First Byte is all 6 of first symbol and 2 most significant bits of second symbol.
char Base64Decoder::GetFirstByte(char* decoding_buffer) {
    DecodingMap::iterator first_iter = DecodingTable.find(decoding_buffer[0]);
    DecodingMap::iterator second_iter = DecodingTable.find(decoding_buffer[1]);

    int first_index;
    if(first_iter == DecodingTable.end()) {
        first_index = decoding_buffer[0];
    } else {
        first_index = (*first_iter).second;
    }

    int second_index;
    if(second_iter == DecodingTable.end()) {
        second_index = decoding_buffer[1];
    } else {
        second_index = (*second_iter).second;
    }

    first_index = (first_index & 0x3F) << 2;
    second_index = (second_index & 0x30) >> 4;
    int result = first_index | second_index;
    return result;
}

//Second Byte is 4 least significant bits of second symbol and 4 most significant bits of third symbol.
char Base64Decoder::GetSecondByte(char* decoding_buffer) {
    DecodingMap::iterator second_iter = DecodingTable.find(decoding_buffer[1]);
    DecodingMap::iterator third_iter = DecodingTable.find(decoding_buffer[2]);

    int second_index;
    if(second_iter == DecodingTable.end()) {
        second_index = decoding_buffer[1];
    } else {
        second_index = (*second_iter).second;
    }

    int third_index;
    if(third_iter == DecodingTable.end()) {
        third_index = decoding_buffer[2];
    } else {
        third_index = (*third_iter).second;
    }
    second_index = (second_index & 0x0F) << 4;
    third_index = (third_index & 0x3C) >> 2;
    int result = second_index | third_index;
    return result;
}

//Third Byte is 2 least significant bits of third symbol and all of fourth symbol.
char Base64Decoder::GetThirdByte(char* decoding_buffer) {
    DecodingMap::iterator third_iter = DecodingTable.find(decoding_buffer[2]);
    DecodingMap::iterator fourth_iter = DecodingTable.find(decoding_buffer[3]);

    int third_index;
    if(third_iter == DecodingTable.end()) {
        third_index = decoding_buffer[2];
    } else {
        third_index = (*third_iter).second;
    }

    int fourth_index;
    if(fourth_iter == DecodingTable.end()) {
        fourth_index = decoding_buffer[3];
    } else {
        fourth_index = (*fourth_iter).second;
    }

    third_index = (third_index & 0x03) << 6;
    fourth_index = fourth_index & 0x3F;
    int result = third_index | fourth_index;
    return result;
}

std::string Base64Decoder::Decode(const std::string& file_path) {
    std::string output;
    std::ifstream ifs;
    ifs.open(file_path.c_str(), std::ios_base::binary);
    try {
        output = Decode(ifs);
        ifs.close();
    } catch(...) {
        ifs.close();
    }
    return output;
}

std::string Base64Decoder::Decode(std::istream& input_stream) {

    if(input_stream.fail()) return "";

    unsigned long file_size = 0;
    char decoding_buffer[4] = {'\0', '\0', '\0', '\0'};

    input_stream.seekg(0, std::ios::end);
    file_size = static_cast<unsigned long>(input_stream.tellg());
    input_stream.seekg(0);

    std::string output(static_cast<unsigned long>(3 * std::ceil(file_size / 4.0)) + (file_size % 3), '\0');

    if(file_size == 0) {
        output.clear();
        input_stream.clear();
        return "";
    }

    while(input_stream.read(reinterpret_cast<char*>(decoding_buffer), sizeof(decoding_buffer))) {

        char firstbyte = GetFirstByte(decoding_buffer);
        char secondbyte = GetSecondByte(decoding_buffer);
        char thirdbyte = GetThirdByte(decoding_buffer);

        unsigned long s = static_cast<unsigned long>(3 * std::ceil(static_cast<unsigned long>(input_stream.tellg()) / 4.0));

        if(firstbyte != PADDING_CHAR) output[s - 3] = firstbyte;
        if(secondbyte != PADDING_CHAR) output[s - 2] = secondbyte;
        if(thirdbyte != PADDING_CHAR) output[s - 1] = thirdbyte;

        decoding_buffer[0] = '\0';
        decoding_buffer[1] = '\0';
        decoding_buffer[2] = '\0';
        decoding_buffer[3] = '\0';
    }

    //Erase extraneous null chars.
    output.erase(output.find_first_of('\0'));

    if(input_stream.fail()) {
        if(decoding_buffer[2] == PADDING_CHAR) {
            //Third character is PADDING_CHAR. Only one in decoding_buffer.
            char firstbyte = GetFirstByte(decoding_buffer);
            char secondbyte = GetSecondByte(decoding_buffer);
            char thirdbyte = GetThirdByte(decoding_buffer);
            output.push_back(firstbyte);
        } else if(decoding_buffer[3] == PADDING_CHAR) {
            //Fourth character is PADDING_CHAR. Only two in decoding_buffer.
            char firstbyte = GetFirstByte(decoding_buffer);
            char secondbyte = GetSecondByte(decoding_buffer);
            char thirdbyte = GetThirdByte(decoding_buffer);
            output.push_back(firstbyte);
            output.push_back(secondbyte);
        } else {
            /* DO NOTHING */
        }
    }
    input_stream.clear();

    return output;
}

std::string Base64Decoder::Execute(std::istream& input_stream) {
    return Decode(input_stream);
}

std::string Base64Decoder::Execute(const std::string& file_path) {
    return Decode(file_path);
}

Answer 1

I realise this is an old post but just came across it and couldn't help but notice the following pattern in the original post which was not addressed in the review:

encoding_buffer[1] & 0xF0) >> 4

Constructs like that are dangerous as the data type of the encoding_buffer is char instead of unsigned char and it's up to the compiler to decide whether to use arithmetic (repeat the leftmost bit on the left) or logical (fill 0s to the left) right shift. Far safer would be to rewrite the expression as:

(encoding_buffer[1] >> 4) & 0x0F

As a general rule it's better to do the shift first and apply the mask later.

The original code may or may not work on the designated platform but is certainly not portable.

Answer 2

FOA, code looks clear and clean, well indented and formatted. Thumbs up!!

Now, to the comments:

• Some of the variable names might have more significant names: is can be changed to input_stream, for instance.
• File size: it looks like you try to get the file size out of the stream by fetching the stream until reaching its end. I'd change that to an explicit call to a function provider by the hosting OS' API (see stat), or by a library that implements it, like boost.
• Extract file size calculation to a function, to achieve code reuse.
• Base64 format should convert a byte array (or a binary stream) to an ASCII string. It has nothing to do with Bitmap format in specific. I'd recommend you create some test cases using a C++ unit testing framework (there are some) and find the bug, if such exists.

Good luck!