8
\$\begingroup\$

Was a tiny bit bored reading authentication protocols.
Needed to clear the mind and read some base64 encode text.

So I implemented these iterators that will encode or decode base64 text.

Not sure about:

  • Interface is there a better way
  • Iterator Implementation (its been a while since I did one)
  • How easy to make this work with Ranges?

Usage:

 int main()
 {
      std::string  data = getBase64Message(); // retrieves a message base 64 encoded.
      std::string  message(make_decode64(std::begin(data)), 
                           make_decode64(std::end(data)));
      std::cout << message << "\n";

      std::copy(make_encode64(std::istream_iterator<char>(std::cin)),
                make_encode64(std::istream_iterator<char>()),
                std::ostream_iterator<char>(std::cout));

 }

The basic concept is that they are iterators that are constructed with other iterators. So you can decode any type of container as long as you can get a readable iterator to it (technically the iterator has to be an input iterator).


Nobody has submitted a review. So I am adding version 2 the cleaned up (and commented) version to the question. I will leave the original version at the bottom for comparison:

#ifndef THORS_ANVIL_CRYPTO_BASE_H
#define THORS_ANVIL_CRYPTO_BASE_H

namespace ThorsAnvil::Crypto
{

template<typename I>
class Base64DecodeIterator
{
    I       iter    = I{};
    int     bits    = 0;
    int     buffer  = 0;
    public:

    using difference_type   = std::ptrdiff_t;
    using value_type        = char;
    using pointer           = char*;
    using reference         = char&;
    using iterator_category = std::input_iterator_tag;

    Base64DecodeIterator()  {}
    Base64DecodeIterator(I iter)
        : iter(iter)
    {}

    // Check state of iterator.
    // We are not done until all the bits have been read even if we are at the end iterator.
    bool operator==(Base64DecodeIterator const& rhs) const  {return (iter == rhs.iter) && (bits == 0);}
    bool operator!=(Base64DecodeIterator const& rhs) const  {return !(*this == rhs);}

    // Increment Simply remove bits.
    // Note: The interface for input iterator required a * before each ++ operation.
    //       So we don't need to do any work on the ++ operator but do it all in the * operator
    Base64DecodeIterator& operator++()      {bits -= 8;return *this;}
    Base64DecodeIterator operator++(int)    {Base64DecodeIterator  result(this);++(*this);return result;}

    char operator*()
    {
        // If nothing in the buffer than fill it up.
        if (bits == 0)
        {
            static constexpr char convert[]
                    = "\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F"    //   0 - 15 00 - 0F
                      "\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F"    //  16 - 31 10 - 1F
                      "\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x8F\x3E\x8F\x8F\x8F\x3F"    //  32 - 47 20 - 2F + /
                      "\x34\x35\x36\x37\x38\x39\x3A\x3B\x3C\x3D\x8F\x8F\x8F\x40\x8F\x8F"    //  48 - 63 30 - 3F 0-9
                      "\x8F\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x0C\x0D\x0E"    //  64 - 79 40 - 4F A-O
                      "\x0F\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x8F\x8F\x8F\x8F\x8F"    //  80 - 95 50 - 5F P-Z
                      "\x8F\x1A\x1B\x1C\x1D\x1E\x1F\x20\x21\x22\x23\x24\x25\x26\x27\x28"    //  96 -111 60 - 6F a-o
                      "\x29\x2A\x2B\x2C\x2D\x2E\x2F\x30\x31\x32\x33\x8F\x8F\x8F\x8F\x8F";   // 112 -127 70 - 7F p-z

            int extra = 0;
            // Base64 input is based on the input being 3 input bytes => 4 output bytes.
            // There will always be a multiple of 3 bytes on the input. So read 3 bytes
            // at a time.
            while (bits != 24)
            {
                unsigned char tmp = *iter++;
                unsigned char b64 = convert[tmp & 0x7F];
                if (b64 == 0x8F || tmp > 0x7F)
                {
                    throw std::runtime_error("Base64DecodeIterator::operator*: invalid input");
                }
                if (b64 == 0x40)    // We found a padding byte '='
                {
                    extra += 8;
                    b64 = 0;
                }

                buffer = (buffer << 6) | b64;
                bits  = bits + 6;
            }
            // Remove any padding bits we found.
            buffer = buffer >> extra;
            bits -= extra;
        }
        char result = (buffer >> (bits - 8)) & 0xFF;
        return result;
    }
};

template<typename I>
class Base64EncodeIterator
{
    I               iter    = I{};
    mutable int     bits    = 0;
    mutable int     buffer  = 0;
    public:

