This is an automated email from the ASF dual-hosted git repository. garydgregory pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/commons-codec.git
commit 43ba06b3243a59e821ed887a82694022c55c4af2 Author: Gary Gregory <[email protected]> AuthorDate: Thu Aug 6 11:54:51 2026 -0400 Optimize Base58.convertFromBase58(byte[], Context) for speed and temp object allocation. --- src/changes/changes.xml | 1 + .../org/apache/commons/codec/binary/Base58.java | 65 +++++++++++++++++----- .../apache/commons/codec/binary/Base58Test.java | 7 +++ 3 files changed, 60 insertions(+), 13 deletions(-) diff --git a/src/changes/changes.xml b/src/changes/changes.xml index 26a36f9e..7abfb525 100644 --- a/src/changes/changes.xml +++ b/src/changes/changes.xml @@ -47,6 +47,7 @@ The <action> type attribute can be add,update,fix,remove. <!-- FIX --> <action type="fix" dev="ggregory" due-to="Yu Bao, Gary Gregory">Optimize PhoneticEngine.encode(String, LanguageSet) for speed.</action> <action type="fix" dev="ggregory" due-to="Yu Bao, Gary Gregory">RFC1522Codec.decodeText(String) now throws a DecoderException instead of a StringIndexOutOfBoundsException when a separator is missing.</action> + <action type="fix" dev="ggregory" due-to="Yu Bao, Gary Gregory">Optimize Base58.convertFromBase58(byte[], Context) for speed and temp object allocation.</action> <!-- ADD --> <action type="add" dev="ggregory" due-to="Gary Gregory">Add and use PhoneticEngine.Builder and deprecate old constructors.</action> <!-- UPDATE --> diff --git a/src/main/java/org/apache/commons/codec/binary/Base58.java b/src/main/java/org/apache/commons/codec/binary/Base58.java index 7633646a..981b4c99 100644 --- a/src/main/java/org/apache/commons/codec/binary/Base58.java +++ b/src/main/java/org/apache/commons/codec/binary/Base58.java @@ -219,37 +219,76 @@ public class Base58 extends BaseNCodec { /** * Converts Base58 encoded data to binary. * <p> - * Uses BigInteger arithmetic to convert the Base58 string to binary data. Leading characters that match the first Base58 alphabet entry represent leading - * zero bytes in the binary data. + * Uses 32-bit word arithmetic ({@code int[]} with {@code long} carry) to convert the Base58 string to binary data, avoiding {@link BigInteger} and its + * per-digit object allocation. Each Base58 digit is processed left-to-right using Horner's scheme: {@code value = value * 58 + digit}. An + * {@code wordsStart} cursor tracks the leftmost word that contains data, so the inner loop only touches the active portion of the work buffer — the active + * range grows by at most one word per four digits (since log(58)/log(256) < 1), keeping total work well below {@code inputLength²}. + * </p> + * <p> + * At each word position the carry satisfies {@code carry ≤ 57 + 58 × (2³²−1) < 2⁴⁰}, which fits in a Java {@code long}. + * </p> + * <p> + * Leading characters that match the first Base58 alphabet entry each represent a leading zero byte in the output. * </p> * - * @param base58 The Base58 encoded data. - * @param context The context for this decoding operation. + * @param base58 The Base58 encoded data. + * @param context The context for this decoding operation. * @throws IllegalArgumentException if the Base58 data contains invalid characters. */ private void convertFromBase58(final byte[] base58, final Context context) { - BigInteger value = BigInteger.ZERO; - int leadingZeros = 0; final int zero = encodeTable[0] & 0xff; + // Count leading Base58 "zero" characters; each represents a leading zero byte in the output. + int leadingZeros = 0; for (final byte b : base58) { if ((b & 0xff) != zero) { break; } leadingZeros++; } - BigInteger power = BigInteger.ONE; - for (int i = base58.length - 1; i >= leadingZeros; i--) { + // Instead of using BigInteger instances, we use a 32-bit word array. + // This provides ~4x speedup and avoids per-digit object allocation. + // + // Work buffer of 32-bit words, big-endian, right-aligned. + // Upper bound on decoded bytes is base58.length, so (base58.length+3)/4 words suffice. + final int numWords = base58.length + 3 >>> 2; + final int[] words = new int[numWords]; + int wordsStart = numWords; // grows leftward as the value increases + for (int i = leadingZeros; i < base58.length; i++) { final int b = base58[i] & 0xff; final int digit = b < decodeTable.length ? decodeTable[b] : -1; if (digit < 0) { throw new IllegalArgumentException(String.format("Invalid character in Base58 string: 0x%02x", b)); } - value = value.add(BigInteger.valueOf(digit).multiply(power)); - power = power.multiply(BASE); + // value = value * 58 + digit (Horner's scheme over 32-bit words) + long carry = digit; + for (int j = numWords - 1; j >= wordsStart; j--) { + carry += 58L * (words[j] & 0xFFFFFFFFL); + words[j] = (int) carry; + carry >>>= 32; + } + while (carry != 0) { + words[--wordsStart] = (int) carry; + carry >>>= 32; + } + } + // Expand active words to bytes (big-endian), then skip leading zero bytes. + final int activeWords = numWords - wordsStart; + final byte[] raw = new byte[activeWords * 4]; + for (int i = 0; i < activeWords; i++) { + final int w = words[wordsStart + i]; + raw[i * 4] = (byte) (w >>> 24); + raw[i * 4 + 1] = (byte) (w >>> 16); + raw[i * 4 + 2] = (byte) (w >>> 8); + raw[i * 4 + 3] = (byte) w; + } + int rawStart = 0; + while (rawStart < raw.length && raw[rawStart] == 0) { + rawStart++; } - final byte[] decoded = toUnsignedBytes(value); - final byte[] result = new byte[leadingZeros + decoded.length]; - System.arraycopy(decoded, 0, result, leadingZeros, decoded.length); + // Assemble result: leadingZeros zero bytes followed by the decoded value. + final int decodedLength = raw.length - rawStart; + final byte[] result = new byte[leadingZeros + decodedLength]; + System.arraycopy(raw, rawStart, result, leadingZeros, decodedLength); final byte[] buffer = ensureBufferSize(result.length, context); System.arraycopy(result, 0, buffer, context.pos, result.length); context.pos += result.length; diff --git a/src/test/java/org/apache/commons/codec/binary/Base58Test.java b/src/test/java/org/apache/commons/codec/binary/Base58Test.java index 5a0ffb5e..b5ebec5c 100644 --- a/src/test/java/org/apache/commons/codec/binary/Base58Test.java +++ b/src/test/java/org/apache/commons/codec/binary/Base58Test.java @@ -119,6 +119,13 @@ public class Base58Test { assertThrows(IllegalArgumentException.class, () -> Base58.builder().setEncodeTable(Arrays.copyOf(newEncodeTable(), DEFAULT_ALPHABET.length() - 1))); } + @ParameterizedTest + @ValueSource(ints = { 20_000, 40_000, 80_000, 160_000, 320_000 }) + void testDecodeLargeInput(final int n) { + // any valid non-'1' Base58 char + new Base58().decode(ArrayFill.fill(new byte[n], (byte) 'z')); + } + @Test void testEmptyBase58() { byte[] empty = {};
