/*
								+----------------------------------+
								|                                  |
								|  ***   Base85 coder class   ***  |
								|                                  |
								|   Copyright © -tHE SWINe- 2014   |
								|                                  |
								|            Base85.cpp            |
								|                                  |
								+----------------------------------+
*/

/**
 *	@file Base85.cpp
 *	@author -tHE SWINe-
 *	@date 2014
 *	@brief Base-85 encoding implementation
 */

#include "CallStack.h"
#include "NewFix.h"
#include <string.h> // strlen
#include "Base85.h"
#include "MinMax.h"

/*
 *								=== CModifiedBase85::CInverseTable ===
 */

CModifiedBase85::CInverseTable::CInverseTable(const char *p_s_encode_table
	/*= CModifiedBase85::p_s_Default_EncodeTable()*/)
{
	for(int i = 0; i < 256; ++ i)
		m_p_decode[i] = -1;
	for(int i = 0; i < 85; ++ i)
		m_p_decode[(unsigned char)p_s_encode_table[i]] = i;
	// decoding table
}

/*
 *								=== ~CModifiedBase85::CInverseTable ===
 */

/*
 *								=== CModifiedBase85 ===
 */

const CModifiedBase85::CInverseTable CModifiedBase85::m_default_invtable;

size_t CModifiedBase85::n_DecodedSize_ExplicitNull(const char *p_s_base85,
	size_t n_length /*= size_t(-1)*/, const int *p_decode_table /*= p_Default_DecodeTable()*/)
{
	_ASSERTE(p_s_base85);
	if(n_length == size_t(-1))
		n_length = strlen(p_s_base85);
	// calculate length

	size_t n_output_size = 0;
	const char *p_s_src = p_s_base85, *p_s_end = p_s_base85 + n_length;
	for(size_t i = 0; i < n_length; ++ i, ++ p_s_src) {
		if(p_decode_table[*p_s_src] == 84) {
			if(n_output_size > SIZE_MAX - 4)
				return size_t(-1); // would overflow
			n_output_size += 4;
		} else {
			size_t n_remains = min(n_length - i, size_t(5));
			//n_output_size2 += (n_remains == 5)? 4 : n_remains - 1;
			if(n_output_size > SIZE_MAX - (n_remains - 1))
				return size_t(-1); // would overflow
			n_output_size += n_remains - 1;
			i += 4;
			p_s_src += 4;
		}
	}

	return n_output_size;
}

size_t CModifiedBase85::n_Encode(size_t n_dest_size, void *p_dest, size_t n_size,
	const void *p_data, bool b_allow_explicit_null /*= false*/,
	const char *p_s_encode_table /*= p_s_Default_EncodeTable()*/)
{
	_ASSERTE(p_dest);
	_ASSERTE(p_data);
	if(n_size > n_Max_EncodeSize())
		return false;
	if(n_dest_size < n_EncodedSize_UpperBound(n_size))
		return 0; // error

	char *p_dest8 = (char*)p_dest;
	const uint8_t *p_data8 = (const uint8_t*)p_data;
	for(size_t i = 0, n = n_size - 3; i < n; i += 4, p_data8 += 4) {
		uint32_t n_code = (p_data8[0] << 24) |
			(p_data8[1] << 16) | (p_data8[2] << 8) | p_data8[3];
		if(b_allow_explicit_null && !n_code) {
			*p_dest8 = p_s_encode_table[84];
			++ p_dest8;
			// note that there could also be a character to represent null
			// alternately, because 5 base 85 digits max with "~~~~~" = 4437053125
			// but maximum 32-bit number is 4294967296, the maximum value can only start
			// with 82 digit "|", so anything starting with "~" is invalid and can
			// be used to represent null
		} else {
			char p_out[5];
			for(int i = 0; i < 5; ++ i, n_code /= 85)
				p_out[4 - i] = n_code % 85;
			for(int i = 0; i < 5; ++ i, ++ p_dest8)
				*p_dest8 += p_s_encode_table[p_out[i]];
			// big endian
		}
	}
	int n_modsize;
	if((n_modsize = int(n_size % 4))) {
		uint32_t n_code = (p_data8[0] << 24) |
			((n_modsize >= 2)? p_data8[1] << 16 |
			((n_modsize == 3)? p_data8[2] << 8 : 0) : 0);
		// calculate value

		// no explicit nulls here

		char p_out[5];
		for(int i = 0; i < 5; ++ i, n_code /= 85)
			p_out[4 - i] = n_code % 85;
		for(int i = 0, n = n_modsize + 1; i < n; ++ i, ++ p_dest8)
			*p_dest8 += p_s_encode_table[p_out[i]];
		// each digit stores 6.409 bits; three missing characters = -24, amounts to
		// threee and three quarter missing digits; two missing characters = -16, two
		// and a half missing digits; one missing character = -8 bits, one missing digit
	}
	_ASSERTE((p_dest8 - (char*)p_dest) * sizeof(char) <= n_EncodedSize_UpperBound(n_size));
	// encode Base-85

	return (p_dest8 - (char*)p_dest) * sizeof(char);
}

