// MyStdlib.cpp: 数进制转换等公共函数
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "MyStdlib.h"
#include <string.h>
#include <winnls.h>
#include <ctype.h>
#include <stdlib.h>

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

#define Base64BITLen 6	//定义Base64BITLen以便以下代码快速兼容Base32、Base16等，（但Base32 和BASE16的码表与BASE64不一样，需要改c2digit方法，无须改动最复杂的bit计算部分）

//Base64编码。
//返回串在 dest 中。由调用者保证 dest 的长度，即 >= slen*4/3+4
void	base64Encode(char *dest, const char *src, int slen)
{
	unsigned dlen=0;
	unsigned short	dLastByte=0;	//从src中取出的可供取出一个以上6bit组的数据
	unsigned short	dBitsRemain=0;	//上者的bit数
	while (slen)
	{
		dLastByte = (dLastByte<<8) | ((unsigned char)*src++);	//读出下一个待编码字节
		dBitsRemain += 8;
		slen--;
		while ( dBitsRemain >= Base64BITLen )	//连同上次剩余bit（在高位），从高到低逐个6bit一组，查码表后压入到dest中。
		{
			dBitsRemain -= Base64BITLen;
			dest[dlen++] = digit2c(dLastByte>>dBitsRemain, 1<<Base64BITLen);
			dLastByte = dLastByte &((1<<dBitsRemain) - 1);	//剩余的数据
		}
	}

	if(dBitsRemain)	//须填充pad =
	{
		dest[dlen++] = digit2c(dLastByte<<(Base64BITLen-dBitsRemain), 1<<Base64BITLen);	//最后几个不足Base64BITLen的bit
		while (dBitsRemain)	//只要dest不能成整，则模拟src增加一个字节，继续处理
		{
			dBitsRemain += 8;
			while ( dBitsRemain >= Base64BITLen )
			{
				dBitsRemain -= Base64BITLen;
				dest[dlen++] = '=';
			}
		}
		dlen--;
	}
	dest[dlen]=0;
}

//把src字符串当做Base64对待，尽量还原出编码前数据到dest中。
//	dlen引用中包含成功解码出的字节数。
//返回：
//	0:表示src是严格语法的Base64字符串
//#define BASE64_DEC_ERR_NONE		0
//#define BASE64_DEC_ERR_FORMAT		0x1	//格式错误，比如\x错误。
//#define BASE64_DEC_ERR_INVALIDCHAR	0x2	//非法字符
//	3:上述1和2
//为了防止内存访问越界，需调用时保证 dest的长度不小于src的3/4。
//结果dest中可能包含字节0，所以需要结合返回值判断“字符串”的真正长度。
//容错方面：除了严格语法的Base64字符串（“严格”主要指=填充至slen为4的整数倍，且=以前没有码表以外的字符）以外，
//包括：1、最后的=填充不是必须的；2、即便src中包含了非Base64码表字符，也将返回已经解出的合法数据部分的结果。
unsigned	base64Decode(char *dest, const CString &src, int& dlen)
{
	dlen=0;
	BYTE dLastByte=0;	//记录上次循环后得到的半成品字节
	unsigned short	dBitsRemain=0;	//记录上次循环后得到的半成品字节还剩几个bit需要继续使用
	int slen=src.GetLength();
	unsigned err=BASE64_DEC_ERR_NONE;
	for (int i=0;i<slen;i++)
	{
		int digit=c2digit((char)src[i],1<<Base64BITLen);	//查码表得到数值
		if (digit==-1)	//碰到Base64码表以外的字符，包括=，则将结束解码
		{
			if (src[i] != '=') err |= BASE64_DEC_ERR_INVALIDCHAR;
			break;
		}
		dBitsRemain += Base64BITLen;
		if( dBitsRemain < 8 )	//不足输出一字节，暂存
			dLastByte = ( dLastByte << Base64BITLen ) + digit;
		else			//已足输出一字节
		{
			dBitsRemain = dBitsRemain - 8;
			dest[dlen++] = (dLastByte << (Base64BITLen-dBitsRemain)) + (digit>>dBitsRemain) ;//上次字节左移本次可用的几位，加上当前digit的高几位，凑足8位后新增到结果中
			dLastByte =(BYTE)(digit & ( (1<<Base64BITLen) - 1));	//当前digit的剩余低几位留待下次使用
		}
	}
	dest[dlen]=0;	//构造结束符，当调用者预期结果为ASCII串时可直接作为有结束符的ASCII串使用
	err |= BASE64_DEC_ERR_FORMAT;
	if ( (slen%4)==0 && (slen-i)<=2)
	{
		err &= ~BASE64_DEC_ERR_FORMAT;
		while(i<slen)
		{
			if (src[i++] != '=') err |= BASE64_DEC_ERR_FORMAT;;
		}
	}
	return err;
}

