Source code

001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      https://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018package org.apache.commons.codec.binary;
019
020import java.math.BigInteger;
021import java.nio.charset.StandardCharsets;
022
023/**
024 * Provides Base58 encoding and decoding as commonly used in cryptocurrency and blockchain applications.
025 * <p>
026 * 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
027 * commonly used in Bitcoin and other blockchain systems.
028 * </p>
029 * <p>
030 * This implementation accumulates data internally until EOF is signaled, at which point the entire input is converted using BigInteger arithmetic. This is
031 * necessary because Base58 encoding/decoding requires access to the complete data to properly handle leading zeros.
032 * </p>
033 * <p>
034 * This class is thread-safe for read operations but the Context object used during encoding/decoding should not be shared between threads.
035 * </p>
036 * <p>
037 * The Base58 alphabet is:
038 * </p>
039 *
040 * <pre>
041 * 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz
042 * </pre>
043 * <p>
044 * This excludes: {@code 0}, {@code I}, {@code O}, and {@code l}.
045 * </p>
046 *
047 * @see Base58InputStream
048 * @see Base58OutputStream
049 * @see <a href="https://datatracker.ietf.org/doc/html/draft-msporny-base58-03">The Base58 Encoding Scheme draft-msporny-base58-03</a>
050 * @since 1.22.0
051 */
052public class Base58 extends BaseNCodec {
053
054    /**
055     * Builds {@link Base58} instances with custom configuration.
056     */
057    public static class Builder extends AbstractBuilder<Base58, Builder> {
058
059        /**
060         * Constructs a new Base58 builder.
061         */
062        public Builder() {
063            super(ENCODE_TABLE);
064            setDecodeTable(DECODE_TABLE);
065        }
066
067        /**
068         * Builds a new Base58 instance with the configured settings.
069         *
070         * @return a new Base58 codec.
071         */
072        @Override
073        public Base58 get() {
074            return new Base58(this);
075        }
076
077        /**
078         * Creates a new Base58 codec instance.
079         *
080         * @return a new Base58 codec.
081         */
082        @Override
083        public Base58.Builder setEncodeTable(final byte... encodeTable) {
084            super.setDecodeTableRaw(DECODE_TABLE);
085            return super.setEncodeTable(encodeTable);
086        }
087    }
088    private static final BigInteger BASE = BigInteger.valueOf(58);
089
090    private static final byte[] EMPTY = new byte[0];
091
092    /**
093     * Base58 alphabet: 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz
094     * (excludes: 0, I, O, l).
095     */
096    private static final byte[] ENCODE_TABLE = {
097            '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
098            'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a',
099            '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}