• 彻底弄懂base64的编码与解码原理

    背景

    base64的编码原理网上讲解较多，但解码原理讲解较少，并且没有对其中的内部实现原理进行剖析。想要彻底了解base64的编码与解码原理，请耐心看完此文，你一定会有所收获。

    涉及算法与逻辑运算概念

    在探究base64编码原理和解码原理的过程中，我们首先需要了解下面会用到的算法和逻辑运算的概念，这样才能真正的吃透base64的编码原理和解码原理，体会到其中算法的精妙，甚至是在思考的过程中得到意想不到的收获。不清楚base64编码表和ascII编码表的同学可直接前往文末查看。

    短除法

    短除法运算方法是先用一个除数除以能被它除尽的一个质数，以此类推，除到商是质数为止。
    通过短除法，十进制数可以不断除以2得到多个余数。最后，将余数从下到上进行排列组合，得到二进制数，我们以字符n对应的ascII编码110为例。

    1.     110 / 2  = 55...0
    2.     55  / 2  = 27...1
    3.     27  / 2  = 13...1
    4.     13  / 2  = 6...1
    5.     6   / 2  = 3...0
    6.     3   / 2  = 1...1
    7.     1   / 2  = 0...1

    将余数从下到上进行排列组合，得到字符n对应的ascII编码110转二进制为1101110，因为一字节对应8位(bit), 所以需要向前补0补足8位，得到01101110。其余字符同理可得。

    按权展开求和

    按权展开求和, 8位二进制数从右到左，次数是0到7依次递增, 基数*底数次数，从左到右依次累加，相加结果为对应十进制数。我们以二进制数01101110转10进制为例：

    (01101110)2 = 0 * 20 + 1 * 21 + 1 * 22 + 1 * 23 + 0 * 24 + 1 * 25 + 1 * 26 + 0 * 27

    位概念

    二进制数系统中，每个0或1就是一个位(bit，比特)，也叫存储单元，位是数据存储的最小单位。其中8bit就称为一个字节（Byte）。

    移位运算符

    移位运算符在程序设计中，是位操作运算符的一种。移位运算符可以在二进制的基础上对数字进行平移。按照平移的方向和填充数字的规则分为三种：<<(左移)、>>(带符号右移)和>>>(无符号右移)。我们在base64的编码和解码过程中操作的又是正数，所以仅使用<<(左移)、>>(带符号右移)两种运算符。

    1. 左移运算：是将一个二进制位的操作数按指定移动的位数向左移动，移出位被丢弃，右边移出的空位一律补0。

    2. 右移运算：是将一个二进制位的操作数按指定移动的位数向右移动，移出位被丢弃，左边移出的空位一律补0，或者补符号位，这由不同的机器而定。在使用补码作为机器数的机器中，正数的符号位为0，负数的符号位为1。

    我们用大白话来描述左移位，一共有8个座位，坐了8个人，在8个座位不动的情况下，现在我让这8个人往左挪2个座位，于是最左边的两个人站了起来，没有座位坐，而最右边空出来了两个座位。移位操作就相当于站起来的人出局，留出来的空位补0.

    1.     // 左移
    2.     01101000 << 2 -> 101000(左侧移出位被丢弃) -> 10100000(右侧空位一律补0)
    3.     // 右移
    4.     01101000 >> 2 -> 011010(右侧移出位被丢弃) -> 00011010(左侧空位一律补0)

    与运算、或运算

    与运算、或运算都是计算机中一种基本的逻辑运算方式。

    1. 与运算：符号表示为&。运算规则：两位同时为“1”，结果才为“1”，否则为0

    2. 或运算：符号表示为｜。运算规则：两位只要有一位为“1”，结果就为“1”，否则为0

    什么是base64编码

    Base64编码是将字符串以每3个8比特(bit)的字节子序列拆分成4个6比特(bit)的字节(6比特有效字节，最左边两个永远为0，其实也是8比特的字节)子序列，再将得到的子序列查找Base64的编码索引表，得到对应的字符拼接成新的字符串的一种编码方式。

    每3个8比特(bit)的字节子序列拆分成4个6比特(bit)的字节的拆分过程如下图所示：

    图片

    base64

    为什么base64编码后的大小是原来的4/3倍

    因为6和8的最大公倍数是24，所以3个8比特的字节刚好可以拆分成4个6比特的字节，38 = 64。计算机中，因为一个字节需要8个存储单元存储，所以我们要把6个比特往前面补两位0，补足8个比特。如下图所示：

    图片

    很明显，补足后所需的存储单元为32个，是原来所需的24个的4/3倍。现在大家明白为什么base64编码后的大小是原来的4/3倍了吧。

    为什么命名为base64呢？

    因为6位(bit)的二进制数有2的6次方个,也就是二进制数(00000000-00111111)之间的代表0-63的64个二进制数。

    不是说一个字节是用8位二进制表示的吗，为什么不是2的8次方？

    因为我们得到的8位二进制数的前两位永远是0，真正的有效位只有6位，所以我们所能够得到的二进制数只有2的6次方个。

    Base64字符是哪64个？

    Base64的编码索引表，字符选用了"A-Z、a-z、0-9、+、/" 64个可打印字符来代表(00000000-00111111)这64个二进制数。即

        let base64EncodeChars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'

    编码原理

    我们不妨自己先思考一下，要把3个字节拆分成4个字节可以怎么做？你的实现思路和我的实现思路有哪个不同，我们之间又会碰出怎样的火花？

    流程图

    图片

    流程图

    思路

    分析映射关系：abc -> xyzi。我们从高位到低位添加索引来分析这个过程

    • x: (前面补两个0)a的前六位 => 00a7a6a5a4a3a2

    • y: (前面补两个0)a的后两位 + b的前四位 => 00a1a0b7b6b5b4

    • z: (前面补两个0)b的后四位 + c的前两位 => 00b3b2b1b0c7c6

    • i: (前面补两个0)c的后六位 => 00c5c4c3c2c1c0通过上述的映射关系，我们很容易得到下面的实现思路：

    1. 将字符对应的ascII编码转为8位二进制数

    2. 将每三个8位二进制数进行以下操作

      • 将第一个数右移位2位，得到第一个6位有效位二进制数

      • 将第一个数 & 0x3之后左移位4位，得到第二个6位有效位二进制数的第一个和第二个有效位，将第二个数 & 0xf0之后右移位4位，得到第二个6位有效位二进制数的后四位有效位，两者取且得到第二个6位有效位二进制

      • 将第二个数 & 0xf之后左移位2位，得到第三个6位有效位二进制数的前四位有效位，将第三个数 & 0xC0之后右移位6位，得到第三个6位有效位二进制数的后两位有效位，两者取且得到第三个6位有效位二进制

      • 将第三个数 & 0x3f，得到第四个6位有效位二进制数

    3. 将获得的6位有效位二进制数转十进制，查找对应base64字符

    我们以hao字符串为例，观察base64编码的过程，我们将上面转换通过代码逻辑分析实现吧。

    代码实现

    1. // 输入字符串
    2. let str = 'hao'
    3. // base64字符串
    4. let base64EncodeChars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
    5. // 定义输入、输出字节的二进制数
    6. let char1, char2, char3, out1, out2, out3, out4, out
    7. // 将字符对应的ascII编码转为8位二进制数
    8. char1 = str.charCodeAt(0) & 0xff // 104  01101000
    9. char2 = str.charCodeAt(1) & 0xff // 97  01100001
    10. char3 = str.charCodeAt(2) & 0xff // 111  01101111
    11. // 输出6位有效字节二进制数
    12. 6out1 = char1 >> 2 // 26  011010
    13. out2 = (char1 & 0x3) << 4 | (char2 & 0xf0) >> 4 // 6  000110
    14. out3 = (char2 & 0xf) << 2 | (char3 & 0xc0) >> 6 // 5  000101
    15. out4 = char3 & 0x3f // 47 101111
    16.  
    17. out = base64EncodeChars[out1] + base64EncodeChars[out2] + base64EncodeChars[out3] + base64EncodeChars[out4] // aGFv

    算法剖析

    1. out1: char1 >> 2 
      01101000 -> 00011010
    2. out2 = (char1 & 0x3) << 4 | (char2 & 0xf0) >> 4 
      1. // 且运算
      2. 01101000        01100001
      3. 00000011        11110000
      4. --------        --------
      5. 00000000        01100000
      6.  
      7. // 移位运算后得
      8. 00000000        00000110
      9.  
      10. // 或运算
      11. 00000000
      12. 00000110
      13. --------
      14. 00000110

    第三个字符第四个字符同理

    整理上述代码，扩展至多字符字符串

    1. // 输入字符串
    2. let str = 'haohaohao'
    3. // base64字符串
    4. let base64EncodeChars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
    5.  
    6. // 获取字符串长度
    7. let len = str.length
    8. // 当前字符索引
    9. let index = 0
    10. // 输出字符串
    11. let out = ''
    12. while(index < len) {
    13.     // 定义输入、输出字节的二进制数
    14.     let char1, char2, char3, out1, out2, out3, out4
    15.     // 将字符对应的ascII编码转为8位二进制数
    16.     char1 = str.charCodeAt(index++) & 0xff // 104  01101000
    17.     char2 = str.charCodeAt(index++) & 0xff // 97  01100001
    18.     char3 = str.charCodeAt(index++) & 0xff // 111  01101111
    19.     // 输出6位有效字节二进制数
    20.     out1 = char1 >> 2 // 26  011010
    21.     out2 = (char1 & 0x3) << 4 | (char2 & 0xf0) >> 4 // 6  000110
    22.     out3 = (char2 & 0xf) << 2 | (char3 & 0xc0) >> 6 // 5  000101
    23.     out4 = char3 & 0x3f // 47 101111
    24.  
    25.     out = out + base64EncodeChars[out1] + base64EncodeChars[out2] + base64EncodeChars[out3] + base64EncodeChars[out4] // aGFv
    26. }

    原字符串长度不是3的整倍数的情况，需要特殊处理

    1.     ...
    2.     char1 = str.charCodeAt(index++) & 0xff // 104  01101000
    3.     if (index == len) {
    4.         out2 = (char1 & 0x3) << 4
    5.         out = out + base64EncodeChars[out1] + base64EncodeChars[out2] + '=='
    6.         return out
    7.     }
    8.     char2 = str.charCodeAt(index++) & 0xff // 97  01100001
    9.     if (index == len) {
    10.         out1 = char1 >> 2 // 26  011010
    11.         out2 = (char1 & 0x3) << 4 | (char2 & 0xf0) >> 4 // 6  000110
    12.         out3 = (char2 & 0xf) << 2
    13.         out = out + base64EncodeChars[out1] + base64EncodeChars[out2] + base64EncodeChars[out3] + '='
    14.         return out
    15.     }
    16.     ...
    17.

    全部代码

    1. function base64Encode(str) {
    2.     // base64字符串
    3.     let base64EncodeChars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
    4.  
    5.     // 获取字符串长度
    6.     let len = str.length
    7.     // 当前字符索引
    8.     let index = 0
    9.     // 输出字符串
    10.     let out = ''
    11.     while(index < len) {
    12.         // 定义输入、输出字节的二进制数
    13.         let char1, char2, char3, out1, out2, out3, out4
    14.         // 将字符对应的ascII编码转为8位二进制数
    15.         char1 = str.charCodeAt(index++) & 0xff
    16.         out1 = char1 >> 2
    17.         if (index == len) {
    18.             out2 = (char1 & 0x3) << 4
    19.             out = out + base64EncodeChars[out1] + base64EncodeChars[out2] + '=='
    20.             return out
    21.         }
    22.         char2 = str.charCodeAt(index++) & 0xff
    23.         out2 = (char1 & 0x3) << 4 | (char2 & 0xf0) >> 4 
    24.         if (index == len) {
    25.             out3 = (char2 & 0xf) << 2
    26.             out = out + base64EncodeChars[out1] + base64EncodeChars[out2] + base64EncodeChars[out3] + '='
    27.             return out
    28.         }
    29.         char3 = str.charCodeAt(index++) & 0xff
    30.         // 输出6位有效字节二进制数
    31.         out3 = (char2 & 0xf) << 2 | (char3 & 0xc0) >> 6
    32.         out4 = char3 & 0x3f
    33.  
    34.         out = out + base64EncodeChars[out1] + base64EncodeChars[out2] + base64EncodeChars[out3] + base64EncodeChars[out4]
    35.     }
    36.     return out
    37. }
    38. base64Encode('haohao') // aGFvaGFv
    39. base64Encode('haoha') // aGFvaGE=
    40. base64Encode('haoh') // aGFvaA==

    解码原理

    逆向推导，由每4个6位有效位的二进制数合并成3个8位二进制数，根据ascII编码映射到对应字符后拼接字符串

    思路

    分析映射关系 xyzi -> abc

    • a: x后六位 + y第三、四位 => x5x4x3x2x1x0y5y4

    • b: y后四位 + z第三、四、五、六位 => y3y2y1y0z5z4z3z2

    • c: z后两位 + i后六位 => z1z0i5i4i3i2i1i0

    1. 将字符对应的base64字符集的索引转为6位有效位二进制数

    2. 将每四个6位有效位二进制数进行以下操作

      1. 第一个二进制数左移位2位，得到新二进制数的前6位，第二个二进制数 & 0x30之后右移位4位，或运算后得到第一个新二进制数

      2. 第二个二进制数 & 0xf之后左移位4位，第三个二进制数 & 0x3c之后右移位2位，或运算后得到第二个新二进制数

      3. 第二个二进制数 & 0x3之后左移位6位，与第四个二进制数或运算后得到第二个新二进制数

    3. 根据ascII编码映射到对应字符后拼接字符串

    代码实现

    1. // base64字符串
    2. let str = 'aGFv'
    3. // base64字符集
    4. let base64CharsArr = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'.split('')
    5. // 获取索引值
    6. let char1 = base64CharsArr.findIndex(char => char==str[0]) & 0xff // 26  011010
    7. let char2 = base64CharsArr.findIndex(char => char==str[1]) & 0xff // 6  000110
    8. let char3 = base64CharsArr.findIndex(char => char==str[2]) & 0xff // 5  000101
    9. let char4 = base64CharsArr.findIndex(char => char==str[3]) & 0xff // 47  101111
    10. let out1, out2, out3, out
    11. // 位运算
    12. out1 = char1 << 2 | (char2 & 0x30) >> 4
    13. out2 = (char2 & 0xf) << 4 | (char3 & 0x3c) >> 2
    14. out3 = (char3 & 0x3) << 6 | char4
    15. console.log(out1, out2, out3)
    16. out = String.fromCharCode(out1) + String.fromCharCode(out2) + String.fromCharCode(out3)

    遇到有用'='补过位的情况时

    1. function base64decode(str) {
    2.     // base64字符集
    3.     let base64CharsArr = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'.split('')
    4.     let char1 = base64CharsArr.findIndex(char => char==str[0])
    5.     let char2 = base64CharsArr.findIndex(char => char==str[1])
    6.     let out1, out2, out3, out
    7.     if (char1 == -1 || char2 == -1) return out
    8.     char1 = char1 & 0xff
    9.     char2 = char2 & 0xff
    10.     let char3 = base64CharsArr.findIndex(char => char==str[2])
    11.     // 第三位不在base64对照表中时，只拼接第一个字符串
    12.     if (char3 == -1) {
    13.         out1 = char1 << 2 | (char2 & 0x30) >> 4
    14.         out = String.fromCharCode(out1)
    15.         return out
    16.     }
    17.     let char4 = base64CharsArr.findIndex(char => char==str[3])
    18.     // 第三位不在base64对照表中时，只拼接第一个和第二个字符串
    19.     if (char4 == -1) {
    20.         out1 = char1 << 2 | (char2 & 0x30) >> 4
    21.         out2 = (char2 & 0xf) << 4 | (char3 & 0x3c) >> 2
    22.         out = String.fromCharCode(out1) + String.fromCharCode(out2)
    23.         return out
    24.     }
    25.     // 位运算
    26.     out1 = char1 << 2 | (char2 & 0x30) >> 4
    27.     out2 = (char2 & 0xf) << 4 | (char3 & 0x3c) >> 2
    28.     out3 = (char3 & 0x3) << 6 | char4
    29.     console.log(out1, out2, out3)
    30.     out = String.fromCharCode(out1) + String.fromCharCode(out2) + String.fromCharCode(out3)
    31.     return out
    32. }

    解码整个字符串，整理代码后

    1. function base64decode(str) {
    2.     // base64字符集
    3.     let base64CharsArr = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'.split('')
    4.     let i = 0
    5.     let len = str.length
    6.     let out = ''
    7.     while(i < len) {
    8.         let char1 = base64CharsArr.findIndex(char => char==str[i])
    9.         i++
    10.         let char2 = base64CharsArr.findIndex(char => char==str[i])
    11.         i++
    12.         let out1, out2, out3
    13.         if (char1 == -1 || char2 == -1) return out
    14.         char1 = char1 & 0xff
    15.         char2 = char2 & 0xff
    16.         let char3 = base64CharsArr.findIndex(char => char==str[i])
    17.         i++
    18.         // 第三位不在base64对照表中时，只拼接第一个字符串
    19.         out1 = char1 << 2 | (char2 & 0x30) >> 4
    20.         if (char3 == -1) {
    21.             out = out + String.fromCharCode(out1)
    22.             return out
    23.         }
    24.         let char4 = base64CharsArr.findIndex(char => char==str[i])
    25.         i++
    26.         // 第三位不在base64对照表中时，只拼接第一个和第二个字符串
    27.         out2 = (char2 & 0xf) << 4 | (char3 & 0x3c) >> 2
    28.         if (char4 == -1) {
    29.             out = out + String.fromCharCode(out1) + String.fromCharCode(out2)
    30.             return out
    31.         }
    32.         // 位运算
    33.         out3 = (char3 & 0x3) << 6 | char4
    34.         console.log(out1, out2, out3)
    35.         out = out + String.fromCharCode(out1) + String.fromCharCode(out2) + String.fromCharCode(out3)
    36.     }
    37.     return out
    38. }
    39. base64decode('aGFvaGFv') // haohao
    40. base64decode('aGFvaGE=') // haoha
    41. base64decode('aGFvaA==') // haoh

    上述解码核心是字符与base64字符集索引的映射，网上看到过使用AccII编码索引映射base64字符索引的方法

    1. let base64DecodeChars = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 62, -1, -1, -1, 63, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1, -1, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, -1, -1, -1, -1, -1]
    2. // 
    3. let char1 = 'hao'.charCodeAt(0) // h -> 104
    4. base64DecodeChars[char1] // 33 -> base64编码表中的h

    由此可见，base64DecodeChars对照accII编码表的索引存放的是base64编码表的对应字符的索引。

    总结

    说起Base64编码可能有些奇怪，因为大多数的编码都是由字符转化成二进制的过程，而从二进制转成字符的过程称为解码。而Base64的概念就恰好反了，由二进制转到字符称为编码，由字符到二进制称为解码。Base64 是一种数据编码方式，可做简单加密使用，我们可以改变base64编码映射顺序来形成自己独特的加密算法进行加密解密。

    编码表

    图片

    图片

  • 相关阅读:
    DiskPressure(磁盘压力)
    jsbridge实战2：Swift和h5的jsbridge通信
    Mysql003：基础查询
    简单错误记录-OJ
    基于java+SpringBoot+HTML+Mysql政务审批网站的设计与实现
    洞见云原生微服务及微服务架构浅析
    LabVIEW在不同平台之间移植VI
    【Redis学习笔记】第十四章 Redis企业级解决方案与性能监控
    Vue学习第25天——Vuex中的4个map方法的基本用法及案例练习
    List＜HashMap＜String,String＞＞实现自定义字符串排序（key排序、Value排序）
  • 原文地址：https://blog.csdn.net/Jernnifer_mao/article/details/133981806