/*
关于Base64规则：
截位规则如下，摘自 RFC 3548：(http://www.ietf.org/rfc/rfc3548.txt)

in:	+----第1字节----+----第2字节----+----第3字节----+
	|7 6 5 4 3 2 1 0|7 6 5 4 3 2 1 0|7 6 5 4 3 2 1 0|
out:	+-----------+---+-------+-------+---+-----------+
	|5 4 3 2 1 0|5 4 3 2 1 0|5 4 3 2 1 0|5 4 3 2 1 0|
	+---1位码---+---2位码---+---3位码---+---4位码---+

  即：	in第1字节的高6位，导出out1；
		in第1字节的低2位加第2字节的高4位，导出out2；
		in第2字节的低4位加第3字节的高2位，导出out3；
		in第3字节的低6位，导出out4；
现在out1 2 3 4就是4个6bit的数值，其范围为0~63，再查询Base64码表，就可以得到编码后的字符了。
= pad填充规则：in不足3字节的，out=in*8/6往上取整且缺位填0，然后将剩下的out置为=
可以查阅 RFC 3548 第7章中的以下演示：
（提示，下述的 0x14fb9c03d97e 对应了内存中的顺序，也即0x14是第1个字节，而非在0x14fb9c03d97e整数中的第6个字节，
这涉及到大端小端的问题，后面再说。如果我们朝一个文件中 fprint(0x14fb9c03d97e)，则将是0x7e在第1个字节！！！）

  Input data:  0x14fb9c03d97e
       Hex:     1   4    f   b    9   c     | 0   3    d   9    7   e
       8-bit:   00010100 11111011 10011100  | 00000011 11011001
       11111110
       6-bit:   000101 001111 101110 011100 | 000000 111101 100111
       111110
       Decimal: 5      15     46     28       0      61     37     62
       Output:  F      P      u      c        A      9      l      +

       Input data:  0x14fb9c03d9
       Hex:     1   4    f   b    9   c     | 0   3    d   9
       8-bit:   00010100 11111011 10011100  | 00000011 11011001
                                                       pad with 00
       6-bit:   000101 001111 101110 011100 | 000000 111101 100100
       Decimal: 5      15     46     28       0      61     36
                                                          pad with =
       Output:  F      P      u      c        A      9      k      =

       Input data:  0x14fb9c03
       Hex:     1   4    f   b    9   c     | 0   3
       8-bit:   00010100 11111011 10011100  | 00000011
                                              pad with 0000
       6-bit:   000101 001111 101110 011100 | 000000 110000
       Decimal: 5      15     46     28       0      48
                                                   pad with =      =
       Output:  F      P      u      c        A      w      =      =


关于小端（Little Endian）和大端（Big Endian）的简要理解：
它是多字节（字节即8bit数据单元，也叫一个octet）数据保存到内存中的字节顺序规则。
	小端即“‘小’的字节在前‘端’”，比如一个2字节整数0xABCD，内存中是0xCD在前，0xAB在后；
	大端即“‘大’的字节在前‘端’”；同样还是2字节整数0xABCD，内存中是0xAB在前，0xCD在后；
请注意，我们说“大端”“小端”的是“字节”，其实是限定在8bit或者说256进制情况下来说的，因此，我们可
以扩展到从广义角度看，应该说所有进制位的排列都存在大端小端问题！同样拿0xABCD来说，在小端下放第一字节
的0xCD内，放在前4bit的却是0xC，0xC是0xCD的高4bit，所以属于“大端”规则。有点绕吗？说个简单点的例子就
好理解了，12月31日，记录成 "31-12"就是时间小端、月日各自大端，记录成"12-31"就是时间大端、月日各自大
端。而按秦始皇的要求，可能写成："13-21"，就是时间小端，月日各自小端。
*/
/*
MSDN 4.2.1 Integral Types and Values
The values of the integral types are integers in the following ranges:
	For byte, from -128 to 127, inclusive
	For short, from -32768 to 32767, inclusive
	For int, from -2147483648 to 2147483647, inclusive
	For long, from -9223372036854775808 to 9223372036854775807, inclusive
	For char, from '\u0000' to '\uffff' inclusive, that is, from 0 to 65535


“中”的ASCII定义： 	D6D0，或者 0xD0D6，由中国人分配
“中”的Unicdoe定义：	2D4E，或者 0x4E2D，由国际标准组织分配
“中”的UTF8编码：		E4B8AD，或者 0xADB8E4，根据 Unicode 值进行变换得到
2D4E的Base64：		LU4=
0x4E2D的Radix64：	E4t

E4B8AD 得到 4E2D 的转换过程：E4B8AD 的二进制：
11100100 10111000 10101101 ，在三个字节中各取低466位：
    0100   111000   101101 ，共16位，合并为2个字节：
01001110 00101101		，十六进制表达为：
4e 2d
*/

