Base64

Base64是一种用64个字符表示任意二进制数据的方法。

编码前，可以是各种各样的字符，中文、法语、日语等，先把这些字符转成字节，然后对这些字节进行编码，编码后就都是限定了的64个字符了。

好处是编码后文本数据可以显示出来了，可以用在邮件、网页、URL上。
编码后，3字节的二进制数变成了4字节的文本数据，长度增加了33%，所以适合传送少量二进制数据。

编码

首先准备一个含有64个字符的数组，一般是 “A～Za～z0～9+/”；
然后原先的二进制数据每3个字节一组，就是3*8=24个比特，然后分成四组，每组6个比特，每6个比特就对应了一个0～63之间的数字；
把这4个范围在0～63的数字当作索引，在上面的字符数组里查找相应的字符；
这样就是编码后的字符串了。

特殊处理：
如果要编码的二进制数据不是3的倍数，就用\x00字节在末尾补足，然后再在编码的末尾加上1到2个等号（=），表示补了多少字节，这样解码的时候就可以自动去掉了。

特别注意，Base64编码后的文本的长度总是4的倍数，但是如果再加上1到2个=不就不是4的倍数了吗？
所以并不是先编码，再加上1到2个=，而是编码之后，把最后的1到2个字符（这个字符肯定是A）替换成=

解码

与编码相反，首先去除末尾的等号（=），然后比对初始的64字符的数组，把编码后的文本转成各字符在数组里的索引值，再然后转成6比特的二进制数，最后删除多余的\x00。

改进

标准Base64里是包含 + 和 / 的，在URL里不能直接作为参数，所以出现一种 “url safe” 的Base64编码，其实就是把 + 和 / 替换成 - 和 _ 。
同样的，=也会被误解，所以编码后干脆去掉=，解码时，自动添加一定数量的等号，使得其长度为4的倍数即可正常解码了。

思考

编码时，=添加的逻辑是：原始二进制数据的长度不是3的倍数时，要补\x00，补了多少个\x00，就在编码的末尾添加几个=；
而解码时，自动添加=的逻辑是：把编码后的文本的长度补齐到4的倍数。
这两个的逻辑明明是不同的，为什么可以工作呢？

解答

因为这里的=的意义只在于表示编码时添加了多少个\x00，哪怕缺失了=，也可以知道缺失了多少个，那么在解码后就要去掉多少个\x00。
而且编码时添加的=其实是替换，并不会破坏编码后长度为4的倍数的这个特性，所以解码时，把=换成A，然后正常解码，再删除掉尾部的X个\x00即可（X=1或着2）。

Base58

除了Base64，还有Base16、Base32、Base58、Base85等编码方式，这里介绍一下Base58是因为：

它的编码思路和Base64看起来不太一样（虽然实质是一样的）
删除了 + / 0 O I l，让编码后的结果更加清晰，且不容易看错
比特币、Monero、Ripple、Flickr都在用这个Base58的编码方式

Base58的本质就是把256进制的值转成58进制的值。
所以它在编码时不需要考虑补\x00的问题，直接转换即可。
把字节流转成一个256进制的大数，然后不断除以58，保留余数，最后余数当作索引，再倒序，即为转换后的结果。

特殊处理：
不同于一个普通的数字转成某个进制，普通数字最高位是不会为0的，而我们要编码的对象是字节流，那么如果字节流的最前面是0（\x00），那么就会丢失这个信息。所以编码时要特殊记录一下，字节流的开端有多少个\x00，就直接在转换后的编码前面加上多少个b58Alphabet[0]，同理，解码的时候先记录一下前面的b58Alphabet[0]的个数，然后解码之后再在解码的前面加上相同数量的0x00。

示例代码

base58.go

var b58Alphabet = []byte("123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz")

// Base58Encode encodes a byte array to Base58
func Base58Encode(input []byte) []byte {
    var result []byte

    x := big.NewInt(0).SetBytes(input)

    base := big.NewInt(int64(len(b58Alphabet)))
    zero := big.NewInt(0)
    mod := &big.Int{}

    for x.Cmp(zero) != 0 {
        x.DivMod(x, base, mod)
        result = append(result, b58Alphabet[mod.Int64()])
    }

    ReverseBytes(result)
    for _, b := range input {
        if b == 0x00 {
            result = append([]byte{b58Alphabet[0]}, result...)
        } else {
            break
        }
    }

    return result
}

// Base58Decode decodes Base58-encoded data
func Base58Decode(input []byte) []byte {
    result := big.NewInt(0)
    zeroBytes := 0

    for _, b := range input {
        if b == b58Alphabet[0] {
            zeroBytes++
        } else {
            break
        }
    }

    payload := input[zeroBytes:]
    for _, b := range payload {
        charIndex := bytes.IndexByte(b58Alphabet, b)
        result.Mul(result, big.NewInt(58))
        result.Add(result, big.NewInt(int64(charIndex)))
    }

    decoded := result.Bytes()
    decoded = append(bytes.Repeat([]byte{byte(0x00)}, zeroBytes), decoded...)

    return decoded
}

base58_test.go

func TestBase58Encode(t *testing.T) {
    data := []byte{0x00, 0x00, 0x00}
    encoded := Base58Encode(data)
    assert.Equal(t, []byte{'1', '1', '1'}, encoded)

    data = []byte{'a'}
    encoded = Base58Encode(data)
    assert.Equal(t, []byte{'2', 'g'}, encoded)

    data = []byte{'1', 0x00}
    encoded = Base58Encode(data)
    assert.Equal(t, []byte{'4', 'j', 'H'}, encoded)
}

func TestBase58Decode(t *testing.T) {
    data := []byte{0x00, 0x00, 0x00}
    assert.Equal(t, data, Base58Decode(Base58Encode(data)))

    data = []byte{'a'}
    assert.Equal(t, data, Base58Decode(Base58Encode(data)))

    data = []byte{'1', 0x00}
    assert.Equal(t, data, Base58Decode(Base58Encode(data)))
}