base64编码的原理与实现

摘要: Base64 编码的原理、实现与应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们学习一下 Base64 编码的原理与实现，给出一个代码模板，并用代码模板解决力扣 535. TinyURL 的加密与解密。

Base64 编码

(1) 背景

Base64 是一种二进制转换到文本的编码方式，它能够将任意二进制数据转换为ASCII字符串的形式，以便在只支持文本的环境中也能够顺利地传输二进制数据，例如图片数据。

Base64 分为编码和解码两步：

• (1) base64编码：把二进制数据转为字符。
• (2) base64解码：把字符转为二进制数据。

例如在网络传输中常见的传输 8bit 字节码的需求，Base64是常见的编码方式之一，它基于64个可打印字符来表示二进制数据，可用于在HTTP环境下传递较长的标识信息。采用Base64编码具有不可读性，需要解码后才能阅读。

(2) 标准 Base64 原理

以下索引与字符的索引表是标准Base64标准协议规定的，不能更改。64个字节用6个bit位就可以全部表示（32+16+8+4+2+1）就可以全部表示。

索引	字符	索引	字符	索引	字符	索引	字符	索引	字符	索引	字符	索引	字符	索引	字符
0	A	8	I	16	Q	24	Y	32	g	40	o	48	w	56	4
1	B	9	J	17	R	25	Z	33	h	41	p	49	x	57	5
2	C	10	K	18	S	26	a	34	i	42	q	50	y	58	6
3	D	11	L	19	T	27	b	35	j	43	r	51	z	59	7
4	E	12	M	20	U	28	c	36	k	44	s	52	0	60	8
5	F	13	N	21	V	29	d	37	l	45	t	53	1	61	9
6	G	14	O	22	W	30	e	38	m	46	u	54	2	62	+
7	H	15	P	23	X	31	f	39	n	47	v	55	3	63	/

Base64要求把每三个8Bit的字节转换为四个6Bit的字节(3*8 = 4*6 = 24)，然后把6Bit再添两位高位0，组成四个8Bit的字节，也就是说，转换后的字符串理论上将要比原来的长1/3。

总结：一个Base64字符是8个bit，但有效部分只有右边6个bit，左边两个永远是0。

例如 11111111,11111111,11111111 -> 00111111,00111111,00111111,00111111。

(3) 算法

3 个传统字节可以对应 4 个 Base64 字符。

编码

• 3 字节一组遍历二进制数据 data。
• 6 位一组遍历当前的 3 字节数据，得到 4 个 base64 字符。

最后如果不够三字节了：

• 如果剩一个字符，用两个 base64 表示这个字符，最后补 4 个 0 得到最后一组 6 个位，最终还少一个 base64，用两个 '=' 填充。
• 如果剩两个字符，用三个 base64 表示这两个字符，最后补 2 个 0 得到最后一组 6 个位，最终还少一个 base64，用一个 '=' 填充。

解码

• 4 个字符一组遍历字符串。
• 对每个字符，取前 6 位，将信息放进一个 int，低 24 位是有效信息。
• 将所得 int 每 8 位一取从低 24 位取出 3 个字符。

最后一组 4 个字符需要特判：

• 没有 '='，正常解码，得 3 个字符。
• 1 个 '='，最终有 2 个字符，取前 3 个字符的 6 位，再向右移 2 位，得 16 位信息，解码出两个字符。
• 2 个 '='，最终有 1 个字符，取前 2 个字符的 6 位，再向右移 4 位，得 8 位信息，解码出一个字符。

URL 场景优化

标准的 Base64 并不适合直接放在 URL 里传输，因为 URL 编码器会把标准 Base64 中的 ‘/‘ 和 ‘+’ 字符变为形如 “%XX” 的形式，而这些 “%” 号在存入数据库时还需要再进行转换，因为 ANSI SQL 中已将 “%” 号用作通配符。
为解决此问题，可采用一种用于 URL 的改进 Base64 编码，它在末尾填充’=’号，并将标准 Base64 中的 ‘+’ 和 ‘/‘ 分别改成了 ‘-‘ 和 ‘_’，这样就免去了在 URL 编解码和数据库存储时所要作的转换，避免了编码信息长度在此过程中的增加，并统一了数据库、表单等处对象标识符的格式。

(4) 代码 （模板，C++）

URL 场景优化的 Base64 实现

char base64_code(const int& mask)
{
    if(mask <= 25)
        return 'A' + mask;
    else if(mask <= 51)
        return 'a' + mask - 26;
    else if(mask <= 61)
        return '0' + mask - 52;
    else if(mask == 62)
        return '-';
    else if(mask == 63)
        return '_';
    else
        throw "编码 mask 超出 6 bit 范围(0~63)";
}

int reverse_base64_code(const char& ch)
{
    if('A' <= ch && ch <= 'Z')
        return ch - 'A';
    else if('a' <= ch && ch <= 'z')
        return ch - 'a' + 26;
    else if('0' <= ch && ch <= '9')
        return ch - '0' + 52;
    else if(ch == '-')
        return 62;
    else if(ch == '_')
        return 63;
    else
        throw "解码 mask 超出 6 bit 范围(0~63)";
}

