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