base58.mx raw
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
5 package base58
6
7 import (
8 "math/big"
9 )
10
11 //go:generate go run genalphabet.go
12
13 var 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
27 var 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.
30 func Decode(b string) []byte {
31 answer := big.NewInt(0)
32 scratch := &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 if v > 255 {
59 return []byte("")
60 }
61
62 tmp := b58[v]
63 if tmp == 255 {
64 return []byte("")
65 }
66 total = total*58 + uint64(tmp)
67 }
68
69 answer.Mul(answer, bigRadix[n])
70 scratch.SetUint64(total)
71 answer.Add(answer, scratch)
72
73 t = t[n:]
74 }
75
76 tmpval := answer.Bytes()
77
78 var numZeros int
79 for numZeros = 0; numZeros < len(b); numZeros++ {
80 if b[numZeros] != alphabetIdx0 {
81 break
82 }
83 }
84 flen := numZeros + len(tmpval)
85 val := []byte{:flen}
86 copy(val[numZeros:], tmpval)
87
88 return val
89 }
90
91 // Encode encodes a byte slice to a modified base58 string.
92 func Encode(b []byte) string {
93 x := &big.Int{}
94 x.SetBytes(b)
95
96 // maximum length of output is log58(2^(8*len(b))) == len(b) * 8 / log(58)
97 maxlen := int(float64(len(b))*1.365658237309761) + 1
98 answer := []byte{:0:maxlen}
99 mod := &big.Int{}
100 for x.Sign() > 0 {
101 // Calculating with big.Int is slow for each iteration.
102 // x, mod = x / 58, x % 58
103 //
104 // Instead we can try to do as much calculations on int64.
105 // x, mod = x / 58^10, x % 58^10
106 //
107 // Which will give us mod, which is 10 digit base58 number.
108 // We'll loop that 10 times to convert to the answer.
109
110 x.DivMod(x, bigRadix10, mod)
111 if x.Sign() == 0 {
112 // When x = 0, we need to ensure we don't add any extra zeros.
113 m := mod.Int64()
114 for m > 0 {
115 answer = append(answer, Ciphers[m%58])
116 m /= 58
117 }
118 } else {
119 m := mod.Int64()
120 for i := 0; i < 10; i++ {
121 answer = append(answer, Ciphers[m%58])
122 m /= 58
123 }
124 }
125 }
126
127 // leading zero bytes
128 for _, i := range b {
129 if i != 0 {
130 break
131 }
132 answer = append(answer, alphabetIdx0)
133 }
134
135 // reverse
136 alen := len(answer)
137 for i := 0; i < alen/2; i++ {
138 answer[i], answer[alen-1-i] = answer[alen-1-i], answer[i]
139 }
140
141 return string(answer)
142 }
143