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）。现在我们看下go语言中的实现：

// 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)
}