1// Copyright (c) 2013-2015 The btcsuite developers
2// Use of this source code is governed by an ISC
3// license that can be found in the LICENSE file.
4
5package base58
6
7import (
8	"math/big"
9)
10
11//go:generate go run genalphabet.go
12
13var bigRadix = [...]*big.Int{
14	big.NewInt(0),
15	big.NewInt(58),
16	big.NewInt(58 * 58),
17	big.NewInt(58 * 58 * 58),
18	big.NewInt(58 * 58 * 58 * 58),
19	big.NewInt(58 * 58 * 58 * 58 * 58),
20	big.NewInt(58 * 58 * 58 * 58 * 58 * 58),
21	big.NewInt(58 * 58 * 58 * 58 * 58 * 58 * 58),
22	big.NewInt(58 * 58 * 58 * 58 * 58 * 58 * 58 * 58),
23	big.NewInt(58 * 58 * 58 * 58 * 58 * 58 * 58 * 58 * 58),
24	bigRadix10,
25}
26
27var bigRadix10 = big.NewInt(58 * 58 * 58 * 58 * 58 * 58 * 58 * 58 * 58 * 58) // 58^10
28
29// Decode decodes a modified base58 string to a byte slice.
30func Decode(b string) []byte {
31	answer := big.NewInt(0)
32	scratch := new(big.Int)
33
34	// Calculating with big.Int is slow for each iteration.
35	//    x += b58[b[i]] * j
36	//    j *= 58
37	//
38	// Instead we can try to do as much calculations on int64.
39	// We can represent a 10 digit base58 number using an int64.
40	//
41	// Hence we'll try to convert 10, base58 digits at a time.
42	// The rough idea is to calculate `t`, such that:
43	//
44	//   t := b58[b[i+9]] * 58^9 ... + b58[b[i+1]] * 58^1 + b58[b[i]] * 58^0
45	//   x *= 58^10
46	//   x += t
47	//
48	// Of course, in addition, we'll need to handle boundary condition when `b` is not multiple of 58^10.
49	// In that case we'll use the bigRadix[n] lookup for the appropriate power.
50	for t := b; len(t) > 0; {
51		n := len(t)
52		if n > 10 {
53			n = 10
54		}
55
56		total := uint64(0)
57		for _, v := range t[:n] {
58			tmp := b58[v]
59			if tmp == 255 {
60				return []byte("")
61			}
62			total = total*58 + uint64(tmp)
63		}
64
65		answer.Mul(answer, bigRadix[n])
66		scratch.SetUint64(total)
67		answer.Add(answer, scratch)
68
69		t = t[n:]
70	}
71
72	tmpval := answer.Bytes()
73
74	var numZeros int
75	for numZeros = 0; numZeros < len(b); numZeros++ {
76		if b[numZeros] != alphabetIdx0 {
77			break
78		}
79	}
80	flen := numZeros + len(tmpval)
81	val := make([]byte, flen)
82	copy(val[numZeros:], tmpval)
83
84	return val
85}
86
87// Encode encodes a byte slice to a modified base58 string.
88func Encode(b []byte) string {
89	x := new(big.Int)
90	x.SetBytes(b)
91
92	// maximum length of output is log58(2^(8*len(b))) == len(b) * 8 / log(58)
93	maxlen := int(float64(len(b))*1.365658237309761) + 1
94	answer := make([]byte, 0, maxlen)
95	mod := new(big.Int)
96	for x.Sign() > 0 {
97		// Calculating with big.Int is slow for each iteration.
98		//    x, mod = x / 58, x % 58
99		//
100		// Instead we can try to do as much calculations on int64.
101		//    x, mod = x / 58^10, x % 58^10
102		//
103		// Which will give us mod, which is 10 digit base58 number.
104		// We'll loop that 10 times to convert to the answer.
105
106		x.DivMod(x, bigRadix10, mod)
107		if x.Sign() == 0 {
108			// When x = 0, we need to ensure we don't add any extra zeros.
109			m := mod.Int64()
110			for m > 0 {
111				answer = append(answer, alphabet[m%58])
112				m /= 58
113			}
114		} else {
115			m := mod.Int64()
116			for i := 0; i < 10; i++ {
117				answer = append(answer, alphabet[m%58])
118				m /= 58
119			}
120		}
121	}
122
123	// leading zero bytes
124	for _, i := range b {
125		if i != 0 {
126			break
127		}
128		answer = append(answer, alphabetIdx0)
129	}
130
131	// reverse
132	alen := len(answer)
133	for i := 0; i < alen/2; i++ {
134		answer[i], answer[alen-1-i] = answer[alen-1-i], answer[i]
135	}
136
137	return string(answer)
138}
139