    using difference_type   = std::ptrdiff_t;
    using value_type        = char;
    using pointer           = char*;
    using reference         = char&;
    using iterator_category = std::input_iterator_tag;

    Base64EncodeIterator() {}
    Base64EncodeIterator(I iter)
        : iter(iter)
    {}
    enum Flags
    {
            EndFlag  = 0x8000,
            FillFlag = 0x4000,
            Data     = 0x3FFF,
    };

    bool operator==(Base64EncodeIterator const& rhs) const
    {
        // Note: That we have reached the end of the input stream.
        //       That means we can not read more data in the * operator.
        // Note: The input iterator interface requires you to the check␣
        //       the iterator against end before continuing.
        if (iter == rhs.iter)
        {
            buffer = buffer | EndFlag;
        }
        // We are not finished even if we have reached the end iterator
        // if there is still data left to decode in the buffer.
        return (iter == rhs.iter) && (bits == 0);
    }
    bool operator!=(Base64EncodeIterator const& rhs) const  {return !(*this == rhs);}

    // Increment the current position.
    Base64EncodeIterator& operator++()      {bits -= 6;return *this;}
    Base64EncodeIterator operator++(int)    {Base64EncodeIterator  result(this);++(*this);return result;}

    char operator*()
    {
        // We convert three 8 bit values int four 6 bit values.
        // But the input can be any size (i.e. it is not padded to length).
        // We must therefore detect then end of stream (see operator ==) and
        // insert the appropriate padding on the output. But this also means
        // we can not simply keep reading from the input as we cant detect
        // the end here.
        //
        // Therefor we only reads 1 byte at a time from the input. We don't
        // need to read a byte every call as we have 2 bits left over from
        // each character read thus every four call to this function will
        // return a byte without a read.
        //
        // Note this means the buffer will only ever have a maximum of 14 bits (0-13)␣
        // of data in it. We re-use bits 14/15 as flags. Bit 15 marks the end
        // Bit 14 indicates that we should return a padding character.

        // Check if we should return a padding character.
        bool fillFlag = buffer & FillFlag;


        if (bits < 6)
        {
            if (buffer & EndFlag)
            {
                // If we have reached the end if the input
                // we simply pad the data with 0 value in the buffer.
                // Note we add the FillFlag here so the next call
                // will be returning a padding character
                buffer = EndFlag | FillFlag | ((buffer << 8) & Data);
            }
            else
            {
                // Normal operation. Read data from the input
                // Add it to the buffer.
                unsigned char tmp = *iter++;
                buffer = ((buffer << 8) | tmp) &  Data;
            }
            bits += 8;
        }

        static constexpr char convert[]
                    = "ABCDEFGHIJKLMNOP"    // 00 - 0F
                      "QRSTUVWXYZabcdef"    // 10 - 1F
                      "ghijklmnopqrstuv"    // 20 - 2F
                      "wxyz0123456789+/";   // 30 - 3F
        // Output is either padding or converting the 6 bit value into an encoding.
        char result = fillFlag ? '=' : convert[(buffer >> (bits - 6)) & 0x3F];

        return result;
    }
};

template<typename I>
Base64DecodeIterator<I> make_decode64(I iter)
{
    return Base64DecodeIterator<I>(iter);
}
template<typename I>
Base64EncodeIterator<I> make_encode64(I iter)
{
    return Base64EncodeIterator<I>(iter);
}

}

#endif

The original version is below:

#ifndef THORS_ANVIL_CRYPTO_BASE_H
#define THORS_ANVIL_CRYPTO_BASE_H

namespace ThorsAnvil::Crypto
{

template<typename I>
class Base64DecodeIterator
{
    I       iter;
    int     bits;
    int     value;
    public:

    using difference_type   = std::ptrdiff_t;
    using value_type        = char;
    using pointer           = char*;
    using reference         = char&;
    using iterator_category = std::input_iterator_tag;

