1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package org.apache.commons.codec.binary;
19
20 import java.math.BigInteger;
21 import java.nio.charset.StandardCharsets;
22
23 /**
24 * Provides Base58 encoding and decoding as commonly used in cryptocurrency and blockchain applications.
25 * <p>
26 * Base58 is a binary-to-text encoding scheme that uses a 58-character alphabet to encode data. It avoids characters that can be confused (0/O, I/l, +/) and is
27 * commonly used in Bitcoin and other blockchain systems.
28 * </p>
29 * <p>
30 * This implementation accumulates data internally until EOF is signaled, at which point the entire input is converted using BigInteger arithmetic. This is
31 * necessary because Base58 encoding/decoding requires access to the complete data to properly handle leading zeros.
32 * </p>
33 * <p>
34 * This class is thread-safe for read operations but the Context object used during encoding/decoding should not be shared between threads.
35 * </p>
36 * <p>
37 * The Base58 alphabet is:
38 * </p>
39 *
40 * <pre>
41 * 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz
42 * </pre>
43 * <p>
44 * This excludes: {@code 0}, {@code I}, {@code O}, and {@code l}.
45 * </p>
46 *
47 * @see Base58InputStream
48 * @see Base58OutputStream
49 * @see <a href="https://datatracker.ietf.org/doc/html/draft-msporny-base58-03">The Base58 Encoding Scheme draft-msporny-base58-03</a>
50 * @since 1.22.0
51 */
52 public class Base58 extends BaseNCodec {
53
54 /**
55 * Builds {@link Base58} instances with custom configuration.
56 */
57 public static class Builder extends AbstractBuilder<Base58, Builder> {
58
59 /**
60 * Constructs a new Base58 builder.
61 */
62 public Builder() {
63 super(ENCODE_TABLE);
64 setDecodeTable(DECODE_TABLE);
65 }
66
67 /**
68 * Builds a new Base58 instance with the configured settings.
69 *
70 * @return a new Base58 codec.
71 */
72 @Override
73 public Base58 get() {
74 return new Base58(this);
75 }
76
77 /**
78 * Creates a new Base58 codec instance.
79 *
80 * @return a new Base58 codec.
81 */
82 @Override
83 public Base58.Builder setEncodeTable(final byte... encodeTable) {
84 super.setDecodeTableRaw(DECODE_TABLE);
85 return super.setEncodeTable(encodeTable);
86 }
87 }
88 private static final BigInteger BASE = BigInteger.valueOf(58);
89
90 private static final byte[] EMPTY = new byte[0];
91
92 /**
93 * Base58 alphabet: 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz
94 * (excludes: 0, I, O, l).
95 */
96 private static final byte[] ENCODE_TABLE = {
97 '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
98 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a',
99 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'm', 'n', 'o', 'p', 'q', 'r', 's',
100 't', 'u', 'v', 'w', 'x', 'y', 'z'
101 };
102 /**
103 * This array is a lookup table that translates Unicode characters drawn from the "Base58 Alphabet"
104 * into their numeric equivalents (0-57). Characters that are not in the Base58 alphabet are marked
105 * with -1.
106 */
107 // @formatter:off
108 private static final byte[] DECODE_TABLE = {
109 // 0 1 2 3 4 5 6 7 8 9 A B C D E F
110 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 00-0f
111 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 10-1f
112 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 20-2f
113 -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, -1, -1, -1, -1, -1, -1, // 30-3f '1'-'9' -> 0-8
114 -1, 9, 10, 11, 12, 13, 14, 15, 16, -1, 17, 18, 19, 20, 21, -1, // 40-4f 'A'-'N', 'P'-'Z' (skip 'I' and 'O')
115 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, // 50-5a 'P'-'Z'
116 -1, -1, -1, -1, -1, // 5b-5f
117 -1, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, -1, 44, 45, 46, // 60-6f 'a'-'k', 'm'-'o' (skip 'l')
118 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, // 70-7a 'p'-'z'
119 };
120 // @formatter:on
121
122 /**
123 * Creates a new Builder.
124 *
125 * <p>
126 * To configure a new instance, use a {@link Builder}. For example:
127 * </p>
128 *
129 * <pre>
130 * Base58 base58 = Base58.builder()
131 * .setEncode(true)
132 * .get()
133 * </pre>
134 *
135 * @return a new Builder.
136 */
137 public static Builder builder() {
138 return new Builder();
139 }
140
141 /**
142 * Constructs a Base58 codec used for encoding and decoding.
143 */
144 public Base58() {
145 this(new Builder());
146 }
147
148 /**
149 * Constructs a Base58 codec used for encoding and decoding with custom configuration.
150 *
151 * @param builder the builder with custom configuration.
152 */
153 public Base58(final Builder builder) {
154 super(builder);
155 }
156
157 /**
158 * Converts Base58 encoded data to binary.
159 * <p>
160 * Uses BigInteger arithmetic to convert the Base58 string to binary data. Leading '1' characters in the Base58 encoding represent leading zero bytes in the
161 * binary data.
162 * </p>
163 *
164 * @param base58 the Base58 encoded data.
165 * @param context the context for this decoding operation.
166 * @throws IllegalArgumentException if the Base58 data contains invalid characters.
167 */
168 private void convertFromBase58(final byte[] base58, final Context context) {
169 BigInteger value = BigInteger.ZERO;
170 int leadingOnes = 0;
171 for (final byte b : base58) {
172 if (b != '1') {
173 break;
174 }
175 leadingOnes++;
176 }
177 BigInteger power = BigInteger.ONE;
178 for (int i = base58.length - 1; i >= leadingOnes; i--) {
179 final byte b = base58[i];
180 final int digit = b < DECODE_TABLE.length ? DECODE_TABLE[b] : -1;
181 if (digit < 0) {
182 throw new IllegalArgumentException(String.format("Invalid character in Base58 string: 0x%02x", b));
183 }
184 value = value.add(BigInteger.valueOf(digit).multiply(power));
185 power = power.multiply(BASE);
186 }
187 byte[] decoded = value.equals(BigInteger.ZERO) ? EMPTY : value.toByteArray();
188 if (decoded.length > 1 && decoded[0] == 0) {
189 final byte[] tmp = new byte[decoded.length - 1];
190 System.arraycopy(decoded, 1, tmp, 0, tmp.length);
191 decoded = tmp;
192 }
193 final byte[] result = new byte[leadingOnes + decoded.length];
194 System.arraycopy(decoded, 0, result, leadingOnes, decoded.length);
195 final byte[] buffer = ensureBufferSize(result.length, context);
196 System.arraycopy(result, 0, buffer, context.pos, result.length);
197 context.pos += result.length;
198 }
199
200 /**
201 * Converts accumulated binary data to Base58 encoding.
202 * <p>
203 * Uses BigInteger arithmetic to convert the binary data to Base58. Leading zeros in the binary data are represented as '1' characters in the Base58
204 * encoding.
205 * </p>
206 *
207 * @param accumulate the binary data to encode.
208 * @param context the context for this encoding operation.
209 * @return the buffer containing the encoded data.
210 */
211 private byte[] convertToBase58(final byte[] accumulate, final Context context) {
212 final StringBuilder base58 = getStringBuilder(accumulate);
213 final String encoded = base58.reverse().toString();
214 final byte[] encodedBytes = encoded.getBytes(StandardCharsets.UTF_8);
215 final byte[] buffer = ensureBufferSize(encodedBytes.length, context);
216 System.arraycopy(encodedBytes, 0, buffer, context.pos, encodedBytes.length);
217 context.pos += encodedBytes.length;
218 return buffer;
219 }
220
221 /**
222 * Decodes the given Base58 encoded data.
223 * <p>
224 * This implementation accumulates data internally. When length is less than 0 (EOF), the accumulated data is converted from Base58 to binary.
225 * </p>
226 *
227 * @param array the byte array containing Base58 encoded data.
228 * @param offset the offset in the array to start from.
229 * @param length the number of bytes to decode, or negative to signal EOF.
230 * @param context the context for this decoding operation.
231 */
232 @Override
233 void decode(final byte[] array, final int offset, final int length, final Context context) {
234 if (context.eof) {
235 return;
236 }
237 if (length < 0) {
238 context.eof = true;
239 final byte[] accumulate = context.buffer = context.buffer != null ? context.buffer : EMPTY;
240 if (accumulate.length > 0) {
241 convertFromBase58(accumulate, context);
242 }
243 return;
244 }
245 final byte[] accumulate = context.buffer = context.buffer != null ? context.buffer : EMPTY;
246 final byte[] newAccumulated = new byte[accumulate.length + length];
247 if (accumulate.length > 0) {
248 System.arraycopy(accumulate, 0, newAccumulated, 0, accumulate.length);
249 }
250 System.arraycopy(array, offset, newAccumulated, accumulate.length, length);
251 context.buffer = newAccumulated;
252 }
253
254 /**
255 * Encodes the given binary data as Base58.
256 * <p>
257 * This implementation accumulates data internally. When length is less than 0 (EOF), the accumulated data is converted to Base58.
258 * </p>
259 *
260 * @param array the byte array containing binary data to encode.
261 * @param offset the offset in the array to start from.
262 * @param length the number of bytes to encode, or negative to signal EOF.
263 * @param context the context for this encoding operation.
264 */
265 @Override
266 void encode(final byte[] array, final int offset, final int length, final Context context) {
267 if (context.eof) {
268 return;
269 }
270 if (length < 0) {
271 context.eof = true;
272 final byte[] accumulate = context.buffer = context.buffer != null ? context.buffer : EMPTY;
273 convertToBase58(accumulate, context);
274 return;
275 }
276 final byte[] accumulate = context.buffer = context.buffer != null ? context.buffer : EMPTY;
277 final byte[] newAccumulated = new byte[accumulate.length + length];
278 if (accumulate.length > 0) {
279 System.arraycopy(accumulate, 0, newAccumulated, 0, accumulate.length);
280 }
281 System.arraycopy(array, offset, newAccumulated, accumulate.length, length);
282 context.buffer = newAccumulated;
283 }
284
285 /**
286 * Builds the Base58 string representation of the given binary data.
287 * <p>
288 * Converts binary data to a BigInteger and divides by 58 repeatedly to get the Base58 digits. Handles leading zeros by counting them and appending '1' for
289 * each leading zero byte.
290 * </p>
291 *
292 * @param accumulate the binary data to convert.
293 * @return a StringBuilder with the Base58 representation (not yet reversed).
294 */
295 private StringBuilder getStringBuilder(final byte[] accumulate) {
296 BigInteger value = new BigInteger(1, accumulate);
297 int leadingZeros = 0;
298 for (final byte b : accumulate) {
299 if (b != 0) {
300 break;
301 }
302 leadingZeros++;
303 }
304 final StringBuilder base58 = new StringBuilder();
305 while (value.signum() > 0) {
306 final BigInteger[] divRem = value.divideAndRemainder(BASE);
307 base58.append((char) ENCODE_TABLE[divRem[1].intValue()]);
308 value = divRem[0];
309 }
310 for (int i = 0; i < leadingZeros; i++) {
311 base58.append('1');
312 }
313 return base58;
314 }
315
316 /**
317 * Returns whether or not the {@code octet} is in the Base58 alphabet.
318 *
319 * @param value The value to test.
320 * @return {@code true} if the value is defined in the Base58 alphabet {@code false} otherwise.
321 */
322 @Override
323 protected boolean isInAlphabet(final byte value) {
324 return isInAlphabet(value, DECODE_TABLE);
325 }
326 }