生成Base64字符串

Base64字符串的应用很多,特别是在只能传输文本(比如HTML)的情况下。其用于将二进制的字节数据表示为文本。

比如ASP.NET的视图状态的传输就是使用了Base64:将页面上的各控件序列化成一串二进制数据,转换成Base64字符串后存于页面的隐藏域中在服务器和浏览器中来回传输来保存各控件的状态。

今天浏览ValueType的源代码的时候在Convert类中看到了将二进制数据转换成Base64字符串的方法,因此需要记录一下。

我很欣赏实现这些算法的人,其中一点就是尽可能地节省存储空间和提高性能(不像有些人写代码只要能用就行,而对存储空间、性能考虑得很少,这是我不喜欢的 →_→)。

本质上,Base64使用64种字符:A-Z、a-z、0-9、+、-、=。这样做的好处是在任何时候都能传输,不用考虑文字编码等问题。

现在进入正题,给我们的是一个byte*类型的数据,对于每一个字节,取值范围都是00~FF,而Base64的每个字节只有64种取值,所以要做一次转换。原来每个字节是8位,而现在每个字符的有效位是6位,那么至少要4个字符才能表示原来的3个字节数据。M$的设计人员正是使用4个字符表示3个字节的数据,把有效位利用得一干二净。

忽略掉代码的其他部分,最重要的映射部分的代码就是下面这样:

outChars[j] = base64[(inData[i]&0xfc)>>2]; 
outChars[j+1] = base64[((inData[i]&0x03)<<4) | ((inData[i+1]&0xf0)>>4)];
outChars[j+2] = base64[((inData[i+1]&0x0f)<<2) | ((inData[i+2]&0xc0)>>6)];
outChars[j+3] = base64[(inData[i+2]&0x3f)];

Base64数组是事先初始化好的,代表64个字符的其中一个,这里我们先忽略掉。

把这些位运算在表格中标注一下,我们就能发现outChars和inData的对应关系:

Capture

程序每次处理连续的3个字节A、B、C,生成4个字符1、2、3、4。从上图中可以看出对应关系:字节A的高6位存储在1字符中,低2位存储在2字符的高2位中;字符B的高4位存储在2字符的低4位中;以此类推,3个字节正好填满4个字符。

你之前可能就会发现不对啊,A-Z、a-z、0-9、+、-、=一共是65个字符。是,你总算发现了,上面的映射关系生成的字符只有64种,第65种=字符用于填充剩下的位(三字节一起处理,最后可能剩下一个或两个字节):

                switch(lengthmod3) 
                { 
                case 2: //One character padding needed
                    outChars[j] = base64[(inData[i]&0xfc)>>2]; 
                    outChars[j+1] = base64[((inData[i]&0x03)<<4)|((inData[i+1]&0xf0)>>4)];
                    outChars[j+2] = base64[(inData[i+1]&0x0f)<<2];
                    outChars[j+3] = base64[64]; //Pad
                    j+=4; 
                    break;
                case 1: // Two character padding needed 
                    outChars[j] = base64[(inData[i]&0xfc)>>2]; 
                    outChars[j+1] = base64[(inData[i]&0x03)<<4];
                    outChars[j+2] = base64[64]; //Pad 
                    outChars[j+3] = base64[64]; //Pad
                    j+=4;
                    break;
                }

在生成字符串前,M$会计算输出的字符串长度并恰好分配不多不少的空间给它:

            stringLength = ToBase64_CalculateAndValidateOutputLength(length, insertLineBreaks);

            string returnString = string.FastAllocateString(stringLength); 
            fixed (char* outChars = returnString){
                fixed (byte* inData = inArray) { 
                    int j = ConvertToBase64Array(outChars,inData,offset,length, insertLineBreaks); 
                    BCLDebug.Assert(returnString.Length == j, "returnString.Length == j");
                    return returnString; 
                }
            }

