关于base64的一点理解

以前只知道base64是一种编码字节串的算法,但对于它的原理实际并没有多少认识。 前段时间由于一个相关bug,重新深入地了解了下,发现其实非常简单,也很好理解。

如果让我想一种此类的编码算法,第一时间想到的大概就是十六进制表示了,姑且在本文中称作十六进制编码吧。

举个例子,假设一个二进制文件只包含3个字节,都是非打印字符:

char bytes[] = {1, 133, 254};

其十六进制编码表示,即编码结果就是0185fe。

但这个算法的结果串的长度是输入串的两倍,因为需要用两个字节才能表示输入的一个字节。 究其原因,在于没有充分利用可打印字符,才使用了16个。

接下来再来说说base64。从字面看,base64的意思就是“基于64的”,完整的含义是基于64个可打印字符的编码。 标准base64编码使用的64个字符就是英文字母a-zA-Z,数字0-9,外加两个符号+/

而64是2的6次方:

Python 2.7.13 (default, Jan 12 2017, 17:59:37)
[GCC 6.3.1 20161221 (Red Hat 6.3.1-1)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 2**6
64

6个二进制位只能有64种取值,换句话说,以上64个字符可以与6个位的取值一一对应。

从位的角度看,字节串是一堆位串,实际任何内容在位这一级都是一堆位串, base64编码要做的就是把位串按6个一组进行分组, 然后按照映射表,把每组用base64字符表示,就得到了编码结果,映射表详见Wikipedia。

00000001 10000101 11111110      // 每个字节用位表示
000000 011000 010111 111110     // base64重新分组后
AYX+                            // 编码结果。根据映射表进行base64编码,000000对应A……

再来看看base64的“空间效率”,姑且这么说吧。

因为一个输入串是字节表示的,每个字节有8位;而base64按6位分组,6和8的最小公倍数是24, 即3个输入字节,被编码为4个字节,长度只比之前多1/3,比十六进制编码的多100%好很多。

上述最小公倍数决定了base64最少能编码的字节数是3,不足3时需要以字节0补全(padding),补1个或者2个。 为区别补全的0和正常输入字节的0,需要对全是补全0的组的编码结果作特殊处理,用等号=表示。 等号字符不在64个编码字符内,只可能出现在编码串的尾部。

实际上等号并不是必须的,因为上述算法决定了一个有效的base64串,其长度必然是4的倍数。 在解码base64串时,可以对串长度进行一个判断,不足时在尾部补上等号即可。

但最多只可能补2个等号,这是上述补全的机制决定的。补全两个字节0,编码串会有两个等号; 补全一个字节0时,编码串只有一个等号。这点可以在Python shell进行快速验证:

>>> import base64
>>> base64.decodestring('ab==')
'i'
>>> base64.decodestring('ax==')
'k'
>>> base64.decodestring('axc=')
'k\x17'
>>> base64.decodestring('a===')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib64/python2.7/base64.py", line 328, in decodestring
    return binascii.a2b_base64(s)
binascii.Error: Incorrect padding

另外,base64在发展过程中,形成了很多变种,归根结底还是因为不同协议支持的“字符集”不同, 比如在URL参数中,+/这两个符号就还需要进一步编码,这样URL兼容的base64编码变种就会改用其他2个标点符号-_

> param = "+/"
< "+/"
> encodeURIComponent(param)
< "%2B%2F"

写到这里,我发现上述两种编码方法原理其实是一样的:都是先对位流进行分组,再对每组按照固定的映射表进行编码。

不同的地方在于两者分组中包含的位个数不一样,十六进制编码每组只包含4个位,故只要16个十六进制字符就足够表示了。

同时,可以看到组中位数越多,同一个字节串的编码结果越短。 所以如果有base128(组包含7个位),那编码效率就更高了,但这需要128个可打印字符,而ASCII只有95个可见字符, 所以这无法实现:

#include <stdio.h>
#include <ctype.h>

int
main(void)
{
    int i, n;

    for(i = 0, n = 0; i < 256; i++) {
        if(isprint(i)) {
            printf("%c ", i);
            n++;
        }
        if(n && 0 == (n % 20))
            printf("\n");
    }

    printf("\nThere are %d printable ASCII characters above.\n", n);
}

运行以上代码可以看到只有95个可打印字符:

$ ./a.out
  ! " # $ % & ' ( ) * + , - . / 0 1 2 3
4 5 6 7 8 9 : ; < = > ? @ A B C D E F G
H I J K L M N O P Q R S T U V W X Y Z [
\ ] ^ _ ` a b c d e f g h i j k l m n o
p q r s t u v w x y z { | } ~
There are 95 printable ASCII characters above.

BTW,Python base64模块支持标准的(base64.standard_b64encode)、 URL安全的(base64.urlsafe_b64encode),以及自定义的(base64.b64encode)base64编码, 详见Python base64模块文档

social