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