M$支持在输出的时候换行,看代码好像是写死的76个字节处换行,也就是生成的Base64字符串每100个字节换行,所以计算的代码如下:

        private static int ToBase64_CalculateAndValidateOutputLength(int inputLength, bool insertLineBreaks) {
            long outlen = ((long)inputLength) / 3 * 4;          // the base length - we want integer division here.
            outlen += ((inputLength % 3) != 0) ? 4 : 0;         // at most 4 more chars for the remainder

            if (outlen == 0)
                return 0; 

            if (insertLineBreaks) {
                long newLines = outlen / base64LineBreakPosition; 
                if ((outlen % base64LineBreakPosition) == 0) {
                    --newLines;
                }
                outlen += newLines * 2;              // the number of line break chars we'll add, "rn" 
            }

            // If we overflow an int then we cannot allocate enough 
            // memory to output the value so throw
            if (outlen > int.MaxValue) 
                throw new OutOfMemoryException();

            return (int)outlen;
}

加上换行符的代码并没有什么特别之处,我们也就不看了。

在.NET环境中,一个字符是2个字节,所以转换3个字节的数据,需要8个字节的存储空间(不考虑换行符的情况下)。在M$推崇的Unicode环境下,这也是无可奈何的。至少兼容ASCII是没有问题的。

现在我们来看解码的过程。

首先M$会把所有的空格都过滤掉(确切地说是编码小于空格的字符),这样估计是考虑到Web传输可能会有多余的空格吧:

            while (inputPtr < inputEndPtr) {

                UInt32 c = (UInt32) (*inputPtr); 
                inputPtr++;

                // We want to be as fast as possible and filter out spaces with as few comparisons as possible.
                // We end up accepting a number of illegal chars as legal white-space chars.
                // This is ok: as soon as we hit them during actual decode we will recognise them as illegal and throw.
                if (c <= intSpace) 
                    usefulInputLength--;

                else if (c == intEq) { 
                    usefulInputLength--;
                    padding++; 
                }
            }

接下来,根据=字符的个数计算最后有多少个字符补足:

            if (padding != 0) {

                if (padding == 1)
                    padding = 2; 
                else if (padding == 2) 
                    padding = 1;
                else 
                    throw new FormatException(Environment.GetResourceString("Format_BadBase64Char"));
            }

所以结果就是:

return (usefulInputLength / 4) * 3 + padding;

但是我们可以看到M$计算=号的时候把中间的都算进去了,不一定是末尾的。目测M$准备忽略掉输入字符的错误而尽可能地转换,即使输入非法 – -。

在依次读入字符的循环中,首先M$将输入字符转换成对应的Base64表中的对应位置:

                currCode = (UInt32) (*inputPtr); 
                inputPtr++;

                // Determine current char code:

                if (currCode - intA <= intAtoZ)
                    currCode -= intA; 

                else if (currCode - inta <= intAtoZ) 
                    currCode -= (inta - 26u); 

                else if (currCode - int0 <= int0to9) 
                    currCode -= (int0 - 52u);

                else {
                    // Use the slower switch for less common cases: 
                    switch(currCode) {

                        // Significant chars: 
                        case intPlus:  currCode = 62u;
                            break; 

                        case intSlash: currCode = 63u;
                            break;

                        // Legal no-value chars (we ignore these):
                        case intCRt:  case intNLn:  case intSpace:  case intTab: 
                            continue; 

                        // The equality char is only legal at the end of the input. 
                        // Jump after the loop to make it easier for the JIT register predictor to do a good job for the loop itself:
                        case intEq:
                            goto _EqualityCharEncountered;

                        // Other chars are illegal:
                        default: 
                            throw new FormatException(Environment.GetResourceString("Format_BadBase64Char")); 
                    }
                }

可以看出M$发现=符号直接就认为输入中止了,以后的字符也就不会处理(和前面的分配空间对应起来,似乎生成的空间是最大可能的情况,而不是准确的)。