class Base64
{
public:
    string encode(string data) {
        int n = data.size();
        string result;
        int i = 0;
        while(i + 3 <= n)
        {
            // data[i, i+1, i+2]
            int block = 0;
            for(int j = 0; j < 3; ++j)
            {
                char ch = data[i + j];
                block <<= 8;
                block += ch;
            }
            // [23 18], [17 12], [11 6], [5 0]
            int l = 23;
            while(l > 0)
            {
                int r = l - 5;
                int mask = ((1 << 6) - 1) << r;
                result += base64_code((block & mask) >> r);
                l = r - 1;
            }
            i += 3;
        }
        if(n - i == 1)
        {
            int block = data[i];
            block <<= 4;
            // [11 6], [5 0]
            int l = 11;
            while(l > 0)
            {
                int r = l - 5;
                int mask = ((1 << 6) - 1) << r;
                result += base64_code((block & mask) >> r);
                l = r - 1;
            }
            result += "==";
        }
        else if(n - i == 2)
        {
            int block = data[i++];
            block <<= 8;
            block += data[i];
            block <<= 2;
            // [17 12], [11 6], [5 0]
            int l = 17;
            while(l > 0)
            {
                int r = l - 5;
                int mask = ((1 << 6) - 1) << r;
                result += base64_code((block & mask) >> r);
                l = r - 1;
            }
            result += '=';
        }
        return result;
    }

    string decode(string str) {
        string data;
        int n = str.size();
        int i = 0;
        while(i + 4 < n)
        {
            int block = 0;
            for(int j = 0; j < 4; ++j)
            {
                char base64_ch = str[i + j];
                block <<= 6;
                block += reverse_base64_code(base64_ch);
            }
            for(int j = 16; j >= 0; j -= 8)
            {
                int mask = ((1 << 8) - 1) << j;
                data += char((block & mask) >> j);
            }
            i += 4;
        }
        if(str[n - 2] == '=')
        {
            int block = 0;
            for(int j = 0; j < 2; ++j)
            {
                char base64_ch = str[i + j];
                block <<= 6;
                block += reverse_base64_code(base64_ch);
            }
            block >>= 4;
            int mask = (1 << 8) - 1;
            data += char(block & mask);
        }
        else if(str[n - 1] == '=')
        {
            int block = 0;
            for(int j = 0; j < 3; ++j)
            {
                char base64_ch = str[i + j];
                block <<= 6;
                block += reverse_base64_code(base64_ch);
            }
            block >>= 2;
            for(int j = 8; j >= 0; j -= 8)
            {
                int mask = ((1 << 8) - 1) << j;
                data += char((block & mask) >> j);
            }
        }
        else
        {
            int block = 0;
            for(int j = 0; j < 4; ++j)
            {
                char base64_ch = str[i + j];
                block <<= 6;
                block += reverse_base64_code(base64_ch);
            }
            for(int j = 16; j >= 0; j -= 8)
            {
                int mask = ((1 << 8) - 1) << j;
                data += char((block & mask) >> j);
            }
        }
        return data;
    }
};

---

题目：535. TinyURL 的加密与解密

TinyURL 是一种 URL 简化服务， 比如：当你输入一个 URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk 。请你设计一个类来加密与解密 TinyURL 。

加密和解密算法如何设计和运作是没有限制的，你只需要保证一个 URL 可以被加密成一个 TinyURL ，并且这个 TinyURL 可以用解密方法恢复成原本的 URL 。

实现 Solution 类：

• Solution() 初始化 TinyURL 系统对象。
• String encode(String longUrl) 返回 longUrl 对应的 TinyURL 。
• String decode(String shortUrl) 返回 shortUrl 原本的 URL 。题目数据保证给定的 shortUrl 是由同一个系统对象加密的。

示例：
输入：url = "https://leetcode.com/problems/design-tinyurl"
输出："https://leetcode.com/problems/design-tinyurl"
解释：
Solution obj = new Solution();
string tiny = obj.encode(url); // 返回加密后得到的 TinyURL 。
string ans = obj.decode(tiny); // 返回解密后得到的原本的 URL 。

提示：

1 <= url.length <= 1e4
题目数据保证 url 是一个有效的 URL

算法1：base64

直接把前面实现的 Base64 套上本题的壳子即可。

代码 (C++)

class Solution {
public:
    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        return base64.encode(longUrl);
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        return base64.decode(shortUrl);
    }

private:
    Base64 base64;
};

算法2：哈希

从 0-9a-zA-Z 随机取 6 次字符，若得到的长为 6 的键在哈希表中存在，则重新取。

可加密字符串数量几乎为 62 ^ 6。

代码 (C++)

class Solution {
public:
    Solution()
    {
        dre = std::default_random_engine();
        di = std::uniform_int_distribution<int>(0, 61);
    }

    string get_random_key()
    {
        string result;
        for(int i = 0; i < 6; ++i)
        {
            result += ALPHABET[di(dre)];
        }
        return result;
    }

    string encode(string longUrl) {
        string key = get_random_key();
        while(mapping.count(key) != 0)
            key = get_random_key();
        mapping[key] = longUrl;
        return "http://tinyurl.com/" + key;
    }

    string decode(string shortUrl) {
        int it = shortUrl.find_last_of('/');
        string key = shortUrl.substr(it + 1);
        return mapping[key];
    }

private:
    const string ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const int IDX_LAST = 62;
    std::default_random_engine dre;
    std::uniform_int_distribution<int> di;
    unordered_map<string, string> mapping;
};

---