// base64.cpp
//  Simple C++ Base 64 encoder/decoder
//  (c) 2005 Ryan Patterson
//  Distributed under the zlib/libpng license
//  Usage:
//   std::string input;
//   std::string output;
//   input = "Hello, everyone!";
//   output.resize(encoded_size(input.length()));
//   encode_64(input.begin(), input.end(), output.begin());
//   std::cout << output << std::endl;
//   input = "SGVsbG8sIGV2ZXJ5b25lIQo=";
//   output = "";
//   output.resize(decoded_size(input.length()));
//   decode_64(input.begin(), input.end(), output.begin());
//   std::cout << output << std::endl;

#include <string>
#include <iostream>
using namespace std;

int encoded_size(int len)
{ return (len / 4 + 1) * 4; }

int decoded_size(int len)
{ return len * 3 / 4; }

static char encode_64(unsigned char i)
{
	if(i < 26) return 'A' + i;
	if(i < 52) return 'a' + i - 26;
	if(i < 62) return '0' + i - 52;
	if(i == 62) return '+';
	return '/';
}

static unsigned char decode_64(char i)
{
	if(i >= 'A' && i <= 'Z') return i - 'A';
	if(i >= 'a' && i <= 'z') return i - 'a' + 26;
	if(i >= '0' && i <= '9') return i - '0' + 52;
	if(i == '+') return 62;
	return 63; 
}

static bool is_64(char c)
{
	if((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '/' && c <= '9') || c == '+' || c == '=')
		return true;
	return false;
}

template <class InputIterator, class OutputIterator> OutputIterator encode_64(InputIterator first, InputIterator last, OutputIterator result)
{
	for(InputIterator i = first; i != last;)
	{
		char c1, c2, c3;
		unsigned char b1, b2, b3, b4;
		bool have2 = false, have3 = false;
		
		c1 = *i++;
		if(i != last)
		{
			c2 = *i++; have2 = true;
			if(i != last)
			{
				c3 = *i++; have3 = true;
			}
		}
		
		b1 = c1 >> 2;
		b2 = ((c1 & 0x3) << 4) | (c2 >> 4);
		b3 = ((c2 & 0xf) << 2) | (c3 >> 6);
		b4 = c3 & 0x3f;
		
		*result++ = encode_64(b1);
		*result++ = encode_64(b2);
		if(have2) *result++ = encode_64(b3);
		else *result++ = '=';
		if(have3) *result++ = encode_64(b4);
		else *result++ = '=';
	}
	return result;
}

template <class InputIterator, class OutputIterator> OutputIterator decode_64(InputIterator first, InputIterator last, OutputIterator result)
{
	InputIterator i = first;
	while(1)
	{
		char c1 = 'A', c2 = 'A', c3 = 'A', c4 = 'A';
		unsigned char b1, b2, b3, b4;
		
		while(i != last && !is_64(c1 = *i)) i++;
		if(i == last) break;
		i++; while(i != last && !is_64(c2 = *i)) i++;
		if(i != last)
		{
			i++; while(i != last && !is_64(c3 = *i)) i++;
			if(i != last)
			{
				i++; while(i != last && !is_64(c4 = *i)) i++;
			}
		}
		
		b1 = decode_64(c1);
		b2 = decode_64(c2);
		b3 = decode_64(c3);
		b4 = decode_64(c4);
		
		*result++ = (b1 << 2) | (b2 >> 4);
		if(c3 != '=')
			*result++ = ((b2 & 0xf) << 4) | (b3 >> 2);
		if(c4 != '=')
			*result++ = ((b3 & 0x3) << 6) | b4;
		
		if(i == last) break;
		i++;
	}
	return result;
}

// The end