bool CModifiedBase85::Decode(size_t n_dest_size, void *p_dest, const char *p_s_base85,
	size_t n_length /*= size_t(-1)*/, bool b_allow_explicit_null /*= false*/,
	const int *p_decode_table /*= p_Default_DecodeTable()*/)
{
	_ASSERTE(p_s_base85);
	if(n_length == size_t(-1))
		n_length = strlen(p_s_base85);
	// calculate length

	_ASSERTE(b_allow_explicit_null || (n_length % 5 == 0 || n_length % 5 >= 2));
	// if there are no explicit nulls, there are always at least two extra digits (or no extra digits at all)

#if 0
	size_t n_min_output_size = (n_length / 5) * 4 + max(n_length % 5, 1) - 1;
	// if there are no explicit nulls, it is the exact size - otherwise it can be up to 5 times bigger

	size_t n_output_size = 0;
	if(b_allow_explicit_null) {
		/*const char *p_s_src = p_s_base85, *p_s_end = p_s_base85 + n_length;
		for(size_t n_diff, n_rem = n_length; p_s_src < p_s_end;
		   p_s_src += n_diff * 4 + 1, n_rem -= n_diff * 4 + 1)
			n_output_size += (n_diff = (p_decode_table[*p_s_src] != 84))? min(n_rem, 5) - 1 : 4;*/
		/*for(size_t n_diff, n_rem = n_length; p_s_src < p_s_end; p_s_src += n_diff, n_rem -= n_diff) {
			n_output_size += (n_diff = (p_decode_table[*p_s_src] == 84))? 4 : min(n_rem, 5) - 1;
			n_diff = (n_diff)? 1 : 5;
		}*/
		/*for(bool b_null; p_s_src < p_s_end; p_s_src += (b_null)? 1 : 5) {
			n_output_size += (b_null = (p_decode_table[*p_s_src] == 84))? 4 :
				min(p_s_end - p_s_src, 5) - 1;
		}*/
		size_t n_output_size2 = 0;
		{
			const char *p_s_src = p_s_base85, *p_s_end = p_s_base85 + n_length;
			for(size_t i = 0; i < n_length; ++ i, ++ p_s_src) {
				if(p_decode_table[*p_s_src] == 84) {
					n_output_size2 += 4;
				} else {
					size_t n_remains = min(n_length - i, 5);
					//n_output_size2 += (n_remains == 5)? 4 : n_remains - 1;
					n_output_size2 += n_remains - 1;
					i += 4;
					p_s_src += 4;
				}
			}
		}
		n_output_size = n_output_size2;
		_ASSERTE(n_output_size == r_s_dest.size()); // i put it there outside
	} else
		n_output_size = n_min_output_size;
	// exact output size by prescanning the input
#else
	size_t n_min_output_size = n_DecodedSize(n_length * sizeof(char));
	size_t n_output_size = (b_allow_explicit_null)? n_DecodedSize_ExplicitNull(p_s_base85,
		n_length, p_decode_table) : n_min_output_size;
#endif

	try {
#if 0
		char p_extra[] = {33, 35, 36, 37, 38, 40, 41, 42, 43, 45, 59, 60, 61, 62, 63, 64, 94, 95, 96, 123, 124, 125, 126};
		char p_extra33[] = {0, 2, 3, 4, 5, 7, 8, 9, 10, 12, 26, 27, 28, 29, 30, 31, 61, 62, 63, 90, 91, 92, 93};
		char p_extra33i[] = {0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 16, 16, 16, 16, 16, 16, 45, 45, 45, 71, 71, 71, 71};
		char p_extra62[] = {33, 35, 36, 37, 38, 40, 41, 42, 43, 45, 59, 60, 61, 62, 63, 64, 94, 95, 96, 123, 124, 125, 126};
		char p_ic_tab[128] = {0};
		for(int i = 0, j = -62, k = 65; i < 85; ++ i, ++ j, ++ k)
			p_ic_tab[(i < 52)? k + i / 26 * 6 : (j < 0)? i - 4 : "!#$%&()*+-;<=>?@^_`{|}~"[j]] = i;
		//for(int i = 0; i < 85; ++ i)
			//p_ic_tab[(i < 52)? 5 + i + (i / 26 + 10) * 6 : (i < 62)? i - 4 : p_extra33i[i - 62] + 33 + i - 62] = i;
			//p_ic_tab[(i < 52)? 5 + i + (i + 260) / 26 * 6 : (i < 62)? i - 4 : p_extra33i[i - 62] + 33 + i - 62] = i;
			//p_ic_tab[(i < 52)? 65 + i + i / 26 * 6 : (i < 62)? i - 4 : p_extra33i[i - 62] + 33 + i - 62] = i;
			//p_ic_tab[(i < 52)? 65 + i + i / 26 * 6 : (i < 62)? i - 4 : "!#$%&()*+-;<=>?@^_`{|}~"[i - 62]] = i;

		// the below ones work with the original table 0-9A-Za-zspecials, the above with modified A-Za-z0-9specials
		for(int i = 0, j = -10, k = 55, l = -62; i < 85; ++ i, ++ j, ++ k, ++ l)
			p_ic_tab[(j < 0)? k - 7 : (l < 0)? k + j / 26 * 6 : "!#$%&()*+-;<=>?@^_`{|}~"[l]] = i;
		//for(int i = 0; i < 85; ++ i)
			//p_ic_tab[(i < 10)? 48 + i : (i < 62)? i + 1 + (i + 224) / 26 * 6 : p_extra33i[i - 62] + 33 + i - 62] = i;
			//p_ic_tab[(i < 10)? 48 + i : (i < 62)? i + 1 + (i + 224) / 26 * 6 : "!#$%&()*+-;<=>?@^_`{|}~"[i - 62]] = i;
			//p_ic_tab[(i < 10)? '0' + i : (i < 62)? 55 + i + (i - 10) / 26 * 6 : "!#$%&()*+-;<=>?@^_`{|}~"[i - 62]] = i;
			//p_ic_tab[(i < 10)? '0' + i : (i < 62)? 'A' + i - 10 + (i - 10) / 26 * 6 : "!#$%&()*+-;<=>?@^_`{|}~"[i - 62]] = i;
			//p_ic_tab[(i < 10)? '0' + i : (i < 62)? 'A' + i - 10 + (i - 10) / 26 * (32 - 26) : "!#$%&()*+-;<=>?@^_`{|}~"[i - 62]] = i;
			//p_ic_tab[(i < 10)? '0' + i : (i < 62)? 'A' + (i - 10) % 26 + (i - 10) / 26 * 32 : "!#$%&()*+-;<=>?@^_`{|}~"[i - 62]] = i;
			//p_ic_tab[(i < 10)? '0' + i : (i < 62)? ('A' + (i - 10) % 26) | ((i - 10) / 26 * 32) : "!#$%&()*+-;<=>?@^_`{|}~"[i - 62]] = i;
			//p_ic_tab[(i < 10)? '0' + i : (i < 62)? ('A' + (i - 10) % 26) | (((i - 10) / 26) << 5) : "!#$%&()*+-;<=>?@^_`{|}~"[i - 62]] = i;
			//p_ic_tab[(i < 10)? '0' + i : (i < 36)? 'A' - 10 + i : (i < 62)? 'a' - 36 + i : "!#$%&()*+-;<=>?@^_`{|}~"[i - 62]] = i;
			//p_ic_tab["0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!#$%&()*+-;<=>?@^_`{|}~"[i]] = i;
		const char *p_s_end = p_s_base85 + n_length;
		r_s_dest.resize(n_output_size);
		uint8_t *p_dst = (uint8_t*)p_dest - 1;
		for(size_t n_rem = n_length; p_s_base85 != p_s_end; -- n_rem) {
			if(b_allow_explicit_null && p_ic_tab[*p_s_base85] == 84) {
				*(uint32_t*)((p_dst += 4) - 3) = 0;
				++ p_s_base85;
			} else {
				uint32_t n_block = uint32_t(min(n_rem, size_t(5))), n_code = 0;
				_ASSERTE(n_block >= 2);
				for(unsigned int i = 0; i < 5; p_s_base85 += (++ i <= n_block))
					n_code = n_code * 85 + ((i < n_block)? p_ic_tab[*p_s_base85] : 84);
				/*for(const char *p_s_end2 = p_s_base85 + n_block; p_s_base85 != p_s_end2; ++ p_s_base85)
					n_code = n_code * 85 + p_ic_tab[*p_s_base85];
				const int p_multiple[] = {0, 0, 614125, 7225, 85, 1};
				n_code = n_code * p_multiple[n_block] + p_multiple[n_block] - 1;
				//for(int j = n_block; j < 5; ++ j) // n_block can be 2, 3, 4, 5, for 5 this is no-op
				//	n_code = n_code * 85 + 84; // apply the remaining power, pad with ones*/
				for(unsigned int j = 1; j < n_block; ++ j, -- n_rem)
					*(++ p_dst) = n_code >> (8 * (4 - j));
				// write data to output
			}
		}
#else
		uint8_t *p_dst = (uint8_t*)p_dest;
		for(size_t i = 0; i < n_length; ++ i, ++ p_s_base85) {
			if(p_decode_table[*p_s_base85] == -1)
				return false;
			if(b_allow_explicit_null && p_decode_table[*p_s_base85] == 84) {
				for(int j = 0; j < 4; ++ j, ++ p_dst)
					*p_dst = 0;
			} else {
				int n_remains = min(n_length - i, size_t(5));
				if(n_remains < 2)
					return false; // cannot decode only a single character
				uint32_t n_code = 0;
				for(size_t n_end = i + min(n_remains, 4); i < n_end; ++ i, ++ p_s_base85) { // only add four digits first
					if(p_decode_table[*p_s_base85] == -1)
						return false;
					n_code = n_code * 85 + p_decode_table[*p_s_base85];
				}
				if(n_remains == 5) {
					int n_digit = p_decode_table[*p_s_base85];
					//++ p_s_base85;
					//++ i; // to compensate for the ++ i in the outer loop
					if(n_digit == -1)
						return false;
					if(n_code > UINT32_MAX / 85)
						return false;
					n_code *= 85;
					if(n_code > UINT32_MAX - n_digit)
						return false;
					n_code += n_digit;
				} else {
					for(int j = n_remains; j < 5; ++ j) {
						if(n_code > UINT32_MAX / 85)
							return false;
						n_code *= 85;
						if(n_code > UINT32_MAX - 84)
							return false;
						n_code += 84;
					}
					// apply the remaining power

					-- p_s_base85;
					-- i;
					// to compensate for the ++ i in the outer loop
					// note that these do not matter as this is the last iteration anyway
				}
				// handle possible overflows in the last digit

				for(int j = 0, n_output = n_remains - 1; j < n_output; ++ j, ++ p_dst)
					*p_dst = n_code >> (8 * (3 - j));
				// write data to output
			}
		}
#endif
		_ASSERTE(p_dst - (uint8_t*)p_dest == n_output_size);
		// decode Base-85
	} catch(std::bad_alloc&) {
		return false;
	}

	return true;
}

/*
 *								=== ~CModifiedBase85 ===
 */