//替代 MS HIGHBYTE LOWBYTE 的函数
char	getlowbyte(wchar_t wchar)
{
	return (char)(wchar&0xFF);
}

char	gethighbyte(wchar_t wchar)
{
	return (char)((wchar&0xFF00)>>8);
}


//构造 IToA 查找表的一个区域。内部函数
int		MakeIToATableArea(UINT8* areaBegin, BYTE chBegin, int areaLen)
{
	for(int i=0; i<areaLen; i++)
		*areaBegin++ = chBegin++;
	return areaLen;
}

//把一个进制的数值转换为编码字符
//输入：digit是待转的数值，radix是进制基数，取值范围为2~64。
//返回：如果radix超出2~64范围，或者digit值超出 0~radix-1范围，则返回'\xFF'表示出错，否则返回编码字符
//码表分为两段规则：
//	2~36之间的进制用十六进制一样的码表即：	0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ
//	37~64之间的进制用BASE64一样的码表即：	ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
// !!!!!!!!!! 因此按RFC3548写Base32算法的话则不要使用此函数。Base32的码表为：ABCDEFGHIJKLMNOPQRSTUVWXYZ234567。（0相似于O、1相似于l故弃用）
char	digit2c(UINT8 digit, UINT8 radix)
{
	static UINT8 tableIToA[36+64];	//2~36进制以及 37~64进制的查找表。通过查找表，获得速度性能
	if(tableIToA[0] == 0)	//0:static变量或全局变量的初始化值
	{//首次被调用时，将构造查找表
		UINT8* p = tableIToA;
		p += MakeIToATableArea(p, '0', 10);	//36进制码表的数值段
		p += MakeIToATableArea(p, 'A', 26);	//36进制码表的字母段。如果需要小写，则把 A 换 a，或者对返回结果再转
		p += MakeIToATableArea(p, 'A', 26);	//64进制码表的大写字母段
		p += MakeIToATableArea(p, 'a', 26);	//64进制码表的小写字母段
		p += MakeIToATableArea(p, '0', 10);	//64进制码表的数值段
		*p++ = '+';								//64进制码表的第63个字符：'+'
		*p++ = '/';								//64进制码表的第64个字符：'/'
	}
	char ret;
	if(radix>64 || radix<2 || digit>=radix)
		ret='\xFF';					//容错，返回 '\xFF'
	else if(radix<=36)
		ret = tableIToA[digit]; 		//2~36之间的进制
	else
		ret = tableIToA[36+digit];		//37~64之间的进制
	return ret;
}

//构造 AToI 查找表的一个区域。内部函数
UINT8	MakeAToITableArea(__int8* table, BYTE chBegin, UINT8 digitBegin, UINT8 areaLen)
{
	for(UINT8 i=0; i<areaLen; i++)
		table[chBegin++] = digitBegin++;
	return areaLen;
}

#define InvalidDigit	-1	//
//digit2c的逆。出错时返回 InvalidDigit(-1)
//当radix为11~36之间时，C不区分大小写。
__int8	c2digit(char c, UINT8 radix)
{
	static __int8 tableAToI[128+128];	//2~36 进制和 37~64 进制的查找表。通过查找表，获得速度性能
	static __int8* table64 = &tableAToI[128];
	if(tableAToI[0] == 0)	//0:static变量或全局变量的初始化值
	{//首次被调用时，将构造查找表
		memset(tableAToI, InvalidDigit, sizeof(tableAToI));
		UINT8 digit=0;
		digit += MakeAToITableArea(tableAToI, '0', digit, 10);	//36进制码表的数值段
				 MakeAToITableArea(tableAToI, 'A', digit, 26);	//36进制码表的大写字母段
				 MakeAToITableArea(tableAToI, 'a', digit, 26);	//36进制码表的小写字母段，和大写字母段一样初始化
		digit = 0;
		digit += MakeAToITableArea(table64, 'A', digit, 26);	//64进制码表的大写字母段
		digit += MakeAToITableArea(table64, 'a', digit, 26);	//64进制码表的小写字母段
		digit += MakeAToITableArea(table64, '0', digit, 10);	//64进制码表的数值段
		table64['+'] = 62;								//64进制码表的第63个字符：'+'
		table64['/'] = 63;								//64进制码表的第64个字符：'/'
	}
	if(radix>64 || radix<2 ||(BYTE)c > 128 )	return InvalidDigit;		//容错，返回-1
	__int8 digit;
	if(radix<=36)
		digit = tableAToI[c];
	else
		digit = table64[c];
	if(digit>=radix)
		digit = InvalidDigit;	//digit结果超出radix的范围，说明调用者出现了逻辑错误，比如在10进制中查A，则也返回 -1
	return digit;
}

