徹底弄懂Base64的編碼與解碼原理
本文轉(zhuǎn)載自微信公眾號「大轉(zhuǎn)轉(zhuǎn)FE」，作者大轉(zhuǎn)轉(zhuǎn)FE。轉(zhuǎn)載本文請聯(lián)系大轉(zhuǎn)轉(zhuǎn)FE公眾號。
背景
base64的編碼原理網(wǎng)上講解較多，但解碼原理講解較少，并且沒有對其中的內(nèi)部實現(xiàn)原理進行剖析。想要徹底了解base64的編碼與解碼原理，請耐心看完此文，你一定會有所收獲。
涉及算法與邏輯運算概念
在探究base64編碼原理和解碼原理的過程中，我們首先需要了解下面會用到的算法和邏輯運算的概念，這樣才能真正的吃透base64的編碼原理和解碼原理，體會到其中算法的精妙，甚至是在思考的過程中得到意想不到的收獲。不清楚base64編碼表和ascII編碼表的同學(xué)可直接前往文末查看。
短除法
短除法運算方法是先用一個除數(shù)除以能被它除盡的一個質(zhì)數(shù)，以此類推，除到商是質(zhì)數(shù)為止。
通過短除法，十進制數(shù)可以不斷除以2得到多個余數(shù)。最后，將余數(shù)從下到上進行排列組合，得到二進制數(shù)，我們以字符n對應(yīng)的ascII編碼110為例。
- 110 / 2 = 55...0
- 55 / 2 = 27...1
- 27 / 2 = 13...1
- 13 / 2 = 6...1
- 6 / 2 = 3...0
- 3 / 2 = 1...1
- 1 / 2 = 0...1
將余數(shù)從下到上進行排列組合，得到字符n對應(yīng)的ascII編碼110轉(zhuǎn)二進制為1101110，因為一字節(jié)對應(yīng)8位(bit), 所以需要向前補0補足8位，得到01101110。其余字符同理可得。
按權(quán)展開求和
按權(quán)展開求和, 8位二進制數(shù)從右到左，次數(shù)是0到7依次遞增, 基數(shù)*底數(shù)次數(shù)，從左到右依次累加，相加結(jié)果為對應(yīng)十進制數(shù)。我們以二進制數(shù)01101110轉(zhuǎn)10進制為例：
(01101110)2 = 0 * 20 + 1 * 21 + 1 * 22 + 1 * 23 + 0 * 24 + 1 * 25 + 1 * 26 + 0 * 27
位概念
二進制數(shù)系統(tǒng)中，每個0或1就是一個位(bit，比特)，也叫存儲單元，位是數(shù)據(jù)存儲的最小單位。其中8bit就稱為一個字節(jié)(Byte)。
移位運算符
移位運算符在程序設(shè)計中，是位操作運算符的一種。移位運算符可以在二進制的基礎(chǔ)上對數(shù)字進行平移。按照平移的方向和填充數(shù)字的規(guī)則分為三種：<<(左移)、>>(帶符號右移)和>>>(無符號右移)。我們在base64的編碼和解碼過程中操作的又是正數(shù)，所以僅使用<<(左移)、>>(帶符號右移)兩種運算符。
- 左移運算：是將一個二進制位的操作數(shù)按指定移動的位數(shù)向左移動，移出位被丟棄，右邊移出的空位一律補0。
- 右移運算：是將一個二進制位的操作數(shù)按指定移動的位數(shù)向右移動，移出位被丟棄，左邊移出的空位一律補0，或者補符號位，這由不同的機器而定。在使用補碼作為機器數(shù)的機器中，正數(shù)的符號位為0，負數(shù)的符號位為1。
我們用大白話來描述左移位，一共有8個座位，坐了8個人，在8個座位不動的情況下，現(xiàn)在我讓這8個人往左挪2個座位，于是最左邊的兩個人站了起來，沒有座位坐，而最右邊空出來了兩個座位。移位操作就相當(dāng)于站起來的人出局，留出來的空位補0.
- // 左移
- 01101000 << 2 -> 101000(左側(cè)移出位被丟棄) -> 10100000(右側(cè)空位一律補0)
- // 右移
- 01101000 >> 2 -> 011010(右側(cè)移出位被丟棄) -> 00011010(左側(cè)空位一律補0)
與運算、或運算
與運算、或運算都是計算機中一種基本的邏輯運算方式。
- 與運算：符號表示為&。運算規(guī)則：兩位同時為“1”，結(jié)果才為“1”，否則為0
- 或運算：符號表示為|。運算規(guī)則：兩位只要有一位為“1”，結(jié)果就為“1”，否則為0
什么是base64編碼
Base64編碼是將字符串以每3個8比特(bit)的字節(jié)子序列拆分成4個6比特(bit)的字節(jié)(6比特有效字節(jié)，最左邊兩個永遠為0，其實也是8比特的字節(jié))子序列，再將得到的子序列查找Base64的編碼索引表，得到對應(yīng)的字符拼接成新的字符串的一種編碼方式。
每3個8比特(bit)的字節(jié)子序列拆分成4個6比特(bit)的字節(jié)的拆分過程如下圖所示：
base64
為什么base64編碼后的大小是原來的4/3倍
因為6和8的最大公倍數(shù)是24，所以3個8比特的字節(jié)剛好可以拆分成4個6比特的字節(jié)，38 = 64。計算機中，因為一個字節(jié)需要8個存儲單元存儲，所以我們要把6個比特往前面補兩位0，補足8個比特。如下圖所示：
很明顯，補足后所需的存儲單元為32個，是原來所需的24個的4/3倍。現(xiàn)在大家明白為什么base64編碼后的大小是原來的4/3倍了吧。
為什么命名為base64呢?
因為6位(bit)的二進制數(shù)有2的6次方個,也就是二進制數(shù)(00000000-00111111)之間的代表0-63的64個二進制數(shù)。
不是說一個字節(jié)是用8位二進制表示的嗎，為什么不是2的8次方?
因為我們得到的8位二進制數(shù)的前兩位永遠是0，真正的有效位只有6位，所以我們所能夠得到的二進制數(shù)只有2的6次方個。
Base64字符是哪64個?
Base64的編碼索引表，字符選用了"A-Z、a-z、0-9、+、/" 64個可打印字符來代表(00000000-00111111)這64個二進制數(shù)。即
let base64EncodeChars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
編碼原理
我們不妨自己先思考一下，要把3個字節(jié)拆分成4個字節(jié)可以怎么做?你的實現(xiàn)思路和我的實現(xiàn)思路有哪個不同，我們之間又會碰出怎樣的火花?
流程圖
流程圖
思路
分析映射關(guān)系：abc -> xyzi。我們從高位到低位添加索引來分析這個過程
- x: (前面補兩個0)a的前六位 => 00a7a6a5a4a3a2
- y: (前面補兩個0)a的后兩位 + b的前四位 => 00a1a0b7b6b5b4
- z: (前面補兩個0)b的后四位 + c的前兩位 => 00b3b2b1b0c7c6
- i: (前面補兩個0)c的后六位 => 00c5c4c3c2c1c0通過上述的映射關(guān)系，我們很容易得到下面的實現(xiàn)思路：
1.將字符對應(yīng)的ascII編碼轉(zhuǎn)為8位二進制數(shù)
2.將每三個8位二進制數(shù)進行以下操作
- 將第一個數(shù)右移位2位，得到第一個6位有效位二進制數(shù)
- 將第一個數(shù) & 0x3之后左移位4位，得到第二個6位有效位二進制數(shù)的第一個和第二個有效位，將第二個數(shù) & 0xf0之后右移位4位，得到第二個6位有效位二進制數(shù)的后四位有效位，兩者取且得到第二個6位有效位二進制
- 將第二個數(shù) & 0xf之后左移位2位，得到第三個6位有效位二進制數(shù)的前四位有效位，將第三個數(shù) & 0xC0之后右移位6位，得到第三個6位有效位二進制數(shù)的后兩位有效位，兩者取且得到第三個6位有效位二進制
- 將第三個數(shù) & 0x3f，得到第四個6位有效位二進制數(shù)
3.將獲得的6位有效位二進制數(shù)轉(zhuǎn)十進制，查找對應(yīng)base64字符
我們以hao字符串為例，觀察base64編碼的過程，我們將上面轉(zhuǎn)換通過代碼邏輯分析實現(xiàn)吧。
代碼實現(xiàn)
- // 輸入字符串
- let str = 'hao'
- // base64字符串
- let base64EncodeChars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
- // 定義輸入、輸出字節(jié)的二進制數(shù)
- let char1, char2, char3, out1, out2, out3, out4, out
- // 將字符對應(yīng)的ascII編碼轉(zhuǎn)為8位二進制數(shù)
- char1 = str.charCodeAt(0) & 0xff // 104 01101000
- char2 = str.charCodeAt(1) & 0xff // 97 01100001
- char3 = str.charCodeAt(2) & 0xff // 111 01101111
- // 輸出6位有效字節(jié)二進制數(shù)
- 6out1 = char1 >> 2 // 26 011010
- out2 = (char1 & 0x3) << 4 | (char2 & 0xf0) >> 4 // 6 000110
- out3 = (char2 & 0xf) << 2 | (char3 & 0xc0) >> 6 // 5 000101
- out4 = char3 & 0x3f // 47 101111
- out = base64EncodeChars[out1] + base64EncodeChars[out2] + base64EncodeChars[out3] + base64EncodeChars[out4] // aGFv
算法剖析
1.out1: char1 >> 2
- 01101000 -> 00011010
2.out2 = (char1 & 0x3) << 4 | (char2 & 0xf0) >> 4
- // 且運算
- 01101000 01100001
- 00000011 11110000
- -------- --------
- 00000000 01100000
- // 移位運算后得
- 00000000 00000110
- // 或運算
- 00000000
- 00000110
- --------
- 00000110
第三個字符第四個字符同理
整理上述代碼，擴展至多字符字符串
- // 輸入字符串
- let str = 'haohaohao'
- // base64字符串
- let base64EncodeChars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
- // 獲取字符串長度
- let len = str.length
- // 當(dāng)前字符索引
- let index = 0
- // 輸出字符串
- let out = ''
- while(index < len) {
- // 定義輸入、輸出字節(jié)的二進制數(shù)
- let char1, char2, char3, out1, out2, out3, out4
- // 將字符對應(yīng)的ascII編碼轉(zhuǎn)為8位二進制數(shù)
- char1 = str.charCodeAt(index++) & 0xff // 104 01101000
- char2 = str.charCodeAt(index++) & 0xff // 97 01100001
- char3 = str.charCodeAt(index++) & 0xff // 111 01101111
- // 輸出6位有效字節(jié)二進制數(shù)
- out1 = char1 >> 2 // 26 011010
- out2 = (char1 & 0x3) << 4 | (char2 & 0xf0) >> 4 // 6 000110
- out3 = (char2 & 0xf) << 2 | (char3 & 0xc0) >> 6 // 5 000101
- out4 = char3 & 0x3f // 47 101111
- out = out + base64EncodeChars[out1] + base64EncodeChars[out2] + base64EncodeChars[out3] + base64EncodeChars[out4] // aGFv
- }
原字符串長度不是3的整倍數(shù)的情況，需要特殊處理
- ...
- char1 = str.charCodeAt(index++) & 0xff // 104 01101000
- if (index == len) {
- out2 = (char1 & 0x3) << 4
- out = out + base64EncodeChars[out1] + base64EncodeChars[out2] + '=='
- return out
- }
- char2 = str.charCodeAt(index++) & 0xff // 97 01100001
- if (index == len) {
- out1 = char1 >> 2 // 26 011010
- out2 = (char1 & 0x3) << 4 | (char2 & 0xf0) >> 4 // 6 000110
- out3 = (char2 & 0xf) << 2
- out = out + base64EncodeChars[out1] + base64EncodeChars[out2] + base64EncodeChars[out3] + '='
- return out
- }
- ...
全部代碼
- function base64Encode(str) {
- // base64字符串
- let base64EncodeChars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
- // 獲取字符串長度
- let len = str.length
- // 當(dāng)前字符索引
- let index = 0
- // 輸出字符串
- let out = ''
- while(index < len) {
- // 定義輸入、輸出字節(jié)的二進制數(shù)
- let char1, char2, char3, out1, out2, out3, out4
- // 將字符對應(yīng)的ascII編碼轉(zhuǎn)為8位二進制數(shù)
- char1 = str.charCodeAt(index++) & 0xff
- out1 = char1 >> 2
- if (index == len) {
- out2 = (char1 & 0x3) << 4
- out = out + base64EncodeChars[out1] + base64EncodeChars[out2] + '=='
- return out
- }
- char2 = str.charCodeAt(index++) & 0xff
- out2 = (char1 & 0x3) << 4 | (char2 & 0xf0) >> 4
- if (index == len) {
- out3 = (char2 & 0xf) << 2
- out = out + base64EncodeChars[out1] + base64EncodeChars[out2] + base64EncodeChars[out3] + '='
- return out
- }
- char3 = str.charCodeAt(index++) & 0xff
- // 輸出6位有效字節(jié)二進制數(shù)
- out3 = (char2 & 0xf) << 2 | (char3 & 0xc0) >> 6
- out4 = char3 & 0x3f
- out = out + base64EncodeChars[out1] + base64EncodeChars[out2] + base64EncodeChars[out3] + base64EncodeChars[out4]
- }
- return out
- }
- base64Encode('haohao') // aGFvaGFv
- base64Encode('haoha') // aGFvaGE=
- base64Encode('haoh') // aGFvaA==
解碼原理
逆向推導(dǎo)，由每4個6位有效位的二進制數(shù)合并成3個8位二進制數(shù)，根據(jù)ascII編碼映射到對應(yīng)字符后拼接字符串
思路
- 分析映射關(guān)系 xyzi -> abc
- a: x后六位 + y第三、四位 => x5x4x3x2x1x0y5y4
- b: y后四位 + z第三、四、五、六位 => y3y2y1y0z5z4z3z2
1.c: z后兩位 + i后六位 => z1z0i5i4i3i2i1i0
2.將字符對應(yīng)的base64字符集的索引轉(zhuǎn)為6位有效位二進制數(shù)
將每四個6位有效位二進制數(shù)進行以下操作
第一個二進制數(shù)左移位2位，得到新二進制數(shù)的前6位，第二個二進制數(shù) & 0x30之后右移位4位，或運算后得到第一個新二進制數(shù)
第二個二進制數(shù) & 0xf之后左移位4位，第三個二進制數(shù) & 0x3c之后右移位2位，或運算后得到第二個新二進制數(shù)
第二個二進制數(shù) & 0x3之后左移位6位，與第四個二進制數(shù)或運算后得到第二個新二進制數(shù)
3.根據(jù)ascII編碼映射到對應(yīng)字符后拼接字符串
代碼實現(xiàn)
- // base64字符串
- let str = 'aGFv'
- // base64字符集
- let base64CharsArr = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'.split('')
- // 獲取索引值
- let char1 = base64CharsArr.findIndex(char => char==str[0]) & 0xff // 26 011010
- let char2 = base64CharsArr.findIndex(char => char==str[1]) & 0xff // 6 000110
- let char3 = base64CharsArr.findIndex(char => char==str[2]) & 0xff // 5 000101
- let char4 = base64CharsArr.findIndex(char => char==str[3]) & 0xff // 47 101111
- let out1, out2, out3, out
- // 位運算
- out1 = char1 << 2 | (char2 & 0x30) >> 4
- out2 = (char2 & 0xf) << 4 | (char3 & 0x3c) >> 2
- out3 = (char3 & 0x3) << 6 | char4
- console.log(out1, out2, out3)
- out = String.fromCharCode(out1) + String.fromCharCode(out2) + String.fromCharCode(out3)
遇到有用'='補過位的情況時
- function base64decode(str) {
- // base64字符集
- let base64CharsArr = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'.split('')
- let char1 = base64CharsArr.findIndex(char => char==str[0])
- let char2 = base64CharsArr.findIndex(char => char==str[1])
- let out1, out2, out3, out
- if (char1 == -1 || char2 == -1) return out
- char1 = char1 & 0xff
- char2 = char2 & 0xff
- let char3 = base64CharsArr.findIndex(char => char==str[2])
- // 第三位不在base64對照表中時，只拼接第一個字符串
- if (char3 == -1) {
- out1 = char1 << 2 | (char2 & 0x30) >> 4
- out = String.fromCharCode(out1)
- return out
- }
- let char4 = base64CharsArr.findIndex(char => char==str[3])
- // 第三位不在base64對照表中時，只拼接第一個和第二個字符串
- if (char4 == -1) {
- out1 = char1 << 2 | (char2 & 0x30) >> 4
- out2 = (char2 & 0xf) << 4 | (char3 & 0x3c) >> 2
- out = String.fromCharCode(out1) + String.fromCharCode(out2)
- return out
- }
- // 位運算
- out1 = char1 << 2 | (char2 & 0x30) >> 4
- out2 = (char2 & 0xf) << 4 | (char3 & 0x3c) >> 2
- out3 = (char3 & 0x3) << 6 | char4
- console.log(out1, out2, out3)
- out = String.fromCharCode(out1) + String.fromCharCode(out2) + String.fromCharCode(out3)
- return out
- }
解碼整個字符串，整理代碼后
- function base64decode(str) {
- // base64字符集
- let base64CharsArr = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'.split('')
- let i = 0
- let len = str.length
- let out = ''
- while(i < len) {
- let char1 = base64CharsArr.findIndex(char => char==str[i])
- i++
- let char2 = base64CharsArr.findIndex(char => char==str[i])
- i++
- let out1, out2, out3
- if (char1 == -1 || char2 == -1) return out
- char1 = char1 & 0xff
- char2 = char2 & 0xff
- let char3 = base64CharsArr.findIndex(char => char==str[i])
- i++
- // 第三位不在base64對照表中時，只拼接第一個字符串
- out1 = char1 << 2 | (char2 & 0x30) >> 4
- if (char3 == -1) {
- out = out + String.fromCharCode(out1)
- return out
- }
- let char4 = base64CharsArr.findIndex(char => char==str[i])
- i++
- // 第三位不在base64對照表中時，只拼接第一個和第二個字符串
- out2 = (char2 & 0xf) << 4 | (char3 & 0x3c) >> 2
- if (char4 == -1) {
- out = out + String.fromCharCode(out1) + String.fromCharCode(out2)
- return out
- }
- // 位運算
- out3 = (char3 & 0x3) << 6 | char4
- console.log(out1, out2, out3)
- out = out + String.fromCharCode(out1) + String.fromCharCode(out2) + String.fromCharCode(out3)
- }
- return out
- }
- base64decode('aGFvaGFv') // haohao
- base64decode('aGFvaGE=') // haoha
- base64decode('aGFvaA==') // haoh
上述解碼核心是字符與base64字符集索引的映射，網(wǎng)上看到過使用AccII編碼索引映射base64字符索引的方法
- 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]
- //
- let char1 = 'hao'.charCodeAt(0) // h -> 104
- base64DecodeChars[char1] // 33 -> base64編碼表中的h
由此可見，base64DecodeChars對照accII編碼表的索引存放的是base64編碼表的對應(yīng)字符的索引。
總結(jié)
說起B(yǎng)ase64編碼可能有些奇怪，因為大多數(shù)的編碼都是由字符轉(zhuǎn)化成二進制的過程，而從二進制轉(zhuǎn)成字符的過程稱為解碼。而Base64的概念就恰好反了，由二進制轉(zhuǎn)到字符稱為編碼，由字符到二進制稱為解碼。Base64 是一種數(shù)據(jù)編碼方式，可做簡單加密使用，我們可以改變base64編碼映射順序來形成自己獨特的加密算法進行加密解密。
編碼表
