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.util.Arrays;
22 import java.util.function.BiConsumer;
23
24 /**
25 * Provides Base58 encoding and decoding as commonly used in cryptocurrency and blockchain applications.
26 * <p>
27 * 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
28 * commonly used in Bitcoin and other blockchain systems.
29 * </p>
30 * <p>
31 * This implementation accumulates data internally until EOF is signaled, at which point the entire input is converted using BigInteger arithmetic. This is
32 * necessary because Base58 encoding/decoding requires access to the complete data to properly handle leading zeros.
33 * </p>
34 * <p>
35 * This class is thread-safe for read operations but the Context object used during encoding/decoding should not be shared between threads.
36 * </p>
37 * <p>
38 * The Base58 alphabet is:
39 * </p>
40 *
41 * <pre>
42 * 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz
43 * </pre>
44 * <p>
45 * This excludes: {@code 0}, {@code I}, {@code O}, and {@code l}.
46 * </p>
47 *
48 * @see Base58InputStream
49 * @see Base58OutputStream
50 * @see <a href="https://datatracker.ietf.org/doc/html/draft-msporny-base58-03">The Base58 Encoding Scheme draft-msporny-base58-03</a>
51 * @since 1.22.0
52 */
53 public class Base58 extends BaseNCodec {
54
55 /**
56 * Builds {@link Base58} instances with custom configuration.
57 */
58 public static class Builder extends AbstractBuilder<Base58, Builder> {
59
60 /**
61 * Constructs a new Base58 builder.
62 */
63 public Builder() {
64 super(ENCODE_TABLE);
65 setDecodeTable(DECODE_TABLE);
66 }
67
68 /**
69 * Builds a new Base58 instance with the configured settings.
70 *
71 * @return A new Base58 codec.
72 */
73 @Override
74 public Base58 get() {
75 return new Base58(this);
76 }
77
78 /**
79 * Sets the encode table and derives the matching decode table.
80 *
81 * @param encodeTable The encode table with exactly 58 unique entries, null resets to the default.
82 * @return {@code this} instance.
83 * @throws IllegalArgumentException if the encode table does not contain exactly 58 unique entries.
84 */
85 @Override
86 public Base58.Builder setEncodeTable(final byte... encodeTable) {
87 super.setDecodeTableRaw(toDecodeTable(encodeTable));
88 return super.setEncodeTable(encodeTable);
89 }
90 }
91 private static final BigInteger BASE = BigInteger.valueOf(58);
92
93 private static final int DECODING_TABLE_LENGTH = 256;
94 private static final int ENCODING_TABLE_LENGTH = 58;
95
96 /**
97 * Base58 alphabet: 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz
98 * (excludes: 0, I, O, l).
99 */
100 private static final byte[] ENCODE_TABLE = {
101 '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
102 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a',
103 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'm', 'n', 'o', 'p', 'q', 'r', 's',
104 't', 'u', 'v', 'w', 'x', 'y', 'z'
105 };
106 /**
107 * This array is a lookup table that translates Unicode characters drawn from the "Base58 Alphabet"
108 * into their numeric equivalents (0-57). Characters that are not in the Base58 alphabet are marked
109 * with -1.
110 */
111 // @formatter:off
112 private static final byte[] DECODE_TABLE = {
113 // 0 1 2 3 4 5 6 7 8 9 A B C D E F
114 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 00-0f
115 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 10-1f
116 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 20-2f
117 -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, -1, -1, -1, -1, -1, -1, // 30-3f '1'-'9' -> 0-8
118 -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')
119 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, // 50-5a 'P'-'Z'
120 -1, -1, -1, -1, -1, // 5b-5f
121 -1, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, -1, 44, 45, 46, // 60-6f 'a'-'k', 'm'-'o' (skip 'l')
122 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, // 70-7a 'p'-'z'
123 };
124 // @formatter:on
125
126 /**
127 * Creates a new Builder.
128 *
129 * <p>
130 * To configure a new instance, use a {@link Builder}. For example:
131 * </p>
132 *
133 * <pre>
134 * Base58 base58 = Base58.builder()
135 * .setEncode(true)
136 * .get()
137 * </pre>
138 *
139 * @return A new Builder.
140 */
141 public static Builder builder() {
142 return new Builder();
143 }
144
145 /**
146 * Calculates a decode table for a given encode table.
147 *
148 * @param encodeTable that is used to determine decode lookup table.
149 * @return A new decode table.
150 * @throws IllegalArgumentException if the encode table does not contain exactly 58 unique entries.
151 */
152 private static byte[] calculateDecodeTable(final byte[] encodeTable) {
153 if (encodeTable.length != ENCODING_TABLE_LENGTH) {
154 throw new IllegalArgumentException("encodeTable must have exactly 58 entries.");
155 }
156 final byte[] decodeTable = new byte[DECODING_TABLE_LENGTH];
157 Arrays.fill(decodeTable, (byte) -1);
158 for (int i = 0; i < encodeTable.length; i++) {
159 final int encodedByte = encodeTable[i] & 0xff;
160 if (decodeTable[encodedByte] != -1) {
161 throw new IllegalArgumentException("encodeTable must not contain duplicate entries.");
162 }
163 decodeTable[encodedByte] = (byte) i;
164 }
165 return decodeTable;
166 }
167
168 /**
169 * Gets the decode table that matches the given encode table.
170 *
171 * @param encodeTable that is used to determine decode lookup table.
172 * @return The matching decode table.
173 */
174 private static byte[] toDecodeTable(final byte[] encodeTable) {
175 final byte[] table = encodeTable != null ? encodeTable : ENCODE_TABLE;
176 if (Arrays.equals(table, ENCODE_TABLE)) {
177 return DECODE_TABLE;
178 }
179 return calculateDecodeTable(table);
180 }
181
182 /**
183 * Constructs a Base58 codec used for encoding and decoding.
184 */
185 public Base58() {
186 this(new Builder());
187 }
188
189 /**
190 * Constructs a Base58 codec used for encoding and decoding with custom configuration.
191 *
192 * @param builder The builder with custom configuration.
193 */
194 public Base58(final Builder builder) {
195 super(builder);
196 }
197
198 private void code(final byte[] array, final int offset, final int length, final Context context, final BiConsumer<byte[], Context> consumer) {
199 if (context.eof) {
200 return;
201 }
202 if (length < 0) {
203 context.eof = true;
204 final byte[] accumulate = context.buffer = context.buffer != null ? context.buffer : EMPTY_BYTE_ARRAY;
205 if (accumulate.length > 0) {
206 consumer.accept(accumulate, context);
207 }
208 return;
209 }
210 final byte[] accumulate = context.buffer = context.buffer != null ? context.buffer : EMPTY_BYTE_ARRAY;
211 final byte[] newAccumulated = new byte[accumulate.length + length];
212 if (accumulate.length > 0) {
213 System.arraycopy(accumulate, 0, newAccumulated, 0, accumulate.length);
214 }
215 System.arraycopy(array, offset, newAccumulated, accumulate.length, length);
216 context.buffer = newAccumulated;
217 }
218
219 /**
220 * Converts Base58 encoded data to binary.
221 * <p>
222 * Uses BigInteger arithmetic to convert the Base58 string to binary data. Leading characters that match the first Base58 alphabet entry represent leading
223 * zero bytes in the binary data.
224 * </p>
225 *
226 * @param base58 The Base58 encoded data.
227 * @param context The context for this decoding operation.
228 * @throws IllegalArgumentException if the Base58 data contains invalid characters.
229 */
230 private void convertFromBase58(final byte[] base58, final Context context) {
231 BigInteger value = BigInteger.ZERO;
232 int leadingZeros = 0;
233 final int zero = encodeTable[0] & 0xff;
234 for (final byte b : base58) {
235 if ((b & 0xff) != zero) {
236 break;
237 }
238 leadingZeros++;
239 }
240 BigInteger power = BigInteger.ONE;
241 for (int i = base58.length - 1; i >= leadingZeros; i--) {
242 final int b = base58[i] & 0xff;
243 final int digit = b < decodeTable.length ? decodeTable[b] : -1;
244 if (digit < 0) {
245 throw new IllegalArgumentException(String.format("Invalid character in Base58 string: 0x%02x", b));
246 }
247 value = value.add(BigInteger.valueOf(digit).multiply(power));
248 power = power.multiply(BASE);
249 }
250 final byte[] decoded = toUnsignedBytes(value);
251 final byte[] result = new byte[leadingZeros + decoded.length];
252 System.arraycopy(decoded, 0, result, leadingZeros, decoded.length);
253 final byte[] buffer = ensureBufferSize(result.length, context);
254 System.arraycopy(result, 0, buffer, context.pos, result.length);
255 context.pos += result.length;
256 }
257
258 /**
259 * Converts accumulated binary data to Base58 encoding.
260 * <p>
261 * Uses BigInteger arithmetic to convert the binary data to Base58. Leading zeros in the binary data are represented as the first character in the Base58
262 * alphabet.
263 * </p>
264 *
265 * @param accumulate The binary data to encode.
266 * @param context The context for this encoding operation.
267 * @return The buffer containing the encoded data.
268 */
269 private byte[] convertToBase58(final byte[] accumulate, final Context context) {
270 final StringBuilder base58 = getStringBuilder(accumulate);
271 final byte[] encodedBytes = new byte[base58.length()];
272 for (int i = 0; i < encodedBytes.length; i++) {
273 encodedBytes[i] = (byte) base58.charAt(encodedBytes.length - 1 - i);
274 }
275 final byte[] buffer = ensureBufferSize(encodedBytes.length, context);
276 System.arraycopy(encodedBytes, 0, buffer, context.pos, encodedBytes.length);
277 context.pos += encodedBytes.length;
278 return buffer;
279 }
280
281 /**
282 * Decodes the given Base58 encoded data.
283 * <p>
284 * This implementation accumulates data internally. When length is less than 0 (EOF), the accumulated data is converted from Base58 to binary.
285 * </p>
286 *
287 * @param array The byte array containing Base58 encoded data.
288 * @param offset The offset in the array to start from.
289 * @param length The number of bytes to decode, or negative to signal EOF.
290 * @param context The context for this decoding operation.
291 */
292 @Override
293 void decode(final byte[] array, final int offset, final int length, final Context context) {
294 code(array, offset, length, context, this::convertFromBase58);
295 }
296
297 /**
298 * Encodes the given binary data as Base58.
299 * <p>
300 * This implementation accumulates data internally. When length is less than 0 (EOF), the accumulated data is converted to Base58.
301 * </p>
302 *
303 * @param array The byte array containing binary data to encode.
304 * @param offset The offset in the array to start from.
305 * @param length The number of bytes to encode, or negative to signal EOF.
306 * @param context The context for this encoding operation.
307 */
308 @Override
309 void encode(final byte[] array, final int offset, final int length, final Context context) {
310 code(array, offset, length, context, this::convertToBase58);
311 }
312
313 /**
314 * Builds the Base58 string representation of the given binary data.
315 * <p>
316 * Converts binary data to a BigInteger and divides by 58 repeatedly to get the Base58 digits. Handles leading zeros by counting them and appending the first
317 * character in the Base58 alphabet for each leading zero byte.
318 * </p>
319 *
320 * @param accumulate The binary data to convert.
321 * @return A StringBuilder with the Base58 representation (not yet reversed).
322 */
323 private StringBuilder getStringBuilder(final byte[] accumulate) {
324 BigInteger value = new BigInteger(1, accumulate);
325 int leadingZeros = 0;
326 for (final byte b : accumulate) {
327 if (b != 0) {
328 break;
329 }
330 leadingZeros++;
331 }
332 final StringBuilder base58 = new StringBuilder();
333 while (value.signum() > 0) {
334 final BigInteger[] divRem = value.divideAndRemainder(BASE);
335 base58.append((char) (encodeTable[divRem[1].intValue()] & 0xff));
336 value = divRem[0];
337 }
338 final char zero = (char) (encodeTable[0] & 0xff);
339 for (int i = 0; i < leadingZeros; i++) {
340 base58.append(zero);
341 }
342 return base58;
343 }
344
345 /**
346 * Returns whether or not the {@code octet} is in the Base58 alphabet.
347 *
348 * @param value The value to test.
349 * @return {@code true} if the value is defined in the Base58 alphabet {@code false} otherwise.
350 */
351 @Override
352 protected boolean isInAlphabet(final byte value) {
353 final int octet = value & 0xff;
354 return octet < decodeTable.length && decodeTable[octet] != -1;
355 }
356 }