//C stdlib atoi() 的替代与增强
//注：如果 a 不由 "-" 号开头，且转出结果的最高位为1（即介于0x8000000000000000 ~0xffffffffffffffff 之间），则返回结果为负数，但根据C编译器的处理机制，仍可以无损地赋值给 UINT64 型变量得到正确结果（另外，此时 Err 并不会被置为 ERROR_OVERFLOW）
//返回：转换出的数值。注意即使遇到超长或者非法字符，也将返回最接近结果的值
//Err如果指向非空，则被置为 ERROR_NONE \ ERROR_INVALIDCHAR \ ERROR_OVERFLOW  之一。
//特别情况：如果 a 指向 NULL 或者长度为0，则返回0，且 Err=ERROR_INVALIDCHAR
INT64	AtoI(const TCHAR *a, UINT8 radix, unsigned* Err)
{
	bool isNeg = FALSE;
	size_t aLen = 0;
	if(a)	// _tcslen(NULL) 会导致 Access violation 错误
	{
		aLen = _tcslen(a);
		if( *a == '-')
		{
			isNeg = TRUE;
			a++;
			aLen--;
		}
	}

	UINT64 ui64 = 0;
	unsigned err = ERROR_INVALIDCHAR;	// a 可能为 NULL 或0空，则初始化为 ERROR_INVALIDCHAR
	for(size_t i=0; i<aLen; i++)
	{
		int digit = c2digit((char)*a++, radix);
		if (digit == InvalidDigit)	//输入的字符串中有非法字符，则置标志后结束转换。
		{
			err = ERROR_INVALIDCHAR;
			break;
		}
		else
		{
			UINT64 i64tmp = ui64 * radix;
			if (i64tmp < ui64)				// INT64溢出
			{
				err = ERROR_OVERFLOW;
				break;
			}
			else
			{
				err = ERROR_NONE;	//发现有效字符，暂认为合法
				ui64 = i64tmp + digit;
			}
		}
	}
	INT64 ret = (INT64)ui64;	//依赖：UINT64 到 INT64 转换不会改变所有的bit位
	if(isNeg)
	{
		ret = -ret;
		if(ret > 0)
			err = ERROR_OVERFLOW;	//输入了 -9223372036854775809(-0x8000000000000001) ~ -18446744073709551615(-0xFFFFFFFFFFFFFFFF)
	}
	
	if (Err)
		*Err = err;
	return ret;
}

//C stdlib itoa() 的替代与增强: 进制支持到64，并支持填充头'0'或'A'到 padLen 长度，以达到 sprintf "%08X"的效果
//如果 padLen 小于itoa()结果的长度, 则不会填充'0'或'A'，效果等于普通的 itoa()
//当 i 的bit63为1且需要作为正数对待的时候，需把 isSigned 参数置 FALSE。
//返回转换出的字符串
TCHAR*	ItoA(INT64 i64, TCHAR *aDest, UINT8 radix, unsigned padLen, bool isSigned)
{
	UINT64 ui64tmp;
	if(isSigned)
	{
		if(i64<0)
			ui64tmp = -i64;
		else
			ui64tmp = i64;
	}
	else
		ui64tmp = (UINT64) i64;	//-9223372036854775808(-0x8000000000000000) ~ -1 被解释为 9223372036854775808(0x8000000000000000)  ~ 18446744073709551615(0xFFFFFFFFFFFFFFFF)
//逐位处理
	TCHAR *a1 = aDest;
	TCHAR *a2 = a1;
	do		//用 do ... while ... 结构，可以使 0 转换到 "0"(大于36进制时为"A")
	{
		*a2++ = digit2c((UINT8)(ui64tmp%radix), radix);
		ui64tmp = ui64tmp / radix;
	}	while (ui64tmp > 0);
//填充'0'或'A'
	while( (unsigned)(a2-a1) < padLen )
		*a2++ = digit2c(0,radix);
//对负数置 '-' 负号
	if(i64<0 && isSigned)
		*a2++ = '-';
//填尾0
	*a2-- = 0;

//颠倒顺序
	while (a2>a1) { TCHAR c=*a1; *a1++ = *a2; *a2-- = c; }
	return aDest;
}

//Hexdump，就是 HEX Dump，没啥说的。和unix系统的 hexdump 的效果完全一样，和 WinHex或者Ultraedit的hex显示模式也一样除了没有空格以外
//按照Hexdump习惯，src 被以无符号方式处理，即80~FF以正数而不是负数对待。
void	hexdump(TCHAR *dest, const unsigned char *src, unsigned slen)
{
	for (unsigned int i=0; i<slen; i++)
	{
		ItoA(src[i], dest, 16, 2);
		dest++; dest++;
	}
	*dest = 0;	// ItoA 方法也会置尾0，但如果 slen = 0，则须在此处完成置尾0
}