base58 编码

base58 是 Bitcoin 中使用的一种独特的编码方式，主要用于产生 Bitcoin 的钱包地址。

base58 编码与 base64 编码一样，主要作用也是将非可视字符可视化。

base58 采用数字、大写字母、小写字母，去除歧义字符 0（零）、O（大写字母 O）、I（大写字母 i）、l（小写字母 L）和几个影响双击选择的字符：/ 和 +，总计 58 个字符作为编码的字母表，包括 9 个数字，24 个大写字母，25 个小写字母。

因为 58 不是 2 的整次幂，所以没有使用类似 base64 编码中使用直接截取 3 个字符转 4 个字符的方法进行转换，而是采用我们数学上经常使用的进制转换方法——辗转相除法。本质上，base64 编码是64进制，base58 是58进制。

以下是 base58 的编码表：

也就是字符 1 代表 0，字符 2 代表 1，字符 3 代表 2...字符 z 代表 57。然后回一下辗转相除法。

如要将 1234 转换为 58 进制：

第一步：1234 除于 58，商 21，余数为 16，查表得 H；

第二步：21 除于 58，商 0，余数为 21，查表得 N；

所以得到 base58 编码为：NH。

如果待转换的数前面有 0 怎么办？直接附加编码 1 来代表，有多少个就附加多少个（编码表中1代表0）。

现在我们看下 golang 中的实现：

// Copyright (c) 2015 The btcsuite developers
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.

// AUTOGENERATED by genalphabet.go; do not edit.

package base58

import (
	"math/big"
)
const (
	// alphabet is the modified base58 alphabet used by Bitcoin.
	alphabet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"

	alphabetIdx0 = '1'
)

var  b58 = [256]byte{
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 0, 1, 2, 3, 4, 5, 6,
	7, 8, 255, 255, 255, 255, 255, 255,
	255, 9, 10, 11, 12, 13, 14, 15,
	16, 255, 17, 18, 19, 20, 21, 255,
	22, 23, 24, 25, 26, 27, 28, 29,
	30, 31, 32, 255, 255, 255, 255, 255,
	255, 33, 34, 35, 36, 37, 38, 39,
	40, 41, 42, 43, 255, 44, 45, 46,
	47, 48, 49, 50, 51, 52, 53, 54,
	55, 56, 57, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
}
//go:generate go run genalphabet.go

var bigRadix = big.NewInt(58)
var bigZero = big.NewInt(0)

// Decode decodes a modified base58 string to a byte slice.
func Decode(b string) []byte {
	answer := big.NewInt(0)
	j := big.NewInt(1)

	scratch := new(big.Int)
	for i := len(b) - 1; i >= 0; i-- {
		//字符，ascii码表的简版-->得到字符代表的值(0，1,2，..57)
		tmp := b58[b[i]]
		//出现不该出现的字符
		if tmp == 255 {
			return []byte("")
		}
		scratch.SetInt64(int64(tmp))

		//scratch = j*scratch
		scratch.Mul(j, scratch)

		answer.Add(answer, scratch)
		//每次进位都要乘上58
		j.Mul(j, bigRadix)
	}

	//得到大端的字节序
	tmpval := answer.Bytes()

	var numZeros int
	for numZeros = 0; numZeros < len(b); numZeros++ {
		//得到高位0的位数
		if b[numZeros] != alphabetIdx0 {
			break
		}
	}
	//得到原来数字的长度
	flen := numZeros + len(tmpval)
	//构造一个新地存放结果的空间
	val := make([]byte, flen, flen)
	copy(val[numZeros:], tmpval)

	return val
}

// Encode encodes a byte slice to a modified base58 string.
func Encode(b []byte) string {
	x := new(big.Int)
	//将b解释为大端存储
	x.SetBytes(b)

	//Base58编码可以表示的比特位数为Log258 {\displaystyle \approx } \approx5.858bit。经过Base58编码的数据为原始的数据长度的1.37倍
	answer := make([]byte, 0, len(b)*136/100)

	for x.Cmp(bigZero) > 0 {
		mod := new(big.Int)
		//x除于58的余数mod，并将商赋值给x
		x.DivMod(x, bigRadix, mod)
		answer = append(answer, alphabet[mod.Int64()])
	}

	// leading zero bytes
	//因为如果高位为0，0除任何数为0，可以直接设置为‘1’
	for _, i := range b {
		if i != 0 {
			break
		}
		answer = append(answer, alphabetIdx0)
	}

	// reverse
	//因为之前先附加低位的，后附加高位的，所以需要翻转
	alen := len(answer)
	for i := 0; i < alen/2; i++ {
		answer[i], answer[alen-1-i] = answer[alen-1-i], answer[i]
	}

	return string(answer)
}