接下来就是重点了:

                // Ok, we got the code. Save it:
                currBlockCodes = (currBlockCodes << 6) | currCode;

                // Last bit in currBlockCodes will be on after in shifted right 4 times:
                if ((currBlockCodes & 0x80000000u) != 0u) { 

                    if ((Int32) (endDestPtr - destPtr) < 3)
                         return -1; 

                    *(destPtr)     = (Byte) (currBlockCodes >> 16);
                    *(destPtr + 1) = (Byte) (currBlockCodes >> 8);
                    *(destPtr + 2) = (Byte) (currBlockCodes); 
                    destPtr += 3;

                    currBlockCodes = 0x000000FFu; 
                }

这个currBlockCodes就是M$用来判断是否读取了4个字符的标志。初始时值为FF,四次循环后这些1就被移动到了第2个字节的位置。

至于为什么不额外弄个计数器,目测M$是想减少运算量。这样在一次位运算中即可以保存转换后的值又可以知道是否读了4个字符(个人认为在这种比较“高级”的语言中不是很必要,而且循环次数也不会太多,因此也没多少用。在更底层的类库中,这也不失为一种好思路)。

中间的判断destPtr的if语句是保证程序不会出错,但我怎么觉得好像不可能会走到return -1的情况。

那么碰到=号后会中止流的读取。假如最后一个字符正好是=号,那么最后只有一个=对流进行补足,直接按一个=号的情况处理就可以了:

            if (inputPtr == endInputPtr) { 

                // Code is zero for trailing '=': 
                currBlockCodes <<= 6; 

                // The '=' did not complete a 4-group. The input must be bad: 
                if ((currBlockCodes & 0x80000000u) == 0u)
                    throw new FormatException(Environment.GetResourceString("Format_BadBase64CharArrayLength"));

                if ((int)(endDestPtr - destPtr) < 2)  // Autch! We underestimated the output length! 
                    return -1;

                // We are good, store bytes form this past group. We had a single "=", so we take two bytes: 
                *(destPtr++) = (Byte) (currBlockCodes >> 16);
                *(destPtr++) = (Byte) (currBlockCodes >> 8); 

                currBlockCodes = 0x000000FFu;

中间Autch注释的地方我也无力吐槽,如果出错了就说明计算长度的算法不对,为啥要在这里Autch。。。

               while (inputPtr < (endInputPtr - 1))
                { 
                     Int32 lastChar = *(inputPtr);
                     if (lastChar != (Int32) ' ' && lastChar != (Int32) 'n' && lastChar != (Int32) 'r' && lastChar != (Int32) 't')
                           break;
                    inputPtr++; 
                }

                if (inputPtr == (endInputPtr - 1) && *(inputPtr) == '=') { 

                    // Code is zero for each of the two '=': 
                    currBlockCodes <<= 12;

                    // The '=' did not complete a 4-group. The input must be bad:
                    if ((currBlockCodes & 0x80000000u) == 0u) 
                        throw new FormatException(Environment.GetResourceString("Format_BadBase64CharArrayLength"));

                    if ((Int32) (endDestPtr - destPtr) < 1)  // Autch! We underestimated the output length! 
                        return -1;

                    // We are good, store bytes form this past group. We had a "==", so we take only one byte:
                    *(destPtr++) = (Byte) (currBlockCodes >> 16);

                    currBlockCodes = 0x000000FFu; 

                } else  // '=' is not ok at places other than the end: 
                    throw new FormatException(Environment.GetResourceString("Format_BadBase64Char")); 

            }

这段代码是处理最后的情况:最后可能不止一个等号,其中还考虑了有空格等其他字符的额外情况。大家可以自行欣赏。

最终,假如转码后发现还有字符剩余(不足4个字符的情况),那么一定是输入有误(M$是这样认为的):

            if (currBlockCodes != 0x000000FFu) 
                throw new FormatException(Environment.GetResourceString("Format_BadBase64CharArrayLength"));

看到这里,相信大家都已经晕了。

个人认为M$这一块代码写得不好,计算长度、过滤额外字符、判断=号的逻辑很乱。就比如,假如不允许忽略掉=号后面其他字符而直接抛错的设计,以及字符数量不对,应该在计算长度的时候就能判断出,而不是转换到一半的地方又突然抛错……

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s