    Base64DecodeIterator()
        : iter(I{})
        , bits(0)
        , value(0)
    {}
    Base64DecodeIterator(I iter)
        : iter(iter)
        , bits(0)
        , value(0)
    {}
    bool operator==(Base64DecodeIterator const& rhs) const
    {
        return (iter == rhs.iter) && (bits == 0);
    }
    bool operator!=(Base64DecodeIterator const& rhs) const
    {
        return !(*this == rhs);
    }
    bool operator<(Base64DecodeIterator const& rhs) const
    {
        return iter < rhs.iter || (iter == rhs.iter && bits != 0);
    }
    char operator*()
    {
        if (bits == 0)
        {
            int extra = 0;
            while (bits != 24)
            {
                unsigned char tmp = *iter++;
                unsigned char b64;
                if (tmp >= 'A' && tmp <= 'Z')
                {
                    b64 = tmp - 'A';
                }
                else if (tmp >= 'a' && tmp <= 'z')
                {
                    b64 = tmp - 'a' + 26;
                }
                else if (tmp >= '0' && tmp <= '9')
                {
                    b64 = tmp - '0' + 52;
                }
                else if (tmp == '+')
                {
                    b64 = 63;
                }
                else if (tmp == '/')
                {
                    b64 = 64;
                }
                else if (tmp == '=')
                {
                    b64 = 0;
                    extra   += 8;
                }
                else
                {
                    throw std::runtime_error("Bad Input");
                }

                value = (value << 6) | b64;
                bits  = bits + 6;
            }
            value = value >> extra;
            bits -= extra;
        }
        char result = (value >> (bits - 8)) & 0xFF;
        return result;
    }
    Base64DecodeIterator& operator++()
    {
        bits -= 8;
        return *this;
    }
    Base64DecodeIterator operator++(int)
    {
        Base64DecodeIterator  result(this);
        bits -= 8;
        return result;
    }
};

template<typename I>
class Base64EncodeIterator
{
    I       iter;
    mutable int     bits;
    mutable int     value;
    public:

    using difference_type   = std::ptrdiff_t;
    using value_type        = char;
    using pointer           = char*;
    using reference         = char&;
    using iterator_category = std::input_iterator_tag;

    Base64EncodeIterator()
        : iter(I{})
        , bits(0)
        , value(0)
    {}
    Base64EncodeIterator(I iter)
        : iter(iter)
        , bits(0)
        , value(0)
    {}
    enum Flags
    {
            EndFlag  = 0x8000,
            FillFlag = 0x4000,
            Data     = 0x3FFF,
    };

    bool operator==(Base64EncodeIterator const& rhs) const
    {
        if (iter == rhs.iter)
        {
            value = value | EndFlag;
        }
        return (iter == rhs.iter) && (bits == 0);
    }
    bool operator!=(Base64EncodeIterator const& rhs) const
    {
        return !(*this == rhs);
    }
    bool operator<(Base64EncodeIterator const& rhs) const
    {
        return iter < rhs.iter || (iter == rhs.iter && bits != 0);
    }
    char operator*()
    {
        bool fillFlag = value & FillFlag;
        if (bits < 6)
        {
            if (value & EndFlag)
            {
                value = EndFlag | FillFlag | ((value << 8) & Data);
            }
            else
            {
                unsigned char tmp = *iter++;
                value = ((value << 8) | tmp) &  Data;
            }
            bits += 8;
        }

        char result = '=';
        if (!fillFlag)
        {
            int tmp = (value >> (bits - 6)) & 0x3F;
            if (tmp < 26)
            {
                result = 'A' + tmp;
            }
            else if (tmp < 52)
            {
                result = 'a' + (tmp - 26);
            }
            else if (tmp < 62)
            {
                result = '0' + (tmp - 52);
            }
            else if (tmp == 62)
            {
                result = '+';
            }
            else
            {
                result = '/';
            }
        }

        bits -= 6;
        return result;
    }
    Base64EncodeIterator& operator++()
    {
        return *this;
    }
    Base64EncodeIterator operator++(int)
    {
        Base64EncodeIterator  result(this);
        return result;
    }
};

template<typename I>
Base64DecodeIterator<I> make_decode64(I iter)
{
    return Base64DecodeIterator<I>(iter);
}
template<typename I>
Base64EncodeIterator<I> make_encode64(I iter)
{
    return Base64EncodeIterator<I>(iter);
}

}

#endif
\$\endgroup\$
2
  • \$\begingroup\$ where is the function getBase64Message? \$\endgroup\$
    – Peter
    Aug 24 '20 at 15:47
  • 1
    \$\begingroup\$ @Peter It represents your code that retrieves a base 64 message from some part of your system. std::string getBase64Message() {return "AAAA";} \$\endgroup\$ Aug 24 '20 at 17:14
3
\$\begingroup\$

Avoid repeating yourself

I see a few cases where you can avoid repeating type names. For example:

I iter = I{};

This can be written as:

I iter{};

And:

Base64DecodeIterator operator++(int) {Base64DecodeIterator result(this); ++(*this); return result;}

Can be written as:

Base64DecodeIterator operator++(int) {auto result{*this}; ++(*this); return result;}

Avoid writing multiple statements on one line

Since it is so customary in C and C++ to write one statement per line, when you combine multiple statements on one line, especially without whitespace between the statements, it can be confusing. Just split multi-statement one-liners into multiple lines, like:

Base64DecodeIterator operator++(int) {
    auto result{*this};
    ++(*this);
    return result;
}

Consider supporting different input and output types

Consider a situation where you have a blob of binary data, to which you have a char * or uint8_t *, but you need to the base64-encoded string to use wchar_t. You could support this relatively easy by adding another template parameter to describe the output type, like so:

template<typename I, typename CharT = char>
class Base64EncodeIterator
{
     ...
     using value_type = CharT;
     using pointer = CharT*;
     using reference = CharT&;
     ...
     CharT operator*()
     {
         ...
     }
};

You would make the same change for Base64DecodeIterator. The make_* functions can look like:

template<typename CharT = char, typename I>
Base64DecodeIterator<I, CharT> make_encode64(I iter)
{
    return Base64EncodeIterator<I, CharT>(iter);
}

Then you could use it like so:

std::vector<uint8_t> original(...);

std::wstring message(make_encode64<wchar_t>(std::begin(original)), 
                     make_encode64<wchar_t>(std::end(original)));

std::vector<uint8_t> recovered(make_decode64<uint8_t>(std::begin(message)),
                               make_decode64<uint8_t>(std::end(message)));

Consider I::value_type not being an 8 bit integer type during encoding

Your code will accept the following:

std::vector<float> data{1.1, 42, 9.9e99};
make_encode64(data.begin());

But what this will do is cast each element of the vector to an unsigned char before encoding it. That is not what you would expect. Use SFINAE or Concepts to limit the allowed iterators to those that have a value_type that is an 8-bit integer type.

When encoding you have the same problem if you allow the output type to be specified as mentioned in the previous point.

Making it work with ranges

The problem is that your classes do not implement a std::ranges::range. So you would need to introduce some class that provides both the begin and end iterator. But that could be as simple as:

template<typename I>
class Base64Decoder {
    Base64DecodeIterator begin_it;
    Base64DecodeIterator end_it;

public:
    Base64Decoder(const I &begin, const I &end): begin_it(begin), end_it(end) {}

    template<typename T>
    Base64Decoder(T &container): begin_it(std::begin(container)), end_it(std::end(container)) {}

    auto& begin() {
        return begin_it;
    }
 
    auto& end() {
        return end_it;
    }
};

And then you could write:

std::string input = "SGVsbG8sIHdvcmxkIQo=";
Base64Decoder decoder(input);
for (auto c: input | std::ranges::views::take(5))
    std::cout << c;
std::cout << '\n';
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Thanks for the review. Not sure wide characters is a good idea as base64 is 1 octet encoding scheme. \$\endgroup\$ Aug 24 '20 at 21:10
  • 1
    \$\begingroup\$ Well on Windows it is common to use wchar_t to encode things like file names and so on, so there is some merit for it on some platforms. And it's templated, so it's just a few extra lines and no run-time overhead as far as I can tell. \$\endgroup\$
    – G. Sliepen
    Aug 25 '20 at 5:59
  • 1
    \$\begingroup\$ So I understand what the result should look like. I decode the base64 to octet then I place 1 octet per wchar_t character or do I place multiple octets into a single character. When converting back do I treat each wchar_t as a single 8 bit value or multiple 8 bit values. \$\endgroup\$ Aug 25 '20 at 15:59

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.